On Mon, Aug 27, 2007 at 12:37:33PM +0100, Johannes Schindelin wrote:
> 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.
That's a clever trick, and I think it should work in most cases as long
as there are fewer than 65535 generations (though I haven't really
thought hard about it).
Here's my alternate approach which builds a stack of merge traversals,
and let's you compare two stacks (it uses the same criteria as the
original, but now we have the other generational information accessible
for comparison).
It comes up with the answer Uwe expects for his problem commit, and I
think in general is the "right" way to do this. Certainly the code looks
much clearer to me, but that's probably quite subjective. :) And it
should open up the door to alternative comparison mechanisms (Uwe had
mentioned an "oldest" flag, which should be possible, though there might
be assumptions in the name_rev recursion that need to be tweaked).
-- >8 --
name-rev: keep track of all generations, not just latest
Previously, name-rev found the "best" name for a rev by
choosing the one with the fewest number of merge traversals
and first-parent generations. This led to problems when
comparing a tip_name of "foo~1000" to "bar~500"; the
generational numbers were never compared.
This would manifest itself as choosing a non-optimal path to
a particular rev. For example, in the linux-2.6 repo, commit
0567a0c022d5b343370a343121f38fd89925de55 was named as:
tags/v2.6.22~1686^2~1^3~5
when it could be:
tags/v2.6.22-rc1~1009^2~1^3~5
To address this, when we follow a non-first-parent merge,
instead of turning the generation number into a string
(which we cease to compare), we keep a stack of merges, each
with a parent number and a generation.
The two tags above would be represented as (respectively):
tags/v2.6.22, (1/1686, 2/1, 3/5)
tags/v2.6.22-rc1, (1/1009, 2/1, 3/5)
Given these two data structures, we can decide which one is
a better name by comparing the number of merge traversals,
and the generational length of each traversal.
---
builtin-name-rev.c | 183 +++++++++++++++++++++++++++------------------------
1 files changed, 97 insertions(+), 86 deletions(-)
diff --git a/builtin-name-rev.c b/builtin-name-rev.c
index 9830595..099d65b 100644
--- a/builtin-name-rev.c
+++ b/builtin-name-rev.c
@@ -9,17 +9,37 @@
static const char name_rev_usage[] =
"git-name-rev [--tags | --refs=<pattern>] ( --all | --stdin | committish [committish...] )\n";
+#define MAX_GENERATIONS 32
typedef struct rev_name {
- const char *tip_name;
- int merge_traversals;
- int generation;
+ const char *ref;
+ struct {
+ unsigned char parent;
+ unsigned long n;
+ } generations[MAX_GENERATIONS];
+ int len;
} 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)
+static void print_rev_name(struct rev_name *name);
+
+static int rev_name_cmp(rev_name *a, rev_name *b)
+{
+ int i;
+ if (a->len < b->len)
+ return -1;
+ else if (a->len > b->len)
+ return 1;
+ for (i = 0; i < a->len; i++) {
+ if (a->generations[i].n < b->generations[i].n)
+ return -1;
+ else if (a->generations[i].n > b->generations[i].n)
+ return 1;
+ }
+ return 0;
+}
+
+static void name_rev(struct commit *commit, rev_name *cur)
{
struct rev_name *name = (struct rev_name *)commit->util;
struct commit_list *parents;
@@ -31,61 +51,39 @@ static void name_rev(struct commit *commit,
if (commit->date < cutoff)
return;
- if (deref) {
- char *new_name = xmalloc(strlen(tip_name)+3);
- strcpy(new_name, tip_name);
- strcat(new_name, "^0");
- tip_name = new_name;
-
- if (generation)
- 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 {
- printf(" not as good as %s~%d\n",
- name->tip_name, name->generation);
- return;
+ memcpy(name, cur, sizeof(*name));
}
+ else if (rev_name_cmp(cur, name) < 0)
+ memcpy(name, cur, sizeof(*name));
+ 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);
-
- 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);
-
- name_rev(parents->item, new_name,
- merge_traversals + 1 , 0, 0);
- } else {
- name_rev(parents->item, tip_name, merge_traversals,
- generation + 1, 0);
+ if (cur->len == MAX_GENERATIONS)
+ return;
+ cur->generations[cur->len].parent = parent_number;
+ cur->generations[cur->len].n = 0;
+ cur->len++;
+ name_rev(parents->item, cur);
+ cur->len--;
+ }
+ else if (cur->len == 0) {
+ cur->generations[0].parent = 1;
+ cur->generations[0].n = 1;
+ cur->len = 1;
+ name_rev(parents->item, cur);
+ cur->len = 0;
+ }
+ else {
+ cur->generations[cur->len-1].n++;
+ name_rev(parents->item, cur);
+ cur->generations[cur->len-1].n--;
}
}
}
@@ -101,6 +99,7 @@ static int name_ref(const char *path, const unsigned char *sha1, int flags, void
struct object *o = parse_object(sha1);
struct name_ref_data *data = cb_data;
int deref = 0;
+ struct rev_name name;
if (data->tags_only && prefixcmp(path, "refs/tags/"))
return 0;
@@ -127,38 +126,51 @@ 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.ref = xstrdup(path);
+ if (deref) {
+ name.generations[0].parent = 0;
+ name.generations[0].n = 0;
+ name.len = 1;
+ }
+ else
+ name.len = 0;
+ name_rev(commit, &name);
}
return 0;
}
-/* returns a static buffer */
-static const char* get_rev_name(struct object *o)
+static struct rev_name *get_rev_name(struct object *o)
{
- static char buffer[1024];
- struct rev_name *n;
struct commit *c;
-
if (o->type != OBJ_COMMIT)
- return "undefined";
+ return NULL;
c = (struct commit *) o;
- n = c->util;
- if (!n)
- return "undefined";
-
- if (!n->generation)
- return n->tip_name;
- else {
- int len = strlen(n->tip_name);
- if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
- len -= 2;
- snprintf(buffer, sizeof(buffer), "%.*s~%d", len, n->tip_name,
- n->generation);
-
- return buffer;
+ return c->util;
+}
+
+static void print_rev_name(struct rev_name *name)
+{
+ int i;
+
+ if (!name) {
+ fputs("undefined", stdout);
+ return;
+ }
+
+ fputs(name->ref, stdout);
+ for (i = 0; i < name->len; i++) {
+ if (name->generations[i].parent != 1)
+ printf("^%d", name->generations[i].parent);
+ if (name->generations[i].n > 0)
+ printf("~%lu", name->generations[i].n);
}
}
+static void print_object_name(struct object *o)
+{
+ print_rev_name(get_rev_name(o));
+}
+
int cmd_name_rev(int argc, const char **argv, const char *prefix)
{
struct object_array revs = { 0, 0, NULL };
@@ -246,26 +258,23 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
else if (++forty == 40 &&
!ishex(*(p+1))) {
unsigned char sha1[40];
- const char *name = "undefined";
char c = *(p+1);
+ struct object *o;
forty = 0;
*(p+1) = 0;
- if (!get_sha1(p - 39, sha1)) {
- struct object *o =
- lookup_object(sha1);
- if (o)
- name = get_rev_name(o);
- }
+ if (!get_sha1(p - 39, sha1))
+ o = lookup_object(sha1);
*(p+1) = c;
- if (!strcmp(name, "undefined"))
- continue;
-
fwrite(p_start, p - p_start + 1, 1,
stdout);
- printf(" (%s)", name);
+ if (get_rev_name(o)) {
+ printf(" (");
+ print_object_name(o);
+ printf(" )");
+ }
p_start = p + 1;
}
}
@@ -284,14 +293,16 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
continue;
if (!data.name_only)
printf("%s ", sha1_to_hex(obj->sha1));
- printf("%s\n", get_rev_name(obj));
+ print_object_name(obj);
+ printf("\n");
}
} else {
int i;
for (i = 0; i < revs.nr; i++) {
if (!data.name_only)
printf("%s ", revs.objects[i].name);
- printf("%s\n", get_rev_name(revs.objects[i].item));
+ print_object_name(revs.objects[i].item);
+ printf("\n");
}
}
--
1.5.3.rc6.845.g365da-dirty
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
