1 files changed, 206 insertions, 6 deletions

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 51858e323..09e3a60bf 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -36,7 +36,8 @@ static const char rev_list_usage[] =
 "    --abbrev=nr | --no-abbrev\n"
 "    --abbrev-commit\n"
 "  special purpose:\n"
-"    --bisect"
+"    --bisect\n"
+"    --bisect-vars"
 ;
 
 static struct rev_info revs;
@@ -168,7 +169,8 @@ static void clear_distance(struct commit_list *list)
 	}
 }
 
-static struct commit_list *find_bisection(struct commit_list *list)
+static struct commit_list *find_bisection(struct commit_list *list,
+					  int *reaches, int *all)
 {
 	int nr, closest;
 	struct commit_list *p, *best;
@@ -182,19 +184,21 @@ static struct commit_list *find_bisection(struct commit_list *list)
 	}
 	closest = -1;
 	best = list;
+	*all = nr;
 
 	for (p = list; p; p = p->next) {
-		int distance;
+		int distance, reach;
 
 		if (revs.prune_fn && !(p->item->object.flags & TREECHANGE))
 			continue;
 
-		distance = count_distance(p);
+		distance = reach = count_distance(p);
 		clear_distance(list);
 		if (nr - distance < distance)
 			distance = nr - distance;
 		if (distance > closest) {
 			best = p;
+			*reaches = reach;
 			closest = distance;
 		}
 	}
@@ -203,6 +207,160 @@ static struct commit_list *find_bisection(struct commit_list *list)
 	return best;
 }
 
+static inline int commit_interesting(struct commit_list *elem)
+{
+	unsigned flags = elem->item->object.flags;
+	if (flags & UNINTERESTING)
+		return 0;
+	return (!revs.prune_fn || (flags & TREECHANGE));
+}
+
+static inline int weight(struct commit_list *elem)
+{
+	return *((int*)(elem->item->util));
+}
+
+static inline void weight_set(struct commit_list *elem, int weight)
+{
+	*((int*)(elem->item->util)) = weight;
+}
+
+static int count_interesting_parents(struct commit_list *elem)
+{
+	int cnt = 0;
+	if (!elem->item->parents)
+		return cnt;
+	for (elem = elem->item->parents; elem; elem = elem->next) {
+		if (commit_interesting(elem))
+			cnt++;
+	}
+	return cnt;
+}
+
+static struct commit_list *find_bisection_2(struct commit_list *list,
+					    int *reaches, int *all)
+{
+	int n, nr, counted, distance;
+	struct commit_list *p, *best;
+	int *weights;
+
+	for (nr = 0, p = list; p; p = p->next) {
+		if (commit_interesting(p))
+			nr++;
+	}
+	*all = nr;
+	weights = xcalloc(nr, sizeof(int*));
+	counted = 0;
+
+	for (n = 0, p = list; p; p = p->next) {
+		if (!commit_interesting(p))
+			continue;
+		if (commit_interesting(p)) {
+			/*
+			 * positive weight is the number of interesting
+			 * commits it can reach, including itself.
+			 * weight = 0 means it has one parent and
+			 * its distance is unknown.
+			 * weight < 0 means it has more than one
+			 * parent and its distance is unknown.
+			 */
+			p->item->util = &weights[n++];
+			switch (count_interesting_parents(p)) {
+			case 0:
+				weight_set(p, 1);
+				counted++;
+				break;
+			case 1:
+				weight_set(p, 0);
+				break;
+			default:
+				weight_set(p, -1);
+				break;
+			}
+		}
+	}
+
+	/*
+	 * If you have only one parent in the resulting set
+	 * then you can reach one commit more than that parent
+	 * can reach.  So we do not have to run the expensive
+	 * count_distance() for single strand of pearls.
+	 *
+	 * However, if you have more than one parents, you cannot
+	 * just add their distance and one for yourself, since
+	 * they usually reach the same ancestor and you would
+	 * end up counting them twice that way.
+	 *
+	 * So we will first count distance of merges the usual
+	 * way, and then fill the blanks using cheaper algorithm.
+	 */
+	for (p = list; p; p = p->next) {
+		if (!commit_interesting(p))
+			continue;
+		n = weight(p);
+		if (0 <= n)
+			continue;
+		distance = count_distance(p);
+		clear_distance(p);
+		weight_set(p, distance);
+
+		/* Does it happen to be at exactly half-way? */
+		distance *= 2;
+		if (nr == distance || (nr+1) == distance) {
+			p->next = NULL;
+			*reaches = weight(p);
+			free(weights);
+			return p;
+		}
+		counted++;
+	}
+
+	while (counted < nr) {
+		for (p = list; p; p = p->next) {
+			struct commit_list *q;
+
+			if (!commit_interesting(p) || 0 < weight(p))
+				continue;
+			for (q = p->item->parents; q; q = q->next)
+				if (commit_interesting(q) && 0 < weight(q))
+					break;
+			if (!q)
+				continue;
+			weight_set(p, weight(q)+1);
+			counted++;
+
+			/* Does it happen to be at exactly half-way? */
+			distance = weight(p) * 2;
+			if (nr == distance || (nr+1) == distance) {
+				p->next = NULL;
+				*reaches = weight(p);
+				free(weights);
+				return p;
+			}
+		}
+	}
+
+	/* Then find the best one */
+	counted = 0;
+	best = list;
+	for (p = list; p; p = p->next) {
+		if (!commit_interesting(p))
+			continue;
+		distance = weight(p);
+		if (nr - distance < distance)
+			distance = nr - distance;
+		if (distance > counted) {
+			best = p;
+			counted = distance;
+			*reaches = weight(p);
+		}
+	}
+	if (best)
+		best->next = NULL;
+	free(weights);
+	return best;
+}
+
 static void read_revisions_from_stdin(struct rev_info *revs)
 {
 	char line[1000];
@@ -225,6 +383,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	struct commit_list *list;
 	int i;
 	int read_from_stdin = 0;
+	int bisect_show_vars = 0;
 
 	git_config(git_default_config);
 	init_revisions(&revs, prefix);
@@ -247,6 +406,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			bisect_list = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--bisect-vars")) {
+			bisect_list = 1;
+			bisect_show_vars = 1;
+			continue;
+		}
 		if (!strcmp(arg, "--stdin")) {
 			if (read_from_stdin++)
 				die("--stdin given twice?");
@@ -285,8 +449,44 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.tree_objects)
 		mark_edges_uninteresting(revs.commits, &revs, show_edge);
 
-	if (bisect_list)
-		revs.commits = find_bisection(revs.commits);
+	if (bisect_list) {
+		int reaches = reaches, all = all;
+
+		if (!revs.prune_fn)
+			revs.commits = find_bisection_2(revs.commits,
+							&reaches, &all);
+		else
+			revs.commits = find_bisection(revs.commits,
+						      &reaches, &all);
+		if (bisect_show_vars) {
+			int cnt;
+			if (!revs.commits)
+				return 1;
+			/*
+			 * revs.commits can reach "reaches" commits among
+			 * "all" commits.  If it is good, then there are
+			 * (all-reaches) commits left to be bisected.
+			 * On the other hand, if it is bad, then the set
+			 * to bisect is "reaches".
+			 * A bisect set of size N has (N-1) commits further
+			 * to test, as we already know one bad one.
+			 */
+			cnt = all-reaches;
+			if (cnt < reaches)
+				cnt = reaches;
+			printf("bisect_rev=%s\n"
+			       "bisect_nr=%d\n"
+			       "bisect_good=%d\n"
+			       "bisect_bad=%d\n"
+			       "bisect_all=%d\n",
+			       sha1_to_hex(revs.commits->item->object.sha1),
+			       cnt - 1,
+			       all - reaches - 1,
+			       reaches - 1,
+			       all);
+			return 0;
+		}
+	}
 
 	traverse_commit_list(&revs, show_commit, show_object);