[PATCH v2 0/6] describe --contains / name-rev --weight

@@ -7,11 +7,11 @@
 
 #define CUTOFF_DATE_SLOP 86400 /* one day */
 
-typedef struct rev_name {
+struct rev_name {
 	const char *tip_name;
 	int generation;
 	int distance;
-} rev_name;
+};
 
 static long cutoff = LONG_MAX;
 

@@ -43,7 +43,7 @@ static void name_rev(struct commit *commit,
 	}
 
 	if (name == NULL) {
-		name = xmalloc(sizeof(rev_name));
+		name = xmalloc(sizeof(struct rev_name));
 		commit->util = name;
 		goto copy_data;
 	} else if (name->distance > distance) {

@@ -436,11 +436,12 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 		die(_("--long is incompatible with --abbrev=0"));
 
 	if (contains) {
-		const char **args = xmalloc((7 + argc) * sizeof(char *));
+		const char **args = xmalloc((8 + argc) * sizeof(char *));
 		int i = 0;
 		args[i++] = "name-rev";
 		args[i++] = "--name-only";
 		args[i++] = "--no-undefined";
+		args[i++] = "--weight";
 		if (always)
 			args[i++] = "--always";
 		if (!all) {

@@ -9,13 +9,13 @@ git-name-rev - Find symbolic names for given revs
 SYNOPSIS
 --------
 [verse]
-'git name-rev' [--tags] [--refs=<pattern>]
+'git name-rev' [--tags] [--refs=<pattern>] [--weight]
 	       ( --all | --stdin | <committish>... )
 
 DESCRIPTION
 -----------
-Finds symbolic names suitable for human digestion for revisions given in any
-format parsable by 'git rev-parse'.
+Finds symbolic names suitable for human digestion for revisions
+given in any format parsable by 'git rev-parse'.
 
 
 OPTIONS

@@ -47,6 +47,14 @@ OPTIONS
 --always::
 	Show uniquely abbreviated commit object as fallback.
 
+--weight::
+	Name commits based on the oldest ref that contains it.  This
+	is way more expensive than the default behaviour of the
+	command, in which commits are named based on the ref that
+	is topologically the closest, but gives more intuitive
+	answer to the question: what is the oldest tag that contains
+	this commit?
+
 EXAMPLE
 -------
 

@@ -0,0 +1,62 @@
+#!/bin/sh
+
+test_description='name-rev'
+. ./test-lib.sh
+
+# Prepare a history with this shape
+#
+# ---0--1--2--3--4--Y--5---7---Z
+#     \   /               /
+#      \ /               /
+#       X---------------6
+#
+
+test_expect_success setup '
+	test_tick &&
+	git commit --allow-empty -m 0 &&
+	git branch side &&
+	git commit --allow-empty -m 1 &&
+	git checkout side &&
+	git commit --allow-empty -m X &&
+	git branch X &&
+	git commit --allow-empty -m 6 &&
+	git checkout master &&
+	git merge -m 2 X &&
+	git commit --allow-empty -m 3 &&
+	git commit --allow-empty -m 4 &&
+	git commit --allow-empty -m Y &&
+	git tag Y &&
+	git commit --allow-empty -m 5 &&
+	git merge -m 7 side &&
+	git commit --allow-empty -m Z &&
+	git tag Z
+'
+
+test_expect_success 'name-rev (plain)' '
+	# We expect "X tags/Z~1^2~1" but it could
+	# be written as "X tags/Z^^2^"; the only two
+	# important things that matter are that it
+	# is named after Z (not Y), and it correctly
+	# names X.
+	git name-rev --tags X >actual &&
+	read X T <actual &&
+	test "z$X" = zX &&
+	expr "$T" : 'tags/Z[~^]' &&
+	H1=$(git rev-parse --verify "$T") &&
+	H2=$(git rev-parse --verify X) &&
+	test "z$H1" = "z$H2"
+'
+
+test_expect_success 'name-rev --weight' '
+	# Likewise; "X tags/Y~3^2" but we only care
+	# that it is based on Y.
+	git name-rev --weight --tags X >actual &&
+	read X T <actual &&
+	test "z$X" = zX &&
+	expr "$T" : 'tags/Y[~^]' &&
+	H1=$(git rev-parse --verify "$T") &&
+	H2=$(git rev-parse --verify X) &&
+	test "z$H1" = "z$H2"
+'
+
+test_done

@@ -4,6 +4,8 @@
 #include "tag.h"
 #include "refs.h"
 #include "parse-options.h"
+#include "diff.h"
+#include "revision.h"
 
 #define CUTOFF_DATE_SLOP 86400 /* one day */
 

@@ -11,8 +13,85 @@ struct rev_name {
 	const char *tip_name;
 	int generation;
 	int distance;
+	int weight;
 };
 
+/*
+ * Historically, "name-rev" named a rev based on the tip that is
+ * topologically closest to it.
+ *
+ * It does not give a good answer to "what is the earliest tag that
+ * contains the commit?", however, because you can build a new commit
+ * on top of an ancient commit X, merge it to the tip and tag the
+ * result, which would make X reachable from the new tag in two hops,
+ * even though it appears in the part of the history that is contained
+ * in other ancient tags.
+ *
+ * In order to answer that question, "name-rev" can be told to name a
+ * rev based on the tip that has smallest number of commits behind it.
+ */
+static int use_weight;
+
+/*
+ * NEEDSWORK: the result of this computation must be cached to
+ * a dedicated notes tree, keyed by the commit object name.
+ */
+static int compute_ref_weight(struct commit *commit)
+{
+	struct rev_info revs;
+	int weight = 1; /* give root the weight of 1 */
+
+	reset_revision_walk();
+	init_revisions(&revs, NULL);
+	add_pending_object(&revs, (struct object *)commit, NULL);
+	prepare_revision_walk(&revs);
+	while (get_revision(&revs))
+		weight++;
+	return weight;
+}
+
+static int ref_weight(const char *refname, size_t reflen)
+{
+	struct strbuf buf = STRBUF_INIT;
+	unsigned char sha1[20];
+	struct commit *commit;
+	struct rev_name *name;
+
+	strbuf_add(&buf, refname, reflen);
+	if (get_sha1(buf.buf, sha1))
+		die("Internal error: cannot parse tip '%s'", buf.buf);
+	strbuf_release(&buf);
+
+	commit = lookup_commit_reference_gently(sha1, 0);
+	if (!commit)
+		die("Internal error: cannot look up commit '%s'", buf.buf);
+	name = commit->util;
+	if (!name)
+		die("Internal error: a tip without name '%s'", buf.buf);
+	if (!name->weight)
+		name->weight = compute_ref_weight(commit);
+	return name->weight;
+}
+
+static int tip_weight_cmp(const char *a, const char *b)
+{
+	size_t reflen_a, reflen_b;
+	static const char traversal[] = "^~";
+
+	/*
+	 * A "tip" may look like <refname> followed by traversal
+	 * instruction (e.g. ^2~74).  We only are interested in
+	 * the weight of the ref part.
+	 */
+	reflen_a = strcspn(a, traversal);
+	reflen_b = strcspn(b, traversal);
+
+	if (reflen_a == reflen_b && !memcmp(a, b, reflen_a))
+		return 0;
+
+	return ref_weight(a, reflen_a) - ref_weight(b, reflen_b);
+}
+
 static long cutoff = LONG_MAX;
 
 /* How many generations are maximally preferred over _one_ merge traversal? */

@@ -49,8 +128,27 @@ static void name_rev(struct commit *commit,
 		use_this_tip = 1;
 	}
 
-	if (distance < name->distance)
-		use_this_tip = 1;
+	if (!use_weight) {
+		if (distance < name->distance)
+			use_this_tip = 1;
+	} else {
+		if (!name->tip_name)
+			use_this_tip = 1;
+		else {
+			/*
+			 * Pick a name based on the ref that is older,
+			 * i.e. having smaller number of commits
+			 * behind it.  Break the tie by picking the
+			 * path with smaller numer of steps to reach
+			 * that ref from the commit.
+			 */
+			int cmp = tip_weight_cmp(name->tip_name, tip_name);
+			if (0 < cmp)
+				use_this_tip = 1;
+			else if (!cmp && distance < name->distance)
+				use_this_tip = 1;
+		}
+	}
 
 	if (!use_this_tip)
 		return;

@@ -241,6 +339,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		OPT_BOOLEAN(0, "undefined", &allow_undefined, "allow to print `undefined` names"),
 		OPT_BOOLEAN(0, "always",     &always,
 			   "show abbreviated commit object as fallback"),
+		OPT_BOOLEAN(0, "weight", &use_weight,
+			    "name revs based on the oldest tip that contain them"),
 		OPT_END(),
 	};
 

@@ -6,6 +6,7 @@
 #include "parse-options.h"
 #include "diff.h"
 #include "revision.h"
+#include "notes-cache.h"
 
 #define CUTOFF_DATE_SLOP 86400 /* one day */
 

@@ -32,10 +33,6 @@ struct rev_name {
  */
 static int use_weight;
 
-/*
- * NEEDSWORK: the result of this computation must be cached to
- * a dedicated notes tree, keyed by the commit object name.
- */
 static int compute_ref_weight(struct commit *commit)
 {
 	struct rev_info revs;

@@ -50,6 +47,32 @@ static int compute_ref_weight(struct commit *commit)
 	return weight;
 }
 
+static struct notes_cache weight_cache;
+static int weight_cache_updated;
+
+static int get_ref_weight(struct commit *commit)
+{
+	struct strbuf buf = STRBUF_INIT;
+	size_t sz;
+	int weight;
+	char *note;
+
+	note = notes_cache_get(&weight_cache, commit->object.sha1, &sz);
+	if (note && !strtol_i(note, 10, &weight)) {
+		free(note);
+		return weight;
+	}
+	free(note);
+
+	weight = compute_ref_weight(commit);
+	strbuf_addf(&buf, "%d", weight);
+	notes_cache_put(&weight_cache, commit->object.sha1,
+			buf.buf, buf.len);
+	strbuf_release(&buf);
+	weight_cache_updated = 1;
+	return weight;
+}
+
 static int ref_weight(const char *refname, size_t reflen)
 {
 	struct strbuf buf = STRBUF_INIT;

@@ -69,7 +92,7 @@ static int ref_weight(const char *refname, size_t reflen)
 	if (!name)
 		die("Internal error: a tip without name '%s'", buf.buf);
 	if (!name->weight)
-		name->weight = compute_ref_weight(commit);
+		name->weight = get_ref_weight(commit);
 	return name->weight;
 }
 

@@ -323,6 +346,22 @@ static void name_rev_line(char *p, struct name_ref_data *data)
 		fwrite(p_start, p - p_start, 1, stdout);
 }
 
+static const char *get_validity_token(void)
+{
+	/*
+	 * In future versions, we may want to automatically invalidate
+	 * the cached weight data whenever grafts and replacement
+	 * changes.  We could do so by (1) reading the contents of the
+	 * grafts file, (2) enumerating the replacement data (original
+	 * object name and replacement object name) and sorting the
+	 * result, and (3) concatenating (1) and (2) and hashing it,
+	 * to come up with "dynamic validity: [0-9a-f]{40}" or something.
+	 *
+	 * In this verison, we simply do not bother ;-).
+	 */
+	return "static validity token";
+}
+
 int cmd_name_rev(int argc, const char **argv, const char *prefix)
 {
 	struct object_array revs = OBJECT_ARRAY_INIT;

@@ -353,6 +392,10 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 	if (all || transform_stdin)
 		cutoff = 0;
 
+	if (use_weight)
+		notes_cache_init(&weight_cache, "name-rev-weight",
+				 get_validity_token());
+
 	for (; argc; argc--, argv++) {
 		unsigned char sha1[20];
 		struct object *o;

@@ -408,5 +451,8 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 				  always, allow_undefined, data.name_only);
 	}
 
+	if (use_weight && weight_cache_updated)
+		notes_cache_write(&weight_cache);
+
 	return 0;
 }

@@ -19,12 +19,13 @@ static long cutoff = LONG_MAX;
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
 static void name_rev(struct commit *commit,
-		const char *tip_name, int generation, int distance,
-		int deref)
+		     const char *tip_name, int generation, int distance,
+		     int deref)
 {
 	struct rev_name *name = (struct rev_name *)commit->util;
 	struct commit_list *parents;
-	int parent_number = 1;
+	int parent_number;
+	int use_this_tip = 0;
 
 	if (!commit->object.parsed)
 		parse_commit(commit);

@@ -42,21 +43,26 @@ static void name_rev(struct commit *commit,
 			die("generation: %d, but deref?", generation);
 	}
 
-	if (name == NULL) {
-		name = xmalloc(sizeof(struct rev_name));
+	if (!name) {
+		name = xcalloc(1, sizeof(struct rev_name));
 		commit->util = name;
-		goto copy_data;
-	} else if (name->distance > distance) {
-copy_data:
-		name->tip_name = tip_name;
-		name->generation = generation;
-		name->distance = distance;
-	} else
+		use_this_tip = 1;
+	}
+
+	if (distance < name->distance)
+		use_this_tip = 1;
+
+	if (!use_this_tip)
 		return;
 
-	for (parents = commit->parents;
-			parents;
-			parents = parents->next, parent_number++) {
+	name->tip_name = tip_name;
+	name->generation = generation;
+	name->distance = distance;
+
+	/* Propagate our name to our parents */
+	for (parents = commit->parents, parent_number = 1;
+	     parents;
+	     parents = parents->next, parent_number++) {
 		if (parent_number > 1) {
 			int len = strlen(tip_name);
 			char *new_name = xmalloc(len +

@@ -68,16 +74,15 @@ copy_data:
 				len -= 2;
 			if (generation > 0)
 				sprintf(new_name, "%.*s~%d^%d", len, tip_name,
-						generation, parent_number);
+					generation, parent_number);
 			else
 				sprintf(new_name, "%.*s^%d", len, tip_name,
-						parent_number);
-
+					parent_number);
 			name_rev(parents->item, new_name, 0,
-				distance + MERGE_TRAVERSAL_WEIGHT, 0);
+				 distance + MERGE_TRAVERSAL_WEIGHT, 0);
 		} else {
 			name_rev(parents->item, tip_name, generation + 1,
-				distance + 1, 0);
+				 distance + 1, 0);
 		}
 	}
 }