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