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