Re: [PATCH v2 18/19] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well

[Junio C Hamano <gitster@pobox.com>]

Kirill Smelkov <kirr@navytux.spb.ru> writes:

>> > +			if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {
>> > +				for (i = 0; i < nparent; ++i)
>> > +					if (tp[i].entry.mode & S_IFXMIN_NEQ)
>> > +						goto skip_emit_tp;
>> > +			}
>> > +
>> > +			p = emit_path(p, base, opt, nparent,
>> > +					/*t=*/NULL, tp, imin);
>> > +
>> > +		skip_emit_tp:
>> > +			/* ∀ xk=ximin  xk↓ */
>> > +			update_tp_entries(tp, nparent);
>> 
>> There are parents whose path sort earlier than what is in 't'
>> (i.e. they were lost in the result---we would want to show
>> removal).  What makes us jump to the skip label?
>> 
>>     We are looking at path in 't', and some parents have paths that
>>     sort earlier than that path.  We will not go to skip label if
>>     any one of the parent's entry sorts after some other parent (or
>>     the parent in question has ran out its entries), which means we
>>     show the entry from the parents only when all the parents have
>>     that same path, which is missing from 't'.
>> 
>> I am not sure if I am reading this correctly, though.
>> 
>> For the two-way diff, the above degenerates to "show all parent
>> entries that come before the first entry in 't'", which is correct.
>> For the combined diff, the current intersect_paths() makes sure that
>> each path appears in all the pair-wise diff between t and tp[],
>> which again means that the above logic match the current behaviour.
>
> Yes, correct (modulo we *will* go to skip label if any one of the
> parent's entry sorts after some other parent). By definition of combined
> diff we show a path only if it shows in every diff D(T,Pi), and if 
>
>     2.1) ∃j: pj > p[imin]  ->  "-p[imin]" ∉ D(T,Pj)  ->  D += ø;  ∀ pi=p[imin]  pi↓
>
> some pj sorts after p[imin] that would mean that Pj does not have
> p[imin] and since t > p[imin] (which means T does not have p[imin]
> either) diff D(T,Pj) does not have p[imin]. And because of that we know
> the whole combined-diff will not have p[imin] as, by definition,
> combined diff is sets intersection and one of the sets does not have
> that path.
>
>   ( In usual words p[imin] is not changed between Pj..T - it was
>     e.g. removed in Pj~, so merging parents to T does not bring any new
>     information wrt path p[imin] and that is why we do not want to show
>     p[imin] in combined-diff output - no new change about that path )
>
> So nothing to append to the output, and update minimum tree entries,
> preparing for the next step.

That's all in line with the current and traditional definition of
combined diff.

This is a tangent that is outside the scope of this current topic,
but I wonder if you found it disturbing that we treat the result 't'
that has a path and the result 't' that does not have a path with
respect to a parent that does not have the path in a somewhat
assymmetric way.

With a merge M between commits A and B, where they all have the same
path with different contents, we obviously show that path in the
combined diff format.  A merge N that records exactly the same tree
as M that merges the same commits A and B plus another commit C that
does not have that path still shows the combined diff, with one
extra column to express "everything in the result N has been added
with respect to C which did not have the path at all".

However, a merge O between the same commits A and B, where A and B
have a path and O loses it, shows the path in the combined format.
A merge P among the same A, B and an extra parent C that does not
have that path ceases to show it (this is the assymmetry).

It is a natural extension of "Do not show the path when the result
matches one of the parent" rule, and in this case the result P takes
contents, "the path does not exist", from one parent "C", so it is
internally consistent, and I originally designed it that way on
purpose, but somehow it feels a bit strange.