run_hook: use argv_array API
[git/git.git] / bisect.c
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"
12 #include "sha1-array.h"
13 #include "argv-array.h"
14
15 static struct sha1_array good_revs;
16 static struct sha1_array skipped_revs;
17
18 static const unsigned char *current_bad_sha1;
19
20 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
21 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
22
23 /* bits #0-15 in revision.h */
24
25 #define COUNTED (1u<<16)
26
27 /*
28 * This is a truly stupid algorithm, but it's only
29 * used for bisection, and we just don't care enough.
30 *
31 * We care just barely enough to avoid recursing for
32 * non-merge entries.
33 */
34 static int count_distance(struct commit_list *entry)
35 {
36 int nr = 0;
37
38 while (entry) {
39 struct commit *commit = entry->item;
40 struct commit_list *p;
41
42 if (commit->object.flags & (UNINTERESTING | COUNTED))
43 break;
44 if (!(commit->object.flags & TREESAME))
45 nr++;
46 commit->object.flags |= COUNTED;
47 p = commit->parents;
48 entry = p;
49 if (p) {
50 p = p->next;
51 while (p) {
52 nr += count_distance(p);
53 p = p->next;
54 }
55 }
56 }
57
58 return nr;
59 }
60
61 static void clear_distance(struct commit_list *list)
62 {
63 while (list) {
64 struct commit *commit = list->item;
65 commit->object.flags &= ~COUNTED;
66 list = list->next;
67 }
68 }
69
70 #define DEBUG_BISECT 0
71
72 static inline int weight(struct commit_list *elem)
73 {
74 return *((int*)(elem->item->util));
75 }
76
77 static inline void weight_set(struct commit_list *elem, int weight)
78 {
79 *((int*)(elem->item->util)) = weight;
80 }
81
82 static int count_interesting_parents(struct commit *commit)
83 {
84 struct commit_list *p;
85 int count;
86
87 for (count = 0, p = commit->parents; p; p = p->next) {
88 if (p->item->object.flags & UNINTERESTING)
89 continue;
90 count++;
91 }
92 return count;
93 }
94
95 static inline int halfway(struct commit_list *p, int nr)
96 {
97 /*
98 * Don't short-cut something we are not going to return!
99 */
100 if (p->item->object.flags & TREESAME)
101 return 0;
102 if (DEBUG_BISECT)
103 return 0;
104 /*
105 * 2 and 3 are halfway of 5.
106 * 3 is halfway of 6 but 2 and 4 are not.
107 */
108 switch (2 * weight(p) - nr) {
109 case -1: case 0: case 1:
110 return 1;
111 default:
112 return 0;
113 }
114 }
115
116 #if !DEBUG_BISECT
117 #define show_list(a,b,c,d) do { ; } while (0)
118 #else
119 static void show_list(const char *debug, int counted, int nr,
120 struct commit_list *list)
121 {
122 struct commit_list *p;
123
124 fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
125
126 for (p = list; p; p = p->next) {
127 struct commit_list *pp;
128 struct commit *commit = p->item;
129 unsigned flags = commit->object.flags;
130 enum object_type type;
131 unsigned long size;
132 char *buf = read_sha1_file(commit->object.sha1, &type, &size);
133 const char *subject_start;
134 int subject_len;
135
136 fprintf(stderr, "%c%c%c ",
137 (flags & TREESAME) ? ' ' : 'T',
138 (flags & UNINTERESTING) ? 'U' : ' ',
139 (flags & COUNTED) ? 'C' : ' ');
140 if (commit->util)
141 fprintf(stderr, "%3d", weight(p));
142 else
143 fprintf(stderr, "---");
144 fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
145 for (pp = commit->parents; pp; pp = pp->next)
146 fprintf(stderr, " %.*s", 8,
147 sha1_to_hex(pp->item->object.sha1));
148
149 subject_len = find_commit_subject(buf, &subject_start);
150 if (subject_len)
151 fprintf(stderr, " %.*s", subject_len, subject_start);
152 fprintf(stderr, "\n");
153 }
154 }
155 #endif /* DEBUG_BISECT */
156
157 static struct commit_list *best_bisection(struct commit_list *list, int nr)
158 {
159 struct commit_list *p, *best;
160 int best_distance = -1;
161
162 best = list;
163 for (p = list; p; p = p->next) {
164 int distance;
165 unsigned flags = p->item->object.flags;
166
167 if (flags & TREESAME)
168 continue;
169 distance = weight(p);
170 if (nr - distance < distance)
171 distance = nr - distance;
172 if (distance > best_distance) {
173 best = p;
174 best_distance = distance;
175 }
176 }
177
178 return best;
179 }
180
181 struct commit_dist {
182 struct commit *commit;
183 int distance;
184 };
185
186 static int compare_commit_dist(const void *a_, const void *b_)
187 {
188 struct commit_dist *a, *b;
189
190 a = (struct commit_dist *)a_;
191 b = (struct commit_dist *)b_;
192 if (a->distance != b->distance)
193 return b->distance - a->distance; /* desc sort */
194 return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
195 }
196
197 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
198 {
199 struct commit_list *p;
200 struct commit_dist *array = xcalloc(nr, sizeof(*array));
201 int cnt, i;
202
203 for (p = list, cnt = 0; p; p = p->next) {
204 int distance;
205 unsigned flags = p->item->object.flags;
206
207 if (flags & TREESAME)
208 continue;
209 distance = weight(p);
210 if (nr - distance < distance)
211 distance = nr - distance;
212 array[cnt].commit = p->item;
213 array[cnt].distance = distance;
214 cnt++;
215 }
216 qsort(array, cnt, sizeof(*array), compare_commit_dist);
217 for (p = list, i = 0; i < cnt; i++) {
218 struct name_decoration *r = xmalloc(sizeof(*r) + 100);
219 struct object *obj = &(array[i].commit->object);
220
221 sprintf(r->name, "dist=%d", array[i].distance);
222 r->next = add_decoration(&name_decoration, obj, r);
223 p->item = array[i].commit;
224 p = p->next;
225 }
226 if (p)
227 p->next = NULL;
228 free(array);
229 return list;
230 }
231
232 /*
233 * zero or positive weight is the number of interesting commits it can
234 * reach, including itself. Especially, weight = 0 means it does not
235 * reach any tree-changing commits (e.g. just above uninteresting one
236 * but traversal is with pathspec).
237 *
238 * weight = -1 means it has one parent and its distance is yet to
239 * be computed.
240 *
241 * weight = -2 means it has more than one parent and its distance is
242 * unknown. After running count_distance() first, they will get zero
243 * or positive distance.
244 */
245 static struct commit_list *do_find_bisection(struct commit_list *list,
246 int nr, int *weights,
247 int find_all)
248 {
249 int n, counted;
250 struct commit_list *p;
251
252 counted = 0;
253
254 for (n = 0, p = list; p; p = p->next) {
255 struct commit *commit = p->item;
256 unsigned flags = commit->object.flags;
257
258 p->item->util = &weights[n++];
259 switch (count_interesting_parents(commit)) {
260 case 0:
261 if (!(flags & TREESAME)) {
262 weight_set(p, 1);
263 counted++;
264 show_list("bisection 2 count one",
265 counted, nr, list);
266 }
267 /*
268 * otherwise, it is known not to reach any
269 * tree-changing commit and gets weight 0.
270 */
271 break;
272 case 1:
273 weight_set(p, -1);
274 break;
275 default:
276 weight_set(p, -2);
277 break;
278 }
279 }
280
281 show_list("bisection 2 initialize", counted, nr, list);
282
283 /*
284 * If you have only one parent in the resulting set
285 * then you can reach one commit more than that parent
286 * can reach. So we do not have to run the expensive
287 * count_distance() for single strand of pearls.
288 *
289 * However, if you have more than one parents, you cannot
290 * just add their distance and one for yourself, since
291 * they usually reach the same ancestor and you would
292 * end up counting them twice that way.
293 *
294 * So we will first count distance of merges the usual
295 * way, and then fill the blanks using cheaper algorithm.
296 */
297 for (p = list; p; p = p->next) {
298 if (p->item->object.flags & UNINTERESTING)
299 continue;
300 if (weight(p) != -2)
301 continue;
302 weight_set(p, count_distance(p));
303 clear_distance(list);
304
305 /* Does it happen to be at exactly half-way? */
306 if (!find_all && halfway(p, nr))
307 return p;
308 counted++;
309 }
310
311 show_list("bisection 2 count_distance", counted, nr, list);
312
313 while (counted < nr) {
314 for (p = list; p; p = p->next) {
315 struct commit_list *q;
316 unsigned flags = p->item->object.flags;
317
318 if (0 <= weight(p))
319 continue;
320 for (q = p->item->parents; q; q = q->next) {
321 if (q->item->object.flags & UNINTERESTING)
322 continue;
323 if (0 <= weight(q))
324 break;
325 }
326 if (!q)
327 continue;
328
329 /*
330 * weight for p is unknown but q is known.
331 * add one for p itself if p is to be counted,
332 * otherwise inherit it from q directly.
333 */
334 if (!(flags & TREESAME)) {
335 weight_set(p, weight(q)+1);
336 counted++;
337 show_list("bisection 2 count one",
338 counted, nr, list);
339 }
340 else
341 weight_set(p, weight(q));
342
343 /* Does it happen to be at exactly half-way? */
344 if (!find_all && halfway(p, nr))
345 return p;
346 }
347 }
348
349 show_list("bisection 2 counted all", counted, nr, list);
350
351 if (!find_all)
352 return best_bisection(list, nr);
353 else
354 return best_bisection_sorted(list, nr);
355 }
356
357 struct commit_list *find_bisection(struct commit_list *list,
358 int *reaches, int *all,
359 int find_all)
360 {
361 int nr, on_list;
362 struct commit_list *p, *best, *next, *last;
363 int *weights;
364
365 show_list("bisection 2 entry", 0, 0, list);
366
367 /*
368 * Count the number of total and tree-changing items on the
369 * list, while reversing the list.
370 */
371 for (nr = on_list = 0, last = NULL, p = list;
372 p;
373 p = next) {
374 unsigned flags = p->item->object.flags;
375
376 next = p->next;
377 if (flags & UNINTERESTING)
378 continue;
379 p->next = last;
380 last = p;
381 if (!(flags & TREESAME))
382 nr++;
383 on_list++;
384 }
385 list = last;
386 show_list("bisection 2 sorted", 0, nr, list);
387
388 *all = nr;
389 weights = xcalloc(on_list, sizeof(*weights));
390
391 /* Do the real work of finding bisection commit. */
392 best = do_find_bisection(list, nr, weights, find_all);
393 if (best) {
394 if (!find_all)
395 best->next = NULL;
396 *reaches = weight(best);
397 }
398 free(weights);
399 return best;
400 }
401
402 static int register_ref(const char *refname, const unsigned char *sha1,
403 int flags, void *cb_data)
404 {
405 if (!strcmp(refname, "bad")) {
406 current_bad_sha1 = sha1;
407 } else if (!prefixcmp(refname, "good-")) {
408 sha1_array_append(&good_revs, sha1);
409 } else if (!prefixcmp(refname, "skip-")) {
410 sha1_array_append(&skipped_revs, sha1);
411 }
412
413 return 0;
414 }
415
416 static int read_bisect_refs(void)
417 {
418 return for_each_ref_in("refs/bisect/", register_ref, NULL);
419 }
420
421 static void read_bisect_paths(struct argv_array *array)
422 {
423 struct strbuf str = STRBUF_INIT;
424 const char *filename = git_path("BISECT_NAMES");
425 FILE *fp = fopen(filename, "r");
426
427 if (!fp)
428 die_errno("Could not open file '%s'", filename);
429
430 while (strbuf_getline(&str, fp, '\n') != EOF) {
431 strbuf_trim(&str);
432 if (sq_dequote_to_argv_array(str.buf, array))
433 die("Badly quoted content in file '%s': %s",
434 filename, str.buf);
435 }
436
437 strbuf_release(&str);
438 fclose(fp);
439 }
440
441 static char *join_sha1_array_hex(struct sha1_array *array, char delim)
442 {
443 struct strbuf joined_hexs = STRBUF_INIT;
444 int i;
445
446 for (i = 0; i < array->nr; i++) {
447 strbuf_addstr(&joined_hexs, sha1_to_hex(array->sha1[i]));
448 if (i + 1 < array->nr)
449 strbuf_addch(&joined_hexs, delim);
450 }
451
452 return strbuf_detach(&joined_hexs, NULL);
453 }
454
455 /*
456 * In this function, passing a not NULL skipped_first is very special.
457 * It means that we want to know if the first commit in the list is
458 * skipped because we will want to test a commit away from it if it is
459 * indeed skipped.
460 * So if the first commit is skipped, we cannot take the shortcut to
461 * just "return list" when we find the first non skipped commit, we
462 * have to return a fully filtered list.
463 *
464 * We use (*skipped_first == -1) to mean "it has been found that the
465 * first commit is not skipped". In this case *skipped_first is set back
466 * to 0 just before the function returns.
467 */
468 struct commit_list *filter_skipped(struct commit_list *list,
469 struct commit_list **tried,
470 int show_all,
471 int *count,
472 int *skipped_first)
473 {
474 struct commit_list *filtered = NULL, **f = &filtered;
475
476 *tried = NULL;
477
478 if (skipped_first)
479 *skipped_first = 0;
480 if (count)
481 *count = 0;
482
483 if (!skipped_revs.nr)
484 return list;
485
486 while (list) {
487 struct commit_list *next = list->next;
488 list->next = NULL;
489 if (0 <= sha1_array_lookup(&skipped_revs,
490 list->item->object.sha1)) {
491 if (skipped_first && !*skipped_first)
492 *skipped_first = 1;
493 /* Move current to tried list */
494 *tried = list;
495 tried = &list->next;
496 } else {
497 if (!show_all) {
498 if (!skipped_first || !*skipped_first)
499 return list;
500 } else if (skipped_first && !*skipped_first) {
501 /* This means we know it's not skipped */
502 *skipped_first = -1;
503 }
504 /* Move current to filtered list */
505 *f = list;
506 f = &list->next;
507 if (count)
508 (*count)++;
509 }
510 list = next;
511 }
512
513 if (skipped_first && *skipped_first == -1)
514 *skipped_first = 0;
515
516 return filtered;
517 }
518
519 #define PRN_MODULO 32768
520
521 /*
522 * This is a pseudo random number generator based on "man 3 rand".
523 * It is not used properly because the seed is the argument and it
524 * is increased by one between each call, but that should not matter
525 * for this application.
526 */
527 static int get_prn(int count) {
528 count = count * 1103515245 + 12345;
529 return ((unsigned)(count/65536) % PRN_MODULO);
530 }
531
532 /*
533 * Custom integer square root from
534 * http://en.wikipedia.org/wiki/Integer_square_root
535 */
536 static int sqrti(int val)
537 {
538 float d, x = val;
539
540 if (val == 0)
541 return 0;
542
543 do {
544 float y = (x + (float)val / x) / 2;
545 d = (y > x) ? y - x : x - y;
546 x = y;
547 } while (d >= 0.5);
548
549 return (int)x;
550 }
551
552 static struct commit_list *skip_away(struct commit_list *list, int count)
553 {
554 struct commit_list *cur, *previous;
555 int prn, index, i;
556
557 prn = get_prn(count);
558 index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
559
560 cur = list;
561 previous = NULL;
562
563 for (i = 0; cur; cur = cur->next, i++) {
564 if (i == index) {
565 if (hashcmp(cur->item->object.sha1, current_bad_sha1))
566 return cur;
567 if (previous)
568 return previous;
569 return list;
570 }
571 previous = cur;
572 }
573
574 return list;
575 }
576
577 static struct commit_list *managed_skipped(struct commit_list *list,
578 struct commit_list **tried)
579 {
580 int count, skipped_first;
581
582 *tried = NULL;
583
584 if (!skipped_revs.nr)
585 return list;
586
587 list = filter_skipped(list, tried, 0, &count, &skipped_first);
588
589 if (!skipped_first)
590 return list;
591
592 return skip_away(list, count);
593 }
594
595 static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
596 const char *bad_format, const char *good_format,
597 int read_paths)
598 {
599 struct argv_array rev_argv = ARGV_ARRAY_INIT;
600 int i;
601
602 init_revisions(revs, prefix);
603 revs->abbrev = 0;
604 revs->commit_format = CMIT_FMT_UNSPECIFIED;
605
606 /* rev_argv.argv[0] will be ignored by setup_revisions */
607 argv_array_push(&rev_argv, "bisect_rev_setup");
608 argv_array_pushf(&rev_argv, bad_format, sha1_to_hex(current_bad_sha1));
609 for (i = 0; i < good_revs.nr; i++)
610 argv_array_pushf(&rev_argv, good_format,
611 sha1_to_hex(good_revs.sha1[i]));
612 argv_array_push(&rev_argv, "--");
613 if (read_paths)
614 read_bisect_paths(&rev_argv);
615
616 setup_revisions(rev_argv.argc, rev_argv.argv, revs, NULL);
617 /* XXX leak rev_argv, as "revs" may still be pointing to it */
618 }
619
620 static void bisect_common(struct rev_info *revs)
621 {
622 if (prepare_revision_walk(revs))
623 die("revision walk setup failed");
624 if (revs->tree_objects)
625 mark_edges_uninteresting(revs->commits, revs, NULL);
626 }
627
628 static void exit_if_skipped_commits(struct commit_list *tried,
629 const unsigned char *bad)
630 {
631 if (!tried)
632 return;
633
634 printf("There are only 'skip'ped commits left to test.\n"
635 "The first bad commit could be any of:\n");
636 print_commit_list(tried, "%s\n", "%s\n");
637 if (bad)
638 printf("%s\n", sha1_to_hex(bad));
639 printf("We cannot bisect more!\n");
640 exit(2);
641 }
642
643 static int is_expected_rev(const unsigned char *sha1)
644 {
645 const char *filename = git_path("BISECT_EXPECTED_REV");
646 struct stat st;
647 struct strbuf str = STRBUF_INIT;
648 FILE *fp;
649 int res = 0;
650
651 if (stat(filename, &st) || !S_ISREG(st.st_mode))
652 return 0;
653
654 fp = fopen(filename, "r");
655 if (!fp)
656 return 0;
657
658 if (strbuf_getline(&str, fp, '\n') != EOF)
659 res = !strcmp(str.buf, sha1_to_hex(sha1));
660
661 strbuf_release(&str);
662 fclose(fp);
663
664 return res;
665 }
666
667 static void mark_expected_rev(char *bisect_rev_hex)
668 {
669 int len = strlen(bisect_rev_hex);
670 const char *filename = git_path("BISECT_EXPECTED_REV");
671 int fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
672
673 if (fd < 0)
674 die_errno("could not create file '%s'", filename);
675
676 bisect_rev_hex[len] = '\n';
677 write_or_die(fd, bisect_rev_hex, len + 1);
678 bisect_rev_hex[len] = '\0';
679
680 if (close(fd) < 0)
681 die("closing file %s: %s", filename, strerror(errno));
682 }
683
684 static int bisect_checkout(char *bisect_rev_hex)
685 {
686 int res;
687
688 mark_expected_rev(bisect_rev_hex);
689
690 argv_checkout[2] = bisect_rev_hex;
691 res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
692 if (res)
693 exit(res);
694
695 argv_show_branch[1] = bisect_rev_hex;
696 return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
697 }
698
699 static struct commit *get_commit_reference(const unsigned char *sha1)
700 {
701 struct commit *r = lookup_commit_reference(sha1);
702 if (!r)
703 die("Not a valid commit name %s", sha1_to_hex(sha1));
704 return r;
705 }
706
707 static struct commit **get_bad_and_good_commits(int *rev_nr)
708 {
709 int len = 1 + good_revs.nr;
710 struct commit **rev = xmalloc(len * sizeof(*rev));
711 int i, n = 0;
712
713 rev[n++] = get_commit_reference(current_bad_sha1);
714 for (i = 0; i < good_revs.nr; i++)
715 rev[n++] = get_commit_reference(good_revs.sha1[i]);
716 *rev_nr = n;
717
718 return rev;
719 }
720
721 static void handle_bad_merge_base(void)
722 {
723 if (is_expected_rev(current_bad_sha1)) {
724 char *bad_hex = sha1_to_hex(current_bad_sha1);
725 char *good_hex = join_sha1_array_hex(&good_revs, ' ');
726
727 fprintf(stderr, "The merge base %s is bad.\n"
728 "This means the bug has been fixed "
729 "between %s and [%s].\n",
730 bad_hex, bad_hex, good_hex);
731
732 exit(3);
733 }
734
735 fprintf(stderr, "Some good revs are not ancestor of the bad rev.\n"
736 "git bisect cannot work properly in this case.\n"
737 "Maybe you mistake good and bad revs?\n");
738 exit(1);
739 }
740
741 static void handle_skipped_merge_base(const unsigned char *mb)
742 {
743 char *mb_hex = sha1_to_hex(mb);
744 char *bad_hex = sha1_to_hex(current_bad_sha1);
745 char *good_hex = join_sha1_array_hex(&good_revs, ' ');
746
747 warning("the merge base between %s and [%s] "
748 "must be skipped.\n"
749 "So we cannot be sure the first bad commit is "
750 "between %s and %s.\n"
751 "We continue anyway.",
752 bad_hex, good_hex, mb_hex, bad_hex);
753 free(good_hex);
754 }
755
756 /*
757 * "check_merge_bases" checks that merge bases are not "bad".
758 *
759 * - If one is "bad", it means the user assumed something wrong
760 * and we must exit with a non 0 error code.
761 * - If one is "good", that's good, we have nothing to do.
762 * - If one is "skipped", we can't know but we should warn.
763 * - If we don't know, we should check it out and ask the user to test.
764 */
765 static void check_merge_bases(void)
766 {
767 struct commit_list *result;
768 int rev_nr;
769 struct commit **rev = get_bad_and_good_commits(&rev_nr);
770
771 result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1, 0);
772
773 for (; result; result = result->next) {
774 const unsigned char *mb = result->item->object.sha1;
775 if (!hashcmp(mb, current_bad_sha1)) {
776 handle_bad_merge_base();
777 } else if (0 <= sha1_array_lookup(&good_revs, mb)) {
778 continue;
779 } else if (0 <= sha1_array_lookup(&skipped_revs, mb)) {
780 handle_skipped_merge_base(mb);
781 } else {
782 printf("Bisecting: a merge base must be tested\n");
783 exit(bisect_checkout(sha1_to_hex(mb)));
784 }
785 }
786
787 free(rev);
788 free_commit_list(result);
789 }
790
791 static int check_ancestors(const char *prefix)
792 {
793 struct rev_info revs;
794 struct object_array pending_copy;
795 int i, res;
796
797 bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
798
799 /* Save pending objects, so they can be cleaned up later. */
800 memset(&pending_copy, 0, sizeof(pending_copy));
801 for (i = 0; i < revs.pending.nr; i++)
802 add_object_array(revs.pending.objects[i].item,
803 revs.pending.objects[i].name,
804 &pending_copy);
805
806 bisect_common(&revs);
807 res = (revs.commits != NULL);
808
809 /* Clean up objects used, as they will be reused. */
810 for (i = 0; i < pending_copy.nr; i++) {
811 struct object *o = pending_copy.objects[i].item;
812 clear_commit_marks((struct commit *)o, ALL_REV_FLAGS);
813 }
814
815 return res;
816 }
817
818 /*
819 * "check_good_are_ancestors_of_bad" checks that all "good" revs are
820 * ancestor of the "bad" rev.
821 *
822 * If that's not the case, we need to check the merge bases.
823 * If a merge base must be tested by the user, its source code will be
824 * checked out to be tested by the user and we will exit.
825 */
826 static void check_good_are_ancestors_of_bad(const char *prefix)
827 {
828 const char *filename = git_path("BISECT_ANCESTORS_OK");
829 struct stat st;
830 int fd;
831
832 if (!current_bad_sha1)
833 die("a bad revision is needed");
834
835 /* Check if file BISECT_ANCESTORS_OK exists. */
836 if (!stat(filename, &st) && S_ISREG(st.st_mode))
837 return;
838
839 /* Bisecting with no good rev is ok. */
840 if (good_revs.nr == 0)
841 return;
842
843 /* Check if all good revs are ancestor of the bad rev. */
844 if (check_ancestors(prefix))
845 check_merge_bases();
846
847 /* Create file BISECT_ANCESTORS_OK. */
848 fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
849 if (fd < 0)
850 warning("could not create file '%s': %s",
851 filename, strerror(errno));
852 else
853 close(fd);
854 }
855
856 /*
857 * This does "git diff-tree --pretty COMMIT" without one fork+exec.
858 */
859 static void show_diff_tree(const char *prefix, struct commit *commit)
860 {
861 struct rev_info opt;
862
863 /* diff-tree init */
864 init_revisions(&opt, prefix);
865 git_config(git_diff_basic_config, NULL); /* no "diff" UI options */
866 opt.abbrev = 0;
867 opt.diff = 1;
868
869 /* This is what "--pretty" does */
870 opt.verbose_header = 1;
871 opt.use_terminator = 0;
872 opt.commit_format = CMIT_FMT_DEFAULT;
873
874 /* diff-tree init */
875 if (!opt.diffopt.output_format)
876 opt.diffopt.output_format = DIFF_FORMAT_RAW;
877
878 log_tree_commit(&opt, commit);
879 }
880
881 /*
882 * We use the convention that exiting with an exit code 10 means that
883 * the bisection process finished successfully.
884 * In this case the calling shell script should exit 0.
885 */
886 int bisect_next_all(const char *prefix)
887 {
888 struct rev_info revs;
889 struct commit_list *tried;
890 int reaches = 0, all = 0, nr, steps;
891 const unsigned char *bisect_rev;
892 char bisect_rev_hex[41];
893
894 if (read_bisect_refs())
895 die("reading bisect refs failed");
896
897 check_good_are_ancestors_of_bad(prefix);
898
899 bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
900 revs.limited = 1;
901
902 bisect_common(&revs);
903
904 revs.commits = find_bisection(revs.commits, &reaches, &all,
905 !!skipped_revs.nr);
906 revs.commits = managed_skipped(revs.commits, &tried);
907
908 if (!revs.commits) {
909 /*
910 * We should exit here only if the "bad"
911 * commit is also a "skip" commit.
912 */
913 exit_if_skipped_commits(tried, NULL);
914
915 printf("%s was both good and bad\n",
916 sha1_to_hex(current_bad_sha1));
917 exit(1);
918 }
919
920 if (!all) {
921 fprintf(stderr, "No testable commit found.\n"
922 "Maybe you started with bad path parameters?\n");
923 exit(4);
924 }
925
926 bisect_rev = revs.commits->item->object.sha1;
927 memcpy(bisect_rev_hex, sha1_to_hex(bisect_rev), 41);
928
929 if (!hashcmp(bisect_rev, current_bad_sha1)) {
930 exit_if_skipped_commits(tried, current_bad_sha1);
931 printf("%s is the first bad commit\n", bisect_rev_hex);
932 show_diff_tree(prefix, revs.commits->item);
933 /* This means the bisection process succeeded. */
934 exit(10);
935 }
936
937 nr = all - reaches - 1;
938 steps = estimate_bisect_steps(all);
939 printf("Bisecting: %d revision%s left to test after this "
940 "(roughly %d step%s)\n", nr, (nr == 1 ? "" : "s"),
941 steps, (steps == 1 ? "" : "s"));
942
943 return bisect_checkout(bisect_rev_hex);
944 }
945