Google Git
Sign in
chromium / external / github.com / git / git / HEAD / . / commit-reach.c
blob: cc18c86d3bb315ed2a206174fbbcdebf86ca873f [file] [log] [blame]
Patrick Steinhardte7da9382024-06-14 06:50:23[diff] [blame]1#define USE_THE_REPOSITORY_VARIABLE
2
Elijah Newren36bf1952023-02-24 00:09:24[diff] [blame]3#include "git-compat-util.h"
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]4#include "commit.h"
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]5#include "commit-graph.h"
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]6#include "decorate.h"
Elijah Newren41771fa2023-02-24 00:09:27[diff] [blame]7#include "hex.h"
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]8#include "prio-queue.h"
Jonathan Nieder6621c832018-08-28 21:36:57[diff] [blame]9#include "ref-filter.h"
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]10#include "revision.h"
11#include "tag.h"
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]12#include "commit-reach.h"
Derrick Stoleefd67d142023-03-20 11:26:53[diff] [blame]13#include "ewah/ewok.h"
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]14
15/* Remember to update object flag allocation in object.h */
16#define PARENT1 (1u<<16)
17#define PARENT2 (1u<<17)
18#define STALE (1u<<18)
19#define RESULT (1u<<19)
20
21static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
22
Derrick Stoleec8d693e2021-02-19 12:34:08[diff] [blame]23static int compare_commits_by_gen(const void *_a, const void *_b)
24{
25 const struct commit *a = *(const struct commit * const *)_a;
26 const struct commit *b = *(const struct commit * const *)_b;
27
28 timestamp_t generation_a = commit_graph_generation(a);
29 timestamp_t generation_b = commit_graph_generation(b);
30
31 if (generation_a < generation_b)
32 return -1;
33 if (generation_a > generation_b)
34 return 1;
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]35 if (a->date < b->date)
36 return -1;
37 if (a->date > b->date)
38 return 1;
Derrick Stoleec8d693e2021-02-19 12:34:08[diff] [blame]39 return 0;
40}
41
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]42static int queue_has_nonstale(struct prio_queue *queue)
43{
Patrick Steinhardt95c09e42024-12-27 10:46:22[diff] [blame]44 for (size_t i = 0; i < queue->nr; i++) {
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]45 struct commit *commit = queue->array[i].data;
46 if (!(commit->object.flags & STALE))
47 return 1;
48 }
49 return 0;
50}
51
52/* all input commits in one and twos[] must have been parsed! */
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]53static int paint_down_to_common(struct repository *r,
54 struct commit *one, int n,
55 struct commit **twos,
56 timestamp_t min_generation,
57 int ignore_missing_commits,
58 struct commit_list **result)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]59{
60 struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]61 int i;
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]62 timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]63 struct commit_list **tail = result;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]64
Abhishek Kumar8d00d7c2021-01-16 18:11:17[diff] [blame]65 if (!min_generation && !corrected_commit_dates_enabled(r))
Junio C Hamano1b7a91d2018-09-17 20:53:52[diff] [blame]66 queue.compare = compare_commits_by_commit_date;
67
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]68 one->object.flags |= PARENT1;
69 if (!n) {
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]70 commit_list_append(one, result);
71 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]72 }
73 prio_queue_put(&queue, one);
74
75 for (i = 0; i < n; i++) {
76 twos[i]->object.flags |= PARENT2;
77 prio_queue_put(&queue, twos[i]);
78 }
79
80 while (queue_has_nonstale(&queue)) {
81 struct commit *commit = prio_queue_get(&queue);
82 struct commit_list *parents;
83 int flags;
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]84 timestamp_t generation = commit_graph_generation(commit);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]85
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]86 if (min_generation && generation > last_gen)
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]87 BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]88 generation, last_gen,
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]89 oid_to_hex(&commit->object.oid));
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]90 last_gen = generation;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]91
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]92 if (generation < min_generation)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]93 break;
94
95 flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
96 if (flags == (PARENT1 | PARENT2)) {
97 if (!(commit->object.flags & RESULT)) {
98 commit->object.flags |= RESULT;
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]99 tail = commit_list_append(commit, tail);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]100 }
101 /* Mark parents of a found merge stale */
102 flags |= STALE;
103 }
104 parents = commit->parents;
105 while (parents) {
106 struct commit *p = parents->item;
107 parents = parents->next;
108 if ((p->object.flags & flags) == flags)
109 continue;
Johannes Schindeline67431d2024-02-28 09:44:07[diff] [blame]110 if (repo_parse_commit(r, p)) {
111 clear_prio_queue(&queue);
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]112 free_commit_list(*result);
113 *result = NULL;
Johannes Schindelin2d2da172024-02-28 09:44:10[diff] [blame]114 /*
115 * At this stage, we know that the commit is
116 * missing: `repo_parse_commit()` uses
117 * `OBJECT_INFO_DIE_IF_CORRUPT` and therefore
118 * corrupt commits would already have been
119 * dispatched with a `die()`.
120 */
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]121 if (ignore_missing_commits)
122 return 0;
123 return error(_("could not parse commit %s"),
124 oid_to_hex(&p->object.oid));
Johannes Schindeline67431d2024-02-28 09:44:07[diff] [blame]125 }
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]126 p->object.flags |= flags;
127 prio_queue_put(&queue, p);
128 }
129 }
130
131 clear_prio_queue(&queue);
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]132 commit_list_sort_by_date(result);
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]133 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]134}
135
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]136static int merge_bases_many(struct repository *r,
137 struct commit *one, int n,
138 struct commit **twos,
139 struct commit_list **result)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]140{
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]141 struct commit_list *list = NULL, **tail = result;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]142 int i;
143
144 for (i = 0; i < n; i++) {
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]145 if (one == twos[i]) {
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]146 /*
147 * We do not mark this even with RESULT so we do not
148 * have to clean it up.
149 */
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]150 *result = commit_list_insert(one, result);
151 return 0;
152 }
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]153 }
154
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]155 if (!one)
156 return 0;
Stefan Beller18256a92018-11-14 00:12:52[diff] [blame]157 if (repo_parse_commit(r, one))
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]158 return error(_("could not parse commit %s"),
159 oid_to_hex(&one->object.oid));
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]160 for (i = 0; i < n; i++) {
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]161 if (!twos[i])
162 return 0;
Stefan Beller18256a92018-11-14 00:12:52[diff] [blame]163 if (repo_parse_commit(r, twos[i]))
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]164 return error(_("could not parse commit %s"),
165 oid_to_hex(&twos[i]->object.oid));
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]166 }
167
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]168 if (paint_down_to_common(r, one, n, twos, 0, 0, &list)) {
169 free_commit_list(list);
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]170 return -1;
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]171 }
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]172
173 while (list) {
174 struct commit *commit = pop_commit(&list);
175 if (!(commit->object.flags & STALE))
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]176 tail = commit_list_append(commit, tail);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]177 }
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]178 commit_list_sort_by_date(result);
Johannes Schindelinfb02c522024-02-28 09:44:12[diff] [blame]179 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]180}
181
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]182int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]183{
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]184 struct commit_list *i, *j, *k;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]185
186 if (!in)
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]187 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]188
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]189 commit_list_insert(in->item, result);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]190
191 for (i = in->next; i; i = i->next) {
192 struct commit_list *new_commits = NULL, *end = NULL;
193
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]194 for (j = *result; j; j = j->next) {
Johannes Schindelin76e2a092024-02-28 09:44:14[diff] [blame]195 struct commit_list *bases = NULL;
196 if (repo_get_merge_bases(the_repository, i->item,
197 j->item, &bases) < 0) {
198 free_commit_list(bases);
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]199 free_commit_list(*result);
200 *result = NULL;
201 return -1;
Johannes Schindelin76e2a092024-02-28 09:44:14[diff] [blame]202 }
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]203 if (!new_commits)
204 new_commits = bases;
205 else
206 end->next = bases;
207 for (k = bases; k; k = k->next)
208 end = k;
209 }
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]210 free_commit_list(*result);
211 *result = new_commits;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]212 }
Johannes Schindelinf87056c2024-02-28 09:44:15[diff] [blame]213 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]214}
215
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]216static int remove_redundant_no_gen(struct repository *r,
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]217 struct commit **array,
218 size_t cnt, size_t *dedup_cnt)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]219{
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]220 struct commit **work;
221 unsigned char *redundant;
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]222 size_t *filled_index;
223 size_t i, j, filled;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]224
René Scharfeca56dad2021-03-13 16:17:22[diff] [blame]225 CALLOC_ARRAY(work, cnt);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]226 redundant = xcalloc(cnt, 1);
227 ALLOC_ARRAY(filled_index, cnt - 1);
228
229 for (i = 0; i < cnt; i++)
Stefan Bellered8a0e32018-11-14 00:12:53[diff] [blame]230 repo_parse_commit(r, array[i]);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]231 for (i = 0; i < cnt; i++) {
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]232 struct commit_list *common = NULL;
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]233 timestamp_t min_generation = commit_graph_generation(array[i]);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]234
235 if (redundant[i])
236 continue;
237 for (j = filled = 0; j < cnt; j++) {
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]238 timestamp_t curr_generation;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]239 if (i == j || redundant[j])
240 continue;
241 filled_index[filled] = j;
242 work[filled++] = array[j];
243
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]244 curr_generation = commit_graph_generation(array[j]);
245 if (curr_generation < min_generation)
246 min_generation = curr_generation;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]247 }
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]248 if (paint_down_to_common(r, array[i], filled,
249 work, min_generation, 0, &common)) {
250 clear_commit_marks(array[i], all_flags);
251 clear_commit_marks_many(filled, work, all_flags);
252 free_commit_list(common);
253 free(work);
254 free(redundant);
255 free(filled_index);
256 return -1;
257 }
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]258 if (array[i]->object.flags & PARENT2)
259 redundant[i] = 1;
260 for (j = 0; j < filled; j++)
261 if (work[j]->object.flags & PARENT1)
262 redundant[filled_index[j]] = 1;
263 clear_commit_marks(array[i], all_flags);
264 clear_commit_marks_many(filled, work, all_flags);
265 free_commit_list(common);
266 }
267
268 /* Now collect the result */
269 COPY_ARRAY(work, array, cnt);
270 for (i = filled = 0; i < cnt; i++)
271 if (!redundant[i])
272 array[filled++] = work[i];
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]273 *dedup_cnt = filled;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]274 free(work);
275 free(redundant);
276 free(filled_index);
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]277 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]278}
279
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]280static int remove_redundant_with_gen(struct repository *r,
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]281 struct commit **array, size_t cnt,
282 size_t *dedup_cnt)
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]283{
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]284 size_t i, count_non_stale = 0, count_still_independent = cnt;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]285 timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
Derrick Stolee41f3c992021-02-19 12:34:10[diff] [blame]286 struct commit **walk_start, **sorted;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]287 size_t walk_start_nr = 0, walk_start_alloc = cnt;
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]288 size_t min_gen_pos = 0;
Derrick Stolee41f3c992021-02-19 12:34:10[diff] [blame]289
290 /*
291 * Sort the input by generation number, ascending. This allows
292 * us to increase the "min_generation" limit when we discover
293 * the commit with lowest generation is STALE. The index
294 * min_gen_pos points to the current position within 'array'
295 * that is not yet known to be STALE.
296 */
René Scharfe6e578412023-01-01 21:16:48[diff] [blame]297 DUP_ARRAY(sorted, array, cnt);
Derrick Stolee41f3c992021-02-19 12:34:10[diff] [blame]298 QSORT(sorted, cnt, compare_commits_by_gen);
299 min_generation = commit_graph_generation(sorted[0]);
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]300
301 ALLOC_ARRAY(walk_start, walk_start_alloc);
302
303 /* Mark all parents of the input as STALE */
304 for (i = 0; i < cnt; i++) {
305 struct commit_list *parents;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]306
307 repo_parse_commit(r, array[i]);
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]308 array[i]->object.flags |= RESULT;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]309 parents = array[i]->parents;
310
311 while (parents) {
312 repo_parse_commit(r, parents->item);
313 if (!(parents->item->object.flags & STALE)) {
314 parents->item->object.flags |= STALE;
315 ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);
316 walk_start[walk_start_nr++] = parents->item;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]317 }
318 parents = parents->next;
319 }
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]320 }
321
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]322 QSORT(walk_start, walk_start_nr, compare_commits_by_gen);
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]323
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]324 /* remove STALE bit for now to allow walking through parents */
325 for (i = 0; i < walk_start_nr; i++)
326 walk_start[i]->object.flags &= ~STALE;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]327
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]328 /*
329 * Start walking from the highest generation. Hopefully, it will
330 * find all other items during the first-parent walk, and we can
331 * terminate early. Otherwise, we will do the same amount of work
332 * as before.
333 */
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]334 for (i = walk_start_nr; i && count_still_independent > 1; i--) {
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]335 /* push the STALE bits up to min generation */
336 struct commit_list *stack = NULL;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]337
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]338 commit_list_insert(walk_start[i - 1], &stack);
339 walk_start[i - 1]->object.flags |= STALE;
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]340
341 while (stack) {
342 struct commit_list *parents;
343 struct commit *c = stack->item;
344
345 repo_parse_commit(r, c);
346
347 if (c->object.flags & RESULT) {
348 c->object.flags &= ~RESULT;
349 if (--count_still_independent <= 1)
350 break;
Derrick Stolee41f3c992021-02-19 12:34:10[diff] [blame]351 if (oideq(&c->object.oid, &sorted[min_gen_pos]->object.oid)) {
352 while (min_gen_pos < cnt - 1 &&
353 (sorted[min_gen_pos]->object.flags & STALE))
354 min_gen_pos++;
355 min_generation = commit_graph_generation(sorted[min_gen_pos]);
356 }
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]357 }
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]358
359 if (commit_graph_generation(c) < min_generation) {
360 pop_commit(&stack);
361 continue;
362 }
363
364 parents = c->parents;
365 while (parents) {
366 if (!(parents->item->object.flags & STALE)) {
367 parents->item->object.flags |= STALE;
368 commit_list_insert(parents->item, &stack);
369 break;
370 }
371 parents = parents->next;
372 }
373
374 /* pop if all parents have been visited already */
375 if (!parents)
376 pop_commit(&stack);
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]377 }
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]378 free_commit_list(stack);
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]379 }
Derrick Stolee41f3c992021-02-19 12:34:10[diff] [blame]380 free(sorted);
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]381
Derrick Stolee36777732021-02-19 12:34:09[diff] [blame]382 /* clear result */
383 for (i = 0; i < cnt; i++)
384 array[i]->object.flags &= ~RESULT;
385
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]386 /* rearrange array */
387 for (i = count_non_stale = 0; i < cnt; i++) {
388 if (!(array[i]->object.flags & STALE))
389 array[count_non_stale++] = array[i];
390 }
391
392 /* clear marks */
393 clear_commit_marks_many(walk_start_nr, walk_start, STALE);
394 free(walk_start);
395
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]396 *dedup_cnt = count_non_stale;
397 return 0;
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]398}
399
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]400static int remove_redundant(struct repository *r, struct commit **array,
401 size_t cnt, size_t *dedup_cnt)
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]402{
403 /*
404 * Some commit in the array may be an ancestor of
405 * another commit. Move the independent commits to the
406 * beginning of 'array' and return their number. Callers
407 * should not rely upon the contents of 'array' after
408 * that number.
409 */
410 if (generation_numbers_enabled(r)) {
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]411 /*
412 * If we have a single commit with finite generation
413 * number, then the _with_gen algorithm is preferred.
414 */
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]415 for (size_t i = 0; i < cnt; i++) {
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]416 if (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]417 return remove_redundant_with_gen(r, array, cnt, dedup_cnt);
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]418 }
419 }
420
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]421 return remove_redundant_no_gen(r, array, cnt, dedup_cnt);
Derrick Stoleefbc21e32021-02-19 12:34:07[diff] [blame]422}
423
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]424static int get_merge_bases_many_0(struct repository *r,
425 struct commit *one,
Patrick Steinhardt5e7fe8a2024-12-27 10:46:29[diff] [blame]426 size_t n,
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]427 struct commit **twos,
428 int cleanup,
429 struct commit_list **result)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]430{
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]431 struct commit_list *list, **tail = result;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]432 struct commit **rslt;
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]433 size_t cnt, i;
434 int ret;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]435
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]436 if (merge_bases_many(r, one, n, twos, result) < 0)
437 return -1;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]438 for (i = 0; i < n; i++) {
439 if (one == twos[i])
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]440 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]441 }
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]442 if (!*result || !(*result)->next) {
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]443 if (cleanup) {
444 clear_commit_marks(one, all_flags);
445 clear_commit_marks_many(n, twos, all_flags);
446 }
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]447 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]448 }
449
450 /* There are more than one */
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]451 cnt = commit_list_count(*result);
René Scharfeca56dad2021-03-13 16:17:22[diff] [blame]452 CALLOC_ARRAY(rslt, cnt);
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]453 for (list = *result, i = 0; list; list = list->next)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]454 rslt[i++] = list->item;
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]455 free_commit_list(*result);
456 *result = NULL;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]457
458 clear_commit_marks(one, all_flags);
459 clear_commit_marks_many(n, twos, all_flags);
460
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]461 ret = remove_redundant(r, rslt, cnt, &cnt);
462 if (ret < 0) {
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]463 free(rslt);
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]464 return -1;
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]465 }
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]466 for (i = 0; i < cnt; i++)
René Scharfe134ec332025-10-24 16:47:10[diff] [blame]467 tail = commit_list_append(rslt[i], tail);
468 commit_list_sort_by_date(result);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]469 free(rslt);
Johannes Schindelin8226e152024-02-28 09:44:13[diff] [blame]470 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]471}
472
Johannes Schindelin53173802024-02-28 09:44:16[diff] [blame]473int repo_get_merge_bases_many(struct repository *r,
474 struct commit *one,
Patrick Steinhardt5e7fe8a2024-12-27 10:46:29[diff] [blame]475 size_t n,
Johannes Schindelin53173802024-02-28 09:44:16[diff] [blame]476 struct commit **twos,
477 struct commit_list **result)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]478{
Johannes Schindelin53173802024-02-28 09:44:16[diff] [blame]479 return get_merge_bases_many_0(r, one, n, twos, 1, result);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]480}
481
Johannes Schindelincaaf1a22024-02-28 09:44:17[diff] [blame]482int repo_get_merge_bases_many_dirty(struct repository *r,
483 struct commit *one,
Patrick Steinhardt5e7fe8a2024-12-27 10:46:29[diff] [blame]484 size_t n,
Johannes Schindelincaaf1a22024-02-28 09:44:17[diff] [blame]485 struct commit **twos,
486 struct commit_list **result)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]487{
Johannes Schindelincaaf1a22024-02-28 09:44:17[diff] [blame]488 return get_merge_bases_many_0(r, one, n, twos, 0, result);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]489}
490
Johannes Schindelin76e2a092024-02-28 09:44:14[diff] [blame]491int repo_get_merge_bases(struct repository *r,
492 struct commit *one,
493 struct commit *two,
494 struct commit_list **result)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]495{
Johannes Schindelin76e2a092024-02-28 09:44:14[diff] [blame]496 return get_merge_bases_many_0(r, one, 1, &two, 1, result);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]497}
498
499/*
500 * Is "commit" a descendant of one of the elements on the "with_commit" list?
501 */
Carlo Marcelo Arenas Belónc1ea6252020-06-23 18:42:22[diff] [blame]502int repo_is_descendant_of(struct repository *r,
503 struct commit *commit,
504 struct commit_list *with_commit)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]505{
506 if (!with_commit)
507 return 1;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]508
Ævar Arnfjörð Bjarmason4a93b892023-03-28 13:58:58[diff] [blame]509 if (generation_numbers_enabled(r)) {
Derrick Stolee6cc01742018-07-20 16:33:30[diff] [blame]510 struct commit_list *from_list = NULL;
511 int result;
512 commit_list_insert(commit, &from_list);
513 result = can_all_from_reach(from_list, with_commit, 0);
514 free_commit_list(from_list);
515 return result;
516 } else {
517 while (with_commit) {
518 struct commit *other;
Johannes Schindelin24876eb2024-02-28 09:44:09[diff] [blame]519 int ret;
Derrick Stolee6cc01742018-07-20 16:33:30[diff] [blame]520
521 other = with_commit->item;
522 with_commit = with_commit->next;
Johannes Schindelin24876eb2024-02-28 09:44:09[diff] [blame]523 ret = repo_in_merge_bases_many(r, other, 1, &commit, 0);
524 if (ret)
525 return ret;
Derrick Stolee6cc01742018-07-20 16:33:30[diff] [blame]526 }
527 return 0;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]528 }
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]529}
530
531/*
532 * Is "commit" an ancestor of one of the "references"?
533 */
Stefan Beller4d5430f2018-11-14 00:12:56[diff] [blame]534int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
Johannes Schindelin207c40e2024-02-28 09:44:08[diff] [blame]535 int nr_reference, struct commit **reference,
536 int ignore_missing_commits)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]537{
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]538 struct commit_list *bases = NULL;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]539 int ret = 0, i;
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]540 timestamp_t generation, max_generation = GENERATION_NUMBER_ZERO;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]541
Stefan Beller4d5430f2018-11-14 00:12:56[diff] [blame]542 if (repo_parse_commit(r, commit))
Johannes Schindelin207c40e2024-02-28 09:44:08[diff] [blame]543 return ignore_missing_commits ? 0 : -1;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]544 for (i = 0; i < nr_reference; i++) {
Stefan Beller4d5430f2018-11-14 00:12:56[diff] [blame]545 if (repo_parse_commit(r, reference[i]))
Johannes Schindelin207c40e2024-02-28 09:44:08[diff] [blame]546 return ignore_missing_commits ? 0 : -1;
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]547
548 generation = commit_graph_generation(reference[i]);
Derrick Stolee8791bf12020-10-02 14:58:56[diff] [blame]549 if (generation > max_generation)
550 max_generation = generation;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]551 }
552
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]553 generation = commit_graph_generation(commit);
Derrick Stolee8791bf12020-10-02 14:58:56[diff] [blame]554 if (generation > max_generation)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]555 return ret;
556
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]557 if (paint_down_to_common(r, commit,
558 nr_reference, reference,
559 generation, ignore_missing_commits, &bases))
560 ret = -1;
561 else if (commit->object.flags & PARENT2)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]562 ret = 1;
563 clear_commit_marks(commit, all_flags);
564 clear_commit_marks_many(nr_reference, reference, all_flags);
565 free_commit_list(bases);
566 return ret;
567}
568
569/*
570 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
571 */
Stefan Beller4d5430f2018-11-14 00:12:56[diff] [blame]572int repo_in_merge_bases(struct repository *r,
573 struct commit *commit,
574 struct commit *reference)
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]575{
Derrick Stolee80b8ada2020-06-17 17:24:29[diff] [blame]576 int res;
577 struct commit_list *list = NULL;
578 struct commit_list **next = &list;
579
580 next = commit_list_append(commit, next);
581 res = repo_is_descendant_of(r, reference, list);
582 free_commit_list(list);
583
584 return res;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]585}
586
587struct commit_list *reduce_heads(struct commit_list *heads)
588{
589 struct commit_list *p;
590 struct commit_list *result = NULL, **tail = &result;
591 struct commit **array;
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]592 size_t num_head, i;
593 int ret;
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]594
595 if (!heads)
596 return NULL;
597
598 /* Uniquify */
599 for (p = heads; p; p = p->next)
600 p->item->object.flags &= ~STALE;
601 for (p = heads, num_head = 0; p; p = p->next) {
602 if (p->item->object.flags & STALE)
603 continue;
604 p->item->object.flags |= STALE;
605 num_head++;
606 }
René Scharfeca56dad2021-03-13 16:17:22[diff] [blame]607 CALLOC_ARRAY(array, num_head);
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]608 for (p = heads, i = 0; p; p = p->next) {
609 if (p->item->object.flags & STALE) {
610 array[i++] = p->item;
611 p->item->object.flags &= ~STALE;
612 }
613 }
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]614
615 ret = remove_redundant(the_repository, array, num_head, &num_head);
616 if (ret < 0) {
Johannes Schindelin896a0e12024-02-28 09:44:11[diff] [blame]617 free(array);
618 return NULL;
619 }
Patrick Steinhardt45843d82024-12-27 10:46:24[diff] [blame]620
Derrick Stolee5227c382018-07-20 16:33:02[diff] [blame]621 for (i = 0; i < num_head; i++)
622 tail = &commit_list_insert(array[i], tail)->next;
623 free(array);
624 return result;
625}
626
627void reduce_heads_replace(struct commit_list **heads)
628{
629 struct commit_list *result = reduce_heads(*heads);
630 free_commit_list(*heads);
631 *heads = result;
632}
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]633
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]634int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
635{
636 struct object *o;
637 struct commit *old_commit, *new_commit;
Derrick Stolee1e3497a2018-07-20 16:33:27[diff] [blame]638 struct commit_list *old_commit_list = NULL;
René Scharfed546fe22020-06-19 13:13:46[diff] [blame]639 int ret;
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]640
641 /*
642 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
643 * old_commit. Otherwise we require --force.
644 */
645 o = deref_tag(the_repository, parse_object(the_repository, old_oid),
646 NULL, 0);
647 if (!o || o->type != OBJ_COMMIT)
648 return 0;
649 old_commit = (struct commit *) o;
650
651 o = deref_tag(the_repository, parse_object(the_repository, new_oid),
652 NULL, 0);
653 if (!o || o->type != OBJ_COMMIT)
654 return 0;
655 new_commit = (struct commit *) o;
656
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]657 if (repo_parse_commit(the_repository, new_commit) < 0)
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]658 return 0;
659
Derrick Stolee1e3497a2018-07-20 16:33:27[diff] [blame]660 commit_list_insert(old_commit, &old_commit_list);
Junio C Hamano0258ed12020-07-07 05:09:15[diff] [blame]661 ret = repo_is_descendant_of(the_repository,
Carlo Marcelo Arenas Belónc1ea6252020-06-23 18:42:22[diff] [blame]662 new_commit, old_commit_list);
Johannes Schindelin24876eb2024-02-28 09:44:09[diff] [blame]663 if (ret < 0)
664 exit(128);
René Scharfed546fe22020-06-19 13:13:46[diff] [blame]665 free_commit_list(old_commit_list);
666 return ret;
Derrick Stolee1d614d42018-07-20 16:33:06[diff] [blame]667}
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]668
669/*
670 * Mimicking the real stack, this stack lives on the heap, avoiding stack
671 * overflows.
672 *
673 * At each recursion step, the stack items points to the commits whose
674 * ancestors are to be inspected.
675 */
676struct contains_stack {
677 int nr, alloc;
678 struct contains_stack_entry {
679 struct commit *commit;
680 struct commit_list *parents;
681 } *contains_stack;
682};
683
684static int in_commit_list(const struct commit_list *want, struct commit *c)
685{
686 for (; want; want = want->next)
Jeff Kinge43d2dc2018-10-02 21:19:21[diff] [blame]687 if (oideq(&want->item->object.oid, &c->object.oid))
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]688 return 1;
689 return 0;
690}
691
692/*
693 * Test whether the candidate is contained in the list.
694 * Do not recurse to find out, though, but return -1 if inconclusive.
695 */
696static enum contains_result contains_test(struct commit *candidate,
697 const struct commit_list *want,
698 struct contains_cache *cache,
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]699 timestamp_t cutoff)
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]700{
701 enum contains_result *cached = contains_cache_at(cache, candidate);
702
703 /* If we already have the answer cached, return that. */
704 if (*cached)
705 return *cached;
706
707 /* or are we it? */
708 if (in_commit_list(want, candidate)) {
709 *cached = CONTAINS_YES;
710 return CONTAINS_YES;
711 }
712
713 /* Otherwise, we don't know; prepare to recurse */
714 parse_commit_or_die(candidate);
715
Abhishek Kumarc49c82a2020-06-17 09:14:10[diff] [blame]716 if (commit_graph_generation(candidate) < cutoff)
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]717 return CONTAINS_NO;
718
719 return CONTAINS_UNKNOWN;
720}
721
722static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
723{
724 ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
725 contains_stack->contains_stack[contains_stack->nr].commit = candidate;
726 contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
727}
728
729static enum contains_result contains_tag_algo(struct commit *candidate,
730 const struct commit_list *want,
731 struct contains_cache *cache)
732{
733 struct contains_stack contains_stack = { 0, 0, NULL };
734 enum contains_result result;
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]735 timestamp_t cutoff = GENERATION_NUMBER_INFINITY;
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]736 const struct commit_list *p;
737
738 for (p = want; p; p = p->next) {
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]739 timestamp_t generation;
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]740 struct commit *c = p->item;
741 load_commit_graph_info(the_repository, c);
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]742 generation = commit_graph_generation(c);
743 if (generation < cutoff)
744 cutoff = generation;
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]745 }
746
747 result = contains_test(candidate, want, cache, cutoff);
748 if (result != CONTAINS_UNKNOWN)
749 return result;
750
751 push_to_contains_stack(candidate, &contains_stack);
752 while (contains_stack.nr) {
753 struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
754 struct commit *commit = entry->commit;
755 struct commit_list *parents = entry->parents;
756
757 if (!parents) {
758 *contains_cache_at(cache, commit) = CONTAINS_NO;
759 contains_stack.nr--;
760 }
761 /*
762 * If we just popped the stack, parents->item has been marked,
763 * therefore contains_test will return a meaningful yes/no.
764 */
765 else switch (contains_test(parents->item, want, cache, cutoff)) {
766 case CONTAINS_YES:
767 *contains_cache_at(cache, commit) = CONTAINS_YES;
768 contains_stack.nr--;
769 break;
770 case CONTAINS_NO:
771 entry->parents = parents->next;
772 break;
773 case CONTAINS_UNKNOWN:
774 push_to_contains_stack(parents->item, &contains_stack);
775 break;
776 }
777 }
778 free(contains_stack.contains_stack);
779 return contains_test(candidate, want, cache, cutoff);
780}
781
782int commit_contains(struct ref_filter *filter, struct commit *commit,
783 struct commit_list *list, struct contains_cache *cache)
784{
785 if (filter->with_commit_tag_algo)
786 return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
Carlo Marcelo Arenas Belónc1ea6252020-06-23 18:42:22[diff] [blame]787 return repo_is_descendant_of(the_repository, commit, list);
Derrick Stolee920f93c2018-07-20 16:33:08[diff] [blame]788}
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]789
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]790int can_all_from_reach_with_flag(struct object_array *from,
791 unsigned int with_flag,
792 unsigned int assign_flag,
Patrick Steinhardt04aeeea2024-12-27 10:46:23[diff] [blame]793 timestamp_t min_commit_date,
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]794 timestamp_t min_generation)
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]795{
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]796 struct commit **list = NULL;
Patrick Steinhardt85ee0682024-12-27 10:46:25[diff] [blame]797 size_t i;
798 size_t nr_commits;
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]799 int result = 1;
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]800
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]801 ALLOC_ARRAY(list, from->nr);
Derrick Stoleeb67f6b22018-09-21 15:05:26[diff] [blame]802 nr_commits = 0;
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]803 for (i = 0; i < from->nr; i++) {
Derrick Stoleeb67f6b22018-09-21 15:05:26[diff] [blame]804 struct object *from_one = from->objects[i].item;
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]805
Derrick Stoleeb67f6b22018-09-21 15:05:26[diff] [blame]806 if (!from_one || from_one->flags & assign_flag)
807 continue;
808
809 from_one = deref_tag(the_repository, from_one,
810 "a from object", 0);
811 if (!from_one || from_one->type != OBJ_COMMIT) {
Derrick Stolee85806442018-09-25 13:27:41[diff] [blame]812 /*
813 * no way to tell if this is reachable by
Derrick Stoleeb67f6b22018-09-21 15:05:26[diff] [blame]814 * looking at the ancestry chain alone, so
815 * leave a note to ourselves not to worry about
816 * this object anymore.
817 */
818 from->objects[i].item->flags |= assign_flag;
819 continue;
820 }
821
822 list[nr_commits] = (struct commit *)from_one;
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]823 if (repo_parse_commit(the_repository, list[nr_commits]) ||
Abhishek Kumarc49c82a2020-06-17 09:14:10[diff] [blame]824 commit_graph_generation(list[nr_commits]) < min_generation) {
Derrick Stoleeb67f6b22018-09-21 15:05:26[diff] [blame]825 result = 0;
826 goto cleanup;
827 }
828
829 nr_commits++;
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]830 }
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]831
Derrick Stoleeb67f6b22018-09-21 15:05:26[diff] [blame]832 QSORT(list, nr_commits, compare_commits_by_gen);
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]833
Derrick Stoleeb67f6b22018-09-21 15:05:26[diff] [blame]834 for (i = 0; i < nr_commits; i++) {
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]835 /* DFS from list[i] */
836 struct commit_list *stack = NULL;
837
838 list[i]->object.flags |= assign_flag;
839 commit_list_insert(list[i], &stack);
840
841 while (stack) {
842 struct commit_list *parent;
843
Derrick Stoleeb6723e42018-10-18 17:24:40[diff] [blame]844 if (stack->item->object.flags & (with_flag | RESULT)) {
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]845 pop_commit(&stack);
Derrick Stoleeb6723e42018-10-18 17:24:40[diff] [blame]846 if (stack)
847 stack->item->object.flags |= RESULT;
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]848 continue;
849 }
850
851 for (parent = stack->item->parents; parent; parent = parent->next) {
852 if (parent->item->object.flags & (with_flag | RESULT))
853 stack->item->object.flags |= RESULT;
854
855 if (!(parent->item->object.flags & assign_flag)) {
856 parent->item->object.flags |= assign_flag;
857
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]858 if (repo_parse_commit(the_repository, parent->item) ||
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]859 parent->item->date < min_commit_date ||
Abhishek Kumarc49c82a2020-06-17 09:14:10[diff] [blame]860 commit_graph_generation(parent->item) < min_generation)
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]861 continue;
862
863 commit_list_insert(parent->item, &stack);
864 break;
865 }
866 }
867
868 if (!parent)
869 pop_commit(&stack);
870 }
871
872 if (!(list[i]->object.flags & (with_flag | RESULT))) {
873 result = 0;
874 goto cleanup;
875 }
876 }
877
878cleanup:
Derrick Stolee85806442018-09-25 13:27:41[diff] [blame]879 clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
Derrick Stolee4067a642018-09-21 15:05:27[diff] [blame]880 free(list);
881
Eric Wongc5773dc2023-02-11 11:15:26[diff] [blame]882 for (i = 0; i < from->nr; i++) {
883 struct object *from_one = from->objects[i].item;
884
885 if (from_one)
886 from_one->flags &= ~assign_flag;
887 }
Derrick Stolee4067a642018-09-21 15:05:27[diff] [blame]888
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]889 return result;
Derrick Stoleeba3ca1e2018-07-20 16:33:13[diff] [blame]890}
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]891
892int can_all_from_reach(struct commit_list *from, struct commit_list *to,
893 int cutoff_by_min_date)
894{
895 struct object_array from_objs = OBJECT_ARRAY_INIT;
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]896 struct commit_list *from_iter = from, *to_iter = to;
897 int result;
Patrick Steinhardt04aeeea2024-12-27 10:46:23[diff] [blame]898 timestamp_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]899 timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]900
901 while (from_iter) {
902 add_object_array(&from_iter->item->object, NULL, &from_objs);
903
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]904 if (!repo_parse_commit(the_repository, from_iter->item)) {
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]905 timestamp_t generation;
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]906 if (from_iter->item->date < min_commit_date)
907 min_commit_date = from_iter->item->date;
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]908
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]909 generation = commit_graph_generation(from_iter->item);
910 if (generation < min_generation)
911 min_generation = generation;
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]912 }
913
914 from_iter = from_iter->next;
915 }
916
917 while (to_iter) {
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]918 if (!repo_parse_commit(the_repository, to_iter->item)) {
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]919 timestamp_t generation;
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]920 if (to_iter->item->date < min_commit_date)
921 min_commit_date = to_iter->item->date;
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]922
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]923 generation = commit_graph_generation(to_iter->item);
924 if (generation < min_generation)
925 min_generation = generation;
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]926 }
927
928 to_iter->item->object.flags |= PARENT2;
929
930 to_iter = to_iter->next;
931 }
932
933 result = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,
Derrick Stolee4fbcca42018-07-20 16:33:28[diff] [blame]934 min_commit_date, min_generation);
Derrick Stolee1792bc12018-07-20 16:33:23[diff] [blame]935
936 while (from) {
937 clear_commit_marks(from->item, PARENT1);
938 from = from->next;
939 }
940
941 while (to) {
942 clear_commit_marks(to->item, PARENT2);
943 to = to->next;
944 }
945
946 object_array_clear(&from_objs);
947 return result;
948}
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]949
Patrick Steinhardt85ee0682024-12-27 10:46:25[diff] [blame]950struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,
951 struct commit **to, size_t nr_to,
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]952 unsigned int reachable_flag)
953{
954 struct commit **item;
955 struct commit *current;
956 struct commit_list *found_commits = NULL;
957 struct commit **to_last = to + nr_to;
958 struct commit **from_last = from + nr_from;
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]959 timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]960 int num_to_find = 0;
961
962 struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
963
964 for (item = to; item < to_last; item++) {
Abhishek Kumard7f92782021-01-16 18:11:13[diff] [blame]965 timestamp_t generation;
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]966 struct commit *c = *item;
967
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]968 repo_parse_commit(the_repository, c);
Abhishek Kumarc752ad02020-06-17 09:14:11[diff] [blame]969 generation = commit_graph_generation(c);
970 if (generation < min_generation)
971 min_generation = generation;
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]972
973 if (!(c->object.flags & PARENT1)) {
974 c->object.flags |= PARENT1;
975 num_to_find++;
976 }
977 }
978
979 for (item = from; item < from_last; item++) {
980 struct commit *c = *item;
981 if (!(c->object.flags & PARENT2)) {
982 c->object.flags |= PARENT2;
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]983 repo_parse_commit(the_repository, c);
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]984
985 prio_queue_put(&queue, *item);
986 }
987 }
988
989 while (num_to_find && (current = prio_queue_get(&queue)) != NULL) {
990 struct commit_list *parents;
991
992 if (current->object.flags & PARENT1) {
993 current->object.flags &= ~PARENT1;
994 current->object.flags |= reachable_flag;
995 commit_list_insert(current, &found_commits);
996 num_to_find--;
997 }
998
999 for (parents = current->parents; parents; parents = parents->next) {
1000 struct commit *p = parents->item;
1001
Ævar Arnfjörð Bjarmasonecb50912023-03-28 13:58:48[diff] [blame]1002 repo_parse_commit(the_repository, p);
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]1003
Abhishek Kumarc49c82a2020-06-17 09:14:10[diff] [blame]1004 if (commit_graph_generation(p) < min_generation)
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]1005 continue;
1006
1007 if (p->object.flags & PARENT2)
1008 continue;
1009
1010 p->object.flags |= PARENT2;
1011 prio_queue_put(&queue, p);
1012 }
1013 }
1014
Mike Hommey68b51172023-06-03 00:28:19[diff] [blame]1015 clear_prio_queue(&queue);
1016
Derrick Stoleefcb2c072018-11-02 13:14:45[diff] [blame]1017 clear_commit_marks_many(nr_to, to, PARENT1);
1018 clear_commit_marks_many(nr_from, from, PARENT2);
1019
1020 return found_commits;
1021}
Derrick Stoleefd67d142023-03-20 11:26:53[diff] [blame]1022
1023define_commit_slab(bit_arrays, struct bitmap *);
1024static struct bit_arrays bit_arrays;
1025
1026static void insert_no_dup(struct prio_queue *queue, struct commit *c)
1027{
1028 if (c->object.flags & PARENT2)
1029 return;
1030 prio_queue_put(queue, c);
1031 c->object.flags |= PARENT2;
1032}
1033
1034static struct bitmap *get_bit_array(struct commit *c, int width)
1035{
1036 struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c);
1037 if (!*bitmap)
1038 *bitmap = bitmap_word_alloc(width);
1039 return *bitmap;
1040}
1041
1042static void free_bit_array(struct commit *c)
1043{
1044 struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c);
1045 if (!*bitmap)
1046 return;
1047 bitmap_free(*bitmap);
1048 *bitmap = NULL;
1049}
1050
1051void ahead_behind(struct repository *r,
1052 struct commit **commits, size_t commits_nr,
1053 struct ahead_behind_count *counts, size_t counts_nr)
1054{
1055 struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
1056 size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
1057
1058 if (!commits_nr || !counts_nr)
1059 return;
1060
1061 for (size_t i = 0; i < counts_nr; i++) {
1062 counts[i].ahead = 0;
1063 counts[i].behind = 0;
1064 }
1065
1066 ensure_generations_valid(r, commits, commits_nr);
1067
1068 init_bit_arrays(&bit_arrays);
1069
1070 for (size_t i = 0; i < commits_nr; i++) {
1071 struct commit *c = commits[i];
1072 struct bitmap *bitmap = get_bit_array(c, width);
1073
1074 bitmap_set(bitmap, i);
1075 insert_no_dup(&queue, c);
1076 }
1077
1078 while (queue_has_nonstale(&queue)) {
1079 struct commit *c = prio_queue_get(&queue);
1080 struct commit_list *p;
1081 struct bitmap *bitmap_c = get_bit_array(c, width);
1082
1083 for (size_t i = 0; i < counts_nr; i++) {
1084 int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
1085 int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);
1086
1087 if (reach_from_tip ^ reach_from_base) {
1088 if (reach_from_base)
1089 counts[i].behind++;
1090 else
1091 counts[i].ahead++;
1092 }
1093 }
1094
1095 for (p = c->parents; p; p = p->next) {
1096 struct bitmap *bitmap_p;
1097
1098 repo_parse_commit(r, p->item);
1099
1100 bitmap_p = get_bit_array(p->item, width);
1101 bitmap_or(bitmap_p, bitmap_c);
1102
1103 /*
1104 * If this parent is reachable from every starting
1105 * commit, then none of its ancestors can contribute
1106 * to the ahead/behind count. Mark it as STALE, so
1107 * we can stop the walk when every commit in the
1108 * queue is STALE.
1109 */
1110 if (bitmap_popcount(bitmap_p) == commits_nr)
1111 p->item->object.flags |= STALE;
1112
1113 insert_no_dup(&queue, p->item);
1114 }
1115
1116 free_bit_array(c);
1117 }
1118
1119 /* STALE is used here, PARENT2 is used by insert_no_dup(). */
1120 repo_clear_commit_marks(r, PARENT2 | STALE);
Patrick Steinhardtba9d0292024-05-27 11:46:54[diff] [blame]1121 while (prio_queue_peek(&queue)) {
1122 struct commit *c = prio_queue_get(&queue);
1123 free_bit_array(c);
1124 }
Derrick Stoleefd67d142023-03-20 11:26:53[diff] [blame]1125 clear_bit_arrays(&bit_arrays);
1126 clear_prio_queue(&queue);
1127}
Derrick Stoleecbfe3602023-03-20 11:26:55[diff] [blame]1128
1129struct commit_and_index {
1130 struct commit *commit;
1131 unsigned int index;
1132 timestamp_t generation;
1133};
1134
1135static int compare_commit_and_index_by_generation(const void *va, const void *vb)
1136{
1137 const struct commit_and_index *a = (const struct commit_and_index *)va;
1138 const struct commit_and_index *b = (const struct commit_and_index *)vb;
1139
1140 if (a->generation > b->generation)
1141 return 1;
1142 if (a->generation < b->generation)
1143 return -1;
1144 return 0;
1145}
1146
1147void tips_reachable_from_bases(struct repository *r,
1148 struct commit_list *bases,
1149 struct commit **tips, size_t tips_nr,
1150 int mark)
1151{
1152 struct commit_and_index *commits;
1153 size_t min_generation_index = 0;
1154 timestamp_t min_generation;
1155 struct commit_list *stack = NULL;
1156
1157 if (!bases || !tips || !tips_nr)
1158 return;
1159
1160 /*
1161 * Do a depth-first search starting at 'bases' to search for the
1162 * tips. Stop at the lowest (un-found) generation number. When
1163 * finding the lowest commit, increase the minimum generation
1164 * number to the next lowest (un-found) generation number.
1165 */
1166
1167 CALLOC_ARRAY(commits, tips_nr);
1168
1169 for (size_t i = 0; i < tips_nr; i++) {
1170 commits[i].commit = tips[i];
1171 commits[i].index = i;
1172 commits[i].generation = commit_graph_generation(tips[i]);
1173 }
1174
1175 /* Sort with generation number ascending. */
1176 QSORT(commits, tips_nr, compare_commit_and_index_by_generation);
1177 min_generation = commits[0].generation;
1178
1179 while (bases) {
1180 repo_parse_commit(r, bases->item);
1181 commit_list_insert(bases->item, &stack);
1182 bases = bases->next;
1183 }
1184
1185 while (stack) {
1186 int explored_all_parents = 1;
1187 struct commit_list *p;
1188 struct commit *c = stack->item;
1189 timestamp_t c_gen = commit_graph_generation(c);
1190
1191 /* Does it match any of our tips? */
1192 for (size_t j = min_generation_index; j < tips_nr; j++) {
1193 if (c_gen < commits[j].generation)
1194 break;
1195
1196 if (commits[j].commit == c) {
1197 tips[commits[j].index]->object.flags |= mark;
1198
1199 if (j == min_generation_index) {
1200 unsigned int k = j + 1;
1201 while (k < tips_nr &&
1202 (tips[commits[k].index]->object.flags & mark))
1203 k++;
1204
1205 /* Terminate early if all found. */
1206 if (k >= tips_nr)
1207 goto done;
1208
1209 min_generation_index = k;
1210 min_generation = commits[k].generation;
1211 }
1212 }
1213 }
1214
1215 for (p = c->parents; p; p = p->next) {
1216 repo_parse_commit(r, p->item);
1217
1218 /* Have we already explored this parent? */
1219 if (p->item->object.flags & SEEN)
1220 continue;
1221
1222 /* Is it below the current minimum generation? */
1223 if (commit_graph_generation(p->item) < min_generation)
1224 continue;
1225
1226 /* Ok, we will explore from here on. */
1227 p->item->object.flags |= SEEN;
1228 explored_all_parents = 0;
1229 commit_list_insert(p->item, &stack);
1230 break;
1231 }
1232
1233 if (explored_all_parents)
1234 pop_commit(&stack);
1235 }
1236
1237done:
1238 free(commits);
1239 repo_clear_commit_marks(r, SEEN);
Patrick Steinhardtf30bfaf2024-08-01 10:41:15[diff] [blame]1240 free_commit_list(stack);
Derrick Stoleecbfe3602023-03-20 11:26:55[diff] [blame]1241}
Derrick Stoleee32eaf72024-08-14 10:31:27[diff] [blame]1242
1243/*
1244 * This slab initializes integers to zero, so use "-1" for "tip is best" and
1245 * "i + 1" for "bases[i] is best".
1246 */
1247define_commit_slab(best_branch_base, int);
1248static struct best_branch_base best_branch_base;
1249#define get_best(c) (*best_branch_base_at(&best_branch_base, (c)))
1250#define set_best(c,v) (*best_branch_base_at(&best_branch_base, (c)) = (v))
1251
1252int get_branch_base_for_tip(struct repository *r,
1253 struct commit *tip,
1254 struct commit **bases,
1255 size_t bases_nr)
1256{
1257 int best_index = -1;
1258 struct commit *branch_point = NULL;
1259 struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
1260 int found_missing_gen = 0;
1261
1262 if (!bases_nr)
1263 return -1;
1264
1265 repo_parse_commit(r, tip);
1266 if (commit_graph_generation(tip) == GENERATION_NUMBER_INFINITY)
1267 found_missing_gen = 1;
1268
1269 /* Check for missing generation numbers. */
1270 for (size_t i = 0; i < bases_nr; i++) {
1271 struct commit *c = bases[i];
1272 repo_parse_commit(r, c);
1273 if (commit_graph_generation(c) == GENERATION_NUMBER_INFINITY)
1274 found_missing_gen = 1;
1275 }
1276
1277 if (found_missing_gen) {
1278 struct commit **commits;
1279 size_t commits_nr = bases_nr + 1;
1280
1281 CALLOC_ARRAY(commits, commits_nr);
1282 COPY_ARRAY(commits, bases, bases_nr);
1283 commits[bases_nr] = tip;
1284 ensure_generations_valid(r, commits, commits_nr);
1285 free(commits);
1286 }
1287
1288 /* Initialize queue and slab now that generations are guaranteed. */
1289 init_best_branch_base(&best_branch_base);
1290 set_best(tip, -1);
1291 prio_queue_put(&queue, tip);
1292
1293 for (size_t i = 0; i < bases_nr; i++) {
1294 struct commit *c = bases[i];
1295 int best = get_best(c);
1296
1297 /* Has this already been marked as best by another commit? */
1298 if (best) {
1299 if (best == -1) {
1300 /* We agree at this position. Stop now. */
1301 best_index = i + 1;
1302 goto cleanup;
1303 }
1304 continue;
1305 }
1306
1307 set_best(c, i + 1);
1308 prio_queue_put(&queue, c);
1309 }
1310
1311 while (queue.nr) {
1312 struct commit *c = prio_queue_get(&queue);
1313 int best_for_c = get_best(c);
1314 int best_for_p, positive;
1315 struct commit *parent;
1316
1317 /* Have we reached a known branch point? It's optimal. */
1318 if (c == branch_point)
1319 break;
1320
1321 repo_parse_commit(r, c);
1322 if (!c->parents)
1323 continue;
1324
1325 parent = c->parents->item;
1326 repo_parse_commit(r, parent);
1327 best_for_p = get_best(parent);
1328
1329 if (!best_for_p) {
1330 /* 'parent' is new, so pass along best_for_c. */
1331 set_best(parent, best_for_c);
1332 prio_queue_put(&queue, parent);
1333 continue;
1334 }
1335
1336 if (best_for_p > 0 && best_for_c > 0) {
1337 /* Collision among bases. Minimize. */
1338 if (best_for_c < best_for_p)
1339 set_best(parent, best_for_c);
1340 continue;
1341 }
1342
1343 /*
1344 * At this point, we have reached a commit that is reachable
1345 * from the tip, either from 'c' or from an earlier commit to
1346 * have 'parent' as its first parent.
1347 *
1348 * Update 'best_index' to match the minimum of all base indices
1349 * to reach 'parent'.
1350 */
1351
1352 /* Exactly one is positive due to initial conditions. */
1353 positive = (best_for_c < 0) ? best_for_p : best_for_c;
1354
1355 if (best_index < 0 || positive < best_index)
1356 best_index = positive;
1357
1358 /* No matter what, track that the parent is reachable from tip. */
1359 set_best(parent, -1);
1360 branch_point = parent;
1361 }
1362
1363cleanup:
1364 clear_best_branch_base(&best_branch_base);
1365 clear_prio_queue(&queue);
1366 return best_index > 0 ? best_index - 1 : -1;
1367}