diff options
| -rw-r--r-- | Documentation/git-for-each-ref.txt | 12 | ||||
| -rw-r--r-- | builtin/branch.c | 1 | ||||
| -rw-r--r-- | builtin/for-each-ref.c | 26 | ||||
| -rw-r--r-- | builtin/tag.c | 1 | ||||
| -rw-r--r-- | commit-graph.c | 207 | ||||
| -rw-r--r-- | commit-graph.h | 8 | ||||
| -rw-r--r-- | commit-reach.c | 216 | ||||
| -rw-r--r-- | commit-reach.h | 40 | ||||
| -rw-r--r-- | ref-filter.c | 93 | ||||
| -rw-r--r-- | ref-filter.h | 26 | ||||
| -rwxr-xr-x | t/perf/p1500-graph-walks.sh | 50 | ||||
| -rwxr-xr-x | t/t3203-branch-output.sh | 14 | ||||
| -rwxr-xr-x | t/t5318-commit-graph.sh | 2 | ||||
| -rwxr-xr-x | t/t6300-for-each-ref.sh | 50 | ||||
| -rwxr-xr-x | t/t6301-for-each-ref-errors.sh | 14 | ||||
| -rwxr-xr-x | t/t6600-test-reach.sh | 169 | ||||
| -rwxr-xr-x | t/t7004-tag.sh | 28 |
17 files changed, 866 insertions, 91 deletions
diff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt index 6da899c629..0713e49b49 100644 --- a/Documentation/git-for-each-ref.txt +++ b/Documentation/git-for-each-ref.txt @@ -9,7 +9,8 @@ SYNOPSIS -------- [verse] 'git for-each-ref' [--count=<count>] [--shell|--perl|--python|--tcl] - [(--sort=<key>)...] [--format=<format>] [<pattern>...] + [(--sort=<key>)...] [--format=<format>] + [ --stdin | <pattern>... ] [--points-at=<object>] [--merged[=<object>]] [--no-merged[=<object>]] [--contains[=<object>]] [--no-contains[=<object>]] @@ -32,6 +33,10 @@ OPTIONS literally, in the latter case matching completely or from the beginning up to a slash. +--stdin:: + If `--stdin` is supplied, then the list of patterns is read from + standard input instead of from the argument list. + --count=<count>:: By default the command shows all refs that match `<pattern>`. This option makes it stop after showing @@ -217,6 +222,11 @@ worktreepath:: out, if it is checked out in any linked worktree. Empty string otherwise. +ahead-behind:<committish>:: + Two integers, separated by a space, demonstrating the number of + commits ahead and behind, respectively, when comparing the output + ref to the `<committish>` specified in the format. + In addition to the above, for commit and tag objects, the header field names (`tree`, `parent`, `object`, `type`, and `tag`) can be used to specify the value in the header field. diff --git a/builtin/branch.c b/builtin/branch.c index f63fd45edb..0554d7cebb 100644 --- a/builtin/branch.c +++ b/builtin/branch.c @@ -448,6 +448,7 @@ static void print_ref_list(struct ref_filter *filter, struct ref_sorting *sortin if (verify_ref_format(format)) die(_("unable to parse format string")); + filter_ahead_behind(the_repository, format, &array); ref_array_sort(sorting, &array); for (i = 0; i < array.nr; i++) { diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c index 6f62f40d12..6b3d07ef40 100644 --- a/builtin/for-each-ref.c +++ b/builtin/for-each-ref.c @@ -5,6 +5,8 @@ #include "object.h" #include "parse-options.h" #include "ref-filter.h" +#include "strvec.h" +#include "commit-reach.h" static char const * const for_each_ref_usage[] = { N_("git for-each-ref [<options>] [<pattern>]"), @@ -25,6 +27,8 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix) struct ref_format format = REF_FORMAT_INIT; struct strbuf output = STRBUF_INIT; struct strbuf err = STRBUF_INIT; + int from_stdin = 0; + struct strvec vec = STRVEC_INIT; struct option opts[] = { OPT_BIT('s', "shell", &format.quote_style, @@ -49,6 +53,7 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix) OPT_CONTAINS(&filter.with_commit, N_("print only refs which contain the commit")), OPT_NO_CONTAINS(&filter.no_commit, N_("print only refs which don't contain the commit")), OPT_BOOL(0, "ignore-case", &icase, N_("sorting and filtering are case insensitive")), + OPT_BOOL(0, "stdin", &from_stdin, N_("read reference patterns from stdin")), OPT_END(), }; @@ -75,9 +80,27 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix) ref_sorting_set_sort_flags_all(sorting, REF_SORTING_ICASE, icase); filter.ignore_case = icase; - filter.name_patterns = argv; + if (from_stdin) { + struct strbuf line = STRBUF_INIT; + + if (argv[0]) + die(_("unknown arguments supplied with --stdin")); + + while (strbuf_getline(&line, stdin) != EOF) + strvec_push(&vec, line.buf); + + strbuf_release(&line); + + /* vec.v is NULL-terminated, just like 'argv'. */ + filter.name_patterns = vec.v; + } else { + filter.name_patterns = argv; + } + filter.match_as_path = 1; filter_refs(&array, &filter, FILTER_REFS_ALL); + filter_ahead_behind(the_repository, &format, &array); + ref_array_sort(sorting, &array); if (!maxcount || array.nr < maxcount) @@ -97,5 +120,6 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix) free_commit_list(filter.with_commit); free_commit_list(filter.no_commit); ref_sorting_release(sorting); + strvec_clear(&vec); return 0; } diff --git a/builtin/tag.c b/builtin/tag.c index adcaa547b0..7e2f686600 100644 --- a/builtin/tag.c +++ b/builtin/tag.c @@ -67,6 +67,7 @@ static int list_tags(struct ref_filter *filter, struct ref_sorting *sorting, die(_("unable to parse format string")); filter->with_commit_tag_algo = 1; filter_refs(&array, filter, FILTER_REFS_TAGS); + filter_ahead_behind(the_repository, format, &array); ref_array_sort(sorting, &array); for (i = 0; i < array.nr; i++) { diff --git a/commit-graph.c b/commit-graph.c index 5e6098ff35..2ad09f35da 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -117,12 +117,10 @@ timestamp_t commit_graph_generation(const struct commit *c) struct commit_graph_data *data = commit_graph_data_slab_peek(&commit_graph_data_slab, c); - if (!data) - return GENERATION_NUMBER_INFINITY; - else if (data->graph_pos == COMMIT_NOT_FROM_GRAPH) - return GENERATION_NUMBER_INFINITY; + if (data && data->generation) + return data->generation; - return data->generation; + return GENERATION_NUMBER_INFINITY; } static struct commit_graph_data *commit_graph_data_at(const struct commit *c) @@ -1447,24 +1445,52 @@ static void close_reachable(struct write_commit_graph_context *ctx) stop_progress(&ctx->progress); } -static void compute_topological_levels(struct write_commit_graph_context *ctx) +struct compute_generation_info { + struct repository *r; + struct packed_commit_list *commits; + struct progress *progress; + int progress_cnt; + + timestamp_t (*get_generation)(struct commit *c, void *data); + void (*set_generation)(struct commit *c, timestamp_t gen, void *data); + void *data; +}; + +static timestamp_t compute_generation_from_max(struct commit *c, + timestamp_t max_gen, + int generation_version) +{ + switch (generation_version) { + case 1: /* topological levels */ + if (max_gen > GENERATION_NUMBER_V1_MAX - 1) + max_gen = GENERATION_NUMBER_V1_MAX - 1; + return max_gen + 1; + + case 2: /* corrected commit date */ + if (c->date && c->date > max_gen) + max_gen = c->date - 1; + return max_gen + 1; + + default: + BUG("attempting unimplemented version"); + } +} + +static void compute_reachable_generation_numbers( + struct compute_generation_info *info, + int generation_version) { int i; struct commit_list *list = NULL; - if (ctx->report_progress) - ctx->progress = start_delayed_progress( - _("Computing commit graph topological levels"), - ctx->commits.nr); - for (i = 0; i < ctx->commits.nr; i++) { - struct commit *c = ctx->commits.list[i]; - uint32_t level; - - repo_parse_commit(ctx->r, c); - level = *topo_level_slab_at(ctx->topo_levels, c); + for (i = 0; i < info->commits->nr; i++) { + struct commit *c = info->commits->list[i]; + timestamp_t gen; + repo_parse_commit(info->r, c); + gen = info->get_generation(c, info->data); + display_progress(info->progress, info->progress_cnt + 1); - display_progress(ctx->progress, i + 1); - if (level != GENERATION_NUMBER_ZERO) + if (gen != GENERATION_NUMBER_ZERO && gen != GENERATION_NUMBER_INFINITY) continue; commit_list_insert(c, &list); @@ -1472,41 +1498,91 @@ static void compute_topological_levels(struct write_commit_graph_context *ctx) struct commit *current = list->item; struct commit_list *parent; int all_parents_computed = 1; - uint32_t max_level = 0; + uint32_t max_gen = 0; for (parent = current->parents; parent; parent = parent->next) { - repo_parse_commit(ctx->r, parent->item); - level = *topo_level_slab_at(ctx->topo_levels, parent->item); + repo_parse_commit(info->r, parent->item); + gen = info->get_generation(parent->item, info->data); - if (level == GENERATION_NUMBER_ZERO) { + if (gen == GENERATION_NUMBER_ZERO) { all_parents_computed = 0; commit_list_insert(parent->item, &list); break; } - if (level > max_level) - max_level = level; + if (gen > max_gen) + max_gen = gen; } if (all_parents_computed) { pop_commit(&list); - - if (max_level > GENERATION_NUMBER_V1_MAX - 1) - max_level = GENERATION_NUMBER_V1_MAX - 1; - *topo_level_slab_at(ctx->topo_levels, current) = max_level + 1; + gen = compute_generation_from_max( + current, max_gen, + generation_version); + info->set_generation(current, gen, info->data); } } } +} + +static timestamp_t get_topo_level(struct commit *c, void *data) +{ + struct write_commit_graph_context *ctx = data; + return *topo_level_slab_at(ctx->topo_levels, c); +} + +static void set_topo_level(struct commit *c, timestamp_t t, void *data) +{ + struct write_commit_graph_context *ctx = data; + *topo_level_slab_at(ctx->topo_levels, c) = (uint32_t)t; +} + +static void compute_topological_levels(struct write_commit_graph_context *ctx) +{ + struct compute_generation_info info = { + .r = ctx->r, + .commits = &ctx->commits, + .get_generation = get_topo_level, + .set_generation = set_topo_level, + .data = ctx, + }; + + if (ctx->report_progress) + info.progress = ctx->progress + = start_delayed_progress( + _("Computing commit graph topological levels"), + ctx->commits.nr); + + compute_reachable_generation_numbers(&info, 1); + stop_progress(&ctx->progress); } +static timestamp_t get_generation_from_graph_data(struct commit *c, void *data) +{ + return commit_graph_data_at(c)->generation; +} + +static void set_generation_v2(struct commit *c, timestamp_t t, void *data) +{ + struct commit_graph_data *g = commit_graph_data_at(c); + g->generation = (uint32_t)t; +} + static void compute_generation_numbers(struct write_commit_graph_context *ctx) { int i; - struct commit_list *list = NULL; + struct compute_generation_info info = { + .r = ctx->r, + .commits = &ctx->commits, + .get_generation = get_generation_from_graph_data, + .set_generation = set_generation_v2, + .data = ctx, + }; if (ctx->report_progress) - ctx->progress = start_delayed_progress( + info.progress = ctx->progress + = start_delayed_progress( _("Computing commit graph generation numbers"), ctx->commits.nr); @@ -1518,47 +1594,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) } } - for (i = 0; i < ctx->commits.nr; i++) { - struct commit *c = ctx->commits.list[i]; - timestamp_t corrected_commit_date; - - repo_parse_commit(ctx->r, c); - corrected_commit_date = commit_graph_data_at(c)->generation; - - display_progress(ctx->progress, i + 1); - if (corrected_commit_date != GENERATION_NUMBER_ZERO) - continue; - - commit_list_insert(c, &list); - while (list) { - struct commit *current = list->item; - struct commit_list *parent; - int all_parents_computed = 1; - timestamp_t max_corrected_commit_date = 0; - - for (parent = current->parents; parent; parent = parent->next) { - repo_parse_commit(ctx->r, parent->item); - corrected_commit_date = commit_graph_data_at(parent->item)->generation; - - if (corrected_commit_date == GENERATION_NUMBER_ZERO) { - all_parents_computed = 0; - commit_list_insert(parent->item, &list); - break; - } - - if (corrected_commit_date > max_corrected_commit_date) - max_corrected_commit_date = corrected_commit_date; - } - - if (all_parents_computed) { - pop_commit(&list); - - if (current->date && current->date > max_corrected_commit_date) - max_corrected_commit_date = current->date - 1; - commit_graph_data_at(current)->generation = max_corrected_commit_date + 1; - } - } - } + compute_reachable_generation_numbers(&info, 2); for (i = 0; i < ctx->commits.nr; i++) { struct commit *c = ctx->commits.list[i]; @@ -1569,6 +1605,35 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) stop_progress(&ctx->progress); } +static void set_generation_in_graph_data(struct commit *c, timestamp_t t, + void *data) +{ + commit_graph_data_at(c)->generation = t; +} + +/* + * After this method, all commits reachable from those in the given + * list will have non-zero, non-infinite generation numbers. + */ +void ensure_generations_valid(struct repository *r, + struct commit **commits, size_t nr) +{ + int generation_version = get_configured_generation_version(r); + struct packed_commit_list list = { + .list = commits, + .alloc = nr, + .nr = nr, + }; + struct compute_generation_info info = { + .r = r, + .commits = &list, + .get_generation = get_generation_from_graph_data, + .set_generation = set_generation_in_graph_data, + }; + + compute_reachable_generation_numbers(&info, generation_version); +} + static void trace2_bloom_filter_write_statistics(struct write_commit_graph_context *ctx) { trace2_data_intmax("commit-graph", ctx->r, "filter-computed", diff --git a/commit-graph.h b/commit-graph.h index bb88bec7aa..83aaa1dbb9 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -189,4 +189,12 @@ struct commit_graph_data { */ timestamp_t commit_graph_generation(const struct commit *); uint32_t commit_graph_position(const struct commit *); + +/* + * After this method, all commits reachable from those in the given + * list will have non-zero, non-infinite generation numbers. + */ +void ensure_generations_valid(struct repository *r, + struct commit **commits, size_t nr); + #endif diff --git a/commit-reach.c b/commit-reach.c index 7c0c39fd28..d28cc96eb0 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -10,6 +10,7 @@ #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) @@ -947,3 +948,218 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, 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); +} diff --git a/commit-reach.h b/commit-reach.h index 148b56fea5..d6321ae700 100644 --- a/commit-reach.h +++ b/commit-reach.h @@ -104,4 +104,44 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, struct commit **to, int nr_to, unsigned int reachable_flag); +struct ahead_behind_count { + /** + * As input, the *_index members indicate which positions in + * the 'tips' array correspond to the tip and base of this + * comparison. + */ + size_t tip_index; + size_t base_index; + + /** + * These values store the computed counts for each side of the + * symmetric difference: + * + * 'ahead' stores the number of commits reachable from the tip + * and not reachable from the base. + * + * 'behind' stores the number of commits reachable from the base + * and not reachable from the tip. + */ + unsigned int ahead; + unsigned int behind; +}; + +/* + * Given an array of commits and an array of ahead_behind_count pairs, + * compute the ahead/behind counts for each pair. + */ +void ahead_behind(struct repository *r, + struct commit **commits, size_t commits_nr, + struct ahead_behind_count *counts, size_t counts_nr); + +/* + * For all tip commits, add 'mark' to their flags if and only if they + * are reachable from one of the commits in 'bases'. + */ +void tips_reachable_from_bases(struct repository *r, + struct commit_list *bases, + struct commit **tips, size_t tips_nr, + int mark); + #endif diff --git a/ref-filter.c b/ref-filter.c index ed802778da..25831e3336 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -158,6 +158,7 @@ enum atom_type { ATOM_THEN, ATOM_ELSE, ATOM_REST, + ATOM_AHEADBEHIND, }; /* @@ -600,6 +601,22 @@ static int rest_atom_parser(struct ref_format *format, return 0; } +static int ahead_behind_atom_parser(struct ref_format *format, struct used_atom *atom, + const char *arg, struct strbuf *err) +{ + struct string_list_item *item; + + if (!arg) + return strbuf_addf_ret(err, -1, _("expected format: %%(ahead-behind:<committish>)")); + + item = string_list_append(&format->bases, arg); + item->util = lookup_commit_reference_by_name(arg); + if (!item->util) + die("failed to find '%s'", arg); + + return 0; +} + static int head_atom_parser(struct ref_format *format UNUSED, struct used_atom *atom, const char *arg, struct strbuf *err) @@ -660,6 +677,7 @@ static struct { [ATOM_THEN] = { "then", SOURCE_NONE }, [ATOM_ELSE] = { "else", SOURCE_NONE }, [ATOM_REST] = { "rest", SOURCE_NONE, FIELD_STR, rest_atom_parser }, + [ATOM_AHEADBEHIND] = { "ahead-behind", SOURCE_OTHER, FIELD_STR, ahead_behind_atom_parser }, /* * Please update $__git_ref_fieldlist in git-completion.bash * when you add new atoms @@ -1866,6 +1884,7 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err) struct object *obj; int i; struct object_info empty = OBJECT_INFO_INIT; + int ahead_behind_atoms = 0; CALLOC_ARRAY(ref->value, used_atom_cnt); @@ -1996,6 +2015,16 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err) else v->s = xstrdup(""); continue; + } else if (atom_type == ATOM_AHEADBEHIND) { + if (ref->counts) { + const struct ahead_behind_count *count; + count = ref->counts[ahead_behind_atoms++]; + v->s = xstrfmt("%d %d", count->ahead, count->behind); + } else { + /* Not a commit. */ + v->s = xstrdup(""); + } + continue; } else continue; @@ -2346,6 +2375,7 @@ static void free_array_item(struct ref_array_item *item) free((char *)item->value[i].s); free(item->value); } + free(item->counts); free(item); } @@ -2374,6 +2404,8 @@ void ref_array_clear(struct ref_array *array) free_worktrees(ref_to_worktree_map.worktrees); ref_to_worktree_map.worktrees = NULL; } + + FREE_AND_NULL(array->counts); } #define EXCLUDE_REACHED 0 @@ -2382,33 +2414,22 @@ static void reach_filter(struct ref_array *array, struct commit_list *check_reachable, int include_reached) { - struct rev_info revs; int i, old_nr; struct commit **to_clear; - struct commit_list *cr; if (!check_reachable) return; CALLOC_ARRAY(to_clear, array->nr); - - repo_init_revisions(the_repository, &revs, NULL); - for (i = 0; i < array->nr; i++) { struct ref_array_item *item = array->items[i]; - add_pending_object(&revs, &item->commit->object, item->refname); to_clear[i] = item->commit; } - for (cr = check_reachable; cr; cr = cr->next) { - struct commit *merge_commit = cr->item; - merge_commit->object.flags |= UNINTERESTING; - add_pending_object(&revs, &merge_commit->object, ""); - } - - revs.limited = 1; - if (prepare_revision_walk(&revs)) - die(_("revision walk setup failed")); + tips_reachable_from_bases(the_repository, + check_reachable, + to_clear, array->nr, + UNINTERESTING); old_nr = array->nr; array->nr = 0; @@ -2432,10 +2453,50 @@ static void reach_filter(struct ref_array *array, clear_commit_marks(merge_commit, ALL_REV_FLAGS); } - release_revisions(&revs); free(to_clear); } +void filter_ahead_behind(struct repository *r, + struct ref_format *format, + struct ref_array *array) +{ + struct commit **commits; + size_t commits_nr = format->bases.nr + array->nr; + + if (!format->bases.nr || !array->nr) + return; + + ALLOC_ARRAY(commits, commits_nr); + for (size_t i = 0; i < format->bases.nr; i++) + commits[i] = format->bases.items[i].util; + + ALLOC_ARRAY(array->counts, st_mult(format->bases.nr, array->nr)); + + commits_nr = format->bases.nr; + array->counts_nr = 0; + for (size_t i = 0; i < array->nr; i++) { + const char *name = array->items[i]->refname; + commits[commits_nr] = lookup_commit_reference_by_name(name); + + if (!commits[commits_nr]) + continue; + + CALLOC_ARRAY(array->items[i]->counts, format->bases.nr); + for (size_t j = 0; j < format->bases.nr; j++) { + struct ahead_behind_count *count; + count = &array->counts[array->counts_nr++]; + count->tip_index = commits_nr; + count->base_index = j; + + array->items[i]->counts[j] = count; + } + commits_nr++; + } + + ahead_behind(r, commits, commits_nr, array->counts, array->counts_nr); + free(commits); +} + /* * API for filtering a set of refs. Based on the type of refs the user * has requested, we iterate through those refs and apply filters diff --git a/ref-filter.h b/ref-filter.h index daa6d02017..ae51ace3a2 100644 --- a/ref-filter.h +++ b/ref-filter.h @@ -4,6 +4,7 @@ #include "oid-array.h" #include "refs.h" #include "commit.h" +#include "string-list.h" /* Quoting styles */ #define QUOTE_NONE 0 @@ -23,6 +24,7 @@ struct atom_value; struct ref_sorting; +struct ahead_behind_count; struct option; enum ref_sorting_order { @@ -40,6 +42,8 @@ struct ref_array_item { const char *symref; struct commit *commit; struct atom_value *value; + struct ahead_behind_count **counts; + char refname[FLEX_ARRAY]; }; @@ -47,6 +51,9 @@ struct ref_array { int nr, alloc; struct ref_array_item **items; struct rev_info *revs; + + struct ahead_behind_count *counts; + size_t counts_nr; }; struct ref_filter { @@ -80,9 +87,15 @@ struct ref_format { /* Internal state to ref-filter */ int need_color_reset_at_eol; + + /* List of bases for ahead-behind counts. */ + struct string_list bases; }; -#define REF_FORMAT_INIT { .use_color = -1 } +#define REF_FORMAT_INIT { \ + .use_color = -1, \ + .bases = STRING_LIST_INIT_DUP, \ +} /* Macros for checking --merged and --no-merged options */ #define _OPT_MERGED_NO_MERGED(option, filter, h) \ @@ -143,4 +156,15 @@ struct ref_array_item *ref_array_push(struct ref_array *array, const char *refname, const struct object_id *oid); +/* + * If the provided format includes ahead-behind atoms, then compute the + * ahead-behind values for the array of filtered references. Must be + * called after filter_refs() but before outputting the formatted refs. + * + * If this is not called, then any ahead-behind atoms will be blank. + */ +void filter_ahead_behind(struct repository *r, + struct ref_format *format, + struct ref_array *array); + #endif /* REF_FILTER_H */ diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh new file mode 100755 index 0000000000..e14e7620cc --- /dev/null +++ b/t/perf/p1500-graph-walks.sh @@ -0,0 +1,50 @@ +#!/bin/sh + +test_description='Commit walk performance tests' +. ./perf-lib.sh + +test_perf_large_repo + +test_expect_success 'setup' ' + git for-each-ref --format="%(refname)" "refs/heads/*" "refs/tags/*" >allrefs && + sort -r allrefs | head -n 50 >refs && + for ref in $(cat refs) + do + git branch -f ref-$ref $ref && + echo ref-$ref || + return 1 + done >branches && + for ref in $(cat refs) + do + git tag -f tag-$ref $ref && + echo tag-$ref || + return 1 + done >tags && + git commit-graph write --reachable +' + +test_perf 'ahead-behind counts: git for-each-ref' ' + git for-each-ref --format="%(ahead-behind:HEAD)" --stdin <refs +' + +test_perf 'ahead-behind counts: git branch' ' + xargs git branch -l --format="%(ahead-behind:HEAD)" <branches +' + +test_perf 'ahead-behind counts: git tag' ' + xargs git tag -l --format="%(ahead-behind:HEAD)" <tags +' + +test_perf 'contains: git for-each-ref --merged' ' + git for-each-ref --merged=HEAD --stdin <refs +' + +test_perf 'contains: git branch --merged' ' + xargs git branch --merged=HEAD <branches +' + +test_perf 'contains: git tag --merged' ' + xargs git tag --merged=HEAD <tags +' + +test_done diff --git a/t/t3203-branch-output.sh b/t/t3203-branch-output.sh index d34d77f893..1c0f7ea24e 100755 --- a/t/t3203-branch-output.sh +++ b/t/t3203-branch-output.sh @@ -337,6 +337,20 @@ test_expect_success 'git branch --format option' ' test_cmp expect actual ' +test_expect_success 'git branch --format with ahead-behind' ' + cat >expect <<-\EOF && + (HEAD detached from fromtag) 0 0 + refs/heads/ambiguous 0 0 + refs/heads/branch-one 1 0 + refs/heads/branch-two 0 0 + refs/heads/main 1 0 + refs/heads/ref-to-branch 1 0 + refs/heads/ref-to-remote 1 0 + EOF + git branch --format="%(refname) %(ahead-behind:HEAD)" >actual && + test_cmp expect actual +' + test_expect_success 'git branch with --format=%(rest) must fail' ' test_must_fail git branch --format="%(rest)" >actual ' diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh index 049c5fc8ea..b6e1211578 100755 --- a/t/t5318-commit-graph.sh +++ b/t/t5318-commit-graph.sh @@ -630,7 +630,7 @@ test_expect_success 'detect incorrect generation number' ' test_expect_success 'detect incorrect generation number' ' corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \ - "non-zero generation number" + "commit-graph generation for commit" ' test_expect_success 'detect incorrect commit date' ' diff --git a/t/t6300-for-each-ref.sh b/t/t6300-for-each-ref.sh index c466fd989f..6614469d2d 100755 --- a/t/t6300-for-each-ref.sh +++ b/t/t6300-for-each-ref.sh @@ -1464,4 +1464,54 @@ sig_crlf="$(printf "%s" "$sig" | append_cr; echo dummy)" sig_crlf=${sig_crlf%dummy} test_atom refs/tags/fake-sig-crlf contents:signature "$sig_crlf" +test_expect_success 'git for-each-ref --stdin: empty' ' + >in && + git for-each-ref --format="%(refname)" --stdin <in >actual && + git for-each-ref --format="%(refname)" >expect && + test_cmp expect actual +' + +test_expect_success 'git for-each-ref --stdin: fails if extra args' ' + >in && + test_must_fail git for-each-ref --format="%(refname)" \ + --stdin refs/heads/extra <in 2>err && + grep "unknown arguments supplied with --stdin" err +' + +test_expect_success 'git for-each-ref --stdin: matches' ' + cat >in <<-EOF && + refs/tags/multi* + refs/heads/amb* + EOF + + cat >expect <<-EOF && + refs/heads/ambiguous + refs/tags/multi-ref1-100000-user1 + refs/tags/multi-ref1-100000-user2 + refs/tags/multi-ref1-200000-user1 + refs/tags/multi-ref1-200000-user2 + refs/tags/multi-ref2-100000-user1 + refs/tags/multi-ref2-100000-user2 + refs/tags/multi-ref2-200000-user1 + refs/tags/multi-ref2-200000-user2 + refs/tags/multiline + EOF + + git for-each-ref --format="%(refname)" --stdin <in >actual && + test_cmp expect actual +' + +test_expect_success 'git for-each-ref with non-existing refs' ' + cat >in <<-EOF && + refs/heads/this-ref-does-not-exist + refs/tags/bogus + EOF + + git for-each-ref --format="%(refname)" --stdin <in >actual && + test_must_be_empty actual && + + xargs git for-each-ref --format="%(refname)" <in >actual && + test_must_be_empty actual +' + test_done diff --git a/t/t6301-for-each-ref-errors.sh b/t/t6301-for-each-ref-errors.sh index bfda1f46ad..2667dd13fe 100755 --- a/t/t6301-for-each-ref-errors.sh +++ b/t/t6301-for-each-ref-errors.sh @@ -54,4 +54,18 @@ test_expect_success 'Missing objects are reported correctly' ' test_must_be_empty brief-err ' +test_expect_success 'ahead-behind requires an argument' ' + test_must_fail git for-each-ref \ + --format="%(ahead-behind)" 2>err && + echo "fatal: expected format: %(ahead-behind:<committish>)" >expect && + test_cmp expect err +' + +test_expect_success 'missing ahead-behind base' ' + test_must_fail git for-each-ref \ + --format="%(ahead-behind:refs/heads/missing)" 2>err && + echo "fatal: failed to find '\''refs/heads/missing'\''" >expect && + test_cmp expect err +' + test_done diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index 338a9c46a2..b330945f49 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -443,4 +443,173 @@ test_expect_success 'get_reachable_subset:none' ' test_all_modes get_reachable_subset ' +test_expect_success 'for-each-ref ahead-behind:linear' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-1-3 + refs/heads/commit-1-5 + refs/heads/commit-1-8 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 0 8 + refs/heads/commit-1-3 0 6 + refs/heads/commit-1-5 0 4 + refs/heads/commit-1-8 0 1 + EOF + run_all_modes git for-each-ref \ + --format="%(refname) %(ahead-behind:commit-1-9)" --stdin +' + +test_expect_success 'for-each-ref ahead-behind:all' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-2-4 + refs/heads/commit-4-2 + refs/heads/commit-4-4 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 0 24 + refs/heads/commit-2-4 0 17 + refs/heads/commit-4-2 0 17 + refs/heads/commit-4-4 0 9 + EOF + run_all_modes git for-each-ref \ + --format="%(refname) %(ahead-behind:commit-5-5)" --stdin +' + +test_expect_success 'for-each-ref ahead-behind:some' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-5-3 + refs/heads/commit-4-8 + refs/heads/commit-9-9 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 0 53 + refs/heads/commit-4-8 8 30 + refs/heads/commit-5-3 0 39 + refs/heads/commit-9-9 27 0 + EOF + run_all_modes git for-each-ref \ + --format="%(refname) %(ahead-behind:commit-9-6)" --stdin +' + +test_expect_success 'for-each-ref ahead-behind:some, multibase' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-5-3 + refs/heads/commit-7-8 + refs/heads/commit-4-8 + refs/heads/commit-9-9 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 0 53 0 53 + refs/heads/commit-4-8 8 30 0 22 + refs/heads/commit-5-3 0 39 0 39 + refs/heads/commit-7-8 14 12 8 6 + refs/heads/commit-9-9 27 0 27 0 + EOF + run_all_modes git for-each-ref \ + --format="%(refname) %(ahead-behind:commit-9-6) %(ahead-behind:commit-6-9)" \ + --stdin +' + +test_expect_success 'for-each-ref ahead-behind:none' ' + cat >input <<-\EOF && + refs/heads/commit-7-5 + refs/heads/commit-4-8 + refs/heads/commit-9-9 + EOF + cat >expect <<-\EOF && + refs/heads/commit-4-8 16 16 + refs/heads/commit-7-5 7 4 + refs/heads/commit-9-9 49 0 + EOF + run_all_modes git for-each-ref \ + --format="%(refname) %(ahead-behind:commit-8-4)" --stdin +' + +test_expect_success 'for-each-ref merged:linear' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-1-3 + refs/heads/commit-1-5 + refs/heads/commit-1-8 + refs/heads/commit-2-1 + refs/heads/commit-5-1 + refs/heads/commit-9-1 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-1-3 + refs/heads/commit-1-5 + refs/heads/commit-1-8 + EOF + run_all_modes git for-each-ref --merged=commit-1-9 \ + --format="%(refname)" --stdin +' + +test_expect_success 'for-each-ref merged:all' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-2-4 + refs/heads/commit-4-2 + refs/heads/commit-4-4 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-2-4 + refs/heads/commit-4-2 + refs/heads/commit-4-4 + EOF + run_all_modes git for-each-ref --merged=commit-5-5 \ + --format="%(refname)" --stdin +' + +test_expect_success 'for-each-ref ahead-behind:some' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-5-3 + refs/heads/commit-4-8 + refs/heads/commit-9-9 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-5-3 + EOF + run_all_modes git for-each-ref --merged=commit-9-6 \ + --format="%(refname)" --stdin +' + +test_expect_success 'for-each-ref merged:some, multibase' ' + cat >input <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-5-3 + refs/heads/commit-7-8 + refs/heads/commit-4-8 + refs/heads/commit-9-9 + EOF + cat >expect <<-\EOF && + refs/heads/commit-1-1 + refs/heads/commit-4-8 + refs/heads/commit-5-3 + EOF + run_all_modes git for-each-ref \ + --merged=commit-5-8 \ + --merged=commit-8-5 \ + --format="%(refname)" \ + --stdin +' + +test_expect_success 'for-each-ref merged:none' ' + cat >input <<-\EOF && + refs/heads/commit-7-5 + refs/heads/commit-4-8 + refs/heads/commit-9-9 + EOF + >expect && + run_all_modes git for-each-ref --merged=commit-8-4 \ + --format="%(refname)" --stdin +' + test_done diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh index 9aa1660651..04a4b44183 100755 --- a/t/t7004-tag.sh +++ b/t/t7004-tag.sh @@ -792,6 +792,34 @@ test_expect_success 'annotations for blobs are empty' ' test_cmp expect actual ' +# Run this before doing any signing, so the test has the same results +# regardless of the GPG prereq. +test_expect_success 'git tag --format with ahead-behind' ' + test_when_finished git reset --hard tag-one-line && + git commit --allow-empty -m "left" && + git tag -a -m left tag-left && + git reset --hard HEAD~1 && + git commit --allow-empty -m "right" && + git tag -a -m left tag-right && + + # Use " !" at the end to demonstrate whitespace + # around empty ahead-behind token for tag-blob. + cat >expect <<-EOF && + refs/tags/tag-blob ! + refs/tags/tag-left 1 1 ! + refs/tags/tag-lines 0 1 ! + refs/tags/tag-one-line 0 1 ! + refs/tags/tag-right 0 0 ! + refs/tags/tag-zero-lines 0 1 ! + EOF + git tag -l --format="%(refname) %(ahead-behind:HEAD) !" >actual 2>err && + grep "refs/tags/tag" actual >actual.focus && + test_cmp expect actual.focus && + + # Error reported for tags that point to non-commits. + grep "error: object [0-9a-f]* is a blob, not a commit" err +' + # trying to verify annotated non-signed tags: test_expect_success GPG \ |