Makefile: extract Q_() source strings as ngettext()
[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
13 struct sha1_array {
14         unsigned char (*sha1)[20];
15         int sha1_nr;
16         int sha1_alloc;
17         int sorted;
18 };
19
20 static struct sha1_array good_revs;
21 static struct sha1_array skipped_revs;
22
23 static const unsigned char *current_bad_sha1;
24
25 struct argv_array {
26         const char **argv;
27         int argv_nr;
28         int argv_alloc;
29 };
30
31 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
32 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
33
34 /* bits #0-15 in revision.h */
35
36 #define COUNTED         (1u<<16)
37
38 /*
39  * This is a truly stupid algorithm, but it's only
40  * used for bisection, and we just don't care enough.
41  *
42  * We care just barely enough to avoid recursing for
43  * non-merge entries.
44  */
45 static int count_distance(struct commit_list *entry)
46 {
47         int nr = 0;
48
49         while (entry) {
50                 struct commit *commit = entry->item;
51                 struct commit_list *p;
52
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;
65                         }
66                 }
67         }
68
69         return nr;
70 }
71
72 static void clear_distance(struct commit_list *list)
73 {
74         while (list) {
75                 struct commit *commit = list->item;
76                 commit->object.flags &= ~COUNTED;
77                 list = list->next;
78         }
79 }
80
81 #define DEBUG_BISECT 0
82
83 static inline int weight(struct commit_list *elem)
84 {
85         return *((int*)(elem->item->util));
86 }
87
88 static inline void weight_set(struct commit_list *elem, int weight)
89 {
90         *((int*)(elem->item->util)) = weight;
91 }
92
93 static int count_interesting_parents(struct commit *commit)
94 {
95         struct commit_list *p;
96         int count;
97
98         for (count = 0, p = commit->parents; p; p = p->next) {
99                 if (p->item->object.flags & UNINTERESTING)
100                         continue;
101                 count++;
102         }
103         return count;
104 }
105
106 static inline int halfway(struct commit_list *p, int nr)
107 {
108         /*
109          * Don't short-cut something we are not going to return!
110          */
111         if (p->item->object.flags & TREESAME)
112                 return 0;
113         if (DEBUG_BISECT)
114                 return 0;
115         /*
116          * 2 and 3 are halfway of 5.
117          * 3 is halfway of 6 but 2 and 4 are not.
118          */
119         switch (2 * weight(p) - nr) {
120         case -1: case 0: case 1:
121                 return 1;
122         default:
123                 return 0;
124         }
125 }
126
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)
132 {
133         struct commit_list *p;
134
135         fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
136
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;
146
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));
159
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");
164         }
165 }
166 #endif /* DEBUG_BISECT */
167
168 static struct commit_list *best_bisection(struct commit_list *list, int nr)
169 {
170         struct commit_list *p, *best;
171         int best_distance = -1;
172
173         best = list;
174         for (p = list; p; p = p->next) {
175                 int distance;
176                 unsigned flags = p->item->object.flags;
177
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;
186                 }
187         }
188
189         return best;
190 }
191
192 struct commit_dist {
193         struct commit *commit;
194         int distance;
195 };
196
197 static int compare_commit_dist(const void *a_, const void *b_)
198 {
199         struct commit_dist *a, *b;
200
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);
206 }
207
208 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
209 {
210         struct commit_list *p;
211         struct commit_dist *array = xcalloc(nr, sizeof(*array));
212         int cnt, i;
213
214         for (p = list, cnt = 0; p; p = p->next) {
215                 int distance;
216                 unsigned flags = p->item->object.flags;
217
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++;
226         }
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);
231
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;
236         }
237         if (p)
238                 p->next = NULL;
239         free(array);
240         return list;
241 }
242
243 /*
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).
248  *
249  * weight = -1 means it has one parent and its distance is yet to
250  * be computed.
251  *
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.
255  */
256 static struct commit_list *do_find_bisection(struct commit_list *list,
257                                              int nr, int *weights,
258                                              int find_all)
259 {
260         int n, counted;
261         struct commit_list *p;
262
263         counted = 0;
264
265         for (n = 0, p = list; p; p = p->next) {
266                 struct commit *commit = p->item;
267                 unsigned flags = commit->object.flags;
268
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);
277                         }
278                         /*
279                          * otherwise, it is known not to reach any
280                          * tree-changing commit and gets weight 0.
281                          */
282                         break;
283                 case 1:
284                         weight_set(p, -1);
285                         break;
286                 default:
287                         weight_set(p, -2);
288                         break;
289                 }
290         }
291
292         show_list("bisection 2 initialize", counted, nr, list);
293
294         /*
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.
299          *
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.
304          *
305          * So we will first count distance of merges the usual
306          * way, and then fill the blanks using cheaper algorithm.
307          */
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);
315
316                 /* Does it happen to be at exactly half-way? */
317                 if (!find_all && halfway(p, nr))
318                         return p;
319                 counted++;
320         }
321
322         show_list("bisection 2 count_distance", counted, nr, list);
323
324         while (counted < nr) {
325                 for (p = list; p; p = p->next) {
326                         struct commit_list *q;
327                         unsigned flags = p->item->object.flags;
328
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;
336                         }
337                         if (!q)
338                                 continue;
339
340                         /*
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.
344                          */
345                         if (!(flags & TREESAME)) {
346                                 weight_set(p, weight(q)+1);
347                                 counted++;
348                                 show_list("bisection 2 count one",
349                                           counted, nr, list);
350                         }
351                         else
352                                 weight_set(p, weight(q));
353
354                         /* Does it happen to be at exactly half-way? */
355                         if (!find_all && halfway(p, nr))
356                                 return p;
357                 }
358         }
359
360         show_list("bisection 2 counted all", counted, nr, list);
361
362         if (!find_all)
363                 return best_bisection(list, nr);
364         else
365                 return best_bisection_sorted(list, nr);
366 }
367
368 struct commit_list *find_bisection(struct commit_list *list,
369                                           int *reaches, int *all,
370                                           int find_all)
371 {
372         int nr, on_list;
373         struct commit_list *p, *best, *next, *last;
374         int *weights;
375
376         show_list("bisection 2 entry", 0, 0, list);
377
378         /*
379          * Count the number of total and tree-changing items on the
380          * list, while reversing the list.
381          */
382         for (nr = on_list = 0, last = NULL, p = list;
383              p;
384              p = next) {
385                 unsigned flags = p->item->object.flags;
386
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++;
395         }
396         list = last;
397         show_list("bisection 2 sorted", 0, nr, list);
398
399         *all = nr;
400         weights = xcalloc(on_list, sizeof(*weights));
401
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);
408         }
409         free(weights);
410         return best;
411 }
412
413 static void argv_array_push(struct argv_array *array, const char *string)
414 {
415         ALLOC_GROW(array->argv, array->argv_nr + 1, array->argv_alloc);
416         array->argv[array->argv_nr++] = string;
417 }
418
419 static void argv_array_push_sha1(struct argv_array *array,
420                                  const unsigned char *sha1,
421                                  const char *format)
422 {
423         struct strbuf buf = STRBUF_INIT;
424         strbuf_addf(&buf, format, sha1_to_hex(sha1));
425         argv_array_push(array, strbuf_detach(&buf, NULL));
426 }
427
428 static void sha1_array_push(struct sha1_array *array,
429                             const unsigned char *sha1)
430 {
431         ALLOC_GROW(array->sha1, array->sha1_nr + 1, array->sha1_alloc);
432         hashcpy(array->sha1[array->sha1_nr++], sha1);
433 }
434
435 static int register_ref(const char *refname, const unsigned char *sha1,
436                         int flags, void *cb_data)
437 {
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);
444         }
445
446         return 0;
447 }
448
449 static int read_bisect_refs(void)
450 {
451         return for_each_ref_in("refs/bisect/", register_ref, NULL);
452 }
453
454 static void read_bisect_paths(struct argv_array *array)
455 {
456         struct strbuf str = STRBUF_INIT;
457         const char *filename = git_path("BISECT_NAMES");
458         FILE *fp = fopen(filename, "r");
459
460         if (!fp)
461                 die_errno("Could not open file '%s'", filename);
462
463         while (strbuf_getline(&str, fp, '\n') != EOF) {
464                 char *quoted;
465                 int res;
466
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);
474         }
475
476         strbuf_release(&str);
477         fclose(fp);
478 }
479
480 static int array_cmp(const void *a, const void *b)
481 {
482         return hashcmp(a, b);
483 }
484
485 static void sort_sha1_array(struct sha1_array *array)
486 {
487         qsort(array->sha1, array->sha1_nr, sizeof(*array->sha1), array_cmp);
488
489         array->sorted = 1;
490 }
491
492 static const unsigned char *sha1_access(size_t index, void *table)
493 {
494         unsigned char (*array)[20] = table;
495         return array[index];
496 }
497
498 static int lookup_sha1_array(struct sha1_array *array,
499                              const unsigned char *sha1)
500 {
501         if (!array->sorted)
502                 sort_sha1_array(array);
503
504         return sha1_pos(sha1, array->sha1, array->sha1_nr, sha1_access);
505 }
506
507 static char *join_sha1_array_hex(struct sha1_array *array, char delim)
508 {
509         struct strbuf joined_hexs = STRBUF_INIT;
510         int i;
511
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);
516         }
517
518         return strbuf_detach(&joined_hexs, NULL);
519 }
520
521 /*
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.
529  *
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.
533  */
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)
539 {
540         struct commit_list *filtered = NULL, **f = &filtered;
541
542         *tried = NULL;
543
544         if (skipped_first)
545                 *skipped_first = 0;
546         if (count)
547                 *count = 0;
548
549         if (!skipped_revs.sha1_nr)
550                 return list;
551
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;
569                         }
570                         /* Move current to filtered list */
571                         *f = list;
572                         f = &list->next;
573                         if (count)
574                                 (*count)++;
575                 }
576                 list = next;
577         }
578
579         if (skipped_first && *skipped_first == -1)
580                 *skipped_first = 0;
581
582         return filtered;
583 }
584
585 #define PRN_MODULO 32768
586
587 /*
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.
592  */
593 static int get_prn(int count) {
594         count = count * 1103515245 + 12345;
595         return ((unsigned)(count/65536) % PRN_MODULO);
596 }
597
598 /*
599  * Custom integer square root from
600  * http://en.wikipedia.org/wiki/Integer_square_root
601  */
602 static int sqrti(int val)
603 {
604         float d, x = val;
605
606         if (val == 0)
607                 return 0;
608
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);
614
615         return (int)x;
616 }
617
618 static struct commit_list *skip_away(struct commit_list *list, int count)
619 {
620         struct commit_list *cur, *previous;
621         int prn, index, i;
622
623         prn = get_prn(count);
624         index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
625
626         cur = list;
627         previous = NULL;
628
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;
636                 }
637                 previous = cur;
638         }
639
640         return list;
641 }
642
643 static struct commit_list *managed_skipped(struct commit_list *list,
644                                            struct commit_list **tried)
645 {
646         int count, skipped_first;
647
648         *tried = NULL;
649
650         if (!skipped_revs.sha1_nr)
651                 return list;
652
653         list = filter_skipped(list, tried, 0, &count, &skipped_first);
654
655         if (!skipped_first)
656                 return list;
657
658         return skip_away(list, count);
659 }
660
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)
664 {
665         struct argv_array rev_argv = { NULL, 0, 0 };
666         int i;
667
668         init_revisions(revs, prefix);
669         revs->abbrev = 0;
670         revs->commit_format = CMIT_FMT_UNSPECIFIED;
671
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);
682
683         setup_revisions(rev_argv.argv_nr, rev_argv.argv, revs, NULL);
684 }
685
686 static void bisect_common(struct rev_info *revs)
687 {
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);
692 }
693
694 static void exit_if_skipped_commits(struct commit_list *tried,
695                                     const unsigned char *bad)
696 {
697         if (!tried)
698                 return;
699
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);
707 }
708
709 static int is_expected_rev(const unsigned char *sha1)
710 {
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;
716
717         if (stat(filename, &st) || !S_ISREG(st.st_mode))
718                 return 0;
719
720         fp = fopen(filename, "r");
721         if (!fp)
722                 return 0;
723
724         if (strbuf_getline(&str, fp, '\n') != EOF)
725                 res = !strcmp(str.buf, sha1_to_hex(sha1));
726
727         strbuf_release(&str);
728         fclose(fp);
729
730         return res;
731 }
732
733 static void mark_expected_rev(char *bisect_rev_hex)
734 {
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);
738
739         if (fd < 0)
740                 die_errno("could not create file '%s'", filename);
741
742         bisect_rev_hex[len] = '\n';
743         write_or_die(fd, bisect_rev_hex, len + 1);
744         bisect_rev_hex[len] = '\0';
745
746         if (close(fd) < 0)
747                 die("closing file %s: %s", filename, strerror(errno));
748 }
749
750 static int bisect_checkout(char *bisect_rev_hex)
751 {
752         int res;
753
754         mark_expected_rev(bisect_rev_hex);
755
756         argv_checkout[2] = bisect_rev_hex;
757         res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
758         if (res)
759                 exit(res);
760
761         argv_show_branch[1] = bisect_rev_hex;
762         return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
763 }
764
765 static struct commit *get_commit_reference(const unsigned char *sha1)
766 {
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;
771 }
772
773 static struct commit **get_bad_and_good_commits(int *rev_nr)
774 {
775         int len = 1 + good_revs.sha1_nr;
776         struct commit **rev = xmalloc(len * sizeof(*rev));
777         int i, n = 0;
778
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;
783
784         return rev;
785 }
786
787 static void handle_bad_merge_base(void)
788 {
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, ' ');
792
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);
797
798                 exit(3);
799         }
800
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);
805 }
806
807 static void handle_skipped_merge_base(const unsigned char *mb)
808 {
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, ' ');
812
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);
820 }
821
822 /*
823  * "check_merge_bases" checks that merge bases are not "bad".
824  *
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.
830  */
831 static void check_merge_bases(void)
832 {
833         struct commit_list *result;
834         int rev_nr;
835         struct commit **rev = get_bad_and_good_commits(&rev_nr);
836
837         result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1, 0);
838
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)));
850                 }
851         }
852
853         free(rev);
854         free_commit_list(result);
855 }
856
857 static int check_ancestors(const char *prefix)
858 {
859         struct rev_info revs;
860         struct object_array pending_copy;
861         int i, res;
862
863         bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
864
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);
871
872         bisect_common(&revs);
873         res = (revs.commits != NULL);
874
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);
879         }
880
881         return res;
882 }
883
884 /*
885  * "check_good_are_ancestors_of_bad" checks that all "good" revs are
886  * ancestor of the "bad" rev.
887  *
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.
891  */
892 static void check_good_are_ancestors_of_bad(const char *prefix)
893 {
894         const char *filename = git_path("BISECT_ANCESTORS_OK");
895         struct stat st;
896         int fd;
897
898         if (!current_bad_sha1)
899                 die("a bad revision is needed");
900
901         /* Check if file BISECT_ANCESTORS_OK exists. */
902         if (!stat(filename, &st) && S_ISREG(st.st_mode))
903                 return;
904
905         /* Bisecting with no good rev is ok. */
906         if (good_revs.sha1_nr == 0)
907                 return;
908
909         /* Check if all good revs are ancestor of the bad rev. */
910         if (check_ancestors(prefix))
911                 check_merge_bases();
912
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);
920 }
921
922 /*
923  * This does "git diff-tree --pretty COMMIT" without one fork+exec.
924  */
925 static void show_diff_tree(const char *prefix, struct commit *commit)
926 {
927         struct rev_info opt;
928
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;
934
935         /* This is what "--pretty" does */
936         opt.verbose_header = 1;
937         opt.use_terminator = 0;
938         opt.commit_format = CMIT_FMT_DEFAULT;
939
940         /* diff-tree init */
941         if (!opt.diffopt.output_format)
942                 opt.diffopt.output_format = DIFF_FORMAT_RAW;
943
944         log_tree_commit(&opt, commit);
945 }
946
947 /*
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.
951  */
952 int bisect_next_all(const char *prefix)
953 {
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];
959
960         if (read_bisect_refs())
961                 die("reading bisect refs failed");
962
963         check_good_are_ancestors_of_bad(prefix);
964
965         bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
966         revs.limited = 1;
967
968         bisect_common(&revs);
969
970         revs.commits = find_bisection(revs.commits, &reaches, &all,
971                                        !!skipped_revs.sha1_nr);
972         revs.commits = managed_skipped(revs.commits, &tried);
973
974         if (!revs.commits) {
975                 /*
976                  * We should exit here only if the "bad"
977                  * commit is also a "skip" commit.
978                  */
979                 exit_if_skipped_commits(tried, NULL);
980
981                 printf("%s was both good and bad\n",
982                        sha1_to_hex(current_bad_sha1));
983                 exit(1);
984         }
985
986         if (!all) {
987                 fprintf(stderr, "No testable commit found.\n"
988                         "Maybe you started with bad path parameters?\n");
989                 exit(4);
990         }
991
992         bisect_rev = revs.commits->item->object.sha1;
993         memcpy(bisect_rev_hex, sha1_to_hex(bisect_rev), 41);
994
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);
1001         }
1002
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"));
1008
1009         return bisect_checkout(bisect_rev_hex);
1010 }
1011