diff options
Diffstat (limited to 'bisect.c')
| -rw-r--r-- | bisect.c | 152 |
1 files changed, 142 insertions, 10 deletions
@@ -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,22 +557,110 @@ 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; } +#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) @@ -699,7 +807,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); @@ -770,7 +878,7 @@ static int check_ancestors(const char *prefix) /* 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; - unparse_commit((struct commit *)o); + clear_commit_marks((struct commit *)o, ALL_REV_FLAGS); } return res; @@ -815,6 +923,31 @@ static void check_good_are_ancestors_of_bad(const char *prefix) } /* + * 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. * In this case the calling shell script should exit 0. @@ -839,7 +972,7 @@ int bisect_next_all(const char *prefix) revs.commits = find_bisection(revs.commits, &reaches, &all, !!skipped_revs.sha1_nr); - revs.commits = filter_skipped(revs.commits, &tried, 0); + revs.commits = managed_skipped(revs.commits, &tried); if (!revs.commits) { /* @@ -859,8 +992,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); } |