revision.c · leroysheep/CrazyWebTemps

master

bisect jch maint master next seen test todo

c 4,792 lines 133 KB

Raw

1	#define USE_THE_REPOSITORY_VARIABLE
2	#define DISABLE_SIGN_COMPARE_WARNINGS
3
4	#include "git-compat-util.h"
5	#include "config.h"
6	#include "environment.h"
7	#include "gettext.h"
8	#include "hex.h"
9	#include "object-name.h"
10	#include "object-file.h"
11	#include "odb.h"
12	#include "oidset.h"
13	#include "tag.h"
14	#include "blob.h"
15	#include "tree.h"
16	#include "commit.h"
17	#include "diff.h"
18	#include "diff-merges.h"
19	#include "refs.h"
20	#include "revision.h"
21	#include "repository.h"
22	#include "graph.h"
23	#include "grep.h"
24	#include "reflog-walk.h"
25	#include "patch-ids.h"
26	#include "decorate.h"
27	#include "string-list.h"
28	#include "line-log.h"
29	#include "log-tree.h"
30	#include "mailmap.h"
31	#include "commit-slab.h"
32	#include "cache-tree.h"
33	#include "bisect.h"
34	#include "packfile.h"
35	#include "worktree.h"
36	#include "path.h"
37	#include "read-cache.h"
38	#include "setup.h"
39	#include "sparse-index.h"
40	#include "strvec.h"
41	#include "trace2.h"
42	#include "commit-reach.h"
43	#include "commit-graph.h"
44	#include "prio-queue.h"
45	#include "hashmap.h"
46	#include "utf8.h"
47	#include "bloom.h"
48	#include "json-writer.h"
49	#include "list-objects-filter-options.h"
50	#include "resolve-undo.h"
51	#include "parse-options.h"
52	#include "wildmatch.h"
53
54	static char *term_bad;
55	static char *term_good;
56
57	implement_shared_commit_slab(revision_sources, char *);
58
59	static inline int want_ancestry(const struct rev_info *revs);
60
61	static void mark_blob_uninteresting(struct blob *blob)
62	{
63	if (!blob)
64	return;
65	if (blob->object.flags & UNINTERESTING)
66	return;
67	blob->object.flags \|= UNINTERESTING;
68	}
69
70	static void mark_tree_contents_uninteresting(struct repository *r,
71	struct tree *tree)
72	{
73	struct tree_desc desc;
74	struct name_entry entry;
75
76	if (repo_parse_tree_gently(the_repository, tree, 1) < 0)
77	return;
78
79	init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);
80	while (tree_entry(&desc, &entry)) {
81	switch (object_type(entry.mode)) {
82	case OBJ_TREE:
83	mark_tree_uninteresting(r, lookup_tree(r, &entry.oid));
84	break;
85	case OBJ_BLOB:
86	mark_blob_uninteresting(lookup_blob(r, &entry.oid));
87	break;
88	default:
89	/* Subproject commit - not in this repository */
90	break;
91	}
92	}
93
94	/*
95	* We don't care about the tree any more
96	* after it has been marked uninteresting.
97	*/
98	free_tree_buffer(tree);
99	}
100
101	void mark_tree_uninteresting(struct repository r, struct tree tree)
102	{
103	struct object *obj;
104
105	if (!tree)
106	return;
107
108	obj = &tree->object;
109	if (obj->flags & UNINTERESTING)
110	return;
111	obj->flags \|= UNINTERESTING;
112	mark_tree_contents_uninteresting(r, tree);
113	}
114
115	struct path_and_oids_entry {
116	struct hashmap_entry ent;
117	char *path;
118	struct oidset trees;
119	};
120
121	static int path_and_oids_cmp(const void *hashmap_cmp_fn_data UNUSED,
122	const struct hashmap_entry *eptr,
123	const struct hashmap_entry *entry_or_key,
124	const void *keydata UNUSED)
125	{
126	const struct path_and_oids_entry e1, e2;
127
128	e1 = container_of(eptr, const struct path_and_oids_entry, ent);
129	e2 = container_of(entry_or_key, const struct path_and_oids_entry, ent);
130
131	return strcmp(e1->path, e2->path);
132	}
133
134	static void paths_and_oids_clear(struct hashmap *map)
135	{
136	struct hashmap_iter iter;
137	struct path_and_oids_entry *entry;
138
139	hashmap_for_each_entry(map, &iter, entry, ent /* member name */) {
140	oidset_clear(&entry->trees);
141	free(entry->path);
142	}
143
144	hashmap_clear_and_free(map, struct path_and_oids_entry, ent);
145	}
146
147	static void paths_and_oids_insert(struct hashmap *map,
148	const char *path,
149	const struct object_id *oid)
150	{
151	int hash = strhash(path);
152	struct path_and_oids_entry key;
153	struct path_and_oids_entry *entry;
154
155	hashmap_entry_init(&key.ent, hash);
156
157	/* use a shallow copy for the lookup */
158	key.path = (char *)path;
159	oidset_init(&key.trees, 0);
160
161	entry = hashmap_get_entry(map, &key, ent, NULL);
162	if (!entry) {
163	CALLOC_ARRAY(entry, 1);
164	hashmap_entry_init(&entry->ent, hash);
165	entry->path = xstrdup(key.path);
166	oidset_init(&entry->trees, 16);
167	hashmap_put(map, &entry->ent);
168	}
169
170	oidset_insert(&entry->trees, oid);
171	}
172
173	static void add_children_by_path(struct repository *r,
174	struct tree *tree,
175	struct hashmap *map)
176	{
177	struct tree_desc desc;
178	struct name_entry entry;
179
180	if (!tree)
181	return;
182
183	if (repo_parse_tree_gently(the_repository, tree, 1) < 0)
184	return;
185
186	init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);
187	while (tree_entry(&desc, &entry)) {
188	switch (object_type(entry.mode)) {
189	case OBJ_TREE:
190	paths_and_oids_insert(map, entry.path, &entry.oid);
191
192	if (tree->object.flags & UNINTERESTING) {
193	struct tree *child = lookup_tree(r, &entry.oid);
194	if (child)
195	child->object.flags \|= UNINTERESTING;
196	}
197	break;
198	case OBJ_BLOB:
199	if (tree->object.flags & UNINTERESTING) {
200	struct blob *child = lookup_blob(r, &entry.oid);
201	if (child)
202	child->object.flags \|= UNINTERESTING;
203	}
204	break;
205	default:
206	/* Subproject commit - not in this repository */
207	break;
208	}
209	}
210
211	free_tree_buffer(tree);
212	}
213
214	void mark_trees_uninteresting_sparse(struct repository *r,
215	struct oidset *trees)
216	{
217	unsigned has_interesting = 0, has_uninteresting = 0;
218	struct hashmap map = HASHMAP_INIT(path_and_oids_cmp, NULL);
219	struct hashmap_iter map_iter;
220	struct path_and_oids_entry *entry;
221	struct object_id *oid;
222	struct oidset_iter iter;
223
224	oidset_iter_init(trees, &iter);
225	while ((!has_interesting \|\| !has_uninteresting) &&
226	(oid = oidset_iter_next(&iter))) {
227	struct tree *tree = lookup_tree(r, oid);
228
229	if (!tree)
230	continue;
231
232	if (tree->object.flags & UNINTERESTING)
233	has_uninteresting = 1;
234	else
235	has_interesting = 1;
236	}
237
238	/* Do not walk unless we have both types of trees. */
239	if (!has_uninteresting \|\| !has_interesting)
240	return;
241
242	oidset_iter_init(trees, &iter);
243	while ((oid = oidset_iter_next(&iter))) {
244	struct tree *tree = lookup_tree(r, oid);
245	add_children_by_path(r, tree, &map);
246	}
247
248	hashmap_for_each_entry(&map, &map_iter, entry, ent /* member name */)
249	mark_trees_uninteresting_sparse(r, &entry->trees);
250
251	paths_and_oids_clear(&map);
252	}
253
254	static void mark_one_parent_uninteresting(struct rev_info revs, struct commit commit,
255	struct commit_stack *pending)
256	{
257	struct commit_list *l;
258
259	if (commit->object.flags & UNINTERESTING)
260	return;
261	commit->object.flags \|= UNINTERESTING;
262
263	/*
264	* Normally we haven't parsed the parent
265	* yet, so we won't have a parent of a parent
266	* here. However, it may turn out that we've
267	* reached this commit some other way (where it
268	* wasn't uninteresting), in which case we need
269	* to mark its parents recursively too..
270	*/
271	for (l = commit->parents; l; l = l->next) {
272	commit_stack_push(pending, l->item);
273	if (revs && revs->exclude_first_parent_only)
274	break;
275	}
276	}
277
278	void mark_parents_uninteresting(struct rev_info revs, struct commit commit)
279	{
280	struct commit_stack pending = COMMIT_STACK_INIT;
281	struct commit_list *l;
282
283	for (l = commit->parents; l; l = l->next) {
284	mark_one_parent_uninteresting(revs, l->item, &pending);
285	if (revs && revs->exclude_first_parent_only)
286	break;
287	}
288
289	while (pending.nr > 0)
290	mark_one_parent_uninteresting(revs, commit_stack_pop(&pending),
291	&pending);
292
293	commit_stack_clear(&pending);
294	}
295
296	static void add_pending_object_with_path(struct rev_info *revs,
297	struct object *obj,
298	const char *name, unsigned mode,
299	const char *path)
300	{
301	struct interpret_branch_name_options options = { 0 };
302	if (!obj)
303	return;
304	if (revs->no_walk && (obj->flags & UNINTERESTING))
305	revs->no_walk = 0;
306	if (revs->reflog_info && obj->type == OBJ_COMMIT) {
307	struct strbuf buf = STRBUF_INIT;
308	size_t namelen = strlen(name);
309	int len = repo_interpret_branch_name(the_repository, name,
310	namelen, &buf, &options);
311
312	if (0 < len && len < namelen && buf.len)
313	strbuf_addstr(&buf, name + len);
314	add_reflog_for_walk(revs->reflog_info,
315	(struct commit *)obj,
316	buf.buf[0] ? buf.buf: name);
317	strbuf_release(&buf);
318	return; /* do not add the commit itself */
319	}
320	add_object_array_with_path(obj, name, &revs->pending, mode, path);
321	}
322
323	static void add_pending_object_with_mode(struct rev_info *revs,
324	struct object *obj,
325	const char *name, unsigned mode)
326	{
327	add_pending_object_with_path(revs, obj, name, mode, NULL);
328	}
329
330	void add_pending_object(struct rev_info *revs,
331	struct object obj, const char name)
332	{
333	add_pending_object_with_mode(revs, obj, name, S_IFINVALID);
334	}
335
336	void add_head_to_pending(struct rev_info *revs)
337	{
338	struct object_id oid;
339	struct object *obj;
340	if (repo_get_oid(the_repository, "HEAD", &oid))
341	return;
342	obj = parse_object(revs->repo, &oid);
343	if (!obj)
344	return;
345	add_pending_object(revs, obj, "HEAD");
346	}
347
348	static struct object get_reference(struct rev_info revs, const char *name,
349	const struct object_id *oid,
350	unsigned int flags)
351	{
352	struct object *object;
353
354	object = parse_object_with_flags(revs->repo, oid,
355	revs->verify_objects ? 0 :
356	PARSE_OBJECT_SKIP_HASH_CHECK \|
357	PARSE_OBJECT_DISCARD_TREE);
358
359	if (!object) {
360	if (revs->ignore_missing)
361	return NULL;
362	if (revs->exclude_promisor_objects &&
363	is_promisor_object(revs->repo, oid))
364	return NULL;
365	if (revs->do_not_die_on_missing_objects) {
366	oidset_insert(&revs->missing_commits, oid);
367	return NULL;
368	}
369	die("bad object %s", name);
370	}
371	object->flags \|= flags;
372	return object;
373	}
374
375	void add_pending_oid(struct rev_info revs, const char name,
376	const struct object_id *oid, unsigned int flags)
377	{
378	struct object *object = get_reference(revs, name, oid, flags);
379	add_pending_object(revs, object, name);
380	}
381
382	static struct commit handle_commit(struct rev_info revs,
383	struct object_array_entry *entry)
384	{
385	struct object *object = entry->item;
386	const char *name = entry->name;
387	const char *path = entry->path;
388	unsigned int mode = entry->mode;
389	unsigned long flags = object->flags;
390
391	/*
392	* Tag object? Look what it points to..
393	*/
394	while (object->type == OBJ_TAG) {
395	struct tag tag = (struct tag ) object;
396	struct object_id *oid;
397	if (revs->tag_objects && !(flags & UNINTERESTING))
398	add_pending_object(revs, object, tag->tag);
399	oid = get_tagged_oid(tag);
400	object = parse_object(revs->repo, oid);
401	if (!object) {
402	if (revs->ignore_missing_links \|\| (flags & UNINTERESTING))
403	return NULL;
404	if (revs->exclude_promisor_objects &&
405	is_promisor_object(revs->repo, &tag->tagged->oid))
406	return NULL;
407	if (revs->do_not_die_on_missing_objects && oid) {
408	oidset_insert(&revs->missing_commits, oid);
409	return NULL;
410	}
411	die("bad object %s", oid_to_hex(&tag->tagged->oid));
412	}
413	object->flags \|= flags;
414	/*
415	* We'll handle the tagged object by looping or dropping
416	* through to the non-tag handlers below. Do not
417	* propagate path data from the tag's pending entry.
418	*/
419	path = NULL;
420	mode = 0;
421	}
422
423	/*
424	* Commit object? Just return it, we'll do all the complex
425	* reachability crud.
426	*/
427	if (object->type == OBJ_COMMIT) {
428	struct commit commit = (struct commit )object;
429
430	if (repo_parse_commit(revs->repo, commit) < 0)
431	die("unable to parse commit %s", name);
432	if (flags & UNINTERESTING) {
433	mark_parents_uninteresting(revs, commit);
434
435	if (!revs->topo_order \|\| !generation_numbers_enabled(the_repository))
436	revs->limited = 1;
437	}
438	if (revs->sources) {
439	char **slot = revision_sources_at(revs->sources, commit);
440
441	if (!*slot)
442	*slot = xstrdup(name);
443	}
444	return commit;
445	}
446
447	/*
448	* Tree object? Either mark it uninteresting, or add it
449	* to the list of objects to look at later..
450	*/
451	if (object->type == OBJ_TREE) {
452	struct tree tree = (struct tree )object;
453	if (!revs->tree_objects)
454	return NULL;
455	if (flags & UNINTERESTING) {
456	mark_tree_contents_uninteresting(revs->repo, tree);
457	return NULL;
458	}
459	add_pending_object_with_path(revs, object, name, mode, path);
460	return NULL;
461	}
462
463	/*
464	* Blob object? You know the drill by now..
465	*/
466	if (object->type == OBJ_BLOB) {
467	if (!revs->blob_objects)
468	return NULL;
469	if (flags & UNINTERESTING)
470	return NULL;
471	add_pending_object_with_path(revs, object, name, mode, path);
472	return NULL;
473	}
474	die("%s is unknown object", name);
475	}
476
477	static int everybody_uninteresting(struct prio_queue *orig,
478	struct commit **interesting_cache)
479	{
480	struct commit *commit;
481
482	if (*interesting_cache) {
483	commit = *interesting_cache;
484	if (!(commit->object.flags & UNINTERESTING))
485	return 0;
486	}
487
488	prio_queue_for_each(orig, commit) {
489	if (commit->object.flags & UNINTERESTING)
490	continue;
491
492	*interesting_cache = commit;
493	return 0;
494	}
495	return 1;
496	}
497
498	/*
499	* A definition of "relevant" commit that we can use to simplify limited graphs
500	* by eliminating side branches.
501	*
502	* A "relevant" commit is one that is !UNINTERESTING (ie we are including it
503	* in our list), or that is a specified BOTTOM commit. Then after computing
504	* a limited list, during processing we can generally ignore boundary merges
505	* coming from outside the graph, (ie from irrelevant parents), and treat
506	* those merges as if they were single-parent. TREESAME is defined to consider
507	* only relevant parents, if any. If we are TREESAME to our on-graph parents,
508	* we don't care if we were !TREESAME to non-graph parents.
509	*
510	* Treating bottom commits as relevant ensures that a limited graph's
511	* connection to the actual bottom commit is not viewed as a side branch, but
512	* treated as part of the graph. For example:
513	*
514	* ....Z...A---X---o---o---B
515	* . /
516	* W---Y
517	*
518	* When computing "A..B", the A-X connection is at least as important as
519	* Y-X, despite A being flagged UNINTERESTING.
520	*
521	* And when computing --ancestry-path "A..B", the A-X connection is more
522	* important than Y-X, despite both A and Y being flagged UNINTERESTING.
523	*/
524	static inline int relevant_commit(struct commit *commit)
525	{
526	return (commit->object.flags & (UNINTERESTING \| BOTTOM)) != UNINTERESTING;
527	}
528
529	/*
530	* Return a single relevant commit from a parent list. If we are a TREESAME
531	* commit, and this selects one of our parents, then we can safely simplify to
532	* that parent.
533	*/
534	static struct commit one_relevant_parent(const struct rev_info revs,
535	struct commit_list *orig)
536	{
537	struct commit_list *list = orig;
538	struct commit *relevant = NULL;
539
540	if (!orig)
541	return NULL;
542
543	/*
544	* For 1-parent commits, or if first-parent-only, then return that
545	* first parent (even if not "relevant" by the above definition).
546	* TREESAME will have been set purely on that parent.
547	*/
548	if (revs->first_parent_only \|\| !orig->next)
549	return orig->item;
550
551	/*
552	* For multi-parent commits, identify a sole relevant parent, if any.
553	* If we have only one relevant parent, then TREESAME will be set purely
554	* with regard to that parent, and we can simplify accordingly.
555	*
556	* If we have more than one relevant parent, or no relevant parents
557	* (and multiple irrelevant ones), then we can't select a parent here
558	* and return NULL.
559	*/
560	while (list) {
561	struct commit *commit = list->item;
562	list = list->next;
563	if (relevant_commit(commit)) {
564	if (relevant)
565	return NULL;
566	relevant = commit;
567	}
568	}
569	return relevant;
570	}
571
572	/*
573	* The goal is to get REV_TREE_NEW as the result only if the
574	* diff consists of all '+' (and no other changes), REV_TREE_OLD
575	* if the whole diff is removal of old data, and otherwise
576	* REV_TREE_DIFFERENT (of course if the trees are the same we
577	* want REV_TREE_SAME).
578	*
579	* The only time we care about the distinction is when
580	* remove_empty_trees is in effect, in which case we care only about
581	* whether the whole change is REV_TREE_NEW, or if there's another type
582	* of change. Which means we can stop the diff early in either of these
583	* cases:
584	*
585	* 1. We're not using remove_empty_trees at all.
586	*
587	* 2. We saw anything except REV_TREE_NEW.
588	*/
589	#define REV_TREE_SAME 0
590	#define REV_TREE_NEW 1 /* Only new files */
591	#define REV_TREE_OLD 2 /* Only files removed */
592	#define REV_TREE_DIFFERENT 3 /* Mixed changes */
593	static int tree_difference = REV_TREE_SAME;
594
595	static void file_add_remove(struct diff_options *options,
596	int addremove,
597	unsigned mode UNUSED,
598	const struct object_id *oid UNUSED,
599	int oid_valid UNUSED,
600	const char *fullpath UNUSED,
601	unsigned dirty_submodule UNUSED)
602	{
603	int diff = addremove == '+' ? REV_TREE_NEW : REV_TREE_OLD;
604	struct rev_info *revs = options->change_fn_data;
605
606	tree_difference \|= diff;
607	if (!revs->remove_empty_trees \|\| tree_difference != REV_TREE_NEW)
608	options->flags.has_changes = 1;
609	}
610
611	static void file_change(struct diff_options *options,
612	unsigned old_mode UNUSED,
613	unsigned new_mode UNUSED,
614	const struct object_id *old_oid UNUSED,
615	const struct object_id *new_oid UNUSED,
616	int old_oid_valid UNUSED,
617	int new_oid_valid UNUSED,
618	const char *fullpath UNUSED,
619	unsigned old_dirty_submodule UNUSED,
620	unsigned new_dirty_submodule UNUSED)
621	{
622	tree_difference = REV_TREE_DIFFERENT;
623	options->flags.has_changes = 1;
624	}
625
626	static int bloom_filter_atexit_registered;
627	static unsigned int count_bloom_filter_maybe;
628	static unsigned int count_bloom_filter_definitely_not;
629	static unsigned int count_bloom_filter_false_positive;
630	static unsigned int count_bloom_filter_not_present;
631
632	static void trace2_bloom_filter_statistics_atexit(void)
633	{
634	struct json_writer jw = JSON_WRITER_INIT;
635
636	jw_object_begin(&jw, 0);
637	jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
638	jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
639	jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
640	jw_object_intmax(&jw, "false_positive", count_bloom_filter_false_positive);
641	jw_end(&jw);
642
643	trace2_data_json("bloom", the_repository, "statistics", &jw);
644
645	jw_release(&jw);
646	}
647
648	static int forbid_bloom_filters(struct pathspec *spec)
649	{
650	unsigned int allowed_magic =
651	PATHSPEC_FROMTOP \|
652	PATHSPEC_MAXDEPTH \|
653	PATHSPEC_LITERAL \|
654	PATHSPEC_GLOB \|
655	PATHSPEC_ATTR;
656
657	if (spec->magic & ~allowed_magic)
658	return 1;
659	for (size_t nr = 0; nr < spec->nr; nr++)
660	if (spec->items[nr].magic & ~allowed_magic)
661	return 1;
662
663	return 0;
664	}
665
666	static void release_revisions_bloom_keyvecs(struct rev_info *revs);
667
668	static int convert_pathspec_to_bloom_keyvec(struct bloom_keyvec **out,
669	const struct pathspec_item *pi,
670	const struct bloom_filter_settings *settings)
671	{
672	char *path_alloc = NULL;
673	const char *path;
674	size_t len;
675	int res = -1;
676
677	len = pi->nowildcard_len;
678	if (len != pi->len) {
679	/*
680	* for path like "dir/file*", nowildcard part would be
681	* "dir/file", but only "dir" should be used for the
682	* bloom filter.
683	*/
684	while (len > 0 && pi->match[len - 1] != '/')
685	len--;
686	}
687	/* remove single trailing slash from path, if needed */
688	if (len > 0 && pi->match[len - 1] == '/')
689	len--;
690
691	if (!len)
692	goto cleanup;
693
694	if (len != pi->len) {
695	path_alloc = xmemdupz(pi->match, len);
696	path = path_alloc;
697	} else
698	path = pi->match;
699
700	*out = bloom_keyvec_new(path, len, settings);
701
702	res = 0;
703	cleanup:
704	free(path_alloc);
705	return res;
706	}
707
708	static void prepare_to_use_bloom_filter(struct rev_info *revs)
709	{
710	release_revisions_bloom_keyvecs(revs);
711
712	if (!revs->commits)
713	return;
714
715	if (forbid_bloom_filters(&revs->prune_data))
716	return;
717
718	repo_parse_commit(revs->repo, revs->commits->item);
719
720	revs->bloom_filter_settings = get_bloom_filter_settings(revs->repo);
721	if (!revs->bloom_filter_settings)
722	return;
723
724	if (!revs->pruning.pathspec.nr)
725	return;
726
727	revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr;
728	CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr);
729
730	for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
731	if (convert_pathspec_to_bloom_keyvec(&revs->bloom_keyvecs[i],
732	&revs->pruning.pathspec.items[i],
733	revs->bloom_filter_settings))
734	goto fail;
735	}
736
737	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
738	atexit(trace2_bloom_filter_statistics_atexit);
739	bloom_filter_atexit_registered = 1;
740	}
741
742	return;
743
744	fail:
745	revs->bloom_filter_settings = NULL;
746	release_revisions_bloom_keyvecs(revs);
747	}
748
749	static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
750	struct commit *commit)
751	{
752	struct bloom_filter *filter;
753	int result = 0;
754
755	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
756	return -1;
757
758	filter = get_bloom_filter(revs->repo, commit);
759
760	if (!filter) {
761	count_bloom_filter_not_present++;
762	return -1;
763	}
764
765	for (size_t nr = 0; !result && nr < revs->bloom_keyvecs_nr; nr++) {
766	result = bloom_filter_contains_vec(filter,
767	revs->bloom_keyvecs[nr],
768	revs->bloom_filter_settings);
769	}
770
771	if (result)
772	count_bloom_filter_maybe++;
773	else
774	count_bloom_filter_definitely_not++;
775
776	return result;
777	}
778
779	static int rev_compare_tree(struct rev_info *revs,
780	struct commit parent, struct commit commit, int nth_parent)
781	{
782	struct tree *t1 = repo_get_commit_tree(the_repository, parent);
783	struct tree *t2 = repo_get_commit_tree(the_repository, commit);
784	int bloom_ret = 1;
785
786	if (!t1)
787	return REV_TREE_NEW;
788	if (!t2)
789	return REV_TREE_OLD;
790
791	if (revs->simplify_by_decoration) {
792	/*
793	* If we are simplifying by decoration, then the commit
794	* is worth showing if it has a tag pointing at it.
795	*/
796	if (get_name_decoration(&commit->object))
797	return REV_TREE_DIFFERENT;
798	/*
799	* A commit that is not pointed by a tag is uninteresting
800	* if we are not limited by path. This means that you will
801	* see the usual "commits that touch the paths" plus any
802	* tagged commit by specifying both --simplify-by-decoration
803	* and pathspec.
804	*/
805	if (!revs->prune_data.nr)
806	return REV_TREE_SAME;
807	}
808
809	if (revs->bloom_keyvecs_nr && !nth_parent) {
810	bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
811
812	if (bloom_ret == 0)
813	return REV_TREE_SAME;
814	}
815
816	tree_difference = REV_TREE_SAME;
817	revs->pruning.flags.has_changes = 0;
818	diff_tree_oid(&t1->object.oid, &t2->object.oid, "", &revs->pruning);
819
820	if (!nth_parent)
821	if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
822	count_bloom_filter_false_positive++;
823
824	return tree_difference;
825	}
826
827	static int rev_same_tree_as_empty(struct rev_info revs, struct commit commit,
828	int nth_parent)
829	{
830	struct tree *t1 = repo_get_commit_tree(the_repository, commit);
831	int bloom_ret = -1;
832
833	if (!t1)
834	return 0;
835
836	if (!nth_parent && revs->bloom_keyvecs_nr) {
837	bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
838	if (!bloom_ret)
839	return 1;
840	}
841
842	tree_difference = REV_TREE_SAME;
843	revs->pruning.flags.has_changes = 0;
844	diff_tree_oid(NULL, &t1->object.oid, "", &revs->pruning);
845
846	if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
847	count_bloom_filter_false_positive++;
848
849	return tree_difference == REV_TREE_SAME;
850	}
851
852	struct treesame_state {
853	unsigned int nparents;
854	unsigned char treesame[FLEX_ARRAY];
855	};
856
857	static struct treesame_state initialise_treesame(struct rev_info revs, struct commit *commit)
858	{
859	unsigned n = commit_list_count(commit->parents);
860	struct treesame_state st = xcalloc(1, st_add(sizeof(st), n));
861	st->nparents = n;
862	add_decoration(&revs->treesame, &commit->object, st);
863	return st;
864	}
865
866	/*
867	* Must be called immediately after removing the nth_parent from a commit's
868	* parent list, if we are maintaining the per-parent treesame[] decoration.
869	* This does not recalculate the master TREESAME flag - update_treesame()
870	* should be called to update it after a sequence of treesame[] modifications
871	* that may have affected it.
872	*/
873	static int compact_treesame(struct rev_info revs, struct commit commit, unsigned nth_parent)
874	{
875	struct treesame_state *st;
876	int old_same;
877
878	if (!commit->parents) {
879	/*
880	* Have just removed the only parent from a non-merge.
881	* Different handling, as we lack decoration.
882	*/
883	if (nth_parent != 0)
884	die("compact_treesame %u", nth_parent);
885	old_same = !!(commit->object.flags & TREESAME);
886	if (rev_same_tree_as_empty(revs, commit, nth_parent))
887	commit->object.flags \|= TREESAME;
888	else
889	commit->object.flags &= ~TREESAME;
890	return old_same;
891	}
892
893	st = lookup_decoration(&revs->treesame, &commit->object);
894	if (!st \|\| nth_parent >= st->nparents)
895	die("compact_treesame %u", nth_parent);
896
897	old_same = st->treesame[nth_parent];
898	memmove(st->treesame + nth_parent,
899	st->treesame + nth_parent + 1,
900	st->nparents - nth_parent - 1);
901
902	/*
903	* If we've just become a non-merge commit, update TREESAME
904	* immediately, and remove the no-longer-needed decoration.
905	* If still a merge, defer update until update_treesame().
906	*/
907	if (--st->nparents == 1) {
908	if (commit->parents->next)
909	die("compact_treesame parents mismatch");
910	if (st->treesame[0] && revs->dense)
911	commit->object.flags \|= TREESAME;
912	else
913	commit->object.flags &= ~TREESAME;
914	free(add_decoration(&revs->treesame, &commit->object, NULL));
915	}
916
917	return old_same;
918	}
919
920	static unsigned update_treesame(struct rev_info revs, struct commit commit)
921	{
922	if (commit->parents && commit->parents->next) {
923	unsigned n;
924	struct treesame_state *st;
925	struct commit_list *p;
926	unsigned relevant_parents;
927	unsigned relevant_change, irrelevant_change;
928
929	st = lookup_decoration(&revs->treesame, &commit->object);
930	if (!st)
931	die("update_treesame %s", oid_to_hex(&commit->object.oid));
932	relevant_parents = 0;
933	relevant_change = irrelevant_change = 0;
934	for (p = commit->parents, n = 0; p; n++, p = p->next) {
935	if (relevant_commit(p->item)) {
936	relevant_change \|= !st->treesame[n];
937	relevant_parents++;
938	} else
939	irrelevant_change \|= !st->treesame[n];
940	}
941	if (relevant_parents ? relevant_change : irrelevant_change)
942	commit->object.flags &= ~TREESAME;
943	else
944	commit->object.flags \|= TREESAME;
945	}
946
947	return commit->object.flags & TREESAME;
948	}
949
950	static inline int limiting_can_increase_treesame(const struct rev_info *revs)
951	{
952	/*
953	* TREESAME is irrelevant unless prune && dense;
954	* if simplify_history is set, we can't have a mixture of TREESAME and
955	* !TREESAME INTERESTING parents (and we don't have treesame[]
956	* decoration anyway);
957	* if first_parent_only is set, then the TREESAME flag is locked
958	* against the first parent (and again we lack treesame[] decoration).
959	*/
960	return revs->prune && revs->dense &&
961	!revs->simplify_history &&
962	!revs->first_parent_only;
963	}
964
965	static void try_to_simplify_commit(struct rev_info revs, struct commit commit)
966	{
967	struct commit_list *pp, parent;
968	struct treesame_state *ts = NULL;
969	int relevant_change = 0, irrelevant_change = 0;
970	int relevant_parents, nth_parent;
971
972	/*
973	* If we don't do pruning, everything is interesting
974	*/
975	if (!revs->prune)
976	return;
977
978	if (!repo_get_commit_tree(the_repository, commit))
979	return;
980
981	if (!commit->parents) {
982	/*
983	* Pretend as if we are comparing ourselves to the
984	* (non-existent) first parent of this commit object. Even
985	* though no such parent exists, its changed-path Bloom filter
986	* (if one exists) is relative to the empty tree, using Bloom
987	* filters is allowed here.
988	*/
989	if (rev_same_tree_as_empty(revs, commit, 0))
990	commit->object.flags \|= TREESAME;
991	return;
992	}
993
994	/*
995	* Normal non-merge commit? If we don't want to make the
996	* history dense, we consider it always to be a change..
997	*/
998	if (!revs->dense && !commit->parents->next)
999	return;
1000
1001	for (pp = &commit->parents, nth_parent = 0, relevant_parents = 0;
1002	(parent = *pp) != NULL;
1003	pp = &parent->next, nth_parent++) {
1004	struct commit *p = parent->item;
1005	if (relevant_commit(p))
1006	relevant_parents++;
1007
1008	if (nth_parent == 1) {
1009	/*
1010	* This our second loop iteration - so we now know
1011	* we're dealing with a merge.
1012	*
1013	* Do not compare with later parents when we care only about
1014	* the first parent chain, in order to avoid derailing the
1015	* traversal to follow a side branch that brought everything
1016	* in the path we are limited to by the pathspec.
1017	*/
1018	if (revs->first_parent_only)
1019	break;
1020	/*
1021	* If this will remain a potentially-simplifiable
1022	* merge, remember per-parent treesame if needed.
1023	* Initialise the array with the comparison from our
1024	* first iteration.
1025	*/
1026	if (revs->treesame.name &&
1027	!revs->simplify_history &&
1028	!(commit->object.flags & UNINTERESTING)) {
1029	ts = initialise_treesame(revs, commit);
1030	if (!(irrelevant_change \|\| relevant_change))
1031	ts->treesame[0] = 1;
1032	}
1033	}
1034	if (repo_parse_commit(revs->repo, p) < 0)
1035	die("cannot simplify commit %s (because of %s)",
1036	oid_to_hex(&commit->object.oid),
1037	oid_to_hex(&p->object.oid));
1038	switch (rev_compare_tree(revs, p, commit, nth_parent)) {
1039	case REV_TREE_SAME:
1040	if (!revs->simplify_history \|\| !relevant_commit(p)) {
1041	/* Even if a merge with an uninteresting
1042	* side branch brought the entire change
1043	* we are interested in, we do not want
1044	* to lose the other branches of this
1045	* merge, so we just keep going.
1046	*/
1047	if (ts)
1048	ts->treesame[nth_parent] = 1;
1049	continue;
1050	}
1051
1052	commit_list_free(parent->next);
1053	parent->next = NULL;
1054	while (commit->parents != parent)
1055	pop_commit(&commit->parents);
1056	commit->parents = parent;
1057
1058	/*
1059	* A merge commit is a "diversion" if it is not
1060	* TREESAME to its first parent but is TREESAME
1061	* to a later parent. In the simplified history,
1062	* we "divert" the history walk to the later
1063	* parent. These commits are shown when "show_pulls"
1064	* is enabled, so do not mark the object as
1065	* TREESAME here.
1066	*/
1067	if (!revs->show_pulls \|\| !nth_parent)
1068	commit->object.flags \|= TREESAME;
1069
1070	return;
1071
1072	case REV_TREE_NEW:
1073	if (revs->remove_empty_trees &&
1074	rev_same_tree_as_empty(revs, p, nth_parent)) {
1075	/* We are adding all the specified
1076	* paths from this parent, so the
1077	* history beyond this parent is not
1078	* interesting. Remove its parents
1079	* (they are grandparents for us).
1080	* IOW, we pretend this parent is a
1081	* "root" commit.
1082	*/
1083	if (repo_parse_commit(revs->repo, p) < 0)
1084	die("cannot simplify commit %s (invalid %s)",
1085	oid_to_hex(&commit->object.oid),
1086	oid_to_hex(&p->object.oid));
1087	commit_list_free(p->parents);
1088	p->parents = NULL;
1089	}
1090	/* fallthrough */
1091	case REV_TREE_OLD:
1092	case REV_TREE_DIFFERENT:
1093	if (relevant_commit(p))
1094	relevant_change = 1;
1095	else
1096	irrelevant_change = 1;
1097
1098	if (!nth_parent)
1099	commit->object.flags \|= PULL_MERGE;
1100
1101	continue;
1102	}
1103	die("bad tree compare for commit %s", oid_to_hex(&commit->object.oid));
1104	}
1105
1106	/*
1107	* TREESAME is straightforward for single-parent commits. For merge
1108	* commits, it is most useful to define it so that "irrelevant"
1109	* parents cannot make us !TREESAME - if we have any relevant
1110	* parents, then we only consider TREESAMEness with respect to them,
1111	* allowing irrelevant merges from uninteresting branches to be
1112	* simplified away. Only if we have only irrelevant parents do we
1113	* base TREESAME on them. Note that this logic is replicated in
1114	* update_treesame, which should be kept in sync.
1115	*/
1116	if (relevant_parents ? !relevant_change : !irrelevant_change)
1117	commit->object.flags \|= TREESAME;
1118	}
1119
1120	static int process_parents(struct rev_info revs, struct commit commit,
1121	struct prio_queue *queue)
1122	{
1123	struct commit_list *parent = commit->parents;
1124	unsigned pass_flags;
1125
1126	if (commit->object.flags & ADDED)
1127	return 0;
1128	if (revs->do_not_die_on_missing_objects &&
1129	oidset_contains(&revs->missing_commits, &commit->object.oid))
1130	return 0;
1131	commit->object.flags \|= ADDED;
1132
1133	if (revs->include_check &&
1134	!revs->include_check(commit, revs->include_check_data))
1135	return 0;
1136
1137	/*
1138	* If the commit is uninteresting, don't try to
1139	* prune parents - we want the maximal uninteresting
1140	* set.
1141	*
1142	* Normally we haven't parsed the parent
1143	* yet, so we won't have a parent of a parent
1144	* here. However, it may turn out that we've
1145	* reached this commit some other way (where it
1146	* wasn't uninteresting), in which case we need
1147	* to mark its parents recursively too..
1148	*/
1149	if (commit->object.flags & UNINTERESTING) {
1150	while (parent) {
1151	struct commit *p = parent->item;
1152	parent = parent->next;
1153	if (p)
1154	p->object.flags \|= UNINTERESTING \|
1155	CHILD_VISITED;
1156	if (repo_parse_commit_gently(revs->repo, p, 1) < 0) {
1157	if (revs->exclude_first_parent_only)
1158	break;
1159	continue;
1160	}
1161	if (p->parents)
1162	mark_parents_uninteresting(revs, p);
1163	if (p->object.flags & SEEN) {
1164	if (revs->exclude_first_parent_only)
1165	break;
1166	continue;
1167	}
1168	p->object.flags \|= (SEEN \| NOT_USER_GIVEN);
1169	if (queue)
1170	prio_queue_put(queue, p);
1171	if (revs->exclude_first_parent_only)
1172	break;
1173	}
1174	return 0;
1175	}
1176
1177	/*
1178	* Ok, the commit wasn't uninteresting. Try to
1179	* simplify the commit history and find the parent
1180	* that has no differences in the path set if one exists.
1181	*/
1182	try_to_simplify_commit(revs, commit);
1183
1184	if (revs->no_walk)
1185	return 0;
1186
1187	pass_flags = (commit->object.flags & (SYMMETRIC_LEFT \| ANCESTRY_PATH));
1188
1189	for (parent = commit->parents; parent; parent = parent->next) {
1190	struct commit *p = parent->item;
1191	int gently = revs->ignore_missing_links \|\|
1192	revs->exclude_promisor_objects \|\|
1193	revs->do_not_die_on_missing_objects;
1194	if (repo_parse_commit_gently(revs->repo, p, gently) < 0) {
1195	if (revs->exclude_promisor_objects &&
1196	is_promisor_object(revs->repo, &p->object.oid)) {
1197	if (revs->first_parent_only)
1198	break;
1199	continue;
1200	}
1201
1202	if (revs->do_not_die_on_missing_objects)
1203	oidset_insert(&revs->missing_commits, &p->object.oid);
1204	else
1205	return -1; /* corrupt repository */
1206	}
1207	if (revs->sources) {
1208	char **slot = revision_sources_at(revs->sources, p);
1209
1210	if (!*slot)
1211	slot = revision_sources_at(revs->sources, commit);
1212	}
1213	p->object.flags \|= pass_flags \| CHILD_VISITED;
1214	if (!(p->object.flags & SEEN)) {
1215	p->object.flags \|= (SEEN \| NOT_USER_GIVEN);
1216	if (queue)
1217	prio_queue_put(queue, p);
1218	}
1219	if (revs->first_parent_only)
1220	break;
1221	}
1222	return 0;
1223	}
1224
1225	static void cherry_pick_list(struct commit_list list, struct rev_info revs)
1226	{
1227	struct commit_list *p;
1228	int left_count = 0, right_count = 0;
1229	int left_first;
1230	struct patch_ids ids;
1231	unsigned cherry_flag;
1232
1233	/* First count the commits on the left and on the right */
1234	for (p = list; p; p = p->next) {
1235	struct commit *commit = p->item;
1236	unsigned flags = commit->object.flags;
1237	if (flags & BOUNDARY)
1238	;
1239	else if (flags & SYMMETRIC_LEFT)
1240	left_count++;
1241	else
1242	right_count++;
1243	}
1244
1245	if (!left_count \|\| !right_count)
1246	return;
1247
1248	left_first = left_count < right_count;
1249	init_patch_ids(revs->repo, &ids);
1250	ids.diffopts.pathspec = revs->diffopt.pathspec;
1251
1252	/* Compute patch-ids for one side */
1253	for (p = list; p; p = p->next) {
1254	struct commit *commit = p->item;
1255	unsigned flags = commit->object.flags;
1256
1257	if (flags & BOUNDARY)
1258	continue;
1259	/*
1260	* If we have fewer left, left_first is set and we omit
1261	* commits on the right branch in this loop. If we have
1262	* fewer right, we skip the left ones.
1263	*/
1264	if (left_first != !!(flags & SYMMETRIC_LEFT))
1265	continue;
1266	add_commit_patch_id(commit, &ids);
1267	}
1268
1269	/* either cherry_mark or cherry_pick are true */
1270	cherry_flag = revs->cherry_mark ? PATCHSAME : SHOWN;
1271
1272	/* Check the other side */
1273	for (p = list; p; p = p->next) {
1274	struct commit *commit = p->item;
1275	struct patch_id *id;
1276	unsigned flags = commit->object.flags;
1277
1278	if (flags & BOUNDARY)
1279	continue;
1280	/*
1281	* If we have fewer left, left_first is set and we omit
1282	* commits on the left branch in this loop.
1283	*/
1284	if (left_first == !!(flags & SYMMETRIC_LEFT))
1285	continue;
1286
1287	/*
1288	* Have we seen the same patch id?
1289	*/
1290	id = patch_id_iter_first(commit, &ids);
1291	if (!id)
1292	continue;
1293
1294	commit->object.flags \|= cherry_flag;
1295	do {
1296	id->commit->object.flags \|= cherry_flag;
1297	} while ((id = patch_id_iter_next(id, &ids)));
1298	}
1299
1300	free_patch_ids(&ids);
1301	}
1302
1303	/* How many extra uninteresting commits we want to see.. */
1304	#define SLOP 5
1305
1306	static int still_interesting(struct prio_queue *src, timestamp_t date, int slop,
1307	struct commit **interesting_cache)
1308	{
1309	/*
1310	* Since src is sorted by date, it is enough to peek at the
1311	* first entry to compare dates. No entry at all means done.
1312	*/
1313	struct commit *commit = prio_queue_peek(src);
1314	if (!commit)
1315	return 0;
1316	if (date <= commit->date)
1317	return SLOP;
1318
1319	/*
1320	* Does the source list still have interesting commits in
1321	* it? Definitely not done..
1322	*/
1323	if (!everybody_uninteresting(src, interesting_cache))
1324	return SLOP;
1325
1326	/* Ok, we're closing in.. */
1327	return slop-1;
1328	}
1329
1330	/*
1331	* "rev-list --ancestry-path=C_0 [--ancestry-path=C_1 ...] A..B"
1332	* computes commits that are ancestors of B but not ancestors of A but
1333	* further limits the result to those that have any of C in their
1334	* ancestry path (i.e. are either ancestors of any of C, descendants
1335	* of any of C, or are any of C). If --ancestry-path is specified with
1336	* no commit, we use all bottom commits for C.
1337	*
1338	* Before this function is called, ancestors of C will have already
1339	* been marked with ANCESTRY_PATH previously.
1340	*
1341	* This takes the list of bottom commits and the result of "A..B"
1342	* without --ancestry-path, and limits the latter further to the ones
1343	* that have any of C in their ancestry path. Since the ancestors of C
1344	* have already been marked (a prerequisite of this function), we just
1345	* need to mark the descendants, then exclude any commit that does not
1346	* have any of these marks.
1347	*/
1348	static void limit_to_ancestry(struct commit_list bottoms, struct commit_list list)
1349	{
1350	struct commit_list *p;
1351	struct commit_list *rlist = NULL;
1352	int made_progress;
1353
1354	/*
1355	* Reverse the list so that it will be likely that we would
1356	* process parents before children.
1357	*/
1358	for (p = list; p; p = p->next)
1359	commit_list_insert(p->item, &rlist);
1360
1361	for (p = bottoms; p; p = p->next)
1362	p->item->object.flags \|= TMP_MARK;
1363
1364	/*
1365	* Mark the ones that can reach bottom commits in "list",
1366	* in a bottom-up fashion.
1367	*/
1368	do {
1369	made_progress = 0;
1370	for (p = rlist; p; p = p->next) {
1371	struct commit *c = p->item;
1372	struct commit_list *parents;
1373	if (c->object.flags & (TMP_MARK \| UNINTERESTING))
1374	continue;
1375	for (parents = c->parents;
1376	parents;
1377	parents = parents->next) {
1378	if (!(parents->item->object.flags & TMP_MARK))
1379	continue;
1380	c->object.flags \|= TMP_MARK;
1381	made_progress = 1;
1382	break;
1383	}
1384	}
1385	} while (made_progress);
1386
1387	/*
1388	* NEEDSWORK: decide if we want to remove parents that are
1389	* not marked with TMP_MARK from commit->parents for commits
1390	* in the resulting list. We may not want to do that, though.
1391	*/
1392
1393	/*
1394	* The ones that are not marked with either TMP_MARK or
1395	* ANCESTRY_PATH are uninteresting
1396	*/
1397	for (p = list; p; p = p->next) {
1398	struct commit *c = p->item;
1399	if (c->object.flags & (TMP_MARK \| ANCESTRY_PATH))
1400	continue;
1401	c->object.flags \|= UNINTERESTING;
1402	}
1403
1404	/* We are done with TMP_MARK and ANCESTRY_PATH */
1405	for (p = list; p; p = p->next)
1406	p->item->object.flags &= ~(TMP_MARK \| ANCESTRY_PATH);
1407	for (p = bottoms; p; p = p->next)
1408	p->item->object.flags &= ~(TMP_MARK \| ANCESTRY_PATH);
1409	commit_list_free(rlist);
1410	}
1411
1412	/*
1413	* Before walking the history, add the set of "negative" refs the
1414	* caller has asked to exclude to the bottom list.
1415	*
1416	* This is used to compute "rev-list --ancestry-path A..B", as we need
1417	* to filter the result of "A..B" further to the ones that can actually
1418	* reach A.
1419	*/
1420	static void collect_bottom_commits(struct commit_list *list,
1421	struct commit_list **bottom)
1422	{
1423	struct commit_list *elem;
1424	for (elem = list; elem; elem = elem->next)
1425	if (elem->item->object.flags & BOTTOM)
1426	commit_list_insert(elem->item, bottom);
1427	}
1428
1429	/* Assumes either left_only or right_only is set */
1430	static void limit_left_right(struct commit_list list, struct rev_info revs)
1431	{
1432	struct commit_list *p;
1433
1434	for (p = list; p; p = p->next) {
1435	struct commit *commit = p->item;
1436
1437	if (revs->right_only) {
1438	if (commit->object.flags & SYMMETRIC_LEFT)
1439	commit->object.flags \|= SHOWN;
1440	} else /* revs->left_only is set */
1441	if (!(commit->object.flags & SYMMETRIC_LEFT))
1442	commit->object.flags \|= SHOWN;
1443	}
1444	}
1445
1446	static int limit_list(struct rev_info *revs)
1447	{
1448	int slop = SLOP;
1449	timestamp_t date = TIME_MAX;
1450	struct commit_list *original_list = revs->commits;
1451	struct commit_list *newlist = NULL;
1452	struct commit_list **p = &newlist;
1453	struct commit commit, interesting_cache = NULL;
1454	struct prio_queue queue = { .compare = compare_commits_by_commit_date };
1455
1456	if (revs->ancestry_path_implicit_bottoms) {
1457	collect_bottom_commits(original_list,
1458	&revs->ancestry_path_bottoms);
1459	if (!revs->ancestry_path_bottoms)
1460	die("--ancestry-path given but there are no bottom commits");
1461	}
1462
1463	while (original_list) {
1464	struct commit *commit = pop_commit(&original_list);
1465	prio_queue_put(&queue, commit);
1466	}
1467
1468	while ((commit = prio_queue_get(&queue))) {
1469	struct object *obj = &commit->object;
1470
1471	if (commit == interesting_cache)
1472	interesting_cache = NULL;
1473
1474	if (revs->max_age != -1 && (commit->date < revs->max_age))
1475	obj->flags \|= UNINTERESTING;
1476	if (process_parents(revs, commit, &queue) < 0) {
1477	clear_prio_queue(&queue);
1478	return -1;
1479	}
1480	if (obj->flags & UNINTERESTING) {
1481	mark_parents_uninteresting(revs, commit);
1482	slop = still_interesting(&queue, date, slop, &interesting_cache);
1483	if (slop)
1484	continue;
1485	break;
1486	}
1487	if (revs->min_age != -1 && (commit->date > revs->min_age) &&
1488	!revs->line_level_traverse)
1489	continue;
1490	if (revs->max_age_as_filter != -1 &&
1491	(commit->date < revs->max_age_as_filter) && !revs->line_level_traverse)
1492	continue;
1493	date = commit->date;
1494	p = &commit_list_insert(commit, p)->next;
1495	}
1496	if (revs->cherry_pick \|\| revs->cherry_mark)
1497	cherry_pick_list(newlist, revs);
1498
1499	if (revs->left_only \|\| revs->right_only)
1500	limit_left_right(newlist, revs);
1501
1502	if (revs->ancestry_path)
1503	limit_to_ancestry(revs->ancestry_path_bottoms, newlist);
1504
1505	/*
1506	* Check if any commits have become TREESAME by some of their parents
1507	* becoming UNINTERESTING.
1508	*/
1509	if (limiting_can_increase_treesame(revs)) {
1510	struct commit_list *list = NULL;
1511	for (list = newlist; list; list = list->next) {
1512	struct commit *c = list->item;
1513	if (c->object.flags & (UNINTERESTING \| TREESAME))
1514	continue;
1515	update_treesame(revs, c);
1516	}
1517	}
1518
1519	clear_prio_queue(&queue);
1520	revs->commits = newlist;
1521	return 0;
1522	}
1523
1524	/*
1525	* Add an entry to refs->cmdline with the specified information.
1526	* *name is copied.
1527	*/
1528	static void add_rev_cmdline(struct rev_info *revs,
1529	struct object *item,
1530	const char *name,
1531	int whence,
1532	unsigned flags)
1533	{
1534	struct rev_cmdline_info *info = &revs->cmdline;
1535	unsigned int nr = info->nr;
1536
1537	ALLOC_GROW(info->rev, nr + 1, info->alloc);
1538	info->rev[nr].item = item;
1539	info->rev[nr].name = xstrdup(name);
1540	info->rev[nr].whence = whence;
1541	info->rev[nr].flags = flags;
1542	info->nr++;
1543	}
1544
1545	static void add_rev_cmdline_list(struct rev_info *revs,
1546	struct commit_list *commit_list,
1547	int whence,
1548	unsigned flags)
1549	{
1550	while (commit_list) {
1551	struct object *object = &commit_list->item->object;
1552	add_rev_cmdline(revs, object, oid_to_hex(&object->oid),
1553	whence, flags);
1554	commit_list = commit_list->next;
1555	}
1556	}
1557
1558	int ref_excluded(const struct ref_exclusions exclusions, const char path)
1559	{
1560	const char *stripped_path = strip_namespace(path);
1561	struct string_list_item *item;
1562
1563	for_each_string_list_item(item, &exclusions->excluded_refs) {
1564	if (!wildmatch(item->string, path, 0))
1565	return 1;
1566	}
1567
1568	if (ref_is_hidden(stripped_path, path, &exclusions->hidden_refs))
1569	return 1;
1570
1571	return 0;
1572	}
1573
1574	void init_ref_exclusions(struct ref_exclusions *exclusions)
1575	{
1576	struct ref_exclusions blank = REF_EXCLUSIONS_INIT;
1577	memcpy(exclusions, &blank, sizeof(*exclusions));
1578	}
1579
1580	void clear_ref_exclusions(struct ref_exclusions *exclusions)
1581	{
1582	string_list_clear(&exclusions->excluded_refs, 0);
1583	strvec_clear(&exclusions->hidden_refs);
1584	exclusions->hidden_refs_configured = 0;
1585	}
1586
1587	void add_ref_exclusion(struct ref_exclusions exclusions, const char exclude)
1588	{
1589	string_list_append(&exclusions->excluded_refs, exclude);
1590	}
1591
1592	struct exclude_hidden_refs_cb {
1593	struct ref_exclusions *exclusions;
1594	const char *section;
1595	};
1596
1597	static int hide_refs_config(const char var, const char value,
1598	const struct config_context *ctx UNUSED,
1599	void *cb_data)
1600	{
1601	struct exclude_hidden_refs_cb *cb = cb_data;
1602	cb->exclusions->hidden_refs_configured = 1;
1603	return parse_hide_refs_config(var, value, cb->section,
1604	&cb->exclusions->hidden_refs);
1605	}
1606
1607	void exclude_hidden_refs(struct ref_exclusions exclusions, const char section)
1608	{
1609	struct exclude_hidden_refs_cb cb;
1610
1611	if (strcmp(section, "fetch") && strcmp(section, "receive") &&
1612	strcmp(section, "uploadpack"))
1613	die(_("unsupported section for hidden refs: %s"), section);
1614
1615	if (exclusions->hidden_refs_configured)
1616	die(_("--exclude-hidden= passed more than once"));
1617
1618	cb.exclusions = exclusions;
1619	cb.section = section;
1620
1621	repo_config(the_repository, hide_refs_config, &cb);
1622	}
1623
1624	struct all_refs_cb {
1625	int all_flags;
1626	int warned_bad_reflog;
1627	struct rev_info *all_revs;
1628	const char *name_for_errormsg;
1629	struct worktree *wt;
1630	};
1631
1632	static int handle_one_ref(const struct reference ref, void cb_data)
1633	{
1634	struct all_refs_cb *cb = cb_data;
1635	struct object *object;
1636
1637	if (ref_excluded(&cb->all_revs->ref_excludes, ref->name))
1638	return 0;
1639
1640	object = get_reference(cb->all_revs, ref->name, ref->oid, cb->all_flags);
1641	add_rev_cmdline(cb->all_revs, object, ref->name, REV_CMD_REF, cb->all_flags);
1642	add_pending_object(cb->all_revs, object, ref->name);
1643	return 0;
1644	}
1645
1646	static void init_all_refs_cb(struct all_refs_cb cb, struct rev_info revs,
1647	unsigned flags)
1648	{
1649	cb->all_revs = revs;
1650	cb->all_flags = flags;
1651	revs->rev_input_given = 1;
1652	cb->wt = NULL;
1653	}
1654
1655	static void handle_refs(struct ref_store *refs,
1656	struct rev_info *revs, unsigned flags,
1657	int (for_each)(struct ref_store , refs_for_each_cb, void *))
1658	{
1659	struct all_refs_cb cb;
1660
1661	if (!refs) {
1662	/* this could happen with uninitialized submodules */
1663	return;
1664	}
1665
1666	init_all_refs_cb(&cb, revs, flags);
1667	for_each(refs, handle_one_ref, &cb);
1668	}
1669
1670	static void handle_one_reflog_commit(struct object_id oid, void cb_data)
1671	{
1672	struct all_refs_cb *cb = cb_data;
1673	if (!is_null_oid(oid)) {
1674	struct object *o = parse_object(cb->all_revs->repo, oid);
1675	if (o) {
1676	o->flags \|= cb->all_flags;
1677	/* ??? CMDLINEFLAGS ??? */
1678	add_pending_object(cb->all_revs, o, "");
1679	}
1680	else if (!cb->warned_bad_reflog) {
1681	warning("reflog of '%s' references pruned commits",
1682	cb->name_for_errormsg);
1683	cb->warned_bad_reflog = 1;
1684	}
1685	}
1686	}
1687
1688	static int handle_one_reflog_ent(const char *refname UNUSED,
1689	struct object_id ooid, struct object_id noid,
1690	const char *email UNUSED,
1691	timestamp_t timestamp UNUSED,
1692	int tz UNUSED,
1693	const char *message UNUSED,
1694	void *cb_data)
1695	{
1696	handle_one_reflog_commit(ooid, cb_data);
1697	handle_one_reflog_commit(noid, cb_data);
1698	return 0;
1699	}
1700
1701	static int handle_one_reflog(const char refname_in_wt, void cb_data)
1702	{
1703	struct all_refs_cb *cb = cb_data;
1704	struct strbuf refname = STRBUF_INIT;
1705
1706	cb->warned_bad_reflog = 0;
1707	strbuf_worktree_ref(cb->wt, &refname, refname_in_wt);
1708	cb->name_for_errormsg = refname.buf;
1709	refs_for_each_reflog_ent(get_main_ref_store(the_repository),
1710	refname.buf,
1711	handle_one_reflog_ent, cb_data);
1712	strbuf_release(&refname);
1713	return 0;
1714	}
1715
1716	static void add_other_reflogs_to_pending(struct all_refs_cb *cb)
1717	{
1718	struct worktree worktrees, p;
1719
1720	worktrees = get_worktrees(the_repository);
1721	for (p = worktrees; *p; p++) {
1722	struct worktree wt = p;
1723
1724	if (wt->is_current)
1725	continue;
1726
1727	cb->wt = wt;
1728	refs_for_each_reflog(get_worktree_ref_store(wt),
1729	handle_one_reflog,
1730	cb);
1731	}
1732	free_worktrees(worktrees);
1733	}
1734
1735	void add_reflogs_to_pending(struct rev_info *revs, unsigned flags)
1736	{
1737	struct all_refs_cb cb;
1738
1739	cb.all_revs = revs;
1740	cb.all_flags = flags;
1741	cb.wt = NULL;
1742	refs_for_each_reflog(get_main_ref_store(the_repository),
1743	handle_one_reflog, &cb);
1744
1745	if (!revs->single_worktree)
1746	add_other_reflogs_to_pending(&cb);
1747	}
1748
1749	static void add_cache_tree(struct cache_tree it, struct rev_info revs,
1750	struct strbuf *path, unsigned int flags)
1751	{
1752	size_t baselen = path->len;
1753	int i;
1754
1755	if (it->entry_count >= 0) {
1756	struct tree *tree = lookup_tree(revs->repo, &it->oid);
1757	tree->object.flags \|= flags;
1758	add_pending_object_with_path(revs, &tree->object, "",
1759	040000, path->buf);
1760	}
1761
1762	for (i = 0; i < it->subtree_nr; i++) {
1763	struct cache_tree_sub *sub = it->down[i];
1764	strbuf_addf(path, "%s%s", baselen ? "/" : "", sub->name);
1765	add_cache_tree(sub->cache_tree, revs, path, flags);
1766	strbuf_setlen(path, baselen);
1767	}
1768
1769	}
1770
1771	static void add_resolve_undo_to_pending(struct index_state istate, struct rev_info revs)
1772	{
1773	struct string_list_item *item;
1774	struct string_list *resolve_undo = istate->resolve_undo;
1775
1776	if (!resolve_undo)
1777	return;
1778
1779	for_each_string_list_item(item, resolve_undo) {
1780	const char *path = item->string;
1781	struct resolve_undo_info *ru = item->util;
1782	int i;
1783
1784	if (!ru)
1785	continue;
1786	for (i = 0; i < 3; i++) {
1787	struct blob *blob;
1788
1789	if (!ru->mode[i] \|\| !S_ISREG(ru->mode[i]))
1790	continue;
1791
1792	blob = lookup_blob(revs->repo, &ru->oid[i]);
1793	if (!blob) {
1794	warning(_("resolve-undo records `%s` which is missing"),
1795	oid_to_hex(&ru->oid[i]));
1796	continue;
1797	}
1798	add_pending_object_with_path(revs, &blob->object, "",
1799	ru->mode[i], path);
1800	}
1801	}
1802	}
1803
1804	static void do_add_index_objects_to_pending(struct rev_info *revs,
1805	struct index_state *istate,
1806	unsigned int flags)
1807	{
1808	int i;
1809
1810	/* TODO: audit for interaction with sparse-index. */
1811	ensure_full_index(istate);
1812	for (i = 0; i < istate->cache_nr; i++) {
1813	struct cache_entry *ce = istate->cache[i];
1814	struct blob *blob;
1815
1816	if (S_ISGITLINK(ce->ce_mode))
1817	continue;
1818
1819	blob = lookup_blob(revs->repo, &ce->oid);
1820	if (!blob)
1821	die("unable to add index blob to traversal");
1822	blob->object.flags \|= flags;
1823	add_pending_object_with_path(revs, &blob->object, "",
1824	ce->ce_mode, ce->name);
1825	}
1826
1827	if (istate->cache_tree) {
1828	struct strbuf path = STRBUF_INIT;
1829	add_cache_tree(istate->cache_tree, revs, &path, flags);
1830	strbuf_release(&path);
1831	}
1832
1833	add_resolve_undo_to_pending(istate, revs);
1834	}
1835
1836	void add_index_objects_to_pending(struct rev_info *revs, unsigned int flags)
1837	{
1838	struct worktree worktrees, p;
1839
1840	repo_read_index(revs->repo);
1841	do_add_index_objects_to_pending(revs, revs->repo->index, flags);
1842
1843	if (revs->single_worktree)
1844	return;
1845
1846	worktrees = get_worktrees(the_repository);
1847	for (p = worktrees; *p; p++) {
1848	struct worktree wt = p;
1849	struct index_state istate = INDEX_STATE_INIT(revs->repo);
1850	char *wt_gitdir;
1851
1852	if (wt->is_current)
1853	continue; /* current index already taken care of */
1854
1855	wt_gitdir = get_worktree_git_dir(wt);
1856
1857	if (read_index_from(&istate,
1858	worktree_git_path(wt, "index"),
1859	wt_gitdir) > 0)
1860	do_add_index_objects_to_pending(revs, &istate, flags);
1861
1862	discard_index(&istate);
1863	free(wt_gitdir);
1864	}
1865	free_worktrees(worktrees);
1866	}
1867
1868	struct add_alternate_refs_data {
1869	struct rev_info *revs;
1870	unsigned int flags;
1871	};
1872
1873	static void add_one_alternate_ref(const struct object_id *oid,
1874	void *vdata)
1875	{
1876	const char *name = ".alternate";
1877	struct add_alternate_refs_data *data = vdata;
1878	struct object *obj;
1879
1880	obj = get_reference(data->revs, name, oid, data->flags);
1881	add_rev_cmdline(data->revs, obj, name, REV_CMD_REV, data->flags);
1882	add_pending_object(data->revs, obj, name);
1883	}
1884
1885	static void add_alternate_refs_to_pending(struct rev_info *revs,
1886	unsigned int flags)
1887	{
1888	struct add_alternate_refs_data data;
1889	data.revs = revs;
1890	data.flags = flags;
1891	odb_for_each_alternate_ref(the_repository->objects,
1892	add_one_alternate_ref, &data);
1893	}
1894
1895	static int add_parents_only(struct rev_info revs, const char arg_, int flags,
1896	int exclude_parent)
1897	{
1898	struct object_id oid;
1899	struct object *it;
1900	struct commit *commit;
1901	struct commit_list *parents;
1902	int parent_number;
1903	const char *arg = arg_;
1904
1905	if (*arg == '^') {
1906	flags ^= UNINTERESTING \| BOTTOM;
1907	arg++;
1908	}
1909	if (repo_get_oid_committish(the_repository, arg, &oid))
1910	return 0;
1911	while (1) {
1912	it = get_reference(revs, arg, &oid, 0);
1913	if (!it) {
1914	if (revs->ignore_missing)
1915	return 0;
1916	if (revs->do_not_die_on_missing_objects)
1917	return 0;
1918	return -1;
1919	}
1920	if (it->type != OBJ_TAG)
1921	break;
1922	if (!((struct tag*)it)->tagged)
1923	return 0;
1924	oidcpy(&oid, &((struct tag*)it)->tagged->oid);
1925	}
1926	if (it->type != OBJ_COMMIT)
1927	return 0;
1928	commit = (struct commit *)it;
1929	if (exclude_parent &&
1930	exclude_parent > commit_list_count(commit->parents))
1931	return 0;
1932	for (parents = commit->parents, parent_number = 1;
1933	parents;
1934	parents = parents->next, parent_number++) {
1935	if (exclude_parent && parent_number != exclude_parent)
1936	continue;
1937
1938	it = &parents->item->object;
1939	it->flags \|= flags;
1940	add_rev_cmdline(revs, it, arg_, REV_CMD_PARENTS_ONLY, flags);
1941	add_pending_object(revs, it, arg);
1942	}
1943	return 1;
1944	}
1945
1946	void repo_init_revisions(struct repository *r,
1947	struct rev_info *revs,
1948	const char *prefix)
1949	{
1950	struct rev_info blank = REV_INFO_INIT;
1951	memcpy(revs, &blank, sizeof(*revs));
1952
1953	revs->repo = r;
1954	revs->pruning.repo = r;
1955	revs->pruning.add_remove = file_add_remove;
1956	revs->pruning.change = file_change;
1957	revs->pruning.change_fn_data = revs;
1958	revs->prefix = prefix;
1959
1960	grep_init(&revs->grep_filter, revs->repo);
1961	revs->grep_filter.status_only = 1;
1962
1963	repo_diff_setup(revs->repo, &revs->diffopt);
1964	if (prefix && !revs->diffopt.prefix) {
1965	revs->diffopt.prefix = prefix;
1966	revs->diffopt.prefix_length = strlen(prefix);
1967	}
1968
1969	init_display_notes(&revs->notes_opt);
1970	list_objects_filter_init(&revs->filter);
1971	init_ref_exclusions(&revs->ref_excludes);
1972	oidset_init(&revs->missing_commits, 0);
1973	}
1974
1975	static void add_pending_commit_list(struct rev_info *revs,
1976	struct commit_list *commit_list,
1977	unsigned int flags)
1978	{
1979	while (commit_list) {
1980	struct object *object = &commit_list->item->object;
1981	object->flags \|= flags;
1982	add_pending_object(revs, object, oid_to_hex(&object->oid));
1983	commit_list = commit_list->next;
1984	}
1985	}
1986
1987	static const char lookup_other_head(struct object_id oid)
1988	{
1989	int i;
1990	static const char *const other_head[] = {
1991	"MERGE_HEAD", "CHERRY_PICK_HEAD", "REVERT_HEAD", "REBASE_HEAD"
1992	};
1993
1994	for (i = 0; i < ARRAY_SIZE(other_head); i++)
1995	if (!refs_read_ref_full(get_main_ref_store(the_repository), other_head[i],
1996	RESOLVE_REF_READING \| RESOLVE_REF_NO_RECURSE,
1997	oid, NULL)) {
1998	if (is_null_oid(oid))
1999	die(_("%s exists but is a symbolic ref"), other_head[i]);
2000	return other_head[i];
2001	}
2002
2003	die(_("--merge requires one of the pseudorefs MERGE_HEAD, CHERRY_PICK_HEAD, REVERT_HEAD or REBASE_HEAD"));
2004	}
2005
2006	static void prepare_show_merge(struct rev_info *revs)
2007	{
2008	struct commit_list *bases = NULL;
2009	struct commit head, other;
2010	struct object_id oid;
2011	const char *other_name;
2012	const char **prune = NULL;
2013	int i, prune_num = 1; /* counting terminating NULL */
2014	struct index_state *istate = revs->repo->index;
2015
2016	if (repo_get_oid(the_repository, "HEAD", &oid))
2017	die("--merge without HEAD?");
2018	head = lookup_commit_or_die(&oid, "HEAD");
2019	other_name = lookup_other_head(&oid);
2020	other = lookup_commit_or_die(&oid, other_name);
2021	add_pending_object(revs, &head->object, "HEAD");
2022	add_pending_object(revs, &other->object, other_name);
2023	if (repo_get_merge_bases(the_repository, head, other, &bases) < 0)
2024	exit(128);
2025	add_rev_cmdline_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING \| BOTTOM);
2026	add_pending_commit_list(revs, bases, UNINTERESTING \| BOTTOM);
2027	commit_list_free(bases);
2028	head->object.flags \|= SYMMETRIC_LEFT;
2029
2030	if (!istate->cache_nr)
2031	repo_read_index(revs->repo);
2032	for (i = 0; i < istate->cache_nr; i++) {
2033	const struct cache_entry *ce = istate->cache[i];
2034	if (!ce_stage(ce))
2035	continue;
2036	if (ce_path_match(istate, ce, &revs->prune_data, NULL)) {
2037	prune_num++;
2038	REALLOC_ARRAY(prune, prune_num);
2039	prune[prune_num-2] = ce->name;
2040	prune[prune_num-1] = NULL;
2041	}
2042	while ((i+1 < istate->cache_nr) &&
2043	ce_same_name(ce, istate->cache[i+1]))
2044	i++;
2045	}
2046	clear_pathspec(&revs->prune_data);
2047	parse_pathspec(&revs->prune_data, PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
2048	PATHSPEC_PREFER_FULL \| PATHSPEC_LITERAL_PATH, "", prune);
2049	revs->limited = 1;
2050	free(prune);
2051	}
2052
2053	static int dotdot_missing(const char *full_name,
2054	struct rev_info *revs, int symmetric)
2055	{
2056	if (revs->ignore_missing)
2057	return 0;
2058	die(symmetric
2059	? "Invalid symmetric difference expression %s"
2060	: "Invalid revision range %s", full_name);
2061	}
2062
2063	static int handle_dotdot_1(const char a_name, const char b_name,
2064	const char *full_name, int symmetric,
2065	struct rev_info *revs, int flags,
2066	int cant_be_filename,
2067	struct object_context *a_oc,
2068	struct object_context *b_oc)
2069	{
2070	struct object_id a_oid, b_oid;
2071	struct object a_obj, b_obj;
2072	unsigned int a_flags, b_flags;
2073	unsigned int flags_exclude = flags ^ (UNINTERESTING \| BOTTOM);
2074	unsigned int oc_flags = GET_OID_COMMITTISH \| GET_OID_RECORD_PATH;
2075
2076	if (!*a_name)
2077	a_name = "HEAD";
2078
2079	if (!*b_name)
2080	b_name = "HEAD";
2081
2082	if (get_oid_with_context(revs->repo, a_name, oc_flags, &a_oid, a_oc) \|\|
2083	get_oid_with_context(revs->repo, b_name, oc_flags, &b_oid, b_oc))
2084	return -1;
2085
2086	if (!cant_be_filename) {
2087	verify_non_filename(the_repository, revs->prefix, full_name);
2088	}
2089
2090	a_obj = parse_object(revs->repo, &a_oid);
2091	b_obj = parse_object(revs->repo, &b_oid);
2092	if (!a_obj \|\| !b_obj)
2093	return dotdot_missing(full_name, revs, symmetric);
2094
2095	if (!symmetric) {
2096	/* just A..B */
2097	b_flags = flags;
2098	a_flags = flags_exclude;
2099	} else {
2100	/* A...B -- find merge bases between the two */
2101	struct commit a, b;
2102	struct commit_list *exclude = NULL;
2103
2104	a = lookup_commit_reference(revs->repo, &a_obj->oid);
2105	b = lookup_commit_reference(revs->repo, &b_obj->oid);
2106	if (!a \|\| !b)
2107	return dotdot_missing(full_name, revs, symmetric);
2108
2109	if (repo_get_merge_bases(the_repository, a, b, &exclude) < 0) {
2110	commit_list_free(exclude);
2111	return -1;
2112	}
2113	add_rev_cmdline_list(revs, exclude, REV_CMD_MERGE_BASE,
2114	flags_exclude);
2115	add_pending_commit_list(revs, exclude, flags_exclude);
2116	commit_list_free(exclude);
2117
2118	b_flags = flags;
2119	a_flags = flags \| SYMMETRIC_LEFT;
2120	}
2121
2122	a_obj->flags \|= a_flags;
2123	b_obj->flags \|= b_flags;
2124	add_rev_cmdline(revs, a_obj, a_name, REV_CMD_LEFT, a_flags);
2125	add_rev_cmdline(revs, b_obj, b_name, REV_CMD_RIGHT, b_flags);
2126	add_pending_object_with_path(revs, a_obj, a_name, a_oc->mode, a_oc->path);
2127	add_pending_object_with_path(revs, b_obj, b_name, b_oc->mode, b_oc->path);
2128	return 0;
2129	}
2130
2131	static int handle_dotdot(const char *arg,
2132	struct rev_info *revs, int flags,
2133	int cant_be_filename)
2134	{
2135	struct object_context a_oc = {0}, b_oc = {0};
2136	const char *dotdot = strstr(arg, "..");
2137	char *tmp;
2138	int symmetric = 0;
2139	int ret;
2140
2141	if (!dotdot)
2142	return -1;
2143
2144	tmp = xmemdupz(arg, dotdot - arg);
2145	dotdot += 2;
2146	if (*dotdot == '.') {
2147	symmetric = 1;
2148	dotdot++;
2149	}
2150	ret = handle_dotdot_1(tmp, dotdot, arg, symmetric, revs, flags,
2151	cant_be_filename, &a_oc, &b_oc);
2152	free(tmp);
2153
2154	object_context_release(&a_oc);
2155	object_context_release(&b_oc);
2156	return ret;
2157	}
2158
2159	static int handle_revision_arg_1(const char arg_, struct rev_info revs, int flags, unsigned revarg_opt)
2160	{
2161	struct object_context oc = {0};
2162	const char *mark;
2163	char *arg_minus_at = NULL;
2164	char *arg_minus_excl = NULL;
2165	char *arg_minus_dash = NULL;
2166	struct object *object;
2167	struct object_id oid;
2168	int local_flags;
2169	const char *arg = arg_;
2170	int cant_be_filename = revarg_opt & REVARG_CANNOT_BE_FILENAME;
2171	unsigned get_sha1_flags = GET_OID_RECORD_PATH;
2172	int ret;
2173
2174	flags = flags & UNINTERESTING ? flags \| BOTTOM : flags & ~BOTTOM;
2175
2176	if (!cant_be_filename && !strcmp(arg, "..")) {
2177	/*
2178	* Just ".."? That is not a range but the
2179	* pathspec for the parent directory.
2180	*/
2181	ret = -1;
2182	goto out;
2183	}
2184
2185	if (!handle_dotdot(arg, revs, flags, revarg_opt)) {
2186	ret = 0;
2187	goto out;
2188	}
2189
2190	mark = strstr(arg, "^@");
2191	if (mark && !mark[2]) {
2192	arg_minus_at = xmemdupz(arg, mark - arg);
2193	if (add_parents_only(revs, arg_minus_at, flags, 0)) {
2194	ret = 0;
2195	goto out;
2196	}
2197	}
2198	mark = strstr(arg, "^!");
2199	if (mark && !mark[2]) {
2200	arg_minus_excl = xmemdupz(arg, mark - arg);
2201	if (add_parents_only(revs, arg_minus_excl, flags ^ (UNINTERESTING \| BOTTOM), 0))
2202	arg = arg_minus_excl;
2203	}
2204	mark = strstr(arg, "^-");
2205	if (mark) {
2206	int exclude_parent = 1;
2207
2208	if (mark[2]) {
2209	if (strtol_i(mark + 2, 10, &exclude_parent) \|\|
2210	exclude_parent < 1) {
2211	ret = -1;
2212	goto out;
2213	}
2214	}
2215
2216	arg_minus_dash = xmemdupz(arg, mark - arg);
2217	if (add_parents_only(revs, arg_minus_dash, flags ^ (UNINTERESTING \| BOTTOM), exclude_parent))
2218	arg = arg_minus_dash;
2219	}
2220
2221	local_flags = 0;
2222	if (*arg == '^') {
2223	local_flags = UNINTERESTING \| BOTTOM;
2224	arg++;
2225	}
2226
2227	if (revarg_opt & REVARG_COMMITTISH)
2228	get_sha1_flags \|= GET_OID_COMMITTISH;
2229
2230	/*
2231	* Even if revs->do_not_die_on_missing_objects is set, we
2232	* should error out if we can't even get an oid, as
2233	* `--missing=print` should be able to report missing oids.
2234	*/
2235	if (get_oid_with_context(revs->repo, arg, get_sha1_flags, &oid, &oc)) {
2236	ret = revs->ignore_missing ? 0 : -1;
2237	goto out;
2238	}
2239	if (!cant_be_filename)
2240	verify_non_filename(the_repository, revs->prefix, arg);
2241	object = get_reference(revs, arg, &oid, flags ^ local_flags);
2242	if (!object) {
2243	ret = (revs->ignore_missing \|\| revs->do_not_die_on_missing_objects) ? 0 : -1;
2244	goto out;
2245	}
2246	add_rev_cmdline(revs, object, arg_, REV_CMD_REV, flags ^ local_flags);
2247	add_pending_object_with_path(revs, object, arg, oc.mode, oc.path);
2248
2249	ret = 0;
2250
2251	out:
2252	object_context_release(&oc);
2253	free(arg_minus_at);
2254	free(arg_minus_excl);
2255	free(arg_minus_dash);
2256	return ret;
2257	}
2258
2259	int handle_revision_arg(const char arg, struct rev_info revs, int flags, unsigned revarg_opt)
2260	{
2261	int ret = handle_revision_arg_1(arg, revs, flags, revarg_opt);
2262	if (!ret)
2263	revs->rev_input_given = 1;
2264	return ret;
2265	}
2266
2267	static void read_pathspec_from_stdin(struct strbuf *sb,
2268	struct strvec *prune)
2269	{
2270	while (strbuf_getline(sb, stdin) != EOF)
2271	strvec_push(prune, sb->buf);
2272	}
2273
2274	static void add_grep(struct rev_info revs, const char ptn, enum grep_pat_token what)
2275	{
2276	append_grep_pattern(&revs->grep_filter, ptn, "command line", 0, what);
2277	}
2278
2279	static void add_header_grep(struct rev_info revs, enum grep_header_field field, const char pattern)
2280	{
2281	append_header_grep_pattern(&revs->grep_filter, field, pattern);
2282	}
2283
2284	static void add_message_grep(struct rev_info revs, const char pattern)
2285	{
2286	add_grep(revs, pattern, GREP_PATTERN_BODY);
2287	}
2288
2289	static int parse_count(const char *arg)
2290	{
2291	int count;
2292
2293	if (strtol_i(arg, 10, &count) < 0)
2294	die("'%s': not an integer", arg);
2295	return count;
2296	}
2297
2298	static timestamp_t parse_age(const char *arg)
2299	{
2300	timestamp_t num;
2301	char *p;
2302
2303	errno = 0;
2304	num = parse_timestamp(arg, &p, 10);
2305	if (errno \|\| *p \|\| p == arg)
2306	die("'%s': not a number of seconds since epoch", arg);
2307	return num;
2308	}
2309
2310	static void overwrite_argv(int argc, const char *argv,
2311	const char **value,
2312	const struct setup_revision_opt *opt)
2313	{
2314	/*
2315	* Detect the case when we are overwriting ourselves. The assignment
2316	* itself would be a noop either way, but this lets us avoid corner
2317	* cases around the free() and NULL operations.
2318	*/
2319	if (value != argv[argc]) {
2320	if (opt && opt->free_removed_argv_elements)
2321	free((char )argv[argc]);
2322	argv[argc] = value;
2323	*value = NULL;
2324	}
2325	(*argc)++;
2326	}
2327
2328	static int handle_revision_opt(struct rev_info revs, int argc, const char *argv,
2329	int unkc, const char *unkv,
2330	const struct setup_revision_opt* opt)
2331	{
2332	const char *arg = argv[0];
2333	const char *optarg = NULL;
2334	int argcount;
2335	const unsigned hexsz = the_hash_algo->hexsz;
2336
2337	/* pseudo revision arguments */
2338	if (!strcmp(arg, "--all") \|\| !strcmp(arg, "--branches") \|\|
2339	!strcmp(arg, "--tags") \|\| !strcmp(arg, "--remotes") \|\|
2340	!strcmp(arg, "--reflog") \|\| !strcmp(arg, "--not") \|\|
2341	!strcmp(arg, "--no-walk") \|\| !strcmp(arg, "--do-walk") \|\|
2342	!strcmp(arg, "--bisect") \|\| starts_with(arg, "--glob=") \|\|
2343	!strcmp(arg, "--indexed-objects") \|\|
2344	!strcmp(arg, "--alternate-refs") \|\|
2345	starts_with(arg, "--exclude=") \|\| starts_with(arg, "--exclude-hidden=") \|\|
2346	starts_with(arg, "--branches=") \|\| starts_with(arg, "--tags=") \|\|
2347	starts_with(arg, "--remotes=") \|\| starts_with(arg, "--no-walk="))
2348	{
2349	overwrite_argv(unkc, unkv, &argv[0], opt);
2350	return 1;
2351	}
2352
2353	if ((argcount = parse_long_opt("max-count", argv, &optarg))) {
2354	if (revs->max_count_type == 1)
2355	die_for_incompatible_opt2(1, "--max-count", 1,
2356	"--max-count-oldest");
2357	revs->max_count = parse_count(optarg);
2358	revs->no_walk = 0;
2359	revs->max_count_type = 0;
2360	return argcount;
2361	} else if ((argcount = parse_long_opt("max-count-oldest", argv, &optarg))) {
2362	if (revs->max_count_type == 0 && revs->max_count != -1)
2363	die_for_incompatible_opt2(1, "--max-count", 1,
2364	"--max-count-oldest");
2365	if (revs->skip_count > 0)
2366	die_for_incompatible_opt2(1, "--skip", 1,
2367	"--max-count-oldest");
2368	revs->max_count = parse_count(optarg);
2369	revs->no_walk = 0;
2370	revs->max_count_type = 1;
2371	revs->max_count_stage = 0;
2372	} else if ((argcount = parse_long_opt("skip", argv, &optarg))) {
2373	if (revs->max_count_type == 1)
2374	die_for_incompatible_opt2(1, "--skip", 1,
2375	"--max-count-oldest");
2376	revs->skip_count = parse_count(optarg);
2377	return argcount;
2378	} else if ((*arg == '-') && isdigit(arg[1])) {
2379	/* accept -<digit>, like traditional "head" */
2380	revs->max_count = parse_count(arg + 1);
2381	revs->no_walk = 0;
2382	} else if (!strcmp(arg, "-n")) {
2383	if (argc <= 1)
2384	return error("-n requires an argument");
2385	revs->max_count = parse_count(argv[1]);
2386	revs->no_walk = 0;
2387	return 2;
2388	} else if (skip_prefix(arg, "-n", &optarg)) {
2389	revs->max_count = parse_count(optarg);
2390	revs->no_walk = 0;
2391	} else if ((argcount = parse_long_opt("max-age", argv, &optarg))) {
2392	revs->max_age = parse_age(optarg);
2393	return argcount;
2394	} else if ((argcount = parse_long_opt("since", argv, &optarg))) {
2395	revs->max_age = approxidate(optarg);
2396	return argcount;
2397	} else if ((argcount = parse_long_opt("since-as-filter", argv, &optarg))) {
2398	revs->max_age_as_filter = approxidate(optarg);
2399	return argcount;
2400	} else if ((argcount = parse_long_opt("after", argv, &optarg))) {
2401	revs->max_age = approxidate(optarg);
2402	return argcount;
2403	} else if ((argcount = parse_long_opt("min-age", argv, &optarg))) {
2404	revs->min_age = parse_age(optarg);
2405	return argcount;
2406	} else if ((argcount = parse_long_opt("before", argv, &optarg))) {
2407	revs->min_age = approxidate(optarg);
2408	return argcount;
2409	} else if ((argcount = parse_long_opt("until", argv, &optarg))) {
2410	revs->min_age = approxidate(optarg);
2411	return argcount;
2412	} else if (!strcmp(arg, "--maximal-only")) {
2413	revs->maximal_only = 1;
2414	} else if (!strcmp(arg, "--first-parent")) {
2415	revs->first_parent_only = 1;
2416	} else if (!strcmp(arg, "--exclude-first-parent-only")) {
2417	revs->exclude_first_parent_only = 1;
2418	} else if (!strcmp(arg, "--ancestry-path")) {
2419	revs->ancestry_path = 1;
2420	revs->simplify_history = 0;
2421	revs->limited = 1;
2422	revs->ancestry_path_implicit_bottoms = 1;
2423	} else if (skip_prefix(arg, "--ancestry-path=", &optarg)) {
2424	struct commit *c;
2425	struct object_id oid;
2426	const char *msg = _("could not get commit for --ancestry-path argument %s");
2427
2428	revs->ancestry_path = 1;
2429	revs->simplify_history = 0;
2430	revs->limited = 1;
2431
2432	if (repo_get_oid_committish(revs->repo, optarg, &oid))
2433	return error(msg, optarg);
2434	get_reference(revs, optarg, &oid, ANCESTRY_PATH);
2435	c = lookup_commit_reference(revs->repo, &oid);
2436	if (!c)
2437	return error(msg, optarg);
2438	commit_list_insert(c, &revs->ancestry_path_bottoms);
2439	} else if (!strcmp(arg, "-g") \|\| !strcmp(arg, "--walk-reflogs")) {
2440	init_reflog_walk(&revs->reflog_info);
2441	} else if (!strcmp(arg, "--default")) {
2442	if (argc <= 1)
2443	return error("bad --default argument");
2444	revs->def = argv[1];
2445	return 2;
2446	} else if (!strcmp(arg, "--merge")) {
2447	revs->show_merge = 1;
2448	} else if (!strcmp(arg, "--topo-order")) {
2449	revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
2450	revs->topo_order = 1;
2451	} else if (!strcmp(arg, "--simplify-merges")) {
2452	revs->simplify_merges = 1;
2453	revs->topo_order = 1;
2454	revs->rewrite_parents = 1;
2455	revs->simplify_history = 0;
2456	revs->limited = 1;
2457	} else if (!strcmp(arg, "--simplify-by-decoration")) {
2458	revs->simplify_merges = 1;
2459	revs->topo_order = 1;
2460	revs->rewrite_parents = 1;
2461	revs->simplify_history = 0;
2462	revs->simplify_by_decoration = 1;
2463	revs->limited = 1;
2464	revs->prune = 1;
2465	} else if (!strcmp(arg, "--date-order")) {
2466	revs->sort_order = REV_SORT_BY_COMMIT_DATE;
2467	revs->topo_order = 1;
2468	} else if (!strcmp(arg, "--author-date-order")) {
2469	revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
2470	revs->topo_order = 1;
2471	} else if (!strcmp(arg, "--parents")) {
2472	revs->rewrite_parents = 1;
2473	revs->print_parents = 1;
2474	} else if (!strcmp(arg, "--dense")) {
2475	revs->dense = 1;
2476	} else if (!strcmp(arg, "--sparse")) {
2477	revs->dense = 0;
2478	} else if (!strcmp(arg, "--in-commit-order")) {
2479	revs->tree_blobs_in_commit_order = 1;
2480	} else if (!strcmp(arg, "--remove-empty")) {
2481	revs->remove_empty_trees = 1;
2482	} else if (!strcmp(arg, "--merges")) {
2483	revs->min_parents = 2;
2484	} else if (!strcmp(arg, "--no-merges")) {
2485	revs->max_parents = 1;
2486	} else if (skip_prefix(arg, "--min-parents=", &optarg)) {
2487	revs->min_parents = parse_count(optarg);
2488	} else if (!strcmp(arg, "--no-min-parents")) {
2489	revs->min_parents = 0;
2490	} else if (skip_prefix(arg, "--max-parents=", &optarg)) {
2491	revs->max_parents = parse_count(optarg);
2492	} else if (!strcmp(arg, "--no-max-parents")) {
2493	revs->max_parents = -1;
2494	} else if (!strcmp(arg, "--boundary")) {
2495	revs->boundary = 1;
2496	} else if (!strcmp(arg, "--left-right")) {
2497	revs->left_right = 1;
2498	} else if (!strcmp(arg, "--left-only")) {
2499	if (revs->right_only)
2500	die(_("options '%s' and '%s' cannot be used together"),
2501	"--left-only", "--right-only/--cherry");
2502	revs->left_only = 1;
2503	revs->limited = 1;
2504	} else if (!strcmp(arg, "--right-only")) {
2505	if (revs->left_only)
2506	die(_("options '%s' and '%s' cannot be used together"), "--right-only", "--left-only");
2507	revs->right_only = 1;
2508	revs->limited = 1;
2509	} else if (!strcmp(arg, "--cherry")) {
2510	if (revs->left_only)
2511	die(_("options '%s' and '%s' cannot be used together"), "--cherry", "--left-only");
2512	revs->cherry_mark = 1;
2513	revs->right_only = 1;
2514	revs->max_parents = 1;
2515	revs->limited = 1;
2516	} else if (!strcmp(arg, "--count")) {
2517	revs->count = 1;
2518	} else if (!strcmp(arg, "--cherry-mark")) {
2519	if (revs->cherry_pick)
2520	die(_("options '%s' and '%s' cannot be used together"), "--cherry-mark", "--cherry-pick");
2521	revs->cherry_mark = 1;
2522	revs->limited = 1; /* needs limit_list() */
2523	} else if (!strcmp(arg, "--cherry-pick")) {
2524	if (revs->cherry_mark)
2525	die(_("options '%s' and '%s' cannot be used together"), "--cherry-pick", "--cherry-mark");
2526	revs->cherry_pick = 1;
2527	revs->limited = 1;
2528	} else if (!strcmp(arg, "--objects")) {
2529	revs->tag_objects = 1;
2530	revs->tree_objects = 1;
2531	revs->blob_objects = 1;
2532	} else if (!strcmp(arg, "--objects-edge")) {
2533	revs->tag_objects = 1;
2534	revs->tree_objects = 1;
2535	revs->blob_objects = 1;
2536	revs->edge_hint = 1;
2537	} else if (!strcmp(arg, "--objects-edge-aggressive")) {
2538	revs->tag_objects = 1;
2539	revs->tree_objects = 1;
2540	revs->blob_objects = 1;
2541	revs->edge_hint = 1;
2542	revs->edge_hint_aggressive = 1;
2543	} else if (!strcmp(arg, "--verify-objects")) {
2544	revs->tag_objects = 1;
2545	revs->tree_objects = 1;
2546	revs->blob_objects = 1;
2547	revs->verify_objects = 1;
2548	disable_commit_graph(revs->repo);
2549	} else if (!strcmp(arg, "--unpacked")) {
2550	revs->unpacked = 1;
2551	} else if (starts_with(arg, "--unpacked=")) {
2552	die(_("--unpacked=<packfile> no longer supported"));
2553	} else if (!strcmp(arg, "--no-kept-objects")) {
2554	revs->no_kept_objects = 1;
2555	revs->keep_pack_cache_flags \|= KEPT_PACK_IN_CORE;
2556	revs->keep_pack_cache_flags \|= KEPT_PACK_ON_DISK;
2557	} else if (skip_prefix(arg, "--no-kept-objects=", &optarg)) {
2558	revs->no_kept_objects = 1;
2559	if (!strcmp(optarg, "in-core"))
2560	revs->keep_pack_cache_flags \|= KEPT_PACK_IN_CORE;
2561	if (!strcmp(optarg, "on-disk"))
2562	revs->keep_pack_cache_flags \|= KEPT_PACK_ON_DISK;
2563	} else if (!strcmp(arg, "-r")) {
2564	revs->diff = 1;
2565	revs->diffopt.flags.recursive = 1;
2566	} else if (!strcmp(arg, "-t")) {
2567	revs->diff = 1;
2568	revs->diffopt.flags.recursive = 1;
2569	revs->diffopt.flags.tree_in_recursive = 1;
2570	} else if ((argcount = diff_merges_parse_opts(revs, argv))) {
2571	return argcount;
2572	} else if (!strcmp(arg, "-v")) {
2573	revs->verbose_header = 1;
2574	} else if (!strcmp(arg, "--pretty")) {
2575	revs->verbose_header = 1;
2576	revs->pretty_given = 1;
2577	get_commit_format(NULL, revs);
2578	} else if (skip_prefix(arg, "--pretty=", &optarg) \|\|
2579	skip_prefix(arg, "--format=", &optarg)) {
2580	/*
2581	* Detached form ("--pretty X" as opposed to "--pretty=X")
2582	* not allowed, since the argument is optional.
2583	*/
2584	revs->verbose_header = 1;
2585	revs->pretty_given = 1;
2586	get_commit_format(optarg, revs);
2587	} else if (!strcmp(arg, "--expand-tabs")) {
2588	revs->expand_tabs_in_log = 8;
2589	} else if (!strcmp(arg, "--no-expand-tabs")) {
2590	revs->expand_tabs_in_log = 0;
2591	} else if (skip_prefix(arg, "--expand-tabs=", &arg)) {
2592	int val;
2593	if (strtol_i(arg, 10, &val) < 0 \|\| val < 0)
2594	die("'%s': not a non-negative integer", arg);
2595	revs->expand_tabs_in_log = val;
2596	} else if (!strcmp(arg, "--show-notes") \|\| !strcmp(arg, "--notes")) {
2597	enable_default_display_notes(&revs->notes_opt, &revs->show_notes);
2598	revs->show_notes_given = 1;
2599	} else if (!strcmp(arg, "--show-signature")) {
2600	revs->show_signature = 1;
2601	} else if (!strcmp(arg, "--no-show-signature")) {
2602	revs->show_signature = 0;
2603	} else if (!strcmp(arg, "--show-linear-break")) {
2604	revs->break_bar = " ..........";
2605	revs->track_linear = 1;
2606	revs->track_first_time = 1;
2607	} else if (skip_prefix(arg, "--show-linear-break=", &optarg)) {
2608	revs->break_bar = xstrdup(optarg);
2609	revs->track_linear = 1;
2610	revs->track_first_time = 1;
2611	} else if (!strcmp(arg, "--show-notes-by-default")) {
2612	revs->show_notes_by_default = 1;
2613	} else if (skip_prefix(arg, "--show-notes=", &optarg) \|\|
2614	skip_prefix(arg, "--notes=", &optarg)) {
2615	if (starts_with(arg, "--show-notes=") &&
2616	revs->notes_opt.use_default_notes < 0)
2617	revs->notes_opt.use_default_notes = 1;
2618	enable_ref_display_notes(&revs->notes_opt, &revs->show_notes, optarg);
2619	revs->show_notes_given = 1;
2620	} else if (!strcmp(arg, "--no-notes")) {
2621	disable_display_notes(&revs->notes_opt, &revs->show_notes);
2622	revs->show_notes_given = 1;
2623	} else if (!strcmp(arg, "--standard-notes")) {
2624	revs->show_notes_given = 1;
2625	revs->notes_opt.use_default_notes = 1;
2626	} else if (!strcmp(arg, "--no-standard-notes")) {
2627	revs->notes_opt.use_default_notes = 0;
2628	} else if (!strcmp(arg, "--oneline")) {
2629	revs->verbose_header = 1;
2630	get_commit_format("oneline", revs);
2631	revs->pretty_given = 1;
2632	revs->abbrev_commit = 1;
2633	} else if (!strcmp(arg, "--graph")) {
2634	graph_clear(revs->graph);
2635	revs->graph = graph_init(revs);
2636	} else if (!strcmp(arg, "--no-graph")) {
2637	graph_clear(revs->graph);
2638	revs->graph = NULL;
2639	} else if (skip_prefix(arg, "--graph-lane-limit=", &optarg)) {
2640	revs->graph_max_lanes = parse_count(optarg);
2641	} else if (!strcmp(arg, "--graph-indent")) {
2642	revs->no_graph_indent = 0;
2643	revs->graph_indent_set = 1;
2644	} else if (!strcmp(arg, "--no-graph-indent")) {
2645	revs->no_graph_indent = 1;
2646	revs->graph_indent_set = 1;
2647	} else if (!strcmp(arg, "--encode-email-headers")) {
2648	revs->encode_email_headers = 1;
2649	} else if (!strcmp(arg, "--no-encode-email-headers")) {
2650	revs->encode_email_headers = 0;
2651	} else if (!strcmp(arg, "--root")) {
2652	revs->show_root_diff = 1;
2653	} else if (!strcmp(arg, "--no-commit-id")) {
2654	revs->no_commit_id = 1;
2655	} else if (!strcmp(arg, "--always")) {
2656	revs->always_show_header = 1;
2657	} else if (!strcmp(arg, "--no-abbrev")) {
2658	revs->abbrev = 0;
2659	} else if (!strcmp(arg, "--abbrev")) {
2660	revs->abbrev = DEFAULT_ABBREV;
2661	} else if (skip_prefix(arg, "--abbrev=", &optarg)) {
2662	revs->abbrev = strtoul(optarg, NULL, 10);
2663	if (revs->abbrev < MINIMUM_ABBREV)
2664	revs->abbrev = MINIMUM_ABBREV;
2665	else if (revs->abbrev > hexsz)
2666	revs->abbrev = hexsz;
2667	} else if (!strcmp(arg, "--abbrev-commit")) {
2668	revs->abbrev_commit = 1;
2669	revs->abbrev_commit_given = 1;
2670	} else if (!strcmp(arg, "--no-abbrev-commit")) {
2671	revs->abbrev_commit = 0;
2672	} else if (!strcmp(arg, "--full-diff")) {
2673	revs->diff = 1;
2674	revs->full_diff = 1;
2675	} else if (!strcmp(arg, "--show-pulls")) {
2676	revs->show_pulls = 1;
2677	} else if (!strcmp(arg, "--full-history")) {
2678	revs->simplify_history = 0;
2679	} else if (!strcmp(arg, "--relative-date")) {
2680	revs->date_mode.type = DATE_RELATIVE;
2681	revs->date_mode_explicit = 1;
2682	} else if ((argcount = parse_long_opt("date", argv, &optarg))) {
2683	parse_date_format(optarg, &revs->date_mode);
2684	revs->date_mode_explicit = 1;
2685	return argcount;
2686	} else if (!strcmp(arg, "--log-size")) {
2687	revs->show_log_size = 1;
2688	}
2689	/*
2690	* Grepping the commit log
2691	*/
2692	else if ((argcount = parse_long_opt("author", argv, &optarg))) {
2693	add_header_grep(revs, GREP_HEADER_AUTHOR, optarg);
2694	return argcount;
2695	} else if ((argcount = parse_long_opt("committer", argv, &optarg))) {
2696	add_header_grep(revs, GREP_HEADER_COMMITTER, optarg);
2697	return argcount;
2698	} else if ((argcount = parse_long_opt("grep-reflog", argv, &optarg))) {
2699	add_header_grep(revs, GREP_HEADER_REFLOG, optarg);
2700	return argcount;
2701	} else if ((argcount = parse_long_opt("grep", argv, &optarg))) {
2702	add_message_grep(revs, optarg);
2703	return argcount;
2704	} else if (!strcmp(arg, "--basic-regexp")) {
2705	revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_BRE;
2706	} else if (!strcmp(arg, "--extended-regexp") \|\| !strcmp(arg, "-E")) {
2707	revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_ERE;
2708	} else if (!strcmp(arg, "--regexp-ignore-case") \|\| !strcmp(arg, "-i")) {
2709	revs->grep_filter.ignore_case = 1;
2710	revs->diffopt.pickaxe_opts \|= DIFF_PICKAXE_IGNORE_CASE;
2711	} else if (!strcmp(arg, "--fixed-strings") \|\| !strcmp(arg, "-F")) {
2712	revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_FIXED;
2713	} else if (!strcmp(arg, "--perl-regexp") \|\| !strcmp(arg, "-P")) {
2714	revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_PCRE;
2715	} else if (!strcmp(arg, "--all-match")) {
2716	revs->grep_filter.all_match = 1;
2717	} else if (!strcmp(arg, "--invert-grep")) {
2718	revs->grep_filter.no_body_match = 1;
2719	} else if ((argcount = parse_long_opt("encoding", argv, &optarg))) {
2720	free(git_log_output_encoding);
2721	if (strcmp(optarg, "none"))
2722	git_log_output_encoding = xstrdup(optarg);
2723	else
2724	git_log_output_encoding = xstrdup("");
2725	return argcount;
2726	} else if (!strcmp(arg, "--reverse")) {
2727	revs->reverse ^= 1;
2728	} else if (!strcmp(arg, "--children")) {
2729	revs->children.name = "children";
2730	revs->limited = 1;
2731	} else if (!strcmp(arg, "--ignore-missing")) {
2732	revs->ignore_missing = 1;
2733	} else if (opt && opt->allow_exclude_promisor_objects &&
2734	!strcmp(arg, "--exclude-promisor-objects")) {
2735	if (fetch_if_missing)
2736	BUG("exclude_promisor_objects can only be used when fetch_if_missing is 0");
2737	revs->exclude_promisor_objects = 1;
2738	} else {
2739	int opts = diff_opt_parse(&revs->diffopt, argv, argc, revs->prefix);
2740	if (!opts)
2741	overwrite_argv(unkc, unkv, &argv[0], opt);
2742	return opts;
2743	}
2744
2745	return 1;
2746	}
2747
2748	void parse_revision_opt(struct rev_info revs, struct parse_opt_ctx_t ctx,
2749	const struct option *options,
2750	const char * const usagestr[])
2751	{
2752	int n = handle_revision_opt(revs, ctx->argc, ctx->argv,
2753	&ctx->cpidx, ctx->out, NULL);
2754	if (n <= 0) {
2755	error("unknown option `%s'", ctx->argv[0]);
2756	usage_with_options(usagestr, options);
2757	}
2758	ctx->argv += n;
2759	ctx->argc -= n;
2760	}
2761
2762	void revision_opts_finish(struct rev_info *revs)
2763	{
2764	if (revs->graph && revs->track_linear)
2765	die(_("options '%s' and '%s' cannot be used together"), "--show-linear-break", "--graph");
2766
2767	if (revs->graph) {
2768	revs->topo_order = 1;
2769	revs->rewrite_parents = 1;
2770	}
2771	}
2772
2773	static int for_each_bisect_ref(struct ref_store *refs, refs_for_each_cb fn,
2774	void cb_data, const char term)
2775	{
2776	struct refs_for_each_ref_options opts = { 0 };
2777	struct strbuf bisect_refs = STRBUF_INIT;
2778	int status;
2779	strbuf_addf(&bisect_refs, "refs/bisect/%s", term);
2780	opts.prefix = bisect_refs.buf;
2781	status = refs_for_each_ref_ext(refs, fn, cb_data, &opts);
2782	strbuf_release(&bisect_refs);
2783	return status;
2784	}
2785
2786	static int for_each_bad_bisect_ref(struct ref_store refs, refs_for_each_cb fn, void cb_data)
2787	{
2788	return for_each_bisect_ref(refs, fn, cb_data, term_bad);
2789	}
2790
2791	static int for_each_good_bisect_ref(struct ref_store refs, refs_for_each_cb fn, void cb_data)
2792	{
2793	return for_each_bisect_ref(refs, fn, cb_data, term_good);
2794	}
2795
2796	static int handle_revision_pseudo_opt(struct rev_info *revs,
2797	const char *argv, int flags)
2798	{
2799	const char *arg = argv[0];
2800	const char *optarg;
2801	struct ref_store *refs;
2802	int argcount;
2803
2804	if (revs->repo != the_repository) {
2805	/*
2806	* We need some something like get_submodule_worktrees()
2807	* before we can go through all worktrees of a submodule,
2808	* .e.g with adding all HEADs from --all, which is not
2809	* supported right now, so stick to single worktree.
2810	*/
2811	if (!revs->single_worktree)
2812	BUG("--single-worktree cannot be used together with submodule");
2813	}
2814	refs = get_main_ref_store(revs->repo);
2815
2816	/*
2817	* NOTE!
2818	*
2819	* Commands like "git shortlog" will not accept the options below
2820	* unless parse_revision_opt queues them (as opposed to erroring
2821	* out).
2822	*
2823	* When implementing your new pseudo-option, remember to
2824	* register it in the list at the top of handle_revision_opt.
2825	*/
2826	if (!strcmp(arg, "--all")) {
2827	handle_refs(refs, revs, *flags, refs_for_each_ref);
2828	handle_refs(refs, revs, *flags, refs_head_ref);
2829	if (!revs->single_worktree) {
2830	struct all_refs_cb cb;
2831
2832	init_all_refs_cb(&cb, revs, *flags);
2833	other_head_refs(the_repository, handle_one_ref, &cb);
2834	}
2835	clear_ref_exclusions(&revs->ref_excludes);
2836	} else if (!strcmp(arg, "--branches")) {
2837	if (revs->ref_excludes.hidden_refs_configured)
2838	return error(_("options '%s' and '%s' cannot be used together"),
2839	"--exclude-hidden", "--branches");
2840	handle_refs(refs, revs, *flags, refs_for_each_branch_ref);
2841	clear_ref_exclusions(&revs->ref_excludes);
2842	} else if (!strcmp(arg, "--bisect")) {
2843	read_bisect_terms(&term_bad, &term_good);
2844	handle_refs(refs, revs, *flags, for_each_bad_bisect_ref);
2845	handle_refs(refs, revs, *flags ^ (UNINTERESTING \| BOTTOM),
2846	for_each_good_bisect_ref);
2847	revs->bisect = 1;
2848	} else if (!strcmp(arg, "--tags")) {
2849	if (revs->ref_excludes.hidden_refs_configured)
2850	return error(_("options '%s' and '%s' cannot be used together"),
2851	"--exclude-hidden", "--tags");
2852	handle_refs(refs, revs, *flags, refs_for_each_tag_ref);
2853	clear_ref_exclusions(&revs->ref_excludes);
2854	} else if (!strcmp(arg, "--remotes")) {
2855	if (revs->ref_excludes.hidden_refs_configured)
2856	return error(_("options '%s' and '%s' cannot be used together"),
2857	"--exclude-hidden", "--remotes");
2858	handle_refs(refs, revs, *flags, refs_for_each_remote_ref);
2859	clear_ref_exclusions(&revs->ref_excludes);
2860	} else if ((argcount = parse_long_opt("glob", argv, &optarg))) {
2861	struct refs_for_each_ref_options opts = {
2862	.pattern = optarg,
2863	};
2864	struct all_refs_cb cb;
2865	init_all_refs_cb(&cb, revs, *flags);
2866	refs_for_each_ref_ext(get_main_ref_store(the_repository),
2867	handle_one_ref, &cb, &opts);
2868	clear_ref_exclusions(&revs->ref_excludes);
2869	return argcount;
2870	} else if ((argcount = parse_long_opt("exclude", argv, &optarg))) {
2871	add_ref_exclusion(&revs->ref_excludes, optarg);
2872	return argcount;
2873	} else if ((argcount = parse_long_opt("exclude-hidden", argv, &optarg))) {
2874	exclude_hidden_refs(&revs->ref_excludes, optarg);
2875	return argcount;
2876	} else if (skip_prefix(arg, "--branches=", &optarg)) {
2877	struct refs_for_each_ref_options opts = {
2878	.prefix = "refs/heads/",
2879	.trim_prefix = strlen("refs/heads/"),
2880	.pattern = optarg,
2881	};
2882	struct all_refs_cb cb;
2883	if (revs->ref_excludes.hidden_refs_configured)
2884	return error(_("options '%s' and '%s' cannot be used together"),
2885	"--exclude-hidden", "--branches");
2886	init_all_refs_cb(&cb, revs, *flags);
2887	refs_for_each_ref_ext(get_main_ref_store(the_repository),
2888	handle_one_ref, &cb, &opts);
2889	clear_ref_exclusions(&revs->ref_excludes);
2890	} else if (skip_prefix(arg, "--tags=", &optarg)) {
2891	struct refs_for_each_ref_options opts = {
2892	.prefix = "refs/tags/",
2893	.trim_prefix = strlen("refs/tags/"),
2894	.pattern = optarg,
2895	};
2896	struct all_refs_cb cb;
2897	if (revs->ref_excludes.hidden_refs_configured)
2898	return error(_("options '%s' and '%s' cannot be used together"),
2899	"--exclude-hidden", "--tags");
2900	init_all_refs_cb(&cb, revs, *flags);
2901	refs_for_each_ref_ext(get_main_ref_store(the_repository),
2902	handle_one_ref, &cb, &opts);
2903	clear_ref_exclusions(&revs->ref_excludes);
2904	} else if (skip_prefix(arg, "--remotes=", &optarg)) {
2905	struct refs_for_each_ref_options opts = {
2906	.prefix = "refs/remotes/",
2907	.trim_prefix = strlen("refs/remotes/"),
2908	.pattern = optarg,
2909	};
2910	struct all_refs_cb cb;
2911	if (revs->ref_excludes.hidden_refs_configured)
2912	return error(_("options '%s' and '%s' cannot be used together"),
2913	"--exclude-hidden", "--remotes");
2914	init_all_refs_cb(&cb, revs, *flags);
2915	refs_for_each_ref_ext(get_main_ref_store(the_repository),
2916	handle_one_ref, &cb, &opts);
2917	clear_ref_exclusions(&revs->ref_excludes);
2918	} else if (!strcmp(arg, "--reflog")) {
2919	add_reflogs_to_pending(revs, *flags);
2920	} else if (!strcmp(arg, "--indexed-objects")) {
2921	add_index_objects_to_pending(revs, *flags);
2922	} else if (!strcmp(arg, "--alternate-refs")) {
2923	add_alternate_refs_to_pending(revs, *flags);
2924	} else if (!strcmp(arg, "--not")) {
2925	*flags ^= UNINTERESTING \| BOTTOM;
2926	} else if (!strcmp(arg, "--no-walk")) {
2927	revs->no_walk = 1;
2928	} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
2929	/*
2930	* Detached form ("--no-walk X" as opposed to "--no-walk=X")
2931	* not allowed, since the argument is optional.
2932	*/
2933	revs->no_walk = 1;
2934	if (!strcmp(optarg, "sorted"))
2935	revs->unsorted_input = 0;
2936	else if (!strcmp(optarg, "unsorted"))
2937	revs->unsorted_input = 1;
2938	else
2939	return error("invalid argument to --no-walk");
2940	} else if (!strcmp(arg, "--do-walk")) {
2941	revs->no_walk = 0;
2942	} else if (!strcmp(arg, "--single-worktree")) {
2943	revs->single_worktree = 1;
2944	} else if (skip_prefix(arg, ("--filter="), &arg)) {
2945	parse_list_objects_filter(&revs->filter, arg);
2946	} else if (!strcmp(arg, ("--no-filter"))) {
2947	list_objects_filter_set_no_filter(&revs->filter);
2948	} else {
2949	return 0;
2950	}
2951
2952	return 1;
2953	}
2954
2955	static void read_revisions_from_stdin(struct rev_info *revs,
2956	struct strvec *prune)
2957	{
2958	struct strbuf sb;
2959	int seen_dashdash = 0;
2960	int seen_end_of_options = 0;
2961	int save_warning;
2962	int flags = 0;
2963	struct repo_config_values *cfg = repo_config_values(the_repository);
2964
2965	save_warning = cfg->warn_on_object_refname_ambiguity;
2966	cfg->warn_on_object_refname_ambiguity = 0;
2967
2968	strbuf_init(&sb, 1000);
2969	while (strbuf_getline(&sb, stdin) != EOF) {
2970	if (!sb.len)
2971	break;
2972
2973	if (!strcmp(sb.buf, "--")) {
2974	seen_dashdash = 1;
2975	break;
2976	}
2977
2978	if (!seen_end_of_options && sb.buf[0] == '-') {
2979	const char *argv[] = { sb.buf, NULL };
2980
2981	if (!strcmp(sb.buf, "--end-of-options")) {
2982	seen_end_of_options = 1;
2983	continue;
2984	}
2985
2986	if (handle_revision_pseudo_opt(revs, argv, &flags) > 0)
2987	continue;
2988
2989	die(_("invalid option '%s' in --stdin mode"), sb.buf);
2990	}
2991
2992	if (handle_revision_arg(sb.buf, revs, flags,
2993	REVARG_CANNOT_BE_FILENAME))
2994	die("bad revision '%s'", sb.buf);
2995	}
2996	if (seen_dashdash)
2997	read_pathspec_from_stdin(&sb, prune);
2998
2999	strbuf_release(&sb);
3000	cfg->warn_on_object_refname_ambiguity = save_warning;
3001	}
3002
3003	static void NORETURN diagnose_missing_default(const char *def)
3004	{
3005	int flags;
3006	const char *refname;
3007
3008	refname = refs_resolve_ref_unsafe(get_main_ref_store(the_repository),
3009	def, 0, NULL, &flags);
3010	if (!refname \|\| !(flags & REF_ISSYMREF) \|\| (flags & REF_ISBROKEN))
3011	die(_("your current branch appears to be broken"));
3012
3013	skip_prefix(refname, "refs/heads/", &refname);
3014	die(_("your current branch '%s' does not have any commits yet"),
3015	refname);
3016	}
3017
3018	/*
3019	* Parse revision information, filling in the "rev_info" structure,
3020	* and removing the used arguments from the argument list.
3021	*
3022	* Returns the number of arguments left that weren't recognized
3023	* (which are also moved to the head of the argument list)
3024	*/
3025	int setup_revisions(int argc, const char *argv, struct rev_info revs, struct setup_revision_opt *opt)
3026	{
3027	int i, flags, left, seen_dashdash, revarg_opt;
3028	struct strvec prune_data = STRVEC_INIT;
3029	int seen_end_of_options = 0;
3030
3031	/* First, search for "--" */
3032	if (opt && opt->assume_dashdash) {
3033	seen_dashdash = 1;
3034	} else {
3035	seen_dashdash = 0;
3036	for (i = 1; i < argc; i++) {
3037	const char *arg = argv[i];
3038	if (strcmp(arg, "--"))
3039	continue;
3040	if (opt && opt->free_removed_argv_elements)
3041	free((char *)argv[i]);
3042	argv[i] = NULL;
3043	argc = i;
3044	if (argv[i + 1])
3045	strvec_pushv(&prune_data, argv + i + 1);
3046	seen_dashdash = 1;
3047	break;
3048	}
3049	}
3050
3051	/* Second, deal with arguments and options */
3052	flags = 0;
3053	revarg_opt = opt ? opt->revarg_opt : 0;
3054	if (seen_dashdash)
3055	revarg_opt \|= REVARG_CANNOT_BE_FILENAME;
3056	for (left = i = 1; i < argc; i++) {
3057	const char *arg = argv[i];
3058	if (!seen_end_of_options && *arg == '-') {
3059	int opts;
3060
3061	opts = handle_revision_pseudo_opt(
3062	revs, argv + i,
3063	&flags);
3064	if (opts > 0) {
3065	i += opts - 1;
3066	continue;
3067	}
3068
3069	if (!strcmp(arg, "--stdin")) {
3070	if (revs->disable_stdin) {
3071	overwrite_argv(&left, argv, &argv[i], opt);
3072	continue;
3073	}
3074	if (revs->read_from_stdin++)
3075	die("--stdin given twice?");
3076	read_revisions_from_stdin(revs, &prune_data);
3077	continue;
3078	}
3079
3080	if (!strcmp(arg, "--end-of-options")) {
3081	seen_end_of_options = 1;
3082	continue;
3083	}
3084
3085	opts = handle_revision_opt(revs, argc - i, argv + i,
3086	&left, argv, opt);
3087	if (opts > 0) {
3088	i += opts - 1;
3089	continue;
3090	}
3091	if (opts < 0)
3092	exit(128);
3093	continue;
3094	}
3095
3096
3097	if (handle_revision_arg(arg, revs, flags, revarg_opt)) {
3098	int j;
3099	if (seen_dashdash \|\| *arg == '^')
3100	die("bad revision '%s'", arg);
3101
3102	/* If we didn't have a "--":
3103	* (1) all filenames must exist;
3104	* (2) all rev-args must not be interpretable
3105	* as a valid filename.
3106	* but the latter we have checked in the main loop.
3107	*/
3108	for (j = i; j < argc; j++)
3109	verify_filename(the_repository, revs->prefix, argv[j], j == i);
3110
3111	strvec_pushv(&prune_data, argv + i);
3112	break;
3113	}
3114	}
3115	revision_opts_finish(revs);
3116
3117	if (prune_data.nr) {
3118	/*
3119	* If we need to introduce the magic "a lone ':' means no
3120	* pathspec whatsoever", here is the place to do so.
3121	*
3122	* if (prune_data.nr == 1 && !strcmp(prune_data[0], ":")) {
3123	* prune_data.nr = 0;
3124	* prune_data.alloc = 0;
3125	* free(prune_data.path);
3126	* prune_data.path = NULL;
3127	* } else {
3128	* terminate prune_data.alloc with NULL and
3129	* call init_pathspec() to set revs->prune_data here.
3130	* }
3131	*/
3132	parse_pathspec(&revs->prune_data, 0, 0,
3133	revs->prefix, prune_data.v);
3134	}
3135	strvec_clear(&prune_data);
3136
3137	if (!revs->def)
3138	revs->def = opt ? opt->def : NULL;
3139	if (opt && opt->tweak)
3140	opt->tweak(revs);
3141	if (revs->show_merge)
3142	prepare_show_merge(revs);
3143	if (revs->def && !revs->pending.nr && !revs->rev_input_given) {
3144	struct object_id oid;
3145	struct object *object;
3146	struct object_context oc;
3147	if (get_oid_with_context(revs->repo, revs->def, 0, &oid, &oc))
3148	diagnose_missing_default(revs->def);
3149	object = get_reference(revs, revs->def, &oid, 0);
3150	add_pending_object_with_mode(revs, object, revs->def, oc.mode);
3151	object_context_release(&oc);
3152	}
3153
3154	if (revs->line_level_traverse) {
3155	if (want_ancestry(revs))
3156	revs->limited = 1;
3157	revs->topo_order = 1;
3158	if (!revs->diffopt.output_format)
3159	revs->diffopt.output_format = DIFF_FORMAT_PATCH;
3160	}
3161
3162	/* Did the user ask for any diff output? Run the diff! */
3163	if (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT)
3164	revs->diff = 1;
3165
3166	/* Pickaxe, diff-filter and rename following need diffs */
3167	if ((revs->diffopt.pickaxe_opts & DIFF_PICKAXE_KINDS_MASK) \|\|
3168	revs->diffopt.filter \|\| revs->diffopt.filter_not \|\|
3169	revs->diffopt.flags.follow_renames)
3170	revs->diff = 1;
3171
3172	if (revs->diffopt.objfind)
3173	revs->simplify_history = 0;
3174
3175	if (revs->topo_order && !generation_numbers_enabled(the_repository))
3176	revs->limited = 1;
3177
3178	if (revs->prune_data.nr) {
3179	copy_pathspec(&revs->pruning.pathspec, &revs->prune_data);
3180	/* Can't prune commits with rename following: the paths change.. */
3181	if (!revs->diffopt.flags.follow_renames)
3182	revs->prune = 1;
3183	if (!revs->full_diff)
3184	copy_pathspec(&revs->diffopt.pathspec,
3185	&revs->prune_data);
3186	}
3187
3188	diff_merges_setup_revs(revs);
3189
3190	revs->diffopt.abbrev = revs->abbrev;
3191
3192	diff_setup_done(&revs->diffopt);
3193
3194	if (!is_encoding_utf8(get_log_output_encoding()))
3195	revs->grep_filter.ignore_locale = 1;
3196	compile_grep_patterns(&revs->grep_filter);
3197
3198	if (revs->reflog_info && revs->limited)
3199	die("cannot combine --walk-reflogs with history-limiting options");
3200	if (revs->rewrite_parents && revs->children.name)
3201	die(_("options '%s' and '%s' cannot be used together"), "--parents", "--children");
3202	if (revs->filter.choice && !revs->blob_objects)
3203	die(_("object filtering requires --objects"));
3204
3205	/*
3206	* Limitations on the graph functionality
3207	*/
3208	die_for_incompatible_opt3(!!revs->graph, "--graph",
3209	!!revs->reverse, "--reverse",
3210	!!revs->reflog_info, "--walk-reflogs");
3211
3212	die_for_incompatible_opt2(!!revs->boundary, "--boundary",
3213	!!revs->maximal_only, "--maximal-only");
3214
3215	if (revs->no_walk && revs->graph)
3216	die(_("options '%s' and '%s' cannot be used together"), "--no-walk", "--graph");
3217
3218	if (revs->graph_max_lanes > 0 && !revs->graph)
3219	die(_("the option '%s' requires '%s'"), "--graph-lane-limit", "--graph");
3220
3221	if (revs->graph_indent_set && !revs->graph)
3222	die(_("the option '%s' requires '%s'"), "--[no-]graph-indent", "--graph");
3223
3224	if (!revs->reflog_info && revs->grep_filter.use_reflog_filter)
3225	die(_("the option '%s' requires '%s'"), "--grep-reflog", "--walk-reflogs");
3226
3227	if (revs->line_level_traverse &&
3228	(revs->full_diff \|\|
3229	(revs->diffopt.output_format &
3230	~(DIFF_FORMAT_PATCH \| DIFF_FORMAT_NO_OUTPUT \|
3231	DIFF_FORMAT_RAW \| DIFF_FORMAT_NAME \|
3232	DIFF_FORMAT_NAME_STATUS \| DIFF_FORMAT_SUMMARY))))
3233	die(_("-L does not yet support the requested diff format"));
3234
3235	if (revs->expand_tabs_in_log < 0)
3236	revs->expand_tabs_in_log = revs->expand_tabs_in_log_default;
3237
3238	if (!revs->show_notes_given && revs->show_notes_by_default) {
3239	enable_default_display_notes(&revs->notes_opt, &revs->show_notes);
3240	revs->show_notes_given = 1;
3241	}
3242
3243	if (argv) {
3244	if (opt && opt->free_removed_argv_elements)
3245	free((char *)argv[left]);
3246	argv[left] = NULL;
3247	}
3248
3249	return left;
3250	}
3251
3252	void setup_revisions_from_strvec(struct strvec argv, struct rev_info revs,
3253	struct setup_revision_opt *opt)
3254	{
3255	struct setup_revision_opt fallback_opt;
3256	int ret;
3257
3258	if (!opt) {
3259	memset(&fallback_opt, 0, sizeof(fallback_opt));
3260	opt = &fallback_opt;
3261	}
3262	opt->free_removed_argv_elements = 1;
3263
3264	ret = setup_revisions(argv->nr, argv->v, revs, opt);
3265
3266	for (size_t i = ret; i < argv->nr; i++)
3267	free((char *)argv->v[i]);
3268	argv->nr = ret;
3269	}
3270
3271	static void release_revisions_cmdline(struct rev_cmdline_info *cmdline)
3272	{
3273	unsigned int i;
3274
3275	for (i = 0; i < cmdline->nr; i++)
3276	free((char *)cmdline->rev[i].name);
3277	free(cmdline->rev);
3278	}
3279
3280	static void release_revisions_mailmap(struct string_list *mailmap)
3281	{
3282	if (!mailmap)
3283	return;
3284	clear_mailmap(mailmap);
3285	free(mailmap);
3286	}
3287
3288	static void release_revisions_topo_walk_info(struct topo_walk_info *info);
3289
3290	static void release_revisions_bloom_keyvecs(struct rev_info *revs)
3291	{
3292	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
3293	bloom_keyvec_free(revs->bloom_keyvecs[nr]);
3294	FREE_AND_NULL(revs->bloom_keyvecs);
3295	revs->bloom_keyvecs_nr = 0;
3296	}
3297
3298	static void free_void_commit_list(void *list)
3299	{
3300	commit_list_free(list);
3301	}
3302
3303	void release_revisions(struct rev_info *revs)
3304	{
3305	commit_list_free(revs->commits);
3306	clear_prio_queue(&revs->commit_queue);
3307	commit_list_free(revs->ancestry_path_bottoms);
3308	release_display_notes(&revs->notes_opt);
3309	object_array_clear(&revs->pending);
3310	object_array_clear(&revs->boundary_commits);
3311	release_revisions_cmdline(&revs->cmdline);
3312	list_objects_filter_release(&revs->filter);
3313	clear_pathspec(&revs->prune_data);
3314	date_mode_release(&revs->date_mode);
3315	release_revisions_mailmap(revs->mailmap);
3316	free_grep_patterns(&revs->grep_filter);
3317	graph_clear(revs->graph);
3318	diff_free(&revs->diffopt);
3319	diff_free(&revs->pruning);
3320	reflog_walk_info_release(revs->reflog_info);
3321	release_revisions_topo_walk_info(revs->topo_walk_info);
3322	clear_decoration(&revs->children, free_void_commit_list);
3323	clear_decoration(&revs->merge_simplification, free);
3324	clear_decoration(&revs->treesame, free);
3325	line_log_free(revs);
3326	oidset_clear(&revs->missing_commits);
3327	release_revisions_bloom_keyvecs(revs);
3328	release_follow_pathspec_slab(revs);
3329	}
3330
3331	static void add_child(struct rev_info revs, struct commit parent, struct commit *child)
3332	{
3333	struct commit_list l = xcalloc(1, sizeof(l));
3334
3335	l->item = child;
3336	l->next = add_decoration(&revs->children, &parent->object, l);
3337	}
3338
3339	static int remove_duplicate_parents(struct rev_info revs, struct commit commit)
3340	{
3341	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
3342	struct commit_list *pp, p;
3343	int surviving_parents;
3344
3345	/* Examine existing parents while marking ones we have seen... */
3346	pp = &commit->parents;
3347	surviving_parents = 0;
3348	while ((p = *pp) != NULL) {
3349	struct commit *parent = p->item;
3350	if (parent->object.flags & TMP_MARK) {
3351	*pp = p->next;
3352	free(p);
3353	if (ts)
3354	compact_treesame(revs, commit, surviving_parents);
3355	continue;
3356	}
3357	parent->object.flags \|= TMP_MARK;
3358	surviving_parents++;
3359	pp = &p->next;
3360	}
3361	/* clear the temporary mark */
3362	for (p = commit->parents; p; p = p->next) {
3363	p->item->object.flags &= ~TMP_MARK;
3364	}
3365	/* no update_treesame() - removing duplicates can't affect TREESAME */
3366	return surviving_parents;
3367	}
3368
3369	struct merge_simplify_state {
3370	struct commit *simplified;
3371	};
3372
3373	static struct merge_simplify_state locate_simplify_state(struct rev_info revs, struct commit *commit)
3374	{
3375	struct merge_simplify_state *st;
3376
3377	st = lookup_decoration(&revs->merge_simplification, &commit->object);
3378	if (!st) {
3379	CALLOC_ARRAY(st, 1);
3380	add_decoration(&revs->merge_simplification, &commit->object, st);
3381	}
3382	return st;
3383	}
3384
3385	static int mark_redundant_parents(struct commit *commit)
3386	{
3387	struct commit_list *h = reduce_heads(commit->parents);
3388	int i = 0, marked = 0;
3389	struct commit_list po, pn;
3390
3391	/* Want these for sanity-checking only */
3392	int orig_cnt = commit_list_count(commit->parents);
3393	int cnt = commit_list_count(h);
3394
3395	/*
3396	* Not ready to remove items yet, just mark them for now, based
3397	* on the output of reduce_heads(). reduce_heads outputs the reduced
3398	* set in its original order, so this isn't too hard.
3399	*/
3400	po = commit->parents;
3401	pn = h;
3402	while (po) {
3403	if (pn && po->item == pn->item) {
3404	pn = pn->next;
3405	i++;
3406	} else {
3407	po->item->object.flags \|= TMP_MARK;
3408	marked++;
3409	}
3410	po=po->next;
3411	}
3412
3413	if (i != cnt \|\| cnt+marked != orig_cnt)
3414	die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked);
3415
3416	commit_list_free(h);
3417
3418	return marked;
3419	}
3420
3421	static int mark_treesame_root_parents(struct commit *commit)
3422	{
3423	struct commit_list *p;
3424	int marked = 0;
3425
3426	for (p = commit->parents; p; p = p->next) {
3427	struct commit *parent = p->item;
3428	if (!parent->parents && (parent->object.flags & TREESAME)) {
3429	parent->object.flags \|= TMP_MARK;
3430	marked++;
3431	}
3432	}
3433
3434	return marked;
3435	}
3436
3437	/*
3438	* Awkward naming - this means one parent we are TREESAME to.
3439	* cf mark_treesame_root_parents: root parents that are TREESAME (to an
3440	* empty tree). Better name suggestions?
3441	*/
3442	static int leave_one_treesame_to_parent(struct rev_info revs, struct commit commit)
3443	{
3444	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
3445	struct commit unmarked = NULL, marked = NULL;
3446	struct commit_list *p;
3447	unsigned n;
3448
3449	for (p = commit->parents, n = 0; p; p = p->next, n++) {
3450	if (ts->treesame[n]) {
3451	if (p->item->object.flags & TMP_MARK) {
3452	if (!marked)
3453	marked = p->item;
3454	} else {
3455	if (!unmarked) {
3456	unmarked = p->item;
3457	break;
3458	}
3459	}
3460	}
3461	}
3462
3463	/*
3464	* If we are TREESAME to a marked-for-deletion parent, but not to any
3465	* unmarked parents, unmark the first TREESAME parent. This is the
3466	* parent that the default simplify_history==1 scan would have followed,
3467	* and it doesn't make sense to omit that path when asking for a
3468	* simplified full history. Retaining it improves the chances of
3469	* understanding odd missed merges that took an old version of a file.
3470	*
3471	* Example:
3472	*
3473	* I--------*X A modified the file, but mainline merge X used
3474	* \ / "-s ours", so took the version from I. X is
3475	* `-*A--' TREESAME to I and !TREESAME to A.
3476	*
3477	* Default log from X would produce "I". Without this check,
3478	* --full-history --simplify-merges would produce "I-A-X", showing
3479	* the merge commit X and that it changed A, but not making clear that
3480	* it had just taken the I version. With this check, the topology above
3481	* is retained.
3482	*
3483	* Note that it is possible that the simplification chooses a different
3484	* TREESAME parent from the default, in which case this test doesn't
3485	* activate, and we _do_ drop the default parent. Example:
3486	*
3487	* I------X A modified the file, but it was reverted in B,
3488	* \ / meaning mainline merge X is TREESAME to both
3489	* A-B parents.
3490	*
3491	* Default log would produce "I" by following the first parent;
3492	* --full-history --simplify-merges will produce "I-A-B". But this is a
3493	* reasonable result - it presents a logical full history leading from
3494	* I to X, and X is not an important merge.
3495	*/
3496	if (!unmarked && marked) {
3497	marked->object.flags &= ~TMP_MARK;
3498	return 1;
3499	}
3500
3501	return 0;
3502	}
3503
3504	static int remove_marked_parents(struct rev_info revs, struct commit commit)
3505	{
3506	struct commit_list *pp, p;
3507	int nth_parent, removed = 0;
3508
3509	pp = &commit->parents;
3510	nth_parent = 0;
3511	while ((p = *pp) != NULL) {
3512	struct commit *parent = p->item;
3513	if (parent->object.flags & TMP_MARK) {
3514	parent->object.flags &= ~TMP_MARK;
3515	*pp = p->next;
3516	free(p);
3517	removed++;
3518	compact_treesame(revs, commit, nth_parent);
3519	continue;
3520	}
3521	pp = &p->next;
3522	nth_parent++;
3523	}
3524
3525	/* Removing parents can only increase TREESAMEness */
3526	if (removed && !(commit->object.flags & TREESAME))
3527	update_treesame(revs, commit);
3528
3529	return nth_parent;
3530	}
3531
3532	static struct commit_list *simplify_one(struct rev_info revs, struct commit commit, struct commit_list *tail)
3533	{
3534	struct commit_list *p;
3535	struct commit *parent;
3536	struct merge_simplify_state st, pst;
3537	int cnt;
3538
3539	st = locate_simplify_state(revs, commit);
3540
3541	/*
3542	* Have we handled this one?
3543	*/
3544	if (st->simplified)
3545	return tail;
3546
3547	/*
3548	* An UNINTERESTING commit simplifies to itself, so does a
3549	* root commit. We do not rewrite parents of such commit
3550	* anyway.
3551	*/
3552	if ((commit->object.flags & UNINTERESTING) \|\| !commit->parents) {
3553	st->simplified = commit;
3554	return tail;
3555	}
3556
3557	/*
3558	* Do we know what commit all of our parents that matter
3559	* should be rewritten to? Otherwise we are not ready to
3560	* rewrite this one yet.
3561	*/
3562	for (cnt = 0, p = commit->parents; p; p = p->next) {
3563	pst = locate_simplify_state(revs, p->item);
3564	if (!pst->simplified) {
3565	tail = &commit_list_insert(p->item, tail)->next;
3566	cnt++;
3567	}
3568	if (revs->first_parent_only)
3569	break;
3570	}
3571	if (cnt) {
3572	tail = &commit_list_insert(commit, tail)->next;
3573	return tail;
3574	}
3575
3576	/*
3577	* Rewrite our list of parents. Note that this cannot
3578	* affect our TREESAME flags in any way - a commit is
3579	* always TREESAME to its simplification.
3580	*/
3581	for (p = commit->parents; p; p = p->next) {
3582	pst = locate_simplify_state(revs, p->item);
3583	p->item = pst->simplified;
3584	if (revs->first_parent_only)
3585	break;
3586	}
3587
3588	if (revs->first_parent_only)
3589	cnt = 1;
3590	else
3591	cnt = remove_duplicate_parents(revs, commit);
3592
3593	/*
3594	* It is possible that we are a merge and one side branch
3595	* does not have any commit that touches the given paths;
3596	* in such a case, the immediate parent from that branch
3597	* will be rewritten to be the merge base.
3598	*
3599	* o----X X: the commit we are looking at;
3600	* / / o: a commit that touches the paths;
3601	* ---o----'
3602	*
3603	* Further, a merge of an independent branch that doesn't
3604	* touch the path will reduce to a treesame root parent:
3605	*
3606	* ----o----X X: the commit we are looking at;
3607	* / o: a commit that touches the paths;
3608	* r r: a root commit not touching the paths
3609	*
3610	* Detect and simplify both cases.
3611	*/
3612	if (1 < cnt) {
3613	int marked = mark_redundant_parents(commit);
3614	marked += mark_treesame_root_parents(commit);
3615	if (marked)
3616	marked -= leave_one_treesame_to_parent(revs, commit);
3617	if (marked)
3618	cnt = remove_marked_parents(revs, commit);
3619	}
3620
3621	/*
3622	* A commit simplifies to itself if it is a root, if it is
3623	* UNINTERESTING, if it touches the given paths, or if it is a
3624	* merge and its parents don't simplify to one relevant commit
3625	* (the first two cases are already handled at the beginning of
3626	* this function).
3627	*
3628	* Otherwise, it simplifies to what its sole relevant parent
3629	* simplifies to.
3630	*/
3631	if (!cnt \|\|
3632	(commit->object.flags & UNINTERESTING) \|\|
3633	!(commit->object.flags & TREESAME) \|\|
3634	(parent = one_relevant_parent(revs, commit->parents)) == NULL \|\|
3635	(revs->show_pulls && (commit->object.flags & PULL_MERGE)))
3636	st->simplified = commit;
3637	else {
3638	pst = locate_simplify_state(revs, parent);
3639	st->simplified = pst->simplified;
3640	}
3641	return tail;
3642	}
3643
3644	static void simplify_merges(struct rev_info *revs)
3645	{
3646	struct commit_list list, next;
3647	struct commit_list yet_to_do, *tail;
3648	struct commit *commit;
3649
3650	if (!revs->prune)
3651	return;
3652
3653	/* feed the list reversed */
3654	yet_to_do = NULL;
3655	for (list = revs->commits; list; list = next) {
3656	commit = list->item;
3657	next = list->next;
3658	/*
3659	* Do not free(list) here yet; the original list
3660	* is used later in this function.
3661	*/
3662	commit_list_insert(commit, &yet_to_do);
3663	}
3664	while (yet_to_do) {
3665	list = yet_to_do;
3666	yet_to_do = NULL;
3667	tail = &yet_to_do;
3668	while (list) {
3669	commit = pop_commit(&list);
3670	tail = simplify_one(revs, commit, tail);
3671	}
3672	}
3673
3674	/* clean up the result, removing the simplified ones */
3675	list = revs->commits;
3676	revs->commits = NULL;
3677	tail = &revs->commits;
3678	while (list) {
3679	struct merge_simplify_state *st;
3680
3681	commit = pop_commit(&list);
3682	st = locate_simplify_state(revs, commit);
3683	if (st->simplified == commit)
3684	tail = &commit_list_insert(commit, tail)->next;
3685	}
3686	}
3687
3688	static void set_children(struct rev_info *revs)
3689	{
3690	struct commit_list *l;
3691	for (l = revs->commits; l; l = l->next) {
3692	struct commit *commit = l->item;
3693	struct commit_list *p;
3694
3695	for (p = commit->parents; p; p = p->next)
3696	add_child(revs, p->item, commit);
3697	}
3698	}
3699
3700	void reset_revision_walk(void)
3701	{
3702	clear_object_flags(the_repository,
3703	SEEN \| ADDED \| SHOWN \| TOPO_WALK_EXPLORED \| TOPO_WALK_INDEGREE);
3704	}
3705
3706	static int mark_uninteresting(const struct object_id *oid,
3707	struct object_info *oi UNUSED,
3708	void *cb)
3709	{
3710	struct rev_info *revs = cb;
3711	struct object *o = lookup_unknown_object(revs->repo, oid);
3712	o->flags \|= UNINTERESTING \| SEEN;
3713	return 0;
3714	}
3715
3716	define_commit_slab(indegree_slab, int);
3717	define_commit_slab(author_date_slab, timestamp_t);
3718
3719	struct topo_walk_info {
3720	timestamp_t min_generation;
3721	struct prio_queue explore_queue;
3722	struct prio_queue indegree_queue;
3723	struct prio_queue topo_queue;
3724	struct indegree_slab indegree;
3725	struct author_date_slab author_date;
3726	};
3727
3728	static int topo_walk_atexit_registered;
3729	static unsigned int count_explore_walked;
3730	static unsigned int count_indegree_walked;
3731	static unsigned int count_topo_walked;
3732
3733	static void trace2_topo_walk_statistics_atexit(void)
3734	{
3735	struct json_writer jw = JSON_WRITER_INIT;
3736
3737	jw_object_begin(&jw, 0);
3738	jw_object_intmax(&jw, "count_explore_walked", count_explore_walked);
3739	jw_object_intmax(&jw, "count_indegree_walked", count_indegree_walked);
3740	jw_object_intmax(&jw, "count_topo_walked", count_topo_walked);
3741	jw_end(&jw);
3742
3743	trace2_data_json("topo_walk", the_repository, "statistics", &jw);
3744
3745	jw_release(&jw);
3746	}
3747
3748	static inline void test_flag_and_insert(struct prio_queue q, struct commit c, int flag)
3749	{
3750	if (c->object.flags & flag)
3751	return;
3752
3753	c->object.flags \|= flag;
3754	prio_queue_put(q, c);
3755	}
3756
3757	static void explore_walk_step(struct rev_info *revs)
3758	{
3759	struct topo_walk_info *info = revs->topo_walk_info;
3760	struct commit_list *p;
3761	struct commit *c = prio_queue_get(&info->explore_queue);
3762
3763	if (!c)
3764	return;
3765
3766	if (repo_parse_commit_gently(revs->repo, c, 1) < 0)
3767	return;
3768
3769	count_explore_walked++;
3770
3771	if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
3772	record_author_date(&info->author_date, c);
3773
3774	if (revs->max_age != -1 && (c->date < revs->max_age))
3775	c->object.flags \|= UNINTERESTING;
3776
3777	if (process_parents(revs, c, NULL) < 0)
3778	return;
3779
3780	if (c->object.flags & UNINTERESTING)
3781	mark_parents_uninteresting(revs, c);
3782
3783	for (p = c->parents; p; p = p->next)
3784	test_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);
3785	}
3786
3787	static void explore_to_depth(struct rev_info *revs,
3788	timestamp_t gen_cutoff)
3789	{
3790	struct topo_walk_info *info = revs->topo_walk_info;
3791	struct commit *c;
3792	while ((c = prio_queue_peek(&info->explore_queue)) &&
3793	commit_graph_generation(c) >= gen_cutoff)
3794	explore_walk_step(revs);
3795	}
3796
3797	static void indegree_walk_step(struct rev_info *revs)
3798	{
3799	struct commit_list *p;
3800	struct topo_walk_info *info = revs->topo_walk_info;
3801	struct commit *c = prio_queue_get(&info->indegree_queue);
3802
3803	if (!c)
3804	return;
3805
3806	if (repo_parse_commit_gently(revs->repo, c, 1) < 0)
3807	return;
3808
3809	count_indegree_walked++;
3810
3811	explore_to_depth(revs, commit_graph_generation(c));
3812
3813	for (p = c->parents; p; p = p->next) {
3814	struct commit *parent = p->item;
3815	int *pi = indegree_slab_at(&info->indegree, parent);
3816
3817	if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
3818	return;
3819
3820	if (*pi)
3821	(*pi)++;
3822	else
3823	*pi = 2;
3824
3825	test_flag_and_insert(&info->indegree_queue, parent, TOPO_WALK_INDEGREE);
3826
3827	if (revs->first_parent_only)
3828	return;
3829	}
3830	}
3831
3832	static void compute_indegrees_to_depth(struct rev_info *revs,
3833	timestamp_t gen_cutoff)
3834	{
3835	struct topo_walk_info *info = revs->topo_walk_info;
3836	struct commit *c;
3837	while ((c = prio_queue_peek(&info->indegree_queue)) &&
3838	commit_graph_generation(c) >= gen_cutoff)
3839	indegree_walk_step(revs);
3840	}
3841
3842	static void release_revisions_topo_walk_info(struct topo_walk_info *info)
3843	{
3844	if (!info)
3845	return;
3846	clear_prio_queue(&info->explore_queue);
3847	clear_prio_queue(&info->indegree_queue);
3848	clear_prio_queue(&info->topo_queue);
3849	clear_indegree_slab(&info->indegree);
3850	clear_author_date_slab(&info->author_date);
3851	free(info);
3852	}
3853
3854	static void reset_topo_walk(struct rev_info *revs)
3855	{
3856	release_revisions_topo_walk_info(revs->topo_walk_info);
3857	revs->topo_walk_info = NULL;
3858	}
3859
3860	static void init_topo_walk(struct rev_info *revs)
3861	{
3862	struct topo_walk_info *info;
3863	struct commit_list *list;
3864	if (revs->topo_walk_info)
3865	reset_topo_walk(revs);
3866
3867	revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info));
3868	info = revs->topo_walk_info;
3869	memset(info, 0, sizeof(struct topo_walk_info));
3870
3871	init_indegree_slab(&info->indegree);
3872	memset(&info->explore_queue, 0, sizeof(info->explore_queue));
3873	memset(&info->indegree_queue, 0, sizeof(info->indegree_queue));
3874	memset(&info->topo_queue, 0, sizeof(info->topo_queue));
3875
3876	switch (revs->sort_order) {
3877	default: /* REV_SORT_IN_GRAPH_ORDER */
3878	info->topo_queue.compare = NULL;
3879	break;
3880	case REV_SORT_BY_COMMIT_DATE:
3881	info->topo_queue.compare = compare_commits_by_commit_date;
3882	break;
3883	case REV_SORT_BY_AUTHOR_DATE:
3884	init_author_date_slab(&info->author_date);
3885	info->topo_queue.compare = compare_commits_by_author_date;
3886	info->topo_queue.cb_data = &info->author_date;
3887	break;
3888	}
3889
3890	info->explore_queue.compare = compare_commits_by_gen_then_commit_date;
3891	info->indegree_queue.compare = compare_commits_by_gen_then_commit_date;
3892
3893	info->min_generation = GENERATION_NUMBER_INFINITY;
3894	for (list = revs->commits; list; list = list->next) {
3895	struct commit *c = list->item;
3896	timestamp_t generation;
3897
3898	if (repo_parse_commit_gently(revs->repo, c, 1))
3899	continue;
3900
3901	test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);
3902	test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);
3903
3904	generation = commit_graph_generation(c);
3905	if (generation < info->min_generation)
3906	info->min_generation = generation;
3907
3908	*(indegree_slab_at(&info->indegree, c)) = 1;
3909
3910	if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
3911	record_author_date(&info->author_date, c);
3912	}
3913	compute_indegrees_to_depth(revs, info->min_generation);
3914
3915	for (list = revs->commits; list; list = list->next) {
3916	struct commit *c = list->item;
3917
3918	if (*(indegree_slab_at(&info->indegree, c)) == 1)
3919	prio_queue_put(&info->topo_queue, c);
3920	}
3921
3922	/*
3923	* This is unfortunate; the initial tips need to be shown
3924	* in the order given from the revision traversal machinery.
3925	*/
3926	if (revs->sort_order == REV_SORT_IN_GRAPH_ORDER)
3927	prio_queue_reverse(&info->topo_queue);
3928
3929	if (trace2_is_enabled() && !topo_walk_atexit_registered) {
3930	atexit(trace2_topo_walk_statistics_atexit);
3931	topo_walk_atexit_registered = 1;
3932	}
3933	}
3934
3935	static struct commit next_topo_commit(struct rev_info revs)
3936	{
3937	struct commit *c;
3938	struct topo_walk_info *info = revs->topo_walk_info;
3939
3940	/* pop next off of topo_queue */
3941	c = prio_queue_get(&info->topo_queue);
3942
3943	if (c)
3944	*(indegree_slab_at(&info->indegree, c)) = 0;
3945
3946	return c;
3947	}
3948
3949	static void expand_topo_walk(struct rev_info revs, struct commit commit)
3950	{
3951	struct commit_list *p;
3952	struct topo_walk_info *info = revs->topo_walk_info;
3953	if (process_parents(revs, commit, NULL) < 0) {
3954	if (!revs->ignore_missing_links)
3955	die("Failed to traverse parents of commit %s",
3956	oid_to_hex(&commit->object.oid));
3957	}
3958
3959	count_topo_walked++;
3960
3961	for (p = commit->parents; p; p = p->next) {
3962	struct commit *parent = p->item;
3963	int *pi;
3964	timestamp_t generation;
3965
3966	if (parent->object.flags & UNINTERESTING)
3967	continue;
3968
3969	if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
3970	continue;
3971
3972	generation = commit_graph_generation(parent);
3973	if (generation < info->min_generation) {
3974	info->min_generation = generation;
3975	compute_indegrees_to_depth(revs, info->min_generation);
3976	}
3977
3978	pi = indegree_slab_at(&info->indegree, parent);
3979
3980	(*pi)--;
3981	if (*pi == 1)
3982	prio_queue_put(&info->topo_queue, parent);
3983
3984	if (revs->first_parent_only)
3985	return;
3986	}
3987	}
3988
3989	void rev_info_commit_list_to_queue(struct rev_info *revs)
3990	{
3991	while (revs->commits)
3992	prio_queue_put(&revs->commit_queue, pop_commit(&revs->commits));
3993	}
3994
3995
3996	int prepare_revision_walk(struct rev_info *revs)
3997	{
3998	int i;
3999	struct object_array old_pending;
4000	struct commit_list **next = &revs->commits;
4001
4002	memcpy(&old_pending, &revs->pending, sizeof(old_pending));
4003	revs->pending.nr = 0;
4004	revs->pending.alloc = 0;
4005	revs->pending.objects = NULL;
4006	for (i = 0; i < old_pending.nr; i++) {
4007	struct object_array_entry *e = old_pending.objects + i;
4008	struct commit *commit = handle_commit(revs, e);
4009	if (commit) {
4010	if (!(commit->object.flags & SEEN)) {
4011	commit->object.flags \|= SEEN;
4012	next = commit_list_append(commit, next);
4013	}
4014	}
4015	}
4016	object_array_clear(&old_pending);
4017
4018	/* Signal whether we need per-parent treesame decoration */
4019	if (revs->simplify_merges \|\|
4020	(revs->limited && limiting_can_increase_treesame(revs)))
4021	revs->treesame.name = "treesame";
4022
4023	if (revs->exclude_promisor_objects)
4024	odb_for_each_object(revs->repo->objects, NULL, mark_uninteresting,
4025	revs, ODB_FOR_EACH_OBJECT_PROMISOR_ONLY);
4026
4027	if (!revs->reflog_info)
4028	prepare_to_use_bloom_filter(revs);
4029	if (!revs->unsorted_input)
4030	commit_list_sort_by_date(&revs->commits);
4031	if (revs->no_walk)
4032	return 0;
4033	if (revs->limited) {
4034	if (limit_list(revs) < 0)
4035	return -1;
4036	if (revs->topo_order)
4037	sort_in_topological_order(&revs->commits, revs->sort_order);
4038	} else if (revs->topo_order)
4039	init_topo_walk(revs);
4040	if (revs->line_level_traverse && want_ancestry(revs))
4041	/*
4042	* At the moment we can only do line-level log with parent
4043	* rewriting by performing this expensive pre-filtering step.
4044	* If parent rewriting is not requested, then we rather
4045	* perform the line-level log filtering during the regular
4046	* history traversal.
4047	*/
4048	line_log_filter(revs);
4049	if (revs->simplify_merges)
4050	simplify_merges(revs);
4051	if (revs->children.name)
4052	set_children(revs);
4053
4054	return 0;
4055	}
4056
4057	static enum rewrite_result rewrite_one_1(struct rev_info *revs,
4058	struct commit **pp,
4059	struct prio_queue *queue)
4060	{
4061	for (;;) {
4062	struct commit p = pp;
4063	if (!revs->limited)
4064	if (process_parents(revs, p, queue) < 0)
4065	return rewrite_one_error;
4066	if (p->object.flags & UNINTERESTING)
4067	return rewrite_one_ok;
4068	if (!(p->object.flags & TREESAME))
4069	return rewrite_one_ok;
4070	if (!p->parents)
4071	return rewrite_one_noparents;
4072	if (!(p = one_relevant_parent(revs, p->parents)))
4073	return rewrite_one_ok;
4074	*pp = p;
4075	}
4076	}
4077
4078	static void merge_queue_into_prio_queue(struct prio_queue *from,
4079	struct prio_queue *to)
4080	{
4081	struct commit *item;
4082	while ((item = prio_queue_get(from)))
4083	prio_queue_put(to, item);
4084	}
4085
4086	static enum rewrite_result rewrite_one(struct rev_info revs, struct commit *pp)
4087	{
4088	struct prio_queue queue = { compare_commits_by_commit_date };
4089	enum rewrite_result ret = rewrite_one_1(revs, pp, &queue);
4090	merge_queue_into_prio_queue(&queue, &revs->commit_queue);
4091	clear_prio_queue(&queue);
4092	return ret;
4093	}
4094
4095	int rewrite_parents(struct rev_info revs, struct commit commit,
4096	rewrite_parent_fn_t rewrite_parent)
4097	{
4098	struct commit_list **pp = &commit->parents;
4099	while (*pp) {
4100	struct commit_list parent = pp;
4101	switch (rewrite_parent(revs, &parent->item)) {
4102	case rewrite_one_ok:
4103	break;
4104	case rewrite_one_noparents:
4105	*pp = parent->next;
4106	free(parent);
4107	continue;
4108	case rewrite_one_error:
4109	return -1;
4110	}
4111	pp = &parent->next;
4112	}
4113	remove_duplicate_parents(revs, commit);
4114	return 0;
4115	}
4116
4117	static int commit_match(struct commit commit, struct rev_info opt)
4118	{
4119	int retval;
4120	const char *encoding;
4121	const char *message;
4122	struct strbuf buf = STRBUF_INIT;
4123
4124	if (!opt->grep_filter.pattern_list && !opt->grep_filter.header_list)
4125	return 1;
4126
4127	/* Prepend "fake" headers as needed */
4128	if (opt->grep_filter.use_reflog_filter) {
4129	strbuf_addstr(&buf, "reflog ");
4130	get_reflog_message(&buf, opt->reflog_info);
4131	strbuf_addch(&buf, '\n');
4132	}
4133
4134	/*
4135	* We grep in the user's output encoding, under the assumption that it
4136	* is the encoding they are most likely to write their grep pattern
4137	* for. In addition, it means we will match the "notes" encoding below,
4138	* so we will not end up with a buffer that has two different encodings
4139	* in it.
4140	*/
4141	encoding = get_log_output_encoding();
4142	message = repo_logmsg_reencode(the_repository, commit, NULL, encoding);
4143
4144	/* Copy the commit to temporary if we are using "fake" headers */
4145	if (buf.len)
4146	strbuf_addstr(&buf, message);
4147
4148	if (opt->grep_filter.header_list && opt->mailmap) {
4149	const char *commit_headers[] = { "author ", "committer ", NULL };
4150
4151	if (!buf.len)
4152	strbuf_addstr(&buf, message);
4153
4154	apply_mailmap_to_header(&buf, commit_headers, opt->mailmap);
4155	}
4156
4157	/* Append "fake" message parts as needed */
4158	if (opt->show_notes) {
4159	if (!buf.len)
4160	strbuf_addstr(&buf, message);
4161	format_display_notes(&commit->object.oid, &buf, encoding, 1);
4162	}
4163
4164	/*
4165	* Find either in the original commit message, or in the temporary.
4166	* Note that we cast away the constness of "message" here. It is
4167	* const because it may come from the cached commit buffer. That's OK,
4168	* because we know that it is modifiable heap memory, and that while
4169	* grep_buffer may modify it for speed, it will restore any
4170	* changes before returning.
4171	*/
4172	if (buf.len)
4173	retval = grep_buffer(&opt->grep_filter, buf.buf, buf.len);
4174	else
4175	retval = grep_buffer(&opt->grep_filter,
4176	(char *)message, strlen(message));
4177	strbuf_release(&buf);
4178	repo_unuse_commit_buffer(the_repository, commit, message);
4179	return retval;
4180	}
4181
4182	static inline int want_ancestry(const struct rev_info *revs)
4183	{
4184	return (revs->rewrite_parents \|\| revs->children.name);
4185	}
4186
4187	/*
4188	* Return a timestamp to be used for --since/--until comparisons for this
4189	* commit, based on the revision options.
4190	*/
4191	static timestamp_t comparison_date(const struct rev_info *revs,
4192	struct commit *commit)
4193	{
4194	return revs->reflog_info ?
4195	get_reflog_timestamp(revs->reflog_info) :
4196	commit->date;
4197	}
4198
4199	enum commit_action get_commit_action(struct rev_info revs, struct commit commit)
4200	{
4201	if (commit->object.flags & SHOWN)
4202	return commit_ignore;
4203	if (revs->maximal_only && (commit->object.flags & CHILD_VISITED))
4204	return commit_ignore;
4205	if (revs->unpacked && has_object_pack(revs->repo, &commit->object.oid))
4206	return commit_ignore;
4207	if (revs->no_kept_objects) {
4208	if (has_object_kept_pack(revs->repo, &commit->object.oid,
4209	revs->keep_pack_cache_flags))
4210	return commit_ignore;
4211	}
4212	if (commit->object.flags & UNINTERESTING)
4213	return commit_ignore;
4214	if (revs->line_level_traverse && !want_ancestry(revs)) {
4215	/*
4216	* In case of line-level log with parent rewriting
4217	* prepare_revision_walk() already took care of all line-level
4218	* log filtering, and there is nothing left to do here.
4219	*
4220	* If parent rewriting was not requested, then this is the
4221	* place to perform the line-level log filtering. Notably,
4222	* this check, though expensive, must come before the other,
4223	* cheaper filtering conditions, because the tracked line
4224	* ranges must be adjusted even when the commit will end up
4225	* being ignored based on other conditions.
4226	*/
4227	if (!line_log_process_ranges_arbitrary_commit(revs, commit))
4228	return commit_ignore;
4229	}
4230	if (revs->min_age != -1 &&
4231	comparison_date(revs, commit) > revs->min_age)
4232	return commit_ignore;
4233	if (revs->max_age_as_filter != -1 &&
4234	comparison_date(revs, commit) < revs->max_age_as_filter)
4235	return commit_ignore;
4236	if (revs->min_parents \|\| (revs->max_parents >= 0)) {
4237	int n = commit_list_count(commit->parents);
4238	if ((n < revs->min_parents) \|\|
4239	((revs->max_parents >= 0) && (n > revs->max_parents)))
4240	return commit_ignore;
4241	}
4242	if (!commit_match(commit, revs))
4243	return commit_ignore;
4244	if (revs->prune && revs->dense) {
4245	/* Commit without changes? */
4246	if (commit->object.flags & TREESAME) {
4247	int n;
4248	struct commit_list *p;
4249	/* drop merges unless we want parenthood */
4250	if (!want_ancestry(revs))
4251	return commit_ignore;
4252
4253	if (revs->show_pulls && (commit->object.flags & PULL_MERGE))
4254	return commit_show;
4255
4256	/*
4257	* If we want ancestry, then need to keep any merges
4258	* between relevant commits to tie together topology.
4259	* For consistency with TREESAME and simplification
4260	* use "relevant" here rather than just INTERESTING,
4261	* to treat bottom commit(s) as part of the topology.
4262	*/
4263	for (n = 0, p = commit->parents; p; p = p->next)
4264	if (relevant_commit(p->item))
4265	if (++n >= 2)
4266	return commit_show;
4267	return commit_ignore;
4268	}
4269	}
4270	return commit_show;
4271	}
4272
4273	define_commit_slab(saved_parents, struct commit_list *);
4274
4275	#define EMPTY_PARENT_LIST ((struct commit_list *)-1)
4276
4277	/*
4278	* You may only call save_parents() once per commit (this is checked
4279	* for non-root commits).
4280	*/
4281	static void save_parents(struct rev_info revs, struct commit commit)
4282	{
4283	struct commit_list **pp;
4284
4285	if (!revs->saved_parents_slab) {
4286	revs->saved_parents_slab = xmalloc(sizeof(struct saved_parents));
4287	init_saved_parents(revs->saved_parents_slab);
4288	}
4289
4290	pp = saved_parents_at(revs->saved_parents_slab, commit);
4291
4292	/*
4293	* When walking with reflogs, we may visit the same commit
4294	* several times: once for each appearance in the reflog.
4295	*
4296	* In this case, save_parents() will be called multiple times.
4297	* We want to keep only the first set of parents. We need to
4298	* store a sentinel value for an empty (i.e., NULL) parent
4299	* list to distinguish it from a not-yet-saved list, however.
4300	*/
4301	if (*pp)
4302	return;
4303	if (commit->parents)
4304	*pp = commit_list_copy(commit->parents);
4305	else
4306	*pp = EMPTY_PARENT_LIST;
4307	}
4308
4309	static void free_saved_parent(struct commit_list **parents)
4310	{
4311	if (*parents != EMPTY_PARENT_LIST)
4312	commit_list_free(*parents);
4313	}
4314
4315	static void free_saved_parents(struct rev_info *revs)
4316	{
4317	if (!revs->saved_parents_slab)
4318	return;
4319	deep_clear_saved_parents(revs->saved_parents_slab, free_saved_parent);
4320	FREE_AND_NULL(revs->saved_parents_slab);
4321	}
4322
4323	struct commit_list get_saved_parents(struct rev_info revs, const struct commit *commit)
4324	{
4325	struct commit_list *parents;
4326
4327	if (!revs->saved_parents_slab)
4328	return commit->parents;
4329
4330	parents = *saved_parents_at(revs->saved_parents_slab, commit);
4331	if (parents == EMPTY_PARENT_LIST)
4332	return NULL;
4333	return parents;
4334	}
4335
4336	enum commit_action simplify_commit(struct rev_info revs, struct commit commit)
4337	{
4338	enum commit_action action = get_commit_action(revs, commit);
4339
4340	if (action == commit_show &&
4341	revs->prune && revs->dense && want_ancestry(revs)) {
4342	/*
4343	* --full-diff on simplified parents is no good: it
4344	* will show spurious changes from the commits that
4345	* were elided. So we save the parents on the side
4346	* when --full-diff is in effect.
4347	*/
4348	if (revs->full_diff)
4349	save_parents(revs, commit);
4350	if (rewrite_parents(revs, commit, rewrite_one) < 0)
4351	return commit_error;
4352	}
4353	return action;
4354	}
4355
4356	static void track_linear(struct rev_info revs, struct commit commit)
4357	{
4358	if (revs->track_first_time) {
4359	revs->linear = 1;
4360	revs->track_first_time = 0;
4361	} else {
4362	struct commit_list *p;
4363	for (p = revs->previous_parents; p; p = p->next)
4364	if (p->item == NULL \|\| /* first commit */
4365	oideq(&p->item->object.oid, &commit->object.oid))
4366	break;
4367	revs->linear = p != NULL;
4368	}
4369	if (revs->reverse) {
4370	if (revs->linear)
4371	commit->object.flags \|= TRACK_LINEAR;
4372	}
4373	commit_list_free(revs->previous_parents);
4374	revs->previous_parents = commit_list_copy(commit->parents);
4375	}
4376
4377	enum rev_walk_mode {
4378	REV_WALK_REFLOG,
4379	REV_WALK_TOPO,
4380	REV_WALK_LIMITED,
4381	REV_WALK_NO_WALK,
4382	REV_WALK_STREAMING,
4383	};
4384
4385	static enum rev_walk_mode get_walk_mode(struct rev_info *revs)
4386	{
4387	if (revs->reflog_info)
4388	return REV_WALK_REFLOG;
4389	if (revs->topo_walk_info)
4390	return REV_WALK_TOPO;
4391	if (revs->limited)
4392	return REV_WALK_LIMITED;
4393	if (revs->no_walk)
4394	return REV_WALK_NO_WALK;
4395	return REV_WALK_STREAMING;
4396	}
4397
4398	static struct commit get_revision_1(struct rev_info revs)
4399	{
4400	enum rev_walk_mode mode = get_walk_mode(revs);
4401
4402	if (mode == REV_WALK_STREAMING && revs->commits)
4403	rev_info_commit_list_to_queue(revs);
4404
4405	while (1) {
4406	struct commit *commit;
4407
4408	switch (mode) {
4409	case REV_WALK_REFLOG:
4410	commit = next_reflog_entry(revs->reflog_info);
4411	break;
4412	case REV_WALK_TOPO:
4413	commit = next_topo_commit(revs);
4414	break;
4415	case REV_WALK_LIMITED:
4416	case REV_WALK_NO_WALK:
4417	commit = pop_commit(&revs->commits);
4418	break;
4419	case REV_WALK_STREAMING:
4420	commit = prio_queue_get(&revs->commit_queue);
4421	break;
4422	}
4423
4424	if (!commit)
4425	return NULL;
4426
4427	if (mode == REV_WALK_REFLOG)
4428	commit->object.flags &= ~(ADDED \| SEEN \| SHOWN);
4429
4430	/*
4431	* If we haven't done the list limiting, we need to look at
4432	* the parents here. We also need to do the date-based limiting
4433	* that we'd otherwise have done in limit_list().
4434	*/
4435	if (mode != REV_WALK_LIMITED &&
4436	revs->max_age != -1 &&
4437	comparison_date(revs, commit) < revs->max_age)
4438	continue;
4439
4440	switch (mode) {
4441	case REV_WALK_REFLOG:
4442	case REV_WALK_NO_WALK:
4443	try_to_simplify_commit(revs, commit);
4444	break;
4445	case REV_WALK_TOPO:
4446	expand_topo_walk(revs, commit);
4447	break;
4448	case REV_WALK_STREAMING:
4449	if (process_parents(revs, commit,
4450	&revs->commit_queue) < 0) {
4451	if (!revs->ignore_missing_links)
4452	die("Failed to traverse parents of commit %s",
4453	oid_to_hex(&commit->object.oid));
4454	}
4455	break;
4456	case REV_WALK_LIMITED:
4457	break;
4458	}
4459
4460	switch (simplify_commit(revs, commit)) {
4461	case commit_ignore:
4462	continue;
4463	case commit_error:
4464	die("Failed to simplify parents of commit %s",
4465	oid_to_hex(&commit->object.oid));
4466	default:
4467	if (revs->track_linear)
4468	track_linear(revs, commit);
4469	return commit;
4470	}
4471	}
4472	}
4473
4474	/*
4475	* Return true for entries that have not yet been shown. (This is an
4476	* object_array_each_func_t.)
4477	*/
4478	static int entry_unshown(struct object_array_entry entry, void cb_data UNUSED)
4479	{
4480	return !(entry->item->flags & SHOWN);
4481	}
4482
4483	/*
4484	* If array is on the verge of a realloc, garbage-collect any entries
4485	* that have already been shown to try to free up some space.
4486	*/
4487	static void gc_boundary(struct object_array *array)
4488	{
4489	if (array->nr == array->alloc)
4490	object_array_filter(array, entry_unshown, NULL);
4491	}
4492
4493	static void create_boundary_commit_list(struct rev_info *revs)
4494	{
4495	unsigned i;
4496	struct commit *c;
4497	struct object_array *array = &revs->boundary_commits;
4498	struct object_array_entry *objects = array->objects;
4499
4500	/*
4501	* If revs->commits is non-NULL at this point, an error occurred in
4502	* get_revision_1(). Ignore the error and continue printing the
4503	* boundary commits anyway. (This is what the code has always
4504	* done.)
4505	*/
4506	commit_list_free(revs->commits);
4507	revs->commits = NULL;
4508
4509	/*
4510	* Put all of the actual boundary commits from revs->boundary_commits
4511	* into revs->commits
4512	*/
4513	for (i = 0; i < array->nr; i++) {
4514	c = (struct commit *)(objects[i].item);
4515	if (!c)
4516	continue;
4517	if (!(c->object.flags & CHILD_SHOWN))
4518	continue;
4519	if (c->object.flags & (SHOWN \| BOUNDARY))
4520	continue;
4521	c->object.flags \|= BOUNDARY;
4522	commit_list_insert(c, &revs->commits);
4523	}
4524
4525	/*
4526	* If revs->topo_order is set, sort the boundary commits
4527	* in topological order
4528	*/
4529	sort_in_topological_order(&revs->commits, revs->sort_order);
4530	}
4531
4532	static struct commit get_revision_internal(struct rev_info revs)
4533	{
4534	struct commit *c = NULL;
4535	struct commit_list *l;
4536
4537	if (revs->boundary == 2) {
4538	/*
4539	* All of the normal commits have already been returned,
4540	* and we are now returning boundary commits.
4541	* create_boundary_commit_list() has populated
4542	* revs->commits with the remaining commits to return.
4543	*/
4544	c = pop_commit(&revs->commits);
4545	if (c)
4546	c->object.flags \|= SHOWN;
4547	return c;
4548	}
4549
4550	/*
4551	* If our max_count counter has reached zero, then we are done. We
4552	* don't simply return NULL because we still might need to show
4553	* boundary commits. But we want to avoid calling get_revision_1, which
4554	* might do a considerable amount of work finding the next commit only
4555	* for us to throw it away.
4556	*
4557	* If it is non-zero, then either we don't have a max_count at all
4558	* (-1), or it is still counting, in which case we decrement.
4559	*/
4560	if (revs->max_count) {
4561	c = get_revision_1(revs);
4562	if (c) {
4563	while (revs->skip_count > 0) {
4564	revs->skip_count--;
4565	c = get_revision_1(revs);
4566	if (!c)
4567	break;
4568	free_commit_buffer(revs->repo->parsed_objects, c);
4569	}
4570	}
4571
4572	if (revs->max_count > 0)
4573	revs->max_count--;
4574	}
4575
4576	if (c)
4577	c->object.flags \|= SHOWN;
4578
4579	if (!revs->boundary)
4580	return c;
4581
4582	if (!c) {
4583	/*
4584	* get_revision_1() runs out the commits, and
4585	* we are done computing the boundaries.
4586	* switch to boundary commits output mode.
4587	*/
4588	revs->boundary = 2;
4589
4590	/*
4591	* Update revs->commits to contain the list of
4592	* boundary commits.
4593	*/
4594	create_boundary_commit_list(revs);
4595
4596	return get_revision_internal(revs);
4597	}
4598
4599	/*
4600	* boundary commits are the commits that are parents of the
4601	* ones we got from get_revision_1() but they themselves are
4602	* not returned from get_revision_1(). Before returning
4603	* 'c', we need to mark its parents that they could be boundaries.
4604	*/
4605
4606	for (l = c->parents; l; l = l->next) {
4607	struct object *p;
4608	p = &(l->item->object);
4609	if (p->flags & (CHILD_SHOWN \| SHOWN))
4610	continue;
4611	p->flags \|= CHILD_SHOWN;
4612	gc_boundary(&revs->boundary_commits);
4613	add_object_array(p, NULL, &revs->boundary_commits);
4614	}
4615
4616	return c;
4617	}
4618
4619	static void retrieve_oldest_commits(struct rev_info *revs,
4620	struct commit_list **queue)
4621	{
4622	struct commit *c;
4623	int max_count = revs->max_count;
4624	int queuei_count = 0;
4625	int queueo_count = 0;
4626	struct commit_list *queueo = NULL;
4627	struct commit_list *queuei = NULL;
4628	struct commit_list *reversed_queue = NULL;
4629	struct commit_list *p;
4630
4631	revs->max_count = -1;
4632	while ((c = get_revision_internal(revs))) {
4633	/*
4634	* We need to reset SHOWN status otherwise --graph breaks.
4635	* It is fine to do, get_revision_internal() doesn't consider
4636	* children commits as they have been already processed and the
4637	* traversal happens only child to parent.
4638	*
4639	* We do this because the --graph machinery relies on the status
4640	* of the parents to decide how the printing will happen.
4641	*
4642	* We can't simply replace this instruction with a
4643	* graph_update() as it doesn't do the actualy printing, we'd
4644	* have to remove any commit that goes over the
4645	* --max-count-oldest limit from revs->graph.
4646	*/
4647	c->object.flags &= ~(SHOWN \| CHILD_SHOWN);
4648	commit_list_insert(c, &queuei);
4649	if (!(c->object.flags & BOUNDARY))
4650	queuei_count++;
4651	while (queuei_count + queueo_count > max_count) {
4652	if (!queueo_count) {
4653	while ((c = pop_commit(&queuei))) {
4654	commit_list_insert(c, &queueo);
4655	queueo_count++;
4656	}
4657	queuei_count = 0;
4658	}
4659	c = pop_commit(&queueo);
4660	queueo_count--;
4661	/* We need to do this otherwise we'll discard the
4662	* commits that go over the --max-count-oldest limit but
4663	* not their respective boundaries. This matters only if
4664	* we're discarding the commit right before the boundary.
4665	*/
4666	for (p = c->parents; p; p = p->next)
4667	p->item->object.flags &= ~CHILD_SHOWN;
4668	}
4669	}
4670
4671	while ((c = pop_commit(&queueo)))
4672	commit_list_insert(c, &reversed_queue);
4673	while ((c = pop_commit(&queuei)))
4674	commit_list_insert(c, &queueo);
4675	while ((c = pop_commit(&queueo)))
4676	commit_list_insert(c, &reversed_queue);
4677
4678	while ((c = pop_commit(&reversed_queue)))
4679	commit_list_insert(c, queue);
4680	}
4681
4682	/*
4683	* Returns the next commit that will be shown, regardless of whether it comes
4684	* directly from the revision walk or from the list saved by the staged output
4685	* of --max-count-oldest.
4686	*/
4687	static struct commit next_commit_to_show(struct rev_info revs)
4688	{
4689	struct commit *c;
4690	struct commit_list *p;
4691
4692	if (!revs->max_count_stage)
4693	return get_revision_internal(revs);
4694
4695	c = pop_commit(&revs->commits);
4696	if (c) {
4697	c->object.flags \|= SHOWN;
4698	if (!(c->object.flags & BOUNDARY))
4699	for (p = c->parents; p; p = p->next)
4700	p->item->object.flags \|= CHILD_SHOWN;
4701	}
4702	return c;
4703	}
4704
4705	struct commit get_revision(struct rev_info revs)
4706	{
4707	struct commit *c;
4708	struct commit_list *reversed;
4709	struct commit_list *queue = NULL;
4710
4711	if (revs->max_count_type == 1 && !revs->max_count_stage) {
4712	retrieve_oldest_commits(revs, &queue);
4713	commit_list_free(revs->commits);
4714	revs->commits = queue;
4715	revs->max_count_stage = 1;
4716	}
4717
4718	if (revs->reverse) {
4719	reversed = NULL;
4720	if (revs->max_count_type == 1)
4721	while ((c = pop_commit(&revs->commits)))
4722	commit_list_insert(c, &reversed);
4723	else
4724	while ((c = get_revision_internal(revs)))
4725	commit_list_insert(c, &reversed);
4726	commit_list_free(revs->commits);
4727	revs->commits = reversed;
4728	revs->reverse = 0;
4729	revs->reverse_output_stage = 1;
4730	}
4731
4732	if (revs->reverse_output_stage) {
4733	c = pop_commit(&revs->commits);
4734	if (revs->track_linear)
4735	revs->linear = !!(c && c->object.flags & TRACK_LINEAR);
4736	return c;
4737	}
4738
4739	if (revs->graph) {
4740	c = graph_pop_lookahead(revs->graph);
4741	if (!c)
4742	c = next_commit_to_show(revs);
4743	} else {
4744	c = next_commit_to_show(revs);
4745	}
4746
4747	if (c && revs->graph) {
4748	while (graph_get_lookahead_room(revs->graph)) {
4749	struct commit *next = next_commit_to_show(revs);
4750	if (!next)
4751	break;
4752	graph_push_lookahead(revs->graph, next);
4753	}
4754	graph_update(revs->graph, c);
4755	}
4756
4757	if (!c) {
4758	free_saved_parents(revs);
4759	commit_list_free(revs->previous_parents);
4760	revs->previous_parents = NULL;
4761	}
4762	return c;
4763	}
4764
4765	const char get_revision_mark(const struct rev_info revs, const struct commit *commit)
4766	{
4767	if (commit->object.flags & BOUNDARY)
4768	return "-";
4769	else if (commit->object.flags & UNINTERESTING)
4770	return "^";
4771	else if (commit->object.flags & PATCHSAME)
4772	return "=";
4773	else if (!revs \|\| revs->left_right) {
4774	if (commit->object.flags & SYMMETRIC_LEFT)
4775	return "<";
4776	else
4777	return ">";
4778	} else if (revs->graph)
4779	return "*";
4780	else if (revs->cherry_mark)
4781	return "+";
4782	return "";
4783	}
4784
4785	void put_revision_mark(const struct rev_info revs, const struct commit commit)
4786	{
4787	const char *mark = get_revision_mark(revs, commit);
4788	if (!strlen(mark))
4789	return;
4790	fputs(mark, stdout);
4791	putchar(' ');
4792	}