{"thread":{"id":"52891","subject":"[PATCH v2] describe: dont abort too early when searching tags","startedAt":"2020-02-26T17:50:24Z","lastAt":"2020-02-26T20:13:40Z","messageCount":2,"participants":["benno@bmevers.de","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"392548","messageId":"20200226174853.27404-1-benno@bmevers.de","threadId":"52891","inReplyTo":null,"subject":"[PATCH v2] describe: dont abort too early when searching tags","fromName":"","fromEmail":"benno@bmevers.de","sentAt":"2020-02-26T17:48:53Z","receivedAt":"2020-02-26T17:50:24Z","isPatch":true,"sender":{"key":"benno@bmevers.de","avatar":"https://avatars.githubusercontent.com/u/51410?v=4"},"body":"From: Benno Evers <benno@bmevers.de>\n\nWhen searching the commit graph for tag candidates, `git-describe`\nwill stop as soon as there is only one active branch left and\nit already found an annotated tag as a candidate.\n\nThis works well as long as all branches eventually connect back\nto a common root, but if the tags are found across branches\nwith no common ancestor\n\n                  B\n                  o----.\n                        \\\n          o-----o---o----x\n          A\n\nit can happen that the search on one branch terminates prematurely\nbecause a tag was found on another, independent branch. This scenario\nisn't quite as obscure as it sounds, since cloning with a limited\ndepth often introduces many independent \"dead ends\" into the commit\ngraph.\n\nThe help text of `git-describe` states pretty clearly that when\ndescribing a commit D, the number appended to the emitted tag X should\ncorrespond to the number of commits found by `git log X..D`.\n\nThus, this commit modifies the stopping condition to only abort\nthe search when only one branch is left to search *and* all current\nbest candidates are descendants from that branch.\n\nFor repositories with a single root, this condition is always\ntrue: When the search is reduced to a single active branch, the\ncurrent commit must be an ancestor of *all* tag candidates. This\nmeans that in the common case, this change will have no negative\nperformance impact since the same number of commits as before will\nbe traversed.\n\nSigned-off-by: Benno Evers <benno@bmevers.de>\n---\nChanges since v1:\n\n  * Added a paragraph that discusses performance impact to the commit\n    message.\n\n\n builtin/describe.c  | 22 +++++++++++++++----\n t/t6120-describe.sh | 53 ++++++++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 70 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex b6df81d8d0..420f4c6401 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -376,11 +376,25 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)\n \t\t\tif (!(c->object.flags & t->flag_within))\n \t\t\t\tt->depth++;\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\tif (debug)\n-\t\t\t\tfprintf(stderr, _(\"finished search at %s\\n\"),\n-\t\t\t\t\toid_to_hex(&c->object.oid));\n-\t\t\tbreak;\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+\t\t\t\tstruct possible_tag *t = &all_matches[cur_match];\n+\t\t\t\tif (t->depth < best_depth) {\n+\t\t\t\t\tbest_depth = t->depth;\n+\t\t\t\t\tbest_within = t->flag_within;\n+\t\t\t\t} else if (t->depth == best_depth) {\n+\t\t\t\t\tbest_within |= t->flag_within;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tif ((c->object.flags & best_within) == best_within) {\n+\t\t\t\tif (debug)\n+\t\t\t\t\tfprintf(stderr, _(\"finished search at %s\\n\"),\n+\t\t\t\t\t\toid_to_hex(&c->object.oid));\n+\t\t\t\tbreak;\n+\t\t\t}\n \t\t}\n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 09c50f3f04..d8cc08258e 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -479,4 +479,55 @@ test_expect_success 'name-rev covers all conditions while looking at parents' '\n \t)\n '\n \n-test_done\n+#               B\n+#               o\n+#                \\\n+#  o-----o---o----x\n+#        A\n+#\n+test_expect_success 'describe commits with disjoint bases' '\n+\tgit init disjoint1 &&\n+\t(\n+\t\tcd disjoint1 &&\n+\n+\t\techo o >> file && git add file && git commit -m o &&\n+\t\techo A >> file && git add file && git commit -m A &&\n+\t\tgit tag A -a -m A &&\n+\t\techo o >> file && git add file && git commit -m o &&\n+\n+\t\tgit checkout --orphan branch && rm file &&\n+\t\techo B > file2 && git add file2 && git commit -m B &&\n+\t\tgit tag B -a -m B &&\n+\t\tgit merge --no-ff --allow-unrelated-histories master -m x &&\n+\n+\t\tcheck_describe \"A-3-*\" HEAD\n+\t)\n+'\n+\n+#           B\n+#   o---o---o------------.\n+#                         \\\n+#                  o---o---x\n+#                  A\n+#\n+test_expect_success 'describe commits with disjoint bases 2' '\n+\tgit init disjoint2 &&\n+\t(\n+\t\tcd disjoint2 &&\n+\n+\t\techo A >> file && git add file && GIT_COMMITTER_DATE=\"2020-01-01 18:00\" git commit -m A &&\n+\t\tgit tag A -a -m A &&\n+\t\techo o >> file && git add file && GIT_COMMITTER_DATE=\"2020-01-01 18:01\" git commit -m o &&\n+\n+\t\tgit checkout --orphan branch &&\n+\t\techo o >> file2 && git add file2 && GIT_COMMITTER_DATE=\"2020-01-01 15:00\" git commit -m o &&\n+\t\techo o >> file2 && git add file2 && GIT_COMMITTER_DATE=\"2020-01-01 15:01\" git commit -m o &&\n+\t\techo B >> file2 && git add file2 && GIT_COMMITTER_DATE=\"2020-01-01 15:02\" git commit -m B &&\n+\t\tgit tag B -a -m B &&\n+\t\tgit merge --no-ff --allow-unrelated-histories master -m x &&\n+\n+\t\tcheck_describe \"B-3-*\" HEAD\n+\t)\n+'\n+\n+test_done\n\\ No newline at end of file\n-- \n2.20.1\n\n"},{"id":"392566","messageId":"xmqqmu95hztg.fsf@gitster-ct.c.googlers.com","threadId":"52891","inReplyTo":"20200226174853.27404-1-benno@bmevers.de","subject":"Re: [PATCH v2] describe: dont abort too early when searching tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-26T20:13:31Z","receivedAt":"2020-02-26T20:13:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"benno@bmevers.de writes:\n\n> Thus, this commit modifies the stopping condition to only abort\n> the search when only one branch is left to search *and* all current\n> best candidates are descendants from that branch.\n>\n> For repositories with a single root, this condition is always\n> true: When the search is reduced to a single active branch, the\n> current commit must be an ancestor of *all* tag candidates. This\n> means that in the common case, this change will have no negative\n> performance impact since the same number of commits as before will\n> be traversed.\n>\n> Signed-off-by: Benno Evers <benno@bmevers.de>\n> ---\n> Changes since v1:\n>\n>   * Added a paragraph that discusses performance impact to the commit\n>     message.\n> ...\n> +'\n> +\n> +test_done\n> \\ No newline at end of file\n\nI'll fix this while queuing.\n\nThanks for an update.\n"}]}