which enable recursive bad-branch-first algorithm for git-bisect.
With this algorithm, git-bisect will always try to select commits
that on the same branch current bad commit sits. And will fall back
to default git-bisect algorithm when bad-branch-first algorithm does
not apply
Signed-off-by: Shuang He <shuang.he@xxxxxxxxx>
---
Documentation/config.txt | 8 ++
bisect.c | 244 +++++++++++++++++++++++++++++++++++++++++-----
bisect.h | 2 +-
builtin/rev-list.c | 2 +-
cache.h | 1 +
config.c | 6 +
environment.c | 1 +
7 files changed, 238 insertions(+), 26 deletions(-)
diff --git a/Documentation/config.txt b/Documentation/config.txt
index ff7c225..8502859 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -558,6 +558,14 @@ core.sparseCheckout::
Enable "sparse checkout" feature. See section "Sparse checkout" in
linkgit:git-read-tree[1] for more information.
+core.bisectbadbranchfirst::
+ With this algorithm, git-bisect will always try to select commits
+ that on the same branch current bad commit sits. And will fall back
+ to default git-bisect algorithm when bad-branch-first algorithm does
+ not apply
++
+This setting defaults to "false".
+
add.ignore-errors::
add.ignoreErrors::
Tells 'git add' to continue adding files when some files cannot be
diff --git a/bisect.c b/bisect.c
index 060c042..57c410d 100644
--- a/bisect.c
+++ b/bisect.c
@@ -189,6 +189,46 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)
return best;
}
+static struct commit_list *best_bisection_first_parent(struct commit_list *list, struct commit_list *list2, int nr)
+{
+ struct commit_list *p, *best;
+ struct commit_list *p2;
+ int best_distance = -1;
+
+ best = NULL;
+ for (p2 = list2; p2; p2 = p2->next) {
+ int distance;
+ int on_branch;
+
+ on_branch = 0;
+ for (p = list; p; p = p->next) {
+ unsigned flags = p->item->object.flags;
+ if (flags & TREESAME)
+ continue;
+ if (!hashcmp(p->item->object.sha1, p2->item->object.sha1)) {
+ on_branch = 1;
+ break;
+ }
+ }
+
+ if (!on_branch)
+ continue;
+
+ weight_set(p2, weight(p));
+ distance = weight(p);
+ if (nr - distance < distance)
+ distance = nr - distance;
+ if (distance > best_distance) {
+ best = p;
+ best_distance = distance;
+ }
+
+ }
+
+ return list2;
+}
+
+
struct commit_dist {
struct commit *commit;
int distance;
@@ -253,7 +293,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
* unknown. After running count_distance() first, they will get zero
* or positive distance.
*/
-static struct commit_list *do_find_bisection(struct commit_list *list,
+static struct commit_list *do_find_bisection(struct commit_list *list, struct commit_list *list2,
int nr, int *weights,
int find_all)
{
@@ -314,7 +354,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
clear_distance(list);
/* Does it happen to be at exactly half-way? */
- if (!find_all && halfway(p, nr))
+ if (!list2 && !find_all && halfway(p, nr))
return p;
counted++;
}
@@ -352,20 +392,27 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
weight_set(p, weight(q));
/* Does it happen to be at exactly half-way? */
- if (!find_all && halfway(p, nr))
+ if (!list2 && !find_all && halfway(p, nr))
return p;
}
}
show_list("bisection 2 counted all", counted, nr, list);
+ if (list2) {
+ struct commit_list *t;
+ t = best_bisection_first_parent(list, list2, nr);
+ t = best_bisection_sorted(t, nr);
+ return t;
+ }
+
if (!find_all)
return best_bisection(list, nr);
else
return best_bisection_sorted(list, nr);
}
-struct commit_list *find_bisection(struct commit_list *list,
+struct commit_list *find_bisection(struct commit_list *list, struct commit_list *list2,
int *reaches, int *all,
int find_all)
{
@@ -400,7 +447,7 @@ struct commit_list *find_bisection(struct commit_list *list,
weights = xcalloc(on_list, sizeof(*weights));
/* Do the real work of finding bisection commit. */
- best = do_find_bisection(list, nr, weights, find_all);
+ best = do_find_bisection(list, list2, nr, weights, find_all);
if (best) {
if (!find_all)
best->next = NULL;
@@ -683,6 +730,33 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
setup_revisions(rev_argv.argv_nr, rev_argv.argv, revs, NULL);
}
+static void bisect_rev_setup_first_parent(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;
+
+ init_revisions(revs, prefix);
+ revs->abbrev = 0;
+ revs->commit_format = CMIT_FMT_UNSPECIFIED;
+
+ /* rev_argv.argv[0] will be ignored by setup_revisions */
+ argv_array_push(&rev_argv, xstrdup("bisect_rev_setup_first_parent"));
+ 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],
+ good_format);
+ argv_array_push(&rev_argv, xstrdup("--first-parent"));
+ argv_array_push(&rev_argv, xstrdup("--"));
+ 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);
+}
+
+
static void bisect_common(struct rev_info *revs)
{
if (prepare_revision_walk(revs))
@@ -944,6 +1018,24 @@ static void show_diff_tree(const char *prefix, struct commit *commit)
log_tree_commit(&opt, commit);
}
+int is_merge_commit(struct commit_list *entry) {
+ int nr = 0;
+ struct commit *commit;
+ struct commit_list *p;
+
+ if (entry) {
+ p = entry->item->parents;
+
+ while (p) {
+ nr += 1;
+ p = p->next;
+ }
+ }
+
+ return nr - 1;
+}
+
+
/*
* We use the convention that exiting with an exit code 10 means that
* the bisection process finished successfully.
@@ -952,41 +1044,145 @@ static void show_diff_tree(const char *prefix, struct commit *commit)
int bisect_next_all(const char *prefix)
{
struct rev_info revs;
+ struct rev_info first_parent_revs;
struct commit_list *tried;
int reaches = 0, all = 0, nr, steps;
+ struct object_array pending_copy;
+ struct object_array pending_copy2;
const unsigned char *bisect_rev;
+ int i;
char bisect_rev_hex[41];
+ int bad_branch_first_working = 1;
if (read_bisect_refs())
die("reading bisect refs failed");
check_good_are_ancestors_of_bad(prefix);
+ struct argv_array rev_argv = { NULL, 0, 0 };
+
+ read_bisect_paths(&rev_argv);
+ if (rev_argv.argv_nr > 0)
+ core_bisect_bad_branch_first = 0;
+
+ if (core_bisect_bad_branch_first) {
+ bisect_rev_setup_first_parent(&first_parent_revs, prefix, "%s", "^%s", 1);
+ memset(&pending_copy, 0, sizeof(pending_copy));
+ for (i = 0; i < first_parent_revs.pending.nr; i++)
+ add_object_array(first_parent_revs.pending.objects[i].item,
+ first_parent_revs.pending.objects[i].name,
+ &pending_copy);
+
+ bisect_common(&first_parent_revs);
+
+ /* 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);
+ }
+ }
- bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
- revs.limited = 1;
- bisect_common(&revs);
- revs.commits = find_bisection(revs.commits, &reaches, &all,
- !!skipped_revs.sha1_nr);
- revs.commits = managed_skipped(revs.commits, &tried);
+ if (core_bisect_bad_branch_first) {
+ bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
+ memset(&pending_copy2, 0, sizeof(pending_copy2));
+ for (i = 0; i < revs.pending.nr; i++)
+ add_object_array(revs.pending.objects[i].item,
+ revs.pending.objects[i].name,
+ &pending_copy2);
+
+ revs.limited = 1;
+
+ bisect_common(&revs);
+
+ revs.commits = find_bisection(revs.commits, first_parent_revs.commits, &reaches, &all,
+ !!skipped_revs.sha1_nr);
+ /* TODO: Check if this is a first bad commit on bad branch, and if it's a merge commit */
+ /* If this is a merge commit, we need to try all of its parents, until we found the merged bad branch */
+ /* If all parents are good, we just announce it as first bad commit */
+ if (!hashcmp(revs.commits->item->object.sha1, current_bad_sha1)) {
+ printf("%s is the first bad commit\n", sha1_to_hex(current_bad_sha1));
+
+ if (is_merge_commit(revs.commits)) {
+ int all_parents_good = 1;
+ struct commit_list *p;
+
+ printf("%s is a merge commit\n", sha1_to_hex(current_bad_sha1));
+ printf("need to try each merged branch\n", sha1_to_hex(current_bad_sha1));
+ p = revs.commits->item->parents;
+
+ while (p) {
+ if (!hashcmp(p->item->object.sha1, current_bad_sha1)) {
+ fprintf(stderr, "should not get here\n");
+ exit(1);
+ } else if (0 <= lookup_sha1_array(&good_revs, p->item->object.sha1)) {
+ fprintf(stderr, "good parent %s\n", sha1_to_hex(p->item->object.sha1));
+ } else if (0 <= lookup_sha1_array(&skipped_revs, p->item->object.sha1)) {
+ fprintf(stderr, "skipped parent %s\n", sha1_to_hex(p->item->object.sha1));
+ all_parents_good = 0;
+ } else {
+ printf("try merged branch %s\n", sha1_to_hex(p->item->object.sha1));
+ exit(bisect_checkout(sha1_to_hex(p->item->object.sha1)));
+ }
+ p = p->next;
+ }
+
+ if (all_parents_good) {
+ show_diff_tree(prefix, revs.commits->item);
+ exit(10);
+ }
+ }
+ else {
+ show_diff_tree(prefix, revs.commits->item);
+ exit(10);
+ }
+ }
+
+ revs.commits = managed_skipped(revs.commits, &tried);
- if (!revs.commits) {
- /*
- * We should exit here only if the "bad"
- * commit is also a "skip" commit.
- */
- exit_if_skipped_commits(tried, NULL);
+ if (!revs.commits || !all) {
+ bad_branch_first_working = 0;
+ fprintf(stderr, "fall back to default git-bisect algorithm\n");
+ }
+ else
+ fprintf(stderr, "proceed with core_bisect_bad_branch_first algorithm\n");
- printf("%s was both good and bad\n",
- sha1_to_hex(current_bad_sha1));
- exit(1);
+ /* Clean up objects used, as they will be reused. */
+ for (i = 0; i < pending_copy2.nr; i++) {
+ struct object *o = pending_copy2.objects[i].item;
+ clear_commit_marks((struct commit *)o, ALL_REV_FLAGS);
+ }
}
- if (!all) {
- fprintf(stderr, "No testable commit found.\n"
- "Maybe you started with bad path parameters?\n");
- exit(4);
+
+ if (!core_bisect_bad_branch_first || !bad_branch_first_working) {
+ bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
+ revs.limited = 1;
+
+ bisect_common(&revs);
+ show_list("fall back", 0, 0, revs.commits);
+
+ revs.commits = find_bisection(revs.commits, NULL, &reaches, &all,
+ !!skipped_revs.sha1_nr);
+ revs.commits = managed_skipped(revs.commits, &tried);
+
+ if (!revs.commits) {
+ /*
+ * We should exit here only if the "bad"
+ * commit is also a "skip" commit.
+ */
+ exit_if_skipped_commits(tried, NULL);
+
+ printf("%s was both good and bad\n",
+ sha1_to_hex(current_bad_sha1));
+ exit(1);
+ }
+
+ if (!all) {
+ fprintf(stderr, "No testable commit found.\n"
+ "Maybe you started with bad path parameters?\n");
+ exit(4);
+ }
}
bisect_rev = revs.commits->item->object.sha1;
diff --git a/bisect.h b/bisect.h
index 0862ce5..fad4fbe 100644
--- a/bisect.h
+++ b/bisect.h
@@ -1,7 +1,7 @@
#ifndef BISECT_H
#define BISECT_H
-extern struct commit_list *find_bisection(struct commit_list *list,
+extern struct commit_list *find_bisection(struct commit_list *list, struct commit_list *list2,
int *reaches, int *all,
int find_all);
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index ba27d39..ab56f6b 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -399,7 +399,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
if (bisect_list) {
int reaches = reaches, all = all;
- revs.commits = find_bisection(revs.commits, &reaches, &all,
+ revs.commits = find_bisection(revs.commits, NULL, &reaches, &all,
bisect_find_all);
if (bisect_show_vars)
diff --git a/cache.h b/cache.h
index d83d68c..bfd4448 100644
--- a/cache.h
+++ b/cache.h
@@ -559,6 +559,7 @@ extern int read_replace_refs;
extern int fsync_object_files;
extern int core_preload_index;
extern int core_apply_sparse_checkout;
+extern int core_bisect_bad_branch_first;
enum safe_crlf {
SAFE_CRLF_FALSE = 0,
diff --git a/config.c b/config.c
index 625e051..b37a70c 100644
--- a/config.c
+++ b/config.c
@@ -660,6 +660,12 @@ static int git_default_core_config(const char *var, const char *value)
return 0;
}
+ if (!strcmp(var, "core.bisectbadbranchfirst")) {
+ core_bisect_bad_branch_first = git_config_bool(var, value);
+ return 0;
+ }
+
+
/* Add other config variables here and to Documentation/config.txt. */
return 0;
}
diff --git a/environment.c b/environment.c
index 9564475..cf813af 100644
--- a/environment.c
+++ b/environment.c
@@ -55,6 +55,7 @@ enum object_creation_mode object_creation_mode = OBJECT_CREATION_MODE;
char *notes_ref_name;
int grafts_replace_parents = 1;
int core_apply_sparse_checkout;
+int core_bisect_bad_branch_first = 0;
struct startup_info *startup_info;
/* Parallel index stat data preload? */
--
1.7.4.rc2.21.g7f7a8
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html