{"thread":{"id":"60108","subject":"[BUG] `git describe` doesn't traverse the graph in topological order","startedAt":"2023-08-12T19:37:04Z","lastAt":"2026-02-28T06:11:53Z","messageCount":20,"participants":["Ben Boeckel","rsbecker@nexbridge.com","'Ben Boeckel'","Kristoffer Haugsbakk","Junio C Hamano","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"480631","messageId":"ZNffWAgldUZdpQcr@farprobe","threadId":"60108","inReplyTo":null,"subject":"[BUG] `git describe` doesn't traverse the graph in topological order","fromName":"Ben Boeckel","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-08-12T19:36:56Z","receivedAt":"2023-08-12T19:37:04Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"Hi,\n\nI found an issue where `git describe` doesn't find a \"closer\" tag than\nanother tag as the correct one to base the description off of. I have a\nreproducer, but I'll first give details of the real world issue.\n\nRepository: https://gitlab.kitware.com/vtk/vtk.git\n`master` as of: dedf87b3a1b7e5be5d8cdb46b37ad3030590b8ac\n\n$ git rev-parse HEAD\ndedf87b3a1b7e5be5d8cdb46b37ad3030590b8ac\n$ git rev-parse HEAD~2^2\nda2482f716310fc59ac4be42ce977f6badc6af95\n$ git rev-prase v9.3.0.rc1\nf150d52568f4e00aa9c8b1568a521a08ded8d4cb\n$ git rev-prase v9.3.0.rc1^{commit}\nda2482f716310fc59ac4be42ce977f6badc6af95\n$ git rev-parse HEAD~2^2~2\n0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5\n$ git rev-prase v9.3.0.rc0\ne5e13b14629d445bf65d5f8a181920ed9b97d54c\n$ git rev-prase v9.3.0.rc0^{commit}\n0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5\n$ git describe HEAD\nv9.3.0.rc0-56-gdedf87b3a1\n$ git describe --matches v9.3.0.rc1 HEAD\nv9.3.0.rc1-86876-gdedf87b3a1\n\nAs you can see:\n\n- v9.3.0.rc1 is \"closer\" to `HEAD` than v9.3.0.rc0 (created as a\n  workaround for this bug; v9.2.6 is otherwise reported)\n- v9.3.0.rc0 is an ancestor of v9.3.0.rc1\n- Both v9.3.0.rc0 and v9.3.0.rc1 are ancestors of `HEAD`\n- `git describe` reports that `HEAD` is \"closest\" to v9.3.0.rc0\n- Forcing the issue and asking for v9.3.0.rc1 shows that it thinks there\n  are almost 87000 commits somehow not on that commit.\n\nI have a reproducer script attached. It reproduces back to 2.9.0 and\nprobably before. 2.8.0 didn't support the structure hiding that newer\nOpenSSL 1.1 has done and given that it's at least that old, I don't\nthink it matters too much for backporting or anything like that.\n\nI instrumented `git describe` with some `printf` debugging (diff\nattached) and found out that the commit traversal is not happening in\ntopological order. I suspect that this is the root cause of the issue:\n\n    looking at commit 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5\n    depth of 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5: 16\n    find order of 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5: 2\n    setting flag 4 for commit 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5\n    flag for 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5: 5\n    pushing depth of da2482f716310fc59ac4be42ce977f6badc6af95 because of 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5 (flag_within): 16\n    setting flag 5 for commit d478d2e22e81ee2602035fe1d731b402d9b4eda7 due to ancestry\n\n    looking at commit 1c3d839dac92761ae0866e23d89bdc8ee690de08\n    depth of 1c3d839dac92761ae0866e23d89bdc8ee690de08: 17\n    find order of 1c3d839dac92761ae0866e23d89bdc8ee690de08: 3\n    setting flag 8 for commit 1c3d839dac92761ae0866e23d89bdc8ee690de08\n    flag for 1c3d839dac92761ae0866e23d89bdc8ee690de08: b\n    pushing depth of 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5 because of 1c3d839dac92761ae0866e23d89bdc8ee690de08 (flag_within): 17\n    setting flag f for commit 0a77d7cf4fdbf489ee5d38c6fec6517574cdaeb5 due to ancestry\n\nIt looks at 0a77d7cf4 before it looks at 1c3d839da (which is\nv9.3.0.rc1~), but 1c3d839da~ *is* 0a77d7cf4. Because 0a77d7cf4 has\nalready passed on its presence flags to its parent(s), the update\nperformed when processing 1c3d839da has no effect. Therefore the\n\"entire\" history is not seen as being reachable from da2482f71 and it\nends up not being the best match.\n\nI will note that the authorship date of 1c3d839da is before that of\neither 0a77d7cf4 or da2482f71 (due to a rebase that reordered the\ncommits to keep 1c3d839da on the release-only part of the branch), but\nthe reproducer script doesn't seem to care that much.\n\nI suspect that building of the `commit_list` is the problem, probably by\nusing `commit_list_insert_by_date` instead of by topological sorting.\nThe reproducer script doesn't do anything (AFAICT) sneaky with dates\n(e.g., rebasing and such) though, so I'm nowhere near 100% confident\nabout that.\n\nPerhaps commits should be re-scheduled if their `flags` get updated\nbased on a newly discovered ancestor while traversing? I suspect that\ndepth tracking becomes more complicated in that case though because the\nsecond pass on 0a77d7cf4 needs to subtract a depth from the relevant\ntags with the new flag value. But it'd find the right tag at least…\n\nThanks,\n\n--Ben\n\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex b28a4a1f82..5895d1af3a 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -264,8 +264,10 @@ static unsigned long finish_depth_computation(\n \t\t\t}\n \t\t\tif (!a)\n \t\t\t\tbreak;\n-\t\t} else\n+\t\t} else {\n \t\t\tbest->depth++;\n+\t\t\tfprintf(stderr, \"pushing depth of %s (finish_depth_computation): %d\\n\", oid_to_hex(&c->object.oid), best->depth);\n+\t\t}\n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\n \t\t\trepo_parse_commit(the_repository, p);\n@@ -363,19 +365,24 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n+\t\tfprintf(stderr, \"\\n\\nlooking at commit %s\\n\", oid_to_hex(&c->object.oid));\n \t\tseen_commits++;\n \t\tslot = commit_names_peek(&commit_names, c);\n \t\tn = slot ? *slot : NULL;\n \t\tif (n) {\n \t\t\tif (!tags && !all && n->prio < 2) {\n+\t\t\t\tfprintf(stderr, \"skipping unannotated tag %s\\n\", oid_to_hex(&c->object.oid));\n \t\t\t\tunannotated_cnt++;\n \t\t\t} else if (match_cnt < max_candidates) {\n \t\t\t\tstruct possible_tag *t = &all_matches[match_cnt++];\n \t\t\t\tt->name = n;\n \t\t\t\tt->depth = seen_commits - 1;\n+\t\t\t\tfprintf(stderr, \"depth of %s: %d\\n\", oid_to_hex(&c->object.oid), t->depth);\n \t\t\t\tt->flag_within = 1u << match_cnt;\n \t\t\t\tt->found_order = match_cnt;\n+\t\t\t\tfprintf(stderr, \"find order of %s: %d\\n\", oid_to_hex(&c->object.oid), t->found_order);\n \t\t\t\tc->object.flags |= t->flag_within;\n+\t\t\t\tfprintf(stderr, \"setting flag %x for commit %s\\n\", t->flag_within, oid_to_hex(&c->object.oid));\n \t\t\t\tif (n->prio == 2)\n \t\t\t\t\tannotated_cnt++;\n \t\t\t}\n@@ -386,11 +393,15 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t}\n \t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n \t\t\tstruct possible_tag *t = &all_matches[cur_match];\n-\t\t\tif (!(c->object.flags & t->flag_within))\n+\t\t\tif (!(c->object.flags & t->flag_within)) {\n \t\t\t\tt->depth++;\n+\t\t\t\tfprintf(stderr, \"flag for %s: %x\\n\", oid_to_hex(&c->object.oid), c->object.flags);\n+\t\t\t\tfprintf(stderr, \"pushing depth of %s because of %s (flag_within): %d\\n\", oid_to_hex(&t->name->peeled), oid_to_hex(&c->object.oid), t->depth);\n+\t\t\t}\n \t\t}\n \t\t/* Stop if last remaining path already covered by best candidate(s) */\n \t\tif (annotated_cnt && !list) {\n+\t\t\tfprintf(stderr, \"checking for best candidate\\n\");\n \t\t\tint best_depth = INT_MAX;\n \t\t\tunsigned best_within = 0;\n \t\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n@@ -415,6 +426,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\tif (!(p->object.flags & SEEN))\n \t\t\t\tcommit_list_insert_by_date(p, &list);\n \t\t\tp->object.flags |= c->object.flags;\n+\t\t\tfprintf(stderr, \"setting flag %x for commit %s due to ancestry\\n\", p->object.flags, oid_to_hex(&p->object.oid));\n \t\t\tparents = parents->next;\n \n \t\t\tif (first_parent)\n"},{"id":"482145","messageId":"ZQ21NsLmp+xQU5g+@farprobe","threadId":"60108","inReplyTo":"ZNffWAgldUZdpQcr@farprobe","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"Ben Boeckel","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-22T15:39:34Z","receivedAt":"2023-09-22T15:39:44Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Sat, Aug 12, 2023 at 15:36:56 -0400, Ben Boeckel wrote:\n> I found an issue where `git describe` doesn't find a \"closer\" tag than\n> another tag as the correct one to base the description off of. I have a\n> reproducer, but I'll first give details of the real world issue.\n\nBump. Can anyone provide guidance as to what the best solution to this\nmight be?\n\nThanks,\n\n--Ben\n"},{"id":"482146","messageId":"02d701d9ed6f$abcb4b00$0361e100$@nexbridge.com","threadId":"60108","inReplyTo":"ZQ21NsLmp+xQU5g+@farprobe","subject":"RE: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"","fromEmail":"rsbecker@nexbridge.com","sentAt":"2023-09-22T16:13:00Z","receivedAt":"2023-09-22T16:13:11Z","isPatch":false,"sender":{"key":"randall.becker@nexbridge.ca","avatar":"https://avatars.githubusercontent.com/u/28956764?v=4"},"body":"On Friday, September 22, 2023 11:40 AM, Ben Boeckel wrote:\n>On Sat, Aug 12, 2023 at 15:36:56 -0400, Ben Boeckel wrote:\n>> I found an issue where `git describe` doesn't find a \"closer\" tag than\n>> another tag as the correct one to base the description off of. I have\n>> a reproducer, but I'll first give details of the real world issue.\n>\n>Bump. Can anyone provide guidance as to what the best solution to this might be?\n\nCan you provide details? `git describe` is sensitive to --first-parent and whether the tag has annotations.\n--Randall\n\n"},{"id":"482151","messageId":"ZQ3GAJ/AHsM9e9a6@farprobe","threadId":"60108","inReplyTo":"02d701d9ed6f$abcb4b00$0361e100$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-22T16:51:12Z","receivedAt":"2023-09-22T16:51:18Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 12:13:00 -0400, rsbecker@nexbridge.com wrote:\n> On Friday, September 22, 2023 11:40 AM, Ben Boeckel wrote:\n> >On Sat, Aug 12, 2023 at 15:36:56 -0400, Ben Boeckel wrote:\n> >> I found an issue where `git describe` doesn't find a \"closer\" tag than\n> >> another tag as the correct one to base the description off of. I have\n> >> a reproducer, but I'll first give details of the real world issue.\n> >\n> >Bump. Can anyone provide guidance as to what the best solution to this might be?\n> \n> Can you provide details? `git describe` is sensitive to --first-parent\n> and whether the tag has annotations.\n\nI provided more details and a reproducer in the original email:\n\n    https://lore.kernel.org/git/ZNffWAgldUZdpQcr@farprobe/T/#u\n\nThanks,\n\n--Ben\n"},{"id":"482153","messageId":"44a4e1e3-86d3-448a-ba6a-e78c63a6f85b@app.fastmail.com","threadId":"60108","inReplyTo":"02d701d9ed6f$abcb4b00$0361e100$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"Kristoffer Haugsbakk","fromEmail":"code@khaugsbakk.name","sentAt":"2023-09-22T17:11:47Z","receivedAt":"2023-09-22T17:12:11Z","isPatch":false,"sender":{"key":"code@khaugsbakk.name","avatar":"https://avatars.githubusercontent.com/u/2229597?v=4"},"body":"On Fri, Sep 22, 2023, at 18:13, rsbecker@nexbridge.com wrote:\n> On Friday, September 22, 2023 11:40 AM, Ben Boeckel wrote:\n>>On Sat, Aug 12, 2023 at 15:36:56 -0400, Ben Boeckel wrote:\n>>> I found an issue where `git describe` doesn't find a \"closer\" tag than\n>>> another tag as the correct one to base the description off of. I have\n>>> a reproducer, but I'll first give details of the real world issue.\n>>\n>>Bump. Can anyone provide guidance as to what the best solution to this might be?\n>\n> Can you provide details? `git describe` is sensitive to --first-parent\n> and whether the tag has annotations.\n> --Randall\n\nBoth of the tags (`v9.3.0.rc0` and `v9.3.0.rc1`) are annotated ones.\n\n-- \nKristoffer Haugsbakk\n"},{"id":"482154","messageId":"02e701d9ed78$436b3c60$ca41b520$@nexbridge.com","threadId":"60108","inReplyTo":"ZQ3GAJ/AHsM9e9a6@farprobe","subject":"RE: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"","fromEmail":"rsbecker@nexbridge.com","sentAt":"2023-09-22T17:14:30Z","receivedAt":"2023-09-22T17:14:41Z","isPatch":false,"sender":{"key":"randall.becker@nexbridge.ca","avatar":"https://avatars.githubusercontent.com/u/28956764?v=4"},"body":"On Friday, September 22, 2023 12:51 PM, Ben Boeckel wrote:\n>On Fri, Sep 22, 2023 at 12:13:00 -0400, rsbecker@nexbridge.com wrote:\n>> On Friday, September 22, 2023 11:40 AM, Ben Boeckel wrote:\n>> >On Sat, Aug 12, 2023 at 15:36:56 -0400, Ben Boeckel wrote:\n>> >> I found an issue where `git describe` doesn't find a \"closer\" tag\n>> >> than another tag as the correct one to base the description off of.\n>> >> I have a reproducer, but I'll first give details of the real world issue.\n>> >\n>> >Bump. Can anyone provide guidance as to what the best solution to this might be?\n>>\n>> Can you provide details? `git describe` is sensitive to --first-parent\n>> and whether the tag has annotations.\n>\n>I provided more details and a reproducer in the original email:\n>\n>    https://lore.kernel.org/git/ZNffWAgldUZdpQcr@farprobe/T/#u\n\nAs I indicated, the command is sensitive to --first-parent. For example:\n\n$ git describe\nv9.3.0.rc0-520-g1339e86833\n$ git describe --first-parent\nv9.0.0.rc1-5143-g1339e86833\n\nYou have multiple parents in your tree of HEAD. This is probably confusing the interpretation. The most closely connected tag to HEAD is v9.3.0.rc0, from what I can read from your tree. Dates and times of the commit do not participate in this determination, to my knowledge. You can force selection of a subset of tags by specifying the --match=pattern argument.\n\nThere appears to be a merge at 446120fd88 which brings v9.3.0.rc0 closer to HEAD than v9.3.0.rc1.\n\n"},{"id":"482155","messageId":"8f034aa3-67ac-456c-a754-b0a86666bcdb@app.fastmail.com","threadId":"60108","inReplyTo":"ZQ21NsLmp+xQU5g+@farprobe","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"Kristoffer Haugsbakk","fromEmail":"code@khaugsbakk.name","sentAt":"2023-09-22T17:35:01Z","receivedAt":"2023-09-22T17:35:25Z","isPatch":false,"sender":{"key":"code@khaugsbakk.name","avatar":"https://avatars.githubusercontent.com/u/2229597?v=4"},"body":"Looks related:\n\nLink: https://public-inbox.org/git/CABPp-BH2zuYe87xhjdp5v7M7i+EfEgLHAZgwfzJUAxGk1CFgfA@mail.gmail.com/\nMessage-ID: CABPp-BH2zuYe87xhjdp5v7M7i+EfEgLHAZgwfzJUAxGk1CFgfA@mail.gmail.com\nVia: https://stackoverflow.com/questions/72886894/git-describe-is-not-returning-the-expected-tag\n\n-- \nKristoffer Haugsbakk\n"},{"id":"482156","messageId":"ZQ3RGgEt8nPdTvv3@farprobe","threadId":"60108","inReplyTo":"02e701d9ed78$436b3c60$ca41b520$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-22T17:38:34Z","receivedAt":"2023-09-22T17:38:39Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 13:14:30 -0400, rsbecker@nexbridge.com wrote:\n> On Friday, September 22, 2023 12:51 PM, Ben Boeckel wrote:\n> >On Fri, Sep 22, 2023 at 12:13:00 -0400, rsbecker@nexbridge.com wrote:\n> >> On Friday, September 22, 2023 11:40 AM, Ben Boeckel wrote:\n> >> >On Sat, Aug 12, 2023 at 15:36:56 -0400, Ben Boeckel wrote:\n> >> >> I found an issue where `git describe` doesn't find a \"closer\" tag\n> >> >> than another tag as the correct one to base the description off of.\n> >> >> I have a reproducer, but I'll first give details of the real world issue.\n> >> >\n> >> >Bump. Can anyone provide guidance as to what the best solution to this might be?\n> >>\n> >> Can you provide details? `git describe` is sensitive to --first-parent\n> >> and whether the tag has annotations.\n> >\n> >I provided more details and a reproducer in the original email:\n> >\n> >    https://lore.kernel.org/git/ZNffWAgldUZdpQcr@farprobe/T/#u\n> \n> As I indicated, the command is sensitive to --first-parent. For example:\n> \n> $ git describe\n> v9.3.0.rc0-520-g1339e86833\n> $ git describe --first-parent\n> v9.0.0.rc1-5143-g1339e86833\n\nSorry, but this is just even more confusing to me as neither tag is on\nthe first-parent history of `HEAD`.\n\n> You have multiple parents in your tree of HEAD. This is probably\n> confusing the interpretation. The most closely connected tag to HEAD\n> is v9.3.0.rc0, from what I can read from your tree. Dates and times of\n> the commit do not participate in this determination, to my knowledge.\n> You can force selection of a subset of tags by specifying the\n> --match=pattern argument.\n\nI don't see how that is possible since v9.3.0.rc0 is v9.3.0.rc1~2. Note\nthe \"not on the tag\" commit count for the descriptions being wildly\ndifferent.\n\n> There appears to be a merge at 446120fd88 which brings v9.3.0.rc0\n> closer to HEAD than v9.3.0.rc1.\n\nThat is still giving an incorrect description as there are *fewer*\ncommits not on rc1 than rc0 relative to HEAD (as rc0 is an ancestor of\nrc1).\n\nThanks,\n\n--Ben\n"},{"id":"482157","messageId":"ZQ3SVJWPzAjVbTT0@farprobe","threadId":"60108","inReplyTo":"8f034aa3-67ac-456c-a754-b0a86666bcdb@app.fastmail.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-22T17:43:48Z","receivedAt":"2023-09-22T17:43:54Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 19:35:01 +0200, Kristoffer Haugsbakk wrote:\n> Looks related:\n> \n> Link: https://public-inbox.org/git/CABPp-BH2zuYe87xhjdp5v7M7i+EfEgLHAZgwfzJUAxGk1CFgfA@mail.gmail.com/\n> Message-ID: CABPp-BH2zuYe87xhjdp5v7M7i+EfEgLHAZgwfzJUAxGk1CFgfA@mail.gmail.com\n> Via: https://stackoverflow.com/questions/72886894/git-describe-is-not-returning-the-expected-tag\n\nThanks. It seems that these discussions previously determined the same\n(painful) pill:\n\nSZEDER Gábor at https://lore.kernel.org/git/20191008123156.GG11529@szeder.dev/:\n\n    I think the proper way to fix this issue would be to make 'git\n    describe' traverse the history in topographical order.  Alas, I'm\n    afraid this would result in a noticable performance penalty on big\n    histories without a commit graph.\n\nThe `sleep 1` is probably the remedy we'll use if time to actually fix\nthis doesn't come up (or the \"proper\" fix is deemed as \"too expensive\").\n\nThanks for the links,\n\n--Ben\n"},{"id":"482158","messageId":"xmqqediq2j0g.fsf@gitster.g","threadId":"60108","inReplyTo":"02e701d9ed78$436b3c60$ca41b520$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-09-22T17:51:59Z","receivedAt":"2023-09-22T17:53:36Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"<rsbecker@nexbridge.com> writes:\n\n> There appears to be a merge at 446120fd88 which brings v9.3.0.rc0 closer to HEAD than v9.3.0.rc1.\n\nI didn't look at the actual graph but let me say I trust you ;-)\n\nI wonder if there should be an obvious \"explain why you gave this\nname\" mode added to the command, though.  The command should be able\nto say \"The closest path from HEAD to any tag is via this, that, and\nthat commit, which is N hops to tag T0\", and from there, the user\nshould be able to say \"Oh, I thought T1 was closer, let me try again\nto describe HEAD, limiting the candidate only to T1\" and run the\ncommand in that mode, which should be able to say \"The closest path\nfrom HEAD to any tag that is allowed as a candidate is via these\ncommits, which is M hops to tag T1\".  And if M is smaller than N,\nthen that may deserve to trigger a bug report (but as you said,\nthere are rules like preferring annotated over unannotated tags\ninvolved, so it may not as straight-forward as comparing the two\ninteger hop counts).\n\nThanks for digging.\n\n"},{"id":"482160","messageId":"032d01d9ed80$5e569670$1b03c350$@nexbridge.com","threadId":"60108","inReplyTo":"xmqqediq2j0g.fsf@gitster.g","subject":"RE: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"","fromEmail":"rsbecker@nexbridge.com","sentAt":"2023-09-22T18:12:31Z","receivedAt":"2023-09-22T18:13:01Z","isPatch":false,"sender":{"key":"randall.becker@nexbridge.ca","avatar":"https://avatars.githubusercontent.com/u/28956764?v=4"},"body":"On Friday, September 22, 2023 1:52 PM, Junio C Hamano wrote:\n><rsbecker@nexbridge.com> writes:\n>\n>> There appears to be a merge at 446120fd88 which brings v9.3.0.rc0 closer\nto HEAD\n>than v9.3.0.rc1.\n>\n>I didn't look at the actual graph but let me say I trust you ;-)\n>\n>I wonder if there should be an obvious \"explain why you gave this name\"\nmode added\n>to the command, though.  The command should be able to say \"The closest\npath from\n>HEAD to any tag is via this, that, and that commit, which is N hops to tag\nT0\", and\n>from there, the user should be able to say \"Oh, I thought T1 was closer,\nlet me try\n>again to describe HEAD, limiting the candidate only to T1\" and run the\ncommand in\n>that mode, which should be able to say \"The closest path from HEAD to any\ntag that\n>is allowed as a candidate is via these commits, which is M hops to tag T1\".\nAnd if M\n>is smaller than N, then that may deserve to trigger a bug report (but as\nyou said,\n>there are rules like preferring annotated over unannotated tags involved,\nso it may\n>not as straight-forward as comparing the two integer hop counts).\n>\n>Thanks for digging.\n\nI'm wondering whether we need something more general that --first-parent.\nPerhaps something like\n\ngit describe commitish [ commitish ... ]\n\nWhere the traversal must cross the set of specified commitish points in\nhistory in order to find the expected tag. In Ben's case, I do not think\nthat would help much, given the complexity of his history. Perhaps a\n--verbose argument might display the analysis path done by git describe as\nabove. Sadly, I am not familiar with this code area.\n\nWhat confuses me is how, in the other subthread, that adding sleep 1 to the\nconstruction of history should make any difference. My understanding is that\nthe path to the tag is invariant of the commit-date.\n\n"},{"id":"482164","messageId":"ZQ3f1OZBGbOegVva@farprobe","threadId":"60108","inReplyTo":"xmqqediq2j0g.fsf@gitster.g","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-22T18:41:24Z","receivedAt":"2023-09-22T18:42:04Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 10:51:59 -0700, Junio C Hamano wrote:\n> <rsbecker@nexbridge.com> writes:\n> \n> > There appears to be a merge at 446120fd88 which brings v9.3.0.rc0 closer to HEAD than v9.3.0.rc1.\n> \n> I didn't look at the actual graph but let me say I trust you ;-)\n> \n> I wonder if there should be an obvious \"explain why you gave this\n> name\" mode added to the command, though.  The command should be able\n> to say \"The closest path from HEAD to any tag is via this, that, and\n> that commit, which is N hops to tag T0\", and from there, the user\n> should be able to say \"Oh, I thought T1 was closer, let me try again\n> to describe HEAD, limiting the candidate only to T1\" and run the\n> command in that mode, which should be able to say \"The closest path\n> from HEAD to any tag that is allowed as a candidate is via these\n> commits, which is M hops to tag T1\".  And if M is smaller than N,\n> then that may deserve to trigger a bug report (but as you said,\n> there are rules like preferring annotated over unannotated tags\n> involved, so it may not as straight-forward as comparing the two\n> integer hop counts).\n\nThe thing is that the count is what is wrong here, so the determination\nof what is \"closer\" is wrong. Any explanation would say things like\n\"commit X~10 is not part of X\".\n\n--Ben\n"},{"id":"482165","messageId":"ZQ3ggxA7KOysXrba@farprobe","threadId":"60108","inReplyTo":"032d01d9ed80$5e569670$1b03c350$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-22T18:44:19Z","receivedAt":"2023-09-22T18:44:24Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 14:12:31 -0400, rsbecker@nexbridge.com wrote:\n> What confuses me is how, in the other subthread, that adding sleep 1 to the\n> construction of history should make any difference. My understanding is that\n> the path to the tag is invariant of the commit-date.\n\nYes. It is explained that the commit date stored is only to 1 second\ngranularity. Since the commits are stored in commit-date, an equal\ncommit date ends up \"twisting\" the history and traversing some ancestors\nof commits before the commits themsevles. This loses the \"seen\" bit\ntracking that is done and ends up labeling way more commits as \"not part\nof\" ancestors. By sleeping for a second, the commit dates can be totally\nordered reliably.\n\nAnd this tracks with my and the other thread's result that the traversal\nis not paying attention to the topological history properly.\n\n--Ben\n"},{"id":"482166","messageId":"033201d9ed85$991c6af0$cb5540d0$@nexbridge.com","threadId":"60108","inReplyTo":"ZQ3ggxA7KOysXrba@farprobe","subject":"RE: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"","fromEmail":"rsbecker@nexbridge.com","sentAt":"2023-09-22T18:49:58Z","receivedAt":"2023-09-22T18:50:15Z","isPatch":false,"sender":{"key":"randall.becker@nexbridge.ca","avatar":"https://avatars.githubusercontent.com/u/28956764?v=4"},"body":"On Friday, September 22, 2023 2:44 PM, Ben Boeckel wrote:\n>On Fri, Sep 22, 2023 at 14:12:31 -0400, rsbecker@nexbridge.com wrote:\n>> What confuses me is how, in the other subthread, that adding sleep 1\n>> to the construction of history should make any difference. My\n>> understanding is that the path to the tag is invariant of the commit-date.\n>\n>Yes. It is explained that the commit date stored is only to 1 second granularity. Since\n>the commits are stored in commit-date, an equal commit date ends up \"twisting\" the\n>history and traversing some ancestors of commits before the commits themsevles.\n>This loses the \"seen\" bit tracking that is done and ends up labeling way more\n>commits as \"not part of\" ancestors. By sleeping for a second, the commit dates can\n>be totally ordered reliably.\n\nThis 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.\n\n"},{"id":"482167","messageId":"ZQ3leoLhljc+P5wP@farprobe","threadId":"60108","inReplyTo":"033201d9ed85$991c6af0$cb5540d0$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-22T19:05:30Z","receivedAt":"2023-09-22T19:05:40Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 14:49:58 -0400, rsbecker@nexbridge.com wrote:\n> On Friday, September 22, 2023 2:44 PM, Ben Boeckel wrote:\n> >Yes. It is explained that the commit date stored is only to 1 second granularity. Since\n> >the commits are stored in commit-date, an equal commit date ends up \"twisting\" the\n> >history and traversing some ancestors of commits before the commits themsevles.\n> >This loses the \"seen\" bit tracking that is done and ends up labeling way more\n> >commits as \"not part of\" ancestors. By sleeping for a second, the commit dates can\n> >be totally ordered reliably.\n> \n> This is going to be awkward to resolve as time_t only resolves\n> (portably) to 1 second intervals. I still would prefer the resolution\n> to be path-based rather than time-based.\n\nI certainly agree, but I'm not sure of the best way of doing that. Do we\ncreate/load a commit graph and use that for resolving insertion order\ninto the commit heap?\n\n--Ben\n"},{"id":"482168","messageId":"033c01d9ed8a$c6916f30$53b44d90$@nexbridge.com","threadId":"60108","inReplyTo":"ZQ3leoLhljc+P5wP@farprobe","subject":"RE: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"","fromEmail":"rsbecker@nexbridge.com","sentAt":"2023-09-22T19:27:01Z","receivedAt":"2023-09-22T19:27:12Z","isPatch":false,"sender":{"key":"randall.becker@nexbridge.ca","avatar":"https://avatars.githubusercontent.com/u/28956764?v=4"},"body":"On Friday, September 22, 2023 3:06 PM, Ben Boeckel wrote:\n>On Fri, Sep 22, 2023 at 14:49:58 -0400, rsbecker@nexbridge.com wrote:\n>> On Friday, September 22, 2023 2:44 PM, Ben Boeckel wrote:\n>> >Yes. It is explained that the commit date stored is only to 1 second\n>> >granularity. Since the commits are stored in commit-date, an equal\n>> >commit date ends up \"twisting\" the history and traversing some ancestors of\n>commits before the commits themsevles.\n>> >This loses the \"seen\" bit tracking that is done and ends up labeling\n>> >way more commits as \"not part of\" ancestors. By sleeping for a\n>> >second, the commit dates can be totally ordered reliably.\n>>\n>> This is going to be awkward to resolve as time_t only resolves\n>> (portably) to 1 second intervals. I still would prefer the resolution\n>> to be path-based rather than time-based.\n>\n>I certainly agree, but I'm not sure of the best way of doing that. Do we create/load a\n>commit graph and use that for resolving insertion order into the commit heap?\n\nI 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.\n\n"},{"id":"482208","messageId":"ZQ7a5FOHGNuHFif1@farprobe","threadId":"60108","inReplyTo":"02e701d9ed78$436b3c60$ca41b520$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2023-09-23T12:32:36Z","receivedAt":"2023-09-23T12:37:16Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 13:14:30 -0400, rsbecker@nexbridge.com wrote:\n> There appears to be a merge at 446120fd88 which brings v9.3.0.rc0\n> closer to HEAD than v9.3.0.rc1.\n\nI'll also note that `.rc0` was added as a fix for the situation of\n`.rc1` not being found properly. Without that, it finds `v9.2.6` as the\n\"closest\" tag.\n\n--Ben\n"},{"id":"531037","messageId":"aR6BlHflRVLN8_XO@rotor","threadId":"60108","inReplyTo":"033c01d9ed8a$c6916f30$53b44d90$@nexbridge.com","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2025-11-20T02:48:52Z","receivedAt":"2025-11-20T02:48:56Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Fri, Sep 22, 2023 at 15:27:01 -0400, rsbecker@nexbridge.com wrote:\n> I actually thought it worked that way. This may end up in a bigger\n> change than fixing the issue because --first-parent does not appear to\n> be sufficient to resolve the correct tag from your graph. My thought\n> on using multiple commitish values to do that may help, but\n> implementing that could lead to an O(n*m) scan (n=max commit tree\n> width, m=depth to tag), plus a commitish hash lookup.\n\nSo I finally found some time to go back to this. The actual fix is\nactually rather easy (patch attached). However, as guessed at previously\nin the thread, the performance is in the tank without an up-to-date\ncommit graph (\"instant\" with it versus \"minutes\" without). On the other\nhand, it is *accurate*. It does fix one expect-fail test case already in\nthe test suite (also included in the patch).\n\nWe could go one of two (or more! feel free to offer alternatives) ways:\n\n- swallow the pill and accept the performance for accurate results\n  (e.g., warn if there is not a recent `commit-graph`)\n- add an `--accurate` flag to optionally use it with the caveat that\n  reported descriptions may *change* under the flag (e.g., with the\n  reproducer script, a \"working\" description is `tag-release-7-g<hash>`,\n  but with the graph, it is the correct `tag-release-5-g<hash>`.\n\nAlso note the the reproducer provided was \"fixed\" in 7379046221\n(describe: stop digging for max_candidates+1, 2024-11-06) because it\nstopped searching because there were no more tags in the history.\nTagging the root commit preserves the reproducer state. I've attached an\nupdated reproducer script as well.\n\nThoughts on a plan forward?\n\n--Ben\n\n\nFrom ca4df5b9c9542315f77c166d47d5c63a2ebdafd1 Mon Sep 17 00:00:00 2001\nFrom: Ben Boeckel <mathstuf@gmail.com>\nDate: Wed, 12 Nov 2025 23:53:20 -0500\nSubject: [PATCH 1/1] describe: traverse commits by ancestry instead of commit\n date\n\nAn ancestor commit should never be traversed before its descendents.\nThis could happen if a series of commits are made in rapid succession\nand they all share a commit date (to the 1-second resolution supported\nin the metadata).\n\nThis was discovered in VTK's history where a `git describe` would return\nthe previous release's tag name rather than the one just made. The\nproblematic topology looks like:\n\n    H ---- M1 -- M2 -- M3 -- M4 - ROOT\n    |       \\     \\     \\    \\    /|\n    |        \\     \\     |    \\  / |\n    |         \\    R2 ---|---- R1 |\n    |          \\   /     |    /  /\n     \\          \\ /       \\  /  /\n      P1 - P2 - P3 ------- P4 --\n\nWhere P1 and P3 are tagged commits. If all commits share a commit date,\n`git describe` traverses in the following order:\n\n  - H\n  - M1\n  - P1 (tagged)\n  - M2\n  - P3 (tagged)\n  - P2\n  - M3\n  - R2\n  - P4\n  - M4\n  - ROOT\n  - R1\n\nAlthough P1 is traversed before P3, P1's depth is incremented due to the\n`flag_within` check despite the ancestry actually being the other way\naround. When all is said and done, the description is reported as\n`P3-7-g<hash>` despite the P1 tagged commit having it as an ancestor. If\nP1 is restricted using `describe --match`, it is reported as\n`P1-10-g<hash>` due to the traversal order issue.\n\nUsing topology sorting on the commit queue, the description is\naccurately reported as `P1-5-g<hash>` instead and the traversal order\nis:\n\nInstead of commit date heuristics, use ancestry as the sort constraint.\nThis also fixes one expect-failure test case as well. However, the\nperformance depends on having a `git commit-graph` available.\n\nReported-in: <ZNffWAgldUZdpQcr@farprobe>\n---\n builtin/describe.c  | 20 +++++++++++++++++++-\n t/t6120-describe.sh |  2 +-\n 2 files changed, 20 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex ffaf8d9f0a..789586e5a5 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -3,6 +3,7 @@\n \n #include \"builtin.h\"\n #include \"config.h\"\n+#include \"commit-reach.h\"\n #include \"environment.h\"\n #include \"gettext.h\"\n #include \"hex.h\"\n@@ -256,7 +257,23 @@ struct lazy_queue {\n \tbool get_pending;\n };\n \n-#define LAZY_QUEUE_INIT { { compare_commits_by_commit_date }, false }\n+/*\n+ * Topological comparison: always return parents before children.\n+ * This is reverse topological order: children before parents.\n+ */\n+static int compare_commits_topo(const void *a_, const void *b_, void *_unused_ UNUSED)\n+{\n+\tstruct commit *a = (struct commit *)a_;\n+\tstruct commit *b = (struct commit *)b_;\n+\tif (repo_is_descendant_of(the_repository, a, &(struct commit_list){ b, NULL }))\n+\t\treturn -1; // a is descendant, so comes before b\n+\tif (repo_is_descendant_of(the_repository, b, &(struct commit_list){ a, NULL }))\n+\t\treturn 1; // b is descendant, so comes before a\n+\t// fallback: order by hash for determinism\n+\treturn oidcmp(&a->object.oid, &b->object.oid);\n+}\n+\n+#define LAZY_QUEUE_INIT { { compare_commits_topo }, false }\n \n static void *lazy_queue_get(struct lazy_queue *queue)\n {\n@@ -413,6 +430,7 @@ static void describe_commit(struct commit *cmit, struct strbuf *dst)\n \t\tstruct commit_list *parents = c->parents;\n \t\tstruct commit_name **slot;\n \n+\t\tfprintf(stderr, \"\\n\\nlooking at commit %s\\n\", oid_to_hex(&c->object.oid));\n \t\tseen_commits++;\n \n \t\tif (match_cnt == max_candidates ||\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 2c70cc561a..36e1b9d848 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -711,7 +711,7 @@ test_expect_success 'setup: describe commits with disjoint bases 2' '\n '\n \n check_describe -C disjoint2 \"B-3-gHASH\" HEAD\n-check_describe -C disjoint2 --expect-failure \"B-3-gHASH\" --candidates=2 HEAD\n+check_describe -C disjoint2 \"B-3-gHASH\" --candidates=2 HEAD\n \n test_expect_success 'setup misleading taggerdates' '\n \tGIT_COMMITTER_DATE=\"2006-12-12 12:31\" git tag -a -m \"another tag\" newer-tag-older-commit unique-file~1\n-- \n2.51.1\n\n"},{"id":"531051","messageId":"20251120080525.GB1283645@coredump.intra.peff.net","threadId":"60108","inReplyTo":"aR6BlHflRVLN8_XO@rotor","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-11-20T08:05:25Z","receivedAt":"2025-11-20T08:05:26Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 19, 2025 at 09:48:52PM -0500, 'Ben Boeckel' wrote:\n\n> So I finally found some time to go back to this. The actual fix is\n> actually rather easy (patch attached). However, as guessed at previously\n> in the thread, the performance is in the tank without an up-to-date\n> commit graph (\"instant\" with it versus \"minutes\" without). On the other\n> hand, it is *accurate*. It does fix one expect-fail test case already in\n> the test suite (also included in the patch).\n\nMinutes? Yikes. Let's look...\n\n> +/*\n> + * Topological comparison: always return parents before children.\n> + * This is reverse topological order: children before parents.\n> + */\n> +static int compare_commits_topo(const void *a_, const void *b_, void *_unused_ UNUSED)\n> +{\n> +\tstruct commit *a = (struct commit *)a_;\n> +\tstruct commit *b = (struct commit *)b_;\n> +\tif (repo_is_descendant_of(the_repository, a, &(struct commit_list){ b, NULL }))\n> +\t\treturn -1; // a is descendant, so comes before b\n> +\tif (repo_is_descendant_of(the_repository, b, &(struct commit_list){ a, NULL }))\n> +\t\treturn 1; // b is descendant, so comes before a\n> +\t// fallback: order by hash for determinism\n> +\treturn oidcmp(&a->object.oid, &b->object.oid);\n> +}\n\nAh. So you are doing two full traversals for each comparison. That is\ngoing to be expensive. You would do much better to walk all of history\none time, marking the generation number (distance to root) of each\ncommit, and then comparing generations here (if A has a lower generation\nthan B, then you know that B cannot be an ancestor of A). Or if we have\ncommit graphs, just use the generation numbers they already contain. ;)\n\nWe do all of this already for the \"--topo-order\" option of the revision\ntraversal machinery. If we have commit graphs, it can output in\ntopographical order in a streaming way (see init_topo_walk() in\nrevision.c). If not, then we collect all of the commits up front and\ncall sort_in_topological_order().\n\nSadly, git-describe does not seem to use the traversal machinery, so it\nis not as easy as just setting revs.topo_order. Either we have to adapt\nto using the regular traversal code, or those same concepts need to be\napplied to its custom traversal.\n\n-Peff\n"},{"id":"537375","messageId":"aaKHH6Mf_oKJ9H6M@rotor.dev.benboeckel.internal","threadId":"60108","inReplyTo":"20251120080525.GB1283645@coredump.intra.peff.net","subject":"Re: [BUG] `git describe` doesn't traverse the graph in topological order","fromName":"'Ben Boeckel'","fromEmail":"ben.boeckel@kitware.com","sentAt":"2026-02-28T06:11:43Z","receivedAt":"2026-02-28T06:11:53Z","isPatch":false,"sender":{"key":"ben.boeckel@kitware.com","avatar":null},"body":"On Thu, Nov 20, 2025 at 03:05:25 -0500, Jeff King wrote:\n> On Wed, Nov 19, 2025 at 09:48:52PM -0500, 'Ben Boeckel' wrote:\n> \n> > So I finally found some time to go back to this. The actual fix is\n> > actually rather easy (patch attached). However, as guessed at previously\n> > in the thread, the performance is in the tank without an up-to-date\n> > commit graph (\"instant\" with it versus \"minutes\" without). On the other\n> > hand, it is *accurate*. It does fix one expect-fail test case already in\n> > the test suite (also included in the patch).\n> \n> Minutes? Yikes. Let's look...\n> \n> > +/*\n> > + * Topological comparison: always return parents before children.\n> > + * This is reverse topological order: children before parents.\n> > + */\n> > +static int compare_commits_topo(const void *a_, const void *b_, void *_unused_ UNUSED)\n> > +{\n> > +\tstruct commit *a = (struct commit *)a_;\n> > +\tstruct commit *b = (struct commit *)b_;\n> > +\tif (repo_is_descendant_of(the_repository, a, &(struct commit_list){ b, NULL }))\n> > +\t\treturn -1; // a is descendant, so comes before b\n> > +\tif (repo_is_descendant_of(the_repository, b, &(struct commit_list){ a, NULL }))\n> > +\t\treturn 1; // b is descendant, so comes before a\n> > +\t// fallback: order by hash for determinism\n> > +\treturn oidcmp(&a->object.oid, &b->object.oid);\n> > +}\n> \n> Ah. So you are doing two full traversals for each comparison. That is\n> going to be expensive. You would do much better to walk all of history\n> one time, marking the generation number (distance to root) of each\n> commit, and then comparing generations here (if A has a lower generation\n> than B, then you know that B cannot be an ancestor of A). Or if we have\n> commit graphs, just use the generation numbers they already contain. ;)\n\nOk, so it sounds like I should, in `describe_commit`:\n\n- check if commit graphs are enabled (and verified?): if so, use their\n  generation numbers\n- if they're not enabled, perform a local walk to store a generation\n  number (somewhere?) that is `max(cmit->parents[].generation) + 1`\n  (however the `generation` is stored)\n\nand then in the comparator, use this to exclude one of the comparisons\nat least. However…\n\n> We do all of this already for the \"--topo-order\" option of the revision\n> traversal machinery. If we have commit graphs, it can output in\n> topographical order in a streaming way (see init_topo_walk() in\n> revision.c). If not, then we collect all of the commits up front and\n> call sort_in_topological_order().\n\nThe key here seems to be:\n\n\tif (revs->topo_order && !generation_numbers_enabled(the_repository))\n\t\trevs->limited = 1;\n\nwhich then goes down the `sort_in_topological_order` path.\n\n> Sadly, git-describe does not seem to use the traversal machinery, so it\n> is not as easy as just setting revs.topo_order. Either we have to adapt\n> to using the regular traversal code, or those same concepts need to be\n> applied to its custom traversal.\n\nI suppose I can try to convert it over to a proper walk following\n`MyFirstObjectWalk.adoc` if that is a more fruitful path than the above\nideas. As long as all children of a commit are walked before the commit\nitself, it should slot into the existing bookkeeping fairly well.\n\nThanks,\n\n--Ben\n"}]}