Merge branch 'jc/blame' (early part) into HEAD

* 'jc/blame' (early part):
  git-blame --reverse
  builtin-blame.c: allow more than 16 parents
  builtin-blame.c: move prepare_final() into a separate function.
  rev-list --children
  revision traversal: --children option

Conflicts:

	Documentation/rev-list-options.txt
	revision.c

1 files changed, 147 insertions, 59 deletions

diff --git a/builtin-blame.c b/builtin-blame.c
index b451f6c64d..cf41511c79 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;
@@ -91,7 +92,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 +107,6 @@ static char *fill_origin_blob(struct origin *o, mmfile_t *file)
 	}
 	else
 		*file = o->file;
-	return file->ptr;
 }
 
 /*
@@ -178,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;
 
 	/*
@@ -1192,18 +1192,48 @@ 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 rev_info *revs, struct commit *commit)
+{
+	if (!reverse)
+		return commit->parents;
+	return lookup_decoration(&revs->children, &commit->object);
+}
+
+static int num_scapegoats(struct rev_info *revs, struct commit *commit)
+{
+	int cnt;
+	struct commit_list *l = first_scapegoat(revs, 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;
+	struct rev_info *revs = sb->revs;
+	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(revs, 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++) {
@@ -1211,13 +1241,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(revs, 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;
@@ -1230,24 +1260,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(revs, 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))
@@ -1258,10 +1288,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(revs, 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))
@@ -1272,23 +1302,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(revs, 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);
 }
 
 /*
@@ -1487,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;
@@ -1509,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;
@@ -2006,6 +2041,10 @@ static int git_blame_config(const char *var, const char *value, void *cb)
 	return git_default_config(var, value, cb);
 }
 
+/*
+ * 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 +2161,64 @@ static struct commit *fake_working_tree_commit(const char *path, const char *con
 	return commit;
 }
 
+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
+	 * 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;
+}
+
+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;
@@ -2154,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))
@@ -2327,26 +2428,13 @@ 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;
-	}
+	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) {
 		/*
@@ -2425,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;