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

On Mon, Apr 07, 2014 at 10:29:46AM -0700, Junio C Hamano wrote:

Kirill Smelkov [off-list ref] writes:

quoted

The following
...
maybe looks a bit simpler, but calls tree_entry_pathcmp twice more times.

Besides for important nparent=1 case we were not calling
tree_entry_pathcmp at all and here we'll call it once, which would slow
execution down a bit, as base_name_compare shows measurable enough in profile.
To avoid that we'll need to add 'if (i==imin) continue' and this won't
be so simple then. And for general nparent case, as I've said, we'll be
calling tree_entry_pathcmp twice more times...

Because of all that I'd suggest to go with my original version.

OK.

Thanks.

quoted

... After some break on the topic,
with a fresh eye I see a lot of confusion goes from the notation I've
chosen initially (because of how I was reasoning about it on paper, when
it was in flux) - i.e. xi for x[imin] and also using i as looping
variable. And also because xi was already used for x[imin] I've used
another letter 'k' denoting all other x'es, which leads to confusion...


I propose we do the following renaming to clarify things:

    A/a     ->      T/t     (to match resulting tree t name in the code)
    X/x     ->      P/p     (to match parents trees tp in the code)
    i       ->      imin    (so that i would be free for other tasks)

then the above (with a prologue) would look like

---- 8< ----
 *       T     P1       Pn
 *       -     -        -
 *      |t|   |p1|     |pn|
 *      |-|   |--| ... |--|      imin = argmin(p1...pn)
 *      | |   |  |     |  |
 *      |-|   |--|     |--|
 *      |.|   |. |     |. |
 *       .     .        .
 *       .     .        .
 *
 * at any time there could be 3 cases:
 *
 *      1)  t < p[imin];
 *      2)  t > p[imin];
 *      3)  t = p[imin].
 *
 * Schematic deduction of what every case means, and what to do, follows:
 *
 * 1)  t < p[imin]  ->  ∀j t ∉ Pj  ->  "+t" ∈ D(T,Pj)  ->  D += "+t";  t↓
 *
 * 2)  t > p[imin]
 *
 *     2.1) ∃j: pj > p[imin]  ->  "-p[imin]" ∉ D(T,Pj)  ->  D += ø;  ∀ pi=p[imin]  pi↓
 *     2.2) ∀i  pi = p[imin]  ->  pi ∉ T  ->  "-pi" ∈ D(T,Pi)  ->  D += "-p[imin]";  ∀i pi↓
 *
 * 3)  t = p[imin]
 *
 *     3.1) ∃j: pj > p[imin]  ->  "+t" ∈ D(T,Pj)  ->  only pi=p[imin] remains to investigate
 *     3.2) pi = p[imin]  ->  investigate δ(t,pi)
 *      |
 *      |
 *      v
 *
 *     3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø  ->
 *
 *                       ⎧δ(t,pi)  - if pi=p[imin]
 *              ->  D += ⎨
 *                       ⎩"+t"     - if pi>p[imin]
 *
 *
 *     in any case t↓  ∀ pi=p[imin]  pi↓
...
now xk is gone and i matches p[i] (= pi) etc so variable names correlate
to algorithm description better.

Does that maybe clarify things?

That sounds more consistent (modulo perhaps s/argmin/min/ at the
beginning?).

Thanks. argmin is there on purpose - min(p1...pn) is the minimal p, and
argmin(p1...pn) is imin such that p[imin] is minimal. As we are finding
the index of the minimal element we should use argmin.

quoted

P.S. Sorry for maybe some crept-in mistakes - I've tried to verify it
thoroughly, but am too sleepy to be completely sure. On the other hand I
think and hope the patch should be ok.

Thanks and do not be sorry for "mistakes"---we have the review
process exactly for catching them.

Thanks, I appreciate that.


On Mon, Apr 07, 2014 at 11:07:47AM -0700, Junio C Hamano wrote:

Kirill Smelkov [off-list ref] writes:

quoted

quoted

quoted

+			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.

Ok.

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).

Symmetry properties are very important and if something does not fit into
symmetry - then something somewhere is really wrong for sure, but I
think there is no asymmetry here. In your example

      M∆∙    N∆∙
     / \ . '''
    / .'\  '  '
    A∆   B∙    Cø
    \ ''/. '  '
     \ /   '''
      Oø     Pø

let's say a path can be:

    ø   - empty
    ∆   - triangle
    ∙   - bullet
    ∆∙  - triangle+bullet

then some symmetry operation is

    ∆∙  <-> ø
    ∙   <-> ∙
    ∆   <-> ∆

so you "mirror" ∆∙ to ø (M,N->O,P), and so ø is mirrored back to ∆∙
(O,P->M,N). But then, when we mirror the whole graph, Cø should be
mirrored to C'∆∙ and then that would be correct:

    A∆   B∙    C'∆∙
    \ ''/. '  '
     \ /   '''
      Oø     Pø

P to A,B,C' would show the path as N to A,B,C(without')


In other words a merge P among the same A, B and extra parent C' with
"contains everything" content is symmetrical to merge N to A,B and C
with empty content.

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.

I hope it does not fill strange once the true symmetry is discovered,
and also P does not add a change compared to C, so the combined diff
should be empty as no new information is present in a merge itself.

A bit unusual on the first glance, but not strange, once you are used to
it and consistent.

Thanks,
Kirill