commit-reach: fix memory and flag leaks
[git/git.git] / commit-reach.c
CommitLineData
5227c385 1#include "cache.h"
5227c385 2#include "commit.h"
920f93ca 3#include "commit-graph.h"
1d614d41
DS
4#include "decorate.h"
5#include "prio-queue.h"
6#include "tree.h"
6621c838 7#include "ref-filter.h"
1d614d41
DS
8#include "revision.h"
9#include "tag.h"
5227c385
DS
10#include "commit-reach.h"
11
12/* Remember to update object flag allocation in object.h */
ba3ca1ed 13#define REACHABLE (1u<<15)
5227c385
DS
14#define PARENT1 (1u<<16)
15#define PARENT2 (1u<<17)
16#define STALE (1u<<18)
17#define RESULT (1u<<19)
18
19static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
20
21static int queue_has_nonstale(struct prio_queue *queue)
22{
23 int i;
24 for (i = 0; i < queue->nr; i++) {
25 struct commit *commit = queue->array[i].data;
26 if (!(commit->object.flags & STALE))
27 return 1;
28 }
29 return 0;
30}
31
32/* all input commits in one and twos[] must have been parsed! */
33static struct commit_list *paint_down_to_common(struct commit *one, int n,
34 struct commit **twos,
35 int min_generation)
36{
37 struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
38 struct commit_list *result = NULL;
39 int i;
40 uint32_t last_gen = GENERATION_NUMBER_INFINITY;
41
42 one->object.flags |= PARENT1;
43 if (!n) {
44 commit_list_append(one, &result);
45 return result;
46 }
47 prio_queue_put(&queue, one);
48
49 for (i = 0; i < n; i++) {
50 twos[i]->object.flags |= PARENT2;
51 prio_queue_put(&queue, twos[i]);
52 }
53
54 while (queue_has_nonstale(&queue)) {
55 struct commit *commit = prio_queue_get(&queue);
56 struct commit_list *parents;
57 int flags;
58
59 if (commit->generation > last_gen)
60 BUG("bad generation skip %8x > %8x at %s",
61 commit->generation, last_gen,
62 oid_to_hex(&commit->object.oid));
63 last_gen = commit->generation;
64
65 if (commit->generation < min_generation)
66 break;
67
68 flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
69 if (flags == (PARENT1 | PARENT2)) {
70 if (!(commit->object.flags & RESULT)) {
71 commit->object.flags |= RESULT;
72 commit_list_insert_by_date(commit, &result);
73 }
74 /* Mark parents of a found merge stale */
75 flags |= STALE;
76 }
77 parents = commit->parents;
78 while (parents) {
79 struct commit *p = parents->item;
80 parents = parents->next;
81 if ((p->object.flags & flags) == flags)
82 continue;
83 if (parse_commit(p))
84 return NULL;
85 p->object.flags |= flags;
86 prio_queue_put(&queue, p);
87 }
88 }
89
90 clear_prio_queue(&queue);
91 return result;
92}
93
94static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
95{
96 struct commit_list *list = NULL;
97 struct commit_list *result = NULL;
98 int i;
99
100 for (i = 0; i < n; i++) {
101 if (one == twos[i])
102 /*
103 * We do not mark this even with RESULT so we do not
104 * have to clean it up.
105 */
106 return commit_list_insert(one, &result);
107 }
108
109 if (parse_commit(one))
110 return NULL;
111 for (i = 0; i < n; i++) {
112 if (parse_commit(twos[i]))
113 return NULL;
114 }
115
116 list = paint_down_to_common(one, n, twos, 0);
117
118 while (list) {
119 struct commit *commit = pop_commit(&list);
120 if (!(commit->object.flags & STALE))
121 commit_list_insert_by_date(commit, &result);
122 }
123 return result;
124}
125
126struct commit_list *get_octopus_merge_bases(struct commit_list *in)
127{
128 struct commit_list *i, *j, *k, *ret = NULL;
129
130 if (!in)
131 return ret;
132
133 commit_list_insert(in->item, &ret);
134
135 for (i = in->next; i; i = i->next) {
136 struct commit_list *new_commits = NULL, *end = NULL;
137
138 for (j = ret; j; j = j->next) {
139 struct commit_list *bases;
140 bases = get_merge_bases(i->item, j->item);
141 if (!new_commits)
142 new_commits = bases;
143 else
144 end->next = bases;
145 for (k = bases; k; k = k->next)
146 end = k;
147 }
148 ret = new_commits;
149 }
150 return ret;
151}
152
153static int remove_redundant(struct commit **array, int cnt)
154{
155 /*
156 * Some commit in the array may be an ancestor of
157 * another commit. Move such commit to the end of
158 * the array, and return the number of commits that
159 * are independent from each other.
160 */
161 struct commit **work;
162 unsigned char *redundant;
163 int *filled_index;
164 int i, j, filled;
165
166 work = xcalloc(cnt, sizeof(*work));
167 redundant = xcalloc(cnt, 1);
168 ALLOC_ARRAY(filled_index, cnt - 1);
169
170 for (i = 0; i < cnt; i++)
171 parse_commit(array[i]);
172 for (i = 0; i < cnt; i++) {
173 struct commit_list *common;
174 uint32_t min_generation = array[i]->generation;
175
176 if (redundant[i])
177 continue;
178 for (j = filled = 0; j < cnt; j++) {
179 if (i == j || redundant[j])
180 continue;
181 filled_index[filled] = j;
182 work[filled++] = array[j];
183
184 if (array[j]->generation < min_generation)
185 min_generation = array[j]->generation;
186 }
187 common = paint_down_to_common(array[i], filled, work,
188 min_generation);
189 if (array[i]->object.flags & PARENT2)
190 redundant[i] = 1;
191 for (j = 0; j < filled; j++)
192 if (work[j]->object.flags & PARENT1)
193 redundant[filled_index[j]] = 1;
194 clear_commit_marks(array[i], all_flags);
195 clear_commit_marks_many(filled, work, all_flags);
196 free_commit_list(common);
197 }
198
199 /* Now collect the result */
200 COPY_ARRAY(work, array, cnt);
201 for (i = filled = 0; i < cnt; i++)
202 if (!redundant[i])
203 array[filled++] = work[i];
204 for (j = filled, i = 0; i < cnt; i++)
205 if (redundant[i])
206 array[j++] = work[i];
207 free(work);
208 free(redundant);
209 free(filled_index);
210 return filled;
211}
212
213static struct commit_list *get_merge_bases_many_0(struct commit *one,
214 int n,
215 struct commit **twos,
216 int cleanup)
217{
218 struct commit_list *list;
219 struct commit **rslt;
220 struct commit_list *result;
221 int cnt, i;
222
223 result = merge_bases_many(one, n, twos);
224 for (i = 0; i < n; i++) {
225 if (one == twos[i])
226 return result;
227 }
228 if (!result || !result->next) {
229 if (cleanup) {
230 clear_commit_marks(one, all_flags);
231 clear_commit_marks_many(n, twos, all_flags);
232 }
233 return result;
234 }
235
236 /* There are more than one */
237 cnt = commit_list_count(result);
238 rslt = xcalloc(cnt, sizeof(*rslt));
239 for (list = result, i = 0; list; list = list->next)
240 rslt[i++] = list->item;
241 free_commit_list(result);
242
243 clear_commit_marks(one, all_flags);
244 clear_commit_marks_many(n, twos, all_flags);
245
246 cnt = remove_redundant(rslt, cnt);
247 result = NULL;
248 for (i = 0; i < cnt; i++)
249 commit_list_insert_by_date(rslt[i], &result);
250 free(rslt);
251 return result;
252}
253
254struct commit_list *get_merge_bases_many(struct commit *one,
255 int n,
256 struct commit **twos)
257{
258 return get_merge_bases_many_0(one, n, twos, 1);
259}
260
261struct commit_list *get_merge_bases_many_dirty(struct commit *one,
262 int n,
263 struct commit **twos)
264{
265 return get_merge_bases_many_0(one, n, twos, 0);
266}
267
268struct commit_list *get_merge_bases(struct commit *one, struct commit *two)
269{
270 return get_merge_bases_many_0(one, 1, &two, 1);
271}
272
273/*
274 * Is "commit" a descendant of one of the elements on the "with_commit" list?
275 */
276int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
277{
278 if (!with_commit)
279 return 1;
5227c385 280
6cc01743
DS
281 if (generation_numbers_enabled(the_repository)) {
282 struct commit_list *from_list = NULL;
283 int result;
284 commit_list_insert(commit, &from_list);
285 result = can_all_from_reach(from_list, with_commit, 0);
286 free_commit_list(from_list);
287 return result;
288 } else {
289 while (with_commit) {
290 struct commit *other;
291
292 other = with_commit->item;
293 with_commit = with_commit->next;
294 if (in_merge_bases(other, commit))
295 return 1;
296 }
297 return 0;
5227c385 298 }
5227c385
DS
299}
300
301/*
302 * Is "commit" an ancestor of one of the "references"?
303 */
304int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)
305{
306 struct commit_list *bases;
307 int ret = 0, i;
308 uint32_t min_generation = GENERATION_NUMBER_INFINITY;
309
310 if (parse_commit(commit))
311 return ret;
312 for (i = 0; i < nr_reference; i++) {
313 if (parse_commit(reference[i]))
314 return ret;
315 if (reference[i]->generation < min_generation)
316 min_generation = reference[i]->generation;
317 }
318
319 if (commit->generation > min_generation)
320 return ret;
321
322 bases = paint_down_to_common(commit, nr_reference, reference, commit->generation);
323 if (commit->object.flags & PARENT2)
324 ret = 1;
325 clear_commit_marks(commit, all_flags);
326 clear_commit_marks_many(nr_reference, reference, all_flags);
327 free_commit_list(bases);
328 return ret;
329}
330
331/*
332 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
333 */
334int in_merge_bases(struct commit *commit, struct commit *reference)
335{
336 return in_merge_bases_many(commit, 1, &reference);
337}
338
339struct commit_list *reduce_heads(struct commit_list *heads)
340{
341 struct commit_list *p;
342 struct commit_list *result = NULL, **tail = &result;
343 struct commit **array;
344 int num_head, i;
345
346 if (!heads)
347 return NULL;
348
349 /* Uniquify */
350 for (p = heads; p; p = p->next)
351 p->item->object.flags &= ~STALE;
352 for (p = heads, num_head = 0; p; p = p->next) {
353 if (p->item->object.flags & STALE)
354 continue;
355 p->item->object.flags |= STALE;
356 num_head++;
357 }
358 array = xcalloc(num_head, sizeof(*array));
359 for (p = heads, i = 0; p; p = p->next) {
360 if (p->item->object.flags & STALE) {
361 array[i++] = p->item;
362 p->item->object.flags &= ~STALE;
363 }
364 }
365 num_head = remove_redundant(array, num_head);
366 for (i = 0; i < num_head; i++)
367 tail = &commit_list_insert(array[i], tail)->next;
368 free(array);
369 return result;
370}
371
372void reduce_heads_replace(struct commit_list **heads)
373{
374 struct commit_list *result = reduce_heads(*heads);
375 free_commit_list(*heads);
376 *heads = result;
377}
1d614d41 378
1d614d41
DS
379int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
380{
381 struct object *o;
382 struct commit *old_commit, *new_commit;
1e3497a2 383 struct commit_list *old_commit_list = NULL;
1d614d41
DS
384
385 /*
386 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
387 * old_commit. Otherwise we require --force.
388 */
389 o = deref_tag(the_repository, parse_object(the_repository, old_oid),
390 NULL, 0);
391 if (!o || o->type != OBJ_COMMIT)
392 return 0;
393 old_commit = (struct commit *) o;
394
395 o = deref_tag(the_repository, parse_object(the_repository, new_oid),
396 NULL, 0);
397 if (!o || o->type != OBJ_COMMIT)
398 return 0;
399 new_commit = (struct commit *) o;
400
401 if (parse_commit(new_commit) < 0)
402 return 0;
403
1e3497a2
DS
404 commit_list_insert(old_commit, &old_commit_list);
405 return is_descendant_of(new_commit, old_commit_list);
1d614d41 406}
920f93ca
DS
407
408/*
409 * Mimicking the real stack, this stack lives on the heap, avoiding stack
410 * overflows.
411 *
412 * At each recursion step, the stack items points to the commits whose
413 * ancestors are to be inspected.
414 */
415struct contains_stack {
416 int nr, alloc;
417 struct contains_stack_entry {
418 struct commit *commit;
419 struct commit_list *parents;
420 } *contains_stack;
421};
422
423static int in_commit_list(const struct commit_list *want, struct commit *c)
424{
425 for (; want; want = want->next)
426 if (!oidcmp(&want->item->object.oid, &c->object.oid))
427 return 1;
428 return 0;
429}
430
431/*
432 * Test whether the candidate is contained in the list.
433 * Do not recurse to find out, though, but return -1 if inconclusive.
434 */
435static enum contains_result contains_test(struct commit *candidate,
436 const struct commit_list *want,
437 struct contains_cache *cache,
438 uint32_t cutoff)
439{
440 enum contains_result *cached = contains_cache_at(cache, candidate);
441
442 /* If we already have the answer cached, return that. */
443 if (*cached)
444 return *cached;
445
446 /* or are we it? */
447 if (in_commit_list(want, candidate)) {
448 *cached = CONTAINS_YES;
449 return CONTAINS_YES;
450 }
451
452 /* Otherwise, we don't know; prepare to recurse */
453 parse_commit_or_die(candidate);
454
455 if (candidate->generation < cutoff)
456 return CONTAINS_NO;
457
458 return CONTAINS_UNKNOWN;
459}
460
461static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
462{
463 ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
464 contains_stack->contains_stack[contains_stack->nr].commit = candidate;
465 contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
466}
467
468static enum contains_result contains_tag_algo(struct commit *candidate,
469 const struct commit_list *want,
470 struct contains_cache *cache)
471{
472 struct contains_stack contains_stack = { 0, 0, NULL };
473 enum contains_result result;
474 uint32_t cutoff = GENERATION_NUMBER_INFINITY;
475 const struct commit_list *p;
476
477 for (p = want; p; p = p->next) {
478 struct commit *c = p->item;
479 load_commit_graph_info(the_repository, c);
480 if (c->generation < cutoff)
481 cutoff = c->generation;
482 }
483
484 result = contains_test(candidate, want, cache, cutoff);
485 if (result != CONTAINS_UNKNOWN)
486 return result;
487
488 push_to_contains_stack(candidate, &contains_stack);
489 while (contains_stack.nr) {
490 struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
491 struct commit *commit = entry->commit;
492 struct commit_list *parents = entry->parents;
493
494 if (!parents) {
495 *contains_cache_at(cache, commit) = CONTAINS_NO;
496 contains_stack.nr--;
497 }
498 /*
499 * If we just popped the stack, parents->item has been marked,
500 * therefore contains_test will return a meaningful yes/no.
501 */
502 else switch (contains_test(parents->item, want, cache, cutoff)) {
503 case CONTAINS_YES:
504 *contains_cache_at(cache, commit) = CONTAINS_YES;
505 contains_stack.nr--;
506 break;
507 case CONTAINS_NO:
508 entry->parents = parents->next;
509 break;
510 case CONTAINS_UNKNOWN:
511 push_to_contains_stack(parents->item, &contains_stack);
512 break;
513 }
514 }
515 free(contains_stack.contains_stack);
516 return contains_test(candidate, want, cache, cutoff);
517}
518
519int commit_contains(struct ref_filter *filter, struct commit *commit,
520 struct commit_list *list, struct contains_cache *cache)
521{
522 if (filter->with_commit_tag_algo)
523 return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
524 return is_descendant_of(commit, list);
525}
ba3ca1ed 526
4fbcca4e 527static int compare_commits_by_gen(const void *_a, const void *_b)
ba3ca1ed 528{
4fbcca4e
DS
529 const struct commit *a = (const struct commit *)_a;
530 const struct commit *b = (const struct commit *)_b;
ba3ca1ed 531
4fbcca4e
DS
532 if (a->generation < b->generation)
533 return -1;
534 if (a->generation > b->generation)
535 return 1;
536 return 0;
ba3ca1ed
DS
537}
538
539int can_all_from_reach_with_flag(struct object_array *from,
540 unsigned int with_flag,
541 unsigned int assign_flag,
4fbcca4e
DS
542 time_t min_commit_date,
543 uint32_t min_generation)
ba3ca1ed 544{
4fbcca4e 545 struct commit **list = NULL;
ba3ca1ed 546 int i;
b67f6b26 547 int nr_commits;
4fbcca4e 548 int result = 1;
ba3ca1ed 549
4fbcca4e 550 ALLOC_ARRAY(list, from->nr);
b67f6b26 551 nr_commits = 0;
ba3ca1ed 552 for (i = 0; i < from->nr; i++) {
b67f6b26 553 struct object *from_one = from->objects[i].item;
ba3ca1ed 554
b67f6b26
DS
555 if (!from_one || from_one->flags & assign_flag)
556 continue;
557
558 from_one = deref_tag(the_repository, from_one,
559 "a from object", 0);
560 if (!from_one || from_one->type != OBJ_COMMIT) {
561 /* no way to tell if this is reachable by
562 * looking at the ancestry chain alone, so
563 * leave a note to ourselves not to worry about
564 * this object anymore.
565 */
566 from->objects[i].item->flags |= assign_flag;
567 continue;
568 }
569
570 list[nr_commits] = (struct commit *)from_one;
571 if (parse_commit(list[nr_commits]) ||
572 list[nr_commits]->generation < min_generation) {
573 result = 0;
574 goto cleanup;
575 }
576
577 nr_commits++;
ba3ca1ed 578 }
4fbcca4e 579
b67f6b26 580 QSORT(list, nr_commits, compare_commits_by_gen);
4fbcca4e 581
b67f6b26 582 for (i = 0; i < nr_commits; i++) {
4fbcca4e
DS
583 /* DFS from list[i] */
584 struct commit_list *stack = NULL;
585
586 list[i]->object.flags |= assign_flag;
587 commit_list_insert(list[i], &stack);
588
589 while (stack) {
590 struct commit_list *parent;
591
592 if (stack->item->object.flags & with_flag) {
593 pop_commit(&stack);
594 continue;
595 }
596
597 for (parent = stack->item->parents; parent; parent = parent->next) {
598 if (parent->item->object.flags & (with_flag | RESULT))
599 stack->item->object.flags |= RESULT;
600
601 if (!(parent->item->object.flags & assign_flag)) {
602 parent->item->object.flags |= assign_flag;
603
604 if (parse_commit(parent->item) ||
605 parent->item->date < min_commit_date ||
606 parent->item->generation < min_generation)
607 continue;
608
609 commit_list_insert(parent->item, &stack);
610 break;
611 }
612 }
613
614 if (!parent)
615 pop_commit(&stack);
616 }
617
618 if (!(list[i]->object.flags & (with_flag | RESULT))) {
619 result = 0;
620 goto cleanup;
621 }
622 }
623
624cleanup:
b67f6b26 625 for (i = 0; i < nr_commits; i++) {
4fbcca4e
DS
626 clear_commit_marks(list[i], RESULT);
627 clear_commit_marks(list[i], assign_flag);
628 }
4067a646
DS
629 free(list);
630
631 for (i = 0; i < from->nr; i++)
632 from->objects[i].item->flags &= ~assign_flag;
633
4fbcca4e 634 return result;
ba3ca1ed 635}
1792bc12
DS
636
637int can_all_from_reach(struct commit_list *from, struct commit_list *to,
638 int cutoff_by_min_date)
639{
640 struct object_array from_objs = OBJECT_ARRAY_INIT;
641 time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
642 struct commit_list *from_iter = from, *to_iter = to;
643 int result;
4fbcca4e 644 uint32_t min_generation = GENERATION_NUMBER_INFINITY;
1792bc12
DS
645
646 while (from_iter) {
647 add_object_array(&from_iter->item->object, NULL, &from_objs);
648
649 if (!parse_commit(from_iter->item)) {
650 if (from_iter->item->date < min_commit_date)
651 min_commit_date = from_iter->item->date;
4fbcca4e
DS
652
653 if (from_iter->item->generation < min_generation)
654 min_generation = from_iter->item->generation;
1792bc12
DS
655 }
656
657 from_iter = from_iter->next;
658 }
659
660 while (to_iter) {
661 if (!parse_commit(to_iter->item)) {
662 if (to_iter->item->date < min_commit_date)
663 min_commit_date = to_iter->item->date;
4fbcca4e
DS
664
665 if (to_iter->item->generation < min_generation)
666 min_generation = to_iter->item->generation;
1792bc12
DS
667 }
668
669 to_iter->item->object.flags |= PARENT2;
670
671 to_iter = to_iter->next;
672 }
673
674 result = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,
4fbcca4e 675 min_commit_date, min_generation);
1792bc12
DS
676
677 while (from) {
678 clear_commit_marks(from->item, PARENT1);
679 from = from->next;
680 }
681
682 while (to) {
683 clear_commit_marks(to->item, PARENT2);
684 to = to->next;
685 }
686
687 object_array_clear(&from_objs);
688 return result;
689}