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