revision.con commit git-svn: migrate out of contrib (60d02cc)
   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
  10static char *path_name(struct name_path *path, const char *name)
  11{
  12        struct name_path *p;
  13        char *n, *m;
  14        int nlen = strlen(name);
  15        int len = nlen + 1;
  16
  17        for (p = path; p; p = p->up) {
  18                if (p->elem_len)
  19                        len += p->elem_len + 1;
  20        }
  21        n = xmalloc(len);
  22        m = n + len - (nlen + 1);
  23        strcpy(m, name);
  24        for (p = path; p; p = p->up) {
  25                if (p->elem_len) {
  26                        m -= p->elem_len + 1;
  27                        memcpy(m, p->elem, p->elem_len);
  28                        m[p->elem_len] = '/';
  29                }
  30        }
  31        return n;
  32}
  33
  34void add_object(struct object *obj,
  35                struct object_array *p,
  36                struct name_path *path,
  37                const char *name)
  38{
  39        add_object_array(obj, path_name(path, name), p);
  40}
  41
  42static void mark_blob_uninteresting(struct blob *blob)
  43{
  44        if (blob->object.flags & UNINTERESTING)
  45                return;
  46        blob->object.flags |= UNINTERESTING;
  47}
  48
  49void mark_tree_uninteresting(struct tree *tree)
  50{
  51        struct tree_desc desc;
  52        struct name_entry entry;
  53        struct object *obj = &tree->object;
  54
  55        if (obj->flags & UNINTERESTING)
  56                return;
  57        obj->flags |= UNINTERESTING;
  58        if (!has_sha1_file(obj->sha1))
  59                return;
  60        if (parse_tree(tree) < 0)
  61                die("bad tree %s", sha1_to_hex(obj->sha1));
  62
  63        desc.buf = tree->buffer;
  64        desc.size = tree->size;
  65        while (tree_entry(&desc, &entry)) {
  66                if (S_ISDIR(entry.mode))
  67                        mark_tree_uninteresting(lookup_tree(entry.sha1));
  68                else
  69                        mark_blob_uninteresting(lookup_blob(entry.sha1));
  70        }
  71
  72        /*
  73         * We don't care about the tree any more
  74         * after it has been marked uninteresting.
  75         */
  76        free(tree->buffer);
  77        tree->buffer = NULL;
  78}
  79
  80void mark_parents_uninteresting(struct commit *commit)
  81{
  82        struct commit_list *parents = commit->parents;
  83
  84        while (parents) {
  85                struct commit *commit = parents->item;
  86                if (!(commit->object.flags & UNINTERESTING)) {
  87                        commit->object.flags |= UNINTERESTING;
  88
  89                        /*
  90                         * Normally we haven't parsed the parent
  91                         * yet, so we won't have a parent of a parent
  92                         * here. However, it may turn out that we've
  93                         * reached this commit some other way (where it
  94                         * wasn't uninteresting), in which case we need
  95                         * to mark its parents recursively too..
  96                         */
  97                        if (commit->parents)
  98                                mark_parents_uninteresting(commit);
  99                }
 100
 101                /*
 102                 * A missing commit is ok iff its parent is marked
 103                 * uninteresting.
 104                 *
 105                 * We just mark such a thing parsed, so that when
 106                 * it is popped next time around, we won't be trying
 107                 * to parse it and get an error.
 108                 */
 109                if (!has_sha1_file(commit->object.sha1))
 110                        commit->object.parsed = 1;
 111                parents = parents->next;
 112        }
 113}
 114
 115void add_pending_object(struct rev_info *revs, struct object *obj, const char *name)
 116{
 117        add_object_array(obj, name, &revs->pending);
 118}
 119
 120static struct object *get_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)
 121{
 122        struct object *object;
 123
 124        object = parse_object(sha1);
 125        if (!object)
 126                die("bad object %s", name);
 127        object->flags |= flags;
 128        return object;
 129}
 130
 131static struct commit *handle_commit(struct rev_info *revs, struct object *object, const char *name)
 132{
 133        unsigned long flags = object->flags;
 134
 135        /*
 136         * Tag object? Look what it points to..
 137         */
 138        while (object->type == TYPE_TAG) {
 139                struct tag *tag = (struct tag *) object;
 140                if (revs->tag_objects && !(flags & UNINTERESTING))
 141                        add_pending_object(revs, object, tag->tag);
 142                object = parse_object(tag->tagged->sha1);
 143                if (!object)
 144                        die("bad object %s", sha1_to_hex(tag->tagged->sha1));
 145        }
 146
 147        /*
 148         * Commit object? Just return it, we'll do all the complex
 149         * reachability crud.
 150         */
 151        if (object->type == TYPE_COMMIT) {
 152                struct commit *commit = (struct commit *)object;
 153                if (parse_commit(commit) < 0)
 154                        die("unable to parse commit %s", name);
 155                if (flags & UNINTERESTING) {
 156                        commit->object.flags |= UNINTERESTING;
 157                        mark_parents_uninteresting(commit);
 158                        revs->limited = 1;
 159                }
 160                return commit;
 161        }
 162
 163        /*
 164         * Tree object? Either mark it uniniteresting, or add it
 165         * to the list of objects to look at later..
 166         */
 167        if (object->type == TYPE_TREE) {
 168                struct tree *tree = (struct tree *)object;
 169                if (!revs->tree_objects)
 170                        return NULL;
 171                if (flags & UNINTERESTING) {
 172                        mark_tree_uninteresting(tree);
 173                        return NULL;
 174                }
 175                add_pending_object(revs, object, "");
 176                return NULL;
 177        }
 178
 179        /*
 180         * Blob object? You know the drill by now..
 181         */
 182        if (object->type == TYPE_BLOB) {
 183                struct blob *blob = (struct blob *)object;
 184                if (!revs->blob_objects)
 185                        return NULL;
 186                if (flags & UNINTERESTING) {
 187                        mark_blob_uninteresting(blob);
 188                        return NULL;
 189                }
 190                add_pending_object(revs, object, "");
 191                return NULL;
 192        }
 193        die("%s is unknown object", name);
 194}
 195
 196static int everybody_uninteresting(struct commit_list *orig)
 197{
 198        struct commit_list *list = orig;
 199        while (list) {
 200                struct commit *commit = list->item;
 201                list = list->next;
 202                if (commit->object.flags & UNINTERESTING)
 203                        continue;
 204                return 0;
 205        }
 206        return 1;
 207}
 208
 209static int tree_difference = REV_TREE_SAME;
 210
 211static void file_add_remove(struct diff_options *options,
 212                    int addremove, unsigned mode,
 213                    const unsigned char *sha1,
 214                    const char *base, const char *path)
 215{
 216        int diff = REV_TREE_DIFFERENT;
 217
 218        /*
 219         * Is it an add of a new file? It means that the old tree
 220         * didn't have it at all, so we will turn "REV_TREE_SAME" ->
 221         * "REV_TREE_NEW", but leave any "REV_TREE_DIFFERENT" alone
 222         * (and if it already was "REV_TREE_NEW", we'll keep it
 223         * "REV_TREE_NEW" of course).
 224         */
 225        if (addremove == '+') {
 226                diff = tree_difference;
 227                if (diff != REV_TREE_SAME)
 228                        return;
 229                diff = REV_TREE_NEW;
 230        }
 231        tree_difference = diff;
 232}
 233
 234static void file_change(struct diff_options *options,
 235                 unsigned old_mode, unsigned new_mode,
 236                 const unsigned char *old_sha1,
 237                 const unsigned char *new_sha1,
 238                 const char *base, const char *path)
 239{
 240        tree_difference = REV_TREE_DIFFERENT;
 241}
 242
 243int rev_compare_tree(struct rev_info *revs, struct tree *t1, struct tree *t2)
 244{
 245        if (!t1)
 246                return REV_TREE_NEW;
 247        if (!t2)
 248                return REV_TREE_DIFFERENT;
 249        tree_difference = REV_TREE_SAME;
 250        if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "",
 251                           &revs->pruning) < 0)
 252                return REV_TREE_DIFFERENT;
 253        return tree_difference;
 254}
 255
 256int rev_same_tree_as_empty(struct rev_info *revs, struct tree *t1)
 257{
 258        int retval;
 259        void *tree;
 260        struct tree_desc empty, real;
 261
 262        if (!t1)
 263                return 0;
 264
 265        tree = read_object_with_reference(t1->object.sha1, tree_type, &real.size, NULL);
 266        if (!tree)
 267                return 0;
 268        real.buf = tree;
 269
 270        empty.buf = "";
 271        empty.size = 0;
 272
 273        tree_difference = 0;
 274        retval = diff_tree(&empty, &real, "", &revs->pruning);
 275        free(tree);
 276
 277        return retval >= 0 && !tree_difference;
 278}
 279
 280static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 281{
 282        struct commit_list **pp, *parent;
 283        int tree_changed = 0, tree_same = 0;
 284
 285        if (!commit->tree)
 286                return;
 287
 288        if (!commit->parents) {
 289                if (!rev_same_tree_as_empty(revs, commit->tree))
 290                        commit->object.flags |= TREECHANGE;
 291                return;
 292        }
 293
 294        pp = &commit->parents;
 295        while ((parent = *pp) != NULL) {
 296                struct commit *p = parent->item;
 297
 298                parse_commit(p);
 299                switch (rev_compare_tree(revs, p->tree, commit->tree)) {
 300                case REV_TREE_SAME:
 301                        tree_same = 1;
 302                        if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
 303                                /* Even if a merge with an uninteresting
 304                                 * side branch brought the entire change
 305                                 * we are interested in, we do not want
 306                                 * to lose the other branches of this
 307                                 * merge, so we just keep going.
 308                                 */
 309                                pp = &parent->next;
 310                                continue;
 311                        }
 312                        parent->next = NULL;
 313                        commit->parents = parent;
 314                        return;
 315
 316                case REV_TREE_NEW:
 317                        if (revs->remove_empty_trees &&
 318                            rev_same_tree_as_empty(revs, p->tree)) {
 319                                /* We are adding all the specified
 320                                 * paths from this parent, so the
 321                                 * history beyond this parent is not
 322                                 * interesting.  Remove its parents
 323                                 * (they are grandparents for us).
 324                                 * IOW, we pretend this parent is a
 325                                 * "root" commit.
 326                                 */
 327                                parse_commit(p);
 328                                p->parents = NULL;
 329                        }
 330                /* fallthrough */
 331                case REV_TREE_DIFFERENT:
 332                        tree_changed = 1;
 333                        pp = &parent->next;
 334                        continue;
 335                }
 336                die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
 337        }
 338        if (tree_changed && !tree_same)
 339                commit->object.flags |= TREECHANGE;
 340}
 341
 342static void add_parents_to_list(struct rev_info *revs, struct commit *commit, struct commit_list **list)
 343{
 344        struct commit_list *parent = commit->parents;
 345
 346        if (commit->object.flags & ADDED)
 347                return;
 348        commit->object.flags |= ADDED;
 349
 350        /*
 351         * If the commit is uninteresting, don't try to
 352         * prune parents - we want the maximal uninteresting
 353         * set.
 354         *
 355         * Normally we haven't parsed the parent
 356         * yet, so we won't have a parent of a parent
 357         * here. However, it may turn out that we've
 358         * reached this commit some other way (where it
 359         * wasn't uninteresting), in which case we need
 360         * to mark its parents recursively too..
 361         */
 362        if (commit->object.flags & UNINTERESTING) {
 363                while (parent) {
 364                        struct commit *p = parent->item;
 365                        parent = parent->next;
 366                        parse_commit(p);
 367                        p->object.flags |= UNINTERESTING;
 368                        if (p->parents)
 369                                mark_parents_uninteresting(p);
 370                        if (p->object.flags & SEEN)
 371                                continue;
 372                        p->object.flags |= SEEN;
 373                        insert_by_date(p, list);
 374                }
 375                return;
 376        }
 377
 378        /*
 379         * Ok, the commit wasn't uninteresting. Try to
 380         * simplify the commit history and find the parent
 381         * that has no differences in the path set if one exists.
 382         */
 383        if (revs->prune_fn)
 384                revs->prune_fn(revs, commit);
 385
 386        if (revs->no_walk)
 387                return;
 388
 389        parent = commit->parents;
 390        while (parent) {
 391                struct commit *p = parent->item;
 392
 393                parent = parent->next;
 394
 395                parse_commit(p);
 396                if (p->object.flags & SEEN)
 397                        continue;
 398                p->object.flags |= SEEN;
 399                insert_by_date(p, list);
 400        }
 401}
 402
 403static void limit_list(struct rev_info *revs)
 404{
 405        struct commit_list *list = revs->commits;
 406        struct commit_list *newlist = NULL;
 407        struct commit_list **p = &newlist;
 408
 409        while (list) {
 410                struct commit_list *entry = list;
 411                struct commit *commit = list->item;
 412                struct object *obj = &commit->object;
 413
 414                list = list->next;
 415                free(entry);
 416
 417                if (revs->max_age != -1 && (commit->date < revs->max_age))
 418                        obj->flags |= UNINTERESTING;
 419                if (revs->unpacked && has_sha1_pack(obj->sha1))
 420                        obj->flags |= UNINTERESTING;
 421                add_parents_to_list(revs, commit, &list);
 422                if (obj->flags & UNINTERESTING) {
 423                        mark_parents_uninteresting(commit);
 424                        if (everybody_uninteresting(list))
 425                                break;
 426                        continue;
 427                }
 428                if (revs->min_age != -1 && (commit->date > revs->min_age))
 429                        continue;
 430                p = &commit_list_insert(commit, p)->next;
 431        }
 432        if (revs->boundary) {
 433                /* mark the ones that are on the result list first */
 434                for (list = newlist; list; list = list->next) {
 435                        struct commit *commit = list->item;
 436                        commit->object.flags |= TMP_MARK;
 437                }
 438                for (list = newlist; list; list = list->next) {
 439                        struct commit *commit = list->item;
 440                        struct object *obj = &commit->object;
 441                        struct commit_list *parent;
 442                        if (obj->flags & UNINTERESTING)
 443                                continue;
 444                        for (parent = commit->parents;
 445                             parent;
 446                             parent = parent->next) {
 447                                struct commit *pcommit = parent->item;
 448                                if (!(pcommit->object.flags & UNINTERESTING))
 449                                        continue;
 450                                pcommit->object.flags |= BOUNDARY;
 451                                if (pcommit->object.flags & TMP_MARK)
 452                                        continue;
 453                                pcommit->object.flags |= TMP_MARK;
 454                                p = &commit_list_insert(pcommit, p)->next;
 455                        }
 456                }
 457                for (list = newlist; list; list = list->next) {
 458                        struct commit *commit = list->item;
 459                        commit->object.flags &= ~TMP_MARK;
 460                }
 461        }
 462        revs->commits = newlist;
 463}
 464
 465static int all_flags;
 466static struct rev_info *all_revs;
 467
 468static int handle_one_ref(const char *path, const unsigned char *sha1)
 469{
 470        struct object *object = get_reference(all_revs, path, sha1, all_flags);
 471        add_pending_object(all_revs, object, "");
 472        return 0;
 473}
 474
 475static void handle_all(struct rev_info *revs, unsigned flags)
 476{
 477        all_revs = revs;
 478        all_flags = flags;
 479        for_each_ref(handle_one_ref);
 480}
 481
 482static int add_parents_only(struct rev_info *revs, const char *arg, int flags)
 483{
 484        unsigned char sha1[20];
 485        struct object *it;
 486        struct commit *commit;
 487        struct commit_list *parents;
 488
 489        if (*arg == '^') {
 490                flags ^= UNINTERESTING;
 491                arg++;
 492        }
 493        if (get_sha1(arg, sha1))
 494                return 0;
 495        while (1) {
 496                it = get_reference(revs, arg, sha1, 0);
 497                if (it->type != TYPE_TAG)
 498                        break;
 499                memcpy(sha1, ((struct tag*)it)->tagged->sha1, 20);
 500        }
 501        if (it->type != TYPE_COMMIT)
 502                return 0;
 503        commit = (struct commit *)it;
 504        for (parents = commit->parents; parents; parents = parents->next) {
 505                it = &parents->item->object;
 506                it->flags |= flags;
 507                add_pending_object(revs, it, arg);
 508        }
 509        return 1;
 510}
 511
 512void init_revisions(struct rev_info *revs)
 513{
 514        memset(revs, 0, sizeof(*revs));
 515
 516        revs->abbrev = DEFAULT_ABBREV;
 517        revs->ignore_merges = 1;
 518        revs->simplify_history = 1;
 519        revs->pruning.recursive = 1;
 520        revs->pruning.add_remove = file_add_remove;
 521        revs->pruning.change = file_change;
 522        revs->lifo = 1;
 523        revs->dense = 1;
 524        revs->prefix = setup_git_directory();
 525        revs->max_age = -1;
 526        revs->min_age = -1;
 527        revs->max_count = -1;
 528
 529        revs->prune_fn = NULL;
 530        revs->prune_data = NULL;
 531
 532        revs->topo_setter = topo_sort_default_setter;
 533        revs->topo_getter = topo_sort_default_getter;
 534
 535        revs->commit_format = CMIT_FMT_DEFAULT;
 536
 537        diff_setup(&revs->diffopt);
 538}
 539
 540/*
 541 * Parse revision information, filling in the "rev_info" structure,
 542 * and removing the used arguments from the argument list.
 543 *
 544 * Returns the number of arguments left that weren't recognized
 545 * (which are also moved to the head of the argument list)
 546 */
 547int setup_revisions(int argc, const char **argv, struct rev_info *revs, const char *def)
 548{
 549        int i, flags, seen_dashdash;
 550        const char **unrecognized = argv + 1;
 551        int left = 1;
 552
 553        /* First, search for "--" */
 554        seen_dashdash = 0;
 555        for (i = 1; i < argc; i++) {
 556                const char *arg = argv[i];
 557                if (strcmp(arg, "--"))
 558                        continue;
 559                argv[i] = NULL;
 560                argc = i;
 561                revs->prune_data = get_pathspec(revs->prefix, argv + i + 1);
 562                seen_dashdash = 1;
 563                break;
 564        }
 565
 566        flags = 0;
 567        for (i = 1; i < argc; i++) {
 568                struct object *object;
 569                const char *arg = argv[i];
 570                unsigned char sha1[20];
 571                char *dotdot;
 572                int local_flags;
 573
 574                if (*arg == '-') {
 575                        int opts;
 576                        if (!strncmp(arg, "--max-count=", 12)) {
 577                                revs->max_count = atoi(arg + 12);
 578                                continue;
 579                        }
 580                        /* accept -<digit>, like traditional "head" */
 581                        if ((*arg == '-') && isdigit(arg[1])) {
 582                                revs->max_count = atoi(arg + 1);
 583                                continue;
 584                        }
 585                        if (!strcmp(arg, "-n")) {
 586                                if (argc <= i + 1)
 587                                        die("-n requires an argument");
 588                                revs->max_count = atoi(argv[++i]);
 589                                continue;
 590                        }
 591                        if (!strncmp(arg,"-n",2)) {
 592                                revs->max_count = atoi(arg + 2);
 593                                continue;
 594                        }
 595                        if (!strncmp(arg, "--max-age=", 10)) {
 596                                revs->max_age = atoi(arg + 10);
 597                                continue;
 598                        }
 599                        if (!strncmp(arg, "--since=", 8)) {
 600                                revs->max_age = approxidate(arg + 8);
 601                                continue;
 602                        }
 603                        if (!strncmp(arg, "--after=", 8)) {
 604                                revs->max_age = approxidate(arg + 8);
 605                                continue;
 606                        }
 607                        if (!strncmp(arg, "--min-age=", 10)) {
 608                                revs->min_age = atoi(arg + 10);
 609                                continue;
 610                        }
 611                        if (!strncmp(arg, "--before=", 9)) {
 612                                revs->min_age = approxidate(arg + 9);
 613                                continue;
 614                        }
 615                        if (!strncmp(arg, "--until=", 8)) {
 616                                revs->min_age = approxidate(arg + 8);
 617                                continue;
 618                        }
 619                        if (!strcmp(arg, "--all")) {
 620                                handle_all(revs, flags);
 621                                continue;
 622                        }
 623                        if (!strcmp(arg, "--not")) {
 624                                flags ^= UNINTERESTING;
 625                                continue;
 626                        }
 627                        if (!strcmp(arg, "--default")) {
 628                                if (++i >= argc)
 629                                        die("bad --default argument");
 630                                def = argv[i];
 631                                continue;
 632                        }
 633                        if (!strcmp(arg, "--topo-order")) {
 634                                revs->topo_order = 1;
 635                                continue;
 636                        }
 637                        if (!strcmp(arg, "--date-order")) {
 638                                revs->lifo = 0;
 639                                revs->topo_order = 1;
 640                                continue;
 641                        }
 642                        if (!strcmp(arg, "--parents")) {
 643                                revs->parents = 1;
 644                                continue;
 645                        }
 646                        if (!strcmp(arg, "--dense")) {
 647                                revs->dense = 1;
 648                                continue;
 649                        }
 650                        if (!strcmp(arg, "--sparse")) {
 651                                revs->dense = 0;
 652                                continue;
 653                        }
 654                        if (!strcmp(arg, "--remove-empty")) {
 655                                revs->remove_empty_trees = 1;
 656                                continue;
 657                        }
 658                        if (!strcmp(arg, "--no-merges")) {
 659                                revs->no_merges = 1;
 660                                continue;
 661                        }
 662                        if (!strcmp(arg, "--boundary")) {
 663                                revs->boundary = 1;
 664                                continue;
 665                        }
 666                        if (!strcmp(arg, "--objects")) {
 667                                revs->tag_objects = 1;
 668                                revs->tree_objects = 1;
 669                                revs->blob_objects = 1;
 670                                continue;
 671                        }
 672                        if (!strcmp(arg, "--objects-edge")) {
 673                                revs->tag_objects = 1;
 674                                revs->tree_objects = 1;
 675                                revs->blob_objects = 1;
 676                                revs->edge_hint = 1;
 677                                continue;
 678                        }
 679                        if (!strcmp(arg, "--unpacked")) {
 680                                revs->unpacked = 1;
 681                                continue;
 682                        }
 683                        if (!strcmp(arg, "-r")) {
 684                                revs->diff = 1;
 685                                revs->diffopt.recursive = 1;
 686                                continue;
 687                        }
 688                        if (!strcmp(arg, "-t")) {
 689                                revs->diff = 1;
 690                                revs->diffopt.recursive = 1;
 691                                revs->diffopt.tree_in_recursive = 1;
 692                                continue;
 693                        }
 694                        if (!strcmp(arg, "-m")) {
 695                                revs->ignore_merges = 0;
 696                                continue;
 697                        }
 698                        if (!strcmp(arg, "-c")) {
 699                                revs->diff = 1;
 700                                revs->dense_combined_merges = 0;
 701                                revs->combine_merges = 1;
 702                                continue;
 703                        }
 704                        if (!strcmp(arg, "--cc")) {
 705                                revs->diff = 1;
 706                                revs->dense_combined_merges = 1;
 707                                revs->combine_merges = 1;
 708                                continue;
 709                        }
 710                        if (!strcmp(arg, "-v")) {
 711                                revs->verbose_header = 1;
 712                                continue;
 713                        }
 714                        if (!strncmp(arg, "--pretty", 8)) {
 715                                revs->verbose_header = 1;
 716                                revs->commit_format = get_commit_format(arg+8);
 717                                continue;
 718                        }
 719                        if (!strcmp(arg, "--root")) {
 720                                revs->show_root_diff = 1;
 721                                continue;
 722                        }
 723                        if (!strcmp(arg, "--no-commit-id")) {
 724                                revs->no_commit_id = 1;
 725                                continue;
 726                        }
 727                        if (!strcmp(arg, "--always")) {
 728                                revs->always_show_header = 1;
 729                                continue;
 730                        }
 731                        if (!strcmp(arg, "--no-abbrev")) {
 732                                revs->abbrev = 0;
 733                                continue;
 734                        }
 735                        if (!strcmp(arg, "--abbrev")) {
 736                                revs->abbrev = DEFAULT_ABBREV;
 737                                continue;
 738                        }
 739                        if (!strncmp(arg, "--abbrev=", 9)) {
 740                                revs->abbrev = strtoul(arg + 9, NULL, 10);
 741                                if (revs->abbrev < MINIMUM_ABBREV)
 742                                        revs->abbrev = MINIMUM_ABBREV;
 743                                else if (revs->abbrev > 40)
 744                                        revs->abbrev = 40;
 745                                continue;
 746                        }
 747                        if (!strcmp(arg, "--abbrev-commit")) {
 748                                revs->abbrev_commit = 1;
 749                                continue;
 750                        }
 751                        if (!strcmp(arg, "--full-diff")) {
 752                                revs->diff = 1;
 753                                revs->full_diff = 1;
 754                                continue;
 755                        }
 756                        if (!strcmp(arg, "--full-history")) {
 757                                revs->simplify_history = 0;
 758                                continue;
 759                        }
 760                        opts = diff_opt_parse(&revs->diffopt, argv+i, argc-i);
 761                        if (opts > 0) {
 762                                revs->diff = 1;
 763                                i += opts - 1;
 764                                continue;
 765                        }
 766                        *unrecognized++ = arg;
 767                        left++;
 768                        continue;
 769                }
 770                dotdot = strstr(arg, "..");
 771                if (dotdot) {
 772                        unsigned char from_sha1[20];
 773                        const char *next = dotdot + 2;
 774                        const char *this = arg;
 775                        *dotdot = 0;
 776                        if (!*next)
 777                                next = "HEAD";
 778                        if (dotdot == arg)
 779                                this = "HEAD";
 780                        if (!get_sha1(this, from_sha1) &&
 781                            !get_sha1(next, sha1)) {
 782                                struct object *exclude;
 783                                struct object *include;
 784
 785                                exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
 786                                include = get_reference(revs, next, sha1, flags);
 787                                if (!exclude || !include)
 788                                        die("Invalid revision range %s..%s", arg, next);
 789
 790                                if (!seen_dashdash) {
 791                                        *dotdot = '.';
 792                                        verify_non_filename(revs->prefix, arg);
 793                                }
 794                                add_pending_object(revs, exclude, this);
 795                                add_pending_object(revs, include, next);
 796                                continue;
 797                        }
 798                        *dotdot = '.';
 799                }
 800                dotdot = strstr(arg, "^@");
 801                if (dotdot && !dotdot[2]) {
 802                        *dotdot = 0;
 803                        if (add_parents_only(revs, arg, flags))
 804                                continue;
 805                        *dotdot = '^';
 806                }
 807                local_flags = 0;
 808                if (*arg == '^') {
 809                        local_flags = UNINTERESTING;
 810                        arg++;
 811                }
 812                if (get_sha1(arg, sha1)) {
 813                        int j;
 814
 815                        if (seen_dashdash || local_flags)
 816                                die("bad revision '%s'", arg);
 817
 818                        /* If we didn't have a "--":
 819                         * (1) all filenames must exist;
 820                         * (2) all rev-args must not be interpretable
 821                         *     as a valid filename.
 822                         * but the latter we have checked in the main loop.
 823                         */
 824                        for (j = i; j < argc; j++)
 825                                verify_filename(revs->prefix, argv[j]);
 826
 827                        revs->prune_data = get_pathspec(revs->prefix, argv + i);
 828                        break;
 829                }
 830                if (!seen_dashdash)
 831                        verify_non_filename(revs->prefix, arg);
 832                object = get_reference(revs, arg, sha1, flags ^ local_flags);
 833                add_pending_object(revs, object, arg);
 834        }
 835        if (def && !revs->pending.nr) {
 836                unsigned char sha1[20];
 837                struct object *object;
 838                if (get_sha1(def, sha1))
 839                        die("bad default revision '%s'", def);
 840                object = get_reference(revs, def, sha1, 0);
 841                add_pending_object(revs, object, def);
 842        }
 843
 844        if (revs->topo_order || revs->unpacked)
 845                revs->limited = 1;
 846
 847        if (revs->prune_data) {
 848                diff_tree_setup_paths(revs->prune_data, &revs->pruning);
 849                revs->prune_fn = try_to_simplify_commit;
 850                if (!revs->full_diff)
 851                        diff_tree_setup_paths(revs->prune_data, &revs->diffopt);
 852        }
 853        if (revs->combine_merges) {
 854                revs->ignore_merges = 0;
 855                if (revs->dense_combined_merges && !revs->diffopt.output_format)
 856                        revs->diffopt.output_format = DIFF_FORMAT_PATCH;
 857        }
 858        revs->diffopt.abbrev = revs->abbrev;
 859        diff_setup_done(&revs->diffopt);
 860
 861        return left;
 862}
 863
 864void prepare_revision_walk(struct rev_info *revs)
 865{
 866        int nr = revs->pending.nr;
 867        struct object_array_entry *list = revs->pending.objects;
 868
 869        revs->pending.nr = 0;
 870        revs->pending.alloc = 0;
 871        revs->pending.objects = NULL;
 872        while (--nr >= 0) {
 873                struct commit *commit = handle_commit(revs, list->item, list->name);
 874                if (commit) {
 875                        if (!(commit->object.flags & SEEN)) {
 876                                commit->object.flags |= SEEN;
 877                                insert_by_date(commit, &revs->commits);
 878                        }
 879                }
 880                list++;
 881        }
 882
 883        if (revs->no_walk)
 884                return;
 885        if (revs->limited)
 886                limit_list(revs);
 887        if (revs->topo_order)
 888                sort_in_topological_order_fn(&revs->commits, revs->lifo,
 889                                             revs->topo_setter,
 890                                             revs->topo_getter);
 891}
 892
 893static int rewrite_one(struct rev_info *revs, struct commit **pp)
 894{
 895        for (;;) {
 896                struct commit *p = *pp;
 897                if (!revs->limited)
 898                        add_parents_to_list(revs, p, &revs->commits);
 899                if (p->parents && p->parents->next)
 900                        return 0;
 901                if (p->object.flags & (TREECHANGE | UNINTERESTING))
 902                        return 0;
 903                if (!p->parents)
 904                        return -1;
 905                *pp = p->parents->item;
 906        }
 907}
 908
 909static void rewrite_parents(struct rev_info *revs, struct commit *commit)
 910{
 911        struct commit_list **pp = &commit->parents;
 912        while (*pp) {
 913                struct commit_list *parent = *pp;
 914                if (rewrite_one(revs, &parent->item) < 0) {
 915                        *pp = parent->next;
 916                        continue;
 917                }
 918                pp = &parent->next;
 919        }
 920}
 921
 922static void mark_boundary_to_show(struct commit *commit)
 923{
 924        struct commit_list *p = commit->parents;
 925        while (p) {
 926                commit = p->item;
 927                p = p->next;
 928                if (commit->object.flags & BOUNDARY)
 929                        commit->object.flags |= BOUNDARY_SHOW;
 930        }
 931}
 932
 933struct commit *get_revision(struct rev_info *revs)
 934{
 935        struct commit_list *list = revs->commits;
 936
 937        if (!list)
 938                return NULL;
 939
 940        /* Check the max_count ... */
 941        switch (revs->max_count) {
 942        case -1:
 943                break;
 944        case 0:
 945                return NULL;
 946        default:
 947                revs->max_count--;
 948        }
 949
 950        do {
 951                struct commit_list *entry = revs->commits;
 952                struct commit *commit = entry->item;
 953
 954                revs->commits = entry->next;
 955                free(entry);
 956
 957                /*
 958                 * If we haven't done the list limiting, we need to look at
 959                 * the parents here. We also need to do the date-based limiting
 960                 * that we'd otherwise have done in limit_list().
 961                 */
 962                if (!revs->limited) {
 963                        if ((revs->unpacked &&
 964                             has_sha1_pack(commit->object.sha1)) ||
 965                            (revs->max_age != -1 &&
 966                             (commit->date < revs->max_age)))
 967                                continue;
 968                        add_parents_to_list(revs, commit, &revs->commits);
 969                }
 970                if (commit->object.flags & SHOWN)
 971                        continue;
 972
 973                /* We want to show boundary commits only when their
 974                 * children are shown.  When path-limiter is in effect,
 975                 * rewrite_parents() drops some commits from getting shown,
 976                 * and there is no point showing boundary parents that
 977                 * are not shown.  After rewrite_parents() rewrites the
 978                 * parents of a commit that is shown, we mark the boundary
 979                 * parents with BOUNDARY_SHOW.
 980                 */
 981                if (commit->object.flags & BOUNDARY_SHOW) {
 982                        commit->object.flags |= SHOWN;
 983                        return commit;
 984                }
 985                if (commit->object.flags & UNINTERESTING)
 986                        continue;
 987                if (revs->min_age != -1 && (commit->date > revs->min_age))
 988                        continue;
 989                if (revs->no_merges &&
 990                    commit->parents && commit->parents->next)
 991                        continue;
 992                if (revs->prune_fn && revs->dense) {
 993                        /* Commit without changes? */
 994                        if (!(commit->object.flags & TREECHANGE)) {
 995                                /* drop merges unless we want parenthood */
 996                                if (!revs->parents)
 997                                        continue;
 998                                /* non-merge - always ignore it */
 999                                if (!commit->parents || !commit->parents->next)
1000                                        continue;
1001                        }
1002                        if (revs->parents)
1003                                rewrite_parents(revs, commit);
1004                }
1005                if (revs->boundary)
1006                        mark_boundary_to_show(commit);
1007                commit->object.flags |= SHOWN;
1008                return commit;
1009        } while (revs->commits);
1010        return NULL;
1011}