[PATCH 00/10] bisect: port git bisect merge base checking to C

[PATCH 00/10] bisect: port git bisect merge base checking to C

[Christian Couder]

This patch series continues porting "git bisect next" code
from shell in "git-bisect.sh" to C in "bisect.c".

After this series, the bisect ref lookup is done only once in the
C code, instead of once in the shell code and once in the C code.

  bisect: use "sha1_array" to store skipped revisions
  bisect: implement "rev_argv_push" to fill an argv with revs
  bisect: store good revisions in a "sha1_array"
  bisect: use new "struct argv_array" to prepare argv for
    "setup_revisions"
  bisect: remove too much function nesting
  bisect: make skipped array functions more generic
  bisect: automatically sort sha1_array if needed when looking it up
  bisect: implement the "check_merge_bases" function
  bisect: add "check_good_are_ancestors_of_bad" function
  bisect: make "git bisect" use new "--next-all" bisect-helper function

 bisect.c                 |  342 ++++++++++++++++++++++++++++++++++++++--------
 bisect.h                 |    2 +-
 builtin-bisect--helper.c |   14 +-
 git-bisect.sh            |  127 +-----------------
 4 files changed, 296 insertions(+), 189 deletions(-)

[PATCH 01/10] bisect: use "sha1_array" to store skipped revisions

[Christian Couder]

This patch creates a "struct sha1_array" to store skipped revisions,
so that the same struct can be reused in a later patch for good
revisions.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   25 +++++++++++++++----------
 1 files changed, 15 insertions(+), 10 deletions(-)

diff --git a/bisect.c b/bisect.c
index 4796aa9..12df855 100644
--- a/bisect.c
+++ b/bisect.c
@@ -9,9 +9,13 @@
 #include "run-command.h"
 #include "bisect.h"
 
-static unsigned char (*skipped_sha1)[20];
-static int skipped_sha1_nr;
-static int skipped_sha1_alloc;
+struct sha1_array {
+	unsigned char (*sha1)[20];
+	int sha1_nr;
+	int sha1_alloc;
+};
+
+static struct sha1_array skipped_revs;
 
 static const char **rev_argv;
 static int rev_argv_nr;
@@ -420,9 +424,9 @@ static int register_ref(const char *refname, const unsigned char *sha1,
 		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);
+		ALLOC_GROW(skipped_revs.sha1, skipped_revs.sha1_nr + 1,
+			   skipped_revs.sha1_alloc);
+		hashcpy(skipped_revs.sha1[skipped_revs.sha1_nr++], sha1);
 	}
 
 	return 0;
@@ -466,7 +470,8 @@ static int skipcmp(const void *a, const void *b)
 
 static void prepare_skipped(void)
 {
-	qsort(skipped_sha1, skipped_sha1_nr, sizeof(*skipped_sha1), skipcmp);
+	qsort(skipped_revs.sha1, skipped_revs.sha1_nr,
+	      sizeof(*skipped_revs.sha1), skipcmp);
 }
 
 static const unsigned char *skipped_sha1_access(size_t index, void *table)
@@ -477,7 +482,7 @@ static const unsigned char *skipped_sha1_access(size_t index, void *table)
 
 static int lookup_skipped(unsigned char *sha1)
 {
-	return sha1_pos(sha1, skipped_sha1, skipped_sha1_nr,
+	return sha1_pos(sha1, skipped_revs.sha1, skipped_revs.sha1_nr,
 			skipped_sha1_access);
 }
 
@@ -489,7 +494,7 @@ struct commit_list *filter_skipped(struct commit_list *list,
 
 	*tried = NULL;
 
-	if (!skipped_sha1_nr)
+	if (!skipped_revs.sha1_nr)
 		return list;
 
 	prepare_skipped();
@@ -551,7 +556,7 @@ static void bisect_common(struct rev_info *revs, const char *prefix,
 		mark_edges_uninteresting(revs->commits, revs, NULL);
 
 	revs->commits = find_bisection(revs->commits, reaches, all,
-				       !!skipped_sha1_nr);
+				       !!skipped_revs.sha1_nr);
 }
 
 static void exit_if_skipped_commits(struct commit_list *tried,
-- 
1.6.3.rc1.112.g17e25

[PATCH 02/10] bisect: implement "rev_argv_push" to fill an argv with revs

[Christian Couder]

This patch is a minor clean up right now, but the new function
will evolve and be used more later.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   19 +++++++++++--------
 1 files changed, 11 insertions(+), 8 deletions(-)

diff --git a/bisect.c b/bisect.c
index 12df855..f99637d 100644
--- a/bisect.c
+++ b/bisect.c
@@ -409,20 +409,23 @@ struct commit_list *find_bisection(struct commit_list *list,
 	return best;
 }
 
+static void rev_argv_push(const unsigned char *sha1, const char *format)
+{
+	struct strbuf buf = STRBUF_INIT;
+
+	strbuf_addf(&buf, format, sha1_to_hex(sha1));
+	ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
+	rev_argv[rev_argv_nr++] = strbuf_detach(&buf, NULL);
+}
+
 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);
 		current_bad_sha1 = sha1;
-		rev_argv[rev_argv_nr++] = xstrdup(sha1_to_hex(sha1));
+		rev_argv_push(sha1, "%s");
 	} 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;
+		rev_argv_push(sha1, "^%s");
 	} else if (!prefixcmp(refname, "skip-")) {
 		ALLOC_GROW(skipped_revs.sha1, skipped_revs.sha1_nr + 1,
 			   skipped_revs.sha1_alloc);
-- 
1.6.3.rc1.112.g17e25

[PATCH 03/10] bisect: store good revisions in a "sha1_array"

[Christian Couder]

This will make it easier to use good revisions for checking merge
bases later.

To simplify the code, a new "sha1_array_push" function is also
introduced.

And while at it we move the earlier part of the code to fill the
argv that is passed to "setup_revisions", so that all this code is
now completely after "read_bisect_refs".

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   26 +++++++++++++++++++-------
 1 files changed, 19 insertions(+), 7 deletions(-)

diff --git a/bisect.c b/bisect.c
index f99637d..7976cbf 100644
--- a/bisect.c
+++ b/bisect.c
@@ -15,6 +15,7 @@ struct sha1_array {
 	int sha1_alloc;
 };
 
+static struct sha1_array good_revs;
 static struct sha1_array skipped_revs;
 
 static const char **rev_argv;
@@ -418,18 +419,22 @@ static void rev_argv_push(const unsigned char *sha1, const char *format)
 	rev_argv[rev_argv_nr++] = strbuf_detach(&buf, NULL);
 }
 
+static void sha1_array_push(struct sha1_array *array,
+			    const unsigned char *sha1)
+{
+	ALLOC_GROW(array->sha1, array->sha1_nr + 1, array->sha1_alloc);
+	hashcpy(array->sha1[array->sha1_nr++], sha1);
+}
+
 static int register_ref(const char *refname, const unsigned char *sha1,
 			int flags, void *cb_data)
 {
 	if (!strcmp(refname, "bad")) {
 		current_bad_sha1 = sha1;
-		rev_argv_push(sha1, "%s");
 	} else if (!prefixcmp(refname, "good-")) {
-		rev_argv_push(sha1, "^%s");
+		sha1_array_push(&good_revs, sha1);
 	} else if (!prefixcmp(refname, "skip-")) {
-		ALLOC_GROW(skipped_revs.sha1, skipped_revs.sha1_nr + 1,
-			   skipped_revs.sha1_alloc);
-		hashcpy(skipped_revs.sha1[skipped_revs.sha1_nr++], sha1);
+		sha1_array_push(&skipped_revs, sha1);
 	}
 
 	return 0;
@@ -524,16 +529,23 @@ struct commit_list *filter_skipped(struct commit_list *list,
 
 static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
 {
+	int i;
+
 	init_revisions(revs, prefix);
 	revs->abbrev = 0;
 	revs->commit_format = CMIT_FMT_UNSPECIFIED;
 
+	if (read_bisect_refs())
+		die("reading bisect refs failed");
+
 	/* 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");
+	rev_argv_push(current_bad_sha1, "%s");
+
+	for (i = 0; i < good_revs.sha1_nr; i++)
+		rev_argv_push(good_revs.sha1[i], "^%s");
 
 	ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
 	rev_argv[rev_argv_nr++] = xstrdup("--");
-- 
1.6.3.rc1.112.g17e25

[PATCH 04/10] bisect: use new "struct argv_array" to prepare argv for "setup_revisions"

[Christian Couder]

Because we will use other instances of this struct.

The "rev_argv_push" function is changed into 2 functions
"argv_array_push" and "argv_array_push_sha1" that take a "struct
argv_array *" as first argument. And these functions are used to
simplify "bisect_rev_setup".

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   57 +++++++++++++++++++++++++++++----------------------------
 1 files changed, 29 insertions(+), 28 deletions(-)

diff --git a/bisect.c b/bisect.c
index 7976cbf..8e34186 100644
--- a/bisect.c
+++ b/bisect.c
@@ -18,12 +18,16 @@ struct sha1_array {
 static struct sha1_array good_revs;
 static struct sha1_array skipped_revs;
 
-static const char **rev_argv;
-static int rev_argv_nr;
-static int rev_argv_alloc;
-
 static const unsigned char *current_bad_sha1;
 
+struct argv_array {
+	const char **argv;
+	int argv_nr;
+	int argv_alloc;
+};
+
+struct argv_array rev_argv;
+
 static const char *argv_diff_tree[] = {"diff-tree", "--pretty", NULL, NULL};
 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
@@ -410,13 +414,19 @@ struct commit_list *find_bisection(struct commit_list *list,
 	return best;
 }
 
-static void rev_argv_push(const unsigned char *sha1, const char *format)
+static void argv_array_push(struct argv_array *array, const char *string)
 {
-	struct strbuf buf = STRBUF_INIT;
+	ALLOC_GROW(array->argv, array->argv_nr + 1, array->argv_alloc);
+	array->argv[array->argv_nr++] = string;
+}
 
+static void argv_array_push_sha1(struct argv_array *array,
+				 const unsigned char *sha1,
+				 const char *format)
+{
+	struct strbuf buf = STRBUF_INIT;
 	strbuf_addf(&buf, format, sha1_to_hex(sha1));
-	ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
-	rev_argv[rev_argv_nr++] = strbuf_detach(&buf, NULL);
+	argv_array_push(array, strbuf_detach(&buf, NULL));
 }
 
 static void sha1_array_push(struct sha1_array *array,
@@ -445,7 +455,7 @@ static int read_bisect_refs(void)
 	return for_each_ref_in("refs/bisect/", register_ref, NULL);
 }
 
-void read_bisect_paths(void)
+void read_bisect_paths(struct argv_array *array)
 {
 	struct strbuf str = STRBUF_INIT;
 	const char *filename = git_path("BISECT_NAMES");
@@ -460,8 +470,8 @@ void read_bisect_paths(void)
 
 		strbuf_trim(&str);
 		quoted = strbuf_detach(&str, NULL);
-		res = sq_dequote_to_argv(quoted, &rev_argv,
-					 &rev_argv_nr, &rev_argv_alloc);
+		res = sq_dequote_to_argv(quoted, &array->argv,
+					 &array->argv_nr, &array->argv_alloc);
 		if (res)
 			die("Badly quoted content in file '%s': %s",
 			    filename, quoted);
@@ -538,25 +548,16 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
 	if (read_bisect_refs())
 		die("reading bisect refs failed");
 
-	/* 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");
-
-	rev_argv_push(current_bad_sha1, "%s");
-
+	/* rev_argv.argv[0] will be ignored by setup_revisions */
+	argv_array_push(&rev_argv, xstrdup("bisect_rev_setup"));
+	argv_array_push_sha1(&rev_argv, current_bad_sha1, "%s");
 	for (i = 0; i < good_revs.sha1_nr; i++)
-		rev_argv_push(good_revs.sha1[i], "^%s");
-
-	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);
+		argv_array_push_sha1(&rev_argv, good_revs.sha1[i], "^%s");
+	argv_array_push(&rev_argv, xstrdup("--"));
+	read_bisect_paths(&rev_argv);
+	argv_array_push(&rev_argv, NULL);
 
+	setup_revisions(rev_argv.argv_nr, rev_argv.argv, revs, NULL);
 	revs->limited = 1;
 }
 
-- 
1.6.3.rc1.112.g17e25

[PATCH 05/10] bisect: remove too much function nesting

[Christian Couder]

This patch moves some function calls into "bisect_next_exit" so
that functions are nesting less.

The call to "bisect_rev_setup" is moved from "bisect_common" into
"bisect_next_exit" and the call to "read_bisect_refs" from
"bisect_rev_setup" into "bisect_next_exit".

While at it, "rev_argv" is moved into "bisect_rev_setup".

This will make it easier and cleaner to implement checking merge
bases.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   18 ++++++++----------
 1 files changed, 8 insertions(+), 10 deletions(-)

diff --git a/bisect.c b/bisect.c
index 8e34186..9e01b9e 100644
--- a/bisect.c
+++ b/bisect.c
@@ -26,8 +26,6 @@ struct argv_array {
 	int argv_alloc;
 };
 
-struct argv_array rev_argv;
-
 static const char *argv_diff_tree[] = {"diff-tree", "--pretty", NULL, NULL};
 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
@@ -539,15 +537,13 @@ struct commit_list *filter_skipped(struct commit_list *list,
 
 static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
 {
+	struct argv_array rev_argv = { NULL, 0, 0 };
 	int i;
 
 	init_revisions(revs, prefix);
 	revs->abbrev = 0;
 	revs->commit_format = CMIT_FMT_UNSPECIFIED;
 
-	if (read_bisect_refs())
-		die("reading bisect refs failed");
-
 	/* rev_argv.argv[0] will be ignored by setup_revisions */
 	argv_array_push(&rev_argv, xstrdup("bisect_rev_setup"));
 	argv_array_push_sha1(&rev_argv, current_bad_sha1, "%s");
@@ -561,11 +557,8 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
 	revs->limited = 1;
 }
 
-static void bisect_common(struct rev_info *revs, const char *prefix,
-			  int *reaches, int *all)
+static void bisect_common(struct rev_info *revs, int *reaches, int *all)
 {
-	bisect_rev_setup(revs, prefix);
-
 	if (prepare_revision_walk(revs))
 		die("revision walk setup failed");
 	if (revs->tree_objects)
@@ -636,7 +629,12 @@ int bisect_next_exit(const char *prefix)
 	const unsigned char *bisect_rev;
 	char bisect_rev_hex[41];
 
-	bisect_common(&revs, prefix, &reaches, &all);
+	if (read_bisect_refs())
+		die("reading bisect refs failed");
+
+	bisect_rev_setup(&revs, prefix);
+
+	bisect_common(&revs, &reaches, &all);
 
 	revs.commits = filter_skipped(revs.commits, &tried, 0);
 
-- 
1.6.3.rc1.112.g17e25

[PATCH 06/10] bisect: make skipped array functions more generic

[Christian Couder]

So they can be used on the good array too.

This is done by renaming many functions and some variables to
remove "skip" in the name, and by adding a
"struct sha1_array *array" argument where needed.

While at it, make the second argument to "lookup_sha1_array"
const. It becomes "const unsigned char *sha1".

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   24 ++++++++++++------------
 1 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/bisect.c b/bisect.c
index 9e01b9e..77edeca 100644
--- a/bisect.c
+++ b/bisect.c
@@ -479,27 +479,26 @@ void read_bisect_paths(struct argv_array *array)
 	fclose(fp);
 }
 
-static int skipcmp(const void *a, const void *b)
+static int array_cmp(const void *a, const void *b)
 {
 	return hashcmp(a, b);
 }
 
-static void prepare_skipped(void)
+static void sort_sha1_array(struct sha1_array *array)
 {
-	qsort(skipped_revs.sha1, skipped_revs.sha1_nr,
-	      sizeof(*skipped_revs.sha1), skipcmp);
+	qsort(array->sha1, array->sha1_nr, sizeof(*array->sha1), array_cmp);
 }
 
-static const unsigned char *skipped_sha1_access(size_t index, void *table)
+static const unsigned char *sha1_access(size_t index, void *table)
 {
-	unsigned char (*skipped)[20] = table;
-	return skipped[index];
+	unsigned char (*array)[20] = table;
+	return array[index];
 }
 
-static int lookup_skipped(unsigned char *sha1)
+static int lookup_sha1_array(struct sha1_array *array,
+			     const unsigned char *sha1)
 {
-	return sha1_pos(sha1, skipped_revs.sha1, skipped_revs.sha1_nr,
-			skipped_sha1_access);
+	return sha1_pos(sha1, array->sha1, array->sha1_nr, sha1_access);
 }
 
 struct commit_list *filter_skipped(struct commit_list *list,
@@ -513,12 +512,13 @@ struct commit_list *filter_skipped(struct commit_list *list,
 	if (!skipped_revs.sha1_nr)
 		return list;
 
-	prepare_skipped();
+	sort_sha1_array(&skipped_revs);
 
 	while (list) {
 		struct commit_list *next = list->next;
 		list->next = NULL;
-		if (0 <= lookup_skipped(list->item->object.sha1)) {
+		if (0 <= lookup_sha1_array(&skipped_revs,
+					   list->item->object.sha1)) {
 			/* Move current to tried list */
 			*tried = list;
 			tried = &list->next;
-- 
1.6.3.rc1.112.g17e25

[PATCH 07/10] bisect: automatically sort sha1_array if needed when looking it up

[Christian Couder]

This makes sha1_array easier to use, so later patches will be simpler.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/bisect.c b/bisect.c
index 77edeca..d2a34d1 100644
--- a/bisect.c
+++ b/bisect.c
@@ -13,6 +13,7 @@ struct sha1_array {
 	unsigned char (*sha1)[20];
 	int sha1_nr;
 	int sha1_alloc;
+	int sorted;
 };
 
 static struct sha1_array good_revs;
@@ -487,6 +488,8 @@ static int array_cmp(const void *a, const void *b)
 static void sort_sha1_array(struct sha1_array *array)
 {
 	qsort(array->sha1, array->sha1_nr, sizeof(*array->sha1), array_cmp);
+
+	array->sorted = 1;
 }
 
 static const unsigned char *sha1_access(size_t index, void *table)
@@ -498,6 +501,9 @@ static const unsigned char *sha1_access(size_t index, void *table)
 static int lookup_sha1_array(struct sha1_array *array,
 			     const unsigned char *sha1)
 {
+	if (!array->sorted)
+		sort_sha1_array(array);
+
 	return sha1_pos(sha1, array->sha1, array->sha1_nr, sha1_access);
 }
 
@@ -512,8 +518,6 @@ struct commit_list *filter_skipped(struct commit_list *list,
 	if (!skipped_revs.sha1_nr)
 		return list;
 
-	sort_sha1_array(&skipped_revs);
-
 	while (list) {
 		struct commit_list *next = list->next;
 		list->next = NULL;
-- 
1.6.3.rc1.112.g17e25

[PATCH 08/10] bisect: implement the "check_merge_bases" function

[Christian Couder]

And all functions needed to make it work.

This is a port from the shell function with the same name
"git-bisect.sh". This function is not used yet but it will be used
later.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |  130 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 130 insertions(+), 0 deletions(-)

diff --git a/bisect.c b/bisect.c
index d2a34d1..b24ee78 100644
--- a/bisect.c
+++ b/bisect.c
@@ -507,6 +507,20 @@ static int lookup_sha1_array(struct sha1_array *array,
 	return sha1_pos(sha1, array->sha1, array->sha1_nr, sha1_access);
 }
 
+static char *join_sha1_array_hex(struct sha1_array *array, char delim)
+{
+	struct strbuf joined_hexs = STRBUF_INIT;
+	int i;
+
+	for (i = 0; i < array->sha1_nr; i++) {
+		strbuf_addstr(&joined_hexs, sha1_to_hex(array->sha1[i]));
+		if (i + 1 < array->sha1_nr)
+			strbuf_addch(&joined_hexs, delim);
+	}
+
+	return strbuf_detach(&joined_hexs, NULL);
+}
+
 struct commit_list *filter_skipped(struct commit_list *list,
 				   struct commit_list **tried,
 				   int show_all)
@@ -587,6 +601,30 @@ static void exit_if_skipped_commits(struct commit_list *tried,
 	exit(2);
 }
 
+static int is_expected_rev(const unsigned char *sha1)
+{
+	const char *filename = git_path("BISECT_EXPECTED_REV");
+	struct stat st;
+	struct strbuf str = STRBUF_INIT;
+	FILE *fp;
+	int res = 0;
+
+	if (stat(filename, &st) || !S_ISREG(st.st_mode))
+		return 0;
+
+	fp = fopen(filename, "r");
+	if (!fp)
+		return 0;
+
+	if (strbuf_getline(&str, fp, '\n') != EOF)
+		res = !strcmp(str.buf, sha1_to_hex(sha1));
+
+	strbuf_release(&str);
+	fclose(fp);
+
+	return res;
+}
+
 static void mark_expected_rev(char *bisect_rev_hex)
 {
 	int len = strlen(bisect_rev_hex);
@@ -620,6 +658,98 @@ static int bisect_checkout(char *bisect_rev_hex)
 	return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
 }
 
+static struct commit *get_commit_reference(const unsigned char *sha1)
+{
+	struct commit *r = lookup_commit_reference(sha1);
+	if (!r)
+		die("Not a valid commit name %s", sha1_to_hex(sha1));
+	return r;
+}
+
+static struct commit **get_bad_and_good_commits(int *rev_nr)
+{
+	int len = 1 + good_revs.sha1_nr;
+	struct commit **rev = xmalloc(len * sizeof(*rev));
+	int i, n = 0;
+
+	rev[n++] = get_commit_reference(current_bad_sha1);
+	for (i = 0; i < good_revs.sha1_nr; i++)
+		rev[n++] = get_commit_reference(good_revs.sha1[i]);
+	*rev_nr = n;
+
+	return rev;
+}
+
+static void handle_bad_merge_base(void)
+{
+	if (is_expected_rev(current_bad_sha1)) {
+		char *bad_hex = sha1_to_hex(current_bad_sha1);
+		char *good_hex = join_sha1_array_hex(&good_revs, ' ');
+
+		fprintf(stderr, "The merge base %s is bad.\n"
+			"This means the bug has been fixed "
+			"between %s and [%s].\n",
+			bad_hex, bad_hex, good_hex);
+
+		exit(3);
+	}
+
+	fprintf(stderr, "Some good revs are not ancestor of the bad rev.\n"
+		"git bisect cannot work properly in this case.\n"
+		"Maybe you mistake good and bad revs?\n");
+	exit(1);
+}
+
+void handle_skipped_merge_base(const unsigned char *mb)
+{
+	char *mb_hex = sha1_to_hex(mb);
+	char *bad_hex = sha1_to_hex(current_bad_sha1);
+	char *good_hex = join_sha1_array_hex(&good_revs, ' ');
+
+	fprintf(stderr, "Warning: the merge base between %s and [%s] "
+		"must be skipped.\n"
+		"So we cannot be sure the first bad commit is "
+		"between %s and %s.\n"
+		"We continue anyway.\n",
+		bad_hex, good_hex, mb_hex, bad_hex);
+	free(good_hex);
+}
+
+/*
+ * "check_merge_bases" checks that merge bases are not "bad".
+ *
+ * - If one is "bad", it means the user assumed something wrong
+ * and we must exit with a non 0 error code.
+ * - If one is "good", that's good, we have nothing to do.
+ * - If one is "skipped", we can't know but we should warn.
+ * - If we don't know, we should check it out and ask the user to test.
+ */
+static void check_merge_bases(void)
+{
+	struct commit_list *result;
+	int rev_nr;
+	struct commit **rev = get_bad_and_good_commits(&rev_nr);
+
+	result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1, 0);
+
+	for (; result; result = result->next) {
+		const unsigned char *mb = result->item->object.sha1;
+		if (!hashcmp(mb, current_bad_sha1)) {
+			handle_bad_merge_base();
+		} else if (0 <= lookup_sha1_array(&good_revs, mb)) {
+			continue;
+		} else if (0 <= lookup_sha1_array(&skipped_revs, mb)) {
+			handle_skipped_merge_base(mb);
+		} else {
+			printf("Bisecting: a merge base must be tested\n");
+			exit(bisect_checkout(sha1_to_hex(mb)));
+		}
+	}
+
+	free(rev);
+	free_commit_list(result);
+}
+
 /*
  * We use the convention that exiting with an exit code 10 means that
  * the bisection process finished successfully.
-- 
1.6.3.rc1.112.g17e25

[PATCH 09/10] bisect: add "check_good_are_ancestors_of_bad" function

[Christian Couder]

This is a port of the function with the same name that is in
"git-bisect.sh". The new function is not used yet but will be in
a later patch.

We also implement an helper "check_ancestors" function that use
"start_command" and "finish_command" to launch
"git rev-list $good ^$bad".

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 75 insertions(+), 0 deletions(-)

diff --git a/bisect.c b/bisect.c
index b24ee78..09102da 100644
--- a/bisect.c
+++ b/bisect.c
@@ -751,6 +751,81 @@ static void check_merge_bases(void)
 }
 
 /*
+ * This function runs the command "git rev-list $_good ^$_bad"
+ * and returns 1 if it produces some output, 0 otherwise.
+ */
+static int check_ancestors(void)
+{
+	struct argv_array rev_argv = { NULL, 0, 0 };
+	struct strbuf str = STRBUF_INIT;
+	int i, result = 0;
+	struct child_process rls;
+	FILE *rls_fout;
+
+	argv_array_push(&rev_argv, xstrdup("rev-list"));
+	argv_array_push_sha1(&rev_argv, current_bad_sha1, "^%s");
+	for (i = 0; i < good_revs.sha1_nr; i++)
+		argv_array_push_sha1(&rev_argv, good_revs.sha1[i], "%s");
+	argv_array_push(&rev_argv, NULL);
+
+	memset(&rls, 0, sizeof(rls));
+	rls.argv = rev_argv.argv;
+	rls.out = -1;
+	rls.git_cmd = 1;
+	if (start_command(&rls))
+		die("Could not launch 'git rev-list' command.");
+	rls_fout = fdopen(rls.out, "r");
+	while (strbuf_getline(&str, rls_fout, '\n') != EOF) {
+		strbuf_trim(&str);
+		if (*str.buf) {
+			result = 1;
+			break;
+		}
+	}
+	fclose(rls_fout);
+	finish_command(&rls);
+
+	return result;
+}
+
+/*
+ * "check_good_are_ancestors_of_bad" checks that all "good" revs are
+ * ancestor of the "bad" rev.
+ *
+ * If that's not the case, we need to check the merge bases.
+ * If a merge base must be tested by the user, its source code will be
+ * checked out to be tested by the user and we will exit.
+ */
+static void check_good_are_ancestors_of_bad(const char *prefix)
+{
+	const char *filename = git_path("BISECT_ANCESTORS_OK");
+	struct stat st;
+	int fd;
+
+	if (!current_bad_sha1)
+		die("a bad revision is needed");
+
+	/* Check if file BISECT_ANCESTORS_OK exists. */
+	if (!stat(filename, &st) && S_ISREG(st.st_mode))
+		return;
+
+	/* Bisecting with no good rev is ok. */
+	if (good_revs.sha1_nr == 0)
+		return;
+
+	if (check_ancestors())
+		check_merge_bases();
+
+	/* Create file BISECT_ANCESTORS_OK. */
+	fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
+	if (fd < 0)
+		warning("could not create file '%s': %s",
+			filename, strerror(errno));
+	else
+		close(fd);
+}
+
+/*
  * We use the convention that exiting with an exit code 10 means that
  * the bisection process finished successfully.
  * In this case the calling shell script should exit 0.
-- 
1.6.3.rc1.112.g17e25

[PATCH 10/10] bisect: make "git bisect" use new "--next-all" bisect-helper function

[Christian Couder]

This patch replace the "--next-exit" option of "git bisect--helper"
with a "--next-all" option that does merge base checking using
the "check_good_are_ancestors_of_bad" function implemented in
"bisect.c" in a former patch.

The new "--next-all" option is then used in "git-bisect.sh" instead
of the "--next-exit" option, and all the shell functions in
"git-bisect.sh" that are now unused are removed.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c                 |    4 +-
 bisect.h                 |    2 +-
 builtin-bisect--helper.c |   14 +++---
 git-bisect.sh            |  127 +---------------------------------------------
 4 files changed, 13 insertions(+), 134 deletions(-)

diff --git a/bisect.c b/bisect.c
index 09102da..f57b62c 100644
--- a/bisect.c
+++ b/bisect.c
@@ -830,7 +830,7 @@ static void check_good_are_ancestors_of_bad(const char *prefix)
  * the bisection process finished successfully.
  * In this case the calling shell script should exit 0.
  */
-int bisect_next_exit(const char *prefix)
+int bisect_next_all(const char *prefix)
 {
 	struct rev_info revs;
 	struct commit_list *tried;
@@ -841,6 +841,8 @@ int bisect_next_exit(const char *prefix)
 	if (read_bisect_refs())
 		die("reading bisect refs failed");
 
+	check_good_are_ancestors_of_bad(prefix);
+
 	bisect_rev_setup(&revs, prefix);
 
 	bisect_common(&revs, &reaches, &all);
diff --git a/bisect.h b/bisect.h
index 0b5d122..fb744fd 100644
--- a/bisect.h
+++ b/bisect.h
@@ -27,7 +27,7 @@ struct rev_list_info {
 
 extern int show_bisect_vars(struct rev_list_info *info, int reaches, int all);
 
-extern int bisect_next_exit(const char *prefix);
+extern int bisect_next_all(const char *prefix);
 
 extern int estimate_bisect_steps(int all);
 
diff --git a/builtin-bisect--helper.c b/builtin-bisect--helper.c
index aca7018..cb3e155 100644
--- a/builtin-bisect--helper.c
+++ b/builtin-bisect--helper.c
@@ -4,24 +4,24 @@
 #include "bisect.h"
 
 static const char * const git_bisect_helper_usage[] = {
-	"git bisect--helper --next-exit",
+	"git bisect--helper --next-all",
 	NULL
 };
 
 int cmd_bisect__helper(int argc, const char **argv, const char *prefix)
 {
-	int next_exit = 0;
+	int next_all = 0;
 	struct option options[] = {
-		OPT_BOOLEAN(0, "next-exit", &next_exit,
-			    "output bisect result and exit instuctions"),
+		OPT_BOOLEAN(0, "next-all", &next_all,
+			    "perform 'git bisect next'"),
 		OPT_END()
 	};
 
 	argc = parse_options(argc, argv, options, git_bisect_helper_usage, 0);
 
-	if (!next_exit)
+	if (!next_all)
 		usage_with_options(git_bisect_helper_usage, options);
 
-	/* next-exit */
-	return bisect_next_exit(prefix);
+	/* next-all */
+	return bisect_next_all(prefix);
 }
diff --git a/git-bisect.sh b/git-bisect.sh
index 786b7b9..8969553 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -167,10 +167,6 @@ is_expected_rev() {
 	test "$1" = $(cat "$GIT_DIR/BISECT_EXPECTED_REV")
 }
 
-mark_expected_rev() {
-	echo "$1" > "$GIT_DIR/BISECT_EXPECTED_REV"
-}
-
 check_expected_revs() {
 	for _rev in "$@"; do
 		if ! is_expected_rev "$_rev"; then
@@ -269,132 +265,13 @@ bisect_auto_next() {
 	bisect_next_check && bisect_next || :
 }
 
-bisect_checkout() {
-	_rev="$1"
-	_msg="$2"
-	echo "Bisecting: $_msg"
-	mark_expected_rev "$_rev"
-	git checkout -q "$_rev" -- || exit
-	git show-branch "$_rev"
-}
-
-is_among() {
-	_rev="$1"
-	_list="$2"
-	case "$_list" in *$_rev*) return 0 ;; esac
-	return 1
-}
-
-handle_bad_merge_base() {
-	_badmb="$1"
-	_good="$2"
-	if is_expected_rev "$_badmb"; then
-		cat >&2 <<EOF
-The merge base $_badmb is bad.
-This means the bug has been fixed between $_badmb and [$_good].
-EOF
-		exit 3
-	else
-		cat >&2 <<EOF
-Some good revs are not ancestor of the bad rev.
-git bisect cannot work properly in this case.
-Maybe you mistake good and bad revs?
-EOF
-		exit 1
-	fi
-}
-
-handle_skipped_merge_base() {
-	_mb="$1"
-	_bad="$2"
-	_good="$3"
-	cat >&2 <<EOF
-Warning: the merge base between $_bad and [$_good] must be skipped.
-So we cannot be sure the first bad commit is between $_mb and $_bad.
-We continue anyway.
-EOF
-}
-
-#
-# "check_merge_bases" checks that merge bases are not "bad".
-#
-# - If one is "good", that's good, we have nothing to do.
-# - If one is "bad", it means the user assumed something wrong
-# and we must exit.
-# - If one is "skipped", we can't know but we should warn.
-# - If we don't know, we should check it out and ask the user to test.
-#
-# In the last case we will return 1, and otherwise 0.
-#
-check_merge_bases() {
-	_bad="$1"
-	_good="$2"
-	_skip="$3"
-	for _mb in $(git merge-base --all $_bad $_good)
-	do
-		if is_among "$_mb" "$_good"; then
-			continue
-		elif test "$_mb" = "$_bad"; then
-			handle_bad_merge_base "$_bad" "$_good"
-		elif is_among "$_mb" "$_skip"; then
-			handle_skipped_merge_base "$_mb" "$_bad" "$_good"
-		else
-			bisect_checkout "$_mb" "a merge base must be tested"
-			return 1
-		fi
-	done
-	return 0
-}
-
-#
-# "check_good_are_ancestors_of_bad" checks that all "good" revs are
-# ancestor of the "bad" rev.
-#
-# If that's not the case, we need to check the merge bases.
-# If a merge base must be tested by the user we return 1 and
-# otherwise 0.
-#
-check_good_are_ancestors_of_bad() {
-	test -f "$GIT_DIR/BISECT_ANCESTORS_OK" &&
-		return
-
-	_bad="$1"
-	_good=$(echo $2 | sed -e 's/\^//g')
-	_skip="$3"
-
-	# Bisecting with no good rev is ok
-	test -z "$_good" && return
-
-	_side=$(git rev-list $_good ^$_bad)
-	if test -n "$_side"; then
-		# Return if a checkout was done
-		check_merge_bases "$_bad" "$_good" "$_skip" || return
-	fi
-
-	: > "$GIT_DIR/BISECT_ANCESTORS_OK"
-
-	return 0
-}
-
 bisect_next() {
 	case "$#" in 0) ;; *) usage ;; esac
 	bisect_autostart
 	bisect_next_check good
 
-	# Get bad, good and skipped revs
-	bad=$(git rev-parse --verify refs/bisect/bad) &&
-	good=$(git for-each-ref --format='^%(objectname)' \
-		"refs/bisect/good-*" | tr '\012' ' ') &&
-	skip=$(git for-each-ref --format='%(objectname)' \
-		"refs/bisect/skip-*" | tr '\012' ' ') || exit
-
-	# Maybe some merge bases must be tested first
-	check_good_are_ancestors_of_bad "$bad" "$good" "$skip"
-	# Return now if a checkout has already been done
-	test "$?" -eq "1" && return
-
-	# Perform bisection computation, display and checkout
-	git bisect--helper --next-exit
+	# Perform all bisection computation, display and checkout
+	git bisect--helper --next-all
 	res=$?
 
         # Check if we should exit because bisection is finished
-- 
1.6.3.rc1.112.g17e25

Re: [PATCH 07/10] bisect: automatically sort sha1_array if needed when looking it up

[Jakub Narebski]

Christian Couder <chriscool@tuxfamily.org> writes:

> This makes sha1_array easier to use, so later patches will be simpler.

Hmmm... sort on lookup array. I wonder if it would be worth
librarizing, and if there is any smart optimization for that (like
e.g. heap for fast access to smallest value and fast insertion, using
insertion sort for almost sorted array, etc.).

BTW. does it become unsorted anywhere?

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [PATCH 07/10] bisect: automatically sort sha1_array if needed when looking it up

[Christian Couder]

Le samedi 9 mai 2009, Jakub Narebski a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
> > This makes sha1_array easier to use, so later patches will be simpler.
>
> Hmmm... sort on lookup array. I wonder if it would be worth
> librarizing, and if there is any smart optimization for that (like
> e.g. heap for fast access to smallest value and fast insertion, using
> insertion sort for almost sorted array, etc.).
>
> BTW. does it become unsorted anywhere?

No, it doesn't. We first read all the "refs/bisect/good-*" 
and "refs/bisect/skip-*" and put them in some "struct sha1_array".
Then later we may lookup sha1 there from 2 different functions:
"check_merge_bases" first and then "filter_skipped".

This patch optimizes by not sorting before we lookup, so if we don't lookup 
anything, we pay no sorting price.

Best regards,
Christian.

Re: [PATCH 10/10] bisect: make "git bisect" use new "--next-all" bisect-helper function

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> This patch replace the "--next-exit" option of "git bisect--helper"
> with a "--next-all" option that does merge base checking using
> the "check_good_are_ancestors_of_bad" function implemented in
> "bisect.c" in a former patch.
>
> The new "--next-all" option is then used in "git-bisect.sh" instead
> of the "--next-exit" option, and all the shell functions in
> "git-bisect.sh" that are now unused are removed.
>
> Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
> ---
>  bisect.c                 |    4 +-
>  bisect.h                 |    2 +-
>  builtin-bisect--helper.c |   14 +++---
>  git-bisect.sh            |  127 +---------------------------------------------
>  4 files changed, 13 insertions(+), 134 deletions(-)

Nice.

All patches looked sensible; will queue.

Thanks.