Re: git describe weird behaviour

From: Miklos Vajna <vmiklos@frugalware.org>
Date: Nov 10, 2010, 14:03 UTC
Message-ID: <20101110140334.GJ22105@genesis.frugalware.org>
In-Reply-To: <20101110041428.GA8955@sigill.intra.peff.net>

On Tue, Nov 09, 2010 at 11:14:28PM -0500, Jeff King <peff@peff.net> wrote:

> we had to travel to get here. Looking at the frugalware history in gitk,
> you might be triggering this; you have a history with just a few merges,
> but extremely long chains of commits on each branch. Repos like linux or
> git.git are a bit bushier in the shape of the graph.

Agreed.

Actually I thought git describe is just a C version of something like:

- run git log, find the first reachable tag (1.4pre1 in this case)
- git rev-list 1.4pre1..|wc -l (880 in this case)
- append "-g<hash>" to make it still unique

Then it turned out it's a bit more complicated, so I mailed the list. :)

> The patch below implements that in a very rough-and-dirty way. It does
> find the 1.4 tag in your repository that you expect. However:

Yes, works here as well:

$ ~/git/git/git describe 1.4pre1-210-g48b67cd

Show 13 quoted lines

>   2. I am getting nonsensical results when trying it in git.git. It
>      really wants to point me to gitgui tags, which makes no sense. So
>      clearly there is a bug, or my idea is flawed somehow. But it's too
>      late to think about anymore tonight. :)
> 
> -Peff
> 
> PS This would be a much simpler algorithm to write in a depth-first way.
>    But that would also involve traversing the entire graph down to the
>    roots, which we try to avoid.  Which reminds me of my "tag
>    --contains" depth first algorithm, and gives me some ideas on how to
>    make it work in a breadth-first way. So even if my idea here is
>    flawed, this thinking hasn't been completely fruitless. :)

Hm, but can't we way git describe does history walk in a --first-parent way? It might not be efficient, but what may work is to:

- traverse the history by using the first parrents only to find the
  first reachable tag (this way you will never hit git-gui tags)
- count the commits from the first tag till HEAD by traversing the other
  parents as well

To sum up, I think your patch is great about it picks up the right tag for me, though:

$ git rev-list 1.4pre1..|wc -l 880 <- this is what I would expect in the git describe output $ git rev-list --first-parent 1.4pre1..|wc -l 569 <- this is less informative, though probably is faster to produce (we may have this info already when searching for the first tag) $ ~/git/git/git describe 1.4pre1-210-g48b67cd <- an even smaller number you give. :)

Thanks!