From f35f5603f4f07c939754743b2a6cf61bb3a4694e Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 3 Apr 2008 02:12:06 -0700 Subject: revision traversal: --children option This adds a new --children option to the revision machinery. In addition to the list of parents, child commits of each commit are computed and stored as a decoration to each commit. Signed-off-by: Junio C Hamano diff --git a/revision.c b/revision.c index ffbed3f..979241e 100644 --- a/revision.c +++ b/revision.c @@ -9,6 +9,7 @@ #include "grep.h" #include "reflog-walk.h" #include "patch-ids.h" +#include "decorate.h" volatile show_early_output_fn_t show_early_output; @@ -1310,6 +1311,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch revs->no_walk = 0; continue; } + if (!strcmp(arg, "--children")) { + revs->children.name = "children"; + revs->limited = 1; + continue; + } opts = diff_opt_parse(&revs->diffopt, argv+i, argc-i); if (opts > 0) { @@ -1395,10 +1401,31 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch if (revs->reverse && revs->reflog_info) die("cannot combine --reverse with --walk-reflogs"); - + if (revs->parents && revs->children.name) + die("cannot combine --parents and --children"); return left; } +static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child) +{ + struct commit_list *l = xcalloc(1, sizeof(*l)); + + l->item = child; + l->next = add_decoration(&revs->children, &parent->object, l); +} + +static void set_children(struct rev_info *revs) +{ + struct commit_list *l; + for (l = revs->commits; l; l = l->next) { + struct commit *commit = l->item; + struct commit_list *p; + + for (p = commit->parents; p; p = p->next) + add_child(revs, p->item, commit); + } +} + int prepare_revision_walk(struct rev_info *revs) { int nr = revs->pending.nr; @@ -1427,6 +1454,8 @@ int prepare_revision_walk(struct rev_info *revs) return -1; if (revs->topo_order) sort_in_topological_order(&revs->commits, revs->lifo); + if (revs->children.name) + set_children(revs); return 0; } @@ -1504,6 +1533,11 @@ static int commit_match(struct commit *commit, struct rev_info *opt) commit->buffer, strlen(commit->buffer)); } +static inline int want_ancestry(struct rev_info *revs) +{ + return (revs->parents || revs->children.name); +} + enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit) { if (commit->object.flags & SHOWN) @@ -1524,13 +1558,13 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit) /* Commit without changes? */ if (commit->object.flags & TREESAME) { /* drop merges unless we want parenthood */ - if (!revs->parents) + if (!want_ancestry(revs)) return commit_ignore; /* non-merge - always ignore it */ if (!commit->parents || !commit->parents->next) return commit_ignore; } - if (revs->parents && rewrite_parents(revs, commit) < 0) + if (want_ancestry(revs) && rewrite_parents(revs, commit) < 0) return commit_error; } return commit_show; diff --git a/revision.h b/revision.h index c8b3b94..966116c 100644 --- a/revision.h +++ b/revision.h @@ -98,6 +98,7 @@ struct rev_info { struct diff_options pruning; struct reflog_walk_info *reflog_info; + struct decoration children; }; #define REV_TREE_SAME 0 -- cgit v0.10.2-6-g49f6 From 72276a3ecbe6353b83ab37e0ce96cc21c94cf6ee Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 3 Apr 2008 23:01:47 -0700 Subject: rev-list --children Just like --parents option shows the parents of commits, this shows the children of commits. Signed-off-by: Junio C Hamano diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt index 2648a55..e582395 100644 --- a/Documentation/rev-list-options.txt +++ b/Documentation/rev-list-options.txt @@ -42,6 +42,10 @@ format, often found in E-mail messages. Print the parents of the commit. +--children:: + + Print the children of the commit. + --timestamp:: Print the raw commit timestamp. diff --git a/builtin-rev-list.c b/builtin-rev-list.c index edc0bd3..9da2f76 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -36,6 +36,7 @@ static const char rev_list_usage[] = " --reverse\n" " formatting output:\n" " --parents\n" +" --children\n" " --objects | --objects-edge\n" " --unpacked\n" " --header | --pretty\n" @@ -84,6 +85,15 @@ static void show_commit(struct commit *commit) parents = parents->next; } } + if (revs.children.name) { + struct commit_list *children; + + children = lookup_decoration(&revs.children, &commit->object); + while (children) { + printf(" %s", sha1_to_hex(children->item->object.sha1)); + children = children->next; + } + } show_decorations(commit); if (revs.commit_format == CMIT_FMT_ONELINE) putchar(' '); -- cgit v0.10.2-6-g49f6 From f6c07d7d475ffaa67b817beb2635fd73a5e0e962 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Wed, 2 Apr 2008 22:17:53 -0700 Subject: builtin-blame.c: move prepare_final() into a separate function. After parsing the command line, we have a long loop to compute the commit object to start annotating from. Move the logic to a separate function, so that later patches become easier to read. It also makes fill_origin_blob() return void; the check is always done on !file->ptr, and nobody looks at the return value from the function. Signed-off-by: Junio C Hamano diff --git a/builtin-blame.c b/builtin-blame.c index bfd562d..996f535 100644 --- a/builtin-blame.c +++ b/builtin-blame.c @@ -91,7 +91,7 @@ struct origin { * Given an origin, prepare mmfile_t structure to be used by the * diff machinery */ -static char *fill_origin_blob(struct origin *o, mmfile_t *file) +static void fill_origin_blob(struct origin *o, mmfile_t *file) { if (!o->file.ptr) { enum object_type type; @@ -106,7 +106,6 @@ static char *fill_origin_blob(struct origin *o, mmfile_t *file) } else *file = o->file; - return file->ptr; } /* @@ -2006,6 +2005,10 @@ static int git_blame_config(const char *var, const char *value) return git_default_config(var, value); } +/* + * Prepare a dummy commit that represents the work tree (or staged) item. + * Note that annotating work tree item never works in the reverse. + */ static struct commit *fake_working_tree_commit(const char *path, const char *contents_from) { struct commit *commit; @@ -2122,6 +2125,33 @@ static struct commit *fake_working_tree_commit(const char *path, const char *con return commit; } +static const char *prepare_final(struct scoreboard *sb, struct rev_info *revs) +{ + int i; + const char *final_commit_name = NULL; + + /* + * There must be one and only one positive commit in the + * revs->pending array. + */ + for (i = 0; i < revs->pending.nr; i++) { + struct object *obj = revs->pending.objects[i].item; + if (obj->flags & UNINTERESTING) + continue; + while (obj->type == OBJ_TAG) + obj = deref_tag(obj, NULL, 0); + if (obj->type != OBJ_COMMIT) + die("Non commit %s?", revs->pending.objects[i].name); + if (sb->final) + die("More than one commit to dig from %s and %s?", + revs->pending.objects[i].name, + final_commit_name); + sb->final = (struct commit *) obj; + final_commit_name = revs->pending.objects[i].name; + } + return final_commit_name; +} + int cmd_blame(int argc, const char **argv, const char *prefix) { struct rev_info revs; @@ -2327,27 +2357,7 @@ int cmd_blame(int argc, const char **argv, const char *prefix) setup_revisions(unk, argv, &revs, NULL); memset(&sb, 0, sizeof(sb)); - /* - * There must be one and only one positive commit in the - * revs->pending array. - */ - for (i = 0; i < revs.pending.nr; i++) { - struct object *obj = revs.pending.objects[i].item; - if (obj->flags & UNINTERESTING) - continue; - while (obj->type == OBJ_TAG) - obj = deref_tag(obj, NULL, 0); - if (obj->type != OBJ_COMMIT) - die("Non commit %s?", - revs.pending.objects[i].name); - if (sb.final) - die("More than one commit to dig from %s and %s?", - revs.pending.objects[i].name, - final_commit_name); - sb.final = (struct commit *) obj; - final_commit_name = revs.pending.objects[i].name; - } - + final_commit_name = prepare_final(&sb, &revs); if (!sb.final) { /* * "--not A B -- path" without anything positive; -- cgit v0.10.2-6-g49f6 From 69264f46a193ae9dec5761984b4bae32f4810916 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 3 Apr 2008 00:56:23 -0700 Subject: builtin-blame.c: allow more than 16 parents This removes the hardcoded 16 parents limit from git-blame by allowing the parent array to be allocated dynamically. As the ultimate objective is not about allowing dodecapus, but about annotating the history upside down, it also renames "parent" in the code to "scapegoat"; the name of the game used to be "pass blame to your parents", but now it is "find a scapegoat to pass blame on". Signed-off-by: Junio C Hamano diff --git a/builtin-blame.c b/builtin-blame.c index 996f535..fbc441f 100644 --- a/builtin-blame.c +++ b/builtin-blame.c @@ -1191,18 +1191,45 @@ static void pass_whole_blame(struct scoreboard *sb, } } -#define MAXPARENT 16 +/* + * We pass blame from the current commit to its parents. We keep saying + * "parent" (and "porigin"), but what we mean is to find scapegoat to + * exonerate ourselves. + */ +static struct commit_list *first_scapegoat(struct commit *commit) +{ + return commit->parents; +} + +static int num_scapegoats(struct commit *commit) +{ + int cnt; + struct commit_list *l = first_scapegoat(commit); + for (cnt = 0; l; l = l->next) + cnt++; + return cnt; +} + +#define MAXSG 16 static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) { - int i, pass; + int i, pass, num_sg; struct commit *commit = origin->commit; - struct commit_list *parent; - struct origin *parent_origin[MAXPARENT], *porigin; - - memset(parent_origin, 0, sizeof(parent_origin)); + struct commit_list *sg; + struct origin *sg_buf[MAXSG]; + struct origin *porigin, **sg_origin = sg_buf; + + num_sg = num_scapegoats(commit); + if (!num_sg) + goto finish; + else if (num_sg < ARRAY_SIZE(sg_buf)) + memset(sg_buf, 0, sizeof(sg_buf)); + else + sg_origin = xcalloc(num_sg, sizeof(*sg_origin)); - /* The first pass looks for unrenamed path to optimize for + /* + * The first pass looks for unrenamed path to optimize for * common cases, then we look for renames in the second pass. */ for (pass = 0; pass < 2; pass++) { @@ -1210,13 +1237,13 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) struct commit *, struct origin *); find = pass ? find_rename : find_origin; - for (i = 0, parent = commit->parents; - i < MAXPARENT && parent; - parent = parent->next, i++) { - struct commit *p = parent->item; + for (i = 0, sg = first_scapegoat(commit); + i < num_sg && sg; + sg = sg->next, i++) { + struct commit *p = sg->item; int j, same; - if (parent_origin[i]) + if (sg_origin[i]) continue; if (parse_commit(p)) continue; @@ -1229,24 +1256,24 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) goto finish; } for (j = same = 0; j < i; j++) - if (parent_origin[j] && - !hashcmp(parent_origin[j]->blob_sha1, + if (sg_origin[j] && + !hashcmp(sg_origin[j]->blob_sha1, porigin->blob_sha1)) { same = 1; break; } if (!same) - parent_origin[i] = porigin; + sg_origin[i] = porigin; else origin_decref(porigin); } } num_commits++; - for (i = 0, parent = commit->parents; - i < MAXPARENT && parent; - parent = parent->next, i++) { - struct origin *porigin = parent_origin[i]; + for (i = 0, sg = first_scapegoat(commit); + i < num_sg && sg; + sg = sg->next, i++) { + struct origin *porigin = sg_origin[i]; if (!porigin) continue; if (pass_blame_to_parent(sb, origin, porigin)) @@ -1257,10 +1284,10 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) * Optionally find moves in parents' files. */ if (opt & PICKAXE_BLAME_MOVE) - for (i = 0, parent = commit->parents; - i < MAXPARENT && parent; - parent = parent->next, i++) { - struct origin *porigin = parent_origin[i]; + for (i = 0, sg = first_scapegoat(commit); + i < num_sg && sg; + sg = sg->next, i++) { + struct origin *porigin = sg_origin[i]; if (!porigin) continue; if (find_move_in_parent(sb, origin, porigin)) @@ -1271,23 +1298,25 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) * Optionally find copies from parents' files. */ if (opt & PICKAXE_BLAME_COPY) - for (i = 0, parent = commit->parents; - i < MAXPARENT && parent; - parent = parent->next, i++) { - struct origin *porigin = parent_origin[i]; - if (find_copy_in_parent(sb, origin, parent->item, + for (i = 0, sg = first_scapegoat(commit); + i < num_sg && sg; + sg = sg->next, i++) { + struct origin *porigin = sg_origin[i]; + if (find_copy_in_parent(sb, origin, sg->item, porigin, opt)) goto finish; } finish: - for (i = 0; i < MAXPARENT; i++) { - if (parent_origin[i]) { - drop_origin_blob(parent_origin[i]); - origin_decref(parent_origin[i]); + for (i = 0; i < num_sg; i++) { + if (sg_origin[i]) { + drop_origin_blob(sg_origin[i]); + origin_decref(sg_origin[i]); } } drop_origin_blob(origin); + if (sg_buf != sg_origin) + free(sg_origin); } /* -- cgit v0.10.2-6-g49f6 From 85af7929ee125385c2771fa4eaccfa2f29dc63c9 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Wed, 2 Apr 2008 22:17:53 -0700 Subject: git-blame --reverse This new option allows "git blame" to read an old version of the file, and up to which commit each line survived (i.e. their children rewrote the line out of the contents). The previous revision machinery update to decorate each commit with its children was leading to this change. When the --reverse option is given, we read the old version and pass blame to the children of the current suspect, instead of the usual order of starting from the latest and passing blame to parents. The standard yardstick of "blame" in git.git history is "rev-list.c" which was refactored heavily in its existence. For example: git blame -C -C -w --reverse 9de48752..master -- rev-list.c begins like this: 6c41b801 builtin-rev-list.c (JC Hamano 2008-04-02 1) #include "cache... 6c41b801 builtin-rev-list.c (JC Hamano 2008-04-02 2) #include "commi... 6c41b801 builtin-rev-list.c (JC Hamano 2008-04-02 3) #include "tree.... 6c41b801 builtin-rev-list.c (JC Hamano 2008-04-02 4) #include "blob.... 213523f4 rev-list.c (JC Hamano 2006-03-01 5) #include "epoch... 6c41b801 builtin-rev-list.c (JC Hamano 2008-04-02 6) ab57c8dd rev-list.c (JC Hamano 2006-02-24 7) #define SEEN ab57c8dd rev-list.c (JC Hamano 2006-02-24 8) #define INTERES... 213523f4 rev-list.c (JC Hamano 2006-03-01 9) #define COUNTED... 7e21c29b rev-list.c (LTorvalds 2005-07-06 10) #define SHOWN ... 6c41b801 builtin-rev-list.c (JC Hamano 2008-04-02 11) 6c41b801 builtin-rev-list.c (JC Hamano 2008-04-02 12) static const ch... b1349229 rev-list.c (LTorvalds 2005-07-26 13) "usage: git-... This reveals that the original first four lines survived until now in builtin-rev-list.c , inclusion of "epoch.h" was removed after 213523f4 while the contents was still in rev-list.c. This mode probably needs more tweaking so that the commit that removed the line (i.e. the children of the commits listed in the above sample output) is shown instead to be useful, but then there is a little matter of which child of a fork point to show. For now, you can find the diff that rewrote the fifth line above by doing: $ git log --children 213523f4^.. to find its child, which is 1025fe5 (Merge branch 'lt/rev-list' into next, 2006-03-01), and then look at that child with: $ git show 1025fe5 Signed-off-by: Junio C Hamano diff --git a/builtin-blame.c b/builtin-blame.c index fbc441f..5c7546d 100644 --- a/builtin-blame.c +++ b/builtin-blame.c @@ -43,6 +43,7 @@ static int max_orig_digits; static int max_digits; static int max_score_digits; static int show_root; +static int reverse; static int blank_boundary; static int incremental; static int cmd_is_annotate; @@ -177,7 +178,7 @@ struct blame_entry { struct scoreboard { /* the final commit (i.e. where we started digging from) */ struct commit *final; - + struct rev_info *revs; const char *path; /* @@ -1196,15 +1197,17 @@ static void pass_whole_blame(struct scoreboard *sb, * "parent" (and "porigin"), but what we mean is to find scapegoat to * exonerate ourselves. */ -static struct commit_list *first_scapegoat(struct commit *commit) +static struct commit_list *first_scapegoat(struct rev_info *revs, struct commit *commit) { - return commit->parents; + if (!reverse) + return commit->parents; + return lookup_decoration(&revs->children, &commit->object); } -static int num_scapegoats(struct commit *commit) +static int num_scapegoats(struct rev_info *revs, struct commit *commit) { int cnt; - struct commit_list *l = first_scapegoat(commit); + struct commit_list *l = first_scapegoat(revs, commit); for (cnt = 0; l; l = l->next) cnt++; return cnt; @@ -1214,13 +1217,14 @@ static int num_scapegoats(struct commit *commit) static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) { + struct rev_info *revs = sb->revs; int i, pass, num_sg; struct commit *commit = origin->commit; struct commit_list *sg; struct origin *sg_buf[MAXSG]; struct origin *porigin, **sg_origin = sg_buf; - num_sg = num_scapegoats(commit); + num_sg = num_scapegoats(revs, commit); if (!num_sg) goto finish; else if (num_sg < ARRAY_SIZE(sg_buf)) @@ -1237,7 +1241,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) struct commit *, struct origin *); find = pass ? find_rename : find_origin; - for (i = 0, sg = first_scapegoat(commit); + for (i = 0, sg = first_scapegoat(revs, commit); i < num_sg && sg; sg = sg->next, i++) { struct commit *p = sg->item; @@ -1270,7 +1274,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) } num_commits++; - for (i = 0, sg = first_scapegoat(commit); + for (i = 0, sg = first_scapegoat(revs, commit); i < num_sg && sg; sg = sg->next, i++) { struct origin *porigin = sg_origin[i]; @@ -1284,7 +1288,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) * Optionally find moves in parents' files. */ if (opt & PICKAXE_BLAME_MOVE) - for (i = 0, sg = first_scapegoat(commit); + for (i = 0, sg = first_scapegoat(revs, commit); i < num_sg && sg; sg = sg->next, i++) { struct origin *porigin = sg_origin[i]; @@ -1298,7 +1302,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt) * Optionally find copies from parents' files. */ if (opt & PICKAXE_BLAME_COPY) - for (i = 0, sg = first_scapegoat(commit); + for (i = 0, sg = first_scapegoat(revs, commit); i < num_sg && sg; sg = sg->next, i++) { struct origin *porigin = sg_origin[i]; @@ -1515,8 +1519,10 @@ static void found_guilty_entry(struct blame_entry *ent) * is still unknown, pick one blame_entry, and allow its current * suspect to pass blames to its parents. */ -static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt) +static void assign_blame(struct scoreboard *sb, int opt) { + struct rev_info *revs = sb->revs; + while (1) { struct blame_entry *ent; struct commit *commit; @@ -1537,8 +1543,9 @@ static void assign_blame(struct scoreboard *sb, struct rev_info *revs, int opt) commit = suspect->commit; if (!commit->object.parsed) parse_commit(commit); - if (!(commit->object.flags & UNINTERESTING) && - !(revs->max_age != -1 && commit->date < revs->max_age)) + if (reverse || + (!(commit->object.flags & UNINTERESTING) && + !(revs->max_age != -1 && commit->date < revs->max_age))) pass_blame(sb, suspect, opt); else { commit->object.flags |= UNINTERESTING; @@ -2154,10 +2161,11 @@ static struct commit *fake_working_tree_commit(const char *path, const char *con return commit; } -static const char *prepare_final(struct scoreboard *sb, struct rev_info *revs) +static const char *prepare_final(struct scoreboard *sb) { int i; const char *final_commit_name = NULL; + struct rev_info *revs = sb->revs; /* * There must be one and only one positive commit in the @@ -2181,6 +2189,36 @@ static const char *prepare_final(struct scoreboard *sb, struct rev_info *revs) return final_commit_name; } +static const char *prepare_initial(struct scoreboard *sb) +{ + int i; + const char *final_commit_name = NULL; + struct rev_info *revs = sb->revs; + + /* + * There must be one and only one negative commit, and it must be + * the boundary. + */ + for (i = 0; i < revs->pending.nr; i++) { + struct object *obj = revs->pending.objects[i].item; + if (!(obj->flags & UNINTERESTING)) + continue; + while (obj->type == OBJ_TAG) + obj = deref_tag(obj, NULL, 0); + if (obj->type != OBJ_COMMIT) + die("Non commit %s?", revs->pending.objects[i].name); + if (sb->final) + die("More than one commit to dig down to %s and %s?", + revs->pending.objects[i].name, + final_commit_name); + sb->final = (struct commit *) obj; + final_commit_name = revs->pending.objects[i].name; + } + if (!final_commit_name) + die("No commit to dig down to?"); + return final_commit_name; +} + int cmd_blame(int argc, const char **argv, const char *prefix) { struct rev_info revs; @@ -2213,6 +2251,10 @@ int cmd_blame(int argc, const char **argv, const char *prefix) blank_boundary = 1; else if (!strcmp("--root", arg)) show_root = 1; + else if (!strcmp("--reverse", arg)) { + argv[unk++] = "--children"; + reverse = 1; + } else if (!strcmp(arg, "--show-stats")) show_stats = 1; else if (!strcmp("-c", arg)) @@ -2386,7 +2428,14 @@ int cmd_blame(int argc, const char **argv, const char *prefix) setup_revisions(unk, argv, &revs, NULL); memset(&sb, 0, sizeof(sb)); - final_commit_name = prepare_final(&sb, &revs); + sb.revs = &revs; + if (!reverse) + final_commit_name = prepare_final(&sb); + else if (contents_from) + die("--contents and --children do not blend well."); + else + final_commit_name = prepare_initial(&sb); + if (!sb.final) { /* * "--not A B -- path" without anything positive; @@ -2464,7 +2513,7 @@ int cmd_blame(int argc, const char **argv, const char *prefix) if (!incremental) setup_pager(); - assign_blame(&sb, &revs, opt); + assign_blame(&sb, opt); if (incremental) return 0; -- cgit v0.10.2-6-g49f6