X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=bisect.c;h=52220df751aaacec08792c01ad83f2a1b27aae5f;hb=444f29ce42a6de8e29a05f892f9ce5215cd38d56;hp=f57b62cdddb7ff96acaabdee6e4bfc551d8a195f;hpb=212fa1d96040a01054d6bd92ee2bb74fe7071d33;p=git.git

diff --git a/bisect.c b/bisect.c
index f57b62cdd..52220df75 100644
--- a/bisect.c
+++ b/bisect.c
@@ -7,6 +7,7 @@
 #include "quote.h"
 #include "sha1-lookup.h"
 #include "run-command.h"
+#include "log-tree.h"
 #include "bisect.h"
 
 struct sha1_array {
@@ -27,7 +28,6 @@ struct argv_array {
 	int argv_alloc;
 };
 
-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};
 
@@ -454,7 +454,7 @@ static int read_bisect_refs(void)
 	return for_each_ref_in("refs/bisect/", register_ref, NULL);
 }
 
-void read_bisect_paths(struct argv_array *array)
+static void read_bisect_paths(struct argv_array *array)
 {
 	struct strbuf str = STRBUF_INIT;
 	const char *filename = git_path("BISECT_NAMES");
@@ -521,14 +521,34 @@ static char *join_sha1_array_hex(struct sha1_array *array, char delim)
 	return strbuf_detach(&joined_hexs, NULL);
 }
 
+/*
+ * In this function, passing a not NULL skipped_first is very special.
+ * It means that we want to know if the first commit in the list is
+ * skipped because we will want to test a commit away from it if it is
+ * indeed skipped.
+ * So if the first commit is skipped, we cannot take the shortcut to
+ * just "return list" when we find the first non skipped commit, we
+ * have to return a fully filtered list.
+ *
+ * We use (*skipped_first == -1) to mean "it has been found that the
+ * first commit is not skipped". In this case *skipped_first is set back
+ * to 0 just before the function returns.
+ */
 struct commit_list *filter_skipped(struct commit_list *list,
 				   struct commit_list **tried,
-				   int show_all)
+				   int show_all,
+				   int *count,
+				   int *skipped_first)
 {
 	struct commit_list *filtered = NULL, **f = &filtered;
 
 	*tried = NULL;
 
+	if (skipped_first)
+		*skipped_first = 0;
+	if (count)
+		*count = 0;
+
 	if (!skipped_revs.sha1_nr)
 		return list;
 
@@ -537,23 +557,113 @@ struct commit_list *filter_skipped(struct commit_list *list,
 		list->next = NULL;
 		if (0 <= lookup_sha1_array(&skipped_revs,
 					   list->item->object.sha1)) {
+			if (skipped_first && !*skipped_first)
+				*skipped_first = 1;
 			/* Move current to tried list */
 			*tried = list;
 			tried = &list->next;
 		} else {
-			if (!show_all)
-				return list;
+			if (!show_all) {
+				if (!skipped_first || !*skipped_first)
+					return list;
+			} else if (skipped_first && !*skipped_first) {
+				/* This means we know it's not skipped */
+				*skipped_first = -1;
+			}
 			/* Move current to filtered list */
 			*f = list;
 			f = &list->next;
+			if (count)
+				(*count)++;
 		}
 		list = next;
 	}
 
+	if (skipped_first && *skipped_first == -1)
+		*skipped_first = 0;
+
 	return filtered;
 }
 
-static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
+#define PRN_MODULO 32768
+
+/*
+ * This is a pseudo random number generator based on "man 3 rand".
+ * It is not used properly because the seed is the argument and it
+ * is increased by one between each call, but that should not matter
+ * for this application.
+ */
+int get_prn(int count) {
+	count = count * 1103515245 + 12345;
+	return ((unsigned)(count/65536) % PRN_MODULO);
+}
+
+/*
+ * Custom integer square root from
+ * http://en.wikipedia.org/wiki/Integer_square_root
+ */
+static int sqrti(int val)
+{
+	float d, x = val;
+
+	if (val == 0)
+		return 0;
+
+	do {
+		float y = (x + (float)val / x) / 2;
+		d = (y > x) ? y - x : x - y;
+		x = y;
+	} while (d >= 0.5);
+
+	return (int)x;
+}
+
+static struct commit_list *skip_away(struct commit_list *list, int count)
+{
+	struct commit_list *cur, *previous;
+	int prn, index, i;
+
+	prn = get_prn(count);
+	index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
+
+	cur = list;
+	previous = NULL;
+
+	for (i = 0; cur; cur = cur->next, i++) {
+		if (i == index) {
+			if (hashcmp(cur->item->object.sha1, current_bad_sha1))
+				return cur;
+			if (previous)
+				return previous;
+			return list;
+		}
+		previous = cur;
+	}
+
+	return list;
+}
+
+static struct commit_list *managed_skipped(struct commit_list *list,
+					   struct commit_list **tried)
+{
+	int count, skipped_first;
+
+	*tried = NULL;
+
+	if (!skipped_revs.sha1_nr)
+		return list;
+
+	list = filter_skipped(list, tried, 0, &count, &skipped_first);
+
+	if (!skipped_first)
+		return list;
+
+	return skip_away(list, count);
+}
+
+static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
+			     const char *bad_format, const char *good_format,
+			     int read_paths)
 {
 	struct argv_array rev_argv = { NULL, 0, 0 };
 	int i;
@@ -564,26 +674,24 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
 
 	/* 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");
+	argv_array_push_sha1(&rev_argv, current_bad_sha1, bad_format);
 	for (i = 0; i < good_revs.sha1_nr; i++)
-		argv_array_push_sha1(&rev_argv, good_revs.sha1[i], "^%s");
+		argv_array_push_sha1(&rev_argv, good_revs.sha1[i],
+				     good_format);
 	argv_array_push(&rev_argv, xstrdup("--"));
-	read_bisect_paths(&rev_argv);
+	if (read_paths)
+		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;
 }
 
-static void bisect_common(struct rev_info *revs, int *reaches, int *all)
+static void bisect_common(struct rev_info *revs)
 {
 	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_revs.sha1_nr);
 }
 
 static void exit_if_skipped_commits(struct commit_list *tried,
@@ -700,7 +808,7 @@ static void handle_bad_merge_base(void)
 	exit(1);
 }
 
-void handle_skipped_merge_base(const unsigned char *mb)
+static 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);
@@ -750,42 +858,31 @@ static void check_merge_bases(void)
 	free_commit_list(result);
 }
 
-/*
- * 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)
+static int check_ancestors(const char *prefix)
 {
-	struct argv_array rev_argv = { NULL, 0, 0 };
-	struct strbuf str = STRBUF_INIT;
-	int i, result = 0;
-	struct child_process rls;
-	FILE *rls_fout;
+	struct rev_info revs;
+	struct object_array pending_copy;
+	int i, res;
 
-	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);
+	bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
 
-	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;
-		}
+	/* Save pending objects, so they can be cleaned up later. */
+	memset(&pending_copy, 0, sizeof(pending_copy));
+	for (i = 0; i < revs.pending.nr; i++)
+		add_object_array(revs.pending.objects[i].item,
+				 revs.pending.objects[i].name,
+				 &pending_copy);
+
+	bisect_common(&revs);
+	res = (revs.commits != NULL);
+
+	/* Clean up objects used, as they will be reused. */
+	for (i = 0; i < pending_copy.nr; i++) {
+		struct object *o = pending_copy.objects[i].item;
+		clear_commit_marks((struct commit *)o, ALL_REV_FLAGS);
 	}
-	fclose(rls_fout);
-	finish_command(&rls);
 
-	return result;
+	return res;
 }
 
 /*
@@ -813,7 +910,8 @@ static void check_good_are_ancestors_of_bad(const char *prefix)
 	if (good_revs.sha1_nr == 0)
 		return;
 
-	if (check_ancestors())
+	/* Check if all good revs are ancestor of the bad rev. */
+	if (check_ancestors(prefix))
 		check_merge_bases();
 
 	/* Create file BISECT_ANCESTORS_OK. */
@@ -825,6 +923,31 @@ static void check_good_are_ancestors_of_bad(const char *prefix)
 		close(fd);
 }
 
+/*
+ * This does "git diff-tree --pretty COMMIT" without one fork+exec.
+ */
+static void show_diff_tree(const char *prefix, struct commit *commit)
+{
+	struct rev_info opt;
+
+	/* diff-tree init */
+	init_revisions(&opt, prefix);
+	git_config(git_diff_basic_config, NULL); /* no "diff" UI options */
+	opt.abbrev = 0;
+	opt.diff = 1;
+
+	/* This is what "--pretty" does */
+	opt.verbose_header = 1;
+	opt.use_terminator = 0;
+	opt.commit_format = CMIT_FMT_DEFAULT;
+
+	/* diff-tree init */
+	if (!opt.diffopt.output_format)
+		opt.diffopt.output_format = DIFF_FORMAT_RAW;
+
+	log_tree_commit(&opt, commit);
+}
+
 /*
  * We use the convention that exiting with an exit code 10 means that
  * the bisection process finished successfully.
@@ -843,11 +966,14 @@ int bisect_next_all(const char *prefix)
 
 	check_good_are_ancestors_of_bad(prefix);
 
-	bisect_rev_setup(&revs, prefix);
+	bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
+	revs.limited = 1;
 
-	bisect_common(&revs, &reaches, &all);
+	bisect_common(&revs);
 
-	revs.commits = filter_skipped(revs.commits, &tried, 0);
+	revs.commits = find_bisection(revs.commits, &reaches, &all,
+				       !!skipped_revs.sha1_nr);
+	revs.commits = managed_skipped(revs.commits, &tried);
 
 	if (!revs.commits) {
 		/*
@@ -867,8 +993,7 @@ int bisect_next_all(const char *prefix)
 	if (!hashcmp(bisect_rev, current_bad_sha1)) {
 		exit_if_skipped_commits(tried, current_bad_sha1);
 		printf("%s is first bad commit\n", bisect_rev_hex);
-		argv_diff_tree[2] = bisect_rev_hex;
-		run_command_v_opt(argv_diff_tree, RUN_GIT_CMD);
+		show_diff_tree(prefix, revs.commits->item);
 		/* This means the bisection process succeeded. */
 		exit(10);
 	}