describe: don't abort too early when searching tags

When searching the commit graph for tag candidates, `git-describe`
will stop as soon as there is only one active branch left and
it already found an annotated tag as a candidate.

This works well as long as all branches eventually connect back
to a common root, but if the tags are found across branches
with no common ancestor

                  B
                  o----.
                        \
          o-----o---o----x
          A

it can happen that the search on one branch terminates prematurely
because a tag was found on another, independent branch. This scenario
isn't quite as obscure as it sounds, since cloning with a limited
depth often introduces many independent "dead ends" into the commit
graph.

The help text of `git-describe` states pretty clearly that when
describing a commit D, the number appended to the emitted tag X should
correspond to the number of commits found by `git log X..D`.

Thus, this commit modifies the stopping condition to only abort
the search when only one branch is left to search *and* all current
best candidates are descendants from that branch.

For repositories with a single root, this condition is always
true: When the search is reduced to a single active branch, the
current commit must be an ancestor of *all* tag candidates. This
means that in the common case, this change will have no negative
performance impact since the same number of commits as before will
be traversed.

Signed-off-by: Benno Evers <benno@bmevers.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 18 insertions, 4 deletions

diff --git a/builtin/describe.c b/builtin/describe.c
index b6df81d8d0..420f4c6401 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -376,11 +376,25 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			if (!(c->object.flags & t->flag_within))
 				t->depth++;
 		}
+		/* Stop if last remaining path already covered by best candidate(s) */
 		if (annotated_cnt && !list) {
-			if (debug)
-				fprintf(stderr, _("finished search at %s\n"),
-					oid_to_hex(&c->object.oid));
-			break;
+			int best_depth = INT_MAX;
+			unsigned best_within = 0;
+			for (cur_match = 0; cur_match < match_cnt; cur_match++) {
+				struct possible_tag *t = &all_matches[cur_match];
+				if (t->depth < best_depth) {
+					best_depth = t->depth;
+					best_within = t->flag_within;
+				} else if (t->depth == best_depth) {
+					best_within |= t->flag_within;
+				}
+			}
+			if ((c->object.flags & best_within) == best_within) {
+				if (debug)
+					fprintf(stderr, _("finished search at %s\n"),
+						oid_to_hex(&c->object.oid));
+				break;
+			}
 		}
 		while (parents) {
 			struct commit *p = parents->item;