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 "bisect.h"
  11
  12 struct sha1_array {
  13         unsigned char (*sha1)[20];
  14         int sha1_nr;
  15         int sha1_alloc;
  16 };
  17
  18 static struct sha1_array good_revs;
  19 static struct sha1_array skipped_revs;
  20
  21 static const char **rev_argv;
  22 static int rev_argv_nr;
  23 static int rev_argv_alloc;
  24
  25 static const unsigned char *current_bad_sha1;
  26
  27 static const char *argv_diff_tree[] = {"diff-tree", "--pretty", NULL, NULL};
  28 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
  29 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
  30
  31 /* bits #0-15 in revision.h */
  32
  33 #define COUNTED         (1u<<16)
  34
  35 /*
  36  * This is a truly stupid algorithm, but it's only
  37  * used for bisection, and we just don't care enough.
  38  *
  39  * We care just barely enough to avoid recursing for
  40  * non-merge entries.
  41  */
  42 static int count_distance(struct commit_list *entry)
  43 {
  44         int nr = 0;
  45
  46         while (entry) {
  47                 struct commit *commit = entry->item;
  48                 struct commit_list *p;
  49
  50                 if (commit->object.flags & (UNINTERESTING | COUNTED))
  51                         break;
  52                 if (!(commit->object.flags & TREESAME))
  53                         nr++;
  54                 commit->object.flags |= COUNTED;
  55                 p = commit->parents;
  56                 entry = p;
  57                 if (p) {
  58                         p = p->next;
  59                         while (p) {
  60                                 nr += count_distance(p);
  61                                 p = p->next;
  62                         }
  63                 }
  64         }
  65
  66         return nr;
  67 }
  68
  69 static void clear_distance(struct commit_list *list)
  70 {
  71         while (list) {
  72                 struct commit *commit = list->item;
  73                 commit->object.flags &= ~COUNTED;
  74                 list = list->next;
  75         }
  76 }
  77
  78 #define DEBUG_BISECT 0
  79
  80 static inline int weight(struct commit_list *elem)
  81 {
  82         return *((int*)(elem->item->util));
  83 }
  84
  85 static inline void weight_set(struct commit_list *elem, int weight)
  86 {
  87         *((int*)(elem->item->util)) = weight;
  88 }
  89
  90 static int count_interesting_parents(struct commit *commit)
  91 {
  92         struct commit_list *p;
  93         int count;
  94
  95         for (count = 0, p = commit->parents; p; p = p->next) {
  96                 if (p->item->object.flags & UNINTERESTING)
  97                         continue;
  98                 count++;
  99         }
 100         return count;
 101 }
 102
 103 static inline int halfway(struct commit_list *p, int nr)
 104 {
 105         /*
 106          * Don't short-cut something we are not going to return!
 107          */
 108         if (p->item->object.flags & TREESAME)
 109                 return 0;
 110         if (DEBUG_BISECT)
 111                 return 0;
 112         /*
 113          * 2 and 3 are halfway of 5.
 114          * 3 is halfway of 6 but 2 and 4 are not.
 115          */
 116         switch (2 * weight(p) - nr) {
 117         case -1: case 0: case 1:
 118                 return 1;
 119         default:
 120                 return 0;
 121         }
 122 }
 123
 124 #if !DEBUG_BISECT
 125 #define show_list(a,b,c,d) do { ; } while (0)
 126 #else
 127 static void show_list(const char *debug, int counted, int nr,
 128                       struct commit_list *list)
 129 {
 130         struct commit_list *p;
 131
 132         fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
 133
 134         for (p = list; p; p = p->next) {
 135                 struct commit_list *pp;
 136                 struct commit *commit = p->item;
 137                 unsigned flags = commit->object.flags;
 138                 enum object_type type;
 139                 unsigned long size;
 140                 char *buf = read_sha1_file(commit->object.sha1, &type, &size);
 141                 char *ep, *sp;
 142
 143                 fprintf(stderr, "%c%c%c ",
 144                         (flags & TREESAME) ? ' ' : 'T',
 145                         (flags & UNINTERESTING) ? 'U' : ' ',
 146                         (flags & COUNTED) ? 'C' : ' ');
 147                 if (commit->util)
 148                         fprintf(stderr, "%3d", weight(p));
 149                 else
 150                         fprintf(stderr, "---");
 151                 fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
 152                 for (pp = commit->parents; pp; pp = pp->next)
 153                         fprintf(stderr, " %.*s", 8,
 154                                 sha1_to_hex(pp->item->object.sha1));
 155
 156                 sp = strstr(buf, "\n\n");
 157                 if (sp) {
 158                         sp += 2;
 159                         for (ep = sp; *ep && *ep != '\n'; ep++)
 160                                 ;
 161                         fprintf(stderr, " %.*s", (int)(ep - sp), sp);
 162                 }
 163                 fprintf(stderr, "\n");
 164         }
 165 }
 166 #endif /* DEBUG_BISECT */
 167
 168 static struct commit_list *best_bisection(struct commit_list *list, int nr)
 169 {
 170         struct commit_list *p, *best;
 171         int best_distance = -1;
 172
 173         best = list;
 174         for (p = list; p; p = p->next) {
 175                 int distance;
 176                 unsigned flags = p->item->object.flags;
 177
 178                 if (flags & TREESAME)
 179                         continue;
 180                 distance = weight(p);
 181                 if (nr - distance < distance)
 182                         distance = nr - distance;
 183                 if (distance > best_distance) {
 184                         best = p;
 185                         best_distance = distance;
 186                 }
 187         }
 188
 189         return best;
 190 }
 191
 192 struct commit_dist {
 193         struct commit *commit;
 194         int distance;
 195 };
 196
 197 static int compare_commit_dist(const void *a_, const void *b_)
 198 {
 199         struct commit_dist *a, *b;
 200
 201         a = (struct commit_dist *)a_;
 202         b = (struct commit_dist *)b_;
 203         if (a->distance != b->distance)
 204                 return b->distance - a->distance; /* desc sort */
 205         return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
 206 }
 207
 208 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
 209 {
 210         struct commit_list *p;
 211         struct commit_dist *array = xcalloc(nr, sizeof(*array));
 212         int cnt, i;
 213
 214         for (p = list, cnt = 0; p; p = p->next) {
 215                 int distance;
 216                 unsigned flags = p->item->object.flags;
 217
 218                 if (flags & TREESAME)
 219                         continue;
 220                 distance = weight(p);
 221                 if (nr - distance < distance)
 222                         distance = nr - distance;
 223                 array[cnt].commit = p->item;
 224                 array[cnt].distance = distance;
 225                 cnt++;
 226         }
 227         qsort(array, cnt, sizeof(*array), compare_commit_dist);
 228         for (p = list, i = 0; i < cnt; i++) {
 229                 struct name_decoration *r = xmalloc(sizeof(*r) + 100);
 230                 struct object *obj = &(array[i].commit->object);
 231
 232                 sprintf(r->name, "dist=%d", array[i].distance);
 233                 r->next = add_decoration(&name_decoration, obj, r);
 234                 p->item = array[i].commit;
 235                 p = p->next;
 236         }
 237         if (p)
 238                 p->next = NULL;
 239         free(array);
 240         return list;
 241 }
 242
 243 /*
 244  * zero or positive weight is the number of interesting commits it can
 245  * reach, including itself.  Especially, weight = 0 means it does not
 246  * reach any tree-changing commits (e.g. just above uninteresting one
 247  * but traversal is with pathspec).
 248  *
 249  * weight = -1 means it has one parent and its distance is yet to
 250  * be computed.
 251  *
 252  * weight = -2 means it has more than one parent and its distance is
 253  * unknown.  After running count_distance() first, they will get zero
 254  * or positive distance.
 255  */
 256 static struct commit_list *do_find_bisection(struct commit_list *list,
 257                                              int nr, int *weights,
 258                                              int find_all)
 259 {
 260         int n, counted;
 261         struct commit_list *p;
 262
 263         counted = 0;
 264
 265         for (n = 0, p = list; p; p = p->next) {
 266                 struct commit *commit = p->item;
 267                 unsigned flags = commit->object.flags;
 268
 269                 p->item->util = &weights[n++];
 270                 switch (count_interesting_parents(commit)) {
 271                 case 0:
 272                         if (!(flags & TREESAME)) {
 273                                 weight_set(p, 1);
 274                                 counted++;
 275                                 show_list("bisection 2 count one",
 276                                           counted, nr, list);
 277                         }
 278                         /*
 279                          * otherwise, it is known not to reach any
 280                          * tree-changing commit and gets weight 0.
 281                          */
 282                         break;
 283                 case 1:
 284                         weight_set(p, -1);
 285                         break;
 286                 default:
 287                         weight_set(p, -2);
 288                         break;
 289                 }
 290         }
 291
 292         show_list("bisection 2 initialize", counted, nr, list);
 293
 294         /*
 295          * If you have only one parent in the resulting set
 296          * then you can reach one commit more than that parent
 297          * can reach.  So we do not have to run the expensive
 298          * count_distance() for single strand of pearls.
 299          *
 300          * However, if you have more than one parents, you cannot
 301          * just add their distance and one for yourself, since
 302          * they usually reach the same ancestor and you would
 303          * end up counting them twice that way.
 304          *
 305          * So we will first count distance of merges the usual
 306          * way, and then fill the blanks using cheaper algorithm.
 307          */
 308         for (p = list; p; p = p->next) {
 309                 if (p->item->object.flags & UNINTERESTING)
 310                         continue;
 311                 if (weight(p) != -2)
 312                         continue;
 313                 weight_set(p, count_distance(p));
 314                 clear_distance(list);
 315
 316                 /* Does it happen to be at exactly half-way? */
 317                 if (!find_all && halfway(p, nr))
 318                         return p;
 319                 counted++;
 320         }
 321
 322         show_list("bisection 2 count_distance", counted, nr, list);
 323
 324         while (counted < nr) {
 325                 for (p = list; p; p = p->next) {
 326                         struct commit_list *q;
 327                         unsigned flags = p->item->object.flags;
 328
 329                         if (0 <= weight(p))
 330                                 continue;
 331                         for (q = p->item->parents; q; q = q->next) {
 332                                 if (q->item->object.flags & UNINTERESTING)
 333                                         continue;
 334                                 if (0 <= weight(q))
 335                                         break;
 336                         }
 337                         if (!q)
 338                                 continue;
 339
 340                         /*
 341                          * weight for p is unknown but q is known.
 342                          * add one for p itself if p is to be counted,
 343                          * otherwise inherit it from q directly.
 344                          */
 345                         if (!(flags & TREESAME)) {
 346                                 weight_set(p, weight(q)+1);
 347                                 counted++;
 348                                 show_list("bisection 2 count one",
 349                                           counted, nr, list);
 350                         }
 351                         else
 352                                 weight_set(p, weight(q));
 353
 354                         /* Does it happen to be at exactly half-way? */
 355                         if (!find_all && halfway(p, nr))
 356                                 return p;
 357                 }
 358         }
 359
 360         show_list("bisection 2 counted all", counted, nr, list);
 361
 362         if (!find_all)
 363                 return best_bisection(list, nr);
 364         else
 365                 return best_bisection_sorted(list, nr);
 366 }
 367
 368 struct commit_list *find_bisection(struct commit_list *list,
 369                                           int *reaches, int *all,
 370                                           int find_all)
 371 {
 372         int nr, on_list;
 373         struct commit_list *p, *best, *next, *last;
 374         int *weights;
 375
 376         show_list("bisection 2 entry", 0, 0, list);
 377
 378         /*
 379          * Count the number of total and tree-changing items on the
 380          * list, while reversing the list.
 381          */
 382         for (nr = on_list = 0, last = NULL, p = list;
 383              p;
 384              p = next) {
 385                 unsigned flags = p->item->object.flags;
 386
 387                 next = p->next;
 388                 if (flags & UNINTERESTING)
 389                         continue;
 390                 p->next = last;
 391                 last = p;
 392                 if (!(flags & TREESAME))
 393                         nr++;
 394                 on_list++;
 395         }
 396         list = last;
 397         show_list("bisection 2 sorted", 0, nr, list);
 398
 399         *all = nr;
 400         weights = xcalloc(on_list, sizeof(*weights));
 401
 402         /* Do the real work of finding bisection commit. */
 403         best = do_find_bisection(list, nr, weights, find_all);
 404         if (best) {
 405                 if (!find_all)
 406                         best->next = NULL;
 407                 *reaches = weight(best);
 408         }
 409         free(weights);
 410         return best;
 411 }
 412
 413 static void rev_argv_push(const unsigned char *sha1, const char *format)
 414 {
 415         struct strbuf buf = STRBUF_INIT;
 416
 417         strbuf_addf(&buf, format, sha1_to_hex(sha1));
 418         ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
 419         rev_argv[rev_argv_nr++] = strbuf_detach(&buf, NULL);
 420 }
 421
 422 static void sha1_array_push(struct sha1_array *array,
 423                             const unsigned char *sha1)
 424 {
 425         ALLOC_GROW(array->sha1, array->sha1_nr + 1, array->sha1_alloc);
 426         hashcpy(array->sha1[array->sha1_nr++], sha1);
 427 }
 428
 429 static int register_ref(const char *refname, const unsigned char *sha1,
 430                         int flags, void *cb_data)
 431 {
 432         if (!strcmp(refname, "bad")) {
 433                 current_bad_sha1 = sha1;
 434         } else if (!prefixcmp(refname, "good-")) {
 435                 sha1_array_push(&good_revs, sha1);
 436         } else if (!prefixcmp(refname, "skip-")) {
 437                 sha1_array_push(&skipped_revs, sha1);
 438         }
 439
 440         return 0;
 441 }
 442
 443 static int read_bisect_refs(void)
 444 {
 445         return for_each_ref_in("refs/bisect/", register_ref, NULL);
 446 }
 447
 448 void read_bisect_paths(void)
 449 {
 450         struct strbuf str = STRBUF_INIT;
 451         const char *filename = git_path("BISECT_NAMES");
 452         FILE *fp = fopen(filename, "r");
 453
 454         if (!fp)
 455                 die("Could not open file '%s': %s", filename, strerror(errno));
 456
 457         while (strbuf_getline(&str, fp, '\n') != EOF) {
 458                 char *quoted;
 459                 int res;
 460
 461                 strbuf_trim(&str);
 462                 quoted = strbuf_detach(&str, NULL);
 463                 res = sq_dequote_to_argv(quoted, &rev_argv,
 464                                          &rev_argv_nr, &rev_argv_alloc);
 465                 if (res)
 466                         die("Badly quoted content in file '%s': %s",
 467                             filename, quoted);
 468         }
 469
 470         strbuf_release(&str);
 471         fclose(fp);
 472 }
 473
 474 static int skipcmp(const void *a, const void *b)
 475 {
 476         return hashcmp(a, b);
 477 }
 478
 479 static void prepare_skipped(void)
 480 {
 481         qsort(skipped_revs.sha1, skipped_revs.sha1_nr,
 482               sizeof(*skipped_revs.sha1), skipcmp);
 483 }
 484
 485 static const unsigned char *skipped_sha1_access(size_t index, void *table)
 486 {
 487         unsigned char (*skipped)[20] = table;
 488         return skipped[index];
 489 }
 490
 491 static int lookup_skipped(unsigned char *sha1)
 492 {
 493         return sha1_pos(sha1, skipped_revs.sha1, skipped_revs.sha1_nr,
 494                         skipped_sha1_access);
 495 }
 496
 497 struct commit_list *filter_skipped(struct commit_list *list,
 498                                    struct commit_list **tried,
 499                                    int show_all)
 500 {
 501         struct commit_list *filtered = NULL, **f = &filtered;
 502
 503         *tried = NULL;
 504
 505         if (!skipped_revs.sha1_nr)
 506                 return list;
 507
 508         prepare_skipped();
 509
 510         while (list) {
 511                 struct commit_list *next = list->next;
 512                 list->next = NULL;
 513                 if (0 <= lookup_skipped(list->item->object.sha1)) {
 514                         /* Move current to tried list */
 515                         *tried = list;
 516                         tried = &list->next;
 517                 } else {
 518                         if (!show_all)
 519                                 return list;
 520                         /* Move current to filtered list */
 521                         *f = list;
 522                         f = &list->next;
 523                 }
 524                 list = next;
 525         }
 526
 527         return filtered;
 528 }
 529
 530 static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
 531 {
 532         int i;
 533
 534         init_revisions(revs, prefix);
 535         revs->abbrev = 0;
 536         revs->commit_format = CMIT_FMT_UNSPECIFIED;
 537
 538         if (read_bisect_refs())
 539                 die("reading bisect refs failed");
 540
 541         /* argv[0] will be ignored by setup_revisions */
 542         ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
 543         rev_argv[rev_argv_nr++] = xstrdup("bisect_rev_setup");
 544
 545         rev_argv_push(current_bad_sha1, "%s");
 546
 547         for (i = 0; i < good_revs.sha1_nr; i++)
 548                 rev_argv_push(good_revs.sha1[i], "^%s");
 549
 550         ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
 551         rev_argv[rev_argv_nr++] = xstrdup("--");
 552
 553         read_bisect_paths();
 554
 555         ALLOC_GROW(rev_argv, rev_argv_nr + 1, rev_argv_alloc);
 556         rev_argv[rev_argv_nr++] = NULL;
 557
 558         setup_revisions(rev_argv_nr, rev_argv, revs, NULL);
 559
 560         revs->limited = 1;
 561 }
 562
 563 static void bisect_common(struct rev_info *revs, const char *prefix,
 564                           int *reaches, int *all)
 565 {
 566         bisect_rev_setup(revs, prefix);
 567
 568         if (prepare_revision_walk(revs))
 569                 die("revision walk setup failed");
 570         if (revs->tree_objects)
 571                 mark_edges_uninteresting(revs->commits, revs, NULL);
 572
 573         revs->commits = find_bisection(revs->commits, reaches, all,
 574                                        !!skipped_revs.sha1_nr);
 575 }
 576
 577 static void exit_if_skipped_commits(struct commit_list *tried,
 578                                     const unsigned char *bad)
 579 {
 580         if (!tried)
 581                 return;
 582
 583         printf("There are only 'skip'ped commits left to test.\n"
 584                "The first bad commit could be any of:\n");
 585         print_commit_list(tried, "%s\n", "%s\n");
 586         if (bad)
 587                 printf("%s\n", sha1_to_hex(bad));
 588         printf("We cannot bisect more!\n");
 589         exit(2);
 590 }
 591
 592 static void mark_expected_rev(char *bisect_rev_hex)
 593 {
 594         int len = strlen(bisect_rev_hex);
 595         const char *filename = git_path("BISECT_EXPECTED_REV");
 596         int fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
 597
 598         if (fd < 0)
 599                 die("could not create file '%s': %s",
 600                     filename, strerror(errno));
 601
 602         bisect_rev_hex[len] = '\n';
 603         write_or_die(fd, bisect_rev_hex, len + 1);
 604         bisect_rev_hex[len] = '\0';
 605
 606         if (close(fd) < 0)
 607                 die("closing file %s: %s", filename, strerror(errno));
 608 }
 609
 610 static int bisect_checkout(char *bisect_rev_hex)
 611 {
 612         int res;
 613
 614         mark_expected_rev(bisect_rev_hex);
 615
 616         argv_checkout[2] = bisect_rev_hex;
 617         res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
 618         if (res)
 619                 exit(res);
 620
 621         argv_show_branch[1] = bisect_rev_hex;
 622         return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
 623 }
 624
 625 /*
 626  * We use the convention that exiting with an exit code 10 means that
 627  * the bisection process finished successfully.
 628  * In this case the calling shell script should exit 0.
 629  */
 630 int bisect_next_exit(const char *prefix)
 631 {
 632         struct rev_info revs;
 633         struct commit_list *tried;
 634         int reaches = 0, all = 0, nr;
 635         const unsigned char *bisect_rev;
 636         char bisect_rev_hex[41];
 637
 638         bisect_common(&revs, prefix, &reaches, &all);
 639
 640         revs.commits = filter_skipped(revs.commits, &tried, 0);
 641
 642         if (!revs.commits) {
 643                 /*
 644                  * We should exit here only if the "bad"
 645                  * commit is also a "skip" commit.
 646                  */
 647                 exit_if_skipped_commits(tried, NULL);
 648
 649                 printf("%s was both good and bad\n",
 650                        sha1_to_hex(current_bad_sha1));
 651                 exit(1);
 652         }
 653
 654         bisect_rev = revs.commits->item->object.sha1;
 655         memcpy(bisect_rev_hex, sha1_to_hex(bisect_rev), 41);
 656
 657         if (!hashcmp(bisect_rev, current_bad_sha1)) {
 658                 exit_if_skipped_commits(tried, current_bad_sha1);
 659                 printf("%s is first bad commit\n", bisect_rev_hex);
 660                 argv_diff_tree[2] = bisect_rev_hex;
 661                 run_command_v_opt(argv_diff_tree, RUN_GIT_CMD);
 662                 /* This means the bisection process succeeded. */
 663                 exit(10);
 664         }
 665
 666         nr = all - reaches - 1;
 667         printf("Bisecting: %d revisions left to test after this "
 668                "(roughly %d steps)\n", nr, estimate_bisect_steps(all));
 669
 670         return bisect_checkout(bisect_rev_hex);
 671 }
 672