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:

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