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