revision.c

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