3 #include "commit-graph.h"
5 #include "prio-queue.h"
7 #include "ref-filter.h"
10 #include "commit-reach.h"
12 /* Remember to update object flag allocation in object.h */
13 #define PARENT1 (1u<<16)
14 #define PARENT2 (1u<<17)
15 #define STALE (1u<<18)
16 #define RESULT (1u<<19)
18 static const unsigned all_flags
= (PARENT1
| PARENT2
| STALE
| RESULT
);
20 static int queue_has_nonstale(struct prio_queue
*queue
)
23 for (i
= 0; i
< queue
->nr
; i
++) {
24 struct commit
*commit
= queue
->array
[i
].data
;
25 if (!(commit
->object
.flags
& STALE
))
31 /* all input commits in one and twos[] must have been parsed! */
32 static struct commit_list
*paint_down_to_common(struct repository
*r
,
33 struct commit
*one
, int n
,
37 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
38 struct commit_list
*result
= NULL
;
40 uint32_t last_gen
= GENERATION_NUMBER_INFINITY
;
43 queue
.compare
= compare_commits_by_commit_date
;
45 one
->object
.flags
|= PARENT1
;
47 commit_list_append(one
, &result
);
50 prio_queue_put(&queue
, one
);
52 for (i
= 0; i
< n
; i
++) {
53 twos
[i
]->object
.flags
|= PARENT2
;
54 prio_queue_put(&queue
, twos
[i
]);
57 while (queue_has_nonstale(&queue
)) {
58 struct commit
*commit
= prio_queue_get(&queue
);
59 struct commit_list
*parents
;
62 if (min_generation
&& commit
->generation
> last_gen
)
63 BUG("bad generation skip %8x > %8x at %s",
64 commit
->generation
, last_gen
,
65 oid_to_hex(&commit
->object
.oid
));
66 last_gen
= commit
->generation
;
68 if (commit
->generation
< min_generation
)
71 flags
= commit
->object
.flags
& (PARENT1
| PARENT2
| STALE
);
72 if (flags
== (PARENT1
| PARENT2
)) {
73 if (!(commit
->object
.flags
& RESULT
)) {
74 commit
->object
.flags
|= RESULT
;
75 commit_list_insert_by_date(commit
, &result
);
77 /* Mark parents of a found merge stale */
80 parents
= commit
->parents
;
82 struct commit
*p
= parents
->item
;
83 parents
= parents
->next
;
84 if ((p
->object
.flags
& flags
) == flags
)
86 if (repo_parse_commit(r
, p
))
88 p
->object
.flags
|= flags
;
89 prio_queue_put(&queue
, p
);
93 clear_prio_queue(&queue
);
97 static struct commit_list
*merge_bases_many(struct repository
*r
,
98 struct commit
*one
, int n
,
101 struct commit_list
*list
= NULL
;
102 struct commit_list
*result
= NULL
;
105 for (i
= 0; i
< n
; i
++) {
108 * We do not mark this even with RESULT so we do not
109 * have to clean it up.
111 return commit_list_insert(one
, &result
);
114 if (repo_parse_commit(r
, one
))
116 for (i
= 0; i
< n
; i
++) {
117 if (repo_parse_commit(r
, twos
[i
]))
121 list
= paint_down_to_common(r
, one
, n
, twos
, 0);
124 struct commit
*commit
= pop_commit(&list
);
125 if (!(commit
->object
.flags
& STALE
))
126 commit_list_insert_by_date(commit
, &result
);
131 struct commit_list
*get_octopus_merge_bases(struct commit_list
*in
)
133 struct commit_list
*i
, *j
, *k
, *ret
= NULL
;
138 commit_list_insert(in
->item
, &ret
);
140 for (i
= in
->next
; i
; i
= i
->next
) {
141 struct commit_list
*new_commits
= NULL
, *end
= NULL
;
143 for (j
= ret
; j
; j
= j
->next
) {
144 struct commit_list
*bases
;
145 bases
= get_merge_bases(i
->item
, j
->item
);
150 for (k
= bases
; k
; k
= k
->next
)
158 static int remove_redundant(struct repository
*r
, struct commit
**array
, int cnt
)
161 * Some commit in the array may be an ancestor of
162 * another commit. Move such commit to the end of
163 * the array, and return the number of commits that
164 * are independent from each other.
166 struct commit
**work
;
167 unsigned char *redundant
;
171 work
= xcalloc(cnt
, sizeof(*work
));
172 redundant
= xcalloc(cnt
, 1);
173 ALLOC_ARRAY(filled_index
, cnt
- 1);
175 for (i
= 0; i
< cnt
; i
++)
176 repo_parse_commit(r
, array
[i
]);
177 for (i
= 0; i
< cnt
; i
++) {
178 struct commit_list
*common
;
179 uint32_t min_generation
= array
[i
]->generation
;
183 for (j
= filled
= 0; j
< cnt
; j
++) {
184 if (i
== j
|| redundant
[j
])
186 filled_index
[filled
] = j
;
187 work
[filled
++] = array
[j
];
189 if (array
[j
]->generation
< min_generation
)
190 min_generation
= array
[j
]->generation
;
192 common
= paint_down_to_common(r
, array
[i
], filled
,
193 work
, min_generation
);
194 if (array
[i
]->object
.flags
& PARENT2
)
196 for (j
= 0; j
< filled
; j
++)
197 if (work
[j
]->object
.flags
& PARENT1
)
198 redundant
[filled_index
[j
]] = 1;
199 clear_commit_marks(array
[i
], all_flags
);
200 clear_commit_marks_many(filled
, work
, all_flags
);
201 free_commit_list(common
);
204 /* Now collect the result */
205 COPY_ARRAY(work
, array
, cnt
);
206 for (i
= filled
= 0; i
< cnt
; i
++)
208 array
[filled
++] = work
[i
];
209 for (j
= filled
, i
= 0; i
< cnt
; i
++)
211 array
[j
++] = work
[i
];
218 static struct commit_list
*get_merge_bases_many_0(struct repository
*r
,
221 struct commit
**twos
,
224 struct commit_list
*list
;
225 struct commit
**rslt
;
226 struct commit_list
*result
;
229 result
= merge_bases_many(r
, one
, n
, twos
);
230 for (i
= 0; i
< n
; i
++) {
234 if (!result
|| !result
->next
) {
236 clear_commit_marks(one
, all_flags
);
237 clear_commit_marks_many(n
, twos
, all_flags
);
242 /* There are more than one */
243 cnt
= commit_list_count(result
);
244 rslt
= xcalloc(cnt
, sizeof(*rslt
));
245 for (list
= result
, i
= 0; list
; list
= list
->next
)
246 rslt
[i
++] = list
->item
;
247 free_commit_list(result
);
249 clear_commit_marks(one
, all_flags
);
250 clear_commit_marks_many(n
, twos
, all_flags
);
252 cnt
= remove_redundant(r
, rslt
, cnt
);
254 for (i
= 0; i
< cnt
; i
++)
255 commit_list_insert_by_date(rslt
[i
], &result
);
260 struct commit_list
*repo_get_merge_bases_many(struct repository
*r
,
263 struct commit
**twos
)
265 return get_merge_bases_many_0(r
, one
, n
, twos
, 1);
268 struct commit_list
*repo_get_merge_bases_many_dirty(struct repository
*r
,
271 struct commit
**twos
)
273 return get_merge_bases_many_0(r
, one
, n
, twos
, 0);
276 struct commit_list
*repo_get_merge_bases(struct repository
*r
,
280 return get_merge_bases_many_0(r
, one
, 1, &two
, 1);
284 * Is "commit" a descendant of one of the elements on the "with_commit" list?
286 static int repo_is_descendant_of(struct repository
*r
,
287 struct commit
*commit
,
288 struct commit_list
*with_commit
)
293 if (generation_numbers_enabled(the_repository
)) {
294 struct commit_list
*from_list
= NULL
;
296 commit_list_insert(commit
, &from_list
);
297 result
= can_all_from_reach(from_list
, with_commit
, 0);
298 free_commit_list(from_list
);
301 while (with_commit
) {
302 struct commit
*other
;
304 other
= with_commit
->item
;
305 with_commit
= with_commit
->next
;
306 if (repo_in_merge_bases_many(r
, other
, 1, &commit
))
313 int is_descendant_of(struct commit
*commit
, struct commit_list
*with_commit
)
315 return repo_is_descendant_of(the_repository
, commit
, with_commit
);
319 * Is "commit" an ancestor of one of the "references"?
321 int repo_in_merge_bases_many(struct repository
*r
, struct commit
*commit
,
322 int nr_reference
, struct commit
**reference
)
324 struct commit_list
*bases
;
326 uint32_t min_generation
= GENERATION_NUMBER_INFINITY
;
328 if (repo_parse_commit(r
, commit
))
330 for (i
= 0; i
< nr_reference
; i
++) {
331 if (repo_parse_commit(r
, reference
[i
]))
333 if (reference
[i
]->generation
< min_generation
)
334 min_generation
= reference
[i
]->generation
;
337 if (commit
->generation
> min_generation
)
340 bases
= paint_down_to_common(r
, commit
,
341 nr_reference
, reference
,
343 if (commit
->object
.flags
& PARENT2
)
345 clear_commit_marks(commit
, all_flags
);
346 clear_commit_marks_many(nr_reference
, reference
, all_flags
);
347 free_commit_list(bases
);
352 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
354 int repo_in_merge_bases(struct repository
*r
,
355 struct commit
*commit
,
356 struct commit
*reference
)
359 struct commit_list
*list
= NULL
;
360 struct commit_list
**next
= &list
;
362 next
= commit_list_append(commit
, next
);
363 res
= repo_is_descendant_of(r
, reference
, list
);
364 free_commit_list(list
);
369 struct commit_list
*reduce_heads(struct commit_list
*heads
)
371 struct commit_list
*p
;
372 struct commit_list
*result
= NULL
, **tail
= &result
;
373 struct commit
**array
;
380 for (p
= heads
; p
; p
= p
->next
)
381 p
->item
->object
.flags
&= ~STALE
;
382 for (p
= heads
, num_head
= 0; p
; p
= p
->next
) {
383 if (p
->item
->object
.flags
& STALE
)
385 p
->item
->object
.flags
|= STALE
;
388 array
= xcalloc(num_head
, sizeof(*array
));
389 for (p
= heads
, i
= 0; p
; p
= p
->next
) {
390 if (p
->item
->object
.flags
& STALE
) {
391 array
[i
++] = p
->item
;
392 p
->item
->object
.flags
&= ~STALE
;
395 num_head
= remove_redundant(the_repository
, array
, num_head
);
396 for (i
= 0; i
< num_head
; i
++)
397 tail
= &commit_list_insert(array
[i
], tail
)->next
;
402 void reduce_heads_replace(struct commit_list
**heads
)
404 struct commit_list
*result
= reduce_heads(*heads
);
405 free_commit_list(*heads
);
409 int ref_newer(const struct object_id
*new_oid
, const struct object_id
*old_oid
)
412 struct commit
*old_commit
, *new_commit
;
413 struct commit_list
*old_commit_list
= NULL
;
417 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
418 * old_commit. Otherwise we require --force.
420 o
= deref_tag(the_repository
, parse_object(the_repository
, old_oid
),
422 if (!o
|| o
->type
!= OBJ_COMMIT
)
424 old_commit
= (struct commit
*) o
;
426 o
= deref_tag(the_repository
, parse_object(the_repository
, new_oid
),
428 if (!o
|| o
->type
!= OBJ_COMMIT
)
430 new_commit
= (struct commit
*) o
;
432 if (parse_commit(new_commit
) < 0)
435 commit_list_insert(old_commit
, &old_commit_list
);
436 ret
= is_descendant_of(new_commit
, old_commit_list
);
437 free_commit_list(old_commit_list
);
442 * Mimicking the real stack, this stack lives on the heap, avoiding stack
445 * At each recursion step, the stack items points to the commits whose
446 * ancestors are to be inspected.
448 struct contains_stack
{
450 struct contains_stack_entry
{
451 struct commit
*commit
;
452 struct commit_list
*parents
;
456 static int in_commit_list(const struct commit_list
*want
, struct commit
*c
)
458 for (; want
; want
= want
->next
)
459 if (oideq(&want
->item
->object
.oid
, &c
->object
.oid
))
465 * Test whether the candidate is contained in the list.
466 * Do not recurse to find out, though, but return -1 if inconclusive.
468 static enum contains_result
contains_test(struct commit
*candidate
,
469 const struct commit_list
*want
,
470 struct contains_cache
*cache
,
473 enum contains_result
*cached
= contains_cache_at(cache
, candidate
);
475 /* If we already have the answer cached, return that. */
480 if (in_commit_list(want
, candidate
)) {
481 *cached
= CONTAINS_YES
;
485 /* Otherwise, we don't know; prepare to recurse */
486 parse_commit_or_die(candidate
);
488 if (candidate
->generation
< cutoff
)
491 return CONTAINS_UNKNOWN
;
494 static void push_to_contains_stack(struct commit
*candidate
, struct contains_stack
*contains_stack
)
496 ALLOC_GROW(contains_stack
->contains_stack
, contains_stack
->nr
+ 1, contains_stack
->alloc
);
497 contains_stack
->contains_stack
[contains_stack
->nr
].commit
= candidate
;
498 contains_stack
->contains_stack
[contains_stack
->nr
++].parents
= candidate
->parents
;
501 static enum contains_result
contains_tag_algo(struct commit
*candidate
,
502 const struct commit_list
*want
,
503 struct contains_cache
*cache
)
505 struct contains_stack contains_stack
= { 0, 0, NULL
};
506 enum contains_result result
;
507 uint32_t cutoff
= GENERATION_NUMBER_INFINITY
;
508 const struct commit_list
*p
;
510 for (p
= want
; p
; p
= p
->next
) {
511 struct commit
*c
= p
->item
;
512 load_commit_graph_info(the_repository
, c
);
513 if (c
->generation
< cutoff
)
514 cutoff
= c
->generation
;
517 result
= contains_test(candidate
, want
, cache
, cutoff
);
518 if (result
!= CONTAINS_UNKNOWN
)
521 push_to_contains_stack(candidate
, &contains_stack
);
522 while (contains_stack
.nr
) {
523 struct contains_stack_entry
*entry
= &contains_stack
.contains_stack
[contains_stack
.nr
- 1];
524 struct commit
*commit
= entry
->commit
;
525 struct commit_list
*parents
= entry
->parents
;
528 *contains_cache_at(cache
, commit
) = CONTAINS_NO
;
532 * If we just popped the stack, parents->item has been marked,
533 * therefore contains_test will return a meaningful yes/no.
535 else switch (contains_test(parents
->item
, want
, cache
, cutoff
)) {
537 *contains_cache_at(cache
, commit
) = CONTAINS_YES
;
541 entry
->parents
= parents
->next
;
543 case CONTAINS_UNKNOWN
:
544 push_to_contains_stack(parents
->item
, &contains_stack
);
548 free(contains_stack
.contains_stack
);
549 return contains_test(candidate
, want
, cache
, cutoff
);
552 int commit_contains(struct ref_filter
*filter
, struct commit
*commit
,
553 struct commit_list
*list
, struct contains_cache
*cache
)
555 if (filter
->with_commit_tag_algo
)
556 return contains_tag_algo(commit
, list
, cache
) == CONTAINS_YES
;
557 return is_descendant_of(commit
, list
);
560 static int compare_commits_by_gen(const void *_a
, const void *_b
)
562 const struct commit
*a
= *(const struct commit
* const *)_a
;
563 const struct commit
*b
= *(const struct commit
* const *)_b
;
565 if (a
->generation
< b
->generation
)
567 if (a
->generation
> b
->generation
)
572 int can_all_from_reach_with_flag(struct object_array
*from
,
573 unsigned int with_flag
,
574 unsigned int assign_flag
,
575 time_t min_commit_date
,
576 uint32_t min_generation
)
578 struct commit
**list
= NULL
;
583 ALLOC_ARRAY(list
, from
->nr
);
585 for (i
= 0; i
< from
->nr
; i
++) {
586 struct object
*from_one
= from
->objects
[i
].item
;
588 if (!from_one
|| from_one
->flags
& assign_flag
)
591 from_one
= deref_tag(the_repository
, from_one
,
593 if (!from_one
|| from_one
->type
!= OBJ_COMMIT
) {
595 * no way to tell if this is reachable by
596 * looking at the ancestry chain alone, so
597 * leave a note to ourselves not to worry about
598 * this object anymore.
600 from
->objects
[i
].item
->flags
|= assign_flag
;
604 list
[nr_commits
] = (struct commit
*)from_one
;
605 if (parse_commit(list
[nr_commits
]) ||
606 list
[nr_commits
]->generation
< min_generation
) {
614 QSORT(list
, nr_commits
, compare_commits_by_gen
);
616 for (i
= 0; i
< nr_commits
; i
++) {
617 /* DFS from list[i] */
618 struct commit_list
*stack
= NULL
;
620 list
[i
]->object
.flags
|= assign_flag
;
621 commit_list_insert(list
[i
], &stack
);
624 struct commit_list
*parent
;
626 if (stack
->item
->object
.flags
& (with_flag
| RESULT
)) {
629 stack
->item
->object
.flags
|= RESULT
;
633 for (parent
= stack
->item
->parents
; parent
; parent
= parent
->next
) {
634 if (parent
->item
->object
.flags
& (with_flag
| RESULT
))
635 stack
->item
->object
.flags
|= RESULT
;
637 if (!(parent
->item
->object
.flags
& assign_flag
)) {
638 parent
->item
->object
.flags
|= assign_flag
;
640 if (parse_commit(parent
->item
) ||
641 parent
->item
->date
< min_commit_date
||
642 parent
->item
->generation
< min_generation
)
645 commit_list_insert(parent
->item
, &stack
);
654 if (!(list
[i
]->object
.flags
& (with_flag
| RESULT
))) {
661 clear_commit_marks_many(nr_commits
, list
, RESULT
| assign_flag
);
664 for (i
= 0; i
< from
->nr
; i
++)
665 from
->objects
[i
].item
->flags
&= ~assign_flag
;
670 int can_all_from_reach(struct commit_list
*from
, struct commit_list
*to
,
671 int cutoff_by_min_date
)
673 struct object_array from_objs
= OBJECT_ARRAY_INIT
;
674 time_t min_commit_date
= cutoff_by_min_date
? from
->item
->date
: 0;
675 struct commit_list
*from_iter
= from
, *to_iter
= to
;
677 uint32_t min_generation
= GENERATION_NUMBER_INFINITY
;
680 add_object_array(&from_iter
->item
->object
, NULL
, &from_objs
);
682 if (!parse_commit(from_iter
->item
)) {
683 if (from_iter
->item
->date
< min_commit_date
)
684 min_commit_date
= from_iter
->item
->date
;
686 if (from_iter
->item
->generation
< min_generation
)
687 min_generation
= from_iter
->item
->generation
;
690 from_iter
= from_iter
->next
;
694 if (!parse_commit(to_iter
->item
)) {
695 if (to_iter
->item
->date
< min_commit_date
)
696 min_commit_date
= to_iter
->item
->date
;
698 if (to_iter
->item
->generation
< min_generation
)
699 min_generation
= to_iter
->item
->generation
;
702 to_iter
->item
->object
.flags
|= PARENT2
;
704 to_iter
= to_iter
->next
;
707 result
= can_all_from_reach_with_flag(&from_objs
, PARENT2
, PARENT1
,
708 min_commit_date
, min_generation
);
711 clear_commit_marks(from
->item
, PARENT1
);
716 clear_commit_marks(to
->item
, PARENT2
);
720 object_array_clear(&from_objs
);
724 struct commit_list
*get_reachable_subset(struct commit
**from
, int nr_from
,
725 struct commit
**to
, int nr_to
,
726 unsigned int reachable_flag
)
728 struct commit
**item
;
729 struct commit
*current
;
730 struct commit_list
*found_commits
= NULL
;
731 struct commit
**to_last
= to
+ nr_to
;
732 struct commit
**from_last
= from
+ nr_from
;
733 uint32_t min_generation
= GENERATION_NUMBER_INFINITY
;
736 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
738 for (item
= to
; item
< to_last
; item
++) {
739 struct commit
*c
= *item
;
742 if (c
->generation
< min_generation
)
743 min_generation
= c
->generation
;
745 if (!(c
->object
.flags
& PARENT1
)) {
746 c
->object
.flags
|= PARENT1
;
751 for (item
= from
; item
< from_last
; item
++) {
752 struct commit
*c
= *item
;
753 if (!(c
->object
.flags
& PARENT2
)) {
754 c
->object
.flags
|= PARENT2
;
757 prio_queue_put(&queue
, *item
);
761 while (num_to_find
&& (current
= prio_queue_get(&queue
)) != NULL
) {
762 struct commit_list
*parents
;
764 if (current
->object
.flags
& PARENT1
) {
765 current
->object
.flags
&= ~PARENT1
;
766 current
->object
.flags
|= reachable_flag
;
767 commit_list_insert(current
, &found_commits
);
771 for (parents
= current
->parents
; parents
; parents
= parents
->next
) {
772 struct commit
*p
= parents
->item
;
776 if (p
->generation
< min_generation
)
779 if (p
->object
.flags
& PARENT2
)
782 p
->object
.flags
|= PARENT2
;
783 prio_queue_put(&queue
, p
);
787 clear_commit_marks_many(nr_to
, to
, PARENT1
);
788 clear_commit_marks_many(nr_from
, from
, PARENT2
);
790 return found_commits
;