* [PATCH v2] describe: dont abort too early when searching tags
@ 2020-02-26 17:48 benno
2020-02-26 20:13 ` Junio C Hamano
0 siblings, 1 reply; 2+ messages in thread
From: benno @ 2020-02-26 17:48 UTC (permalink / raw)
To: gitster; +Cc: git, spearce, Benno Evers
From: Benno Evers <benno@bmevers.de>
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>
---
Changes since v1:
* Added a paragraph that discusses performance impact to the commit
message.
builtin/describe.c | 22 +++++++++++++++----
t/t6120-describe.sh | 53 ++++++++++++++++++++++++++++++++++++++++++++-
2 files changed, 70 insertions(+), 5 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;
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 09c50f3f04..d8cc08258e 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -479,4 +479,55 @@ test_expect_success 'name-rev covers all conditions while looking at parents' '
)
'
-test_done
+# B
+# o
+# \
+# o-----o---o----x
+# A
+#
+test_expect_success 'describe commits with disjoint bases' '
+ git init disjoint1 &&
+ (
+ cd disjoint1 &&
+
+ echo o >> file && git add file && git commit -m o &&
+ echo A >> file && git add file && git commit -m A &&
+ git tag A -a -m A &&
+ echo o >> file && git add file && git commit -m o &&
+
+ git checkout --orphan branch && rm file &&
+ echo B > file2 && git add file2 && git commit -m B &&
+ git tag B -a -m B &&
+ git merge --no-ff --allow-unrelated-histories master -m x &&
+
+ check_describe "A-3-*" HEAD
+ )
+'
+
+# B
+# o---o---o------------.
+# \
+# o---o---x
+# A
+#
+test_expect_success 'describe commits with disjoint bases 2' '
+ git init disjoint2 &&
+ (
+ cd disjoint2 &&
+
+ echo A >> file && git add file && GIT_COMMITTER_DATE="2020-01-01 18:00" git commit -m A &&
+ git tag A -a -m A &&
+ echo o >> file && git add file && GIT_COMMITTER_DATE="2020-01-01 18:01" git commit -m o &&
+
+ git checkout --orphan branch &&
+ echo o >> file2 && git add file2 && GIT_COMMITTER_DATE="2020-01-01 15:00" git commit -m o &&
+ echo o >> file2 && git add file2 && GIT_COMMITTER_DATE="2020-01-01 15:01" git commit -m o &&
+ echo B >> file2 && git add file2 && GIT_COMMITTER_DATE="2020-01-01 15:02" git commit -m B &&
+ git tag B -a -m B &&
+ git merge --no-ff --allow-unrelated-histories master -m x &&
+
+ check_describe "B-3-*" HEAD
+ )
+'
+
+test_done
\ No newline at end of file
--
2.20.1
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [PATCH v2] describe: dont abort too early when searching tags
2020-02-26 17:48 [PATCH v2] describe: dont abort too early when searching tags benno
@ 2020-02-26 20:13 ` Junio C Hamano
0 siblings, 0 replies; 2+ messages in thread
From: Junio C Hamano @ 2020-02-26 20:13 UTC (permalink / raw)
To: benno; +Cc: git, spearce
benno@bmevers.de writes:
> 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>
> ---
> Changes since v1:
>
> * Added a paragraph that discusses performance impact to the commit
> message.
> ...
> +'
> +
> +test_done
> \ No newline at end of file
I'll fix this while queuing.
Thanks for an update.
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2020-02-26 20:13 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-02-26 17:48 [PATCH v2] describe: dont abort too early when searching tags benno
2020-02-26 20:13 ` Junio C Hamano
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).