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