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