3 #include "commit-graph.h"
5 #include "prio-queue.h"
7 #include "ref-filter.c"
10 #include "commit-reach.h"
12 /* Remember to update object flag allocation in object.h */
13 #define REACHABLE (1u<<15)
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 queue_has_nonstale(struct prio_queue
*queue
)
24 for (i
= 0; i
< queue
->nr
; i
++) {
25 struct commit
*commit
= queue
->array
[i
].data
;
26 if (!(commit
->object
.flags
& STALE
))
32 /* all input commits in one and twos[] must have been parsed! */
33 static struct commit_list
*paint_down_to_common(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
;
42 one
->object
.flags
|= PARENT1
;
44 commit_list_append(one
, &result
);
47 prio_queue_put(&queue
, one
);
49 for (i
= 0; i
< n
; i
++) {
50 twos
[i
]->object
.flags
|= PARENT2
;
51 prio_queue_put(&queue
, twos
[i
]);
54 while (queue_has_nonstale(&queue
)) {
55 struct commit
*commit
= prio_queue_get(&queue
);
56 struct commit_list
*parents
;
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
;
65 if (commit
->generation
< min_generation
)
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
);
74 /* Mark parents of a found merge stale */
77 parents
= commit
->parents
;
79 struct commit
*p
= parents
->item
;
80 parents
= parents
->next
;
81 if ((p
->object
.flags
& flags
) == flags
)
85 p
->object
.flags
|= flags
;
86 prio_queue_put(&queue
, p
);
90 clear_prio_queue(&queue
);
94 static struct commit_list
*merge_bases_many(struct commit
*one
, int n
, struct commit
**twos
)
96 struct commit_list
*list
= NULL
;
97 struct commit_list
*result
= NULL
;
100 for (i
= 0; i
< n
; i
++) {
103 * We do not mark this even with RESULT so we do not
104 * have to clean it up.
106 return commit_list_insert(one
, &result
);
109 if (parse_commit(one
))
111 for (i
= 0; i
< n
; i
++) {
112 if (parse_commit(twos
[i
]))
116 list
= paint_down_to_common(one
, n
, twos
, 0);
119 struct commit
*commit
= pop_commit(&list
);
120 if (!(commit
->object
.flags
& STALE
))
121 commit_list_insert_by_date(commit
, &result
);
126 struct commit_list
*get_octopus_merge_bases(struct commit_list
*in
)
128 struct commit_list
*i
, *j
, *k
, *ret
= NULL
;
133 commit_list_insert(in
->item
, &ret
);
135 for (i
= in
->next
; i
; i
= i
->next
) {
136 struct commit_list
*new_commits
= NULL
, *end
= NULL
;
138 for (j
= ret
; j
; j
= j
->next
) {
139 struct commit_list
*bases
;
140 bases
= get_merge_bases(i
->item
, j
->item
);
145 for (k
= bases
; k
; k
= k
->next
)
153 static int remove_redundant(struct commit
**array
, int cnt
)
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.
161 struct commit
**work
;
162 unsigned char *redundant
;
166 work
= xcalloc(cnt
, sizeof(*work
));
167 redundant
= xcalloc(cnt
, 1);
168 ALLOC_ARRAY(filled_index
, cnt
- 1);
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
;
178 for (j
= filled
= 0; j
< cnt
; j
++) {
179 if (i
== j
|| redundant
[j
])
181 filled_index
[filled
] = j
;
182 work
[filled
++] = array
[j
];
184 if (array
[j
]->generation
< min_generation
)
185 min_generation
= array
[j
]->generation
;
187 common
= paint_down_to_common(array
[i
], filled
, work
,
189 if (array
[i
]->object
.flags
& PARENT2
)
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
);
199 /* Now collect the result */
200 COPY_ARRAY(work
, array
, cnt
);
201 for (i
= filled
= 0; i
< cnt
; i
++)
203 array
[filled
++] = work
[i
];
204 for (j
= filled
, i
= 0; i
< cnt
; i
++)
206 array
[j
++] = work
[i
];
213 static struct commit_list
*get_merge_bases_many_0(struct commit
*one
,
215 struct commit
**twos
,
218 struct commit_list
*list
;
219 struct commit
**rslt
;
220 struct commit_list
*result
;
223 result
= merge_bases_many(one
, n
, twos
);
224 for (i
= 0; i
< n
; i
++) {
228 if (!result
|| !result
->next
) {
230 clear_commit_marks(one
, all_flags
);
231 clear_commit_marks_many(n
, twos
, all_flags
);
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
);
243 clear_commit_marks(one
, all_flags
);
244 clear_commit_marks_many(n
, twos
, all_flags
);
246 cnt
= remove_redundant(rslt
, cnt
);
248 for (i
= 0; i
< cnt
; i
++)
249 commit_list_insert_by_date(rslt
[i
], &result
);
254 struct commit_list
*get_merge_bases_many(struct commit
*one
,
256 struct commit
**twos
)
258 return get_merge_bases_many_0(one
, n
, twos
, 1);
261 struct commit_list
*get_merge_bases_many_dirty(struct commit
*one
,
263 struct commit
**twos
)
265 return get_merge_bases_many_0(one
, n
, twos
, 0);
268 struct commit_list
*get_merge_bases(struct commit
*one
, struct commit
*two
)
270 return get_merge_bases_many_0(one
, 1, &two
, 1);
274 * Is "commit" a descendant of one of the elements on the "with_commit" list?
276 int is_descendant_of(struct commit
*commit
, struct commit_list
*with_commit
)
280 while (with_commit
) {
281 struct commit
*other
;
283 other
= with_commit
->item
;
284 with_commit
= with_commit
->next
;
285 if (in_merge_bases(other
, commit
))
292 * Is "commit" an ancestor of one of the "references"?
294 int in_merge_bases_many(struct commit
*commit
, int nr_reference
, struct commit
**reference
)
296 struct commit_list
*bases
;
298 uint32_t min_generation
= GENERATION_NUMBER_INFINITY
;
300 if (parse_commit(commit
))
302 for (i
= 0; i
< nr_reference
; i
++) {
303 if (parse_commit(reference
[i
]))
305 if (reference
[i
]->generation
< min_generation
)
306 min_generation
= reference
[i
]->generation
;
309 if (commit
->generation
> min_generation
)
312 bases
= paint_down_to_common(commit
, nr_reference
, reference
, commit
->generation
);
313 if (commit
->object
.flags
& PARENT2
)
315 clear_commit_marks(commit
, all_flags
);
316 clear_commit_marks_many(nr_reference
, reference
, all_flags
);
317 free_commit_list(bases
);
322 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
324 int in_merge_bases(struct commit
*commit
, struct commit
*reference
)
326 return in_merge_bases_many(commit
, 1, &reference
);
329 struct commit_list
*reduce_heads(struct commit_list
*heads
)
331 struct commit_list
*p
;
332 struct commit_list
*result
= NULL
, **tail
= &result
;
333 struct commit
**array
;
340 for (p
= heads
; p
; p
= p
->next
)
341 p
->item
->object
.flags
&= ~STALE
;
342 for (p
= heads
, num_head
= 0; p
; p
= p
->next
) {
343 if (p
->item
->object
.flags
& STALE
)
345 p
->item
->object
.flags
|= STALE
;
348 array
= xcalloc(num_head
, sizeof(*array
));
349 for (p
= heads
, i
= 0; p
; p
= p
->next
) {
350 if (p
->item
->object
.flags
& STALE
) {
351 array
[i
++] = p
->item
;
352 p
->item
->object
.flags
&= ~STALE
;
355 num_head
= remove_redundant(array
, num_head
);
356 for (i
= 0; i
< num_head
; i
++)
357 tail
= &commit_list_insert(array
[i
], tail
)->next
;
362 void reduce_heads_replace(struct commit_list
**heads
)
364 struct commit_list
*result
= reduce_heads(*heads
);
365 free_commit_list(*heads
);
369 static void unmark_and_free(struct commit_list
*list
, unsigned int mark
)
372 struct commit
*commit
= pop_commit(&list
);
373 commit
->object
.flags
&= ~mark
;
377 int ref_newer(const struct object_id
*new_oid
, const struct object_id
*old_oid
)
380 struct commit
*old_commit
, *new_commit
;
381 struct commit_list
*list
, *used
;
385 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
386 * old_commit. Otherwise we require --force.
388 o
= deref_tag(the_repository
, parse_object(the_repository
, old_oid
),
390 if (!o
|| o
->type
!= OBJ_COMMIT
)
392 old_commit
= (struct commit
*) o
;
394 o
= deref_tag(the_repository
, parse_object(the_repository
, new_oid
),
396 if (!o
|| o
->type
!= OBJ_COMMIT
)
398 new_commit
= (struct commit
*) o
;
400 if (parse_commit(new_commit
) < 0)
404 commit_list_insert(new_commit
, &list
);
406 new_commit
= pop_most_recent_commit(&list
, TMP_MARK
);
407 commit_list_insert(new_commit
, &used
);
408 if (new_commit
== old_commit
) {
413 unmark_and_free(list
, TMP_MARK
);
414 unmark_and_free(used
, TMP_MARK
);
419 * Mimicking the real stack, this stack lives on the heap, avoiding stack
422 * At each recursion step, the stack items points to the commits whose
423 * ancestors are to be inspected.
425 struct contains_stack
{
427 struct contains_stack_entry
{
428 struct commit
*commit
;
429 struct commit_list
*parents
;
433 static int in_commit_list(const struct commit_list
*want
, struct commit
*c
)
435 for (; want
; want
= want
->next
)
436 if (!oidcmp(&want
->item
->object
.oid
, &c
->object
.oid
))
442 * Test whether the candidate is contained in the list.
443 * Do not recurse to find out, though, but return -1 if inconclusive.
445 static enum contains_result
contains_test(struct commit
*candidate
,
446 const struct commit_list
*want
,
447 struct contains_cache
*cache
,
450 enum contains_result
*cached
= contains_cache_at(cache
, candidate
);
452 /* If we already have the answer cached, return that. */
457 if (in_commit_list(want
, candidate
)) {
458 *cached
= CONTAINS_YES
;
462 /* Otherwise, we don't know; prepare to recurse */
463 parse_commit_or_die(candidate
);
465 if (candidate
->generation
< cutoff
)
468 return CONTAINS_UNKNOWN
;
471 static void push_to_contains_stack(struct commit
*candidate
, struct contains_stack
*contains_stack
)
473 ALLOC_GROW(contains_stack
->contains_stack
, contains_stack
->nr
+ 1, contains_stack
->alloc
);
474 contains_stack
->contains_stack
[contains_stack
->nr
].commit
= candidate
;
475 contains_stack
->contains_stack
[contains_stack
->nr
++].parents
= candidate
->parents
;
478 static enum contains_result
contains_tag_algo(struct commit
*candidate
,
479 const struct commit_list
*want
,
480 struct contains_cache
*cache
)
482 struct contains_stack contains_stack
= { 0, 0, NULL
};
483 enum contains_result result
;
484 uint32_t cutoff
= GENERATION_NUMBER_INFINITY
;
485 const struct commit_list
*p
;
487 for (p
= want
; p
; p
= p
->next
) {
488 struct commit
*c
= p
->item
;
489 load_commit_graph_info(the_repository
, c
);
490 if (c
->generation
< cutoff
)
491 cutoff
= c
->generation
;
494 result
= contains_test(candidate
, want
, cache
, cutoff
);
495 if (result
!= CONTAINS_UNKNOWN
)
498 push_to_contains_stack(candidate
, &contains_stack
);
499 while (contains_stack
.nr
) {
500 struct contains_stack_entry
*entry
= &contains_stack
.contains_stack
[contains_stack
.nr
- 1];
501 struct commit
*commit
= entry
->commit
;
502 struct commit_list
*parents
= entry
->parents
;
505 *contains_cache_at(cache
, commit
) = CONTAINS_NO
;
509 * If we just popped the stack, parents->item has been marked,
510 * therefore contains_test will return a meaningful yes/no.
512 else switch (contains_test(parents
->item
, want
, cache
, cutoff
)) {
514 *contains_cache_at(cache
, commit
) = CONTAINS_YES
;
518 entry
->parents
= parents
->next
;
520 case CONTAINS_UNKNOWN
:
521 push_to_contains_stack(parents
->item
, &contains_stack
);
525 free(contains_stack
.contains_stack
);
526 return contains_test(candidate
, want
, cache
, cutoff
);
529 int commit_contains(struct ref_filter
*filter
, struct commit
*commit
,
530 struct commit_list
*list
, struct contains_cache
*cache
)
532 if (filter
->with_commit_tag_algo
)
533 return contains_tag_algo(commit
, list
, cache
) == CONTAINS_YES
;
534 return is_descendant_of(commit
, list
);
537 int reachable(struct commit
*from
, unsigned int with_flag
,
538 unsigned int assign_flag
, time_t min_commit_date
)
540 struct prio_queue work
= { compare_commits_by_commit_date
};
542 prio_queue_put(&work
, from
);
544 struct commit_list
*list
;
545 struct commit
*commit
= prio_queue_get(&work
);
547 if (commit
->object
.flags
& with_flag
) {
548 from
->object
.flags
|= assign_flag
;
551 if (!commit
->object
.parsed
)
552 parse_object(the_repository
, &commit
->object
.oid
);
553 if (commit
->object
.flags
& REACHABLE
)
555 commit
->object
.flags
|= REACHABLE
;
556 if (commit
->date
< min_commit_date
)
558 for (list
= commit
->parents
; list
; list
= list
->next
) {
559 struct commit
*parent
= list
->item
;
560 if (!(parent
->object
.flags
& REACHABLE
))
561 prio_queue_put(&work
, parent
);
564 from
->object
.flags
|= REACHABLE
;
565 clear_commit_marks(from
, REACHABLE
);
566 clear_prio_queue(&work
);
567 return (from
->object
.flags
& assign_flag
);
570 int can_all_from_reach_with_flag(struct object_array
*from
,
571 unsigned int with_flag
,
572 unsigned int assign_flag
,
573 time_t min_commit_date
)
577 for (i
= 0; i
< from
->nr
; i
++) {
578 struct object
*from_one
= from
->objects
[i
].item
;
580 if (from_one
->flags
& assign_flag
)
582 from_one
= deref_tag(the_repository
, from_one
, "a from object", 0);
583 if (!from_one
|| from_one
->type
!= OBJ_COMMIT
) {
584 /* no way to tell if this is reachable by
585 * looking at the ancestry chain alone, so
586 * leave a note to ourselves not to worry about
587 * this object anymore.
589 from
->objects
[i
].item
->flags
|= assign_flag
;
592 if (!reachable((struct commit
*)from_one
, with_flag
, assign_flag
,