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

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

[Junio C Hamano]

Greg KH noticed that the commit 0136db586c that was merged to the
mainline back in v3.5-rc1 days was merged again as part of a
different branch to the mainline before v3.6-rc1.

"git describe --contains" gives the commit a name based on the newer
v3.6-rc1 tag, which was surprising.

This is because "describe --contains" calls "name-rev", which tries
to use the tag that minimizes the steps between the tag and the
commit being named.  The branch merged recently to the mainline did
not have as much work done on top of the commit as the old branch
that was merged earlier, and "name-rev" chose to use the newer tag
to base the name on.

The new "--weight" option introduced by this series tells it to use
the oldest tag that contains the commit being named instead.  This
matches what people expect from "describe --contains" better.

Junio C Hamano (6):
  name-rev: lose unnecessary typedef
  name_rev: clarify the logic to assign a new tip-name to a commit
  name-rev: --weight option
  name-rev --weight: cache the computed weight in notes
  name-rev --weight: tests and documentation
  describe --contains: use "name-rev --weight"

 Documentation/git-name-rev.txt |  14 ++-
 builtin/describe.c             |   3 +-
 builtin/name-rev.c             | 195 ++++++++++++++++++++++++++++++++++++-----
 t/t6039-name-rev.sh            |  62 +++++++++++++
 4 files changed, 248 insertions(+), 26 deletions(-)
 create mode 100755 t/t6039-name-rev.sh

-- 
1.7.12.286.g9df01f7

[PATCH v2 1/6] name-rev: lose unnecessary typedef

[Junio C Hamano]

Just spell it "struct rev_name"; it makes it more clear what is
going on.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/name-rev.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 1b37458..8af2cfa 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -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) {
-- 
1.7.12.286.g9df01f7

[PATCH v2 2/6] name_rev: clarify the logic to assign a new tip-name to a commit

[Junio C Hamano]

In preparation for later changes, restructure the logic a little bit
to separate how the code decides to use the new "tip" for naming a
particular commit, and what happens based on the decision.

Also re-indent and correct style of this function while we are at it.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/name-rev.c | 45 +++++++++++++++++++++++++--------------------
 1 file changed, 25 insertions(+), 20 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 8af2cfa..ebbf541 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -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);
 		}
 	}
 }
-- 
1.7.12.286.g9df01f7

[PATCH v2 3/6] name-rev: --weight option

[Junio C Hamano]

Instead of naming a rev after a tip that is topologically closest,
use the tip that is the oldest one among those which contain the
rev.

The semantics "name-rev --weight" would give us is closer to what
people expect from "describe --contains".

Note that this is fairly expensive to compute; a later change in the
series will cache the weight value using notes-cache.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/name-rev.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 102 insertions(+), 2 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index ebbf541..7cdb758 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -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(),
 	};
 
-- 
1.7.12.286.g9df01f7

[PATCH v2 4/6] name-rev --weight: cache the computed weight in notes

[Junio C Hamano]

With the "weight" assigned to tip of each ref, we can give more
intuitive results from "name-rev" that is more suitable to answer
"what is the oldest tag that contains this commit?"  However, this
number is very expensive to compute.

Use the notes-cache mechanism to cache this value.  The result
becomes usable again.

    (priming the cache from scratch)
    $ rm .git/refs/notes/name-rev-weight
    $ /usr/bin/time git name-rev --weight --tags 0136db586c
    0136db586c tags/v3.5-rc1~83^2~81^2~76
    6.06user 0.46system 0:06.54elapsed 99%CPU (0avgtext+0avgdata 1861456maxresident)k
    8inputs+16outputs (0major+128576minor)pagefaults 0swaps

    (with cache already primed)
    $ /usr/bin/time git name-rev --weight --tags 0136db586c
    0136db586c tags/v3.5-rc1~83^2~81^2~76
    0.50user 0.22system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 244224maxresident)k
    0inputs+0outputs (0major+16062minor)pagefaults 0swaps

    (the old "shortest path" version)
    $ /usr/bin/time git name-rev --tags 0136db586c
    0136db586c tags/v3.6-rc1~59^2~56^2~76
    0.31user 0.01system 0:00.32elapsed 100%CPU (0avgtext+0avgdata 243488maxresident)k
    0inputs+0outputs (0major+16000minor)pagefaults 0swaps

This version does not invalidate the cache in the presense of
modified grafts and object replacement, but in a later version we
can compute a hash of the grafts and replacement data and pass it as
the validity token to automatically invalidate the cache when these
data that affects the perceived topology change.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/name-rev.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 51 insertions(+), 5 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 7cdb758..d78eedd 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -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;
 }
-- 
1.7.12.286.g9df01f7

[PATCH v2 5/6] name-rev --weight: tests and documentation

[Junio C Hamano]

We are almost there...

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Documentation/git-name-rev.txt | 14 ++++++++--
 t/t6039-name-rev.sh            | 62 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 73 insertions(+), 3 deletions(-)
 create mode 100755 t/t6039-name-rev.sh

diff --git a/Documentation/git-name-rev.txt b/Documentation/git-name-rev.txt
index ad1d146..f40027a 100644
--- a/Documentation/git-name-rev.txt
+++ b/Documentation/git-name-rev.txt
@@ -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
 -------
 
diff --git a/t/t6039-name-rev.sh b/t/t6039-name-rev.sh
new file mode 100755
index 0000000..315ce14
--- /dev/null
+++ b/t/t6039-name-rev.sh
@@ -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
-- 
1.7.12.286.g9df01f7

[PATCH v2 6/6] describe --contains: use "name-rev --weight"

[Junio C Hamano]

And this is the logical conclusion of the series, to
allow 0136db586c in the kernel history to be described
as v3.5-rc1~83^2~81^2~76, not as v3.6-rc1~59^2~56^2~76.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/describe.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index 9f63067..fbd5be5 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -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) {
-- 
1.7.12.286.g9df01f7

[PATCH 3.5/6] name-rev --weight: trivial optimization

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Instead of naming a rev after a tip that is topologically closest,
> use the tip that is the oldest one among those which contain the
> rev.
>
> The semantics "name-rev --weight" would give us is closer to what
> people expect from "describe --contains".
>
> Note that this is fairly expensive to compute; a later change in the
> series will cache the weight value using notes-cache.
>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>

Here is a trivial optimization on top of the one from the other day.

-- >8 --
It often happens that immediately after traversing from v1.2.3 to
find out its weight, we are asked to see if another commit v1.2.0
is heavier than that.

Because the commits that are reachable from v1.2.3 are painted with
the SHOWN flag until the next "rev-list" traversal, we can notice
that the new commit v1.2.0 is reachable from v1.2.3 without doing
any traversal.  We cannot learn exactly how much it weighs, but we
can tell it must weigh less than v1.2.3, and that is all that the
caller wants to know.

In the kernel history, "git name-rev --tags 0136db586c" which
started this topic needs 26k calls to tip_weight_cmp().  13k of them
are comparisons between tips based on the same ref and answered
without computing any weight.  Among the remaining 13k, 1.8k
comparisons are answered with this trivial "fast-forward"
optimization.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/name-rev.c | 37 +++++++++++++++++++++++++++++++++----
 1 file changed, 33 insertions(+), 4 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 7cdb758..809553b 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -32,6 +32,9 @@ struct rev_name {
  */
 static int use_weight;
 
+/* To optimize revision traversal */
+static struct commit *painted_commit;
+
 /*
  * NEEDSWORK: the result of this computation must be cached to
  * a dedicated notes tree, keyed by the commit object name.
@@ -47,15 +50,15 @@ static int compute_ref_weight(struct commit *commit)
 	prepare_revision_walk(&revs);
 	while (get_revision(&revs))
 		weight++;
+	painted_commit = commit;
 	return weight;
 }
 
-static int ref_weight(const char *refname, size_t reflen)
+static struct commit *ref_commit(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))
@@ -65,9 +68,16 @@ static int ref_weight(const char *refname, size_t reflen)
 	commit = lookup_commit_reference_gently(sha1, 0);
 	if (!commit)
 		die("Internal error: cannot look up commit '%s'", buf.buf);
+	return commit;
+}
+
+static int ref_weight(struct commit *commit, const char *refname, size_t reflen)
+{
+	struct rev_name *name;
+
 	name = commit->util;
 	if (!name)
-		die("Internal error: a tip without name '%s'", buf.buf);
+		die("Internal error: a tip without name '%.*s'", (int) reflen, refname);
 	if (!name->weight)
 		name->weight = compute_ref_weight(commit);
 	return name->weight;
@@ -76,6 +86,7 @@ static int ref_weight(const char *refname, size_t reflen)
 static int tip_weight_cmp(const char *a, const char *b)
 {
 	size_t reflen_a, reflen_b;
+	struct commit *commit_a, *commit_b;
 	static const char traversal[] = "^~";
 
 	/*
@@ -89,7 +100,25 @@ static int tip_weight_cmp(const char *a, const char *b)
 	if (reflen_a == reflen_b && !memcmp(a, b, reflen_a))
 		return 0;
 
-	return ref_weight(a, reflen_a) - ref_weight(b, reflen_b);
+	commit_a = ref_commit(a, reflen_a);
+	commit_b = ref_commit(b, reflen_b);
+
+	/* Have we painted either one of these recently? */
+	if (commit_a == painted_commit &&
+	    (commit_b->object.flags & SHOWN)) {
+		/*
+		 * We know b can be reached from a, so b must be older
+		 * (lighter, as it has fewer commits behind it) than
+		 * a.
+		 */
+		return 1;
+	} else if (commit_b == painted_commit &&
+		   (commit_a->object.flags & SHOWN)) {
+		/* Likewise */
+		return -1;
+	}
+
+	return ref_weight(commit_a, a, reflen_a) - ref_weight(commit_b, b, reflen_b);
 }
 
 static long cutoff = LONG_MAX;
-- 
1.7.12.321.g60f00e5