@@ -8,7 +8,7 @@ git-ahead-behind - Count the commits on each side of a revision range
SYNOPSIS
--------
[verse]
-'git ahead-behind' --base=<ref> [ --stdin | <revs> ]
+'git ahead-behind' --base=<ref> [ --contains ] [ --stdin | <revs> ]
DESCRIPTION
-----------
@@ -39,6 +39,9 @@ reported to stdout one line at a time as follows:
There will be exactly one line per input revision, but the lines may be
in an arbitrary order.
+If the `--contains` option is provided, then the output will list the
+`<tip>` refs are reachable from the provided `<base>`, one per line.
+
OPTIONS
-------
@@ -50,6 +53,13 @@ OPTIONS
Read revision tips and ranges from stdin instead of from the
command-line.
+--contains::
+ Specify that instead of counting the ahead/behind values, only
+ indicate whether each tip reference is reachable from the base. In
+ this mode, the output format changes to include only the name of
+ each tip by name, one per line, and only the tips reachable from
+ the base are included in the output.
+
--ignore-missing::
When parsing tip references, ignore any references that are not
found. This is useful when operating in an environment where a
@@ -5,7 +5,7 @@
#include "commit-reach.h"
static const char * const ahead_behind_usage[] = {
- N_("git ahead-behind --base=<ref> [ --stdin | <revs> ]"),
+ N_("git ahead-behind --base=<ref> [ --contains ] [ --stdin | <revs> ]"),
NULL
};
@@ -31,7 +31,7 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
{
const char *base_ref = NULL;
struct commit *base;
- int from_stdin = 0;
+ int from_stdin = 0, contains = 0;
struct string_list tips = STRING_LIST_INIT_DUP;
struct commit **commits;
struct ahead_behind_count *counts;
@@ -41,6 +41,7 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")),
OPT_BOOL(0 , "stdin", &from_stdin, N_("read rev names from stdin")),
OPT_BOOL(0 , "ignore-missing", &ignore_missing, N_("ignore missing tip references")),
+ OPT_BOOL(0 , "contains", &contains, N_("only check that tips are reachable from the base")),
OPT_END()
};
@@ -52,6 +53,10 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
git_config(git_default_config, NULL);
+ base = lookup_commit_reference_by_name(base_ref);
+ if (!base)
+ die(_("could not resolve '%s'"), base_ref);
+
if (from_stdin) {
struct strbuf line = STRBUF_INIT;
@@ -76,6 +81,24 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
if (!tips.nr)
return 0;
+ if (contains) {
+ struct string_list_item *item;
+
+ /* clear out */
+ for_each_string_list_item(item, &tips)
+ item->util = NULL;
+
+ tips_reachable_from_base(base, &tips);
+
+ for_each_string_list_item(item, &tips) {
+ if (item->util)
+ printf("%s\n", item->string);
+ }
+
+ return 0;
+ }
+ /* else: not --contains, but normal ahead-behind counting. */
+
ALLOC_ARRAY(commits, tips.nr + 1);
ALLOC_ARRAY(counts, tips.nr);
@@ -1036,3 +1036,113 @@ void ahead_behind(struct commit **commits, size_t commits_nr,
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_base(struct commit *base,
+ struct string_list *tips)
+{
+ unsigned int i;
+ struct commit_and_index *commits;
+ unsigned int min_generation_index = 0;
+ timestamp_t min_generation;
+ struct commit_list *stack = NULL;
+
+ if (!base || !tips || !tips->nr)
+ return;
+
+ /*
+ * Do a depth-first search starting at 'base' 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 (i = 0; i < tips->nr; i++) {
+ commits[i].commit = lookup_commit_reference_by_name(tips->items[i].string);
+ commits[i].index = i;
+ commits[i].generation = commit_graph_generation(commits[i].commit);
+ }
+
+ /* Sort with generation number ascending. */
+ QSORT(commits, tips->nr, compare_commit_and_index_by_generation);
+ min_generation = commits[0].generation;
+
+ parse_commit(base);
+ commit_list_insert(base, &stack);
+
+ while (stack) {
+ unsigned int j;
+ 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 bases? */
+ for (j = min_generation_index; j < tips->nr; j++) {
+ if (c_gen < commits[j].generation)
+ break;
+
+ if (commits[j].commit == c) {
+ tips->items[commits[j].index].util = (void *)(uintptr_t)1;
+
+ if (j == min_generation_index) {
+ unsigned int k = j + 1;
+ while (k < tips->nr &&
+ tips->items[commits[k].index].util)
+ 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) {
+ parse_commit(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(the_repository, SEEN);
+}
@@ -134,4 +134,11 @@ struct ahead_behind_count {
void ahead_behind(struct commit **commits, size_t commits_nr,
struct ahead_behind_count *counts, size_t counts_nr);
+/*
+ * Populate the "util" of each string_list item with the boolean value
+ * corresponding to "can 'base' reach this tip?"
+ */
+void tips_reachable_from_base(struct commit *base,
+ struct string_list *tips);
+
#endif
@@ -22,4 +22,8 @@ test_perf 'ahead-behind counts: git rev-list' '
done
'
+test_perf 'ahead-behind counts: git ahead-behind --contains' '
+ git ahead-behind --contains --base=HEAD --stdin <refs
+'
+
test_done
@@ -40,6 +40,19 @@ test_expect_success 'git ahead-behind with broken tip and --ignore-missing' '
test_must_be_empty out
'
+test_expect_success 'git ahead-behind --contains with broken tip' '
+ test_must_fail git ahead-behind --contains \
+ --base=HEAD bogus 2>err &&
+ grep "could not resolve '\''bogus'\''" err
+'
+
+test_expect_success 'git ahead-behind --contains with broken tip and --ignore-missing' '
+ git ahead-behind --base=HEAD --contains \
+ --ignore-missing bogus 2>err >out &&
+ test_must_be_empty err &&
+ test_must_be_empty out
+'
+
test_expect_success 'git ahead-behind without tips' '
git ahead-behind --base=HEAD 2>err &&
test_must_be_empty err
@@ -97,4 +110,53 @@ test_expect_success 'git ahead-behind --base=merge' '
test_cmp expect actual
'
+test_expect_success 'git ahead-behind --contains --base=base' '
+ git ahead-behind --contains --base=base \
+ base left right merge >actual &&
+
+ cat >expect <<-EOF &&
+ base
+ EOF
+
+ test_cmp expect actual
+'
+
+test_expect_success 'git ahead-behind --contains --base=left' '
+ git ahead-behind --contains --base=left \
+ base left right merge >actual &&
+
+ cat >expect <<-EOF &&
+ base
+ left
+ EOF
+
+ test_cmp expect actual
+'
+
+test_expect_success 'git ahead-behind --contains --base=right' '
+ git ahead-behind --contains --base=right \
+ base left right merge >actual &&
+
+ cat >expect <<-EOF &&
+ base
+ right
+ EOF
+
+ test_cmp expect actual
+'
+
+test_expect_success 'git ahead-behind --contains --base=merge' '
+ git ahead-behind --contains --base=merge \
+ base left right merge >actual &&
+
+ cat >expect <<-EOF &&
+ base
+ left
+ right
+ merge
+ EOF
+
+ test_cmp expect actual
+'
+
test_done
@@ -505,4 +505,62 @@ test_expect_success 'ahead-behind:none' '
run_all_modes git ahead-behind --base=commit-8-4 --stdin
'
+test_expect_success 'ahead-behind--contains:all' '
+ cat >input <<-\EOF &&
+ commit-1-1
+ commit-2-4
+ commit-4-2
+ commit-4-4
+ EOF
+ cat >expect <<-\EOF &&
+ commit-1-1
+ commit-2-4
+ commit-4-2
+ commit-4-4
+ EOF
+ run_all_modes git ahead-behind --contains --base=commit-5-5 \
+ --stdin --use-bitmap-index
+'
+
+test_expect_success 'ahead-behind--contains:some' '
+ cat >input <<-\EOF &&
+ commit-1-1
+ commit-5-3
+ commit-4-8
+ commit-9-9
+ EOF
+ cat >expect <<-\EOF &&
+ commit-1-1
+ commit-5-3
+ EOF
+ run_all_modes git ahead-behind --contains --base=commit-9-6 \
+ --stdin --use-bitmap-index
+'
+
+test_expect_success 'ahead-behind--contains:some, reordered' '
+ cat >input <<-\EOF &&
+ commit-4-8
+ commit-5-3
+ commit-9-9
+ commit-1-1
+ EOF
+ cat >expect <<-\EOF &&
+ commit-5-3
+ commit-1-1
+ EOF
+ run_all_modes git ahead-behind --contains --base=commit-9-6 \
+ --stdin --use-bitmap-index
+'
+
+test_expect_success 'ahead-behind--contains:none' '
+ cat >input <<-\EOF &&
+ commit-7-5
+ commit-4-8
+ commit-9-9
+ EOF
+ >expect &&
+ run_all_modes git ahead-behind --contains --base=commit-8-4 \
+ --stdin --use-bitmap-index
+'
+
test_done