builtin / rev-list.con commit list-objects: consume sparse tree walk (4f6d26b)
   1#include "cache.h"
   2#include "config.h"
   3#include "commit.h"
   4#include "diff.h"
   5#include "revision.h"
   6#include "list-objects.h"
   7#include "list-objects-filter.h"
   8#include "list-objects-filter-options.h"
   9#include "object.h"
  10#include "object-store.h"
  11#include "pack.h"
  12#include "pack-bitmap.h"
  13#include "builtin.h"
  14#include "log-tree.h"
  15#include "graph.h"
  16#include "bisect.h"
  17#include "progress.h"
  18#include "reflog-walk.h"
  19#include "oidset.h"
  20#include "packfile.h"
  21#include "object-store.h"
  22
  23static const char rev_list_usage[] =
  24"git rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
  25"  limiting output:\n"
  26"    --max-count=<n>\n"
  27"    --max-age=<epoch>\n"
  28"    --min-age=<epoch>\n"
  29"    --sparse\n"
  30"    --no-merges\n"
  31"    --min-parents=<n>\n"
  32"    --no-min-parents\n"
  33"    --max-parents=<n>\n"
  34"    --no-max-parents\n"
  35"    --remove-empty\n"
  36"    --all\n"
  37"    --branches\n"
  38"    --tags\n"
  39"    --remotes\n"
  40"    --stdin\n"
  41"    --quiet\n"
  42"  ordering output:\n"
  43"    --topo-order\n"
  44"    --date-order\n"
  45"    --reverse\n"
  46"  formatting output:\n"
  47"    --parents\n"
  48"    --children\n"
  49"    --objects | --objects-edge\n"
  50"    --unpacked\n"
  51"    --header | --pretty\n"
  52"    --abbrev=<n> | --no-abbrev\n"
  53"    --abbrev-commit\n"
  54"    --left-right\n"
  55"    --count\n"
  56"  special purpose:\n"
  57"    --bisect\n"
  58"    --bisect-vars\n"
  59"    --bisect-all"
  60;
  61
  62static struct progress *progress;
  63static unsigned progress_counter;
  64
  65static struct list_objects_filter_options filter_options;
  66static struct oidset omitted_objects;
  67static int arg_print_omitted; /* print objects omitted by filter */
  68
  69static struct oidset missing_objects;
  70enum missing_action {
  71        MA_ERROR = 0,    /* fail if any missing objects are encountered */
  72        MA_ALLOW_ANY,    /* silently allow ALL missing objects */
  73        MA_PRINT,        /* print ALL missing objects in special section */
  74        MA_ALLOW_PROMISOR, /* silently allow all missing PROMISOR objects */
  75};
  76static enum missing_action arg_missing_action;
  77
  78#define DEFAULT_OIDSET_SIZE     (16*1024)
  79
  80static void finish_commit(struct commit *commit, void *data);
  81static void show_commit(struct commit *commit, void *data)
  82{
  83        struct rev_list_info *info = data;
  84        struct rev_info *revs = info->revs;
  85
  86        display_progress(progress, ++progress_counter);
  87
  88        if (info->flags & REV_LIST_QUIET) {
  89                finish_commit(commit, data);
  90                return;
  91        }
  92
  93        graph_show_commit(revs->graph);
  94
  95        if (revs->count) {
  96                if (commit->object.flags & PATCHSAME)
  97                        revs->count_same++;
  98                else if (commit->object.flags & SYMMETRIC_LEFT)
  99                        revs->count_left++;
 100                else
 101                        revs->count_right++;
 102                finish_commit(commit, data);
 103                return;
 104        }
 105
 106        if (info->show_timestamp)
 107                printf("%"PRItime" ", commit->date);
 108        if (info->header_prefix)
 109                fputs(info->header_prefix, stdout);
 110
 111        if (!revs->graph)
 112                fputs(get_revision_mark(revs, commit), stdout);
 113        if (revs->abbrev_commit && revs->abbrev)
 114                fputs(find_unique_abbrev(&commit->object.oid, revs->abbrev),
 115                      stdout);
 116        else
 117                fputs(oid_to_hex(&commit->object.oid), stdout);
 118        if (revs->print_parents) {
 119                struct commit_list *parents = commit->parents;
 120                while (parents) {
 121                        printf(" %s", oid_to_hex(&parents->item->object.oid));
 122                        parents = parents->next;
 123                }
 124        }
 125        if (revs->children.name) {
 126                struct commit_list *children;
 127
 128                children = lookup_decoration(&revs->children, &commit->object);
 129                while (children) {
 130                        printf(" %s", oid_to_hex(&children->item->object.oid));
 131                        children = children->next;
 132                }
 133        }
 134        show_decorations(revs, commit);
 135        if (revs->commit_format == CMIT_FMT_ONELINE)
 136                putchar(' ');
 137        else
 138                putchar('\n');
 139
 140        if (revs->verbose_header) {
 141                struct strbuf buf = STRBUF_INIT;
 142                struct pretty_print_context ctx = {0};
 143                ctx.abbrev = revs->abbrev;
 144                ctx.date_mode = revs->date_mode;
 145                ctx.date_mode_explicit = revs->date_mode_explicit;
 146                ctx.fmt = revs->commit_format;
 147                ctx.output_encoding = get_log_output_encoding();
 148                ctx.color = revs->diffopt.use_color;
 149                pretty_print_commit(&ctx, commit, &buf);
 150                if (buf.len) {
 151                        if (revs->commit_format != CMIT_FMT_ONELINE)
 152                                graph_show_oneline(revs->graph);
 153
 154                        graph_show_commit_msg(revs->graph, stdout, &buf);
 155
 156                        /*
 157                         * Add a newline after the commit message.
 158                         *
 159                         * Usually, this newline produces a blank
 160                         * padding line between entries, in which case
 161                         * we need to add graph padding on this line.
 162                         *
 163                         * However, the commit message may not end in a
 164                         * newline.  In this case the newline simply
 165                         * ends the last line of the commit message,
 166                         * and we don't need any graph output.  (This
 167                         * always happens with CMIT_FMT_ONELINE, and it
 168                         * happens with CMIT_FMT_USERFORMAT when the
 169                         * format doesn't explicitly end in a newline.)
 170                         */
 171                        if (buf.len && buf.buf[buf.len - 1] == '\n')
 172                                graph_show_padding(revs->graph);
 173                        putchar(info->hdr_termination);
 174                } else {
 175                        /*
 176                         * If the message buffer is empty, just show
 177                         * the rest of the graph output for this
 178                         * commit.
 179                         */
 180                        if (graph_show_remainder(revs->graph))
 181                                putchar('\n');
 182                        if (revs->commit_format == CMIT_FMT_ONELINE)
 183                                putchar('\n');
 184                }
 185                strbuf_release(&buf);
 186        } else {
 187                if (graph_show_remainder(revs->graph))
 188                        putchar('\n');
 189        }
 190        maybe_flush_or_die(stdout, "stdout");
 191        finish_commit(commit, data);
 192}
 193
 194static void finish_commit(struct commit *commit, void *data)
 195{
 196        if (commit->parents) {
 197                free_commit_list(commit->parents);
 198                commit->parents = NULL;
 199        }
 200        free_commit_buffer(commit);
 201}
 202
 203static inline void finish_object__ma(struct object *obj)
 204{
 205        /*
 206         * Whether or not we try to dynamically fetch missing objects
 207         * from the server, we currently DO NOT have the object.  We
 208         * can either print, allow (ignore), or conditionally allow
 209         * (ignore) them.
 210         */
 211        switch (arg_missing_action) {
 212        case MA_ERROR:
 213                die("missing %s object '%s'",
 214                    type_name(obj->type), oid_to_hex(&obj->oid));
 215                return;
 216
 217        case MA_ALLOW_ANY:
 218                return;
 219
 220        case MA_PRINT:
 221                oidset_insert(&missing_objects, &obj->oid);
 222                return;
 223
 224        case MA_ALLOW_PROMISOR:
 225                if (is_promisor_object(&obj->oid))
 226                        return;
 227                die("unexpected missing %s object '%s'",
 228                    type_name(obj->type), oid_to_hex(&obj->oid));
 229                return;
 230
 231        default:
 232                BUG("unhandled missing_action");
 233                return;
 234        }
 235}
 236
 237static int finish_object(struct object *obj, const char *name, void *cb_data)
 238{
 239        struct rev_list_info *info = cb_data;
 240        if (!has_object_file(&obj->oid)) {
 241                finish_object__ma(obj);
 242                return 1;
 243        }
 244        if (info->revs->verify_objects && !obj->parsed && obj->type != OBJ_COMMIT)
 245                parse_object(the_repository, &obj->oid);
 246        return 0;
 247}
 248
 249static void show_object(struct object *obj, const char *name, void *cb_data)
 250{
 251        struct rev_list_info *info = cb_data;
 252        if (finish_object(obj, name, cb_data))
 253                return;
 254        display_progress(progress, ++progress_counter);
 255        if (info->flags & REV_LIST_QUIET)
 256                return;
 257        show_object_with_name(stdout, obj, name);
 258}
 259
 260static void show_edge(struct commit *commit)
 261{
 262        printf("-%s\n", oid_to_hex(&commit->object.oid));
 263}
 264
 265static void print_var_str(const char *var, const char *val)
 266{
 267        printf("%s='%s'\n", var, val);
 268}
 269
 270static void print_var_int(const char *var, int val)
 271{
 272        printf("%s=%d\n", var, val);
 273}
 274
 275static int show_bisect_vars(struct rev_list_info *info, int reaches, int all)
 276{
 277        int cnt, flags = info->flags;
 278        char hex[GIT_MAX_HEXSZ + 1] = "";
 279        struct commit_list *tried;
 280        struct rev_info *revs = info->revs;
 281
 282        if (!revs->commits)
 283                return 1;
 284
 285        revs->commits = filter_skipped(revs->commits, &tried,
 286                                       flags & BISECT_SHOW_ALL,
 287                                       NULL, NULL);
 288
 289        /*
 290         * revs->commits can reach "reaches" commits among
 291         * "all" commits.  If it is good, then there are
 292         * (all-reaches) commits left to be bisected.
 293         * On the other hand, if it is bad, then the set
 294         * to bisect is "reaches".
 295         * A bisect set of size N has (N-1) commits further
 296         * to test, as we already know one bad one.
 297         */
 298        cnt = all - reaches;
 299        if (cnt < reaches)
 300                cnt = reaches;
 301
 302        if (revs->commits)
 303                oid_to_hex_r(hex, &revs->commits->item->object.oid);
 304
 305        if (flags & BISECT_SHOW_ALL) {
 306                traverse_commit_list(revs, show_commit, show_object, info);
 307                printf("------\n");
 308        }
 309
 310        print_var_str("bisect_rev", hex);
 311        print_var_int("bisect_nr", cnt - 1);
 312        print_var_int("bisect_good", all - reaches - 1);
 313        print_var_int("bisect_bad", reaches - 1);
 314        print_var_int("bisect_all", all);
 315        print_var_int("bisect_steps", estimate_bisect_steps(all));
 316
 317        return 0;
 318}
 319
 320static int show_object_fast(
 321        const struct object_id *oid,
 322        enum object_type type,
 323        int exclude,
 324        uint32_t name_hash,
 325        struct packed_git *found_pack,
 326        off_t found_offset)
 327{
 328        fprintf(stdout, "%s\n", oid_to_hex(oid));
 329        return 1;
 330}
 331
 332static inline int parse_missing_action_value(const char *value)
 333{
 334        if (!strcmp(value, "error")) {
 335                arg_missing_action = MA_ERROR;
 336                return 1;
 337        }
 338
 339        if (!strcmp(value, "allow-any")) {
 340                arg_missing_action = MA_ALLOW_ANY;
 341                fetch_if_missing = 0;
 342                return 1;
 343        }
 344
 345        if (!strcmp(value, "print")) {
 346                arg_missing_action = MA_PRINT;
 347                fetch_if_missing = 0;
 348                return 1;
 349        }
 350
 351        if (!strcmp(value, "allow-promisor")) {
 352                arg_missing_action = MA_ALLOW_PROMISOR;
 353                fetch_if_missing = 0;
 354                return 1;
 355        }
 356
 357        return 0;
 358}
 359
 360int cmd_rev_list(int argc, const char **argv, const char *prefix)
 361{
 362        struct rev_info revs;
 363        struct rev_list_info info;
 364        int i;
 365        int bisect_list = 0;
 366        int bisect_show_vars = 0;
 367        int bisect_find_all = 0;
 368        int use_bitmap_index = 0;
 369        const char *show_progress = NULL;
 370
 371        if (argc == 2 && !strcmp(argv[1], "-h"))
 372                usage(rev_list_usage);
 373
 374        git_config(git_default_config, NULL);
 375        repo_init_revisions(the_repository, &revs, prefix);
 376        revs.abbrev = DEFAULT_ABBREV;
 377        revs.allow_exclude_promisor_objects_opt = 1;
 378        revs.commit_format = CMIT_FMT_UNSPECIFIED;
 379        revs.do_not_die_on_missing_tree = 1;
 380
 381        /*
 382         * Scan the argument list before invoking setup_revisions(), so that we
 383         * know if fetch_if_missing needs to be set to 0.
 384         *
 385         * "--exclude-promisor-objects" acts as a pre-filter on missing objects
 386         * by not crossing the boundary from realized objects to promisor
 387         * objects.
 388         *
 389         * Let "--missing" to conditionally set fetch_if_missing.
 390         */
 391        for (i = 1; i < argc; i++) {
 392                const char *arg = argv[i];
 393                if (!strcmp(arg, "--exclude-promisor-objects")) {
 394                        fetch_if_missing = 0;
 395                        revs.exclude_promisor_objects = 1;
 396                        break;
 397                }
 398        }
 399        for (i = 1; i < argc; i++) {
 400                const char *arg = argv[i];
 401                if (skip_prefix(arg, "--missing=", &arg)) {
 402                        if (revs.exclude_promisor_objects)
 403                                die(_("cannot combine --exclude-promisor-objects and --missing"));
 404                        if (parse_missing_action_value(arg))
 405                                break;
 406                }
 407        }
 408
 409        argc = setup_revisions(argc, argv, &revs, NULL);
 410
 411        memset(&info, 0, sizeof(info));
 412        info.revs = &revs;
 413        if (revs.bisect)
 414                bisect_list = 1;
 415
 416        if (revs.diffopt.flags.quick)
 417                info.flags |= REV_LIST_QUIET;
 418        for (i = 1 ; i < argc; i++) {
 419                const char *arg = argv[i];
 420
 421                if (!strcmp(arg, "--header")) {
 422                        revs.verbose_header = 1;
 423                        continue;
 424                }
 425                if (!strcmp(arg, "--timestamp")) {
 426                        info.show_timestamp = 1;
 427                        continue;
 428                }
 429                if (!strcmp(arg, "--bisect")) {
 430                        bisect_list = 1;
 431                        continue;
 432                }
 433                if (!strcmp(arg, "--bisect-all")) {
 434                        bisect_list = 1;
 435                        bisect_find_all = 1;
 436                        info.flags |= BISECT_SHOW_ALL;
 437                        revs.show_decorations = 1;
 438                        continue;
 439                }
 440                if (!strcmp(arg, "--bisect-vars")) {
 441                        bisect_list = 1;
 442                        bisect_show_vars = 1;
 443                        continue;
 444                }
 445                if (!strcmp(arg, "--use-bitmap-index")) {
 446                        use_bitmap_index = 1;
 447                        continue;
 448                }
 449                if (!strcmp(arg, "--test-bitmap")) {
 450                        test_bitmap_walk(&revs);
 451                        return 0;
 452                }
 453                if (skip_prefix(arg, "--progress=", &arg)) {
 454                        show_progress = arg;
 455                        continue;
 456                }
 457
 458                if (skip_prefix(arg, ("--" CL_ARG__FILTER "="), &arg)) {
 459                        parse_list_objects_filter(&filter_options, arg);
 460                        if (filter_options.choice && !revs.blob_objects)
 461                                die(_("object filtering requires --objects"));
 462                        if (filter_options.choice == LOFC_SPARSE_OID &&
 463                            !filter_options.sparse_oid_value)
 464                                die(_("invalid sparse value '%s'"),
 465                                    filter_options.filter_spec);
 466                        continue;
 467                }
 468                if (!strcmp(arg, ("--no-" CL_ARG__FILTER))) {
 469                        list_objects_filter_set_no_filter(&filter_options);
 470                        continue;
 471                }
 472                if (!strcmp(arg, "--filter-print-omitted")) {
 473                        arg_print_omitted = 1;
 474                        continue;
 475                }
 476
 477                if (!strcmp(arg, "--exclude-promisor-objects"))
 478                        continue; /* already handled above */
 479                if (skip_prefix(arg, "--missing=", &arg))
 480                        continue; /* already handled above */
 481
 482                usage(rev_list_usage);
 483
 484        }
 485        if (revs.commit_format != CMIT_FMT_UNSPECIFIED) {
 486                /* The command line has a --pretty  */
 487                info.hdr_termination = '\n';
 488                if (revs.commit_format == CMIT_FMT_ONELINE)
 489                        info.header_prefix = "";
 490                else
 491                        info.header_prefix = "commit ";
 492        }
 493        else if (revs.verbose_header)
 494                /* Only --header was specified */
 495                revs.commit_format = CMIT_FMT_RAW;
 496
 497        if ((!revs.commits && reflog_walk_empty(revs.reflog_info) &&
 498             (!(revs.tag_objects || revs.tree_objects || revs.blob_objects) &&
 499              !revs.pending.nr) &&
 500             !revs.rev_input_given && !revs.read_from_stdin) ||
 501            revs.diff)
 502                usage(rev_list_usage);
 503
 504        if (revs.show_notes)
 505                die(_("rev-list does not support display of notes"));
 506
 507        if (filter_options.choice && use_bitmap_index)
 508                die(_("cannot combine --use-bitmap-index with object filtering"));
 509
 510        save_commit_buffer = (revs.verbose_header ||
 511                              revs.grep_filter.pattern_list ||
 512                              revs.grep_filter.header_list);
 513        if (bisect_list)
 514                revs.limited = 1;
 515
 516        if (show_progress)
 517                progress = start_delayed_progress(show_progress, 0);
 518
 519        if (use_bitmap_index && !revs.prune) {
 520                if (revs.count && !revs.left_right && !revs.cherry_mark) {
 521                        uint32_t commit_count;
 522                        int max_count = revs.max_count;
 523                        struct bitmap_index *bitmap_git;
 524                        if ((bitmap_git = prepare_bitmap_walk(&revs))) {
 525                                count_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);
 526                                if (max_count >= 0 && max_count < commit_count)
 527                                        commit_count = max_count;
 528                                printf("%d\n", commit_count);
 529                                free_bitmap_index(bitmap_git);
 530                                return 0;
 531                        }
 532                } else if (revs.max_count < 0 &&
 533                           revs.tag_objects && revs.tree_objects && revs.blob_objects) {
 534                        struct bitmap_index *bitmap_git;
 535                        if ((bitmap_git = prepare_bitmap_walk(&revs))) {
 536                                traverse_bitmap_commit_list(bitmap_git, &show_object_fast);
 537                                free_bitmap_index(bitmap_git);
 538                                return 0;
 539                        }
 540                }
 541        }
 542
 543        if (prepare_revision_walk(&revs))
 544                die("revision walk setup failed");
 545        if (revs.tree_objects)
 546                mark_edges_uninteresting(&revs, show_edge, 0);
 547
 548        if (bisect_list) {
 549                int reaches, all;
 550
 551                find_bisection(&revs.commits, &reaches, &all, bisect_find_all);
 552
 553                if (bisect_show_vars)
 554                        return show_bisect_vars(&info, reaches, all);
 555        }
 556
 557        if (arg_print_omitted)
 558                oidset_init(&omitted_objects, DEFAULT_OIDSET_SIZE);
 559        if (arg_missing_action == MA_PRINT)
 560                oidset_init(&missing_objects, DEFAULT_OIDSET_SIZE);
 561
 562        traverse_commit_list_filtered(
 563                &filter_options, &revs, show_commit, show_object, &info,
 564                (arg_print_omitted ? &omitted_objects : NULL));
 565
 566        if (arg_print_omitted) {
 567                struct oidset_iter iter;
 568                struct object_id *oid;
 569                oidset_iter_init(&omitted_objects, &iter);
 570                while ((oid = oidset_iter_next(&iter)))
 571                        printf("~%s\n", oid_to_hex(oid));
 572                oidset_clear(&omitted_objects);
 573        }
 574        if (arg_missing_action == MA_PRINT) {
 575                struct oidset_iter iter;
 576                struct object_id *oid;
 577                oidset_iter_init(&missing_objects, &iter);
 578                while ((oid = oidset_iter_next(&iter)))
 579                        printf("?%s\n", oid_to_hex(oid));
 580                oidset_clear(&missing_objects);
 581        }
 582
 583        stop_progress(&progress);
 584
 585        if (revs.count) {
 586                if (revs.left_right && revs.cherry_mark)
 587                        printf("%d\t%d\t%d\n", revs.count_left, revs.count_right, revs.count_same);
 588                else if (revs.left_right)
 589                        printf("%d\t%d\n", revs.count_left, revs.count_right);
 590                else if (revs.cherry_mark)
 591                        printf("%d\t%d\n", revs.count_left + revs.count_right, revs.count_same);
 592                else
 593                        printf("%d\n", revs.count_left + revs.count_right);
 594        }
 595
 596        return 0;
 597}