Re: name-rev does not show the shortest path

[Jeff King <peff@peff.net>]

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