Merge branch 'cb/maint-orphan-merge-noclobber'
[git/kirr.git] / bisect.c
blob060c042f8bcc2d402cb9908be3bdbd3bb180a862
1 #include "cache.h"
2 #include "commit.h"
3 #include "diff.h"
4 #include "revision.h"
5 #include "refs.h"
6 #include "list-objects.h"
7 #include "quote.h"
8 #include "sha1-lookup.h"
9 #include "run-command.h"
10 #include "log-tree.h"
11 #include "bisect.h"
13 struct sha1_array {
14 unsigned char (*sha1)[20];
15 int sha1_nr;
16 int sha1_alloc;
17 int sorted;
20 static struct sha1_array good_revs;
21 static struct sha1_array skipped_revs;
23 static const unsigned char *current_bad_sha1;
25 struct argv_array {
26 const char **argv;
27 int argv_nr;
28 int argv_alloc;
31 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
32 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
34 /* bits #0-15 in revision.h */
36 #define COUNTED (1u<<16)
39 * This is a truly stupid algorithm, but it's only
40 * used for bisection, and we just don't care enough.
42 * We care just barely enough to avoid recursing for
43 * non-merge entries.
45 static int count_distance(struct commit_list *entry)
47 int nr = 0;
49 while (entry) {
50 struct commit *commit = entry->item;
51 struct commit_list *p;
53 if (commit->object.flags & (UNINTERESTING | COUNTED))
54 break;
55 if (!(commit->object.flags & TREESAME))
56 nr++;
57 commit->object.flags |= COUNTED;
58 p = commit->parents;
59 entry = p;
60 if (p) {
61 p = p->next;
62 while (p) {
63 nr += count_distance(p);
64 p = p->next;
69 return nr;
72 static void clear_distance(struct commit_list *list)
74 while (list) {
75 struct commit *commit = list->item;
76 commit->object.flags &= ~COUNTED;
77 list = list->next;
81 #define DEBUG_BISECT 0
83 static inline int weight(struct commit_list *elem)
85 return *((int*)(elem->item->util));
88 static inline void weight_set(struct commit_list *elem, int weight)
90 *((int*)(elem->item->util)) = weight;
93 static int count_interesting_parents(struct commit *commit)
95 struct commit_list *p;
96 int count;
98 for (count = 0, p = commit->parents; p; p = p->next) {
99 if (p->item->object.flags & UNINTERESTING)
100 continue;
101 count++;
103 return count;
106 static inline int halfway(struct commit_list *p, int nr)
109 * Don't short-cut something we are not going to return!
111 if (p->item->object.flags & TREESAME)
112 return 0;
113 if (DEBUG_BISECT)
114 return 0;
116 * 2 and 3 are halfway of 5.
117 * 3 is halfway of 6 but 2 and 4 are not.
119 switch (2 * weight(p) - nr) {
120 case -1: case 0: case 1:
121 return 1;
122 default:
123 return 0;
127 #if !DEBUG_BISECT
128 #define show_list(a,b,c,d) do { ; } while (0)
129 #else
130 static void show_list(const char *debug, int counted, int nr,
131 struct commit_list *list)
133 struct commit_list *p;
135 fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
137 for (p = list; p; p = p->next) {
138 struct commit_list *pp;
139 struct commit *commit = p->item;
140 unsigned flags = commit->object.flags;
141 enum object_type type;
142 unsigned long size;
143 char *buf = read_sha1_file(commit->object.sha1, &type, &size);
144 const char *subject_start;
145 int subject_len;
147 fprintf(stderr, "%c%c%c ",
148 (flags & TREESAME) ? ' ' : 'T',
149 (flags & UNINTERESTING) ? 'U' : ' ',
150 (flags & COUNTED) ? 'C' : ' ');
151 if (commit->util)
152 fprintf(stderr, "%3d", weight(p));
153 else
154 fprintf(stderr, "---");
155 fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
156 for (pp = commit->parents; pp; pp = pp->next)
157 fprintf(stderr, " %.*s", 8,
158 sha1_to_hex(pp->item->object.sha1));
160 subject_len = find_commit_subject(buf, &subject_start);
161 if (subject_len)
162 fprintf(stderr, " %.*s", subject_len, subject_start);
163 fprintf(stderr, "\n");
166 #endif /* DEBUG_BISECT */
168 static struct commit_list *best_bisection(struct commit_list *list, int nr)
170 struct commit_list *p, *best;
171 int best_distance = -1;
173 best = list;
174 for (p = list; p; p = p->next) {
175 int distance;
176 unsigned flags = p->item->object.flags;
178 if (flags & TREESAME)
179 continue;
180 distance = weight(p);
181 if (nr - distance < distance)
182 distance = nr - distance;
183 if (distance > best_distance) {
184 best = p;
185 best_distance = distance;
189 return best;
192 struct commit_dist {
193 struct commit *commit;
194 int distance;
197 static int compare_commit_dist(const void *a_, const void *b_)
199 struct commit_dist *a, *b;
201 a = (struct commit_dist *)a_;
202 b = (struct commit_dist *)b_;
203 if (a->distance != b->distance)
204 return b->distance - a->distance; /* desc sort */
205 return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
208 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
210 struct commit_list *p;
211 struct commit_dist *array = xcalloc(nr, sizeof(*array));
212 int cnt, i;
214 for (p = list, cnt = 0; p; p = p->next) {
215 int distance;
216 unsigned flags = p->item->object.flags;
218 if (flags & TREESAME)
219 continue;
220 distance = weight(p);
221 if (nr - distance < distance)
222 distance = nr - distance;
223 array[cnt].commit = p->item;
224 array[cnt].distance = distance;
225 cnt++;
227 qsort(array, cnt, sizeof(*array), compare_commit_dist);
228 for (p = list, i = 0; i < cnt; i++) {
229 struct name_decoration *r = xmalloc(sizeof(*r) + 100);
230 struct object *obj = &(array[i].commit->object);
232 sprintf(r->name, "dist=%d", array[i].distance);
233 r->next = add_decoration(&name_decoration, obj, r);
234 p->item = array[i].commit;
235 p = p->next;
237 if (p)
238 p->next = NULL;
239 free(array);
240 return list;
244 * zero or positive weight is the number of interesting commits it can
245 * reach, including itself. Especially, weight = 0 means it does not
246 * reach any tree-changing commits (e.g. just above uninteresting one
247 * but traversal is with pathspec).
249 * weight = -1 means it has one parent and its distance is yet to
250 * be computed.
252 * weight = -2 means it has more than one parent and its distance is
253 * unknown. After running count_distance() first, they will get zero
254 * or positive distance.
256 static struct commit_list *do_find_bisection(struct commit_list *list,
257 int nr, int *weights,
258 int find_all)
260 int n, counted;
261 struct commit_list *p;
263 counted = 0;
265 for (n = 0, p = list; p; p = p->next) {
266 struct commit *commit = p->item;
267 unsigned flags = commit->object.flags;
269 p->item->util = &weights[n++];
270 switch (count_interesting_parents(commit)) {
271 case 0:
272 if (!(flags & TREESAME)) {
273 weight_set(p, 1);
274 counted++;
275 show_list("bisection 2 count one",
276 counted, nr, list);
279 * otherwise, it is known not to reach any
280 * tree-changing commit and gets weight 0.
282 break;
283 case 1:
284 weight_set(p, -1);
285 break;
286 default:
287 weight_set(p, -2);
288 break;
292 show_list("bisection 2 initialize", counted, nr, list);
295 * If you have only one parent in the resulting set
296 * then you can reach one commit more than that parent
297 * can reach. So we do not have to run the expensive
298 * count_distance() for single strand of pearls.
300 * However, if you have more than one parents, you cannot
301 * just add their distance and one for yourself, since
302 * they usually reach the same ancestor and you would
303 * end up counting them twice that way.
305 * So we will first count distance of merges the usual
306 * way, and then fill the blanks using cheaper algorithm.
308 for (p = list; p; p = p->next) {
309 if (p->item->object.flags & UNINTERESTING)
310 continue;
311 if (weight(p) != -2)
312 continue;
313 weight_set(p, count_distance(p));
314 clear_distance(list);
316 /* Does it happen to be at exactly half-way? */
317 if (!find_all && halfway(p, nr))
318 return p;
319 counted++;
322 show_list("bisection 2 count_distance", counted, nr, list);
324 while (counted < nr) {
325 for (p = list; p; p = p->next) {
326 struct commit_list *q;
327 unsigned flags = p->item->object.flags;
329 if (0 <= weight(p))
330 continue;
331 for (q = p->item->parents; q; q = q->next) {
332 if (q->item->object.flags & UNINTERESTING)
333 continue;
334 if (0 <= weight(q))
335 break;
337 if (!q)
338 continue;
341 * weight for p is unknown but q is known.
342 * add one for p itself if p is to be counted,
343 * otherwise inherit it from q directly.
345 if (!(flags & TREESAME)) {
346 weight_set(p, weight(q)+1);
347 counted++;
348 show_list("bisection 2 count one",
349 counted, nr, list);
351 else
352 weight_set(p, weight(q));
354 /* Does it happen to be at exactly half-way? */
355 if (!find_all && halfway(p, nr))
356 return p;
360 show_list("bisection 2 counted all", counted, nr, list);
362 if (!find_all)
363 return best_bisection(list, nr);
364 else
365 return best_bisection_sorted(list, nr);
368 struct commit_list *find_bisection(struct commit_list *list,
369 int *reaches, int *all,
370 int find_all)
372 int nr, on_list;
373 struct commit_list *p, *best, *next, *last;
374 int *weights;
376 show_list("bisection 2 entry", 0, 0, list);
379 * Count the number of total and tree-changing items on the
380 * list, while reversing the list.
382 for (nr = on_list = 0, last = NULL, p = list;
384 p = next) {
385 unsigned flags = p->item->object.flags;
387 next = p->next;
388 if (flags & UNINTERESTING)
389 continue;
390 p->next = last;
391 last = p;
392 if (!(flags & TREESAME))
393 nr++;
394 on_list++;
396 list = last;
397 show_list("bisection 2 sorted", 0, nr, list);
399 *all = nr;
400 weights = xcalloc(on_list, sizeof(*weights));
402 /* Do the real work of finding bisection commit. */
403 best = do_find_bisection(list, nr, weights, find_all);
404 if (best) {
405 if (!find_all)
406 best->next = NULL;
407 *reaches = weight(best);
409 free(weights);
410 return best;
413 static void argv_array_push(struct argv_array *array, const char *string)
415 ALLOC_GROW(array->argv, array->argv_nr + 1, array->argv_alloc);
416 array->argv[array->argv_nr++] = string;
419 static void argv_array_push_sha1(struct argv_array *array,
420 const unsigned char *sha1,
421 const char *format)
423 struct strbuf buf = STRBUF_INIT;
424 strbuf_addf(&buf, format, sha1_to_hex(sha1));
425 argv_array_push(array, strbuf_detach(&buf, NULL));
428 static void sha1_array_push(struct sha1_array *array,
429 const unsigned char *sha1)
431 ALLOC_GROW(array->sha1, array->sha1_nr + 1, array->sha1_alloc);
432 hashcpy(array->sha1[array->sha1_nr++], sha1);
435 static int register_ref(const char *refname, const unsigned char *sha1,
436 int flags, void *cb_data)
438 if (!strcmp(refname, "bad")) {
439 current_bad_sha1 = sha1;
440 } else if (!prefixcmp(refname, "good-")) {
441 sha1_array_push(&good_revs, sha1);
442 } else if (!prefixcmp(refname, "skip-")) {
443 sha1_array_push(&skipped_revs, sha1);
446 return 0;
449 static int read_bisect_refs(void)
451 return for_each_ref_in("refs/bisect/", register_ref, NULL);
454 static void read_bisect_paths(struct argv_array *array)
456 struct strbuf str = STRBUF_INIT;
457 const char *filename = git_path("BISECT_NAMES");
458 FILE *fp = fopen(filename, "r");
460 if (!fp)
461 die_errno("Could not open file '%s'", filename);
463 while (strbuf_getline(&str, fp, '\n') != EOF) {
464 char *quoted;
465 int res;
467 strbuf_trim(&str);
468 quoted = strbuf_detach(&str, NULL);
469 res = sq_dequote_to_argv(quoted, &array->argv,
470 &array->argv_nr, &array->argv_alloc);
471 if (res)
472 die("Badly quoted content in file '%s': %s",
473 filename, quoted);
476 strbuf_release(&str);
477 fclose(fp);
480 static int array_cmp(const void *a, const void *b)
482 return hashcmp(a, b);
485 static void sort_sha1_array(struct sha1_array *array)
487 qsort(array->sha1, array->sha1_nr, sizeof(*array->sha1), array_cmp);
489 array->sorted = 1;
492 static const unsigned char *sha1_access(size_t index, void *table)
494 unsigned char (*array)[20] = table;
495 return array[index];
498 static int lookup_sha1_array(struct sha1_array *array,
499 const unsigned char *sha1)
501 if (!array->sorted)
502 sort_sha1_array(array);
504 return sha1_pos(sha1, array->sha1, array->sha1_nr, sha1_access);
507 static char *join_sha1_array_hex(struct sha1_array *array, char delim)
509 struct strbuf joined_hexs = STRBUF_INIT;
510 int i;
512 for (i = 0; i < array->sha1_nr; i++) {
513 strbuf_addstr(&joined_hexs, sha1_to_hex(array->sha1[i]));
514 if (i + 1 < array->sha1_nr)
515 strbuf_addch(&joined_hexs, delim);
518 return strbuf_detach(&joined_hexs, NULL);
522 * In this function, passing a not NULL skipped_first is very special.
523 * It means that we want to know if the first commit in the list is
524 * skipped because we will want to test a commit away from it if it is
525 * indeed skipped.
526 * So if the first commit is skipped, we cannot take the shortcut to
527 * just "return list" when we find the first non skipped commit, we
528 * have to return a fully filtered list.
530 * We use (*skipped_first == -1) to mean "it has been found that the
531 * first commit is not skipped". In this case *skipped_first is set back
532 * to 0 just before the function returns.
534 struct commit_list *filter_skipped(struct commit_list *list,
535 struct commit_list **tried,
536 int show_all,
537 int *count,
538 int *skipped_first)
540 struct commit_list *filtered = NULL, **f = &filtered;
542 *tried = NULL;
544 if (skipped_first)
545 *skipped_first = 0;
546 if (count)
547 *count = 0;
549 if (!skipped_revs.sha1_nr)
550 return list;
552 while (list) {
553 struct commit_list *next = list->next;
554 list->next = NULL;
555 if (0 <= lookup_sha1_array(&skipped_revs,
556 list->item->object.sha1)) {
557 if (skipped_first && !*skipped_first)
558 *skipped_first = 1;
559 /* Move current to tried list */
560 *tried = list;
561 tried = &list->next;
562 } else {
563 if (!show_all) {
564 if (!skipped_first || !*skipped_first)
565 return list;
566 } else if (skipped_first && !*skipped_first) {
567 /* This means we know it's not skipped */
568 *skipped_first = -1;
570 /* Move current to filtered list */
571 *f = list;
572 f = &list->next;
573 if (count)
574 (*count)++;
576 list = next;
579 if (skipped_first && *skipped_first == -1)
580 *skipped_first = 0;
582 return filtered;
585 #define PRN_MODULO 32768
588 * This is a pseudo random number generator based on "man 3 rand".
589 * It is not used properly because the seed is the argument and it
590 * is increased by one between each call, but that should not matter
591 * for this application.
593 static int get_prn(int count) {
594 count = count * 1103515245 + 12345;
595 return ((unsigned)(count/65536) % PRN_MODULO);
599 * Custom integer square root from
600 * http://en.wikipedia.org/wiki/Integer_square_root
602 static int sqrti(int val)
604 float d, x = val;
606 if (val == 0)
607 return 0;
609 do {
610 float y = (x + (float)val / x) / 2;
611 d = (y > x) ? y - x : x - y;
612 x = y;
613 } while (d >= 0.5);
615 return (int)x;
618 static struct commit_list *skip_away(struct commit_list *list, int count)
620 struct commit_list *cur, *previous;
621 int prn, index, i;
623 prn = get_prn(count);
624 index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
626 cur = list;
627 previous = NULL;
629 for (i = 0; cur; cur = cur->next, i++) {
630 if (i == index) {
631 if (hashcmp(cur->item->object.sha1, current_bad_sha1))
632 return cur;
633 if (previous)
634 return previous;
635 return list;
637 previous = cur;
640 return list;
643 static struct commit_list *managed_skipped(struct commit_list *list,
644 struct commit_list **tried)
646 int count, skipped_first;
648 *tried = NULL;
650 if (!skipped_revs.sha1_nr)
651 return list;
653 list = filter_skipped(list, tried, 0, &count, &skipped_first);
655 if (!skipped_first)
656 return list;
658 return skip_away(list, count);
661 static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
662 const char *bad_format, const char *good_format,
663 int read_paths)
665 struct argv_array rev_argv = { NULL, 0, 0 };
666 int i;
668 init_revisions(revs, prefix);
669 revs->abbrev = 0;
670 revs->commit_format = CMIT_FMT_UNSPECIFIED;
672 /* rev_argv.argv[0] will be ignored by setup_revisions */
673 argv_array_push(&rev_argv, xstrdup("bisect_rev_setup"));
674 argv_array_push_sha1(&rev_argv, current_bad_sha1, bad_format);
675 for (i = 0; i < good_revs.sha1_nr; i++)
676 argv_array_push_sha1(&rev_argv, good_revs.sha1[i],
677 good_format);
678 argv_array_push(&rev_argv, xstrdup("--"));
679 if (read_paths)
680 read_bisect_paths(&rev_argv);
681 argv_array_push(&rev_argv, NULL);
683 setup_revisions(rev_argv.argv_nr, rev_argv.argv, revs, NULL);
686 static void bisect_common(struct rev_info *revs)
688 if (prepare_revision_walk(revs))
689 die("revision walk setup failed");
690 if (revs->tree_objects)
691 mark_edges_uninteresting(revs->commits, revs, NULL);
694 static void exit_if_skipped_commits(struct commit_list *tried,
695 const unsigned char *bad)
697 if (!tried)
698 return;
700 printf("There are only 'skip'ped commits left to test.\n"
701 "The first bad commit could be any of:\n");
702 print_commit_list(tried, "%s\n", "%s\n");
703 if (bad)
704 printf("%s\n", sha1_to_hex(bad));
705 printf("We cannot bisect more!\n");
706 exit(2);
709 static int is_expected_rev(const unsigned char *sha1)
711 const char *filename = git_path("BISECT_EXPECTED_REV");
712 struct stat st;
713 struct strbuf str = STRBUF_INIT;
714 FILE *fp;
715 int res = 0;
717 if (stat(filename, &st) || !S_ISREG(st.st_mode))
718 return 0;
720 fp = fopen(filename, "r");
721 if (!fp)
722 return 0;
724 if (strbuf_getline(&str, fp, '\n') != EOF)
725 res = !strcmp(str.buf, sha1_to_hex(sha1));
727 strbuf_release(&str);
728 fclose(fp);
730 return res;
733 static void mark_expected_rev(char *bisect_rev_hex)
735 int len = strlen(bisect_rev_hex);
736 const char *filename = git_path("BISECT_EXPECTED_REV");
737 int fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
739 if (fd < 0)
740 die_errno("could not create file '%s'", filename);
742 bisect_rev_hex[len] = '\n';
743 write_or_die(fd, bisect_rev_hex, len + 1);
744 bisect_rev_hex[len] = '\0';
746 if (close(fd) < 0)
747 die("closing file %s: %s", filename, strerror(errno));
750 static int bisect_checkout(char *bisect_rev_hex)
752 int res;
754 mark_expected_rev(bisect_rev_hex);
756 argv_checkout[2] = bisect_rev_hex;
757 res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
758 if (res)
759 exit(res);
761 argv_show_branch[1] = bisect_rev_hex;
762 return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
765 static struct commit *get_commit_reference(const unsigned char *sha1)
767 struct commit *r = lookup_commit_reference(sha1);
768 if (!r)
769 die("Not a valid commit name %s", sha1_to_hex(sha1));
770 return r;
773 static struct commit **get_bad_and_good_commits(int *rev_nr)
775 int len = 1 + good_revs.sha1_nr;
776 struct commit **rev = xmalloc(len * sizeof(*rev));
777 int i, n = 0;
779 rev[n++] = get_commit_reference(current_bad_sha1);
780 for (i = 0; i < good_revs.sha1_nr; i++)
781 rev[n++] = get_commit_reference(good_revs.sha1[i]);
782 *rev_nr = n;
784 return rev;
787 static void handle_bad_merge_base(void)
789 if (is_expected_rev(current_bad_sha1)) {
790 char *bad_hex = sha1_to_hex(current_bad_sha1);
791 char *good_hex = join_sha1_array_hex(&good_revs, ' ');
793 fprintf(stderr, "The merge base %s is bad.\n"
794 "This means the bug has been fixed "
795 "between %s and [%s].\n",
796 bad_hex, bad_hex, good_hex);
798 exit(3);
801 fprintf(stderr, "Some good revs are not ancestor of the bad rev.\n"
802 "git bisect cannot work properly in this case.\n"
803 "Maybe you mistake good and bad revs?\n");
804 exit(1);
807 static void handle_skipped_merge_base(const unsigned char *mb)
809 char *mb_hex = sha1_to_hex(mb);
810 char *bad_hex = sha1_to_hex(current_bad_sha1);
811 char *good_hex = join_sha1_array_hex(&good_revs, ' ');
813 warning("the merge base between %s and [%s] "
814 "must be skipped.\n"
815 "So we cannot be sure the first bad commit is "
816 "between %s and %s.\n"
817 "We continue anyway.",
818 bad_hex, good_hex, mb_hex, bad_hex);
819 free(good_hex);
823 * "check_merge_bases" checks that merge bases are not "bad".
825 * - If one is "bad", it means the user assumed something wrong
826 * and we must exit with a non 0 error code.
827 * - If one is "good", that's good, we have nothing to do.
828 * - If one is "skipped", we can't know but we should warn.
829 * - If we don't know, we should check it out and ask the user to test.
831 static void check_merge_bases(void)
833 struct commit_list *result;
834 int rev_nr;
835 struct commit **rev = get_bad_and_good_commits(&rev_nr);
837 result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1, 0);
839 for (; result; result = result->next) {
840 const unsigned char *mb = result->item->object.sha1;
841 if (!hashcmp(mb, current_bad_sha1)) {
842 handle_bad_merge_base();
843 } else if (0 <= lookup_sha1_array(&good_revs, mb)) {
844 continue;
845 } else if (0 <= lookup_sha1_array(&skipped_revs, mb)) {
846 handle_skipped_merge_base(mb);
847 } else {
848 printf("Bisecting: a merge base must be tested\n");
849 exit(bisect_checkout(sha1_to_hex(mb)));
853 free(rev);
854 free_commit_list(result);
857 static int check_ancestors(const char *prefix)
859 struct rev_info revs;
860 struct object_array pending_copy;
861 int i, res;
863 bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
865 /* Save pending objects, so they can be cleaned up later. */
866 memset(&pending_copy, 0, sizeof(pending_copy));
867 for (i = 0; i < revs.pending.nr; i++)
868 add_object_array(revs.pending.objects[i].item,
869 revs.pending.objects[i].name,
870 &pending_copy);
872 bisect_common(&revs);
873 res = (revs.commits != NULL);
875 /* Clean up objects used, as they will be reused. */
876 for (i = 0; i < pending_copy.nr; i++) {
877 struct object *o = pending_copy.objects[i].item;
878 clear_commit_marks((struct commit *)o, ALL_REV_FLAGS);
881 return res;
885 * "check_good_are_ancestors_of_bad" checks that all "good" revs are
886 * ancestor of the "bad" rev.
888 * If that's not the case, we need to check the merge bases.
889 * If a merge base must be tested by the user, its source code will be
890 * checked out to be tested by the user and we will exit.
892 static void check_good_are_ancestors_of_bad(const char *prefix)
894 const char *filename = git_path("BISECT_ANCESTORS_OK");
895 struct stat st;
896 int fd;
898 if (!current_bad_sha1)
899 die("a bad revision is needed");
901 /* Check if file BISECT_ANCESTORS_OK exists. */
902 if (!stat(filename, &st) && S_ISREG(st.st_mode))
903 return;
905 /* Bisecting with no good rev is ok. */
906 if (good_revs.sha1_nr == 0)
907 return;
909 /* Check if all good revs are ancestor of the bad rev. */
910 if (check_ancestors(prefix))
911 check_merge_bases();
913 /* Create file BISECT_ANCESTORS_OK. */
914 fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
915 if (fd < 0)
916 warning("could not create file '%s': %s",
917 filename, strerror(errno));
918 else
919 close(fd);
923 * This does "git diff-tree --pretty COMMIT" without one fork+exec.
925 static void show_diff_tree(const char *prefix, struct commit *commit)
927 struct rev_info opt;
929 /* diff-tree init */
930 init_revisions(&opt, prefix);
931 git_config(git_diff_basic_config, NULL); /* no "diff" UI options */
932 opt.abbrev = 0;
933 opt.diff = 1;
935 /* This is what "--pretty" does */
936 opt.verbose_header = 1;
937 opt.use_terminator = 0;
938 opt.commit_format = CMIT_FMT_DEFAULT;
940 /* diff-tree init */
941 if (!opt.diffopt.output_format)
942 opt.diffopt.output_format = DIFF_FORMAT_RAW;
944 log_tree_commit(&opt, commit);
948 * We use the convention that exiting with an exit code 10 means that
949 * the bisection process finished successfully.
950 * In this case the calling shell script should exit 0.
952 int bisect_next_all(const char *prefix)
954 struct rev_info revs;
955 struct commit_list *tried;
956 int reaches = 0, all = 0, nr, steps;
957 const unsigned char *bisect_rev;
958 char bisect_rev_hex[41];
960 if (read_bisect_refs())
961 die("reading bisect refs failed");
963 check_good_are_ancestors_of_bad(prefix);
965 bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
966 revs.limited = 1;
968 bisect_common(&revs);
970 revs.commits = find_bisection(revs.commits, &reaches, &all,
971 !!skipped_revs.sha1_nr);
972 revs.commits = managed_skipped(revs.commits, &tried);
974 if (!revs.commits) {
976 * We should exit here only if the "bad"
977 * commit is also a "skip" commit.
979 exit_if_skipped_commits(tried, NULL);
981 printf("%s was both good and bad\n",
982 sha1_to_hex(current_bad_sha1));
983 exit(1);
986 if (!all) {
987 fprintf(stderr, "No testable commit found.\n"
988 "Maybe you started with bad path parameters?\n");
989 exit(4);
992 bisect_rev = revs.commits->item->object.sha1;
993 memcpy(bisect_rev_hex, sha1_to_hex(bisect_rev), 41);
995 if (!hashcmp(bisect_rev, current_bad_sha1)) {
996 exit_if_skipped_commits(tried, current_bad_sha1);
997 printf("%s is the first bad commit\n", bisect_rev_hex);
998 show_diff_tree(prefix, revs.commits->item);
999 /* This means the bisection process succeeded. */
1000 exit(10);
1003 nr = all - reaches - 1;
1004 steps = estimate_bisect_steps(all);
1005 printf("Bisecting: %d revision%s left to test after this "
1006 "(roughly %d step%s)\n", nr, (nr == 1 ? "" : "s"),
1007 steps, (steps == 1 ? "" : "s"));
1009 return bisect_checkout(bisect_rev_hex);