bisect.con commit Merge branch 'jk/consistent-h' (50ad856)
   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 oid_array good_revs;
  16static struct oid_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        struct strbuf buf = STRBUF_INIT;
 204        int cnt, i;
 205
 206        for (p = list, cnt = 0; p; p = p->next) {
 207                int distance;
 208                unsigned flags = p->item->object.flags;
 209
 210                if (flags & TREESAME)
 211                        continue;
 212                distance = weight(p);
 213                if (nr - distance < distance)
 214                        distance = nr - distance;
 215                array[cnt].commit = p->item;
 216                array[cnt].distance = distance;
 217                cnt++;
 218        }
 219        QSORT(array, cnt, compare_commit_dist);
 220        for (p = list, i = 0; i < cnt; i++) {
 221                struct object *obj = &(array[i].commit->object);
 222
 223                strbuf_reset(&buf);
 224                strbuf_addf(&buf, "dist=%d", array[i].distance);
 225                add_name_decoration(DECORATION_NONE, buf.buf, obj);
 226
 227                p->item = array[i].commit;
 228                p = p->next;
 229        }
 230        if (p)
 231                p->next = NULL;
 232        strbuf_release(&buf);
 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 */
 250static 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
 362struct 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
 407static int register_ref(const char *refname, const struct object_id *oid,
 408                        int flags, void *cb_data)
 409{
 410        struct strbuf good_prefix = STRBUF_INIT;
 411        strbuf_addstr(&good_prefix, term_good);
 412        strbuf_addstr(&good_prefix, "-");
 413
 414        if (!strcmp(refname, term_bad)) {
 415                current_bad_oid = xmalloc(sizeof(*current_bad_oid));
 416                oidcpy(current_bad_oid, oid);
 417        } else if (starts_with(refname, good_prefix.buf)) {
 418                oid_array_append(&good_revs, oid);
 419        } else if (starts_with(refname, "skip-")) {
 420                oid_array_append(&skipped_revs, oid);
 421        }
 422
 423        strbuf_release(&good_prefix);
 424
 425        return 0;
 426}
 427
 428static int read_bisect_refs(void)
 429{
 430        return for_each_ref_in("refs/bisect/", register_ref, NULL);
 431}
 432
 433static GIT_PATH_FUNC(git_path_bisect_names, "BISECT_NAMES")
 434static GIT_PATH_FUNC(git_path_bisect_expected_rev, "BISECT_EXPECTED_REV")
 435static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS")
 436
 437static void read_bisect_paths(struct argv_array *array)
 438{
 439        struct strbuf str = STRBUF_INIT;
 440        const char *filename = git_path_bisect_names();
 441        FILE *fp = xfopen(filename, "r");
 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 oid_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, oid_to_hex(array->oid + 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 <= oid_array_lookup(&skipped_revs, &list->item->object.oid)) {
 503                        if (skipped_first && !*skipped_first)
 504                                *skipped_first = 1;
 505                        /* Move current to tried list */
 506                        *tried = list;
 507                        tried = &list->next;
 508                } else {
 509                        if (!show_all) {
 510                                if (!skipped_first || !*skipped_first)
 511                                        return list;
 512                        } else if (skipped_first && !*skipped_first) {
 513                                /* This means we know it's not skipped */
 514                                *skipped_first = -1;
 515                        }
 516                        /* Move current to filtered list */
 517                        *f = list;
 518                        f = &list->next;
 519                        if (count)
 520                                (*count)++;
 521                }
 522                list = next;
 523        }
 524
 525        if (skipped_first && *skipped_first == -1)
 526                *skipped_first = 0;
 527
 528        return filtered;
 529}
 530
 531#define PRN_MODULO 32768
 532
 533/*
 534 * This is a pseudo random number generator based on "man 3 rand".
 535 * It is not used properly because the seed is the argument and it
 536 * is increased by one between each call, but that should not matter
 537 * for this application.
 538 */
 539static unsigned get_prn(unsigned count) {
 540        count = count * 1103515245 + 12345;
 541        return (count/65536) % PRN_MODULO;
 542}
 543
 544/*
 545 * Custom integer square root from
 546 * https://en.wikipedia.org/wiki/Integer_square_root
 547 */
 548static int sqrti(int val)
 549{
 550        float d, x = val;
 551
 552        if (val == 0)
 553                return 0;
 554
 555        do {
 556                float y = (x + (float)val / x) / 2;
 557                d = (y > x) ? y - x : x - y;
 558                x = y;
 559        } while (d >= 0.5);
 560
 561        return (int)x;
 562}
 563
 564static struct commit_list *skip_away(struct commit_list *list, int count)
 565{
 566        struct commit_list *cur, *previous;
 567        int prn, index, i;
 568
 569        prn = get_prn(count);
 570        index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
 571
 572        cur = list;
 573        previous = NULL;
 574
 575        for (i = 0; cur; cur = cur->next, i++) {
 576                if (i == index) {
 577                        if (oidcmp(&cur->item->object.oid, current_bad_oid))
 578                                return cur;
 579                        if (previous)
 580                                return previous;
 581                        return list;
 582                }
 583                previous = cur;
 584        }
 585
 586        return list;
 587}
 588
 589static struct commit_list *managed_skipped(struct commit_list *list,
 590                                           struct commit_list **tried)
 591{
 592        int count, skipped_first;
 593
 594        *tried = NULL;
 595
 596        if (!skipped_revs.nr)
 597                return list;
 598
 599        list = filter_skipped(list, tried, 0, &count, &skipped_first);
 600
 601        if (!skipped_first)
 602                return list;
 603
 604        return skip_away(list, count);
 605}
 606
 607static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
 608                             const char *bad_format, const char *good_format,
 609                             int read_paths)
 610{
 611        struct argv_array rev_argv = ARGV_ARRAY_INIT;
 612        int i;
 613
 614        init_revisions(revs, prefix);
 615        revs->abbrev = 0;
 616        revs->commit_format = CMIT_FMT_UNSPECIFIED;
 617
 618        /* rev_argv.argv[0] will be ignored by setup_revisions */
 619        argv_array_push(&rev_argv, "bisect_rev_setup");
 620        argv_array_pushf(&rev_argv, bad_format, oid_to_hex(current_bad_oid));
 621        for (i = 0; i < good_revs.nr; i++)
 622                argv_array_pushf(&rev_argv, good_format,
 623                                 oid_to_hex(good_revs.oid + i));
 624        argv_array_push(&rev_argv, "--");
 625        if (read_paths)
 626                read_bisect_paths(&rev_argv);
 627
 628        setup_revisions(rev_argv.argc, rev_argv.argv, revs, NULL);
 629        /* XXX leak rev_argv, as "revs" may still be pointing to it */
 630}
 631
 632static void bisect_common(struct rev_info *revs)
 633{
 634        if (prepare_revision_walk(revs))
 635                die("revision walk setup failed");
 636        if (revs->tree_objects)
 637                mark_edges_uninteresting(revs, NULL);
 638}
 639
 640static void exit_if_skipped_commits(struct commit_list *tried,
 641                                    const struct object_id *bad)
 642{
 643        if (!tried)
 644                return;
 645
 646        printf("There are only 'skip'ped commits left to test.\n"
 647               "The first %s commit could be any of:\n", term_bad);
 648
 649        for ( ; tried; tried = tried->next)
 650                printf("%s\n", oid_to_hex(&tried->item->object.oid));
 651
 652        if (bad)
 653                printf("%s\n", oid_to_hex(bad));
 654        printf(_("We cannot bisect more!\n"));
 655        exit(2);
 656}
 657
 658static int is_expected_rev(const struct object_id *oid)
 659{
 660        const char *filename = git_path_bisect_expected_rev();
 661        struct stat st;
 662        struct strbuf str = STRBUF_INIT;
 663        FILE *fp;
 664        int res = 0;
 665
 666        if (stat(filename, &st) || !S_ISREG(st.st_mode))
 667                return 0;
 668
 669        fp = fopen_or_warn(filename, "r");
 670        if (!fp)
 671                return 0;
 672
 673        if (strbuf_getline_lf(&str, fp) != EOF)
 674                res = !strcmp(str.buf, oid_to_hex(oid));
 675
 676        strbuf_release(&str);
 677        fclose(fp);
 678
 679        return res;
 680}
 681
 682static int bisect_checkout(const unsigned char *bisect_rev, int no_checkout)
 683{
 684        char bisect_rev_hex[GIT_MAX_HEXSZ + 1];
 685
 686        memcpy(bisect_rev_hex, sha1_to_hex(bisect_rev), GIT_SHA1_HEXSZ + 1);
 687        update_ref(NULL, "BISECT_EXPECTED_REV", bisect_rev, NULL, 0, UPDATE_REFS_DIE_ON_ERR);
 688
 689        argv_checkout[2] = bisect_rev_hex;
 690        if (no_checkout) {
 691                update_ref(NULL, "BISECT_HEAD", bisect_rev, NULL, 0, UPDATE_REFS_DIE_ON_ERR);
 692        } else {
 693                int res;
 694                res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
 695                if (res)
 696                        exit(res);
 697        }
 698
 699        argv_show_branch[1] = bisect_rev_hex;
 700        return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
 701}
 702
 703static struct commit *get_commit_reference(const struct object_id *oid)
 704{
 705        struct commit *r = lookup_commit_reference(oid);
 706        if (!r)
 707                die(_("Not a valid commit name %s"), oid_to_hex(oid));
 708        return r;
 709}
 710
 711static struct commit **get_bad_and_good_commits(int *rev_nr)
 712{
 713        struct commit **rev;
 714        int i, n = 0;
 715
 716        ALLOC_ARRAY(rev, 1 + good_revs.nr);
 717        rev[n++] = get_commit_reference(current_bad_oid);
 718        for (i = 0; i < good_revs.nr; i++)
 719                rev[n++] = get_commit_reference(good_revs.oid + i);
 720        *rev_nr = n;
 721
 722        return rev;
 723}
 724
 725static void handle_bad_merge_base(void)
 726{
 727        if (is_expected_rev(current_bad_oid)) {
 728                char *bad_hex = oid_to_hex(current_bad_oid);
 729                char *good_hex = join_sha1_array_hex(&good_revs, ' ');
 730                if (!strcmp(term_bad, "bad") && !strcmp(term_good, "good")) {
 731                        fprintf(stderr, _("The merge base %s is bad.\n"
 732                                "This means the bug has been fixed "
 733                                "between %s and [%s].\n"),
 734                                bad_hex, bad_hex, good_hex);
 735                } else if (!strcmp(term_bad, "new") && !strcmp(term_good, "old")) {
 736                        fprintf(stderr, _("The merge base %s is new.\n"
 737                                "The property has changed "
 738                                "between %s and [%s].\n"),
 739                                bad_hex, bad_hex, good_hex);
 740                } else {
 741                        fprintf(stderr, _("The merge base %s is %s.\n"
 742                                "This means the first '%s' commit is "
 743                                "between %s and [%s].\n"),
 744                                bad_hex, term_bad, term_good, bad_hex, good_hex);
 745                }
 746                exit(3);
 747        }
 748
 749        fprintf(stderr, _("Some %s revs are not ancestors of the %s rev.\n"
 750                "git bisect cannot work properly in this case.\n"
 751                "Maybe you mistook %s and %s revs?\n"),
 752                term_good, term_bad, term_good, term_bad);
 753        exit(1);
 754}
 755
 756static void handle_skipped_merge_base(const struct object_id *mb)
 757{
 758        char *mb_hex = oid_to_hex(mb);
 759        char *bad_hex = oid_to_hex(current_bad_oid);
 760        char *good_hex = join_sha1_array_hex(&good_revs, ' ');
 761
 762        warning(_("the merge base between %s and [%s] "
 763                "must be skipped.\n"
 764                "So we cannot be sure the first %s commit is "
 765                "between %s and %s.\n"
 766                "We continue anyway."),
 767                bad_hex, good_hex, term_bad, mb_hex, bad_hex);
 768        free(good_hex);
 769}
 770
 771/*
 772 * "check_merge_bases" checks that merge bases are not "bad" (or "new").
 773 *
 774 * - If one is "bad" (or "new"), it means the user assumed something wrong
 775 * and we must exit with a non 0 error code.
 776 * - If one is "good" (or "old"), that's good, we have nothing to do.
 777 * - If one is "skipped", we can't know but we should warn.
 778 * - If we don't know, we should check it out and ask the user to test.
 779 */
 780static void check_merge_bases(int no_checkout)
 781{
 782        struct commit_list *result;
 783        int rev_nr;
 784        struct commit **rev = get_bad_and_good_commits(&rev_nr);
 785
 786        result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1);
 787
 788        for (; result; result = result->next) {
 789                const struct object_id *mb = &result->item->object.oid;
 790                if (!oidcmp(mb, current_bad_oid)) {
 791                        handle_bad_merge_base();
 792                } else if (0 <= oid_array_lookup(&good_revs, mb)) {
 793                        continue;
 794                } else if (0 <= oid_array_lookup(&skipped_revs, mb)) {
 795                        handle_skipped_merge_base(mb);
 796                } else {
 797                        printf(_("Bisecting: a merge base must be tested\n"));
 798                        exit(bisect_checkout(mb->hash, no_checkout));
 799                }
 800        }
 801
 802        free(rev);
 803        free_commit_list(result);
 804}
 805
 806static int check_ancestors(const char *prefix)
 807{
 808        struct rev_info revs;
 809        struct object_array pending_copy;
 810        int res;
 811
 812        bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
 813
 814        /* Save pending objects, so they can be cleaned up later. */
 815        pending_copy = revs.pending;
 816        revs.leak_pending = 1;
 817
 818        /*
 819         * bisect_common calls prepare_revision_walk right away, which
 820         * (together with .leak_pending = 1) makes us the sole owner of
 821         * the list of pending objects.
 822         */
 823        bisect_common(&revs);
 824        res = (revs.commits != NULL);
 825
 826        /* Clean up objects used, as they will be reused. */
 827        clear_commit_marks_for_object_array(&pending_copy, ALL_REV_FLAGS);
 828        free(pending_copy.objects);
 829
 830        return res;
 831}
 832
 833/*
 834 * "check_good_are_ancestors_of_bad" checks that all "good" revs are
 835 * ancestor of the "bad" rev.
 836 *
 837 * If that's not the case, we need to check the merge bases.
 838 * If a merge base must be tested by the user, its source code will be
 839 * checked out to be tested by the user and we will exit.
 840 */
 841static void check_good_are_ancestors_of_bad(const char *prefix, int no_checkout)
 842{
 843        char *filename = git_pathdup("BISECT_ANCESTORS_OK");
 844        struct stat st;
 845        int fd;
 846
 847        if (!current_bad_oid)
 848                die(_("a %s revision is needed"), term_bad);
 849
 850        /* Check if file BISECT_ANCESTORS_OK exists. */
 851        if (!stat(filename, &st) && S_ISREG(st.st_mode))
 852                goto done;
 853
 854        /* Bisecting with no good rev is ok. */
 855        if (good_revs.nr == 0)
 856                goto done;
 857
 858        /* Check if all good revs are ancestor of the bad rev. */
 859        if (check_ancestors(prefix))
 860                check_merge_bases(no_checkout);
 861
 862        /* Create file BISECT_ANCESTORS_OK. */
 863        fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
 864        if (fd < 0)
 865                warning_errno(_("could not create file '%s'"),
 866                              filename);
 867        else
 868                close(fd);
 869 done:
 870        free(filename);
 871}
 872
 873/*
 874 * This does "git diff-tree --pretty COMMIT" without one fork+exec.
 875 */
 876static void show_diff_tree(const char *prefix, struct commit *commit)
 877{
 878        struct rev_info opt;
 879
 880        /* diff-tree init */
 881        init_revisions(&opt, prefix);
 882        git_config(git_diff_basic_config, NULL); /* no "diff" UI options */
 883        opt.abbrev = 0;
 884        opt.diff = 1;
 885
 886        /* This is what "--pretty" does */
 887        opt.verbose_header = 1;
 888        opt.use_terminator = 0;
 889        opt.commit_format = CMIT_FMT_DEFAULT;
 890
 891        /* diff-tree init */
 892        if (!opt.diffopt.output_format)
 893                opt.diffopt.output_format = DIFF_FORMAT_RAW;
 894
 895        setup_revisions(0, NULL, &opt, NULL);
 896        log_tree_commit(&opt, commit);
 897}
 898
 899/*
 900 * The terms used for this bisect session are stored in BISECT_TERMS.
 901 * We read them and store them to adapt the messages accordingly.
 902 * Default is bad/good.
 903 */
 904void read_bisect_terms(const char **read_bad, const char **read_good)
 905{
 906        struct strbuf str = STRBUF_INIT;
 907        const char *filename = git_path_bisect_terms();
 908        FILE *fp = fopen(filename, "r");
 909
 910        if (!fp) {
 911                if (errno == ENOENT) {
 912                        *read_bad = "bad";
 913                        *read_good = "good";
 914                        return;
 915                } else {
 916                        die_errno(_("could not read file '%s'"), filename);
 917                }
 918        } else {
 919                strbuf_getline_lf(&str, fp);
 920                *read_bad = strbuf_detach(&str, NULL);
 921                strbuf_getline_lf(&str, fp);
 922                *read_good = strbuf_detach(&str, NULL);
 923        }
 924        strbuf_release(&str);
 925        fclose(fp);
 926}
 927
 928/*
 929 * We use the convention that exiting with an exit code 10 means that
 930 * the bisection process finished successfully.
 931 * In this case the calling shell script should exit 0.
 932 *
 933 * If no_checkout is non-zero, the bisection process does not
 934 * checkout the trial commit but instead simply updates BISECT_HEAD.
 935 */
 936int bisect_next_all(const char *prefix, int no_checkout)
 937{
 938        struct rev_info revs;
 939        struct commit_list *tried;
 940        int reaches = 0, all = 0, nr, steps;
 941        const unsigned char *bisect_rev;
 942        char *steps_msg;
 943
 944        read_bisect_terms(&term_bad, &term_good);
 945        if (read_bisect_refs())
 946                die(_("reading bisect refs failed"));
 947
 948        check_good_are_ancestors_of_bad(prefix, no_checkout);
 949
 950        bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
 951        revs.limited = 1;
 952
 953        bisect_common(&revs);
 954
 955        revs.commits = find_bisection(revs.commits, &reaches, &all,
 956                                       !!skipped_revs.nr);
 957        revs.commits = managed_skipped(revs.commits, &tried);
 958
 959        if (!revs.commits) {
 960                /*
 961                 * We should exit here only if the "bad"
 962                 * commit is also a "skip" commit.
 963                 */
 964                exit_if_skipped_commits(tried, NULL);
 965
 966                printf(_("%s was both %s and %s\n"),
 967                       oid_to_hex(current_bad_oid),
 968                       term_good,
 969                       term_bad);
 970                exit(1);
 971        }
 972
 973        if (!all) {
 974                fprintf(stderr, _("No testable commit found.\n"
 975                        "Maybe you started with bad path parameters?\n"));
 976                exit(4);
 977        }
 978
 979        bisect_rev = revs.commits->item->object.oid.hash;
 980
 981        if (!hashcmp(bisect_rev, current_bad_oid->hash)) {
 982                exit_if_skipped_commits(tried, current_bad_oid);
 983                printf("%s is the first %s commit\n", sha1_to_hex(bisect_rev),
 984                        term_bad);
 985                show_diff_tree(prefix, revs.commits->item);
 986                /* This means the bisection process succeeded. */
 987                exit(10);
 988        }
 989
 990        nr = all - reaches - 1;
 991        steps = estimate_bisect_steps(all);
 992
 993        steps_msg = xstrfmt(Q_("(roughly %d step)", "(roughly %d steps)",
 994                  steps), steps);
 995        /*
 996         * TRANSLATORS: the last %s will be replaced with "(roughly %d
 997         * steps)" translation.
 998         */
 999        printf(Q_("Bisecting: %d revision left to test after this %s\n",
1000                  "Bisecting: %d revisions left to test after this %s\n",
1001                  nr), nr, steps_msg);
1002        free(steps_msg);
1003
1004        return bisect_checkout(bisect_rev, no_checkout);
1005}
1006
1007static inline int log2i(int n)
1008{
1009        int log2 = 0;
1010
1011        for (; n > 1; n >>= 1)
1012                log2++;
1013
1014        return log2;
1015}
1016
1017static inline int exp2i(int n)
1018{
1019        return 1 << n;
1020}
1021
1022/*
1023 * Estimate the number of bisect steps left (after the current step)
1024 *
1025 * For any x between 0 included and 2^n excluded, the probability for
1026 * n - 1 steps left looks like:
1027 *
1028 * P(2^n + x) == (2^n - x) / (2^n + x)
1029 *
1030 * and P(2^n + x) < 0.5 means 2^n < 3x
1031 */
1032int estimate_bisect_steps(int all)
1033{
1034        int n, x, e;
1035
1036        if (all < 3)
1037                return 0;
1038
1039        n = log2i(all);
1040        e = exp2i(n);
1041        x = all - e;
1042
1043        return (e < 3 * x) ? n : n - 1;
1044}