name-rev does not show the shortest path

name-rev does not show the shortest path

[Uwe Kleine-König]

Hello,

I want to check to which kernel version I need to upgrade to get a
certain feature.  For my case it was introduced in 0567a0c022d5b.

	zeisberg@cassiopeia:~/gsrc/linux-2.6$ rev=0567a0c022d5b343370a343121f38fd89925de55

	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev
	0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5

	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev
	0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1009^2~1^3~5

I don't now the underlaying algorithm, maybe it's to get a short string?

Anyhow I want to know the earliest tag that includes this patch?  Is
there something I missed?

I remember there was a similar discussion regarding describe.

BTW: gitk does the right thing, it says:

	Follows: v2.6.21-rc7
	Precedes: v2.6.22-rc1

(called with 

	zeisberg@cassiopeia:~/gsrc/linux-2.6$ gitk 0567a0c022d5b343370a343121f38fd89925de55^..0567a0c022d5b343370a343121f38fd89925de55
)

I didn't check how it does that though.

Best regards
Uwe

-- 
Uwe Kleine-König

exit vi, lesson I:
: q ! <CR>

Re: name-rev does not show the shortest path

[Julian Phillips]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1005 bytes --]

On Thu, 23 Aug 2007, Uwe Kleine-König wrote:

> Hello,
>
> I want to check to which kernel version I need to upgrade to get a
> certain feature.  For my case it was introduced in 0567a0c022d5b.
>
> 	zeisberg@cassiopeia:~/gsrc/linux-2.6$ rev=0567a0c022d5b343370a343121f38fd89925de55
>
> 	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev
> 	0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5
>
> 	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev
> 	0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1009^2~1^3~5
>
> I don't now the underlaying algorithm, maybe it's to get a short string?
>
> Anyhow I want to know the earliest tag that includes this patch?  Is
> there something I missed?
>
> I remember there was a similar discussion regarding describe.

git describe --contains 0567a0c022d5b

probably a 1.5.3 feature? (certainly doesn't exist in 1.5.2.2)

-- 
Julian

  ---
Man who sleep in beer keg wake up sticky.

Re: name-rev does not show the shortest path

[Uwe Kleine-König]

Hello Julian,

Julian Phillips wrote:
> On Thu, 23 Aug 2007, Uwe Kleine-König wrote:
> >I want to check to which kernel version I need to upgrade to get a
> >certain feature.  For my case it was introduced in 0567a0c022d5b.
> >
> >	zeisberg@cassiopeia:~/gsrc/linux-2.6$ 
> >	rev=0567a0c022d5b343370a343121f38fd89925de55
> >
> >	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev
> >	0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5
> >
> >	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev
> >	0567a0c022d5b343370a343121f38fd89925de55 
> >	tags/v2.6.22-rc1~1009^2~1^3~5
> >
> >I don't now the underlaying algorithm, maybe it's to get a short string?
> >
> >Anyhow I want to know the earliest tag that includes this patch?  Is
> >there something I missed?
> >
> >I remember there was a similar discussion regarding describe.
> 
> git describe --contains 0567a0c022d5b
> 
> probably a 1.5.3 feature? (certainly doesn't exist in 1.5.2.2)
That command says v2.6.22~1686^2~1^3~5, too.  That is, it doesn't use
the "older" v2.6.22-rc1 tag as a basis.

Best regards
Uwe


-- 
Uwe Kleine-König

http://www.google.com/search?q=1+degree+celsius+in+kelvin

Re: name-rev does not show the shortest path

[Julian Phillips]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1599 bytes --]

On Fri, 24 Aug 2007, Uwe Kleine-König wrote:

> Hello Julian,
>
> Julian Phillips wrote:
>> On Thu, 23 Aug 2007, Uwe Kleine-König wrote:
>>> I want to check to which kernel version I need to upgrade to get a
>>> certain feature.  For my case it was introduced in 0567a0c022d5b.
>>>
>>> 	zeisberg@cassiopeia:~/gsrc/linux-2.6$
>>> 	rev=0567a0c022d5b343370a343121f38fd89925de55
>>>
>>> 	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev
>>> 	0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22~1686^2~1^3~5
>>>
>>> 	zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev
>>> 	0567a0c022d5b343370a343121f38fd89925de55
>>> 	tags/v2.6.22-rc1~1009^2~1^3~5
>>>
>>> I don't now the underlaying algorithm, maybe it's to get a short string?
>>>
>>> Anyhow I want to know the earliest tag that includes this patch?  Is
>>> there something I missed?
>>>
>>> I remember there was a similar discussion regarding describe.
>>
>> git describe --contains 0567a0c022d5b
>>
>> probably a 1.5.3 feature? (certainly doesn't exist in 1.5.2.2)
> That command says v2.6.22~1686^2~1^3~5, too.  That is, it doesn't use
> the "older" v2.6.22-rc1 tag as a basis.

From a quick look at the code, that's not surprising, it runs "git 
name-rev --name-only --tags" under the bonnet - so not helpful at all, 
sorry.

So now I wonder how useful --contains really is ... I would have expected 
to always get the "closest" tag.  ~1009^2~1^3~5 seems closer than 
~1686^2~1^3~5 to me ... ho hum.

-- 
Julian

  ---
And that's the way it is...
 		-- Walter Cronkite

Re: name-rev does not show the shortest path

[Junio C Hamano]

Julian Phillips <julian@quantumfyre.co.uk> writes:

> From a quick look at the code, that's not surprising, it runs "git
> name-rev --name-only --tags" under the bonnet - so not helpful at all,
> sorry.
>
> So now I wonder how useful --contains really is ... I would have
> expected to always get the "closest" tag.  ~1009^2~1^3~5 seems closer
> than ~1686^2~1^3~5 to me ... ho hum.

The usefulness of --contains is only to provide a nicer looking
shortcut to older name-rev program, as more people are already
familiar with "git describe".  It does not improve name-rev.

I _think_ name-rev goes for shorter-to-type tags and does not
have any other heuristics.  Dscho?

Re: name-rev does not show the shortest path

[Johannes Schindelin]

Hi,

On Fri, 24 Aug 2007, Junio C Hamano wrote:

> I _think_ name-rev goes for shorter-to-type tags and does not have any 
> other heuristics.  Dscho?

I briefly looked into this, and did not find out why it is behaving that 
way.  It _should_ pick the closer one with this code:

        } else if (name->merge_traversals > merge_traversals ||
                        (name->merge_traversals == merge_traversals &&
                         name->generation > generation)) {

However, it did not even get to that code in my tests.  I'll have to look 
at that problem closer in a quiet moment (which I will not have for at 
least another 24 hours).

Ciao,
Dscho

Re: name-rev does not show the shortest path

[Jeff King]

On Sat, Aug 25, 2007 at 05:04:33PM +0200, Johannes Schindelin wrote:

> I briefly looked into this, and did not find out why it is behaving that 
> way.  It _should_ pick the closer one with this code:
> 
>         } else if (name->merge_traversals > merge_traversals ||
>                         (name->merge_traversals == merge_traversals &&
>                          name->generation > generation)) {
> 
> However, it did not even get to that code in my tests.  I'll have to look 
> at that problem closer in a quiet moment (which I will not have for at 
> least another 24 hours).

It does execute that code, just not for the rev in question. We hit the
third part of that conditional and stop recursing on a different rev, so
we only touch our "interesting" rev one time.

That being said, I think this test is totally bogus. You're just looking
at the generation and merge traversals from some tip. However, the tip
_isn't_ the actual ref, but instead gets re-written as a string when we
follow a merge. That string contains important generational information
that is no longer taken into account, so you end up with things like
"foo~999" with generation "3" is better than "bar~10" with generation
"5".

Here is a patch (below) that tracks an absolute "distance to ref" and at
least names the rev in question after v2.6.22-rc1. However, because it
is now preferring "distance to ref" strictly over merge traversals, it
seems to generate some obscenely long names:

0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1^2^2^2~11^2~13^2~8^2~1^3~5

So perhaps there is a more sane metric, but I'd have to think about it
more.

-Peff

---
diff --git a/builtin-name-rev.c b/builtin-name-rev.c
index 61eba34..c003e20 100644
--- a/builtin-name-rev.c
+++ b/builtin-name-rev.c
@@ -13,13 +13,14 @@ typedef struct rev_name {
 	const char *tip_name;
 	int merge_traversals;
 	int generation;
+	int distance;
 } rev_name;
 
 static long cutoff = LONG_MAX;
 
 static void name_rev(struct commit *commit,
 		const char *tip_name, int merge_traversals, int generation,
-		int deref)
+		int deref, int distance)
 {
 	struct rev_name *name = (struct rev_name *)commit->util;
 	struct commit_list *parents;
@@ -45,13 +46,16 @@ static void name_rev(struct commit *commit,
 		name = xmalloc(sizeof(rev_name));
 		commit->util = name;
 		goto copy_data;
-	} else if (name->merge_traversals > merge_traversals ||
-			(name->merge_traversals == merge_traversals &&
-			 name->generation > generation)) {
+	} else if (name->distance > distance ||
+			(name->distance == distance &&
+			 name->merge_traversals > merge_traversals ||
+			 (name->merge_traversals == merge_traversals &&
+			  name->generation > generation))) {
 copy_data:
 		name->tip_name = tip_name;
 		name->merge_traversals = merge_traversals;
 		name->generation = generation;
+		name->distance = distance;
 	} else
 		return;
 
@@ -75,10 +79,10 @@ copy_data:
 						parent_number);
 
 			name_rev(parents->item, new_name,
-				merge_traversals + 1 , 0, 0);
+				merge_traversals + 1 , 0, 0, distance + 1);
 		} else {
 			name_rev(parents->item, tip_name, merge_traversals,
-				generation + 1, 0);
+				generation + 1, 0, distance + 1);
 		}
 	}
 }
@@ -120,7 +124,7 @@ static int name_ref(const char *path, const unsigned char *sha1, int flags, void
 		else if (!prefixcmp(path, "refs/"))
 			path = path + 5;
 
-		name_rev(commit, xstrdup(path), 0, 0, deref);
+		name_rev(commit, xstrdup(path), 0, 0, deref, 0);
 	}
 	return 0;
 }

Re: name-rev does not show the shortest path

[Johannes Schindelin]

Hi,

On Sun, 26 Aug 2007, Jeff King wrote:

> On Sat, Aug 25, 2007 at 05:04:33PM +0200, Johannes Schindelin wrote:
> 
> > I briefly looked into this, and did not find out why it is behaving that 
> > way.  It _should_ pick the closer one with this code:
> > 
> >         } else if (name->merge_traversals > merge_traversals ||
> >                         (name->merge_traversals == merge_traversals &&
> >                          name->generation > generation)) {
> > 
> > However, it did not even get to that code in my tests.  I'll have to look 
> > at that problem closer in a quiet moment (which I will not have for at 
> > least another 24 hours).
> 
> It does execute that code, just not for the rev in question. We hit the
> third part of that conditional and stop recursing on a different rev, so
> we only touch our "interesting" rev one time.

Yes, I guessed as much.

> That being said, I think this test is totally bogus. You're just looking
> at the generation and merge traversals from some tip. However, the tip
> _isn't_ the actual ref, but instead gets re-written as a string when we
> follow a merge. That string contains important generational information
> that is no longer taken into account, so you end up with things like
> "foo~999" with generation "3" is better than "bar~10" with generation
> "5".

But this did not happen here, right?  Just the first part was different...

> Here is a patch (below) that tracks an absolute "distance to ref" and at
> least names the rev in question after v2.6.22-rc1. However, because it
> is now preferring "distance to ref" strictly over merge traversals, it
> seems to generate some obscenely long names:
> 
> 0567a0c022d5b343370a343121f38fd89925de55 tags/v2.6.22-rc1~1^2^2^2~11^2~13^2~8^2~1^3~5
> 
> So perhaps there is a more sane metric, but I'd have to think about it
> more.

The old code _should_ have worked; it is more likely that your different 
metric just hides the bug.  The old metric tried to favour less merge 
traversals over more traversals, but at the same time, it favoured smaller 
numbers over larger ones (but as you found out, only in the last 
component).

I guess there is something else going on, such as the tag v2.6.22-rc1 
being marked uninteresting because v2.6.22 and its ancestors being 
traversed already.

Ciao,
Dscho

Re: name-rev does not show the shortest path

[Jeff King]

On Sun, Aug 26, 2007 at 05:38:22PM +0200, Johannes Schindelin wrote:

> > that is no longer taken into account, so you end up with things like
> > "foo~999" with generation "3" is better than "bar~10" with generation
> > "5".
> 
> But this did not happen here, right?  Just the first part was different...

Yes, in this case, I think the process is stopping because the
generations and merge traversals are the same for two paths, but the
'tip_name' information is indicating a much larger generational
difference from a ref. For example, "tags/v2.6.22-rc1~1131^2" loses out
to "tags/v2.6.22~1808^2", which seems very wrong.

I found it informative to instrument the code like this:

diff --git a/builtin-name-rev.c b/builtin-name-rev.c
index 61eba34..9830595 100644
--- a/builtin-name-rev.c
+++ b/builtin-name-rev.c
@@ -41,19 +41,26 @@ static void name_rev(struct commit *commit,
 			die("generation: %d, but deref?", generation);
 	}
 
+	printf("considering %s~%d\n", tip_name, generation);
 	if (name == NULL) {
 		name = xmalloc(sizeof(rev_name));
 		commit->util = name;
+		printf("  better than NULL\n");
 		goto copy_data;
 	} else if (name->merge_traversals > merge_traversals ||
 			(name->merge_traversals == merge_traversals &&
 			 name->generation > generation)) {
+		printf("  better than %s~%d\n",
+				name->tip_name, name->generation);
 copy_data:
 		name->tip_name = tip_name;
 		name->merge_traversals = merge_traversals;
 		name->generation = generation;
-	} else
+	} else {
+		printf("  not as good as %s~%d\n",
+				name->tip_name, name->generation);
 		return;
+	}
 
 	for (parents = commit->parents;
 			parents;


> The old code _should_ have worked; it is more likely that your different 
> metric just hides the bug.  The old metric tried to favour less merge 
> traversals over more traversals, but at the same time, it favoured smaller 
> numbers over larger ones (but as you found out, only in the last 
> component).

Right, the problem is that we have effectively _thrown away_ the
"smaller numbers over larger ones" information for components other than
the last. I wonder if what we really want is to maintain a list of
generations, one per merge traversal.

So that foo~500^2~20 and bar~499^2~20 would be represented as:

  [500, 21]
  [499, 21]

And then you could compare names by favoring smaller numbers in earlier
traversals (you could still use "fewer merge traversals" as a metric
before that, as well).

> I guess there is something else going on, such as the tag v2.6.22-rc1 
> being marked uninteresting because v2.6.22 and its ancestors being 
> traversed already.

I don't think that is the case; it tries to name quite a few revs based
on v2.6.22-rc1, but they lose out to existing names given when
traversing from v2.6.22.

-Peff

Re: name-rev does not show the shortest path

[Johannes Schindelin]

Hi,

On Mon, 27 Aug 2007, Jeff King wrote:

> On Sun, Aug 26, 2007 at 05:38:22PM +0200, Johannes Schindelin wrote:
> 
> > The old code _should_ have worked; it is more likely that your 
> > different metric just hides the bug.  The old metric tried to favour 
> > less merge traversals over more traversals, but at the same time, it 
> > favoured smaller numbers over larger ones (but as you found out, only 
> > in the last component).
> 
> Right, the problem is that we have effectively _thrown away_ the
> "smaller numbers over larger ones" information for components other than
> the last.

You're right.  I misremembered name-rev to use a fifo instead of stupid 
recursion.

Will fix.

Ciao,
Dscho

Re: name-rev does not show the shortest path

[Johannes Schindelin]

Hi,

On Mon, 27 Aug 2007, Johannes Schindelin wrote:

> On Mon, 27 Aug 2007, Jeff King wrote:
> 
> > On Sun, Aug 26, 2007 at 05:38:22PM +0200, Johannes Schindelin wrote:
> > 
> > > The old code _should_ have worked; it is more likely that your 
> > > different metric just hides the bug.  The old metric tried to favour 
> > > less merge traversals over more traversals, but at the same time, it 
> > > favoured smaller numbers over larger ones (but as you found out, only 
> > > in the last component).
> > 
> > Right, the problem is that we have effectively _thrown away_ the
> > "smaller numbers over larger ones" information for components other than
> > the last.
> 
> You're right.  I misremembered name-rev to use a fifo instead of stupid 
> recursion.
> 
> Will fix.

Seems that this is not really good (having a fifo):

-- snip --
 builtin-name-rev.c |  108 +++++++++++++++++++++++++++++++---------------------
 1 files changed, 65 insertions(+), 43 deletions(-)

diff --git a/builtin-name-rev.c b/builtin-name-rev.c
index 61eba34..e42e436 100644
--- a/builtin-name-rev.c
+++ b/builtin-name-rev.c
@@ -11,19 +11,22 @@ static const char name_rev_usage[] =
 
 typedef struct rev_name {
 	const char *tip_name;
-	int merge_traversals;
 	int generation;
 } rev_name;
 
 static long cutoff = LONG_MAX;
 
+/* The parents of these refs are potentially unnamed */
+static struct commit_list *rev_queue, *rev_queue_end;
+
 static void name_rev(struct commit *commit,
-		const char *tip_name, int merge_traversals, int generation,
+		const char *tip_name, int generation,
 		int deref)
 {
 	struct rev_name *name = (struct rev_name *)commit->util;
-	struct commit_list *parents;
-	int parent_number = 1;
+
+	if (commit->util)
+		return;
 
 	if (!commit->object.parsed)
 		parse_commit(commit);
@@ -41,46 +44,20 @@ static void name_rev(struct commit *commit,
 			die("generation: %d, but deref?", generation);
 	}
 
-	if (name == NULL) {
-		name = xmalloc(sizeof(rev_name));
-		commit->util = name;
-		goto copy_data;
-	} else if (name->merge_traversals > merge_traversals ||
-			(name->merge_traversals == merge_traversals &&
-			 name->generation > generation)) {
-copy_data:
-		name->tip_name = tip_name;
-		name->merge_traversals = merge_traversals;
-		name->generation = generation;
-	} else
-		return;
-
-	for (parents = commit->parents;
-			parents;
-			parents = parents->next, parent_number++) {
-		if (parent_number > 1) {
-			int len = strlen(tip_name);
-			char *new_name = xmalloc(len +
-				1 + decimal_length(generation) +  /* ~<n> */
-				1 + 2 +				  /* ^NN */
-				1);
+	name = xmalloc(sizeof(rev_name));
+	commit->util = name;
+	name->tip_name = tip_name;
+	name->generation = generation;
 
-			if (len > 2 && !strcmp(tip_name + len - 2, "^0"))
-				len -= 2;
-			if (generation > 0)
-				sprintf(new_name, "%.*s~%d^%d", len, tip_name,
-						generation, parent_number);
-			else
-				sprintf(new_name, "%.*s^%d", len, tip_name,
-						parent_number);
+	if (rev_queue_end)
+		rev_queue_end = rev_queue_end->next =
+			xmalloc(sizeof(struct commit_list));
+	else
+		rev_queue = rev_queue_end =
+			xmalloc(sizeof(struct commit_list));
 
-			name_rev(parents->item, new_name,
-				merge_traversals + 1 , 0, 0);
-		} else {
-			name_rev(parents->item, tip_name, merge_traversals,
-				generation + 1, 0);
-		}
-	}
+	rev_queue_end->item = commit;
+	rev_queue_end->next = NULL;
 }
 
 struct name_ref_data {
@@ -120,11 +97,46 @@ static int name_ref(const char *path, const unsigned char *sha1, int flags, void
 		else if (!prefixcmp(path, "refs/"))
 			path = path + 5;
 
-		name_rev(commit, xstrdup(path), 0, 0, deref);
+		name_rev(commit, xstrdup(path), 0, deref);
 	}
 	return 0;
 }
 
+static void name_parents(struct commit *commit)
+{
+	struct rev_name *n = commit->util;
+	int parent_number = 1;
+	struct commit_list *parents;
+
+	if (!n)
+		die("Huh?");
+	for (parents = commit->parents;
+			parents;
+			parents = parents->next, parent_number++) {
+		if (parent_number > 1) {
+			int len = strlen(n->tip_name);
+			char *new_name = xmalloc(len +
+				1 + decimal_length(n->generation) +  /* ~<n> */
+				1 + 2 +				     /* ^NN */
+				1);
+
+			if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
+				len -= 2;
+			if (n->generation > 0)
+				sprintf(new_name, "%.*s~%d^%d", len,
+						n->tip_name, n->generation,
+						parent_number);
+			else
+				sprintf(new_name, "%.*s^%d", len,
+						n->tip_name, parent_number);
+
+			name_rev(parents->item, new_name, 0, 0);
+		} else
+			name_rev(parents->item, n->tip_name,
+					n->generation + 1, 0);
+	}
+}
+
 /* returns a static buffer */
 static const char* get_rev_name(struct object *o)
 {
@@ -135,6 +147,16 @@ static const char* get_rev_name(struct object *o)
 	if (o->type != OBJ_COMMIT)
 		return "undefined";
 	c = (struct commit *) o;
+	while (c->util == NULL) {
+		struct commit_list *current = rev_queue;
+
+		name_parents(current->item);
+		rev_queue = current->next;
+		if (!rev_queue)
+			rev_queue_end = NULL;
+		free(current);
+	}
+
 	n = c->util;
 	if (!n)
 		return "undefined";
-- snap --

It outputs this:

git name-rev --tags 0567a0c022d5b343370a343121f38fd89925de55
0567a0c[...] tags/v2.6.22-rc1~1^2^2^2~11^2~13^2~8^2~1^3~5

Not really nice.

Ciao,
Dscho

[PATCH] name-rev: Fix non-shortest description

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2798 bytes --]


Uwe Kleine-König noticed that under certain circumstances, name-rev
picked a non-optimal tag.  Jeff King analyzed that name-rev only
takes into account the number of merge traversals, and then the
_last_ number in the description.

As an easy way to fix it, use a weighting factor for merge traversals:
A merge traversal is now made 65535 times more expensive than a
first-parent traversal.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---

	On Thu, 23 Aug 2007, Uwe Kleine-K?nig wrote:

	> I want to check to which kernel version I need to upgrade to get 
	> a certain feature.  For my case it was introduced in 
	> 0567a0c022d5b.
	> 
	> zeisberg@cassiopeia:~/gsrc/linux-2.6$ 
	> 	rev=0567a0c022d5b343370a343121f38fd89925de55
	> 
	> zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --tags $rev
	> 0567a0c02[...] tags/v2.6.22~1686^2~1^3~5
	> 
	> zeisberg@cassiopeia:~/gsrc/linux-2.6$ git name-rev --refs=*-rc1 $rev
	> 0567a0c02[...] tags/v2.6.22-rc1~1009^2~1^3~5

	This fixes it.

 builtin-name-rev.c |   21 +++++++++++----------
 1 files changed, 11 insertions(+), 10 deletions(-)

diff --git a/builtin-name-rev.c b/builtin-name-rev.c
index 61eba34..03083e9 100644
--- a/builtin-name-rev.c
+++ b/builtin-name-rev.c
@@ -11,14 +11,17 @@ static const char name_rev_usage[] =
 
 typedef struct rev_name {
 	const char *tip_name;
-	int merge_traversals;
 	int generation;
+	int distance;
 } rev_name;
 
 static long cutoff = LONG_MAX;
 
+/* How many generations are maximally preferred over _one_ merge traversal? */
+#define MERGE_TRAVERSAL_WEIGHT 65535
+
 static void name_rev(struct commit *commit,
-		const char *tip_name, int merge_traversals, int generation,
+		const char *tip_name, int generation, int distance,
 		int deref)
 {
 	struct rev_name *name = (struct rev_name *)commit->util;
@@ -45,13 +48,11 @@ static void name_rev(struct commit *commit,
 		name = xmalloc(sizeof(rev_name));
 		commit->util = name;
 		goto copy_data;
-	} else if (name->merge_traversals > merge_traversals ||
-			(name->merge_traversals == merge_traversals &&
-			 name->generation > generation)) {
+	} else if (name->distance > distance) {
 copy_data:
 		name->tip_name = tip_name;
-		name->merge_traversals = merge_traversals;
 		name->generation = generation;
+		name->distance = distance;
 	} else
 		return;
 
@@ -74,11 +75,11 @@ copy_data:
 				sprintf(new_name, "%.*s^%d", len, tip_name,
 						parent_number);
 
-			name_rev(parents->item, new_name,
-				merge_traversals + 1 , 0, 0);
+			name_rev(parents->item, new_name, 0,
+				distance + MERGE_TRAVERSAL_WEIGHT, 0);
 		} else {
-			name_rev(parents->item, tip_name, merge_traversals,
-				generation + 1, 0);
+			name_rev(parents->item, tip_name, generation + 1,
+				distance + 1, 0);
 		}
 	}
 }
-- 
1.5.3.rc6.52.g5113-dirty

Re: [PATCH] name-rev: Fix non-shortest description

[Uwe Kleine-König]

Johannes Schindelin wrote:
> 
> Uwe Kleine-König noticed that under certain circumstances, name-rev
> picked a non-optimal tag.  Jeff King analyzed that name-rev only
> takes into account the number of merge traversals, and then the
> _last_ number in the description.
> 
> As an easy way to fix it, use a weighting factor for merge traversals:
> A merge traversal is now made 65535 times more expensive than a
> first-parent traversal.
> 
> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Just from looking at the patch it seems to do what the log says.  It
passes the test suite and fixed my use case.  So:

Acked-by: Uwe Kleine-König <ukleinek@informatik.uni-freiburg.de>

But if I'd really prefer to know the "oldest" tag that includes the
given rev, I don't want that weighting.  I will try to come up with a
patch that introduces a flag.

Best regards and thanks to Johannes
Uwe

-- 
Uwe Kleine-König

primes where sieve (p:xs) = [ x | x<-xs, x `rem` p /= 0 ]; \
primes = map head (iterate sieve [2..])