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