1 #include "git-compat-util.h"
3 #include "commit-graph.h"
6 #include "prio-queue.h"
7 #include "ref-filter.h"
10 #include "commit-reach.h"
11 #include "ewah/ewok.h"
13 /* Remember to update object flag allocation in object.h */
14 #define PARENT1 (1u<<16)
15 #define PARENT2 (1u<<17)
16 #define STALE (1u<<18)
17 #define RESULT (1u<<19)
19 static const unsigned all_flags
= (PARENT1
| PARENT2
| STALE
| RESULT
);
21 static int compare_commits_by_gen(const void *_a
, const void *_b
)
23 const struct commit
*a
= *(const struct commit
* const *)_a
;
24 const struct commit
*b
= *(const struct commit
* const *)_b
;
26 timestamp_t generation_a
= commit_graph_generation(a
);
27 timestamp_t generation_b
= commit_graph_generation(b
);
29 if (generation_a
< generation_b
)
31 if (generation_a
> generation_b
)
33 if (a
->date
< b
->date
)
35 if (a
->date
> b
->date
)
40 static int queue_has_nonstale(struct prio_queue
*queue
)
43 for (i
= 0; i
< queue
->nr
; i
++) {
44 struct commit
*commit
= queue
->array
[i
].data
;
45 if (!(commit
->object
.flags
& STALE
))
51 /* all input commits in one and twos[] must have been parsed! */
52 static int paint_down_to_common(struct repository
*r
,
53 struct commit
*one
, int n
,
55 timestamp_t min_generation
,
56 int ignore_missing_commits
,
57 struct commit_list
**result
)
59 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
61 timestamp_t last_gen
= GENERATION_NUMBER_INFINITY
;
63 if (!min_generation
&& !corrected_commit_dates_enabled(r
))
64 queue
.compare
= compare_commits_by_commit_date
;
66 one
->object
.flags
|= PARENT1
;
68 commit_list_append(one
, result
);
71 prio_queue_put(&queue
, one
);
73 for (i
= 0; i
< n
; i
++) {
74 twos
[i
]->object
.flags
|= PARENT2
;
75 prio_queue_put(&queue
, twos
[i
]);
78 while (queue_has_nonstale(&queue
)) {
79 struct commit
*commit
= prio_queue_get(&queue
);
80 struct commit_list
*parents
;
82 timestamp_t generation
= commit_graph_generation(commit
);
84 if (min_generation
&& generation
> last_gen
)
85 BUG("bad generation skip %"PRItime
" > %"PRItime
" at %s",
87 oid_to_hex(&commit
->object
.oid
));
88 last_gen
= generation
;
90 if (generation
< min_generation
)
93 flags
= commit
->object
.flags
& (PARENT1
| PARENT2
| STALE
);
94 if (flags
== (PARENT1
| PARENT2
)) {
95 if (!(commit
->object
.flags
& RESULT
)) {
96 commit
->object
.flags
|= RESULT
;
97 commit_list_insert_by_date(commit
, result
);
99 /* Mark parents of a found merge stale */
102 parents
= commit
->parents
;
104 struct commit
*p
= parents
->item
;
105 parents
= parents
->next
;
106 if ((p
->object
.flags
& flags
) == flags
)
108 if (repo_parse_commit(r
, p
)) {
109 clear_prio_queue(&queue
);
110 free_commit_list(*result
);
113 * At this stage, we know that the commit is
114 * missing: `repo_parse_commit()` uses
115 * `OBJECT_INFO_DIE_IF_CORRUPT` and therefore
116 * corrupt commits would already have been
117 * dispatched with a `die()`.
119 if (ignore_missing_commits
)
121 return error(_("could not parse commit %s"),
122 oid_to_hex(&p
->object
.oid
));
124 p
->object
.flags
|= flags
;
125 prio_queue_put(&queue
, p
);
129 clear_prio_queue(&queue
);
133 static int merge_bases_many(struct repository
*r
,
134 struct commit
*one
, int n
,
135 struct commit
**twos
,
136 struct commit_list
**result
)
138 struct commit_list
*list
= NULL
;
141 for (i
= 0; i
< n
; i
++) {
142 if (one
== twos
[i
]) {
144 * We do not mark this even with RESULT so we do not
145 * have to clean it up.
147 *result
= commit_list_insert(one
, result
);
154 if (repo_parse_commit(r
, one
))
155 return error(_("could not parse commit %s"),
156 oid_to_hex(&one
->object
.oid
));
157 for (i
= 0; i
< n
; i
++) {
160 if (repo_parse_commit(r
, twos
[i
]))
161 return error(_("could not parse commit %s"),
162 oid_to_hex(&twos
[i
]->object
.oid
));
165 if (paint_down_to_common(r
, one
, n
, twos
, 0, 0, &list
)) {
166 free_commit_list(list
);
171 struct commit
*commit
= pop_commit(&list
);
172 if (!(commit
->object
.flags
& STALE
))
173 commit_list_insert_by_date(commit
, result
);
178 int get_octopus_merge_bases(struct commit_list
*in
, struct commit_list
**result
)
180 struct commit_list
*i
, *j
, *k
;
185 commit_list_insert(in
->item
, result
);
187 for (i
= in
->next
; i
; i
= i
->next
) {
188 struct commit_list
*new_commits
= NULL
, *end
= NULL
;
190 for (j
= *result
; j
; j
= j
->next
) {
191 struct commit_list
*bases
= NULL
;
192 if (repo_get_merge_bases(the_repository
, i
->item
,
193 j
->item
, &bases
) < 0) {
194 free_commit_list(bases
);
195 free_commit_list(*result
);
203 for (k
= bases
; k
; k
= k
->next
)
206 free_commit_list(*result
);
207 *result
= new_commits
;
212 static int remove_redundant_no_gen(struct repository
*r
,
213 struct commit
**array
, int cnt
)
215 struct commit
**work
;
216 unsigned char *redundant
;
220 CALLOC_ARRAY(work
, cnt
);
221 redundant
= xcalloc(cnt
, 1);
222 ALLOC_ARRAY(filled_index
, cnt
- 1);
224 for (i
= 0; i
< cnt
; i
++)
225 repo_parse_commit(r
, array
[i
]);
226 for (i
= 0; i
< cnt
; i
++) {
227 struct commit_list
*common
= NULL
;
228 timestamp_t min_generation
= commit_graph_generation(array
[i
]);
232 for (j
= filled
= 0; j
< cnt
; j
++) {
233 timestamp_t curr_generation
;
234 if (i
== j
|| redundant
[j
])
236 filled_index
[filled
] = j
;
237 work
[filled
++] = array
[j
];
239 curr_generation
= commit_graph_generation(array
[j
]);
240 if (curr_generation
< min_generation
)
241 min_generation
= curr_generation
;
243 if (paint_down_to_common(r
, array
[i
], filled
,
244 work
, min_generation
, 0, &common
)) {
245 clear_commit_marks(array
[i
], all_flags
);
246 clear_commit_marks_many(filled
, work
, all_flags
);
247 free_commit_list(common
);
253 if (array
[i
]->object
.flags
& PARENT2
)
255 for (j
= 0; j
< filled
; j
++)
256 if (work
[j
]->object
.flags
& PARENT1
)
257 redundant
[filled_index
[j
]] = 1;
258 clear_commit_marks(array
[i
], all_flags
);
259 clear_commit_marks_many(filled
, work
, all_flags
);
260 free_commit_list(common
);
263 /* Now collect the result */
264 COPY_ARRAY(work
, array
, cnt
);
265 for (i
= filled
= 0; i
< cnt
; i
++)
267 array
[filled
++] = work
[i
];
274 static int remove_redundant_with_gen(struct repository
*r
,
275 struct commit
**array
, int cnt
)
277 int i
, count_non_stale
= 0, count_still_independent
= cnt
;
278 timestamp_t min_generation
= GENERATION_NUMBER_INFINITY
;
279 struct commit
**walk_start
, **sorted
;
280 size_t walk_start_nr
= 0, walk_start_alloc
= cnt
;
284 * Sort the input by generation number, ascending. This allows
285 * us to increase the "min_generation" limit when we discover
286 * the commit with lowest generation is STALE. The index
287 * min_gen_pos points to the current position within 'array'
288 * that is not yet known to be STALE.
290 DUP_ARRAY(sorted
, array
, cnt
);
291 QSORT(sorted
, cnt
, compare_commits_by_gen
);
292 min_generation
= commit_graph_generation(sorted
[0]);
294 ALLOC_ARRAY(walk_start
, walk_start_alloc
);
296 /* Mark all parents of the input as STALE */
297 for (i
= 0; i
< cnt
; i
++) {
298 struct commit_list
*parents
;
300 repo_parse_commit(r
, array
[i
]);
301 array
[i
]->object
.flags
|= RESULT
;
302 parents
= array
[i
]->parents
;
305 repo_parse_commit(r
, parents
->item
);
306 if (!(parents
->item
->object
.flags
& STALE
)) {
307 parents
->item
->object
.flags
|= STALE
;
308 ALLOC_GROW(walk_start
, walk_start_nr
+ 1, walk_start_alloc
);
309 walk_start
[walk_start_nr
++] = parents
->item
;
311 parents
= parents
->next
;
315 QSORT(walk_start
, walk_start_nr
, compare_commits_by_gen
);
317 /* remove STALE bit for now to allow walking through parents */
318 for (i
= 0; i
< walk_start_nr
; i
++)
319 walk_start
[i
]->object
.flags
&= ~STALE
;
322 * Start walking from the highest generation. Hopefully, it will
323 * find all other items during the first-parent walk, and we can
324 * terminate early. Otherwise, we will do the same amount of work
327 for (i
= walk_start_nr
- 1; i
>= 0 && count_still_independent
> 1; i
--) {
328 /* push the STALE bits up to min generation */
329 struct commit_list
*stack
= NULL
;
331 commit_list_insert(walk_start
[i
], &stack
);
332 walk_start
[i
]->object
.flags
|= STALE
;
335 struct commit_list
*parents
;
336 struct commit
*c
= stack
->item
;
338 repo_parse_commit(r
, c
);
340 if (c
->object
.flags
& RESULT
) {
341 c
->object
.flags
&= ~RESULT
;
342 if (--count_still_independent
<= 1)
344 if (oideq(&c
->object
.oid
, &sorted
[min_gen_pos
]->object
.oid
)) {
345 while (min_gen_pos
< cnt
- 1 &&
346 (sorted
[min_gen_pos
]->object
.flags
& STALE
))
348 min_generation
= commit_graph_generation(sorted
[min_gen_pos
]);
352 if (commit_graph_generation(c
) < min_generation
) {
357 parents
= c
->parents
;
359 if (!(parents
->item
->object
.flags
& STALE
)) {
360 parents
->item
->object
.flags
|= STALE
;
361 commit_list_insert(parents
->item
, &stack
);
364 parents
= parents
->next
;
367 /* pop if all parents have been visited already */
371 free_commit_list(stack
);
376 for (i
= 0; i
< cnt
; i
++)
377 array
[i
]->object
.flags
&= ~RESULT
;
379 /* rearrange array */
380 for (i
= count_non_stale
= 0; i
< cnt
; i
++) {
381 if (!(array
[i
]->object
.flags
& STALE
))
382 array
[count_non_stale
++] = array
[i
];
386 clear_commit_marks_many(walk_start_nr
, walk_start
, STALE
);
389 return count_non_stale
;
392 static int remove_redundant(struct repository
*r
, struct commit
**array
, int cnt
)
395 * Some commit in the array may be an ancestor of
396 * another commit. Move the independent commits to the
397 * beginning of 'array' and return their number. Callers
398 * should not rely upon the contents of 'array' after
401 if (generation_numbers_enabled(r
)) {
405 * If we have a single commit with finite generation
406 * number, then the _with_gen algorithm is preferred.
408 for (i
= 0; i
< cnt
; i
++) {
409 if (commit_graph_generation(array
[i
]) < GENERATION_NUMBER_INFINITY
)
410 return remove_redundant_with_gen(r
, array
, cnt
);
414 return remove_redundant_no_gen(r
, array
, cnt
);
417 static int get_merge_bases_many_0(struct repository
*r
,
420 struct commit
**twos
,
422 struct commit_list
**result
)
424 struct commit_list
*list
;
425 struct commit
**rslt
;
428 if (merge_bases_many(r
, one
, n
, twos
, result
) < 0)
430 for (i
= 0; i
< n
; i
++) {
434 if (!*result
|| !(*result
)->next
) {
436 clear_commit_marks(one
, all_flags
);
437 clear_commit_marks_many(n
, twos
, all_flags
);
442 /* There are more than one */
443 cnt
= commit_list_count(*result
);
444 CALLOC_ARRAY(rslt
, cnt
);
445 for (list
= *result
, i
= 0; list
; list
= list
->next
)
446 rslt
[i
++] = list
->item
;
447 free_commit_list(*result
);
450 clear_commit_marks(one
, all_flags
);
451 clear_commit_marks_many(n
, twos
, all_flags
);
453 cnt
= remove_redundant(r
, rslt
, cnt
);
458 for (i
= 0; i
< cnt
; i
++)
459 commit_list_insert_by_date(rslt
[i
], result
);
464 struct commit_list
*repo_get_merge_bases_many(struct repository
*r
,
467 struct commit
**twos
)
469 struct commit_list
*result
= NULL
;
470 if (get_merge_bases_many_0(r
, one
, n
, twos
, 1, &result
) < 0) {
471 free_commit_list(result
);
477 struct commit_list
*repo_get_merge_bases_many_dirty(struct repository
*r
,
480 struct commit
**twos
)
482 struct commit_list
*result
= NULL
;
483 if (get_merge_bases_many_0(r
, one
, n
, twos
, 0, &result
) < 0) {
484 free_commit_list(result
);
490 int repo_get_merge_bases(struct repository
*r
,
493 struct commit_list
**result
)
495 return get_merge_bases_many_0(r
, one
, 1, &two
, 1, result
);
499 * Is "commit" a descendant of one of the elements on the "with_commit" list?
501 int repo_is_descendant_of(struct repository
*r
,
502 struct commit
*commit
,
503 struct commit_list
*with_commit
)
508 if (generation_numbers_enabled(r
)) {
509 struct commit_list
*from_list
= NULL
;
511 commit_list_insert(commit
, &from_list
);
512 result
= can_all_from_reach(from_list
, with_commit
, 0);
513 free_commit_list(from_list
);
516 while (with_commit
) {
517 struct commit
*other
;
520 other
= with_commit
->item
;
521 with_commit
= with_commit
->next
;
522 ret
= repo_in_merge_bases_many(r
, other
, 1, &commit
, 0);
531 * Is "commit" an ancestor of one of the "references"?
533 int repo_in_merge_bases_many(struct repository
*r
, struct commit
*commit
,
534 int nr_reference
, struct commit
**reference
,
535 int ignore_missing_commits
)
537 struct commit_list
*bases
= NULL
;
539 timestamp_t generation
, max_generation
= GENERATION_NUMBER_ZERO
;
541 if (repo_parse_commit(r
, commit
))
542 return ignore_missing_commits
? 0 : -1;
543 for (i
= 0; i
< nr_reference
; i
++) {
544 if (repo_parse_commit(r
, reference
[i
]))
545 return ignore_missing_commits
? 0 : -1;
547 generation
= commit_graph_generation(reference
[i
]);
548 if (generation
> max_generation
)
549 max_generation
= generation
;
552 generation
= commit_graph_generation(commit
);
553 if (generation
> max_generation
)
556 if (paint_down_to_common(r
, commit
,
557 nr_reference
, reference
,
558 generation
, ignore_missing_commits
, &bases
))
560 else if (commit
->object
.flags
& PARENT2
)
562 clear_commit_marks(commit
, all_flags
);
563 clear_commit_marks_many(nr_reference
, reference
, all_flags
);
564 free_commit_list(bases
);
569 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
571 int repo_in_merge_bases(struct repository
*r
,
572 struct commit
*commit
,
573 struct commit
*reference
)
576 struct commit_list
*list
= NULL
;
577 struct commit_list
**next
= &list
;
579 next
= commit_list_append(commit
, next
);
580 res
= repo_is_descendant_of(r
, reference
, list
);
581 free_commit_list(list
);
586 struct commit_list
*reduce_heads(struct commit_list
*heads
)
588 struct commit_list
*p
;
589 struct commit_list
*result
= NULL
, **tail
= &result
;
590 struct commit
**array
;
597 for (p
= heads
; p
; p
= p
->next
)
598 p
->item
->object
.flags
&= ~STALE
;
599 for (p
= heads
, num_head
= 0; p
; p
= p
->next
) {
600 if (p
->item
->object
.flags
& STALE
)
602 p
->item
->object
.flags
|= STALE
;
605 CALLOC_ARRAY(array
, num_head
);
606 for (p
= heads
, i
= 0; p
; p
= p
->next
) {
607 if (p
->item
->object
.flags
& STALE
) {
608 array
[i
++] = p
->item
;
609 p
->item
->object
.flags
&= ~STALE
;
612 num_head
= remove_redundant(the_repository
, array
, num_head
);
617 for (i
= 0; i
< num_head
; i
++)
618 tail
= &commit_list_insert(array
[i
], tail
)->next
;
623 void reduce_heads_replace(struct commit_list
**heads
)
625 struct commit_list
*result
= reduce_heads(*heads
);
626 free_commit_list(*heads
);
630 int ref_newer(const struct object_id
*new_oid
, const struct object_id
*old_oid
)
633 struct commit
*old_commit
, *new_commit
;
634 struct commit_list
*old_commit_list
= NULL
;
638 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
639 * old_commit. Otherwise we require --force.
641 o
= deref_tag(the_repository
, parse_object(the_repository
, old_oid
),
643 if (!o
|| o
->type
!= OBJ_COMMIT
)
645 old_commit
= (struct commit
*) o
;
647 o
= deref_tag(the_repository
, parse_object(the_repository
, new_oid
),
649 if (!o
|| o
->type
!= OBJ_COMMIT
)
651 new_commit
= (struct commit
*) o
;
653 if (repo_parse_commit(the_repository
, new_commit
) < 0)
656 commit_list_insert(old_commit
, &old_commit_list
);
657 ret
= repo_is_descendant_of(the_repository
,
658 new_commit
, old_commit_list
);
661 free_commit_list(old_commit_list
);
666 * Mimicking the real stack, this stack lives on the heap, avoiding stack
669 * At each recursion step, the stack items points to the commits whose
670 * ancestors are to be inspected.
672 struct contains_stack
{
674 struct contains_stack_entry
{
675 struct commit
*commit
;
676 struct commit_list
*parents
;
680 static int in_commit_list(const struct commit_list
*want
, struct commit
*c
)
682 for (; want
; want
= want
->next
)
683 if (oideq(&want
->item
->object
.oid
, &c
->object
.oid
))
689 * Test whether the candidate is contained in the list.
690 * Do not recurse to find out, though, but return -1 if inconclusive.
692 static enum contains_result
contains_test(struct commit
*candidate
,
693 const struct commit_list
*want
,
694 struct contains_cache
*cache
,
697 enum contains_result
*cached
= contains_cache_at(cache
, candidate
);
699 /* If we already have the answer cached, return that. */
704 if (in_commit_list(want
, candidate
)) {
705 *cached
= CONTAINS_YES
;
709 /* Otherwise, we don't know; prepare to recurse */
710 parse_commit_or_die(candidate
);
712 if (commit_graph_generation(candidate
) < cutoff
)
715 return CONTAINS_UNKNOWN
;
718 static void push_to_contains_stack(struct commit
*candidate
, struct contains_stack
*contains_stack
)
720 ALLOC_GROW(contains_stack
->contains_stack
, contains_stack
->nr
+ 1, contains_stack
->alloc
);
721 contains_stack
->contains_stack
[contains_stack
->nr
].commit
= candidate
;
722 contains_stack
->contains_stack
[contains_stack
->nr
++].parents
= candidate
->parents
;
725 static enum contains_result
contains_tag_algo(struct commit
*candidate
,
726 const struct commit_list
*want
,
727 struct contains_cache
*cache
)
729 struct contains_stack contains_stack
= { 0, 0, NULL
};
730 enum contains_result result
;
731 timestamp_t cutoff
= GENERATION_NUMBER_INFINITY
;
732 const struct commit_list
*p
;
734 for (p
= want
; p
; p
= p
->next
) {
735 timestamp_t generation
;
736 struct commit
*c
= p
->item
;
737 load_commit_graph_info(the_repository
, c
);
738 generation
= commit_graph_generation(c
);
739 if (generation
< cutoff
)
743 result
= contains_test(candidate
, want
, cache
, cutoff
);
744 if (result
!= CONTAINS_UNKNOWN
)
747 push_to_contains_stack(candidate
, &contains_stack
);
748 while (contains_stack
.nr
) {
749 struct contains_stack_entry
*entry
= &contains_stack
.contains_stack
[contains_stack
.nr
- 1];
750 struct commit
*commit
= entry
->commit
;
751 struct commit_list
*parents
= entry
->parents
;
754 *contains_cache_at(cache
, commit
) = CONTAINS_NO
;
758 * If we just popped the stack, parents->item has been marked,
759 * therefore contains_test will return a meaningful yes/no.
761 else switch (contains_test(parents
->item
, want
, cache
, cutoff
)) {
763 *contains_cache_at(cache
, commit
) = CONTAINS_YES
;
767 entry
->parents
= parents
->next
;
769 case CONTAINS_UNKNOWN
:
770 push_to_contains_stack(parents
->item
, &contains_stack
);
774 free(contains_stack
.contains_stack
);
775 return contains_test(candidate
, want
, cache
, cutoff
);
778 int commit_contains(struct ref_filter
*filter
, struct commit
*commit
,
779 struct commit_list
*list
, struct contains_cache
*cache
)
781 if (filter
->with_commit_tag_algo
)
782 return contains_tag_algo(commit
, list
, cache
) == CONTAINS_YES
;
783 return repo_is_descendant_of(the_repository
, commit
, list
);
786 int can_all_from_reach_with_flag(struct object_array
*from
,
787 unsigned int with_flag
,
788 unsigned int assign_flag
,
789 time_t min_commit_date
,
790 timestamp_t min_generation
)
792 struct commit
**list
= NULL
;
797 ALLOC_ARRAY(list
, from
->nr
);
799 for (i
= 0; i
< from
->nr
; i
++) {
800 struct object
*from_one
= from
->objects
[i
].item
;
802 if (!from_one
|| from_one
->flags
& assign_flag
)
805 from_one
= deref_tag(the_repository
, from_one
,
807 if (!from_one
|| from_one
->type
!= OBJ_COMMIT
) {
809 * no way to tell if this is reachable by
810 * looking at the ancestry chain alone, so
811 * leave a note to ourselves not to worry about
812 * this object anymore.
814 from
->objects
[i
].item
->flags
|= assign_flag
;
818 list
[nr_commits
] = (struct commit
*)from_one
;
819 if (repo_parse_commit(the_repository
, list
[nr_commits
]) ||
820 commit_graph_generation(list
[nr_commits
]) < min_generation
) {
828 QSORT(list
, nr_commits
, compare_commits_by_gen
);
830 for (i
= 0; i
< nr_commits
; i
++) {
831 /* DFS from list[i] */
832 struct commit_list
*stack
= NULL
;
834 list
[i
]->object
.flags
|= assign_flag
;
835 commit_list_insert(list
[i
], &stack
);
838 struct commit_list
*parent
;
840 if (stack
->item
->object
.flags
& (with_flag
| RESULT
)) {
843 stack
->item
->object
.flags
|= RESULT
;
847 for (parent
= stack
->item
->parents
; parent
; parent
= parent
->next
) {
848 if (parent
->item
->object
.flags
& (with_flag
| RESULT
))
849 stack
->item
->object
.flags
|= RESULT
;
851 if (!(parent
->item
->object
.flags
& assign_flag
)) {
852 parent
->item
->object
.flags
|= assign_flag
;
854 if (repo_parse_commit(the_repository
, parent
->item
) ||
855 parent
->item
->date
< min_commit_date
||
856 commit_graph_generation(parent
->item
) < min_generation
)
859 commit_list_insert(parent
->item
, &stack
);
868 if (!(list
[i
]->object
.flags
& (with_flag
| RESULT
))) {
875 clear_commit_marks_many(nr_commits
, list
, RESULT
| assign_flag
);
878 for (i
= 0; i
< from
->nr
; i
++) {
879 struct object
*from_one
= from
->objects
[i
].item
;
882 from_one
->flags
&= ~assign_flag
;
888 int can_all_from_reach(struct commit_list
*from
, struct commit_list
*to
,
889 int cutoff_by_min_date
)
891 struct object_array from_objs
= OBJECT_ARRAY_INIT
;
892 time_t min_commit_date
= cutoff_by_min_date
? from
->item
->date
: 0;
893 struct commit_list
*from_iter
= from
, *to_iter
= to
;
895 timestamp_t min_generation
= GENERATION_NUMBER_INFINITY
;
898 add_object_array(&from_iter
->item
->object
, NULL
, &from_objs
);
900 if (!repo_parse_commit(the_repository
, from_iter
->item
)) {
901 timestamp_t generation
;
902 if (from_iter
->item
->date
< min_commit_date
)
903 min_commit_date
= from_iter
->item
->date
;
905 generation
= commit_graph_generation(from_iter
->item
);
906 if (generation
< min_generation
)
907 min_generation
= generation
;
910 from_iter
= from_iter
->next
;
914 if (!repo_parse_commit(the_repository
, to_iter
->item
)) {
915 timestamp_t generation
;
916 if (to_iter
->item
->date
< min_commit_date
)
917 min_commit_date
= to_iter
->item
->date
;
919 generation
= commit_graph_generation(to_iter
->item
);
920 if (generation
< min_generation
)
921 min_generation
= generation
;
924 to_iter
->item
->object
.flags
|= PARENT2
;
926 to_iter
= to_iter
->next
;
929 result
= can_all_from_reach_with_flag(&from_objs
, PARENT2
, PARENT1
,
930 min_commit_date
, min_generation
);
933 clear_commit_marks(from
->item
, PARENT1
);
938 clear_commit_marks(to
->item
, PARENT2
);
942 object_array_clear(&from_objs
);
946 struct commit_list
*get_reachable_subset(struct commit
**from
, int nr_from
,
947 struct commit
**to
, int nr_to
,
948 unsigned int reachable_flag
)
950 struct commit
**item
;
951 struct commit
*current
;
952 struct commit_list
*found_commits
= NULL
;
953 struct commit
**to_last
= to
+ nr_to
;
954 struct commit
**from_last
= from
+ nr_from
;
955 timestamp_t min_generation
= GENERATION_NUMBER_INFINITY
;
958 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
960 for (item
= to
; item
< to_last
; item
++) {
961 timestamp_t generation
;
962 struct commit
*c
= *item
;
964 repo_parse_commit(the_repository
, c
);
965 generation
= commit_graph_generation(c
);
966 if (generation
< min_generation
)
967 min_generation
= generation
;
969 if (!(c
->object
.flags
& PARENT1
)) {
970 c
->object
.flags
|= PARENT1
;
975 for (item
= from
; item
< from_last
; item
++) {
976 struct commit
*c
= *item
;
977 if (!(c
->object
.flags
& PARENT2
)) {
978 c
->object
.flags
|= PARENT2
;
979 repo_parse_commit(the_repository
, c
);
981 prio_queue_put(&queue
, *item
);
985 while (num_to_find
&& (current
= prio_queue_get(&queue
)) != NULL
) {
986 struct commit_list
*parents
;
988 if (current
->object
.flags
& PARENT1
) {
989 current
->object
.flags
&= ~PARENT1
;
990 current
->object
.flags
|= reachable_flag
;
991 commit_list_insert(current
, &found_commits
);
995 for (parents
= current
->parents
; parents
; parents
= parents
->next
) {
996 struct commit
*p
= parents
->item
;
998 repo_parse_commit(the_repository
, p
);
1000 if (commit_graph_generation(p
) < min_generation
)
1003 if (p
->object
.flags
& PARENT2
)
1006 p
->object
.flags
|= PARENT2
;
1007 prio_queue_put(&queue
, p
);
1011 clear_prio_queue(&queue
);
1013 clear_commit_marks_many(nr_to
, to
, PARENT1
);
1014 clear_commit_marks_many(nr_from
, from
, PARENT2
);
1016 return found_commits
;
1019 define_commit_slab(bit_arrays
, struct bitmap
*);
1020 static struct bit_arrays bit_arrays
;
1022 static void insert_no_dup(struct prio_queue
*queue
, struct commit
*c
)
1024 if (c
->object
.flags
& PARENT2
)
1026 prio_queue_put(queue
, c
);
1027 c
->object
.flags
|= PARENT2
;
1030 static struct bitmap
*get_bit_array(struct commit
*c
, int width
)
1032 struct bitmap
**bitmap
= bit_arrays_at(&bit_arrays
, c
);
1034 *bitmap
= bitmap_word_alloc(width
);
1038 static void free_bit_array(struct commit
*c
)
1040 struct bitmap
**bitmap
= bit_arrays_at(&bit_arrays
, c
);
1043 bitmap_free(*bitmap
);
1047 void ahead_behind(struct repository
*r
,
1048 struct commit
**commits
, size_t commits_nr
,
1049 struct ahead_behind_count
*counts
, size_t counts_nr
)
1051 struct prio_queue queue
= { .compare
= compare_commits_by_gen_then_commit_date
};
1052 size_t width
= DIV_ROUND_UP(commits_nr
, BITS_IN_EWORD
);
1054 if (!commits_nr
|| !counts_nr
)
1057 for (size_t i
= 0; i
< counts_nr
; i
++) {
1058 counts
[i
].ahead
= 0;
1059 counts
[i
].behind
= 0;
1062 ensure_generations_valid(r
, commits
, commits_nr
);
1064 init_bit_arrays(&bit_arrays
);
1066 for (size_t i
= 0; i
< commits_nr
; i
++) {
1067 struct commit
*c
= commits
[i
];
1068 struct bitmap
*bitmap
= get_bit_array(c
, width
);
1070 bitmap_set(bitmap
, i
);
1071 insert_no_dup(&queue
, c
);
1074 while (queue_has_nonstale(&queue
)) {
1075 struct commit
*c
= prio_queue_get(&queue
);
1076 struct commit_list
*p
;
1077 struct bitmap
*bitmap_c
= get_bit_array(c
, width
);
1079 for (size_t i
= 0; i
< counts_nr
; i
++) {
1080 int reach_from_tip
= !!bitmap_get(bitmap_c
, counts
[i
].tip_index
);
1081 int reach_from_base
= !!bitmap_get(bitmap_c
, counts
[i
].base_index
);
1083 if (reach_from_tip
^ reach_from_base
) {
1084 if (reach_from_base
)
1091 for (p
= c
->parents
; p
; p
= p
->next
) {
1092 struct bitmap
*bitmap_p
;
1094 repo_parse_commit(r
, p
->item
);
1096 bitmap_p
= get_bit_array(p
->item
, width
);
1097 bitmap_or(bitmap_p
, bitmap_c
);
1100 * If this parent is reachable from every starting
1101 * commit, then none of its ancestors can contribute
1102 * to the ahead/behind count. Mark it as STALE, so
1103 * we can stop the walk when every commit in the
1106 if (bitmap_popcount(bitmap_p
) == commits_nr
)
1107 p
->item
->object
.flags
|= STALE
;
1109 insert_no_dup(&queue
, p
->item
);
1115 /* STALE is used here, PARENT2 is used by insert_no_dup(). */
1116 repo_clear_commit_marks(r
, PARENT2
| STALE
);
1117 clear_bit_arrays(&bit_arrays
);
1118 clear_prio_queue(&queue
);
1121 struct commit_and_index
{
1122 struct commit
*commit
;
1124 timestamp_t generation
;
1127 static int compare_commit_and_index_by_generation(const void *va
, const void *vb
)
1129 const struct commit_and_index
*a
= (const struct commit_and_index
*)va
;
1130 const struct commit_and_index
*b
= (const struct commit_and_index
*)vb
;
1132 if (a
->generation
> b
->generation
)
1134 if (a
->generation
< b
->generation
)
1139 void tips_reachable_from_bases(struct repository
*r
,
1140 struct commit_list
*bases
,
1141 struct commit
**tips
, size_t tips_nr
,
1144 struct commit_and_index
*commits
;
1145 size_t min_generation_index
= 0;
1146 timestamp_t min_generation
;
1147 struct commit_list
*stack
= NULL
;
1149 if (!bases
|| !tips
|| !tips_nr
)
1153 * Do a depth-first search starting at 'bases' to search for the
1154 * tips. Stop at the lowest (un-found) generation number. When
1155 * finding the lowest commit, increase the minimum generation
1156 * number to the next lowest (un-found) generation number.
1159 CALLOC_ARRAY(commits
, tips_nr
);
1161 for (size_t i
= 0; i
< tips_nr
; i
++) {
1162 commits
[i
].commit
= tips
[i
];
1163 commits
[i
].index
= i
;
1164 commits
[i
].generation
= commit_graph_generation(tips
[i
]);
1167 /* Sort with generation number ascending. */
1168 QSORT(commits
, tips_nr
, compare_commit_and_index_by_generation
);
1169 min_generation
= commits
[0].generation
;
1172 repo_parse_commit(r
, bases
->item
);
1173 commit_list_insert(bases
->item
, &stack
);
1174 bases
= bases
->next
;
1178 int explored_all_parents
= 1;
1179 struct commit_list
*p
;
1180 struct commit
*c
= stack
->item
;
1181 timestamp_t c_gen
= commit_graph_generation(c
);
1183 /* Does it match any of our tips? */
1184 for (size_t j
= min_generation_index
; j
< tips_nr
; j
++) {
1185 if (c_gen
< commits
[j
].generation
)
1188 if (commits
[j
].commit
== c
) {
1189 tips
[commits
[j
].index
]->object
.flags
|= mark
;
1191 if (j
== min_generation_index
) {
1192 unsigned int k
= j
+ 1;
1193 while (k
< tips_nr
&&
1194 (tips
[commits
[k
].index
]->object
.flags
& mark
))
1197 /* Terminate early if all found. */
1201 min_generation_index
= k
;
1202 min_generation
= commits
[k
].generation
;
1207 for (p
= c
->parents
; p
; p
= p
->next
) {
1208 repo_parse_commit(r
, p
->item
);
1210 /* Have we already explored this parent? */
1211 if (p
->item
->object
.flags
& SEEN
)
1214 /* Is it below the current minimum generation? */
1215 if (commit_graph_generation(p
->item
) < min_generation
)
1218 /* Ok, we will explore from here on. */
1219 p
->item
->object
.flags
|= SEEN
;
1220 explored_all_parents
= 0;
1221 commit_list_insert(p
->item
, &stack
);
1225 if (explored_all_parents
)
1231 repo_clear_commit_marks(r
, SEEN
);