c5b38cc1174356c15d6b544ab8eab4391a4621a7
   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
  17volatile show_early_output_fn_t show_early_output;
  18
  19char *path_name(const struct name_path *path, const char *name)
  20{
  21        const struct name_path *p;
  22        char *n, *m;
  23        int nlen = strlen(name);
  24        int len = nlen + 1;
  25
  26        for (p = path; p; p = p->up) {
  27                if (p->elem_len)
  28                        len += p->elem_len + 1;
  29        }
  30        n = xmalloc(len);
  31        m = n + len - (nlen + 1);
  32        strcpy(m, name);
  33        for (p = path; p; p = p->up) {
  34                if (p->elem_len) {
  35                        m -= p->elem_len + 1;
  36                        memcpy(m, p->elem, p->elem_len);
  37                        m[p->elem_len] = '/';
  38                }
  39        }
  40        return n;
  41}
  42
  43void show_object_with_name(FILE *out, struct object *obj, const struct name_path *path, const char *component)
  44{
  45        char *name = path_name(path, component);
  46        const char *ep = strchr(name, '\n');
  47
  48        /*
  49         * An object with name "foo\n0000000..." can be used to
  50         * confuse downstream "git pack-objects" very badly.
  51         */
  52        if (ep) {
  53                fprintf(out, "%s %.*s\n", sha1_to_hex(obj->sha1),
  54                        (int) (ep - name),
  55                        name);
  56        }
  57        else
  58                fprintf(out, "%s %s\n", sha1_to_hex(obj->sha1), name);
  59        free(name);
  60}
  61
  62void add_object(struct object *obj,
  63                struct object_array *p,
  64                struct name_path *path,
  65                const char *name)
  66{
  67        add_object_array(obj, path_name(path, name), p);
  68}
  69
  70static void mark_blob_uninteresting(struct blob *blob)
  71{
  72        if (!blob)
  73                return;
  74        if (blob->object.flags & UNINTERESTING)
  75                return;
  76        blob->object.flags |= UNINTERESTING;
  77}
  78
  79void mark_tree_uninteresting(struct tree *tree)
  80{
  81        struct tree_desc desc;
  82        struct name_entry entry;
  83        struct object *obj = &tree->object;
  84
  85        if (!tree)
  86                return;
  87        if (obj->flags & UNINTERESTING)
  88                return;
  89        obj->flags |= UNINTERESTING;
  90        if (!has_sha1_file(obj->sha1))
  91                return;
  92        if (parse_tree(tree) < 0)
  93                die("bad tree %s", sha1_to_hex(obj->sha1));
  94
  95        init_tree_desc(&desc, tree->buffer, tree->size);
  96        while (tree_entry(&desc, &entry)) {
  97                switch (object_type(entry.mode)) {
  98                case OBJ_TREE:
  99                        mark_tree_uninteresting(lookup_tree(entry.sha1));
 100                        break;
 101                case OBJ_BLOB:
 102                        mark_blob_uninteresting(lookup_blob(entry.sha1));
 103                        break;
 104                default:
 105                        /* Subproject commit - not in this repository */
 106                        break;
 107                }
 108        }
 109
 110        /*
 111         * We don't care about the tree any more
 112         * after it has been marked uninteresting.
 113         */
 114        free(tree->buffer);
 115        tree->buffer = NULL;
 116}
 117
 118void mark_parents_uninteresting(struct commit *commit)
 119{
 120        struct commit_list *parents = commit->parents;
 121
 122        while (parents) {
 123                struct commit *commit = parents->item;
 124                if (!(commit->object.flags & UNINTERESTING)) {
 125                        commit->object.flags |= UNINTERESTING;
 126
 127                        /*
 128                         * Normally we haven't parsed the parent
 129                         * yet, so we won't have a parent of a parent
 130                         * here. However, it may turn out that we've
 131                         * reached this commit some other way (where it
 132                         * wasn't uninteresting), in which case we need
 133                         * to mark its parents recursively too..
 134                         */
 135                        if (commit->parents)
 136                                mark_parents_uninteresting(commit);
 137                }
 138
 139                /*
 140                 * A missing commit is ok iff its parent is marked
 141                 * uninteresting.
 142                 *
 143                 * We just mark such a thing parsed, so that when
 144                 * it is popped next time around, we won't be trying
 145                 * to parse it and get an error.
 146                 */
 147                if (!has_sha1_file(commit->object.sha1))
 148                        commit->object.parsed = 1;
 149                parents = parents->next;
 150        }
 151}
 152
 153static void add_pending_object_with_mode(struct rev_info *revs, struct object *obj, const char *name, unsigned mode)
 154{
 155        if (!obj)
 156                return;
 157        if (revs->no_walk && (obj->flags & UNINTERESTING))
 158                revs->no_walk = 0;
 159        if (revs->reflog_info && obj->type == OBJ_COMMIT) {
 160                struct strbuf buf = STRBUF_INIT;
 161                int len = interpret_branch_name(name, &buf);
 162                int st;
 163
 164                if (0 < len && name[len] && buf.len)
 165                        strbuf_addstr(&buf, name + len);
 166                st = add_reflog_for_walk(revs->reflog_info,
 167                                         (struct commit *)obj,
 168                                         buf.buf[0] ? buf.buf: name);
 169                strbuf_release(&buf);
 170                if (st)
 171                        return;
 172        }
 173        add_object_array_with_mode(obj, name, &revs->pending, mode);
 174}
 175
 176void add_pending_object(struct rev_info *revs, struct object *obj, const char *name)
 177{
 178        add_pending_object_with_mode(revs, obj, name, S_IFINVALID);
 179}
 180
 181void add_head_to_pending(struct rev_info *revs)
 182{
 183        unsigned char sha1[20];
 184        struct object *obj;
 185        if (get_sha1("HEAD", sha1))
 186                return;
 187        obj = parse_object(sha1);
 188        if (!obj)
 189                return;
 190        add_pending_object(revs, obj, "HEAD");
 191}
 192
 193static struct object *get_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)
 194{
 195        struct object *object;
 196
 197        object = parse_object(sha1);
 198        if (!object) {
 199                if (revs->ignore_missing)
 200                        return object;
 201                die("bad object %s", name);
 202        }
 203        object->flags |= flags;
 204        return object;
 205}
 206
 207static struct commit *handle_commit(struct rev_info *revs, struct object *object, const char *name)
 208{
 209        unsigned long flags = object->flags;
 210
 211        /*
 212         * Tag object? Look what it points to..
 213         */
 214        while (object->type == OBJ_TAG) {
 215                struct tag *tag = (struct tag *) object;
 216                if (revs->tag_objects && !(flags & UNINTERESTING))
 217                        add_pending_object(revs, object, tag->tag);
 218                if (!tag->tagged)
 219                        die("bad tag");
 220                object = parse_object(tag->tagged->sha1);
 221                if (!object) {
 222                        if (flags & UNINTERESTING)
 223                                return NULL;
 224                        die("bad object %s", sha1_to_hex(tag->tagged->sha1));
 225                }
 226        }
 227
 228        /*
 229         * Commit object? Just return it, we'll do all the complex
 230         * reachability crud.
 231         */
 232        if (object->type == OBJ_COMMIT) {
 233                struct commit *commit = (struct commit *)object;
 234                if (parse_commit(commit) < 0)
 235                        die("unable to parse commit %s", name);
 236                if (flags & UNINTERESTING) {
 237                        commit->object.flags |= UNINTERESTING;
 238                        mark_parents_uninteresting(commit);
 239                        revs->limited = 1;
 240                }
 241                if (revs->show_source && !commit->util)
 242                        commit->util = (void *) name;
 243                return commit;
 244        }
 245
 246        /*
 247         * Tree object? Either mark it uninteresting, or add it
 248         * to the list of objects to look at later..
 249         */
 250        if (object->type == OBJ_TREE) {
 251                struct tree *tree = (struct tree *)object;
 252                if (!revs->tree_objects)
 253                        return NULL;
 254                if (flags & UNINTERESTING) {
 255                        mark_tree_uninteresting(tree);
 256                        return NULL;
 257                }
 258                add_pending_object(revs, object, "");
 259                return NULL;
 260        }
 261
 262        /*
 263         * Blob object? You know the drill by now..
 264         */
 265        if (object->type == OBJ_BLOB) {
 266                struct blob *blob = (struct blob *)object;
 267                if (!revs->blob_objects)
 268                        return NULL;
 269                if (flags & UNINTERESTING) {
 270                        mark_blob_uninteresting(blob);
 271                        return NULL;
 272                }
 273                add_pending_object(revs, object, "");
 274                return NULL;
 275        }
 276        die("%s is unknown object", name);
 277}
 278
 279static int everybody_uninteresting(struct commit_list *orig)
 280{
 281        struct commit_list *list = orig;
 282        while (list) {
 283                struct commit *commit = list->item;
 284                list = list->next;
 285                if (commit->object.flags & UNINTERESTING)
 286                        continue;
 287                return 0;
 288        }
 289        return 1;
 290}
 291
 292/*
 293 * The goal is to get REV_TREE_NEW as the result only if the
 294 * diff consists of all '+' (and no other changes), REV_TREE_OLD
 295 * if the whole diff is removal of old data, and otherwise
 296 * REV_TREE_DIFFERENT (of course if the trees are the same we
 297 * want REV_TREE_SAME).
 298 * That means that once we get to REV_TREE_DIFFERENT, we do not
 299 * have to look any further.
 300 */
 301static int tree_difference = REV_TREE_SAME;
 302
 303static void file_add_remove(struct diff_options *options,
 304                    int addremove, unsigned mode,
 305                    const unsigned char *sha1,
 306                    const char *fullpath, unsigned dirty_submodule)
 307{
 308        int diff = addremove == '+' ? REV_TREE_NEW : REV_TREE_OLD;
 309
 310        tree_difference |= diff;
 311        if (tree_difference == REV_TREE_DIFFERENT)
 312                DIFF_OPT_SET(options, HAS_CHANGES);
 313}
 314
 315static void file_change(struct diff_options *options,
 316                 unsigned old_mode, unsigned new_mode,
 317                 const unsigned char *old_sha1,
 318                 const unsigned char *new_sha1,
 319                 const char *fullpath,
 320                 unsigned old_dirty_submodule, unsigned new_dirty_submodule)
 321{
 322        tree_difference = REV_TREE_DIFFERENT;
 323        DIFF_OPT_SET(options, HAS_CHANGES);
 324}
 325
 326static int rev_compare_tree(struct rev_info *revs, struct commit *parent, struct commit *commit)
 327{
 328        struct tree *t1 = parent->tree;
 329        struct tree *t2 = commit->tree;
 330
 331        if (!t1)
 332                return REV_TREE_NEW;
 333        if (!t2)
 334                return REV_TREE_OLD;
 335
 336        if (revs->simplify_by_decoration) {
 337                /*
 338                 * If we are simplifying by decoration, then the commit
 339                 * is worth showing if it has a tag pointing at it.
 340                 */
 341                if (lookup_decoration(&name_decoration, &commit->object))
 342                        return REV_TREE_DIFFERENT;
 343                /*
 344                 * A commit that is not pointed by a tag is uninteresting
 345                 * if we are not limited by path.  This means that you will
 346                 * see the usual "commits that touch the paths" plus any
 347                 * tagged commit by specifying both --simplify-by-decoration
 348                 * and pathspec.
 349                 */
 350                if (!revs->prune_data.nr)
 351                        return REV_TREE_SAME;
 352        }
 353
 354        tree_difference = REV_TREE_SAME;
 355        DIFF_OPT_CLR(&revs->pruning, HAS_CHANGES);
 356        if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "",
 357                           &revs->pruning) < 0)
 358                return REV_TREE_DIFFERENT;
 359        return tree_difference;
 360}
 361
 362static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
 363{
 364        int retval;
 365        void *tree;
 366        unsigned long size;
 367        struct tree_desc empty, real;
 368        struct tree *t1 = commit->tree;
 369
 370        if (!t1)
 371                return 0;
 372
 373        tree = read_object_with_reference(t1->object.sha1, tree_type, &size, NULL);
 374        if (!tree)
 375                return 0;
 376        init_tree_desc(&real, tree, size);
 377        init_tree_desc(&empty, "", 0);
 378
 379        tree_difference = REV_TREE_SAME;
 380        DIFF_OPT_CLR(&revs->pruning, HAS_CHANGES);
 381        retval = diff_tree(&empty, &real, "", &revs->pruning);
 382        free(tree);
 383
 384        return retval >= 0 && (tree_difference == REV_TREE_SAME);
 385}
 386
 387static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 388{
 389        struct commit_list **pp, *parent;
 390        int tree_changed = 0, tree_same = 0;
 391
 392        /*
 393         * If we don't do pruning, everything is interesting
 394         */
 395        if (!revs->prune)
 396                return;
 397
 398        if (!commit->tree)
 399                return;
 400
 401        if (!commit->parents) {
 402                if (rev_same_tree_as_empty(revs, commit))
 403                        commit->object.flags |= TREESAME;
 404                return;
 405        }
 406
 407        /*
 408         * Normal non-merge commit? If we don't want to make the
 409         * history dense, we consider it always to be a change..
 410         */
 411        if (!revs->dense && !commit->parents->next)
 412                return;
 413
 414        pp = &commit->parents;
 415        while ((parent = *pp) != NULL) {
 416                struct commit *p = parent->item;
 417
 418                if (parse_commit(p) < 0)
 419                        die("cannot simplify commit %s (because of %s)",
 420                            sha1_to_hex(commit->object.sha1),
 421                            sha1_to_hex(p->object.sha1));
 422                switch (rev_compare_tree(revs, p, commit)) {
 423                case REV_TREE_SAME:
 424                        tree_same = 1;
 425                        if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
 426                                /* Even if a merge with an uninteresting
 427                                 * side branch brought the entire change
 428                                 * we are interested in, we do not want
 429                                 * to lose the other branches of this
 430                                 * merge, so we just keep going.
 431                                 */
 432                                pp = &parent->next;
 433                                continue;
 434                        }
 435                        parent->next = NULL;
 436                        commit->parents = parent;
 437                        commit->object.flags |= TREESAME;
 438                        return;
 439
 440                case REV_TREE_NEW:
 441                        if (revs->remove_empty_trees &&
 442                            rev_same_tree_as_empty(revs, p)) {
 443                                /* We are adding all the specified
 444                                 * paths from this parent, so the
 445                                 * history beyond this parent is not
 446                                 * interesting.  Remove its parents
 447                                 * (they are grandparents for us).
 448                                 * IOW, we pretend this parent is a
 449                                 * "root" commit.
 450                                 */
 451                                if (parse_commit(p) < 0)
 452                                        die("cannot simplify commit %s (invalid %s)",
 453                                            sha1_to_hex(commit->object.sha1),
 454                                            sha1_to_hex(p->object.sha1));
 455                                p->parents = NULL;
 456                        }
 457                /* fallthrough */
 458                case REV_TREE_OLD:
 459                case REV_TREE_DIFFERENT:
 460                        tree_changed = 1;
 461                        pp = &parent->next;
 462                        continue;
 463                }
 464                die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
 465        }
 466        if (tree_changed && !tree_same)
 467                return;
 468        commit->object.flags |= TREESAME;
 469}
 470
 471static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head,
 472                    struct commit_list *cached_base, struct commit_list **cache)
 473{
 474        struct commit_list *new_entry;
 475
 476        if (cached_base && p->date < cached_base->item->date)
 477                new_entry = commit_list_insert_by_date(p, &cached_base->next);
 478        else
 479                new_entry = commit_list_insert_by_date(p, head);
 480
 481        if (cache && (!*cache || p->date < (*cache)->item->date))
 482                *cache = new_entry;
 483}
 484
 485static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 486                    struct commit_list **list, struct commit_list **cache_ptr)
 487{
 488        struct commit_list *parent = commit->parents;
 489        unsigned left_flag;
 490        struct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;
 491
 492        if (commit->object.flags & ADDED)
 493                return 0;
 494        commit->object.flags |= ADDED;
 495
 496        /*
 497         * If the commit is uninteresting, don't try to
 498         * prune parents - we want the maximal uninteresting
 499         * set.
 500         *
 501         * Normally we haven't parsed the parent
 502         * yet, so we won't have a parent of a parent
 503         * here. However, it may turn out that we've
 504         * reached this commit some other way (where it
 505         * wasn't uninteresting), in which case we need
 506         * to mark its parents recursively too..
 507         */
 508        if (commit->object.flags & UNINTERESTING) {
 509                while (parent) {
 510                        struct commit *p = parent->item;
 511                        parent = parent->next;
 512                        if (p)
 513                                p->object.flags |= UNINTERESTING;
 514                        if (parse_commit(p) < 0)
 515                                continue;
 516                        if (p->parents)
 517                                mark_parents_uninteresting(p);
 518                        if (p->object.flags & SEEN)
 519                                continue;
 520                        p->object.flags |= SEEN;
 521                        commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 522                }
 523                return 0;
 524        }
 525
 526        /*
 527         * Ok, the commit wasn't uninteresting. Try to
 528         * simplify the commit history and find the parent
 529         * that has no differences in the path set if one exists.
 530         */
 531        try_to_simplify_commit(revs, commit);
 532
 533        if (revs->no_walk)
 534                return 0;
 535
 536        left_flag = (commit->object.flags & SYMMETRIC_LEFT);
 537
 538        for (parent = commit->parents; parent; parent = parent->next) {
 539                struct commit *p = parent->item;
 540
 541                if (parse_commit(p) < 0)
 542                        return -1;
 543                if (revs->show_source && !p->util)
 544                        p->util = commit->util;
 545                p->object.flags |= left_flag;
 546                if (!(p->object.flags & SEEN)) {
 547                        p->object.flags |= SEEN;
 548                        commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 549                }
 550                if (revs->first_parent_only)
 551                        break;
 552        }
 553        return 0;
 554}
 555
 556static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 557{
 558        struct commit_list *p;
 559        int left_count = 0, right_count = 0;
 560        int left_first;
 561        struct patch_ids ids;
 562        unsigned cherry_flag;
 563
 564        /* First count the commits on the left and on the right */
 565        for (p = list; p; p = p->next) {
 566                struct commit *commit = p->item;
 567                unsigned flags = commit->object.flags;
 568                if (flags & BOUNDARY)
 569                        ;
 570                else if (flags & SYMMETRIC_LEFT)
 571                        left_count++;
 572                else
 573                        right_count++;
 574        }
 575
 576        if (!left_count || !right_count)
 577                return;
 578
 579        left_first = left_count < right_count;
 580        init_patch_ids(&ids);
 581        ids.diffopts.pathspec = revs->diffopt.pathspec;
 582
 583        /* Compute patch-ids for one side */
 584        for (p = list; p; p = p->next) {
 585                struct commit *commit = p->item;
 586                unsigned flags = commit->object.flags;
 587
 588                if (flags & BOUNDARY)
 589                        continue;
 590                /*
 591                 * If we have fewer left, left_first is set and we omit
 592                 * commits on the right branch in this loop.  If we have
 593                 * fewer right, we skip the left ones.
 594                 */
 595                if (left_first != !!(flags & SYMMETRIC_LEFT))
 596                        continue;
 597                commit->util = add_commit_patch_id(commit, &ids);
 598        }
 599
 600        /* either cherry_mark or cherry_pick are true */
 601        cherry_flag = revs->cherry_mark ? PATCHSAME : SHOWN;
 602
 603        /* Check the other side */
 604        for (p = list; p; p = p->next) {
 605                struct commit *commit = p->item;
 606                struct patch_id *id;
 607                unsigned flags = commit->object.flags;
 608
 609                if (flags & BOUNDARY)
 610                        continue;
 611                /*
 612                 * If we have fewer left, left_first is set and we omit
 613                 * commits on the left branch in this loop.
 614                 */
 615                if (left_first == !!(flags & SYMMETRIC_LEFT))
 616                        continue;
 617
 618                /*
 619                 * Have we seen the same patch id?
 620                 */
 621                id = has_commit_patch_id(commit, &ids);
 622                if (!id)
 623                        continue;
 624                id->seen = 1;
 625                commit->object.flags |= cherry_flag;
 626        }
 627
 628        /* Now check the original side for seen ones */
 629        for (p = list; p; p = p->next) {
 630                struct commit *commit = p->item;
 631                struct patch_id *ent;
 632
 633                ent = commit->util;
 634                if (!ent)
 635                        continue;
 636                if (ent->seen)
 637                        commit->object.flags |= cherry_flag;
 638                commit->util = NULL;
 639        }
 640
 641        free_patch_ids(&ids);
 642}
 643
 644/* How many extra uninteresting commits we want to see.. */
 645#define SLOP 5
 646
 647static int still_interesting(struct commit_list *src, unsigned long date, int slop)
 648{
 649        /*
 650         * No source list at all? We're definitely done..
 651         */
 652        if (!src)
 653                return 0;
 654
 655        /*
 656         * Does the destination list contain entries with a date
 657         * before the source list? Definitely _not_ done.
 658         */
 659        if (date < src->item->date)
 660                return SLOP;
 661
 662        /*
 663         * Does the source list still have interesting commits in
 664         * it? Definitely not done..
 665         */
 666        if (!everybody_uninteresting(src))
 667                return SLOP;
 668
 669        /* Ok, we're closing in.. */
 670        return slop-1;
 671}
 672
 673/*
 674 * "rev-list --ancestry-path A..B" computes commits that are ancestors
 675 * of B but not ancestors of A but further limits the result to those
 676 * that are descendants of A.  This takes the list of bottom commits and
 677 * the result of "A..B" without --ancestry-path, and limits the latter
 678 * further to the ones that can reach one of the commits in "bottom".
 679 */
 680static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list)
 681{
 682        struct commit_list *p;
 683        struct commit_list *rlist = NULL;
 684        int made_progress;
 685
 686        /*
 687         * Reverse the list so that it will be likely that we would
 688         * process parents before children.
 689         */
 690        for (p = list; p; p = p->next)
 691                commit_list_insert(p->item, &rlist);
 692
 693        for (p = bottom; p; p = p->next)
 694                p->item->object.flags |= TMP_MARK;
 695
 696        /*
 697         * Mark the ones that can reach bottom commits in "list",
 698         * in a bottom-up fashion.
 699         */
 700        do {
 701                made_progress = 0;
 702                for (p = rlist; p; p = p->next) {
 703                        struct commit *c = p->item;
 704                        struct commit_list *parents;
 705                        if (c->object.flags & (TMP_MARK | UNINTERESTING))
 706                                continue;
 707                        for (parents = c->parents;
 708                             parents;
 709                             parents = parents->next) {
 710                                if (!(parents->item->object.flags & TMP_MARK))
 711                                        continue;
 712                                c->object.flags |= TMP_MARK;
 713                                made_progress = 1;
 714                                break;
 715                        }
 716                }
 717        } while (made_progress);
 718
 719        /*
 720         * NEEDSWORK: decide if we want to remove parents that are
 721         * not marked with TMP_MARK from commit->parents for commits
 722         * in the resulting list.  We may not want to do that, though.
 723         */
 724
 725        /*
 726         * The ones that are not marked with TMP_MARK are uninteresting
 727         */
 728        for (p = list; p; p = p->next) {
 729                struct commit *c = p->item;
 730                if (c->object.flags & TMP_MARK)
 731                        continue;
 732                c->object.flags |= UNINTERESTING;
 733        }
 734
 735        /* We are done with the TMP_MARK */
 736        for (p = list; p; p = p->next)
 737                p->item->object.flags &= ~TMP_MARK;
 738        for (p = bottom; p; p = p->next)
 739                p->item->object.flags &= ~TMP_MARK;
 740        free_commit_list(rlist);
 741}
 742
 743/*
 744 * Before walking the history, keep the set of "negative" refs the
 745 * caller has asked to exclude.
 746 *
 747 * This is used to compute "rev-list --ancestry-path A..B", as we need
 748 * to filter the result of "A..B" further to the ones that can actually
 749 * reach A.
 750 */
 751static struct commit_list *collect_bottom_commits(struct commit_list *list)
 752{
 753        struct commit_list *elem, *bottom = NULL;
 754        for (elem = list; elem; elem = elem->next)
 755                if (elem->item->object.flags & UNINTERESTING)
 756                        commit_list_insert(elem->item, &bottom);
 757        return bottom;
 758}
 759
 760/* Assumes either left_only or right_only is set */
 761static void limit_left_right(struct commit_list *list, struct rev_info *revs)
 762{
 763        struct commit_list *p;
 764
 765        for (p = list; p; p = p->next) {
 766                struct commit *commit = p->item;
 767
 768                if (revs->right_only) {
 769                        if (commit->object.flags & SYMMETRIC_LEFT)
 770                                commit->object.flags |= SHOWN;
 771                } else  /* revs->left_only is set */
 772                        if (!(commit->object.flags & SYMMETRIC_LEFT))
 773                                commit->object.flags |= SHOWN;
 774        }
 775}
 776
 777static int limit_list(struct rev_info *revs)
 778{
 779        int slop = SLOP;
 780        unsigned long date = ~0ul;
 781        struct commit_list *list = revs->commits;
 782        struct commit_list *newlist = NULL;
 783        struct commit_list **p = &newlist;
 784        struct commit_list *bottom = NULL;
 785
 786        if (revs->ancestry_path) {
 787                bottom = collect_bottom_commits(list);
 788                if (!bottom)
 789                        die("--ancestry-path given but there are no bottom commits");
 790        }
 791
 792        while (list) {
 793                struct commit_list *entry = list;
 794                struct commit *commit = list->item;
 795                struct object *obj = &commit->object;
 796                show_early_output_fn_t show;
 797
 798                list = list->next;
 799                free(entry);
 800
 801                if (revs->max_age != -1 && (commit->date < revs->max_age))
 802                        obj->flags |= UNINTERESTING;
 803                if (add_parents_to_list(revs, commit, &list, NULL) < 0)
 804                        return -1;
 805                if (obj->flags & UNINTERESTING) {
 806                        mark_parents_uninteresting(commit);
 807                        if (revs->show_all)
 808                                p = &commit_list_insert(commit, p)->next;
 809                        slop = still_interesting(list, date, slop);
 810                        if (slop)
 811                                continue;
 812                        /* If showing all, add the whole pending list to the end */
 813                        if (revs->show_all)
 814                                *p = list;
 815                        break;
 816                }
 817                if (revs->min_age != -1 && (commit->date > revs->min_age))
 818                        continue;
 819                date = commit->date;
 820                p = &commit_list_insert(commit, p)->next;
 821
 822                show = show_early_output;
 823                if (!show)
 824                        continue;
 825
 826                show(revs, newlist);
 827                show_early_output = NULL;
 828        }
 829        if (revs->cherry_pick || revs->cherry_mark)
 830                cherry_pick_list(newlist, revs);
 831
 832        if (revs->left_only || revs->right_only)
 833                limit_left_right(newlist, revs);
 834
 835        if (bottom) {
 836                limit_to_ancestry(bottom, newlist);
 837                free_commit_list(bottom);
 838        }
 839
 840        revs->commits = newlist;
 841        return 0;
 842}
 843
 844struct all_refs_cb {
 845        int all_flags;
 846        int warned_bad_reflog;
 847        struct rev_info *all_revs;
 848        const char *name_for_errormsg;
 849};
 850
 851static int handle_one_ref(const char *path, const unsigned char *sha1, int flag, void *cb_data)
 852{
 853        struct all_refs_cb *cb = cb_data;
 854        struct object *object = get_reference(cb->all_revs, path, sha1,
 855                                              cb->all_flags);
 856        add_pending_object(cb->all_revs, object, path);
 857        return 0;
 858}
 859
 860static void init_all_refs_cb(struct all_refs_cb *cb, struct rev_info *revs,
 861        unsigned flags)
 862{
 863        cb->all_revs = revs;
 864        cb->all_flags = flags;
 865}
 866
 867static void handle_refs(const char *submodule, struct rev_info *revs, unsigned flags,
 868                int (*for_each)(const char *, each_ref_fn, void *))
 869{
 870        struct all_refs_cb cb;
 871        init_all_refs_cb(&cb, revs, flags);
 872        for_each(submodule, handle_one_ref, &cb);
 873}
 874
 875static void handle_one_reflog_commit(unsigned char *sha1, void *cb_data)
 876{
 877        struct all_refs_cb *cb = cb_data;
 878        if (!is_null_sha1(sha1)) {
 879                struct object *o = parse_object(sha1);
 880                if (o) {
 881                        o->flags |= cb->all_flags;
 882                        add_pending_object(cb->all_revs, o, "");
 883                }
 884                else if (!cb->warned_bad_reflog) {
 885                        warning("reflog of '%s' references pruned commits",
 886                                cb->name_for_errormsg);
 887                        cb->warned_bad_reflog = 1;
 888                }
 889        }
 890}
 891
 892static int handle_one_reflog_ent(unsigned char *osha1, unsigned char *nsha1,
 893                const char *email, unsigned long timestamp, int tz,
 894                const char *message, void *cb_data)
 895{
 896        handle_one_reflog_commit(osha1, cb_data);
 897        handle_one_reflog_commit(nsha1, cb_data);
 898        return 0;
 899}
 900
 901static int handle_one_reflog(const char *path, const unsigned char *sha1, int flag, void *cb_data)
 902{
 903        struct all_refs_cb *cb = cb_data;
 904        cb->warned_bad_reflog = 0;
 905        cb->name_for_errormsg = path;
 906        for_each_reflog_ent(path, handle_one_reflog_ent, cb_data);
 907        return 0;
 908}
 909
 910static void handle_reflog(struct rev_info *revs, unsigned flags)
 911{
 912        struct all_refs_cb cb;
 913        cb.all_revs = revs;
 914        cb.all_flags = flags;
 915        for_each_reflog(handle_one_reflog, &cb);
 916}
 917
 918static int add_parents_only(struct rev_info *revs, const char *arg, int flags)
 919{
 920        unsigned char sha1[20];
 921        struct object *it;
 922        struct commit *commit;
 923        struct commit_list *parents;
 924
 925        if (*arg == '^') {
 926                flags ^= UNINTERESTING;
 927                arg++;
 928        }
 929        if (get_sha1(arg, sha1))
 930                return 0;
 931        while (1) {
 932                it = get_reference(revs, arg, sha1, 0);
 933                if (!it && revs->ignore_missing)
 934                        return 0;
 935                if (it->type != OBJ_TAG)
 936                        break;
 937                if (!((struct tag*)it)->tagged)
 938                        return 0;
 939                hashcpy(sha1, ((struct tag*)it)->tagged->sha1);
 940        }
 941        if (it->type != OBJ_COMMIT)
 942                return 0;
 943        commit = (struct commit *)it;
 944        for (parents = commit->parents; parents; parents = parents->next) {
 945                it = &parents->item->object;
 946                it->flags |= flags;
 947                add_pending_object(revs, it, arg);
 948        }
 949        return 1;
 950}
 951
 952void init_revisions(struct rev_info *revs, const char *prefix)
 953{
 954        memset(revs, 0, sizeof(*revs));
 955
 956        revs->abbrev = DEFAULT_ABBREV;
 957        revs->ignore_merges = 1;
 958        revs->simplify_history = 1;
 959        DIFF_OPT_SET(&revs->pruning, RECURSIVE);
 960        DIFF_OPT_SET(&revs->pruning, QUICK);
 961        revs->pruning.add_remove = file_add_remove;
 962        revs->pruning.change = file_change;
 963        revs->lifo = 1;
 964        revs->dense = 1;
 965        revs->prefix = prefix;
 966        revs->max_age = -1;
 967        revs->min_age = -1;
 968        revs->skip_count = -1;
 969        revs->max_count = -1;
 970        revs->max_parents = -1;
 971
 972        revs->commit_format = CMIT_FMT_DEFAULT;
 973
 974        revs->grep_filter.status_only = 1;
 975        revs->grep_filter.pattern_tail = &(revs->grep_filter.pattern_list);
 976        revs->grep_filter.header_tail = &(revs->grep_filter.header_list);
 977        revs->grep_filter.regflags = REG_NEWLINE;
 978
 979        diff_setup(&revs->diffopt);
 980        if (prefix && !revs->diffopt.prefix) {
 981                revs->diffopt.prefix = prefix;
 982                revs->diffopt.prefix_length = strlen(prefix);
 983        }
 984
 985        revs->notes_opt.use_default_notes = -1;
 986}
 987
 988static void add_pending_commit_list(struct rev_info *revs,
 989                                    struct commit_list *commit_list,
 990                                    unsigned int flags)
 991{
 992        while (commit_list) {
 993                struct object *object = &commit_list->item->object;
 994                object->flags |= flags;
 995                add_pending_object(revs, object, sha1_to_hex(object->sha1));
 996                commit_list = commit_list->next;
 997        }
 998}
 999
1000static void prepare_show_merge(struct rev_info *revs)
1001{
1002        struct commit_list *bases;
1003        struct commit *head, *other;
1004        unsigned char sha1[20];
1005        const char **prune = NULL;
1006        int i, prune_num = 1; /* counting terminating NULL */
1007
1008        if (get_sha1("HEAD", sha1) || !(head = lookup_commit(sha1)))
1009                die("--merge without HEAD?");
1010        if (get_sha1("MERGE_HEAD", sha1) || !(other = lookup_commit(sha1)))
1011                die("--merge without MERGE_HEAD?");
1012        add_pending_object(revs, &head->object, "HEAD");
1013        add_pending_object(revs, &other->object, "MERGE_HEAD");
1014        bases = get_merge_bases(head, other, 1);
1015        add_pending_commit_list(revs, bases, UNINTERESTING);
1016        free_commit_list(bases);
1017        head->object.flags |= SYMMETRIC_LEFT;
1018
1019        if (!active_nr)
1020                read_cache();
1021        for (i = 0; i < active_nr; i++) {
1022                struct cache_entry *ce = active_cache[i];
1023                if (!ce_stage(ce))
1024                        continue;
1025                if (ce_path_match(ce, &revs->prune_data)) {
1026                        prune_num++;
1027                        prune = xrealloc(prune, sizeof(*prune) * prune_num);
1028                        prune[prune_num-2] = ce->name;
1029                        prune[prune_num-1] = NULL;
1030                }
1031                while ((i+1 < active_nr) &&
1032                       ce_same_name(ce, active_cache[i+1]))
1033                        i++;
1034        }
1035        free_pathspec(&revs->prune_data);
1036        init_pathspec(&revs->prune_data, prune);
1037        revs->limited = 1;
1038}
1039
1040int handle_revision_arg(const char *arg, struct rev_info *revs,
1041                        int flags,
1042                        int cant_be_filename)
1043{
1044        unsigned mode;
1045        char *dotdot;
1046        struct object *object;
1047        unsigned char sha1[20];
1048        int local_flags;
1049
1050        dotdot = strstr(arg, "..");
1051        if (dotdot) {
1052                unsigned char from_sha1[20];
1053                const char *next = dotdot + 2;
1054                const char *this = arg;
1055                int symmetric = *next == '.';
1056                unsigned int flags_exclude = flags ^ UNINTERESTING;
1057
1058                *dotdot = 0;
1059                next += symmetric;
1060
1061                if (!*next)
1062                        next = "HEAD";
1063                if (dotdot == arg)
1064                        this = "HEAD";
1065                if (!get_sha1(this, from_sha1) &&
1066                    !get_sha1(next, sha1)) {
1067                        struct commit *a, *b;
1068                        struct commit_list *exclude;
1069
1070                        a = lookup_commit_reference(from_sha1);
1071                        b = lookup_commit_reference(sha1);
1072                        if (!a || !b) {
1073                                if (revs->ignore_missing)
1074                                        return 0;
1075                                die(symmetric ?
1076                                    "Invalid symmetric difference expression %s...%s" :
1077                                    "Invalid revision range %s..%s",
1078                                    arg, next);
1079                        }
1080
1081                        if (!cant_be_filename) {
1082                                *dotdot = '.';
1083                                verify_non_filename(revs->prefix, arg);
1084                        }
1085
1086                        if (symmetric) {
1087                                exclude = get_merge_bases(a, b, 1);
1088                                add_pending_commit_list(revs, exclude,
1089                                                        flags_exclude);
1090                                free_commit_list(exclude);
1091                                a->object.flags |= flags | SYMMETRIC_LEFT;
1092                        } else
1093                                a->object.flags |= flags_exclude;
1094                        b->object.flags |= flags;
1095                        add_pending_object(revs, &a->object, this);
1096                        add_pending_object(revs, &b->object, next);
1097                        return 0;
1098                }
1099                *dotdot = '.';
1100        }
1101        dotdot = strstr(arg, "^@");
1102        if (dotdot && !dotdot[2]) {
1103                *dotdot = 0;
1104                if (add_parents_only(revs, arg, flags))
1105                        return 0;
1106                *dotdot = '^';
1107        }
1108        dotdot = strstr(arg, "^!");
1109        if (dotdot && !dotdot[2]) {
1110                *dotdot = 0;
1111                if (!add_parents_only(revs, arg, flags ^ UNINTERESTING))
1112                        *dotdot = '^';
1113        }
1114
1115        local_flags = 0;
1116        if (*arg == '^') {
1117                local_flags = UNINTERESTING;
1118                arg++;
1119        }
1120        if (get_sha1_with_mode(arg, sha1, &mode))
1121                return revs->ignore_missing ? 0 : -1;
1122        if (!cant_be_filename)
1123                verify_non_filename(revs->prefix, arg);
1124        object = get_reference(revs, arg, sha1, flags ^ local_flags);
1125        add_pending_object_with_mode(revs, object, arg, mode);
1126        return 0;
1127}
1128
1129struct cmdline_pathspec {
1130        int alloc;
1131        int nr;
1132        const char **path;
1133};
1134
1135static void append_prune_data(struct cmdline_pathspec *prune, const char **av)
1136{
1137        while (*av) {
1138                ALLOC_GROW(prune->path, prune->nr+1, prune->alloc);
1139                prune->path[prune->nr++] = *(av++);
1140        }
1141}
1142
1143static void read_pathspec_from_stdin(struct rev_info *revs, struct strbuf *sb,
1144                                     struct cmdline_pathspec *prune)
1145{
1146        while (strbuf_getwholeline(sb, stdin, '\n') != EOF) {
1147                int len = sb->len;
1148                if (len && sb->buf[len - 1] == '\n')
1149                        sb->buf[--len] = '\0';
1150                ALLOC_GROW(prune->path, prune->nr+1, prune->alloc);
1151                prune->path[prune->nr++] = xstrdup(sb->buf);
1152        }
1153}
1154
1155static void read_revisions_from_stdin(struct rev_info *revs,
1156                                      struct cmdline_pathspec *prune)
1157{
1158        struct strbuf sb;
1159        int seen_dashdash = 0;
1160
1161        strbuf_init(&sb, 1000);
1162        while (strbuf_getwholeline(&sb, stdin, '\n') != EOF) {
1163                int len = sb.len;
1164                if (len && sb.buf[len - 1] == '\n')
1165                        sb.buf[--len] = '\0';
1166                if (!len)
1167                        break;
1168                if (sb.buf[0] == '-') {
1169                        if (len == 2 && sb.buf[1] == '-') {
1170                                seen_dashdash = 1;
1171                                break;
1172                        }
1173                        die("options not supported in --stdin mode");
1174                }
1175                if (handle_revision_arg(sb.buf, revs, 0, 1))
1176                        die("bad revision '%s'", sb.buf);
1177        }
1178        if (seen_dashdash)
1179                read_pathspec_from_stdin(revs, &sb, prune);
1180        strbuf_release(&sb);
1181}
1182
1183static void add_grep(struct rev_info *revs, const char *ptn, enum grep_pat_token what)
1184{
1185        append_grep_pattern(&revs->grep_filter, ptn, "command line", 0, what);
1186}
1187
1188static void add_header_grep(struct rev_info *revs, enum grep_header_field field, const char *pattern)
1189{
1190        append_header_grep_pattern(&revs->grep_filter, field, pattern);
1191}
1192
1193static void add_message_grep(struct rev_info *revs, const char *pattern)
1194{
1195        add_grep(revs, pattern, GREP_PATTERN_BODY);
1196}
1197
1198static int handle_revision_opt(struct rev_info *revs, int argc, const char **argv,
1199                               int *unkc, const char **unkv)
1200{
1201        const char *arg = argv[0];
1202        const char *optarg;
1203        int argcount;
1204
1205        /* pseudo revision arguments */
1206        if (!strcmp(arg, "--all") || !strcmp(arg, "--branches") ||
1207            !strcmp(arg, "--tags") || !strcmp(arg, "--remotes") ||
1208            !strcmp(arg, "--reflog") || !strcmp(arg, "--not") ||
1209            !strcmp(arg, "--no-walk") || !strcmp(arg, "--do-walk") ||
1210            !strcmp(arg, "--bisect") || !prefixcmp(arg, "--glob=") ||
1211            !prefixcmp(arg, "--branches=") || !prefixcmp(arg, "--tags=") ||
1212            !prefixcmp(arg, "--remotes="))
1213        {
1214                unkv[(*unkc)++] = arg;
1215                return 1;
1216        }
1217
1218        if ((argcount = parse_long_opt("max-count", argv, &optarg))) {
1219                revs->max_count = atoi(optarg);
1220                revs->no_walk = 0;
1221                return argcount;
1222        } else if ((argcount = parse_long_opt("skip", argv, &optarg))) {
1223                revs->skip_count = atoi(optarg);
1224                return argcount;
1225        } else if ((*arg == '-') && isdigit(arg[1])) {
1226        /* accept -<digit>, like traditional "head" */
1227                revs->max_count = atoi(arg + 1);
1228                revs->no_walk = 0;
1229        } else if (!strcmp(arg, "-n")) {
1230                if (argc <= 1)
1231                        return error("-n requires an argument");
1232                revs->max_count = atoi(argv[1]);
1233                revs->no_walk = 0;
1234                return 2;
1235        } else if (!prefixcmp(arg, "-n")) {
1236                revs->max_count = atoi(arg + 2);
1237                revs->no_walk = 0;
1238        } else if ((argcount = parse_long_opt("max-age", argv, &optarg))) {
1239                revs->max_age = atoi(optarg);
1240                return argcount;
1241        } else if ((argcount = parse_long_opt("since", argv, &optarg))) {
1242                revs->max_age = approxidate(optarg);
1243                return argcount;
1244        } else if ((argcount = parse_long_opt("after", argv, &optarg))) {
1245                revs->max_age = approxidate(optarg);
1246                return argcount;
1247        } else if ((argcount = parse_long_opt("min-age", argv, &optarg))) {
1248                revs->min_age = atoi(optarg);
1249                return argcount;
1250        } else if ((argcount = parse_long_opt("before", argv, &optarg))) {
1251                revs->min_age = approxidate(optarg);
1252                return argcount;
1253        } else if ((argcount = parse_long_opt("until", argv, &optarg))) {
1254                revs->min_age = approxidate(optarg);
1255                return argcount;
1256        } else if (!strcmp(arg, "--first-parent")) {
1257                revs->first_parent_only = 1;
1258        } else if (!strcmp(arg, "--ancestry-path")) {
1259                revs->ancestry_path = 1;
1260                revs->simplify_history = 0;
1261                revs->limited = 1;
1262        } else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) {
1263                init_reflog_walk(&revs->reflog_info);
1264        } else if (!strcmp(arg, "--default")) {
1265                if (argc <= 1)
1266                        return error("bad --default argument");
1267                revs->def = argv[1];
1268                return 2;
1269        } else if (!strcmp(arg, "--merge")) {
1270                revs->show_merge = 1;
1271        } else if (!strcmp(arg, "--topo-order")) {
1272                revs->lifo = 1;
1273                revs->topo_order = 1;
1274        } else if (!strcmp(arg, "--simplify-merges")) {
1275                revs->simplify_merges = 1;
1276                revs->rewrite_parents = 1;
1277                revs->simplify_history = 0;
1278                revs->limited = 1;
1279        } else if (!strcmp(arg, "--simplify-by-decoration")) {
1280                revs->simplify_merges = 1;
1281                revs->rewrite_parents = 1;
1282                revs->simplify_history = 0;
1283                revs->simplify_by_decoration = 1;
1284                revs->limited = 1;
1285                revs->prune = 1;
1286                load_ref_decorations(DECORATE_SHORT_REFS);
1287        } else if (!strcmp(arg, "--date-order")) {
1288                revs->lifo = 0;
1289                revs->topo_order = 1;
1290        } else if (!prefixcmp(arg, "--early-output")) {
1291                int count = 100;
1292                switch (arg[14]) {
1293                case '=':
1294                        count = atoi(arg+15);
1295                        /* Fallthrough */
1296                case 0:
1297                        revs->topo_order = 1;
1298                       revs->early_output = count;
1299                }
1300        } else if (!strcmp(arg, "--parents")) {
1301                revs->rewrite_parents = 1;
1302                revs->print_parents = 1;
1303        } else if (!strcmp(arg, "--dense")) {
1304                revs->dense = 1;
1305        } else if (!strcmp(arg, "--sparse")) {
1306                revs->dense = 0;
1307        } else if (!strcmp(arg, "--show-all")) {
1308                revs->show_all = 1;
1309        } else if (!strcmp(arg, "--remove-empty")) {
1310                revs->remove_empty_trees = 1;
1311        } else if (!strcmp(arg, "--merges")) {
1312                revs->min_parents = 2;
1313        } else if (!strcmp(arg, "--no-merges")) {
1314                revs->max_parents = 1;
1315        } else if (!prefixcmp(arg, "--min-parents=")) {
1316                revs->min_parents = atoi(arg+14);
1317        } else if (!prefixcmp(arg, "--no-min-parents")) {
1318                revs->min_parents = 0;
1319        } else if (!prefixcmp(arg, "--max-parents=")) {
1320                revs->max_parents = atoi(arg+14);
1321        } else if (!prefixcmp(arg, "--no-max-parents")) {
1322                revs->max_parents = -1;
1323        } else if (!strcmp(arg, "--boundary")) {
1324                revs->boundary = 1;
1325        } else if (!strcmp(arg, "--left-right")) {
1326                revs->left_right = 1;
1327        } else if (!strcmp(arg, "--left-only")) {
1328                if (revs->right_only)
1329                        die("--left-only is incompatible with --right-only"
1330                            " or --cherry");
1331                revs->left_only = 1;
1332        } else if (!strcmp(arg, "--right-only")) {
1333                if (revs->left_only)
1334                        die("--right-only is incompatible with --left-only");
1335                revs->right_only = 1;
1336        } else if (!strcmp(arg, "--cherry")) {
1337                if (revs->left_only)
1338                        die("--cherry is incompatible with --left-only");
1339                revs->cherry_mark = 1;
1340                revs->right_only = 1;
1341                revs->max_parents = 1;
1342                revs->limited = 1;
1343        } else if (!strcmp(arg, "--count")) {
1344                revs->count = 1;
1345        } else if (!strcmp(arg, "--cherry-mark")) {
1346                if (revs->cherry_pick)
1347                        die("--cherry-mark is incompatible with --cherry-pick");
1348                revs->cherry_mark = 1;
1349                revs->limited = 1; /* needs limit_list() */
1350        } else if (!strcmp(arg, "--cherry-pick")) {
1351                if (revs->cherry_mark)
1352                        die("--cherry-pick is incompatible with --cherry-mark");
1353                revs->cherry_pick = 1;
1354                revs->limited = 1;
1355        } else if (!strcmp(arg, "--objects")) {
1356                revs->tag_objects = 1;
1357                revs->tree_objects = 1;
1358                revs->blob_objects = 1;
1359        } else if (!strcmp(arg, "--objects-edge")) {
1360                revs->tag_objects = 1;
1361                revs->tree_objects = 1;
1362                revs->blob_objects = 1;
1363                revs->edge_hint = 1;
1364        } else if (!strcmp(arg, "--unpacked")) {
1365                revs->unpacked = 1;
1366        } else if (!prefixcmp(arg, "--unpacked=")) {
1367                die("--unpacked=<packfile> no longer supported.");
1368        } else if (!strcmp(arg, "-r")) {
1369                revs->diff = 1;
1370                DIFF_OPT_SET(&revs->diffopt, RECURSIVE);
1371        } else if (!strcmp(arg, "-t")) {
1372                revs->diff = 1;
1373                DIFF_OPT_SET(&revs->diffopt, RECURSIVE);
1374                DIFF_OPT_SET(&revs->diffopt, TREE_IN_RECURSIVE);
1375        } else if (!strcmp(arg, "-m")) {
1376                revs->ignore_merges = 0;
1377        } else if (!strcmp(arg, "-c")) {
1378                revs->diff = 1;
1379                revs->dense_combined_merges = 0;
1380                revs->combine_merges = 1;
1381        } else if (!strcmp(arg, "--cc")) {
1382                revs->diff = 1;
1383                revs->dense_combined_merges = 1;
1384                revs->combine_merges = 1;
1385        } else if (!strcmp(arg, "-v")) {
1386                revs->verbose_header = 1;
1387        } else if (!strcmp(arg, "--pretty")) {
1388                revs->verbose_header = 1;
1389                revs->pretty_given = 1;
1390                get_commit_format(arg+8, revs);
1391        } else if (!prefixcmp(arg, "--pretty=") || !prefixcmp(arg, "--format=")) {
1392                /*
1393                 * Detached form ("--pretty X" as opposed to "--pretty=X")
1394                 * not allowed, since the argument is optional.
1395                 */
1396                revs->verbose_header = 1;
1397                revs->pretty_given = 1;
1398                get_commit_format(arg+9, revs);
1399        } else if (!strcmp(arg, "--show-notes") || !strcmp(arg, "--notes")) {
1400                revs->show_notes = 1;
1401                revs->show_notes_given = 1;
1402                revs->notes_opt.use_default_notes = 1;
1403        } else if (!prefixcmp(arg, "--show-notes=") ||
1404                   !prefixcmp(arg, "--notes=")) {
1405                struct strbuf buf = STRBUF_INIT;
1406                revs->show_notes = 1;
1407                revs->show_notes_given = 1;
1408                if (!prefixcmp(arg, "--show-notes")) {
1409                        if (revs->notes_opt.use_default_notes < 0)
1410                                revs->notes_opt.use_default_notes = 1;
1411                        strbuf_addstr(&buf, arg+13);
1412                }
1413                else
1414                        strbuf_addstr(&buf, arg+8);
1415                expand_notes_ref(&buf);
1416                string_list_append(&revs->notes_opt.extra_notes_refs,
1417                                   strbuf_detach(&buf, NULL));
1418        } else if (!strcmp(arg, "--no-notes")) {
1419                revs->show_notes = 0;
1420                revs->show_notes_given = 1;
1421                revs->notes_opt.use_default_notes = -1;
1422                /* we have been strdup'ing ourselves, so trick
1423                 * string_list into free()ing strings */
1424                revs->notes_opt.extra_notes_refs.strdup_strings = 1;
1425                string_list_clear(&revs->notes_opt.extra_notes_refs, 0);
1426                revs->notes_opt.extra_notes_refs.strdup_strings = 0;
1427        } else if (!strcmp(arg, "--standard-notes")) {
1428                revs->show_notes_given = 1;
1429                revs->notes_opt.use_default_notes = 1;
1430        } else if (!strcmp(arg, "--no-standard-notes")) {
1431                revs->notes_opt.use_default_notes = 0;
1432        } else if (!strcmp(arg, "--oneline")) {
1433                revs->verbose_header = 1;
1434                get_commit_format("oneline", revs);
1435                revs->pretty_given = 1;
1436                revs->abbrev_commit = 1;
1437        } else if (!strcmp(arg, "--graph")) {
1438                revs->topo_order = 1;
1439                revs->rewrite_parents = 1;
1440                revs->graph = graph_init(revs);
1441        } else if (!strcmp(arg, "--root")) {
1442                revs->show_root_diff = 1;
1443        } else if (!strcmp(arg, "--no-commit-id")) {
1444                revs->no_commit_id = 1;
1445        } else if (!strcmp(arg, "--always")) {
1446                revs->always_show_header = 1;
1447        } else if (!strcmp(arg, "--no-abbrev")) {
1448                revs->abbrev = 0;
1449        } else if (!strcmp(arg, "--abbrev")) {
1450                revs->abbrev = DEFAULT_ABBREV;
1451        } else if (!prefixcmp(arg, "--abbrev=")) {
1452                revs->abbrev = strtoul(arg + 9, NULL, 10);
1453                if (revs->abbrev < MINIMUM_ABBREV)
1454                        revs->abbrev = MINIMUM_ABBREV;
1455                else if (revs->abbrev > 40)
1456                        revs->abbrev = 40;
1457        } else if (!strcmp(arg, "--abbrev-commit")) {
1458                revs->abbrev_commit = 1;
1459                revs->abbrev_commit_given = 1;
1460        } else if (!strcmp(arg, "--no-abbrev-commit")) {
1461                revs->abbrev_commit = 0;
1462        } else if (!strcmp(arg, "--full-diff")) {
1463                revs->diff = 1;
1464                revs->full_diff = 1;
1465        } else if (!strcmp(arg, "--full-history")) {
1466                revs->simplify_history = 0;
1467        } else if (!strcmp(arg, "--relative-date")) {
1468                revs->date_mode = DATE_RELATIVE;
1469                revs->date_mode_explicit = 1;
1470        } else if ((argcount = parse_long_opt("date", argv, &optarg))) {
1471                revs->date_mode = parse_date_format(optarg);
1472                revs->date_mode_explicit = 1;
1473                return argcount;
1474        } else if (!strcmp(arg, "--log-size")) {
1475                revs->show_log_size = 1;
1476        }
1477        /*
1478         * Grepping the commit log
1479         */
1480        else if ((argcount = parse_long_opt("author", argv, &optarg))) {
1481                add_header_grep(revs, GREP_HEADER_AUTHOR, optarg);
1482                return argcount;
1483        } else if ((argcount = parse_long_opt("committer", argv, &optarg))) {
1484                add_header_grep(revs, GREP_HEADER_COMMITTER, optarg);
1485                return argcount;
1486        } else if ((argcount = parse_long_opt("grep", argv, &optarg))) {
1487                add_message_grep(revs, optarg);
1488                return argcount;
1489        } else if (!strcmp(arg, "--extended-regexp") || !strcmp(arg, "-E")) {
1490                revs->grep_filter.regflags |= REG_EXTENDED;
1491        } else if (!strcmp(arg, "--regexp-ignore-case") || !strcmp(arg, "-i")) {
1492                revs->grep_filter.regflags |= REG_ICASE;
1493        } else if (!strcmp(arg, "--fixed-strings") || !strcmp(arg, "-F")) {
1494                revs->grep_filter.fixed = 1;
1495        } else if (!strcmp(arg, "--all-match")) {
1496                revs->grep_filter.all_match = 1;
1497        } else if ((argcount = parse_long_opt("encoding", argv, &optarg))) {
1498                if (strcmp(optarg, "none"))
1499                        git_log_output_encoding = xstrdup(optarg);
1500                else
1501                        git_log_output_encoding = "";
1502                return argcount;
1503        } else if (!strcmp(arg, "--reverse")) {
1504                revs->reverse ^= 1;
1505        } else if (!strcmp(arg, "--children")) {
1506                revs->children.name = "children";
1507                revs->limited = 1;
1508        } else if (!strcmp(arg, "--ignore-missing")) {
1509                revs->ignore_missing = 1;
1510        } else {
1511                int opts = diff_opt_parse(&revs->diffopt, argv, argc);
1512                if (!opts)
1513                        unkv[(*unkc)++] = arg;
1514                return opts;
1515        }
1516
1517        return 1;
1518}
1519
1520void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx,
1521                        const struct option *options,
1522                        const char * const usagestr[])
1523{
1524        int n = handle_revision_opt(revs, ctx->argc, ctx->argv,
1525                                    &ctx->cpidx, ctx->out);
1526        if (n <= 0) {
1527                error("unknown option `%s'", ctx->argv[0]);
1528                usage_with_options(usagestr, options);
1529        }
1530        ctx->argv += n;
1531        ctx->argc -= n;
1532}
1533
1534static int for_each_bad_bisect_ref(const char *submodule, each_ref_fn fn, void *cb_data)
1535{
1536        return for_each_ref_in_submodule(submodule, "refs/bisect/bad", fn, cb_data);
1537}
1538
1539static int for_each_good_bisect_ref(const char *submodule, each_ref_fn fn, void *cb_data)
1540{
1541        return for_each_ref_in_submodule(submodule, "refs/bisect/good", fn, cb_data);
1542}
1543
1544static int handle_revision_pseudo_opt(const char *submodule,
1545                                struct rev_info *revs,
1546                                int argc, const char **argv, int *flags)
1547{
1548        const char *arg = argv[0];
1549        const char *optarg;
1550        int argcount;
1551
1552        /*
1553         * NOTE!
1554         *
1555         * Commands like "git shortlog" will not accept the options below
1556         * unless parse_revision_opt queues them (as opposed to erroring
1557         * out).
1558         *
1559         * When implementing your new pseudo-option, remember to
1560         * register it in the list at the top of handle_revision_opt.
1561         */
1562        if (!strcmp(arg, "--all")) {
1563                handle_refs(submodule, revs, *flags, for_each_ref_submodule);
1564                handle_refs(submodule, revs, *flags, head_ref_submodule);
1565        } else if (!strcmp(arg, "--branches")) {
1566                handle_refs(submodule, revs, *flags, for_each_branch_ref_submodule);
1567        } else if (!strcmp(arg, "--bisect")) {
1568                handle_refs(submodule, revs, *flags, for_each_bad_bisect_ref);
1569                handle_refs(submodule, revs, *flags ^ UNINTERESTING, for_each_good_bisect_ref);
1570                revs->bisect = 1;
1571        } else if (!strcmp(arg, "--tags")) {
1572                handle_refs(submodule, revs, *flags, for_each_tag_ref_submodule);
1573        } else if (!strcmp(arg, "--remotes")) {
1574                handle_refs(submodule, revs, *flags, for_each_remote_ref_submodule);
1575        } else if ((argcount = parse_long_opt("glob", argv, &optarg))) {
1576                struct all_refs_cb cb;
1577                init_all_refs_cb(&cb, revs, *flags);
1578                for_each_glob_ref(handle_one_ref, optarg, &cb);
1579                return argcount;
1580        } else if (!prefixcmp(arg, "--branches=")) {
1581                struct all_refs_cb cb;
1582                init_all_refs_cb(&cb, revs, *flags);
1583                for_each_glob_ref_in(handle_one_ref, arg + 11, "refs/heads/", &cb);
1584        } else if (!prefixcmp(arg, "--tags=")) {
1585                struct all_refs_cb cb;
1586                init_all_refs_cb(&cb, revs, *flags);
1587                for_each_glob_ref_in(handle_one_ref, arg + 7, "refs/tags/", &cb);
1588        } else if (!prefixcmp(arg, "--remotes=")) {
1589                struct all_refs_cb cb;
1590                init_all_refs_cb(&cb, revs, *flags);
1591                for_each_glob_ref_in(handle_one_ref, arg + 10, "refs/remotes/", &cb);
1592        } else if (!strcmp(arg, "--reflog")) {
1593                handle_reflog(revs, *flags);
1594        } else if (!strcmp(arg, "--not")) {
1595                *flags ^= UNINTERESTING;
1596        } else if (!strcmp(arg, "--no-walk")) {
1597                revs->no_walk = 1;
1598        } else if (!strcmp(arg, "--do-walk")) {
1599                revs->no_walk = 0;
1600        } else {
1601                return 0;
1602        }
1603
1604        return 1;
1605}
1606
1607/*
1608 * Parse revision information, filling in the "rev_info" structure,
1609 * and removing the used arguments from the argument list.
1610 *
1611 * Returns the number of arguments left that weren't recognized
1612 * (which are also moved to the head of the argument list)
1613 */
1614int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *opt)
1615{
1616        int i, flags, left, seen_dashdash, read_from_stdin, got_rev_arg = 0;
1617        struct cmdline_pathspec prune_data;
1618        const char *submodule = NULL;
1619
1620        memset(&prune_data, 0, sizeof(prune_data));
1621        if (opt)
1622                submodule = opt->submodule;
1623
1624        /* First, search for "--" */
1625        seen_dashdash = 0;
1626        for (i = 1; i < argc; i++) {
1627                const char *arg = argv[i];
1628                if (strcmp(arg, "--"))
1629                        continue;
1630                argv[i] = NULL;
1631                argc = i;
1632                if (argv[i + 1])
1633                        append_prune_data(&prune_data, argv + i + 1);
1634                seen_dashdash = 1;
1635                break;
1636        }
1637
1638        /* Second, deal with arguments and options */
1639        flags = 0;
1640        read_from_stdin = 0;
1641        for (left = i = 1; i < argc; i++) {
1642                const char *arg = argv[i];
1643                if (*arg == '-') {
1644                        int opts;
1645
1646                        opts = handle_revision_pseudo_opt(submodule,
1647                                                revs, argc - i, argv + i,
1648                                                &flags);
1649                        if (opts > 0) {
1650                                i += opts - 1;
1651                                continue;
1652                        }
1653
1654                        if (!strcmp(arg, "--stdin")) {
1655                                if (revs->disable_stdin) {
1656                                        argv[left++] = arg;
1657                                        continue;
1658                                }
1659                                if (read_from_stdin++)
1660                                        die("--stdin given twice?");
1661                                read_revisions_from_stdin(revs, &prune_data);
1662                                continue;
1663                        }
1664
1665                        opts = handle_revision_opt(revs, argc - i, argv + i, &left, argv);
1666                        if (opts > 0) {
1667                                i += opts - 1;
1668                                continue;
1669                        }
1670                        if (opts < 0)
1671                                exit(128);
1672                        continue;
1673                }
1674
1675                if (handle_revision_arg(arg, revs, flags, seen_dashdash)) {
1676                        int j;
1677                        if (seen_dashdash || *arg == '^')
1678                                die("bad revision '%s'", arg);
1679
1680                        /* If we didn't have a "--":
1681                         * (1) all filenames must exist;
1682                         * (2) all rev-args must not be interpretable
1683                         *     as a valid filename.
1684                         * but the latter we have checked in the main loop.
1685                         */
1686                        for (j = i; j < argc; j++)
1687                                verify_filename(revs->prefix, argv[j]);
1688
1689                        append_prune_data(&prune_data, argv + i);
1690                        break;
1691                }
1692                else
1693                        got_rev_arg = 1;
1694        }
1695
1696        if (prune_data.nr) {
1697                /*
1698                 * If we need to introduce the magic "a lone ':' means no
1699                 * pathspec whatsoever", here is the place to do so.
1700                 *
1701                 * if (prune_data.nr == 1 && !strcmp(prune_data[0], ":")) {
1702                 *      prune_data.nr = 0;
1703                 *      prune_data.alloc = 0;
1704                 *      free(prune_data.path);
1705                 *      prune_data.path = NULL;
1706                 * } else {
1707                 *      terminate prune_data.alloc with NULL and
1708                 *      call init_pathspec() to set revs->prune_data here.
1709                 * }
1710                 */
1711                ALLOC_GROW(prune_data.path, prune_data.nr+1, prune_data.alloc);
1712                prune_data.path[prune_data.nr++] = NULL;
1713                init_pathspec(&revs->prune_data,
1714                              get_pathspec(revs->prefix, prune_data.path));
1715        }
1716
1717        if (revs->def == NULL)
1718                revs->def = opt ? opt->def : NULL;
1719        if (opt && opt->tweak)
1720                opt->tweak(revs, opt);
1721        if (revs->show_merge)
1722                prepare_show_merge(revs);
1723        if (revs->def && !revs->pending.nr && !got_rev_arg) {
1724                unsigned char sha1[20];
1725                struct object *object;
1726                unsigned mode;
1727                if (get_sha1_with_mode(revs->def, sha1, &mode))
1728                        die("bad default revision '%s'", revs->def);
1729                object = get_reference(revs, revs->def, sha1, 0);
1730                add_pending_object_with_mode(revs, object, revs->def, mode);
1731        }
1732
1733        /* Did the user ask for any diff output? Run the diff! */
1734        if (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT)
1735                revs->diff = 1;
1736
1737        /* Pickaxe, diff-filter and rename following need diffs */
1738        if (revs->diffopt.pickaxe ||
1739            revs->diffopt.filter ||
1740            DIFF_OPT_TST(&revs->diffopt, FOLLOW_RENAMES))
1741                revs->diff = 1;
1742
1743        if (revs->topo_order)
1744                revs->limited = 1;
1745
1746        if (revs->prune_data.nr) {
1747                diff_tree_setup_paths(revs->prune_data.raw, &revs->pruning);
1748                /* Can't prune commits with rename following: the paths change.. */
1749                if (!DIFF_OPT_TST(&revs->diffopt, FOLLOW_RENAMES))
1750                        revs->prune = 1;
1751                if (!revs->full_diff)
1752                        diff_tree_setup_paths(revs->prune_data.raw, &revs->diffopt);
1753        }
1754        if (revs->combine_merges)
1755                revs->ignore_merges = 0;
1756        revs->diffopt.abbrev = revs->abbrev;
1757        if (diff_setup_done(&revs->diffopt) < 0)
1758                die("diff_setup_done failed");
1759
1760        compile_grep_patterns(&revs->grep_filter);
1761
1762        if (revs->reverse && revs->reflog_info)
1763                die("cannot combine --reverse with --walk-reflogs");
1764        if (revs->rewrite_parents && revs->children.name)
1765                die("cannot combine --parents and --children");
1766
1767        /*
1768         * Limitations on the graph functionality
1769         */
1770        if (revs->reverse && revs->graph)
1771                die("cannot combine --reverse with --graph");
1772
1773        if (revs->reflog_info && revs->graph)
1774                die("cannot combine --walk-reflogs with --graph");
1775
1776        return left;
1777}
1778
1779static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)
1780{
1781        struct commit_list *l = xcalloc(1, sizeof(*l));
1782
1783        l->item = child;
1784        l->next = add_decoration(&revs->children, &parent->object, l);
1785}
1786
1787static int remove_duplicate_parents(struct commit *commit)
1788{
1789        struct commit_list **pp, *p;
1790        int surviving_parents;
1791
1792        /* Examine existing parents while marking ones we have seen... */
1793        pp = &commit->parents;
1794        while ((p = *pp) != NULL) {
1795                struct commit *parent = p->item;
1796                if (parent->object.flags & TMP_MARK) {
1797                        *pp = p->next;
1798                        continue;
1799                }
1800                parent->object.flags |= TMP_MARK;
1801                pp = &p->next;
1802        }
1803        /* count them while clearing the temporary mark */
1804        surviving_parents = 0;
1805        for (p = commit->parents; p; p = p->next) {
1806                p->item->object.flags &= ~TMP_MARK;
1807                surviving_parents++;
1808        }
1809        return surviving_parents;
1810}
1811
1812struct merge_simplify_state {
1813        struct commit *simplified;
1814};
1815
1816static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs, struct commit *commit)
1817{
1818        struct merge_simplify_state *st;
1819
1820        st = lookup_decoration(&revs->merge_simplification, &commit->object);
1821        if (!st) {
1822                st = xcalloc(1, sizeof(*st));
1823                add_decoration(&revs->merge_simplification, &commit->object, st);
1824        }
1825        return st;
1826}
1827
1828static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)
1829{
1830        struct commit_list *p;
1831        struct merge_simplify_state *st, *pst;
1832        int cnt;
1833
1834        st = locate_simplify_state(revs, commit);
1835
1836        /*
1837         * Have we handled this one?
1838         */
1839        if (st->simplified)
1840                return tail;
1841
1842        /*
1843         * An UNINTERESTING commit simplifies to itself, so does a
1844         * root commit.  We do not rewrite parents of such commit
1845         * anyway.
1846         */
1847        if ((commit->object.flags & UNINTERESTING) || !commit->parents) {
1848                st->simplified = commit;
1849                return tail;
1850        }
1851
1852        /*
1853         * Do we know what commit all of our parents should be rewritten to?
1854         * Otherwise we are not ready to rewrite this one yet.
1855         */
1856        for (cnt = 0, p = commit->parents; p; p = p->next) {
1857                pst = locate_simplify_state(revs, p->item);
1858                if (!pst->simplified) {
1859                        tail = &commit_list_insert(p->item, tail)->next;
1860                        cnt++;
1861                }
1862        }
1863        if (cnt) {
1864                tail = &commit_list_insert(commit, tail)->next;
1865                return tail;
1866        }
1867
1868        /*
1869         * Rewrite our list of parents.
1870         */
1871        for (p = commit->parents; p; p = p->next) {
1872                pst = locate_simplify_state(revs, p->item);
1873                p->item = pst->simplified;
1874        }
1875        cnt = remove_duplicate_parents(commit);
1876
1877        /*
1878         * It is possible that we are a merge and one side branch
1879         * does not have any commit that touches the given paths;
1880         * in such a case, the immediate parents will be rewritten
1881         * to different commits.
1882         *
1883         *      o----X          X: the commit we are looking at;
1884         *     /    /           o: a commit that touches the paths;
1885         * ---o----'
1886         *
1887         * Further reduce the parents by removing redundant parents.
1888         */
1889        if (1 < cnt) {
1890                struct commit_list *h = reduce_heads(commit->parents);
1891                cnt = commit_list_count(h);
1892                free_commit_list(commit->parents);
1893                commit->parents = h;
1894        }
1895
1896        /*
1897         * A commit simplifies to itself if it is a root, if it is
1898         * UNINTERESTING, if it touches the given paths, or if it is a
1899         * merge and its parents simplifies to more than one commits
1900         * (the first two cases are already handled at the beginning of
1901         * this function).
1902         *
1903         * Otherwise, it simplifies to what its sole parent simplifies to.
1904         */
1905        if (!cnt ||
1906            (commit->object.flags & UNINTERESTING) ||
1907            !(commit->object.flags & TREESAME) ||
1908            (1 < cnt))
1909                st->simplified = commit;
1910        else {
1911                pst = locate_simplify_state(revs, commit->parents->item);
1912                st->simplified = pst->simplified;
1913        }
1914        return tail;
1915}
1916
1917static void simplify_merges(struct rev_info *revs)
1918{
1919        struct commit_list *list;
1920        struct commit_list *yet_to_do, **tail;
1921
1922        if (!revs->topo_order)
1923                sort_in_topological_order(&revs->commits, revs->lifo);
1924        if (!revs->prune)
1925                return;
1926
1927        /* feed the list reversed */
1928        yet_to_do = NULL;
1929        for (list = revs->commits; list; list = list->next)
1930                commit_list_insert(list->item, &yet_to_do);
1931        while (yet_to_do) {
1932                list = yet_to_do;
1933                yet_to_do = NULL;
1934                tail = &yet_to_do;
1935                while (list) {
1936                        struct commit *commit = list->item;
1937                        struct commit_list *next = list->next;
1938                        free(list);
1939                        list = next;
1940                        tail = simplify_one(revs, commit, tail);
1941                }
1942        }
1943
1944        /* clean up the result, removing the simplified ones */
1945        list = revs->commits;
1946        revs->commits = NULL;
1947        tail = &revs->commits;
1948        while (list) {
1949                struct commit *commit = list->item;
1950                struct commit_list *next = list->next;
1951                struct merge_simplify_state *st;
1952                free(list);
1953                list = next;
1954                st = locate_simplify_state(revs, commit);
1955                if (st->simplified == commit)
1956                        tail = &commit_list_insert(commit, tail)->next;
1957        }
1958}
1959
1960static void set_children(struct rev_info *revs)
1961{
1962        struct commit_list *l;
1963        for (l = revs->commits; l; l = l->next) {
1964                struct commit *commit = l->item;
1965                struct commit_list *p;
1966
1967                for (p = commit->parents; p; p = p->next)
1968                        add_child(revs, p->item, commit);
1969        }
1970}
1971
1972int prepare_revision_walk(struct rev_info *revs)
1973{
1974        int nr = revs->pending.nr;
1975        struct object_array_entry *e, *list;
1976
1977        e = list = revs->pending.objects;
1978        revs->pending.nr = 0;
1979        revs->pending.alloc = 0;
1980        revs->pending.objects = NULL;
1981        while (--nr >= 0) {
1982                struct commit *commit = handle_commit(revs, e->item, e->name);
1983                if (commit) {
1984                        if (!(commit->object.flags & SEEN)) {
1985                                commit->object.flags |= SEEN;
1986                                commit_list_insert_by_date(commit, &revs->commits);
1987                        }
1988                }
1989                e++;
1990        }
1991        free(list);
1992
1993        if (revs->no_walk)
1994                return 0;
1995        if (revs->limited)
1996                if (limit_list(revs) < 0)
1997                        return -1;
1998        if (revs->topo_order)
1999                sort_in_topological_order(&revs->commits, revs->lifo);
2000        if (revs->simplify_merges)
2001                simplify_merges(revs);
2002        if (revs->children.name)
2003                set_children(revs);
2004        return 0;
2005}
2006
2007enum rewrite_result {
2008        rewrite_one_ok,
2009        rewrite_one_noparents,
2010        rewrite_one_error
2011};
2012
2013static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)
2014{
2015        struct commit_list *cache = NULL;
2016
2017        for (;;) {
2018                struct commit *p = *pp;
2019                if (!revs->limited)
2020                        if (add_parents_to_list(revs, p, &revs->commits, &cache) < 0)
2021                                return rewrite_one_error;
2022                if (p->parents && p->parents->next)
2023                        return rewrite_one_ok;
2024                if (p->object.flags & UNINTERESTING)
2025                        return rewrite_one_ok;
2026                if (!(p->object.flags & TREESAME))
2027                        return rewrite_one_ok;
2028                if (!p->parents)
2029                        return rewrite_one_noparents;
2030                *pp = p->parents->item;
2031        }
2032}
2033
2034static int rewrite_parents(struct rev_info *revs, struct commit *commit)
2035{
2036        struct commit_list **pp = &commit->parents;
2037        while (*pp) {
2038                struct commit_list *parent = *pp;
2039                switch (rewrite_one(revs, &parent->item)) {
2040                case rewrite_one_ok:
2041                        break;
2042                case rewrite_one_noparents:
2043                        *pp = parent->next;
2044                        continue;
2045                case rewrite_one_error:
2046                        return -1;
2047                }
2048                pp = &parent->next;
2049        }
2050        remove_duplicate_parents(commit);
2051        return 0;
2052}
2053
2054static int commit_match(struct commit *commit, struct rev_info *opt)
2055{
2056        if (!opt->grep_filter.pattern_list && !opt->grep_filter.header_list)
2057                return 1;
2058        return grep_buffer(&opt->grep_filter,
2059                           NULL, /* we say nothing, not even filename */
2060                           commit->buffer, strlen(commit->buffer));
2061}
2062
2063static inline int want_ancestry(struct rev_info *revs)
2064{
2065        return (revs->rewrite_parents || revs->children.name);
2066}
2067
2068enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit)
2069{
2070        if (commit->object.flags & SHOWN)
2071                return commit_ignore;
2072        if (revs->unpacked && has_sha1_pack(commit->object.sha1))
2073                return commit_ignore;
2074        if (revs->show_all)
2075                return commit_show;
2076        if (commit->object.flags & UNINTERESTING)
2077                return commit_ignore;
2078        if (revs->min_age != -1 && (commit->date > revs->min_age))
2079                return commit_ignore;
2080        if (revs->min_parents || (revs->max_parents >= 0)) {
2081                int n = 0;
2082                struct commit_list *p;
2083                for (p = commit->parents; p; p = p->next)
2084                        n++;
2085                if ((n < revs->min_parents) ||
2086                    ((revs->max_parents >= 0) && (n > revs->max_parents)))
2087                        return commit_ignore;
2088        }
2089        if (!commit_match(commit, revs))
2090                return commit_ignore;
2091        if (revs->prune && revs->dense) {
2092                /* Commit without changes? */
2093                if (commit->object.flags & TREESAME) {
2094                        /* drop merges unless we want parenthood */
2095                        if (!want_ancestry(revs))
2096                                return commit_ignore;
2097                        /* non-merge - always ignore it */
2098                        if (!commit->parents || !commit->parents->next)
2099                                return commit_ignore;
2100                }
2101        }
2102        return commit_show;
2103}
2104
2105enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)
2106{
2107        enum commit_action action = get_commit_action(revs, commit);
2108
2109        if (action == commit_show &&
2110            !revs->show_all &&
2111            revs->prune && revs->dense && want_ancestry(revs)) {
2112                if (rewrite_parents(revs, commit) < 0)
2113                        return commit_error;
2114        }
2115        return action;
2116}
2117
2118static struct commit *get_revision_1(struct rev_info *revs)
2119{
2120        if (!revs->commits)
2121                return NULL;
2122
2123        do {
2124                struct commit_list *entry = revs->commits;
2125                struct commit *commit = entry->item;
2126
2127                revs->commits = entry->next;
2128                free(entry);
2129
2130                if (revs->reflog_info) {
2131                        fake_reflog_parent(revs->reflog_info, commit);
2132                        commit->object.flags &= ~(ADDED | SEEN | SHOWN);
2133                }
2134
2135                /*
2136                 * If we haven't done the list limiting, we need to look at
2137                 * the parents here. We also need to do the date-based limiting
2138                 * that we'd otherwise have done in limit_list().
2139                 */
2140                if (!revs->limited) {
2141                        if (revs->max_age != -1 &&
2142                            (commit->date < revs->max_age))
2143                                continue;
2144                        if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)
2145                                die("Failed to traverse parents of commit %s",
2146                                    sha1_to_hex(commit->object.sha1));
2147                }
2148
2149                switch (simplify_commit(revs, commit)) {
2150                case commit_ignore:
2151                        continue;
2152                case commit_error:
2153                        die("Failed to simplify parents of commit %s",
2154                            sha1_to_hex(commit->object.sha1));
2155                default:
2156                        return commit;
2157                }
2158        } while (revs->commits);
2159        return NULL;
2160}
2161
2162static void gc_boundary(struct object_array *array)
2163{
2164        unsigned nr = array->nr;
2165        unsigned alloc = array->alloc;
2166        struct object_array_entry *objects = array->objects;
2167
2168        if (alloc <= nr) {
2169                unsigned i, j;
2170                for (i = j = 0; i < nr; i++) {
2171                        if (objects[i].item->flags & SHOWN)
2172                                continue;
2173                        if (i != j)
2174                                objects[j] = objects[i];
2175                        j++;
2176                }
2177                for (i = j; i < nr; i++)
2178                        objects[i].item = NULL;
2179                array->nr = j;
2180        }
2181}
2182
2183static void create_boundary_commit_list(struct rev_info *revs)
2184{
2185        unsigned i;
2186        struct commit *c;
2187        struct object_array *array = &revs->boundary_commits;
2188        struct object_array_entry *objects = array->objects;
2189
2190        /*
2191         * If revs->commits is non-NULL at this point, an error occurred in
2192         * get_revision_1().  Ignore the error and continue printing the
2193         * boundary commits anyway.  (This is what the code has always
2194         * done.)
2195         */
2196        if (revs->commits) {
2197                free_commit_list(revs->commits);
2198                revs->commits = NULL;
2199        }
2200
2201        /*
2202         * Put all of the actual boundary commits from revs->boundary_commits
2203         * into revs->commits
2204         */
2205        for (i = 0; i < array->nr; i++) {
2206                c = (struct commit *)(objects[i].item);
2207                if (!c)
2208                        continue;
2209                if (!(c->object.flags & CHILD_SHOWN))
2210                        continue;
2211                if (c->object.flags & (SHOWN | BOUNDARY))
2212                        continue;
2213                c->object.flags |= BOUNDARY;
2214                commit_list_insert(c, &revs->commits);
2215        }
2216
2217        /*
2218         * If revs->topo_order is set, sort the boundary commits
2219         * in topological order
2220         */
2221        sort_in_topological_order(&revs->commits, revs->lifo);
2222}
2223
2224static struct commit *get_revision_internal(struct rev_info *revs)
2225{
2226        struct commit *c = NULL;
2227        struct commit_list *l;
2228
2229        if (revs->boundary == 2) {
2230                /*
2231                 * All of the normal commits have already been returned,
2232                 * and we are now returning boundary commits.
2233                 * create_boundary_commit_list() has populated
2234                 * revs->commits with the remaining commits to return.
2235                 */
2236                c = pop_commit(&revs->commits);
2237                if (c)
2238                        c->object.flags |= SHOWN;
2239                return c;
2240        }
2241
2242        /*
2243         * Now pick up what they want to give us
2244         */
2245        c = get_revision_1(revs);
2246        if (c) {
2247                while (0 < revs->skip_count) {
2248                        revs->skip_count--;
2249                        c = get_revision_1(revs);
2250                        if (!c)
2251                                break;
2252                }
2253        }
2254
2255        /*
2256         * Check the max_count.
2257         */
2258        switch (revs->max_count) {
2259        case -1:
2260                break;
2261        case 0:
2262                c = NULL;
2263                break;
2264        default:
2265                revs->max_count--;
2266        }
2267
2268        if (c)
2269                c->object.flags |= SHOWN;
2270
2271        if (!revs->boundary) {
2272                return c;
2273        }
2274
2275        if (!c) {
2276                /*
2277                 * get_revision_1() runs out the commits, and
2278                 * we are done computing the boundaries.
2279                 * switch to boundary commits output mode.
2280                 */
2281                revs->boundary = 2;
2282
2283                /*
2284                 * Update revs->commits to contain the list of
2285                 * boundary commits.
2286                 */
2287                create_boundary_commit_list(revs);
2288
2289                return get_revision_internal(revs);
2290        }
2291
2292        /*
2293         * boundary commits are the commits that are parents of the
2294         * ones we got from get_revision_1() but they themselves are
2295         * not returned from get_revision_1().  Before returning
2296         * 'c', we need to mark its parents that they could be boundaries.
2297         */
2298
2299        for (l = c->parents; l; l = l->next) {
2300                struct object *p;
2301                p = &(l->item->object);
2302                if (p->flags & (CHILD_SHOWN | SHOWN))
2303                        continue;
2304                p->flags |= CHILD_SHOWN;
2305                gc_boundary(&revs->boundary_commits);
2306                add_object_array(p, NULL, &revs->boundary_commits);
2307        }
2308
2309        return c;
2310}
2311
2312struct commit *get_revision(struct rev_info *revs)
2313{
2314        struct commit *c;
2315        struct commit_list *reversed;
2316
2317        if (revs->reverse) {
2318                reversed = NULL;
2319                while ((c = get_revision_internal(revs))) {
2320                        commit_list_insert(c, &reversed);
2321                }
2322                revs->commits = reversed;
2323                revs->reverse = 0;
2324                revs->reverse_output_stage = 1;
2325        }
2326
2327        if (revs->reverse_output_stage)
2328                return pop_commit(&revs->commits);
2329
2330        c = get_revision_internal(revs);
2331        if (c && revs->graph)
2332                graph_update(revs->graph, c);
2333        return c;
2334}
2335
2336char *get_revision_mark(const struct rev_info *revs, const struct commit *commit)
2337{
2338        if (commit->object.flags & BOUNDARY)
2339                return "-";
2340        else if (commit->object.flags & UNINTERESTING)
2341                return "^";
2342        else if (commit->object.flags & PATCHSAME)
2343                return "=";
2344        else if (!revs || revs->left_right) {
2345                if (commit->object.flags & SYMMETRIC_LEFT)
2346                        return "<";
2347                else
2348                        return ">";
2349        } else if (revs->graph)
2350                return "*";
2351        else if (revs->cherry_mark)
2352                return "+";
2353        return "";
2354}
2355
2356void put_revision_mark(const struct rev_info *revs, const struct commit *commit)
2357{
2358        char *mark = get_revision_mark(revs, commit);
2359        if (!strlen(mark))
2360                return;
2361        fputs(mark, stdout);
2362        putchar(' ');
2363}