[PATCH] name-rev: prefer shorter names over following merges

From: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>
Date: Nov 13, 2021, 00:14 UTC
Message-ID: <pull.1119.git.git.1636762454792.gitgitgadget@gmail.com>

From: Elijah Newren <newren@gmail.com>

name-rev has a MERGE_TRAVERSAL_WEIGHT to say that traversing a second or later parent of a merge should be 65535 times more expensive than a first-parent traversal, as per ac076c29ae8d (name-rev: Fix non-shortest description, 2007-08-27). The point of this weight is to prefer names like

    v2.32.0~1471^2

over names like

    v2.32.0~43^2~15^2~11^2~20^2~31^2

which are two equally valid names in git.git for the same commit. Note that the first follows 1472 parent traversals compared to a mere 125 for the second. Weighting all traversals equally would clearly prefer the second name since it has fewer parent traversals, but humans aren't going to be traversing commits and they tend to have an easier time digesting names with fewer segments. The fact that the former only has two segments (~1471, ^2) makes it much simpler than the latter which has six segments (~43, ^2, ~15, etc.). Since name-rev is meant to "find symbolic names suitable for human digestion", we prefer fewer segments.

However, the particular rule implemented in name-rev would actually prefer

    v2.33.0-rc0~11^2~1

over

    v2.33.0-rc0~20^2

because both have precisely one second parent traversal, and it gives the tie breaker to shortest number of total parent traversals. Fewer segments is more important for human consumption than number of hops, so we'd rather see the latter which has one fewer segment.

Include the generation in is_better_name() and use a new effective_distance() calculation so that we prefer fewer segments in the printed name over fewer total parent traversals performed to get the answer.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
    name-rev: prefer shorter names over following merges

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1119%2Fnewren%2Fprefer-shorter-names-in-name-rev-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1119/newren/prefer-shorter-names-in-name-rev-v1
Pull-Request: https://github.com/git/git/pull/1119

 builtin/name-rev.c | 17 +++++++++++++----
 1 file changed, 13 insertions(+), 4 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index b221d300147..27f60153a6c 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -44,11 +44,20 @@ static struct rev_name *get_commit_rev_name(const struct commit *commit)
 	return is_valid_rev_name(name) ? name : NULL;
 }
 
+static int effective_distance(int distance, int generation)
+{
+	return distance + (generation > 0 ? MERGE_TRAVERSAL_WEIGHT : 0);
+}
+
 static int is_better_name(struct rev_name *name,
 			  timestamp_t taggerdate,
+			  int generation,
 			  int distance,
 			  int from_tag)
 {
+	int name_distance = effective_distance(name->distance, name->generation);
+	int new_distance = effective_distance(distance, generation);
+
 	/*
 	 * When comparing names based on tags, prefer names
 	 * based on the older tag, even if it is farther away.
@@ -56,7 +65,7 @@ static int is_better_name(struct rev_name *name,
 	if (from_tag && name->from_tag)
 		return (name->taggerdate > taggerdate ||
 			(name->taggerdate == taggerdate &&
-			 name->distance > distance));
+			 name_distance > new_distance));
 
 	/*
 	 * We know that at least one of them is a non-tag at this point.
@@ -69,8 +78,8 @@ static int is_better_name(struct rev_name *name,
 	 * We are now looking at two non-tags.  Tiebreak to favor
 	 * shorter hops.
 	 */
-	if (name->distance != distance)
-		return name->distance > distance;
+	if (name_distance != new_distance)
+		return name_distance > new_distance;
 
 	/* ... or tiebreak to favor older date */
 	if (name->taggerdate != taggerdate)
@@ -88,7 +97,7 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 	struct rev_name *name = commit_rev_name_at(&rev_names, commit);
 
 	if (is_valid_rev_name(name)) {
-		if (!is_better_name(name, taggerdate, distance, from_tag))
+		if (!is_better_name(name, taggerdate, generation, distance, from_tag))
 			return NULL;
 
 		/*

base-commit: 9d530dc0024503ab4218fe6c4395b8a0aa245478

-- 
gitgitgadget