20 files changed, 985 insertions, 665 deletions

diff --git a/Makefile b/Makefile
index bcf7cbb3fb..d8cd011146 100644
--- a/Makefile
+++ b/Makefile
@@ -432,6 +432,7 @@ LIB_OBJS += archive-tar.o
 LIB_OBJS += archive-zip.o
 LIB_OBJS += attr.o
 LIB_OBJS += base85.o
+LIB_OBJS += bisect.o
 LIB_OBJS += blob.o
 LIB_OBJS += branch.o
 LIB_OBJS += bundle.o
@@ -532,6 +533,7 @@ BUILTIN_OBJS += builtin-add.o
 BUILTIN_OBJS += builtin-annotate.o
 BUILTIN_OBJS += builtin-apply.o
 BUILTIN_OBJS += builtin-archive.o
+BUILTIN_OBJS += builtin-bisect--helper.o
 BUILTIN_OBJS += builtin-blame.o
 BUILTIN_OBJS += builtin-branch.o
 BUILTIN_OBJS += builtin-bundle.o
diff --git a/bisect.c b/bisect.c
new file mode 100644
index 0000000000..58f7e6f773
--- /dev/null
+++ b/bisect.c
@@ -0,0 +1,556 @@
+#include "cache.h"
+#include "commit.h"
+#include "diff.h"
+#include "revision.h"
+#include "refs.h"
+#include "list-objects.h"
+#include "quote.h"
+#include "sha1-lookup.h"
+#include "bisect.h"
+
+static unsigned char (*skipped_sha1)[20];
+static int skipped_sha1_nr;
+static int skipped_sha1_alloc;
+
+static const char **rev_argv;
+static int rev_argv_nr;
+static int rev_argv_alloc;
+
+/* bits #0-15 in revision.h */
+
+#define COUNTED		(1u<<16)
+
+/*
+ * This is a truly stupid algorithm, but it's only
+ * used for bisection, and we just don't care enough.
+ *
+ * We care just barely enough to avoid recursing for
+ * non-merge entries.
+ */
+static int count_distance(struct commit_list *entry)
+{
+	int nr = 0;
+
+	while (entry) {
+		struct commit *commit = entry->item;
+		struct commit_list *p;
+
+		if (commit->object.flags & (UNINTERESTING | COUNTED))
+			break;
+		if (!(commit->object.flags & TREESAME))
+			nr++;
+		commit->object.flags |= COUNTED;
+		p = commit->parents;
+		entry = p;
+		if (p) {
+			p = p->next;
+			while (p) {
+				nr += count_distance(p);
+				p = p->next;
+			}
+		}
+	}
+
+	return nr;
+}
+
+static void clear_distance(struct commit_list *list)
+{
+	while (list) {
+		struct commit *commit = list->item;
+		commit->object.flags &= ~COUNTED;
+		list = list->next;
+	}
+}
+
+#define DEBUG_BISECT 0
+
+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 *commit)
+{
+	struct commit_list *p;
+	int count;
+
+	for (count = 0, p = commit->parents; p; p = p->next) {
+		if (p->item->object.flags & UNINTERESTING)
+			continue;
+		count++;
+	}
+	return count;
+}
+
+static inline int halfway(struct commit_list *p, int nr)
+{
+	/*
+	 * Don't short-cut something we are not going to return!
+	 */
+	if (p->item->object.flags & TREESAME)
+		return 0;
+	if (DEBUG_BISECT)
+		return 0;
+	/*
+	 * 2 and 3 are halfway of 5.
+	 * 3 is halfway of 6 but 2 and 4 are not.
+	 */
+	switch (2 * weight(p) - nr) {
+	case -1: case 0: case 1:
+		return 1;
+	default:
+		return 0;
+	}
+}
+
+#if !DEBUG_BISECT
+#define show_list(a,b,c,d) do { ; } while (0)
+#else
+static void show_list(const char *debug, int counted, int nr,
+		      struct commit_list *list)
+{
+	struct commit_list *p;
+
+	fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
+
+	for (p = list; p; p = p->next) {
+		struct commit_list *pp;
+		struct commit *commit = p->item;
+		unsigned flags = commit->object.flags;
+		enum object_type type;
+		unsigned long size;
+		char *buf = read_sha1_file(commit->object.sha1, &type, &size);
+		char *ep, *sp;
+
+		fprintf(stderr, "%c%c%c ",
+			(flags & TREESAME) ? ' ' : 'T',
+			(flags & UNINTERESTING) ? 'U' : ' ',
+			(flags & COUNTED) ? 'C' : ' ');
+		if (commit->util)
+			fprintf(stderr, "%3d", weight(p));
+		else
+			fprintf(stderr, "---");
+		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
+		for (pp = commit->parents; pp; pp = pp->next)
+			fprintf(stderr, " %.*s", 8,
+				sha1_to_hex(pp->item->object.sha1));
+
+		sp = strstr(buf, "\n\n");
+		if (sp) {
+			sp += 2;
+			for (ep = sp; *ep && *ep != '\n'; ep++)
+				;
+			fprintf(stderr, " %.*s", (int)(ep - sp), sp);
+		}
+		fprintf(stderr, "\n");
+	}
+}
+#endif /* DEBUG_BISECT */
+
+static struct commit_list *best_bisection(struct commit_list *list, int nr)
+{
+	struct commit_list *p, *best;
+	int best_distance = -1;
+
+	best = list;
+	for (p = list; p; p = p->next) {
+		int distance;
+		unsigned flags = p->item->object.flags;
+
+		if (flags & TREESAME)
+			continue;
+		distance = weight(p);
+		if (nr - distance < distance)
+			distance = nr - distance;
+		if (distance > best_distance) {
+			best = p;
+			best_distance = distance;
+		}
+	}
+
+	return best;
+}
+
+struct commit_dist {
+	struct commit *commit;
+	int distance;
+};
+
+static int compare_commit_dist(const void *a_, const void *b_)
+{
+	struct commit_dist *a, *b;
+
+	a = (struct commit_dist *)a_;
+	b = (struct commit_dist *)b_;
+	if (a->distance != b->distance)
+		return b->distance - a->distance; /* desc sort */
+	return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
+}
+
+static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
+{
+	struct commit_list *p;
+	struct commit_dist *array = xcalloc(nr, sizeof(*array));
+	int cnt, i;
+
+	for (p = list, cnt = 0; p; p = p->next) {
+		int distance;
+		unsigned flags = p->item->object.flags;
+
+		if (flags & TREESAME)
+			continue;
+		distance = weight(p);
+		if (nr - distance < distance)
+			distance = nr - distance;
+		array[cnt].commit = p->item;
+		array[cnt].distance = distance;
+		cnt++;
+	}
+	qsort(array, cnt, sizeof(*array), compare_commit_dist);
+	for (p = list, i = 0; i < cnt; i++) {
+		struct name_decoration *r = xmalloc(sizeof(*r) + 100);
+		struct object *obj = &(array[i].commit->object);
+
+		sprintf(r->name, "dist=%d", array[i].distance);
+		r->next = add_decoration(&name_decoration, obj, r);
+		p->item = array[i].commit;
+		p = p->next;
+	}
+	if (p)
+		p->next = NULL;
+	free(array);
+	return list;
+}
+
+/*
+ * zero or positive weight is the number of interesting commits it can
+ * reach, including itself.  Especially, weight = 0 means it does not
+ * reach any tree-changing commits (e.g. just above uninteresting one
+ * but traversal is with pathspec).
+ *
+ * weight = -1 means it has one parent and its distance is yet to
+ * be computed.
+ *
+ * weight = -2 means it has more than one parent and its distance is
+ * unknown.  After running count_distance() first, they will get zero
+ * or positive distance.
+ */
+static struct commit_list *do_find_bisection(struct commit_list *list,
+					     int nr, int *weights,
+					     int find_all)
+{
+	int n, counted;
+	struct commit_list *p;
+
+	counted = 0;
+
+	for (n = 0, p = list; p; p = p->next) {
+		struct commit *commit = p->item;
+		unsigned flags = commit->object.flags;
+
+		p->item->util = &weights[n++];
+		switch (count_interesting_parents(commit)) {
+		case 0:
+			if (!(flags & TREESAME)) {
+				weight_set(p, 1);
+				counted++;
+				show_list("bisection 2 count one",
+					  counted, nr, list);
+			}
+			/*
+			 * otherwise, it is known not to reach any
+			 * tree-changing commit and gets weight 0.
+			 */
+			break;
+		case 1:
+			weight_set(p, -1);
+			break;
+		default:
+			weight_set(p, -2);
+			break;
+		}
+	}
+
+	show_list("bisection 2 initialize", counted, nr, list);
+
+	/*
+	 * 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 (p->item->object.flags & UNINTERESTING)
+			continue;
+		if (weight(p) != -2)
+			continue;
+		weight_set(p, count_distance(p));
+		clear_distance(list);
+
+		/* Does it happen to be at exactly half-way? */
+		if (!find_all && halfway(p, nr))
+			return p;
+		counted++;
+	}
+
+	show_list("bisection 2 count_distance", counted, nr, list);
+
+	while (counted < nr) {
+		for (p = list; p; p = p->next) {
+			struct commit_list *q;
+			unsigned flags = p->item->object.flags;
+
+			if (0 <= weight(p))
+				continue;
+			for (q = p->item->parents; q; q = q->next) {
+				if (q->item->object.flags & UNINTERESTING)
+					continue;
+				if (0 <= weight(q))
+					break;
+			}
+			if (!q)
+				continue;
+
+			/*
+			 * weight for p is unknown but q is known.
+			 * add one for p itself if p is to be counted,
+			 * otherwise inherit it from q directly.
+			 */
+			if (!(flags & TREESAME)) {
+				weight_set(p, weight(q)+1);
+				counted++;
+				show_list("bisection 2 count one",
+					  counted, nr, list);
+			}
+			else
+				weight_set(p, weight(q));
+
+			/* Does it happen to be at exactly half-way? */
+			if (!find_all && halfway(p, nr))
+				return p;
+		}
+	}
+
+	show_list("bisection 2 counted all", counted, nr, list);
+
+	if (!find_all)
+		return best_bisection(list, nr);
+	else
+		return best_bisection_sorted(list, nr);
+}
+
+struct commit_list *find_bisection(struct commit_list *list,
+					  int *reaches, int *all,
+					  int find_all)
+{
+	int nr, on_list;
+	struct commit_list *p, *best, *next, *last;
+	int *weights;
+
+	show_list("bisection 2 entry", 0, 0, list);
+
+	/*
+	 * Count the number of total and tree-changing items on the
+	 * list, while reversing the list.
+	 */
+	for (nr = on_list = 0, last = NULL, p = list;
+	     p;
+	     p = next) {
+		unsigned flags = p->item->object.flags;
+
+		next = p->next;
+		if (flags & UNINTERESTING)
+			continue;
+		p->next = last;
+		last = p;
+		if (!(flags & TREESAME))
+			nr++;
+		on_list++;
+	}
+	list = last;
+	show_list("bisection 2 sorted", 0, nr, list);
+
+	*all = nr;
+	weights = xcalloc(on_list, sizeof(*weights));
+
+	/* Do the real work of finding bisection commit. */
+	best = do_find_bisection(list, nr, weights, find_all);
+	if (best) {
+		if (!find_all)
+			best->next = NULL;
+		*reaches = weight(best);
+	}
+	free(weights);
+	return best;
+}
+
+static int register_ref(const char *refname, const unsigned char *sha1,
+			int flags, void *cb_data)
+{
+	if (!strcmp(refname, "bad")) {
+		ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
+		rev_argv[rev_argv_nr++] = xstrdup(sha1_to_hex(sha1));
+	} else if (!prefixcmp(refname, "good-")) {
+		const char *hex = sha1_to_hex(sha1);
+		char *good = xmalloc(strlen(hex) + 2);
+		*good = '^';
+		memcpy(good + 1, hex, strlen(hex) + 1);
+		ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
+		rev_argv[rev_argv_nr++] = good;
+	} else if (!prefixcmp(refname, "skip-")) {
+		ALLOC_GROW(skipped_sha1, skipped_sha1_nr + 1,
+			   skipped_sha1_alloc);
+		hashcpy(skipped_sha1[skipped_sha1_nr++], sha1);
+	}
+
+	return 0;
+}
+
+static int read_bisect_refs(void)
+{
+	return for_each_ref_in("refs/bisect/", register_ref, NULL);
+}
+
+void read_bisect_paths(void)
+{
+	struct strbuf str = STRBUF_INIT;
+	const char *filename = git_path("BISECT_NAMES");
+	FILE *fp = fopen(filename, "r");
+
+	if (!fp)
+		die("Could not open file '%s': %s", filename, strerror(errno));
+
+	while (strbuf_getline(&str, fp, '\n') != EOF) {
+		char *quoted;
+		int res;
+
+		strbuf_trim(&str);
+		quoted = strbuf_detach(&str, NULL);
+		res = sq_dequote_to_argv(quoted, &rev_argv,
+					 &rev_argv_nr, &rev_argv_alloc);
+		if (res)
+			die("Badly quoted content in file '%s': %s",
+			    filename, quoted);
+	}
+
+	strbuf_release(&str);
+	fclose(fp);
+}
+
+static int skipcmp(const void *a, const void *b)
+{
+	return hashcmp(a, b);
+}
+
+static void prepare_skipped(void)
+{
+	qsort(skipped_sha1, skipped_sha1_nr, sizeof(*skipped_sha1), skipcmp);
+}
+
+static const unsigned char *skipped_sha1_access(size_t index, void *table)
+{
+	unsigned char (*skipped)[20] = table;
+	return skipped[index];
+}
+
+static int lookup_skipped(unsigned char *sha1)
+{
+	return sha1_pos(sha1, skipped_sha1, skipped_sha1_nr,
+			skipped_sha1_access);
+}
+
+struct commit_list *filter_skipped(struct commit_list *list,
+				   struct commit_list **tried,
+				   int show_all)
+{
+	struct commit_list *filtered = NULL, **f = &filtered;
+
+	*tried = NULL;
+
+	if (!skipped_sha1_nr)
+		return list;
+
+	prepare_skipped();
+
+	while (list) {
+		struct commit_list *next = list->next;
+		list->next = NULL;
+		if (0 <= lookup_skipped(list->item->object.sha1)) {
+			/* Move current to tried list */
+			*tried = list;
+			tried = &list->next;
+		} else {
+			if (!show_all)
+				return list;
+			/* Move current to filtered list */
+			*f = list;
+			f = &list->next;
+		}
+		list = next;
+	}
+
+	return filtered;
+}
+
+static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
+{
+	init_revisions(revs, prefix);
+	revs->abbrev = 0;
+	revs->commit_format = CMIT_FMT_UNSPECIFIED;
+
+	/* argv[0] will be ignored by setup_revisions */
+	ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
+	rev_argv[rev_argv_nr++] = xstrdup("bisect_rev_setup");
+
+	if (read_bisect_refs())
+		die("reading bisect refs failed");
+
+	ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
+	rev_argv[rev_argv_nr++] = xstrdup("--");
+
+	read_bisect_paths();
+
+	ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
+	rev_argv[rev_argv_nr++] = NULL;
+
+	setup_revisions(rev_argv_nr, rev_argv, revs, NULL);
+
+	revs->limited = 1;
+}
+
+int bisect_next_vars(const char *prefix)
+{
+	struct rev_info revs;
+	struct rev_list_info info;
+	int reaches = 0, all = 0;
+
+	memset(&info, 0, sizeof(info));
+	info.revs = &revs;
+	info.bisect_show_flags = BISECT_SHOW_TRIED | BISECT_SHOW_STRINGED;
+
+	bisect_rev_setup(&revs, prefix);
+
+	if (prepare_revision_walk(&revs))
+		die("revision walk setup failed");
+	if (revs.tree_objects)
+		mark_edges_uninteresting(revs.commits, &revs, NULL);
+
+	revs.commits = find_bisection(revs.commits, &reaches, &all,
+				      !!skipped_sha1_nr);
+
+	return show_bisect_vars(&info, reaches, all);
+}
diff --git a/bisect.h b/bisect.h
new file mode 100644
index 0000000000..fdba913877
--- /dev/null
+++ b/bisect.h
@@ -0,0 +1,29 @@
+#ifndef BISECT_H
+#define BISECT_H
+
+extern struct commit_list *find_bisection(struct commit_list *list,
+					  int *reaches, int *all,
+					  int find_all);
+
+extern struct commit_list *filter_skipped(struct commit_list *list,
+					  struct commit_list **tried,
+					  int show_all);
+
+/* bisect_show_flags flags in struct rev_list_info */
+#define BISECT_SHOW_ALL		(1<<0)
+#define BISECT_SHOW_TRIED	(1<<1)
+#define BISECT_SHOW_STRINGED	(1<<2)
+
+struct rev_list_info {
+	struct rev_info *revs;
+	int bisect_show_flags;
+	int show_timestamp;
+	int hdr_termination;
+	const char *header_prefix;
+};
+
+extern int show_bisect_vars(struct rev_list_info *info, int reaches, int all);
+
+extern int bisect_next_vars(const char *prefix);
+
+#endif
diff --git a/builtin-bisect--helper.c b/builtin-bisect--helper.c
new file mode 100644
index 0000000000..8fe778766a
--- /dev/null
+++ b/builtin-bisect--helper.c
@@ -0,0 +1,27 @@
+#include "builtin.h"
+#include "cache.h"
+#include "parse-options.h"
+#include "bisect.h"
+
+static const char * const git_bisect_helper_usage[] = {
+	"git bisect--helper --next-vars",
+	NULL
+};
+
+int cmd_bisect__helper(int argc, const char **argv, const char *prefix)
+{
+	int next_vars = 0;
+	struct option options[] = {
+		OPT_BOOLEAN(0, "next-vars", &next_vars,
+			    "output next bisect step variables"),
+		OPT_END()
+	};
+
+	argc = parse_options(argc, argv, options, git_bisect_helper_usage, 0);
+
+	if (!next_vars)
+		usage_with_options(git_bisect_helper_usage, options);
+
+	/* next-vars */
+	return bisect_next_vars(prefix);
+}
diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index e58d300e3f..d3360ac1f8 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -1901,13 +1901,13 @@ static void read_object_list_from_stdin(void)
 
 #define OBJECT_ADDED (1u<<20)
 
-static void show_commit(struct commit *commit)
+static void show_commit(struct commit *commit, void *data)
 {
 	add_object_entry(commit->object.sha1, OBJ_COMMIT, NULL, 0);
 	commit->object.flags |= OBJECT_ADDED;
 }
 
-static void show_object(struct object_array_entry *p)
+static void show_object(struct object_array_entry *p, void *data)
 {
 	add_preferred_base_object(p->name);
 	add_object_entry(p->item->sha1, p->item->type, p->name, 0);
@@ -2073,7 +2073,7 @@ static void get_object_list(int ac, const char **av)
 	if (prepare_revision_walk(&revs))
 		die("revision walk setup failed");
 	mark_edges_uninteresting(revs.commits, &revs, show_edge);
-	traverse_commit_list(&revs, show_commit, show_object);
+	traverse_commit_list(&revs, show_commit, show_object, NULL);
 
 	if (keep_unreachable)
 		add_objects_in_unpacked_packs(&revs);
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 40d5fcb6b0..193993cf44 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -1,20 +1,12 @@
 #include "cache.h"
-#include "refs.h"
-#include "tag.h"
 #include "commit.h"
-#include "tree.h"
-#include "blob.h"
-#include "tree-walk.h"
 #include "diff.h"
 #include "revision.h"
 #include "list-objects.h"
 #include "builtin.h"
 #include "log-tree.h"
 #include "graph.h"
-
-/* bits #0-15 in revision.h */
-
-#define COUNTED		(1u<<16)
+#include "bisect.h"
 
 static const char rev_list_usage[] =
 "git rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
@@ -50,73 +42,69 @@ static const char rev_list_usage[] =
 "    --bisect-all"
 ;
 
-static struct rev_info revs;
-
-static int bisect_list;
-static int show_timestamp;
-static int hdr_termination;
-static const char *header_prefix;
-
-static void finish_commit(struct commit *commit);
-static void show_commit(struct commit *commit)
+static void finish_commit(struct commit *commit, void *data);
+static void show_commit(struct commit *commit, void *data)
 {
-	graph_show_commit(revs.graph);
+	struct rev_list_info *info = data;
+	struct rev_info *revs = info->revs;
+
+	graph_show_commit(revs->graph);
 
-	if (show_timestamp)
+	if (info->show_timestamp)
 		printf("%lu ", commit->date);
-	if (header_prefix)
-		fputs(header_prefix, stdout);
+	if (info->header_prefix)
+		fputs(info->header_prefix, stdout);
 
-	if (!revs.graph) {
+	if (!revs->graph) {
 		if (commit->object.flags & BOUNDARY)
 			putchar('-');
 		else if (commit->object.flags & UNINTERESTING)
 			putchar('^');
-		else if (revs.left_right) {
+		else if (revs->left_right) {
 			if (commit->object.flags & SYMMETRIC_LEFT)
 				putchar('<');
 			else
 				putchar('>');
 		}
 	}
-	if (revs.abbrev_commit && revs.abbrev)
-		fputs(find_unique_abbrev(commit->object.sha1, revs.abbrev),
+	if (revs->abbrev_commit && revs->abbrev)
+		fputs(find_unique_abbrev(commit->object.sha1, revs->abbrev),
 		      stdout);
 	else
 		fputs(sha1_to_hex(commit->object.sha1), stdout);
-	if (revs.print_parents) {
+	if (revs->print_parents) {
 		struct commit_list *parents = commit->parents;
 		while (parents) {
 			printf(" %s", sha1_to_hex(parents->item->object.sha1));
 			parents = parents->next;
 		}
 	}
-	if (revs.children.name) {
+	if (revs->children.name) {
 		struct commit_list *children;
 
-		children = lookup_decoration(&revs.children, &commit->object);
+		children = lookup_decoration(&revs->children, &commit->object);
 		while (children) {
 			printf(" %s", sha1_to_hex(children->item->object.sha1));
 			children = children->next;
 		}
 	}
-	show_decorations(&revs, commit);
-	if (revs.commit_format == CMIT_FMT_ONELINE)
+	show_decorations(revs, commit);
+	if (revs->commit_format == CMIT_FMT_ONELINE)
 		putchar(' ');
 	else
 		putchar('\n');
 
-	if (revs.verbose_header && commit->buffer) {
+	if (revs->verbose_header && commit->buffer) {
 		struct strbuf buf = STRBUF_INIT;
-		pretty_print_commit(revs.commit_format, commit,
-				    &buf, revs.abbrev, NULL, NULL,
-				    revs.date_mode, 0);
-		if (revs.graph) {
+		pretty_print_commit(revs->commit_format, commit,
+				    &buf, revs->abbrev, NULL, NULL,
+				    revs->date_mode, 0);
+		if (revs->graph) {
 			if (buf.len) {
-				if (revs.commit_format != CMIT_FMT_ONELINE)
-					graph_show_oneline(revs.graph);
+				if (revs->commit_format != CMIT_FMT_ONELINE)
+					graph_show_oneline(revs->graph);
 
-				graph_show_commit_msg(revs.graph, &buf);
+				graph_show_commit_msg(revs->graph, &buf);
 
 				/*
 				 * Add a newline after the commit message.
@@ -134,7 +122,7 @@ static void show_commit(struct commit *commit)
 				 * format doesn't explicitly end in a newline.)
 				 */
 				if (buf.len && buf.buf[buf.len - 1] == '\n')
-					graph_show_padding(revs.graph);
+					graph_show_padding(revs->graph);
 				putchar('\n');
 			} else {
 				/*
@@ -142,23 +130,23 @@ static void show_commit(struct commit *commit)
 				 * the rest of the graph output for this
 				 * commit.
 				 */
-				if (graph_show_remainder(revs.graph))
+				if (graph_show_remainder(revs->graph))
 					putchar('\n');
 			}
 		} else {
 			if (buf.len)
-				printf("%s%c", buf.buf, hdr_termination);
+				printf("%s%c", buf.buf, info->hdr_termination);
 		}
 		strbuf_release(&buf);
 	} else {
-		if (graph_show_remainder(revs.graph))
+		if (graph_show_remainder(revs->graph))
 			putchar('\n');
 	}
 	maybe_flush_or_die(stdout, "stdout");
-	finish_commit(commit);
+	finish_commit(commit, data);
 }
 
-static void finish_commit(struct commit *commit)
+static void finish_commit(struct commit *commit, void *data)
 {
 	if (commit->parents) {
 		free_commit_list(commit->parents);
@@ -168,20 +156,20 @@ static void finish_commit(struct commit *commit)
 	commit->buffer = NULL;
 }
 
-static void finish_object(struct object_array_entry *p)
+static void finish_object(struct object_array_entry *p, void *data)
 {
 	if (p->item->type == OBJ_BLOB && !has_sha1_file(p->item->sha1))
 		die("missing blob object '%s'", sha1_to_hex(p->item->sha1));
 }
 
-static void show_object(struct object_array_entry *p)
+static void show_object(struct object_array_entry *p, void *data)
 {
 	/* An object with name "foo\n0000000..." can be used to
 	 * confuse downstream "git pack-objects" very badly.
 	 */
 	const char *ep = strchr(p->name, '\n');
 
-	finish_object(p);
+	finish_object(p, data);
 	if (ep) {
 		printf("%s %.*s\n", sha1_to_hex(p->item->sha1),
 		       (int) (ep - p->name),
@@ -196,384 +184,6 @@ static void show_edge(struct commit *commit)
 	printf("-%s\n", sha1_to_hex(commit->object.sha1));
 }
 
-/*
- * This is a truly stupid algorithm, but it's only
- * used for bisection, and we just don't care enough.
- *
- * We care just barely enough to avoid recursing for
- * non-merge entries.
- */
-static int count_distance(struct commit_list *entry)
-{
-	int nr = 0;
-
-	while (entry) {
-		struct commit *commit = entry->item;
-		struct commit_list *p;
-
-		if (commit->object.flags & (UNINTERESTING | COUNTED))
-			break;
-		if (!(commit->object.flags & TREESAME))
-			nr++;
-		commit->object.flags |= COUNTED;
-		p = commit->parents;
-		entry = p;
-		if (p) {
-			p = p->next;
-			while (p) {
-				nr += count_distance(p);
-				p = p->next;
-			}
-		}
-	}
-
-	return nr;
-}
-
-static void clear_distance(struct commit_list *list)
-{
-	while (list) {
-		struct commit *commit = list->item;
-		commit->object.flags &= ~COUNTED;
-		list = list->next;
-	}
-}
-
-#define DEBUG_BISECT 0
-
-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 *commit)
-{
-	struct commit_list *p;
-	int count;
-
-	for (count = 0, p = commit->parents; p; p = p->next) {
-		if (p->item->object.flags & UNINTERESTING)
-			continue;
-		count++;
-	}
-	return count;
-}
-
-static inline int halfway(struct commit_list *p, int nr)
-{
-	/*
-	 * Don't short-cut something we are not going to return!
-	 */
-	if (p->item->object.flags & TREESAME)
-		return 0;
-	if (DEBUG_BISECT)
-		return 0;
-	/*
-	 * 2 and 3 are halfway of 5.
-	 * 3 is halfway of 6 but 2 and 4 are not.
-	 */
-	switch (2 * weight(p) - nr) {
-	case -1: case 0: case 1:
-		return 1;
-	default:
-		return 0;
-	}
-}
-
-#if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
-#else
-static void show_list(const char *debug, int counted, int nr,
-		      struct commit_list *list)
-{
-	struct commit_list *p;
-
-	fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
-
-	for (p = list; p; p = p->next) {
-		struct commit_list *pp;
-		struct commit *commit = p->item;
-		unsigned flags = commit->object.flags;
-		enum object_type type;
-		unsigned long size;
-		char *buf = read_sha1_file(commit->object.sha1, &type, &size);
-		char *ep, *sp;
-
-		fprintf(stderr, "%c%c%c ",
-			(flags & TREESAME) ? ' ' : 'T',
-			(flags & UNINTERESTING) ? 'U' : ' ',
-			(flags & COUNTED) ? 'C' : ' ');
-		if (commit->util)
-			fprintf(stderr, "%3d", weight(p));
-		else
-			fprintf(stderr, "---");
-		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
-		for (pp = commit->parents; pp; pp = pp->next)
-			fprintf(stderr, " %.*s", 8,
-				sha1_to_hex(pp->item->object.sha1));
-
-		sp = strstr(buf, "\n\n");
-		if (sp) {
-			sp += 2;
-			for (ep = sp; *ep && *ep != '\n'; ep++)
-				;
-			fprintf(stderr, " %.*s", (int)(ep - sp), sp);
-		}
-		fprintf(stderr, "\n");
-	}
-}
-#endif /* DEBUG_BISECT */
-
-static struct commit_list *best_bisection(struct commit_list *list, int nr)
-{
-	struct commit_list *p, *best;
-	int best_distance = -1;
-
-	best = list;
-	for (p = list; p; p = p->next) {
-		int distance;
-		unsigned flags = p->item->object.flags;
-
-		if (flags & TREESAME)
-			continue;
-		distance = weight(p);
-		if (nr - distance < distance)
-			distance = nr - distance;
-		if (distance > best_distance) {
-			best = p;
-			best_distance = distance;
-		}
-	}
-
-	return best;
-}
-
-struct commit_dist {
-	struct commit *commit;
-	int distance;
-};
-
-static int compare_commit_dist(const void *a_, const void *b_)
-{
-	struct commit_dist *a, *b;
-
-	a = (struct commit_dist *)a_;
-	b = (struct commit_dist *)b_;
-	if (a->distance != b->distance)
-		return b->distance - a->distance; /* desc sort */
-	return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
-}
-
-static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
-{
-	struct commit_list *p;
-	struct commit_dist *array = xcalloc(nr, sizeof(*array));
-	int cnt, i;
-
-	for (p = list, cnt = 0; p; p = p->next) {
-		int distance;
-		unsigned flags = p->item->object.flags;
-
-		if (flags & TREESAME)
-			continue;
-		distance = weight(p);
-		if (nr - distance < distance)
-			distance = nr - distance;
-		array[cnt].commit = p->item;
-		array[cnt].distance = distance;
-		cnt++;
-	}
-	qsort(array, cnt, sizeof(*array), compare_commit_dist);
-	for (p = list, i = 0; i < cnt; i++) {
-		struct name_decoration *r = xmalloc(sizeof(*r) + 100);
-		struct object *obj = &(array[i].commit->object);
-
-		sprintf(r->name, "dist=%d", array[i].distance);
-		r->next = add_decoration(&name_decoration, obj, r);
-		p->item = array[i].commit;
-		p = p->next;
-	}
-	if (p)
-		p->next = NULL;
-	free(array);
-	return list;
-}
-
-/*
- * zero or positive weight is the number of interesting commits it can
- * reach, including itself.  Especially, weight = 0 means it does not
- * reach any tree-changing commits (e.g. just above uninteresting one
- * but traversal is with pathspec).
- *
- * weight = -1 means it has one parent and its distance is yet to
- * be computed.
- *
- * weight = -2 means it has more than one parent and its distance is
- * unknown.  After running count_distance() first, they will get zero
- * or positive distance.
- */
-static struct commit_list *do_find_bisection(struct commit_list *list,
-					     int nr, int *weights,
-					     int find_all)
-{
-	int n, counted;
-	struct commit_list *p;
-
-	counted = 0;
-
-	for (n = 0, p = list; p; p = p->next) {
-		struct commit *commit = p->item;
-		unsigned flags = commit->object.flags;
-
-		p->item->util = &weights[n++];
-		switch (count_interesting_parents(commit)) {
-		case 0:
-			if (!(flags & TREESAME)) {
-				weight_set(p, 1);
-				counted++;
-				show_list("bisection 2 count one",
-					  counted, nr, list);
-			}
-			/*
-			 * otherwise, it is known not to reach any
-			 * tree-changing commit and gets weight 0.
-			 */
-			break;
-		case 1:
-			weight_set(p, -1);
-			break;
-		default:
-			weight_set(p, -2);
-			break;
-		}
-	}
-
-	show_list("bisection 2 initialize", counted, nr, list);
-
-	/*
-	 * 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 (p->item->object.flags & UNINTERESTING)
-			continue;
-		if (weight(p) != -2)
-			continue;
-		weight_set(p, count_distance(p));
-		clear_distance(list);
-
-		/* Does it happen to be at exactly half-way? */
-		if (!find_all && halfway(p, nr))
-			return p;
-		counted++;
-	}
-
-	show_list("bisection 2 count_distance", counted, nr, list);
-
-	while (counted < nr) {
-		for (p = list; p; p = p->next) {
-			struct commit_list *q;
-			unsigned flags = p->item->object.flags;
-
-			if (0 <= weight(p))
-				continue;
-			for (q = p->item->parents; q; q = q->next) {
-				if (q->item->object.flags & UNINTERESTING)
-					continue;
-				if (0 <= weight(q))
-					break;
-			}
-			if (!q)
-				continue;
-
-			/*
-			 * weight for p is unknown but q is known.
-			 * add one for p itself if p is to be counted,
-			 * otherwise inherit it from q directly.
-			 */
-			if (!(flags & TREESAME)) {
-				weight_set(p, weight(q)+1);
-				counted++;
-				show_list("bisection 2 count one",
-					  counted, nr, list);
-			}
-			else
-				weight_set(p, weight(q));
-
-			/* Does it happen to be at exactly half-way? */
-			if (!find_all && halfway(p, nr))
-				return p;
-		}
-	}
-
-	show_list("bisection 2 counted all", counted, nr, list);
-
-	if (!find_all)
-		return best_bisection(list, nr);
-	else
-		return best_bisection_sorted(list, nr);
-}
-
-static struct commit_list *find_bisection(struct commit_list *list,
-					  int *reaches, int *all,
-					  int find_all)
-{
-	int nr, on_list;
-	struct commit_list *p, *best, *next, *last;
-	int *weights;
-
-	show_list("bisection 2 entry", 0, 0, list);
-
-	/*
-	 * Count the number of total and tree-changing items on the
-	 * list, while reversing the list.
-	 */
-	for (nr = on_list = 0, last = NULL, p = list;
-	     p;
-	     p = next) {
-		unsigned flags = p->item->object.flags;
-
-		next = p->next;
-		if (flags & UNINTERESTING)
-			continue;
-		p->next = last;
-		last = p;
-		if (!(flags & TREESAME))
-			nr++;
-		on_list++;
-	}
-	list = last;
-	show_list("bisection 2 sorted", 0, nr, list);
-
-	*all = nr;
-	weights = xcalloc(on_list, sizeof(*weights));
-
-	/* Do the real work of finding bisection commit. */
-	best = do_find_bisection(list, nr, weights, find_all);
-	if (best) {
-		if (!find_all)
-			best->next = NULL;
-		*reaches = weight(best);
-	}
-	free(weights);
-	return best;
-}
-
 static inline int log2i(int n)
 {
 	int log2 = 0;
@@ -613,11 +223,83 @@ static int estimate_bisect_steps(int all)
 	return (e < 3 * x) ? n : n - 1;
 }
 
+static void show_tried_revs(struct commit_list *tried, int stringed)
+{
+	printf("bisect_tried='");
+	for (;tried; tried = tried->next) {
+		char *format = tried->next ? "%s|" : "%s";
+		printf(format, sha1_to_hex(tried->item->object.sha1));
+	}
+	printf(stringed ? "' &&\n" : "'\n");
+}
+
+int show_bisect_vars(struct rev_list_info *info, int reaches, int all)
+{
+	int cnt, flags = info->bisect_show_flags;
+	char hex[41] = "", *format;
+	struct commit_list *tried;
+	struct rev_info *revs = info->revs;
+
+	if (!revs->commits && !(flags & BISECT_SHOW_TRIED))
+		return 1;
+
+	revs->commits = filter_skipped(revs->commits, &tried, flags & BISECT_SHOW_ALL);
+
+	/*
+	 * 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;
+
+	if (revs->commits)
+		strcpy(hex, sha1_to_hex(revs->commits->item->object.sha1));
+
+	if (flags & BISECT_SHOW_ALL) {
+		traverse_commit_list(revs, show_commit, show_object, info);
+		printf("------\n");
+	}
+
+	if (flags & BISECT_SHOW_TRIED)
+		show_tried_revs(tried, flags & BISECT_SHOW_STRINGED);
+	format = (flags & BISECT_SHOW_STRINGED) ?
+		"bisect_rev=%s &&\n"
+		"bisect_nr=%d &&\n"
+		"bisect_good=%d &&\n"
+		"bisect_bad=%d &&\n"
+		"bisect_all=%d &&\n"
+		"bisect_steps=%d\n"
+		:
+		"bisect_rev=%s\n"
+		"bisect_nr=%d\n"
+		"bisect_good=%d\n"
+		"bisect_bad=%d\n"
+		"bisect_all=%d\n"
+		"bisect_steps=%d\n";
+	printf(format,
+	       hex,
+	       cnt - 1,
+	       all - reaches - 1,
+	       reaches - 1,
+	       all,
+	       estimate_bisect_steps(all));
+
+	return 0;
+}
+
 int cmd_rev_list(int argc, const char **argv, const char *prefix)
 {
-	struct commit_list *list;
+	struct rev_info revs;
+	struct rev_list_info info;
 	int i;
 	int read_from_stdin = 0;
+	int bisect_list = 0;
 	int bisect_show_vars = 0;
 	int bisect_find_all = 0;
 	int quiet = 0;
@@ -628,6 +310,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	revs.commit_format = CMIT_FMT_UNSPECIFIED;
 	argc = setup_revisions(argc, argv, &revs, NULL);
 
+	memset(&info, 0, sizeof(info));
+	info.revs = &revs;
+
 	quiet = DIFF_OPT_TST(&revs.diffopt, QUIET);
 	for (i = 1 ; i < argc; i++) {
 		const char *arg = argv[i];
@@ -637,7 +322,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			continue;
 		}
 		if (!strcmp(arg, "--timestamp")) {
-			show_timestamp = 1;
+			info.show_timestamp = 1;
 			continue;
 		}
 		if (!strcmp(arg, "--bisect")) {
@@ -647,6 +332,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		if (!strcmp(arg, "--bisect-all")) {
 			bisect_list = 1;
 			bisect_find_all = 1;
+			info.bisect_show_flags = BISECT_SHOW_ALL;
 			revs.show_decorations = 1;
 			continue;
 		}
@@ -666,19 +352,17 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	}
 	if (revs.commit_format != CMIT_FMT_UNSPECIFIED) {
 		/* The command line has a --pretty  */
-		hdr_termination = '\n';
+		info.hdr_termination = '\n';
 		if (revs.commit_format == CMIT_FMT_ONELINE)
-			header_prefix = "";
+			info.header_prefix = "";
 		else
-			header_prefix = "commit ";
+			info.header_prefix = "commit ";
 	}
 	else if (revs.verbose_header)
 		/* Only --header was specified */
 		revs.commit_format = CMIT_FMT_RAW;
 
-	list = revs.commits;
-
-	if ((!list &&
+	if ((!revs.commits &&
 	     (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) &&
 	      !revs.pending.nr)) ||
 	    revs.diff)
@@ -699,49 +383,15 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 
 		revs.commits = find_bisection(revs.commits, &reaches, &all,
 					      bisect_find_all);
-		if (bisect_show_vars) {
-			int cnt;
-			char hex[41];
-			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;
-			strcpy(hex, sha1_to_hex(revs.commits->item->object.sha1));
-
-			if (bisect_find_all) {
-				traverse_commit_list(&revs, show_commit, show_object);
-				printf("------\n");
-			}
 
-			printf("bisect_rev=%s\n"
-			       "bisect_nr=%d\n"
-			       "bisect_good=%d\n"
-			       "bisect_bad=%d\n"
-			       "bisect_all=%d\n"
-			       "bisect_steps=%d\n",
-			       hex,
-			       cnt - 1,
-			       all - reaches - 1,
-			       reaches - 1,
-			       all,
-			       estimate_bisect_steps(all));
-			return 0;
-		}
+		if (bisect_show_vars)
+			return show_bisect_vars(&info, reaches, all);
 	}
 
 	traverse_commit_list(&revs,
-		quiet ? finish_commit : show_commit,
-		quiet ? finish_object : show_object);
+			     quiet ? finish_commit : show_commit,
+			     quiet ? finish_object : show_object,
+			     &info);
 
 	return 0;
 }
diff --git a/builtin.h b/builtin.h
index 1495cf6a20..425ff8e89b 100644
--- a/builtin.h
+++ b/builtin.h
@@ -25,6 +25,7 @@ extern int cmd_add(int argc, const char **argv, const char *prefix);
 extern int cmd_annotate(int argc, const char **argv, const char *prefix);
 extern int cmd_apply(int argc, const char **argv, const char *prefix);
 extern int cmd_archive(int argc, const char **argv, const char *prefix);
+extern int cmd_bisect__helper(int argc, const char **argv, const char *prefix);
 extern int cmd_blame(int argc, const char **argv, const char *prefix);
 extern int cmd_branch(int argc, const char **argv, const char *prefix);
 extern int cmd_bundle(int argc, const char **argv, const char *prefix);
diff --git a/git-bisect.sh b/git-bisect.sh
index df0ae63b4e..24712ff304 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -279,87 +279,14 @@ bisect_auto_next() {
 	bisect_next_check && bisect_next || :
 }
 
-filter_skipped() {
-	_eval="$1"
-	_skip="$2"
-
-	if [ -z "$_skip" ]; then
-		eval "$_eval" | {
-			while read line
-			do
-				echo "$line &&"
-			done
-			echo ':'
-		}
-		return
-	fi
-
-	# Let's parse the output of:
-	# "git rev-list --bisect-vars --bisect-all ..."
-	eval "$_eval" | {
-		VARS= FOUND= TRIED=
-		while read hash line
-		do
-			case "$VARS,$FOUND,$TRIED,$hash" in
-			1,*,*,*)
-				# "bisect_foo=bar" read from rev-list output.
-				echo "$hash &&"
-				;;
-			,*,*,---*)
-				# Separator
-				;;
-			,,,bisect_rev*)
-				# We had nothing to search.
-				echo "bisect_rev= &&"
-				VARS=1
-				;;
-			,,*,bisect_rev*)
-				# We did not find a good bisect rev.
-				# This should happen only if the "bad"
-				# commit is also a "skip" commit.
-				echo "bisect_rev='$TRIED' &&"
-				VARS=1
-				;;
-			,,*,*)
-				# We are searching.
-				TRIED="${TRIED:+$TRIED|}$hash"
-				case "$_skip" in
-				*$hash*) ;;
-				*)
-					echo "bisect_rev=$hash &&"
-					echo "bisect_tried='$TRIED' &&"
-					FOUND=1
-					;;
-				esac
-				;;
-			,1,*,bisect_rev*)
-				# We have already found a rev to be tested.
-				VARS=1
-				;;
-			,1,*,*)
-				;;
-			*)
-				# Unexpected input
-				echo "die 'filter_skipped error'"
-				die "filter_skipped error " \
-				    "VARS: '$VARS' " \
-				    "FOUND: '$FOUND' " \
-				    "TRIED: '$TRIED' " \
-				    "hash: '$hash' " \
-				    "line: '$line'"
-				;;
-			esac
-		done
-		echo ':'
-	}
-}
-
 exit_if_skipped_commits () {
 	_tried=$1
-	if expr "$_tried" : ".*[|].*" > /dev/null ; then
+	_bad=$2
+	if test -n "$_tried" ; then
 		echo "There are only 'skip'ped commit left to test."
 		echo "The first bad commit could be any of:"
 		echo "$_tried" | tr '[|]' '[\012]'
+		test -n "$_bad" && echo "$_bad"
 		echo "We cannot bisect more!"
 		exit 2
 	fi
@@ -490,28 +417,23 @@ bisect_next() {
 	test "$?" -eq "1" && return
 
 	# Get bisection information
-	BISECT_OPT=''
-	test -n "$skip" && BISECT_OPT='--bisect-all'
-	eval="git rev-list --bisect-vars $BISECT_OPT $good $bad --" &&
-	eval="$eval $(cat "$GIT_DIR/BISECT_NAMES")" &&
-	eval=$(filter_skipped "$eval" "$skip") &&
+	eval=$(eval "git bisect--helper --next-vars") &&
 	eval "$eval" || exit
 
 	if [ -z "$bisect_rev" ]; then
+		# We should exit here only if the "bad"
+		# commit is also a "skip" commit (see above).
+		exit_if_skipped_commits "$bisect_tried"
 		echo "$bad was both good and bad"
 		exit 1
 	fi
 	if [ "$bisect_rev" = "$bad" ]; then
-		exit_if_skipped_commits "$bisect_tried"
+		exit_if_skipped_commits "$bisect_tried" "$bad"
 		echo "$bisect_rev is first bad commit"
 		git diff-tree --pretty $bisect_rev
 		exit 0
 	fi
 
-	# We should exit here only if the "bad"
-	# commit is also a "skip" commit (see above).
-	exit_if_skipped_commits "$bisect_rev"
-
 	bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this (roughly $bisect_steps steps)"
 }
 
diff --git a/git.c b/git.c
index ff72e22bec..bfb6508ad0 100644
--- a/git.c
+++ b/git.c
@@ -274,6 +274,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "annotate", cmd_annotate, RUN_SETUP },
 		{ "apply", cmd_apply },
 		{ "archive", cmd_archive },
+		{ "bisect--helper", cmd_bisect__helper, RUN_SETUP | NEED_WORK_TREE },
 		{ "blame", cmd_blame, RUN_SETUP },
 		{ "branch", cmd_branch, RUN_SETUP },
 		{ "bundle", cmd_bundle },
diff --git a/list-objects.c b/list-objects.c
index dd243c7c66..433394a107 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -135,8 +135,9 @@ void mark_edges_uninteresting(struct commit_list *list,
 }
 
 void traverse_commit_list(struct rev_info *revs,
-			  void (*show_commit)(struct commit *),
-			  void (*show_object)(struct object_array_entry *))
+			  show_commit_fn show_commit,
+			  show_object_fn show_object,
+			  void *data)
 {
 	int i;
 	struct commit *commit;
@@ -144,7 +145,7 @@ void traverse_commit_list(struct rev_info *revs,
 
 	while ((commit = get_revision(revs)) != NULL) {
 		process_tree(revs, commit->tree, &objects, NULL, "");
-		show_commit(commit);
+		show_commit(commit, data);
 	}
 	for (i = 0; i < revs->pending.nr; i++) {
 		struct object_array_entry *pending = revs->pending.objects + i;
@@ -171,7 +172,7 @@ void traverse_commit_list(struct rev_info *revs,
 		    sha1_to_hex(obj->sha1), name);
 	}
 	for (i = 0; i < objects.nr; i++)
-		show_object(&objects.objects[i]);
+		show_object(&objects.objects[i], data);
 	free(objects.objects);
 	if (revs->pending.nr) {
 		free(revs->pending.objects);
diff --git a/list-objects.h b/list-objects.h
index 0f41391ecc..47fae2e468 100644
--- a/list-objects.h
+++ b/list-objects.h
@@ -1,11 +1,11 @@
 #ifndef LIST_OBJECTS_H
 #define LIST_OBJECTS_H
 
-typedef void (*show_commit_fn)(struct commit *);
-typedef void (*show_object_fn)(struct object_array_entry *);
+typedef void (*show_commit_fn)(struct commit *, void *);
+typedef void (*show_object_fn)(struct object_array_entry *, void *);
 typedef void (*show_edge_fn)(struct commit *);
 
-void traverse_commit_list(struct rev_info *revs, show_commit_fn, show_object_fn);
+void traverse_commit_list(struct rev_info *, show_commit_fn, show_object_fn, void *);
 
 void mark_edges_uninteresting(struct commit_list *, struct rev_info *, show_edge_fn);
 
diff --git a/patch-ids.c b/patch-ids.c
index 3be5d3165e..5717257051 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "diff.h"
 #include "commit.h"
+#include "sha1-lookup.h"
 #include "patch-ids.h"
 
 static int commit_patch_id(struct commit *commit, struct diff_options *options,
@@ -15,99 +16,15 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,
 	return diff_flush_patch_id(options, sha1);
 }
 
-static uint32_t take2(const unsigned char *id)
+static const unsigned char *patch_id_access(size_t index, void *table)
 {
-	return ((id[0] << 8) | id[1]);
+	struct patch_id **id_table = table;
+	return id_table[index]->patch_id;
 }
 
-/*
- * Conventional binary search loop looks like this:
- *
- *      do {
- *              int mi = (lo + hi) / 2;
- *              int cmp = "entry pointed at by mi" minus "target";
- *              if (!cmp)
- *                      return (mi is the wanted one)
- *              if (cmp > 0)
- *                      hi = mi; "mi is larger than target"
- *              else
- *                      lo = mi+1; "mi is smaller than target"
- *      } while (lo < hi);
- *
- * The invariants are:
- *
- * - When entering the loop, lo points at a slot that is never
- *   above the target (it could be at the target), hi points at a
- *   slot that is guaranteed to be above the target (it can never
- *   be at the target).
- *
- * - We find a point 'mi' between lo and hi (mi could be the same
- *   as lo, but never can be the same as hi), and check if it hits
- *   the target.  There are three cases:
- *
- *    - if it is a hit, we are happy.
- *
- *    - if it is strictly higher than the target, we update hi with
- *      it.
- *
- *    - if it is strictly lower than the target, we update lo to be
- *      one slot after it, because we allow lo to be at the target.
- *
- * When choosing 'mi', we do not have to take the "middle" but
- * anywhere in between lo and hi, as long as lo <= mi < hi is
- * satisfied.  When we somehow know that the distance between the
- * target and lo is much shorter than the target and hi, we could
- * pick mi that is much closer to lo than the midway.
- */
 static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)
 {
-	int hi = nr;
-	int lo = 0;
-	int mi = 0;
-
-	if (!nr)
-		return -1;
-
-	if (nr != 1) {
-		unsigned lov, hiv, miv, ofs;
-
-		for (ofs = 0; ofs < 18; ofs += 2) {
-			lov = take2(table[0]->patch_id + ofs);
-			hiv = take2(table[nr-1]->patch_id + ofs);
-			miv = take2(id + ofs);
-			if (miv < lov)
-				return -1;
-			if (hiv < miv)
-				return -1 - nr;
-			if (lov != hiv) {
-				/*
-				 * At this point miv could be equal
-				 * to hiv (but id could still be higher);
-				 * the invariant of (mi < hi) should be
-				 * kept.
-				 */
-				mi = (nr-1) * (miv - lov) / (hiv - lov);
-				if (lo <= mi && mi < hi)
-					break;
-				die("oops");
-			}
-		}
-		if (18 <= ofs)
-			die("cannot happen -- lo and hi are identical");
-	}
-
-	do {
-		int cmp;
-		cmp = hashcmp(table[mi]->patch_id, id);
-		if (!cmp)
-			return mi;
-		if (cmp > 0)
-			hi = mi;
-		else
-			lo = mi + 1;
-		mi = (hi + lo) / 2;
-	} while (lo < hi);
-	return -lo-1;
+	return sha1_pos(id, table, nr, patch_id_access);
 }
 
 #define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */
diff --git a/quote.c b/quote.c
index 6a520855d6..7a49fcf696 100644
--- a/quote.c
+++ b/quote.c
@@ -72,7 +72,7 @@ void sq_quote_argv(struct strbuf *dst, const char** argv, size_t maxlen)
 	}
 }
 
-char *sq_dequote(char *arg)
+char *sq_dequote_step(char *arg, char **next)
 {
 	char *dst = arg;
 	char *src = arg;
@@ -92,6 +92,8 @@ char *sq_dequote(char *arg)
 		switch (*++src) {
 		case '\0':
 			*dst = 0;
+			if (next)
+				*next = NULL;
 			return arg;
 		case '\\':
 			c = *++src;
@@ -101,11 +103,40 @@ char *sq_dequote(char *arg)
 			}
 		/* Fallthrough */
 		default:
-			return NULL;
+			if (!next || !isspace(*src))
+				return NULL;
+			do {
+				c = *++src;
+			} while (isspace(c));
+			*dst = 0;
+			*next = src;
+			return arg;
 		}
 	}
 }
 
+char *sq_dequote(char *arg)
+{
+	return sq_dequote_step(arg, NULL);
+}
+
+int sq_dequote_to_argv(char *arg, const char ***argv, int *nr, int *alloc)
+{
+	char *next = arg;
+
+	if (!*arg)
+		return 0;
+	do {
+		char *dequoted = sq_dequote_step(next, &next);
+		if (!dequoted)
+			return -1;
+		ALLOC_GROW(*argv, *nr + 1, *alloc);
+		(*argv)[(*nr)++] = dequoted;
+	} while (next);
+
+	return 0;
+}
+
 /* 1 means: quote as octal
  * 0 means: quote as octal if (quote_path_fully)
  * -1 means: never quote
diff --git a/quote.h b/quote.h
index c5eea6f18e..66730f2bff 100644
--- a/quote.h
+++ b/quote.h
@@ -39,6 +39,15 @@ extern void sq_quote_argv(struct strbuf *, const char **argv, size_t maxlen);
  */
 extern char *sq_dequote(char *);
 
+/*
+ * Same as the above, but can be used to unwrap many arguments in the
+ * same string separated by space. "next" is changed to point to the
+ * next argument that should be passed as first parameter. When there
+ * is no more argument to be dequoted, "next" is updated to point to NULL.
+ */
+extern char *sq_dequote_step(char *arg, char **next);
+extern int sq_dequote_to_argv(char *arg, const char ***argv, int *nr, int *alloc);
+
 extern int unquote_c_style(struct strbuf *, const char *quoted, const char **endp);
 extern size_t quote_c_style(const char *name, struct strbuf *, FILE *, int no_dq);
 extern void quote_two_c_style(struct strbuf *, const char *, const char *, int);
diff --git a/refs.c b/refs.c
index 59c373fc6d..9ccaf40172 100644
--- a/refs.c
+++ b/refs.c
@@ -647,19 +647,24 @@ int for_each_ref(each_ref_fn fn, void *cb_data)
 	return do_for_each_ref("refs/", fn, 0, 0, cb_data);
 }
 
+int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data)
+{
+	return do_for_each_ref(prefix, fn, strlen(prefix), 0, cb_data);
+}
+
 int for_each_tag_ref(each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref("refs/tags/", fn, 10, 0, cb_data);
+	return for_each_ref_in("refs/tags/", fn, cb_data);
 }
 
 int for_each_branch_ref(each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref("refs/heads/", fn, 11, 0, cb_data);
+	return for_each_ref_in("refs/heads/", fn, cb_data);
 }
 
 int for_each_remote_ref(each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref("refs/remotes/", fn, 13, 0, cb_data);
+	return for_each_ref_in("refs/remotes/", fn, cb_data);
 }
 
 int for_each_rawref(each_ref_fn fn, void *cb_data)
diff --git a/refs.h b/refs.h
index 68c2d16d53..2f6a8af608 100644
--- a/refs.h
+++ b/refs.h
@@ -20,6 +20,7 @@ struct ref_lock {
 typedef int each_ref_fn(const char *refname, const unsigned char *sha1, int flags, void *cb_data);
 extern int head_ref(each_ref_fn, void *);
 extern int for_each_ref(each_ref_fn, void *);
+extern int for_each_ref_in(const char *, each_ref_fn, void *);
 extern int for_each_tag_ref(each_ref_fn, void *);
 extern int for_each_branch_ref(each_ref_fn, void *);
 extern int for_each_remote_ref(each_ref_fn, void *);
diff --git a/sha1-lookup.c b/sha1-lookup.c
index da357479cf..055dd87dc1 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -1,6 +1,107 @@
 #include "cache.h"
 #include "sha1-lookup.h"
 
+static uint32_t take2(const unsigned char *sha1)
+{
+	return ((sha1[0] << 8) | sha1[1]);
+}
+
+/*
+ * Conventional binary search loop looks like this:
+ *
+ *      do {
+ *              int mi = (lo + hi) / 2;
+ *              int cmp = "entry pointed at by mi" minus "target";
+ *              if (!cmp)
+ *                      return (mi is the wanted one)
+ *              if (cmp > 0)
+ *                      hi = mi; "mi is larger than target"
+ *              else
+ *                      lo = mi+1; "mi is smaller than target"
+ *      } while (lo < hi);
+ *
+ * The invariants are:
+ *
+ * - When entering the loop, lo points at a slot that is never
+ *   above the target (it could be at the target), hi points at a
+ *   slot that is guaranteed to be above the target (it can never
+ *   be at the target).
+ *
+ * - We find a point 'mi' between lo and hi (mi could be the same
+ *   as lo, but never can be the same as hi), and check if it hits
+ *   the target.  There are three cases:
+ *
+ *    - if it is a hit, we are happy.
+ *
+ *    - if it is strictly higher than the target, we update hi with
+ *      it.
+ *
+ *    - if it is strictly lower than the target, we update lo to be
+ *      one slot after it, because we allow lo to be at the target.
+ *
+ * When choosing 'mi', we do not have to take the "middle" but
+ * anywhere in between lo and hi, as long as lo <= mi < hi is
+ * satisfied.  When we somehow know that the distance between the
+ * target and lo is much shorter than the target and hi, we could
+ * pick mi that is much closer to lo than the midway.
+ */
+/*
+ * The table should contain "nr" elements.
+ * The sha1 of element i (between 0 and nr - 1) should be returned
+ * by "fn(i, table)".
+ */
+int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
+	     sha1_access_fn fn)
+{
+	size_t hi = nr;
+	size_t lo = 0;
+	size_t mi = 0;
+
+	if (!nr)
+		return -1;
+
+	if (nr != 1) {
+		size_t lov, hiv, miv, ofs;
+
+		for (ofs = 0; ofs < 18; ofs += 2) {
+			lov = take2(fn(0, table) + ofs);
+			hiv = take2(fn(nr - 1, table) + ofs);
+			miv = take2(sha1 + ofs);
+			if (miv < lov)
+				return -1;
+			if (hiv < miv)
+				return -1 - nr;
+			if (lov != hiv) {
+				/*
+				 * At this point miv could be equal
+				 * to hiv (but sha1 could still be higher);
+				 * the invariant of (mi < hi) should be
+				 * kept.
+				 */
+				mi = (nr - 1) * (miv - lov) / (hiv - lov);
+				if (lo <= mi && mi < hi)
+					break;
+				die("oops");
+			}
+		}
+		if (18 <= ofs)
+			die("cannot happen -- lo and hi are identical");
+	}
+
+	do {
+		int cmp;
+		cmp = hashcmp(fn(mi, table), sha1);
+		if (!cmp)
+			return mi;
+		if (cmp > 0)
+			hi = mi;
+		else
+			lo = mi + 1;
+		mi = (hi + lo) / 2;
+	} while (lo < hi);
+	return -lo-1;
+}
+
 /*
  * Conventional binary search loop looks like this:
  *
diff --git a/sha1-lookup.h b/sha1-lookup.h
index 3249a81b3d..20af285681 100644
--- a/sha1-lookup.h
+++ b/sha1-lookup.h
@@ -1,6 +1,13 @@
 #ifndef SHA1_LOOKUP_H
 #define SHA1_LOOKUP_H
 
+typedef const unsigned char *sha1_access_fn(size_t index, void *table);
+
+extern int sha1_pos(const unsigned char *sha1,
+		    void *table,
+		    size_t nr,
+		    sha1_access_fn fn);
+
 extern int sha1_entry_pos(const void *table,
 			  size_t elem_size,
 			  size_t key_offset,
diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index 052a6c90f5..54b7ea6505 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -506,6 +506,66 @@ test_expect_success 'optimized merge base checks' '
 	unset GIT_TRACE
 '
 
+# This creates another side branch called "parallel" with some files
+# in some directories, to test bisecting with paths.
+#
+# We should have the following:
+#
+#    P1-P2-P3-P4-P5-P6-P7
+#   /        /        /
+# H1-H2-H3-H4-H5-H6-H7
+#            \  \     \
+#             S5-A     \
+#              \        \
+#               S6-S7----B
+#
+test_expect_success '"parallel" side branch creation' '
+	git bisect reset &&
+	git checkout -b parallel $HASH1 &&
+	mkdir dir1 dir2 &&
+	add_line_into_file "1(para): line 1 on parallel branch" dir1/file1 &&
+	PARA_HASH1=$(git rev-parse --verify HEAD) &&
+	add_line_into_file "2(para): line 2 on parallel branch" dir2/file2 &&
+	PARA_HASH2=$(git rev-parse --verify HEAD) &&
+	add_line_into_file "3(para): line 3 on parallel branch" dir2/file3 &&
+	PARA_HASH3=$(git rev-parse --verify HEAD)
+	git merge -m "merge HASH4 and PARA_HASH3" "$HASH4" &&
+	PARA_HASH4=$(git rev-parse --verify HEAD)
+	add_line_into_file "5(para): add line on parallel branch" dir1/file1 &&
+	PARA_HASH5=$(git rev-parse --verify HEAD)
+	add_line_into_file "6(para): add line on parallel branch" dir2/file2 &&
+	PARA_HASH6=$(git rev-parse --verify HEAD)
+	git merge -m "merge HASH7 and PARA_HASH6" "$HASH7" &&
+	PARA_HASH7=$(git rev-parse --verify HEAD)
+'
+
+test_expect_success 'restricting bisection on one dir' '
+	git bisect reset &&
+	git bisect start HEAD $HASH1 -- dir1 &&
+	para1=$(git rev-parse --verify HEAD) &&
+	test "$para1" = "$PARA_HASH1" &&
+	git bisect bad > my_bisect_log.txt &&
+	grep "$PARA_HASH1 is first bad commit" my_bisect_log.txt
+'
+
+test_expect_success 'restricting bisection on one dir and a file' '
+	git bisect reset &&
+	git bisect start HEAD $HASH1 -- dir1 hello &&
+	para4=$(git rev-parse --verify HEAD) &&
+	test "$para4" = "$PARA_HASH4" &&
+	git bisect bad &&
+	hash3=$(git rev-parse --verify HEAD) &&
+	test "$hash3" = "$HASH3" &&
+	git bisect good &&
+	hash4=$(git rev-parse --verify HEAD) &&
+	test "$hash4" = "$HASH4" &&
+	git bisect good &&
+	para1=$(git rev-parse --verify HEAD) &&
+	test "$para1" = "$PARA_HASH1" &&
+	git bisect good > my_bisect_log.txt &&
+	grep "$PARA_HASH4 is first bad commit" my_bisect_log.txt
+'
+
 #
 #
 test_done
diff --git a/upload-pack.c b/upload-pack.c
index a49d872447..495c99f80a 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -66,7 +66,7 @@ static ssize_t send_client_data(int fd, const char *data, ssize_t sz)
 }
 
 static FILE *pack_pipe = NULL;
-static void show_commit(struct commit *commit)
+static void show_commit(struct commit *commit, void *data)
 {
 	if (commit->object.flags & BOUNDARY)
 		fputc('-', pack_pipe);
@@ -78,7 +78,7 @@ static void show_commit(struct commit *commit)
 	commit->buffer = NULL;
 }
 
-static void show_object(struct object_array_entry *p)
+static void show_object(struct object_array_entry *p, void *data)
 {
 	/* An object with name "foo\n0000000..." can be used to
 	 * confuse downstream git-pack-objects very badly.
@@ -134,7 +134,7 @@ static int do_rev_list(int fd, void *create_full_pack)
 	if (prepare_revision_walk(&revs))
 		die("revision walk setup failed");
 	mark_edges_uninteresting(revs.commits, &revs, show_edge);
-	traverse_commit_list(&revs, show_commit, show_object);
+	traverse_commit_list(&revs, show_commit, show_object, NULL);
 	fflush(pack_pipe);
 	fclose(pack_pipe);
 	return 0;