Re: history damage in linux.git

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

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Thu, Apr 21, 2016 at 9:36 AM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
>>
>> This seems to be a git bug.
>>
>> That commit aed06b9 can also be described as
>>
>>     v3.13-rc7~9^2~14^2~42
>>
>> so describing it as 'v4.6-rc1~9^2~792' is clearly not closer in any way.
>
> Hmm. I think I see what's up. The git distance function has a special
> hack for preferring first-parent traversal, introduced long long ago
> with commit ac076c29ae8d ("name-rev: Fix non-shortest description").
>
> Changing that
>
>   #define MERGE_TRAVERSAL_WEIGHT 65535
>
> to be a smaller value makes git find the shorter path.
>
> I do not know what the correct fix is, though.

I think avoiding side branches to describe with the weight is a
right thing to do, i.e. if you have this history:

    X---o---o---o---o---v4.6
     \             /
      o-----------o

you do not want to explain X as "v4.6~^2~2", and instead you want it
as "v4.6~5", even though the former is 4 hops while the latter is 5
hops (which is longer).

But when comparing a name based on v4.6 (which I think the algorithm
with the weight heuristics would choose v4.6~5) and another name
based on v3.13, I suspect that we compare them with number of hops
with the weight heuristics, and that is what gives us a wrong
result, isn't it?

I think it should instead compare the number of true hops.

v3.13-rc7~9^2~14^2~42 = 9 + 1 + 14 + 1 + 42 = 67 hops from v3.13
v4.6-rc1~9^2~792 = 9 + 1 + 792 = 802 hops from v4.6-rc1