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