git

1
#define USE_THE_REPOSITORY_VARIABLE
2

3
#include "git-compat-util.h"
4
#include "config.h"
5
#include "environment.h"
6
#include "gettext.h"
7
#include "hex.h"
8
#include "object-name.h"
9
#include "object-file.h"
10
#include "object-store-ll.h"
11
#include "oidset.h"
12
#include "tag.h"
13
#include "blob.h"
14
#include "tree.h"
15
#include "commit.h"
16
#include "diff.h"
17
#include "diff-merges.h"
18
#include "refs.h"
19
#include "revision.h"
20
#include "repository.h"
21
#include "graph.h"
22
#include "grep.h"
23
#include "reflog-walk.h"
24
#include "patch-ids.h"
25
#include "decorate.h"
26
#include "string-list.h"
27
#include "line-log.h"
28
#include "mailmap.h"
29
#include "commit-slab.h"
30
#include "cache-tree.h"
31
#include "bisect.h"
32
#include "packfile.h"
33
#include "worktree.h"
34
#include "path.h"
35
#include "read-cache.h"
36
#include "setup.h"
37
#include "sparse-index.h"
38
#include "strvec.h"
39
#include "trace2.h"
40
#include "commit-reach.h"
41
#include "commit-graph.h"
42
#include "prio-queue.h"
43
#include "hashmap.h"
44
#include "utf8.h"
45
#include "bloom.h"
46
#include "json-writer.h"
47
#include "list-objects-filter-options.h"
48
#include "resolve-undo.h"
49
#include "parse-options.h"
50
#include "wildmatch.h"
51

52
volatile show_early_output_fn_t show_early_output;
53

54
static const char *term_bad;
55
static const 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
void show_object_with_name(FILE *out, struct object *obj, const char *name)
62
{
63
	fprintf(out, "%s ", oid_to_hex(&obj->oid));
64
	for (const char *p = name; *p && *p != '\n'; p++)
65
		fputc(*p, out);
66
	fputc('\n', out);
67
}
68

69
static void mark_blob_uninteresting(struct blob *blob)
70
{
71
	if (!blob)
72
		return;
73
	if (blob->object.flags & UNINTERESTING)
74
		return;
75
	blob->object.flags |= UNINTERESTING;
76
}
77

78
static void mark_tree_contents_uninteresting(struct repository *r,
79
					     struct tree *tree)
80
{
81
	struct tree_desc desc;
82
	struct name_entry entry;
83

84
	if (parse_tree_gently(tree, 1) < 0)
85
		return;
86

87
	init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);
88
	while (tree_entry(&desc, &entry)) {
89
		switch (object_type(entry.mode)) {
90
		case OBJ_TREE:
91
			mark_tree_uninteresting(r, lookup_tree(r, &entry.oid));
92
			break;
93
		case OBJ_BLOB:
94
			mark_blob_uninteresting(lookup_blob(r, &entry.oid));
95
			break;
96
		default:
97
			/* Subproject commit - not in this repository */
98
			break;
99
		}
100
	}
101

102
	/*
103
	 * We don't care about the tree any more
104
	 * after it has been marked uninteresting.
105
	 */
106
	free_tree_buffer(tree);
107
}
108

109
void mark_tree_uninteresting(struct repository *r, struct tree *tree)
110
{
111
	struct object *obj;
112

113
	if (!tree)
114
		return;
115

116
	obj = &tree->object;
117
	if (obj->flags & UNINTERESTING)
118
		return;
119
	obj->flags |= UNINTERESTING;
120
	mark_tree_contents_uninteresting(r, tree);
121
}
122

123
struct path_and_oids_entry {
124
	struct hashmap_entry ent;
125
	char *path;
126
	struct oidset trees;
127
};
128

129
static int path_and_oids_cmp(const void *hashmap_cmp_fn_data UNUSED,
130
			     const struct hashmap_entry *eptr,
131
			     const struct hashmap_entry *entry_or_key,
132
			     const void *keydata UNUSED)
133
{
134
	const struct path_and_oids_entry *e1, *e2;
135

136
	e1 = container_of(eptr, const struct path_and_oids_entry, ent);
137
	e2 = container_of(entry_or_key, const struct path_and_oids_entry, ent);
138

139
	return strcmp(e1->path, e2->path);
140
}
141

142
static void paths_and_oids_clear(struct hashmap *map)
143
{
144
	struct hashmap_iter iter;
145
	struct path_and_oids_entry *entry;
146

147
	hashmap_for_each_entry(map, &iter, entry, ent /* member name */) {
148
		oidset_clear(&entry->trees);
149
		free(entry->path);
150
	}
151

152
	hashmap_clear_and_free(map, struct path_and_oids_entry, ent);
153
}
154

155
static void paths_and_oids_insert(struct hashmap *map,
156
				  const char *path,
157
				  const struct object_id *oid)
158
{
159
	int hash = strhash(path);
160
	struct path_and_oids_entry key;
161
	struct path_and_oids_entry *entry;
162

163
	hashmap_entry_init(&key.ent, hash);
164

165
	/* use a shallow copy for the lookup */
166
	key.path = (char *)path;
167
	oidset_init(&key.trees, 0);
168

169
	entry = hashmap_get_entry(map, &key, ent, NULL);
170
	if (!entry) {
171
		CALLOC_ARRAY(entry, 1);
172
		hashmap_entry_init(&entry->ent, hash);
173
		entry->path = xstrdup(key.path);
174
		oidset_init(&entry->trees, 16);
175
		hashmap_put(map, &entry->ent);
176
	}
177

178
	oidset_insert(&entry->trees, oid);
179
}
180

181
static void add_children_by_path(struct repository *r,
182
				 struct tree *tree,
183
				 struct hashmap *map)
184
{
185
	struct tree_desc desc;
186
	struct name_entry entry;
187

188
	if (!tree)
189
		return;
190

191
	if (parse_tree_gently(tree, 1) < 0)
192
		return;
193

194
	init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);
195
	while (tree_entry(&desc, &entry)) {
196
		switch (object_type(entry.mode)) {
197
		case OBJ_TREE:
198
			paths_and_oids_insert(map, entry.path, &entry.oid);
199

200
			if (tree->object.flags & UNINTERESTING) {
201
				struct tree *child = lookup_tree(r, &entry.oid);
202
				if (child)
203
					child->object.flags |= UNINTERESTING;
204
			}
205
			break;
206
		case OBJ_BLOB:
207
			if (tree->object.flags & UNINTERESTING) {
208
				struct blob *child = lookup_blob(r, &entry.oid);
209
				if (child)
210
					child->object.flags |= UNINTERESTING;
211
			}
212
			break;
213
		default:
214
			/* Subproject commit - not in this repository */
215
			break;
216
		}
217
	}
218

219
	free_tree_buffer(tree);
220
}
221

222
void mark_trees_uninteresting_sparse(struct repository *r,
223
				     struct oidset *trees)
224
{
225
	unsigned has_interesting = 0, has_uninteresting = 0;
226
	struct hashmap map = HASHMAP_INIT(path_and_oids_cmp, NULL);
227
	struct hashmap_iter map_iter;
228
	struct path_and_oids_entry *entry;
229
	struct object_id *oid;
230
	struct oidset_iter iter;
231

232
	oidset_iter_init(trees, &iter);
233
	while ((!has_interesting || !has_uninteresting) &&
234
	       (oid = oidset_iter_next(&iter))) {
235
		struct tree *tree = lookup_tree(r, oid);
236

237
		if (!tree)
238
			continue;
239

240
		if (tree->object.flags & UNINTERESTING)
241
			has_uninteresting = 1;
242
		else
243
			has_interesting = 1;
244
	}
245

246
	/* Do not walk unless we have both types of trees. */
247
	if (!has_uninteresting || !has_interesting)
248
		return;
249

250
	oidset_iter_init(trees, &iter);
251
	while ((oid = oidset_iter_next(&iter))) {
252
		struct tree *tree = lookup_tree(r, oid);
253
		add_children_by_path(r, tree, &map);
254
	}
255

256
	hashmap_for_each_entry(&map, &map_iter, entry, ent /* member name */)
257
		mark_trees_uninteresting_sparse(r, &entry->trees);
258

259
	paths_and_oids_clear(&map);
260
}
261

262
struct commit_stack {
263
	struct commit **items;
264
	size_t nr, alloc;
265
};
266
#define COMMIT_STACK_INIT { 0 }
267

268
static void commit_stack_push(struct commit_stack *stack, struct commit *commit)
269
{
270
	ALLOC_GROW(stack->items, stack->nr + 1, stack->alloc);
271
	stack->items[stack->nr++] = commit;
272
}
273

274
static struct commit *commit_stack_pop(struct commit_stack *stack)
275
{
276
	return stack->nr ? stack->items[--stack->nr] : NULL;
277
}
278

279
static void commit_stack_clear(struct commit_stack *stack)
280
{
281
	FREE_AND_NULL(stack->items);
282
	stack->nr = stack->alloc = 0;
283
}
284

285
static void mark_one_parent_uninteresting(struct rev_info *revs, struct commit *commit,
286
					  struct commit_stack *pending)
287
{
288
	struct commit_list *l;
289

290
	if (commit->object.flags & UNINTERESTING)
291
		return;
292
	commit->object.flags |= UNINTERESTING;
293

294
	/*
295
	 * Normally we haven't parsed the parent
296
	 * yet, so we won't have a parent of a parent
297
	 * here. However, it may turn out that we've
298
	 * reached this commit some other way (where it
299
	 * wasn't uninteresting), in which case we need
300
	 * to mark its parents recursively too..
301
	 */
302
	for (l = commit->parents; l; l = l->next) {
303
		commit_stack_push(pending, l->item);
304
		if (revs && revs->exclude_first_parent_only)
305
			break;
306
	}
307
}
308

309
void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit)
310
{
311
	struct commit_stack pending = COMMIT_STACK_INIT;
312
	struct commit_list *l;
313

314
	for (l = commit->parents; l; l = l->next) {
315
		mark_one_parent_uninteresting(revs, l->item, &pending);
316
		if (revs && revs->exclude_first_parent_only)
317
			break;
318
	}
319

320
	while (pending.nr > 0)
321
		mark_one_parent_uninteresting(revs, commit_stack_pop(&pending),
322
					      &pending);
323

324
	commit_stack_clear(&pending);
325
}
326

327
static void add_pending_object_with_path(struct rev_info *revs,
328
					 struct object *obj,
329
					 const char *name, unsigned mode,
330
					 const char *path)
331
{
332
	struct interpret_branch_name_options options = { 0 };
333
	if (!obj)
334
		return;
335
	if (revs->no_walk && (obj->flags & UNINTERESTING))
336
		revs->no_walk = 0;
337
	if (revs->reflog_info && obj->type == OBJ_COMMIT) {
338
		struct strbuf buf = STRBUF_INIT;
339
		size_t namelen = strlen(name);
340
		int len = repo_interpret_branch_name(the_repository, name,
341
						     namelen, &buf, &options);
342

343
		if (0 < len && len < namelen && buf.len)
344
			strbuf_addstr(&buf, name + len);
345
		add_reflog_for_walk(revs->reflog_info,
346
				    (struct commit *)obj,
347
				    buf.buf[0] ? buf.buf: name);
348
		strbuf_release(&buf);
349
		return; /* do not add the commit itself */
350
	}
351
	add_object_array_with_path(obj, name, &revs->pending, mode, path);
352
}
353

354
static void add_pending_object_with_mode(struct rev_info *revs,
355
					 struct object *obj,
356
					 const char *name, unsigned mode)
357
{
358
	add_pending_object_with_path(revs, obj, name, mode, NULL);
359
}
360

361
void add_pending_object(struct rev_info *revs,
362
			struct object *obj, const char *name)
363
{
364
	add_pending_object_with_mode(revs, obj, name, S_IFINVALID);
365
}
366

367
void add_head_to_pending(struct rev_info *revs)
368
{
369
	struct object_id oid;
370
	struct object *obj;
371
	if (repo_get_oid(the_repository, "HEAD", &oid))
372
		return;
373
	obj = parse_object(revs->repo, &oid);
374
	if (!obj)
375
		return;
376
	add_pending_object(revs, obj, "HEAD");
377
}
378

379
static struct object *get_reference(struct rev_info *revs, const char *name,
380
				    const struct object_id *oid,
381
				    unsigned int flags)
382
{
383
	struct object *object;
384

385
	object = parse_object_with_flags(revs->repo, oid,
386
					 revs->verify_objects ? 0 :
387
					 PARSE_OBJECT_SKIP_HASH_CHECK |
388
					 PARSE_OBJECT_DISCARD_TREE);
389

390
	if (!object) {
391
		if (revs->ignore_missing)
392
			return NULL;
393
		if (revs->exclude_promisor_objects && is_promisor_object(oid))
394
			return NULL;
395
		if (revs->do_not_die_on_missing_objects) {
396
			oidset_insert(&revs->missing_commits, oid);
397
			return NULL;
398
		}
399
		die("bad object %s", name);
400
	}
401
	object->flags |= flags;
402
	return object;
403
}
404

405
void add_pending_oid(struct rev_info *revs, const char *name,
406
		      const struct object_id *oid, unsigned int flags)
407
{
408
	struct object *object = get_reference(revs, name, oid, flags);
409
	add_pending_object(revs, object, name);
410
}
411

412
static struct commit *handle_commit(struct rev_info *revs,
413
				    struct object_array_entry *entry)
414
{
415
	struct object *object = entry->item;
416
	const char *name = entry->name;
417
	const char *path = entry->path;
418
	unsigned int mode = entry->mode;
419
	unsigned long flags = object->flags;
420

421
	/*
422
	 * Tag object? Look what it points to..
423
	 */
424
	while (object->type == OBJ_TAG) {
425
		struct tag *tag = (struct tag *) object;
426
		struct object_id *oid;
427
		if (revs->tag_objects && !(flags & UNINTERESTING))
428
			add_pending_object(revs, object, tag->tag);
429
		oid = get_tagged_oid(tag);
430
		object = parse_object(revs->repo, oid);
431
		if (!object) {
432
			if (revs->ignore_missing_links || (flags & UNINTERESTING))
433
				return NULL;
434
			if (revs->exclude_promisor_objects &&
435
			    is_promisor_object(&tag->tagged->oid))
436
				return NULL;
437
			if (revs->do_not_die_on_missing_objects && oid) {
438
				oidset_insert(&revs->missing_commits, oid);
439
				return NULL;
440
			}
441
			die("bad object %s", oid_to_hex(&tag->tagged->oid));
442
		}
443
		object->flags |= flags;
444
		/*
445
		 * We'll handle the tagged object by looping or dropping
446
		 * through to the non-tag handlers below. Do not
447
		 * propagate path data from the tag's pending entry.
448
		 */
449
		path = NULL;
450
		mode = 0;
451
	}
452

453
	/*
454
	 * Commit object? Just return it, we'll do all the complex
455
	 * reachability crud.
456
	 */
457
	if (object->type == OBJ_COMMIT) {
458
		struct commit *commit = (struct commit *)object;
459

460
		if (repo_parse_commit(revs->repo, commit) < 0)
461
			die("unable to parse commit %s", name);
462
		if (flags & UNINTERESTING) {
463
			mark_parents_uninteresting(revs, commit);
464

465
			if (!revs->topo_order || !generation_numbers_enabled(the_repository))
466
				revs->limited = 1;
467
		}
468
		if (revs->sources) {
469
			char **slot = revision_sources_at(revs->sources, commit);
470

471
			if (!*slot)
472
				*slot = xstrdup(name);
473
		}
474
		return commit;
475
	}
476

477
	/*
478
	 * Tree object? Either mark it uninteresting, or add it
479
	 * to the list of objects to look at later..
480
	 */
481
	if (object->type == OBJ_TREE) {
482
		struct tree *tree = (struct tree *)object;
483
		if (!revs->tree_objects)
484
			return NULL;
485
		if (flags & UNINTERESTING) {
486
			mark_tree_contents_uninteresting(revs->repo, tree);
487
			return NULL;
488
		}
489
		add_pending_object_with_path(revs, object, name, mode, path);
490
		return NULL;
491
	}
492

493
	/*
494
	 * Blob object? You know the drill by now..
495
	 */
496
	if (object->type == OBJ_BLOB) {
497
		if (!revs->blob_objects)
498
			return NULL;
499
		if (flags & UNINTERESTING)
500
			return NULL;
501
		add_pending_object_with_path(revs, object, name, mode, path);
502
		return NULL;
503
	}
504
	die("%s is unknown object", name);
505
}
506

507
static int everybody_uninteresting(struct commit_list *orig,
508
				   struct commit **interesting_cache)
509
{
510
	struct commit_list *list = orig;
511

512
	if (*interesting_cache) {
513
		struct commit *commit = *interesting_cache;
514
		if (!(commit->object.flags & UNINTERESTING))
515
			return 0;
516
	}
517

518
	while (list) {
519
		struct commit *commit = list->item;
520
		list = list->next;
521
		if (commit->object.flags & UNINTERESTING)
522
			continue;
523

524
		*interesting_cache = commit;
525
		return 0;
526
	}
527
	return 1;
528
}
529

530
/*
531
 * A definition of "relevant" commit that we can use to simplify limited graphs
532
 * by eliminating side branches.
533
 *
534
 * A "relevant" commit is one that is !UNINTERESTING (ie we are including it
535
 * in our list), or that is a specified BOTTOM commit. Then after computing
536
 * a limited list, during processing we can generally ignore boundary merges
537
 * coming from outside the graph, (ie from irrelevant parents), and treat
538
 * those merges as if they were single-parent. TREESAME is defined to consider
539
 * only relevant parents, if any. If we are TREESAME to our on-graph parents,
540
 * we don't care if we were !TREESAME to non-graph parents.
541
 *
542
 * Treating bottom commits as relevant ensures that a limited graph's
543
 * connection to the actual bottom commit is not viewed as a side branch, but
544
 * treated as part of the graph. For example:
545
 *
546
 *   ....Z...A---X---o---o---B
547
 *        .     /
548
 *         W---Y
549
 *
550
 * When computing "A..B", the A-X connection is at least as important as
551
 * Y-X, despite A being flagged UNINTERESTING.
552
 *
553
 * And when computing --ancestry-path "A..B", the A-X connection is more
554
 * important than Y-X, despite both A and Y being flagged UNINTERESTING.
555
 */
556
static inline int relevant_commit(struct commit *commit)
557
{
558
	return (commit->object.flags & (UNINTERESTING | BOTTOM)) != UNINTERESTING;
559
}
560

561
/*
562
 * Return a single relevant commit from a parent list. If we are a TREESAME
563
 * commit, and this selects one of our parents, then we can safely simplify to
564
 * that parent.
565
 */
566
static struct commit *one_relevant_parent(const struct rev_info *revs,
567
					  struct commit_list *orig)
568
{
569
	struct commit_list *list = orig;
570
	struct commit *relevant = NULL;
571

572
	if (!orig)
573
		return NULL;
574

575
	/*
576
	 * For 1-parent commits, or if first-parent-only, then return that
577
	 * first parent (even if not "relevant" by the above definition).
578
	 * TREESAME will have been set purely on that parent.
579
	 */
580
	if (revs->first_parent_only || !orig->next)
581
		return orig->item;
582

583
	/*
584
	 * For multi-parent commits, identify a sole relevant parent, if any.
585
	 * If we have only one relevant parent, then TREESAME will be set purely
586
	 * with regard to that parent, and we can simplify accordingly.
587
	 *
588
	 * If we have more than one relevant parent, or no relevant parents
589
	 * (and multiple irrelevant ones), then we can't select a parent here
590
	 * and return NULL.
591
	 */
592
	while (list) {
593
		struct commit *commit = list->item;
594
		list = list->next;
595
		if (relevant_commit(commit)) {
596
			if (relevant)
597
				return NULL;
598
			relevant = commit;
599
		}
600
	}
601
	return relevant;
602
}
603

604
/*
605
 * The goal is to get REV_TREE_NEW as the result only if the
606
 * diff consists of all '+' (and no other changes), REV_TREE_OLD
607
 * if the whole diff is removal of old data, and otherwise
608
 * REV_TREE_DIFFERENT (of course if the trees are the same we
609
 * want REV_TREE_SAME).
610
 *
611
 * The only time we care about the distinction is when
612
 * remove_empty_trees is in effect, in which case we care only about
613
 * whether the whole change is REV_TREE_NEW, or if there's another type
614
 * of change. Which means we can stop the diff early in either of these
615
 * cases:
616
 *
617
 *   1. We're not using remove_empty_trees at all.
618
 *
619
 *   2. We saw anything except REV_TREE_NEW.
620
 */
621
#define REV_TREE_SAME		0
622
#define REV_TREE_NEW		1	/* Only new files */
623
#define REV_TREE_OLD		2	/* Only files removed */
624
#define REV_TREE_DIFFERENT	3	/* Mixed changes */
625
static int tree_difference = REV_TREE_SAME;
626

627
static void file_add_remove(struct diff_options *options,
628
		    int addremove,
629
		    unsigned mode UNUSED,
630
		    const struct object_id *oid UNUSED,
631
		    int oid_valid UNUSED,
632
		    const char *fullpath UNUSED,
633
		    unsigned dirty_submodule UNUSED)
634
{
635
	int diff = addremove == '+' ? REV_TREE_NEW : REV_TREE_OLD;
636
	struct rev_info *revs = options->change_fn_data;
637

638
	tree_difference |= diff;
639
	if (!revs->remove_empty_trees || tree_difference != REV_TREE_NEW)
640
		options->flags.has_changes = 1;
641
}
642

643
static void file_change(struct diff_options *options,
644
		 unsigned old_mode UNUSED,
645
		 unsigned new_mode UNUSED,
646
		 const struct object_id *old_oid UNUSED,
647
		 const struct object_id *new_oid UNUSED,
648
		 int old_oid_valid UNUSED,
649
		 int new_oid_valid UNUSED,
650
		 const char *fullpath UNUSED,
651
		 unsigned old_dirty_submodule UNUSED,
652
		 unsigned new_dirty_submodule UNUSED)
653
{
654
	tree_difference = REV_TREE_DIFFERENT;
655
	options->flags.has_changes = 1;
656
}
657

658
static int bloom_filter_atexit_registered;
659
static unsigned int count_bloom_filter_maybe;
660
static unsigned int count_bloom_filter_definitely_not;
661
static unsigned int count_bloom_filter_false_positive;
662
static unsigned int count_bloom_filter_not_present;
663

664
static void trace2_bloom_filter_statistics_atexit(void)
665
{
666
	struct json_writer jw = JSON_WRITER_INIT;
667

668
	jw_object_begin(&jw, 0);
669
	jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
670
	jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
671
	jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
672
	jw_object_intmax(&jw, "false_positive", count_bloom_filter_false_positive);
673
	jw_end(&jw);
674

675
	trace2_data_json("bloom", the_repository, "statistics", &jw);
676

677
	jw_release(&jw);
678
}
679

680
static int forbid_bloom_filters(struct pathspec *spec)
681
{
682
	if (spec->has_wildcard)
683
		return 1;
684
	if (spec->nr > 1)
685
		return 1;
686
	if (spec->magic & ~PATHSPEC_LITERAL)
687
		return 1;
688
	if (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))
689
		return 1;
690

691
	return 0;
692
}
693

694
static void prepare_to_use_bloom_filter(struct rev_info *revs)
695
{
696
	struct pathspec_item *pi;
697
	char *path_alloc = NULL;
698
	const char *path, *p;
699
	size_t len;
700
	int path_component_nr = 1;
701

702
	if (!revs->commits)
703
		return;
704

705
	if (forbid_bloom_filters(&revs->prune_data))
706
		return;
707

708
	repo_parse_commit(revs->repo, revs->commits->item);
709

710
	revs->bloom_filter_settings = get_bloom_filter_settings(revs->repo);
711
	if (!revs->bloom_filter_settings)
712
		return;
713

714
	if (!revs->pruning.pathspec.nr)
715
		return;
716

717
	pi = &revs->pruning.pathspec.items[0];
718

719
	/* remove single trailing slash from path, if needed */
720
	if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
721
		path_alloc = xmemdupz(pi->match, pi->len - 1);
722
		path = path_alloc;
723
	} else
724
		path = pi->match;
725

726
	len = strlen(path);
727
	if (!len) {
728
		revs->bloom_filter_settings = NULL;
729
		free(path_alloc);
730
		return;
731
	}
732

733
	p = path;
734
	while (*p) {
735
		/*
736
		 * At this point, the path is normalized to use Unix-style
737
		 * path separators. This is required due to how the
738
		 * changed-path Bloom filters store the paths.
739
		 */
740
		if (*p == '/')
741
			path_component_nr++;
742
		p++;
743
	}
744

745
	revs->bloom_keys_nr = path_component_nr;
746
	ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr);
747

748
	fill_bloom_key(path, len, &revs->bloom_keys[0],
749
		       revs->bloom_filter_settings);
750
	path_component_nr = 1;
751

752
	p = path + len - 1;
753
	while (p > path) {
754
		if (*p == '/')
755
			fill_bloom_key(path, p - path,
756
				       &revs->bloom_keys[path_component_nr++],
757
				       revs->bloom_filter_settings);
758
		p--;
759
	}
760

761
	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
762
		atexit(trace2_bloom_filter_statistics_atexit);
763
		bloom_filter_atexit_registered = 1;
764
	}
765

766
	free(path_alloc);
767
}
768

769
static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
770
						 struct commit *commit)
771
{
772
	struct bloom_filter *filter;
773
	int result = 1, j;
774

775
	if (!revs->repo->objects->commit_graph)
776
		return -1;
777

778
	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
779
		return -1;
780

781
	filter = get_bloom_filter(revs->repo, commit);
782

783
	if (!filter) {
784
		count_bloom_filter_not_present++;
785
		return -1;
786
	}
787

788
	for (j = 0; result && j < revs->bloom_keys_nr; j++) {
789
		result = bloom_filter_contains(filter,
790
					       &revs->bloom_keys[j],
791
					       revs->bloom_filter_settings);
792
	}
793

794
	if (result)
795
		count_bloom_filter_maybe++;
796
	else
797
		count_bloom_filter_definitely_not++;
798

799
	return result;
800
}
801

802
static int rev_compare_tree(struct rev_info *revs,
803
			    struct commit *parent, struct commit *commit, int nth_parent)
804
{
805
	struct tree *t1 = repo_get_commit_tree(the_repository, parent);
806
	struct tree *t2 = repo_get_commit_tree(the_repository, commit);
807
	int bloom_ret = 1;
808

809
	if (!t1)
810
		return REV_TREE_NEW;
811
	if (!t2)
812
		return REV_TREE_OLD;
813

814
	if (revs->simplify_by_decoration) {
815
		/*
816
		 * If we are simplifying by decoration, then the commit
817
		 * is worth showing if it has a tag pointing at it.
818
		 */
819
		if (get_name_decoration(&commit->object))
820
			return REV_TREE_DIFFERENT;
821
		/*
822
		 * A commit that is not pointed by a tag is uninteresting
823
		 * if we are not limited by path.  This means that you will
824
		 * see the usual "commits that touch the paths" plus any
825
		 * tagged commit by specifying both --simplify-by-decoration
826
		 * and pathspec.
827
		 */
828
		if (!revs->prune_data.nr)
829
			return REV_TREE_SAME;
830
	}
831

832
	if (revs->bloom_keys_nr && !nth_parent) {
833
		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
834

835
		if (bloom_ret == 0)
836
			return REV_TREE_SAME;
837
	}
838

839
	tree_difference = REV_TREE_SAME;
840
	revs->pruning.flags.has_changes = 0;
841
	diff_tree_oid(&t1->object.oid, &t2->object.oid, "", &revs->pruning);
842

843
	if (!nth_parent)
844
		if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
845
			count_bloom_filter_false_positive++;
846

847
	return tree_difference;
848
}
849

850
static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,
851
				  int nth_parent)
852
{
853
	struct tree *t1 = repo_get_commit_tree(the_repository, commit);
854
	int bloom_ret = -1;
855

856
	if (!t1)
857
		return 0;
858

859
	if (!nth_parent && revs->bloom_keys_nr) {
860
		bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
861
		if (!bloom_ret)
862
			return 1;
863
	}
864

865
	tree_difference = REV_TREE_SAME;
866
	revs->pruning.flags.has_changes = 0;
867
	diff_tree_oid(NULL, &t1->object.oid, "", &revs->pruning);
868

869
	if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
870
		count_bloom_filter_false_positive++;
871

872
	return tree_difference == REV_TREE_SAME;
873
}
874

875
struct treesame_state {
876
	unsigned int nparents;
877
	unsigned char treesame[FLEX_ARRAY];
878
};
879

880
static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)
881
{
882
	unsigned n = commit_list_count(commit->parents);
883
	struct treesame_state *st = xcalloc(1, st_add(sizeof(*st), n));
884
	st->nparents = n;
885
	add_decoration(&revs->treesame, &commit->object, st);
886
	return st;
887
}
888

889
/*
890
 * Must be called immediately after removing the nth_parent from a commit's
891
 * parent list, if we are maintaining the per-parent treesame[] decoration.
892
 * This does not recalculate the master TREESAME flag - update_treesame()
893
 * should be called to update it after a sequence of treesame[] modifications
894
 * that may have affected it.
895
 */
896
static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned nth_parent)
897
{
898
	struct treesame_state *st;
899
	int old_same;
900

901
	if (!commit->parents) {
902
		/*
903
		 * Have just removed the only parent from a non-merge.
904
		 * Different handling, as we lack decoration.
905
		 */
906
		if (nth_parent != 0)
907
			die("compact_treesame %u", nth_parent);
908
		old_same = !!(commit->object.flags & TREESAME);
909
		if (rev_same_tree_as_empty(revs, commit, nth_parent))
910
			commit->object.flags |= TREESAME;
911
		else
912
			commit->object.flags &= ~TREESAME;
913
		return old_same;
914
	}
915

916
	st = lookup_decoration(&revs->treesame, &commit->object);
917
	if (!st || nth_parent >= st->nparents)
918
		die("compact_treesame %u", nth_parent);
919

920
	old_same = st->treesame[nth_parent];
921
	memmove(st->treesame + nth_parent,
922
		st->treesame + nth_parent + 1,
923
		st->nparents - nth_parent - 1);
924

925
	/*
926
	 * If we've just become a non-merge commit, update TREESAME
927
	 * immediately, and remove the no-longer-needed decoration.
928
	 * If still a merge, defer update until update_treesame().
929
	 */
930
	if (--st->nparents == 1) {
931
		if (commit->parents->next)
932
			die("compact_treesame parents mismatch");
933
		if (st->treesame[0] && revs->dense)
934
			commit->object.flags |= TREESAME;
935
		else
936
			commit->object.flags &= ~TREESAME;
937
		free(add_decoration(&revs->treesame, &commit->object, NULL));
938
	}
939

940
	return old_same;
941
}
942

943
static unsigned update_treesame(struct rev_info *revs, struct commit *commit)
944
{
945
	if (commit->parents && commit->parents->next) {
946
		unsigned n;
947
		struct treesame_state *st;
948
		struct commit_list *p;
949
		unsigned relevant_parents;
950
		unsigned relevant_change, irrelevant_change;
951

952
		st = lookup_decoration(&revs->treesame, &commit->object);
953
		if (!st)
954
			die("update_treesame %s", oid_to_hex(&commit->object.oid));
955
		relevant_parents = 0;
956
		relevant_change = irrelevant_change = 0;
957
		for (p = commit->parents, n = 0; p; n++, p = p->next) {
958
			if (relevant_commit(p->item)) {
959
				relevant_change |= !st->treesame[n];
960
				relevant_parents++;
961
			} else
962
				irrelevant_change |= !st->treesame[n];
963
		}
964
		if (relevant_parents ? relevant_change : irrelevant_change)
965
			commit->object.flags &= ~TREESAME;
966
		else
967
			commit->object.flags |= TREESAME;
968
	}
969

970
	return commit->object.flags & TREESAME;
971
}
972

973
static inline int limiting_can_increase_treesame(const struct rev_info *revs)
974
{
975
	/*
976
	 * TREESAME is irrelevant unless prune && dense;
977
	 * if simplify_history is set, we can't have a mixture of TREESAME and
978
	 *    !TREESAME INTERESTING parents (and we don't have treesame[]
979
	 *    decoration anyway);
980
	 * if first_parent_only is set, then the TREESAME flag is locked
981
	 *    against the first parent (and again we lack treesame[] decoration).
982
	 */
983
	return revs->prune && revs->dense &&
984
	       !revs->simplify_history &&
985
	       !revs->first_parent_only;
986
}
987

988
static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
989
{
990
	struct commit_list **pp, *parent;
991
	struct treesame_state *ts = NULL;
992
	int relevant_change = 0, irrelevant_change = 0;
993
	int relevant_parents, nth_parent;
994

995
	/*
996
	 * If we don't do pruning, everything is interesting
997
	 */
998
	if (!revs->prune)
999
		return;
1000

1001
	if (!repo_get_commit_tree(the_repository, commit))
1002
		return;
1003

1004
	if (!commit->parents) {
1005
		/*
1006
		 * Pretend as if we are comparing ourselves to the
1007
		 * (non-existent) first parent of this commit object. Even
1008
		 * though no such parent exists, its changed-path Bloom filter
1009
		 * (if one exists) is relative to the empty tree, using Bloom
1010
		 * filters is allowed here.
1011
		 */
1012
		if (rev_same_tree_as_empty(revs, commit, 0))
1013
			commit->object.flags |= TREESAME;
1014
		return;
1015
	}
1016

1017
	/*
1018
	 * Normal non-merge commit? If we don't want to make the
1019
	 * history dense, we consider it always to be a change..
1020
	 */
1021
	if (!revs->dense && !commit->parents->next)
1022
		return;
1023

1024
	for (pp = &commit->parents, nth_parent = 0, relevant_parents = 0;
1025
	     (parent = *pp) != NULL;
1026
	     pp = &parent->next, nth_parent++) {
1027
		struct commit *p = parent->item;
1028
		if (relevant_commit(p))
1029
			relevant_parents++;
1030

1031
		if (nth_parent == 1) {
1032
			/*
1033
			 * This our second loop iteration - so we now know
1034
			 * we're dealing with a merge.
1035
			 *
1036
			 * Do not compare with later parents when we care only about
1037
			 * the first parent chain, in order to avoid derailing the
1038
			 * traversal to follow a side branch that brought everything
1039
			 * in the path we are limited to by the pathspec.
1040
			 */
1041
			if (revs->first_parent_only)
1042
				break;
1043
			/*
1044
			 * If this will remain a potentially-simplifiable
1045
			 * merge, remember per-parent treesame if needed.
1046
			 * Initialise the array with the comparison from our
1047
			 * first iteration.
1048
			 */
1049
			if (revs->treesame.name &&
1050
			    !revs->simplify_history &&
1051
			    !(commit->object.flags & UNINTERESTING)) {
1052
				ts = initialise_treesame(revs, commit);
1053
				if (!(irrelevant_change || relevant_change))
1054
					ts->treesame[0] = 1;
1055
			}
1056
		}
1057
		if (repo_parse_commit(revs->repo, p) < 0)
1058
			die("cannot simplify commit %s (because of %s)",
1059
			    oid_to_hex(&commit->object.oid),
1060
			    oid_to_hex(&p->object.oid));
1061
		switch (rev_compare_tree(revs, p, commit, nth_parent)) {
1062
		case REV_TREE_SAME:
1063
			if (!revs->simplify_history || !relevant_commit(p)) {
1064
				/* Even if a merge with an uninteresting
1065
				 * side branch brought the entire change
1066
				 * we are interested in, we do not want
1067
				 * to lose the other branches of this
1068
				 * merge, so we just keep going.
1069
				 */
1070
				if (ts)
1071
					ts->treesame[nth_parent] = 1;
1072
				continue;
1073
			}
1074
			parent->next = NULL;
1075
			commit->parents = parent;
1076

1077
			/*
1078
			 * A merge commit is a "diversion" if it is not
1079
			 * TREESAME to its first parent but is TREESAME
1080
			 * to a later parent. In the simplified history,
1081
			 * we "divert" the history walk to the later
1082
			 * parent. These commits are shown when "show_pulls"
1083
			 * is enabled, so do not mark the object as
1084
			 * TREESAME here.
1085
			 */
1086
			if (!revs->show_pulls || !nth_parent)
1087
				commit->object.flags |= TREESAME;
1088

1089
			return;
1090

1091
		case REV_TREE_NEW:
1092
			if (revs->remove_empty_trees &&
1093
			    rev_same_tree_as_empty(revs, p, nth_parent)) {
1094
				/* We are adding all the specified
1095
				 * paths from this parent, so the
1096
				 * history beyond this parent is not
1097
				 * interesting.  Remove its parents
1098
				 * (they are grandparents for us).
1099
				 * IOW, we pretend this parent is a
1100
				 * "root" commit.
1101
				 */
1102
				if (repo_parse_commit(revs->repo, p) < 0)
1103
					die("cannot simplify commit %s (invalid %s)",
1104
					    oid_to_hex(&commit->object.oid),
1105
					    oid_to_hex(&p->object.oid));
1106
				p->parents = NULL;
1107
			}
1108
		/* fallthrough */
1109
		case REV_TREE_OLD:
1110
		case REV_TREE_DIFFERENT:
1111
			if (relevant_commit(p))
1112
				relevant_change = 1;
1113
			else
1114
				irrelevant_change = 1;
1115

1116
			if (!nth_parent)
1117
				commit->object.flags |= PULL_MERGE;
1118

1119
			continue;
1120
		}
1121
		die("bad tree compare for commit %s", oid_to_hex(&commit->object.oid));
1122
	}
1123

1124
	/*
1125
	 * TREESAME is straightforward for single-parent commits. For merge
1126
	 * commits, it is most useful to define it so that "irrelevant"
1127
	 * parents cannot make us !TREESAME - if we have any relevant
1128
	 * parents, then we only consider TREESAMEness with respect to them,
1129
	 * allowing irrelevant merges from uninteresting branches to be
1130
	 * simplified away. Only if we have only irrelevant parents do we
1131
	 * base TREESAME on them. Note that this logic is replicated in
1132
	 * update_treesame, which should be kept in sync.
1133
	 */
1134
	if (relevant_parents ? !relevant_change : !irrelevant_change)
1135
		commit->object.flags |= TREESAME;
1136
}
1137

1138
static int process_parents(struct rev_info *revs, struct commit *commit,
1139
			   struct commit_list **list, struct prio_queue *queue)
1140
{
1141
	struct commit_list *parent = commit->parents;
1142
	unsigned pass_flags;
1143

1144
	if (commit->object.flags & ADDED)
1145
		return 0;
1146
	if (revs->do_not_die_on_missing_objects &&
1147
	    oidset_contains(&revs->missing_commits, &commit->object.oid))
1148
		return 0;
1149
	commit->object.flags |= ADDED;
1150

1151
	if (revs->include_check &&
1152
	    !revs->include_check(commit, revs->include_check_data))
1153
		return 0;
1154

1155
	/*
1156
	 * If the commit is uninteresting, don't try to
1157
	 * prune parents - we want the maximal uninteresting
1158
	 * set.
1159
	 *
1160
	 * Normally we haven't parsed the parent
1161
	 * yet, so we won't have a parent of a parent
1162
	 * here. However, it may turn out that we've
1163
	 * reached this commit some other way (where it
1164
	 * wasn't uninteresting), in which case we need
1165
	 * to mark its parents recursively too..
1166
	 */
1167
	if (commit->object.flags & UNINTERESTING) {
1168
		while (parent) {
1169
			struct commit *p = parent->item;
1170
			parent = parent->next;
1171
			if (p)
1172
				p->object.flags |= UNINTERESTING;
1173
			if (repo_parse_commit_gently(revs->repo, p, 1) < 0)
1174
				continue;
1175
			if (p->parents)
1176
				mark_parents_uninteresting(revs, p);
1177
			if (p->object.flags & SEEN)
1178
				continue;
1179
			p->object.flags |= (SEEN | NOT_USER_GIVEN);
1180
			if (list)
1181
				commit_list_insert_by_date(p, list);
1182
			if (queue)
1183
				prio_queue_put(queue, p);
1184
			if (revs->exclude_first_parent_only)
1185
				break;
1186
		}
1187
		return 0;
1188
	}
1189

1190
	/*
1191
	 * Ok, the commit wasn't uninteresting. Try to
1192
	 * simplify the commit history and find the parent
1193
	 * that has no differences in the path set if one exists.
1194
	 */
1195
	try_to_simplify_commit(revs, commit);
1196

1197
	if (revs->no_walk)
1198
		return 0;
1199

1200
	pass_flags = (commit->object.flags & (SYMMETRIC_LEFT | ANCESTRY_PATH));
1201

1202
	for (parent = commit->parents; parent; parent = parent->next) {
1203
		struct commit *p = parent->item;
1204
		int gently = revs->ignore_missing_links ||
1205
			     revs->exclude_promisor_objects ||
1206
			     revs->do_not_die_on_missing_objects;
1207
		if (repo_parse_commit_gently(revs->repo, p, gently) < 0) {
1208
			if (revs->exclude_promisor_objects &&
1209
			    is_promisor_object(&p->object.oid)) {
1210
				if (revs->first_parent_only)
1211
					break;
1212
				continue;
1213
			}
1214

1215
			if (revs->do_not_die_on_missing_objects)
1216
				oidset_insert(&revs->missing_commits, &p->object.oid);
1217
			else
1218
				return -1; /* corrupt repository */
1219
		}
1220
		if (revs->sources) {
1221
			char **slot = revision_sources_at(revs->sources, p);
1222

1223
			if (!*slot)
1224
				*slot = *revision_sources_at(revs->sources, commit);
1225
		}
1226
		p->object.flags |= pass_flags;
1227
		if (!(p->object.flags & SEEN)) {
1228
			p->object.flags |= (SEEN | NOT_USER_GIVEN);
1229
			if (list)
1230
				commit_list_insert_by_date(p, list);
1231
			if (queue)
1232
				prio_queue_put(queue, p);
1233
		}
1234
		if (revs->first_parent_only)
1235
			break;
1236
	}
1237
	return 0;
1238
}
1239

1240
static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
1241
{
1242
	struct commit_list *p;
1243
	int left_count = 0, right_count = 0;
1244
	int left_first;
1245
	struct patch_ids ids;
1246
	unsigned cherry_flag;
1247

1248
	/* First count the commits on the left and on the right */
1249
	for (p = list; p; p = p->next) {
1250
		struct commit *commit = p->item;
1251
		unsigned flags = commit->object.flags;
1252
		if (flags & BOUNDARY)
1253
			;
1254
		else if (flags & SYMMETRIC_LEFT)
1255
			left_count++;
1256
		else
1257
			right_count++;
1258
	}
1259

1260
	if (!left_count || !right_count)
1261
		return;
1262

1263
	left_first = left_count < right_count;
1264
	init_patch_ids(revs->repo, &ids);
1265
	ids.diffopts.pathspec = revs->diffopt.pathspec;
1266

1267
	/* Compute patch-ids for one side */
1268
	for (p = list; p; p = p->next) {
1269
		struct commit *commit = p->item;
1270
		unsigned flags = commit->object.flags;
1271

1272
		if (flags & BOUNDARY)
1273
			continue;
1274
		/*
1275
		 * If we have fewer left, left_first is set and we omit
1276
		 * commits on the right branch in this loop.  If we have
1277
		 * fewer right, we skip the left ones.
1278
		 */
1279
		if (left_first != !!(flags & SYMMETRIC_LEFT))
1280
			continue;
1281
		add_commit_patch_id(commit, &ids);
1282
	}
1283

1284
	/* either cherry_mark or cherry_pick are true */
1285
	cherry_flag = revs->cherry_mark ? PATCHSAME : SHOWN;
1286

1287
	/* Check the other side */
1288
	for (p = list; p; p = p->next) {
1289
		struct commit *commit = p->item;
1290
		struct patch_id *id;
1291
		unsigned flags = commit->object.flags;
1292

1293
		if (flags & BOUNDARY)
1294
			continue;
1295
		/*
1296
		 * If we have fewer left, left_first is set and we omit
1297
		 * commits on the left branch in this loop.
1298
		 */
1299
		if (left_first == !!(flags & SYMMETRIC_LEFT))
1300
			continue;
1301

1302
		/*
1303
		 * Have we seen the same patch id?
1304
		 */
1305
		id = patch_id_iter_first(commit, &ids);
1306
		if (!id)
1307
			continue;
1308

1309
		commit->object.flags |= cherry_flag;
1310
		do {
1311
			id->commit->object.flags |= cherry_flag;
1312
		} while ((id = patch_id_iter_next(id, &ids)));
1313
	}
1314

1315
	free_patch_ids(&ids);
1316
}
1317

1318
/* How many extra uninteresting commits we want to see.. */
1319
#define SLOP 5
1320

1321
static int still_interesting(struct commit_list *src, timestamp_t date, int slop,
1322
			     struct commit **interesting_cache)
1323
{
1324
	/*
1325
	 * No source list at all? We're definitely done..
1326
	 */
1327
	if (!src)
1328
		return 0;
1329

1330
	/*
1331
	 * Does the destination list contain entries with a date
1332
	 * before the source list? Definitely _not_ done.
1333
	 */
1334
	if (date <= src->item->date)
1335
		return SLOP;
1336

1337
	/*
1338
	 * Does the source list still have interesting commits in
1339
	 * it? Definitely not done..
1340
	 */
1341
	if (!everybody_uninteresting(src, interesting_cache))
1342
		return SLOP;
1343

1344
	/* Ok, we're closing in.. */
1345
	return slop-1;
1346
}
1347

1348
/*
1349
 * "rev-list --ancestry-path=C_0 [--ancestry-path=C_1 ...] A..B"
1350
 * computes commits that are ancestors of B but not ancestors of A but
1351
 * further limits the result to those that have any of C in their
1352
 * ancestry path (i.e. are either ancestors of any of C, descendants
1353
 * of any of C, or are any of C). If --ancestry-path is specified with
1354
 * no commit, we use all bottom commits for C.
1355
 *
1356
 * Before this function is called, ancestors of C will have already
1357
 * been marked with ANCESTRY_PATH previously.
1358
 *
1359
 * This takes the list of bottom commits and the result of "A..B"
1360
 * without --ancestry-path, and limits the latter further to the ones
1361
 * that have any of C in their ancestry path. Since the ancestors of C
1362
 * have already been marked (a prerequisite of this function), we just
1363
 * need to mark the descendants, then exclude any commit that does not
1364
 * have any of these marks.
1365
 */
1366
static void limit_to_ancestry(struct commit_list *bottoms, struct commit_list *list)
1367
{
1368
	struct commit_list *p;
1369
	struct commit_list *rlist = NULL;
1370
	int made_progress;
1371

1372
	/*
1373
	 * Reverse the list so that it will be likely that we would
1374
	 * process parents before children.
1375
	 */
1376
	for (p = list; p; p = p->next)
1377
		commit_list_insert(p->item, &rlist);
1378

1379
	for (p = bottoms; p; p = p->next)
1380
		p->item->object.flags |= TMP_MARK;
1381

1382
	/*
1383
	 * Mark the ones that can reach bottom commits in "list",
1384
	 * in a bottom-up fashion.
1385
	 */
1386
	do {
1387
		made_progress = 0;
1388
		for (p = rlist; p; p = p->next) {
1389
			struct commit *c = p->item;
1390
			struct commit_list *parents;
1391
			if (c->object.flags & (TMP_MARK | UNINTERESTING))
1392
				continue;
1393
			for (parents = c->parents;
1394
			     parents;
1395
			     parents = parents->next) {
1396
				if (!(parents->item->object.flags & TMP_MARK))
1397
					continue;
1398
				c->object.flags |= TMP_MARK;
1399
				made_progress = 1;
1400
				break;
1401
			}
1402
		}
1403
	} while (made_progress);
1404

1405
	/*
1406
	 * NEEDSWORK: decide if we want to remove parents that are
1407
	 * not marked with TMP_MARK from commit->parents for commits
1408
	 * in the resulting list.  We may not want to do that, though.
1409
	 */
1410

1411
	/*
1412
	 * The ones that are not marked with either TMP_MARK or
1413
	 * ANCESTRY_PATH are uninteresting
1414
	 */
1415
	for (p = list; p; p = p->next) {
1416
		struct commit *c = p->item;
1417
		if (c->object.flags & (TMP_MARK | ANCESTRY_PATH))
1418
			continue;
1419
		c->object.flags |= UNINTERESTING;
1420
	}
1421

1422
	/* We are done with TMP_MARK and ANCESTRY_PATH */
1423
	for (p = list; p; p = p->next)
1424
		p->item->object.flags &= ~(TMP_MARK | ANCESTRY_PATH);
1425
	for (p = bottoms; p; p = p->next)
1426
		p->item->object.flags &= ~(TMP_MARK | ANCESTRY_PATH);
1427
	free_commit_list(rlist);
1428
}
1429

1430
/*
1431
 * Before walking the history, add the set of "negative" refs the
1432
 * caller has asked to exclude to the bottom list.
1433
 *
1434
 * This is used to compute "rev-list --ancestry-path A..B", as we need
1435
 * to filter the result of "A..B" further to the ones that can actually
1436
 * reach A.
1437
 */
1438
static void collect_bottom_commits(struct commit_list *list,
1439
				   struct commit_list **bottom)
1440
{
1441
	struct commit_list *elem;
1442
	for (elem = list; elem; elem = elem->next)
1443
		if (elem->item->object.flags & BOTTOM)
1444
			commit_list_insert(elem->item, bottom);
1445
}
1446

1447
/* Assumes either left_only or right_only is set */
1448
static void limit_left_right(struct commit_list *list, struct rev_info *revs)
1449
{
1450
	struct commit_list *p;
1451

1452
	for (p = list; p; p = p->next) {
1453
		struct commit *commit = p->item;
1454

1455
		if (revs->right_only) {
1456
			if (commit->object.flags & SYMMETRIC_LEFT)
1457
				commit->object.flags |= SHOWN;
1458
		} else	/* revs->left_only is set */
1459
			if (!(commit->object.flags & SYMMETRIC_LEFT))
1460
				commit->object.flags |= SHOWN;
1461
	}
1462
}
1463

1464
static int limit_list(struct rev_info *revs)
1465
{
1466
	int slop = SLOP;
1467
	timestamp_t date = TIME_MAX;
1468
	struct commit_list *original_list = revs->commits;
1469
	struct commit_list *newlist = NULL;
1470
	struct commit_list **p = &newlist;
1471
	struct commit *interesting_cache = NULL;
1472

1473
	if (revs->ancestry_path_implicit_bottoms) {
1474
		collect_bottom_commits(original_list,
1475
				       &revs->ancestry_path_bottoms);
1476
		if (!revs->ancestry_path_bottoms)
1477
			die("--ancestry-path given but there are no bottom commits");
1478
	}
1479

1480
	while (original_list) {
1481
		struct commit *commit = pop_commit(&original_list);
1482
		struct object *obj = &commit->object;
1483
		show_early_output_fn_t show;
1484

1485
		if (commit == interesting_cache)
1486
			interesting_cache = NULL;
1487

1488
		if (revs->max_age != -1 && (commit->date < revs->max_age))
1489
			obj->flags |= UNINTERESTING;
1490
		if (process_parents(revs, commit, &original_list, NULL) < 0)
1491
			return -1;
1492
		if (obj->flags & UNINTERESTING) {
1493
			mark_parents_uninteresting(revs, commit);
1494
			slop = still_interesting(original_list, date, slop, &interesting_cache);
1495
			if (slop)
1496
				continue;
1497
			break;
1498
		}
1499
		if (revs->min_age != -1 && (commit->date > revs->min_age) &&
1500
		    !revs->line_level_traverse)
1501
			continue;
1502
		if (revs->max_age_as_filter != -1 &&
1503
			(commit->date < revs->max_age_as_filter) && !revs->line_level_traverse)
1504
			continue;
1505
		date = commit->date;
1506
		p = &commit_list_insert(commit, p)->next;
1507

1508
		show = show_early_output;
1509
		if (!show)
1510
			continue;
1511

1512
		show(revs, newlist);
1513
		show_early_output = NULL;
1514
	}
1515
	if (revs->cherry_pick || revs->cherry_mark)
1516
		cherry_pick_list(newlist, revs);
1517

1518
	if (revs->left_only || revs->right_only)
1519
		limit_left_right(newlist, revs);
1520

1521
	if (revs->ancestry_path)
1522
		limit_to_ancestry(revs->ancestry_path_bottoms, newlist);
1523

1524
	/*
1525
	 * Check if any commits have become TREESAME by some of their parents
1526
	 * becoming UNINTERESTING.
1527
	 */
1528
	if (limiting_can_increase_treesame(revs)) {
1529
		struct commit_list *list = NULL;
1530
		for (list = newlist; list; list = list->next) {
1531
			struct commit *c = list->item;
1532
			if (c->object.flags & (UNINTERESTING | TREESAME))
1533
				continue;
1534
			update_treesame(revs, c);
1535
		}
1536
	}
1537

1538
	free_commit_list(original_list);
1539
	revs->commits = newlist;
1540
	return 0;
1541
}
1542

1543
/*
1544
 * Add an entry to refs->cmdline with the specified information.
1545
 * *name is copied.
1546
 */
1547
static void add_rev_cmdline(struct rev_info *revs,
1548
			    struct object *item,
1549
			    const char *name,
1550
			    int whence,
1551
			    unsigned flags)
1552
{
1553
	struct rev_cmdline_info *info = &revs->cmdline;
1554
	unsigned int nr = info->nr;
1555

1556
	ALLOC_GROW(info->rev, nr + 1, info->alloc);
1557
	info->rev[nr].item = item;
1558
	info->rev[nr].name = xstrdup(name);
1559
	info->rev[nr].whence = whence;
1560
	info->rev[nr].flags = flags;
1561
	info->nr++;
1562
}
1563

1564
static void add_rev_cmdline_list(struct rev_info *revs,
1565
				 struct commit_list *commit_list,
1566
				 int whence,
1567
				 unsigned flags)
1568
{
1569
	while (commit_list) {
1570
		struct object *object = &commit_list->item->object;
1571
		add_rev_cmdline(revs, object, oid_to_hex(&object->oid),
1572
				whence, flags);
1573
		commit_list = commit_list->next;
1574
	}
1575
}
1576

1577
int ref_excluded(const struct ref_exclusions *exclusions, const char *path)
1578
{
1579
	const char *stripped_path = strip_namespace(path);
1580
	struct string_list_item *item;
1581

1582
	for_each_string_list_item(item, &exclusions->excluded_refs) {
1583
		if (!wildmatch(item->string, path, 0))
1584
			return 1;
1585
	}
1586

1587
	if (ref_is_hidden(stripped_path, path, &exclusions->hidden_refs))
1588
		return 1;
1589

1590
	return 0;
1591
}
1592

1593
void init_ref_exclusions(struct ref_exclusions *exclusions)
1594
{
1595
	struct ref_exclusions blank = REF_EXCLUSIONS_INIT;
1596
	memcpy(exclusions, &blank, sizeof(*exclusions));
1597
}
1598

1599
void clear_ref_exclusions(struct ref_exclusions *exclusions)
1600
{
1601
	string_list_clear(&exclusions->excluded_refs, 0);
1602
	strvec_clear(&exclusions->hidden_refs);
1603
	exclusions->hidden_refs_configured = 0;
1604
}
1605

1606
void add_ref_exclusion(struct ref_exclusions *exclusions, const char *exclude)
1607
{
1608
	string_list_append(&exclusions->excluded_refs, exclude);
1609
}
1610

1611
struct exclude_hidden_refs_cb {
1612
	struct ref_exclusions *exclusions;
1613
	const char *section;
1614
};
1615

1616
static int hide_refs_config(const char *var, const char *value,
1617
			    const struct config_context *ctx UNUSED,
1618
			    void *cb_data)
1619
{
1620
	struct exclude_hidden_refs_cb *cb = cb_data;
1621
	cb->exclusions->hidden_refs_configured = 1;
1622
	return parse_hide_refs_config(var, value, cb->section,
1623
				      &cb->exclusions->hidden_refs);
1624
}
1625

1626
void exclude_hidden_refs(struct ref_exclusions *exclusions, const char *section)
1627
{
1628
	struct exclude_hidden_refs_cb cb;
1629

1630
	if (strcmp(section, "fetch") && strcmp(section, "receive") &&
1631
			strcmp(section, "uploadpack"))
1632
		die(_("unsupported section for hidden refs: %s"), section);
1633

1634
	if (exclusions->hidden_refs_configured)
1635
		die(_("--exclude-hidden= passed more than once"));
1636

1637
	cb.exclusions = exclusions;
1638
	cb.section = section;
1639

1640
	git_config(hide_refs_config, &cb);
1641
}
1642

1643
struct all_refs_cb {
1644
	int all_flags;
1645
	int warned_bad_reflog;
1646
	struct rev_info *all_revs;
1647
	const char *name_for_errormsg;
1648
	struct worktree *wt;
1649
};
1650

1651
static int handle_one_ref(const char *path, const char *referent UNUSED, const struct object_id *oid,
1652
			  int flag UNUSED,
1653
			  void *cb_data)
1654
{
1655
	struct all_refs_cb *cb = cb_data;
1656
	struct object *object;
1657

1658
	if (ref_excluded(&cb->all_revs->ref_excludes, path))
1659
	    return 0;
1660

1661
	object = get_reference(cb->all_revs, path, oid, cb->all_flags);
1662
	add_rev_cmdline(cb->all_revs, object, path, REV_CMD_REF, cb->all_flags);
1663
	add_pending_object(cb->all_revs, object, path);
1664
	return 0;
1665
}
1666

1667
static void init_all_refs_cb(struct all_refs_cb *cb, struct rev_info *revs,
1668
	unsigned flags)
1669
{
1670
	cb->all_revs = revs;
1671
	cb->all_flags = flags;
1672
	revs->rev_input_given = 1;
1673
	cb->wt = NULL;
1674
}
1675

1676
static void handle_refs(struct ref_store *refs,
1677
			struct rev_info *revs, unsigned flags,
1678
			int (*for_each)(struct ref_store *, each_ref_fn, void *))
1679
{
1680
	struct all_refs_cb cb;
1681

1682
	if (!refs) {
1683
		/* this could happen with uninitialized submodules */
1684
		return;
1685
	}
1686

1687
	init_all_refs_cb(&cb, revs, flags);
1688
	for_each(refs, handle_one_ref, &cb);
1689
}
1690

1691
static void handle_one_reflog_commit(struct object_id *oid, void *cb_data)
1692
{
1693
	struct all_refs_cb *cb = cb_data;
1694
	if (!is_null_oid(oid)) {
1695
		struct object *o = parse_object(cb->all_revs->repo, oid);
1696
		if (o) {
1697
			o->flags |= cb->all_flags;
1698
			/* ??? CMDLINEFLAGS ??? */
1699
			add_pending_object(cb->all_revs, o, "");
1700
		}
1701
		else if (!cb->warned_bad_reflog) {
1702
			warning("reflog of '%s' references pruned commits",
1703
				cb->name_for_errormsg);
1704
			cb->warned_bad_reflog = 1;
1705
		}
1706
	}
1707
}
1708

1709
static int handle_one_reflog_ent(struct object_id *ooid, struct object_id *noid,
1710
				 const char *email UNUSED,
1711
				 timestamp_t timestamp UNUSED,
1712
				 int tz UNUSED,
1713
				 const char *message UNUSED,
1714
				 void *cb_data)
1715
{
1716
	handle_one_reflog_commit(ooid, cb_data);
1717
	handle_one_reflog_commit(noid, cb_data);
1718
	return 0;
1719
}
1720

1721
static int handle_one_reflog(const char *refname_in_wt, void *cb_data)
1722
{
1723
	struct all_refs_cb *cb = cb_data;
1724
	struct strbuf refname = STRBUF_INIT;
1725

1726
	cb->warned_bad_reflog = 0;
1727
	strbuf_worktree_ref(cb->wt, &refname, refname_in_wt);
1728
	cb->name_for_errormsg = refname.buf;
1729
	refs_for_each_reflog_ent(get_main_ref_store(the_repository),
1730
				 refname.buf,
1731
				 handle_one_reflog_ent, cb_data);
1732
	strbuf_release(&refname);
1733
	return 0;
1734
}
1735

1736
static void add_other_reflogs_to_pending(struct all_refs_cb *cb)
1737
{
1738
	struct worktree **worktrees, **p;
1739

1740
	worktrees = get_worktrees();
1741
	for (p = worktrees; *p; p++) {
1742
		struct worktree *wt = *p;
1743

1744
		if (wt->is_current)
1745
			continue;
1746

1747
		cb->wt = wt;
1748
		refs_for_each_reflog(get_worktree_ref_store(wt),
1749
				     handle_one_reflog,
1750
				     cb);
1751
	}
1752
	free_worktrees(worktrees);
1753
}
1754

1755
void add_reflogs_to_pending(struct rev_info *revs, unsigned flags)
1756
{
1757
	struct all_refs_cb cb;
1758

1759
	cb.all_revs = revs;
1760
	cb.all_flags = flags;
1761
	cb.wt = NULL;
1762
	refs_for_each_reflog(get_main_ref_store(the_repository),
1763
			     handle_one_reflog, &cb);
1764

1765
	if (!revs->single_worktree)
1766
		add_other_reflogs_to_pending(&cb);
1767
}
1768

1769
static void add_cache_tree(struct cache_tree *it, struct rev_info *revs,
1770
			   struct strbuf *path, unsigned int flags)
1771
{
1772
	size_t baselen = path->len;
1773
	int i;
1774

1775
	if (it->entry_count >= 0) {
1776
		struct tree *tree = lookup_tree(revs->repo, &it->oid);
1777
		tree->object.flags |= flags;
1778
		add_pending_object_with_path(revs, &tree->object, "",
1779
					     040000, path->buf);
1780
	}
1781

1782
	for (i = 0; i < it->subtree_nr; i++) {
1783
		struct cache_tree_sub *sub = it->down[i];
1784
		strbuf_addf(path, "%s%s", baselen ? "/" : "", sub->name);
1785
		add_cache_tree(sub->cache_tree, revs, path, flags);
1786
		strbuf_setlen(path, baselen);
1787
	}
1788

1789
}
1790

1791
static void add_resolve_undo_to_pending(struct index_state *istate, struct rev_info *revs)
1792
{
1793
	struct string_list_item *item;
1794
	struct string_list *resolve_undo = istate->resolve_undo;
1795

1796
	if (!resolve_undo)
1797
		return;
1798

1799
	for_each_string_list_item(item, resolve_undo) {
1800
		const char *path = item->string;
1801
		struct resolve_undo_info *ru = item->util;
1802
		int i;
1803

1804
		if (!ru)
1805
			continue;
1806
		for (i = 0; i < 3; i++) {
1807
			struct blob *blob;
1808

1809
			if (!ru->mode[i] || !S_ISREG(ru->mode[i]))
1810
				continue;
1811

1812
			blob = lookup_blob(revs->repo, &ru->oid[i]);
1813
			if (!blob) {
1814
				warning(_("resolve-undo records `%s` which is missing"),
1815
					oid_to_hex(&ru->oid[i]));
1816
				continue;
1817
			}
1818
			add_pending_object_with_path(revs, &blob->object, "",
1819
						     ru->mode[i], path);
1820
		}
1821
	}
1822
}
1823

1824
static void do_add_index_objects_to_pending(struct rev_info *revs,
1825
					    struct index_state *istate,
1826
					    unsigned int flags)
1827
{
1828
	int i;
1829

1830
	/* TODO: audit for interaction with sparse-index. */
1831
	ensure_full_index(istate);
1832
	for (i = 0; i < istate->cache_nr; i++) {
1833
		struct cache_entry *ce = istate->cache[i];
1834
		struct blob *blob;
1835

1836
		if (S_ISGITLINK(ce->ce_mode))
1837
			continue;
1838

1839
		blob = lookup_blob(revs->repo, &ce->oid);
1840
		if (!blob)
1841
			die("unable to add index blob to traversal");
1842
		blob->object.flags |= flags;
1843
		add_pending_object_with_path(revs, &blob->object, "",
1844
					     ce->ce_mode, ce->name);
1845
	}
1846

1847
	if (istate->cache_tree) {
1848
		struct strbuf path = STRBUF_INIT;
1849
		add_cache_tree(istate->cache_tree, revs, &path, flags);
1850
		strbuf_release(&path);
1851
	}
1852

1853
	add_resolve_undo_to_pending(istate, revs);
1854
}
1855

1856
void add_index_objects_to_pending(struct rev_info *revs, unsigned int flags)
1857
{
1858
	struct worktree **worktrees, **p;
1859

1860
	repo_read_index(revs->repo);
1861
	do_add_index_objects_to_pending(revs, revs->repo->index, flags);
1862

1863
	if (revs->single_worktree)
1864
		return;
1865

1866
	worktrees = get_worktrees();
1867
	for (p = worktrees; *p; p++) {
1868
		struct worktree *wt = *p;
1869
		struct index_state istate = INDEX_STATE_INIT(revs->repo);
1870

1871
		if (wt->is_current)
1872
			continue; /* current index already taken care of */
1873

1874
		if (read_index_from(&istate,
1875
				    worktree_git_path(the_repository, wt, "index"),
1876
				    get_worktree_git_dir(wt)) > 0)
1877
			do_add_index_objects_to_pending(revs, &istate, flags);
1878
		discard_index(&istate);
1879
	}
1880
	free_worktrees(worktrees);
1881
}
1882

1883
struct add_alternate_refs_data {
1884
	struct rev_info *revs;
1885
	unsigned int flags;
1886
};
1887

1888
static void add_one_alternate_ref(const struct object_id *oid,
1889
				  void *vdata)
1890
{
1891
	const char *name = ".alternate";
1892
	struct add_alternate_refs_data *data = vdata;
1893
	struct object *obj;
1894

1895
	obj = get_reference(data->revs, name, oid, data->flags);
1896
	add_rev_cmdline(data->revs, obj, name, REV_CMD_REV, data->flags);
1897
	add_pending_object(data->revs, obj, name);
1898
}
1899

1900
static void add_alternate_refs_to_pending(struct rev_info *revs,
1901
					  unsigned int flags)
1902
{
1903
	struct add_alternate_refs_data data;
1904
	data.revs = revs;
1905
	data.flags = flags;
1906
	for_each_alternate_ref(add_one_alternate_ref, &data);
1907
}
1908

1909
static int add_parents_only(struct rev_info *revs, const char *arg_, int flags,
1910
			    int exclude_parent)
1911
{
1912
	struct object_id oid;
1913
	struct object *it;
1914
	struct commit *commit;
1915
	struct commit_list *parents;
1916
	int parent_number;
1917
	const char *arg = arg_;
1918

1919
	if (*arg == '^') {
1920
		flags ^= UNINTERESTING | BOTTOM;
1921
		arg++;
1922
	}
1923
	if (repo_get_oid_committish(the_repository, arg, &oid))
1924
		return 0;
1925
	while (1) {
1926
		it = get_reference(revs, arg, &oid, 0);
1927
		if (!it && revs->ignore_missing)
1928
			return 0;
1929
		if (it->type != OBJ_TAG)
1930
			break;
1931
		if (!((struct tag*)it)->tagged)
1932
			return 0;
1933
		oidcpy(&oid, &((struct tag*)it)->tagged->oid);
1934
	}
1935
	if (it->type != OBJ_COMMIT)
1936
		return 0;
1937
	commit = (struct commit *)it;
1938
	if (exclude_parent &&
1939
	    exclude_parent > commit_list_count(commit->parents))
1940
		return 0;
1941
	for (parents = commit->parents, parent_number = 1;
1942
	     parents;
1943
	     parents = parents->next, parent_number++) {
1944
		if (exclude_parent && parent_number != exclude_parent)
1945
			continue;
1946

1947
		it = &parents->item->object;
1948
		it->flags |= flags;
1949
		add_rev_cmdline(revs, it, arg_, REV_CMD_PARENTS_ONLY, flags);
1950
		add_pending_object(revs, it, arg);
1951
	}
1952
	return 1;
1953
}
1954

1955
void repo_init_revisions(struct repository *r,
1956
			 struct rev_info *revs,
1957
			 const char *prefix)
1958
{
1959
	struct rev_info blank = REV_INFO_INIT;
1960
	memcpy(revs, &blank, sizeof(*revs));
1961

1962
	revs->repo = r;
1963
	revs->pruning.repo = r;
1964
	revs->pruning.add_remove = file_add_remove;
1965
	revs->pruning.change = file_change;
1966
	revs->pruning.change_fn_data = revs;
1967
	revs->prefix = prefix;
1968

1969
	grep_init(&revs->grep_filter, revs->repo);
1970
	revs->grep_filter.status_only = 1;
1971

1972
	repo_diff_setup(revs->repo, &revs->diffopt);
1973
	if (prefix && !revs->diffopt.prefix) {
1974
		revs->diffopt.prefix = prefix;
1975
		revs->diffopt.prefix_length = strlen(prefix);
1976
	}
1977

1978
	init_display_notes(&revs->notes_opt);
1979
	list_objects_filter_init(&revs->filter);
1980
	init_ref_exclusions(&revs->ref_excludes);
1981
	oidset_init(&revs->missing_commits, 0);
1982
}
1983

1984
static void add_pending_commit_list(struct rev_info *revs,
1985
				    struct commit_list *commit_list,
1986
				    unsigned int flags)
1987
{
1988
	while (commit_list) {
1989
		struct object *object = &commit_list->item->object;
1990
		object->flags |= flags;
1991
		add_pending_object(revs, object, oid_to_hex(&object->oid));
1992
		commit_list = commit_list->next;
1993
	}
1994
}
1995

1996
static const char *lookup_other_head(struct object_id *oid)
1997
{
1998
	int i;
1999
	static const char *const other_head[] = {
2000
		"MERGE_HEAD", "CHERRY_PICK_HEAD", "REVERT_HEAD", "REBASE_HEAD"
2001
	};
2002

2003
	for (i = 0; i < ARRAY_SIZE(other_head); i++)
2004
		if (!refs_read_ref_full(get_main_ref_store(the_repository), other_head[i],
2005
					RESOLVE_REF_READING | RESOLVE_REF_NO_RECURSE,
2006
					oid, NULL)) {
2007
			if (is_null_oid(oid))
2008
				die(_("%s exists but is a symbolic ref"), other_head[i]);
2009
			return other_head[i];
2010
		}
2011

2012
	die(_("--merge requires one of the pseudorefs MERGE_HEAD, CHERRY_PICK_HEAD, REVERT_HEAD or REBASE_HEAD"));
2013
}
2014

2015
static void prepare_show_merge(struct rev_info *revs)
2016
{
2017
	struct commit_list *bases = NULL;
2018
	struct commit *head, *other;
2019
	struct object_id oid;
2020
	const char *other_name;
2021
	const char **prune = NULL;
2022
	int i, prune_num = 1; /* counting terminating NULL */
2023
	struct index_state *istate = revs->repo->index;
2024

2025
	if (repo_get_oid(the_repository, "HEAD", &oid))
2026
		die("--merge without HEAD?");
2027
	head = lookup_commit_or_die(&oid, "HEAD");
2028
	other_name = lookup_other_head(&oid);
2029
	other = lookup_commit_or_die(&oid, other_name);
2030
	add_pending_object(revs, &head->object, "HEAD");
2031
	add_pending_object(revs, &other->object, other_name);
2032
	if (repo_get_merge_bases(the_repository, head, other, &bases) < 0)
2033
		exit(128);
2034
	add_rev_cmdline_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING | BOTTOM);
2035
	add_pending_commit_list(revs, bases, UNINTERESTING | BOTTOM);
2036
	free_commit_list(bases);
2037
	head->object.flags |= SYMMETRIC_LEFT;
2038

2039
	if (!istate->cache_nr)
2040
		repo_read_index(revs->repo);
2041
	for (i = 0; i < istate->cache_nr; i++) {
2042
		const struct cache_entry *ce = istate->cache[i];
2043
		if (!ce_stage(ce))
2044
			continue;
2045
		if (ce_path_match(istate, ce, &revs->prune_data, NULL)) {
2046
			prune_num++;
2047
			REALLOC_ARRAY(prune, prune_num);
2048
			prune[prune_num-2] = ce->name;
2049
			prune[prune_num-1] = NULL;
2050
		}
2051
		while ((i+1 < istate->cache_nr) &&
2052
		       ce_same_name(ce, istate->cache[i+1]))
2053
			i++;
2054
	}
2055
	clear_pathspec(&revs->prune_data);
2056
	parse_pathspec(&revs->prune_data, PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
2057
		       PATHSPEC_PREFER_FULL | PATHSPEC_LITERAL_PATH, "", prune);
2058
	revs->limited = 1;
2059
}
2060

2061
static int dotdot_missing(const char *arg, char *dotdot,
2062
			  struct rev_info *revs, int symmetric)
2063
{
2064
	if (revs->ignore_missing)
2065
		return 0;
2066
	/* de-munge so we report the full argument */
2067
	*dotdot = '.';
2068
	die(symmetric
2069
	    ? "Invalid symmetric difference expression %s"
2070
	    : "Invalid revision range %s", arg);
2071
}
2072

2073
static int handle_dotdot_1(const char *arg, char *dotdot,
2074
			   struct rev_info *revs, int flags,
2075
			   int cant_be_filename,
2076
			   struct object_context *a_oc,
2077
			   struct object_context *b_oc)
2078
{
2079
	const char *a_name, *b_name;
2080
	struct object_id a_oid, b_oid;
2081
	struct object *a_obj, *b_obj;
2082
	unsigned int a_flags, b_flags;
2083
	int symmetric = 0;
2084
	unsigned int flags_exclude = flags ^ (UNINTERESTING | BOTTOM);
2085
	unsigned int oc_flags = GET_OID_COMMITTISH | GET_OID_RECORD_PATH;
2086

2087
	a_name = arg;
2088
	if (!*a_name)
2089
		a_name = "HEAD";
2090

2091
	b_name = dotdot + 2;
2092
	if (*b_name == '.') {
2093
		symmetric = 1;
2094
		b_name++;
2095
	}
2096
	if (!*b_name)
2097
		b_name = "HEAD";
2098

2099
	if (get_oid_with_context(revs->repo, a_name, oc_flags, &a_oid, a_oc) ||
2100
	    get_oid_with_context(revs->repo, b_name, oc_flags, &b_oid, b_oc))
2101
		return -1;
2102

2103
	if (!cant_be_filename) {
2104
		*dotdot = '.';
2105
		verify_non_filename(revs->prefix, arg);
2106
		*dotdot = '\0';
2107
	}
2108

2109
	a_obj = parse_object(revs->repo, &a_oid);
2110
	b_obj = parse_object(revs->repo, &b_oid);
2111
	if (!a_obj || !b_obj)
2112
		return dotdot_missing(arg, dotdot, revs, symmetric);
2113

2114
	if (!symmetric) {
2115
		/* just A..B */
2116
		b_flags = flags;
2117
		a_flags = flags_exclude;
2118
	} else {
2119
		/* A...B -- find merge bases between the two */
2120
		struct commit *a, *b;
2121
		struct commit_list *exclude = NULL;
2122

2123
		a = lookup_commit_reference(revs->repo, &a_obj->oid);
2124
		b = lookup_commit_reference(revs->repo, &b_obj->oid);
2125
		if (!a || !b)
2126
			return dotdot_missing(arg, dotdot, revs, symmetric);
2127

2128
		if (repo_get_merge_bases(the_repository, a, b, &exclude) < 0) {
2129
			free_commit_list(exclude);
2130
			return -1;
2131
		}
2132
		add_rev_cmdline_list(revs, exclude, REV_CMD_MERGE_BASE,
2133
				     flags_exclude);
2134
		add_pending_commit_list(revs, exclude, flags_exclude);
2135
		free_commit_list(exclude);
2136

2137
		b_flags = flags;
2138
		a_flags = flags | SYMMETRIC_LEFT;
2139
	}
2140

2141
	a_obj->flags |= a_flags;
2142
	b_obj->flags |= b_flags;
2143
	add_rev_cmdline(revs, a_obj, a_name, REV_CMD_LEFT, a_flags);
2144
	add_rev_cmdline(revs, b_obj, b_name, REV_CMD_RIGHT, b_flags);
2145
	add_pending_object_with_path(revs, a_obj, a_name, a_oc->mode, a_oc->path);
2146
	add_pending_object_with_path(revs, b_obj, b_name, b_oc->mode, b_oc->path);
2147
	return 0;
2148
}
2149

2150
static int handle_dotdot(const char *arg,
2151
			 struct rev_info *revs, int flags,
2152
			 int cant_be_filename)
2153
{
2154
	struct object_context a_oc = {0}, b_oc = {0};
2155
	char *dotdot = strstr(arg, "..");
2156
	int ret;
2157

2158
	if (!dotdot)
2159
		return -1;
2160

2161
	*dotdot = '\0';
2162
	ret = handle_dotdot_1(arg, dotdot, revs, flags, cant_be_filename,
2163
			      &a_oc, &b_oc);
2164
	*dotdot = '.';
2165

2166
	object_context_release(&a_oc);
2167
	object_context_release(&b_oc);
2168
	return ret;
2169
}
2170

2171
static int handle_revision_arg_1(const char *arg_, struct rev_info *revs, int flags, unsigned revarg_opt)
2172
{
2173
	struct object_context oc = {0};
2174
	char *mark;
2175
	struct object *object;
2176
	struct object_id oid;
2177
	int local_flags;
2178
	const char *arg = arg_;
2179
	int cant_be_filename = revarg_opt & REVARG_CANNOT_BE_FILENAME;
2180
	unsigned get_sha1_flags = GET_OID_RECORD_PATH;
2181
	int ret;
2182

2183
	flags = flags & UNINTERESTING ? flags | BOTTOM : flags & ~BOTTOM;
2184

2185
	if (!cant_be_filename && !strcmp(arg, "..")) {
2186
		/*
2187
		 * Just ".."?  That is not a range but the
2188
		 * pathspec for the parent directory.
2189
		 */
2190
		ret = -1;
2191
		goto out;
2192
	}
2193

2194
	if (!handle_dotdot(arg, revs, flags, revarg_opt)) {
2195
		ret = 0;
2196
		goto out;
2197
	}
2198

2199
	mark = strstr(arg, "^@");
2200
	if (mark && !mark[2]) {
2201
		*mark = 0;
2202
		if (add_parents_only(revs, arg, flags, 0)) {
2203
			ret = 0;
2204
			goto out;
2205
		}
2206
		*mark = '^';
2207
	}
2208
	mark = strstr(arg, "^!");
2209
	if (mark && !mark[2]) {
2210
		*mark = 0;
2211
		if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), 0))
2212
			*mark = '^';
2213
	}
2214
	mark = strstr(arg, "^-");
2215
	if (mark) {
2216
		int exclude_parent = 1;
2217

2218
		if (mark[2]) {
2219
			if (strtol_i(mark + 2, 10, &exclude_parent) ||
2220
			    exclude_parent < 1) {
2221
				ret = -1;
2222
				goto out;
2223
			}
2224
		}
2225

2226
		*mark = 0;
2227
		if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), exclude_parent))
2228
			*mark = '^';
2229
	}
2230

2231
	local_flags = 0;
2232
	if (*arg == '^') {
2233
		local_flags = UNINTERESTING | BOTTOM;
2234
		arg++;
2235
	}
2236

2237
	if (revarg_opt & REVARG_COMMITTISH)
2238
		get_sha1_flags |= GET_OID_COMMITTISH;
2239

2240
	/*
2241
	 * Even if revs->do_not_die_on_missing_objects is set, we
2242
	 * should error out if we can't even get an oid, as
2243
	 * `--missing=print` should be able to report missing oids.
2244
	 */
2245
	if (get_oid_with_context(revs->repo, arg, get_sha1_flags, &oid, &oc)) {
2246
		ret = revs->ignore_missing ? 0 : -1;
2247
		goto out;
2248
	}
2249
	if (!cant_be_filename)
2250
		verify_non_filename(revs->prefix, arg);
2251
	object = get_reference(revs, arg, &oid, flags ^ local_flags);
2252
	if (!object) {
2253
		ret = (revs->ignore_missing || revs->do_not_die_on_missing_objects) ? 0 : -1;
2254
		goto out;
2255
	}
2256
	add_rev_cmdline(revs, object, arg_, REV_CMD_REV, flags ^ local_flags);
2257
	add_pending_object_with_path(revs, object, arg, oc.mode, oc.path);
2258

2259
	ret = 0;
2260

2261
out:
2262
	object_context_release(&oc);
2263
	return ret;
2264
}
2265

2266
int handle_revision_arg(const char *arg, struct rev_info *revs, int flags, unsigned revarg_opt)
2267
{
2268
	int ret = handle_revision_arg_1(arg, revs, flags, revarg_opt);
2269
	if (!ret)
2270
		revs->rev_input_given = 1;
2271
	return ret;
2272
}
2273

2274
static void read_pathspec_from_stdin(struct strbuf *sb,
2275
				     struct strvec *prune)
2276
{
2277
	while (strbuf_getline(sb, stdin) != EOF)
2278
		strvec_push(prune, sb->buf);
2279
}
2280

2281
static void add_grep(struct rev_info *revs, const char *ptn, enum grep_pat_token what)
2282
{
2283
	append_grep_pattern(&revs->grep_filter, ptn, "command line", 0, what);
2284
}
2285

2286
static void add_header_grep(struct rev_info *revs, enum grep_header_field field, const char *pattern)
2287
{
2288
	append_header_grep_pattern(&revs->grep_filter, field, pattern);
2289
}
2290

2291
static void add_message_grep(struct rev_info *revs, const char *pattern)
2292
{
2293
	add_grep(revs, pattern, GREP_PATTERN_BODY);
2294
}
2295

2296
static int parse_count(const char *arg)
2297
{
2298
	int count;
2299

2300
	if (strtol_i(arg, 10, &count) < 0)
2301
		die("'%s': not an integer", arg);
2302
	return count;
2303
}
2304

2305
static timestamp_t parse_age(const char *arg)
2306
{
2307
	timestamp_t num;
2308
	char *p;
2309

2310
	errno = 0;
2311
	num = parse_timestamp(arg, &p, 10);
2312
	if (errno || *p || p == arg)
2313
		die("'%s': not a number of seconds since epoch", arg);
2314
	return num;
2315
}
2316

2317
static int handle_revision_opt(struct rev_info *revs, int argc, const char **argv,
2318
			       int *unkc, const char **unkv,
2319
			       const struct setup_revision_opt* opt)
2320
{
2321
	const char *arg = argv[0];
2322
	const char *optarg = NULL;
2323
	int argcount;
2324
	const unsigned hexsz = the_hash_algo->hexsz;
2325

2326
	/* pseudo revision arguments */
2327
	if (!strcmp(arg, "--all") || !strcmp(arg, "--branches") ||
2328
	    !strcmp(arg, "--tags") || !strcmp(arg, "--remotes") ||
2329
	    !strcmp(arg, "--reflog") || !strcmp(arg, "--not") ||
2330
	    !strcmp(arg, "--no-walk") || !strcmp(arg, "--do-walk") ||
2331
	    !strcmp(arg, "--bisect") || starts_with(arg, "--glob=") ||
2332
	    !strcmp(arg, "--indexed-objects") ||
2333
	    !strcmp(arg, "--alternate-refs") ||
2334
	    starts_with(arg, "--exclude=") || starts_with(arg, "--exclude-hidden=") ||
2335
	    starts_with(arg, "--branches=") || starts_with(arg, "--tags=") ||
2336
	    starts_with(arg, "--remotes=") || starts_with(arg, "--no-walk="))
2337
	{
2338
		unkv[(*unkc)++] = arg;
2339
		return 1;
2340
	}
2341

2342
	if ((argcount = parse_long_opt("max-count", argv, &optarg))) {
2343
		revs->max_count = parse_count(optarg);
2344
		revs->no_walk = 0;
2345
		return argcount;
2346
	} else if ((argcount = parse_long_opt("skip", argv, &optarg))) {
2347
		revs->skip_count = parse_count(optarg);
2348
		return argcount;
2349
	} else if ((*arg == '-') && isdigit(arg[1])) {
2350
		/* accept -<digit>, like traditional "head" */
2351
		revs->max_count = parse_count(arg + 1);
2352
		revs->no_walk = 0;
2353
	} else if (!strcmp(arg, "-n")) {
2354
		if (argc <= 1)
2355
			return error("-n requires an argument");
2356
		revs->max_count = parse_count(argv[1]);
2357
		revs->no_walk = 0;
2358
		return 2;
2359
	} else if (skip_prefix(arg, "-n", &optarg)) {
2360
		revs->max_count = parse_count(optarg);
2361
		revs->no_walk = 0;
2362
	} else if ((argcount = parse_long_opt("max-age", argv, &optarg))) {
2363
		revs->max_age = parse_age(optarg);
2364
		return argcount;
2365
	} else if ((argcount = parse_long_opt("since", argv, &optarg))) {
2366
		revs->max_age = approxidate(optarg);
2367
		return argcount;
2368
	} else if ((argcount = parse_long_opt("since-as-filter", argv, &optarg))) {
2369
		revs->max_age_as_filter = approxidate(optarg);
2370
		return argcount;
2371
	} else if ((argcount = parse_long_opt("after", argv, &optarg))) {
2372
		revs->max_age = approxidate(optarg);
2373
		return argcount;
2374
	} else if ((argcount = parse_long_opt("min-age", argv, &optarg))) {
2375
		revs->min_age = parse_age(optarg);
2376
		return argcount;
2377
	} else if ((argcount = parse_long_opt("before", argv, &optarg))) {
2378
		revs->min_age = approxidate(optarg);
2379
		return argcount;
2380
	} else if ((argcount = parse_long_opt("until", argv, &optarg))) {
2381
		revs->min_age = approxidate(optarg);
2382
		return argcount;
2383
	} else if (!strcmp(arg, "--first-parent")) {
2384
		revs->first_parent_only = 1;
2385
	} else if (!strcmp(arg, "--exclude-first-parent-only")) {
2386
		revs->exclude_first_parent_only = 1;
2387
	} else if (!strcmp(arg, "--ancestry-path")) {
2388
		revs->ancestry_path = 1;
2389
		revs->simplify_history = 0;
2390
		revs->limited = 1;
2391
		revs->ancestry_path_implicit_bottoms = 1;
2392
	} else if (skip_prefix(arg, "--ancestry-path=", &optarg)) {
2393
		struct commit *c;
2394
		struct object_id oid;
2395
		const char *msg = _("could not get commit for --ancestry-path argument %s");
2396

2397
		revs->ancestry_path = 1;
2398
		revs->simplify_history = 0;
2399
		revs->limited = 1;
2400

2401
		if (repo_get_oid_committish(revs->repo, optarg, &oid))
2402
			return error(msg, optarg);
2403
		get_reference(revs, optarg, &oid, ANCESTRY_PATH);
2404
		c = lookup_commit_reference(revs->repo, &oid);
2405
		if (!c)
2406
			return error(msg, optarg);
2407
		commit_list_insert(c, &revs->ancestry_path_bottoms);
2408
	} else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) {
2409
		init_reflog_walk(&revs->reflog_info);
2410
	} else if (!strcmp(arg, "--default")) {
2411
		if (argc <= 1)
2412
			return error("bad --default argument");
2413
		revs->def = argv[1];
2414
		return 2;
2415
	} else if (!strcmp(arg, "--merge")) {
2416
		revs->show_merge = 1;
2417
	} else if (!strcmp(arg, "--topo-order")) {
2418
		revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
2419
		revs->topo_order = 1;
2420
	} else if (!strcmp(arg, "--simplify-merges")) {
2421
		revs->simplify_merges = 1;
2422
		revs->topo_order = 1;
2423
		revs->rewrite_parents = 1;
2424
		revs->simplify_history = 0;
2425
		revs->limited = 1;
2426
	} else if (!strcmp(arg, "--simplify-by-decoration")) {
2427
		revs->simplify_merges = 1;
2428
		revs->topo_order = 1;
2429
		revs->rewrite_parents = 1;
2430
		revs->simplify_history = 0;
2431
		revs->simplify_by_decoration = 1;
2432
		revs->limited = 1;
2433
		revs->prune = 1;
2434
	} else if (!strcmp(arg, "--date-order")) {
2435
		revs->sort_order = REV_SORT_BY_COMMIT_DATE;
2436
		revs->topo_order = 1;
2437
	} else if (!strcmp(arg, "--author-date-order")) {
2438
		revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
2439
		revs->topo_order = 1;
2440
	} else if (!strcmp(arg, "--early-output")) {
2441
		revs->early_output = 100;
2442
		revs->topo_order = 1;
2443
	} else if (skip_prefix(arg, "--early-output=", &optarg)) {
2444
		if (strtoul_ui(optarg, 10, &revs->early_output) < 0)
2445
			die("'%s': not a non-negative integer", optarg);
2446
		revs->topo_order = 1;
2447
	} else if (!strcmp(arg, "--parents")) {
2448
		revs->rewrite_parents = 1;
2449
		revs->print_parents = 1;
2450
	} else if (!strcmp(arg, "--dense")) {
2451
		revs->dense = 1;
2452
	} else if (!strcmp(arg, "--sparse")) {
2453
		revs->dense = 0;
2454
	} else if (!strcmp(arg, "--in-commit-order")) {
2455
		revs->tree_blobs_in_commit_order = 1;
2456
	} else if (!strcmp(arg, "--remove-empty")) {
2457
		revs->remove_empty_trees = 1;
2458
	} else if (!strcmp(arg, "--merges")) {
2459
		revs->min_parents = 2;
2460
	} else if (!strcmp(arg, "--no-merges")) {
2461
		revs->max_parents = 1;
2462
	} else if (skip_prefix(arg, "--min-parents=", &optarg)) {
2463
		revs->min_parents = parse_count(optarg);
2464
	} else if (!strcmp(arg, "--no-min-parents")) {
2465
		revs->min_parents = 0;
2466
	} else if (skip_prefix(arg, "--max-parents=", &optarg)) {
2467
		revs->max_parents = parse_count(optarg);
2468
	} else if (!strcmp(arg, "--no-max-parents")) {
2469
		revs->max_parents = -1;
2470
	} else if (!strcmp(arg, "--boundary")) {
2471
		revs->boundary = 1;
2472
	} else if (!strcmp(arg, "--left-right")) {
2473
		revs->left_right = 1;
2474
	} else if (!strcmp(arg, "--left-only")) {
2475
		if (revs->right_only)
2476
			die(_("options '%s' and '%s' cannot be used together"),
2477
			    "--left-only", "--right-only/--cherry");
2478
		revs->left_only = 1;
2479
	} else if (!strcmp(arg, "--right-only")) {
2480
		if (revs->left_only)
2481
			die(_("options '%s' and '%s' cannot be used together"), "--right-only", "--left-only");
2482
		revs->right_only = 1;
2483
	} else if (!strcmp(arg, "--cherry")) {
2484
		if (revs->left_only)
2485
			die(_("options '%s' and '%s' cannot be used together"), "--cherry", "--left-only");
2486
		revs->cherry_mark = 1;
2487
		revs->right_only = 1;
2488
		revs->max_parents = 1;
2489
		revs->limited = 1;
2490
	} else if (!strcmp(arg, "--count")) {
2491
		revs->count = 1;
2492
	} else if (!strcmp(arg, "--cherry-mark")) {
2493
		if (revs->cherry_pick)
2494
			die(_("options '%s' and '%s' cannot be used together"), "--cherry-mark", "--cherry-pick");
2495
		revs->cherry_mark = 1;
2496
		revs->limited = 1; /* needs limit_list() */
2497
	} else if (!strcmp(arg, "--cherry-pick")) {
2498
		if (revs->cherry_mark)
2499
			die(_("options '%s' and '%s' cannot be used together"), "--cherry-pick", "--cherry-mark");
2500
		revs->cherry_pick = 1;
2501
		revs->limited = 1;
2502
	} else if (!strcmp(arg, "--objects")) {
2503
		revs->tag_objects = 1;
2504
		revs->tree_objects = 1;
2505
		revs->blob_objects = 1;
2506
	} else if (!strcmp(arg, "--objects-edge")) {
2507
		revs->tag_objects = 1;
2508
		revs->tree_objects = 1;
2509
		revs->blob_objects = 1;
2510
		revs->edge_hint = 1;
2511
	} else if (!strcmp(arg, "--objects-edge-aggressive")) {
2512
		revs->tag_objects = 1;
2513
		revs->tree_objects = 1;
2514
		revs->blob_objects = 1;
2515
		revs->edge_hint = 1;
2516
		revs->edge_hint_aggressive = 1;
2517
	} else if (!strcmp(arg, "--verify-objects")) {
2518
		revs->tag_objects = 1;
2519
		revs->tree_objects = 1;
2520
		revs->blob_objects = 1;
2521
		revs->verify_objects = 1;
2522
		disable_commit_graph(revs->repo);
2523
	} else if (!strcmp(arg, "--unpacked")) {
2524
		revs->unpacked = 1;
2525
	} else if (starts_with(arg, "--unpacked=")) {
2526
		die(_("--unpacked=<packfile> no longer supported"));
2527
	} else if (!strcmp(arg, "--no-kept-objects")) {
2528
		revs->no_kept_objects = 1;
2529
		revs->keep_pack_cache_flags |= IN_CORE_KEEP_PACKS;
2530
		revs->keep_pack_cache_flags |= ON_DISK_KEEP_PACKS;
2531
	} else if (skip_prefix(arg, "--no-kept-objects=", &optarg)) {
2532
		revs->no_kept_objects = 1;
2533
		if (!strcmp(optarg, "in-core"))
2534
			revs->keep_pack_cache_flags |= IN_CORE_KEEP_PACKS;
2535
		if (!strcmp(optarg, "on-disk"))
2536
			revs->keep_pack_cache_flags |= ON_DISK_KEEP_PACKS;
2537
	} else if (!strcmp(arg, "-r")) {
2538
		revs->diff = 1;
2539
		revs->diffopt.flags.recursive = 1;
2540
	} else if (!strcmp(arg, "-t")) {
2541
		revs->diff = 1;
2542
		revs->diffopt.flags.recursive = 1;
2543
		revs->diffopt.flags.tree_in_recursive = 1;
2544
	} else if ((argcount = diff_merges_parse_opts(revs, argv))) {
2545
		return argcount;
2546
	} else if (!strcmp(arg, "-v")) {
2547
		revs->verbose_header = 1;
2548
	} else if (!strcmp(arg, "--pretty")) {
2549
		revs->verbose_header = 1;
2550
		revs->pretty_given = 1;
2551
		get_commit_format(NULL, revs);
2552
	} else if (skip_prefix(arg, "--pretty=", &optarg) ||
2553
		   skip_prefix(arg, "--format=", &optarg)) {
2554
		/*
2555
		 * Detached form ("--pretty X" as opposed to "--pretty=X")
2556
		 * not allowed, since the argument is optional.
2557
		 */
2558
		revs->verbose_header = 1;
2559
		revs->pretty_given = 1;
2560
		get_commit_format(optarg, revs);
2561
	} else if (!strcmp(arg, "--expand-tabs")) {
2562
		revs->expand_tabs_in_log = 8;
2563
	} else if (!strcmp(arg, "--no-expand-tabs")) {
2564
		revs->expand_tabs_in_log = 0;
2565
	} else if (skip_prefix(arg, "--expand-tabs=", &arg)) {
2566
		int val;
2567
		if (strtol_i(arg, 10, &val) < 0 || val < 0)
2568
			die("'%s': not a non-negative integer", arg);
2569
		revs->expand_tabs_in_log = val;
2570
	} else if (!strcmp(arg, "--show-notes") || !strcmp(arg, "--notes")) {
2571
		enable_default_display_notes(&revs->notes_opt, &revs->show_notes);
2572
		revs->show_notes_given = 1;
2573
	} else if (!strcmp(arg, "--show-signature")) {
2574
		revs->show_signature = 1;
2575
	} else if (!strcmp(arg, "--no-show-signature")) {
2576
		revs->show_signature = 0;
2577
	} else if (!strcmp(arg, "--show-linear-break")) {
2578
		revs->break_bar = "                    ..........";
2579
		revs->track_linear = 1;
2580
		revs->track_first_time = 1;
2581
	} else if (skip_prefix(arg, "--show-linear-break=", &optarg)) {
2582
		revs->break_bar = xstrdup(optarg);
2583
		revs->track_linear = 1;
2584
		revs->track_first_time = 1;
2585
	} else if (!strcmp(arg, "--show-notes-by-default")) {
2586
		revs->show_notes_by_default = 1;
2587
	} else if (skip_prefix(arg, "--show-notes=", &optarg) ||
2588
		   skip_prefix(arg, "--notes=", &optarg)) {
2589
		if (starts_with(arg, "--show-notes=") &&
2590
		    revs->notes_opt.use_default_notes < 0)
2591
			revs->notes_opt.use_default_notes = 1;
2592
		enable_ref_display_notes(&revs->notes_opt, &revs->show_notes, optarg);
2593
		revs->show_notes_given = 1;
2594
	} else if (!strcmp(arg, "--no-notes")) {
2595
		disable_display_notes(&revs->notes_opt, &revs->show_notes);
2596
		revs->show_notes_given = 1;
2597
	} else if (!strcmp(arg, "--standard-notes")) {
2598
		revs->show_notes_given = 1;
2599
		revs->notes_opt.use_default_notes = 1;
2600
	} else if (!strcmp(arg, "--no-standard-notes")) {
2601
		revs->notes_opt.use_default_notes = 0;
2602
	} else if (!strcmp(arg, "--oneline")) {
2603
		revs->verbose_header = 1;
2604
		get_commit_format("oneline", revs);
2605
		revs->pretty_given = 1;
2606
		revs->abbrev_commit = 1;
2607
	} else if (!strcmp(arg, "--graph")) {
2608
		graph_clear(revs->graph);
2609
		revs->graph = graph_init(revs);
2610
	} else if (!strcmp(arg, "--no-graph")) {
2611
		graph_clear(revs->graph);
2612
		revs->graph = NULL;
2613
	} else if (!strcmp(arg, "--encode-email-headers")) {
2614
		revs->encode_email_headers = 1;
2615
	} else if (!strcmp(arg, "--no-encode-email-headers")) {
2616
		revs->encode_email_headers = 0;
2617
	} else if (!strcmp(arg, "--root")) {
2618
		revs->show_root_diff = 1;
2619
	} else if (!strcmp(arg, "--no-commit-id")) {
2620
		revs->no_commit_id = 1;
2621
	} else if (!strcmp(arg, "--always")) {
2622
		revs->always_show_header = 1;
2623
	} else if (!strcmp(arg, "--no-abbrev")) {
2624
		revs->abbrev = 0;
2625
	} else if (!strcmp(arg, "--abbrev")) {
2626
		revs->abbrev = DEFAULT_ABBREV;
2627
	} else if (skip_prefix(arg, "--abbrev=", &optarg)) {
2628
		revs->abbrev = strtoul(optarg, NULL, 10);
2629
		if (revs->abbrev < MINIMUM_ABBREV)
2630
			revs->abbrev = MINIMUM_ABBREV;
2631
		else if (revs->abbrev > hexsz)
2632
			revs->abbrev = hexsz;
2633
	} else if (!strcmp(arg, "--abbrev-commit")) {
2634
		revs->abbrev_commit = 1;
2635
		revs->abbrev_commit_given = 1;
2636
	} else if (!strcmp(arg, "--no-abbrev-commit")) {
2637
		revs->abbrev_commit = 0;
2638
	} else if (!strcmp(arg, "--full-diff")) {
2639
		revs->diff = 1;
2640
		revs->full_diff = 1;
2641
	} else if (!strcmp(arg, "--show-pulls")) {
2642
		revs->show_pulls = 1;
2643
	} else if (!strcmp(arg, "--full-history")) {
2644
		revs->simplify_history = 0;
2645
	} else if (!strcmp(arg, "--relative-date")) {
2646
		revs->date_mode.type = DATE_RELATIVE;
2647
		revs->date_mode_explicit = 1;
2648
	} else if ((argcount = parse_long_opt("date", argv, &optarg))) {
2649
		parse_date_format(optarg, &revs->date_mode);
2650
		revs->date_mode_explicit = 1;
2651
		return argcount;
2652
	} else if (!strcmp(arg, "--log-size")) {
2653
		revs->show_log_size = 1;
2654
	}
2655
	/*
2656
	 * Grepping the commit log
2657
	 */
2658
	else if ((argcount = parse_long_opt("author", argv, &optarg))) {
2659
		add_header_grep(revs, GREP_HEADER_AUTHOR, optarg);
2660
		return argcount;
2661
	} else if ((argcount = parse_long_opt("committer", argv, &optarg))) {
2662
		add_header_grep(revs, GREP_HEADER_COMMITTER, optarg);
2663
		return argcount;
2664
	} else if ((argcount = parse_long_opt("grep-reflog", argv, &optarg))) {
2665
		add_header_grep(revs, GREP_HEADER_REFLOG, optarg);
2666
		return argcount;
2667
	} else if ((argcount = parse_long_opt("grep", argv, &optarg))) {
2668
		add_message_grep(revs, optarg);
2669
		return argcount;
2670
	} else if (!strcmp(arg, "--basic-regexp")) {
2671
		revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_BRE;
2672
	} else if (!strcmp(arg, "--extended-regexp") || !strcmp(arg, "-E")) {
2673
		revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_ERE;
2674
	} else if (!strcmp(arg, "--regexp-ignore-case") || !strcmp(arg, "-i")) {
2675
		revs->grep_filter.ignore_case = 1;
2676
		revs->diffopt.pickaxe_opts |= DIFF_PICKAXE_IGNORE_CASE;
2677
	} else if (!strcmp(arg, "--fixed-strings") || !strcmp(arg, "-F")) {
2678
		revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_FIXED;
2679
	} else if (!strcmp(arg, "--perl-regexp") || !strcmp(arg, "-P")) {
2680
		revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_PCRE;
2681
	} else if (!strcmp(arg, "--all-match")) {
2682
		revs->grep_filter.all_match = 1;
2683
	} else if (!strcmp(arg, "--invert-grep")) {
2684
		revs->grep_filter.no_body_match = 1;
2685
	} else if ((argcount = parse_long_opt("encoding", argv, &optarg))) {
2686
		free(git_log_output_encoding);
2687
		if (strcmp(optarg, "none"))
2688
			git_log_output_encoding = xstrdup(optarg);
2689
		else
2690
			git_log_output_encoding = xstrdup("");
2691
		return argcount;
2692
	} else if (!strcmp(arg, "--reverse")) {
2693
		revs->reverse ^= 1;
2694
	} else if (!strcmp(arg, "--children")) {
2695
		revs->children.name = "children";
2696
		revs->limited = 1;
2697
	} else if (!strcmp(arg, "--ignore-missing")) {
2698
		revs->ignore_missing = 1;
2699
	} else if (opt && opt->allow_exclude_promisor_objects &&
2700
		   !strcmp(arg, "--exclude-promisor-objects")) {
2701
		if (fetch_if_missing)
2702
			BUG("exclude_promisor_objects can only be used when fetch_if_missing is 0");
2703
		revs->exclude_promisor_objects = 1;
2704
	} else {
2705
		int opts = diff_opt_parse(&revs->diffopt, argv, argc, revs->prefix);
2706
		if (!opts)
2707
			unkv[(*unkc)++] = arg;
2708
		return opts;
2709
	}
2710

2711
	return 1;
2712
}
2713

2714
void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx,
2715
			const struct option *options,
2716
			const char * const usagestr[])
2717
{
2718
	int n = handle_revision_opt(revs, ctx->argc, ctx->argv,
2719
				    &ctx->cpidx, ctx->out, NULL);
2720
	if (n <= 0) {
2721
		error("unknown option `%s'", ctx->argv[0]);
2722
		usage_with_options(usagestr, options);
2723
	}
2724
	ctx->argv += n;
2725
	ctx->argc -= n;
2726
}
2727

2728
void revision_opts_finish(struct rev_info *revs)
2729
{
2730
	if (revs->graph && revs->track_linear)
2731
		die(_("options '%s' and '%s' cannot be used together"), "--show-linear-break", "--graph");
2732

2733
	if (revs->graph) {
2734
		revs->topo_order = 1;
2735
		revs->rewrite_parents = 1;
2736
	}
2737
}
2738

2739
static int for_each_bisect_ref(struct ref_store *refs, each_ref_fn fn,
2740
			       void *cb_data, const char *term)
2741
{
2742
	struct strbuf bisect_refs = STRBUF_INIT;
2743
	int status;
2744
	strbuf_addf(&bisect_refs, "refs/bisect/%s", term);
2745
	status = refs_for_each_fullref_in(refs, bisect_refs.buf, NULL, fn, cb_data);
2746
	strbuf_release(&bisect_refs);
2747
	return status;
2748
}
2749

2750
static int for_each_bad_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
2751
{
2752
	return for_each_bisect_ref(refs, fn, cb_data, term_bad);
2753
}
2754

2755
static int for_each_good_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
2756
{
2757
	return for_each_bisect_ref(refs, fn, cb_data, term_good);
2758
}
2759

2760
static int handle_revision_pseudo_opt(struct rev_info *revs,
2761
				      const char **argv, int *flags)
2762
{
2763
	const char *arg = argv[0];
2764
	const char *optarg;
2765
	struct ref_store *refs;
2766
	int argcount;
2767

2768
	if (revs->repo != the_repository) {
2769
		/*
2770
		 * We need some something like get_submodule_worktrees()
2771
		 * before we can go through all worktrees of a submodule,
2772
		 * .e.g with adding all HEADs from --all, which is not
2773
		 * supported right now, so stick to single worktree.
2774
		 */
2775
		if (!revs->single_worktree)
2776
			BUG("--single-worktree cannot be used together with submodule");
2777
	}
2778
	refs = get_main_ref_store(revs->repo);
2779

2780
	/*
2781
	 * NOTE!
2782
	 *
2783
	 * Commands like "git shortlog" will not accept the options below
2784
	 * unless parse_revision_opt queues them (as opposed to erroring
2785
	 * out).
2786
	 *
2787
	 * When implementing your new pseudo-option, remember to
2788
	 * register it in the list at the top of handle_revision_opt.
2789
	 */
2790
	if (!strcmp(arg, "--all")) {
2791
		handle_refs(refs, revs, *flags, refs_for_each_ref);
2792
		handle_refs(refs, revs, *flags, refs_head_ref);
2793
		if (!revs->single_worktree) {
2794
			struct all_refs_cb cb;
2795

2796
			init_all_refs_cb(&cb, revs, *flags);
2797
			other_head_refs(handle_one_ref, &cb);
2798
		}
2799
		clear_ref_exclusions(&revs->ref_excludes);
2800
	} else if (!strcmp(arg, "--branches")) {
2801
		if (revs->ref_excludes.hidden_refs_configured)
2802
			return error(_("options '%s' and '%s' cannot be used together"),
2803
				     "--exclude-hidden", "--branches");
2804
		handle_refs(refs, revs, *flags, refs_for_each_branch_ref);
2805
		clear_ref_exclusions(&revs->ref_excludes);
2806
	} else if (!strcmp(arg, "--bisect")) {
2807
		read_bisect_terms(&term_bad, &term_good);
2808
		handle_refs(refs, revs, *flags, for_each_bad_bisect_ref);
2809
		handle_refs(refs, revs, *flags ^ (UNINTERESTING | BOTTOM),
2810
			    for_each_good_bisect_ref);
2811
		revs->bisect = 1;
2812
	} else if (!strcmp(arg, "--tags")) {
2813
		if (revs->ref_excludes.hidden_refs_configured)
2814
			return error(_("options '%s' and '%s' cannot be used together"),
2815
				     "--exclude-hidden", "--tags");
2816
		handle_refs(refs, revs, *flags, refs_for_each_tag_ref);
2817
		clear_ref_exclusions(&revs->ref_excludes);
2818
	} else if (!strcmp(arg, "--remotes")) {
2819
		if (revs->ref_excludes.hidden_refs_configured)
2820
			return error(_("options '%s' and '%s' cannot be used together"),
2821
				     "--exclude-hidden", "--remotes");
2822
		handle_refs(refs, revs, *flags, refs_for_each_remote_ref);
2823
		clear_ref_exclusions(&revs->ref_excludes);
2824
	} else if ((argcount = parse_long_opt("glob", argv, &optarg))) {
2825
		struct all_refs_cb cb;
2826
		init_all_refs_cb(&cb, revs, *flags);
2827
		refs_for_each_glob_ref(get_main_ref_store(the_repository),
2828
				       handle_one_ref, optarg, &cb);
2829
		clear_ref_exclusions(&revs->ref_excludes);
2830
		return argcount;
2831
	} else if ((argcount = parse_long_opt("exclude", argv, &optarg))) {
2832
		add_ref_exclusion(&revs->ref_excludes, optarg);
2833
		return argcount;
2834
	} else if ((argcount = parse_long_opt("exclude-hidden", argv, &optarg))) {
2835
		exclude_hidden_refs(&revs->ref_excludes, optarg);
2836
		return argcount;
2837
	} else if (skip_prefix(arg, "--branches=", &optarg)) {
2838
		struct all_refs_cb cb;
2839
		if (revs->ref_excludes.hidden_refs_configured)
2840
			return error(_("options '%s' and '%s' cannot be used together"),
2841
				     "--exclude-hidden", "--branches");
2842
		init_all_refs_cb(&cb, revs, *flags);
2843
		refs_for_each_glob_ref_in(get_main_ref_store(the_repository),
2844
					  handle_one_ref, optarg,
2845
					  "refs/heads/", &cb);
2846
		clear_ref_exclusions(&revs->ref_excludes);
2847
	} else if (skip_prefix(arg, "--tags=", &optarg)) {
2848
		struct all_refs_cb cb;
2849
		if (revs->ref_excludes.hidden_refs_configured)
2850
			return error(_("options '%s' and '%s' cannot be used together"),
2851
				     "--exclude-hidden", "--tags");
2852
		init_all_refs_cb(&cb, revs, *flags);
2853
		refs_for_each_glob_ref_in(get_main_ref_store(the_repository),
2854
					  handle_one_ref, optarg,
2855
					  "refs/tags/", &cb);
2856
		clear_ref_exclusions(&revs->ref_excludes);
2857
	} else if (skip_prefix(arg, "--remotes=", &optarg)) {
2858
		struct all_refs_cb cb;
2859
		if (revs->ref_excludes.hidden_refs_configured)
2860
			return error(_("options '%s' and '%s' cannot be used together"),
2861
				     "--exclude-hidden", "--remotes");
2862
		init_all_refs_cb(&cb, revs, *flags);
2863
		refs_for_each_glob_ref_in(get_main_ref_store(the_repository),
2864
					  handle_one_ref, optarg,
2865
					  "refs/remotes/", &cb);
2866
		clear_ref_exclusions(&revs->ref_excludes);
2867
	} else if (!strcmp(arg, "--reflog")) {
2868
		add_reflogs_to_pending(revs, *flags);
2869
	} else if (!strcmp(arg, "--indexed-objects")) {
2870
		add_index_objects_to_pending(revs, *flags);
2871
	} else if (!strcmp(arg, "--alternate-refs")) {
2872
		add_alternate_refs_to_pending(revs, *flags);
2873
	} else if (!strcmp(arg, "--not")) {
2874
		*flags ^= UNINTERESTING | BOTTOM;
2875
	} else if (!strcmp(arg, "--no-walk")) {
2876
		revs->no_walk = 1;
2877
	} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
2878
		/*
2879
		 * Detached form ("--no-walk X" as opposed to "--no-walk=X")
2880
		 * not allowed, since the argument is optional.
2881
		 */
2882
		revs->no_walk = 1;
2883
		if (!strcmp(optarg, "sorted"))
2884
			revs->unsorted_input = 0;
2885
		else if (!strcmp(optarg, "unsorted"))
2886
			revs->unsorted_input = 1;
2887
		else
2888
			return error("invalid argument to --no-walk");
2889
	} else if (!strcmp(arg, "--do-walk")) {
2890
		revs->no_walk = 0;
2891
	} else if (!strcmp(arg, "--single-worktree")) {
2892
		revs->single_worktree = 1;
2893
	} else if (skip_prefix(arg, ("--filter="), &arg)) {
2894
		parse_list_objects_filter(&revs->filter, arg);
2895
	} else if (!strcmp(arg, ("--no-filter"))) {
2896
		list_objects_filter_set_no_filter(&revs->filter);
2897
	} else {
2898
		return 0;
2899
	}
2900

2901
	return 1;
2902
}
2903

2904
static void read_revisions_from_stdin(struct rev_info *revs,
2905
				      struct strvec *prune)
2906
{
2907
	struct strbuf sb;
2908
	int seen_dashdash = 0;
2909
	int seen_end_of_options = 0;
2910
	int save_warning;
2911
	int flags = 0;
2912

2913
	save_warning = warn_on_object_refname_ambiguity;
2914
	warn_on_object_refname_ambiguity = 0;
2915

2916
	strbuf_init(&sb, 1000);
2917
	while (strbuf_getline(&sb, stdin) != EOF) {
2918
		if (!sb.len)
2919
			break;
2920

2921
		if (!strcmp(sb.buf, "--")) {
2922
			seen_dashdash = 1;
2923
			break;
2924
		}
2925

2926
		if (!seen_end_of_options && sb.buf[0] == '-') {
2927
			const char *argv[] = { sb.buf, NULL };
2928

2929
			if (!strcmp(sb.buf, "--end-of-options")) {
2930
				seen_end_of_options = 1;
2931
				continue;
2932
			}
2933

2934
			if (handle_revision_pseudo_opt(revs, argv, &flags) > 0)
2935
				continue;
2936

2937
			die(_("invalid option '%s' in --stdin mode"), sb.buf);
2938
		}
2939

2940
		if (handle_revision_arg(sb.buf, revs, flags,
2941
					REVARG_CANNOT_BE_FILENAME))
2942
			die("bad revision '%s'", sb.buf);
2943
	}
2944
	if (seen_dashdash)
2945
		read_pathspec_from_stdin(&sb, prune);
2946

2947
	strbuf_release(&sb);
2948
	warn_on_object_refname_ambiguity = save_warning;
2949
}
2950

2951
static void NORETURN diagnose_missing_default(const char *def)
2952
{
2953
	int flags;
2954
	const char *refname;
2955

2956
	refname = refs_resolve_ref_unsafe(get_main_ref_store(the_repository),
2957
					  def, 0, NULL, &flags);
2958
	if (!refname || !(flags & REF_ISSYMREF) || (flags & REF_ISBROKEN))
2959
		die(_("your current branch appears to be broken"));
2960

2961
	skip_prefix(refname, "refs/heads/", &refname);
2962
	die(_("your current branch '%s' does not have any commits yet"),
2963
	    refname);
2964
}
2965

2966
/*
2967
 * Parse revision information, filling in the "rev_info" structure,
2968
 * and removing the used arguments from the argument list.
2969
 *
2970
 * Returns the number of arguments left that weren't recognized
2971
 * (which are also moved to the head of the argument list)
2972
 */
2973
int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *opt)
2974
{
2975
	int i, flags, left, seen_dashdash, revarg_opt;
2976
	struct strvec prune_data = STRVEC_INIT;
2977
	int seen_end_of_options = 0;
2978

2979
	/* First, search for "--" */
2980
	if (opt && opt->assume_dashdash) {
2981
		seen_dashdash = 1;
2982
	} else {
2983
		seen_dashdash = 0;
2984
		for (i = 1; i < argc; i++) {
2985
			const char *arg = argv[i];
2986
			if (strcmp(arg, "--"))
2987
				continue;
2988
			if (opt && opt->free_removed_argv_elements)
2989
				free((char *)argv[i]);
2990
			argv[i] = NULL;
2991
			argc = i;
2992
			if (argv[i + 1])
2993
				strvec_pushv(&prune_data, argv + i + 1);
2994
			seen_dashdash = 1;
2995
			break;
2996
		}
2997
	}
2998

2999
	/* Second, deal with arguments and options */
3000
	flags = 0;
3001
	revarg_opt = opt ? opt->revarg_opt : 0;
3002
	if (seen_dashdash)
3003
		revarg_opt |= REVARG_CANNOT_BE_FILENAME;
3004
	for (left = i = 1; i < argc; i++) {
3005
		const char *arg = argv[i];
3006
		if (!seen_end_of_options && *arg == '-') {
3007
			int opts;
3008

3009
			opts = handle_revision_pseudo_opt(
3010
						revs, argv + i,
3011
						&flags);
3012
			if (opts > 0) {
3013
				i += opts - 1;
3014
				continue;
3015
			}
3016

3017
			if (!strcmp(arg, "--stdin")) {
3018
				if (revs->disable_stdin) {
3019
					argv[left++] = arg;
3020
					continue;
3021
				}
3022
				if (revs->read_from_stdin++)
3023
					die("--stdin given twice?");
3024
				read_revisions_from_stdin(revs, &prune_data);
3025
				continue;
3026
			}
3027

3028
			if (!strcmp(arg, "--end-of-options")) {
3029
				seen_end_of_options = 1;
3030
				continue;
3031
			}
3032

3033
			opts = handle_revision_opt(revs, argc - i, argv + i,
3034
						   &left, argv, opt);
3035
			if (opts > 0) {
3036
				i += opts - 1;
3037
				continue;
3038
			}
3039
			if (opts < 0)
3040
				exit(128);
3041
			continue;
3042
		}
3043

3044

3045
		if (handle_revision_arg(arg, revs, flags, revarg_opt)) {
3046
			int j;
3047
			if (seen_dashdash || *arg == '^')
3048
				die("bad revision '%s'", arg);
3049

3050
			/* If we didn't have a "--":
3051
			 * (1) all filenames must exist;
3052
			 * (2) all rev-args must not be interpretable
3053
			 *     as a valid filename.
3054
			 * but the latter we have checked in the main loop.
3055
			 */
3056
			for (j = i; j < argc; j++)
3057
				verify_filename(revs->prefix, argv[j], j == i);
3058

3059
			strvec_pushv(&prune_data, argv + i);
3060
			break;
3061
		}
3062
	}
3063
	revision_opts_finish(revs);
3064

3065
	if (prune_data.nr) {
3066
		/*
3067
		 * If we need to introduce the magic "a lone ':' means no
3068
		 * pathspec whatsoever", here is the place to do so.
3069
		 *
3070
		 * if (prune_data.nr == 1 && !strcmp(prune_data[0], ":")) {
3071
		 *	prune_data.nr = 0;
3072
		 *	prune_data.alloc = 0;
3073
		 *	free(prune_data.path);
3074
		 *	prune_data.path = NULL;
3075
		 * } else {
3076
		 *	terminate prune_data.alloc with NULL and
3077
		 *	call init_pathspec() to set revs->prune_data here.
3078
		 * }
3079
		 */
3080
		parse_pathspec(&revs->prune_data, 0, 0,
3081
			       revs->prefix, prune_data.v);
3082
	}
3083
	strvec_clear(&prune_data);
3084

3085
	if (!revs->def)
3086
		revs->def = opt ? opt->def : NULL;
3087
	if (opt && opt->tweak)
3088
		opt->tweak(revs);
3089
	if (revs->show_merge)
3090
		prepare_show_merge(revs);
3091
	if (revs->def && !revs->pending.nr && !revs->rev_input_given) {
3092
		struct object_id oid;
3093
		struct object *object;
3094
		struct object_context oc;
3095
		if (get_oid_with_context(revs->repo, revs->def, 0, &oid, &oc))
3096
			diagnose_missing_default(revs->def);
3097
		object = get_reference(revs, revs->def, &oid, 0);
3098
		add_pending_object_with_mode(revs, object, revs->def, oc.mode);
3099
		object_context_release(&oc);
3100
	}
3101

3102
	/* Did the user ask for any diff output? Run the diff! */
3103
	if (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT)
3104
		revs->diff = 1;
3105

3106
	/* Pickaxe, diff-filter and rename following need diffs */
3107
	if ((revs->diffopt.pickaxe_opts & DIFF_PICKAXE_KINDS_MASK) ||
3108
	    revs->diffopt.filter ||
3109
	    revs->diffopt.flags.follow_renames)
3110
		revs->diff = 1;
3111

3112
	if (revs->diffopt.objfind)
3113
		revs->simplify_history = 0;
3114

3115
	if (revs->line_level_traverse) {
3116
		if (want_ancestry(revs))
3117
			revs->limited = 1;
3118
		revs->topo_order = 1;
3119
	}
3120

3121
	if (revs->topo_order && !generation_numbers_enabled(the_repository))
3122
		revs->limited = 1;
3123

3124
	if (revs->prune_data.nr) {
3125
		copy_pathspec(&revs->pruning.pathspec, &revs->prune_data);
3126
		/* Can't prune commits with rename following: the paths change.. */
3127
		if (!revs->diffopt.flags.follow_renames)
3128
			revs->prune = 1;
3129
		if (!revs->full_diff)
3130
			copy_pathspec(&revs->diffopt.pathspec,
3131
				      &revs->prune_data);
3132
	}
3133

3134
	diff_merges_setup_revs(revs);
3135

3136
	revs->diffopt.abbrev = revs->abbrev;
3137

3138
	diff_setup_done(&revs->diffopt);
3139

3140
	if (!is_encoding_utf8(get_log_output_encoding()))
3141
		revs->grep_filter.ignore_locale = 1;
3142
	compile_grep_patterns(&revs->grep_filter);
3143

3144
	if (revs->reflog_info && revs->limited)
3145
		die("cannot combine --walk-reflogs with history-limiting options");
3146
	if (revs->rewrite_parents && revs->children.name)
3147
		die(_("options '%s' and '%s' cannot be used together"), "--parents", "--children");
3148
	if (revs->filter.choice && !revs->blob_objects)
3149
		die(_("object filtering requires --objects"));
3150

3151
	/*
3152
	 * Limitations on the graph functionality
3153
	 */
3154
	die_for_incompatible_opt3(!!revs->graph, "--graph",
3155
				  !!revs->reverse, "--reverse",
3156
				  !!revs->reflog_info, "--walk-reflogs");
3157

3158
	if (revs->no_walk && revs->graph)
3159
		die(_("options '%s' and '%s' cannot be used together"), "--no-walk", "--graph");
3160
	if (!revs->reflog_info && revs->grep_filter.use_reflog_filter)
3161
		die(_("the option '%s' requires '%s'"), "--grep-reflog", "--walk-reflogs");
3162

3163
	if (revs->line_level_traverse &&
3164
	    (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT)))
3165
		die(_("-L does not yet support diff formats besides -p and -s"));
3166

3167
	if (revs->expand_tabs_in_log < 0)
3168
		revs->expand_tabs_in_log = revs->expand_tabs_in_log_default;
3169

3170
	if (!revs->show_notes_given && revs->show_notes_by_default) {
3171
		enable_default_display_notes(&revs->notes_opt, &revs->show_notes);
3172
		revs->show_notes_given = 1;
3173
	}
3174

3175
	return left;
3176
}
3177

3178
static void release_revisions_cmdline(struct rev_cmdline_info *cmdline)
3179
{
3180
	unsigned int i;
3181

3182
	for (i = 0; i < cmdline->nr; i++)
3183
		free((char *)cmdline->rev[i].name);
3184
	free(cmdline->rev);
3185
}
3186

3187
static void release_revisions_mailmap(struct string_list *mailmap)
3188
{
3189
	if (!mailmap)
3190
		return;
3191
	clear_mailmap(mailmap);
3192
	free(mailmap);
3193
}
3194

3195
static void release_revisions_topo_walk_info(struct topo_walk_info *info);
3196

3197
static void free_void_commit_list(void *list)
3198
{
3199
	free_commit_list(list);
3200
}
3201

3202
void release_revisions(struct rev_info *revs)
3203
{
3204
	free_commit_list(revs->commits);
3205
	free_commit_list(revs->ancestry_path_bottoms);
3206
	release_display_notes(&revs->notes_opt);
3207
	object_array_clear(&revs->pending);
3208
	object_array_clear(&revs->boundary_commits);
3209
	release_revisions_cmdline(&revs->cmdline);
3210
	list_objects_filter_release(&revs->filter);
3211
	clear_pathspec(&revs->prune_data);
3212
	date_mode_release(&revs->date_mode);
3213
	release_revisions_mailmap(revs->mailmap);
3214
	free_grep_patterns(&revs->grep_filter);
3215
	graph_clear(revs->graph);
3216
	diff_free(&revs->diffopt);
3217
	diff_free(&revs->pruning);
3218
	reflog_walk_info_release(revs->reflog_info);
3219
	release_revisions_topo_walk_info(revs->topo_walk_info);
3220
	clear_decoration(&revs->children, free_void_commit_list);
3221
	clear_decoration(&revs->merge_simplification, free);
3222
	clear_decoration(&revs->treesame, free);
3223
	line_log_free(revs);
3224
	oidset_clear(&revs->missing_commits);
3225
}
3226

3227
static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)
3228
{
3229
	struct commit_list *l = xcalloc(1, sizeof(*l));
3230

3231
	l->item = child;
3232
	l->next = add_decoration(&revs->children, &parent->object, l);
3233
}
3234

3235
static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)
3236
{
3237
	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
3238
	struct commit_list **pp, *p;
3239
	int surviving_parents;
3240

3241
	/* Examine existing parents while marking ones we have seen... */
3242
	pp = &commit->parents;
3243
	surviving_parents = 0;
3244
	while ((p = *pp) != NULL) {
3245
		struct commit *parent = p->item;
3246
		if (parent->object.flags & TMP_MARK) {
3247
			*pp = p->next;
3248
			if (ts)
3249
				compact_treesame(revs, commit, surviving_parents);
3250
			continue;
3251
		}
3252
		parent->object.flags |= TMP_MARK;
3253
		surviving_parents++;
3254
		pp = &p->next;
3255
	}
3256
	/* clear the temporary mark */
3257
	for (p = commit->parents; p; p = p->next) {
3258
		p->item->object.flags &= ~TMP_MARK;
3259
	}
3260
	/* no update_treesame() - removing duplicates can't affect TREESAME */
3261
	return surviving_parents;
3262
}
3263

3264
struct merge_simplify_state {
3265
	struct commit *simplified;
3266
};
3267

3268
static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs, struct commit *commit)
3269
{
3270
	struct merge_simplify_state *st;
3271

3272
	st = lookup_decoration(&revs->merge_simplification, &commit->object);
3273
	if (!st) {
3274
		CALLOC_ARRAY(st, 1);
3275
		add_decoration(&revs->merge_simplification, &commit->object, st);
3276
	}
3277
	return st;
3278
}
3279

3280
static int mark_redundant_parents(struct commit *commit)
3281
{
3282
	struct commit_list *h = reduce_heads(commit->parents);
3283
	int i = 0, marked = 0;
3284
	struct commit_list *po, *pn;
3285

3286
	/* Want these for sanity-checking only */
3287
	int orig_cnt = commit_list_count(commit->parents);
3288
	int cnt = commit_list_count(h);
3289

3290
	/*
3291
	 * Not ready to remove items yet, just mark them for now, based
3292
	 * on the output of reduce_heads(). reduce_heads outputs the reduced
3293
	 * set in its original order, so this isn't too hard.
3294
	 */
3295
	po = commit->parents;
3296
	pn = h;
3297
	while (po) {
3298
		if (pn && po->item == pn->item) {
3299
			pn = pn->next;
3300
			i++;
3301
		} else {
3302
			po->item->object.flags |= TMP_MARK;
3303
			marked++;
3304
		}
3305
		po=po->next;
3306
	}
3307

3308
	if (i != cnt || cnt+marked != orig_cnt)
3309
		die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked);
3310

3311
	free_commit_list(h);
3312

3313
	return marked;
3314
}
3315

3316
static int mark_treesame_root_parents(struct commit *commit)
3317
{
3318
	struct commit_list *p;
3319
	int marked = 0;
3320

3321
	for (p = commit->parents; p; p = p->next) {
3322
		struct commit *parent = p->item;
3323
		if (!parent->parents && (parent->object.flags & TREESAME)) {
3324
			parent->object.flags |= TMP_MARK;
3325
			marked++;
3326
		}
3327
	}
3328

3329
	return marked;
3330
}
3331

3332
/*
3333
 * Awkward naming - this means one parent we are TREESAME to.
3334
 * cf mark_treesame_root_parents: root parents that are TREESAME (to an
3335
 * empty tree). Better name suggestions?
3336
 */
3337
static int leave_one_treesame_to_parent(struct rev_info *revs, struct commit *commit)
3338
{
3339
	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
3340
	struct commit *unmarked = NULL, *marked = NULL;
3341
	struct commit_list *p;
3342
	unsigned n;
3343

3344
	for (p = commit->parents, n = 0; p; p = p->next, n++) {
3345
		if (ts->treesame[n]) {
3346
			if (p->item->object.flags & TMP_MARK) {
3347
				if (!marked)
3348
					marked = p->item;
3349
			} else {
3350
				if (!unmarked) {
3351
					unmarked = p->item;
3352
					break;
3353
				}
3354
			}
3355
		}
3356
	}
3357

3358
	/*
3359
	 * If we are TREESAME to a marked-for-deletion parent, but not to any
3360
	 * unmarked parents, unmark the first TREESAME parent. This is the
3361
	 * parent that the default simplify_history==1 scan would have followed,
3362
	 * and it doesn't make sense to omit that path when asking for a
3363
	 * simplified full history. Retaining it improves the chances of
3364
	 * understanding odd missed merges that took an old version of a file.
3365
	 *
3366
	 * Example:
3367
	 *
3368
	 *   I--------*X       A modified the file, but mainline merge X used
3369
	 *    \       /        "-s ours", so took the version from I. X is
3370
	 *     `-*A--'         TREESAME to I and !TREESAME to A.
3371
	 *
3372
	 * Default log from X would produce "I". Without this check,
3373
	 * --full-history --simplify-merges would produce "I-A-X", showing
3374
	 * the merge commit X and that it changed A, but not making clear that
3375
	 * it had just taken the I version. With this check, the topology above
3376
	 * is retained.
3377
	 *
3378
	 * Note that it is possible that the simplification chooses a different
3379
	 * TREESAME parent from the default, in which case this test doesn't
3380
	 * activate, and we _do_ drop the default parent. Example:
3381
	 *
3382
	 *   I------X         A modified the file, but it was reverted in B,
3383
	 *    \    /          meaning mainline merge X is TREESAME to both
3384
	 *    *A-*B           parents.
3385
	 *
3386
	 * Default log would produce "I" by following the first parent;
3387
	 * --full-history --simplify-merges will produce "I-A-B". But this is a
3388
	 * reasonable result - it presents a logical full history leading from
3389
	 * I to X, and X is not an important merge.
3390
	 */
3391
	if (!unmarked && marked) {
3392
		marked->object.flags &= ~TMP_MARK;
3393
		return 1;
3394
	}
3395

3396
	return 0;
3397
}
3398

3399
static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
3400
{
3401
	struct commit_list **pp, *p;
3402
	int nth_parent, removed = 0;
3403

3404
	pp = &commit->parents;
3405
	nth_parent = 0;
3406
	while ((p = *pp) != NULL) {
3407
		struct commit *parent = p->item;
3408
		if (parent->object.flags & TMP_MARK) {
3409
			parent->object.flags &= ~TMP_MARK;
3410
			*pp = p->next;
3411
			free(p);
3412
			removed++;
3413
			compact_treesame(revs, commit, nth_parent);
3414
			continue;
3415
		}
3416
		pp = &p->next;
3417
		nth_parent++;
3418
	}
3419

3420
	/* Removing parents can only increase TREESAMEness */
3421
	if (removed && !(commit->object.flags & TREESAME))
3422
		update_treesame(revs, commit);
3423

3424
	return nth_parent;
3425
}
3426

3427
static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)
3428
{
3429
	struct commit_list *p;
3430
	struct commit *parent;
3431
	struct merge_simplify_state *st, *pst;
3432
	int cnt;
3433

3434
	st = locate_simplify_state(revs, commit);
3435

3436
	/*
3437
	 * Have we handled this one?
3438
	 */
3439
	if (st->simplified)
3440
		return tail;
3441

3442
	/*
3443
	 * An UNINTERESTING commit simplifies to itself, so does a
3444
	 * root commit.  We do not rewrite parents of such commit
3445
	 * anyway.
3446
	 */
3447
	if ((commit->object.flags & UNINTERESTING) || !commit->parents) {
3448
		st->simplified = commit;
3449
		return tail;
3450
	}
3451

3452
	/*
3453
	 * Do we know what commit all of our parents that matter
3454
	 * should be rewritten to?  Otherwise we are not ready to
3455
	 * rewrite this one yet.
3456
	 */
3457
	for (cnt = 0, p = commit->parents; p; p = p->next) {
3458
		pst = locate_simplify_state(revs, p->item);
3459
		if (!pst->simplified) {
3460
			tail = &commit_list_insert(p->item, tail)->next;
3461
			cnt++;
3462
		}
3463
		if (revs->first_parent_only)
3464
			break;
3465
	}
3466
	if (cnt) {
3467
		tail = &commit_list_insert(commit, tail)->next;
3468
		return tail;
3469
	}
3470

3471
	/*
3472
	 * Rewrite our list of parents. Note that this cannot
3473
	 * affect our TREESAME flags in any way - a commit is
3474
	 * always TREESAME to its simplification.
3475
	 */
3476
	for (p = commit->parents; p; p = p->next) {
3477
		pst = locate_simplify_state(revs, p->item);
3478
		p->item = pst->simplified;
3479
		if (revs->first_parent_only)
3480
			break;
3481
	}
3482

3483
	if (revs->first_parent_only)
3484
		cnt = 1;
3485
	else
3486
		cnt = remove_duplicate_parents(revs, commit);
3487

3488
	/*
3489
	 * It is possible that we are a merge and one side branch
3490
	 * does not have any commit that touches the given paths;
3491
	 * in such a case, the immediate parent from that branch
3492
	 * will be rewritten to be the merge base.
3493
	 *
3494
	 *      o----X		X: the commit we are looking at;
3495
	 *     /    /		o: a commit that touches the paths;
3496
	 * ---o----'
3497
	 *
3498
	 * Further, a merge of an independent branch that doesn't
3499
	 * touch the path will reduce to a treesame root parent:
3500
	 *
3501
	 *  ----o----X		X: the commit we are looking at;
3502
	 *          /		o: a commit that touches the paths;
3503
	 *         r		r: a root commit not touching the paths
3504
	 *
3505
	 * Detect and simplify both cases.
3506
	 */
3507
	if (1 < cnt) {
3508
		int marked = mark_redundant_parents(commit);
3509
		marked += mark_treesame_root_parents(commit);
3510
		if (marked)
3511
			marked -= leave_one_treesame_to_parent(revs, commit);
3512
		if (marked)
3513
			cnt = remove_marked_parents(revs, commit);
3514
	}
3515

3516
	/*
3517
	 * A commit simplifies to itself if it is a root, if it is
3518
	 * UNINTERESTING, if it touches the given paths, or if it is a
3519
	 * merge and its parents don't simplify to one relevant commit
3520
	 * (the first two cases are already handled at the beginning of
3521
	 * this function).
3522
	 *
3523
	 * Otherwise, it simplifies to what its sole relevant parent
3524
	 * simplifies to.
3525
	 */
3526
	if (!cnt ||
3527
	    (commit->object.flags & UNINTERESTING) ||
3528
	    !(commit->object.flags & TREESAME) ||
3529
	    (parent = one_relevant_parent(revs, commit->parents)) == NULL ||
3530
	    (revs->show_pulls && (commit->object.flags & PULL_MERGE)))
3531
		st->simplified = commit;
3532
	else {
3533
		pst = locate_simplify_state(revs, parent);
3534
		st->simplified = pst->simplified;
3535
	}
3536
	return tail;
3537
}
3538

3539
static void simplify_merges(struct rev_info *revs)
3540
{
3541
	struct commit_list *list, *next;
3542
	struct commit_list *yet_to_do, **tail;
3543
	struct commit *commit;
3544

3545
	if (!revs->prune)
3546
		return;
3547

3548
	/* feed the list reversed */
3549
	yet_to_do = NULL;
3550
	for (list = revs->commits; list; list = next) {
3551
		commit = list->item;
3552
		next = list->next;
3553
		/*
3554
		 * Do not free(list) here yet; the original list
3555
		 * is used later in this function.
3556
		 */
3557
		commit_list_insert(commit, &yet_to_do);
3558
	}
3559
	while (yet_to_do) {
3560
		list = yet_to_do;
3561
		yet_to_do = NULL;
3562
		tail = &yet_to_do;
3563
		while (list) {
3564
			commit = pop_commit(&list);
3565
			tail = simplify_one(revs, commit, tail);
3566
		}
3567
	}
3568

3569
	/* clean up the result, removing the simplified ones */
3570
	list = revs->commits;
3571
	revs->commits = NULL;
3572
	tail = &revs->commits;
3573
	while (list) {
3574
		struct merge_simplify_state *st;
3575

3576
		commit = pop_commit(&list);
3577
		st = locate_simplify_state(revs, commit);
3578
		if (st->simplified == commit)
3579
			tail = &commit_list_insert(commit, tail)->next;
3580
	}
3581
}
3582

3583
static void set_children(struct rev_info *revs)
3584
{
3585
	struct commit_list *l;
3586
	for (l = revs->commits; l; l = l->next) {
3587
		struct commit *commit = l->item;
3588
		struct commit_list *p;
3589

3590
		for (p = commit->parents; p; p = p->next)
3591
			add_child(revs, p->item, commit);
3592
	}
3593
}
3594

3595
void reset_revision_walk(void)
3596
{
3597
	clear_object_flags(SEEN | ADDED | SHOWN | TOPO_WALK_EXPLORED | TOPO_WALK_INDEGREE);
3598
}
3599

3600
static int mark_uninteresting(const struct object_id *oid,
3601
			      struct packed_git *pack UNUSED,
3602
			      uint32_t pos UNUSED,
3603
			      void *cb)
3604
{
3605
	struct rev_info *revs = cb;
3606
	struct object *o = lookup_unknown_object(revs->repo, oid);
3607
	o->flags |= UNINTERESTING | SEEN;
3608
	return 0;
3609
}
3610

3611
define_commit_slab(indegree_slab, int);
3612
define_commit_slab(author_date_slab, timestamp_t);
3613

3614
struct topo_walk_info {
3615
	timestamp_t min_generation;
3616
	struct prio_queue explore_queue;
3617
	struct prio_queue indegree_queue;
3618
	struct prio_queue topo_queue;
3619
	struct indegree_slab indegree;
3620
	struct author_date_slab author_date;
3621
};
3622

3623
static int topo_walk_atexit_registered;
3624
static unsigned int count_explore_walked;
3625
static unsigned int count_indegree_walked;
3626
static unsigned int count_topo_walked;
3627

3628
static void trace2_topo_walk_statistics_atexit(void)
3629
{
3630
	struct json_writer jw = JSON_WRITER_INIT;
3631

3632
	jw_object_begin(&jw, 0);
3633
	jw_object_intmax(&jw, "count_explore_walked", count_explore_walked);
3634
	jw_object_intmax(&jw, "count_indegree_walked", count_indegree_walked);
3635
	jw_object_intmax(&jw, "count_topo_walked", count_topo_walked);
3636
	jw_end(&jw);
3637

3638
	trace2_data_json("topo_walk", the_repository, "statistics", &jw);
3639

3640
	jw_release(&jw);
3641
}
3642

3643
static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag)
3644
{
3645
	if (c->object.flags & flag)
3646
		return;
3647

3648
	c->object.flags |= flag;
3649
	prio_queue_put(q, c);
3650
}
3651

3652
static void explore_walk_step(struct rev_info *revs)
3653
{
3654
	struct topo_walk_info *info = revs->topo_walk_info;
3655
	struct commit_list *p;
3656
	struct commit *c = prio_queue_get(&info->explore_queue);
3657

3658
	if (!c)
3659
		return;
3660

3661
	if (repo_parse_commit_gently(revs->repo, c, 1) < 0)
3662
		return;
3663

3664
	count_explore_walked++;
3665

3666
	if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
3667
		record_author_date(&info->author_date, c);
3668

3669
	if (revs->max_age != -1 && (c->date < revs->max_age))
3670
		c->object.flags |= UNINTERESTING;
3671

3672
	if (process_parents(revs, c, NULL, NULL) < 0)
3673
		return;
3674

3675
	if (c->object.flags & UNINTERESTING)
3676
		mark_parents_uninteresting(revs, c);
3677

3678
	for (p = c->parents; p; p = p->next)
3679
		test_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);
3680
}
3681

3682
static void explore_to_depth(struct rev_info *revs,
3683
			     timestamp_t gen_cutoff)
3684
{
3685
	struct topo_walk_info *info = revs->topo_walk_info;
3686
	struct commit *c;
3687
	while ((c = prio_queue_peek(&info->explore_queue)) &&
3688
	       commit_graph_generation(c) >= gen_cutoff)
3689
		explore_walk_step(revs);
3690
}
3691

3692
static void indegree_walk_step(struct rev_info *revs)
3693
{
3694
	struct commit_list *p;
3695
	struct topo_walk_info *info = revs->topo_walk_info;
3696
	struct commit *c = prio_queue_get(&info->indegree_queue);
3697

3698
	if (!c)
3699
		return;
3700

3701
	if (repo_parse_commit_gently(revs->repo, c, 1) < 0)
3702
		return;
3703

3704
	count_indegree_walked++;
3705

3706
	explore_to_depth(revs, commit_graph_generation(c));
3707

3708
	for (p = c->parents; p; p = p->next) {
3709
		struct commit *parent = p->item;
3710
		int *pi = indegree_slab_at(&info->indegree, parent);
3711

3712
		if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
3713
			return;
3714

3715
		if (*pi)
3716
			(*pi)++;
3717
		else
3718
			*pi = 2;
3719

3720
		test_flag_and_insert(&info->indegree_queue, parent, TOPO_WALK_INDEGREE);
3721

3722
		if (revs->first_parent_only)
3723
			return;
3724
	}
3725
}
3726

3727
static void compute_indegrees_to_depth(struct rev_info *revs,
3728
				       timestamp_t gen_cutoff)
3729
{
3730
	struct topo_walk_info *info = revs->topo_walk_info;
3731
	struct commit *c;
3732
	while ((c = prio_queue_peek(&info->indegree_queue)) &&
3733
	       commit_graph_generation(c) >= gen_cutoff)
3734
		indegree_walk_step(revs);
3735
}
3736

3737
static void release_revisions_topo_walk_info(struct topo_walk_info *info)
3738
{
3739
	if (!info)
3740
		return;
3741
	clear_prio_queue(&info->explore_queue);
3742
	clear_prio_queue(&info->indegree_queue);
3743
	clear_prio_queue(&info->topo_queue);
3744
	clear_indegree_slab(&info->indegree);
3745
	clear_author_date_slab(&info->author_date);
3746
	free(info);
3747
}
3748

3749
static void reset_topo_walk(struct rev_info *revs)
3750
{
3751
	release_revisions_topo_walk_info(revs->topo_walk_info);
3752
	revs->topo_walk_info = NULL;
3753
}
3754

3755
static void init_topo_walk(struct rev_info *revs)
3756
{
3757
	struct topo_walk_info *info;
3758
	struct commit_list *list;
3759
	if (revs->topo_walk_info)
3760
		reset_topo_walk(revs);
3761

3762
	revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info));
3763
	info = revs->topo_walk_info;
3764
	memset(info, 0, sizeof(struct topo_walk_info));
3765

3766
	init_indegree_slab(&info->indegree);
3767
	memset(&info->explore_queue, 0, sizeof(info->explore_queue));
3768
	memset(&info->indegree_queue, 0, sizeof(info->indegree_queue));
3769
	memset(&info->topo_queue, 0, sizeof(info->topo_queue));
3770

3771
	switch (revs->sort_order) {
3772
	default: /* REV_SORT_IN_GRAPH_ORDER */
3773
		info->topo_queue.compare = NULL;
3774
		break;
3775
	case REV_SORT_BY_COMMIT_DATE:
3776
		info->topo_queue.compare = compare_commits_by_commit_date;
3777
		break;
3778
	case REV_SORT_BY_AUTHOR_DATE:
3779
		init_author_date_slab(&info->author_date);
3780
		info->topo_queue.compare = compare_commits_by_author_date;
3781
		info->topo_queue.cb_data = &info->author_date;
3782
		break;
3783
	}
3784

3785
	info->explore_queue.compare = compare_commits_by_gen_then_commit_date;
3786
	info->indegree_queue.compare = compare_commits_by_gen_then_commit_date;
3787

3788
	info->min_generation = GENERATION_NUMBER_INFINITY;
3789
	for (list = revs->commits; list; list = list->next) {
3790
		struct commit *c = list->item;
3791
		timestamp_t generation;
3792

3793
		if (repo_parse_commit_gently(revs->repo, c, 1))
3794
			continue;
3795

3796
		test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);
3797
		test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);
3798

3799
		generation = commit_graph_generation(c);
3800
		if (generation < info->min_generation)
3801
			info->min_generation = generation;
3802

3803
		*(indegree_slab_at(&info->indegree, c)) = 1;
3804

3805
		if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
3806
			record_author_date(&info->author_date, c);
3807
	}
3808
	compute_indegrees_to_depth(revs, info->min_generation);
3809

3810
	for (list = revs->commits; list; list = list->next) {
3811
		struct commit *c = list->item;
3812

3813
		if (*(indegree_slab_at(&info->indegree, c)) == 1)
3814
			prio_queue_put(&info->topo_queue, c);
3815
	}
3816

3817
	/*
3818
	 * This is unfortunate; the initial tips need to be shown
3819
	 * in the order given from the revision traversal machinery.
3820
	 */
3821
	if (revs->sort_order == REV_SORT_IN_GRAPH_ORDER)
3822
		prio_queue_reverse(&info->topo_queue);
3823

3824
	if (trace2_is_enabled() && !topo_walk_atexit_registered) {
3825
		atexit(trace2_topo_walk_statistics_atexit);
3826
		topo_walk_atexit_registered = 1;
3827
	}
3828
}
3829

3830
static struct commit *next_topo_commit(struct rev_info *revs)
3831
{
3832
	struct commit *c;
3833
	struct topo_walk_info *info = revs->topo_walk_info;
3834

3835
	/* pop next off of topo_queue */
3836
	c = prio_queue_get(&info->topo_queue);
3837

3838
	if (c)
3839
		*(indegree_slab_at(&info->indegree, c)) = 0;
3840

3841
	return c;
3842
}
3843

3844
static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
3845
{
3846
	struct commit_list *p;
3847
	struct topo_walk_info *info = revs->topo_walk_info;
3848
	if (process_parents(revs, commit, NULL, NULL) < 0) {
3849
		if (!revs->ignore_missing_links)
3850
			die("Failed to traverse parents of commit %s",
3851
			    oid_to_hex(&commit->object.oid));
3852
	}
3853

3854
	count_topo_walked++;
3855

3856
	for (p = commit->parents; p; p = p->next) {
3857
		struct commit *parent = p->item;
3858
		int *pi;
3859
		timestamp_t generation;
3860

3861
		if (parent->object.flags & UNINTERESTING)
3862
			continue;
3863

3864
		if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
3865
			continue;
3866

3867
		generation = commit_graph_generation(parent);
3868
		if (generation < info->min_generation) {
3869
			info->min_generation = generation;
3870
			compute_indegrees_to_depth(revs, info->min_generation);
3871
		}
3872

3873
		pi = indegree_slab_at(&info->indegree, parent);
3874

3875
		(*pi)--;
3876
		if (*pi == 1)
3877
			prio_queue_put(&info->topo_queue, parent);
3878

3879
		if (revs->first_parent_only)
3880
			return;
3881
	}
3882
}
3883

3884
int prepare_revision_walk(struct rev_info *revs)
3885
{
3886
	int i;
3887
	struct object_array old_pending;
3888
	struct commit_list **next = &revs->commits;
3889

3890
	memcpy(&old_pending, &revs->pending, sizeof(old_pending));
3891
	revs->pending.nr = 0;
3892
	revs->pending.alloc = 0;
3893
	revs->pending.objects = NULL;
3894
	for (i = 0; i < old_pending.nr; i++) {
3895
		struct object_array_entry *e = old_pending.objects + i;
3896
		struct commit *commit = handle_commit(revs, e);
3897
		if (commit) {
3898
			if (!(commit->object.flags & SEEN)) {
3899
				commit->object.flags |= SEEN;
3900
				next = commit_list_append(commit, next);
3901
			}
3902
		}
3903
	}
3904
	object_array_clear(&old_pending);
3905

3906
	/* Signal whether we need per-parent treesame decoration */
3907
	if (revs->simplify_merges ||
3908
	    (revs->limited && limiting_can_increase_treesame(revs)))
3909
		revs->treesame.name = "treesame";
3910

3911
	if (revs->exclude_promisor_objects) {
3912
		for_each_packed_object(mark_uninteresting, revs,
3913
				       FOR_EACH_OBJECT_PROMISOR_ONLY);
3914
	}
3915

3916
	if (!revs->reflog_info)
3917
		prepare_to_use_bloom_filter(revs);
3918
	if (!revs->unsorted_input)
3919
		commit_list_sort_by_date(&revs->commits);
3920
	if (revs->no_walk)
3921
		return 0;
3922
	if (revs->limited) {
3923
		if (limit_list(revs) < 0)
3924
			return -1;
3925
		if (revs->topo_order)
3926
			sort_in_topological_order(&revs->commits, revs->sort_order);
3927
	} else if (revs->topo_order)
3928
		init_topo_walk(revs);
3929
	if (revs->line_level_traverse && want_ancestry(revs))
3930
		/*
3931
		 * At the moment we can only do line-level log with parent
3932
		 * rewriting by performing this expensive pre-filtering step.
3933
		 * If parent rewriting is not requested, then we rather
3934
		 * perform the line-level log filtering during the regular
3935
		 * history traversal.
3936
		 */
3937
		line_log_filter(revs);
3938
	if (revs->simplify_merges)
3939
		simplify_merges(revs);
3940
	if (revs->children.name)
3941
		set_children(revs);
3942

3943
	return 0;
3944
}
3945

3946
static enum rewrite_result rewrite_one_1(struct rev_info *revs,
3947
					 struct commit **pp,
3948
					 struct prio_queue *queue)
3949
{
3950
	for (;;) {
3951
		struct commit *p = *pp;
3952
		if (!revs->limited)
3953
			if (process_parents(revs, p, NULL, queue) < 0)
3954
				return rewrite_one_error;
3955
		if (p->object.flags & UNINTERESTING)
3956
			return rewrite_one_ok;
3957
		if (!(p->object.flags & TREESAME))
3958
			return rewrite_one_ok;
3959
		if (!p->parents)
3960
			return rewrite_one_noparents;
3961
		if (!(p = one_relevant_parent(revs, p->parents)))
3962
			return rewrite_one_ok;
3963
		*pp = p;
3964
	}
3965
}
3966

3967
static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)
3968
{
3969
	while (q->nr) {
3970
		struct commit *item = prio_queue_peek(q);
3971
		struct commit_list *p = *list;
3972

3973
		if (p && p->item->date >= item->date)
3974
			list = &p->next;
3975
		else {
3976
			p = commit_list_insert(item, list);
3977
			list = &p->next; /* skip newly added item */
3978
			prio_queue_get(q); /* pop item */
3979
		}
3980
	}
3981
}
3982

3983
static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)
3984
{
3985
	struct prio_queue queue = { compare_commits_by_commit_date };
3986
	enum rewrite_result ret = rewrite_one_1(revs, pp, &queue);
3987
	merge_queue_into_list(&queue, &revs->commits);
3988
	clear_prio_queue(&queue);
3989
	return ret;
3990
}
3991

3992
int rewrite_parents(struct rev_info *revs, struct commit *commit,
3993
	rewrite_parent_fn_t rewrite_parent)
3994
{
3995
	struct commit_list **pp = &commit->parents;
3996
	while (*pp) {
3997
		struct commit_list *parent = *pp;
3998
		switch (rewrite_parent(revs, &parent->item)) {
3999
		case rewrite_one_ok:
4000
			break;
4001
		case rewrite_one_noparents:
4002
			*pp = parent->next;
4003
			continue;
4004
		case rewrite_one_error:
4005
			return -1;
4006
		}
4007
		pp = &parent->next;
4008
	}
4009
	remove_duplicate_parents(revs, commit);
4010
	return 0;
4011
}
4012

4013
static int commit_match(struct commit *commit, struct rev_info *opt)
4014
{
4015
	int retval;
4016
	const char *encoding;
4017
	const char *message;
4018
	struct strbuf buf = STRBUF_INIT;
4019

4020
	if (!opt->grep_filter.pattern_list && !opt->grep_filter.header_list)
4021
		return 1;
4022

4023
	/* Prepend "fake" headers as needed */
4024
	if (opt->grep_filter.use_reflog_filter) {
4025
		strbuf_addstr(&buf, "reflog ");
4026
		get_reflog_message(&buf, opt->reflog_info);
4027
		strbuf_addch(&buf, '\n');
4028
	}
4029

4030
	/*
4031
	 * We grep in the user's output encoding, under the assumption that it
4032
	 * is the encoding they are most likely to write their grep pattern
4033
	 * for. In addition, it means we will match the "notes" encoding below,
4034
	 * so we will not end up with a buffer that has two different encodings
4035
	 * in it.
4036
	 */
4037
	encoding = get_log_output_encoding();
4038
	message = repo_logmsg_reencode(the_repository, commit, NULL, encoding);
4039

4040
	/* Copy the commit to temporary if we are using "fake" headers */
4041
	if (buf.len)
4042
		strbuf_addstr(&buf, message);
4043

4044
	if (opt->grep_filter.header_list && opt->mailmap) {
4045
		const char *commit_headers[] = { "author ", "committer ", NULL };
4046

4047
		if (!buf.len)
4048
			strbuf_addstr(&buf, message);
4049

4050
		apply_mailmap_to_header(&buf, commit_headers, opt->mailmap);
4051
	}
4052

4053
	/* Append "fake" message parts as needed */
4054
	if (opt->show_notes) {
4055
		if (!buf.len)
4056
			strbuf_addstr(&buf, message);
4057
		format_display_notes(&commit->object.oid, &buf, encoding, 1);
4058
	}
4059

4060
	/*
4061
	 * Find either in the original commit message, or in the temporary.
4062
	 * Note that we cast away the constness of "message" here. It is
4063
	 * const because it may come from the cached commit buffer. That's OK,
4064
	 * because we know that it is modifiable heap memory, and that while
4065
	 * grep_buffer may modify it for speed, it will restore any
4066
	 * changes before returning.
4067
	 */
4068
	if (buf.len)
4069
		retval = grep_buffer(&opt->grep_filter, buf.buf, buf.len);
4070
	else
4071
		retval = grep_buffer(&opt->grep_filter,
4072
				     (char *)message, strlen(message));
4073
	strbuf_release(&buf);
4074
	repo_unuse_commit_buffer(the_repository, commit, message);
4075
	return retval;
4076
}
4077

4078
static inline int want_ancestry(const struct rev_info *revs)
4079
{
4080
	return (revs->rewrite_parents || revs->children.name);
4081
}
4082

4083
/*
4084
 * Return a timestamp to be used for --since/--until comparisons for this
4085
 * commit, based on the revision options.
4086
 */
4087
static timestamp_t comparison_date(const struct rev_info *revs,
4088
				   struct commit *commit)
4089
{
4090
	return revs->reflog_info ?
4091
		get_reflog_timestamp(revs->reflog_info) :
4092
		commit->date;
4093
}
4094

4095
enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit)
4096
{
4097
	if (commit->object.flags & SHOWN)
4098
		return commit_ignore;
4099
	if (revs->unpacked && has_object_pack(&commit->object.oid))
4100
		return commit_ignore;
4101
	if (revs->no_kept_objects) {
4102
		if (has_object_kept_pack(&commit->object.oid,
4103
					 revs->keep_pack_cache_flags))
4104
			return commit_ignore;
4105
	}
4106
	if (commit->object.flags & UNINTERESTING)
4107
		return commit_ignore;
4108
	if (revs->line_level_traverse && !want_ancestry(revs)) {
4109
		/*
4110
		 * In case of line-level log with parent rewriting
4111
		 * prepare_revision_walk() already took care of all line-level
4112
		 * log filtering, and there is nothing left to do here.
4113
		 *
4114
		 * If parent rewriting was not requested, then this is the
4115
		 * place to perform the line-level log filtering.  Notably,
4116
		 * this check, though expensive, must come before the other,
4117
		 * cheaper filtering conditions, because the tracked line
4118
		 * ranges must be adjusted even when the commit will end up
4119
		 * being ignored based on other conditions.
4120
		 */
4121
		if (!line_log_process_ranges_arbitrary_commit(revs, commit))
4122
			return commit_ignore;
4123
	}
4124
	if (revs->min_age != -1 &&
4125
	    comparison_date(revs, commit) > revs->min_age)
4126
			return commit_ignore;
4127
	if (revs->max_age_as_filter != -1 &&
4128
	    comparison_date(revs, commit) < revs->max_age_as_filter)
4129
			return commit_ignore;
4130
	if (revs->min_parents || (revs->max_parents >= 0)) {
4131
		int n = commit_list_count(commit->parents);
4132
		if ((n < revs->min_parents) ||
4133
		    ((revs->max_parents >= 0) && (n > revs->max_parents)))
4134
			return commit_ignore;
4135
	}
4136
	if (!commit_match(commit, revs))
4137
		return commit_ignore;
4138
	if (revs->prune && revs->dense) {
4139
		/* Commit without changes? */
4140
		if (commit->object.flags & TREESAME) {
4141
			int n;
4142
			struct commit_list *p;
4143
			/* drop merges unless we want parenthood */
4144
			if (!want_ancestry(revs))
4145
				return commit_ignore;
4146

4147
			if (revs->show_pulls && (commit->object.flags & PULL_MERGE))
4148
				return commit_show;
4149

4150
			/*
4151
			 * If we want ancestry, then need to keep any merges
4152
			 * between relevant commits to tie together topology.
4153
			 * For consistency with TREESAME and simplification
4154
			 * use "relevant" here rather than just INTERESTING,
4155
			 * to treat bottom commit(s) as part of the topology.
4156
			 */
4157
			for (n = 0, p = commit->parents; p; p = p->next)
4158
				if (relevant_commit(p->item))
4159
					if (++n >= 2)
4160
						return commit_show;
4161
			return commit_ignore;
4162
		}
4163
	}
4164
	return commit_show;
4165
}
4166

4167
define_commit_slab(saved_parents, struct commit_list *);
4168

4169
#define EMPTY_PARENT_LIST ((struct commit_list *)-1)
4170

4171
/*
4172
 * You may only call save_parents() once per commit (this is checked
4173
 * for non-root commits).
4174
 */
4175
static void save_parents(struct rev_info *revs, struct commit *commit)
4176
{
4177
	struct commit_list **pp;
4178

4179
	if (!revs->saved_parents_slab) {
4180
		revs->saved_parents_slab = xmalloc(sizeof(struct saved_parents));
4181
		init_saved_parents(revs->saved_parents_slab);
4182
	}
4183

4184
	pp = saved_parents_at(revs->saved_parents_slab, commit);
4185

4186
	/*
4187
	 * When walking with reflogs, we may visit the same commit
4188
	 * several times: once for each appearance in the reflog.
4189
	 *
4190
	 * In this case, save_parents() will be called multiple times.
4191
	 * We want to keep only the first set of parents.  We need to
4192
	 * store a sentinel value for an empty (i.e., NULL) parent
4193
	 * list to distinguish it from a not-yet-saved list, however.
4194
	 */
4195
	if (*pp)
4196
		return;
4197
	if (commit->parents)
4198
		*pp = copy_commit_list(commit->parents);
4199
	else
4200
		*pp = EMPTY_PARENT_LIST;
4201
}
4202

4203
static void free_saved_parents(struct rev_info *revs)
4204
{
4205
	if (revs->saved_parents_slab)
4206
		clear_saved_parents(revs->saved_parents_slab);
4207
}
4208

4209
struct commit_list *get_saved_parents(struct rev_info *revs, const struct commit *commit)
4210
{
4211
	struct commit_list *parents;
4212

4213
	if (!revs->saved_parents_slab)
4214
		return commit->parents;
4215

4216
	parents = *saved_parents_at(revs->saved_parents_slab, commit);
4217
	if (parents == EMPTY_PARENT_LIST)
4218
		return NULL;
4219
	return parents;
4220
}
4221

4222
enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)
4223
{
4224
	enum commit_action action = get_commit_action(revs, commit);
4225

4226
	if (action == commit_show &&
4227
	    revs->prune && revs->dense && want_ancestry(revs)) {
4228
		/*
4229
		 * --full-diff on simplified parents is no good: it
4230
		 * will show spurious changes from the commits that
4231
		 * were elided.  So we save the parents on the side
4232
		 * when --full-diff is in effect.
4233
		 */
4234
		if (revs->full_diff)
4235
			save_parents(revs, commit);
4236
		if (rewrite_parents(revs, commit, rewrite_one) < 0)
4237
			return commit_error;
4238
	}
4239
	return action;
4240
}
4241

4242
static void track_linear(struct rev_info *revs, struct commit *commit)
4243
{
4244
	if (revs->track_first_time) {
4245
		revs->linear = 1;
4246
		revs->track_first_time = 0;
4247
	} else {
4248
		struct commit_list *p;
4249
		for (p = revs->previous_parents; p; p = p->next)
4250
			if (p->item == NULL || /* first commit */
4251
			    oideq(&p->item->object.oid, &commit->object.oid))
4252
				break;
4253
		revs->linear = p != NULL;
4254
	}
4255
	if (revs->reverse) {
4256
		if (revs->linear)
4257
			commit->object.flags |= TRACK_LINEAR;
4258
	}
4259
	free_commit_list(revs->previous_parents);
4260
	revs->previous_parents = copy_commit_list(commit->parents);
4261
}
4262

4263
static struct commit *get_revision_1(struct rev_info *revs)
4264
{
4265
	while (1) {
4266
		struct commit *commit;
4267

4268
		if (revs->reflog_info)
4269
			commit = next_reflog_entry(revs->reflog_info);
4270
		else if (revs->topo_walk_info)
4271
			commit = next_topo_commit(revs);
4272
		else
4273
			commit = pop_commit(&revs->commits);
4274

4275
		if (!commit)
4276
			return NULL;
4277

4278
		if (revs->reflog_info)
4279
			commit->object.flags &= ~(ADDED | SEEN | SHOWN);
4280

4281
		/*
4282
		 * If we haven't done the list limiting, we need to look at
4283
		 * the parents here. We also need to do the date-based limiting
4284
		 * that we'd otherwise have done in limit_list().
4285
		 */
4286
		if (!revs->limited) {
4287
			if (revs->max_age != -1 &&
4288
			    comparison_date(revs, commit) < revs->max_age)
4289
				continue;
4290

4291
			if (revs->reflog_info)
4292
				try_to_simplify_commit(revs, commit);
4293
			else if (revs->topo_walk_info)
4294
				expand_topo_walk(revs, commit);
4295
			else if (process_parents(revs, commit, &revs->commits, NULL) < 0) {
4296
				if (!revs->ignore_missing_links)
4297
					die("Failed to traverse parents of commit %s",
4298
						oid_to_hex(&commit->object.oid));
4299
			}
4300
		}
4301

4302
		switch (simplify_commit(revs, commit)) {
4303
		case commit_ignore:
4304
			continue;
4305
		case commit_error:
4306
			die("Failed to simplify parents of commit %s",
4307
			    oid_to_hex(&commit->object.oid));
4308
		default:
4309
			if (revs->track_linear)
4310
				track_linear(revs, commit);
4311
			return commit;
4312
		}
4313
	}
4314
}
4315

4316
/*
4317
 * Return true for entries that have not yet been shown.  (This is an
4318
 * object_array_each_func_t.)
4319
 */
4320
static int entry_unshown(struct object_array_entry *entry, void *cb_data UNUSED)
4321
{
4322
	return !(entry->item->flags & SHOWN);
4323
}
4324

4325
/*
4326
 * If array is on the verge of a realloc, garbage-collect any entries
4327
 * that have already been shown to try to free up some space.
4328
 */
4329
static void gc_boundary(struct object_array *array)
4330
{
4331
	if (array->nr == array->alloc)
4332
		object_array_filter(array, entry_unshown, NULL);
4333
}
4334

4335
static void create_boundary_commit_list(struct rev_info *revs)
4336
{
4337
	unsigned i;
4338
	struct commit *c;
4339
	struct object_array *array = &revs->boundary_commits;
4340
	struct object_array_entry *objects = array->objects;
4341

4342
	/*
4343
	 * If revs->commits is non-NULL at this point, an error occurred in
4344
	 * get_revision_1().  Ignore the error and continue printing the
4345
	 * boundary commits anyway.  (This is what the code has always
4346
	 * done.)
4347
	 */
4348
	free_commit_list(revs->commits);
4349
	revs->commits = NULL;
4350

4351
	/*
4352
	 * Put all of the actual boundary commits from revs->boundary_commits
4353
	 * into revs->commits
4354
	 */
4355
	for (i = 0; i < array->nr; i++) {
4356
		c = (struct commit *)(objects[i].item);
4357
		if (!c)
4358
			continue;
4359
		if (!(c->object.flags & CHILD_SHOWN))
4360
			continue;
4361
		if (c->object.flags & (SHOWN | BOUNDARY))
4362
			continue;
4363
		c->object.flags |= BOUNDARY;
4364
		commit_list_insert(c, &revs->commits);
4365
	}
4366

4367
	/*
4368
	 * If revs->topo_order is set, sort the boundary commits
4369
	 * in topological order
4370
	 */
4371
	sort_in_topological_order(&revs->commits, revs->sort_order);
4372
}
4373

4374
static struct commit *get_revision_internal(struct rev_info *revs)
4375
{
4376
	struct commit *c = NULL;
4377
	struct commit_list *l;
4378

4379
	if (revs->boundary == 2) {
4380
		/*
4381
		 * All of the normal commits have already been returned,
4382
		 * and we are now returning boundary commits.
4383
		 * create_boundary_commit_list() has populated
4384
		 * revs->commits with the remaining commits to return.
4385
		 */
4386
		c = pop_commit(&revs->commits);
4387
		if (c)
4388
			c->object.flags |= SHOWN;
4389
		return c;
4390
	}
4391

4392
	/*
4393
	 * If our max_count counter has reached zero, then we are done. We
4394
	 * don't simply return NULL because we still might need to show
4395
	 * boundary commits. But we want to avoid calling get_revision_1, which
4396
	 * might do a considerable amount of work finding the next commit only
4397
	 * for us to throw it away.
4398
	 *
4399
	 * If it is non-zero, then either we don't have a max_count at all
4400
	 * (-1), or it is still counting, in which case we decrement.
4401
	 */
4402
	if (revs->max_count) {
4403
		c = get_revision_1(revs);
4404
		if (c) {
4405
			while (revs->skip_count > 0) {
4406
				revs->skip_count--;
4407
				c = get_revision_1(revs);
4408
				if (!c)
4409
					break;
4410
			}
4411
		}
4412

4413
		if (revs->max_count > 0)
4414
			revs->max_count--;
4415
	}
4416

4417
	if (c)
4418
		c->object.flags |= SHOWN;
4419

4420
	if (!revs->boundary)
4421
		return c;
4422

4423
	if (!c) {
4424
		/*
4425
		 * get_revision_1() runs out the commits, and
4426
		 * we are done computing the boundaries.
4427
		 * switch to boundary commits output mode.
4428
		 */
4429
		revs->boundary = 2;
4430

4431
		/*
4432
		 * Update revs->commits to contain the list of
4433
		 * boundary commits.
4434
		 */
4435
		create_boundary_commit_list(revs);
4436

4437
		return get_revision_internal(revs);
4438
	}
4439

4440
	/*
4441
	 * boundary commits are the commits that are parents of the
4442
	 * ones we got from get_revision_1() but they themselves are
4443
	 * not returned from get_revision_1().  Before returning
4444
	 * 'c', we need to mark its parents that they could be boundaries.
4445
	 */
4446

4447
	for (l = c->parents; l; l = l->next) {
4448
		struct object *p;
4449
		p = &(l->item->object);
4450
		if (p->flags & (CHILD_SHOWN | SHOWN))
4451
			continue;
4452
		p->flags |= CHILD_SHOWN;
4453
		gc_boundary(&revs->boundary_commits);
4454
		add_object_array(p, NULL, &revs->boundary_commits);
4455
	}
4456

4457
	return c;
4458
}
4459

4460
struct commit *get_revision(struct rev_info *revs)
4461
{
4462
	struct commit *c;
4463
	struct commit_list *reversed;
4464

4465
	if (revs->reverse) {
4466
		reversed = NULL;
4467
		while ((c = get_revision_internal(revs)))
4468
			commit_list_insert(c, &reversed);
4469
		free_commit_list(revs->commits);
4470
		revs->commits = reversed;
4471
		revs->reverse = 0;
4472
		revs->reverse_output_stage = 1;
4473
	}
4474

4475
	if (revs->reverse_output_stage) {
4476
		c = pop_commit(&revs->commits);
4477
		if (revs->track_linear)
4478
			revs->linear = !!(c && c->object.flags & TRACK_LINEAR);
4479
		return c;
4480
	}
4481

4482
	c = get_revision_internal(revs);
4483
	if (c && revs->graph)
4484
		graph_update(revs->graph, c);
4485
	if (!c) {
4486
		free_saved_parents(revs);
4487
		free_commit_list(revs->previous_parents);
4488
		revs->previous_parents = NULL;
4489
	}
4490
	return c;
4491
}
4492

4493
const char *get_revision_mark(const struct rev_info *revs, const struct commit *commit)
4494
{
4495
	if (commit->object.flags & BOUNDARY)
4496
		return "-";
4497
	else if (commit->object.flags & UNINTERESTING)
4498
		return "^";
4499
	else if (commit->object.flags & PATCHSAME)
4500
		return "=";
4501
	else if (!revs || revs->left_right) {
4502
		if (commit->object.flags & SYMMETRIC_LEFT)
4503
			return "<";
4504
		else
4505
			return ">";
4506
	} else if (revs->graph)
4507
		return "*";
4508
	else if (revs->cherry_mark)
4509
		return "+";
4510
	return "";
4511
}
4512

4513
void put_revision_mark(const struct rev_info *revs, const struct commit *commit)
4514
{
4515
	const char *mark = get_revision_mark(revs, commit);
4516
	if (!strlen(mark))
4517
		return;
4518
	fputs(mark, stdout);
4519
	putchar(' ');
4520
}
4521