Documentation/bisect: revise overall content
[git/git.git] / bisect.c
CommitLineData
a2ad79ce
CC
1#include "cache.h"
2#include "commit.h"
3#include "diff.h"
4#include "revision.h"
1bf072e3
CC
5#include "refs.h"
6#include "list-objects.h"
3b437b0d 7#include "quote.h"
4eb5b646 8#include "sha1-lookup.h"
ef24c7ca 9#include "run-command.h"
e22278c0 10#include "log-tree.h"
a2ad79ce 11#include "bisect.h"
902bb364 12#include "sha1-array.h"
8a534b61 13#include "argv-array.h"
6212b1aa 14
fad2d31d 15static struct sha1_array good_revs;
6212b1aa 16static struct sha1_array skipped_revs;
1bf072e3 17
3c5ff995 18static struct object_id *current_bad_oid;
ef24c7ca 19
ef24c7ca
CC
20static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
21static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
fee92fc1 22static const char *argv_update_ref[] = {"update-ref", "--no-deref", "BISECT_HEAD", NULL, NULL};
ef24c7ca 23
208acbfb 24/* Remember to update object flag allocation in object.h */
a2ad79ce
CC
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 */
34static 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
61static 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
72static inline int weight(struct commit_list *elem)
73{
74 return *((int*)(elem->item->util));
75}
76
77static inline void weight_set(struct commit_list *elem, int weight)
78{
79 *((int*)(elem->item->util)) = weight;
80}
81
82static 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
95static 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
119static 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);
56ff3794
CC
133 const char *subject_start;
134 int subject_len;
a2ad79ce
CC
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
56ff3794
CC
149 subject_len = find_commit_subject(buf, &subject_start);
150 if (subject_len)
151 fprintf(stderr, " %.*s", subject_len, subject_start);
a2ad79ce
CC
152 fprintf(stderr, "\n");
153 }
154}
155#endif /* DEBUG_BISECT */
156
157static 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
181struct commit_dist {
182 struct commit *commit;
183 int distance;
184};
185
186static 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
197static 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++) {
662174d2 218 char buf[100]; /* enough for dist=%d */
a2ad79ce
CC
219 struct object *obj = &(array[i].commit->object);
220
662174d2
JK
221 snprintf(buf, sizeof(buf), "dist=%d", array[i].distance);
222 add_name_decoration(DECORATION_NONE, buf, obj);
223
a2ad79ce
CC
224 p->item = array[i].commit;
225 p = p->next;
226 }
227 if (p)
228 p->next = NULL;
229 free(array);
230 return list;
231}
232
233/*
234 * zero or positive weight is the number of interesting commits it can
235 * reach, including itself. Especially, weight = 0 means it does not
236 * reach any tree-changing commits (e.g. just above uninteresting one
237 * but traversal is with pathspec).
238 *
239 * weight = -1 means it has one parent and its distance is yet to
240 * be computed.
241 *
242 * weight = -2 means it has more than one parent and its distance is
243 * unknown. After running count_distance() first, they will get zero
244 * or positive distance.
245 */
246static struct commit_list *do_find_bisection(struct commit_list *list,
247 int nr, int *weights,
248 int find_all)
249{
250 int n, counted;
251 struct commit_list *p;
252
253 counted = 0;
254
255 for (n = 0, p = list; p; p = p->next) {
256 struct commit *commit = p->item;
257 unsigned flags = commit->object.flags;
258
259 p->item->util = &weights[n++];
260 switch (count_interesting_parents(commit)) {
261 case 0:
262 if (!(flags & TREESAME)) {
263 weight_set(p, 1);
264 counted++;
265 show_list("bisection 2 count one",
266 counted, nr, list);
267 }
268 /*
269 * otherwise, it is known not to reach any
270 * tree-changing commit and gets weight 0.
271 */
272 break;
273 case 1:
274 weight_set(p, -1);
275 break;
276 default:
277 weight_set(p, -2);
278 break;
279 }
280 }
281
282 show_list("bisection 2 initialize", counted, nr, list);
283
284 /*
285 * If you have only one parent in the resulting set
286 * then you can reach one commit more than that parent
287 * can reach. So we do not have to run the expensive
288 * count_distance() for single strand of pearls.
289 *
290 * However, if you have more than one parents, you cannot
291 * just add their distance and one for yourself, since
292 * they usually reach the same ancestor and you would
293 * end up counting them twice that way.
294 *
295 * So we will first count distance of merges the usual
296 * way, and then fill the blanks using cheaper algorithm.
297 */
298 for (p = list; p; p = p->next) {
299 if (p->item->object.flags & UNINTERESTING)
300 continue;
301 if (weight(p) != -2)
302 continue;
303 weight_set(p, count_distance(p));
304 clear_distance(list);
305
306 /* Does it happen to be at exactly half-way? */
307 if (!find_all && halfway(p, nr))
308 return p;
309 counted++;
310 }
311
312 show_list("bisection 2 count_distance", counted, nr, list);
313
314 while (counted < nr) {
315 for (p = list; p; p = p->next) {
316 struct commit_list *q;
317 unsigned flags = p->item->object.flags;
318
319 if (0 <= weight(p))
320 continue;
321 for (q = p->item->parents; q; q = q->next) {
322 if (q->item->object.flags & UNINTERESTING)
323 continue;
324 if (0 <= weight(q))
325 break;
326 }
327 if (!q)
328 continue;
329
330 /*
331 * weight for p is unknown but q is known.
332 * add one for p itself if p is to be counted,
333 * otherwise inherit it from q directly.
334 */
335 if (!(flags & TREESAME)) {
336 weight_set(p, weight(q)+1);
337 counted++;
338 show_list("bisection 2 count one",
339 counted, nr, list);
340 }
341 else
342 weight_set(p, weight(q));
343
344 /* Does it happen to be at exactly half-way? */
345 if (!find_all && halfway(p, nr))
346 return p;
347 }
348 }
349
350 show_list("bisection 2 counted all", counted, nr, list);
351
352 if (!find_all)
353 return best_bisection(list, nr);
354 else
355 return best_bisection_sorted(list, nr);
356}
357
358struct commit_list *find_bisection(struct commit_list *list,
359 int *reaches, int *all,
360 int find_all)
361{
362 int nr, on_list;
363 struct commit_list *p, *best, *next, *last;
364 int *weights;
365
366 show_list("bisection 2 entry", 0, 0, list);
367
368 /*
369 * Count the number of total and tree-changing items on the
370 * list, while reversing the list.
371 */
372 for (nr = on_list = 0, last = NULL, p = list;
373 p;
374 p = next) {
375 unsigned flags = p->item->object.flags;
376
377 next = p->next;
378 if (flags & UNINTERESTING)
379 continue;
380 p->next = last;
381 last = p;
382 if (!(flags & TREESAME))
383 nr++;
384 on_list++;
385 }
386 list = last;
387 show_list("bisection 2 sorted", 0, nr, list);
388
389 *all = nr;
390 weights = xcalloc(on_list, sizeof(*weights));
391
392 /* Do the real work of finding bisection commit. */
393 best = do_find_bisection(list, nr, weights, find_all);
394 if (best) {
395 if (!find_all)
396 best->next = NULL;
397 *reaches = weight(best);
398 }
399 free(weights);
400 return best;
401}
402
eed25148 403static int register_ref(const char *refname, const struct object_id *oid,
1bf072e3
CC
404 int flags, void *cb_data)
405{
406 if (!strcmp(refname, "bad")) {
3c5ff995 407 current_bad_oid = xmalloc(sizeof(*current_bad_oid));
eed25148 408 oidcpy(current_bad_oid, oid);
59556548 409 } else if (starts_with(refname, "good-")) {
eed25148 410 sha1_array_append(&good_revs, oid->hash);
59556548 411 } else if (starts_with(refname, "skip-")) {
eed25148 412 sha1_array_append(&skipped_revs, oid->hash);
1bf072e3
CC
413 }
414
415 return 0;
416}
417
418static int read_bisect_refs(void)
419{
eed25148 420 return for_each_ref_in("refs/bisect/", register_ref, NULL);
1bf072e3
CC
421}
422
2af202be 423static void read_bisect_paths(struct argv_array *array)
3b437b0d
CC
424{
425 struct strbuf str = STRBUF_INIT;
426 const char *filename = git_path("BISECT_NAMES");
427 FILE *fp = fopen(filename, "r");
428
429 if (!fp)
d824cbba 430 die_errno("Could not open file '%s'", filename);
3b437b0d
CC
431
432 while (strbuf_getline(&str, fp, '\n') != EOF) {
3b437b0d 433 strbuf_trim(&str);
8a534b61 434 if (sq_dequote_to_argv_array(str.buf, array))
3b437b0d 435 die("Badly quoted content in file '%s': %s",
8a534b61 436 filename, str.buf);
3b437b0d
CC
437 }
438
439 strbuf_release(&str);
440 fclose(fp);
441}
442
c0537662
CC
443static char *join_sha1_array_hex(struct sha1_array *array, char delim)
444{
445 struct strbuf joined_hexs = STRBUF_INIT;
446 int i;
447
902bb364 448 for (i = 0; i < array->nr; i++) {
c0537662 449 strbuf_addstr(&joined_hexs, sha1_to_hex(array->sha1[i]));
902bb364 450 if (i + 1 < array->nr)
c0537662
CC
451 strbuf_addch(&joined_hexs, delim);
452 }
453
454 return strbuf_detach(&joined_hexs, NULL);
455}
456
9af3589e
CC
457/*
458 * In this function, passing a not NULL skipped_first is very special.
459 * It means that we want to know if the first commit in the list is
460 * skipped because we will want to test a commit away from it if it is
461 * indeed skipped.
462 * So if the first commit is skipped, we cannot take the shortcut to
463 * just "return list" when we find the first non skipped commit, we
464 * have to return a fully filtered list.
465 *
466 * We use (*skipped_first == -1) to mean "it has been found that the
467 * first commit is not skipped". In this case *skipped_first is set back
468 * to 0 just before the function returns.
469 */
95188648
CC
470struct commit_list *filter_skipped(struct commit_list *list,
471 struct commit_list **tried,
9af3589e
CC
472 int show_all,
473 int *count,
474 int *skipped_first)
95188648
CC
475{
476 struct commit_list *filtered = NULL, **f = &filtered;
477
478 *tried = NULL;
479
9af3589e
CC
480 if (skipped_first)
481 *skipped_first = 0;
482 if (count)
483 *count = 0;
484
902bb364 485 if (!skipped_revs.nr)
95188648
CC
486 return list;
487
95188648
CC
488 while (list) {
489 struct commit_list *next = list->next;
490 list->next = NULL;
902bb364 491 if (0 <= sha1_array_lookup(&skipped_revs,
aaaff9e2 492 list->item->object.sha1)) {
9af3589e
CC
493 if (skipped_first && !*skipped_first)
494 *skipped_first = 1;
95188648
CC
495 /* Move current to tried list */
496 *tried = list;
497 tried = &list->next;
498 } else {
9af3589e
CC
499 if (!show_all) {
500 if (!skipped_first || !*skipped_first)
501 return list;
502 } else if (skipped_first && !*skipped_first) {
503 /* This means we know it's not skipped */
504 *skipped_first = -1;
505 }
95188648
CC
506 /* Move current to filtered list */
507 *f = list;
508 f = &list->next;
9af3589e
CC
509 if (count)
510 (*count)++;
95188648
CC
511 }
512 list = next;
513 }
514
9af3589e
CC
515 if (skipped_first && *skipped_first == -1)
516 *skipped_first = 0;
517
95188648
CC
518 return filtered;
519}
1bf072e3 520
ebc9529f
CC
521#define PRN_MODULO 32768
522
523/*
524 * This is a pseudo random number generator based on "man 3 rand".
525 * It is not used properly because the seed is the argument and it
526 * is increased by one between each call, but that should not matter
527 * for this application.
528 */
7b96d888 529static unsigned get_prn(unsigned count) {
ebc9529f 530 count = count * 1103515245 + 12345;
7b96d888 531 return (count/65536) % PRN_MODULO;
ebc9529f
CC
532}
533
534/*
535 * Custom integer square root from
536 * http://en.wikipedia.org/wiki/Integer_square_root
537 */
538static int sqrti(int val)
539{
540 float d, x = val;
541
542 if (val == 0)
543 return 0;
544
545 do {
546 float y = (x + (float)val / x) / 2;
547 d = (y > x) ? y - x : x - y;
548 x = y;
549 } while (d >= 0.5);
550
551 return (int)x;
552}
553
554static struct commit_list *skip_away(struct commit_list *list, int count)
62d0b0da 555{
62d0b0da 556 struct commit_list *cur, *previous;
ebc9529f
CC
557 int prn, index, i;
558
559 prn = get_prn(count);
560 index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
62d0b0da
CC
561
562 cur = list;
563 previous = NULL;
62d0b0da
CC
564
565 for (i = 0; cur; cur = cur->next, i++) {
566 if (i == index) {
3c5ff995 567 if (hashcmp(cur->item->object.sha1, current_bad_oid->hash))
62d0b0da
CC
568 return cur;
569 if (previous)
570 return previous;
571 return list;
572 }
573 previous = cur;
574 }
575
576 return list;
577}
578
579static struct commit_list *managed_skipped(struct commit_list *list,
580 struct commit_list **tried)
581{
582 int count, skipped_first;
62d0b0da
CC
583
584 *tried = NULL;
585
902bb364 586 if (!skipped_revs.nr)
62d0b0da
CC
587 return list;
588
589 list = filter_skipped(list, tried, 0, &count, &skipped_first);
590
591 if (!skipped_first)
592 return list;
593
ebc9529f 594 return skip_away(list, count);
62d0b0da
CC
595}
596
a22347c6
CC
597static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
598 const char *bad_format, const char *good_format,
599 int read_paths)
1bf072e3 600{
8a534b61 601 struct argv_array rev_argv = ARGV_ARRAY_INIT;
fad2d31d
CC
602 int i;
603
3b437b0d
CC
604 init_revisions(revs, prefix);
605 revs->abbrev = 0;
606 revs->commit_format = CMIT_FMT_UNSPECIFIED;
1bf072e3 607
1c953a1f 608 /* rev_argv.argv[0] will be ignored by setup_revisions */
8a534b61 609 argv_array_push(&rev_argv, "bisect_rev_setup");
3c5ff995 610 argv_array_pushf(&rev_argv, bad_format, oid_to_hex(current_bad_oid));
902bb364 611 for (i = 0; i < good_revs.nr; i++)
8a534b61
JK
612 argv_array_pushf(&rev_argv, good_format,
613 sha1_to_hex(good_revs.sha1[i]));
614 argv_array_push(&rev_argv, "--");
a22347c6
CC
615 if (read_paths)
616 read_bisect_paths(&rev_argv);
3b437b0d 617
8a534b61
JK
618 setup_revisions(rev_argv.argc, rev_argv.argv, revs, NULL);
619 /* XXX leak rev_argv, as "revs" may still be pointing to it */
3b437b0d
CC
620}
621
a22347c6 622static void bisect_common(struct rev_info *revs)
2ace9727 623{
2ace9727
CC
624 if (prepare_revision_walk(revs))
625 die("revision walk setup failed");
626 if (revs->tree_objects)
e76a5fb4 627 mark_edges_uninteresting(revs, NULL);
2ace9727
CC
628}
629
ef24c7ca 630static void exit_if_skipped_commits(struct commit_list *tried,
3c5ff995 631 const struct object_id *bad)
ef24c7ca
CC
632{
633 if (!tried)
634 return;
635
636 printf("There are only 'skip'ped commits left to test.\n"
637 "The first bad commit could be any of:\n");
638 print_commit_list(tried, "%s\n", "%s\n");
639 if (bad)
3c5ff995 640 printf("%s\n", oid_to_hex(bad));
ef24c7ca
CC
641 printf("We cannot bisect more!\n");
642 exit(2);
643}
644
3c5ff995 645static int is_expected_rev(const struct object_id *oid)
c0537662
CC
646{
647 const char *filename = git_path("BISECT_EXPECTED_REV");
648 struct stat st;
649 struct strbuf str = STRBUF_INIT;
650 FILE *fp;
651 int res = 0;
652
653 if (stat(filename, &st) || !S_ISREG(st.st_mode))
654 return 0;
655
656 fp = fopen(filename, "r");
657 if (!fp)
658 return 0;
659
660 if (strbuf_getline(&str, fp, '\n') != EOF)
3c5ff995 661 res = !strcmp(str.buf, oid_to_hex(oid));
c0537662
CC
662
663 strbuf_release(&str);
664 fclose(fp);
665
666 return res;
667}
668
ef24c7ca
CC
669static void mark_expected_rev(char *bisect_rev_hex)
670{
671 int len = strlen(bisect_rev_hex);
672 const char *filename = git_path("BISECT_EXPECTED_REV");
673 int fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
674
675 if (fd < 0)
d824cbba 676 die_errno("could not create file '%s'", filename);
ef24c7ca
CC
677
678 bisect_rev_hex[len] = '\n';
679 write_or_die(fd, bisect_rev_hex, len + 1);
680 bisect_rev_hex[len] = '\0';
681
682 if (close(fd) < 0)
683 die("closing file %s: %s", filename, strerror(errno));
684}
685
fee92fc1 686static int bisect_checkout(char *bisect_rev_hex, int no_checkout)
ef24c7ca 687{
ef24c7ca
CC
688
689 mark_expected_rev(bisect_rev_hex);
690
691 argv_checkout[2] = bisect_rev_hex;
fee92fc1
JS
692 if (no_checkout) {
693 argv_update_ref[3] = bisect_rev_hex;
694 if (run_command_v_opt(argv_update_ref, RUN_GIT_CMD))
695 die("update-ref --no-deref HEAD failed on %s",
696 bisect_rev_hex);
697 } else {
4824d1b8 698 int res;
fee92fc1
JS
699 res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
700 if (res)
701 exit(res);
702 }
ef24c7ca
CC
703
704 argv_show_branch[1] = bisect_rev_hex;
705 return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
706}
707
c0537662
CC
708static struct commit *get_commit_reference(const unsigned char *sha1)
709{
710 struct commit *r = lookup_commit_reference(sha1);
711 if (!r)
712 die("Not a valid commit name %s", sha1_to_hex(sha1));
713 return r;
714}
715
716static struct commit **get_bad_and_good_commits(int *rev_nr)
717{
902bb364 718 int len = 1 + good_revs.nr;
c0537662
CC
719 struct commit **rev = xmalloc(len * sizeof(*rev));
720 int i, n = 0;
721
3c5ff995 722 rev[n++] = get_commit_reference(current_bad_oid->hash);
902bb364 723 for (i = 0; i < good_revs.nr; i++)
c0537662
CC
724 rev[n++] = get_commit_reference(good_revs.sha1[i]);
725 *rev_nr = n;
726
727 return rev;
728}
729
730static void handle_bad_merge_base(void)
731{
3c5ff995 732 if (is_expected_rev(current_bad_oid)) {
733 char *bad_hex = oid_to_hex(current_bad_oid);
c0537662
CC
734 char *good_hex = join_sha1_array_hex(&good_revs, ' ');
735
736 fprintf(stderr, "The merge base %s is bad.\n"
737 "This means the bug has been fixed "
738 "between %s and [%s].\n",
739 bad_hex, bad_hex, good_hex);
740
741 exit(3);
742 }
743
744 fprintf(stderr, "Some good revs are not ancestor of the bad rev.\n"
745 "git bisect cannot work properly in this case.\n"
f6216c2c 746 "Maybe you mistook good and bad revs?\n");
c0537662
CC
747 exit(1);
748}
749
2af202be 750static void handle_skipped_merge_base(const unsigned char *mb)
c0537662
CC
751{
752 char *mb_hex = sha1_to_hex(mb);
3c5ff995 753 char *bad_hex = sha1_to_hex(current_bad_oid->hash);
c0537662
CC
754 char *good_hex = join_sha1_array_hex(&good_revs, ' ');
755
bd757c18 756 warning("the merge base between %s and [%s] "
c0537662
CC
757 "must be skipped.\n"
758 "So we cannot be sure the first bad commit is "
759 "between %s and %s.\n"
bd757c18 760 "We continue anyway.",
c0537662
CC
761 bad_hex, good_hex, mb_hex, bad_hex);
762 free(good_hex);
763}
764
765/*
766 * "check_merge_bases" checks that merge bases are not "bad".
767 *
768 * - If one is "bad", it means the user assumed something wrong
769 * and we must exit with a non 0 error code.
770 * - If one is "good", that's good, we have nothing to do.
771 * - If one is "skipped", we can't know but we should warn.
772 * - If we don't know, we should check it out and ask the user to test.
773 */
fee92fc1 774static void check_merge_bases(int no_checkout)
c0537662
CC
775{
776 struct commit_list *result;
777 int rev_nr;
778 struct commit **rev = get_bad_and_good_commits(&rev_nr);
779
2ce406cc 780 result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1);
c0537662
CC
781
782 for (; result; result = result->next) {
783 const unsigned char *mb = result->item->object.sha1;
3c5ff995 784 if (!hashcmp(mb, current_bad_oid->hash)) {
c0537662 785 handle_bad_merge_base();
902bb364 786 } else if (0 <= sha1_array_lookup(&good_revs, mb)) {
c0537662 787 continue;
902bb364 788 } else if (0 <= sha1_array_lookup(&skipped_revs, mb)) {
c0537662
CC
789 handle_skipped_merge_base(mb);
790 } else {
791 printf("Bisecting: a merge base must be tested\n");
fee92fc1 792 exit(bisect_checkout(sha1_to_hex(mb), no_checkout));
c0537662
CC
793 }
794 }
795
796 free(rev);
797 free_commit_list(result);
798}
799
2d938fc7 800static int check_ancestors(const char *prefix)
d937d4ac 801{
2d938fc7
CC
802 struct rev_info revs;
803 struct object_array pending_copy;
86a0a408 804 int res;
d937d4ac 805
2d938fc7 806 bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
d937d4ac 807
2d938fc7 808 /* Save pending objects, so they can be cleaned up later. */
353f5657
RS
809 pending_copy = revs.pending;
810 revs.leak_pending = 1;
2d938fc7 811
353f5657
RS
812 /*
813 * bisect_common calls prepare_revision_walk right away, which
814 * (together with .leak_pending = 1) makes us the sole owner of
815 * the list of pending objects.
816 */
2d938fc7
CC
817 bisect_common(&revs);
818 res = (revs.commits != NULL);
819
820 /* Clean up objects used, as they will be reused. */
86a0a408 821 clear_commit_marks_for_object_array(&pending_copy, ALL_REV_FLAGS);
353f5657 822 free(pending_copy.objects);
d937d4ac 823
2d938fc7 824 return res;
d937d4ac
CC
825}
826
827/*
828 * "check_good_are_ancestors_of_bad" checks that all "good" revs are
829 * ancestor of the "bad" rev.
830 *
831 * If that's not the case, we need to check the merge bases.
832 * If a merge base must be tested by the user, its source code will be
833 * checked out to be tested by the user and we will exit.
834 */
fee92fc1 835static void check_good_are_ancestors_of_bad(const char *prefix, int no_checkout)
d937d4ac 836{
d292bfaf 837 char *filename = git_pathdup("BISECT_ANCESTORS_OK");
d937d4ac
CC
838 struct stat st;
839 int fd;
840
3c5ff995 841 if (!current_bad_oid)
d937d4ac
CC
842 die("a bad revision is needed");
843
844 /* Check if file BISECT_ANCESTORS_OK exists. */
845 if (!stat(filename, &st) && S_ISREG(st.st_mode))
144e7090 846 goto done;
d937d4ac
CC
847
848 /* Bisecting with no good rev is ok. */
902bb364 849 if (good_revs.nr == 0)
144e7090 850 goto done;
d937d4ac 851
2d938fc7
CC
852 /* Check if all good revs are ancestor of the bad rev. */
853 if (check_ancestors(prefix))
fee92fc1 854 check_merge_bases(no_checkout);
d937d4ac
CC
855
856 /* Create file BISECT_ANCESTORS_OK. */
857 fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
858 if (fd < 0)
859 warning("could not create file '%s': %s",
860 filename, strerror(errno));
861 else
862 close(fd);
144e7090
MH
863 done:
864 free(filename);
d937d4ac
CC
865}
866
e22278c0
CC
867/*
868 * This does "git diff-tree --pretty COMMIT" without one fork+exec.
869 */
870static void show_diff_tree(const char *prefix, struct commit *commit)
871{
872 struct rev_info opt;
873
874 /* diff-tree init */
875 init_revisions(&opt, prefix);
876 git_config(git_diff_basic_config, NULL); /* no "diff" UI options */
877 opt.abbrev = 0;
878 opt.diff = 1;
879
880 /* This is what "--pretty" does */
881 opt.verbose_header = 1;
882 opt.use_terminator = 0;
883 opt.commit_format = CMIT_FMT_DEFAULT;
884
885 /* diff-tree init */
886 if (!opt.diffopt.output_format)
887 opt.diffopt.output_format = DIFF_FORMAT_RAW;
888
889 log_tree_commit(&opt, commit);
890}
891
ef24c7ca
CC
892/*
893 * We use the convention that exiting with an exit code 10 means that
894 * the bisection process finished successfully.
895 * In this case the calling shell script should exit 0.
fee92fc1
JS
896 *
897 * If no_checkout is non-zero, the bisection process does not
898 * checkout the trial commit but instead simply updates BISECT_HEAD.
ef24c7ca 899 */
fee92fc1 900int bisect_next_all(const char *prefix, int no_checkout)
ef24c7ca
CC
901{
902 struct rev_info revs;
903 struct commit_list *tried;
6329bade 904 int reaches = 0, all = 0, nr, steps;
ef24c7ca 905 const unsigned char *bisect_rev;
3c5ff995 906 char bisect_rev_hex[GIT_SHA1_HEXSZ + 1];
ef24c7ca 907
2b020695
CC
908 if (read_bisect_refs())
909 die("reading bisect refs failed");
910
fee92fc1 911 check_good_are_ancestors_of_bad(prefix, no_checkout);
0871984d 912
a22347c6
CC
913 bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
914 revs.limited = 1;
2b020695 915
a22347c6 916 bisect_common(&revs);
ef24c7ca 917
a22347c6 918 revs.commits = find_bisection(revs.commits, &reaches, &all,
902bb364 919 !!skipped_revs.nr);
62d0b0da 920 revs.commits = managed_skipped(revs.commits, &tried);
ef24c7ca
CC
921
922 if (!revs.commits) {
923 /*
924 * We should exit here only if the "bad"
925 * commit is also a "skip" commit.
926 */
927 exit_if_skipped_commits(tried, NULL);
928
929 printf("%s was both good and bad\n",
3c5ff995 930 oid_to_hex(current_bad_oid));
ef24c7ca
CC
931 exit(1);
932 }
933
8f69f72f
CC
934 if (!all) {
935 fprintf(stderr, "No testable commit found.\n"
936 "Maybe you started with bad path parameters?\n");
937 exit(4);
938 }
939
ef24c7ca 940 bisect_rev = revs.commits->item->object.sha1;
3c5ff995 941 memcpy(bisect_rev_hex, sha1_to_hex(bisect_rev), GIT_SHA1_HEXSZ + 1);
ef24c7ca 942
3c5ff995 943 if (!hashcmp(bisect_rev, current_bad_oid->hash)) {
944 exit_if_skipped_commits(tried, current_bad_oid);
21d0bc2f 945 printf("%s is the first bad commit\n", bisect_rev_hex);
e22278c0 946 show_diff_tree(prefix, revs.commits->item);
ef24c7ca
CC
947 /* This means the bisection process succeeded. */
948 exit(10);
949 }
950
951 nr = all - reaches - 1;
6329bade
DR
952 steps = estimate_bisect_steps(all);
953 printf("Bisecting: %d revision%s left to test after this "
954 "(roughly %d step%s)\n", nr, (nr == 1 ? "" : "s"),
955 steps, (steps == 1 ? "" : "s"));
ef24c7ca 956
fee92fc1 957 return bisect_checkout(bisect_rev_hex, no_checkout);
ef24c7ca
CC
958}
959
c43cb386
NTND
960static inline int log2i(int n)
961{
962 int log2 = 0;
963
964 for (; n > 1; n >>= 1)
965 log2++;
966
967 return log2;
968}
969
970static inline int exp2i(int n)
971{
972 return 1 << n;
973}
974
975/*
976 * Estimate the number of bisect steps left (after the current step)
977 *
978 * For any x between 0 included and 2^n excluded, the probability for
979 * n - 1 steps left looks like:
980 *
981 * P(2^n + x) == (2^n - x) / (2^n + x)
982 *
983 * and P(2^n + x) < 0.5 means 2^n < 3x
984 */
985int estimate_bisect_steps(int all)
986{
987 int n, x, e;
988
989 if (all < 3)
990 return 0;
991
992 n = log2i(all);
993 e = exp2i(n);
994 x = all - e;
995
996 return (e < 3 * x) ? n : n - 1;
997}