Re: Funny 'git describe --contains' output

Junio C Hamano [off-list ref] writes:

Greg KH [off-list ref] writes:

quoted

In the Linux kernel tree, commit 0136db586c028f71e7cc21cc183064ff0d5919
is a bit "odd".

If I go to look to see what release it was in, I normally do:
	$ git describe --contains 0136db586c028f71e7cc21cc183064ff0d5919
	v3.6-rc1~59^2~56^2~76
...
Any ideas?

That is 59 + 1 + 56 + 1 + 76 = 193 steps away from the tag v3.6-rc1.

$ git name-rev --refs=refs/tags/v3.5-rc1 0136db58
0136db58 tags/v3.5-rc1~83^2~81^2~76

which is 83 + 1 + 81 + 1 + 76 = 242 steps away from that tag.

So it _is_ odd that the newly tagged tip merged a branch that had
smaller development since it merged the commit, but name-rev seems
to be measuring the steps it takes from the tags to reach the commit
and giving us the one that gives the shortest path correctly.

Obviously, that is not the same as "which tag is the oldest one
among the ones that can reach this commit?"

As is usual for what I say, the above is an explanation of what we
are seeing, not necessarily a justification.

Given a history of this shape:

        o---o---o---o TONS!!!
                     \
 ---o--o--o--o--o--Y--o---o---Z
     \   /               /
      \ /               /
       X---------------o

where Y is v3.5-rc1 and Z is v3.6-rc1, "name-rev X" measures the
distance of the shortest path between Z and X (Z^^2^ = 3 steps away)
and between Y and X (Y~3^2 = 4 steps away), and uses the tag with
the shortest path.

But in order to answer "which is the earlier tag that merges X",
what "name-rev" measures is not very interesting.

What we want to see is the tag whose "weight" (imagine these commits
are beads on strings, and you hold the tag between your fingers and
lift it, pulling all the commits behind it on the history) is the
smallest and reaches the commit X in question.  The distance on the
shortest path to X totally ignores tons of merges that went into the
mainline between Y and Z.  That is what makes name-rev not useful
for this purpose.

That "weight" is what Linus's "rev-list | wc -l" showed, but it is
fairly expensive to compute.  We do have a code that computes such
weight in the history bisection code (it computes this exact weight
for each and every commit that is still suspect, and picks the one
that is half-way).  We know how to compute it, but I suspect that
applying that code naively to name-rev would make it unusably slow.

On Tue, Aug 28, 2012 at 11:36:46PM -0700, Junio C Hamano wrote:

Junio C Hamano [off-list ref] writes:

quoted

Greg KH [off-list ref] writes:

quoted

In the Linux kernel tree, commit 0136db586c028f71e7cc21cc183064ff0d5919
is a bit "odd".

If I go to look to see what release it was in, I normally do:
	$ git describe --contains 0136db586c028f71e7cc21cc183064ff0d5919
	v3.6-rc1~59^2~56^2~76
...
Any ideas?

That is 59 + 1 + 56 + 1 + 76 = 193 steps away from the tag v3.6-rc1.

$ git name-rev --refs=refs/tags/v3.5-rc1 0136db58
0136db58 tags/v3.5-rc1~83^2~81^2~76

which is 83 + 1 + 81 + 1 + 76 = 242 steps away from that tag.

So it _is_ odd that the newly tagged tip merged a branch that had
smaller development since it merged the commit, but name-rev seems
to be measuring the steps it takes from the tags to reach the commit
and giving us the one that gives the shortest path correctly.

Obviously, that is not the same as "which tag is the oldest one
among the ones that can reach this commit?"

As is usual for what I say, the above is an explanation of what we
are seeing, not necessarily a justification.

Given a history of this shape:

        o---o---o---o TONS!!!
                     \
 ---o--o--o--o--o--Y--o---o---Z
     \   /               /
      \ /               /
       X---------------o

where Y is v3.5-rc1 and Z is v3.6-rc1, "name-rev X" measures the
distance of the shortest path between Z and X (Z^^2^ = 3 steps away)
and between Y and X (Y~3^2 = 4 steps away), and uses the tag with
the shortest path.

But in order to answer "which is the earlier tag that merges X",
what "name-rev" measures is not very interesting.

What we want to see is the tag whose "weight" (imagine these commits
are beads on strings, and you hold the tag between your fingers and
lift it, pulling all the commits behind it on the history) is the
smallest and reaches the commit X in question.  The distance on the
shortest path to X totally ignores tons of merges that went into the
mainline between Y and Z.  That is what makes name-rev not useful
for this purpose.

That "weight" is what Linus's "rev-list | wc -l" showed, but it is
fairly expensive to compute.  We do have a code that computes such
weight in the history bisection code (it computes this exact weight
for each and every commit that is still suspect, and picks the one
that is half-way).  We know how to compute it, but I suspect that
applying that code naively to name-rev would make it unusably slow.

Thanks for the full explaination.  "Normally" this never is an issue for
me, as this is the first time, in the history of Linux stable kernel
releases, that I've ever noticed this.  And I agree, it's probably not
something that can easily be resolved in git, given how it's calculated.

thanks,

greg k-h

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 is closer to what
people expect from "describe --contains".

Note that this is fairly expensive (see NEEDSWORK comment in the
code).

Signed-off-by: Junio C Hamano <redacted>
---
 builtin/name-rev.c | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 95 insertions(+), 2 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index ebbf541..69da41d 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
+ * 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_tip_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 tip_weight(const char *tip, size_t reflen)
+{
+	struct strbuf buf = STRBUF_INIT;
+	unsigned char sha1[20];
+	struct commit *commit;
+	struct rev_name *name;
+
+	strbuf_add(&buf, tip, reflen);
+	if (get_sha1(buf.buf, sha1))
+		die("Internal error: cannot parse tip '%s'", tip);
+	strbuf_release(&buf);
+
+	commit = lookup_commit_reference_gently(sha1, 0);
+	if (!commit)
+		die("Internal error: cannot look up commit '%s'", tip);
+	name = commit->util;
+	if (!name)
+		die("Internal error: a tip without name '%s'", tip);
+	if (!name->weight)
+		name->weight = compute_tip_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 tip_weight(a, reflen_a) - tip_weight(b, reflen_b);
+}
+
 static long cutoff = LONG_MAX;
 
 /* How many generations are maximally preferred over _one_ merge traversal? */

@@ -49,8 +128,20 @@ 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 {
+			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 +332,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.285.ga3d5fc0

In preparation for the 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 <redacted>
---
 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.285.ga3d5fc0

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

Signed-off-by: Junio C Hamano <redacted>
---
 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.285.ga3d5fc0

So here is an attempt to teach "name-rev" a mode that tries to base
its name on oldest tag that can reach the commit.  It needs the
reset_revision_walk() call recently added to the revision traversal
API, and applies to bcc0a3e (v1.7.11-rc0~111^2~2) or newer.

Note that this can benefit from caching, as the "weight" of the tag
(rather, the commit that is tagged) will never change once a history
is made, but that part is left as an exercise to the reader.

It correctly names 0136db586c in the kernel history as based on
v3.5-rc1 as tags/v3.5-rc1~83^2~81^2~76, not on v3.6-rc1, as we saw
on the list recently.

Once it is verified to operate correctly and updated to perform
properly, we can start passing --weight when "describe --contains"
runs the command.

Junio C Hamano (3):
  name-rev: lose unnecessary typedef
  name_rev: clarify when a new tip-name is assigned to a commit
  name-rev: --weight option (WIP)

 builtin/name-rev.c | 142 ++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 120 insertions(+), 22 deletions(-)

-- 
1.7.12.285.ga3d5fc0

On Wed, Aug 29, 2012 at 02:17:24PM -0700, Junio C Hamano wrote:

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.

When you wrote "oldest" here, I thought that meant you would do a
comparison on the taggerdate. But reading the implementation, you really
mean "topologically oldest".

I wonder, though, if the former would be sufficient for most people. Or
even just sorting based on the tag name. For example, taking Greg's
original example:

  $ commit=0136db586c028f71e7cc21cc183064ff0d5919
  $ oldest_tag=`git tag --contains $commit | sort -V | head -1`
  $ git name-rev --refs="refs/tags/$oldest_tag" $commit
  0136db586c028f71e7cc21cc183064ff0d5919 tags/v3.5~335^2~81^2~76

Of course "sort -V" is not portable, and it actually places -rc tags
after release tags (note that we found v3.5 here, not v3.5-rc1). But
that is an implementation detail that could be solved (either by a
better comparison function, or by just using taggerdate instead).

In some ways it is not as elegant (clock skew in your tag dates would be
relevant), but it is simple and performs well without needing to manage
a cache.

-Peff

From: "Junio C Hamano" <redacted>
Sent: Wednesday, August 29, 2012 10:17 PM

So here is an attempt to teach "name-rev" a mode that tries to base
its name on oldest tag that can reach the commit.  It needs the
reset_revision_walk() call recently added to the revision traversal
API, and applies to bcc0a3e (v1.7.11-rc0~111^2~2) or newer.

Note that this can benefit from caching, as the "weight" of the tag
(rather, the commit that is tagged) will never change once a history
is made, but that part is left as an exercise to the reader.

Is "--weight" the right term to use for the user (cli) interface? 
Wouldn't '--oldest' (or similar) be a better statement of what is 
desired (absent clock skew).

While 'weight' may be a good internal technical description it didn't 
convey to me what was being sought (maybe -- deepest'?).

It correctly names 0136db586c in the kernel history as based on
v3.5-rc1 as tags/v3.5-rc1~83^2~81^2~76, not on v3.6-rc1, as we saw
on the list recently.

Once it is verified to operate correctly and updated to perform
properly, we can start passing --weight when "describe --contains"
runs the command.

Junio C Hamano (3):
 name-rev: lose unnecessary typedef
 name_rev: clarify when a new tip-name is assigned to a commit
 name-rev: --weight option (WIP)

builtin/name-rev.c | 142 
++++++++++++++++++++++++++++++++++++++++++++---------
1 file changed, 120 insertions(+), 22 deletions(-)

-- 
1.7.12.285.ga3d5fc0