Re: Funny 'git describe --contains' output

> Junio C Hamano <gitster@pobox.com> writes:
> 
> > Greg KH <gregkh@linuxfoundation.org> writes:
> >
> >> In the Linux kernel tree, commit 0136db586c028f71e7cc21cc183064ff0d5919
> >> is a bit "odd".
> >>
> >> If I go to look to see what release it was in, I normally do:
> >> 	$ git describe --contains 0136db586c028f71e7cc21cc183064ff0d5919
> >> 	v3.6-rc1~59^2~56^2~76
> >> ...
> >> Any ideas?
> >
> > That is 59 + 1 + 56 + 1 + 76 = 193 steps away from the tag v3.6-rc1.
> >
> > $ git name-rev --refs=refs/tags/v3.5-rc1 0136db58
> > 0136db58 tags/v3.5-rc1~83^2~81^2~76
> >
> > which is 83 + 1 + 81 + 1 + 76 = 242 steps away from that tag.
> >
> > So it _is_ odd that the newly tagged tip merged a branch that had
> > smaller development since it merged the commit, but name-rev seems
> > to be measuring the steps it takes from the tags to reach the commit
> > and giving us the one that gives the shortest path correctly.
> >
> > Obviously, that is not the same as "which tag is the oldest one
> > among the ones that can reach this commit?"
> 
> As is usual for what I say, the above is an explanation of what we
> are seeing, not necessarily a justification.
> 
> Given a history of this shape:
> 
>         o---o---o---o TONS!!!
>                      \
>  ---o--o--o--o--o--Y--o---o---Z
>      \   /               /
>       \ /               /
>        X---------------o
> 
> where Y is v3.5-rc1 and Z is v3.6-rc1, "name-rev X" measures the
> distance of the shortest path between Z and X (Z^^2^ = 3 steps away)
> and between Y and X (Y~3^2 = 4 steps away), and uses the tag with
> the shortest path.
> 
> But in order to answer "which is the earlier tag that merges X",
> what "name-rev" measures is not very interesting.
> 
> What we want to see is the tag whose "weight" (imagine these commits
> are beads on strings, and you hold the tag between your fingers and
> lift it, pulling all the commits behind it on the history) is the
> smallest and reaches the commit X in question.  The distance on the
> shortest path to X totally ignores tons of merges that went into the
> mainline between Y and Z.  That is what makes name-rev not useful
> for this purpose.
> 
> That "weight" is what Linus's "rev-list | wc -l" showed, but it is
> fairly expensive to compute.  We do have a code that computes such
> weight in the history bisection code (it computes this exact weight
> for each and every commit that is still suspect, and picks the one
> that is half-way).  We know how to compute it, but I suspect that
> applying that code naively to name-rev would make it unusably slow.