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