diff options
Diffstat (limited to 'commit-reach.c')
| -rw-r--r-- | commit-reach.c | 682 |
1 files changed, 551 insertions, 131 deletions
diff --git a/commit-reach.c b/commit-reach.c index 50175b159e..8f9b008f87 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -1,13 +1,14 @@ -#include "cache.h" +#include "git-compat-util.h" #include "commit.h" #include "commit-graph.h" #include "decorate.h" +#include "hex.h" #include "prio-queue.h" -#include "tree.h" #include "ref-filter.h" #include "revision.h" #include "tag.h" #include "commit-reach.h" +#include "ewah/ewok.h" /* Remember to update object flag allocation in object.h */ #define PARENT1 (1u<<16) @@ -17,6 +18,25 @@ static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT); +static int compare_commits_by_gen(const void *_a, const void *_b) +{ + const struct commit *a = *(const struct commit * const *)_a; + const struct commit *b = *(const struct commit * const *)_b; + + timestamp_t generation_a = commit_graph_generation(a); + timestamp_t generation_b = commit_graph_generation(b); + + if (generation_a < generation_b) + return -1; + if (generation_a > generation_b) + return 1; + if (a->date < b->date) + return -1; + if (a->date > b->date) + return 1; + return 0; +} + static int queue_has_nonstale(struct prio_queue *queue) { int i; @@ -29,23 +49,24 @@ static int queue_has_nonstale(struct prio_queue *queue) } /* all input commits in one and twos[] must have been parsed! */ -static struct commit_list *paint_down_to_common(struct repository *r, - struct commit *one, int n, - struct commit **twos, - int min_generation) +static int paint_down_to_common(struct repository *r, + struct commit *one, int n, + struct commit **twos, + timestamp_t min_generation, + int ignore_missing_commits, + struct commit_list **result) { struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; - struct commit_list *result = NULL; int i; - uint32_t last_gen = GENERATION_NUMBER_INFINITY; + timestamp_t last_gen = GENERATION_NUMBER_INFINITY; - if (!min_generation) + if (!min_generation && !corrected_commit_dates_enabled(r)) queue.compare = compare_commits_by_commit_date; one->object.flags |= PARENT1; if (!n) { - commit_list_append(one, &result); - return result; + commit_list_append(one, result); + return 0; } prio_queue_put(&queue, one); @@ -58,10 +79,10 @@ static struct commit_list *paint_down_to_common(struct repository *r, struct commit *commit = prio_queue_get(&queue); struct commit_list *parents; int flags; - uint32_t generation = commit_graph_generation(commit); + timestamp_t generation = commit_graph_generation(commit); if (min_generation && generation > last_gen) - BUG("bad generation skip %8x > %8x at %s", + BUG("bad generation skip %"PRItime" > %"PRItime" at %s", generation, last_gen, oid_to_hex(&commit->object.oid)); last_gen = generation; @@ -73,7 +94,7 @@ static struct commit_list *paint_down_to_common(struct repository *r, if (flags == (PARENT1 | PARENT2)) { if (!(commit->object.flags & RESULT)) { commit->object.flags |= RESULT; - commit_list_insert_by_date(commit, &result); + commit_list_insert_by_date(commit, result); } /* Mark parents of a found merge stale */ flags |= STALE; @@ -84,66 +105,97 @@ static struct commit_list *paint_down_to_common(struct repository *r, parents = parents->next; if ((p->object.flags & flags) == flags) continue; - if (repo_parse_commit(r, p)) - return NULL; + if (repo_parse_commit(r, p)) { + clear_prio_queue(&queue); + free_commit_list(*result); + *result = NULL; + /* + * At this stage, we know that the commit is + * missing: `repo_parse_commit()` uses + * `OBJECT_INFO_DIE_IF_CORRUPT` and therefore + * corrupt commits would already have been + * dispatched with a `die()`. + */ + if (ignore_missing_commits) + return 0; + return error(_("could not parse commit %s"), + oid_to_hex(&p->object.oid)); + } p->object.flags |= flags; prio_queue_put(&queue, p); } } clear_prio_queue(&queue); - return result; + return 0; } -static struct commit_list *merge_bases_many(struct repository *r, - struct commit *one, int n, - struct commit **twos) +static int merge_bases_many(struct repository *r, + struct commit *one, int n, + struct commit **twos, + struct commit_list **result) { struct commit_list *list = NULL; - struct commit_list *result = NULL; int i; for (i = 0; i < n; i++) { - if (one == twos[i]) + if (one == twos[i]) { /* * We do not mark this even with RESULT so we do not * have to clean it up. */ - return commit_list_insert(one, &result); + *result = commit_list_insert(one, result); + return 0; + } } + if (!one) + return 0; if (repo_parse_commit(r, one)) - return NULL; + return error(_("could not parse commit %s"), + oid_to_hex(&one->object.oid)); for (i = 0; i < n; i++) { + if (!twos[i]) + return 0; if (repo_parse_commit(r, twos[i])) - return NULL; + return error(_("could not parse commit %s"), + oid_to_hex(&twos[i]->object.oid)); } - list = paint_down_to_common(r, one, n, twos, 0); + if (paint_down_to_common(r, one, n, twos, 0, 0, &list)) { + free_commit_list(list); + return -1; + } while (list) { struct commit *commit = pop_commit(&list); if (!(commit->object.flags & STALE)) - commit_list_insert_by_date(commit, &result); + commit_list_insert_by_date(commit, result); } - return result; + return 0; } -struct commit_list *get_octopus_merge_bases(struct commit_list *in) +int get_octopus_merge_bases(struct commit_list *in, struct commit_list **result) { - struct commit_list *i, *j, *k, *ret = NULL; + struct commit_list *i, *j, *k; if (!in) - return ret; + return 0; - commit_list_insert(in->item, &ret); + commit_list_insert(in->item, result); for (i = in->next; i; i = i->next) { struct commit_list *new_commits = NULL, *end = NULL; - for (j = ret; j; j = j->next) { - struct commit_list *bases; - bases = get_merge_bases(i->item, j->item); + for (j = *result; j; j = j->next) { + struct commit_list *bases = NULL; + if (repo_get_merge_bases(the_repository, i->item, + j->item, &bases) < 0) { + free_commit_list(bases); + free_commit_list(*result); + *result = NULL; + return -1; + } if (!new_commits) new_commits = bases; else @@ -151,38 +203,34 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in) for (k = bases; k; k = k->next) end = k; } - ret = new_commits; + free_commit_list(*result); + *result = new_commits; } - return ret; + return 0; } -static int remove_redundant(struct repository *r, struct commit **array, int cnt) +static int remove_redundant_no_gen(struct repository *r, + struct commit **array, int cnt) { - /* - * Some commit in the array may be an ancestor of - * another commit. Move such commit to the end of - * the array, and return the number of commits that - * are independent from each other. - */ struct commit **work; unsigned char *redundant; int *filled_index; int i, j, filled; - work = xcalloc(cnt, sizeof(*work)); + CALLOC_ARRAY(work, cnt); redundant = xcalloc(cnt, 1); ALLOC_ARRAY(filled_index, cnt - 1); for (i = 0; i < cnt; i++) repo_parse_commit(r, array[i]); for (i = 0; i < cnt; i++) { - struct commit_list *common; - uint32_t min_generation = commit_graph_generation(array[i]); + struct commit_list *common = NULL; + timestamp_t min_generation = commit_graph_generation(array[i]); if (redundant[i]) continue; for (j = filled = 0; j < cnt; j++) { - uint32_t curr_generation; + timestamp_t curr_generation; if (i == j || redundant[j]) continue; filled_index[filled] = j; @@ -192,8 +240,16 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt if (curr_generation < min_generation) min_generation = curr_generation; } - common = paint_down_to_common(r, array[i], filled, - work, min_generation); + if (paint_down_to_common(r, array[i], filled, + work, min_generation, 0, &common)) { + clear_commit_marks(array[i], all_flags); + clear_commit_marks_many(filled, work, all_flags); + free_commit_list(common); + free(work); + free(redundant); + free(filled_index); + return -1; + } if (array[i]->object.flags & PARENT2) redundant[i] = 1; for (j = 0; j < filled; j++) @@ -209,78 +265,226 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt for (i = filled = 0; i < cnt; i++) if (!redundant[i]) array[filled++] = work[i]; - for (j = filled, i = 0; i < cnt; i++) - if (redundant[i]) - array[j++] = work[i]; free(work); free(redundant); free(filled_index); return filled; } -static struct commit_list *get_merge_bases_many_0(struct repository *r, - struct commit *one, - int n, - struct commit **twos, - int cleanup) +static int remove_redundant_with_gen(struct repository *r, + struct commit **array, int cnt) +{ + int i, count_non_stale = 0, count_still_independent = cnt; + timestamp_t min_generation = GENERATION_NUMBER_INFINITY; + struct commit **walk_start, **sorted; + size_t walk_start_nr = 0, walk_start_alloc = cnt; + int min_gen_pos = 0; + + /* + * Sort the input by generation number, ascending. This allows + * us to increase the "min_generation" limit when we discover + * the commit with lowest generation is STALE. The index + * min_gen_pos points to the current position within 'array' + * that is not yet known to be STALE. + */ + DUP_ARRAY(sorted, array, cnt); + QSORT(sorted, cnt, compare_commits_by_gen); + min_generation = commit_graph_generation(sorted[0]); + + ALLOC_ARRAY(walk_start, walk_start_alloc); + + /* Mark all parents of the input as STALE */ + for (i = 0; i < cnt; i++) { + struct commit_list *parents; + + repo_parse_commit(r, array[i]); + array[i]->object.flags |= RESULT; + parents = array[i]->parents; + + while (parents) { + repo_parse_commit(r, parents->item); + if (!(parents->item->object.flags & STALE)) { + parents->item->object.flags |= STALE; + ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc); + walk_start[walk_start_nr++] = parents->item; + } + parents = parents->next; + } + } + + QSORT(walk_start, walk_start_nr, compare_commits_by_gen); + + /* remove STALE bit for now to allow walking through parents */ + for (i = 0; i < walk_start_nr; i++) + walk_start[i]->object.flags &= ~STALE; + + /* + * Start walking from the highest generation. Hopefully, it will + * find all other items during the first-parent walk, and we can + * terminate early. Otherwise, we will do the same amount of work + * as before. + */ + for (i = walk_start_nr - 1; i >= 0 && count_still_independent > 1; i--) { + /* push the STALE bits up to min generation */ + struct commit_list *stack = NULL; + + commit_list_insert(walk_start[i], &stack); + walk_start[i]->object.flags |= STALE; + + while (stack) { + struct commit_list *parents; + struct commit *c = stack->item; + + repo_parse_commit(r, c); + + if (c->object.flags & RESULT) { + c->object.flags &= ~RESULT; + if (--count_still_independent <= 1) + break; + if (oideq(&c->object.oid, &sorted[min_gen_pos]->object.oid)) { + while (min_gen_pos < cnt - 1 && + (sorted[min_gen_pos]->object.flags & STALE)) + min_gen_pos++; + min_generation = commit_graph_generation(sorted[min_gen_pos]); + } + } + + if (commit_graph_generation(c) < min_generation) { + pop_commit(&stack); + continue; + } + + parents = c->parents; + while (parents) { + if (!(parents->item->object.flags & STALE)) { + parents->item->object.flags |= STALE; + commit_list_insert(parents->item, &stack); + break; + } + parents = parents->next; + } + + /* pop if all parents have been visited already */ + if (!parents) + pop_commit(&stack); + } + free_commit_list(stack); + } + free(sorted); + + /* clear result */ + for (i = 0; i < cnt; i++) + array[i]->object.flags &= ~RESULT; + + /* rearrange array */ + for (i = count_non_stale = 0; i < cnt; i++) { + if (!(array[i]->object.flags & STALE)) + array[count_non_stale++] = array[i]; + } + + /* clear marks */ + clear_commit_marks_many(walk_start_nr, walk_start, STALE); + free(walk_start); + + return count_non_stale; +} + +static int remove_redundant(struct repository *r, struct commit **array, int cnt) +{ + /* + * Some commit in the array may be an ancestor of + * another commit. Move the independent commits to the + * beginning of 'array' and return their number. Callers + * should not rely upon the contents of 'array' after + * that number. + */ + if (generation_numbers_enabled(r)) { + int i; + + /* + * If we have a single commit with finite generation + * number, then the _with_gen algorithm is preferred. + */ + for (i = 0; i < cnt; i++) { + if (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY) + return remove_redundant_with_gen(r, array, cnt); + } + } + + return remove_redundant_no_gen(r, array, cnt); +} + +static int get_merge_bases_many_0(struct repository *r, + struct commit *one, + int n, + struct commit **twos, + int cleanup, + struct commit_list **result) { struct commit_list *list; struct commit **rslt; - struct commit_list *result; int cnt, i; - result = merge_bases_many(r, one, n, twos); + if (merge_bases_many(r, one, n, twos, result) < 0) + return -1; for (i = 0; i < n; i++) { if (one == twos[i]) - return result; + return 0; } - if (!result || !result->next) { + if (!*result || !(*result)->next) { if (cleanup) { clear_commit_marks(one, all_flags); clear_commit_marks_many(n, twos, all_flags); } - return result; + return 0; } /* There are more than one */ - cnt = commit_list_count(result); - rslt = xcalloc(cnt, sizeof(*rslt)); - for (list = result, i = 0; list; list = list->next) + cnt = commit_list_count(*result); + CALLOC_ARRAY(rslt, cnt); + for (list = *result, i = 0; list; list = list->next) rslt[i++] = list->item; - free_commit_list(result); + free_commit_list(*result); + *result = NULL; clear_commit_marks(one, all_flags); clear_commit_marks_many(n, twos, all_flags); cnt = remove_redundant(r, rslt, cnt); - result = NULL; + if (cnt < 0) { + free(rslt); + return -1; + } for (i = 0; i < cnt; i++) - commit_list_insert_by_date(rslt[i], &result); + commit_list_insert_by_date(rslt[i], result); free(rslt); - return result; + return 0; } -struct commit_list *repo_get_merge_bases_many(struct repository *r, - struct commit *one, - int n, - struct commit **twos) +int repo_get_merge_bases_many(struct repository *r, + struct commit *one, + int n, + struct commit **twos, + struct commit_list **result) { - return get_merge_bases_many_0(r, one, n, twos, 1); + return get_merge_bases_many_0(r, one, n, twos, 1, result); } -struct commit_list *repo_get_merge_bases_many_dirty(struct repository *r, - struct commit *one, - int n, - struct commit **twos) +int repo_get_merge_bases_many_dirty(struct repository *r, + struct commit *one, + int n, + struct commit **twos, + struct commit_list **result) { - return get_merge_bases_many_0(r, one, n, twos, 0); + return get_merge_bases_many_0(r, one, n, twos, 0, result); } -struct commit_list *repo_get_merge_bases(struct repository *r, - struct commit *one, - struct commit *two) +int repo_get_merge_bases(struct repository *r, + struct commit *one, + struct commit *two, + struct commit_list **result) { - return get_merge_bases_many_0(r, one, 1, &two, 1); + return get_merge_bases_many_0(r, one, 1, &two, 1, result); } /* @@ -293,7 +497,7 @@ int repo_is_descendant_of(struct repository *r, if (!with_commit) return 1; - if (generation_numbers_enabled(the_repository)) { + if (generation_numbers_enabled(r)) { struct commit_list *from_list = NULL; int result; commit_list_insert(commit, &from_list); @@ -303,11 +507,13 @@ int repo_is_descendant_of(struct repository *r, } else { while (with_commit) { struct commit *other; + int ret; other = with_commit->item; with_commit = with_commit->next; - if (repo_in_merge_bases_many(r, other, 1, &commit)) - return 1; + ret = repo_in_merge_bases_many(r, other, 1, &commit, 0); + if (ret) + return ret; } return 0; } @@ -317,17 +523,18 @@ int repo_is_descendant_of(struct repository *r, * Is "commit" an ancestor of one of the "references"? */ int repo_in_merge_bases_many(struct repository *r, struct commit *commit, - int nr_reference, struct commit **reference) + int nr_reference, struct commit **reference, + int ignore_missing_commits) { - struct commit_list *bases; + struct commit_list *bases = NULL; int ret = 0, i; - uint32_t generation, max_generation = GENERATION_NUMBER_ZERO; + timestamp_t generation, max_generation = GENERATION_NUMBER_ZERO; if (repo_parse_commit(r, commit)) - return ret; + return ignore_missing_commits ? 0 : -1; for (i = 0; i < nr_reference; i++) { if (repo_parse_commit(r, reference[i])) - return ret; + return ignore_missing_commits ? 0 : -1; generation = commit_graph_generation(reference[i]); if (generation > max_generation) @@ -338,10 +545,11 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit, if (generation > max_generation) return ret; - bases = paint_down_to_common(r, commit, - nr_reference, reference, - generation); - if (commit->object.flags & PARENT2) + if (paint_down_to_common(r, commit, + nr_reference, reference, + generation, ignore_missing_commits, &bases)) + ret = -1; + else if (commit->object.flags & PARENT2) ret = 1; clear_commit_marks(commit, all_flags); clear_commit_marks_many(nr_reference, reference, all_flags); @@ -386,7 +594,7 @@ struct commit_list *reduce_heads(struct commit_list *heads) p->item->object.flags |= STALE; num_head++; } - array = xcalloc(num_head, sizeof(*array)); + CALLOC_ARRAY(array, num_head); for (p = heads, i = 0; p; p = p->next) { if (p->item->object.flags & STALE) { array[i++] = p->item; @@ -394,6 +602,10 @@ struct commit_list *reduce_heads(struct commit_list *heads) } } num_head = remove_redundant(the_repository, array, num_head); + if (num_head < 0) { + free(array); + return NULL; + } for (i = 0; i < num_head; i++) tail = &commit_list_insert(array[i], tail)->next; free(array); @@ -430,12 +642,14 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid) return 0; new_commit = (struct commit *) o; - if (parse_commit(new_commit) < 0) + if (repo_parse_commit(the_repository, new_commit) < 0) return 0; commit_list_insert(old_commit, &old_commit_list); ret = repo_is_descendant_of(the_repository, new_commit, old_commit_list); + if (ret < 0) + exit(128); free_commit_list(old_commit_list); return ret; } @@ -470,7 +684,7 @@ static int in_commit_list(const struct commit_list *want, struct commit *c) static enum contains_result contains_test(struct commit *candidate, const struct commit_list *want, struct contains_cache *cache, - uint32_t cutoff) + timestamp_t cutoff) { enum contains_result *cached = contains_cache_at(cache, candidate); @@ -506,11 +720,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate, { struct contains_stack contains_stack = { 0, 0, NULL }; enum contains_result result; - uint32_t cutoff = GENERATION_NUMBER_INFINITY; + timestamp_t cutoff = GENERATION_NUMBER_INFINITY; const struct commit_list *p; for (p = want; p; p = p->next) { - uint32_t generation; + timestamp_t generation; struct commit *c = p->item; load_commit_graph_info(the_repository, c); generation = commit_graph_generation(c); @@ -561,26 +775,11 @@ int commit_contains(struct ref_filter *filter, struct commit *commit, return repo_is_descendant_of(the_repository, commit, list); } -static int compare_commits_by_gen(const void *_a, const void *_b) -{ - const struct commit *a = *(const struct commit * const *)_a; - const struct commit *b = *(const struct commit * const *)_b; - - uint32_t generation_a = commit_graph_generation(a); - uint32_t generation_b = commit_graph_generation(b); - - if (generation_a < generation_b) - return -1; - if (generation_a > generation_b) - return 1; - return 0; -} - int can_all_from_reach_with_flag(struct object_array *from, unsigned int with_flag, unsigned int assign_flag, time_t min_commit_date, - uint32_t min_generation) + timestamp_t min_generation) { struct commit **list = NULL; int i; @@ -609,7 +808,7 @@ int can_all_from_reach_with_flag(struct object_array *from, } list[nr_commits] = (struct commit *)from_one; - if (parse_commit(list[nr_commits]) || + if (repo_parse_commit(the_repository, list[nr_commits]) || commit_graph_generation(list[nr_commits]) < min_generation) { result = 0; goto cleanup; @@ -644,7 +843,7 @@ int can_all_from_reach_with_flag(struct object_array *from, if (!(parent->item->object.flags & assign_flag)) { parent->item->object.flags |= assign_flag; - if (parse_commit(parent->item) || + if (repo_parse_commit(the_repository, parent->item) || parent->item->date < min_commit_date || commit_graph_generation(parent->item) < min_generation) continue; @@ -668,8 +867,12 @@ cleanup: clear_commit_marks_many(nr_commits, list, RESULT | assign_flag); free(list); - for (i = 0; i < from->nr; i++) - from->objects[i].item->flags &= ~assign_flag; + for (i = 0; i < from->nr; i++) { + struct object *from_one = from->objects[i].item; + + if (from_one) + from_one->flags &= ~assign_flag; + } return result; } @@ -681,13 +884,13 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to, time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0; struct commit_list *from_iter = from, *to_iter = to; int result; - uint32_t min_generation = GENERATION_NUMBER_INFINITY; + timestamp_t min_generation = GENERATION_NUMBER_INFINITY; while (from_iter) { add_object_array(&from_iter->item->object, NULL, &from_objs); - if (!parse_commit(from_iter->item)) { - uint32_t generation; + if (!repo_parse_commit(the_repository, from_iter->item)) { + timestamp_t generation; if (from_iter->item->date < min_commit_date) min_commit_date = from_iter->item->date; @@ -700,8 +903,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to, } while (to_iter) { - if (!parse_commit(to_iter->item)) { - uint32_t generation; + if (!repo_parse_commit(the_repository, to_iter->item)) { + timestamp_t generation; if (to_iter->item->date < min_commit_date) min_commit_date = to_iter->item->date; @@ -741,16 +944,16 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, struct commit_list *found_commits = NULL; struct commit **to_last = to + nr_to; struct commit **from_last = from + nr_from; - uint32_t min_generation = GENERATION_NUMBER_INFINITY; + timestamp_t min_generation = GENERATION_NUMBER_INFINITY; int num_to_find = 0; struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; for (item = to; item < to_last; item++) { - uint32_t generation; + timestamp_t generation; struct commit *c = *item; - parse_commit(c); + repo_parse_commit(the_repository, c); generation = commit_graph_generation(c); if (generation < min_generation) min_generation = generation; @@ -765,7 +968,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, struct commit *c = *item; if (!(c->object.flags & PARENT2)) { c->object.flags |= PARENT2; - parse_commit(c); + repo_parse_commit(the_repository, c); prio_queue_put(&queue, *item); } @@ -784,7 +987,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, for (parents = current->parents; parents; parents = parents->next) { struct commit *p = parents->item; - parse_commit(p); + repo_parse_commit(the_repository, p); if (commit_graph_generation(p) < min_generation) continue; @@ -797,8 +1000,225 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, } } + clear_prio_queue(&queue); + clear_commit_marks_many(nr_to, to, PARENT1); clear_commit_marks_many(nr_from, from, PARENT2); return found_commits; } + +define_commit_slab(bit_arrays, struct bitmap *); +static struct bit_arrays bit_arrays; + +static void insert_no_dup(struct prio_queue *queue, struct commit *c) +{ + if (c->object.flags & PARENT2) + return; + prio_queue_put(queue, c); + c->object.flags |= PARENT2; +} + +static struct bitmap *get_bit_array(struct commit *c, int width) +{ + struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c); + if (!*bitmap) + *bitmap = bitmap_word_alloc(width); + return *bitmap; +} + +static void free_bit_array(struct commit *c) +{ + struct bitmap **bitmap = bit_arrays_at(&bit_arrays, c); + if (!*bitmap) + return; + bitmap_free(*bitmap); + *bitmap = NULL; +} + +void ahead_behind(struct repository *r, + struct commit **commits, size_t commits_nr, + struct ahead_behind_count *counts, size_t counts_nr) +{ + struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date }; + size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD); + + if (!commits_nr || !counts_nr) + return; + + for (size_t i = 0; i < counts_nr; i++) { + counts[i].ahead = 0; + counts[i].behind = 0; + } + + ensure_generations_valid(r, commits, commits_nr); + + init_bit_arrays(&bit_arrays); + + for (size_t i = 0; i < commits_nr; i++) { + struct commit *c = commits[i]; + struct bitmap *bitmap = get_bit_array(c, width); + + bitmap_set(bitmap, i); + insert_no_dup(&queue, c); + } + + while (queue_has_nonstale(&queue)) { + struct commit *c = prio_queue_get(&queue); + struct commit_list *p; + struct bitmap *bitmap_c = get_bit_array(c, width); + + for (size_t i = 0; i < counts_nr; i++) { + int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index); + int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index); + + if (reach_from_tip ^ reach_from_base) { + if (reach_from_base) + counts[i].behind++; + else + counts[i].ahead++; + } + } + + for (p = c->parents; p; p = p->next) { + struct bitmap *bitmap_p; + + repo_parse_commit(r, p->item); + + bitmap_p = get_bit_array(p->item, width); + bitmap_or(bitmap_p, bitmap_c); + + /* + * If this parent is reachable from every starting + * commit, then none of its ancestors can contribute + * to the ahead/behind count. Mark it as STALE, so + * we can stop the walk when every commit in the + * queue is STALE. + */ + if (bitmap_popcount(bitmap_p) == commits_nr) + p->item->object.flags |= STALE; + + insert_no_dup(&queue, p->item); + } + + free_bit_array(c); + } + + /* STALE is used here, PARENT2 is used by insert_no_dup(). */ + repo_clear_commit_marks(r, PARENT2 | STALE); + clear_bit_arrays(&bit_arrays); + clear_prio_queue(&queue); +} + +struct commit_and_index { + struct commit *commit; + unsigned int index; + timestamp_t generation; +}; + +static int compare_commit_and_index_by_generation(const void *va, const void *vb) +{ + const struct commit_and_index *a = (const struct commit_and_index *)va; + const struct commit_and_index *b = (const struct commit_and_index *)vb; + + if (a->generation > b->generation) + return 1; + if (a->generation < b->generation) + return -1; + return 0; +} + +void tips_reachable_from_bases(struct repository *r, + struct commit_list *bases, + struct commit **tips, size_t tips_nr, + int mark) +{ + struct commit_and_index *commits; + size_t min_generation_index = 0; + timestamp_t min_generation; + struct commit_list *stack = NULL; + + if (!bases || !tips || !tips_nr) + return; + + /* + * Do a depth-first search starting at 'bases' to search for the + * tips. Stop at the lowest (un-found) generation number. When + * finding the lowest commit, increase the minimum generation + * number to the next lowest (un-found) generation number. + */ + + CALLOC_ARRAY(commits, tips_nr); + + for (size_t i = 0; i < tips_nr; i++) { + commits[i].commit = tips[i]; + commits[i].index = i; + commits[i].generation = commit_graph_generation(tips[i]); + } + + /* Sort with generation number ascending. */ + QSORT(commits, tips_nr, compare_commit_and_index_by_generation); + min_generation = commits[0].generation; + + while (bases) { + repo_parse_commit(r, bases->item); + commit_list_insert(bases->item, &stack); + bases = bases->next; + } + + while (stack) { + int explored_all_parents = 1; + struct commit_list *p; + struct commit *c = stack->item; + timestamp_t c_gen = commit_graph_generation(c); + + /* Does it match any of our tips? */ + for (size_t j = min_generation_index; j < tips_nr; j++) { + if (c_gen < commits[j].generation) + break; + + if (commits[j].commit == c) { + tips[commits[j].index]->object.flags |= mark; + + if (j == min_generation_index) { + unsigned int k = j + 1; + while (k < tips_nr && + (tips[commits[k].index]->object.flags & mark)) + k++; + + /* Terminate early if all found. */ + if (k >= tips_nr) + goto done; + + min_generation_index = k; + min_generation = commits[k].generation; + } + } + } + + for (p = c->parents; p; p = p->next) { + repo_parse_commit(r, p->item); + + /* Have we already explored this parent? */ + if (p->item->object.flags & SEEN) + continue; + + /* Is it below the current minimum generation? */ + if (commit_graph_generation(p->item) < min_generation) + continue; + + /* Ok, we will explore from here on. */ + p->item->object.flags |= SEEN; + explored_all_parents = 0; + commit_list_insert(p->item, &stack); + break; + } + + if (explored_all_parents) + pop_commit(&stack); + } + +done: + free(commits); + repo_clear_commit_marks(r, SEEN); +} |