8d045162661a81e779b18e1295d470f4194d2f50
   1#include "cache.h"
   2#include "tag.h"
   3#include "blob.h"
   4#include "tree.h"
   5#include "commit.h"
   6#include "diff.h"
   7#include "refs.h"
   8#include "revision.h"
   9#include "graph.h"
  10#include "grep.h"
  11#include "reflog-walk.h"
  12#include "patch-ids.h"
  13#include "decorate.h"
  14#include "log-tree.h"
  15#include "string-list.h"
  16#include "line-log.h"
  17#include "mailmap.h"
  18#include "commit-slab.h"
  19#include "dir.h"
  20#include "cache-tree.h"
  21#include "bisect.h"
  22#include "worktree.h"
  23
  24volatile show_early_output_fn_t show_early_output;
  25
  26static const char *term_bad;
  27static const char *term_good;
  28
  29void show_object_with_name(FILE *out, struct object *obj, const char *name)
  30{
  31        const char *p;
  32
  33        fprintf(out, "%s ", oid_to_hex(&obj->oid));
  34        for (p = name; *p && *p != '\n'; p++)
  35                fputc(*p, out);
  36        fputc('\n', out);
  37}
  38
  39static void mark_blob_uninteresting(struct blob *blob)
  40{
  41        if (!blob)
  42                return;
  43        if (blob->object.flags & UNINTERESTING)
  44                return;
  45        blob->object.flags |= UNINTERESTING;
  46}
  47
  48static void mark_tree_contents_uninteresting(struct tree *tree)
  49{
  50        struct tree_desc desc;
  51        struct name_entry entry;
  52        struct object *obj = &tree->object;
  53
  54        if (!has_object_file(&obj->oid))
  55                return;
  56        if (parse_tree(tree) < 0)
  57                die("bad tree %s", oid_to_hex(&obj->oid));
  58
  59        init_tree_desc(&desc, tree->buffer, tree->size);
  60        while (tree_entry(&desc, &entry)) {
  61                switch (object_type(entry.mode)) {
  62                case OBJ_TREE:
  63                        mark_tree_uninteresting(lookup_tree(entry.oid));
  64                        break;
  65                case OBJ_BLOB:
  66                        mark_blob_uninteresting(lookup_blob(entry.oid));
  67                        break;
  68                default:
  69                        /* Subproject commit - not in this repository */
  70                        break;
  71                }
  72        }
  73
  74        /*
  75         * We don't care about the tree any more
  76         * after it has been marked uninteresting.
  77         */
  78        free_tree_buffer(tree);
  79}
  80
  81void mark_tree_uninteresting(struct tree *tree)
  82{
  83        struct object *obj;
  84
  85        if (!tree)
  86                return;
  87
  88        obj = &tree->object;
  89        if (obj->flags & UNINTERESTING)
  90                return;
  91        obj->flags |= UNINTERESTING;
  92        mark_tree_contents_uninteresting(tree);
  93}
  94
  95void mark_parents_uninteresting(struct commit *commit)
  96{
  97        struct commit_list *parents = NULL, *l;
  98
  99        for (l = commit->parents; l; l = l->next)
 100                commit_list_insert(l->item, &parents);
 101
 102        while (parents) {
 103                struct commit *commit = pop_commit(&parents);
 104
 105                while (commit) {
 106                        /*
 107                         * A missing commit is ok iff its parent is marked
 108                         * uninteresting.
 109                         *
 110                         * We just mark such a thing parsed, so that when
 111                         * it is popped next time around, we won't be trying
 112                         * to parse it and get an error.
 113                         */
 114                        if (!has_object_file(&commit->object.oid))
 115                                commit->object.parsed = 1;
 116
 117                        if (commit->object.flags & UNINTERESTING)
 118                                break;
 119
 120                        commit->object.flags |= UNINTERESTING;
 121
 122                        /*
 123                         * Normally we haven't parsed the parent
 124                         * yet, so we won't have a parent of a parent
 125                         * here. However, it may turn out that we've
 126                         * reached this commit some other way (where it
 127                         * wasn't uninteresting), in which case we need
 128                         * to mark its parents recursively too..
 129                         */
 130                        if (!commit->parents)
 131                                break;
 132
 133                        for (l = commit->parents->next; l; l = l->next)
 134                                commit_list_insert(l->item, &parents);
 135                        commit = commit->parents->item;
 136                }
 137        }
 138}
 139
 140static void add_pending_object_with_path(struct rev_info *revs,
 141                                         struct object *obj,
 142                                         const char *name, unsigned mode,
 143                                         const char *path)
 144{
 145        if (!obj)
 146                return;
 147        if (revs->no_walk && (obj->flags & UNINTERESTING))
 148                revs->no_walk = 0;
 149        if (revs->reflog_info && obj->type == OBJ_COMMIT) {
 150                struct strbuf buf = STRBUF_INIT;
 151                int len = interpret_branch_name(name, 0, &buf, 0);
 152
 153                if (0 < len && name[len] && buf.len)
 154                        strbuf_addstr(&buf, name + len);
 155                add_reflog_for_walk(revs->reflog_info,
 156                                    (struct commit *)obj,
 157                                    buf.buf[0] ? buf.buf: name);
 158                strbuf_release(&buf);
 159                return; /* do not add the commit itself */
 160        }
 161        add_object_array_with_path(obj, name, &revs->pending, mode, path);
 162}
 163
 164static void add_pending_object_with_mode(struct rev_info *revs,
 165                                         struct object *obj,
 166                                         const char *name, unsigned mode)
 167{
 168        add_pending_object_with_path(revs, obj, name, mode, NULL);
 169}
 170
 171void add_pending_object(struct rev_info *revs,
 172                        struct object *obj, const char *name)
 173{
 174        add_pending_object_with_mode(revs, obj, name, S_IFINVALID);
 175}
 176
 177void add_head_to_pending(struct rev_info *revs)
 178{
 179        struct object_id oid;
 180        struct object *obj;
 181        if (get_oid("HEAD", &oid))
 182                return;
 183        obj = parse_object(&oid);
 184        if (!obj)
 185                return;
 186        add_pending_object(revs, obj, "HEAD");
 187}
 188
 189static struct object *get_reference(struct rev_info *revs, const char *name,
 190                                    const struct object_id *oid,
 191                                    unsigned int flags)
 192{
 193        struct object *object;
 194
 195        object = parse_object(oid);
 196        if (!object) {
 197                if (revs->ignore_missing)
 198                        return object;
 199                die("bad object %s", name);
 200        }
 201        object->flags |= flags;
 202        return object;
 203}
 204
 205void add_pending_oid(struct rev_info *revs, const char *name,
 206                      const struct object_id *oid, unsigned int flags)
 207{
 208        struct object *object = get_reference(revs, name, oid, flags);
 209        add_pending_object(revs, object, name);
 210}
 211
 212static struct commit *handle_commit(struct rev_info *revs,
 213                                    struct object_array_entry *entry)
 214{
 215        struct object *object = entry->item;
 216        const char *name = entry->name;
 217        const char *path = entry->path;
 218        unsigned int mode = entry->mode;
 219        unsigned long flags = object->flags;
 220
 221        /*
 222         * Tag object? Look what it points to..
 223         */
 224        while (object->type == OBJ_TAG) {
 225                struct tag *tag = (struct tag *) object;
 226                if (revs->tag_objects && !(flags & UNINTERESTING))
 227                        add_pending_object(revs, object, tag->tag);
 228                if (!tag->tagged)
 229                        die("bad tag");
 230                object = parse_object(&tag->tagged->oid);
 231                if (!object) {
 232                        if (revs->ignore_missing_links || (flags & UNINTERESTING))
 233                                return NULL;
 234                        die("bad object %s", oid_to_hex(&tag->tagged->oid));
 235                }
 236                object->flags |= flags;
 237                /*
 238                 * We'll handle the tagged object by looping or dropping
 239                 * through to the non-tag handlers below. Do not
 240                 * propagate path data from the tag's pending entry.
 241                 */
 242                path = NULL;
 243                mode = 0;
 244        }
 245
 246        /*
 247         * Commit object? Just return it, we'll do all the complex
 248         * reachability crud.
 249         */
 250        if (object->type == OBJ_COMMIT) {
 251                struct commit *commit = (struct commit *)object;
 252                if (parse_commit(commit) < 0)
 253                        die("unable to parse commit %s", name);
 254                if (flags & UNINTERESTING) {
 255                        mark_parents_uninteresting(commit);
 256                        revs->limited = 1;
 257                }
 258                if (revs->show_source && !commit->util)
 259                        commit->util = xstrdup(name);
 260                return commit;
 261        }
 262
 263        /*
 264         * Tree object? Either mark it uninteresting, or add it
 265         * to the list of objects to look at later..
 266         */
 267        if (object->type == OBJ_TREE) {
 268                struct tree *tree = (struct tree *)object;
 269                if (!revs->tree_objects)
 270                        return NULL;
 271                if (flags & UNINTERESTING) {
 272                        mark_tree_contents_uninteresting(tree);
 273                        return NULL;
 274                }
 275                add_pending_object_with_path(revs, object, name, mode, path);
 276                return NULL;
 277        }
 278
 279        /*
 280         * Blob object? You know the drill by now..
 281         */
 282        if (object->type == OBJ_BLOB) {
 283                if (!revs->blob_objects)
 284                        return NULL;
 285                if (flags & UNINTERESTING)
 286                        return NULL;
 287                add_pending_object_with_path(revs, object, name, mode, path);
 288                return NULL;
 289        }
 290        die("%s is unknown object", name);
 291}
 292
 293static int everybody_uninteresting(struct commit_list *orig,
 294                                   struct commit **interesting_cache)
 295{
 296        struct commit_list *list = orig;
 297
 298        if (*interesting_cache) {
 299                struct commit *commit = *interesting_cache;
 300                if (!(commit->object.flags & UNINTERESTING))
 301                        return 0;
 302        }
 303
 304        while (list) {
 305                struct commit *commit = list->item;
 306                list = list->next;
 307                if (commit->object.flags & UNINTERESTING)
 308                        continue;
 309
 310                *interesting_cache = commit;
 311                return 0;
 312        }
 313        return 1;
 314}
 315
 316/*
 317 * A definition of "relevant" commit that we can use to simplify limited graphs
 318 * by eliminating side branches.
 319 *
 320 * A "relevant" commit is one that is !UNINTERESTING (ie we are including it
 321 * in our list), or that is a specified BOTTOM commit. Then after computing
 322 * a limited list, during processing we can generally ignore boundary merges
 323 * coming from outside the graph, (ie from irrelevant parents), and treat
 324 * those merges as if they were single-parent. TREESAME is defined to consider
 325 * only relevant parents, if any. If we are TREESAME to our on-graph parents,
 326 * we don't care if we were !TREESAME to non-graph parents.
 327 *
 328 * Treating bottom commits as relevant ensures that a limited graph's
 329 * connection to the actual bottom commit is not viewed as a side branch, but
 330 * treated as part of the graph. For example:
 331 *
 332 *   ....Z...A---X---o---o---B
 333 *        .     /
 334 *         W---Y
 335 *
 336 * When computing "A..B", the A-X connection is at least as important as
 337 * Y-X, despite A being flagged UNINTERESTING.
 338 *
 339 * And when computing --ancestry-path "A..B", the A-X connection is more
 340 * important than Y-X, despite both A and Y being flagged UNINTERESTING.
 341 */
 342static inline int relevant_commit(struct commit *commit)
 343{
 344        return (commit->object.flags & (UNINTERESTING | BOTTOM)) != UNINTERESTING;
 345}
 346
 347/*
 348 * Return a single relevant commit from a parent list. If we are a TREESAME
 349 * commit, and this selects one of our parents, then we can safely simplify to
 350 * that parent.
 351 */
 352static struct commit *one_relevant_parent(const struct rev_info *revs,
 353                                          struct commit_list *orig)
 354{
 355        struct commit_list *list = orig;
 356        struct commit *relevant = NULL;
 357
 358        if (!orig)
 359                return NULL;
 360
 361        /*
 362         * For 1-parent commits, or if first-parent-only, then return that
 363         * first parent (even if not "relevant" by the above definition).
 364         * TREESAME will have been set purely on that parent.
 365         */
 366        if (revs->first_parent_only || !orig->next)
 367                return orig->item;
 368
 369        /*
 370         * For multi-parent commits, identify a sole relevant parent, if any.
 371         * If we have only one relevant parent, then TREESAME will be set purely
 372         * with regard to that parent, and we can simplify accordingly.
 373         *
 374         * If we have more than one relevant parent, or no relevant parents
 375         * (and multiple irrelevant ones), then we can't select a parent here
 376         * and return NULL.
 377         */
 378        while (list) {
 379                struct commit *commit = list->item;
 380                list = list->next;
 381                if (relevant_commit(commit)) {
 382                        if (relevant)
 383                                return NULL;
 384                        relevant = commit;
 385                }
 386        }
 387        return relevant;
 388}
 389
 390/*
 391 * The goal is to get REV_TREE_NEW as the result only if the
 392 * diff consists of all '+' (and no other changes), REV_TREE_OLD
 393 * if the whole diff is removal of old data, and otherwise
 394 * REV_TREE_DIFFERENT (of course if the trees are the same we
 395 * want REV_TREE_SAME).
 396 * That means that once we get to REV_TREE_DIFFERENT, we do not
 397 * have to look any further.
 398 */
 399static int tree_difference = REV_TREE_SAME;
 400
 401static void file_add_remove(struct diff_options *options,
 402                    int addremove, unsigned mode,
 403                    const struct object_id *oid,
 404                    int oid_valid,
 405                    const char *fullpath, unsigned dirty_submodule)
 406{
 407        int diff = addremove == '+' ? REV_TREE_NEW : REV_TREE_OLD;
 408
 409        tree_difference |= diff;
 410        if (tree_difference == REV_TREE_DIFFERENT)
 411                DIFF_OPT_SET(options, HAS_CHANGES);
 412}
 413
 414static void file_change(struct diff_options *options,
 415                 unsigned old_mode, unsigned new_mode,
 416                 const struct object_id *old_oid,
 417                 const struct object_id *new_oid,
 418                 int old_oid_valid, int new_oid_valid,
 419                 const char *fullpath,
 420                 unsigned old_dirty_submodule, unsigned new_dirty_submodule)
 421{
 422        tree_difference = REV_TREE_DIFFERENT;
 423        DIFF_OPT_SET(options, HAS_CHANGES);
 424}
 425
 426static int rev_compare_tree(struct rev_info *revs,
 427                            struct commit *parent, struct commit *commit)
 428{
 429        struct tree *t1 = parent->tree;
 430        struct tree *t2 = commit->tree;
 431
 432        if (!t1)
 433                return REV_TREE_NEW;
 434        if (!t2)
 435                return REV_TREE_OLD;
 436
 437        if (revs->simplify_by_decoration) {
 438                /*
 439                 * If we are simplifying by decoration, then the commit
 440                 * is worth showing if it has a tag pointing at it.
 441                 */
 442                if (get_name_decoration(&commit->object))
 443                        return REV_TREE_DIFFERENT;
 444                /*
 445                 * A commit that is not pointed by a tag is uninteresting
 446                 * if we are not limited by path.  This means that you will
 447                 * see the usual "commits that touch the paths" plus any
 448                 * tagged commit by specifying both --simplify-by-decoration
 449                 * and pathspec.
 450                 */
 451                if (!revs->prune_data.nr)
 452                        return REV_TREE_SAME;
 453        }
 454
 455        tree_difference = REV_TREE_SAME;
 456        DIFF_OPT_CLR(&revs->pruning, HAS_CHANGES);
 457        if (diff_tree_oid(&t1->object.oid, &t2->object.oid, "",
 458                           &revs->pruning) < 0)
 459                return REV_TREE_DIFFERENT;
 460        return tree_difference;
 461}
 462
 463static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
 464{
 465        int retval;
 466        struct tree *t1 = commit->tree;
 467
 468        if (!t1)
 469                return 0;
 470
 471        tree_difference = REV_TREE_SAME;
 472        DIFF_OPT_CLR(&revs->pruning, HAS_CHANGES);
 473        retval = diff_tree_oid(NULL, &t1->object.oid, "", &revs->pruning);
 474
 475        return retval >= 0 && (tree_difference == REV_TREE_SAME);
 476}
 477
 478struct treesame_state {
 479        unsigned int nparents;
 480        unsigned char treesame[FLEX_ARRAY];
 481};
 482
 483static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)
 484{
 485        unsigned n = commit_list_count(commit->parents);
 486        struct treesame_state *st = xcalloc(1, st_add(sizeof(*st), n));
 487        st->nparents = n;
 488        add_decoration(&revs->treesame, &commit->object, st);
 489        return st;
 490}
 491
 492/*
 493 * Must be called immediately after removing the nth_parent from a commit's
 494 * parent list, if we are maintaining the per-parent treesame[] decoration.
 495 * This does not recalculate the master TREESAME flag - update_treesame()
 496 * should be called to update it after a sequence of treesame[] modifications
 497 * that may have affected it.
 498 */
 499static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned nth_parent)
 500{
 501        struct treesame_state *st;
 502        int old_same;
 503
 504        if (!commit->parents) {
 505                /*
 506                 * Have just removed the only parent from a non-merge.
 507                 * Different handling, as we lack decoration.
 508                 */
 509                if (nth_parent != 0)
 510                        die("compact_treesame %u", nth_parent);
 511                old_same = !!(commit->object.flags & TREESAME);
 512                if (rev_same_tree_as_empty(revs, commit))
 513                        commit->object.flags |= TREESAME;
 514                else
 515                        commit->object.flags &= ~TREESAME;
 516                return old_same;
 517        }
 518
 519        st = lookup_decoration(&revs->treesame, &commit->object);
 520        if (!st || nth_parent >= st->nparents)
 521                die("compact_treesame %u", nth_parent);
 522
 523        old_same = st->treesame[nth_parent];
 524        memmove(st->treesame + nth_parent,
 525                st->treesame + nth_parent + 1,
 526                st->nparents - nth_parent - 1);
 527
 528        /*
 529         * If we've just become a non-merge commit, update TREESAME
 530         * immediately, and remove the no-longer-needed decoration.
 531         * If still a merge, defer update until update_treesame().
 532         */
 533        if (--st->nparents == 1) {
 534                if (commit->parents->next)
 535                        die("compact_treesame parents mismatch");
 536                if (st->treesame[0] && revs->dense)
 537                        commit->object.flags |= TREESAME;
 538                else
 539                        commit->object.flags &= ~TREESAME;
 540                free(add_decoration(&revs->treesame, &commit->object, NULL));
 541        }
 542
 543        return old_same;
 544}
 545
 546static unsigned update_treesame(struct rev_info *revs, struct commit *commit)
 547{
 548        if (commit->parents && commit->parents->next) {
 549                unsigned n;
 550                struct treesame_state *st;
 551                struct commit_list *p;
 552                unsigned relevant_parents;
 553                unsigned relevant_change, irrelevant_change;
 554
 555                st = lookup_decoration(&revs->treesame, &commit->object);
 556                if (!st)
 557                        die("update_treesame %s", oid_to_hex(&commit->object.oid));
 558                relevant_parents = 0;
 559                relevant_change = irrelevant_change = 0;
 560                for (p = commit->parents, n = 0; p; n++, p = p->next) {
 561                        if (relevant_commit(p->item)) {
 562                                relevant_change |= !st->treesame[n];
 563                                relevant_parents++;
 564                        } else
 565                                irrelevant_change |= !st->treesame[n];
 566                }
 567                if (relevant_parents ? relevant_change : irrelevant_change)
 568                        commit->object.flags &= ~TREESAME;
 569                else
 570                        commit->object.flags |= TREESAME;
 571        }
 572
 573        return commit->object.flags & TREESAME;
 574}
 575
 576static inline int limiting_can_increase_treesame(const struct rev_info *revs)
 577{
 578        /*
 579         * TREESAME is irrelevant unless prune && dense;
 580         * if simplify_history is set, we can't have a mixture of TREESAME and
 581         *    !TREESAME INTERESTING parents (and we don't have treesame[]
 582         *    decoration anyway);
 583         * if first_parent_only is set, then the TREESAME flag is locked
 584         *    against the first parent (and again we lack treesame[] decoration).
 585         */
 586        return revs->prune && revs->dense &&
 587               !revs->simplify_history &&
 588               !revs->first_parent_only;
 589}
 590
 591static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 592{
 593        struct commit_list **pp, *parent;
 594        struct treesame_state *ts = NULL;
 595        int relevant_change = 0, irrelevant_change = 0;
 596        int relevant_parents, nth_parent;
 597
 598        /*
 599         * If we don't do pruning, everything is interesting
 600         */
 601        if (!revs->prune)
 602                return;
 603
 604        if (!commit->tree)
 605                return;
 606
 607        if (!commit->parents) {
 608                if (rev_same_tree_as_empty(revs, commit))
 609                        commit->object.flags |= TREESAME;
 610                return;
 611        }
 612
 613        /*
 614         * Normal non-merge commit? If we don't want to make the
 615         * history dense, we consider it always to be a change..
 616         */
 617        if (!revs->dense && !commit->parents->next)
 618                return;
 619
 620        for (pp = &commit->parents, nth_parent = 0, relevant_parents = 0;
 621             (parent = *pp) != NULL;
 622             pp = &parent->next, nth_parent++) {
 623                struct commit *p = parent->item;
 624                if (relevant_commit(p))
 625                        relevant_parents++;
 626
 627                if (nth_parent == 1) {
 628                        /*
 629                         * This our second loop iteration - so we now know
 630                         * we're dealing with a merge.
 631                         *
 632                         * Do not compare with later parents when we care only about
 633                         * the first parent chain, in order to avoid derailing the
 634                         * traversal to follow a side branch that brought everything
 635                         * in the path we are limited to by the pathspec.
 636                         */
 637                        if (revs->first_parent_only)
 638                                break;
 639                        /*
 640                         * If this will remain a potentially-simplifiable
 641                         * merge, remember per-parent treesame if needed.
 642                         * Initialise the array with the comparison from our
 643                         * first iteration.
 644                         */
 645                        if (revs->treesame.name &&
 646                            !revs->simplify_history &&
 647                            !(commit->object.flags & UNINTERESTING)) {
 648                                ts = initialise_treesame(revs, commit);
 649                                if (!(irrelevant_change || relevant_change))
 650                                        ts->treesame[0] = 1;
 651                        }
 652                }
 653                if (parse_commit(p) < 0)
 654                        die("cannot simplify commit %s (because of %s)",
 655                            oid_to_hex(&commit->object.oid),
 656                            oid_to_hex(&p->object.oid));
 657                switch (rev_compare_tree(revs, p, commit)) {
 658                case REV_TREE_SAME:
 659                        if (!revs->simplify_history || !relevant_commit(p)) {
 660                                /* Even if a merge with an uninteresting
 661                                 * side branch brought the entire change
 662                                 * we are interested in, we do not want
 663                                 * to lose the other branches of this
 664                                 * merge, so we just keep going.
 665                                 */
 666                                if (ts)
 667                                        ts->treesame[nth_parent] = 1;
 668                                continue;
 669                        }
 670                        parent->next = NULL;
 671                        commit->parents = parent;
 672                        commit->object.flags |= TREESAME;
 673                        return;
 674
 675                case REV_TREE_NEW:
 676                        if (revs->remove_empty_trees &&
 677                            rev_same_tree_as_empty(revs, p)) {
 678                                /* We are adding all the specified
 679                                 * paths from this parent, so the
 680                                 * history beyond this parent is not
 681                                 * interesting.  Remove its parents
 682                                 * (they are grandparents for us).
 683                                 * IOW, we pretend this parent is a
 684                                 * "root" commit.
 685                                 */
 686                                if (parse_commit(p) < 0)
 687                                        die("cannot simplify commit %s (invalid %s)",
 688                                            oid_to_hex(&commit->object.oid),
 689                                            oid_to_hex(&p->object.oid));
 690                                p->parents = NULL;
 691                        }
 692                /* fallthrough */
 693                case REV_TREE_OLD:
 694                case REV_TREE_DIFFERENT:
 695                        if (relevant_commit(p))
 696                                relevant_change = 1;
 697                        else
 698                                irrelevant_change = 1;
 699                        continue;
 700                }
 701                die("bad tree compare for commit %s", oid_to_hex(&commit->object.oid));
 702        }
 703
 704        /*
 705         * TREESAME is straightforward for single-parent commits. For merge
 706         * commits, it is most useful to define it so that "irrelevant"
 707         * parents cannot make us !TREESAME - if we have any relevant
 708         * parents, then we only consider TREESAMEness with respect to them,
 709         * allowing irrelevant merges from uninteresting branches to be
 710         * simplified away. Only if we have only irrelevant parents do we
 711         * base TREESAME on them. Note that this logic is replicated in
 712         * update_treesame, which should be kept in sync.
 713         */
 714        if (relevant_parents ? !relevant_change : !irrelevant_change)
 715                commit->object.flags |= TREESAME;
 716}
 717
 718static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head,
 719                    struct commit_list *cached_base, struct commit_list **cache)
 720{
 721        struct commit_list *new_entry;
 722
 723        if (cached_base && p->date < cached_base->item->date)
 724                new_entry = commit_list_insert_by_date(p, &cached_base->next);
 725        else
 726                new_entry = commit_list_insert_by_date(p, head);
 727
 728        if (cache && (!*cache || p->date < (*cache)->item->date))
 729                *cache = new_entry;
 730}
 731
 732static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 733                    struct commit_list **list, struct commit_list **cache_ptr)
 734{
 735        struct commit_list *parent = commit->parents;
 736        unsigned left_flag;
 737        struct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;
 738
 739        if (commit->object.flags & ADDED)
 740                return 0;
 741        commit->object.flags |= ADDED;
 742
 743        if (revs->include_check &&
 744            !revs->include_check(commit, revs->include_check_data))
 745                return 0;
 746
 747        /*
 748         * If the commit is uninteresting, don't try to
 749         * prune parents - we want the maximal uninteresting
 750         * set.
 751         *
 752         * Normally we haven't parsed the parent
 753         * yet, so we won't have a parent of a parent
 754         * here. However, it may turn out that we've
 755         * reached this commit some other way (where it
 756         * wasn't uninteresting), in which case we need
 757         * to mark its parents recursively too..
 758         */
 759        if (commit->object.flags & UNINTERESTING) {
 760                while (parent) {
 761                        struct commit *p = parent->item;
 762                        parent = parent->next;
 763                        if (p)
 764                                p->object.flags |= UNINTERESTING;
 765                        if (parse_commit_gently(p, 1) < 0)
 766                                continue;
 767                        if (p->parents)
 768                                mark_parents_uninteresting(p);
 769                        if (p->object.flags & SEEN)
 770                                continue;
 771                        p->object.flags |= SEEN;
 772                        commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 773                }
 774                return 0;
 775        }
 776
 777        /*
 778         * Ok, the commit wasn't uninteresting. Try to
 779         * simplify the commit history and find the parent
 780         * that has no differences in the path set if one exists.
 781         */
 782        try_to_simplify_commit(revs, commit);
 783
 784        if (revs->no_walk)
 785                return 0;
 786
 787        left_flag = (commit->object.flags & SYMMETRIC_LEFT);
 788
 789        for (parent = commit->parents; parent; parent = parent->next) {
 790                struct commit *p = parent->item;
 791
 792                if (parse_commit_gently(p, revs->ignore_missing_links) < 0)
 793                        return -1;
 794                if (revs->show_source && !p->util)
 795                        p->util = commit->util;
 796                p->object.flags |= left_flag;
 797                if (!(p->object.flags & SEEN)) {
 798                        p->object.flags |= SEEN;
 799                        commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 800                }
 801                if (revs->first_parent_only)
 802                        break;
 803        }
 804        return 0;
 805}
 806
 807static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 808{
 809        struct commit_list *p;
 810        int left_count = 0, right_count = 0;
 811        int left_first;
 812        struct patch_ids ids;
 813        unsigned cherry_flag;
 814
 815        /* First count the commits on the left and on the right */
 816        for (p = list; p; p = p->next) {
 817                struct commit *commit = p->item;
 818                unsigned flags = commit->object.flags;
 819                if (flags & BOUNDARY)
 820                        ;
 821                else if (flags & SYMMETRIC_LEFT)
 822                        left_count++;
 823                else
 824                        right_count++;
 825        }
 826
 827        if (!left_count || !right_count)
 828                return;
 829
 830        left_first = left_count < right_count;
 831        init_patch_ids(&ids);
 832        ids.diffopts.pathspec = revs->diffopt.pathspec;
 833
 834        /* Compute patch-ids for one side */
 835        for (p = list; p; p = p->next) {
 836                struct commit *commit = p->item;
 837                unsigned flags = commit->object.flags;
 838
 839                if (flags & BOUNDARY)
 840                        continue;
 841                /*
 842                 * If we have fewer left, left_first is set and we omit
 843                 * commits on the right branch in this loop.  If we have
 844                 * fewer right, we skip the left ones.
 845                 */
 846                if (left_first != !!(flags & SYMMETRIC_LEFT))
 847                        continue;
 848                add_commit_patch_id(commit, &ids);
 849        }
 850
 851        /* either cherry_mark or cherry_pick are true */
 852        cherry_flag = revs->cherry_mark ? PATCHSAME : SHOWN;
 853
 854        /* Check the other side */
 855        for (p = list; p; p = p->next) {
 856                struct commit *commit = p->item;
 857                struct patch_id *id;
 858                unsigned flags = commit->object.flags;
 859
 860                if (flags & BOUNDARY)
 861                        continue;
 862                /*
 863                 * If we have fewer left, left_first is set and we omit
 864                 * commits on the left branch in this loop.
 865                 */
 866                if (left_first == !!(flags & SYMMETRIC_LEFT))
 867                        continue;
 868
 869                /*
 870                 * Have we seen the same patch id?
 871                 */
 872                id = has_commit_patch_id(commit, &ids);
 873                if (!id)
 874                        continue;
 875
 876                commit->object.flags |= cherry_flag;
 877                id->commit->object.flags |= cherry_flag;
 878        }
 879
 880        free_patch_ids(&ids);
 881}
 882
 883/* How many extra uninteresting commits we want to see.. */
 884#define SLOP 5
 885
 886static int still_interesting(struct commit_list *src, timestamp_t date, int slop,
 887                             struct commit **interesting_cache)
 888{
 889        /*
 890         * No source list at all? We're definitely done..
 891         */
 892        if (!src)
 893                return 0;
 894
 895        /*
 896         * Does the destination list contain entries with a date
 897         * before the source list? Definitely _not_ done.
 898         */
 899        if (date <= src->item->date)
 900                return SLOP;
 901
 902        /*
 903         * Does the source list still have interesting commits in
 904         * it? Definitely not done..
 905         */
 906        if (!everybody_uninteresting(src, interesting_cache))
 907                return SLOP;
 908
 909        /* Ok, we're closing in.. */
 910        return slop-1;
 911}
 912
 913/*
 914 * "rev-list --ancestry-path A..B" computes commits that are ancestors
 915 * of B but not ancestors of A but further limits the result to those
 916 * that are descendants of A.  This takes the list of bottom commits and
 917 * the result of "A..B" without --ancestry-path, and limits the latter
 918 * further to the ones that can reach one of the commits in "bottom".
 919 */
 920static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list)
 921{
 922        struct commit_list *p;
 923        struct commit_list *rlist = NULL;
 924        int made_progress;
 925
 926        /*
 927         * Reverse the list so that it will be likely that we would
 928         * process parents before children.
 929         */
 930        for (p = list; p; p = p->next)
 931                commit_list_insert(p->item, &rlist);
 932
 933        for (p = bottom; p; p = p->next)
 934                p->item->object.flags |= TMP_MARK;
 935
 936        /*
 937         * Mark the ones that can reach bottom commits in "list",
 938         * in a bottom-up fashion.
 939         */
 940        do {
 941                made_progress = 0;
 942                for (p = rlist; p; p = p->next) {
 943                        struct commit *c = p->item;
 944                        struct commit_list *parents;
 945                        if (c->object.flags & (TMP_MARK | UNINTERESTING))
 946                                continue;
 947                        for (parents = c->parents;
 948                             parents;
 949                             parents = parents->next) {
 950                                if (!(parents->item->object.flags & TMP_MARK))
 951                                        continue;
 952                                c->object.flags |= TMP_MARK;
 953                                made_progress = 1;
 954                                break;
 955                        }
 956                }
 957        } while (made_progress);
 958
 959        /*
 960         * NEEDSWORK: decide if we want to remove parents that are
 961         * not marked with TMP_MARK from commit->parents for commits
 962         * in the resulting list.  We may not want to do that, though.
 963         */
 964
 965        /*
 966         * The ones that are not marked with TMP_MARK are uninteresting
 967         */
 968        for (p = list; p; p = p->next) {
 969                struct commit *c = p->item;
 970                if (c->object.flags & TMP_MARK)
 971                        continue;
 972                c->object.flags |= UNINTERESTING;
 973        }
 974
 975        /* We are done with the TMP_MARK */
 976        for (p = list; p; p = p->next)
 977                p->item->object.flags &= ~TMP_MARK;
 978        for (p = bottom; p; p = p->next)
 979                p->item->object.flags &= ~TMP_MARK;
 980        free_commit_list(rlist);
 981}
 982
 983/*
 984 * Before walking the history, keep the set of "negative" refs the
 985 * caller has asked to exclude.
 986 *
 987 * This is used to compute "rev-list --ancestry-path A..B", as we need
 988 * to filter the result of "A..B" further to the ones that can actually
 989 * reach A.
 990 */
 991static struct commit_list *collect_bottom_commits(struct commit_list *list)
 992{
 993        struct commit_list *elem, *bottom = NULL;
 994        for (elem = list; elem; elem = elem->next)
 995                if (elem->item->object.flags & BOTTOM)
 996                        commit_list_insert(elem->item, &bottom);
 997        return bottom;
 998}
 999
1000/* Assumes either left_only or right_only is set */
1001static void limit_left_right(struct commit_list *list, struct rev_info *revs)
1002{
1003        struct commit_list *p;
1004
1005        for (p = list; p; p = p->next) {
1006                struct commit *commit = p->item;
1007
1008                if (revs->right_only) {
1009                        if (commit->object.flags & SYMMETRIC_LEFT)
1010                                commit->object.flags |= SHOWN;
1011                } else  /* revs->left_only is set */
1012                        if (!(commit->object.flags & SYMMETRIC_LEFT))
1013                                commit->object.flags |= SHOWN;
1014        }
1015}
1016
1017static int limit_list(struct rev_info *revs)
1018{
1019        int slop = SLOP;
1020        timestamp_t date = TIME_MAX;
1021        struct commit_list *list = revs->commits;
1022        struct commit_list *newlist = NULL;
1023        struct commit_list **p = &newlist;
1024        struct commit_list *bottom = NULL;
1025        struct commit *interesting_cache = NULL;
1026
1027        if (revs->ancestry_path) {
1028                bottom = collect_bottom_commits(list);
1029                if (!bottom)
1030                        die("--ancestry-path given but there are no bottom commits");
1031        }
1032
1033        while (list) {
1034                struct commit *commit = pop_commit(&list);
1035                struct object *obj = &commit->object;
1036                show_early_output_fn_t show;
1037
1038                if (commit == interesting_cache)
1039                        interesting_cache = NULL;
1040
1041                if (revs->max_age != -1 && (commit->date < revs->max_age))
1042                        obj->flags |= UNINTERESTING;
1043                if (add_parents_to_list(revs, commit, &list, NULL) < 0)
1044                        return -1;
1045                if (obj->flags & UNINTERESTING) {
1046                        mark_parents_uninteresting(commit);
1047                        if (revs->show_all)
1048                                p = &commit_list_insert(commit, p)->next;
1049                        slop = still_interesting(list, date, slop, &interesting_cache);
1050                        if (slop)
1051                                continue;
1052                        /* If showing all, add the whole pending list to the end */
1053                        if (revs->show_all)
1054                                *p = list;
1055                        break;
1056                }
1057                if (revs->min_age != -1 && (commit->date > revs->min_age))
1058                        continue;
1059                date = commit->date;
1060                p = &commit_list_insert(commit, p)->next;
1061
1062                show = show_early_output;
1063                if (!show)
1064                        continue;
1065
1066                show(revs, newlist);
1067                show_early_output = NULL;
1068        }
1069        if (revs->cherry_pick || revs->cherry_mark)
1070                cherry_pick_list(newlist, revs);
1071
1072        if (revs->left_only || revs->right_only)
1073                limit_left_right(newlist, revs);
1074
1075        if (bottom) {
1076                limit_to_ancestry(bottom, newlist);
1077                free_commit_list(bottom);
1078        }
1079
1080        /*
1081         * Check if any commits have become TREESAME by some of their parents
1082         * becoming UNINTERESTING.
1083         */
1084        if (limiting_can_increase_treesame(revs))
1085                for (list = newlist; list; list = list->next) {
1086                        struct commit *c = list->item;
1087                        if (c->object.flags & (UNINTERESTING | TREESAME))
1088                                continue;
1089                        update_treesame(revs, c);
1090                }
1091
1092        revs->commits = newlist;
1093        return 0;
1094}
1095
1096/*
1097 * Add an entry to refs->cmdline with the specified information.
1098 * *name is copied.
1099 */
1100static void add_rev_cmdline(struct rev_info *revs,
1101                            struct object *item,
1102                            const char *name,
1103                            int whence,
1104                            unsigned flags)
1105{
1106        struct rev_cmdline_info *info = &revs->cmdline;
1107        int nr = info->nr;
1108
1109        ALLOC_GROW(info->rev, nr + 1, info->alloc);
1110        info->rev[nr].item = item;
1111        info->rev[nr].name = xstrdup(name);
1112        info->rev[nr].whence = whence;
1113        info->rev[nr].flags = flags;
1114        info->nr++;
1115}
1116
1117static void add_rev_cmdline_list(struct rev_info *revs,
1118                                 struct commit_list *commit_list,
1119                                 int whence,
1120                                 unsigned flags)
1121{
1122        while (commit_list) {
1123                struct object *object = &commit_list->item->object;
1124                add_rev_cmdline(revs, object, oid_to_hex(&object->oid),
1125                                whence, flags);
1126                commit_list = commit_list->next;
1127        }
1128}
1129
1130struct all_refs_cb {
1131        int all_flags;
1132        int warned_bad_reflog;
1133        struct rev_info *all_revs;
1134        const char *name_for_errormsg;
1135};
1136
1137int ref_excluded(struct string_list *ref_excludes, const char *path)
1138{
1139        struct string_list_item *item;
1140
1141        if (!ref_excludes)
1142                return 0;
1143        for_each_string_list_item(item, ref_excludes) {
1144                if (!wildmatch(item->string, path, 0))
1145                        return 1;
1146        }
1147        return 0;
1148}
1149
1150static int handle_one_ref(const char *path, const struct object_id *oid,
1151                          int flag, void *cb_data)
1152{
1153        struct all_refs_cb *cb = cb_data;
1154        struct object *object;
1155
1156        if (ref_excluded(cb->all_revs->ref_excludes, path))
1157            return 0;
1158
1159        object = get_reference(cb->all_revs, path, oid, cb->all_flags);
1160        add_rev_cmdline(cb->all_revs, object, path, REV_CMD_REF, cb->all_flags);
1161        add_pending_oid(cb->all_revs, path, oid, cb->all_flags);
1162        return 0;
1163}
1164
1165static void init_all_refs_cb(struct all_refs_cb *cb, struct rev_info *revs,
1166        unsigned flags)
1167{
1168        cb->all_revs = revs;
1169        cb->all_flags = flags;
1170        revs->rev_input_given = 1;
1171}
1172
1173void clear_ref_exclusion(struct string_list **ref_excludes_p)
1174{
1175        if (*ref_excludes_p) {
1176                string_list_clear(*ref_excludes_p, 0);
1177                free(*ref_excludes_p);
1178        }
1179        *ref_excludes_p = NULL;
1180}
1181
1182void add_ref_exclusion(struct string_list **ref_excludes_p, const char *exclude)
1183{
1184        if (!*ref_excludes_p) {
1185                *ref_excludes_p = xcalloc(1, sizeof(**ref_excludes_p));
1186                (*ref_excludes_p)->strdup_strings = 1;
1187        }
1188        string_list_append(*ref_excludes_p, exclude);
1189}
1190
1191static void handle_refs(struct ref_store *refs,
1192                        struct rev_info *revs, unsigned flags,
1193                        int (*for_each)(struct ref_store *, each_ref_fn, void *))
1194{
1195        struct all_refs_cb cb;
1196
1197        if (!refs) {
1198                /* this could happen with uninitialized submodules */
1199                return;
1200        }
1201
1202        init_all_refs_cb(&cb, revs, flags);
1203        for_each(refs, handle_one_ref, &cb);
1204}
1205
1206static void handle_one_reflog_commit(struct object_id *oid, void *cb_data)
1207{
1208        struct all_refs_cb *cb = cb_data;
1209        if (!is_null_oid(oid)) {
1210                struct object *o = parse_object(oid);
1211                if (o) {
1212                        o->flags |= cb->all_flags;
1213                        /* ??? CMDLINEFLAGS ??? */
1214                        add_pending_object(cb->all_revs, o, "");
1215                }
1216                else if (!cb->warned_bad_reflog) {
1217                        warning("reflog of '%s' references pruned commits",
1218                                cb->name_for_errormsg);
1219                        cb->warned_bad_reflog = 1;
1220                }
1221        }
1222}
1223
1224static int handle_one_reflog_ent(struct object_id *ooid, struct object_id *noid,
1225                const char *email, timestamp_t timestamp, int tz,
1226                const char *message, void *cb_data)
1227{
1228        handle_one_reflog_commit(ooid, cb_data);
1229        handle_one_reflog_commit(noid, cb_data);
1230        return 0;
1231}
1232
1233static int handle_one_reflog(const char *path, const struct object_id *oid,
1234                             int flag, void *cb_data)
1235{
1236        struct all_refs_cb *cb = cb_data;
1237        cb->warned_bad_reflog = 0;
1238        cb->name_for_errormsg = path;
1239        for_each_reflog_ent(path, handle_one_reflog_ent, cb_data);
1240        return 0;
1241}
1242
1243void add_reflogs_to_pending(struct rev_info *revs, unsigned flags)
1244{
1245        struct all_refs_cb cb;
1246
1247        cb.all_revs = revs;
1248        cb.all_flags = flags;
1249        for_each_reflog(handle_one_reflog, &cb);
1250}
1251
1252static void add_cache_tree(struct cache_tree *it, struct rev_info *revs,
1253                           struct strbuf *path)
1254{
1255        size_t baselen = path->len;
1256        int i;
1257
1258        if (it->entry_count >= 0) {
1259                struct tree *tree = lookup_tree(&it->oid);
1260                add_pending_object_with_path(revs, &tree->object, "",
1261                                             040000, path->buf);
1262        }
1263
1264        for (i = 0; i < it->subtree_nr; i++) {
1265                struct cache_tree_sub *sub = it->down[i];
1266                strbuf_addf(path, "%s%s", baselen ? "/" : "", sub->name);
1267                add_cache_tree(sub->cache_tree, revs, path);
1268                strbuf_setlen(path, baselen);
1269        }
1270
1271}
1272
1273static void do_add_index_objects_to_pending(struct rev_info *revs,
1274                                            struct index_state *istate)
1275{
1276        int i;
1277
1278        for (i = 0; i < istate->cache_nr; i++) {
1279                struct cache_entry *ce = istate->cache[i];
1280                struct blob *blob;
1281
1282                if (S_ISGITLINK(ce->ce_mode))
1283                        continue;
1284
1285                blob = lookup_blob(&ce->oid);
1286                if (!blob)
1287                        die("unable to add index blob to traversal");
1288                add_pending_object_with_path(revs, &blob->object, "",
1289                                             ce->ce_mode, ce->name);
1290        }
1291
1292        if (istate->cache_tree) {
1293                struct strbuf path = STRBUF_INIT;
1294                add_cache_tree(istate->cache_tree, revs, &path);
1295                strbuf_release(&path);
1296        }
1297}
1298
1299void add_index_objects_to_pending(struct rev_info *revs, unsigned int flags)
1300{
1301        struct worktree **worktrees, **p;
1302
1303        read_cache();
1304        do_add_index_objects_to_pending(revs, &the_index);
1305
1306        if (revs->single_worktree)
1307                return;
1308
1309        worktrees = get_worktrees(0);
1310        for (p = worktrees; *p; p++) {
1311                struct worktree *wt = *p;
1312                struct index_state istate = { NULL };
1313
1314                if (wt->is_current)
1315                        continue; /* current index already taken care of */
1316
1317                if (read_index_from(&istate,
1318                                    worktree_git_path(wt, "index")) > 0)
1319                        do_add_index_objects_to_pending(revs, &istate);
1320                discard_index(&istate);
1321        }
1322        free_worktrees(worktrees);
1323}
1324
1325static int add_parents_only(struct rev_info *revs, const char *arg_, int flags,
1326                            int exclude_parent)
1327{
1328        struct object_id oid;
1329        struct object *it;
1330        struct commit *commit;
1331        struct commit_list *parents;
1332        int parent_number;
1333        const char *arg = arg_;
1334
1335        if (*arg == '^') {
1336                flags ^= UNINTERESTING | BOTTOM;
1337                arg++;
1338        }
1339        if (get_oid_committish(arg, &oid))
1340                return 0;
1341        while (1) {
1342                it = get_reference(revs, arg, &oid, 0);
1343                if (!it && revs->ignore_missing)
1344                        return 0;
1345                if (it->type != OBJ_TAG)
1346                        break;
1347                if (!((struct tag*)it)->tagged)
1348                        return 0;
1349                oidcpy(&oid, &((struct tag*)it)->tagged->oid);
1350        }
1351        if (it->type != OBJ_COMMIT)
1352                return 0;
1353        commit = (struct commit *)it;
1354        if (exclude_parent &&
1355            exclude_parent > commit_list_count(commit->parents))
1356                return 0;
1357        for (parents = commit->parents, parent_number = 1;
1358             parents;
1359             parents = parents->next, parent_number++) {
1360                if (exclude_parent && parent_number != exclude_parent)
1361                        continue;
1362
1363                it = &parents->item->object;
1364                it->flags |= flags;
1365                add_rev_cmdline(revs, it, arg_, REV_CMD_PARENTS_ONLY, flags);
1366                add_pending_object(revs, it, arg);
1367        }
1368        return 1;
1369}
1370
1371void init_revisions(struct rev_info *revs, const char *prefix)
1372{
1373        memset(revs, 0, sizeof(*revs));
1374
1375        revs->abbrev = DEFAULT_ABBREV;
1376        revs->ignore_merges = 1;
1377        revs->simplify_history = 1;
1378        DIFF_OPT_SET(&revs->pruning, RECURSIVE);
1379        DIFF_OPT_SET(&revs->pruning, QUICK);
1380        revs->pruning.add_remove = file_add_remove;
1381        revs->pruning.change = file_change;
1382        revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
1383        revs->dense = 1;
1384        revs->prefix = prefix;
1385        revs->max_age = -1;
1386        revs->min_age = -1;
1387        revs->skip_count = -1;
1388        revs->max_count = -1;
1389        revs->max_parents = -1;
1390        revs->expand_tabs_in_log = -1;
1391
1392        revs->commit_format = CMIT_FMT_DEFAULT;
1393        revs->expand_tabs_in_log_default = 8;
1394
1395        init_grep_defaults();
1396        grep_init(&revs->grep_filter, prefix);
1397        revs->grep_filter.status_only = 1;
1398
1399        diff_setup(&revs->diffopt);
1400        if (prefix && !revs->diffopt.prefix) {
1401                revs->diffopt.prefix = prefix;
1402                revs->diffopt.prefix_length = strlen(prefix);
1403        }
1404
1405        revs->notes_opt.use_default_notes = -1;
1406}
1407
1408static void add_pending_commit_list(struct rev_info *revs,
1409                                    struct commit_list *commit_list,
1410                                    unsigned int flags)
1411{
1412        while (commit_list) {
1413                struct object *object = &commit_list->item->object;
1414                object->flags |= flags;
1415                add_pending_object(revs, object, oid_to_hex(&object->oid));
1416                commit_list = commit_list->next;
1417        }
1418}
1419
1420static void prepare_show_merge(struct rev_info *revs)
1421{
1422        struct commit_list *bases;
1423        struct commit *head, *other;
1424        struct object_id oid;
1425        const char **prune = NULL;
1426        int i, prune_num = 1; /* counting terminating NULL */
1427
1428        if (get_oid("HEAD", &oid))
1429                die("--merge without HEAD?");
1430        head = lookup_commit_or_die(&oid, "HEAD");
1431        if (get_oid("MERGE_HEAD", &oid))
1432                die("--merge without MERGE_HEAD?");
1433        other = lookup_commit_or_die(&oid, "MERGE_HEAD");
1434        add_pending_object(revs, &head->object, "HEAD");
1435        add_pending_object(revs, &other->object, "MERGE_HEAD");
1436        bases = get_merge_bases(head, other);
1437        add_rev_cmdline_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING | BOTTOM);
1438        add_pending_commit_list(revs, bases, UNINTERESTING | BOTTOM);
1439        free_commit_list(bases);
1440        head->object.flags |= SYMMETRIC_LEFT;
1441
1442        if (!active_nr)
1443                read_cache();
1444        for (i = 0; i < active_nr; i++) {
1445                const struct cache_entry *ce = active_cache[i];
1446                if (!ce_stage(ce))
1447                        continue;
1448                if (ce_path_match(ce, &revs->prune_data, NULL)) {
1449                        prune_num++;
1450                        REALLOC_ARRAY(prune, prune_num);
1451                        prune[prune_num-2] = ce->name;
1452                        prune[prune_num-1] = NULL;
1453                }
1454                while ((i+1 < active_nr) &&
1455                       ce_same_name(ce, active_cache[i+1]))
1456                        i++;
1457        }
1458        clear_pathspec(&revs->prune_data);
1459        parse_pathspec(&revs->prune_data, PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
1460                       PATHSPEC_PREFER_FULL | PATHSPEC_LITERAL_PATH, "", prune);
1461        revs->limited = 1;
1462}
1463
1464static int dotdot_missing(const char *arg, char *dotdot,
1465                          struct rev_info *revs, int symmetric)
1466{
1467        if (revs->ignore_missing)
1468                return 0;
1469        /* de-munge so we report the full argument */
1470        *dotdot = '.';
1471        die(symmetric
1472            ? "Invalid symmetric difference expression %s"
1473            : "Invalid revision range %s", arg);
1474}
1475
1476static int handle_dotdot_1(const char *arg, char *dotdot,
1477                           struct rev_info *revs, int flags,
1478                           int cant_be_filename,
1479                           struct object_context *a_oc,
1480                           struct object_context *b_oc)
1481{
1482        const char *a_name, *b_name;
1483        struct object_id a_oid, b_oid;
1484        struct object *a_obj, *b_obj;
1485        unsigned int a_flags, b_flags;
1486        int symmetric = 0;
1487        unsigned int flags_exclude = flags ^ (UNINTERESTING | BOTTOM);
1488        unsigned int oc_flags = GET_OID_COMMITTISH | GET_OID_RECORD_PATH;
1489
1490        a_name = arg;
1491        if (!*a_name)
1492                a_name = "HEAD";
1493
1494        b_name = dotdot + 2;
1495        if (*b_name == '.') {
1496                symmetric = 1;
1497                b_name++;
1498        }
1499        if (!*b_name)
1500                b_name = "HEAD";
1501
1502        if (get_oid_with_context(a_name, oc_flags, &a_oid, a_oc) ||
1503            get_oid_with_context(b_name, oc_flags, &b_oid, b_oc))
1504                return -1;
1505
1506        if (!cant_be_filename) {
1507                *dotdot = '.';
1508                verify_non_filename(revs->prefix, arg);
1509                *dotdot = '\0';
1510        }
1511
1512        a_obj = parse_object(&a_oid);
1513        b_obj = parse_object(&b_oid);
1514        if (!a_obj || !b_obj)
1515                return dotdot_missing(arg, dotdot, revs, symmetric);
1516
1517        if (!symmetric) {
1518                /* just A..B */
1519                b_flags = flags;
1520                a_flags = flags_exclude;
1521        } else {
1522                /* A...B -- find merge bases between the two */
1523                struct commit *a, *b;
1524                struct commit_list *exclude;
1525
1526                a = lookup_commit_reference(&a_obj->oid);
1527                b = lookup_commit_reference(&b_obj->oid);
1528                if (!a || !b)
1529                        return dotdot_missing(arg, dotdot, revs, symmetric);
1530
1531                exclude = get_merge_bases(a, b);
1532                add_rev_cmdline_list(revs, exclude, REV_CMD_MERGE_BASE,
1533                                     flags_exclude);
1534                add_pending_commit_list(revs, exclude, flags_exclude);
1535                free_commit_list(exclude);
1536
1537                b_flags = flags;
1538                a_flags = flags | SYMMETRIC_LEFT;
1539        }
1540
1541        a_obj->flags |= a_flags;
1542        b_obj->flags |= b_flags;
1543        add_rev_cmdline(revs, a_obj, a_name, REV_CMD_LEFT, a_flags);
1544        add_rev_cmdline(revs, b_obj, b_name, REV_CMD_RIGHT, b_flags);
1545        add_pending_object_with_path(revs, a_obj, a_name, a_oc->mode, a_oc->path);
1546        add_pending_object_with_path(revs, b_obj, b_name, b_oc->mode, b_oc->path);
1547        return 0;
1548}
1549
1550static int handle_dotdot(const char *arg,
1551                         struct rev_info *revs, int flags,
1552                         int cant_be_filename)
1553{
1554        struct object_context a_oc, b_oc;
1555        char *dotdot = strstr(arg, "..");
1556        int ret;
1557
1558        if (!dotdot)
1559                return -1;
1560
1561        memset(&a_oc, 0, sizeof(a_oc));
1562        memset(&b_oc, 0, sizeof(b_oc));
1563
1564        *dotdot = '\0';
1565        ret = handle_dotdot_1(arg, dotdot, revs, flags, cant_be_filename,
1566                              &a_oc, &b_oc);
1567        *dotdot = '.';
1568
1569        free(a_oc.path);
1570        free(b_oc.path);
1571
1572        return ret;
1573}
1574
1575int handle_revision_arg(const char *arg_, struct rev_info *revs, int flags, unsigned revarg_opt)
1576{
1577        struct object_context oc;
1578        char *mark;
1579        struct object *object;
1580        struct object_id oid;
1581        int local_flags;
1582        const char *arg = arg_;
1583        int cant_be_filename = revarg_opt & REVARG_CANNOT_BE_FILENAME;
1584        unsigned get_sha1_flags = GET_OID_RECORD_PATH;
1585
1586        flags = flags & UNINTERESTING ? flags | BOTTOM : flags & ~BOTTOM;
1587
1588        if (!cant_be_filename && !strcmp(arg, "..")) {
1589                /*
1590                 * Just ".."?  That is not a range but the
1591                 * pathspec for the parent directory.
1592                 */
1593                return -1;
1594        }
1595
1596        if (!handle_dotdot(arg, revs, flags, revarg_opt))
1597                return 0;
1598
1599        mark = strstr(arg, "^@");
1600        if (mark && !mark[2]) {
1601                *mark = 0;
1602                if (add_parents_only(revs, arg, flags, 0))
1603                        return 0;
1604                *mark = '^';
1605        }
1606        mark = strstr(arg, "^!");
1607        if (mark && !mark[2]) {
1608                *mark = 0;
1609                if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), 0))
1610                        *mark = '^';
1611        }
1612        mark = strstr(arg, "^-");
1613        if (mark) {
1614                int exclude_parent = 1;
1615
1616                if (mark[2]) {
1617                        char *end;
1618                        exclude_parent = strtoul(mark + 2, &end, 10);
1619                        if (*end != '\0' || !exclude_parent)
1620                                return -1;
1621                }
1622
1623                *mark = 0;
1624                if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), exclude_parent))
1625                        *mark = '^';
1626        }
1627
1628        local_flags = 0;
1629        if (*arg == '^') {
1630                local_flags = UNINTERESTING | BOTTOM;
1631                arg++;
1632        }
1633
1634        if (revarg_opt & REVARG_COMMITTISH)
1635                get_sha1_flags |= GET_OID_COMMITTISH;
1636
1637        if (get_oid_with_context(arg, get_sha1_flags, &oid, &oc))
1638                return revs->ignore_missing ? 0 : -1;
1639        if (!cant_be_filename)
1640                verify_non_filename(revs->prefix, arg);
1641        object = get_reference(revs, arg, &oid, flags ^ local_flags);
1642        add_rev_cmdline(revs, object, arg_, REV_CMD_REV, flags ^ local_flags);
1643        add_pending_object_with_path(revs, object, arg, oc.mode, oc.path);
1644        free(oc.path);
1645        return 0;
1646}
1647
1648struct cmdline_pathspec {
1649        int alloc;
1650        int nr;
1651        const char **path;
1652};
1653
1654static void append_prune_data(struct cmdline_pathspec *prune, const char **av)
1655{
1656        while (*av) {
1657                ALLOC_GROW(prune->path, prune->nr + 1, prune->alloc);
1658                prune->path[prune->nr++] = *(av++);
1659        }
1660}
1661
1662static void read_pathspec_from_stdin(struct rev_info *revs, struct strbuf *sb,
1663                                     struct cmdline_pathspec *prune)
1664{
1665        while (strbuf_getline(sb, stdin) != EOF) {
1666                ALLOC_GROW(prune->path, prune->nr + 1, prune->alloc);
1667                prune->path[prune->nr++] = xstrdup(sb->buf);
1668        }
1669}
1670
1671static void read_revisions_from_stdin(struct rev_info *revs,
1672                                      struct cmdline_pathspec *prune)
1673{
1674        struct strbuf sb;
1675        int seen_dashdash = 0;
1676        int save_warning;
1677
1678        save_warning = warn_on_object_refname_ambiguity;
1679        warn_on_object_refname_ambiguity = 0;
1680
1681        strbuf_init(&sb, 1000);
1682        while (strbuf_getline(&sb, stdin) != EOF) {
1683                int len = sb.len;
1684                if (!len)
1685                        break;
1686                if (sb.buf[0] == '-') {
1687                        if (len == 2 && sb.buf[1] == '-') {
1688                                seen_dashdash = 1;
1689                                break;
1690                        }
1691                        die("options not supported in --stdin mode");
1692                }
1693                if (handle_revision_arg(sb.buf, revs, 0,
1694                                        REVARG_CANNOT_BE_FILENAME))
1695                        die("bad revision '%s'", sb.buf);
1696        }
1697        if (seen_dashdash)
1698                read_pathspec_from_stdin(revs, &sb, prune);
1699
1700        strbuf_release(&sb);
1701        warn_on_object_refname_ambiguity = save_warning;
1702}
1703
1704static void add_grep(struct rev_info *revs, const char *ptn, enum grep_pat_token what)
1705{
1706        append_grep_pattern(&revs->grep_filter, ptn, "command line", 0, what);
1707}
1708
1709static void add_header_grep(struct rev_info *revs, enum grep_header_field field, const char *pattern)
1710{
1711        append_header_grep_pattern(&revs->grep_filter, field, pattern);
1712}
1713
1714static void add_message_grep(struct rev_info *revs, const char *pattern)
1715{
1716        add_grep(revs, pattern, GREP_PATTERN_BODY);
1717}
1718
1719static int handle_revision_opt(struct rev_info *revs, int argc, const char **argv,
1720                               int *unkc, const char **unkv)
1721{
1722        const char *arg = argv[0];
1723        const char *optarg;
1724        int argcount;
1725
1726        /* pseudo revision arguments */
1727        if (!strcmp(arg, "--all") || !strcmp(arg, "--branches") ||
1728            !strcmp(arg, "--tags") || !strcmp(arg, "--remotes") ||
1729            !strcmp(arg, "--reflog") || !strcmp(arg, "--not") ||
1730            !strcmp(arg, "--no-walk") || !strcmp(arg, "--do-walk") ||
1731            !strcmp(arg, "--bisect") || starts_with(arg, "--glob=") ||
1732            !strcmp(arg, "--indexed-objects") ||
1733            starts_with(arg, "--exclude=") ||
1734            starts_with(arg, "--branches=") || starts_with(arg, "--tags=") ||
1735            starts_with(arg, "--remotes=") || starts_with(arg, "--no-walk="))
1736        {
1737                unkv[(*unkc)++] = arg;
1738                return 1;
1739        }
1740
1741        if ((argcount = parse_long_opt("max-count", argv, &optarg))) {
1742                revs->max_count = atoi(optarg);
1743                revs->no_walk = 0;
1744                return argcount;
1745        } else if ((argcount = parse_long_opt("skip", argv, &optarg))) {
1746                revs->skip_count = atoi(optarg);
1747                return argcount;
1748        } else if ((*arg == '-') && isdigit(arg[1])) {
1749                /* accept -<digit>, like traditional "head" */
1750                if (strtol_i(arg + 1, 10, &revs->max_count) < 0 ||
1751                    revs->max_count < 0)
1752                        die("'%s': not a non-negative integer", arg + 1);
1753                revs->no_walk = 0;
1754        } else if (!strcmp(arg, "-n")) {
1755                if (argc <= 1)
1756                        return error("-n requires an argument");
1757                revs->max_count = atoi(argv[1]);
1758                revs->no_walk = 0;
1759                return 2;
1760        } else if (skip_prefix(arg, "-n", &optarg)) {
1761                revs->max_count = atoi(optarg);
1762                revs->no_walk = 0;
1763        } else if ((argcount = parse_long_opt("max-age", argv, &optarg))) {
1764                revs->max_age = atoi(optarg);
1765                return argcount;
1766        } else if ((argcount = parse_long_opt("since", argv, &optarg))) {
1767                revs->max_age = approxidate(optarg);
1768                return argcount;
1769        } else if ((argcount = parse_long_opt("after", argv, &optarg))) {
1770                revs->max_age = approxidate(optarg);
1771                return argcount;
1772        } else if ((argcount = parse_long_opt("min-age", argv, &optarg))) {
1773                revs->min_age = atoi(optarg);
1774                return argcount;
1775        } else if ((argcount = parse_long_opt("before", argv, &optarg))) {
1776                revs->min_age = approxidate(optarg);
1777                return argcount;
1778        } else if ((argcount = parse_long_opt("until", argv, &optarg))) {
1779                revs->min_age = approxidate(optarg);
1780                return argcount;
1781        } else if (!strcmp(arg, "--first-parent")) {
1782                revs->first_parent_only = 1;
1783        } else if (!strcmp(arg, "--ancestry-path")) {
1784                revs->ancestry_path = 1;
1785                revs->simplify_history = 0;
1786                revs->limited = 1;
1787        } else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) {
1788                init_reflog_walk(&revs->reflog_info);
1789        } else if (!strcmp(arg, "--default")) {
1790                if (argc <= 1)
1791                        return error("bad --default argument");
1792                revs->def = argv[1];
1793                return 2;
1794        } else if (!strcmp(arg, "--merge")) {
1795                revs->show_merge = 1;
1796        } else if (!strcmp(arg, "--topo-order")) {
1797                revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
1798                revs->topo_order = 1;
1799        } else if (!strcmp(arg, "--simplify-merges")) {
1800                revs->simplify_merges = 1;
1801                revs->topo_order = 1;
1802                revs->rewrite_parents = 1;
1803                revs->simplify_history = 0;
1804                revs->limited = 1;
1805        } else if (!strcmp(arg, "--simplify-by-decoration")) {
1806                revs->simplify_merges = 1;
1807                revs->topo_order = 1;
1808                revs->rewrite_parents = 1;
1809                revs->simplify_history = 0;
1810                revs->simplify_by_decoration = 1;
1811                revs->limited = 1;
1812                revs->prune = 1;
1813                load_ref_decorations(DECORATE_SHORT_REFS);
1814        } else if (!strcmp(arg, "--date-order")) {
1815                revs->sort_order = REV_SORT_BY_COMMIT_DATE;
1816                revs->topo_order = 1;
1817        } else if (!strcmp(arg, "--author-date-order")) {
1818                revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
1819                revs->topo_order = 1;
1820        } else if (!strcmp(arg, "--early-output")) {
1821                revs->early_output = 100;
1822                revs->topo_order = 1;
1823        } else if (skip_prefix(arg, "--early-output=", &optarg)) {
1824                if (strtoul_ui(optarg, 10, &revs->early_output) < 0)
1825                        die("'%s': not a non-negative integer", optarg);
1826                revs->topo_order = 1;
1827        } else if (!strcmp(arg, "--parents")) {
1828                revs->rewrite_parents = 1;
1829                revs->print_parents = 1;
1830        } else if (!strcmp(arg, "--dense")) {
1831                revs->dense = 1;
1832        } else if (!strcmp(arg, "--sparse")) {
1833                revs->dense = 0;
1834        } else if (!strcmp(arg, "--show-all")) {
1835                revs->show_all = 1;
1836        } else if (!strcmp(arg, "--remove-empty")) {
1837                revs->remove_empty_trees = 1;
1838        } else if (!strcmp(arg, "--merges")) {
1839                revs->min_parents = 2;
1840        } else if (!strcmp(arg, "--no-merges")) {
1841                revs->max_parents = 1;
1842        } else if (skip_prefix(arg, "--min-parents=", &optarg)) {
1843                revs->min_parents = atoi(optarg);
1844        } else if (!strcmp(arg, "--no-min-parents")) {
1845                revs->min_parents = 0;
1846        } else if (skip_prefix(arg, "--max-parents=", &optarg)) {
1847                revs->max_parents = atoi(optarg);
1848        } else if (!strcmp(arg, "--no-max-parents")) {
1849                revs->max_parents = -1;
1850        } else if (!strcmp(arg, "--boundary")) {
1851                revs->boundary = 1;
1852        } else if (!strcmp(arg, "--left-right")) {
1853                revs->left_right = 1;
1854        } else if (!strcmp(arg, "--left-only")) {
1855                if (revs->right_only)
1856                        die("--left-only is incompatible with --right-only"
1857                            " or --cherry");
1858                revs->left_only = 1;
1859        } else if (!strcmp(arg, "--right-only")) {
1860                if (revs->left_only)
1861                        die("--right-only is incompatible with --left-only");
1862                revs->right_only = 1;
1863        } else if (!strcmp(arg, "--cherry")) {
1864                if (revs->left_only)
1865                        die("--cherry is incompatible with --left-only");
1866                revs->cherry_mark = 1;
1867                revs->right_only = 1;
1868                revs->max_parents = 1;
1869                revs->limited = 1;
1870        } else if (!strcmp(arg, "--count")) {
1871                revs->count = 1;
1872        } else if (!strcmp(arg, "--cherry-mark")) {
1873                if (revs->cherry_pick)
1874                        die("--cherry-mark is incompatible with --cherry-pick");
1875                revs->cherry_mark = 1;
1876                revs->limited = 1; /* needs limit_list() */
1877        } else if (!strcmp(arg, "--cherry-pick")) {
1878                if (revs->cherry_mark)
1879                        die("--cherry-pick is incompatible with --cherry-mark");
1880                revs->cherry_pick = 1;
1881                revs->limited = 1;
1882        } else if (!strcmp(arg, "--objects")) {
1883                revs->tag_objects = 1;
1884                revs->tree_objects = 1;
1885                revs->blob_objects = 1;
1886        } else if (!strcmp(arg, "--objects-edge")) {
1887                revs->tag_objects = 1;
1888                revs->tree_objects = 1;
1889                revs->blob_objects = 1;
1890                revs->edge_hint = 1;
1891        } else if (!strcmp(arg, "--objects-edge-aggressive")) {
1892                revs->tag_objects = 1;
1893                revs->tree_objects = 1;
1894                revs->blob_objects = 1;
1895                revs->edge_hint = 1;
1896                revs->edge_hint_aggressive = 1;
1897        } else if (!strcmp(arg, "--verify-objects")) {
1898                revs->tag_objects = 1;
1899                revs->tree_objects = 1;
1900                revs->blob_objects = 1;
1901                revs->verify_objects = 1;
1902        } else if (!strcmp(arg, "--unpacked")) {
1903                revs->unpacked = 1;
1904        } else if (starts_with(arg, "--unpacked=")) {
1905                die("--unpacked=<packfile> no longer supported.");
1906        } else if (!strcmp(arg, "-r")) {
1907                revs->diff = 1;
1908                DIFF_OPT_SET(&revs->diffopt, RECURSIVE);
1909        } else if (!strcmp(arg, "-t")) {
1910                revs->diff = 1;
1911                DIFF_OPT_SET(&revs->diffopt, RECURSIVE);
1912                DIFF_OPT_SET(&revs->diffopt, TREE_IN_RECURSIVE);
1913        } else if (!strcmp(arg, "-m")) {
1914                revs->ignore_merges = 0;
1915        } else if (!strcmp(arg, "-c")) {
1916                revs->diff = 1;
1917                revs->dense_combined_merges = 0;
1918                revs->combine_merges = 1;
1919        } else if (!strcmp(arg, "--cc")) {
1920                revs->diff = 1;
1921                revs->dense_combined_merges = 1;
1922                revs->combine_merges = 1;
1923        } else if (!strcmp(arg, "-v")) {
1924                revs->verbose_header = 1;
1925        } else if (!strcmp(arg, "--pretty")) {
1926                revs->verbose_header = 1;
1927                revs->pretty_given = 1;
1928                get_commit_format(NULL, revs);
1929        } else if (skip_prefix(arg, "--pretty=", &optarg) ||
1930                   skip_prefix(arg, "--format=", &optarg)) {
1931                /*
1932                 * Detached form ("--pretty X" as opposed to "--pretty=X")
1933                 * not allowed, since the argument is optional.
1934                 */
1935                revs->verbose_header = 1;
1936                revs->pretty_given = 1;
1937                get_commit_format(optarg, revs);
1938        } else if (!strcmp(arg, "--expand-tabs")) {
1939                revs->expand_tabs_in_log = 8;
1940        } else if (!strcmp(arg, "--no-expand-tabs")) {
1941                revs->expand_tabs_in_log = 0;
1942        } else if (skip_prefix(arg, "--expand-tabs=", &arg)) {
1943                int val;
1944                if (strtol_i(arg, 10, &val) < 0 || val < 0)
1945                        die("'%s': not a non-negative integer", arg);
1946                revs->expand_tabs_in_log = val;
1947        } else if (!strcmp(arg, "--show-notes") || !strcmp(arg, "--notes")) {
1948                revs->show_notes = 1;
1949                revs->show_notes_given = 1;
1950                revs->notes_opt.use_default_notes = 1;
1951        } else if (!strcmp(arg, "--show-signature")) {
1952                revs->show_signature = 1;
1953        } else if (!strcmp(arg, "--no-show-signature")) {
1954                revs->show_signature = 0;
1955        } else if (!strcmp(arg, "--show-linear-break")) {
1956                revs->break_bar = "                    ..........";
1957                revs->track_linear = 1;
1958                revs->track_first_time = 1;
1959        } else if (skip_prefix(arg, "--show-linear-break=", &optarg)) {
1960                revs->break_bar = xstrdup(optarg);
1961                revs->track_linear = 1;
1962                revs->track_first_time = 1;
1963        } else if (skip_prefix(arg, "--show-notes=", &optarg) ||
1964                   skip_prefix(arg, "--notes=", &optarg)) {
1965                struct strbuf buf = STRBUF_INIT;
1966                revs->show_notes = 1;
1967                revs->show_notes_given = 1;
1968                if (starts_with(arg, "--show-notes=") &&
1969                    revs->notes_opt.use_default_notes < 0)
1970                        revs->notes_opt.use_default_notes = 1;
1971                strbuf_addstr(&buf, optarg);
1972                expand_notes_ref(&buf);
1973                string_list_append(&revs->notes_opt.extra_notes_refs,
1974                                   strbuf_detach(&buf, NULL));
1975        } else if (!strcmp(arg, "--no-notes")) {
1976                revs->show_notes = 0;
1977                revs->show_notes_given = 1;
1978                revs->notes_opt.use_default_notes = -1;
1979                /* we have been strdup'ing ourselves, so trick
1980                 * string_list into free()ing strings */
1981                revs->notes_opt.extra_notes_refs.strdup_strings = 1;
1982                string_list_clear(&revs->notes_opt.extra_notes_refs, 0);
1983                revs->notes_opt.extra_notes_refs.strdup_strings = 0;
1984        } else if (!strcmp(arg, "--standard-notes")) {
1985                revs->show_notes_given = 1;
1986                revs->notes_opt.use_default_notes = 1;
1987        } else if (!strcmp(arg, "--no-standard-notes")) {
1988                revs->notes_opt.use_default_notes = 0;
1989        } else if (!strcmp(arg, "--oneline")) {
1990                revs->verbose_header = 1;
1991                get_commit_format("oneline", revs);
1992                revs->pretty_given = 1;
1993                revs->abbrev_commit = 1;
1994        } else if (!strcmp(arg, "--graph")) {
1995                revs->topo_order = 1;
1996                revs->rewrite_parents = 1;
1997                revs->graph = graph_init(revs);
1998        } else if (!strcmp(arg, "--root")) {
1999                revs->show_root_diff = 1;
2000        } else if (!strcmp(arg, "--no-commit-id")) {
2001                revs->no_commit_id = 1;
2002        } else if (!strcmp(arg, "--always")) {
2003                revs->always_show_header = 1;
2004        } else if (!strcmp(arg, "--no-abbrev")) {
2005                revs->abbrev = 0;
2006        } else if (!strcmp(arg, "--abbrev")) {
2007                revs->abbrev = DEFAULT_ABBREV;
2008        } else if (skip_prefix(arg, "--abbrev=", &optarg)) {
2009                revs->abbrev = strtoul(optarg, NULL, 10);
2010                if (revs->abbrev < MINIMUM_ABBREV)
2011                        revs->abbrev = MINIMUM_ABBREV;
2012                else if (revs->abbrev > 40)
2013                        revs->abbrev = 40;
2014        } else if (!strcmp(arg, "--abbrev-commit")) {
2015                revs->abbrev_commit = 1;
2016                revs->abbrev_commit_given = 1;
2017        } else if (!strcmp(arg, "--no-abbrev-commit")) {
2018                revs->abbrev_commit = 0;
2019        } else if (!strcmp(arg, "--full-diff")) {
2020                revs->diff = 1;
2021                revs->full_diff = 1;
2022        } else if (!strcmp(arg, "--full-history")) {
2023                revs->simplify_history = 0;
2024        } else if (!strcmp(arg, "--relative-date")) {
2025                revs->date_mode.type = DATE_RELATIVE;
2026                revs->date_mode_explicit = 1;
2027        } else if ((argcount = parse_long_opt("date", argv, &optarg))) {
2028                parse_date_format(optarg, &revs->date_mode);
2029                revs->date_mode_explicit = 1;
2030                return argcount;
2031        } else if (!strcmp(arg, "--log-size")) {
2032                revs->show_log_size = 1;
2033        }
2034        /*
2035         * Grepping the commit log
2036         */
2037        else if ((argcount = parse_long_opt("author", argv, &optarg))) {
2038                add_header_grep(revs, GREP_HEADER_AUTHOR, optarg);
2039                return argcount;
2040        } else if ((argcount = parse_long_opt("committer", argv, &optarg))) {
2041                add_header_grep(revs, GREP_HEADER_COMMITTER, optarg);
2042                return argcount;
2043        } else if ((argcount = parse_long_opt("grep-reflog", argv, &optarg))) {
2044                add_header_grep(revs, GREP_HEADER_REFLOG, optarg);
2045                return argcount;
2046        } else if ((argcount = parse_long_opt("grep", argv, &optarg))) {
2047                add_message_grep(revs, optarg);
2048                return argcount;
2049        } else if (!strcmp(arg, "--grep-debug")) {
2050                revs->grep_filter.debug = 1;
2051        } else if (!strcmp(arg, "--basic-regexp")) {
2052                revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_BRE;
2053        } else if (!strcmp(arg, "--extended-regexp") || !strcmp(arg, "-E")) {
2054                revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_ERE;
2055        } else if (!strcmp(arg, "--regexp-ignore-case") || !strcmp(arg, "-i")) {
2056                revs->grep_filter.ignore_case = 1;
2057                DIFF_OPT_SET(&revs->diffopt, PICKAXE_IGNORE_CASE);
2058        } else if (!strcmp(arg, "--fixed-strings") || !strcmp(arg, "-F")) {
2059                revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_FIXED;
2060        } else if (!strcmp(arg, "--perl-regexp") || !strcmp(arg, "-P")) {
2061                revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_PCRE;
2062        } else if (!strcmp(arg, "--all-match")) {
2063                revs->grep_filter.all_match = 1;
2064        } else if (!strcmp(arg, "--invert-grep")) {
2065                revs->invert_grep = 1;
2066        } else if ((argcount = parse_long_opt("encoding", argv, &optarg))) {
2067                if (strcmp(optarg, "none"))
2068                        git_log_output_encoding = xstrdup(optarg);
2069                else
2070                        git_log_output_encoding = "";
2071                return argcount;
2072        } else if (!strcmp(arg, "--reverse")) {
2073                revs->reverse ^= 1;
2074        } else if (!strcmp(arg, "--children")) {
2075                revs->children.name = "children";
2076                revs->limited = 1;
2077        } else if (!strcmp(arg, "--ignore-missing")) {
2078                revs->ignore_missing = 1;
2079        } else {
2080                int opts = diff_opt_parse(&revs->diffopt, argv, argc, revs->prefix);
2081                if (!opts)
2082                        unkv[(*unkc)++] = arg;
2083                return opts;
2084        }
2085        if (revs->graph && revs->track_linear)
2086                die("--show-linear-break and --graph are incompatible");
2087
2088        return 1;
2089}
2090
2091void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx,
2092                        const struct option *options,
2093                        const char * const usagestr[])
2094{
2095        int n = handle_revision_opt(revs, ctx->argc, ctx->argv,
2096                                    &ctx->cpidx, ctx->out);
2097        if (n <= 0) {
2098                error("unknown option `%s'", ctx->argv[0]);
2099                usage_with_options(usagestr, options);
2100        }
2101        ctx->argv += n;
2102        ctx->argc -= n;
2103}
2104
2105static int for_each_bisect_ref(struct ref_store *refs, each_ref_fn fn,
2106                               void *cb_data, const char *term)
2107{
2108        struct strbuf bisect_refs = STRBUF_INIT;
2109        int status;
2110        strbuf_addf(&bisect_refs, "refs/bisect/%s", term);
2111        status = refs_for_each_fullref_in(refs, bisect_refs.buf, fn, cb_data, 0);
2112        strbuf_release(&bisect_refs);
2113        return status;
2114}
2115
2116static int for_each_bad_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
2117{
2118        return for_each_bisect_ref(refs, fn, cb_data, term_bad);
2119}
2120
2121static int for_each_good_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
2122{
2123        return for_each_bisect_ref(refs, fn, cb_data, term_good);
2124}
2125
2126static int handle_revision_pseudo_opt(const char *submodule,
2127                                struct rev_info *revs,
2128                                int argc, const char **argv, int *flags)
2129{
2130        const char *arg = argv[0];
2131        const char *optarg;
2132        struct ref_store *refs;
2133        int argcount;
2134
2135        if (submodule) {
2136                refs = get_submodule_ref_store(submodule);
2137        } else
2138                refs = get_main_ref_store();
2139
2140        /*
2141         * NOTE!
2142         *
2143         * Commands like "git shortlog" will not accept the options below
2144         * unless parse_revision_opt queues them (as opposed to erroring
2145         * out).
2146         *
2147         * When implementing your new pseudo-option, remember to
2148         * register it in the list at the top of handle_revision_opt.
2149         */
2150        if (!strcmp(arg, "--all")) {
2151                handle_refs(refs, revs, *flags, refs_for_each_ref);
2152                handle_refs(refs, revs, *flags, refs_head_ref);
2153                clear_ref_exclusion(&revs->ref_excludes);
2154        } else if (!strcmp(arg, "--branches")) {
2155                handle_refs(refs, revs, *flags, refs_for_each_branch_ref);
2156                clear_ref_exclusion(&revs->ref_excludes);
2157        } else if (!strcmp(arg, "--bisect")) {
2158                read_bisect_terms(&term_bad, &term_good);
2159                handle_refs(refs, revs, *flags, for_each_bad_bisect_ref);
2160                handle_refs(refs, revs, *flags ^ (UNINTERESTING | BOTTOM),
2161                            for_each_good_bisect_ref);
2162                revs->bisect = 1;
2163        } else if (!strcmp(arg, "--tags")) {
2164                handle_refs(refs, revs, *flags, refs_for_each_tag_ref);
2165                clear_ref_exclusion(&revs->ref_excludes);
2166        } else if (!strcmp(arg, "--remotes")) {
2167                handle_refs(refs, revs, *flags, refs_for_each_remote_ref);
2168                clear_ref_exclusion(&revs->ref_excludes);
2169        } else if ((argcount = parse_long_opt("glob", argv, &optarg))) {
2170                struct all_refs_cb cb;
2171                init_all_refs_cb(&cb, revs, *flags);
2172                for_each_glob_ref(handle_one_ref, optarg, &cb);
2173                clear_ref_exclusion(&revs->ref_excludes);
2174                return argcount;
2175        } else if ((argcount = parse_long_opt("exclude", argv, &optarg))) {
2176                add_ref_exclusion(&revs->ref_excludes, optarg);
2177                return argcount;
2178        } else if (skip_prefix(arg, "--branches=", &optarg)) {
2179                struct all_refs_cb cb;
2180                init_all_refs_cb(&cb, revs, *flags);
2181                for_each_glob_ref_in(handle_one_ref, optarg, "refs/heads/", &cb);
2182                clear_ref_exclusion(&revs->ref_excludes);
2183        } else if (skip_prefix(arg, "--tags=", &optarg)) {
2184                struct all_refs_cb cb;
2185                init_all_refs_cb(&cb, revs, *flags);
2186                for_each_glob_ref_in(handle_one_ref, optarg, "refs/tags/", &cb);
2187                clear_ref_exclusion(&revs->ref_excludes);
2188        } else if (skip_prefix(arg, "--remotes=", &optarg)) {
2189                struct all_refs_cb cb;
2190                init_all_refs_cb(&cb, revs, *flags);
2191                for_each_glob_ref_in(handle_one_ref, optarg, "refs/remotes/", &cb);
2192                clear_ref_exclusion(&revs->ref_excludes);
2193        } else if (!strcmp(arg, "--reflog")) {
2194                add_reflogs_to_pending(revs, *flags);
2195        } else if (!strcmp(arg, "--indexed-objects")) {
2196                add_index_objects_to_pending(revs, *flags);
2197        } else if (!strcmp(arg, "--not")) {
2198                *flags ^= UNINTERESTING | BOTTOM;
2199        } else if (!strcmp(arg, "--no-walk")) {
2200                revs->no_walk = REVISION_WALK_NO_WALK_SORTED;
2201        } else if (skip_prefix(arg, "--no-walk=", &optarg)) {
2202                /*
2203                 * Detached form ("--no-walk X" as opposed to "--no-walk=X")
2204                 * not allowed, since the argument is optional.
2205                 */
2206                if (!strcmp(optarg, "sorted"))
2207                        revs->no_walk = REVISION_WALK_NO_WALK_SORTED;
2208                else if (!strcmp(optarg, "unsorted"))
2209                        revs->no_walk = REVISION_WALK_NO_WALK_UNSORTED;
2210                else
2211                        return error("invalid argument to --no-walk");
2212        } else if (!strcmp(arg, "--do-walk")) {
2213                revs->no_walk = 0;
2214        } else {
2215                return 0;
2216        }
2217
2218        return 1;
2219}
2220
2221static void NORETURN diagnose_missing_default(const char *def)
2222{
2223        unsigned char sha1[20];
2224        int flags;
2225        const char *refname;
2226
2227        refname = resolve_ref_unsafe(def, 0, sha1, &flags);
2228        if (!refname || !(flags & REF_ISSYMREF) || (flags & REF_ISBROKEN))
2229                die(_("your current branch appears to be broken"));
2230
2231        skip_prefix(refname, "refs/heads/", &refname);
2232        die(_("your current branch '%s' does not have any commits yet"),
2233            refname);
2234}
2235
2236/*
2237 * Parse revision information, filling in the "rev_info" structure,
2238 * and removing the used arguments from the argument list.
2239 *
2240 * Returns the number of arguments left that weren't recognized
2241 * (which are also moved to the head of the argument list)
2242 */
2243int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *opt)
2244{
2245        int i, flags, left, seen_dashdash, read_from_stdin, got_rev_arg = 0, revarg_opt;
2246        struct cmdline_pathspec prune_data;
2247        const char *submodule = NULL;
2248
2249        memset(&prune_data, 0, sizeof(prune_data));
2250        if (opt)
2251                submodule = opt->submodule;
2252
2253        /* First, search for "--" */
2254        if (opt && opt->assume_dashdash) {
2255                seen_dashdash = 1;
2256        } else {
2257                seen_dashdash = 0;
2258                for (i = 1; i < argc; i++) {
2259                        const char *arg = argv[i];
2260                        if (strcmp(arg, "--"))
2261                                continue;
2262                        argv[i] = NULL;
2263                        argc = i;
2264                        if (argv[i + 1])
2265                                append_prune_data(&prune_data, argv + i + 1);
2266                        seen_dashdash = 1;
2267                        break;
2268                }
2269        }
2270
2271        /* Second, deal with arguments and options */
2272        flags = 0;
2273        revarg_opt = opt ? opt->revarg_opt : 0;
2274        if (seen_dashdash)
2275                revarg_opt |= REVARG_CANNOT_BE_FILENAME;
2276        read_from_stdin = 0;
2277        for (left = i = 1; i < argc; i++) {
2278                const char *arg = argv[i];
2279                if (*arg == '-') {
2280                        int opts;
2281
2282                        opts = handle_revision_pseudo_opt(submodule,
2283                                                revs, argc - i, argv + i,
2284                                                &flags);
2285                        if (opts > 0) {
2286                                i += opts - 1;
2287                                continue;
2288                        }
2289
2290                        if (!strcmp(arg, "--stdin")) {
2291                                if (revs->disable_stdin) {
2292                                        argv[left++] = arg;
2293                                        continue;
2294                                }
2295                                if (read_from_stdin++)
2296                                        die("--stdin given twice?");
2297                                read_revisions_from_stdin(revs, &prune_data);
2298                                continue;
2299                        }
2300
2301                        opts = handle_revision_opt(revs, argc - i, argv + i, &left, argv);
2302                        if (opts > 0) {
2303                                i += opts - 1;
2304                                continue;
2305                        }
2306                        if (opts < 0)
2307                                exit(128);
2308                        continue;
2309                }
2310
2311
2312                if (handle_revision_arg(arg, revs, flags, revarg_opt)) {
2313                        int j;
2314                        if (seen_dashdash || *arg == '^')
2315                                die("bad revision '%s'", arg);
2316
2317                        /* If we didn't have a "--":
2318                         * (1) all filenames must exist;
2319                         * (2) all rev-args must not be interpretable
2320                         *     as a valid filename.
2321                         * but the latter we have checked in the main loop.
2322                         */
2323                        for (j = i; j < argc; j++)
2324                                verify_filename(revs->prefix, argv[j], j == i);
2325
2326                        append_prune_data(&prune_data, argv + i);
2327                        break;
2328                }
2329                else
2330                        got_rev_arg = 1;
2331        }
2332
2333        if (prune_data.nr) {
2334                /*
2335                 * If we need to introduce the magic "a lone ':' means no
2336                 * pathspec whatsoever", here is the place to do so.
2337                 *
2338                 * if (prune_data.nr == 1 && !strcmp(prune_data[0], ":")) {
2339                 *      prune_data.nr = 0;
2340                 *      prune_data.alloc = 0;
2341                 *      free(prune_data.path);
2342                 *      prune_data.path = NULL;
2343                 * } else {
2344                 *      terminate prune_data.alloc with NULL and
2345                 *      call init_pathspec() to set revs->prune_data here.
2346                 * }
2347                 */
2348                ALLOC_GROW(prune_data.path, prune_data.nr + 1, prune_data.alloc);
2349                prune_data.path[prune_data.nr++] = NULL;
2350                parse_pathspec(&revs->prune_data, 0, 0,
2351                               revs->prefix, prune_data.path);
2352        }
2353
2354        if (revs->def == NULL)
2355                revs->def = opt ? opt->def : NULL;
2356        if (opt && opt->tweak)
2357                opt->tweak(revs, opt);
2358        if (revs->show_merge)
2359                prepare_show_merge(revs);
2360        if (revs->def && !revs->pending.nr && !revs->rev_input_given && !got_rev_arg) {
2361                struct object_id oid;
2362                struct object *object;
2363                struct object_context oc;
2364                if (get_oid_with_context(revs->def, 0, &oid, &oc))
2365                        diagnose_missing_default(revs->def);
2366                object = get_reference(revs, revs->def, &oid, 0);
2367                add_pending_object_with_mode(revs, object, revs->def, oc.mode);
2368        }
2369
2370        /* Did the user ask for any diff output? Run the diff! */
2371        if (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT)
2372                revs->diff = 1;
2373
2374        /* Pickaxe, diff-filter and rename following need diffs */
2375        if (revs->diffopt.pickaxe ||
2376            revs->diffopt.filter ||
2377            DIFF_OPT_TST(&revs->diffopt, FOLLOW_RENAMES))
2378                revs->diff = 1;
2379
2380        if (revs->topo_order)
2381                revs->limited = 1;
2382
2383        if (revs->prune_data.nr) {
2384                copy_pathspec(&revs->pruning.pathspec, &revs->prune_data);
2385                /* Can't prune commits with rename following: the paths change.. */
2386                if (!DIFF_OPT_TST(&revs->diffopt, FOLLOW_RENAMES))
2387                        revs->prune = 1;
2388                if (!revs->full_diff)
2389                        copy_pathspec(&revs->diffopt.pathspec,
2390                                      &revs->prune_data);
2391        }
2392        if (revs->combine_merges)
2393                revs->ignore_merges = 0;
2394        revs->diffopt.abbrev = revs->abbrev;
2395
2396        if (revs->line_level_traverse) {
2397                revs->limited = 1;
2398                revs->topo_order = 1;
2399        }
2400
2401        diff_setup_done(&revs->diffopt);
2402
2403        grep_commit_pattern_type(GREP_PATTERN_TYPE_UNSPECIFIED,
2404                                 &revs->grep_filter);
2405        compile_grep_patterns(&revs->grep_filter);
2406
2407        if (revs->reverse && revs->reflog_info)
2408                die("cannot combine --reverse with --walk-reflogs");
2409        if (revs->reflog_info && revs->limited)
2410                die("cannot combine --walk-reflogs with history-limiting options");
2411        if (revs->rewrite_parents && revs->children.name)
2412                die("cannot combine --parents and --children");
2413
2414        /*
2415         * Limitations on the graph functionality
2416         */
2417        if (revs->reverse && revs->graph)
2418                die("cannot combine --reverse with --graph");
2419
2420        if (revs->reflog_info && revs->graph)
2421                die("cannot combine --walk-reflogs with --graph");
2422        if (revs->no_walk && revs->graph)
2423                die("cannot combine --no-walk with --graph");
2424        if (!revs->reflog_info && revs->grep_filter.use_reflog_filter)
2425                die("cannot use --grep-reflog without --walk-reflogs");
2426
2427        if (revs->first_parent_only && revs->bisect)
2428                die(_("--first-parent is incompatible with --bisect"));
2429
2430        if (revs->expand_tabs_in_log < 0)
2431                revs->expand_tabs_in_log = revs->expand_tabs_in_log_default;
2432
2433        return left;
2434}
2435
2436static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)
2437{
2438        struct commit_list *l = xcalloc(1, sizeof(*l));
2439
2440        l->item = child;
2441        l->next = add_decoration(&revs->children, &parent->object, l);
2442}
2443
2444static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)
2445{
2446        struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
2447        struct commit_list **pp, *p;
2448        int surviving_parents;
2449
2450        /* Examine existing parents while marking ones we have seen... */
2451        pp = &commit->parents;
2452        surviving_parents = 0;
2453        while ((p = *pp) != NULL) {
2454                struct commit *parent = p->item;
2455                if (parent->object.flags & TMP_MARK) {
2456                        *pp = p->next;
2457                        if (ts)
2458                                compact_treesame(revs, commit, surviving_parents);
2459                        continue;
2460                }
2461                parent->object.flags |= TMP_MARK;
2462                surviving_parents++;
2463                pp = &p->next;
2464        }
2465        /* clear the temporary mark */
2466        for (p = commit->parents; p; p = p->next) {
2467                p->item->object.flags &= ~TMP_MARK;
2468        }
2469        /* no update_treesame() - removing duplicates can't affect TREESAME */
2470        return surviving_parents;
2471}
2472
2473struct merge_simplify_state {
2474        struct commit *simplified;
2475};
2476
2477static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs, struct commit *commit)
2478{
2479        struct merge_simplify_state *st;
2480
2481        st = lookup_decoration(&revs->merge_simplification, &commit->object);
2482        if (!st) {
2483                st = xcalloc(1, sizeof(*st));
2484                add_decoration(&revs->merge_simplification, &commit->object, st);
2485        }
2486        return st;
2487}
2488
2489static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)
2490{
2491        struct commit_list *h = reduce_heads(commit->parents);
2492        int i = 0, marked = 0;
2493        struct commit_list *po, *pn;
2494
2495        /* Want these for sanity-checking only */
2496        int orig_cnt = commit_list_count(commit->parents);
2497        int cnt = commit_list_count(h);
2498
2499        /*
2500         * Not ready to remove items yet, just mark them for now, based
2501         * on the output of reduce_heads(). reduce_heads outputs the reduced
2502         * set in its original order, so this isn't too hard.
2503         */
2504        po = commit->parents;
2505        pn = h;
2506        while (po) {
2507                if (pn && po->item == pn->item) {
2508                        pn = pn->next;
2509                        i++;
2510                } else {
2511                        po->item->object.flags |= TMP_MARK;
2512                        marked++;
2513                }
2514                po=po->next;
2515        }
2516
2517        if (i != cnt || cnt+marked != orig_cnt)
2518                die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked);
2519
2520        free_commit_list(h);
2521
2522        return marked;
2523}
2524
2525static int mark_treesame_root_parents(struct rev_info *revs, struct commit *commit)
2526{
2527        struct commit_list *p;
2528        int marked = 0;
2529
2530        for (p = commit->parents; p; p = p->next) {
2531                struct commit *parent = p->item;
2532                if (!parent->parents && (parent->object.flags & TREESAME)) {
2533                        parent->object.flags |= TMP_MARK;
2534                        marked++;
2535                }
2536        }
2537
2538        return marked;
2539}
2540
2541/*
2542 * Awkward naming - this means one parent we are TREESAME to.
2543 * cf mark_treesame_root_parents: root parents that are TREESAME (to an
2544 * empty tree). Better name suggestions?
2545 */
2546static int leave_one_treesame_to_parent(struct rev_info *revs, struct commit *commit)
2547{
2548        struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
2549        struct commit *unmarked = NULL, *marked = NULL;
2550        struct commit_list *p;
2551        unsigned n;
2552
2553        for (p = commit->parents, n = 0; p; p = p->next, n++) {
2554                if (ts->treesame[n]) {
2555                        if (p->item->object.flags & TMP_MARK) {
2556                                if (!marked)
2557                                        marked = p->item;
2558                        } else {
2559                                if (!unmarked) {
2560                                        unmarked = p->item;
2561                                        break;
2562                                }
2563                        }
2564                }
2565        }
2566
2567        /*
2568         * If we are TREESAME to a marked-for-deletion parent, but not to any
2569         * unmarked parents, unmark the first TREESAME parent. This is the
2570         * parent that the default simplify_history==1 scan would have followed,
2571         * and it doesn't make sense to omit that path when asking for a
2572         * simplified full history. Retaining it improves the chances of
2573         * understanding odd missed merges that took an old version of a file.
2574         *
2575         * Example:
2576         *
2577         *   I--------*X       A modified the file, but mainline merge X used
2578         *    \       /        "-s ours", so took the version from I. X is
2579         *     `-*A--'         TREESAME to I and !TREESAME to A.
2580         *
2581         * Default log from X would produce "I". Without this check,
2582         * --full-history --simplify-merges would produce "I-A-X", showing
2583         * the merge commit X and that it changed A, but not making clear that
2584         * it had just taken the I version. With this check, the topology above
2585         * is retained.
2586         *
2587         * Note that it is possible that the simplification chooses a different
2588         * TREESAME parent from the default, in which case this test doesn't
2589         * activate, and we _do_ drop the default parent. Example:
2590         *
2591         *   I------X         A modified the file, but it was reverted in B,
2592         *    \    /          meaning mainline merge X is TREESAME to both
2593         *    *A-*B           parents.
2594         *
2595         * Default log would produce "I" by following the first parent;
2596         * --full-history --simplify-merges will produce "I-A-B". But this is a
2597         * reasonable result - it presents a logical full history leading from
2598         * I to X, and X is not an important merge.
2599         */
2600        if (!unmarked && marked) {
2601                marked->object.flags &= ~TMP_MARK;
2602                return 1;
2603        }
2604
2605        return 0;
2606}
2607
2608static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
2609{
2610        struct commit_list **pp, *p;
2611        int nth_parent, removed = 0;
2612
2613        pp = &commit->parents;
2614        nth_parent = 0;
2615        while ((p = *pp) != NULL) {
2616                struct commit *parent = p->item;
2617                if (parent->object.flags & TMP_MARK) {
2618                        parent->object.flags &= ~TMP_MARK;
2619                        *pp = p->next;
2620                        free(p);
2621                        removed++;
2622                        compact_treesame(revs, commit, nth_parent);
2623                        continue;
2624                }
2625                pp = &p->next;
2626                nth_parent++;
2627        }
2628
2629        /* Removing parents can only increase TREESAMEness */
2630        if (removed && !(commit->object.flags & TREESAME))
2631                update_treesame(revs, commit);
2632
2633        return nth_parent;
2634}
2635
2636static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)
2637{
2638        struct commit_list *p;
2639        struct commit *parent;
2640        struct merge_simplify_state *st, *pst;
2641        int cnt;
2642
2643        st = locate_simplify_state(revs, commit);
2644
2645        /*
2646         * Have we handled this one?
2647         */
2648        if (st->simplified)
2649                return tail;
2650
2651        /*
2652         * An UNINTERESTING commit simplifies to itself, so does a
2653         * root commit.  We do not rewrite parents of such commit
2654         * anyway.
2655         */
2656        if ((commit->object.flags & UNINTERESTING) || !commit->parents) {
2657                st->simplified = commit;
2658                return tail;
2659        }
2660
2661        /*
2662         * Do we know what commit all of our parents that matter
2663         * should be rewritten to?  Otherwise we are not ready to
2664         * rewrite this one yet.
2665         */
2666        for (cnt = 0, p = commit->parents; p; p = p->next) {
2667                pst = locate_simplify_state(revs, p->item);
2668                if (!pst->simplified) {
2669                        tail = &commit_list_insert(p->item, tail)->next;
2670                        cnt++;
2671                }
2672                if (revs->first_parent_only)
2673                        break;
2674        }
2675        if (cnt) {
2676                tail = &commit_list_insert(commit, tail)->next;
2677                return tail;
2678        }
2679
2680        /*
2681         * Rewrite our list of parents. Note that this cannot
2682         * affect our TREESAME flags in any way - a commit is
2683         * always TREESAME to its simplification.
2684         */
2685        for (p = commit->parents; p; p = p->next) {
2686                pst = locate_simplify_state(revs, p->item);
2687                p->item = pst->simplified;
2688                if (revs->first_parent_only)
2689                        break;
2690        }
2691
2692        if (revs->first_parent_only)
2693                cnt = 1;
2694        else
2695                cnt = remove_duplicate_parents(revs, commit);
2696
2697        /*
2698         * It is possible that we are a merge and one side branch
2699         * does not have any commit that touches the given paths;
2700         * in such a case, the immediate parent from that branch
2701         * will be rewritten to be the merge base.
2702         *
2703         *      o----X          X: the commit we are looking at;
2704         *     /    /           o: a commit that touches the paths;
2705         * ---o----'
2706         *
2707         * Further, a merge of an independent branch that doesn't
2708         * touch the path will reduce to a treesame root parent:
2709         *
2710         *  ----o----X          X: the commit we are looking at;
2711         *          /           o: a commit that touches the paths;
2712         *         r            r: a root commit not touching the paths
2713         *
2714         * Detect and simplify both cases.
2715         */
2716        if (1 < cnt) {
2717                int marked = mark_redundant_parents(revs, commit);
2718                marked += mark_treesame_root_parents(revs, commit);
2719                if (marked)
2720                        marked -= leave_one_treesame_to_parent(revs, commit);
2721                if (marked)
2722                        cnt = remove_marked_parents(revs, commit);
2723        }
2724
2725        /*
2726         * A commit simplifies to itself if it is a root, if it is
2727         * UNINTERESTING, if it touches the given paths, or if it is a
2728         * merge and its parents don't simplify to one relevant commit
2729         * (the first two cases are already handled at the beginning of
2730         * this function).
2731         *
2732         * Otherwise, it simplifies to what its sole relevant parent
2733         * simplifies to.
2734         */
2735        if (!cnt ||
2736            (commit->object.flags & UNINTERESTING) ||
2737            !(commit->object.flags & TREESAME) ||
2738            (parent = one_relevant_parent(revs, commit->parents)) == NULL)
2739                st->simplified = commit;
2740        else {
2741                pst = locate_simplify_state(revs, parent);
2742                st->simplified = pst->simplified;
2743        }
2744        return tail;
2745}
2746
2747static void simplify_merges(struct rev_info *revs)
2748{
2749        struct commit_list *list, *next;
2750        struct commit_list *yet_to_do, **tail;
2751        struct commit *commit;
2752
2753        if (!revs->prune)
2754                return;
2755
2756        /* feed the list reversed */
2757        yet_to_do = NULL;
2758        for (list = revs->commits; list; list = next) {
2759                commit = list->item;
2760                next = list->next;
2761                /*
2762                 * Do not free(list) here yet; the original list
2763                 * is used later in this function.
2764                 */
2765                commit_list_insert(commit, &yet_to_do);
2766        }
2767        while (yet_to_do) {
2768                list = yet_to_do;
2769                yet_to_do = NULL;
2770                tail = &yet_to_do;
2771                while (list) {
2772                        commit = pop_commit(&list);
2773                        tail = simplify_one(revs, commit, tail);
2774                }
2775        }
2776
2777        /* clean up the result, removing the simplified ones */
2778        list = revs->commits;
2779        revs->commits = NULL;
2780        tail = &revs->commits;
2781        while (list) {
2782                struct merge_simplify_state *st;
2783
2784                commit = pop_commit(&list);
2785                st = locate_simplify_state(revs, commit);
2786                if (st->simplified == commit)
2787                        tail = &commit_list_insert(commit, tail)->next;
2788        }
2789}
2790
2791static void set_children(struct rev_info *revs)
2792{
2793        struct commit_list *l;
2794        for (l = revs->commits; l; l = l->next) {
2795                struct commit *commit = l->item;
2796                struct commit_list *p;
2797
2798                for (p = commit->parents; p; p = p->next)
2799                        add_child(revs, p->item, commit);
2800        }
2801}
2802
2803void reset_revision_walk(void)
2804{
2805        clear_object_flags(SEEN | ADDED | SHOWN);
2806}
2807
2808int prepare_revision_walk(struct rev_info *revs)
2809{
2810        int i;
2811        struct object_array old_pending;
2812        struct commit_list **next = &revs->commits;
2813
2814        memcpy(&old_pending, &revs->pending, sizeof(old_pending));
2815        revs->pending.nr = 0;
2816        revs->pending.alloc = 0;
2817        revs->pending.objects = NULL;
2818        for (i = 0; i < old_pending.nr; i++) {
2819                struct object_array_entry *e = old_pending.objects + i;
2820                struct commit *commit = handle_commit(revs, e);
2821                if (commit) {
2822                        if (!(commit->object.flags & SEEN)) {
2823                                commit->object.flags |= SEEN;
2824                                next = commit_list_append(commit, next);
2825                        }
2826                }
2827        }
2828        if (!revs->leak_pending)
2829                object_array_clear(&old_pending);
2830
2831        /* Signal whether we need per-parent treesame decoration */
2832        if (revs->simplify_merges ||
2833            (revs->limited && limiting_can_increase_treesame(revs)))
2834                revs->treesame.name = "treesame";
2835
2836        if (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)
2837                commit_list_sort_by_date(&revs->commits);
2838        if (revs->no_walk)
2839                return 0;
2840        if (revs->limited)
2841                if (limit_list(revs) < 0)
2842                        return -1;
2843        if (revs->topo_order)
2844                sort_in_topological_order(&revs->commits, revs->sort_order);
2845        if (revs->line_level_traverse)
2846                line_log_filter(revs);
2847        if (revs->simplify_merges)
2848                simplify_merges(revs);
2849        if (revs->children.name)
2850                set_children(revs);
2851        return 0;
2852}
2853
2854static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)
2855{
2856        struct commit_list *cache = NULL;
2857
2858        for (;;) {
2859                struct commit *p = *pp;
2860                if (!revs->limited)
2861                        if (add_parents_to_list(revs, p, &revs->commits, &cache) < 0)
2862                                return rewrite_one_error;
2863                if (p->object.flags & UNINTERESTING)
2864                        return rewrite_one_ok;
2865                if (!(p->object.flags & TREESAME))
2866                        return rewrite_one_ok;
2867                if (!p->parents)
2868                        return rewrite_one_noparents;
2869                if ((p = one_relevant_parent(revs, p->parents)) == NULL)
2870                        return rewrite_one_ok;
2871                *pp = p;
2872        }
2873}
2874
2875int rewrite_parents(struct rev_info *revs, struct commit *commit,
2876        rewrite_parent_fn_t rewrite_parent)
2877{
2878        struct commit_list **pp = &commit->parents;
2879        while (*pp) {
2880                struct commit_list *parent = *pp;
2881                switch (rewrite_parent(revs, &parent->item)) {
2882                case rewrite_one_ok:
2883                        break;
2884                case rewrite_one_noparents:
2885                        *pp = parent->next;
2886                        continue;
2887                case rewrite_one_error:
2888                        return -1;
2889                }
2890                pp = &parent->next;
2891        }
2892        remove_duplicate_parents(revs, commit);
2893        return 0;
2894}
2895
2896static int commit_rewrite_person(struct strbuf *buf, const char *what, struct string_list *mailmap)
2897{
2898        char *person, *endp;
2899        size_t len, namelen, maillen;
2900        const char *name;
2901        const char *mail;
2902        struct ident_split ident;
2903
2904        person = strstr(buf->buf, what);
2905        if (!person)
2906                return 0;
2907
2908        person += strlen(what);
2909        endp = strchr(person, '\n');
2910        if (!endp)
2911                return 0;
2912
2913        len = endp - person;
2914
2915        if (split_ident_line(&ident, person, len))
2916                return 0;
2917
2918        mail = ident.mail_begin;
2919        maillen = ident.mail_end - ident.mail_begin;
2920        name = ident.name_begin;
2921        namelen = ident.name_end - ident.name_begin;
2922
2923        if (map_user(mailmap, &mail, &maillen, &name, &namelen)) {
2924                struct strbuf namemail = STRBUF_INIT;
2925
2926                strbuf_addf(&namemail, "%.*s <%.*s>",
2927                            (int)namelen, name, (int)maillen, mail);
2928
2929                strbuf_splice(buf, ident.name_begin - buf->buf,
2930                              ident.mail_end - ident.name_begin + 1,
2931                              namemail.buf, namemail.len);
2932
2933                strbuf_release(&namemail);
2934
2935                return 1;
2936        }
2937
2938        return 0;
2939}
2940
2941static int commit_match(struct commit *commit, struct rev_info *opt)
2942{
2943        int retval;
2944        const char *encoding;
2945        const char *message;
2946        struct strbuf buf = STRBUF_INIT;
2947
2948        if (!opt->grep_filter.pattern_list && !opt->grep_filter.header_list)
2949                return 1;
2950
2951        /* Prepend "fake" headers as needed */
2952        if (opt->grep_filter.use_reflog_filter) {
2953                strbuf_addstr(&buf, "reflog ");
2954                get_reflog_message(&buf, opt->reflog_info);
2955                strbuf_addch(&buf, '\n');
2956        }
2957
2958        /*
2959         * We grep in the user's output encoding, under the assumption that it
2960         * is the encoding they are most likely to write their grep pattern
2961         * for. In addition, it means we will match the "notes" encoding below,
2962         * so we will not end up with a buffer that has two different encodings
2963         * in it.
2964         */
2965        encoding = get_log_output_encoding();
2966        message = logmsg_reencode(commit, NULL, encoding);
2967
2968        /* Copy the commit to temporary if we are using "fake" headers */
2969        if (buf.len)
2970                strbuf_addstr(&buf, message);
2971
2972        if (opt->grep_filter.header_list && opt->mailmap) {
2973                if (!buf.len)
2974                        strbuf_addstr(&buf, message);
2975
2976                commit_rewrite_person(&buf, "\nauthor ", opt->mailmap);
2977                commit_rewrite_person(&buf, "\ncommitter ", opt->mailmap);
2978        }
2979
2980        /* Append "fake" message parts as needed */
2981        if (opt->show_notes) {
2982                if (!buf.len)
2983                        strbuf_addstr(&buf, message);
2984                format_display_notes(&commit->object.oid, &buf, encoding, 1);
2985        }
2986
2987        /*
2988         * Find either in the original commit message, or in the temporary.
2989         * Note that we cast away the constness of "message" here. It is
2990         * const because it may come from the cached commit buffer. That's OK,
2991         * because we know that it is modifiable heap memory, and that while
2992         * grep_buffer may modify it for speed, it will restore any
2993         * changes before returning.
2994         */
2995        if (buf.len)
2996                retval = grep_buffer(&opt->grep_filter, buf.buf, buf.len);
2997        else
2998                retval = grep_buffer(&opt->grep_filter,
2999                                     (char *)message, strlen(message));
3000        strbuf_release(&buf);
3001        unuse_commit_buffer(commit, message);
3002        return opt->invert_grep ? !retval : retval;
3003}
3004
3005static inline int want_ancestry(const struct rev_info *revs)
3006{
3007        return (revs->rewrite_parents || revs->children.name);
3008}
3009
3010/*
3011 * Return a timestamp to be used for --since/--until comparisons for this
3012 * commit, based on the revision options.
3013 */
3014static timestamp_t comparison_date(const struct rev_info *revs,
3015                                   struct commit *commit)
3016{
3017        return revs->reflog_info ?
3018                get_reflog_timestamp(revs->reflog_info) :
3019                commit->date;
3020}
3021
3022enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit)
3023{
3024        if (commit->object.flags & SHOWN)
3025                return commit_ignore;
3026        if (revs->unpacked && has_sha1_pack(commit->object.oid.hash))
3027                return commit_ignore;
3028        if (revs->show_all)
3029                return commit_show;
3030        if (commit->object.flags & UNINTERESTING)
3031                return commit_ignore;
3032        if (revs->min_age != -1 &&
3033            comparison_date(revs, commit) > revs->min_age)
3034                        return commit_ignore;
3035        if (revs->min_parents || (revs->max_parents >= 0)) {
3036                int n = commit_list_count(commit->parents);
3037                if ((n < revs->min_parents) ||
3038                    ((revs->max_parents >= 0) && (n > revs->max_parents)))
3039                        return commit_ignore;
3040        }
3041        if (!commit_match(commit, revs))
3042                return commit_ignore;
3043        if (revs->prune && revs->dense) {
3044                /* Commit without changes? */
3045                if (commit->object.flags & TREESAME) {
3046                        int n;
3047                        struct commit_list *p;
3048                        /* drop merges unless we want parenthood */
3049                        if (!want_ancestry(revs))
3050                                return commit_ignore;
3051                        /*
3052                         * If we want ancestry, then need to keep any merges
3053                         * between relevant commits to tie together topology.
3054                         * For consistency with TREESAME and simplification
3055                         * use "relevant" here rather than just INTERESTING,
3056                         * to treat bottom commit(s) as part of the topology.
3057                         */
3058                        for (n = 0, p = commit->parents; p; p = p->next)
3059                                if (relevant_commit(p->item))
3060                                        if (++n >= 2)
3061                                                return commit_show;
3062                        return commit_ignore;
3063                }
3064        }
3065        return commit_show;
3066}
3067
3068define_commit_slab(saved_parents, struct commit_list *);
3069
3070#define EMPTY_PARENT_LIST ((struct commit_list *)-1)
3071
3072/*
3073 * You may only call save_parents() once per commit (this is checked
3074 * for non-root commits).
3075 */
3076static void save_parents(struct rev_info *revs, struct commit *commit)
3077{
3078        struct commit_list **pp;
3079
3080        if (!revs->saved_parents_slab) {
3081                revs->saved_parents_slab = xmalloc(sizeof(struct saved_parents));
3082                init_saved_parents(revs->saved_parents_slab);
3083        }
3084
3085        pp = saved_parents_at(revs->saved_parents_slab, commit);
3086
3087        /*
3088         * When walking with reflogs, we may visit the same commit
3089         * several times: once for each appearance in the reflog.
3090         *
3091         * In this case, save_parents() will be called multiple times.
3092         * We want to keep only the first set of parents.  We need to
3093         * store a sentinel value for an empty (i.e., NULL) parent
3094         * list to distinguish it from a not-yet-saved list, however.
3095         */
3096        if (*pp)
3097                return;
3098        if (commit->parents)
3099                *pp = copy_commit_list(commit->parents);
3100        else
3101                *pp = EMPTY_PARENT_LIST;
3102}
3103
3104static void free_saved_parents(struct rev_info *revs)
3105{
3106        if (revs->saved_parents_slab)
3107                clear_saved_parents(revs->saved_parents_slab);
3108}
3109
3110struct commit_list *get_saved_parents(struct rev_info *revs, const struct commit *commit)
3111{
3112        struct commit_list *parents;
3113
3114        if (!revs->saved_parents_slab)
3115                return commit->parents;
3116
3117        parents = *saved_parents_at(revs->saved_parents_slab, commit);
3118        if (parents == EMPTY_PARENT_LIST)
3119                return NULL;
3120        return parents;
3121}
3122
3123enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)
3124{
3125        enum commit_action action = get_commit_action(revs, commit);
3126
3127        if (action == commit_show &&
3128            !revs->show_all &&
3129            revs->prune && revs->dense && want_ancestry(revs)) {
3130                /*
3131                 * --full-diff on simplified parents is no good: it
3132                 * will show spurious changes from the commits that
3133                 * were elided.  So we save the parents on the side
3134                 * when --full-diff is in effect.
3135                 */
3136                if (revs->full_diff)
3137                        save_parents(revs, commit);
3138                if (rewrite_parents(revs, commit, rewrite_one) < 0)
3139                        return commit_error;
3140        }
3141        return action;
3142}
3143
3144static void track_linear(struct rev_info *revs, struct commit *commit)
3145{
3146        if (revs->track_first_time) {
3147                revs->linear = 1;
3148                revs->track_first_time = 0;
3149        } else {
3150                struct commit_list *p;
3151                for (p = revs->previous_parents; p; p = p->next)
3152                        if (p->item == NULL || /* first commit */
3153                            !oidcmp(&p->item->object.oid, &commit->object.oid))
3154                                break;
3155                revs->linear = p != NULL;
3156        }
3157        if (revs->reverse) {
3158                if (revs->linear)
3159                        commit->object.flags |= TRACK_LINEAR;
3160        }
3161        free_commit_list(revs->previous_parents);
3162        revs->previous_parents = copy_commit_list(commit->parents);
3163}
3164
3165static struct commit *get_revision_1(struct rev_info *revs)
3166{
3167        while (1) {
3168                struct commit *commit;
3169
3170                if (revs->reflog_info)
3171                        commit = next_reflog_entry(revs->reflog_info);
3172                else
3173                        commit = pop_commit(&revs->commits);
3174
3175                if (!commit)
3176                        return NULL;
3177
3178                if (revs->reflog_info)
3179                        commit->object.flags &= ~(ADDED | SEEN | SHOWN);
3180
3181                /*
3182                 * If we haven't done the list limiting, we need to look at
3183                 * the parents here. We also need to do the date-based limiting
3184                 * that we'd otherwise have done in limit_list().
3185                 */
3186                if (!revs->limited) {
3187                        if (revs->max_age != -1 &&
3188                            comparison_date(revs, commit) < revs->max_age)
3189                                continue;
3190
3191                        if (revs->reflog_info)
3192                                try_to_simplify_commit(revs, commit);
3193                        else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
3194                                if (!revs->ignore_missing_links)
3195                                        die("Failed to traverse parents of commit %s",
3196                                                oid_to_hex(&commit->object.oid));
3197                        }
3198                }
3199
3200                switch (simplify_commit(revs, commit)) {
3201                case commit_ignore:
3202                        continue;
3203                case commit_error:
3204                        die("Failed to simplify parents of commit %s",
3205                            oid_to_hex(&commit->object.oid));
3206                default:
3207                        if (revs->track_linear)
3208                                track_linear(revs, commit);
3209                        return commit;
3210                }
3211        }
3212}
3213
3214/*
3215 * Return true for entries that have not yet been shown.  (This is an
3216 * object_array_each_func_t.)
3217 */
3218static int entry_unshown(struct object_array_entry *entry, void *cb_data_unused)
3219{
3220        return !(entry->item->flags & SHOWN);
3221}
3222
3223/*
3224 * If array is on the verge of a realloc, garbage-collect any entries
3225 * that have already been shown to try to free up some space.
3226 */
3227static void gc_boundary(struct object_array *array)
3228{
3229        if (array->nr == array->alloc)
3230                object_array_filter(array, entry_unshown, NULL);
3231}
3232
3233static void create_boundary_commit_list(struct rev_info *revs)
3234{
3235        unsigned i;
3236        struct commit *c;
3237        struct object_array *array = &revs->boundary_commits;
3238        struct object_array_entry *objects = array->objects;
3239
3240        /*
3241         * If revs->commits is non-NULL at this point, an error occurred in
3242         * get_revision_1().  Ignore the error and continue printing the
3243         * boundary commits anyway.  (This is what the code has always
3244         * done.)
3245         */
3246        if (revs->commits) {
3247                free_commit_list(revs->commits);
3248                revs->commits = NULL;
3249        }
3250
3251        /*
3252         * Put all of the actual boundary commits from revs->boundary_commits
3253         * into revs->commits
3254         */
3255        for (i = 0; i < array->nr; i++) {
3256                c = (struct commit *)(objects[i].item);
3257                if (!c)
3258                        continue;
3259                if (!(c->object.flags & CHILD_SHOWN))
3260                        continue;
3261                if (c->object.flags & (SHOWN | BOUNDARY))
3262                        continue;
3263                c->object.flags |= BOUNDARY;
3264                commit_list_insert(c, &revs->commits);
3265        }
3266
3267        /*
3268         * If revs->topo_order is set, sort the boundary commits
3269         * in topological order
3270         */
3271        sort_in_topological_order(&revs->commits, revs->sort_order);
3272}
3273
3274static struct commit *get_revision_internal(struct rev_info *revs)
3275{
3276        struct commit *c = NULL;
3277        struct commit_list *l;
3278
3279        if (revs->boundary == 2) {
3280                /*
3281                 * All of the normal commits have already been returned,
3282                 * and we are now returning boundary commits.
3283                 * create_boundary_commit_list() has populated
3284                 * revs->commits with the remaining commits to return.
3285                 */
3286                c = pop_commit(&revs->commits);
3287                if (c)
3288                        c->object.flags |= SHOWN;
3289                return c;
3290        }
3291
3292        /*
3293         * If our max_count counter has reached zero, then we are done. We
3294         * don't simply return NULL because we still might need to show
3295         * boundary commits. But we want to avoid calling get_revision_1, which
3296         * might do a considerable amount of work finding the next commit only
3297         * for us to throw it away.
3298         *
3299         * If it is non-zero, then either we don't have a max_count at all
3300         * (-1), or it is still counting, in which case we decrement.
3301         */
3302        if (revs->max_count) {
3303                c = get_revision_1(revs);
3304                if (c) {
3305                        while (revs->skip_count > 0) {
3306                                revs->skip_count--;
3307                                c = get_revision_1(revs);
3308                                if (!c)
3309                                        break;
3310                        }
3311                }
3312
3313                if (revs->max_count > 0)
3314                        revs->max_count--;
3315        }
3316
3317        if (c)
3318                c->object.flags |= SHOWN;
3319
3320        if (!revs->boundary)
3321                return c;
3322
3323        if (!c) {
3324                /*
3325                 * get_revision_1() runs out the commits, and
3326                 * we are done computing the boundaries.
3327                 * switch to boundary commits output mode.
3328                 */
3329                revs->boundary = 2;
3330
3331                /*
3332                 * Update revs->commits to contain the list of
3333                 * boundary commits.
3334                 */
3335                create_boundary_commit_list(revs);
3336
3337                return get_revision_internal(revs);
3338        }
3339
3340        /*
3341         * boundary commits are the commits that are parents of the
3342         * ones we got from get_revision_1() but they themselves are
3343         * not returned from get_revision_1().  Before returning
3344         * 'c', we need to mark its parents that they could be boundaries.
3345         */
3346
3347        for (l = c->parents; l; l = l->next) {
3348                struct object *p;
3349                p = &(l->item->object);
3350                if (p->flags & (CHILD_SHOWN | SHOWN))
3351                        continue;
3352                p->flags |= CHILD_SHOWN;
3353                gc_boundary(&revs->boundary_commits);
3354                add_object_array(p, NULL, &revs->boundary_commits);
3355        }
3356
3357        return c;
3358}
3359
3360struct commit *get_revision(struct rev_info *revs)
3361{
3362        struct commit *c;
3363        struct commit_list *reversed;
3364
3365        if (revs->reverse) {
3366                reversed = NULL;
3367                while ((c = get_revision_internal(revs)))
3368                        commit_list_insert(c, &reversed);
3369                revs->commits = reversed;
3370                revs->reverse = 0;
3371                revs->reverse_output_stage = 1;
3372        }
3373
3374        if (revs->reverse_output_stage) {
3375                c = pop_commit(&revs->commits);
3376                if (revs->track_linear)
3377                        revs->linear = !!(c && c->object.flags & TRACK_LINEAR);
3378                return c;
3379        }
3380
3381        c = get_revision_internal(revs);
3382        if (c && revs->graph)
3383                graph_update(revs->graph, c);
3384        if (!c) {
3385                free_saved_parents(revs);
3386                if (revs->previous_parents) {
3387                        free_commit_list(revs->previous_parents);
3388                        revs->previous_parents = NULL;
3389                }
3390        }
3391        return c;
3392}
3393
3394char *get_revision_mark(const struct rev_info *revs, const struct commit *commit)
3395{
3396        if (commit->object.flags & BOUNDARY)
3397                return "-";
3398        else if (commit->object.flags & UNINTERESTING)
3399                return "^";
3400        else if (commit->object.flags & PATCHSAME)
3401                return "=";
3402        else if (!revs || revs->left_right) {
3403                if (commit->object.flags & SYMMETRIC_LEFT)
3404                        return "<";
3405                else
3406                        return ">";
3407        } else if (revs->graph)
3408                return "*";
3409        else if (revs->cherry_mark)
3410                return "+";
3411        return "";
3412}
3413
3414void put_revision_mark(const struct rev_info *revs, const struct commit *commit)
3415{
3416        char *mark = get_revision_mark(revs, commit);
3417        if (!strlen(mark))
3418                return;
3419        fputs(mark, stdout);
3420        putchar(' ');
3421}