builtin-rev-list.c

   1 #include "cache.h"
   2 #include "refs.h"
   3 #include "tag.h"
   4 #include "commit.h"
   5 #include "tree.h"
   6 #include "blob.h"
   7 #include "tree-walk.h"
   8 #include "diff.h"
   9 #include "revision.h"
  10 #include "list-objects.h"
  11 #include "builtin.h"
  12 #include "log-tree.h"
  13
  14 /* bits #0-15 in revision.h */
  15
  16 #define COUNTED         (1u<<16)
  17
  18 static const char rev_list_usage[] =
  19 "git-rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
  20 "  limiting output:\n"
  21 "    --max-count=nr\n"
  22 "    --max-age=epoch\n"
  23 "    --min-age=epoch\n"
  24 "    --sparse\n"
  25 "    --no-merges\n"
  26 "    --remove-empty\n"
  27 "    --all\n"
  28 "    --branches\n"
  29 "    --tags\n"
  30 "    --remotes\n"
  31 "    --stdin\n"
  32 "    --quiet\n"
  33 "  ordering output:\n"
  34 "    --topo-order\n"
  35 "    --date-order\n"
  36 "    --reverse\n"
  37 "  formatting output:\n"
  38 "    --parents\n"
  39 "    --children\n"
  40 "    --objects | --objects-edge\n"
  41 "    --unpacked\n"
  42 "    --header | --pretty\n"
  43 "    --abbrev=nr | --no-abbrev\n"
  44 "    --abbrev-commit\n"
  45 "    --left-right\n"
  46 "  special purpose:\n"
  47 "    --bisect\n"
  48 "    --bisect-vars\n"
  49 "    --bisect-all"
  50 ;
  51
  52 static struct rev_info revs;
  53
  54 static int bisect_list;
  55 static int show_timestamp;
  56 static int hdr_termination;
  57 static const char *header_prefix;
  58
  59 static void finish_commit(struct commit *commit);
  60 static void show_commit(struct commit *commit)
  61 {
  62         if (show_timestamp)
  63                 printf("%lu ", commit->date);
  64         if (header_prefix)
  65                 fputs(header_prefix, stdout);
  66         if (commit->object.flags & BOUNDARY)
  67                 putchar('-');
  68         else if (commit->object.flags & UNINTERESTING)
  69                 putchar('^');
  70         else if (revs.left_right) {
  71                 if (commit->object.flags & SYMMETRIC_LEFT)
  72                         putchar('<');
  73                 else
  74                         putchar('>');
  75         }
  76         if (revs.abbrev_commit && revs.abbrev)
  77                 fputs(find_unique_abbrev(commit->object.sha1, revs.abbrev),
  78                       stdout);
  79         else
  80                 fputs(sha1_to_hex(commit->object.sha1), stdout);
  81         if (revs.parents) {
  82                 struct commit_list *parents = commit->parents;
  83                 while (parents) {
  84                         printf(" %s", sha1_to_hex(parents->item->object.sha1));
  85                         parents = parents->next;
  86                 }
  87         }
  88         if (revs.children.name) {
  89                 struct commit_list *children;
  90
  91                 children = lookup_decoration(&revs.children, &commit->object);
  92                 while (children) {
  93                         printf(" %s", sha1_to_hex(children->item->object.sha1));
  94                         children = children->next;
  95                 }
  96         }
  97         show_decorations(commit);
  98         if (revs.commit_format == CMIT_FMT_ONELINE)
  99                 putchar(' ');
 100         else
 101                 putchar('\n');
 102
 103         if (revs.verbose_header && commit->buffer) {
 104                 struct strbuf buf;
 105                 strbuf_init(&buf, 0);
 106                 pretty_print_commit(revs.commit_format, commit,
 107                                     &buf, revs.abbrev, NULL, NULL,
 108                                     revs.date_mode, 0);
 109                 if (buf.len)
 110                         printf("%s%c", buf.buf, hdr_termination);
 111                 strbuf_release(&buf);
 112         }
 113         maybe_flush_or_die(stdout, "stdout");
 114         finish_commit(commit);
 115 }
 116
 117 static void finish_commit(struct commit *commit)
 118 {
 119         if (commit->parents) {
 120                 free_commit_list(commit->parents);
 121                 commit->parents = NULL;
 122         }
 123         free(commit->buffer);
 124         commit->buffer = NULL;
 125 }
 126
 127 static void finish_object(struct object_array_entry *p)
 128 {
 129         if (p->item->type == OBJ_BLOB && !has_sha1_file(p->item->sha1))
 130                 die("missing blob object '%s'", sha1_to_hex(p->item->sha1));
 131 }
 132
 133 static void show_object(struct object_array_entry *p)
 134 {
 135         /* An object with name "foo\n0000000..." can be used to
 136          * confuse downstream git-pack-objects very badly.
 137          */
 138         const char *ep = strchr(p->name, '\n');
 139
 140         finish_object(p);
 141         if (ep) {
 142                 printf("%s %.*s\n", sha1_to_hex(p->item->sha1),
 143                        (int) (ep - p->name),
 144                        p->name);
 145         }
 146         else
 147                 printf("%s %s\n", sha1_to_hex(p->item->sha1), p->name);
 148 }
 149
 150 static void show_edge(struct commit *commit)
 151 {
 152         printf("-%s\n", sha1_to_hex(commit->object.sha1));
 153 }
 154
 155 /*
 156  * This is a truly stupid algorithm, but it's only
 157  * used for bisection, and we just don't care enough.
 158  *
 159  * We care just barely enough to avoid recursing for
 160  * non-merge entries.
 161  */
 162 static int count_distance(struct commit_list *entry)
 163 {
 164         int nr = 0;
 165
 166         while (entry) {
 167                 struct commit *commit = entry->item;
 168                 struct commit_list *p;
 169
 170                 if (commit->object.flags & (UNINTERESTING | COUNTED))
 171                         break;
 172                 if (!(commit->object.flags & TREESAME))
 173                         nr++;
 174                 commit->object.flags |= COUNTED;
 175                 p = commit->parents;
 176                 entry = p;
 177                 if (p) {
 178                         p = p->next;
 179                         while (p) {
 180                                 nr += count_distance(p);
 181                                 p = p->next;
 182                         }
 183                 }
 184         }
 185
 186         return nr;
 187 }
 188
 189 static void clear_distance(struct commit_list *list)
 190 {
 191         while (list) {
 192                 struct commit *commit = list->item;
 193                 commit->object.flags &= ~COUNTED;
 194                 list = list->next;
 195         }
 196 }
 197
 198 #define DEBUG_BISECT 0
 199
 200 static inline int weight(struct commit_list *elem)
 201 {
 202         return *((int*)(elem->item->util));
 203 }
 204
 205 static inline void weight_set(struct commit_list *elem, int weight)
 206 {
 207         *((int*)(elem->item->util)) = weight;
 208 }
 209
 210 static int count_interesting_parents(struct commit *commit)
 211 {
 212         struct commit_list *p;
 213         int count;
 214
 215         for (count = 0, p = commit->parents; p; p = p->next) {
 216                 if (p->item->object.flags & UNINTERESTING)
 217                         continue;
 218                 count++;
 219         }
 220         return count;
 221 }
 222
 223 static inline int halfway(struct commit_list *p, int nr)
 224 {
 225         /*
 226          * Don't short-cut something we are not going to return!
 227          */
 228         if (p->item->object.flags & TREESAME)
 229                 return 0;
 230         if (DEBUG_BISECT)
 231                 return 0;
 232         /*
 233          * 2 and 3 are halfway of 5.
 234          * 3 is halfway of 6 but 2 and 4 are not.
 235          */
 236         switch (2 * weight(p) - nr) {
 237         case -1: case 0: case 1:
 238                 return 1;
 239         default:
 240                 return 0;
 241         }
 242 }
 243
 244 #if !DEBUG_BISECT
 245 #define show_list(a,b,c,d) do { ; } while (0)
 246 #else
 247 static void show_list(const char *debug, int counted, int nr,
 248                       struct commit_list *list)
 249 {
 250         struct commit_list *p;
 251
 252         fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
 253
 254         for (p = list; p; p = p->next) {
 255                 struct commit_list *pp;
 256                 struct commit *commit = p->item;
 257                 unsigned flags = commit->object.flags;
 258                 enum object_type type;
 259                 unsigned long size;
 260                 char *buf = read_sha1_file(commit->object.sha1, &type, &size);
 261                 char *ep, *sp;
 262
 263                 fprintf(stderr, "%c%c%c ",
 264                         (flags & TREESAME) ? ' ' : 'T',
 265                         (flags & UNINTERESTING) ? 'U' : ' ',
 266                         (flags & COUNTED) ? 'C' : ' ');
 267                 if (commit->util)
 268                         fprintf(stderr, "%3d", weight(p));
 269                 else
 270                         fprintf(stderr, "---");
 271                 fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
 272                 for (pp = commit->parents; pp; pp = pp->next)
 273                         fprintf(stderr, " %.*s", 8,
 274                                 sha1_to_hex(pp->item->object.sha1));
 275
 276                 sp = strstr(buf, "\n\n");
 277                 if (sp) {
 278                         sp += 2;
 279                         for (ep = sp; *ep && *ep != '\n'; ep++)
 280                                 ;
 281                         fprintf(stderr, " %.*s", (int)(ep - sp), sp);
 282                 }
 283                 fprintf(stderr, "\n");
 284         }
 285 }
 286 #endif /* DEBUG_BISECT */
 287
 288 static struct commit_list *best_bisection(struct commit_list *list, int nr)
 289 {
 290         struct commit_list *p, *best;
 291         int best_distance = -1;
 292
 293         best = list;
 294         for (p = list; p; p = p->next) {
 295                 int distance;
 296                 unsigned flags = p->item->object.flags;
 297
 298                 if (flags & TREESAME)
 299                         continue;
 300                 distance = weight(p);
 301                 if (nr - distance < distance)
 302                         distance = nr - distance;
 303                 if (distance > best_distance) {
 304                         best = p;
 305                         best_distance = distance;
 306                 }
 307         }
 308
 309         return best;
 310 }
 311
 312 struct commit_dist {
 313         struct commit *commit;
 314         int distance;
 315 };
 316
 317 static int compare_commit_dist(const void *a_, const void *b_)
 318 {
 319         struct commit_dist *a, *b;
 320
 321         a = (struct commit_dist *)a_;
 322         b = (struct commit_dist *)b_;
 323         if (a->distance != b->distance)
 324                 return b->distance - a->distance; /* desc sort */
 325         return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
 326 }
 327
 328 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
 329 {
 330         struct commit_list *p;
 331         struct commit_dist *array = xcalloc(nr, sizeof(*array));
 332         int cnt, i;
 333
 334         for (p = list, cnt = 0; p; p = p->next) {
 335                 int distance;
 336                 unsigned flags = p->item->object.flags;
 337
 338                 if (flags & TREESAME)
 339                         continue;
 340                 distance = weight(p);
 341                 if (nr - distance < distance)
 342                         distance = nr - distance;
 343                 array[cnt].commit = p->item;
 344                 array[cnt].distance = distance;
 345                 cnt++;
 346         }
 347         qsort(array, cnt, sizeof(*array), compare_commit_dist);
 348         for (p = list, i = 0; i < cnt; i++) {
 349                 struct name_decoration *r = xmalloc(sizeof(*r) + 100);
 350                 struct object *obj = &(array[i].commit->object);
 351
 352                 sprintf(r->name, "dist=%d", array[i].distance);
 353                 r->next = add_decoration(&name_decoration, obj, r);
 354                 p->item = array[i].commit;
 355                 p = p->next;
 356         }
 357         if (p)
 358                 p->next = NULL;
 359         free(array);
 360         return list;
 361 }
 362
 363 /*
 364  * zero or positive weight is the number of interesting commits it can
 365  * reach, including itself.  Especially, weight = 0 means it does not
 366  * reach any tree-changing commits (e.g. just above uninteresting one
 367  * but traversal is with pathspec).
 368  *
 369  * weight = -1 means it has one parent and its distance is yet to
 370  * be computed.
 371  *
 372  * weight = -2 means it has more than one parent and its distance is
 373  * unknown.  After running count_distance() first, they will get zero
 374  * or positive distance.
 375  */
 376 static struct commit_list *do_find_bisection(struct commit_list *list,
 377                                              int nr, int *weights,
 378                                              int find_all)
 379 {
 380         int n, counted;
 381         struct commit_list *p;
 382
 383         counted = 0;
 384
 385         for (n = 0, p = list; p; p = p->next) {
 386                 struct commit *commit = p->item;
 387                 unsigned flags = commit->object.flags;
 388
 389                 p->item->util = &weights[n++];
 390                 switch (count_interesting_parents(commit)) {
 391                 case 0:
 392                         if (!(flags & TREESAME)) {
 393                                 weight_set(p, 1);
 394                                 counted++;
 395                                 show_list("bisection 2 count one",
 396                                           counted, nr, list);
 397                         }
 398                         /*
 399                          * otherwise, it is known not to reach any
 400                          * tree-changing commit and gets weight 0.
 401                          */
 402                         break;
 403                 case 1:
 404                         weight_set(p, -1);
 405                         break;
 406                 default:
 407                         weight_set(p, -2);
 408                         break;
 409                 }
 410         }
 411
 412         show_list("bisection 2 initialize", counted, nr, list);
 413
 414         /*
 415          * If you have only one parent in the resulting set
 416          * then you can reach one commit more than that parent
 417          * can reach.  So we do not have to run the expensive
 418          * count_distance() for single strand of pearls.
 419          *
 420          * However, if you have more than one parents, you cannot
 421          * just add their distance and one for yourself, since
 422          * they usually reach the same ancestor and you would
 423          * end up counting them twice that way.
 424          *
 425          * So we will first count distance of merges the usual
 426          * way, and then fill the blanks using cheaper algorithm.
 427          */
 428         for (p = list; p; p = p->next) {
 429                 if (p->item->object.flags & UNINTERESTING)
 430                         continue;
 431                 if (weight(p) != -2)
 432                         continue;
 433                 weight_set(p, count_distance(p));
 434                 clear_distance(list);
 435
 436                 /* Does it happen to be at exactly half-way? */
 437                 if (!find_all && halfway(p, nr))
 438                         return p;
 439                 counted++;
 440         }
 441
 442         show_list("bisection 2 count_distance", counted, nr, list);
 443
 444         while (counted < nr) {
 445                 for (p = list; p; p = p->next) {
 446                         struct commit_list *q;
 447                         unsigned flags = p->item->object.flags;
 448
 449                         if (0 <= weight(p))
 450                                 continue;
 451                         for (q = p->item->parents; q; q = q->next) {
 452                                 if (q->item->object.flags & UNINTERESTING)
 453                                         continue;
 454                                 if (0 <= weight(q))
 455                                         break;
 456                         }
 457                         if (!q)
 458                                 continue;
 459
 460                         /*
 461                          * weight for p is unknown but q is known.
 462                          * add one for p itself if p is to be counted,
 463                          * otherwise inherit it from q directly.
 464                          */
 465                         if (!(flags & TREESAME)) {
 466                                 weight_set(p, weight(q)+1);
 467                                 counted++;
 468                                 show_list("bisection 2 count one",
 469                                           counted, nr, list);
 470                         }
 471                         else
 472                                 weight_set(p, weight(q));
 473
 474                         /* Does it happen to be at exactly half-way? */
 475                         if (!find_all && halfway(p, nr))
 476                                 return p;
 477                 }
 478         }
 479
 480         show_list("bisection 2 counted all", counted, nr, list);
 481
 482         if (!find_all)
 483                 return best_bisection(list, nr);
 484         else
 485                 return best_bisection_sorted(list, nr);
 486 }
 487
 488 static struct commit_list *find_bisection(struct commit_list *list,
 489                                           int *reaches, int *all,
 490                                           int find_all)
 491 {
 492         int nr, on_list;
 493         struct commit_list *p, *best, *next, *last;
 494         int *weights;
 495
 496         show_list("bisection 2 entry", 0, 0, list);
 497
 498         /*
 499          * Count the number of total and tree-changing items on the
 500          * list, while reversing the list.
 501          */
 502         for (nr = on_list = 0, last = NULL, p = list;
 503              p;
 504              p = next) {
 505                 unsigned flags = p->item->object.flags;
 506
 507                 next = p->next;
 508                 if (flags & UNINTERESTING)
 509                         continue;
 510                 p->next = last;
 511                 last = p;
 512                 if (!(flags & TREESAME))
 513                         nr++;
 514                 on_list++;
 515         }
 516         list = last;
 517         show_list("bisection 2 sorted", 0, nr, list);
 518
 519         *all = nr;
 520         weights = xcalloc(on_list, sizeof(*weights));
 521
 522         /* Do the real work of finding bisection commit. */
 523         best = do_find_bisection(list, nr, weights, find_all);
 524         if (best) {
 525                 if (!find_all)
 526                         best->next = NULL;
 527                 *reaches = weight(best);
 528         }
 529         free(weights);
 530         return best;
 531 }
 532
 533 static void read_revisions_from_stdin(struct rev_info *revs)
 534 {
 535         char line[1000];
 536
 537         while (fgets(line, sizeof(line), stdin) != NULL) {
 538                 int len = strlen(line);
 539                 if (len && line[len - 1] == '\n')
 540                         line[--len] = 0;
 541                 if (!len)
 542                         break;
 543                 if (line[0] == '-')
 544                         die("options not supported in --stdin mode");
 545                 if (handle_revision_arg(line, revs, 0, 1))
 546                         die("bad revision '%s'", line);
 547         }
 548 }
 549
 550 int cmd_rev_list(int argc, const char **argv, const char *prefix)
 551 {
 552         struct commit_list *list;
 553         int i;
 554         int read_from_stdin = 0;
 555         int bisect_show_vars = 0;
 556         int bisect_find_all = 0;
 557         int quiet = 0;
 558
 559         git_config(git_default_config);
 560         init_revisions(&revs, prefix);
 561         revs.abbrev = 0;
 562         revs.commit_format = CMIT_FMT_UNSPECIFIED;
 563         argc = setup_revisions(argc, argv, &revs, NULL);
 564
 565         for (i = 1 ; i < argc; i++) {
 566                 const char *arg = argv[i];
 567
 568                 if (!strcmp(arg, "--header")) {
 569                         revs.verbose_header = 1;
 570                         continue;
 571                 }
 572                 if (!strcmp(arg, "--timestamp")) {
 573                         show_timestamp = 1;
 574                         continue;
 575                 }
 576                 if (!strcmp(arg, "--bisect")) {
 577                         bisect_list = 1;
 578                         continue;
 579                 }
 580                 if (!strcmp(arg, "--bisect-all")) {
 581                         bisect_list = 1;
 582                         bisect_find_all = 1;
 583                         continue;
 584                 }
 585                 if (!strcmp(arg, "--bisect-vars")) {
 586                         bisect_list = 1;
 587                         bisect_show_vars = 1;
 588                         continue;
 589                 }
 590                 if (!strcmp(arg, "--stdin")) {
 591                         if (read_from_stdin++)
 592                                 die("--stdin given twice?");
 593                         read_revisions_from_stdin(&revs);
 594                         continue;
 595                 }
 596                 if (!strcmp(arg, "--quiet")) {
 597                         quiet = 1;
 598                         continue;
 599                 }
 600                 usage(rev_list_usage);
 601
 602         }
 603         if (revs.commit_format != CMIT_FMT_UNSPECIFIED) {
 604                 /* The command line has a --pretty  */
 605                 hdr_termination = '\n';
 606                 if (revs.commit_format == CMIT_FMT_ONELINE)
 607                         header_prefix = "";
 608                 else
 609                         header_prefix = "commit ";
 610         }
 611         else if (revs.verbose_header)
 612                 /* Only --header was specified */
 613                 revs.commit_format = CMIT_FMT_RAW;
 614
 615         list = revs.commits;
 616
 617         if ((!list &&
 618              (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) &&
 619               !revs.pending.nr)) ||
 620             revs.diff)
 621                 usage(rev_list_usage);
 622
 623         save_commit_buffer = revs.verbose_header || revs.grep_filter;
 624         if (bisect_list)
 625                 revs.limited = 1;
 626
 627         if (prepare_revision_walk(&revs))
 628                 die("revision walk setup failed");
 629         if (revs.tree_objects)
 630                 mark_edges_uninteresting(revs.commits, &revs, show_edge);
 631
 632         if (bisect_list) {
 633                 int reaches = reaches, all = all;
 634
 635                 revs.commits = find_bisection(revs.commits, &reaches, &all,
 636                                               bisect_find_all);
 637                 if (bisect_show_vars) {
 638                         int cnt;
 639                         char hex[41];
 640                         if (!revs.commits)
 641                                 return 1;
 642                         /*
 643                          * revs.commits can reach "reaches" commits among
 644                          * "all" commits.  If it is good, then there are
 645                          * (all-reaches) commits left to be bisected.
 646                          * On the other hand, if it is bad, then the set
 647                          * to bisect is "reaches".
 648                          * A bisect set of size N has (N-1) commits further
 649                          * to test, as we already know one bad one.
 650                          */
 651                         cnt = all - reaches;
 652                         if (cnt < reaches)
 653                                 cnt = reaches;
 654                         strcpy(hex, sha1_to_hex(revs.commits->item->object.sha1));
 655
 656                         if (bisect_find_all) {
 657                                 traverse_commit_list(&revs, show_commit, show_object);
 658                                 printf("------\n");
 659                         }
 660
 661                         printf("bisect_rev=%s\n"
 662                                "bisect_nr=%d\n"
 663                                "bisect_good=%d\n"
 664                                "bisect_bad=%d\n"
 665                                "bisect_all=%d\n",
 666                                hex,
 667                                cnt - 1,
 668                                all - reaches - 1,
 669                                reaches - 1,
 670                                all);
 671                         return 0;
 672                 }
 673         }
 674
 675         traverse_commit_list(&revs,
 676                 quiet ? finish_commit : show_commit,
 677                 quiet ? finish_object : show_object);
 678
 679         return 0;
 680 }