blob: 7d435f80480ef1b7684fdc43b51057d20e79966f [file] [log] [blame]
Linus Torvaldsae563542006-02-25 16:19:46 -08001#include "cache.h"
Stefan Bellercbd53a22018-05-15 16:42:15 -07002#include "object-store.h"
Linus Torvaldsae563542006-02-25 16:19:46 -08003#include "tag.h"
4#include "blob.h"
5#include "tree.h"
6#include "commit.h"
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08007#include "diff.h"
Sergey Organova37eec62020-12-21 18:19:33 +03008#include "diff-merges.h"
Linus Torvaldsae563542006-02-25 16:19:46 -08009#include "refs.h"
10#include "revision.h"
Stefan Beller23a3f0c2018-04-11 17:21:09 -070011#include "repository.h"
Adam Simpkins7fefda52008-05-04 03:36:54 -070012#include "graph.h"
Junio C Hamano8ecae9b2006-09-17 15:43:40 -070013#include "grep.h"
Johannes Schindelin8860fd42007-01-11 11:47:48 +010014#include "reflog-walk.h"
Junio C Hamanod7a17ca2007-04-09 03:40:38 -070015#include "patch-ids.h"
Junio C Hamanof35f5602008-04-03 02:12:06 -070016#include "decorate.h"
Linus Torvalds78892e32008-11-03 11:25:46 -080017#include "log-tree.h"
Thomas Rast894a9d32010-03-12 18:04:26 +010018#include "string-list.h"
Thomas Rast12da1d12013-03-28 17:47:32 +010019#include "line-log.h"
Antoine Pelissed72fbe82013-01-05 22:26:45 +010020#include "mailmap.h"
Thomas Rast53d00b32013-07-31 22:13:20 +020021#include "commit-slab.h"
Nguyễn Thái Ngọc Duy429bb402014-01-24 20:40:28 +070022#include "dir.h"
Jeff King4fe10212014-10-16 20:44:23 -040023#include "cache-tree.h"
Antoine Delaitecb46d632015-06-29 17:40:30 +020024#include "bisect.h"
Jonathan Tan150e3002017-08-18 15:20:36 -070025#include "packfile.h"
Nguyễn Thái Ngọc Duybe489d02017-08-23 19:36:52 +070026#include "worktree.h"
Jeff Kingdbbcd442020-07-28 16:23:39 -040027#include "strvec.h"
Derrick Stolee64043552018-07-20 16:33:04 +000028#include "commit-reach.h"
Derrick Stoleef0d9cc42018-11-01 13:46:20 +000029#include "commit-graph.h"
Derrick Stoleeb4542412018-11-01 13:46:22 +000030#include "prio-queue.h"
Derrick Stoleed5d2e932019-01-16 10:25:59 -080031#include "hashmap.h"
Ævar Arnfjörð Bjarmason44570182019-06-28 01:39:05 +020032#include "utf8.h"
Garima Singha56b9462020-04-06 16:59:52 +000033#include "bloom.h"
Garima Singh42e50e72020-04-06 16:59:53 +000034#include "json-writer.h"
Derrick Stoleec4ea5132022-03-09 16:01:40 +000035#include "list-objects-filter-options.h"
Linus Torvaldsae563542006-02-25 16:19:46 -080036
Linus Torvaldscdcefbc2007-11-03 11:11:10 -070037volatile show_early_output_fn_t show_early_output;
38
Antoine Delaitecb46d632015-06-29 17:40:30 +020039static const char *term_bad;
40static const char *term_good;
41
Nguyễn Thái Ngọc Duy87be2522018-05-19 07:28:24 +020042implement_shared_commit_slab(revision_sources, char *);
43
SZEDER Gábor3cb9d2b2020-05-11 11:56:17 +000044static inline int want_ancestry(const struct rev_info *revs);
45
Jeff Kingde1e67d2016-02-11 17:28:36 -050046void show_object_with_name(FILE *out, struct object *obj, const char *name)
Linus Torvaldsae563542006-02-25 16:19:46 -080047{
brian m. carlsonf2fd0762015-11-10 02:22:28 +000048 fprintf(out, "%s ", oid_to_hex(&obj->oid));
Junio C Hamano44ba10d2021-11-14 22:27:45 -080049 /*
50 * This "for (const char *p = ..." is made as a first step towards
51 * making use of such declarations elsewhere in our codebase. If
52 * it causes compilation problems on your platform, please report
53 * it to the Git mailing list at git@vger.kernel.org. In the meantime,
54 * adding -std=gnu99 to CFLAGS may help if you are with older GCC.
55 */
56 for (const char *p = name; *p && *p != '\n'; p++)
Jeff Kingf9fb9d02016-02-11 17:24:18 -050057 fputc(*p, out);
Junio C Hamanobeba25a2011-08-17 14:30:35 -070058 fputc('\n', out);
Junio C Hamano91f17512011-08-17 14:30:34 -070059}
60
Linus Torvaldsae563542006-02-25 16:19:46 -080061static void mark_blob_uninteresting(struct blob *blob)
62{
Martin Koeglerc1ee9012008-02-18 21:47:54 +010063 if (!blob)
64 return;
Linus Torvaldsae563542006-02-25 16:19:46 -080065 if (blob->object.flags & UNINTERESTING)
66 return;
67 blob->object.flags |= UNINTERESTING;
68}
69
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +020070static void mark_tree_contents_uninteresting(struct repository *r,
71 struct tree *tree)
Linus Torvaldsae563542006-02-25 16:19:46 -080072{
Linus Torvaldsf75e53e2006-05-29 12:20:14 -070073 struct tree_desc desc;
Linus Torvalds4c068a92006-05-30 09:45:45 -070074 struct name_entry entry;
Linus Torvaldsae563542006-02-25 16:19:46 -080075
Jeff Kinga5411df2018-05-11 14:00:55 -040076 if (parse_tree_gently(tree, 1) < 0)
Linus Torvaldsae563542006-02-25 16:19:46 -080077 return;
Linus Torvaldsf75e53e2006-05-29 12:20:14 -070078
Linus Torvalds6fda5e52007-03-21 10:08:25 -070079 init_tree_desc(&desc, tree->buffer, tree->size);
Linus Torvalds4c068a92006-05-30 09:45:45 -070080 while (tree_entry(&desc, &entry)) {
Linus Torvalds4d1012c2007-11-11 23:35:23 +000081 switch (object_type(entry.mode)) {
82 case OBJ_TREE:
brian m. carlsonea82b2a2019-01-15 00:39:44 +000083 mark_tree_uninteresting(r, lookup_tree(r, &entry.oid));
Linus Torvalds4d1012c2007-11-11 23:35:23 +000084 break;
85 case OBJ_BLOB:
brian m. carlsonea82b2a2019-01-15 00:39:44 +000086 mark_blob_uninteresting(lookup_blob(r, &entry.oid));
Linus Torvalds4d1012c2007-11-11 23:35:23 +000087 break;
88 default:
89 /* Subproject commit - not in this repository */
90 break;
91 }
Linus Torvaldsae563542006-02-25 16:19:46 -080092 }
Linus Torvaldsf75e53e2006-05-29 12:20:14 -070093
94 /*
95 * We don't care about the tree any more
96 * after it has been marked uninteresting.
97 */
Jeff King6e454b92013-06-05 18:37:39 -040098 free_tree_buffer(tree);
Linus Torvaldsae563542006-02-25 16:19:46 -080099}
100
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +0200101void mark_tree_uninteresting(struct repository *r, struct tree *tree)
Junio C Hamano2ac5e442014-01-15 15:38:01 -0800102{
Stefan Naewea2678df2015-12-05 16:27:24 +0100103 struct object *obj;
Junio C Hamano2ac5e442014-01-15 15:38:01 -0800104
105 if (!tree)
106 return;
Stefan Naewea2678df2015-12-05 16:27:24 +0100107
108 obj = &tree->object;
Junio C Hamano2ac5e442014-01-15 15:38:01 -0800109 if (obj->flags & UNINTERESTING)
110 return;
111 obj->flags |= UNINTERESTING;
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +0200112 mark_tree_contents_uninteresting(r, tree);
Linus Torvaldsae563542006-02-25 16:19:46 -0800113}
114
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800115struct path_and_oids_entry {
116 struct hashmap_entry ent;
117 char *path;
118 struct oidset trees;
119};
120
121static int path_and_oids_cmp(const void *hashmap_cmp_fn_data,
Eric Wong939af162019-10-06 23:30:37 +0000122 const struct hashmap_entry *eptr,
123 const struct hashmap_entry *entry_or_key,
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800124 const void *keydata)
125{
Eric Wong939af162019-10-06 23:30:37 +0000126 const struct path_and_oids_entry *e1, *e2;
127
128 e1 = container_of(eptr, const struct path_and_oids_entry, ent);
129 e2 = container_of(entry_or_key, const struct path_and_oids_entry, ent);
130
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800131 return strcmp(e1->path, e2->path);
132}
133
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800134static void paths_and_oids_clear(struct hashmap *map)
135{
136 struct hashmap_iter iter;
137 struct path_and_oids_entry *entry;
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800138
Eric Wong23dee692019-10-06 23:30:41 +0000139 hashmap_for_each_entry(map, &iter, entry, ent /* member name */) {
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800140 oidset_clear(&entry->trees);
141 free(entry->path);
142 }
143
Elijah Newren6da1a252020-11-02 18:55:05 +0000144 hashmap_clear_and_free(map, struct path_and_oids_entry, ent);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800145}
146
147static void paths_and_oids_insert(struct hashmap *map,
148 const char *path,
149 const struct object_id *oid)
150{
151 int hash = strhash(path);
152 struct path_and_oids_entry key;
153 struct path_and_oids_entry *entry;
154
Eric Wongd22245a2019-10-06 23:30:27 +0000155 hashmap_entry_init(&key.ent, hash);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800156
157 /* use a shallow copy for the lookup */
158 key.path = (char *)path;
159 oidset_init(&key.trees, 0);
160
Eric Wong404ab782019-10-06 23:30:42 +0000161 entry = hashmap_get_entry(map, &key, ent, NULL);
Eric Wongb6c52412019-10-06 23:30:30 +0000162 if (!entry) {
René Scharfeca56dad2021-03-13 17:17:22 +0100163 CALLOC_ARRAY(entry, 1);
Eric Wongd22245a2019-10-06 23:30:27 +0000164 hashmap_entry_init(&entry->ent, hash);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800165 entry->path = xstrdup(key.path);
166 oidset_init(&entry->trees, 16);
Eric Wong26b455f2019-10-06 23:30:32 +0000167 hashmap_put(map, &entry->ent);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800168 }
169
170 oidset_insert(&entry->trees, oid);
171}
172
173static void add_children_by_path(struct repository *r,
174 struct tree *tree,
175 struct hashmap *map)
176{
177 struct tree_desc desc;
178 struct name_entry entry;
179
180 if (!tree)
181 return;
182
183 if (parse_tree_gently(tree, 1) < 0)
184 return;
185
186 init_tree_desc(&desc, tree->buffer, tree->size);
187 while (tree_entry(&desc, &entry)) {
188 switch (object_type(entry.mode)) {
189 case OBJ_TREE:
Junio C Hamano5fda3432019-02-06 22:05:24 -0800190 paths_and_oids_insert(map, entry.path, &entry.oid);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800191
192 if (tree->object.flags & UNINTERESTING) {
Junio C Hamano5fda3432019-02-06 22:05:24 -0800193 struct tree *child = lookup_tree(r, &entry.oid);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800194 if (child)
195 child->object.flags |= UNINTERESTING;
196 }
197 break;
198 case OBJ_BLOB:
199 if (tree->object.flags & UNINTERESTING) {
Junio C Hamano5fda3432019-02-06 22:05:24 -0800200 struct blob *child = lookup_blob(r, &entry.oid);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800201 if (child)
202 child->object.flags |= UNINTERESTING;
203 }
204 break;
205 default:
206 /* Subproject commit - not in this repository */
207 break;
208 }
209 }
210
211 free_tree_buffer(tree);
212}
213
Derrick Stoleef1f5de42019-01-16 10:25:58 -0800214void mark_trees_uninteresting_sparse(struct repository *r,
215 struct oidset *trees)
216{
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800217 unsigned has_interesting = 0, has_uninteresting = 0;
Elijah Newrenb19315d2020-11-11 20:02:20 +0000218 struct hashmap map = HASHMAP_INIT(path_and_oids_cmp, NULL);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800219 struct hashmap_iter map_iter;
220 struct path_and_oids_entry *entry;
Derrick Stoleef1f5de42019-01-16 10:25:58 -0800221 struct object_id *oid;
222 struct oidset_iter iter;
223
224 oidset_iter_init(trees, &iter);
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800225 while ((!has_interesting || !has_uninteresting) &&
226 (oid = oidset_iter_next(&iter))) {
Derrick Stoleef1f5de42019-01-16 10:25:58 -0800227 struct tree *tree = lookup_tree(r, oid);
228
229 if (!tree)
230 continue;
231
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800232 if (tree->object.flags & UNINTERESTING)
233 has_uninteresting = 1;
234 else
235 has_interesting = 1;
Derrick Stoleef1f5de42019-01-16 10:25:58 -0800236 }
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800237
238 /* Do not walk unless we have both types of trees. */
239 if (!has_uninteresting || !has_interesting)
240 return;
241
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800242 oidset_iter_init(trees, &iter);
243 while ((oid = oidset_iter_next(&iter))) {
244 struct tree *tree = lookup_tree(r, oid);
245 add_children_by_path(r, tree, &map);
246 }
247
Eric Wong23dee692019-10-06 23:30:41 +0000248 hashmap_for_each_entry(&map, &map_iter, entry, ent /* member name */)
Derrick Stoleed5d2e932019-01-16 10:25:59 -0800249 mark_trees_uninteresting_sparse(r, &entry->trees);
250
251 paths_and_oids_clear(&map);
Derrick Stoleef1f5de42019-01-16 10:25:58 -0800252}
253
Jeff King43fc6432018-05-11 14:02:27 -0400254struct commit_stack {
255 struct commit **items;
256 size_t nr, alloc;
257};
Ævar Arnfjörð Bjarmason9865b6e2021-09-27 14:54:25 +0200258#define COMMIT_STACK_INIT { 0 }
Jeff King43fc6432018-05-11 14:02:27 -0400259
260static void commit_stack_push(struct commit_stack *stack, struct commit *commit)
261{
262 ALLOC_GROW(stack->items, stack->nr + 1, stack->alloc);
263 stack->items[stack->nr++] = commit;
264}
265
266static struct commit *commit_stack_pop(struct commit_stack *stack)
267{
268 return stack->nr ? stack->items[--stack->nr] : NULL;
269}
270
271static void commit_stack_clear(struct commit_stack *stack)
272{
273 FREE_AND_NULL(stack->items);
274 stack->nr = stack->alloc = 0;
275}
276
Jerry Zhang9d505b72022-01-11 13:39:41 -0800277static void mark_one_parent_uninteresting(struct rev_info *revs, struct commit *commit,
Jeff King8702b302018-05-11 14:03:15 -0400278 struct commit_stack *pending)
279{
280 struct commit_list *l;
281
282 if (commit->object.flags & UNINTERESTING)
283 return;
284 commit->object.flags |= UNINTERESTING;
285
286 /*
287 * Normally we haven't parsed the parent
288 * yet, so we won't have a parent of a parent
289 * here. However, it may turn out that we've
290 * reached this commit some other way (where it
291 * wasn't uninteresting), in which case we need
292 * to mark its parents recursively too..
293 */
Jerry Zhang9d505b72022-01-11 13:39:41 -0800294 for (l = commit->parents; l; l = l->next) {
Jeff King8702b302018-05-11 14:03:15 -0400295 commit_stack_push(pending, l->item);
Jerry Zhang9d505b72022-01-11 13:39:41 -0800296 if (revs && revs->exclude_first_parent_only)
297 break;
298 }
Jeff King8702b302018-05-11 14:03:15 -0400299}
300
Jerry Zhang9d505b72022-01-11 13:39:41 -0800301void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit)
Linus Torvaldsae563542006-02-25 16:19:46 -0800302{
Jeff King43fc6432018-05-11 14:02:27 -0400303 struct commit_stack pending = COMMIT_STACK_INIT;
304 struct commit_list *l;
Nguyễn Thái Ngọc Duy941ba8d2012-01-14 19:19:53 +0700305
Jerry Zhang9d505b72022-01-11 13:39:41 -0800306 for (l = commit->parents; l; l = l->next) {
307 mark_one_parent_uninteresting(revs, l->item, &pending);
308 if (revs && revs->exclude_first_parent_only)
309 break;
310 }
Linus Torvaldsae563542006-02-25 16:19:46 -0800311
Jeff King8702b302018-05-11 14:03:15 -0400312 while (pending.nr > 0)
Jerry Zhang9d505b72022-01-11 13:39:41 -0800313 mark_one_parent_uninteresting(revs, commit_stack_pop(&pending),
Jeff King8702b302018-05-11 14:03:15 -0400314 &pending);
Nguyễn Thái Ngọc Duy941ba8d2012-01-14 19:19:53 +0700315
Jeff King43fc6432018-05-11 14:02:27 -0400316 commit_stack_clear(&pending);
Linus Torvaldsae563542006-02-25 16:19:46 -0800317}
318
Jeff King20739492014-10-15 18:43:19 -0400319static void add_pending_object_with_path(struct rev_info *revs,
Michael Haggertyff5f5f22013-05-25 11:08:07 +0200320 struct object *obj,
Jeff King20739492014-10-15 18:43:19 -0400321 const char *name, unsigned mode,
322 const char *path)
Martin Koeglerbb6c2fb2007-04-22 18:43:59 +0200323{
Jonathan Tana4f66a72020-09-01 15:28:07 -0700324 struct interpret_branch_name_options options = { 0 };
Junio C Hamanocc243c32011-05-18 18:08:09 -0700325 if (!obj)
326 return;
Linus Torvaldsaa27e462007-02-27 16:22:52 -0800327 if (revs->no_walk && (obj->flags & UNINTERESTING))
Linus Torvaldsf222abd2009-07-13 14:41:12 -0700328 revs->no_walk = 0;
Junio C Hamano105e4732010-01-26 13:48:28 -0800329 if (revs->reflog_info && obj->type == OBJ_COMMIT) {
330 struct strbuf buf = STRBUF_INIT;
Jeff King1d72b602021-06-10 09:06:43 -0400331 size_t namelen = strlen(name);
332 int len = interpret_branch_name(name, namelen, &buf, &options);
Junio C Hamano105e4732010-01-26 13:48:28 -0800333
Jeff King1d72b602021-06-10 09:06:43 -0400334 if (0 < len && len < namelen && buf.len)
Junio C Hamano105e4732010-01-26 13:48:28 -0800335 strbuf_addstr(&buf, name + len);
Jeff Kingd08565b2017-07-07 05:14:07 -0400336 add_reflog_for_walk(revs->reflog_info,
337 (struct commit *)obj,
338 buf.buf[0] ? buf.buf: name);
Junio C Hamano105e4732010-01-26 13:48:28 -0800339 strbuf_release(&buf);
Jeff Kingd08565b2017-07-07 05:14:07 -0400340 return; /* do not add the commit itself */
Junio C Hamano105e4732010-01-26 13:48:28 -0800341 }
Jeff King20739492014-10-15 18:43:19 -0400342 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);
Linus Torvaldsae563542006-02-25 16:19:46 -0800350}
351
Michael Haggertyff5f5f22013-05-25 11:08:07 +0200352void add_pending_object(struct rev_info *revs,
353 struct object *obj, const char *name)
Junio C Hamano2d93b9f2007-06-08 02:24:58 -0700354{
355 add_pending_object_with_mode(revs, obj, name, S_IFINVALID);
356}
357
Junio C Hamano3384a2d2007-12-11 10:09:04 -0800358void add_head_to_pending(struct rev_info *revs)
359{
brian m. carlson654b9a92017-05-06 22:10:27 +0000360 struct object_id oid;
Junio C Hamano3384a2d2007-12-11 10:09:04 -0800361 struct object *obj;
brian m. carlson654b9a92017-05-06 22:10:27 +0000362 if (get_oid("HEAD", &oid))
Junio C Hamano3384a2d2007-12-11 10:09:04 -0800363 return;
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +0200364 obj = parse_object(revs->repo, &oid);
Junio C Hamano3384a2d2007-12-11 10:09:04 -0800365 if (!obj)
366 return;
367 add_pending_object(revs, obj, "HEAD");
368}
369
Michael Haggertyff5f5f22013-05-25 11:08:07 +0200370static struct object *get_reference(struct rev_info *revs, const char *name,
brian m. carlson654b9a92017-05-06 22:10:27 +0000371 const struct object_id *oid,
Michael Haggertyff5f5f22013-05-25 11:08:07 +0200372 unsigned int flags)
Linus Torvaldsae563542006-02-25 16:19:46 -0800373{
374 struct object *object;
Patrick Steinhardtf559d6d2021-08-09 10:12:03 +0200375 struct commit *commit;
Linus Torvaldsae563542006-02-25 16:19:46 -0800376
Jonathan Tanec0c5792018-12-04 14:42:38 -0800377 /*
Patrick Steinhardtf559d6d2021-08-09 10:12:03 +0200378 * If the repository has commit graphs, we try to opportunistically
379 * look up the object ID in those graphs. Like this, we can avoid
380 * parsing commit data from disk.
Jonathan Tanec0c5792018-12-04 14:42:38 -0800381 */
Patrick Steinhardtf559d6d2021-08-09 10:12:03 +0200382 commit = lookup_commit_in_graph(revs->repo, oid);
383 if (commit)
384 object = &commit->object;
385 else
Jonathan Tanec0c5792018-12-04 14:42:38 -0800386 object = parse_object(revs->repo, oid);
Jonathan Tanec0c5792018-12-04 14:42:38 -0800387
Junio C Hamanocc243c32011-05-18 18:08:09 -0700388 if (!object) {
389 if (revs->ignore_missing)
390 return object;
Jonathan Tandf11e192017-12-08 15:27:15 +0000391 if (revs->exclude_promisor_objects && is_promisor_object(oid))
392 return NULL;
Linus Torvaldsae563542006-02-25 16:19:46 -0800393 die("bad object %s", name);
Junio C Hamanocc243c32011-05-18 18:08:09 -0700394 }
Linus Torvaldscd2bdc52006-04-14 16:52:13 -0700395 object->flags |= flags;
396 return object;
397}
398
brian m. carlsona58a1b02017-05-06 22:10:26 +0000399void add_pending_oid(struct rev_info *revs, const char *name,
400 const struct object_id *oid, unsigned int flags)
René Scharfe26c31772011-10-01 17:43:52 +0200401{
brian m. carlson654b9a92017-05-06 22:10:27 +0000402 struct object *object = get_reference(revs, name, oid, flags);
René Scharfe26c31772011-10-01 17:43:52 +0200403 add_pending_object(revs, object, name);
404}
405
Michael Haggertyff5f5f22013-05-25 11:08:07 +0200406static struct commit *handle_commit(struct rev_info *revs,
Jeff King20739492014-10-15 18:43:19 -0400407 struct object_array_entry *entry)
Linus Torvaldscd2bdc52006-04-14 16:52:13 -0700408{
Jeff King20739492014-10-15 18:43:19 -0400409 struct object *object = entry->item;
410 const char *name = entry->name;
411 const char *path = entry->path;
412 unsigned int mode = entry->mode;
Linus Torvaldscd2bdc52006-04-14 16:52:13 -0700413 unsigned long flags = object->flags;
Linus Torvaldsae563542006-02-25 16:19:46 -0800414
415 /*
416 * Tag object? Look what it points to..
417 */
Linus Torvalds19746322006-07-11 20:45:31 -0700418 while (object->type == OBJ_TAG) {
Linus Torvaldsae563542006-02-25 16:19:46 -0800419 struct tag *tag = (struct tag *) object;
Linus Torvaldscd2bdc52006-04-14 16:52:13 -0700420 if (revs->tag_objects && !(flags & UNINTERESTING))
Linus Torvaldsae563542006-02-25 16:19:46 -0800421 add_pending_object(revs, object, tag->tag);
René Scharfedad3f062019-09-05 21:55:55 +0200422 object = parse_object(revs->repo, get_tagged_oid(tag));
Junio C Hamanoaeeae1b2009-01-27 23:19:30 -0800423 if (!object) {
Jeff Kinga3ba6bf2017-05-20 04:30:25 -0400424 if (revs->ignore_missing_links || (flags & UNINTERESTING))
Junio C Hamanoaeeae1b2009-01-27 23:19:30 -0800425 return NULL;
Jonathan Tandc0a13f2018-07-12 17:03:06 -0700426 if (revs->exclude_promisor_objects &&
427 is_promisor_object(&tag->tagged->oid))
428 return NULL;
brian m. carlsonf2fd0762015-11-10 02:22:28 +0000429 die("bad object %s", oid_to_hex(&tag->tagged->oid));
Junio C Hamanoaeeae1b2009-01-27 23:19:30 -0800430 }
Junio C Hamanoa7435282014-01-15 12:26:13 -0800431 object->flags |= flags;
Jeff King20739492014-10-15 18:43:19 -0400432 /*
433 * We'll handle the tagged object by looping or dropping
434 * through to the non-tag handlers below. Do not
Jeff King728350b2015-12-17 01:47:07 -0500435 * propagate path data from the tag's pending entry.
Jeff King20739492014-10-15 18:43:19 -0400436 */
Jeff King20739492014-10-15 18:43:19 -0400437 path = NULL;
438 mode = 0;
Linus Torvaldsae563542006-02-25 16:19:46 -0800439 }
440
441 /*
442 * Commit object? Just return it, we'll do all the complex
443 * reachability crud.
444 */
Linus Torvalds19746322006-07-11 20:45:31 -0700445 if (object->type == OBJ_COMMIT) {
Linus Torvaldsae563542006-02-25 16:19:46 -0800446 struct commit *commit = (struct commit *)object;
Nguyễn Thái Ngọc Duy87be2522018-05-19 07:28:24 +0200447
Michael Forneyea3f7e52020-06-23 13:56:58 -0700448 if (repo_parse_commit(revs->repo, commit) < 0)
Linus Torvaldsae563542006-02-25 16:19:46 -0800449 die("unable to parse commit %s", name);
Linus Torvaldsd9a83682006-02-27 08:54:36 -0800450 if (flags & UNINTERESTING) {
Jerry Zhang9d505b72022-01-11 13:39:41 -0800451 mark_parents_uninteresting(revs, commit);
Derrick Stolee1b4d8822019-05-21 09:14:38 -0400452
453 if (!revs->topo_order || !generation_numbers_enabled(the_repository))
454 revs->limited = 1;
Linus Torvaldsd9a83682006-02-27 08:54:36 -0800455 }
Nguyễn Thái Ngọc Duy87be2522018-05-19 07:28:24 +0200456 if (revs->sources) {
457 char **slot = revision_sources_at(revs->sources, commit);
458
459 if (!*slot)
460 *slot = xstrdup(name);
461 }
Linus Torvaldsae563542006-02-25 16:19:46 -0800462 return commit;
463 }
464
465 /*
Mike Ralphson3ea3c212009-04-17 19:13:30 +0100466 * Tree object? Either mark it uninteresting, or add it
Linus Torvaldsae563542006-02-25 16:19:46 -0800467 * to the list of objects to look at later..
468 */
Linus Torvalds19746322006-07-11 20:45:31 -0700469 if (object->type == OBJ_TREE) {
Linus Torvaldsae563542006-02-25 16:19:46 -0800470 struct tree *tree = (struct tree *)object;
471 if (!revs->tree_objects)
472 return NULL;
473 if (flags & UNINTERESTING) {
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +0200474 mark_tree_contents_uninteresting(revs->repo, tree);
Linus Torvaldsae563542006-02-25 16:19:46 -0800475 return NULL;
476 }
Jeff King20739492014-10-15 18:43:19 -0400477 add_pending_object_with_path(revs, object, name, mode, path);
Linus Torvaldsae563542006-02-25 16:19:46 -0800478 return NULL;
479 }
480
481 /*
482 * Blob object? You know the drill by now..
483 */
Linus Torvalds19746322006-07-11 20:45:31 -0700484 if (object->type == OBJ_BLOB) {
Linus Torvaldsae563542006-02-25 16:19:46 -0800485 if (!revs->blob_objects)
486 return NULL;
Junio C Hamanoa7435282014-01-15 12:26:13 -0800487 if (flags & UNINTERESTING)
Linus Torvaldsae563542006-02-25 16:19:46 -0800488 return NULL;
Jeff King20739492014-10-15 18:43:19 -0400489 add_pending_object_with_path(revs, object, name, mode, path);
Linus Torvaldsae563542006-02-25 16:19:46 -0800490 return NULL;
491 }
492 die("%s is unknown object", name);
493}
494
Jeff Kingb6e8a3b2015-04-17 18:11:04 -0400495static int everybody_uninteresting(struct commit_list *orig,
496 struct commit **interesting_cache)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800497{
498 struct commit_list *list = orig;
Jeff Kingb6e8a3b2015-04-17 18:11:04 -0400499
500 if (*interesting_cache) {
501 struct commit *commit = *interesting_cache;
502 if (!(commit->object.flags & UNINTERESTING))
503 return 0;
504 }
505
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800506 while (list) {
507 struct commit *commit = list->item;
508 list = list->next;
509 if (commit->object.flags & UNINTERESTING)
510 continue;
Stefan Bellerae40ebd2015-06-26 12:40:19 -0700511
512 *interesting_cache = commit;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800513 return 0;
514 }
515 return 1;
516}
517
Junio C Hamano0a4ba7f2007-03-14 13:12:18 -0700518/*
Kevin Bracey4d826602013-05-16 18:32:39 +0300519 * A definition of "relevant" commit that we can use to simplify limited graphs
520 * by eliminating side branches.
521 *
522 * A "relevant" commit is one that is !UNINTERESTING (ie we are including it
523 * in our list), or that is a specified BOTTOM commit. Then after computing
524 * a limited list, during processing we can generally ignore boundary merges
525 * coming from outside the graph, (ie from irrelevant parents), and treat
526 * those merges as if they were single-parent. TREESAME is defined to consider
527 * only relevant parents, if any. If we are TREESAME to our on-graph parents,
528 * we don't care if we were !TREESAME to non-graph parents.
529 *
530 * Treating bottom commits as relevant ensures that a limited graph's
531 * connection to the actual bottom commit is not viewed as a side branch, but
532 * treated as part of the graph. For example:
533 *
534 * ....Z...A---X---o---o---B
535 * . /
536 * W---Y
537 *
538 * When computing "A..B", the A-X connection is at least as important as
539 * Y-X, despite A being flagged UNINTERESTING.
540 *
541 * And when computing --ancestry-path "A..B", the A-X connection is more
542 * important than Y-X, despite both A and Y being flagged UNINTERESTING.
543 */
544static inline int relevant_commit(struct commit *commit)
545{
546 return (commit->object.flags & (UNINTERESTING | BOTTOM)) != UNINTERESTING;
547}
548
549/*
550 * Return a single relevant commit from a parent list. If we are a TREESAME
551 * commit, and this selects one of our parents, then we can safely simplify to
552 * that parent.
553 */
554static struct commit *one_relevant_parent(const struct rev_info *revs,
555 struct commit_list *orig)
556{
557 struct commit_list *list = orig;
558 struct commit *relevant = NULL;
559
560 if (!orig)
561 return NULL;
562
563 /*
564 * For 1-parent commits, or if first-parent-only, then return that
565 * first parent (even if not "relevant" by the above definition).
566 * TREESAME will have been set purely on that parent.
567 */
568 if (revs->first_parent_only || !orig->next)
569 return orig->item;
570
571 /*
572 * For multi-parent commits, identify a sole relevant parent, if any.
573 * If we have only one relevant parent, then TREESAME will be set purely
574 * with regard to that parent, and we can simplify accordingly.
575 *
576 * If we have more than one relevant parent, or no relevant parents
577 * (and multiple irrelevant ones), then we can't select a parent here
578 * and return NULL.
579 */
580 while (list) {
581 struct commit *commit = list->item;
582 list = list->next;
583 if (relevant_commit(commit)) {
584 if (relevant)
585 return NULL;
586 relevant = commit;
587 }
588 }
589 return relevant;
590}
591
592/*
Junio C Hamano0a4ba7f2007-03-14 13:12:18 -0700593 * The goal is to get REV_TREE_NEW as the result only if the
Linus Torvaldsceff8e72009-06-02 18:34:01 -0700594 * diff consists of all '+' (and no other changes), REV_TREE_OLD
595 * if the whole diff is removal of old data, and otherwise
596 * REV_TREE_DIFFERENT (of course if the trees are the same we
597 * want REV_TREE_SAME).
Jeff Kinga937b372017-10-13 11:27:45 -0400598 *
599 * The only time we care about the distinction is when
600 * remove_empty_trees is in effect, in which case we care only about
601 * whether the whole change is REV_TREE_NEW, or if there's another type
602 * of change. Which means we can stop the diff early in either of these
603 * cases:
604 *
605 * 1. We're not using remove_empty_trees at all.
606 *
607 * 2. We saw anything except REV_TREE_NEW.
Junio C Hamano0a4ba7f2007-03-14 13:12:18 -0700608 */
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +0100609static int tree_difference = REV_TREE_SAME;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800610
611static void file_add_remove(struct diff_options *options,
612 int addremove, unsigned mode,
Brandon Williamsc26022e2017-05-30 10:30:47 -0700613 const struct object_id *oid,
614 int oid_valid,
Jens Lehmanne3d42c42010-01-18 21:26:18 +0100615 const char *fullpath, unsigned dirty_submodule)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800616{
Linus Torvaldsceff8e72009-06-02 18:34:01 -0700617 int diff = addremove == '+' ? REV_TREE_NEW : REV_TREE_OLD;
Jeff Kinga937b372017-10-13 11:27:45 -0400618 struct rev_info *revs = options->change_fn_data;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800619
Linus Torvaldsceff8e72009-06-02 18:34:01 -0700620 tree_difference |= diff;
Jeff Kinga937b372017-10-13 11:27:45 -0400621 if (!revs->remove_empty_trees || tree_difference != REV_TREE_NEW)
Brandon Williams0d1e0e72017-10-31 11:19:11 -0700622 options->flags.has_changes = 1;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800623}
624
625static void file_change(struct diff_options *options,
626 unsigned old_mode, unsigned new_mode,
Brandon Williams94a00972017-05-30 10:30:49 -0700627 const struct object_id *old_oid,
628 const struct object_id *new_oid,
629 int old_oid_valid, int new_oid_valid,
Jens Lehmanne3d42c42010-01-18 21:26:18 +0100630 const char *fullpath,
631 unsigned old_dirty_submodule, unsigned new_dirty_submodule)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800632{
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +0100633 tree_difference = REV_TREE_DIFFERENT;
Brandon Williams0d1e0e72017-10-31 11:19:11 -0700634 options->flags.has_changes = 1;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800635}
636
Garima Singh42e50e72020-04-06 16:59:53 +0000637static int bloom_filter_atexit_registered;
638static unsigned int count_bloom_filter_maybe;
639static unsigned int count_bloom_filter_definitely_not;
640static unsigned int count_bloom_filter_false_positive;
641static unsigned int count_bloom_filter_not_present;
Garima Singh42e50e72020-04-06 16:59:53 +0000642
643static void trace2_bloom_filter_statistics_atexit(void)
644{
645 struct json_writer jw = JSON_WRITER_INIT;
646
647 jw_object_begin(&jw, 0);
648 jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
Garima Singh42e50e72020-04-06 16:59:53 +0000649 jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
650 jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
651 jw_object_intmax(&jw, "false_positive", count_bloom_filter_false_positive);
652 jw_end(&jw);
653
654 trace2_data_json("bloom", the_repository, "statistics", &jw);
655
656 jw_release(&jw);
657}
658
Derrick Stolee8918e372020-04-16 20:14:02 +0000659static int forbid_bloom_filters(struct pathspec *spec)
660{
661 if (spec->has_wildcard)
662 return 1;
663 if (spec->nr > 1)
664 return 1;
665 if (spec->magic & ~PATHSPEC_LITERAL)
666 return 1;
667 if (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))
668 return 1;
669
670 return 0;
671}
672
Garima Singha56b9462020-04-06 16:59:52 +0000673static void prepare_to_use_bloom_filter(struct rev_info *revs)
674{
675 struct pathspec_item *pi;
676 char *path_alloc = NULL;
SZEDER Gáborc525ce92020-07-01 13:27:30 +0000677 const char *path, *p;
SZEDER Gáborc525ce92020-07-01 13:27:30 +0000678 size_t len;
679 int path_component_nr = 1;
Garima Singha56b9462020-04-06 16:59:52 +0000680
681 if (!revs->commits)
Derrick Stolee8918e372020-04-16 20:14:02 +0000682 return;
683
684 if (forbid_bloom_filters(&revs->prune_data))
685 return;
Garima Singha56b9462020-04-06 16:59:52 +0000686
687 repo_parse_commit(revs->repo, revs->commits->item);
688
Taylor Blau4f364402020-09-09 11:22:44 -0400689 revs->bloom_filter_settings = get_bloom_filter_settings(revs->repo);
Garima Singha56b9462020-04-06 16:59:52 +0000690 if (!revs->bloom_filter_settings)
691 return;
692
Derrick Stoleef32dde82020-05-11 11:56:19 +0000693 if (!revs->pruning.pathspec.nr)
694 return;
695
Garima Singha56b9462020-04-06 16:59:52 +0000696 pi = &revs->pruning.pathspec.items[0];
Garima Singha56b9462020-04-06 16:59:52 +0000697
698 /* remove single trailing slash from path, if needed */
Jeff Kingfd9a6312020-08-04 03:46:52 -0400699 if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
700 path_alloc = xmemdupz(pi->match, pi->len - 1);
Derrick Stoleedc8e95b2020-07-01 13:27:28 +0000701 path = path_alloc;
Garima Singha56b9462020-04-06 16:59:52 +0000702 } else
Derrick Stoleedc8e95b2020-07-01 13:27:28 +0000703 path = pi->match;
Garima Singha56b9462020-04-06 16:59:52 +0000704
705 len = strlen(path);
Taylor Blauf3c2a362020-07-01 13:27:29 +0000706 if (!len) {
707 revs->bloom_filter_settings = NULL;
Jeff King398e6592020-08-04 03:50:17 -0400708 free(path_alloc);
Taylor Blauf3c2a362020-07-01 13:27:29 +0000709 return;
710 }
Garima Singha56b9462020-04-06 16:59:52 +0000711
SZEDER Gáborc525ce92020-07-01 13:27:30 +0000712 p = path;
713 while (*p) {
714 /*
715 * At this point, the path is normalized to use Unix-style
716 * path separators. This is required due to how the
717 * changed-path Bloom filters store the paths.
718 */
719 if (*p == '/')
720 path_component_nr++;
721 p++;
722 }
723
724 revs->bloom_keys_nr = path_component_nr;
725 ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr);
726
727 fill_bloom_key(path, len, &revs->bloom_keys[0],
728 revs->bloom_filter_settings);
729 path_component_nr = 1;
730
731 p = path + len - 1;
732 while (p > path) {
733 if (*p == '/')
734 fill_bloom_key(path, p - path,
735 &revs->bloom_keys[path_component_nr++],
736 revs->bloom_filter_settings);
737 p--;
738 }
Garima Singha56b9462020-04-06 16:59:52 +0000739
Garima Singh42e50e72020-04-06 16:59:53 +0000740 if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
741 atexit(trace2_bloom_filter_statistics_atexit);
742 bloom_filter_atexit_registered = 1;
743 }
744
Garima Singha56b9462020-04-06 16:59:52 +0000745 free(path_alloc);
746}
747
748static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
749 struct commit *commit)
750{
751 struct bloom_filter *filter;
SZEDER Gáborc525ce92020-07-01 13:27:30 +0000752 int result = 1, j;
Garima Singha56b9462020-04-06 16:59:52 +0000753
754 if (!revs->repo->objects->commit_graph)
755 return -1;
756
Abhishek Kumarc49c82a2020-06-17 14:44:10 +0530757 if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
Garima Singha56b9462020-04-06 16:59:52 +0000758 return -1;
759
Taylor Blau312cff52020-09-16 14:07:32 -0400760 filter = get_bloom_filter(revs->repo, commit);
Garima Singha56b9462020-04-06 16:59:52 +0000761
762 if (!filter) {
Garima Singh42e50e72020-04-06 16:59:53 +0000763 count_bloom_filter_not_present++;
Garima Singha56b9462020-04-06 16:59:52 +0000764 return -1;
765 }
766
SZEDER Gáborc525ce92020-07-01 13:27:30 +0000767 for (j = 0; result && j < revs->bloom_keys_nr; j++) {
768 result = bloom_filter_contains(filter,
769 &revs->bloom_keys[j],
770 revs->bloom_filter_settings);
Garima Singha56b9462020-04-06 16:59:52 +0000771 }
772
Garima Singh42e50e72020-04-06 16:59:53 +0000773 if (result)
774 count_bloom_filter_maybe++;
775 else
776 count_bloom_filter_definitely_not++;
777
Garima Singha56b9462020-04-06 16:59:52 +0000778 return result;
779}
780
Michael Haggertyff5f5f22013-05-25 11:08:07 +0200781static int rev_compare_tree(struct rev_info *revs,
Garima Singha56b9462020-04-06 16:59:52 +0000782 struct commit *parent, struct commit *commit, int nth_parent)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800783{
Derrick Stolee2e27bd72018-04-06 19:09:38 +0000784 struct tree *t1 = get_commit_tree(parent);
785 struct tree *t2 = get_commit_tree(commit);
Garima Singha56b9462020-04-06 16:59:52 +0000786 int bloom_ret = 1;
Linus Torvalds3a5e8602008-11-03 10:45:41 -0800787
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800788 if (!t1)
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +0100789 return REV_TREE_NEW;
Linus Torvaldsceff8e72009-06-02 18:34:01 -0700790 if (!t2)
791 return REV_TREE_OLD;
Linus Torvalds78892e32008-11-03 11:25:46 -0800792
793 if (revs->simplify_by_decoration) {
794 /*
795 * If we are simplifying by decoration, then the commit
796 * is worth showing if it has a tag pointing at it.
797 */
Jeff King2608c242014-08-26 06:23:54 -0400798 if (get_name_decoration(&commit->object))
Linus Torvalds78892e32008-11-03 11:25:46 -0800799 return REV_TREE_DIFFERENT;
800 /*
801 * A commit that is not pointed by a tag is uninteresting
802 * if we are not limited by path. This means that you will
803 * see the usual "commits that touch the paths" plus any
804 * tagged commit by specifying both --simplify-by-decoration
805 * and pathspec.
806 */
Nguyễn Thái Ngọc Duyafe069d2010-12-17 19:43:06 +0700807 if (!revs->prune_data.nr)
Linus Torvalds78892e32008-11-03 11:25:46 -0800808 return REV_TREE_SAME;
809 }
Linus Torvaldsceff8e72009-06-02 18:34:01 -0700810
SZEDER Gáborc525ce92020-07-01 13:27:30 +0000811 if (revs->bloom_keys_nr && !nth_parent) {
Garima Singha56b9462020-04-06 16:59:52 +0000812 bloom_ret = check_maybe_different_in_bloom_filter(revs, commit);
813
814 if (bloom_ret == 0)
815 return REV_TREE_SAME;
816 }
817
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +0100818 tree_difference = REV_TREE_SAME;
Brandon Williams0d1e0e72017-10-31 11:19:11 -0700819 revs->pruning.flags.has_changes = 0;
SZEDER Gábor0ee3cb82020-06-05 13:00:27 +0000820 diff_tree_oid(&t1->object.oid, &t2->object.oid, "", &revs->pruning);
Garima Singha56b9462020-04-06 16:59:52 +0000821
Garima Singh42e50e72020-04-06 16:59:53 +0000822 if (!nth_parent)
823 if (bloom_ret == 1 && tree_difference == REV_TREE_SAME)
824 count_bloom_filter_false_positive++;
825
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800826 return tree_difference;
827}
828
Linus Torvalds3a5e8602008-11-03 10:45:41 -0800829static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800830{
Derrick Stolee2e27bd72018-04-06 19:09:38 +0000831 struct tree *t1 = get_commit_tree(commit);
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800832
833 if (!t1)
834 return 0;
835
Junio C Hamano0a4ba7f2007-03-14 13:12:18 -0700836 tree_difference = REV_TREE_SAME;
Brandon Williams0d1e0e72017-10-31 11:19:11 -0700837 revs->pruning.flags.has_changes = 0;
SZEDER Gábor0ee3cb82020-06-05 13:00:27 +0000838 diff_tree_oid(NULL, &t1->object.oid, "", &revs->pruning);
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800839
SZEDER Gábor0ee3cb82020-06-05 13:00:27 +0000840 return tree_difference == REV_TREE_SAME;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800841}
842
Kevin Braceyd0af6632013-05-16 18:32:34 +0300843struct treesame_state {
844 unsigned int nparents;
845 unsigned char treesame[FLEX_ARRAY];
846};
847
848static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)
849{
850 unsigned n = commit_list_count(commit->parents);
Jeff King50a6c8e2016-02-22 17:44:35 -0500851 struct treesame_state *st = xcalloc(1, st_add(sizeof(*st), n));
Kevin Braceyd0af6632013-05-16 18:32:34 +0300852 st->nparents = n;
853 add_decoration(&revs->treesame, &commit->object, st);
854 return st;
855}
856
857/*
858 * Must be called immediately after removing the nth_parent from a commit's
859 * parent list, if we are maintaining the per-parent treesame[] decoration.
860 * This does not recalculate the master TREESAME flag - update_treesame()
861 * should be called to update it after a sequence of treesame[] modifications
862 * that may have affected it.
863 */
864static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned nth_parent)
865{
866 struct treesame_state *st;
867 int old_same;
868
869 if (!commit->parents) {
870 /*
871 * Have just removed the only parent from a non-merge.
872 * Different handling, as we lack decoration.
873 */
874 if (nth_parent != 0)
875 die("compact_treesame %u", nth_parent);
876 old_same = !!(commit->object.flags & TREESAME);
877 if (rev_same_tree_as_empty(revs, commit))
878 commit->object.flags |= TREESAME;
879 else
880 commit->object.flags &= ~TREESAME;
881 return old_same;
882 }
883
884 st = lookup_decoration(&revs->treesame, &commit->object);
885 if (!st || nth_parent >= st->nparents)
886 die("compact_treesame %u", nth_parent);
887
888 old_same = st->treesame[nth_parent];
889 memmove(st->treesame + nth_parent,
890 st->treesame + nth_parent + 1,
891 st->nparents - nth_parent - 1);
892
893 /*
894 * If we've just become a non-merge commit, update TREESAME
895 * immediately, and remove the no-longer-needed decoration.
896 * If still a merge, defer update until update_treesame().
897 */
898 if (--st->nparents == 1) {
899 if (commit->parents->next)
900 die("compact_treesame parents mismatch");
901 if (st->treesame[0] && revs->dense)
902 commit->object.flags |= TREESAME;
903 else
904 commit->object.flags &= ~TREESAME;
905 free(add_decoration(&revs->treesame, &commit->object, NULL));
906 }
907
908 return old_same;
909}
910
911static unsigned update_treesame(struct rev_info *revs, struct commit *commit)
912{
913 if (commit->parents && commit->parents->next) {
914 unsigned n;
915 struct treesame_state *st;
Kevin Bracey4d826602013-05-16 18:32:39 +0300916 struct commit_list *p;
917 unsigned relevant_parents;
918 unsigned relevant_change, irrelevant_change;
Kevin Braceyd0af6632013-05-16 18:32:34 +0300919
920 st = lookup_decoration(&revs->treesame, &commit->object);
921 if (!st)
brian m. carlsonf2fd0762015-11-10 02:22:28 +0000922 die("update_treesame %s", oid_to_hex(&commit->object.oid));
Kevin Bracey4d826602013-05-16 18:32:39 +0300923 relevant_parents = 0;
924 relevant_change = irrelevant_change = 0;
925 for (p = commit->parents, n = 0; p; n++, p = p->next) {
926 if (relevant_commit(p->item)) {
927 relevant_change |= !st->treesame[n];
928 relevant_parents++;
929 } else
930 irrelevant_change |= !st->treesame[n];
Kevin Braceyd0af6632013-05-16 18:32:34 +0300931 }
Kevin Bracey4d826602013-05-16 18:32:39 +0300932 if (relevant_parents ? relevant_change : irrelevant_change)
933 commit->object.flags &= ~TREESAME;
934 else
935 commit->object.flags |= TREESAME;
Kevin Braceyd0af6632013-05-16 18:32:34 +0300936 }
937
938 return commit->object.flags & TREESAME;
939}
940
Kevin Bracey4d826602013-05-16 18:32:39 +0300941static inline int limiting_can_increase_treesame(const struct rev_info *revs)
942{
943 /*
944 * TREESAME is irrelevant unless prune && dense;
945 * if simplify_history is set, we can't have a mixture of TREESAME and
946 * !TREESAME INTERESTING parents (and we don't have treesame[]
947 * decoration anyway);
948 * if first_parent_only is set, then the TREESAME flag is locked
949 * against the first parent (and again we lack treesame[] decoration).
950 */
951 return revs->prune && revs->dense &&
952 !revs->simplify_history &&
953 !revs->first_parent_only;
954}
955
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800956static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
957{
958 struct commit_list **pp, *parent;
Kevin Braceyd0af6632013-05-16 18:32:34 +0300959 struct treesame_state *ts = NULL;
Kevin Bracey4d826602013-05-16 18:32:39 +0300960 int relevant_change = 0, irrelevant_change = 0;
961 int relevant_parents, nth_parent;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800962
Linus Torvalds53b2c822007-11-05 13:22:34 -0800963 /*
964 * If we don't do pruning, everything is interesting
965 */
Linus Torvalds7dc0fe32007-11-12 23:16:08 -0800966 if (!revs->prune)
Linus Torvalds53b2c822007-11-05 13:22:34 -0800967 return;
Linus Torvalds53b2c822007-11-05 13:22:34 -0800968
Derrick Stolee2e27bd72018-04-06 19:09:38 +0000969 if (!get_commit_tree(commit))
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800970 return;
971
972 if (!commit->parents) {
Linus Torvalds3a5e8602008-11-03 10:45:41 -0800973 if (rev_same_tree_as_empty(revs, commit))
Linus Torvalds7dc0fe32007-11-12 23:16:08 -0800974 commit->object.flags |= TREESAME;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800975 return;
976 }
977
Linus Torvalds53b2c822007-11-05 13:22:34 -0800978 /*
979 * Normal non-merge commit? If we don't want to make the
980 * history dense, we consider it always to be a change..
981 */
Linus Torvalds7dc0fe32007-11-12 23:16:08 -0800982 if (!revs->dense && !commit->parents->next)
Linus Torvalds53b2c822007-11-05 13:22:34 -0800983 return;
Linus Torvalds53b2c822007-11-05 13:22:34 -0800984
Kevin Bracey4d826602013-05-16 18:32:39 +0300985 for (pp = &commit->parents, nth_parent = 0, relevant_parents = 0;
Kevin Braceyd0af6632013-05-16 18:32:34 +0300986 (parent = *pp) != NULL;
987 pp = &parent->next, nth_parent++) {
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800988 struct commit *p = parent->item;
Kevin Bracey4d826602013-05-16 18:32:39 +0300989 if (relevant_commit(p))
990 relevant_parents++;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -0800991
Kevin Braceyd0af6632013-05-16 18:32:34 +0300992 if (nth_parent == 1) {
993 /*
994 * This our second loop iteration - so we now know
995 * we're dealing with a merge.
996 *
997 * Do not compare with later parents when we care only about
998 * the first parent chain, in order to avoid derailing the
999 * traversal to follow a side branch that brought everything
1000 * in the path we are limited to by the pathspec.
1001 */
1002 if (revs->first_parent_only)
1003 break;
1004 /*
1005 * If this will remain a potentially-simplifiable
1006 * merge, remember per-parent treesame if needed.
1007 * Initialise the array with the comparison from our
1008 * first iteration.
1009 */
1010 if (revs->treesame.name &&
1011 !revs->simplify_history &&
1012 !(commit->object.flags & UNINTERESTING)) {
1013 ts = initialise_treesame(revs, commit);
Kevin Bracey4d826602013-05-16 18:32:39 +03001014 if (!(irrelevant_change || relevant_change))
Kevin Braceyd0af6632013-05-16 18:32:34 +03001015 ts->treesame[0] = 1;
1016 }
1017 }
Michael Forneyea3f7e52020-06-23 13:56:58 -07001018 if (repo_parse_commit(revs->repo, p) < 0)
Alex Riesencc0e6c52007-05-04 23:54:57 +02001019 die("cannot simplify commit %s (because of %s)",
brian m. carlsonf2fd0762015-11-10 02:22:28 +00001020 oid_to_hex(&commit->object.oid),
1021 oid_to_hex(&p->object.oid));
Garima Singha56b9462020-04-06 16:59:52 +00001022 switch (rev_compare_tree(revs, p, commit, nth_parent)) {
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001023 case REV_TREE_SAME:
Kevin Bracey141efdb2013-05-16 18:32:41 +03001024 if (!revs->simplify_history || !relevant_commit(p)) {
Junio C Hamanof3219fb2006-03-10 21:59:37 -08001025 /* Even if a merge with an uninteresting
1026 * side branch brought the entire change
1027 * we are interested in, we do not want
1028 * to lose the other branches of this
1029 * merge, so we just keep going.
1030 */
Kevin Braceyd0af6632013-05-16 18:32:34 +03001031 if (ts)
1032 ts->treesame[nth_parent] = 1;
Junio C Hamanof3219fb2006-03-10 21:59:37 -08001033 continue;
1034 }
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001035 parent->next = NULL;
1036 commit->parents = parent;
Derrick Stolee8d049e12020-04-10 12:19:43 +00001037
1038 /*
1039 * A merge commit is a "diversion" if it is not
1040 * TREESAME to its first parent but is TREESAME
1041 * to a later parent. In the simplified history,
1042 * we "divert" the history walk to the later
1043 * parent. These commits are shown when "show_pulls"
1044 * is enabled, so do not mark the object as
1045 * TREESAME here.
1046 */
1047 if (!revs->show_pulls || !nth_parent)
1048 commit->object.flags |= TREESAME;
1049
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001050 return;
1051
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001052 case REV_TREE_NEW:
1053 if (revs->remove_empty_trees &&
Linus Torvalds3a5e8602008-11-03 10:45:41 -08001054 rev_same_tree_as_empty(revs, p)) {
Junio C Hamanoc348f312006-03-12 13:39:31 -08001055 /* We are adding all the specified
1056 * paths from this parent, so the
1057 * history beyond this parent is not
1058 * interesting. Remove its parents
1059 * (they are grandparents for us).
1060 * IOW, we pretend this parent is a
1061 * "root" commit.
Junio C Hamanoa41e1092006-03-12 13:39:31 -08001062 */
Michael Forneyea3f7e52020-06-23 13:56:58 -07001063 if (repo_parse_commit(revs->repo, p) < 0)
Alex Riesencc0e6c52007-05-04 23:54:57 +02001064 die("cannot simplify commit %s (invalid %s)",
brian m. carlsonf2fd0762015-11-10 02:22:28 +00001065 oid_to_hex(&commit->object.oid),
1066 oid_to_hex(&p->object.oid));
Junio C Hamanoc348f312006-03-12 13:39:31 -08001067 p->parents = NULL;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001068 }
1069 /* fallthrough */
Linus Torvaldsceff8e72009-06-02 18:34:01 -07001070 case REV_TREE_OLD:
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001071 case REV_TREE_DIFFERENT:
Kevin Bracey4d826602013-05-16 18:32:39 +03001072 if (relevant_commit(p))
1073 relevant_change = 1;
1074 else
1075 irrelevant_change = 1;
Derrick Stolee8d049e12020-04-10 12:19:43 +00001076
1077 if (!nth_parent)
1078 commit->object.flags |= PULL_MERGE;
1079
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001080 continue;
1081 }
brian m. carlsonf2fd0762015-11-10 02:22:28 +00001082 die("bad tree compare for commit %s", oid_to_hex(&commit->object.oid));
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001083 }
Kevin Bracey4d826602013-05-16 18:32:39 +03001084
1085 /*
1086 * TREESAME is straightforward for single-parent commits. For merge
1087 * commits, it is most useful to define it so that "irrelevant"
1088 * parents cannot make us !TREESAME - if we have any relevant
1089 * parents, then we only consider TREESAMEness with respect to them,
1090 * allowing irrelevant merges from uninteresting branches to be
1091 * simplified away. Only if we have only irrelevant parents do we
1092 * base TREESAME on them. Note that this logic is replicated in
1093 * update_treesame, which should be kept in sync.
1094 */
1095 if (relevant_parents ? !relevant_change : !irrelevant_change)
1096 commit->object.flags |= TREESAME;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001097}
1098
Derrick Stolee5284fc52018-11-01 13:46:21 +00001099static int process_parents(struct rev_info *revs, struct commit *commit,
Jeff King8320b1d2019-04-03 21:41:09 -04001100 struct commit_list **list, struct prio_queue *queue)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001101{
1102 struct commit_list *parent = commit->parents;
Junio C Hamano577ed5c2006-10-22 17:32:47 -07001103 unsigned left_flag;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001104
Linus Torvalds3381c792006-04-08 17:05:58 -07001105 if (commit->object.flags & ADDED)
Alex Riesencc0e6c52007-05-04 23:54:57 +02001106 return 0;
Linus Torvalds3381c792006-04-08 17:05:58 -07001107 commit->object.flags |= ADDED;
1108
Vicent Martia330de32013-10-24 14:01:41 -04001109 if (revs->include_check &&
1110 !revs->include_check(commit, revs->include_check_data))
1111 return 0;
1112
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001113 /*
1114 * If the commit is uninteresting, don't try to
1115 * prune parents - we want the maximal uninteresting
1116 * set.
1117 *
1118 * Normally we haven't parsed the parent
1119 * yet, so we won't have a parent of a parent
1120 * here. However, it may turn out that we've
1121 * reached this commit some other way (where it
1122 * wasn't uninteresting), in which case we need
1123 * to mark its parents recursively too..
1124 */
1125 if (commit->object.flags & UNINTERESTING) {
1126 while (parent) {
1127 struct commit *p = parent->item;
1128 parent = parent->next;
Junio C Hamanoaeeae1b2009-01-27 23:19:30 -08001129 if (p)
1130 p->object.flags |= UNINTERESTING;
Michael Forneyea3f7e52020-06-23 13:56:58 -07001131 if (repo_parse_commit_gently(revs->repo, p, 1) < 0)
Junio C Hamanoaeeae1b2009-01-27 23:19:30 -08001132 continue;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001133 if (p->parents)
Jerry Zhang9d505b72022-01-11 13:39:41 -08001134 mark_parents_uninteresting(revs, p);
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001135 if (p->object.flags & SEEN)
1136 continue;
Patrick Steinhardtb2025da2021-04-09 13:27:57 +02001137 p->object.flags |= (SEEN | NOT_USER_GIVEN);
Derrick Stolee5284fc52018-11-01 13:46:21 +00001138 if (list)
Jeff King8320b1d2019-04-03 21:41:09 -04001139 commit_list_insert_by_date(p, list);
1140 if (queue)
1141 prio_queue_put(queue, p);
Jerry Zhang9d505b72022-01-11 13:39:41 -08001142 if (revs->exclude_first_parent_only)
1143 break;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001144 }
Alex Riesencc0e6c52007-05-04 23:54:57 +02001145 return 0;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001146 }
1147
1148 /*
1149 * Ok, the commit wasn't uninteresting. Try to
1150 * simplify the commit history and find the parent
1151 * that has no differences in the path set if one exists.
1152 */
Linus Torvalds53b2c822007-11-05 13:22:34 -08001153 try_to_simplify_commit(revs, commit);
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001154
Linus Torvaldsba1d4502006-04-15 12:09:56 -07001155 if (revs->no_walk)
Alex Riesencc0e6c52007-05-04 23:54:57 +02001156 return 0;
Linus Torvaldsba1d4502006-04-15 12:09:56 -07001157
Junio C Hamano577ed5c2006-10-22 17:32:47 -07001158 left_flag = (commit->object.flags & SYMMETRIC_LEFT);
Junio C Hamano0053e902007-03-13 01:57:22 -07001159
Stephen R. van den Bergd9c292e2008-04-27 19:32:46 +02001160 for (parent = commit->parents; parent; parent = parent->next) {
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001161 struct commit *p = parent->item;
Jonathan Tandf11e192017-12-08 15:27:15 +00001162 int gently = revs->ignore_missing_links ||
1163 revs->exclude_promisor_objects;
Michael Forneyea3f7e52020-06-23 13:56:58 -07001164 if (repo_parse_commit_gently(revs->repo, p, gently) < 0) {
Jonathan Tandf11e192017-12-08 15:27:15 +00001165 if (revs->exclude_promisor_objects &&
1166 is_promisor_object(&p->object.oid)) {
1167 if (revs->first_parent_only)
1168 break;
1169 continue;
1170 }
Alex Riesencc0e6c52007-05-04 23:54:57 +02001171 return -1;
Jonathan Tandf11e192017-12-08 15:27:15 +00001172 }
Nguyễn Thái Ngọc Duy87be2522018-05-19 07:28:24 +02001173 if (revs->sources) {
1174 char **slot = revision_sources_at(revs->sources, p);
1175
1176 if (!*slot)
1177 *slot = *revision_sources_at(revs->sources, commit);
1178 }
Junio C Hamano577ed5c2006-10-22 17:32:47 -07001179 p->object.flags |= left_flag;
Lars Hjemliad1012e2008-05-12 17:12:36 +02001180 if (!(p->object.flags & SEEN)) {
Patrick Steinhardtb2025da2021-04-09 13:27:57 +02001181 p->object.flags |= (SEEN | NOT_USER_GIVEN);
Derrick Stolee5284fc52018-11-01 13:46:21 +00001182 if (list)
Jeff King8320b1d2019-04-03 21:41:09 -04001183 commit_list_insert_by_date(p, list);
1184 if (queue)
1185 prio_queue_put(queue, p);
Lars Hjemliad1012e2008-05-12 17:12:36 +02001186 }
Junio C Hamano60d30b02008-07-31 22:17:13 -07001187 if (revs->first_parent_only)
Stephen R. van den Bergd9c292e2008-04-27 19:32:46 +02001188 break;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001189 }
Alex Riesencc0e6c52007-05-04 23:54:57 +02001190 return 0;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001191}
1192
Johannes Schindelin36d56de2007-07-10 14:50:49 +01001193static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001194{
1195 struct commit_list *p;
1196 int left_count = 0, right_count = 0;
1197 int left_first;
1198 struct patch_ids ids;
Michael J Gruberadbbb312011-03-07 13:31:40 +01001199 unsigned cherry_flag;
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001200
1201 /* First count the commits on the left and on the right */
1202 for (p = list; p; p = p->next) {
1203 struct commit *commit = p->item;
1204 unsigned flags = commit->object.flags;
1205 if (flags & BOUNDARY)
1206 ;
1207 else if (flags & SYMMETRIC_LEFT)
1208 left_count++;
1209 else
1210 right_count++;
1211 }
1212
Thomas Rast36c07972010-02-20 12:42:04 +01001213 if (!left_count || !right_count)
1214 return;
1215
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001216 left_first = left_count < right_count;
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001217 init_patch_ids(revs->repo, &ids);
Nguyễn Thái Ngọc Duy66f13622010-12-15 22:02:38 +07001218 ids.diffopts.pathspec = revs->diffopt.pathspec;
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001219
1220 /* Compute patch-ids for one side */
1221 for (p = list; p; p = p->next) {
1222 struct commit *commit = p->item;
1223 unsigned flags = commit->object.flags;
1224
1225 if (flags & BOUNDARY)
1226 continue;
1227 /*
1228 * If we have fewer left, left_first is set and we omit
1229 * commits on the right branch in this loop. If we have
1230 * fewer right, we skip the left ones.
1231 */
1232 if (left_first != !!(flags & SYMMETRIC_LEFT))
1233 continue;
Kevin Willford683f17e2016-07-29 12:19:18 -04001234 add_commit_patch_id(commit, &ids);
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001235 }
1236
Michael J Gruberadbbb312011-03-07 13:31:40 +01001237 /* either cherry_mark or cherry_pick are true */
1238 cherry_flag = revs->cherry_mark ? PATCHSAME : SHOWN;
1239
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001240 /* Check the other side */
1241 for (p = list; p; p = p->next) {
1242 struct commit *commit = p->item;
1243 struct patch_id *id;
1244 unsigned flags = commit->object.flags;
1245
1246 if (flags & BOUNDARY)
1247 continue;
1248 /*
1249 * If we have fewer left, left_first is set and we omit
1250 * commits on the left branch in this loop.
1251 */
1252 if (left_first == !!(flags & SYMMETRIC_LEFT))
1253 continue;
1254
1255 /*
1256 * Have we seen the same patch id?
1257 */
Jeff Kingc9e3a4e2021-01-12 10:52:32 -05001258 id = patch_id_iter_first(commit, &ids);
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001259 if (!id)
1260 continue;
Kevin Willford683f17e2016-07-29 12:19:18 -04001261
Michael J Gruberadbbb312011-03-07 13:31:40 +01001262 commit->object.flags |= cherry_flag;
Jeff Kingc9e3a4e2021-01-12 10:52:32 -05001263 do {
1264 id->commit->object.flags |= cherry_flag;
1265 } while ((id = patch_id_iter_next(id, &ids)));
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001266 }
1267
1268 free_patch_ids(&ids);
1269}
1270
Linus Torvalds7d004192008-03-17 18:56:33 -07001271/* How many extra uninteresting commits we want to see.. */
1272#define SLOP 5
1273
Johannes Schindelindddbad72017-04-26 21:29:31 +02001274static int still_interesting(struct commit_list *src, timestamp_t date, int slop,
Jeff Kingb6e8a3b2015-04-17 18:11:04 -04001275 struct commit **interesting_cache)
Linus Torvalds3131b712008-02-09 14:02:07 -08001276{
Linus Torvalds7d004192008-03-17 18:56:33 -07001277 /*
1278 * No source list at all? We're definitely done..
1279 */
1280 if (!src)
1281 return 0;
1282
1283 /*
1284 * Does the destination list contain entries with a date
1285 * before the source list? Definitely _not_ done.
1286 */
Kacper Kornetc19d1b42013-03-22 19:38:19 +01001287 if (date <= src->item->date)
Linus Torvalds7d004192008-03-17 18:56:33 -07001288 return SLOP;
1289
1290 /*
1291 * Does the source list still have interesting commits in
1292 * it? Definitely not done..
1293 */
Jeff Kingb6e8a3b2015-04-17 18:11:04 -04001294 if (!everybody_uninteresting(src, interesting_cache))
Linus Torvalds7d004192008-03-17 18:56:33 -07001295 return SLOP;
1296
1297 /* Ok, we're closing in.. */
1298 return slop-1;
Linus Torvalds3131b712008-02-09 14:02:07 -08001299}
1300
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001301/*
1302 * "rev-list --ancestry-path A..B" computes commits that are ancestors
1303 * of B but not ancestors of A but further limits the result to those
1304 * that are descendants of A. This takes the list of bottom commits and
1305 * the result of "A..B" without --ancestry-path, and limits the latter
1306 * further to the ones that can reach one of the commits in "bottom".
1307 */
1308static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list)
1309{
1310 struct commit_list *p;
1311 struct commit_list *rlist = NULL;
1312 int made_progress;
1313
1314 /*
1315 * Reverse the list so that it will be likely that we would
1316 * process parents before children.
1317 */
1318 for (p = list; p; p = p->next)
1319 commit_list_insert(p->item, &rlist);
1320
1321 for (p = bottom; p; p = p->next)
1322 p->item->object.flags |= TMP_MARK;
1323
1324 /*
1325 * Mark the ones that can reach bottom commits in "list",
1326 * in a bottom-up fashion.
1327 */
1328 do {
1329 made_progress = 0;
1330 for (p = rlist; p; p = p->next) {
1331 struct commit *c = p->item;
1332 struct commit_list *parents;
1333 if (c->object.flags & (TMP_MARK | UNINTERESTING))
1334 continue;
1335 for (parents = c->parents;
1336 parents;
1337 parents = parents->next) {
1338 if (!(parents->item->object.flags & TMP_MARK))
1339 continue;
1340 c->object.flags |= TMP_MARK;
1341 made_progress = 1;
1342 break;
1343 }
1344 }
1345 } while (made_progress);
1346
1347 /*
1348 * NEEDSWORK: decide if we want to remove parents that are
1349 * not marked with TMP_MARK from commit->parents for commits
1350 * in the resulting list. We may not want to do that, though.
1351 */
1352
1353 /*
1354 * The ones that are not marked with TMP_MARK are uninteresting
1355 */
1356 for (p = list; p; p = p->next) {
1357 struct commit *c = p->item;
1358 if (c->object.flags & TMP_MARK)
1359 continue;
1360 c->object.flags |= UNINTERESTING;
1361 }
1362
1363 /* We are done with the TMP_MARK */
1364 for (p = list; p; p = p->next)
1365 p->item->object.flags &= ~TMP_MARK;
1366 for (p = bottom; p; p = p->next)
1367 p->item->object.flags &= ~TMP_MARK;
1368 free_commit_list(rlist);
1369}
1370
1371/*
1372 * Before walking the history, keep the set of "negative" refs the
1373 * caller has asked to exclude.
1374 *
1375 * This is used to compute "rev-list --ancestry-path A..B", as we need
1376 * to filter the result of "A..B" further to the ones that can actually
1377 * reach A.
1378 */
Kevin Bracey7f34a462013-05-16 18:32:38 +03001379static struct commit_list *collect_bottom_commits(struct commit_list *list)
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001380{
Kevin Bracey7f34a462013-05-16 18:32:38 +03001381 struct commit_list *elem, *bottom = NULL;
1382 for (elem = list; elem; elem = elem->next)
1383 if (elem->item->object.flags & BOTTOM)
1384 commit_list_insert(elem->item, &bottom);
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001385 return bottom;
1386}
1387
Michael J Gruber60adf7d2011-02-21 17:09:11 +01001388/* Assumes either left_only or right_only is set */
1389static void limit_left_right(struct commit_list *list, struct rev_info *revs)
1390{
1391 struct commit_list *p;
1392
1393 for (p = list; p; p = p->next) {
1394 struct commit *commit = p->item;
1395
1396 if (revs->right_only) {
1397 if (commit->object.flags & SYMMETRIC_LEFT)
1398 commit->object.flags |= SHOWN;
1399 } else /* revs->left_only is set */
1400 if (!(commit->object.flags & SYMMETRIC_LEFT))
1401 commit->object.flags |= SHOWN;
1402 }
1403}
1404
Alex Riesencc0e6c52007-05-04 23:54:57 +02001405static int limit_list(struct rev_info *revs)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001406{
Linus Torvalds7d004192008-03-17 18:56:33 -07001407 int slop = SLOP;
Johannes Schindelindddbad72017-04-26 21:29:31 +02001408 timestamp_t date = TIME_MAX;
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001409 struct commit_list *original_list = revs->commits;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001410 struct commit_list *newlist = NULL;
1411 struct commit_list **p = &newlist;
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001412 struct commit_list *bottom = NULL;
Jeff Kingb6e8a3b2015-04-17 18:11:04 -04001413 struct commit *interesting_cache = NULL;
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001414
1415 if (revs->ancestry_path) {
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001416 bottom = collect_bottom_commits(original_list);
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001417 if (!bottom)
Johan Herland97b03c32010-06-04 01:17:36 +02001418 die("--ancestry-path given but there are no bottom commits");
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001419 }
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001420
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001421 while (original_list) {
1422 struct commit *commit = pop_commit(&original_list);
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001423 struct object *obj = &commit->object;
Linus Torvaldscdcefbc2007-11-03 11:11:10 -07001424 show_early_output_fn_t show;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001425
Jeff Kingb6e8a3b2015-04-17 18:11:04 -04001426 if (commit == interesting_cache)
1427 interesting_cache = NULL;
1428
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001429 if (revs->max_age != -1 && (commit->date < revs->max_age))
1430 obj->flags |= UNINTERESTING;
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001431 if (process_parents(revs, commit, &original_list, NULL) < 0)
Alex Riesencc0e6c52007-05-04 23:54:57 +02001432 return -1;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001433 if (obj->flags & UNINTERESTING) {
Jerry Zhang9d505b72022-01-11 13:39:41 -08001434 mark_parents_uninteresting(revs, commit);
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001435 slop = still_interesting(original_list, date, slop, &interesting_cache);
Linus Torvalds7d004192008-03-17 18:56:33 -07001436 if (slop)
Linus Torvalds3131b712008-02-09 14:02:07 -08001437 continue;
Linus Torvalds7d004192008-03-17 18:56:33 -07001438 break;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001439 }
René Scharfe01faa912020-07-04 14:56:32 +02001440 if (revs->min_age != -1 && (commit->date > revs->min_age) &&
1441 !revs->line_level_traverse)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001442 continue;
Linus Torvalds7d004192008-03-17 18:56:33 -07001443 date = commit->date;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001444 p = &commit_list_insert(commit, p)->next;
Linus Torvaldscdcefbc2007-11-03 11:11:10 -07001445
1446 show = show_early_output;
1447 if (!show)
1448 continue;
1449
1450 show(revs, newlist);
1451 show_early_output = NULL;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001452 }
Michael J Gruberadbbb312011-03-07 13:31:40 +01001453 if (revs->cherry_pick || revs->cherry_mark)
Johannes Schindelin36d56de2007-07-10 14:50:49 +01001454 cherry_pick_list(newlist, revs);
Junio C Hamanod7a17ca2007-04-09 03:40:38 -07001455
Michael J Gruber60adf7d2011-02-21 17:09:11 +01001456 if (revs->left_only || revs->right_only)
1457 limit_left_right(newlist, revs);
1458
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07001459 if (bottom) {
1460 limit_to_ancestry(bottom, newlist);
1461 free_commit_list(bottom);
1462 }
1463
Kevin Bracey4d826602013-05-16 18:32:39 +03001464 /*
1465 * Check if any commits have become TREESAME by some of their parents
1466 * becoming UNINTERESTING.
1467 */
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001468 if (limiting_can_increase_treesame(revs)) {
1469 struct commit_list *list = NULL;
Kevin Bracey4d826602013-05-16 18:32:39 +03001470 for (list = newlist; list; list = list->next) {
1471 struct commit *c = list->item;
1472 if (c->object.flags & (UNINTERESTING | TREESAME))
1473 continue;
1474 update_treesame(revs, c);
1475 }
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001476 }
Kevin Bracey4d826602013-05-16 18:32:39 +03001477
Andrzej Huntdb69bf62021-04-25 14:16:08 +00001478 free_commit_list(original_list);
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001479 revs->commits = newlist;
Alex Riesencc0e6c52007-05-04 23:54:57 +02001480 return 0;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08001481}
1482
Michael Haggertydf835d32013-05-25 11:08:02 +02001483/*
1484 * Add an entry to refs->cmdline with the specified information.
1485 * *name is copied.
1486 */
Junio C Hamano281eee42011-08-25 17:35:39 -07001487static void add_rev_cmdline(struct rev_info *revs,
1488 struct object *item,
1489 const char *name,
1490 int whence,
1491 unsigned flags)
1492{
1493 struct rev_cmdline_info *info = &revs->cmdline;
Ramsay Jones071bcaa2017-09-21 17:49:38 +01001494 unsigned int nr = info->nr;
Junio C Hamano281eee42011-08-25 17:35:39 -07001495
1496 ALLOC_GROW(info->rev, nr + 1, info->alloc);
1497 info->rev[nr].item = item;
Michael Haggertydf835d32013-05-25 11:08:02 +02001498 info->rev[nr].name = xstrdup(name);
Junio C Hamano281eee42011-08-25 17:35:39 -07001499 info->rev[nr].whence = whence;
1500 info->rev[nr].flags = flags;
1501 info->nr++;
1502}
1503
Kevin Braceya7654992013-05-13 18:00:47 +03001504static void add_rev_cmdline_list(struct rev_info *revs,
1505 struct commit_list *commit_list,
1506 int whence,
1507 unsigned flags)
1508{
1509 while (commit_list) {
1510 struct object *object = &commit_list->item->object;
brian m. carlsonf2fd0762015-11-10 02:22:28 +00001511 add_rev_cmdline(revs, object, oid_to_hex(&object->oid),
Kevin Braceya7654992013-05-13 18:00:47 +03001512 whence, flags);
1513 commit_list = commit_list->next;
1514 }
1515}
1516
Junio C Hamano63049292006-12-18 17:25:28 -08001517struct all_refs_cb {
1518 int all_flags;
Shawn O. Pearce71b03b42006-12-21 19:49:06 -05001519 int warned_bad_reflog;
Junio C Hamano63049292006-12-18 17:25:28 -08001520 struct rev_info *all_revs;
1521 const char *name_for_errormsg;
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001522 struct worktree *wt;
Junio C Hamano63049292006-12-18 17:25:28 -08001523};
Linus Torvaldsae563542006-02-25 16:19:46 -08001524
Junio C Hamanoff32d342013-11-01 12:02:45 -07001525int ref_excluded(struct string_list *ref_excludes, const char *path)
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001526{
1527 struct string_list_item *item;
1528
Junio C Hamanoff32d342013-11-01 12:02:45 -07001529 if (!ref_excludes)
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001530 return 0;
Junio C Hamanoff32d342013-11-01 12:02:45 -07001531 for_each_string_list_item(item, ref_excludes) {
Ævar Arnfjörð Bjarmason55d34262017-06-22 21:38:08 +00001532 if (!wildmatch(item->string, path, 0))
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001533 return 1;
1534 }
1535 return 0;
1536}
1537
Michael Haggertya217dcb2015-05-25 18:38:30 +00001538static int handle_one_ref(const char *path, const struct object_id *oid,
1539 int flag, void *cb_data)
Linus Torvaldsae563542006-02-25 16:19:46 -08001540{
Junio C Hamano63049292006-12-18 17:25:28 -08001541 struct all_refs_cb *cb = cb_data;
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001542 struct object *object;
1543
Junio C Hamanoff32d342013-11-01 12:02:45 -07001544 if (ref_excluded(cb->all_revs->ref_excludes, path))
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001545 return 0;
1546
brian m. carlson654b9a92017-05-06 22:10:27 +00001547 object = get_reference(cb->all_revs, path, oid, cb->all_flags);
Junio C Hamano281eee42011-08-25 17:35:39 -07001548 add_rev_cmdline(cb->all_revs, object, path, REV_CMD_REF, cb->all_flags);
Patrick Steinhardtbf9c0cb2021-08-09 10:11:54 +02001549 add_pending_object(cb->all_revs, object, path);
Linus Torvaldsae563542006-02-25 16:19:46 -08001550 return 0;
1551}
1552
Ilari Liusvaarad08bae72010-01-20 11:48:25 +02001553static void init_all_refs_cb(struct all_refs_cb *cb, struct rev_info *revs,
1554 unsigned flags)
1555{
1556 cb->all_revs = revs;
1557 cb->all_flags = flags;
Jeff King7ba82622017-08-02 18:25:27 -04001558 revs->rev_input_given = 1;
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001559 cb->wt = NULL;
Ilari Liusvaarad08bae72010-01-20 11:48:25 +02001560}
1561
Junio C Hamanoff32d342013-11-01 12:02:45 -07001562void clear_ref_exclusion(struct string_list **ref_excludes_p)
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001563{
Junio C Hamanoff32d342013-11-01 12:02:45 -07001564 if (*ref_excludes_p) {
1565 string_list_clear(*ref_excludes_p, 0);
1566 free(*ref_excludes_p);
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001567 }
Junio C Hamanoff32d342013-11-01 12:02:45 -07001568 *ref_excludes_p = NULL;
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001569}
1570
Junio C Hamanoff32d342013-11-01 12:02:45 -07001571void add_ref_exclusion(struct string_list **ref_excludes_p, const char *exclude)
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001572{
Junio C Hamanoff32d342013-11-01 12:02:45 -07001573 if (!*ref_excludes_p) {
René Scharfeca56dad2021-03-13 17:17:22 +01001574 CALLOC_ARRAY(*ref_excludes_p, 1);
Junio C Hamanoff32d342013-11-01 12:02:45 -07001575 (*ref_excludes_p)->strdup_strings = 1;
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001576 }
Junio C Hamanoff32d342013-11-01 12:02:45 -07001577 string_list_append(*ref_excludes_p, exclude);
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07001578}
1579
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07001580static void handle_refs(struct ref_store *refs,
1581 struct rev_info *revs, unsigned flags,
1582 int (*for_each)(struct ref_store *, each_ref_fn, void *))
Linus Torvaldsae563542006-02-25 16:19:46 -08001583{
Junio C Hamano63049292006-12-18 17:25:28 -08001584 struct all_refs_cb cb;
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07001585
1586 if (!refs) {
1587 /* this could happen with uninitialized submodules */
1588 return;
1589 }
1590
Ilari Liusvaarad08bae72010-01-20 11:48:25 +02001591 init_all_refs_cb(&cb, revs, flags);
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07001592 for_each(refs, handle_one_ref, &cb);
Junio C Hamano63049292006-12-18 17:25:28 -08001593}
1594
brian m. carlson9461d272017-02-21 23:47:32 +00001595static void handle_one_reflog_commit(struct object_id *oid, void *cb_data)
Junio C Hamano63049292006-12-18 17:25:28 -08001596{
1597 struct all_refs_cb *cb = cb_data;
brian m. carlson9461d272017-02-21 23:47:32 +00001598 if (!is_null_oid(oid)) {
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02001599 struct object *o = parse_object(cb->all_revs->repo, oid);
Shawn O. Pearce71b03b42006-12-21 19:49:06 -05001600 if (o) {
1601 o->flags |= cb->all_flags;
Junio C Hamano281eee42011-08-25 17:35:39 -07001602 /* ??? CMDLINEFLAGS ??? */
Shawn O. Pearce71b03b42006-12-21 19:49:06 -05001603 add_pending_object(cb->all_revs, o, "");
1604 }
1605 else if (!cb->warned_bad_reflog) {
Theodore Ts'o46efd2d2007-03-30 19:07:05 -04001606 warning("reflog of '%s' references pruned commits",
Shawn O. Pearce71b03b42006-12-21 19:49:06 -05001607 cb->name_for_errormsg);
1608 cb->warned_bad_reflog = 1;
1609 }
Junio C Hamano63049292006-12-18 17:25:28 -08001610 }
Shawn O. Pearce71b03b42006-12-21 19:49:06 -05001611}
1612
brian m. carlson9461d272017-02-21 23:47:32 +00001613static int handle_one_reflog_ent(struct object_id *ooid, struct object_id *noid,
Johannes Schindelindddbad72017-04-26 21:29:31 +02001614 const char *email, timestamp_t timestamp, int tz,
Johannes Schindelin883d60f2007-01-08 01:59:54 +01001615 const char *message, void *cb_data)
Shawn O. Pearce71b03b42006-12-21 19:49:06 -05001616{
brian m. carlson9461d272017-02-21 23:47:32 +00001617 handle_one_reflog_commit(ooid, cb_data);
1618 handle_one_reflog_commit(noid, cb_data);
Junio C Hamano63049292006-12-18 17:25:28 -08001619 return 0;
1620}
1621
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001622static int handle_one_reflog(const char *refname_in_wt,
Nguyễn Thái Ngọc Duy061e4202018-10-21 10:08:55 +02001623 const struct object_id *oid,
Michael Haggertya89caf42015-05-25 18:39:03 +00001624 int flag, void *cb_data)
Junio C Hamano63049292006-12-18 17:25:28 -08001625{
1626 struct all_refs_cb *cb = cb_data;
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001627 struct strbuf refname = STRBUF_INIT;
1628
Shawn O. Pearce71b03b42006-12-21 19:49:06 -05001629 cb->warned_bad_reflog = 0;
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001630 strbuf_worktree_ref(cb->wt, &refname, refname_in_wt);
1631 cb->name_for_errormsg = refname.buf;
1632 refs_for_each_reflog_ent(get_main_ref_store(the_repository),
1633 refname.buf,
Nguyễn Thái Ngọc Duyacd95442017-08-23 19:37:01 +07001634 handle_one_reflog_ent, cb_data);
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001635 strbuf_release(&refname);
Junio C Hamano63049292006-12-18 17:25:28 -08001636 return 0;
1637}
1638
Nguyễn Thái Ngọc Duyacd95442017-08-23 19:37:01 +07001639static void add_other_reflogs_to_pending(struct all_refs_cb *cb)
1640{
1641 struct worktree **worktrees, **p;
1642
Eric Sunshine03f24652020-06-19 19:35:44 -04001643 worktrees = get_worktrees();
Nguyễn Thái Ngọc Duyacd95442017-08-23 19:37:01 +07001644 for (p = worktrees; *p; p++) {
1645 struct worktree *wt = *p;
1646
1647 if (wt->is_current)
1648 continue;
1649
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001650 cb->wt = wt;
1651 refs_for_each_reflog(get_worktree_ref_store(wt),
Nguyễn Thái Ngọc Duyacd95442017-08-23 19:37:01 +07001652 handle_one_reflog,
1653 cb);
1654 }
1655 free_worktrees(worktrees);
1656}
1657
Jeff King718ccc92014-10-15 18:38:31 -04001658void add_reflogs_to_pending(struct rev_info *revs, unsigned flags)
Junio C Hamano63049292006-12-18 17:25:28 -08001659{
1660 struct all_refs_cb cb;
Michael Haggerty2b2a5be2015-05-25 18:38:28 +00001661
Junio C Hamano63049292006-12-18 17:25:28 -08001662 cb.all_revs = revs;
1663 cb.all_flags = flags;
Nguyễn Thái Ngọc Duyab3e1f72018-10-21 10:08:56 +02001664 cb.wt = NULL;
Michael Haggertya89caf42015-05-25 18:39:03 +00001665 for_each_reflog(handle_one_reflog, &cb);
Nguyễn Thái Ngọc Duyacd95442017-08-23 19:37:01 +07001666
1667 if (!revs->single_worktree)
1668 add_other_reflogs_to_pending(&cb);
Linus Torvaldsae563542006-02-25 16:19:46 -08001669}
1670
Jeff King4fe10212014-10-16 20:44:23 -04001671static void add_cache_tree(struct cache_tree *it, struct rev_info *revs,
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001672 struct strbuf *path, unsigned int flags)
Jeff King4fe10212014-10-16 20:44:23 -04001673{
1674 size_t baselen = path->len;
1675 int i;
1676
1677 if (it->entry_count >= 0) {
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02001678 struct tree *tree = lookup_tree(revs->repo, &it->oid);
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001679 tree->object.flags |= flags;
Jeff King4fe10212014-10-16 20:44:23 -04001680 add_pending_object_with_path(revs, &tree->object, "",
1681 040000, path->buf);
1682 }
1683
1684 for (i = 0; i < it->subtree_nr; i++) {
1685 struct cache_tree_sub *sub = it->down[i];
1686 strbuf_addf(path, "%s%s", baselen ? "/" : "", sub->name);
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001687 add_cache_tree(sub->cache_tree, revs, path, flags);
Jeff King4fe10212014-10-16 20:44:23 -04001688 strbuf_setlen(path, baselen);
1689 }
1690
1691}
1692
Nguyễn Thái Ngọc Duy6c3d8182017-08-23 19:36:51 +07001693static void do_add_index_objects_to_pending(struct rev_info *revs,
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001694 struct index_state *istate,
1695 unsigned int flags)
Jeff King4fe10212014-10-16 20:44:23 -04001696{
1697 int i;
1698
Derrick Stoleef5fed742021-04-01 01:50:00 +00001699 /* TODO: audit for interaction with sparse-index. */
1700 ensure_full_index(istate);
Nguyễn Thái Ngọc Duy6c3d8182017-08-23 19:36:51 +07001701 for (i = 0; i < istate->cache_nr; i++) {
1702 struct cache_entry *ce = istate->cache[i];
Jeff King4fe10212014-10-16 20:44:23 -04001703 struct blob *blob;
1704
1705 if (S_ISGITLINK(ce->ce_mode))
1706 continue;
1707
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02001708 blob = lookup_blob(revs->repo, &ce->oid);
Jeff King4fe10212014-10-16 20:44:23 -04001709 if (!blob)
1710 die("unable to add index blob to traversal");
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001711 blob->object.flags |= flags;
Jeff King4fe10212014-10-16 20:44:23 -04001712 add_pending_object_with_path(revs, &blob->object, "",
1713 ce->ce_mode, ce->name);
1714 }
1715
Nguyễn Thái Ngọc Duy6c3d8182017-08-23 19:36:51 +07001716 if (istate->cache_tree) {
Jeff King4fe10212014-10-16 20:44:23 -04001717 struct strbuf path = STRBUF_INIT;
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001718 add_cache_tree(istate->cache_tree, revs, &path, flags);
Jeff King4fe10212014-10-16 20:44:23 -04001719 strbuf_release(&path);
1720 }
1721}
1722
Nguyễn Thái Ngọc Duy6c3d8182017-08-23 19:36:51 +07001723void add_index_objects_to_pending(struct rev_info *revs, unsigned int flags)
1724{
Nguyễn Thái Ngọc Duybe489d02017-08-23 19:36:52 +07001725 struct worktree **worktrees, **p;
1726
Nguyễn Thái Ngọc Duye1ff0a32019-01-12 09:13:26 +07001727 repo_read_index(revs->repo);
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001728 do_add_index_objects_to_pending(revs, revs->repo->index, flags);
Nguyễn Thái Ngọc Duybe489d02017-08-23 19:36:52 +07001729
1730 if (revs->single_worktree)
1731 return;
1732
Eric Sunshine03f24652020-06-19 19:35:44 -04001733 worktrees = get_worktrees();
Nguyễn Thái Ngọc Duybe489d02017-08-23 19:36:52 +07001734 for (p = worktrees; *p; p++) {
1735 struct worktree *wt = *p;
1736 struct index_state istate = { NULL };
1737
1738 if (wt->is_current)
1739 continue; /* current index already taken care of */
1740
1741 if (read_index_from(&istate,
Thomas Gummerera125a222018-01-07 22:30:13 +00001742 worktree_git_path(wt, "index"),
1743 get_worktree_git_dir(wt)) > 0)
Jeff Kingb4cfcde2018-11-02 01:22:59 -04001744 do_add_index_objects_to_pending(revs, &istate, flags);
Nguyễn Thái Ngọc Duybe489d02017-08-23 19:36:52 +07001745 discard_index(&istate);
1746 }
1747 free_worktrees(worktrees);
Nguyễn Thái Ngọc Duy6c3d8182017-08-23 19:36:51 +07001748}
1749
Jeff King39b44ba2019-07-01 09:18:15 -04001750struct add_alternate_refs_data {
1751 struct rev_info *revs;
1752 unsigned int flags;
1753};
1754
1755static void add_one_alternate_ref(const struct object_id *oid,
1756 void *vdata)
1757{
1758 const char *name = ".alternate";
1759 struct add_alternate_refs_data *data = vdata;
1760 struct object *obj;
1761
1762 obj = get_reference(data->revs, name, oid, data->flags);
1763 add_rev_cmdline(data->revs, obj, name, REV_CMD_REV, data->flags);
1764 add_pending_object(data->revs, obj, name);
1765}
1766
1767static void add_alternate_refs_to_pending(struct rev_info *revs,
1768 unsigned int flags)
1769{
1770 struct add_alternate_refs_data data;
1771 data.revs = revs;
1772 data.flags = flags;
1773 for_each_alternate_ref(add_one_alternate_ref, &data);
1774}
1775
Vegard Nossum87793512016-09-27 10:32:49 +02001776static int add_parents_only(struct rev_info *revs, const char *arg_, int flags,
1777 int exclude_parent)
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001778{
brian m. carlson654b9a92017-05-06 22:10:27 +00001779 struct object_id oid;
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001780 struct object *it;
1781 struct commit *commit;
1782 struct commit_list *parents;
Vegard Nossum87793512016-09-27 10:32:49 +02001783 int parent_number;
Junio C Hamano281eee42011-08-25 17:35:39 -07001784 const char *arg = arg_;
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001785
1786 if (*arg == '^') {
Kevin Bracey7f34a462013-05-16 18:32:38 +03001787 flags ^= UNINTERESTING | BOTTOM;
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001788 arg++;
1789 }
brian m. carlsone82caf32017-07-13 23:49:28 +00001790 if (get_oid_committish(arg, &oid))
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001791 return 0;
1792 while (1) {
brian m. carlson654b9a92017-05-06 22:10:27 +00001793 it = get_reference(revs, arg, &oid, 0);
Junio C Hamanocc243c32011-05-18 18:08:09 -07001794 if (!it && revs->ignore_missing)
1795 return 0;
Linus Torvalds19746322006-07-11 20:45:31 -07001796 if (it->type != OBJ_TAG)
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001797 break;
Martin Koegler9684afd2008-02-18 21:48:01 +01001798 if (!((struct tag*)it)->tagged)
1799 return 0;
brian m. carlson654b9a92017-05-06 22:10:27 +00001800 oidcpy(&oid, &((struct tag*)it)->tagged->oid);
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001801 }
Linus Torvalds19746322006-07-11 20:45:31 -07001802 if (it->type != OBJ_COMMIT)
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001803 return 0;
1804 commit = (struct commit *)it;
Vegard Nossum87793512016-09-27 10:32:49 +02001805 if (exclude_parent &&
1806 exclude_parent > commit_list_count(commit->parents))
1807 return 0;
1808 for (parents = commit->parents, parent_number = 1;
1809 parents;
1810 parents = parents->next, parent_number++) {
1811 if (exclude_parent && parent_number != exclude_parent)
1812 continue;
1813
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001814 it = &parents->item->object;
1815 it->flags |= flags;
Junio C Hamano281eee42011-08-25 17:35:39 -07001816 add_rev_cmdline(revs, it, arg_, REV_CMD_PARENTS_ONLY, flags);
Junio C Hamanoea4a19e2006-04-30 00:54:29 -07001817 add_pending_object(revs, it, arg);
1818 }
1819 return 1;
1820}
1821
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001822void repo_init_revisions(struct repository *r,
1823 struct rev_info *revs,
1824 const char *prefix)
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001825{
1826 memset(revs, 0, sizeof(*revs));
Junio C Hamano8e8f9982006-04-14 22:19:38 -07001827
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001828 revs->repo = r;
Junio C Hamano6b9c58f2006-04-15 23:46:36 -07001829 revs->abbrev = DEFAULT_ABBREV;
Linus Torvalds92024342006-06-11 10:57:35 -07001830 revs->simplify_history = 1;
Nguyễn Thái Ngọc Duy67022e02018-11-18 17:47:57 +01001831 revs->pruning.repo = r;
Brandon Williams0d1e0e72017-10-31 11:19:11 -07001832 revs->pruning.flags.recursive = 1;
1833 revs->pruning.flags.quick = 1;
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07001834 revs->pruning.add_remove = file_add_remove;
1835 revs->pruning.change = file_change;
Jeff Kinga937b372017-10-13 11:27:45 -04001836 revs->pruning.change_fn_data = revs;
Junio C Hamano08f704f2013-06-06 16:07:14 -07001837 revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001838 revs->dense = 1;
Linus Torvaldsdb6296a2006-07-28 21:21:48 -07001839 revs->prefix = prefix;
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001840 revs->max_age = -1;
1841 revs->min_age = -1;
Junio C Hamanod5db6c92006-12-19 18:25:32 -08001842 revs->skip_count = -1;
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001843 revs->max_count = -1;
Michael J Gruberad5aeed2011-03-21 11:14:06 +01001844 revs->max_parents = -1;
Junio C Hamano0893eec2016-03-29 15:49:24 -07001845 revs->expand_tabs_in_log = -1;
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001846
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07001847 revs->commit_format = CMIT_FMT_DEFAULT;
Junio C Hamanofe37a9c2016-03-29 16:05:39 -07001848 revs->expand_tabs_in_log_default = 8;
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07001849
Ævar Arnfjörð Bjarmason9725c8d2022-02-16 01:00:34 +01001850 grep_init(&revs->grep_filter, revs->repo);
Jeff King0843acf2008-08-25 02:15:05 -04001851 revs->grep_filter.status_only = 1;
Jeff King0843acf2008-08-25 02:15:05 -04001852
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001853 repo_diff_setup(revs->repo, &revs->diffopt);
Junio C Hamanoc0cb4a02008-02-13 00:34:39 -08001854 if (prefix && !revs->diffopt.prefix) {
Junio C Hamanocd676a52008-02-12 14:26:02 -08001855 revs->diffopt.prefix = prefix;
1856 revs->diffopt.prefix_length = strlen(prefix);
1857 }
Jeff King3a03cf62011-03-29 16:57:27 -04001858
Denton Liue6e230e2019-12-09 05:10:41 -08001859 init_display_notes(&revs->notes_opt);
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01001860}
1861
Rene Scharfe0d2c9d62006-07-02 01:29:37 +02001862static void add_pending_commit_list(struct rev_info *revs,
Nguyễn Thái Ngọc Duyec36c422018-12-06 16:42:06 +01001863 struct commit_list *commit_list,
1864 unsigned int flags)
Rene Scharfe0d2c9d62006-07-02 01:29:37 +02001865{
1866 while (commit_list) {
1867 struct object *object = &commit_list->item->object;
1868 object->flags |= flags;
brian m. carlsonf2fd0762015-11-10 02:22:28 +00001869 add_pending_object(revs, object, oid_to_hex(&object->oid));
Rene Scharfe0d2c9d62006-07-02 01:29:37 +02001870 commit_list = commit_list->next;
1871 }
1872}
1873
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001874static void prepare_show_merge(struct rev_info *revs)
1875{
1876 struct commit_list *bases;
1877 struct commit *head, *other;
brian m. carlson68ab61d2017-05-06 22:10:05 +00001878 struct object_id oid;
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001879 const char **prune = NULL;
1880 int i, prune_num = 1; /* counting terminating NULL */
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001881 struct index_state *istate = revs->repo->index;
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001882
brian m. carlson68ab61d2017-05-06 22:10:05 +00001883 if (get_oid("HEAD", &oid))
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001884 die("--merge without HEAD?");
brian m. carlsonbc832662017-05-06 22:10:10 +00001885 head = lookup_commit_or_die(&oid, "HEAD");
brian m. carlson68ab61d2017-05-06 22:10:05 +00001886 if (get_oid("MERGE_HEAD", &oid))
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001887 die("--merge without MERGE_HEAD?");
brian m. carlsonbc832662017-05-06 22:10:10 +00001888 other = lookup_commit_or_die(&oid, "MERGE_HEAD");
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001889 add_pending_object(revs, &head->object, "HEAD");
1890 add_pending_object(revs, &other->object, "MERGE_HEAD");
Junio C Hamano2ce406c2014-10-30 12:20:44 -07001891 bases = get_merge_bases(head, other);
Kevin Bracey7f34a462013-05-16 18:32:38 +03001892 add_rev_cmdline_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING | BOTTOM);
1893 add_pending_commit_list(revs, bases, UNINTERESTING | BOTTOM);
Junio C Hamanoe82447b2008-02-26 23:18:38 -08001894 free_commit_list(bases);
1895 head->object.flags |= SYMMETRIC_LEFT;
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001896
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001897 if (!istate->cache_nr)
Nguyễn Thái Ngọc Duye1ff0a32019-01-12 09:13:26 +07001898 repo_read_index(revs->repo);
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001899 for (i = 0; i < istate->cache_nr; i++) {
1900 const struct cache_entry *ce = istate->cache[i];
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001901 if (!ce_stage(ce))
1902 continue;
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001903 if (ce_path_match(istate, ce, &revs->prune_data, NULL)) {
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001904 prune_num++;
René Scharfe2756ca42014-09-16 20:56:57 +02001905 REALLOC_ARRAY(prune, prune_num);
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001906 prune[prune_num-2] = ce->name;
1907 prune[prune_num-1] = NULL;
1908 }
Nguyễn Thái Ngọc Duy2abf3502018-09-21 17:57:38 +02001909 while ((i+1 < istate->cache_nr) &&
1910 ce_same_name(ce, istate->cache[i+1]))
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001911 i++;
1912 }
Junio C Hamanoed6e8032016-06-02 14:09:22 -07001913 clear_pathspec(&revs->prune_data);
Nguyễn Thái Ngọc Duy4a2d5ae2013-10-26 09:09:20 +07001914 parse_pathspec(&revs->prune_data, PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,
Junio C Hamanoc6f1b922013-11-18 14:31:29 -08001915 PATHSPEC_PREFER_FULL | PATHSPEC_LITERAL_PATH, "", prune);
Junio C Hamanoe82447b2008-02-26 23:18:38 -08001916 revs->limited = 1;
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07001917}
1918
Jeff King62faad52017-05-19 08:52:00 -04001919static int dotdot_missing(const char *arg, char *dotdot,
1920 struct rev_info *revs, int symmetric)
1921{
1922 if (revs->ignore_missing)
1923 return 0;
1924 /* de-munge so we report the full argument */
1925 *dotdot = '.';
1926 die(symmetric
1927 ? "Invalid symmetric difference expression %s"
1928 : "Invalid revision range %s", arg);
1929}
1930
1931static int handle_dotdot_1(const char *arg, char *dotdot,
1932 struct rev_info *revs, int flags,
Jeff King18f1ad72017-05-19 08:55:26 -04001933 int cant_be_filename,
1934 struct object_context *a_oc,
1935 struct object_context *b_oc)
Jeff King62faad52017-05-19 08:52:00 -04001936{
1937 const char *a_name, *b_name;
1938 struct object_id a_oid, b_oid;
1939 struct object *a_obj, *b_obj;
1940 unsigned int a_flags, b_flags;
1941 int symmetric = 0;
1942 unsigned int flags_exclude = flags ^ (UNINTERESTING | BOTTOM);
brian m. carlson321c89b2017-07-13 23:49:29 +00001943 unsigned int oc_flags = GET_OID_COMMITTISH | GET_OID_RECORD_PATH;
Jeff King62faad52017-05-19 08:52:00 -04001944
1945 a_name = arg;
1946 if (!*a_name)
1947 a_name = "HEAD";
1948
1949 b_name = dotdot + 2;
1950 if (*b_name == '.') {
1951 symmetric = 1;
1952 b_name++;
1953 }
1954 if (!*b_name)
1955 b_name = "HEAD";
1956
Nguyễn Thái Ngọc Duy3a7a6982019-01-12 09:13:28 +07001957 if (get_oid_with_context(revs->repo, a_name, oc_flags, &a_oid, a_oc) ||
1958 get_oid_with_context(revs->repo, b_name, oc_flags, &b_oid, b_oc))
Jeff King62faad52017-05-19 08:52:00 -04001959 return -1;
1960
1961 if (!cant_be_filename) {
1962 *dotdot = '.';
1963 verify_non_filename(revs->prefix, arg);
1964 *dotdot = '\0';
1965 }
1966
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02001967 a_obj = parse_object(revs->repo, &a_oid);
1968 b_obj = parse_object(revs->repo, &b_oid);
Jeff King62faad52017-05-19 08:52:00 -04001969 if (!a_obj || !b_obj)
1970 return dotdot_missing(arg, dotdot, revs, symmetric);
1971
1972 if (!symmetric) {
1973 /* just A..B */
1974 b_flags = flags;
1975 a_flags = flags_exclude;
1976 } else {
1977 /* A...B -- find merge bases between the two */
1978 struct commit *a, *b;
1979 struct commit_list *exclude;
1980
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02001981 a = lookup_commit_reference(revs->repo, &a_obj->oid);
1982 b = lookup_commit_reference(revs->repo, &b_obj->oid);
Jeff King62faad52017-05-19 08:52:00 -04001983 if (!a || !b)
1984 return dotdot_missing(arg, dotdot, revs, symmetric);
1985
1986 exclude = get_merge_bases(a, b);
1987 add_rev_cmdline_list(revs, exclude, REV_CMD_MERGE_BASE,
1988 flags_exclude);
1989 add_pending_commit_list(revs, exclude, flags_exclude);
1990 free_commit_list(exclude);
1991
1992 b_flags = flags;
1993 a_flags = flags | SYMMETRIC_LEFT;
1994 }
1995
1996 a_obj->flags |= a_flags;
1997 b_obj->flags |= b_flags;
1998 add_rev_cmdline(revs, a_obj, a_name, REV_CMD_LEFT, a_flags);
1999 add_rev_cmdline(revs, b_obj, b_name, REV_CMD_RIGHT, b_flags);
Jeff King18f1ad72017-05-19 08:55:26 -04002000 add_pending_object_with_path(revs, a_obj, a_name, a_oc->mode, a_oc->path);
2001 add_pending_object_with_path(revs, b_obj, b_name, b_oc->mode, b_oc->path);
Jeff King62faad52017-05-19 08:52:00 -04002002 return 0;
2003}
2004
2005static int handle_dotdot(const char *arg,
2006 struct rev_info *revs, int flags,
2007 int cant_be_filename)
2008{
Jeff King18f1ad72017-05-19 08:55:26 -04002009 struct object_context a_oc, b_oc;
Jeff King62faad52017-05-19 08:52:00 -04002010 char *dotdot = strstr(arg, "..");
2011 int ret;
2012
2013 if (!dotdot)
2014 return -1;
2015
Jeff King18f1ad72017-05-19 08:55:26 -04002016 memset(&a_oc, 0, sizeof(a_oc));
2017 memset(&b_oc, 0, sizeof(b_oc));
2018
Jeff King62faad52017-05-19 08:52:00 -04002019 *dotdot = '\0';
Jeff King18f1ad72017-05-19 08:55:26 -04002020 ret = handle_dotdot_1(arg, dotdot, revs, flags, cant_be_filename,
2021 &a_oc, &b_oc);
Jeff King62faad52017-05-19 08:52:00 -04002022 *dotdot = '.';
2023
Jeff King18f1ad72017-05-19 08:55:26 -04002024 free(a_oc.path);
2025 free(b_oc.path);
2026
Jeff King62faad52017-05-19 08:52:00 -04002027 return ret;
2028}
2029
Jeff King04a0e982020-08-26 16:13:05 -04002030static int handle_revision_arg_1(const char *arg_, struct rev_info *revs, int flags, unsigned revarg_opt)
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002031{
Junio C Hamano249c8f42012-07-02 12:56:44 -07002032 struct object_context oc;
Jeff Kingf632ded2017-05-19 08:50:07 -04002033 char *mark;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002034 struct object *object;
brian m. carlson654b9a92017-05-06 22:10:27 +00002035 struct object_id oid;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002036 int local_flags;
Junio C Hamano281eee42011-08-25 17:35:39 -07002037 const char *arg = arg_;
Junio C Hamano8e676e82012-07-02 12:33:52 -07002038 int cant_be_filename = revarg_opt & REVARG_CANNOT_BE_FILENAME;
brian m. carlson321c89b2017-07-13 23:49:29 +00002039 unsigned get_sha1_flags = GET_OID_RECORD_PATH;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002040
Kevin Bracey7f34a462013-05-16 18:32:38 +03002041 flags = flags & UNINTERESTING ? flags | BOTTOM : flags & ~BOTTOM;
2042
Jeff Kingd89797f2017-05-19 08:51:40 -04002043 if (!cant_be_filename && !strcmp(arg, "..")) {
2044 /*
2045 * Just ".."? That is not a range but the
2046 * pathspec for the parent directory.
2047 */
2048 return -1;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002049 }
Vegard Nossum87793512016-09-27 10:32:49 +02002050
Jeff King62faad52017-05-19 08:52:00 -04002051 if (!handle_dotdot(arg, revs, flags, revarg_opt))
2052 return 0;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002053
Jeff Kingf632ded2017-05-19 08:50:07 -04002054 mark = strstr(arg, "^@");
2055 if (mark && !mark[2]) {
2056 *mark = 0;
Vegard Nossum87793512016-09-27 10:32:49 +02002057 if (add_parents_only(revs, arg, flags, 0))
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002058 return 0;
Jeff Kingf632ded2017-05-19 08:50:07 -04002059 *mark = '^';
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002060 }
Jeff Kingf632ded2017-05-19 08:50:07 -04002061 mark = strstr(arg, "^!");
2062 if (mark && !mark[2]) {
2063 *mark = 0;
Vegard Nossum87793512016-09-27 10:32:49 +02002064 if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), 0))
Jeff Kingf632ded2017-05-19 08:50:07 -04002065 *mark = '^';
Vegard Nossum87793512016-09-27 10:32:49 +02002066 }
Jeff Kingf632ded2017-05-19 08:50:07 -04002067 mark = strstr(arg, "^-");
2068 if (mark) {
Vegard Nossum87793512016-09-27 10:32:49 +02002069 int exclude_parent = 1;
2070
Jeff Kingf632ded2017-05-19 08:50:07 -04002071 if (mark[2]) {
Vegard Nossum87793512016-09-27 10:32:49 +02002072 char *end;
Jeff Kingf632ded2017-05-19 08:50:07 -04002073 exclude_parent = strtoul(mark + 2, &end, 10);
Vegard Nossum87793512016-09-27 10:32:49 +02002074 if (*end != '\0' || !exclude_parent)
2075 return -1;
2076 }
2077
Jeff Kingf632ded2017-05-19 08:50:07 -04002078 *mark = 0;
Vegard Nossum87793512016-09-27 10:32:49 +02002079 if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), exclude_parent))
Jeff Kingf632ded2017-05-19 08:50:07 -04002080 *mark = '^';
Junio C Hamano62476c82006-10-31 14:22:34 -08002081 }
2082
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002083 local_flags = 0;
2084 if (*arg == '^') {
Kevin Bracey7f34a462013-05-16 18:32:38 +03002085 local_flags = UNINTERESTING | BOTTOM;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002086 arg++;
2087 }
Junio C Hamanod5f6b1d2012-07-02 12:43:05 -07002088
2089 if (revarg_opt & REVARG_COMMITTISH)
brian m. carlson321c89b2017-07-13 23:49:29 +00002090 get_sha1_flags |= GET_OID_COMMITTISH;
Junio C Hamanod5f6b1d2012-07-02 12:43:05 -07002091
Nguyễn Thái Ngọc Duy3a7a6982019-01-12 09:13:28 +07002092 if (get_oid_with_context(revs->repo, arg, get_sha1_flags, &oid, &oc))
Junio C Hamanocc243c32011-05-18 18:08:09 -07002093 return revs->ignore_missing ? 0 : -1;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002094 if (!cant_be_filename)
2095 verify_non_filename(revs->prefix, arg);
brian m. carlson654b9a92017-05-06 22:10:27 +00002096 object = get_reference(revs, arg, &oid, flags ^ local_flags);
Matthew DeVore4cf67862018-12-05 13:43:46 -08002097 if (!object)
2098 return revs->ignore_missing ? 0 : -1;
Junio C Hamano281eee42011-08-25 17:35:39 -07002099 add_rev_cmdline(revs, object, arg_, REV_CMD_REV, flags ^ local_flags);
Jeff King18f1ad72017-05-19 08:55:26 -04002100 add_pending_object_with_path(revs, object, arg, oc.mode, oc.path);
2101 free(oc.path);
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002102 return 0;
2103}
2104
Jeff King04a0e982020-08-26 16:13:05 -04002105int handle_revision_arg(const char *arg, struct rev_info *revs, int flags, unsigned revarg_opt)
2106{
2107 int ret = handle_revision_arg_1(arg, revs, flags, revarg_opt);
2108 if (!ret)
2109 revs->rev_input_given = 1;
2110 return ret;
2111}
2112
Jeff King91633992019-03-20 04:13:36 -04002113static void read_pathspec_from_stdin(struct strbuf *sb,
Jeff Kingc972bf42020-07-28 16:25:12 -04002114 struct strvec *prune)
Junio C Hamano4da5af32011-05-11 14:01:19 -07002115{
Jeff King7fa3c2a2017-09-20 16:36:59 -04002116 while (strbuf_getline(sb, stdin) != EOF)
Jeff Kingc972bf42020-07-28 16:25:12 -04002117 strvec_push(prune, sb->buf);
Junio C Hamano60da8b12009-11-20 02:50:21 -08002118}
2119
Junio C Hamano4da5af32011-05-11 14:01:19 -07002120static void read_revisions_from_stdin(struct rev_info *revs,
Jeff Kingc972bf42020-07-28 16:25:12 -04002121 struct strvec *prune)
Adam Brewster1fc561d2008-07-05 17:26:39 -04002122{
Junio C Hamano63d564b2009-11-20 02:00:40 -08002123 struct strbuf sb;
Junio C Hamano60da8b12009-11-20 02:50:21 -08002124 int seen_dashdash = 0;
Jeff King4c30d502014-03-12 16:06:17 -04002125 int save_warning;
2126
2127 save_warning = warn_on_object_refname_ambiguity;
2128 warn_on_object_refname_ambiguity = 0;
Adam Brewster1fc561d2008-07-05 17:26:39 -04002129
Junio C Hamano63d564b2009-11-20 02:00:40 -08002130 strbuf_init(&sb, 1000);
Junio C Hamano6e8d46f2015-10-28 14:05:53 -07002131 while (strbuf_getline(&sb, stdin) != EOF) {
Junio C Hamano63d564b2009-11-20 02:00:40 -08002132 int len = sb.len;
Adam Brewster1fc561d2008-07-05 17:26:39 -04002133 if (!len)
2134 break;
Junio C Hamano60da8b12009-11-20 02:50:21 -08002135 if (sb.buf[0] == '-') {
2136 if (len == 2 && sb.buf[1] == '-') {
2137 seen_dashdash = 1;
2138 break;
2139 }
Adam Brewster1fc561d2008-07-05 17:26:39 -04002140 die("options not supported in --stdin mode");
Junio C Hamano60da8b12009-11-20 02:50:21 -08002141 }
Michael Haggerty31faeb22013-05-25 11:08:14 +02002142 if (handle_revision_arg(sb.buf, revs, 0,
Thomas Rast70d26c62013-04-16 11:57:45 +02002143 REVARG_CANNOT_BE_FILENAME))
Junio C Hamano63d564b2009-11-20 02:00:40 -08002144 die("bad revision '%s'", sb.buf);
Adam Brewster1fc561d2008-07-05 17:26:39 -04002145 }
Junio C Hamano60da8b12009-11-20 02:50:21 -08002146 if (seen_dashdash)
Jeff King91633992019-03-20 04:13:36 -04002147 read_pathspec_from_stdin(&sb, prune);
Jeff King4c30d502014-03-12 16:06:17 -04002148
Junio C Hamano63d564b2009-11-20 02:00:40 -08002149 strbuf_release(&sb);
Jeff King4c30d502014-03-12 16:06:17 -04002150 warn_on_object_refname_ambiguity = save_warning;
Adam Brewster1fc561d2008-07-05 17:26:39 -04002151}
2152
Junio C Hamano2d10c552006-09-20 13:21:56 -07002153static void add_grep(struct rev_info *revs, const char *ptn, enum grep_pat_token what)
2154{
Jeff King0843acf2008-08-25 02:15:05 -04002155 append_grep_pattern(&revs->grep_filter, ptn, "command line", 0, what);
Junio C Hamano2d10c552006-09-20 13:21:56 -07002156}
2157
Junio C Hamanoa4d7d2c2008-09-04 22:15:02 -07002158static void add_header_grep(struct rev_info *revs, enum grep_header_field field, const char *pattern)
Junio C Hamanobd95fcd2006-09-17 17:23:20 -07002159{
Junio C Hamanoa4d7d2c2008-09-04 22:15:02 -07002160 append_header_grep_pattern(&revs->grep_filter, field, pattern);
Junio C Hamanobd95fcd2006-09-17 17:23:20 -07002161}
2162
2163static void add_message_grep(struct rev_info *revs, const char *pattern)
2164{
Junio C Hamano2d10c552006-09-20 13:21:56 -07002165 add_grep(revs, pattern, GREP_PATTERN_BODY);
Junio C Hamanobd95fcd2006-09-17 17:23:20 -07002166}
2167
Pierre Habouzit6b61ec02008-07-09 23:38:34 +02002168static int handle_revision_opt(struct rev_info *revs, int argc, const char **argv,
Matthew DeVorebbcde412018-12-03 14:10:19 -08002169 int *unkc, const char **unkv,
2170 const struct setup_revision_opt* opt)
Pierre Habouzit02e54222008-07-08 15:19:33 +02002171{
2172 const char *arg = argv[0];
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002173 const char *optarg;
2174 int argcount;
brian m. carlsonfd521242018-05-02 00:25:50 +00002175 const unsigned hexsz = the_hash_algo->hexsz;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002176
2177 /* pseudo revision arguments */
2178 if (!strcmp(arg, "--all") || !strcmp(arg, "--branches") ||
2179 !strcmp(arg, "--tags") || !strcmp(arg, "--remotes") ||
2180 !strcmp(arg, "--reflog") || !strcmp(arg, "--not") ||
Linus Torvaldsad3f9a72009-10-27 11:28:07 -07002181 !strcmp(arg, "--no-walk") || !strcmp(arg, "--do-walk") ||
Christian Couder59556542013-11-30 21:55:40 +01002182 !strcmp(arg, "--bisect") || starts_with(arg, "--glob=") ||
Jeff King4fe10212014-10-16 20:44:23 -04002183 !strcmp(arg, "--indexed-objects") ||
Jeff King39b44ba2019-07-01 09:18:15 -04002184 !strcmp(arg, "--alternate-refs") ||
Junio C Hamano07768e02014-06-09 11:30:12 -07002185 starts_with(arg, "--exclude=") ||
Christian Couder59556542013-11-30 21:55:40 +01002186 starts_with(arg, "--branches=") || starts_with(arg, "--tags=") ||
2187 starts_with(arg, "--remotes=") || starts_with(arg, "--no-walk="))
Pierre Habouzit02e54222008-07-08 15:19:33 +02002188 {
2189 unkv[(*unkc)++] = arg;
Pierre Habouzit0fe8c132008-07-31 12:22:23 +02002190 return 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002191 }
2192
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002193 if ((argcount = parse_long_opt("max-count", argv, &optarg))) {
2194 revs->max_count = atoi(optarg);
Jonathan Nieder5853cae2010-06-01 03:35:49 -05002195 revs->no_walk = 0;
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002196 return argcount;
2197 } else if ((argcount = parse_long_opt("skip", argv, &optarg))) {
2198 revs->skip_count = atoi(optarg);
2199 return argcount;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002200 } else if ((*arg == '-') && isdigit(arg[1])) {
Junio C Hamanoe3fa5682014-06-06 15:33:25 -07002201 /* accept -<digit>, like traditional "head" */
2202 if (strtol_i(arg + 1, 10, &revs->max_count) < 0 ||
2203 revs->max_count < 0)
2204 die("'%s': not a non-negative integer", arg + 1);
Jonathan Nieder5853cae2010-06-01 03:35:49 -05002205 revs->no_walk = 0;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002206 } else if (!strcmp(arg, "-n")) {
2207 if (argc <= 1)
2208 return error("-n requires an argument");
2209 revs->max_count = atoi(argv[1]);
Jonathan Nieder5853cae2010-06-01 03:35:49 -05002210 revs->no_walk = 0;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002211 return 2;
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002212 } else if (skip_prefix(arg, "-n", &optarg)) {
2213 revs->max_count = atoi(optarg);
Jonathan Nieder5853cae2010-06-01 03:35:49 -05002214 revs->no_walk = 0;
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002215 } else if ((argcount = parse_long_opt("max-age", argv, &optarg))) {
2216 revs->max_age = atoi(optarg);
2217 return argcount;
2218 } else if ((argcount = parse_long_opt("since", argv, &optarg))) {
2219 revs->max_age = approxidate(optarg);
2220 return argcount;
2221 } else if ((argcount = parse_long_opt("after", argv, &optarg))) {
2222 revs->max_age = approxidate(optarg);
2223 return argcount;
2224 } else if ((argcount = parse_long_opt("min-age", argv, &optarg))) {
2225 revs->min_age = atoi(optarg);
2226 return argcount;
2227 } else if ((argcount = parse_long_opt("before", argv, &optarg))) {
2228 revs->min_age = approxidate(optarg);
2229 return argcount;
2230 } else if ((argcount = parse_long_opt("until", argv, &optarg))) {
2231 revs->min_age = approxidate(optarg);
2232 return argcount;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002233 } else if (!strcmp(arg, "--first-parent")) {
2234 revs->first_parent_only = 1;
Jerry Zhang9d505b72022-01-11 13:39:41 -08002235 } else if (!strcmp(arg, "--exclude-first-parent-only")) {
2236 revs->exclude_first_parent_only = 1;
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07002237 } else if (!strcmp(arg, "--ancestry-path")) {
2238 revs->ancestry_path = 1;
Johan Herlandcb7529e2010-06-04 01:17:37 +02002239 revs->simplify_history = 0;
Junio C Hamanoebdc94f2010-04-20 13:48:39 -07002240 revs->limited = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002241 } else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) {
2242 init_reflog_walk(&revs->reflog_info);
2243 } else if (!strcmp(arg, "--default")) {
2244 if (argc <= 1)
2245 return error("bad --default argument");
2246 revs->def = argv[1];
2247 return 2;
2248 } else if (!strcmp(arg, "--merge")) {
2249 revs->show_merge = 1;
2250 } else if (!strcmp(arg, "--topo-order")) {
Junio C Hamano08f704f2013-06-06 16:07:14 -07002251 revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002252 revs->topo_order = 1;
Junio C Hamano6546b592008-07-31 01:17:41 -07002253 } else if (!strcmp(arg, "--simplify-merges")) {
2254 revs->simplify_merges = 1;
Junio C Hamanoa52f0072012-06-08 14:47:08 -07002255 revs->topo_order = 1;
Junio C Hamano6546b592008-07-31 01:17:41 -07002256 revs->rewrite_parents = 1;
2257 revs->simplify_history = 0;
2258 revs->limited = 1;
Linus Torvalds78892e32008-11-03 11:25:46 -08002259 } else if (!strcmp(arg, "--simplify-by-decoration")) {
2260 revs->simplify_merges = 1;
Junio C Hamanoa52f0072012-06-08 14:47:08 -07002261 revs->topo_order = 1;
Linus Torvalds78892e32008-11-03 11:25:46 -08002262 revs->rewrite_parents = 1;
2263 revs->simplify_history = 0;
2264 revs->simplify_by_decoration = 1;
2265 revs->limited = 1;
2266 revs->prune = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002267 } else if (!strcmp(arg, "--date-order")) {
Junio C Hamano08f704f2013-06-06 16:07:14 -07002268 revs->sort_order = REV_SORT_BY_COMMIT_DATE;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002269 revs->topo_order = 1;
Junio C Hamano81c6b382013-06-07 10:35:54 -07002270 } else if (!strcmp(arg, "--author-date-order")) {
2271 revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002272 revs->topo_order = 1;
SZEDER Gábordffc6512017-06-09 20:17:31 +02002273 } else if (!strcmp(arg, "--early-output")) {
2274 revs->early_output = 100;
2275 revs->topo_order = 1;
2276 } else if (skip_prefix(arg, "--early-output=", &optarg)) {
2277 if (strtoul_ui(optarg, 10, &revs->early_output) < 0)
2278 die("'%s': not a non-negative integer", optarg);
2279 revs->topo_order = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002280 } else if (!strcmp(arg, "--parents")) {
2281 revs->rewrite_parents = 1;
2282 revs->print_parents = 1;
2283 } else if (!strcmp(arg, "--dense")) {
2284 revs->dense = 1;
2285 } else if (!strcmp(arg, "--sparse")) {
2286 revs->dense = 0;
Stefan Bellerce5b6f92017-11-15 18:00:35 -08002287 } else if (!strcmp(arg, "--in-commit-order")) {
2288 revs->tree_blobs_in_commit_order = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002289 } else if (!strcmp(arg, "--remove-empty")) {
2290 revs->remove_empty_trees = 1;
Linus Torvaldsb8e8db22009-06-29 10:28:25 -07002291 } else if (!strcmp(arg, "--merges")) {
Michael J Gruberad5aeed2011-03-21 11:14:06 +01002292 revs->min_parents = 2;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002293 } else if (!strcmp(arg, "--no-merges")) {
Michael J Gruberad5aeed2011-03-21 11:14:06 +01002294 revs->max_parents = 1;
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002295 } else if (skip_prefix(arg, "--min-parents=", &optarg)) {
2296 revs->min_parents = atoi(optarg);
SZEDER Gábor9ada7ae2017-06-09 20:17:30 +02002297 } else if (!strcmp(arg, "--no-min-parents")) {
Michael J Gruberad5aeed2011-03-21 11:14:06 +01002298 revs->min_parents = 0;
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002299 } else if (skip_prefix(arg, "--max-parents=", &optarg)) {
2300 revs->max_parents = atoi(optarg);
SZEDER Gábor9ada7ae2017-06-09 20:17:30 +02002301 } else if (!strcmp(arg, "--no-max-parents")) {
Michael J Gruberad5aeed2011-03-21 11:14:06 +01002302 revs->max_parents = -1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002303 } else if (!strcmp(arg, "--boundary")) {
2304 revs->boundary = 1;
2305 } else if (!strcmp(arg, "--left-right")) {
2306 revs->left_right = 1;
Michael J Gruber60adf7d2011-02-21 17:09:11 +01002307 } else if (!strcmp(arg, "--left-only")) {
Junio C Hamano24852d92011-02-21 16:58:37 -08002308 if (revs->right_only)
Michael J Gruber94f605e2011-03-07 13:31:42 +01002309 die("--left-only is incompatible with --right-only"
2310 " or --cherry");
Michael J Gruber60adf7d2011-02-21 17:09:11 +01002311 revs->left_only = 1;
2312 } else if (!strcmp(arg, "--right-only")) {
Junio C Hamano24852d92011-02-21 16:58:37 -08002313 if (revs->left_only)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002314 die(_("options '%s' and '%s' cannot be used together"), "--right-only", "--left-only");
Michael J Gruber60adf7d2011-02-21 17:09:11 +01002315 revs->right_only = 1;
Michael J Gruber94f605e2011-03-07 13:31:42 +01002316 } else if (!strcmp(arg, "--cherry")) {
2317 if (revs->left_only)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002318 die(_("options '%s' and '%s' cannot be used together"), "--cherry", "--left-only");
Michael J Gruber94f605e2011-03-07 13:31:42 +01002319 revs->cherry_mark = 1;
2320 revs->right_only = 1;
Michael J Gruberad5aeed2011-03-21 11:14:06 +01002321 revs->max_parents = 1;
Michael J Gruber94f605e2011-03-07 13:31:42 +01002322 revs->limited = 1;
Thomas Rastf69c5012010-06-10 13:47:23 +02002323 } else if (!strcmp(arg, "--count")) {
2324 revs->count = 1;
Michael J Gruberadbbb312011-03-07 13:31:40 +01002325 } else if (!strcmp(arg, "--cherry-mark")) {
2326 if (revs->cherry_pick)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002327 die(_("options '%s' and '%s' cannot be used together"), "--cherry-mark", "--cherry-pick");
Michael J Gruberadbbb312011-03-07 13:31:40 +01002328 revs->cherry_mark = 1;
2329 revs->limited = 1; /* needs limit_list() */
Pierre Habouzit02e54222008-07-08 15:19:33 +02002330 } else if (!strcmp(arg, "--cherry-pick")) {
Michael J Gruberadbbb312011-03-07 13:31:40 +01002331 if (revs->cherry_mark)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002332 die(_("options '%s' and '%s' cannot be used together"), "--cherry-pick", "--cherry-mark");
Pierre Habouzit02e54222008-07-08 15:19:33 +02002333 revs->cherry_pick = 1;
2334 revs->limited = 1;
2335 } else if (!strcmp(arg, "--objects")) {
2336 revs->tag_objects = 1;
2337 revs->tree_objects = 1;
2338 revs->blob_objects = 1;
2339 } else if (!strcmp(arg, "--objects-edge")) {
2340 revs->tag_objects = 1;
2341 revs->tree_objects = 1;
2342 revs->blob_objects = 1;
2343 revs->edge_hint = 1;
brian m. carlson1684c1b2014-12-24 23:05:39 +00002344 } else if (!strcmp(arg, "--objects-edge-aggressive")) {
2345 revs->tag_objects = 1;
2346 revs->tree_objects = 1;
2347 revs->blob_objects = 1;
2348 revs->edge_hint = 1;
2349 revs->edge_hint_aggressive = 1;
Junio C Hamano5a48d242011-09-01 15:43:34 -07002350 } else if (!strcmp(arg, "--verify-objects")) {
2351 revs->tag_objects = 1;
2352 revs->tree_objects = 1;
2353 revs->blob_objects = 1;
2354 revs->verify_objects = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002355 } else if (!strcmp(arg, "--unpacked")) {
2356 revs->unpacked = 1;
Christian Couder59556542013-11-30 21:55:40 +01002357 } else if (starts_with(arg, "--unpacked=")) {
Sergey Organovf649aaa2020-08-05 01:26:30 +03002358 die(_("--unpacked=<packfile> no longer supported"));
Taylor Blauc9fff002021-02-22 21:25:07 -05002359 } else if (!strcmp(arg, "--no-kept-objects")) {
2360 revs->no_kept_objects = 1;
2361 revs->keep_pack_cache_flags |= IN_CORE_KEEP_PACKS;
2362 revs->keep_pack_cache_flags |= ON_DISK_KEEP_PACKS;
2363 } else if (skip_prefix(arg, "--no-kept-objects=", &optarg)) {
2364 revs->no_kept_objects = 1;
2365 if (!strcmp(optarg, "in-core"))
2366 revs->keep_pack_cache_flags |= IN_CORE_KEEP_PACKS;
2367 if (!strcmp(optarg, "on-disk"))
2368 revs->keep_pack_cache_flags |= ON_DISK_KEEP_PACKS;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002369 } else if (!strcmp(arg, "-r")) {
2370 revs->diff = 1;
Brandon Williams0d1e0e72017-10-31 11:19:11 -07002371 revs->diffopt.flags.recursive = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002372 } else if (!strcmp(arg, "-t")) {
2373 revs->diff = 1;
Brandon Williams0d1e0e72017-10-31 11:19:11 -07002374 revs->diffopt.flags.recursive = 1;
2375 revs->diffopt.flags.tree_in_recursive = 1;
Sergey Organov18f09472020-12-21 18:19:34 +03002376 } else if ((argcount = diff_merges_parse_opts(revs, argv))) {
Sergey Organov65015802020-08-06 01:08:30 +03002377 return argcount;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002378 } else if (!strcmp(arg, "-v")) {
2379 revs->verbose_header = 1;
2380 } else if (!strcmp(arg, "--pretty")) {
2381 revs->verbose_header = 1;
Junio C Hamano66b2ed02010-01-20 13:59:36 -08002382 revs->pretty_given = 1;
Jeff Kingae181652014-07-29 13:53:40 -04002383 get_commit_format(NULL, revs);
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002384 } else if (skip_prefix(arg, "--pretty=", &optarg) ||
2385 skip_prefix(arg, "--format=", &optarg)) {
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002386 /*
2387 * Detached form ("--pretty X" as opposed to "--pretty=X")
2388 * not allowed, since the argument is optional.
2389 */
Pierre Habouzit02e54222008-07-08 15:19:33 +02002390 revs->verbose_header = 1;
Junio C Hamano66b2ed02010-01-20 13:59:36 -08002391 revs->pretty_given = 1;
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002392 get_commit_format(optarg, revs);
Linus Torvalds7cc13c72016-03-16 09:15:53 -07002393 } else if (!strcmp(arg, "--expand-tabs")) {
Junio C Hamanofe37a9c2016-03-29 16:05:39 -07002394 revs->expand_tabs_in_log = 8;
Junio C Hamano0893eec2016-03-29 15:49:24 -07002395 } else if (!strcmp(arg, "--no-expand-tabs")) {
2396 revs->expand_tabs_in_log = 0;
Junio C Hamanofe37a9c2016-03-29 16:05:39 -07002397 } else if (skip_prefix(arg, "--expand-tabs=", &arg)) {
2398 int val;
2399 if (strtol_i(arg, 10, &val) < 0 || val < 0)
2400 die("'%s': not a non-negative integer", arg);
2401 revs->expand_tabs_in_log = val;
Jeff King7249e912011-03-29 16:57:47 -04002402 } else if (!strcmp(arg, "--show-notes") || !strcmp(arg, "--notes")) {
Denton Liu1d729752019-12-11 16:49:50 -08002403 enable_default_display_notes(&revs->notes_opt, &revs->show_notes);
Junio C Hamano66b2ed02010-01-20 13:59:36 -08002404 revs->show_notes_given = 1;
Junio C Hamano0c37f1f2011-10-18 15:53:23 -07002405 } else if (!strcmp(arg, "--show-signature")) {
2406 revs->show_signature = 1;
Mehul Jainaa379992016-06-22 22:21:25 +05302407 } else if (!strcmp(arg, "--no-show-signature")) {
2408 revs->show_signature = 0;
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002409 } else if (!strcmp(arg, "--show-linear-break")) {
2410 revs->break_bar = " ..........";
Nguyễn Thái Ngọc Duy1b32dec2014-03-25 20:23:27 +07002411 revs->track_linear = 1;
2412 revs->track_first_time = 1;
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002413 } else if (skip_prefix(arg, "--show-linear-break=", &optarg)) {
2414 revs->break_bar = xstrdup(optarg);
2415 revs->track_linear = 1;
2416 revs->track_first_time = 1;
2417 } else if (skip_prefix(arg, "--show-notes=", &optarg) ||
2418 skip_prefix(arg, "--notes=", &optarg)) {
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002419 if (starts_with(arg, "--show-notes=") &&
2420 revs->notes_opt.use_default_notes < 0)
2421 revs->notes_opt.use_default_notes = 1;
Denton Liu1d729752019-12-11 16:49:50 -08002422 enable_ref_display_notes(&revs->notes_opt, &revs->show_notes, optarg);
Junio C Hamano66b2ed02010-01-20 13:59:36 -08002423 revs->show_notes_given = 1;
Denton Liu452538c2019-12-09 05:10:44 -08002424 } else if (!strcmp(arg, "--no-notes")) {
Denton Liu1d729752019-12-11 16:49:50 -08002425 disable_display_notes(&revs->notes_opt, &revs->show_notes);
Denton Liu452538c2019-12-09 05:10:44 -08002426 revs->show_notes_given = 1;
Thomas Rast894a9d32010-03-12 18:04:26 +01002427 } else if (!strcmp(arg, "--standard-notes")) {
2428 revs->show_notes_given = 1;
Jeff King3a03cf62011-03-29 16:57:27 -04002429 revs->notes_opt.use_default_notes = 1;
Thomas Rast894a9d32010-03-12 18:04:26 +01002430 } else if (!strcmp(arg, "--no-standard-notes")) {
Jeff King3a03cf62011-03-29 16:57:27 -04002431 revs->notes_opt.use_default_notes = 0;
Nanako Shiraishide84acc2009-02-24 18:59:16 +09002432 } else if (!strcmp(arg, "--oneline")) {
2433 revs->verbose_header = 1;
2434 get_commit_format("oneline", revs);
Junio C Hamano7dccadf2010-01-21 14:57:41 -08002435 revs->pretty_given = 1;
Nanako Shiraishide84acc2009-02-24 18:59:16 +09002436 revs->abbrev_commit = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002437 } else if (!strcmp(arg, "--graph")) {
Alex Henriedccf6c12022-02-11 09:36:24 -07002438 graph_clear(revs->graph);
Pierre Habouzit02e54222008-07-08 15:19:33 +02002439 revs->graph = graph_init(revs);
Alex Henrie087c7452022-02-11 09:36:25 -07002440 } else if (!strcmp(arg, "--no-graph")) {
2441 graph_clear(revs->graph);
2442 revs->graph = NULL;
Emma Brooks19d097e2020-04-08 04:31:38 +00002443 } else if (!strcmp(arg, "--encode-email-headers")) {
2444 revs->encode_email_headers = 1;
2445 } else if (!strcmp(arg, "--no-encode-email-headers")) {
2446 revs->encode_email_headers = 0;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002447 } else if (!strcmp(arg, "--root")) {
2448 revs->show_root_diff = 1;
2449 } else if (!strcmp(arg, "--no-commit-id")) {
2450 revs->no_commit_id = 1;
2451 } else if (!strcmp(arg, "--always")) {
2452 revs->always_show_header = 1;
2453 } else if (!strcmp(arg, "--no-abbrev")) {
2454 revs->abbrev = 0;
2455 } else if (!strcmp(arg, "--abbrev")) {
2456 revs->abbrev = DEFAULT_ABBREV;
SZEDER Gábor479b3d92017-06-09 20:17:32 +02002457 } else if (skip_prefix(arg, "--abbrev=", &optarg)) {
2458 revs->abbrev = strtoul(optarg, NULL, 10);
Pierre Habouzit02e54222008-07-08 15:19:33 +02002459 if (revs->abbrev < MINIMUM_ABBREV)
2460 revs->abbrev = MINIMUM_ABBREV;
brian m. carlsonfd521242018-05-02 00:25:50 +00002461 else if (revs->abbrev > hexsz)
2462 revs->abbrev = hexsz;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002463 } else if (!strcmp(arg, "--abbrev-commit")) {
2464 revs->abbrev_commit = 1;
Jay Soffian0c476952011-05-18 13:56:04 -04002465 revs->abbrev_commit_given = 1;
2466 } else if (!strcmp(arg, "--no-abbrev-commit")) {
2467 revs->abbrev_commit = 0;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002468 } else if (!strcmp(arg, "--full-diff")) {
2469 revs->diff = 1;
2470 revs->full_diff = 1;
Derrick Stolee8d049e12020-04-10 12:19:43 +00002471 } else if (!strcmp(arg, "--show-pulls")) {
2472 revs->show_pulls = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002473 } else if (!strcmp(arg, "--full-history")) {
2474 revs->simplify_history = 0;
2475 } else if (!strcmp(arg, "--relative-date")) {
Jeff Kinga5481a62015-06-25 12:55:02 -04002476 revs->date_mode.type = DATE_RELATIVE;
Jeff Kingf4ea32f2009-09-24 04:28:15 -04002477 revs->date_mode_explicit = 1;
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002478 } else if ((argcount = parse_long_opt("date", argv, &optarg))) {
Jeff Kinga5481a62015-06-25 12:55:02 -04002479 parse_date_format(optarg, &revs->date_mode);
Jeff Kingf4ea32f2009-09-24 04:28:15 -04002480 revs->date_mode_explicit = 1;
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002481 return argcount;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002482 } else if (!strcmp(arg, "--log-size")) {
2483 revs->show_log_size = 1;
2484 }
2485 /*
2486 * Grepping the commit log
2487 */
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002488 else if ((argcount = parse_long_opt("author", argv, &optarg))) {
2489 add_header_grep(revs, GREP_HEADER_AUTHOR, optarg);
2490 return argcount;
2491 } else if ((argcount = parse_long_opt("committer", argv, &optarg))) {
2492 add_header_grep(revs, GREP_HEADER_COMMITTER, optarg);
2493 return argcount;
Nguyễn Thái Ngọc Duy72fd13f2012-09-29 11:41:28 +07002494 } else if ((argcount = parse_long_opt("grep-reflog", argv, &optarg))) {
2495 add_header_grep(revs, GREP_HEADER_REFLOG, optarg);
2496 return argcount;
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002497 } else if ((argcount = parse_long_opt("grep", argv, &optarg))) {
2498 add_message_grep(revs, optarg);
2499 return argcount;
Junio C Hamano727b6fc2012-10-03 15:01:34 -07002500 } else if (!strcmp(arg, "--basic-regexp")) {
Junio C Hamano84655412016-07-22 11:43:14 -07002501 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_BRE;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002502 } else if (!strcmp(arg, "--extended-regexp") || !strcmp(arg, "-E")) {
Junio C Hamano84655412016-07-22 11:43:14 -07002503 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_ERE;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002504 } else if (!strcmp(arg, "--regexp-ignore-case") || !strcmp(arg, "-i")) {
Ævar Arnfjörð Bjarmason9e3cbc52017-05-20 21:42:08 +00002505 revs->grep_filter.ignore_case = 1;
Stefan Bellerc1ddc462018-01-04 14:50:40 -08002506 revs->diffopt.pickaxe_opts |= DIFF_PICKAXE_IGNORE_CASE;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002507 } else if (!strcmp(arg, "--fixed-strings") || !strcmp(arg, "-F")) {
Junio C Hamano84655412016-07-22 11:43:14 -07002508 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_FIXED;
Ævar Arnfjörð Bjarmason7531a2d2017-05-25 20:05:24 +00002509 } else if (!strcmp(arg, "--perl-regexp") || !strcmp(arg, "-P")) {
Junio C Hamano84655412016-07-22 11:43:14 -07002510 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_PCRE;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002511 } else if (!strcmp(arg, "--all-match")) {
Jeff King0843acf2008-08-25 02:15:05 -04002512 revs->grep_filter.all_match = 1;
Christoph Junghans22dfa8a2015-01-12 18:33:32 -07002513 } else if (!strcmp(arg, "--invert-grep")) {
René Scharfe794c0002021-12-17 17:48:49 +01002514 revs->grep_filter.no_body_match = 1;
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002515 } else if ((argcount = parse_long_opt("encoding", argv, &optarg))) {
2516 if (strcmp(optarg, "none"))
2517 git_log_output_encoding = xstrdup(optarg);
Pierre Habouzit02e54222008-07-08 15:19:33 +02002518 else
2519 git_log_output_encoding = "";
Matthieu Moy7d7b86f2010-08-05 10:22:55 +02002520 return argcount;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002521 } else if (!strcmp(arg, "--reverse")) {
2522 revs->reverse ^= 1;
2523 } else if (!strcmp(arg, "--children")) {
2524 revs->children.name = "children";
2525 revs->limited = 1;
Junio C Hamanocc243c32011-05-18 18:08:09 -07002526 } else if (!strcmp(arg, "--ignore-missing")) {
2527 revs->ignore_missing = 1;
Matthew DeVorebbcde412018-12-03 14:10:19 -08002528 } else if (opt && opt->allow_exclude_promisor_objects &&
Matthew DeVore669b1d22018-10-22 18:13:42 -07002529 !strcmp(arg, "--exclude-promisor-objects")) {
Jonathan Tandf11e192017-12-08 15:27:15 +00002530 if (fetch_if_missing)
Johannes Schindelin033abf92018-05-02 11:38:39 +02002531 BUG("exclude_promisor_objects can only be used when fetch_if_missing is 0");
Jonathan Tandf11e192017-12-08 15:27:15 +00002532 revs->exclude_promisor_objects = 1;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002533 } else {
Duy Nguyena97262c2016-01-21 18:48:44 +07002534 int opts = diff_opt_parse(&revs->diffopt, argv, argc, revs->prefix);
Pierre Habouzit02e54222008-07-08 15:19:33 +02002535 if (!opts)
2536 unkv[(*unkc)++] = arg;
2537 return opts;
2538 }
2539
2540 return 1;
2541}
2542
Pierre Habouzit6b61ec02008-07-09 23:38:34 +02002543void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx,
2544 const struct option *options,
2545 const char * const usagestr[])
2546{
2547 int n = handle_revision_opt(revs, ctx->argc, ctx->argv,
Matthew DeVorebbcde412018-12-03 14:10:19 -08002548 &ctx->cpidx, ctx->out, NULL);
Pierre Habouzit6b61ec02008-07-09 23:38:34 +02002549 if (n <= 0) {
2550 error("unknown option `%s'", ctx->argv[0]);
2551 usage_with_options(usagestr, options);
2552 }
2553 ctx->argv += n;
2554 ctx->argc -= n;
2555}
2556
Alex Henrie087c7452022-02-11 09:36:25 -07002557void revision_opts_finish(struct rev_info *revs)
2558{
2559 if (revs->graph && revs->track_linear)
2560 die(_("options '%s' and '%s' cannot be used together"), "--show-linear-break", "--graph");
2561
2562 if (revs->graph) {
2563 revs->topo_order = 1;
2564 revs->rewrite_parents = 1;
2565 }
2566}
2567
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002568static int for_each_bisect_ref(struct ref_store *refs, each_ref_fn fn,
2569 void *cb_data, const char *term)
2570{
Antoine Delaitecb46d632015-06-29 17:40:30 +02002571 struct strbuf bisect_refs = STRBUF_INIT;
2572 int status;
2573 strbuf_addf(&bisect_refs, "refs/bisect/%s", term);
Jeff King67985e42021-09-24 14:48:48 -04002574 status = refs_for_each_fullref_in(refs, bisect_refs.buf, fn, cb_data);
Antoine Delaitecb46d632015-06-29 17:40:30 +02002575 strbuf_release(&bisect_refs);
2576 return status;
2577}
2578
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002579static int for_each_bad_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
Linus Torvaldsad3f9a72009-10-27 11:28:07 -07002580{
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002581 return for_each_bisect_ref(refs, fn, cb_data, term_bad);
Linus Torvaldsad3f9a72009-10-27 11:28:07 -07002582}
2583
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002584static int for_each_good_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
Linus Torvaldsad3f9a72009-10-27 11:28:07 -07002585{
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002586 return for_each_bisect_ref(refs, fn, cb_data, term_good);
Linus Torvaldsad3f9a72009-10-27 11:28:07 -07002587}
2588
Jonathan Tan10a0d6a2021-09-09 11:47:29 -07002589static int handle_revision_pseudo_opt(struct rev_info *revs,
Jeff Kinge885a842020-09-30 08:28:18 -04002590 const char **argv, int *flags)
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002591{
2592 const char *arg = argv[0];
2593 const char *optarg;
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002594 struct ref_store *refs;
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002595 int argcount;
2596
Jonathan Tan10a0d6a2021-09-09 11:47:29 -07002597 if (revs->repo != the_repository) {
Nguyễn Thái Ngọc Duyd0c39a42017-08-23 19:36:59 +07002598 /*
2599 * We need some something like get_submodule_worktrees()
2600 * before we can go through all worktrees of a submodule,
2601 * .e.g with adding all HEADs from --all, which is not
2602 * supported right now, so stick to single worktree.
2603 */
2604 if (!revs->single_worktree)
Johannes Schindelin033abf92018-05-02 11:38:39 +02002605 BUG("--single-worktree cannot be used together with submodule");
Jonathan Tan10a0d6a2021-09-09 11:47:29 -07002606 }
2607 refs = get_main_ref_store(revs->repo);
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002608
Jonathan Nieder0fc63ec2011-04-21 05:48:24 -05002609 /*
2610 * NOTE!
2611 *
2612 * Commands like "git shortlog" will not accept the options below
2613 * unless parse_revision_opt queues them (as opposed to erroring
2614 * out).
2615 *
2616 * When implementing your new pseudo-option, remember to
2617 * register it in the list at the top of handle_revision_opt.
2618 */
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002619 if (!strcmp(arg, "--all")) {
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002620 handle_refs(refs, revs, *flags, refs_for_each_ref);
2621 handle_refs(refs, revs, *flags, refs_head_ref);
Nguyễn Thái Ngọc Duyd0c39a42017-08-23 19:36:59 +07002622 if (!revs->single_worktree) {
2623 struct all_refs_cb cb;
2624
2625 init_all_refs_cb(&cb, revs, *flags);
2626 other_head_refs(handle_one_ref, &cb);
2627 }
Junio C Hamanoff32d342013-11-01 12:02:45 -07002628 clear_ref_exclusion(&revs->ref_excludes);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002629 } else if (!strcmp(arg, "--branches")) {
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002630 handle_refs(refs, revs, *flags, refs_for_each_branch_ref);
Junio C Hamanoff32d342013-11-01 12:02:45 -07002631 clear_ref_exclusion(&revs->ref_excludes);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002632 } else if (!strcmp(arg, "--bisect")) {
Antoine Delaitecb46d632015-06-29 17:40:30 +02002633 read_bisect_terms(&term_bad, &term_good);
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002634 handle_refs(refs, revs, *flags, for_each_bad_bisect_ref);
2635 handle_refs(refs, revs, *flags ^ (UNINTERESTING | BOTTOM),
2636 for_each_good_bisect_ref);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002637 revs->bisect = 1;
2638 } else if (!strcmp(arg, "--tags")) {
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002639 handle_refs(refs, revs, *flags, refs_for_each_tag_ref);
Junio C Hamanoff32d342013-11-01 12:02:45 -07002640 clear_ref_exclusion(&revs->ref_excludes);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002641 } else if (!strcmp(arg, "--remotes")) {
Nguyễn Thái Ngọc Duy073cf632017-08-23 19:36:56 +07002642 handle_refs(refs, revs, *flags, refs_for_each_remote_ref);
Junio C Hamanoff32d342013-11-01 12:02:45 -07002643 clear_ref_exclusion(&revs->ref_excludes);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002644 } else if ((argcount = parse_long_opt("glob", argv, &optarg))) {
2645 struct all_refs_cb cb;
2646 init_all_refs_cb(&cb, revs, *flags);
Michael Haggertya217dcb2015-05-25 18:38:30 +00002647 for_each_glob_ref(handle_one_ref, optarg, &cb);
Junio C Hamanoff32d342013-11-01 12:02:45 -07002648 clear_ref_exclusion(&revs->ref_excludes);
Junio C Hamanoe7b432c2013-08-30 16:37:55 -07002649 return argcount;
2650 } else if ((argcount = parse_long_opt("exclude", argv, &optarg))) {
Junio C Hamanoff32d342013-11-01 12:02:45 -07002651 add_ref_exclusion(&revs->ref_excludes, optarg);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002652 return argcount;
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002653 } else if (skip_prefix(arg, "--branches=", &optarg)) {
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002654 struct all_refs_cb cb;
2655 init_all_refs_cb(&cb, revs, *flags);
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002656 for_each_glob_ref_in(handle_one_ref, optarg, "refs/heads/", &cb);
Junio C Hamanoff32d342013-11-01 12:02:45 -07002657 clear_ref_exclusion(&revs->ref_excludes);
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002658 } else if (skip_prefix(arg, "--tags=", &optarg)) {
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002659 struct all_refs_cb cb;
2660 init_all_refs_cb(&cb, revs, *flags);
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002661 for_each_glob_ref_in(handle_one_ref, optarg, "refs/tags/", &cb);
Junio C Hamanoff32d342013-11-01 12:02:45 -07002662 clear_ref_exclusion(&revs->ref_excludes);
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002663 } else if (skip_prefix(arg, "--remotes=", &optarg)) {
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002664 struct all_refs_cb cb;
2665 init_all_refs_cb(&cb, revs, *flags);
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002666 for_each_glob_ref_in(handle_one_ref, optarg, "refs/remotes/", &cb);
Junio C Hamanoff32d342013-11-01 12:02:45 -07002667 clear_ref_exclusion(&revs->ref_excludes);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002668 } else if (!strcmp(arg, "--reflog")) {
Jeff King718ccc92014-10-15 18:38:31 -04002669 add_reflogs_to_pending(revs, *flags);
Jeff King4fe10212014-10-16 20:44:23 -04002670 } else if (!strcmp(arg, "--indexed-objects")) {
2671 add_index_objects_to_pending(revs, *flags);
Jeff King39b44ba2019-07-01 09:18:15 -04002672 } else if (!strcmp(arg, "--alternate-refs")) {
2673 add_alternate_refs_to_pending(revs, *flags);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002674 } else if (!strcmp(arg, "--not")) {
Kevin Bracey7f34a462013-05-16 18:32:38 +03002675 *flags ^= UNINTERESTING | BOTTOM;
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002676 } else if (!strcmp(arg, "--no-walk")) {
Patrick Steinhardt29ef1f22021-08-05 13:25:24 +02002677 revs->no_walk = 1;
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002678 } else if (skip_prefix(arg, "--no-walk=", &optarg)) {
Martin von Zweigbergkca92e592012-08-28 23:15:54 -07002679 /*
2680 * Detached form ("--no-walk X" as opposed to "--no-walk=X")
2681 * not allowed, since the argument is optional.
2682 */
Patrick Steinhardt29ef1f22021-08-05 13:25:24 +02002683 revs->no_walk = 1;
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002684 if (!strcmp(optarg, "sorted"))
Patrick Steinhardt29ef1f22021-08-05 13:25:24 +02002685 revs->unsorted_input = 0;
SZEDER Gábor8b1d9132017-06-09 20:17:33 +02002686 else if (!strcmp(optarg, "unsorted"))
Patrick Steinhardt29ef1f22021-08-05 13:25:24 +02002687 revs->unsorted_input = 1;
Martin von Zweigbergkca92e592012-08-28 23:15:54 -07002688 else
2689 return error("invalid argument to --no-walk");
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002690 } else if (!strcmp(arg, "--do-walk")) {
2691 revs->no_walk = 0;
Nguyễn Thái Ngọc Duy32619f92017-08-23 19:37:02 +07002692 } else if (!strcmp(arg, "--single-worktree")) {
2693 revs->single_worktree = 1;
Derrick Stoleecc910442022-03-22 17:28:35 +00002694 } else if (skip_prefix(arg, ("--filter="), &arg)) {
Derrick Stoleec4ea5132022-03-09 16:01:40 +00002695 parse_list_objects_filter(&revs->filter, arg);
Derrick Stoleecc910442022-03-22 17:28:35 +00002696 } else if (!strcmp(arg, ("--no-filter"))) {
Derrick Stoleec4ea5132022-03-09 16:01:40 +00002697 list_objects_filter_set_no_filter(&revs->filter);
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002698 } else {
2699 return 0;
2700 }
2701
2702 return 1;
2703}
2704
Jeff Kingce113602015-08-29 01:04:18 -04002705static void NORETURN diagnose_missing_default(const char *def)
2706{
Jeff Kingce113602015-08-29 01:04:18 -04002707 int flags;
2708 const char *refname;
2709
René Scharfe744c0402017-09-23 11:45:04 +02002710 refname = resolve_ref_unsafe(def, 0, NULL, &flags);
Jeff Kingce113602015-08-29 01:04:18 -04002711 if (!refname || !(flags & REF_ISSYMREF) || (flags & REF_ISBROKEN))
2712 die(_("your current branch appears to be broken"));
2713
2714 skip_prefix(refname, "refs/heads/", &refname);
2715 die(_("your current branch '%s' does not have any commits yet"),
2716 refname);
2717}
2718
Linus Torvaldsae563542006-02-25 16:19:46 -08002719/*
2720 * Parse revision information, filling in the "rev_info" structure,
2721 * and removing the used arguments from the argument list.
2722 *
Linus Torvalds765ac8e2006-02-28 15:07:20 -08002723 * Returns the number of arguments left that weren't recognized
2724 * (which are also moved to the head of the argument list)
Linus Torvaldsae563542006-02-25 16:19:46 -08002725 */
Junio C Hamano32962c92010-03-08 22:58:09 -08002726int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *opt)
Linus Torvaldsae563542006-02-25 16:19:46 -08002727{
Jeff King04a0e982020-08-26 16:13:05 -04002728 int i, flags, left, seen_dashdash, revarg_opt;
Jeff Kingc972bf42020-07-28 16:25:12 -04002729 struct strvec prune_data = STRVEC_INIT;
Jeff King19e87892019-08-06 10:39:58 -04002730 int seen_end_of_options = 0;
Heiko Voigt9ef6aeb2010-07-07 15:39:12 +02002731
Linus Torvaldsae563542006-02-25 16:19:46 -08002732 /* First, search for "--" */
Clemens Buchacher6d5b93f2012-04-14 21:04:48 +02002733 if (opt && opt->assume_dashdash) {
Linus Torvaldsae563542006-02-25 16:19:46 -08002734 seen_dashdash = 1;
Clemens Buchacher6d5b93f2012-04-14 21:04:48 +02002735 } else {
2736 seen_dashdash = 0;
2737 for (i = 1; i < argc; i++) {
2738 const char *arg = argv[i];
2739 if (strcmp(arg, "--"))
2740 continue;
2741 argv[i] = NULL;
2742 argc = i;
2743 if (argv[i + 1])
Jeff Kingc972bf42020-07-28 16:25:12 -04002744 strvec_pushv(&prune_data, argv + i + 1);
Clemens Buchacher6d5b93f2012-04-14 21:04:48 +02002745 seen_dashdash = 1;
2746 break;
2747 }
Linus Torvaldsae563542006-02-25 16:19:46 -08002748 }
2749
Pierre Habouzit02e54222008-07-08 15:19:33 +02002750 /* Second, deal with arguments and options */
2751 flags = 0;
Junio C Hamanod5f6b1d2012-07-02 12:43:05 -07002752 revarg_opt = opt ? opt->revarg_opt : 0;
2753 if (seen_dashdash)
2754 revarg_opt |= REVARG_CANNOT_BE_FILENAME;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002755 for (left = i = 1; i < argc; i++) {
Linus Torvaldsae563542006-02-25 16:19:46 -08002756 const char *arg = argv[i];
Jeff King19e87892019-08-06 10:39:58 -04002757 if (!seen_end_of_options && *arg == '-') {
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07002758 int opts;
Pierre Habouzit02e54222008-07-08 15:19:33 +02002759
Jonathan Tan10a0d6a2021-09-09 11:47:29 -07002760 opts = handle_revision_pseudo_opt(
Jeff Kinge885a842020-09-30 08:28:18 -04002761 revs, argv + i,
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002762 &flags);
2763 if (opts > 0) {
2764 i += opts - 1;
Uwe Kleine-Königa5aa9302008-02-28 08:24:25 +01002765 continue;
2766 }
Jonathan Niederf6aca0d2011-04-21 05:45:07 -05002767
Junio C Hamano8b3dce52009-11-03 06:59:18 -08002768 if (!strcmp(arg, "--stdin")) {
2769 if (revs->disable_stdin) {
2770 argv[left++] = arg;
2771 continue;
2772 }
Jeff Kinga12cbe22018-08-22 17:37:23 -04002773 if (revs->read_from_stdin++)
Junio C Hamano8b3dce52009-11-03 06:59:18 -08002774 die("--stdin given twice?");
Junio C Hamano60da8b12009-11-20 02:50:21 -08002775 read_revisions_from_stdin(revs, &prune_data);
Junio C Hamano8b3dce52009-11-03 06:59:18 -08002776 continue;
2777 }
Junio C Hamano2d10c552006-09-20 13:21:56 -07002778
Jeff King19e87892019-08-06 10:39:58 -04002779 if (!strcmp(arg, "--end-of-options")) {
2780 seen_end_of_options = 1;
2781 continue;
2782 }
2783
Matthew DeVorebbcde412018-12-03 14:10:19 -08002784 opts = handle_revision_opt(revs, argc - i, argv + i,
2785 &left, argv, opt);
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07002786 if (opts > 0) {
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07002787 i += opts - 1;
2788 continue;
2789 }
Pierre Habouzit02e54222008-07-08 15:19:33 +02002790 if (opts < 0)
2791 exit(128);
Linus Torvaldsae563542006-02-25 16:19:46 -08002792 continue;
2793 }
Rene Scharfe0d2c9d62006-07-02 01:29:37 +02002794
Junio C Hamano8e676e82012-07-02 12:33:52 -07002795
2796 if (handle_revision_arg(arg, revs, flags, revarg_opt)) {
Linus Torvaldsae563542006-02-25 16:19:46 -08002797 int j;
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002798 if (seen_dashdash || *arg == '^')
Linus Torvaldsae563542006-02-25 16:19:46 -08002799 die("bad revision '%s'", arg);
2800
Junio C Hamanoea92f412006-04-26 15:09:27 -07002801 /* If we didn't have a "--":
2802 * (1) all filenames must exist;
2803 * (2) all rev-args must not be interpretable
2804 * as a valid filename.
2805 * but the latter we have checked in the main loop.
2806 */
Linus Torvaldse23d0b42006-04-26 10:15:54 -07002807 for (j = i; j < argc; j++)
Matthieu Moy023e37c2012-06-18 20:18:21 +02002808 verify_filename(revs->prefix, argv[j], j == i);
Linus Torvaldse23d0b42006-04-26 10:15:54 -07002809
Jeff Kingc972bf42020-07-28 16:25:12 -04002810 strvec_pushv(&prune_data, argv + i);
Linus Torvaldsae563542006-02-25 16:19:46 -08002811 break;
2812 }
Linus Torvaldsae563542006-02-25 16:19:46 -08002813 }
Alex Henrie087c7452022-02-11 09:36:25 -07002814 revision_opts_finish(revs);
Junio C Hamano5d6f0932006-09-05 21:28:36 -07002815
Jeff Kingd70a9eb2020-07-28 20:37:20 -04002816 if (prune_data.nr) {
Junio C Hamano93e7d672011-05-11 15:23:25 -07002817 /*
2818 * If we need to introduce the magic "a lone ':' means no
2819 * pathspec whatsoever", here is the place to do so.
2820 *
2821 * if (prune_data.nr == 1 && !strcmp(prune_data[0], ":")) {
2822 * prune_data.nr = 0;
2823 * prune_data.alloc = 0;
2824 * free(prune_data.path);
2825 * prune_data.path = NULL;
2826 * } else {
2827 * terminate prune_data.alloc with NULL and
2828 * call init_pathspec() to set revs->prune_data here.
2829 * }
2830 */
Nguyễn Thái Ngọc Duy0fdc2ae2013-07-14 15:35:31 +07002831 parse_pathspec(&revs->prune_data, 0, 0,
Jeff Kingd70a9eb2020-07-28 20:37:20 -04002832 revs->prefix, prune_data.v);
Junio C Hamano4da5af32011-05-11 14:01:19 -07002833 }
Jeff Kingc972bf42020-07-28 16:25:12 -04002834 strvec_clear(&prune_data);
Junio C Hamano5486ef02009-11-20 02:33:28 -08002835
Pierre Habouzit02e54222008-07-08 15:19:33 +02002836 if (revs->def == NULL)
Junio C Hamano32962c92010-03-08 22:58:09 -08002837 revs->def = opt ? opt->def : NULL;
Junio C Hamanob4490052010-03-08 23:27:25 -08002838 if (opt && opt->tweak)
2839 opt->tweak(revs, opt);
Pierre Habouzit02e54222008-07-08 15:19:33 +02002840 if (revs->show_merge)
Junio C Hamanoae3e5e12006-07-03 02:59:32 -07002841 prepare_show_merge(revs);
Jeff King04a0e982020-08-26 16:13:05 -04002842 if (revs->def && !revs->pending.nr && !revs->rev_input_given) {
brian m. carlson654b9a92017-05-06 22:10:27 +00002843 struct object_id oid;
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07002844 struct object *object;
Junio C Hamano249c8f42012-07-02 12:56:44 -07002845 struct object_context oc;
Nguyễn Thái Ngọc Duy3a7a6982019-01-12 09:13:28 +07002846 if (get_oid_with_context(revs->repo, revs->def, 0, &oid, &oc))
Jeff Kingce113602015-08-29 01:04:18 -04002847 diagnose_missing_default(revs->def);
brian m. carlson654b9a92017-05-06 22:10:27 +00002848 object = get_reference(revs, revs->def, &oid, 0);
Junio C Hamano249c8f42012-07-02 12:56:44 -07002849 add_pending_object_with_mode(revs, object, revs->def, oc.mode);
Linus Torvaldsae563542006-02-25 16:19:46 -08002850 }
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01002851
Linus Torvaldsb7bb7602007-09-29 09:50:39 -07002852 /* Did the user ask for any diff output? Run the diff! */
2853 if (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT)
2854 revs->diff = 1;
2855
Arjen Laarhoven0faf2da2007-12-25 12:06:47 +01002856 /* Pickaxe, diff-filter and rename following need diffs */
Stefan Bellercf630512018-01-04 14:50:41 -08002857 if ((revs->diffopt.pickaxe_opts & DIFF_PICKAXE_KINDS_MASK) ||
Arjen Laarhoven0faf2da2007-12-25 12:06:47 +01002858 revs->diffopt.filter ||
Brandon Williams0d1e0e72017-10-31 11:19:11 -07002859 revs->diffopt.flags.follow_renames)
Linus Torvaldsb7bb7602007-09-29 09:50:39 -07002860 revs->diff = 1;
2861
Stefan Beller15af58c2018-01-04 14:50:42 -08002862 if (revs->diffopt.objfind)
2863 revs->simplify_history = 0;
2864
SZEDER Gábor002933f2020-05-11 11:56:18 +00002865 if (revs->line_level_traverse) {
2866 if (want_ancestry(revs))
2867 revs->limited = 1;
2868 revs->topo_order = 1;
2869 }
2870
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00002871 if (revs->topo_order && !generation_numbers_enabled(the_repository))
Junio C Hamano53069682006-04-01 18:38:25 -08002872 revs->limited = 1;
2873
Nguyễn Thái Ngọc Duyafe069d2010-12-17 19:43:06 +07002874 if (revs->prune_data.nr) {
Nguyễn Thái Ngọc Duybd1928d2013-07-14 15:35:58 +07002875 copy_pathspec(&revs->pruning.pathspec, &revs->prune_data);
Linus Torvalds750f7b62007-06-19 14:22:46 -07002876 /* Can't prune commits with rename following: the paths change.. */
Brandon Williams0d1e0e72017-10-31 11:19:11 -07002877 if (!revs->diffopt.flags.follow_renames)
Linus Torvalds53b2c822007-11-05 13:22:34 -08002878 revs->prune = 1;
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07002879 if (!revs->full_diff)
Nguyễn Thái Ngọc Duybd1928d2013-07-14 15:35:58 +07002880 copy_pathspec(&revs->diffopt.pathspec,
2881 &revs->prune_data);
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01002882 }
Sergey Organov299a6632020-12-21 18:19:30 +03002883
Sergey Organov18f09472020-12-21 18:19:34 +03002884 diff_merges_setup_revs(revs);
Elijah Newrend76ce4f2019-02-07 17:12:46 -08002885
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07002886 revs->diffopt.abbrev = revs->abbrev;
Thomas Rast12da1d12013-03-28 17:47:32 +01002887
Thomas Rast28452652012-08-03 14:16:24 +02002888 diff_setup_done(&revs->diffopt);
Fredrik Kuivinen8efdc322006-03-10 10:21:39 +01002889
Ævar Arnfjörð Bjarmason44570182019-06-28 01:39:05 +02002890 if (!is_encoding_utf8(get_log_output_encoding()))
2891 revs->grep_filter.ignore_locale = 1;
Jeff King0843acf2008-08-25 02:15:05 -04002892 compile_grep_patterns(&revs->grep_filter);
Junio C Hamanobd95fcd2006-09-17 17:23:20 -07002893
Shawn O. Pearced56651c2007-08-19 22:33:43 -04002894 if (revs->reverse && revs->reflog_info)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002895 die(_("options '%s' and '%s' cannot be used together"), "--reverse", "--walk-reflogs");
Jeff King82fd0f42017-07-07 05:07:16 -04002896 if (revs->reflog_info && revs->limited)
2897 die("cannot combine --walk-reflogs with history-limiting options");
Junio C Hamano8bb65882008-07-08 15:25:44 -07002898 if (revs->rewrite_parents && revs->children.name)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002899 die(_("options '%s' and '%s' cannot be used together"), "--parents", "--children");
Derrick Stoleec4ea5132022-03-09 16:01:40 +00002900 if (revs->filter.choice && !revs->blob_objects)
2901 die(_("object filtering requires --objects"));
Shawn O. Pearced56651c2007-08-19 22:33:43 -04002902
Adam Simpkins7fefda52008-05-04 03:36:54 -07002903 /*
2904 * Limitations on the graph functionality
2905 */
2906 if (revs->reverse && revs->graph)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002907 die(_("options '%s' and '%s' cannot be used together"), "--reverse", "--graph");
Adam Simpkins7fefda52008-05-04 03:36:54 -07002908
2909 if (revs->reflog_info && revs->graph)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002910 die(_("options '%s' and '%s' cannot be used together"), "--walk-reflogs", "--graph");
Dongcan Jiang695985f2015-03-11 10:13:02 +08002911 if (revs->no_walk && revs->graph)
Jean-Noël Avila12909b62022-01-05 20:02:16 +00002912 die(_("options '%s' and '%s' cannot be used together"), "--no-walk", "--graph");
Junio C Hamanobaa63782012-09-29 11:59:52 -07002913 if (!revs->reflog_info && revs->grep_filter.use_reflog_filter)
Jean-Noël Avila6fa00ee2022-01-05 20:02:19 +00002914 die(_("the option '%s' requires '%s'"), "--grep-reflog", "--walk-reflogs");
Adam Simpkins7fefda52008-05-04 03:36:54 -07002915
Jeff King05314ef2019-03-10 23:54:33 -04002916 if (revs->line_level_traverse &&
2917 (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT)))
2918 die(_("-L does not yet support diff formats besides -p and -s"));
2919
Junio C Hamano0893eec2016-03-29 15:49:24 -07002920 if (revs->expand_tabs_in_log < 0)
2921 revs->expand_tabs_in_log = revs->expand_tabs_in_log_default;
2922
Linus Torvaldsae563542006-02-25 16:19:46 -08002923 return left;
2924}
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08002925
Junio C Hamanof35f5602008-04-03 02:12:06 -07002926static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)
2927{
2928 struct commit_list *l = xcalloc(1, sizeof(*l));
2929
2930 l->item = child;
2931 l->next = add_decoration(&revs->children, &parent->object, l);
2932}
2933
Kevin Braceyd0af6632013-05-16 18:32:34 +03002934static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)
Junio C Hamano6546b592008-07-31 01:17:41 -07002935{
Kevin Braceyd0af6632013-05-16 18:32:34 +03002936 struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
Junio C Hamano6546b592008-07-31 01:17:41 -07002937 struct commit_list **pp, *p;
2938 int surviving_parents;
2939
2940 /* Examine existing parents while marking ones we have seen... */
2941 pp = &commit->parents;
Kevin Braceyd0af6632013-05-16 18:32:34 +03002942 surviving_parents = 0;
Junio C Hamano6546b592008-07-31 01:17:41 -07002943 while ((p = *pp) != NULL) {
2944 struct commit *parent = p->item;
2945 if (parent->object.flags & TMP_MARK) {
2946 *pp = p->next;
Kevin Braceyd0af6632013-05-16 18:32:34 +03002947 if (ts)
2948 compact_treesame(revs, commit, surviving_parents);
Junio C Hamano6546b592008-07-31 01:17:41 -07002949 continue;
2950 }
2951 parent->object.flags |= TMP_MARK;
Kevin Braceyd0af6632013-05-16 18:32:34 +03002952 surviving_parents++;
Junio C Hamano6546b592008-07-31 01:17:41 -07002953 pp = &p->next;
2954 }
Kevin Braceyd0af6632013-05-16 18:32:34 +03002955 /* clear the temporary mark */
Junio C Hamano6546b592008-07-31 01:17:41 -07002956 for (p = commit->parents; p; p = p->next) {
2957 p->item->object.flags &= ~TMP_MARK;
Junio C Hamano6546b592008-07-31 01:17:41 -07002958 }
Kevin Braceyd0af6632013-05-16 18:32:34 +03002959 /* no update_treesame() - removing duplicates can't affect TREESAME */
Junio C Hamano6546b592008-07-31 01:17:41 -07002960 return surviving_parents;
2961}
2962
Junio C Hamanofaf01562008-08-14 10:59:44 -07002963struct merge_simplify_state {
2964 struct commit *simplified;
2965};
2966
2967static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs, struct commit *commit)
2968{
2969 struct merge_simplify_state *st;
2970
2971 st = lookup_decoration(&revs->merge_simplification, &commit->object);
2972 if (!st) {
René Scharfeca56dad2021-03-13 17:17:22 +01002973 CALLOC_ARRAY(st, 1);
Junio C Hamanofaf01562008-08-14 10:59:44 -07002974 add_decoration(&revs->merge_simplification, &commit->object, st);
2975 }
2976 return st;
2977}
2978
Jeff King91633992019-03-20 04:13:36 -04002979static int mark_redundant_parents(struct commit *commit)
Kevin Braceyd0af6632013-05-16 18:32:34 +03002980{
2981 struct commit_list *h = reduce_heads(commit->parents);
2982 int i = 0, marked = 0;
2983 struct commit_list *po, *pn;
2984
2985 /* Want these for sanity-checking only */
2986 int orig_cnt = commit_list_count(commit->parents);
2987 int cnt = commit_list_count(h);
2988
2989 /*
2990 * Not ready to remove items yet, just mark them for now, based
2991 * on the output of reduce_heads(). reduce_heads outputs the reduced
2992 * set in its original order, so this isn't too hard.
2993 */
2994 po = commit->parents;
2995 pn = h;
2996 while (po) {
2997 if (pn && po->item == pn->item) {
2998 pn = pn->next;
2999 i++;
3000 } else {
3001 po->item->object.flags |= TMP_MARK;
3002 marked++;
3003 }
3004 po=po->next;
3005 }
3006
3007 if (i != cnt || cnt+marked != orig_cnt)
3008 die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked);
3009
3010 free_commit_list(h);
3011
3012 return marked;
3013}
3014
Jeff King91633992019-03-20 04:13:36 -04003015static int mark_treesame_root_parents(struct commit *commit)
Kevin Bracey143f1ea2013-05-16 18:32:37 +03003016{
3017 struct commit_list *p;
3018 int marked = 0;
3019
3020 for (p = commit->parents; p; p = p->next) {
3021 struct commit *parent = p->item;
3022 if (!parent->parents && (parent->object.flags & TREESAME)) {
3023 parent->object.flags |= TMP_MARK;
3024 marked++;
3025 }
3026 }
3027
3028 return marked;
3029}
3030
Kevin Bracey9c129ea2013-05-16 18:32:36 +03003031/*
3032 * Awkward naming - this means one parent we are TREESAME to.
3033 * cf mark_treesame_root_parents: root parents that are TREESAME (to an
3034 * empty tree). Better name suggestions?
3035 */
3036static int leave_one_treesame_to_parent(struct rev_info *revs, struct commit *commit)
3037{
3038 struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
3039 struct commit *unmarked = NULL, *marked = NULL;
3040 struct commit_list *p;
3041 unsigned n;
3042
3043 for (p = commit->parents, n = 0; p; p = p->next, n++) {
3044 if (ts->treesame[n]) {
3045 if (p->item->object.flags & TMP_MARK) {
3046 if (!marked)
3047 marked = p->item;
3048 } else {
3049 if (!unmarked) {
3050 unmarked = p->item;
3051 break;
3052 }
3053 }
3054 }
3055 }
3056
3057 /*
3058 * If we are TREESAME to a marked-for-deletion parent, but not to any
3059 * unmarked parents, unmark the first TREESAME parent. This is the
3060 * parent that the default simplify_history==1 scan would have followed,
3061 * and it doesn't make sense to omit that path when asking for a
3062 * simplified full history. Retaining it improves the chances of
3063 * understanding odd missed merges that took an old version of a file.
3064 *
3065 * Example:
3066 *
3067 * I--------*X A modified the file, but mainline merge X used
3068 * \ / "-s ours", so took the version from I. X is
3069 * `-*A--' TREESAME to I and !TREESAME to A.
3070 *
3071 * Default log from X would produce "I". Without this check,
3072 * --full-history --simplify-merges would produce "I-A-X", showing
3073 * the merge commit X and that it changed A, but not making clear that
3074 * it had just taken the I version. With this check, the topology above
3075 * is retained.
3076 *
3077 * Note that it is possible that the simplification chooses a different
3078 * TREESAME parent from the default, in which case this test doesn't
3079 * activate, and we _do_ drop the default parent. Example:
3080 *
3081 * I------X A modified the file, but it was reverted in B,
3082 * \ / meaning mainline merge X is TREESAME to both
3083 * *A-*B parents.
3084 *
3085 * Default log would produce "I" by following the first parent;
3086 * --full-history --simplify-merges will produce "I-A-B". But this is a
3087 * reasonable result - it presents a logical full history leading from
3088 * I to X, and X is not an important merge.
3089 */
3090 if (!unmarked && marked) {
3091 marked->object.flags &= ~TMP_MARK;
3092 return 1;
3093 }
3094
3095 return 0;
3096}
3097
Kevin Braceyd0af6632013-05-16 18:32:34 +03003098static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
3099{
3100 struct commit_list **pp, *p;
3101 int nth_parent, removed = 0;
3102
3103 pp = &commit->parents;
3104 nth_parent = 0;
3105 while ((p = *pp) != NULL) {
3106 struct commit *parent = p->item;
3107 if (parent->object.flags & TMP_MARK) {
3108 parent->object.flags &= ~TMP_MARK;
3109 *pp = p->next;
3110 free(p);
3111 removed++;
3112 compact_treesame(revs, commit, nth_parent);
3113 continue;
3114 }
3115 pp = &p->next;
3116 nth_parent++;
3117 }
3118
3119 /* Removing parents can only increase TREESAMEness */
3120 if (removed && !(commit->object.flags & TREESAME))
3121 update_treesame(revs, commit);
3122
3123 return nth_parent;
3124}
3125
Junio C Hamanofaf01562008-08-14 10:59:44 -07003126static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)
Junio C Hamano6546b592008-07-31 01:17:41 -07003127{
3128 struct commit_list *p;
Kevin Bracey4d826602013-05-16 18:32:39 +03003129 struct commit *parent;
Junio C Hamanofaf01562008-08-14 10:59:44 -07003130 struct merge_simplify_state *st, *pst;
Junio C Hamano6546b592008-07-31 01:17:41 -07003131 int cnt;
3132
Junio C Hamanofaf01562008-08-14 10:59:44 -07003133 st = locate_simplify_state(revs, commit);
3134
Junio C Hamano6546b592008-07-31 01:17:41 -07003135 /*
Junio C Hamano6546b592008-07-31 01:17:41 -07003136 * Have we handled this one?
3137 */
Junio C Hamanofaf01562008-08-14 10:59:44 -07003138 if (st->simplified)
Junio C Hamano6546b592008-07-31 01:17:41 -07003139 return tail;
3140
3141 /*
3142 * An UNINTERESTING commit simplifies to itself, so does a
3143 * root commit. We do not rewrite parents of such commit
3144 * anyway.
3145 */
3146 if ((commit->object.flags & UNINTERESTING) || !commit->parents) {
Junio C Hamanofaf01562008-08-14 10:59:44 -07003147 st->simplified = commit;
Junio C Hamano6546b592008-07-31 01:17:41 -07003148 return tail;
3149 }
3150
3151 /*
Junio C Hamano6e513ba2012-06-08 14:56:03 -07003152 * Do we know what commit all of our parents that matter
3153 * should be rewritten to? Otherwise we are not ready to
3154 * rewrite this one yet.
Junio C Hamano6546b592008-07-31 01:17:41 -07003155 */
3156 for (cnt = 0, p = commit->parents; p; p = p->next) {
Junio C Hamanofaf01562008-08-14 10:59:44 -07003157 pst = locate_simplify_state(revs, p->item);
3158 if (!pst->simplified) {
Junio C Hamano6546b592008-07-31 01:17:41 -07003159 tail = &commit_list_insert(p->item, tail)->next;
3160 cnt++;
3161 }
Junio C Hamano6e513ba2012-06-08 14:56:03 -07003162 if (revs->first_parent_only)
3163 break;
Junio C Hamano6546b592008-07-31 01:17:41 -07003164 }
Junio C Hamano53030f82008-08-18 00:37:34 -07003165 if (cnt) {
3166 tail = &commit_list_insert(commit, tail)->next;
Junio C Hamano6546b592008-07-31 01:17:41 -07003167 return tail;
Junio C Hamano53030f82008-08-18 00:37:34 -07003168 }
Junio C Hamano6546b592008-07-31 01:17:41 -07003169
3170 /*
Kevin Braceyd0af6632013-05-16 18:32:34 +03003171 * Rewrite our list of parents. Note that this cannot
3172 * affect our TREESAME flags in any way - a commit is
3173 * always TREESAME to its simplification.
Junio C Hamano6546b592008-07-31 01:17:41 -07003174 */
Junio C Hamanofaf01562008-08-14 10:59:44 -07003175 for (p = commit->parents; p; p = p->next) {
3176 pst = locate_simplify_state(revs, p->item);
3177 p->item = pst->simplified;
Junio C Hamano6e513ba2012-06-08 14:56:03 -07003178 if (revs->first_parent_only)
3179 break;
Junio C Hamanofaf01562008-08-14 10:59:44 -07003180 }
Junio C Hamano4b7f53d2013-01-17 14:23:03 -08003181
Junio C Hamano0290bf12013-04-08 13:10:27 -07003182 if (revs->first_parent_only)
Junio C Hamano6e513ba2012-06-08 14:56:03 -07003183 cnt = 1;
Junio C Hamano0290bf12013-04-08 13:10:27 -07003184 else
Kevin Braceyd0af6632013-05-16 18:32:34 +03003185 cnt = remove_duplicate_parents(revs, commit);
Junio C Hamano6546b592008-07-31 01:17:41 -07003186
3187 /*
3188 * It is possible that we are a merge and one side branch
3189 * does not have any commit that touches the given paths;
Kevin Braceyd0af6632013-05-16 18:32:34 +03003190 * in such a case, the immediate parent from that branch
3191 * will be rewritten to be the merge base.
Junio C Hamano6546b592008-07-31 01:17:41 -07003192 *
3193 * o----X X: the commit we are looking at;
3194 * / / o: a commit that touches the paths;
3195 * ---o----'
3196 *
Kevin Bracey143f1ea2013-05-16 18:32:37 +03003197 * Further, a merge of an independent branch that doesn't
3198 * touch the path will reduce to a treesame root parent:
3199 *
3200 * ----o----X X: the commit we are looking at;
3201 * / o: a commit that touches the paths;
3202 * r r: a root commit not touching the paths
3203 *
3204 * Detect and simplify both cases.
Junio C Hamano6546b592008-07-31 01:17:41 -07003205 */
3206 if (1 < cnt) {
Jeff King91633992019-03-20 04:13:36 -04003207 int marked = mark_redundant_parents(commit);
3208 marked += mark_treesame_root_parents(commit);
Kevin Braceyd0af6632013-05-16 18:32:34 +03003209 if (marked)
Kevin Bracey9c129ea2013-05-16 18:32:36 +03003210 marked -= leave_one_treesame_to_parent(revs, commit);
3211 if (marked)
Kevin Braceyd0af6632013-05-16 18:32:34 +03003212 cnt = remove_marked_parents(revs, commit);
Junio C Hamano6546b592008-07-31 01:17:41 -07003213 }
3214
3215 /*
3216 * A commit simplifies to itself if it is a root, if it is
3217 * UNINTERESTING, if it touches the given paths, or if it is a
Kevin Bracey4d826602013-05-16 18:32:39 +03003218 * merge and its parents don't simplify to one relevant commit
Junio C Hamano6546b592008-07-31 01:17:41 -07003219 * (the first two cases are already handled at the beginning of
3220 * this function).
3221 *
Kevin Bracey4d826602013-05-16 18:32:39 +03003222 * Otherwise, it simplifies to what its sole relevant parent
3223 * simplifies to.
Junio C Hamano6546b592008-07-31 01:17:41 -07003224 */
3225 if (!cnt ||
3226 (commit->object.flags & UNINTERESTING) ||
3227 !(commit->object.flags & TREESAME) ||
Derrick Stolee8d049e12020-04-10 12:19:43 +00003228 (parent = one_relevant_parent(revs, commit->parents)) == NULL ||
3229 (revs->show_pulls && (commit->object.flags & PULL_MERGE)))
Junio C Hamanofaf01562008-08-14 10:59:44 -07003230 st->simplified = commit;
3231 else {
Kevin Bracey4d826602013-05-16 18:32:39 +03003232 pst = locate_simplify_state(revs, parent);
Junio C Hamanofaf01562008-08-14 10:59:44 -07003233 st->simplified = pst->simplified;
3234 }
Junio C Hamano6546b592008-07-31 01:17:41 -07003235 return tail;
3236}
3237
3238static void simplify_merges(struct rev_info *revs)
3239{
Junio C Hamanoab9d75a2012-06-08 14:50:22 -07003240 struct commit_list *list, *next;
Junio C Hamano6546b592008-07-31 01:17:41 -07003241 struct commit_list *yet_to_do, **tail;
Junio C Hamanoab9d75a2012-06-08 14:50:22 -07003242 struct commit *commit;
Junio C Hamano6546b592008-07-31 01:17:41 -07003243
Junio C Hamano5eac7392008-08-14 13:52:36 -07003244 if (!revs->prune)
3245 return;
Junio C Hamano65347032008-08-03 17:47:16 -07003246
Junio C Hamano6546b592008-07-31 01:17:41 -07003247 /* feed the list reversed */
3248 yet_to_do = NULL;
Junio C Hamanoab9d75a2012-06-08 14:50:22 -07003249 for (list = revs->commits; list; list = next) {
3250 commit = list->item;
3251 next = list->next;
3252 /*
3253 * Do not free(list) here yet; the original list
3254 * is used later in this function.
3255 */
3256 commit_list_insert(commit, &yet_to_do);
3257 }
Junio C Hamano6546b592008-07-31 01:17:41 -07003258 while (yet_to_do) {
3259 list = yet_to_do;
3260 yet_to_do = NULL;
3261 tail = &yet_to_do;
3262 while (list) {
René Scharfee510ab82015-10-24 18:21:31 +02003263 commit = pop_commit(&list);
Junio C Hamanofaf01562008-08-14 10:59:44 -07003264 tail = simplify_one(revs, commit, tail);
Junio C Hamano6546b592008-07-31 01:17:41 -07003265 }
3266 }
3267
3268 /* clean up the result, removing the simplified ones */
3269 list = revs->commits;
3270 revs->commits = NULL;
3271 tail = &revs->commits;
3272 while (list) {
Junio C Hamanofaf01562008-08-14 10:59:44 -07003273 struct merge_simplify_state *st;
Junio C Hamanoab9d75a2012-06-08 14:50:22 -07003274
René Scharfee510ab82015-10-24 18:21:31 +02003275 commit = pop_commit(&list);
Junio C Hamanofaf01562008-08-14 10:59:44 -07003276 st = locate_simplify_state(revs, commit);
3277 if (st->simplified == commit)
Junio C Hamano6546b592008-07-31 01:17:41 -07003278 tail = &commit_list_insert(commit, tail)->next;
3279 }
Junio C Hamano6546b592008-07-31 01:17:41 -07003280}
3281
Junio C Hamanof35f5602008-04-03 02:12:06 -07003282static void set_children(struct rev_info *revs)
3283{
3284 struct commit_list *l;
3285 for (l = revs->commits; l; l = l->next) {
3286 struct commit *commit = l->item;
3287 struct commit_list *p;
3288
3289 for (p = commit->parents; p; p = p->next)
3290 add_child(revs, p->item, commit);
3291 }
3292}
3293
Heiko Voigtbcc0a3e2012-03-29 09:21:21 +02003294void reset_revision_walk(void)
3295{
Mike Hommeyffa1f282019-11-22 17:37:03 +09003296 clear_object_flags(SEEN | ADDED | SHOWN | TOPO_WALK_EXPLORED | TOPO_WALK_INDEGREE);
Heiko Voigtbcc0a3e2012-03-29 09:21:21 +02003297}
3298
Jonathan Tandf11e192017-12-08 15:27:15 +00003299static int mark_uninteresting(const struct object_id *oid,
3300 struct packed_git *pack,
3301 uint32_t pos,
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02003302 void *cb)
Jonathan Tandf11e192017-12-08 15:27:15 +00003303{
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02003304 struct rev_info *revs = cb;
Jeff Kingc1fa9512021-04-13 03:17:48 -04003305 struct object *o = lookup_unknown_object(revs->repo, oid);
Jonathan Tandf11e192017-12-08 15:27:15 +00003306 o->flags |= UNINTERESTING | SEEN;
3307 return 0;
3308}
3309
Derrick Stoleeb4542412018-11-01 13:46:22 +00003310define_commit_slab(indegree_slab, int);
3311define_commit_slab(author_date_slab, timestamp_t);
3312
3313struct topo_walk_info {
Abhishek Kumard7f92782021-01-16 18:11:13 +00003314 timestamp_t min_generation;
Derrick Stoleeb4542412018-11-01 13:46:22 +00003315 struct prio_queue explore_queue;
3316 struct prio_queue indegree_queue;
3317 struct prio_queue topo_queue;
3318 struct indegree_slab indegree;
3319 struct author_date_slab author_date;
3320};
3321
Derrick Stolee90b666d2020-12-30 04:31:53 +00003322static int topo_walk_atexit_registered;
3323static unsigned int count_explore_walked;
3324static unsigned int count_indegree_walked;
3325static unsigned int count_topo_walked;
3326
3327static void trace2_topo_walk_statistics_atexit(void)
3328{
3329 struct json_writer jw = JSON_WRITER_INIT;
3330
3331 jw_object_begin(&jw, 0);
3332 jw_object_intmax(&jw, "count_explore_walked", count_explore_walked);
3333 jw_object_intmax(&jw, "count_indegree_walked", count_indegree_walked);
3334 jw_object_intmax(&jw, "count_topo_walked", count_topo_walked);
3335 jw_end(&jw);
3336
3337 trace2_data_json("topo_walk", the_repository, "statistics", &jw);
3338
3339 jw_release(&jw);
3340}
3341
Derrick Stoleeb4542412018-11-01 13:46:22 +00003342static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag)
3343{
3344 if (c->object.flags & flag)
3345 return;
3346
3347 c->object.flags |= flag;
3348 prio_queue_put(q, c);
3349}
3350
3351static void explore_walk_step(struct rev_info *revs)
3352{
3353 struct topo_walk_info *info = revs->topo_walk_info;
3354 struct commit_list *p;
3355 struct commit *c = prio_queue_get(&info->explore_queue);
3356
3357 if (!c)
3358 return;
3359
Michael Forneyea3f7e52020-06-23 13:56:58 -07003360 if (repo_parse_commit_gently(revs->repo, c, 1) < 0)
Derrick Stoleeb4542412018-11-01 13:46:22 +00003361 return;
3362
Derrick Stolee90b666d2020-12-30 04:31:53 +00003363 count_explore_walked++;
3364
Derrick Stoleeb4542412018-11-01 13:46:22 +00003365 if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
3366 record_author_date(&info->author_date, c);
3367
3368 if (revs->max_age != -1 && (c->date < revs->max_age))
3369 c->object.flags |= UNINTERESTING;
3370
3371 if (process_parents(revs, c, NULL, NULL) < 0)
3372 return;
3373
3374 if (c->object.flags & UNINTERESTING)
Jerry Zhang9d505b72022-01-11 13:39:41 -08003375 mark_parents_uninteresting(revs, c);
Derrick Stoleeb4542412018-11-01 13:46:22 +00003376
3377 for (p = c->parents; p; p = p->next)
3378 test_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);
3379}
3380
3381static void explore_to_depth(struct rev_info *revs,
Abhishek Kumard7f92782021-01-16 18:11:13 +00003382 timestamp_t gen_cutoff)
Derrick Stoleeb4542412018-11-01 13:46:22 +00003383{
3384 struct topo_walk_info *info = revs->topo_walk_info;
3385 struct commit *c;
3386 while ((c = prio_queue_peek(&info->explore_queue)) &&
Abhishek Kumarc49c82a2020-06-17 14:44:10 +05303387 commit_graph_generation(c) >= gen_cutoff)
Derrick Stoleeb4542412018-11-01 13:46:22 +00003388 explore_walk_step(revs);
3389}
3390
3391static void indegree_walk_step(struct rev_info *revs)
3392{
3393 struct commit_list *p;
3394 struct topo_walk_info *info = revs->topo_walk_info;
3395 struct commit *c = prio_queue_get(&info->indegree_queue);
3396
3397 if (!c)
3398 return;
3399
Michael Forneyea3f7e52020-06-23 13:56:58 -07003400 if (repo_parse_commit_gently(revs->repo, c, 1) < 0)
Derrick Stoleeb4542412018-11-01 13:46:22 +00003401 return;
3402
Derrick Stolee90b666d2020-12-30 04:31:53 +00003403 count_indegree_walked++;
3404
Abhishek Kumarc49c82a2020-06-17 14:44:10 +05303405 explore_to_depth(revs, commit_graph_generation(c));
Derrick Stoleeb4542412018-11-01 13:46:22 +00003406
3407 for (p = c->parents; p; p = p->next) {
3408 struct commit *parent = p->item;
3409 int *pi = indegree_slab_at(&info->indegree, parent);
3410
Abhishek Kumar2f9bbb62021-01-16 18:11:09 +00003411 if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
3412 return;
3413
Derrick Stoleeb4542412018-11-01 13:46:22 +00003414 if (*pi)
3415 (*pi)++;
3416 else
3417 *pi = 2;
3418
3419 test_flag_and_insert(&info->indegree_queue, parent, TOPO_WALK_INDEGREE);
3420
3421 if (revs->first_parent_only)
3422 return;
3423 }
3424}
3425
3426static void compute_indegrees_to_depth(struct rev_info *revs,
Abhishek Kumard7f92782021-01-16 18:11:13 +00003427 timestamp_t gen_cutoff)
Derrick Stoleeb4542412018-11-01 13:46:22 +00003428{
3429 struct topo_walk_info *info = revs->topo_walk_info;
3430 struct commit *c;
3431 while ((c = prio_queue_peek(&info->indegree_queue)) &&
Abhishek Kumarc49c82a2020-06-17 14:44:10 +05303432 commit_graph_generation(c) >= gen_cutoff)
Derrick Stoleeb4542412018-11-01 13:46:22 +00003433 indegree_walk_step(revs);
3434}
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003435
Mike Hommey0aa0c2b2019-11-22 17:37:04 +09003436static void reset_topo_walk(struct rev_info *revs)
3437{
3438 struct topo_walk_info *info = revs->topo_walk_info;
3439
3440 clear_prio_queue(&info->explore_queue);
3441 clear_prio_queue(&info->indegree_queue);
3442 clear_prio_queue(&info->topo_queue);
3443 clear_indegree_slab(&info->indegree);
3444 clear_author_date_slab(&info->author_date);
3445
3446 FREE_AND_NULL(revs->topo_walk_info);
3447}
3448
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003449static void init_topo_walk(struct rev_info *revs)
3450{
3451 struct topo_walk_info *info;
Derrick Stoleeb4542412018-11-01 13:46:22 +00003452 struct commit_list *list;
Mike Hommey0aa0c2b2019-11-22 17:37:04 +09003453 if (revs->topo_walk_info)
3454 reset_topo_walk(revs);
3455
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003456 revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info));
3457 info = revs->topo_walk_info;
3458 memset(info, 0, sizeof(struct topo_walk_info));
3459
Derrick Stoleeb4542412018-11-01 13:46:22 +00003460 init_indegree_slab(&info->indegree);
3461 memset(&info->explore_queue, 0, sizeof(info->explore_queue));
3462 memset(&info->indegree_queue, 0, sizeof(info->indegree_queue));
3463 memset(&info->topo_queue, 0, sizeof(info->topo_queue));
3464
3465 switch (revs->sort_order) {
3466 default: /* REV_SORT_IN_GRAPH_ORDER */
3467 info->topo_queue.compare = NULL;
3468 break;
3469 case REV_SORT_BY_COMMIT_DATE:
3470 info->topo_queue.compare = compare_commits_by_commit_date;
3471 break;
3472 case REV_SORT_BY_AUTHOR_DATE:
3473 init_author_date_slab(&info->author_date);
3474 info->topo_queue.compare = compare_commits_by_author_date;
3475 info->topo_queue.cb_data = &info->author_date;
3476 break;
3477 }
3478
3479 info->explore_queue.compare = compare_commits_by_gen_then_commit_date;
3480 info->indegree_queue.compare = compare_commits_by_gen_then_commit_date;
3481
3482 info->min_generation = GENERATION_NUMBER_INFINITY;
3483 for (list = revs->commits; list; list = list->next) {
3484 struct commit *c = list->item;
Abhishek Kumard7f92782021-01-16 18:11:13 +00003485 timestamp_t generation;
Derrick Stoleeb4542412018-11-01 13:46:22 +00003486
Michael Forneyea3f7e52020-06-23 13:56:58 -07003487 if (repo_parse_commit_gently(revs->repo, c, 1))
Derrick Stoleeb4542412018-11-01 13:46:22 +00003488 continue;
3489
3490 test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);
3491 test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);
3492
Abhishek Kumarc752ad02020-06-17 14:44:11 +05303493 generation = commit_graph_generation(c);
3494 if (generation < info->min_generation)
3495 info->min_generation = generation;
Derrick Stoleeb4542412018-11-01 13:46:22 +00003496
3497 *(indegree_slab_at(&info->indegree, c)) = 1;
3498
3499 if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
3500 record_author_date(&info->author_date, c);
3501 }
3502 compute_indegrees_to_depth(revs, info->min_generation);
3503
3504 for (list = revs->commits; list; list = list->next) {
3505 struct commit *c = list->item;
3506
3507 if (*(indegree_slab_at(&info->indegree, c)) == 1)
3508 prio_queue_put(&info->topo_queue, c);
3509 }
3510
3511 /*
3512 * This is unfortunate; the initial tips need to be shown
3513 * in the order given from the revision traversal machinery.
3514 */
3515 if (revs->sort_order == REV_SORT_IN_GRAPH_ORDER)
3516 prio_queue_reverse(&info->topo_queue);
Derrick Stolee90b666d2020-12-30 04:31:53 +00003517
3518 if (trace2_is_enabled() && !topo_walk_atexit_registered) {
3519 atexit(trace2_topo_walk_statistics_atexit);
3520 topo_walk_atexit_registered = 1;
3521 }
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003522}
3523
3524static struct commit *next_topo_commit(struct rev_info *revs)
3525{
Derrick Stoleeb4542412018-11-01 13:46:22 +00003526 struct commit *c;
3527 struct topo_walk_info *info = revs->topo_walk_info;
3528
3529 /* pop next off of topo_queue */
3530 c = prio_queue_get(&info->topo_queue);
3531
3532 if (c)
3533 *(indegree_slab_at(&info->indegree, c)) = 0;
3534
3535 return c;
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003536}
3537
3538static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
3539{
Derrick Stoleeb4542412018-11-01 13:46:22 +00003540 struct commit_list *p;
3541 struct topo_walk_info *info = revs->topo_walk_info;
3542 if (process_parents(revs, commit, NULL, NULL) < 0) {
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003543 if (!revs->ignore_missing_links)
3544 die("Failed to traverse parents of commit %s",
3545 oid_to_hex(&commit->object.oid));
3546 }
Derrick Stoleeb4542412018-11-01 13:46:22 +00003547
Derrick Stolee90b666d2020-12-30 04:31:53 +00003548 count_topo_walked++;
3549
Derrick Stoleeb4542412018-11-01 13:46:22 +00003550 for (p = commit->parents; p; p = p->next) {
3551 struct commit *parent = p->item;
3552 int *pi;
Abhishek Kumard7f92782021-01-16 18:11:13 +00003553 timestamp_t generation;
Derrick Stoleeb4542412018-11-01 13:46:22 +00003554
Derrick Stolee1d8e31a2019-05-21 09:59:53 -04003555 if (parent->object.flags & UNINTERESTING)
3556 continue;
3557
Michael Forneyea3f7e52020-06-23 13:56:58 -07003558 if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
Derrick Stoleeb4542412018-11-01 13:46:22 +00003559 continue;
3560
Abhishek Kumarc752ad02020-06-17 14:44:11 +05303561 generation = commit_graph_generation(parent);
3562 if (generation < info->min_generation) {
3563 info->min_generation = generation;
Derrick Stoleeb4542412018-11-01 13:46:22 +00003564 compute_indegrees_to_depth(revs, info->min_generation);
3565 }
3566
3567 pi = indegree_slab_at(&info->indegree, parent);
3568
3569 (*pi)--;
3570 if (*pi == 1)
3571 prio_queue_put(&info->topo_queue, parent);
3572
3573 if (revs->first_parent_only)
3574 return;
3575 }
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003576}
3577
Alex Riesencc0e6c52007-05-04 23:54:57 +02003578int prepare_revision_walk(struct rev_info *revs)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08003579{
Jeff King1da1e072014-10-15 18:35:12 -04003580 int i;
3581 struct object_array old_pending;
René Scharfe2e7da8e2012-04-25 22:35:41 +02003582 struct commit_list **next = &revs->commits;
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07003583
Jeff King1da1e072014-10-15 18:35:12 -04003584 memcpy(&old_pending, &revs->pending, sizeof(old_pending));
Linus Torvalds1f1e8952006-06-19 17:42:35 -07003585 revs->pending.nr = 0;
3586 revs->pending.alloc = 0;
3587 revs->pending.objects = NULL;
Jeff King1da1e072014-10-15 18:35:12 -04003588 for (i = 0; i < old_pending.nr; i++) {
3589 struct object_array_entry *e = old_pending.objects + i;
Jeff King20739492014-10-15 18:43:19 -04003590 struct commit *commit = handle_commit(revs, e);
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07003591 if (commit) {
3592 if (!(commit->object.flags & SEEN)) {
3593 commit->object.flags |= SEEN;
René Scharfe2e7da8e2012-04-25 22:35:41 +02003594 next = commit_list_append(commit, next);
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07003595 }
3596 }
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07003597 }
René Scharfef1230fb2017-12-25 18:47:51 +01003598 object_array_clear(&old_pending);
Linus Torvaldscd2bdc52006-04-14 16:52:13 -07003599
Kevin Braceyd0af6632013-05-16 18:32:34 +03003600 /* Signal whether we need per-parent treesame decoration */
Kevin Bracey4d826602013-05-16 18:32:39 +03003601 if (revs->simplify_merges ||
3602 (revs->limited && limiting_can_increase_treesame(revs)))
Kevin Braceyd0af6632013-05-16 18:32:34 +03003603 revs->treesame.name = "treesame";
3604
Jonathan Tandf11e192017-12-08 15:27:15 +00003605 if (revs->exclude_promisor_objects) {
Nguyễn Thái Ngọc Duyb3c7eef2018-09-21 17:57:39 +02003606 for_each_packed_object(mark_uninteresting, revs,
Jonathan Tandf11e192017-12-08 15:27:15 +00003607 FOR_EACH_OBJECT_PROMISOR_ONLY);
3608 }
3609
Derrick Stoleef32dde82020-05-11 11:56:19 +00003610 if (!revs->reflog_info)
Garima Singha56b9462020-04-06 16:59:52 +00003611 prepare_to_use_bloom_filter(revs);
Patrick Steinhardt29ef1f22021-08-05 13:25:24 +02003612 if (!revs->unsorted_input)
Martin von Zweigbergkca92e592012-08-28 23:15:54 -07003613 commit_list_sort_by_date(&revs->commits);
Linus Torvaldsba1d4502006-04-15 12:09:56 -07003614 if (revs->no_walk)
Alex Riesencc0e6c52007-05-04 23:54:57 +02003615 return 0;
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003616 if (revs->limited) {
Alex Riesencc0e6c52007-05-04 23:54:57 +02003617 if (limit_list(revs) < 0)
3618 return -1;
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00003619 if (revs->topo_order)
3620 sort_in_topological_order(&revs->commits, revs->sort_order);
3621 } else if (revs->topo_order)
3622 init_topo_walk(revs);
SZEDER Gábor3cb9d2b2020-05-11 11:56:17 +00003623 if (revs->line_level_traverse && want_ancestry(revs))
3624 /*
3625 * At the moment we can only do line-level log with parent
3626 * rewriting by performing this expensive pre-filtering step.
3627 * If parent rewriting is not requested, then we rather
3628 * perform the line-level log filtering during the regular
3629 * history traversal.
3630 */
Thomas Rast12da1d12013-03-28 17:47:32 +01003631 line_log_filter(revs);
Junio C Hamano6546b592008-07-31 01:17:41 -07003632 if (revs->simplify_merges)
3633 simplify_merges(revs);
Junio C Hamanof35f5602008-04-03 02:12:06 -07003634 if (revs->children.name)
3635 set_children(revs);
Garima Singha56b9462020-04-06 16:59:52 +00003636
Alex Riesencc0e6c52007-05-04 23:54:57 +02003637 return 0;
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08003638}
3639
Jeff King8320b1d2019-04-03 21:41:09 -04003640static enum rewrite_result rewrite_one_1(struct rev_info *revs,
3641 struct commit **pp,
3642 struct prio_queue *queue)
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08003643{
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003644 for (;;) {
3645 struct commit *p = *pp;
Linus Torvalds3381c792006-04-08 17:05:58 -07003646 if (!revs->limited)
Jeff King8320b1d2019-04-03 21:41:09 -04003647 if (process_parents(revs, p, NULL, queue) < 0)
Alex Riesencc0e6c52007-05-04 23:54:57 +02003648 return rewrite_one_error;
Linus Torvalds7dc0fe32007-11-12 23:16:08 -08003649 if (p->object.flags & UNINTERESTING)
3650 return rewrite_one_ok;
3651 if (!(p->object.flags & TREESAME))
Alex Riesencc0e6c52007-05-04 23:54:57 +02003652 return rewrite_one_ok;
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003653 if (!p->parents)
Alex Riesencc0e6c52007-05-04 23:54:57 +02003654 return rewrite_one_noparents;
Kevin Bracey4d826602013-05-16 18:32:39 +03003655 if ((p = one_relevant_parent(revs, p->parents)) == NULL)
3656 return rewrite_one_ok;
3657 *pp = p;
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003658 }
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08003659}
3660
Jeff King8320b1d2019-04-03 21:41:09 -04003661static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)
3662{
3663 while (q->nr) {
3664 struct commit *item = prio_queue_peek(q);
3665 struct commit_list *p = *list;
3666
3667 if (p && p->item->date >= item->date)
3668 list = &p->next;
3669 else {
3670 p = commit_list_insert(item, list);
3671 list = &p->next; /* skip newly added item */
3672 prio_queue_get(q); /* pop item */
3673 }
3674 }
3675}
3676
3677static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)
3678{
3679 struct prio_queue queue = { compare_commits_by_commit_date };
3680 enum rewrite_result ret = rewrite_one_1(revs, pp, &queue);
3681 merge_queue_into_list(&queue, &revs->commits);
3682 clear_prio_queue(&queue);
3683 return ret;
3684}
3685
Bo Yangc7edcae2013-03-28 17:47:31 +01003686int rewrite_parents(struct rev_info *revs, struct commit *commit,
3687 rewrite_parent_fn_t rewrite_parent)
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003688{
3689 struct commit_list **pp = &commit->parents;
3690 while (*pp) {
3691 struct commit_list *parent = *pp;
Bo Yangc7edcae2013-03-28 17:47:31 +01003692 switch (rewrite_parent(revs, &parent->item)) {
Alex Riesencc0e6c52007-05-04 23:54:57 +02003693 case rewrite_one_ok:
3694 break;
3695 case rewrite_one_noparents:
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003696 *pp = parent->next;
3697 continue;
Alex Riesencc0e6c52007-05-04 23:54:57 +02003698 case rewrite_one_error:
3699 return -1;
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003700 }
3701 pp = &parent->next;
3702 }
Kevin Braceyd0af6632013-05-16 18:32:34 +03003703 remove_duplicate_parents(revs, commit);
Alex Riesencc0e6c52007-05-04 23:54:57 +02003704 return 0;
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003705}
Linus Torvaldsa4a88b22006-02-28 11:24:00 -08003706
Antoine Pelissed72fbe82013-01-05 22:26:45 +01003707static int commit_rewrite_person(struct strbuf *buf, const char *what, struct string_list *mailmap)
3708{
3709 char *person, *endp;
3710 size_t len, namelen, maillen;
3711 const char *name;
3712 const char *mail;
3713 struct ident_split ident;
3714
3715 person = strstr(buf->buf, what);
3716 if (!person)
3717 return 0;
3718
3719 person += strlen(what);
3720 endp = strchr(person, '\n');
3721 if (!endp)
3722 return 0;
3723
3724 len = endp - person;
3725
3726 if (split_ident_line(&ident, person, len))
3727 return 0;
3728
3729 mail = ident.mail_begin;
3730 maillen = ident.mail_end - ident.mail_begin;
3731 name = ident.name_begin;
3732 namelen = ident.name_end - ident.name_begin;
3733
3734 if (map_user(mailmap, &mail, &maillen, &name, &namelen)) {
3735 struct strbuf namemail = STRBUF_INIT;
3736
3737 strbuf_addf(&namemail, "%.*s <%.*s>",
3738 (int)namelen, name, (int)maillen, mail);
3739
3740 strbuf_splice(buf, ident.name_begin - buf->buf,
3741 ident.mail_end - ident.name_begin + 1,
3742 namemail.buf, namemail.len);
3743
3744 strbuf_release(&namemail);
3745
3746 return 1;
3747 }
3748
3749 return 0;
3750}
3751
Junio C Hamano8ecae9b2006-09-17 15:43:40 -07003752static int commit_match(struct commit *commit, struct rev_info *opt)
3753{
Nguyễn Thái Ngọc Duy72fd13f2012-09-29 11:41:28 +07003754 int retval;
Jeff King04deccd2013-02-11 15:59:58 -05003755 const char *encoding;
Jeff Kingb000c592014-06-10 17:39:30 -04003756 const char *message;
Nguyễn Thái Ngọc Duy72fd13f2012-09-29 11:41:28 +07003757 struct strbuf buf = STRBUF_INIT;
Jeff King04deccd2013-02-11 15:59:58 -05003758
Junio C Hamano80235ba2010-01-17 20:09:06 -08003759 if (!opt->grep_filter.pattern_list && !opt->grep_filter.header_list)
Junio C Hamano8ecae9b2006-09-17 15:43:40 -07003760 return 1;
Junio C Hamanobaa63782012-09-29 11:59:52 -07003761
3762 /* Prepend "fake" headers as needed */
3763 if (opt->grep_filter.use_reflog_filter) {
Nguyễn Thái Ngọc Duy72fd13f2012-09-29 11:41:28 +07003764 strbuf_addstr(&buf, "reflog ");
3765 get_reflog_message(&buf, opt->reflog_info);
3766 strbuf_addch(&buf, '\n');
Nguyễn Thái Ngọc Duy72fd13f2012-09-29 11:41:28 +07003767 }
Junio C Hamanobaa63782012-09-29 11:59:52 -07003768
Jeff King04deccd2013-02-11 15:59:58 -05003769 /*
3770 * We grep in the user's output encoding, under the assumption that it
3771 * is the encoding they are most likely to write their grep pattern
3772 * for. In addition, it means we will match the "notes" encoding below,
3773 * so we will not end up with a buffer that has two different encodings
3774 * in it.
3775 */
3776 encoding = get_log_output_encoding();
Nguyễn Thái Ngọc Duy5a10d232013-04-19 09:08:40 +10003777 message = logmsg_reencode(commit, NULL, encoding);
Jeff King04deccd2013-02-11 15:59:58 -05003778
Junio C Hamanobaa63782012-09-29 11:59:52 -07003779 /* Copy the commit to temporary if we are using "fake" headers */
3780 if (buf.len)
Jeff King04deccd2013-02-11 15:59:58 -05003781 strbuf_addstr(&buf, message);
Junio C Hamanobaa63782012-09-29 11:59:52 -07003782
Junio C Hamanodf874fa2013-01-08 00:02:49 -08003783 if (opt->grep_filter.header_list && opt->mailmap) {
Antoine Pelissed72fbe82013-01-05 22:26:45 +01003784 if (!buf.len)
Jeff King04deccd2013-02-11 15:59:58 -05003785 strbuf_addstr(&buf, message);
Antoine Pelissed72fbe82013-01-05 22:26:45 +01003786
3787 commit_rewrite_person(&buf, "\nauthor ", opt->mailmap);
3788 commit_rewrite_person(&buf, "\ncommitter ", opt->mailmap);
3789 }
3790
Nguyễn Thái Ngọc Duy38cfe912012-09-29 11:41:29 +07003791 /* Append "fake" message parts as needed */
3792 if (opt->show_notes) {
3793 if (!buf.len)
Jeff King04deccd2013-02-11 15:59:58 -05003794 strbuf_addstr(&buf, message);
brian m. carlsonfb61e4d2017-05-30 10:30:41 -07003795 format_display_notes(&commit->object.oid, &buf, encoding, 1);
Nguyễn Thái Ngọc Duy38cfe912012-09-29 11:41:29 +07003796 }
3797
Jeff Kingb000c592014-06-10 17:39:30 -04003798 /*
3799 * Find either in the original commit message, or in the temporary.
3800 * Note that we cast away the constness of "message" here. It is
3801 * const because it may come from the cached commit buffer. That's OK,
3802 * because we know that it is modifiable heap memory, and that while
3803 * grep_buffer may modify it for speed, it will restore any
3804 * changes before returning.
3805 */
Nguyễn Thái Ngọc Duy72fd13f2012-09-29 11:41:28 +07003806 if (buf.len)
3807 retval = grep_buffer(&opt->grep_filter, buf.buf, buf.len);
3808 else
3809 retval = grep_buffer(&opt->grep_filter,
Jeff Kingb000c592014-06-10 17:39:30 -04003810 (char *)message, strlen(message));
Nguyễn Thái Ngọc Duy72fd13f2012-09-29 11:41:28 +07003811 strbuf_release(&buf);
Jeff Kingb66103c2014-06-10 17:41:39 -04003812 unuse_commit_buffer(commit, message);
René Scharfe794c0002021-12-17 17:48:49 +01003813 return retval;
Junio C Hamano8ecae9b2006-09-17 15:43:40 -07003814}
3815
Thomas Rast53d00b32013-07-31 22:13:20 +02003816static inline int want_ancestry(const struct rev_info *revs)
Junio C Hamanof35f5602008-04-03 02:12:06 -07003817{
Junio C Hamano8bb65882008-07-08 15:25:44 -07003818 return (revs->rewrite_parents || revs->children.name);
Junio C Hamanof35f5602008-04-03 02:12:06 -07003819}
3820
Jeff Kingde239442017-07-07 05:16:21 -04003821/*
3822 * Return a timestamp to be used for --since/--until comparisons for this
3823 * commit, based on the revision options.
3824 */
3825static timestamp_t comparison_date(const struct rev_info *revs,
3826 struct commit *commit)
3827{
3828 return revs->reflog_info ?
3829 get_reflog_timestamp(revs->reflog_info) :
3830 commit->date;
3831}
3832
Adam Simpkinsbeb5af42009-08-18 19:34:33 -07003833enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit)
Linus Torvalds252a7c02007-11-04 12:12:05 -08003834{
3835 if (commit->object.flags & SHOWN)
3836 return commit_ignore;
brian m. carlson14c3c802018-05-02 00:25:33 +00003837 if (revs->unpacked && has_object_pack(&commit->object.oid))
Linus Torvalds252a7c02007-11-04 12:12:05 -08003838 return commit_ignore;
Taylor Blauc9fff002021-02-22 21:25:07 -05003839 if (revs->no_kept_objects) {
3840 if (has_object_kept_pack(&commit->object.oid,
3841 revs->keep_pack_cache_flags))
3842 return commit_ignore;
3843 }
Linus Torvalds252a7c02007-11-04 12:12:05 -08003844 if (commit->object.flags & UNINTERESTING)
3845 return commit_ignore;
SZEDER Gábor3cb9d2b2020-05-11 11:56:17 +00003846 if (revs->line_level_traverse && !want_ancestry(revs)) {
3847 /*
3848 * In case of line-level log with parent rewriting
3849 * prepare_revision_walk() already took care of all line-level
3850 * log filtering, and there is nothing left to do here.
3851 *
3852 * If parent rewriting was not requested, then this is the
3853 * place to perform the line-level log filtering. Notably,
3854 * this check, though expensive, must come before the other,
3855 * cheaper filtering conditions, because the tracked line
3856 * ranges must be adjusted even when the commit will end up
3857 * being ignored based on other conditions.
3858 */
3859 if (!line_log_process_ranges_arbitrary_commit(revs, commit))
3860 return commit_ignore;
3861 }
Jeff Kingde239442017-07-07 05:16:21 -04003862 if (revs->min_age != -1 &&
3863 comparison_date(revs, commit) > revs->min_age)
3864 return commit_ignore;
Michael J Gruberad5aeed2011-03-21 11:14:06 +01003865 if (revs->min_parents || (revs->max_parents >= 0)) {
Kevin Braceybf3418b2013-05-16 18:32:40 +03003866 int n = commit_list_count(commit->parents);
Michael J Gruberad5aeed2011-03-21 11:14:06 +01003867 if ((n < revs->min_parents) ||
3868 ((revs->max_parents >= 0) && (n > revs->max_parents)))
3869 return commit_ignore;
3870 }
Linus Torvalds252a7c02007-11-04 12:12:05 -08003871 if (!commit_match(commit, revs))
3872 return commit_ignore;
Linus Torvalds53b2c822007-11-05 13:22:34 -08003873 if (revs->prune && revs->dense) {
Linus Torvalds252a7c02007-11-04 12:12:05 -08003874 /* Commit without changes? */
Linus Torvalds7dc0fe32007-11-12 23:16:08 -08003875 if (commit->object.flags & TREESAME) {
Kevin Braceybf3418b2013-05-16 18:32:40 +03003876 int n;
3877 struct commit_list *p;
Linus Torvalds252a7c02007-11-04 12:12:05 -08003878 /* drop merges unless we want parenthood */
Junio C Hamanof35f5602008-04-03 02:12:06 -07003879 if (!want_ancestry(revs))
Linus Torvalds252a7c02007-11-04 12:12:05 -08003880 return commit_ignore;
Derrick Stolee8d049e12020-04-10 12:19:43 +00003881
3882 if (revs->show_pulls && (commit->object.flags & PULL_MERGE))
3883 return commit_show;
3884
Kevin Braceybf3418b2013-05-16 18:32:40 +03003885 /*
3886 * If we want ancestry, then need to keep any merges
3887 * between relevant commits to tie together topology.
3888 * For consistency with TREESAME and simplification
3889 * use "relevant" here rather than just INTERESTING,
3890 * to treat bottom commit(s) as part of the topology.
3891 */
3892 for (n = 0, p = commit->parents; p; p = p->next)
3893 if (relevant_commit(p->item))
3894 if (++n >= 2)
3895 return commit_show;
3896 return commit_ignore;
Linus Torvalds252a7c02007-11-04 12:12:05 -08003897 }
Linus Torvalds252a7c02007-11-04 12:12:05 -08003898 }
3899 return commit_show;
3900}
3901
Junio C Hamano0131c492015-01-14 14:49:24 -08003902define_commit_slab(saved_parents, struct commit_list *);
3903
3904#define EMPTY_PARENT_LIST ((struct commit_list *)-1)
3905
3906/*
3907 * You may only call save_parents() once per commit (this is checked
3908 * for non-root commits).
3909 */
3910static void save_parents(struct rev_info *revs, struct commit *commit)
3911{
3912 struct commit_list **pp;
3913
3914 if (!revs->saved_parents_slab) {
3915 revs->saved_parents_slab = xmalloc(sizeof(struct saved_parents));
3916 init_saved_parents(revs->saved_parents_slab);
3917 }
3918
3919 pp = saved_parents_at(revs->saved_parents_slab, commit);
3920
3921 /*
3922 * When walking with reflogs, we may visit the same commit
3923 * several times: once for each appearance in the reflog.
3924 *
3925 * In this case, save_parents() will be called multiple times.
3926 * We want to keep only the first set of parents. We need to
3927 * store a sentinel value for an empty (i.e., NULL) parent
3928 * list to distinguish it from a not-yet-saved list, however.
3929 */
3930 if (*pp)
3931 return;
3932 if (commit->parents)
3933 *pp = copy_commit_list(commit->parents);
3934 else
3935 *pp = EMPTY_PARENT_LIST;
3936}
3937
3938static void free_saved_parents(struct rev_info *revs)
3939{
3940 if (revs->saved_parents_slab)
3941 clear_saved_parents(revs->saved_parents_slab);
3942}
3943
3944struct commit_list *get_saved_parents(struct rev_info *revs, const struct commit *commit)
3945{
3946 struct commit_list *parents;
3947
3948 if (!revs->saved_parents_slab)
3949 return commit->parents;
3950
3951 parents = *saved_parents_at(revs->saved_parents_slab, commit);
3952 if (parents == EMPTY_PARENT_LIST)
3953 return NULL;
3954 return parents;
3955}
3956
Adam Simpkinsbeb5af42009-08-18 19:34:33 -07003957enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)
3958{
3959 enum commit_action action = get_commit_action(revs, commit);
3960
3961 if (action == commit_show &&
Adam Simpkinsbeb5af42009-08-18 19:34:33 -07003962 revs->prune && revs->dense && want_ancestry(revs)) {
Thomas Rast53d00b32013-07-31 22:13:20 +02003963 /*
3964 * --full-diff on simplified parents is no good: it
3965 * will show spurious changes from the commits that
3966 * were elided. So we save the parents on the side
3967 * when --full-diff is in effect.
3968 */
3969 if (revs->full_diff)
3970 save_parents(revs, commit);
Bo Yangc7edcae2013-03-28 17:47:31 +01003971 if (rewrite_parents(revs, commit, rewrite_one) < 0)
Adam Simpkinsbeb5af42009-08-18 19:34:33 -07003972 return commit_error;
3973 }
3974 return action;
3975}
3976
Nguyễn Thái Ngọc Duy1b32dec2014-03-25 20:23:27 +07003977static void track_linear(struct rev_info *revs, struct commit *commit)
3978{
3979 if (revs->track_first_time) {
3980 revs->linear = 1;
3981 revs->track_first_time = 0;
3982 } else {
3983 struct commit_list *p;
3984 for (p = revs->previous_parents; p; p = p->next)
3985 if (p->item == NULL || /* first commit */
Jeff King4a7e27e2018-08-28 17:22:40 -04003986 oideq(&p->item->object.oid, &commit->object.oid))
Nguyễn Thái Ngọc Duy1b32dec2014-03-25 20:23:27 +07003987 break;
3988 revs->linear = p != NULL;
3989 }
3990 if (revs->reverse) {
3991 if (revs->linear)
3992 commit->object.flags |= TRACK_LINEAR;
3993 }
3994 free_commit_list(revs->previous_parents);
3995 revs->previous_parents = copy_commit_list(commit->parents);
3996}
3997
Junio C Hamanod5db6c92006-12-19 18:25:32 -08003998static struct commit *get_revision_1(struct rev_info *revs)
Linus Torvalds765ac8e2006-02-28 15:07:20 -08003999{
Jeff King7c2f08a2017-07-07 05:07:58 -04004000 while (1) {
Jeff Kingd08565b2017-07-07 05:14:07 -04004001 struct commit *commit;
Linus Torvalds765ac8e2006-02-28 15:07:20 -08004002
Jeff Kingd08565b2017-07-07 05:14:07 -04004003 if (revs->reflog_info)
4004 commit = next_reflog_entry(revs->reflog_info);
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00004005 else if (revs->topo_walk_info)
4006 commit = next_topo_commit(revs);
Jeff Kingd08565b2017-07-07 05:14:07 -04004007 else
4008 commit = pop_commit(&revs->commits);
Linus Torvalds2a0925b2006-03-30 17:05:25 -08004009
Jeff King7c2f08a2017-07-07 05:07:58 -04004010 if (!commit)
4011 return NULL;
4012
Jeff Kingd08565b2017-07-07 05:14:07 -04004013 if (revs->reflog_info)
Jeff Kingffa1eea2010-11-21 23:42:53 -05004014 commit->object.flags &= ~(ADDED | SEEN | SHOWN);
Johannes Schindelin8860fd42007-01-11 11:47:48 +01004015
Linus Torvalds2a0925b2006-03-30 17:05:25 -08004016 /*
4017 * If we haven't done the list limiting, we need to look at
Linus Torvaldsbe7db6e2006-04-01 16:35:06 -08004018 * the parents here. We also need to do the date-based limiting
4019 * that we'd otherwise have done in limit_list().
Linus Torvalds2a0925b2006-03-30 17:05:25 -08004020 */
Linus Torvaldsbe7db6e2006-04-01 16:35:06 -08004021 if (!revs->limited) {
Jan Harkes744f4982006-10-30 20:37:49 -05004022 if (revs->max_age != -1 &&
Jeff Kingde239442017-07-07 05:16:21 -04004023 comparison_date(revs, commit) < revs->max_age)
Junio C Hamano86ab4902007-03-05 13:10:06 -08004024 continue;
Jeff Kingd08565b2017-07-07 05:14:07 -04004025
4026 if (revs->reflog_info)
4027 try_to_simplify_commit(revs, commit);
Derrick Stoleef0d9cc42018-11-01 13:46:20 +00004028 else if (revs->topo_walk_info)
4029 expand_topo_walk(revs, commit);
Derrick Stolee5284fc52018-11-01 13:46:21 +00004030 else if (process_parents(revs, commit, &revs->commits, NULL) < 0) {
Vicent Marti2db1a432014-03-28 06:00:43 -04004031 if (!revs->ignore_missing_links)
4032 die("Failed to traverse parents of commit %s",
brian m. carlsonf2fd0762015-11-10 02:22:28 +00004033 oid_to_hex(&commit->object.oid));
Vicent Marti2db1a432014-03-28 06:00:43 -04004034 }
Linus Torvaldsbe7db6e2006-04-01 16:35:06 -08004035 }
Junio C Hamano1b65a5a2006-04-16 18:12:49 -07004036
Linus Torvalds252a7c02007-11-04 12:12:05 -08004037 switch (simplify_commit(revs, commit)) {
4038 case commit_ignore:
Linus Torvalds2a0925b2006-03-30 17:05:25 -08004039 continue;
Linus Torvalds252a7c02007-11-04 12:12:05 -08004040 case commit_error:
Junio C Hamanoed620892009-02-11 01:27:43 -08004041 die("Failed to simplify parents of commit %s",
brian m. carlsonf2fd0762015-11-10 02:22:28 +00004042 oid_to_hex(&commit->object.oid));
Linus Torvalds252a7c02007-11-04 12:12:05 -08004043 default:
Nguyễn Thái Ngọc Duy1b32dec2014-03-25 20:23:27 +07004044 if (revs->track_linear)
4045 track_linear(revs, commit);
Linus Torvalds252a7c02007-11-04 12:12:05 -08004046 return commit;
Junio C Hamano384e99a2006-03-27 23:58:34 -08004047 }
Jeff King7c2f08a2017-07-07 05:07:58 -04004048 }
Linus Torvalds765ac8e2006-02-28 15:07:20 -08004049}
Junio C Hamanod5db6c92006-12-19 18:25:32 -08004050
Michael Haggertybe6754c2013-05-25 11:08:09 +02004051/*
4052 * Return true for entries that have not yet been shown. (This is an
4053 * object_array_each_func_t.)
4054 */
4055static int entry_unshown(struct object_array_entry *entry, void *cb_data_unused)
4056{
4057 return !(entry->item->flags & SHOWN);
4058}
4059
4060/*
4061 * If array is on the verge of a realloc, garbage-collect any entries
4062 * that have already been shown to try to free up some space.
4063 */
Junio C Hamano86ab4902007-03-05 13:10:06 -08004064static void gc_boundary(struct object_array *array)
4065{
Michael Haggertybe6754c2013-05-25 11:08:09 +02004066 if (array->nr == array->alloc)
4067 object_array_filter(array, entry_unshown, NULL);
Junio C Hamano86ab4902007-03-05 13:10:06 -08004068}
4069
Adam Simpkins4603ec02008-05-24 16:02:05 -07004070static void create_boundary_commit_list(struct rev_info *revs)
4071{
4072 unsigned i;
4073 struct commit *c;
4074 struct object_array *array = &revs->boundary_commits;
4075 struct object_array_entry *objects = array->objects;
4076
4077 /*
4078 * If revs->commits is non-NULL at this point, an error occurred in
4079 * get_revision_1(). Ignore the error and continue printing the
4080 * boundary commits anyway. (This is what the code has always
4081 * done.)
4082 */
4083 if (revs->commits) {
4084 free_commit_list(revs->commits);
4085 revs->commits = NULL;
4086 }
4087
4088 /*
4089 * Put all of the actual boundary commits from revs->boundary_commits
4090 * into revs->commits
4091 */
4092 for (i = 0; i < array->nr; i++) {
4093 c = (struct commit *)(objects[i].item);
4094 if (!c)
4095 continue;
4096 if (!(c->object.flags & CHILD_SHOWN))
4097 continue;
4098 if (c->object.flags & (SHOWN | BOUNDARY))
4099 continue;
4100 c->object.flags |= BOUNDARY;
4101 commit_list_insert(c, &revs->commits);
4102 }
4103
4104 /*
4105 * If revs->topo_order is set, sort the boundary commits
4106 * in topological order
4107 */
Junio C Hamano08f704f2013-06-06 16:07:14 -07004108 sort_in_topological_order(&revs->commits, revs->sort_order);
Adam Simpkins4603ec02008-05-24 16:02:05 -07004109}
4110
Adam Simpkins7fefda52008-05-04 03:36:54 -07004111static struct commit *get_revision_internal(struct rev_info *revs)
Junio C Hamanod5db6c92006-12-19 18:25:32 -08004112{
4113 struct commit *c = NULL;
Junio C Hamano86ab4902007-03-05 13:10:06 -08004114 struct commit_list *l;
Junio C Hamanod5db6c92006-12-19 18:25:32 -08004115
Junio C Hamano86ab4902007-03-05 13:10:06 -08004116 if (revs->boundary == 2) {
Adam Simpkins4603ec02008-05-24 16:02:05 -07004117 /*
4118 * All of the normal commits have already been returned,
4119 * and we are now returning boundary commits.
4120 * create_boundary_commit_list() has populated
4121 * revs->commits with the remaining commits to return.
4122 */
4123 c = pop_commit(&revs->commits);
4124 if (c)
4125 c->object.flags |= SHOWN;
Johannes Schindelin9c5e66e2007-01-20 23:04:02 +01004126 return c;
4127 }
4128
Junio C Hamano86ab4902007-03-05 13:10:06 -08004129 /*
Jeff Kingb72a1902012-07-13 03:50:23 -04004130 * If our max_count counter has reached zero, then we are done. We
4131 * don't simply return NULL because we still might need to show
4132 * boundary commits. But we want to avoid calling get_revision_1, which
4133 * might do a considerable amount of work finding the next commit only
4134 * for us to throw it away.
4135 *
4136 * If it is non-zero, then either we don't have a max_count at all
4137 * (-1), or it is still counting, in which case we decrement.
Junio C Hamano86ab4902007-03-05 13:10:06 -08004138 */
Jeff Kingb72a1902012-07-13 03:50:23 -04004139 if (revs->max_count) {
4140 c = get_revision_1(revs);
4141 if (c) {
Felipe Contreras9e57ac52013-10-31 03:25:43 -06004142 while (revs->skip_count > 0) {
Jeff Kingb72a1902012-07-13 03:50:23 -04004143 revs->skip_count--;
4144 c = get_revision_1(revs);
4145 if (!c)
4146 break;
4147 }
Junio C Hamano8839ac92007-03-06 03:20:55 -08004148 }
Junio C Hamano86ab4902007-03-05 13:10:06 -08004149
Jeff Kingb72a1902012-07-13 03:50:23 -04004150 if (revs->max_count > 0)
4151 revs->max_count--;
Junio C Hamanod5db6c92006-12-19 18:25:32 -08004152 }
Junio C Hamano86ab4902007-03-05 13:10:06 -08004153
Junio C Hamanoc33d8592007-03-05 18:23:57 -08004154 if (c)
4155 c->object.flags |= SHOWN;
4156
Felipe Contreras9e57ac52013-10-31 03:25:43 -06004157 if (!revs->boundary)
Junio C Hamanod5db6c92006-12-19 18:25:32 -08004158 return c;
Junio C Hamano86ab4902007-03-05 13:10:06 -08004159
4160 if (!c) {
4161 /*
4162 * get_revision_1() runs out the commits, and
4163 * we are done computing the boundaries.
4164 * switch to boundary commits output mode.
4165 */
4166 revs->boundary = 2;
Adam Simpkins4603ec02008-05-24 16:02:05 -07004167
4168 /*
4169 * Update revs->commits to contain the list of
4170 * boundary commits.
4171 */
4172 create_boundary_commit_list(revs);
4173
Adam Simpkins3c68d672008-05-24 16:02:04 -07004174 return get_revision_internal(revs);
Junio C Hamano86ab4902007-03-05 13:10:06 -08004175 }
4176
4177 /*
4178 * boundary commits are the commits that are parents of the
4179 * ones we got from get_revision_1() but they themselves are
4180 * not returned from get_revision_1(). Before returning
4181 * 'c', we need to mark its parents that they could be boundaries.
4182 */
4183
4184 for (l = c->parents; l; l = l->next) {
4185 struct object *p;
4186 p = &(l->item->object);
Junio C Hamanoc33d8592007-03-05 18:23:57 -08004187 if (p->flags & (CHILD_SHOWN | SHOWN))
Junio C Hamano86ab4902007-03-05 13:10:06 -08004188 continue;
4189 p->flags |= CHILD_SHOWN;
4190 gc_boundary(&revs->boundary_commits);
4191 add_object_array(p, NULL, &revs->boundary_commits);
4192 }
4193
4194 return c;
Junio C Hamanod5db6c92006-12-19 18:25:32 -08004195}
Adam Simpkins7fefda52008-05-04 03:36:54 -07004196
4197struct commit *get_revision(struct rev_info *revs)
4198{
Thomas Rast498bcd32008-08-29 21:18:38 +02004199 struct commit *c;
4200 struct commit_list *reversed;
4201
4202 if (revs->reverse) {
4203 reversed = NULL;
Felipe Contreras9e57ac52013-10-31 03:25:43 -06004204 while ((c = get_revision_internal(revs)))
Thomas Rast498bcd32008-08-29 21:18:38 +02004205 commit_list_insert(c, &reversed);
Thomas Rast498bcd32008-08-29 21:18:38 +02004206 revs->commits = reversed;
4207 revs->reverse = 0;
4208 revs->reverse_output_stage = 1;
4209 }
4210
Nguyễn Thái Ngọc Duy1b32dec2014-03-25 20:23:27 +07004211 if (revs->reverse_output_stage) {
4212 c = pop_commit(&revs->commits);
4213 if (revs->track_linear)
4214 revs->linear = !!(c && c->object.flags & TRACK_LINEAR);
4215 return c;
4216 }
Thomas Rast498bcd32008-08-29 21:18:38 +02004217
4218 c = get_revision_internal(revs);
Adam Simpkins7fefda52008-05-04 03:36:54 -07004219 if (c && revs->graph)
4220 graph_update(revs->graph, c);
Nguyễn Thái Ngọc Duy1b32dec2014-03-25 20:23:27 +07004221 if (!c) {
Thomas Rast53d00b32013-07-31 22:13:20 +02004222 free_saved_parents(revs);
Nguyễn Thái Ngọc Duy1b32dec2014-03-25 20:23:27 +07004223 if (revs->previous_parents) {
4224 free_commit_list(revs->previous_parents);
4225 revs->previous_parents = NULL;
4226 }
4227 }
Adam Simpkins7fefda52008-05-04 03:36:54 -07004228 return c;
4229}
Michael J Gruber1df2d652011-03-07 13:31:39 +01004230
Denton Liu49825162019-11-19 16:51:13 -08004231const char *get_revision_mark(const struct rev_info *revs, const struct commit *commit)
Michael J Gruber1df2d652011-03-07 13:31:39 +01004232{
4233 if (commit->object.flags & BOUNDARY)
4234 return "-";
4235 else if (commit->object.flags & UNINTERESTING)
4236 return "^";
Michael J Gruberadbbb312011-03-07 13:31:40 +01004237 else if (commit->object.flags & PATCHSAME)
4238 return "=";
Michael J Gruber1df2d652011-03-07 13:31:39 +01004239 else if (!revs || revs->left_right) {
4240 if (commit->object.flags & SYMMETRIC_LEFT)
4241 return "<";
4242 else
4243 return ">";
4244 } else if (revs->graph)
4245 return "*";
Michael J Gruberadbbb312011-03-07 13:31:40 +01004246 else if (revs->cherry_mark)
4247 return "+";
Michael J Gruber1df2d652011-03-07 13:31:39 +01004248 return "";
4249}
Michael J Gruberb1b47552011-03-10 15:45:03 +01004250
4251void put_revision_mark(const struct rev_info *revs, const struct commit *commit)
4252{
Denton Liu49825162019-11-19 16:51:13 -08004253 const char *mark = get_revision_mark(revs, commit);
Michael J Gruberb1b47552011-03-10 15:45:03 +01004254 if (!strlen(mark))
4255 return;
4256 fputs(mark, stdout);
4257 putchar(' ');
4258}