RE: [BUG] `git describe` doesn't traverse the graph in topological order

From: rsbecker@nexbridge.com <rsbecker@nexbridge.com>
Date: Sep 22, 2023, 19:27 UTC
Message-ID: <033c01d9ed8a$c6916f30$53b44d90$@nexbridge.com>
In-Reply-To: <ZQ3leoLhljc+P5wP@farprobe>

On Friday, September 22, 2023 3:06 PM, Ben Boeckel wrote:

Show 16 quoted lines

>On Fri, Sep 22, 2023 at 14:49:58 -0400, rsbecker@nexbridge.com wrote:
>> On Friday, September 22, 2023 2:44 PM, Ben Boeckel wrote:
>> >Yes. It is explained that the commit date stored is only to 1 second
>> >granularity. Since the commits are stored in commit-date, an equal
>> >commit date ends up "twisting" the history and traversing some ancestors of
>commits before the commits themsevles.
>> >This loses the "seen" bit tracking that is done and ends up labeling
>> >way more commits as "not part of" ancestors. By sleeping for a
>> >second, the commit dates can be totally ordered reliably.
>>
>> This is going to be awkward to resolve as time_t only resolves
>> (portably) to 1 second intervals. I still would prefer the resolution
>> to be path-based rather than time-based.
>
>I certainly agree, but I'm not sure of the best way of doing that. Do we create/load a
>commit graph and use that for resolving insertion order into the commit heap?

I actually thought it worked that way. This may end up in a bigger change than fixing the issue because --first-parent does not appear to be sufficient to resolve the correct tag from your graph. My thought on using multiple commitish values to do that may help, but implementing that could lead to an O(n*m) scan (n=max commit tree width, m=depth to tag), plus a commitish hash lookup.