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

Kirill Smelkov [off-list ref] writes:

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.

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

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.