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