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