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