[PATCH] describe: count the distance correctly when commit dates are skewed

[Linus Torvalds <torvalds@kernel.org>]

From: Linus Torvalds <torvalds@linux-foundation.org>

The current merge window for Linux v7.4 showed annoying behavior with
'git describe', where it doesn't actually follow the documented intent
of the result: the commit distance is miscomputed when the commit dates
aren't entirely reliable.

This makes the 'git describe' output not match what the kernel
calculates in its localversion:

	linux$ git describe && uname -r
	v7.3-19342-g2a500a04d6f9
	7.3.0-19059-g2a500a04d6f9

and the kernel calculation is correct, and 'git describe' is wrong. The
number that 'git describe' gives (19342) is nonsense.

The reason is that 'git describe' has walked the commit list past the
actual tagged release due to walking the commits purely in date order,
and is thus counting a few hundred commits that were already included in
Linux 7.3.

The fix is to take the commit generation number into account when
ordering the commits. That will still fail if the repository has no
commit graph, but it at least improves on the situation in the common
case. With that one-liner fix, 'git describe' gets the correct commit
distance on my kernel tree:

	linux$ git describe && uname -r
	v7.3-19059-g2a500a04d6f9
	7.3.0-19059-g2a500a04d6f9

See also commit 1b600e659a ("Compute accurate distances in git-describe
before output.", 2007-01-27) which fixed a different issue in this same
area. Clearly the *intent* is that the distance number is actually the
real distance.

Also add a test-case for this. Thanks to Claude.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

[ Using my kernel.org email to send this, because setting that up is
  easier than fighting gmail ..   - Linus ]

 builtin/describe.c  |  2 +-
 t/t6120-describe.sh | 27 +++++++++++++++++++++++++++
 2 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index c0abc931a5..2cd597d919 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -328,7 +328,7 @@ static void append_suffix(int depth, const struct object_id *oid, struct strbuf
 static void describe_commit(struct commit *cmit, struct strbuf *dst)
 {
 	struct commit *c, *gave_up_on = NULL;
-	struct prio_queue queue = { compare_commits_by_commit_date };
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 	struct commit_name *n;
 	struct possible_tag all_matches[MAX_TAGS];
 	unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 7a7c46658a..a75f9227d9 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -749,6 +749,33 @@ test_expect_success 'setup: describe commits with disjoint bases 2' '
 check_describe -C disjoint2 "B-3-gHASH" HEAD
 check_describe -C disjoint2 --expect-failure "B-3-gHASH" --candidates=2 HEAD
 
+#            T
+#  o----o----o----x
+#        \       /
+#         `--o--'
+#            B
+#
+# T is dated an hour before its parent, so a walk by commit date
+# reaches T's parent through B before it reaches T.
+#
+test_expect_success 'setup: describe a tag dated before its parent' '
+	git init skew &&
+	(
+		cd skew &&
+		git config core.commitGraph true &&
+		test_commit --date "2020-01-01 18:00" base &&
+		test_commit --date "2020-01-01 18:01" o &&
+		test_commit --annotate --date "2020-01-01 17:01" T &&
+		git checkout -b side o &&
+		test_commit --date "2020-01-01 18:02" B &&
+		git checkout main &&
+		GIT_COMMITTER_DATE="2020-01-01 18:03" git merge --no-ff -m x side &&
+		git commit-graph write --reachable
+	)
+'
+
+check_describe -C skew "T-2-gHASH" HEAD
+
 test_expect_success 'setup misleading taggerdates' '
 	GIT_COMMITTER_DATE="2006-12-12 12:31" git tag -a -m "another tag" newer-tag-older-commit unique-file~1
 '
-- 
2.56.0.237.g993442f913