[PATCH 8/8] ahead-behind: add --contains mode

From

Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com>

Date

Mar 6, 2023, 14:06 UTC

Message-ID

<07eb2cbb699c875e5fdca86d675c97d4d434f511.1678111599.git.gitgitgadget@gmail.com>

In-Reply-To

<pull.1489.git.1678111598.gitgitgadget@gmail.com>

From: Derrick Stolee <derrickstolee@github.com>

In the Linux kernel repository, the impact is more pronounced:

Signed-off-by: Derrick Stolee <derrickstolee@github.com>
---
 Documentation/git-ahead-behind.txt |  12 +++-
 builtin/ahead-behind.c             |  27 ++++++-
 commit-reach.c                     | 110 +++++++++++++++++++++++++++++
 commit-reach.h                     |   7 ++
 t/perf/p1500-graph-walks.sh        |   4 ++
 t/t4218-ahead-behind.sh            |  62 ++++++++++++++++
 t/t6600-test-reach.sh              |  58 +++++++++++++++
 7 files changed, 277 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-ahead-behind.txt b/Documentation/git-ahead-behind.txt
index 2dd5147f6b2..1652a51d719 100644
--- a/Documentation/git-ahead-behind.txt
+++ b/Documentation/git-ahead-behind.txt
@@ -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
diff --git a/builtin/ahead-behind.c b/builtin/ahead-behind.c
index c06b95b5f37..4efd324d5d9 100644
--- a/builtin/ahead-behind.c
+++ b/builtin/ahead-behind.c
@@ -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);
 
diff --git a/commit-reach.c b/commit-reach.c
index 87ccc2cd4f5..a7a2c045551 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -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);
+}
diff --git a/commit-reach.h b/commit-reach.h
index 1780f9317bf..fa8994f5696 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -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
diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh
index c9ac4b7e6e2..56de6c5b13d 100755
--- a/t/perf/p1500-graph-walks.sh
+++ b/t/perf/p1500-graph-walks.sh
@@ -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
diff --git a/t/t4218-ahead-behind.sh b/t/t4218-ahead-behind.sh
index 6658c919fdf..c333cb623f8 100755
--- a/t/t4218-ahead-behind.sh
+++ b/t/t4218-ahead-behind.sh
@@ -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
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 951e07100f6..2fdad7b3619 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -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

-- 
gitgitgadget