ahead-behind: new builtin for counting multiple commit ranges

This series introduces the 'git ahead-behind' builtin, which has been used at $DAYJOB for many years, but took many forms before landing on the current version.

The main goal of the builtin is to compare multiple references against a common base reference. The comparison is number of commits that are in each side of the symmtric difference of their reachable sets. A commit C is "ahead" of a commit B by the number of commits in B..C (reachable from C but not reachable from B). Similarly, the commit C is "behind" the commit B by the number of commits in C..B (reachable from B but not reachable from C).

These numbers can be computed by 'git rev-list --count B..C' and 'git rev-list --count C..B', but there are common needs that benefit from having the checks being done in the same process:

1. Our "branches" page lists ahead/behind counts for each listed branch as compared to the repo's default branch. This can be done with a single 'git ahead-behind' process.
2. When a branch is updated, a background job checks if any pull requests that target that branch should be closed because their branches were merged implicitly by that update. These queries can e batched into 'git ahead-behind' calls.

In that second example, we don't need the full ahead/behind counts (although it is sufficient to look for branches that are "zero commits ahead", meaning they are reachable from the base), so this builtin has an extra '--contains' mode that only checks reachability from the base to each of the tips. 'git ahead-behind --contains' is sort of the reverse of 'git branch --contains'.

The series starts with some basic boilerplate and argument parsing, along with error conditions for missing objects. To avoid TOCTOU races, an '--ignore-missing' option allows being flexible when a tip reference does not exist. This is all covered in patches 1-3.

Patches 4-6 introduce a new method: ensure_generations_valid(). Patch 4 does some refactoring of the existing generation number computations to make it more generic, and patch 5 updates the definition of commit_graph_generation() slightly, making way for patch 6 to implement the method. With an existing commit-graph file, the commits that are not present in the file are considered as having generation number "infinity". This is useful for most of our reachability queries to this point, since those commits are "above" the ones tracked by the commit-graph. When these commits are low in number, then there is very little performance cost and zero correctness cost.

However, we will see that the ahead/behind computation requires accurate generation numbers to avoid overcounting. Thus, ensure_generations_valid() is a way to specify a list of commits that need generation numbers computed before continuing. It's a no-op if all of those commits are in the commit-graph file. It's expensive if the commit-graph doesn't exist. However, 'git ahead-behind' computations are likely to be slow no matter what without a commit-graph, so assuming an existing commit-graph file is reasonable. If we find sufficient desire to have an implementation that does not have this requirement, we could create a second implementation and toggle to it when generation_numbers_enabled() returns false.

Patch 7 implements the ahead-behind algorithm, as well as integrating the builtin with that implementation. It's a long commit message, so hopefully it explains the algorithm sufficiently.

Patch 8 implements the --contains option, which is another algorithm, but more similar to other depth-first searches that already exist in commit-reach.c.

Thanks, -Stolee

Derrick Stolee (7):
ahead-behind: create empty builtin
ahead-behind: parse tip references
ahead-behind: implement --ignore-missing option
commit-graph: combine generation computations
commit-graph: return generation from memory
ahead-behind: implement ahead_behind() logic
ahead-behind: add --contains mode

Taylor Blau (1):
commit-graph: introduce ensure_generations_valid()

 .gitignore                         |   1 +
 Documentation/git-ahead-behind.txt |  78 +++++++++++
 Makefile                           |   1 +
 builtin.h                          |   1 +
 builtin/ahead-behind.c             | 121 +++++++++++++++++
 commit-graph.c                     | 209 +++++++++++++++++++----------
 commit-graph.h                     |   7 +
 commit-reach.c                     | 205 ++++++++++++++++++++++++++++
 commit-reach.h                     |  37 +++++
 git.c                              |   1 +
 t/perf/p1500-graph-walks.sh        |  29 ++++
 t/t4218-ahead-behind.sh            | 162 ++++++++++++++++++++++
 t/t5318-commit-graph.sh            |   2 +-
 t/t6600-test-reach.sh              | 120 +++++++++++++++++
 14 files changed, 904 insertions(+), 70 deletions(-)
 create mode 100644 Documentation/git-ahead-behind.txt
 create mode 100644 builtin/ahead-behind.c
 create mode 100755 t/perf/p1500-graph-walks.sh
 create mode 100755 t/t4218-ahead-behind.sh

base-commit: d15644fe0226af7ffc874572d968598564a230dd
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1489%2Fderrickstolee%2Fstolee%2Fupstream-ahead-behind-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1489/derrickstolee/stolee/upstream-ahead-behind-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1489

gitgitgadget

From: Derrick Stolee <[email protected]>

The 'git ahead-behind' builtin _will_ allow users to specify multiple tip revisions relative to a common base and _will_ report the number of commits on each side of the symmetric difference between each tip and the base. However, that algorithm is not implemented yet and instead this change introduces the builtin and the basic boilerplate for a new builtin.

This builtin could be replaced with multiple invocations of 'git rev-list --count <base>..<tip>' (for ahead values) and 'git rev-list --count <tip>..<base>' (for behind values). However, it is important to be able to batch these calls into a single process.

For example, we will be able to track all local branches relative to an upstream branch using an invocation such as

  git for-each-ref --format=%(refname) refs/heads/* |
    git ahead-behind --base=origin/main --stdin

This would report each local branch and how far ahead or behind it is relative to the remote branch 'origin/main'. This could be used to signal some branches are very old and need to be updated via 'git rebase' or deleted. We will see in future changes how such commit counting can be done efficiently within a single process (and a single commit walk) instead of multiple processes.

For now, only 'git ahead-behind -h' works, and the builtin reports failure and shows the usage if the '--base' option is skipped. The documentation is light. These will be updated in the coming changes.

---
 .gitignore                         |  1 +
 Documentation/git-ahead-behind.txt | 62 ++++++++++++++++++++++++++++++
 Makefile                           |  1 +
 builtin.h                          |  1 +
 builtin/ahead-behind.c             | 30 +++++++++++++++
 git.c                              |  1 +
 t/t4218-ahead-behind.sh            | 17 ++++++++
 7 files changed, 113 insertions(+)
 create mode 100644 Documentation/git-ahead-behind.txt
 create mode 100644 builtin/ahead-behind.c
 create mode 100755 t/t4218-ahead-behind.sh

index e875c590545..cc064a4817a 100644
@@ -14,6 +14,7 @@
 /bin-wrappers/
 /git
 /git-add
+/git-ahead-behind
 /git-am
 /git-annotate
 /git-apply

index 50ee51fde32..691f84e8d4e 100644
@@ -1199,6 +1199,7 @@ LIB_OBJS += xdiff-interface.o
 LIB_OBJS += zlib.o
 
 BUILTIN_OBJS += builtin/add.o
+BUILTIN_OBJS += builtin/ahead-behind.o
 BUILTIN_OBJS += builtin/am.o
 BUILTIN_OBJS += builtin/annotate.o
 BUILTIN_OBJS += builtin/apply.o

index 46cc7897898..1ae168fa3e3 100644
@@ -108,6 +108,7 @@ void setup_auto_pager(const char *cmd, int def);
 int is_builtin(const char *s);
 
 int cmd_add(int argc, const char **argv, const char *prefix);
+int cmd_ahead_behind(int argc, const char **argv, const char *prefix);
 int cmd_am(int argc, const char **argv, const char *prefix);
 int cmd_annotate(int argc, const char **argv, const char *prefix);
 int cmd_apply(int argc, const char **argv, const char *prefix);

new file mode 100644
index 00000000000..a56cc565def
@@ -0,0 +1,30 @@
+#include "builtin.h"
+#include "parse-options.h"
+#include "config.h"
+
+static const char * const ahead_behind_usage[] = {
+	N_("git ahead-behind --base=<ref> [ --stdin | <revs> ]"),
+	NULL
+};
+
+int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
+{
+	const char *base_ref = NULL;
+	int from_stdin = 0;
+
+	struct option ahead_behind_opts[] = {
+		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_END()
+	};
+
+	argc = parse_options(argc, argv, NULL, ahead_behind_opts,
+			     ahead_behind_usage, PARSE_OPT_KEEP_UNKNOWN_OPT);
+
+	if (!base_ref)
+		usage_with_options(ahead_behind_usage, ahead_behind_opts);
+
+	git_config(git_default_config, NULL);
+
+	return 0;
+}

index 6171fd6769d..64e3d493561 100644
@@ -467,6 +467,7 @@ static int run_builtin(struct cmd_struct *p, int argc, const char **argv)
 
 static struct cmd_struct commands[] = {
 	{ "add", cmd_add, RUN_SETUP | NEED_WORK_TREE },
+	{ "ahead-behind", cmd_ahead_behind, RUN_SETUP },
 	{ "am", cmd_am, RUN_SETUP | NEED_WORK_TREE },
 	{ "annotate", cmd_annotate, RUN_SETUP },
 	{ "apply", cmd_apply, RUN_SETUP_GENTLY },

new file mode 100755
index 00000000000..bc08f1207a0
@@ -0,0 +1,17 @@
+#!/bin/sh
+
+test_description='git ahead-behind command-line options'
+
+. ./test-lib.sh
+
+test_expect_success 'git ahead-behind -h' '
+	test_must_fail git ahead-behind -h >out &&
+	grep "usage:" out
+'
+
+test_expect_success 'git ahead-behind without --base' '
+	test_must_fail git ahead-behind HEAD 2>err &&
+	grep "usage:" err
+'
+
+test_done

gitgitgadget

Stepping back a bit, this motivating example makes me wonder if

 $ git for-each-ref --format='%(refname) %(aheadbehind)' refs/heads/\*

that computes the ahead-behind number for each ref (that matches the pattern) based on their own "upstream" (presumably each branch is configured to track the same, or different, upstreams), or overrriding @{upstream}, a specified base, i.e.

 $ git for-each-ref --format='%(refname) %(aheadbehind:origin/main)' refs/heads/\*

would be a more intuitive interface to the end-users.

It would probably work well in conjunction with

    git for-each-ref --format='%(refname)' --merged origin/main refs/heads/\*

which is a way to list local branches that are already merged into the upstream, to have the feature appear in the same command, perhaps?

One disadvantage to using for-each-ref here is that we are bound to use all of the ref-sorting code, so callers can't see intermediate results until the entire walk is complete.

I can't remember enough of the details about the custom traversal we use here to know if that would even matter or not (i.e., do we need to traverse through the whole set of objects entirely before outputting a single result anyway?). But something to think about nonetheless.

At the very least, it is quite a cute idea (especially something like '%(aheadbehind:origin/main)') ;-).

One thing that we had talked about internally[^1] was the idea of specifying multiple bases. IOW, having some way to invoke the ahead-behind builtin that gives some set of tips with a common base B1, and another set of tips (which could--but doesn't have to--intersect with the first) and a common base to compare *them* to, say, B2.

There are some technical reasons that we might want to consider such a thing at least motivated by GitHub's proposed future use of it. But they are kind of technical and not that interesting to this discussion, so I wouldn't be sad if we didn't have a way to specify multiple bases.

OTOH, it would be nice to avoid painting ourselves into a corner from a UI-perspective if we can avoid it.

Thanks,
Taylor

[^1]: ...and couldn't decide if it was going to be a nice future addition or simply another case of YAGNI ;-).

This use of 'git for-each-ref --format=""' actually fixes some of the issues I had with how to specify multiple bases. I'm not sure there is a huge need for it, except that if we allow a "%(ahead-behind:<ref>)" format token, then we would need to support multiple bases.

Thankfully, the implementation in this series is already prepared for that, so the following diff implements this format token:

--- >8 ---

 builtin/for-each-ref.c | 50 ++++++++++++++++++++++++++++++++++++++++++
 ref-filter.c           | 23 +++++++++++++++++++
 ref-filter.h           | 15 ++++++++++++-
 3 files changed, 87 insertions(+), 1 deletion(-)

index 6f62f40d126..c8dd21d7e13 100644
@@ -5,6 +5,7 @@
 #include "object.h"
 #include "parse-options.h"
 #include "ref-filter.h"
+#include "commit-reach.h"
 
 static char const * const for_each_ref_usage[] = {
 	N_("git for-each-ref [<options>] [<pattern>]"),

@@ -14,6 +15,51 @@ static char const * const for_each_ref_usage[] = {
 	NULL
 };
 
+static void compute_ahead_behind(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++) {
+		const char *name = format->bases.items[i].string;
+		commits[i] = lookup_commit_reference_by_name(name);
+		if (!commits[i])
+			die("failed to find '%s'", name);
+	}
+
+	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]) {
+			warning(_("could not find '%s'"), name);
+			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 = format->bases.nr + i;
+			count->base_index = j;
+
+			array->items[i]->counts[j] = count;
+		}
+		commits_nr++;
+	}
+
+	ahead_behind(commits, commits_nr, array->counts, array->counts_nr);
+}
+
 int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 {
 	int i;

@@ -78,6 +124,10 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	filter.name_patterns = argv;
 	filter.match_as_path = 1;
 	filter_refs(&array, &filter, FILTER_REFS_ALL);
+
+	/* Do ahead-behind things, if necessary. */
+	compute_ahead_behind(&format, &array);
+
 	ref_array_sort(sorting, &array);
 
 	if (!maxcount || array.nr < maxcount)

index f8203c6b052..1706b9dd0d5 100644
@@ -158,6 +158,7 @@ enum atom_type {
 	ATOM_THEN,
 	ATOM_ELSE,
 	ATOM_REST,
+	ATOM_AHEADBEHIND,
 };
 
 /*

@@ -586,6 +587,16 @@ static int rest_atom_parser(struct ref_format *format, struct used_atom *atom,
 	return 0;
 }
 
+static int ahead_behind_atom_parser(struct ref_format *format, struct used_atom *atom,
+				    const char *arg, struct strbuf *err)
+{
+	if (!arg)
+		return strbuf_addf_ret(err, -1, _("expected format: %%(ahead-behind:<ref>)"));
+
+	string_list_append(&format->bases, arg);
+	return 0;
+}
+
 static int head_atom_parser(struct ref_format *format, struct used_atom *atom,
 			    const char *arg, struct strbuf *err)
 {

@@ -645,6 +656,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

@@ -1848,6 +1860,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);
 

@@ -1978,6 +1991,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;
 

index aa0eea4ecf5..937a857ddee 100644
@@ -5,6 +5,7 @@
 #include "refs.h"
 #include "commit.h"
 #include "parse-options.h"
+#include "string-list.h"
 
 /* Quoting styles */
 #define QUOTE_NONE 0

@@ -24,6 +25,7 @@
 
 struct atom_value;
 struct ref_sorting;
+struct ahead_behind_count;
 
 enum ref_sorting_order {
 	REF_SORTING_REVERSE = 1<<0,

@@ -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) \

2.40.0.vfs.0.0.3.g5872ac9aaa4

--- >8 ---

I can already see some things I want to change about this quick
and dirty implementation, but it gets the point across. This
"test" can be added to the end of t6302 for some demonstration:

test_expect_success 'ahead-behind' '
	git for-each-ref --format="%(refname) %(ahead-behind:HEAD)" &&
	git for-each-ref --format="%(refname) %(ahead-behind:HEAD) %(ahead-behind:refs/heads/side)"
'

What I have yet to determine is that 'git for-each-ref' does
not have significant overhead due to how it's implementation is
built around listing "all refs that match" versus an explicit
input list of refs. There's also the concept of '--stdin' that
would be interesting to interact with.

I'll continue to investigate this path and report back when I
have more of this information. This is as far I as I could get
today.

Thanks,
-Stolee

Yeah, we could add --no-sort to allow streaming better and --stdin to feed list of refs to work on, if the end-user facing interface based on --format is what people find reasonable.

Thanks. It is a very interesting experiment.

From: Derrick Stolee <[email protected]>

Before implementing the logic to compute the ahead/behind counts, parse the unknown options as commits and place them in a string_list.

Be sure to error out when the reference is not found.

---
 builtin/ahead-behind.c  | 39 +++++++++++++++++++++++++++++++++++++++
 t/t4218-ahead-behind.sh | 10 ++++++++++
 2 files changed, 49 insertions(+)

index a56cc565def..c1212cc8d46 100644
@@ -1,16 +1,31 @@
 #include "builtin.h"
 #include "parse-options.h"
 #include "config.h"
+#include "commit.h"
 
 static const char * const ahead_behind_usage[] = {
 	N_("git ahead-behind --base=<ref> [ --stdin | <revs> ]"),
 	NULL
 };
 
+static int handle_arg(struct string_list *tips, const char *arg)
+{
+	struct string_list_item *item;
+	struct commit *c = lookup_commit_reference_by_name(arg);
+
+	if (!c)
+		return error(_("could not resolve '%s'"), arg);
+
+	item = string_list_append(tips, arg);
+	item->util = c;
+	return 0;
+}
+
 int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
 {
 	const char *base_ref = NULL;
 	int from_stdin = 0;
+	struct string_list tips = STRING_LIST_INIT_DUP;
 
 	struct option ahead_behind_opts[] = {
 		OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")),

@@ -26,5 +41,29 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
 
 	git_config(git_default_config, NULL);
 
+	if (from_stdin) {
+		struct strbuf line = STRBUF_INIT;
+
+		while (strbuf_getline(&line, stdin) != EOF) {
+			if (!line.len)
+				break;
+
+			if (handle_arg(&tips, line.buf))
+				return 1;
+		}
+
+		strbuf_release(&line);
+	} else {
+		int i;
+		for (i = 0; i < argc; ++i) {
+			if (handle_arg(&tips, argv[i]))
+				return 1;
+		}
+	}
+
+	/* Early return for no tips. */
+	if (!tips.nr)
+		return 0;
+
 	return 0;
 }

index bc08f1207a0..3b8b9dc9887 100755
@@ -14,4 +14,14 @@ test_expect_success 'git ahead-behind without --base' '
 	grep "usage:" err
 '
 
+test_expect_success 'git ahead-behind with broken tip' '
+	test_must_fail git ahead-behind --base=HEAD bogus 2>err &&
+	grep "could not resolve '\''bogus'\''" err
+'
+
+test_expect_success 'git ahead-behind without tips' '
+	git ahead-behind --base=HEAD 2>err &&
+	test_must_be_empty err
+'
+
 test_done

gitgitgadget

This all looks reasonable (and forging my S-o-b here and elsewhere throughout this series is all fine). I have seen most of this code before at least in its final state, but the intermediate bits are new to me.

And they all look fine and familiar, except...

From: Derrick Stolee <[email protected]>

When parsing the tip revisions from the ahead-behind inputs, it is important to check that those tips exist before adding them to the list for computation. The previous change caused the builtin to return with errors if the revisions could not be resolved.

However, when running 'git ahead-behind' in an environment with concurrent edits, such as a Git server, then the references could be deleted from underneath the caller between reading the reference list and starting the 'git ahead-behind' process. Avoid this race by allowing the caller to specify '--ignore-missing' and continue using the information that is still available.

---
 Documentation/git-ahead-behind.txt | 6 ++++++
 builtin/ahead-behind.c             | 8 +++++++-
 t/t4218-ahead-behind.sh            | 6 ++++++
 3 files changed, 19 insertions(+), 1 deletion(-)

index 0e2f989a1a0..2dd5147f6b2 100644
@@ -50,6 +50,12 @@ OPTIONS
 	Read revision tips and ranges from stdin instead of from the
 	command-line.
 
+--ignore-missing::
+	When parsing tip references, ignore any references that are not
+	found. This is useful when operating in an environment where a
+	reference could be deleted between reading the reference and
+	starting the `git ahead-behind` process.
+
 
 SEE ALSO
 --------

index c1212cc8d46..e4f65fc0548 100644
@@ -8,13 +8,18 @@ static const char * const ahead_behind_usage[] = {
 	NULL
 };
 
+static int ignore_missing;
+
 static int handle_arg(struct string_list *tips, const char *arg)
 {
 	struct string_list_item *item;
 	struct commit *c = lookup_commit_reference_by_name(arg);
 
-	if (!c)
+	if (!c) {
+		if (ignore_missing)
+			return 0;
 		return error(_("could not resolve '%s'"), arg);
+	}
 
 	item = string_list_append(tips, arg);
 	item->util = c;

@@ -30,6 +35,7 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
 	struct option ahead_behind_opts[] = {
 		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_END()
 	};
 

index 3b8b9dc9887..56f16515896 100755
@@ -19,6 +19,12 @@ test_expect_success 'git ahead-behind with broken tip' '
 	grep "could not resolve '\''bogus'\''" err
 '
 
+test_expect_success 'git ahead-behind with broken tip and --ignore-missing' '
+	git ahead-behind --base=HEAD --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

gitgitgadget

Well explained, thanks for writing this all out :-).

From: Derrick Stolee <[email protected]>

This patch extracts the common code used to compute topological levels and corrected committer dates into a common routine, compute_reachable_generation_numbers_1().

This new routine dispatches to call the necessary functions to get and set the generation number for a given commit through a vtable (the compute_generation_info struct).

Computing the generation number itself is done in compute_generation_from_max(), which dispatches its implementation based on the generation version requested, or issuing a BUG() for unrecognized generation versions.

This patch cleans up the two places that currently compute topological levels and corrected commit dates by reducing the amount of duplicated code. It also makes it possible to introduce a function which dynamically computes those values for commits that aren't stored in a commit-graph, which will be required for the forthcoming ahead-behind rewrite.

---
 commit-graph.c | 171 +++++++++++++++++++++++++++++++------------------
 1 file changed, 107 insertions(+), 64 deletions(-)

index c11b59f28b3..deccf984a0d 100644
@@ -1446,24 +1446,53 @@ 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_1(
+			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;
+	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);
 
-		repo_parse_commit(ctx->r, c);
-		level = *topo_level_slab_at(ctx->topo_levels, c);
+		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);

@@ -1471,38 +1500,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;
+	display_progress(ctx->progress, ctx->progress_cnt + 1);
+}
+
+static void compute_topological_levels(struct write_commit_graph_context *ctx)
+{
+	struct compute_generation_info info = {
+		.r = ctx->r,
+		.progress = ctx->progress,
+		.commits = &ctx->commits,
+		.get_generation = get_topo_level,
+		.set_generation = set_topo_level,
+		.data = ctx,
+	};
+
+	if (ctx->report_progress)
+		ctx->progress = start_delayed_progress(
+					_("Computing commit graph topological levels"),
+					ctx->commits.nr);
+
+	compute_reachable_generation_numbers_1(&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 write_commit_graph_context *ctx = data;
+	struct commit_graph_data *g = commit_graph_data_at(c);
+	g->generation = (uint32_t)t;
+	display_progress(ctx->progress, ctx->progress_cnt + 1);
+}
+
 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,
+		.progress = ctx->progress,
+		.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(

@@ -1517,47 +1599,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_1(&info, 2);
 
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = ctx->commits.list[i];

@@ -1565,6 +1607,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX)
 			ctx->num_generation_data_overflows++;
 	}
+
 	stop_progress(&ctx->progress);
 }
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The commit_graph_generation() method used to report a value of GENERATION_NUMBER_INFINITY if the commit_graph_data_slab had an instance for the given commit but the graph_pos indicated the commit was not in the commit-graph file.

Instead, trust the 'generation' member if the commit has a value in the slab _and_ the 'generation' member is non-zero. Otherwise, treat it as GENERATION_NUMBER_INFINITY.

This only makes a difference for a very old case for the commit-graph:
the very first Git release to write commit-graph files wrote zeroes in the topological level positions. If we are parsing a commit-graph with all zeroes, those commits will now appear to have GENERATION_NUMBER_INFINITY (as if they were not parsed from the commit-graph).

I attempted several variations to work around the need for providing an uninitialized 'generation' member, but this was the best one I found. It does require a change to a verification test in t5318 because it reports a different error than the one about non-zero generation numbers.

---
 commit-graph.c          | 9 ++++-----
 t/t5318-commit-graph.sh | 2 +-
 2 files changed, 5 insertions(+), 6 deletions(-)

index deccf984a0d..f04b02be1bb 100644
@@ -111,17 +111,16 @@ uint32_t commit_graph_position(const struct commit *c)
 	return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;
 }
 
+
 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)

index 049c5fc8ead..b6e12115786 100755
@@ -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' '

gitgitgadget

From: Taylor Blau <[email protected]>

Use the just-introduced compute_reachable_generation_numbers_1() to implement a function which dynamically computes topological levels (or corrected commit dates) for out-of-graph commits.

This will be useful for the ahead-behind algorithm we are about to introduce, which needs accurate topological levels on _all_ commits reachable from the tips in order to avoid over-counting.

---
 commit-graph.c | 29 +++++++++++++++++++++++++++++
 commit-graph.h |  7 +++++++
 2 files changed, 36 insertions(+)

index f04b02be1bb..a573d1b89ff 100644
@@ -1610,6 +1610,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 commit **commits, size_t nr)
+{
+	struct repository *r = the_repository;
+	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_1(&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",

index 37faee6b66d..a529c62b518 100644
@@ -190,4 +190,11 @@ 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 commit **commits, size_t nr);
+
 #endif

gitgitgadget

Interesting and nice to see it done with so small a change thanks to the previous refactoring.

Stolee did all of the hard work ;-). But chiming in to say that I remember all of these changes well and they look faithful to my original read of them (as well as what I wrote in this patch).

So, LGTM so far.

Thanks,
Taylor

From: Derrick Stolee <[email protected]>

Fully implement the commit-counting logic behind the ahead-behind builtin as a new ahead_behind() method in commit-reach.h. Add tests for the functionality in both t4218-ahead-behind.sh and t6600-test-reach.sh. The tests in t4218 are rather simple, but cover a simple diamond commit history completely while the tests in t6600 make use of the more complicated commit history and the test setup to check three repository states: no commit-graph, a complete commit-graph, and a half-filled commit-graph. These extra states are particularly helpful to check due to the implementation of ahead_behind() and how it relies upon ensure_generations_valid().

The interface for ahead_behind() uses two arrays. The first array of commits contains the list of all starting points for the walk. This includes all tip commits _and_ base commits. The second array, using the new ahead_behind_count struct, indicates which commits from that initial array form the base/tip pair for the ahead/behind count it will store.

While the ahead-behind builtin currently only supports one base, this implementation of ahead_behind() allows multiple bases, if desired. Even with multiple bases, there is only one commit walk used for counting the ahead/behind values, saving time when the base/tip ranges overlap significantly.

This interface for ahead_behind() also makes it very easy to call ensure_generations_valid() on the entire array of bases and tips. This call is necessary because it is critical that the walk that counts ahead/behind values never walks a commit more than once. Without generation numbers on every commit, there is a possibility that a commit date skew could cause the walk to revisit a commit and then double-count it. For this reason, it is strongly recommended that 'git ahead-behind' is only run in a repository with a commit-graph file that covers most of the reachable commits, storing precomputed generation numbers. If no commit-graph exists, this walk will be much slower as it must walk all reachable commits in ensure_generations_valid() before performing the counting logic.

It is possible to detect if generation numbers are available at run time and redirect the implementation to another algorithm that does not require this property. However, that implementation requires a commit walk per base/tip pair _and_ can be slower due to the commit date heuristics required. Such an implementation could be considered in the future if there is a reason to include it, but most Git hosts should already be generating a commit-graph file as part of repository maintenance. Most Git clients should also be generating commit-graph files as part of background maintenance or automatic GCs.

Now, let's discuss the ahead/behind counting algorithm.

Each commit in the input commit list is associated with a bit position indicating "the ith commit can reach this commit". Each of these commits is associated with a bitmap with its position flipped on and then placed in a queue for walking commit history. We walk commits by popping the commit with maximum generation number out of the queue, guaranteeing that we will never walk a child of that commit in any future steps.

As we walk, we load the bitmap for the current commit and perform two main steps. The _second_ step examines each parent of the current commit and adds the current commit's bitmap bits to each parent's bitmap. (We create a new bitmap for the parent if this is our first time seeing that parent.) After adding the bits to the parent's bitmap, the parent is added to the walk queue. Due to this passing of bits to parents, the current commit has a guarantee that the ith bit is enabled on its bitmap if and only if the ith commit can reach the current commit.

The first step of the walk is to examine the bitmask on the current commit and decide which ranges the commit is in or not. Due to the "bit pushing" in the second step, we have a guarantee that the ith bit of the current commit's bitmap is on if and only if the ith starting commit can reach it. For each ahead_behind_count struct, check the base_index and tip_index to see if those bits are enabled on the current bitmap. If exactly one bit is enabled, then increment the corresponding 'ahead' or 'behind' count. This increment is the reason we _absolutely need_ to walk commits at most once.

The only subtle thing to do with this walk is to check to see if a parent has all bits on in its bitmap, in which case it becomes "stale" and is marked with the STALE bit. This allows queue_has_nonstale() to be the terminating condition of the walk, which greatly reduces the number of commits walked if all of the commits are nearby in history. It avoids walking a large number of common commits when there is a deep history. We also use the helper method insert_no_dup() to add commits to the priority queue without adding them multiple times. This uses the PARENT2 flag. Thus, we must clear both the STALE and PARENT2 bits of all commits, in case ahead_behind() is called multiple times in the same process.

There is no previous implementation of ahead-behind to compare against. A previous implementation in another fork of Git used a single process to essentially do the same walk as 'git rev-list --count <base>..<tip>' for every base/tip pair given as input. The single-walk implementation in this change was a significant improvement over that implementation. Another version from that fork used reachability bitmaps for the comparison, but that implementation was slower than the current commit walk implementation in almost all cases.

To best present _some_ amount of evidence for this performance gain, create a new performance test, p1500-graph-walks.sh. This script could be used for other walks than just ahead-behind in the future, but let's limit to ahead-behind now.

To gain some amount of a baseline, create one test that checks 'git ahead-behind' against up to 50 tips and another that uses 'git rev-list --count' in a loop. Be sure to write a commit-graph before running the performance tests.

Using the Git source code as the repository, we see a pronounced improvement:

Test this tree
---------------------------------------------------------------
1500.2: ahead-behind counts: git ahead-behind 0.08(0.07+0.01)
1500.3: ahead-behind counts: git rev-list 1.11(0.92+0.18)

But the de-facto performance benchmark is the Linux kernel repository, which presents these values for my copy:

Test this tree
---------------------------------------------------------------
1500.2: ahead-behind counts: git ahead-behind 0.27(0.25+0.02)
1500.3: ahead-behind counts: git rev-list 4.53(3.92+0.60)

---
 builtin/ahead-behind.c      | 23 +++++++++
 commit-reach.c              | 95 +++++++++++++++++++++++++++++++++++++
 commit-reach.h              | 30 ++++++++++++
 t/perf/p1500-graph-walks.sh | 25 ++++++++++
 t/t4218-ahead-behind.sh     | 67 ++++++++++++++++++++++++++
 t/t6600-test-reach.sh       | 62 ++++++++++++++++++++++++
 6 files changed, 302 insertions(+)
 create mode 100755 t/perf/p1500-graph-walks.sh

index e4f65fc0548..c06b95b5f37 100644
@@ -2,6 +2,7 @@
 #include "parse-options.h"
 #include "config.h"
 #include "commit.h"
+#include "commit-reach.h"
 
 static const char * const ahead_behind_usage[] = {
 	N_("git ahead-behind --base=<ref> [ --stdin | <revs> ]"),

@@ -29,8 +30,12 @@ static int handle_arg(struct string_list *tips, const char *arg)
 int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
 {
 	const char *base_ref = NULL;
+	struct commit *base;
 	int from_stdin = 0;
 	struct string_list tips = STRING_LIST_INIT_DUP;
+	struct commit **commits;
+	struct ahead_behind_count *counts;
+	size_t i;
 
 	struct option ahead_behind_opts[] = {
 		OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")),

@@ -71,5 +76,23 @@ int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
 	if (!tips.nr)
 		return 0;
 
+	ALLOC_ARRAY(commits, tips.nr + 1);
+	ALLOC_ARRAY(counts, tips.nr);
+
+	for (i = 0; i < tips.nr; i++) {
+		commits[i] = tips.items[i].util;
+		counts[i].tip_index = i;
+		counts[i].base_index = tips.nr;
+	}
+	commits[tips.nr] = base;
+
+	ahead_behind(commits, tips.nr + 1, counts, tips.nr);
+
+	for (i = 0; i < tips.nr; i++)
+		printf("%s %d %d\n", tips.items[i].string,
+		       counts[i].ahead, counts[i].behind);
+
+	free(counts);
+	free(commits);
 	return 0;
 }

index 148b56fea50..1780f9317bf 100644
@@ -104,4 +104,34 @@ 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.
+	 */
+	int ahead;
+	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 commit **commits, size_t commits_nr,
+		  struct ahead_behind_count *counts, size_t counts_nr);
+
 #endif

new file mode 100755
index 00000000000..c9ac4b7e6e2
@@ -0,0 +1,25 @@
+#!/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 &&
+	git commit-graph write --reachable
+'
+
+test_perf 'ahead-behind counts: git ahead-behind' '
+	git ahead-behind --base=HEAD --stdin <refs
+'
+
+test_perf 'ahead-behind counts: git rev-list' '
+	for r in $(cat refs)
+	do
+		git rev-list --count "HEAD..$r" || return 1
+	done
+'
+
+test_done

gitgitgadget

Having read and worked with this code before, I don't have a ton of substance to add here. But it was interesting to reread, and I left a few sprinklings here and there of some thing that we may want to consider for v2.

Before that, though, IIRC we wrote most of this together, so I would be happy to have my:

above your S-o-b here. But you've done so much work since we originally wrote this together that I don't mind being dropped here. Up to you :-).

    (self->words[EWAH_BLOCK(pos)] & EWAH_MASK(pos)) != 0

    self->words[EWAH_BLOCK(pos)] & EWAH_MASK(pos)

    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 (bitmap_popcount(bitmap_p) == commits_nr)
      p->item->object.flags |= STALE;
    else
      insert_no_dup(&queue, p->item);

Sounds good. Sorry for forgetting that collaboration.

I'll add a comment before we clear the bits, to be clear about why we need each bit.

Can't hurt.

We need to push p->item to the queue, even if stale, because it may need to be walked in order to pass the bitmaps (and the STALE bit) to other commits that were reached by only a subset of the tips.

Here's an example:

     A B
     |/ \
     C   D
     |  /
     E /
     |/
     F

If A and B are the starting commits, then C is stale when we walk it, so its parent E would be stale. Your proposed change would not add it to the queue, and thus F would never see that it is stale and would be counted as reachable from B but not A.

Unsigned sounds good.

I think double-asterisk is the preferred choice for new things, but commit-reach.h only uses a single asterisk so I'll change this to be consistent.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

The 'git ahead-behind' builtin can answer a list of questions that do not require the full ahead/behind counts. For example, instead of using 'git branch --contains=<ref>' to get the full list of branches that contain the commit at <ref>, a list of tips could be passed to 'git ahead-behind --base=<ref>' and the rows that report a "behind" value of zero show which tips can reach <ref>.

By contract, the rows that report an "ahead" value of zero show which tips are reachable from the given base. This type of query does not have an existing equivalent for batching this request. While extracting the information from 'git ahead-behind' is not terribly difficult, it does more work than required to answer this query: it _counts_.

Add a new '--contains' mode to 'git ahead-behind' that removes the counting behavior and focuses instead on the reachability concern. The output of the builtin changes in this mode: instead of reporting "<tip> <ahead> <behind>" for every input tip, it will instead report "<tip>" for the input tips that are reachable from the specified base.

The algorithm is implemented in commit-reach.c in the method tips_reachable_from_base(). This method takes a string_list of tips and assigns the 'util' for each item with the value 1 if the base commit can reach those tips.

Like other reachability queries in commit-reach.c, the fastest way to search for "can A reach B?" is to do a depth-first search up to the generation number of B, preferring to explore first parents before later parents. While we must walk all reachable commits up to that generation number when the answer is "no", the depth-first search can answer "yes" much faster than other approaches in most cases.

This search becomes trickier when there are multiple targets for the depth-first search. The commits with lower generation number are more likely to be within the history of the start commit, but we don't want to waste time searching commits of low generation number if the commit target with lowest generation number has already been found.

The trick here is to take the input commits and sort them by generation number in ascending order. Track the index within this order as min_generation_index. When we find a commit, if its index in the list is equal to min_generation_index, then we can increase the generation number boundary of our search to the next-lowest value in the list.

With this mechanism, the number of commits to search is minimized with respect to the depth-first search heuristic. We will walk all commits up to the minimum generation number of a commit that is _not_ reachable from the start, but we will walk only the necessary portion of the depth-first search for the reachable commits of lower generation.

We can test this completely in the simple repo example in t4218 and more substantially in the larger repository example in t6600. We can also add a performance test to demonstrate the speedup relative to the 'git ahead-behind' builtin without the '--contains' option.

For the Git source code repository, I was able to measure a speedup, even though both are quite fast.

Test this tree
--------------------------------------------------------------------------

1500.2: ahead-behind counts: git ahead-behind              0.06(0.06+0.00)
1500.3: ahead-behind counts: git rev-list                  1.08(0.90+0.18)
1500.4: ahead-behind counts: git ahead-behind --contains   0.02(0.02+0.00)

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

Test this tree
--------------------------------------------------------------------------

1500.2: ahead-behind counts: git ahead-behind              0.26(0.25+0.01)
1500.3: ahead-behind counts: git rev-list                  4.58(3.92+0.66)
1500.4: ahead-behind counts: git ahead-behind --contains   0.02(0.00+0.02)

---
 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(-)

index 2dd5147f6b2..1652a51d719 100644
@@ -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

index c06b95b5f37..4efd324d5d9 100644
@@ -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);
 

index 1780f9317bf..fa8994f5696 100644
@@ -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

index c9ac4b7e6e2..56de6c5b13d 100755
@@ -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

gitgitgadget

This makes readers wonder if "git rev-list --count B...C" should be the end-user facing UI for this new feature, perhaps?

Of course if you are checking how C0, C1, C2,... relate to a single B, the existing rev-list syntax would not work, and makes a totally new subcommand a possibilty.

I thought that the reverse of "git branch --contains" was "git branch --merged". "git branch --merged maint ??/\*" is how I cull topic branches that have already served their purpose.

Isn't closing pull requests because they have been already merged the same idea? "git for-each-ref --merged main refs/pull/\*" or something, perhaps?

All of the above are from only reading the cover letter. I'm sure I'll have more thoughts or even change my mind after reading the patches.

Thanks.

You are definitely on to something, and I was not aware of --merged as an option to either of these.

'git branch --merged' has some limitations that tags cannot be used.

'git for-each-ref --merged' is probably sufficient. The only difference being that it would be nice to specify the matching refs over stdin with --stdin to avoid long argument lists.

With this in mind, I can update the performance test to look like this (after updating the setup step to add branches for each line in 'refs')

test_perf 'batch reachability: git ahead-behind --contains' '

	git ahead-behind --contains --base=HEAD --stdin <refs

'

test_perf 'batch reachability: git branch --merged' '

	xargs git branch --merged=HEAD <branches

'

test_perf 'batch reachability: git for-each-ref --merged' '

	xargs git for-each-ref --merged=HEAD <refs

'

And get decent results on all cases with the Linux kernel repository:

Test this tree
-------------------------------------------------------------------------

1500.2: ahead-behind counts: git ahead-behind             0.26(0.24+0.01)
1500.3: ahead-behind counts: git rev-list                 4.46(3.91+0.54)
1500.4: batch reachability: git ahead-behind --contains   0.02(0.01+0.01)
1500.5: batch reachability: git branch --merged           0.14(0.13+0.00)
1500.6: batch reachability: git for-each-ref --merged     0.14(0.13+0.00)

So, there is benefit in using this tips_reachable_from_base() method in the two existing 'git (branch|for-each-ref) --merged' computations. The API boundary selected in this series might not be the most appropriate for those builtins, so let's kick out patch 8 from this series for now and I'll revisit it separately.

Thanks,
-Stolee

Yeah, if you have a list of concrete refs maintained externally (as opposed to the example I responded to, where you generate the refs by telling for-each-ref what pattern they should match), having --stdin would be a good thing.

Yup, if the reachability API refactoring in these patches can also help the "for-each-ref" listing (which "git branch" and "git tag" bases their listing behaviour), it would be very good.

Thanks.

Yeah. You could imagine that rev-list --count might do something fancy like coalescing

    git rev-list --count B...C1 B...C2 B...C3

into a single walk. But I am not sure that just because rev-list --count provides similar functionality that we should fold in the proposed ahead-behind interface into that flag.

On the other hand, I could see a compelling argument for a slightly different syntax (maybe --count-ahead-behind or --count=ahead-behind) that would fold this functionality into rev-list.

And that is the sort of thing that we would want to settle on sooner rather than later, since it's fairly baked in once we decide one way or another and then merge this up.

My personal feeling is that we ought to avoid (further) overloading rev-list absent of a compelling reason to do so. But I am definitely open to other thoughts here.

Thanks,
Taylor

It does coalesce all of that into a single walk. The problem is somewhat the opposite: it only has a notion of two "sides" for a symmetric
traversal: left and right. But in your example there are many sides, and we have to remember which is which.

I think getting the answer from one walk would require an arbitrary number of bits to paint down each path. Certainly the ahead-behind that Vicent and I wrote long ago didn't do that (IIRC it mostly relied on doing multiple traversals in the same process, which amortized the cost of commit parsing; that's not really an issue these days with commit graphs).

Peeking at patch 7 of Stolee's series...yep. That's exactly what it does. :)

I wondered how much it would matter on top of a naive loop of single-traversals, now that we have commit graphs. It looks like there's still quite a nice speedup from the numbers in patch 7 (though the totally naive "loop of rev-list" is incurring extra startup overhead, too).

So I think this actually is what "git rev-list --left-right --count old...new" does now. But extending it to multiple sets in one traversal means you need:

- being able to ask for individual left-right markers for each pair, not treating all lefts and all rights together

- don't stop traversing when you hit an UNINTERESTING commit if there are still bits to paint. In a single-pair traversal, those two are the same thing (we stop at the merge base), but with multiple pairs you may have to keep walking past a commit that is excluded from one pair, but not another. This _might_ be doable if you assume all of the left-hand bases are the same, but I didn't think hard enough to feel confident in that. But even so, that only solves cases like "how do these branches compare to HEAD" (which I think is what GitHub does). But it doesn't allow "how do these branches compare to to their respective @{upstream} refs".

So I don't think it would be impossible to make this a mode of rev-list. And that mode might even provide flexibility for other similar operations, like a mass "git rev-list --cherry-mark"[1]. But it is a pretty big departure from the current rev-list traversal (to my mind, especially the "keep walking past UNINTERESTING part). I don't mind it as its own command.

-Peff

[1] The reason you might want a mass cherry-mark is basically doing something like the "branches" page, but in a workflow where upstream applies patches, like git.git. There you may want to ask about "origin/next...$branch" for all of your branches to see which ones have been merged where.

Yeah, this reminds me of what I had to do in "show-branch", where each tip gets assigned a bit in the object->flags (which means it can only traverse from a very small limited number of tips, like 30 or so), which I once planned to extend to arbitrary number of tips by storing these bits in commit slab, but it never materialized.

I agree this is not a good fit for the mental model of rev-list or the revision.c::get_revision() traversal.

Thanks.

Thanks for a helpful summary of all of the details here. I am of course familiar with your use of this builtin at our common $DAYJOB, but it was nice to see a from-scratch explanation of what you're trying to do here.

Now let's take a look at how the patches came together... ;-).

Thanks,
Taylor

At $DAYJOB, we have used a custom 'ahead-behind' builtin in our fork of Git for lots of reasons. The main goal of the builtin is to compare multiple references against a common base reference. The comparison is number of commits that are in each side of the symmtric difference of their reachable sets. A commit C is "ahead" of a commit B by the number of commits in B..C (reachable from C but not reachable from B). Similarly, the commit C is "behind" the commit B by the number of commits in C..B (reachable from B but not reachable from C).

These numbers can be computed by 'git rev-list --count B..C' and 'git rev-list --count C..B', but there are common needs that benefit from having the checks being done in the same process:

1. Our "branches" page lists ahead/behind counts for each listed branch as compared to the repo's default branch. This can be done with a single 'git ahead-behind' process.
2. When a branch is updated, a background job checks if any pull requests that target that branch should be closed because their branches were merged implicitly by that update. These queries can e batched into 'git ahead-behind' calls.

In that second example, we don't need the full ahead/behind counts (although it is sufficient to look for branches that are "zero commits ahead", meaning they are reachable from the base), and instead reachability is the critical piece.

This series contributes the custom algorithms we used for our 'git ahead-behind' builtin, but as extensions to 'git for-each-ref':

* Add a new "%(ahead-behind:)" format token to for-each-ref which allows outputting the ahead/behind values in the format string for a matching ref.
* Add a new algorithm that speeds up the 'git for-each-ref --merged=' option. This also applies to the 'git branch --merged=' option.

The idea to use 'git for-each-ref' instead of creating a new builtin is from Junio, and simplifies this series significantly compared to v1. I was initially concerned about the overhead of 'git for-each-ref' and its generality and sorting, but I was not able to measure any important difference between this implementation and our internal 'git ahead-behind' implementation. In particular, when a pattern is given to 'git for-each-ref' that looks like an exact ref, it navigates directly to the ref instead of scanning all references for matches.

However, for our specific uses, we like to batch a list of exact references that could be very long. We introduce a new --stdin option here.

To keep things close to the v1 outline, I replaced the existing patches with closely-related ones, when possible.

Patch 1 adds the --stdin option to 'git for-each-ref'. (This is similar to the boilerplate patch from v1.)

Patch 2 adds a test to explicitly check that 'git for-each-ref' will still succeed when all input refs are missing. (This is similar to the --ignore-missing patch from v1.)

Patches 3-5 introduce a new method: ensure_generations_valid(). Patch 3 does some refactoring of the existing generation number computations to make it more generic, and patch 4 updates the definition of commit_graph_generation() slightly, making way for patch 5 to implement the method. With an existing commit-graph file, the commits that are not present in the file are considered as having generation number "infinity". This is useful for most of our reachability queries to this point, since those commits are "above" the ones tracked by the commit-graph. When these commits are low in number, then there is very little performance cost and zero correctness cost. (These patches match v1 exactly.)

However, we will see that the ahead/behind computation requires accurate generation numbers to avoid overcounting. Thus, ensure_generations_valid() is a way to specify a list of commits that need generation numbers computed before continuing. It's a no-op if all of those commits are in the commit-graph file. It's expensive if the commit-graph doesn't exist. However, '%(ahead-behind:)' computations are likely to be slow no matter what without a commit-graph, so assuming an existing commit-graph file is reasonable. If we find sufficient desire to have an implementation that does not have this requirement, we could create a second implementation and toggle to it when generation_numbers_enabled() returns false.

Patch 6 implements the ahead-behind algorithm, but it is not connected to a builtin. It's a long commit message, so hopefully it explains the algorithm sufficiently. (The difference from v1 is that it no longer integrates with a builtin and there are no new tests. It also uses 'unsigned int' and is correctly co-authored by Taylor.)

Patch 7 integrates the ahead-behind algorithm with the ref-filter code, including parsing the "ahead-behind" token. This finally adds tests that check both ahead_behind() and ensure_generations_valid() via t6600-test-reach.sh. (This patch is essentially completely new in v2.)

Patch 8 implements the tips_reachable_from_base() method, and uses it within the ref-filter code to speed up 'git for-each-ref --merged' and 'git branch --merged'. (The interface is slightly different than v1, due to the needs of the new caller.)

Thanks, -Stolee

Derrick Stolee (7):
for-each-ref: add --stdin option
for-each-ref: explicitly test no matches
commit-graph: combine generation computations
commit-graph: return generation from memory
commit-reach: implement ahead_behind() logic
for-each-ref: add ahead-behind format atom
commit-reach: add tips_reachable_from_bases()

Taylor Blau (1):
commit-graph: introduce ensure_generations_valid()

 Documentation/git-for-each-ref.txt |  12 +-
 builtin/branch.c                   |   1 +
 builtin/for-each-ref.c             |  32 ++++-
 builtin/tag.c                      |   1 +
 commit-graph.c                     | 208 ++++++++++++++++++----------
 commit-graph.h                     |   7 +
 commit-reach.c                     | 210 +++++++++++++++++++++++++++++
 commit-reach.h                     |  38 ++++++
 ref-filter.c                       |  89 +++++++++---
 ref-filter.h                       |  25 +++-
 t/perf/p1500-graph-walks.sh        |  50 +++++++
 t/t3203-branch-output.sh           |  14 ++
 t/t5318-commit-graph.sh            |   2 +-
 t/t6300-for-each-ref.sh            |  50 +++++++
 t/t6301-for-each-ref-errors.sh     |  12 ++
 t/t6600-test-reach.sh              | 169 +++++++++++++++++++++++
 t/t7004-tag.sh                     |  28 ++++
 17 files changed, 859 insertions(+), 89 deletions(-)
 create mode 100755 t/perf/p1500-graph-walks.sh

base-commit: 725f57037d81e24eacfda6e59a19c60c0b4c8062
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1489%2Fderrickstolee%2Fstolee%2Fupstream-ahead-behind-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1489/derrickstolee/stolee/upstream-ahead-behind-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1489

Range-diff vs v1:

 1:  0fd18b6d740 < -:  ----------- ahead-behind: create empty builtin
 2:  08fc0710017 ! 1:  a1d9e0f6ff6 ahead-behind: parse tip references
     @@ Metadata
      Author: Derrick Stolee <[email protected]>
      
       ## Commit message ##
     -    ahead-behind: parse tip references
     +    for-each-ref: add --stdin option
      
     -    Before implementing the logic to compute the ahead/behind counts, parse
     -    the unknown options as commits and place them in a string_list.
     +    When a user wishes to input a large list of patterns to 'git
     +    for-each-ref' (likely a long list of exact refs) there are frequently
     +    system limits on the number of command-line arguments.
      
     -    Be sure to error out when the reference is not found.
     +    Add a new --stdin option to instead read the patterns from standard
     +    input. Add tests that check that any unrecognized arguments are
     +    considered an error when --stdin is provided. Also, an empty pattern
     +    list is interpreted as the complete ref set.
     +
     +    When reading from stdin, we populate the filter.name_patterns array
     +    dynamically as opposed to pointing to the 'argv' array directly. This
     +    requires a careful cast while freeing the individual strings,
     +    conditioned on the --stdin option.
      
     -    Co-authored-by: Taylor Blau <[email protected]>
     -    Signed-off-by: Taylor Blau <[email protected]>
          Signed-off-by: Derrick Stolee <[email protected]>
      
     - ## builtin/ahead-behind.c ##
     -@@
     - #include "builtin.h"
     - #include "parse-options.h"
     - #include "config.h"
     -+#include "commit.h"
     - 
     - static const char * const ahead_behind_usage[] = {
     - 	N_("git ahead-behind --base=<ref> [ --stdin | <revs> ]"),
     - 	NULL
     - };
     + ## Documentation/git-for-each-ref.txt ##
     +@@ Documentation/git-for-each-ref.txt: 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>]]
     +@@ Documentation/git-for-each-ref.txt: OPTIONS
     + 	literally, in the latter case matching completely or from the
     + 	beginning up to a slash.
       
     -+static int handle_arg(struct string_list *tips, const char *arg)
     -+{
     -+	struct string_list_item *item;
     -+	struct commit *c = lookup_commit_reference_by_name(arg);
     -+
     -+	if (!c)
     -+		return error(_("could not resolve '%s'"), arg);
     -+
     -+	item = string_list_append(tips, arg);
     -+	item->util = c;
     -+	return 0;
     -+}
     ++--stdin::
     ++	If `--stdin` is supplied, then the list of patterns is read from
     ++	standard input instead of from the argument list.
      +
     - int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
     - {
     - 	const char *base_ref = NULL;
     - 	int from_stdin = 0;
     -+	struct string_list tips = STRING_LIST_INIT_DUP;
     + --count=<count>::
     + 	By default the command shows all refs that match
     + 	`<pattern>`.  This option makes it stop after showing
     +
     + ## builtin/for-each-ref.c ##
     +@@ builtin/for-each-ref.c: 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 option ahead_behind_opts[] = {
     - 		OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")),
     -@@ builtin/ahead-behind.c: int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
     + 	struct option opts[] = {
     + 		OPT_BIT('s', "shell", &format.quote_style,
     +@@ builtin/for-each-ref.c: 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(),
     + 	};
       
     - 	git_config(git_default_config, NULL);
     +@@ builtin/for-each-ref.c: 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;
     ++		size_t nr = 0, alloc = 16;
      +
     -+		while (strbuf_getline(&line, stdin) != EOF) {
     -+			if (!line.len)
     -+				break;
     ++		if (argv[0])
     ++			die(_("unknown arguments supplied with --stdin"));
      +
     -+			if (handle_arg(&tips, line.buf))
     -+				return 1;
     ++		CALLOC_ARRAY(filter.name_patterns, alloc);
     ++
     ++		while (strbuf_getline(&line, stdin) != EOF) {
     ++			ALLOC_GROW(filter.name_patterns, nr + 1, alloc);
     ++			filter.name_patterns[nr++] = strbuf_detach(&line, NULL);
      +		}
      +
     -+		strbuf_release(&line);
     ++		/* Add a terminating NULL string. */
     ++		ALLOC_GROW(filter.name_patterns, nr + 1, alloc);
     ++		filter.name_patterns[nr + 1] = NULL;
      +	} else {
     -+		int i;
     -+		for (i = 0; i < argc; ++i) {
     -+			if (handle_arg(&tips, argv[i]))
     -+				return 1;
     -+		}
     ++		filter.name_patterns = argv;
      +	}
      +
     -+	/* Early return for no tips. */
     -+	if (!tips.nr)
     -+		return 0;
     -+
     + 	filter.match_as_path = 1;
     + 	filter_refs(&array, &filter, FILTER_REFS_ALL);
     + 	ref_array_sort(sorting, &array);
     +@@ builtin/for-each-ref.c: 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);
     ++	if (from_stdin) {
     ++		for (size_t i = 0; filter.name_patterns[i]; i++)
     ++			free((char *)filter.name_patterns[i]);
     ++		free(filter.name_patterns);
     ++	}
       	return 0;
       }
      
     - ## t/t4218-ahead-behind.sh ##
     -@@ t/t4218-ahead-behind.sh: test_expect_success 'git ahead-behind without --base' '
     - 	grep "usage:" err
     - '
     + ## t/t6300-for-each-ref.sh ##
     +@@ t/t6300-for-each-ref.sh: 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 ahead-behind with broken tip' '
     -+	test_must_fail git ahead-behind --base=HEAD bogus 2>err &&
     -+	grep "could not resolve '\''bogus'\''" err
     ++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 ahead-behind without tips' '
     -+	git ahead-behind --base=HEAD 2>err &&
     -+	test_must_be_empty err
     ++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_done
 3:  b1d022c7cac < -:  ----------- ahead-behind: implement --ignore-missing option
 -:  ----------- > 2:  2f162a2f39f for-each-ref: explicitly test no matches
 4:  853891c0b14 = 3:  db28e82d2a6 commit-graph: combine generation computations
 5:  c6e6581e0ea ! 4:  3cf33801443 commit-graph: return generation from memory

@@ Commit message

## commit-graph.c ##
-@@ commit-graph.c: uint32_t commit_graph_position(const struct commit *c)
- return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;
- }
-
-+
- timestamp_t commit_graph_generation(const struct commit *c)
- {
+@@ commit-graph.c: timestamp_t commit_graph_generation(const struct commit *c)
struct commit_graph_data *data =
commit_graph_data_slab_peek(&commit_graph_data_slab, c);

 6:  f31994ac78a = 5:  34dffd836b1 commit-graph: introduce `ensure_generations_valid()`
 7:  b8c55ecf88d ! 6:  9831c23eadb ahead-behind: implement ahead_behind() logic
     @@ Metadata
      Author: Derrick Stolee <[email protected]>
      
       ## Commit message ##
     -    ahead-behind: implement ahead_behind() logic
     +    commit-reach: implement ahead_behind() logic
      
     -    Fully implement the commit-counting logic behind the ahead-behind
     -    builtin as a new ahead_behind() method in commit-reach.h. Add tests
     -    for the functionality in both t4218-ahead-behind.sh and
     -    t6600-test-reach.sh. The tests in t4218 are rather simple, but cover a
     -    simple diamond commit history completely while the tests in t6600 make
     -    use of the more complicated commit history and the test setup to check
     -    three repository states: no commit-graph, a complete commit-graph, and a
     -    half-filled commit-graph. These extra states are particularly helpful to
     -    check due to the implementation of ahead_behind() and how it relies upon
     -    ensure_generations_valid().
     +    Fully implement the commit-counting logic required to determine
     +    ahead/behind counts for a batch of commit pairs. This is a new library
     +    method within commit-reach.h. This method will be linked to the
     +    for-each-ref builtin in the next change.
      
          The interface for ahead_behind() uses two arrays. The first array of
          commits contains the list of all starting points for the walk. This
     @@ Commit message
          new ahead_behind_count struct, indicates which commits from that initial
          array form the base/tip pair for the ahead/behind count it will store.
      
     -    While the ahead-behind builtin currently only supports one base, this
     -    implementation of ahead_behind() allows multiple bases, if desired. Even
     -    with multiple bases, there is only one commit walk used for counting the
     -    ahead/behind values, saving time when the base/tip ranges overlap
     -    significantly.
     +    This implementation of ahead_behind() allows multiple bases, if desired.
     +    Even with multiple bases, there is only one commit walk used for
     +    counting the ahead/behind values, saving time when the base/tip ranges
     +    overlap significantly.
      
          This interface for ahead_behind() also makes it very easy to call
          ensure_generations_valid() on the entire array of bases and tips. This
     @@ Commit message
          commits, in case ahead_behind() is called multiple times in the same
          process.
      
     -    There is no previous implementation of ahead-behind to compare against.
     -    A previous implementation in another fork of Git used a single process
     -    to essentially do the same walk as 'git rev-list --count <base>..<tip>'
     -    for every base/tip pair given as input. The single-walk implementation
     -    in this change was a significant improvement over that implementation.
     -    Another version from that fork used reachability bitmaps for the
     -    comparison, but that implementation was slower than the current commit
     -    walk implementation in almost all cases.
     -
     -    To best present _some_ amount of evidence for this performance gain,
     -    create a new performance test, p1500-graph-walks.sh. This script could
     -    be used for other walks than just ahead-behind in the future, but let's
     -    limit to ahead-behind now.
     -
     -    To gain some amount of a baseline, create one test that checks 'git
     -    ahead-behind' against up to 50 tips and another that uses 'git rev-list
     -    --count' in a loop. Be sure to write a commit-graph before running the
     -    performance tests.
     -
     -    Using the Git source code as the repository, we see a pronounced
     -    improvement:
     -
     -    Test                                            this tree
     -    ---------------------------------------------------------------
     -    1500.2: ahead-behind counts: git ahead-behind   0.08(0.07+0.01)
     -    1500.3: ahead-behind counts: git rev-list       1.11(0.92+0.18)
     -
     -    But the de-facto performance benchmark is the Linux kernel repository,
     -    which presents these values for my copy:
     -
     -    Test                                            this tree
     -    ---------------------------------------------------------------
     -    1500.2: ahead-behind counts: git ahead-behind   0.27(0.25+0.02)
     -    1500.3: ahead-behind counts: git rev-list       4.53(3.92+0.60)
     -
     +    Co-authored-by: Taylor Blau <[email protected]>
     +    Signed-off-by: Taylor Blau <[email protected]>
          Signed-off-by: Derrick Stolee <[email protected]>
      
     - ## builtin/ahead-behind.c ##
     -@@
     - #include "parse-options.h"
     - #include "config.h"
     - #include "commit.h"
     -+#include "commit-reach.h"
     - 
     - static const char * const ahead_behind_usage[] = {
     - 	N_("git ahead-behind --base=<ref> [ --stdin | <revs> ]"),
     -@@ builtin/ahead-behind.c: static int handle_arg(struct string_list *tips, const char *arg)
     - int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
     - {
     - 	const char *base_ref = NULL;
     -+	struct commit *base;
     - 	int from_stdin = 0;
     - 	struct string_list tips = STRING_LIST_INIT_DUP;
     -+	struct commit **commits;
     -+	struct ahead_behind_count *counts;
     -+	size_t i;
     - 
     - 	struct option ahead_behind_opts[] = {
     - 		OPT_STRING('b', "base", &base_ref, N_("base"), N_("base reference to process")),
     -@@ builtin/ahead-behind.c: int cmd_ahead_behind(int argc, const char **argv, const char *prefix)
     - 	if (!tips.nr)
     - 		return 0;
     - 
     -+	ALLOC_ARRAY(commits, tips.nr + 1);
     -+	ALLOC_ARRAY(counts, tips.nr);
     -+
     -+	for (i = 0; i < tips.nr; i++) {
     -+		commits[i] = tips.items[i].util;
     -+		counts[i].tip_index = i;
     -+		counts[i].base_index = tips.nr;
     -+	}
     -+	commits[tips.nr] = base;
     -+
     -+	ahead_behind(commits, tips.nr + 1, counts, tips.nr);
     -+
     -+	for (i = 0; i < tips.nr; i++)
     -+		printf("%s %d %d\n", tips.items[i].string,
     -+		       counts[i].ahead, counts[i].behind);
     -+
     -+	free(counts);
     -+	free(commits);
     - 	return 0;
     - }
     -
       ## commit-reach.c ##
      @@
       #include "revision.h"
     @@ commit-reach.c: struct commit_list *get_reachable_subset(struct commit **from, i
      +		struct bitmap *bitmap_c = init_bit_array(c, width);
      +
      +		for (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);
     ++			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)
     @@ commit-reach.c: struct commit_list *get_reachable_subset(struct commit **from, i
      +		free_bit_array(c);
      +	}
      +
     ++	/* STALE is used here, PARENT2 is used by insert_no_dup(). */
      +	repo_clear_commit_marks(the_repository, PARENT2 | STALE);
      +	clear_bit_arrays(&bit_arrays);
      +	clear_prio_queue(&queue);
     @@ commit-reach.h: struct commit_list *get_reachable_subset(struct commit **from, i
      +	 * 'behind' stores the number of commits reachable from the base
      +	 * and not reachable from the tip.
      +	 */
     -+	int ahead;
     -+	int behind;
     ++	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.
      + */
     @@ commit-reach.h: struct commit_list *get_reachable_subset(struct commit **from, i
      +		  struct ahead_behind_count *counts, size_t counts_nr);
      +
       #endif
     -
     - ## t/perf/p1500-graph-walks.sh (new) ##
     -@@
     -+#!/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 &&
     -+	git commit-graph write --reachable
     -+'
     -+
     -+test_perf 'ahead-behind counts: git ahead-behind' '
     -+	git ahead-behind --base=HEAD --stdin <refs
     -+'
     -+
     -+test_perf 'ahead-behind counts: git rev-list' '
     -+	for r in $(cat refs)
     -+	do
     -+		git rev-list --count "HEAD..$r" || return 1
     -+	done
     -+'
     -+
     -+test_done
     -
     - ## t/t4218-ahead-behind.sh ##
     -@@ t/t4218-ahead-behind.sh: test_description='git ahead-behind command-line options'
     - 
     - . ./test-lib.sh
     - 
     -+test_expect_success 'setup simple history' '
     -+	test_commit base &&
     -+	git checkout -b right &&
     -+	test_commit right &&
     -+	git checkout -b left base &&
     -+	test_commit left &&
     -+	git checkout -b merge &&
     -+	git merge right -m "merge"
     -+'
     -+
     - test_expect_success 'git ahead-behind -h' '
     - 	test_must_fail git ahead-behind -h >out &&
     - 	grep "usage:" out
     -@@ t/t4218-ahead-behind.sh: test_expect_success 'git ahead-behind without --base' '
     - 	grep "usage:" err
     - '
     - 
     -+test_expect_success 'git ahead-behind with broken --base' '
     -+	test_must_fail git ahead-behind --base=bogus HEAD 2>err &&
     -+	grep "could not resolve '\''bogus'\''" err
     -+'
     -+
     - test_expect_success 'git ahead-behind with broken tip' '
     - 	test_must_fail git ahead-behind --base=HEAD bogus 2>err &&
     - 	grep "could not resolve '\''bogus'\''" err
     -@@ t/t4218-ahead-behind.sh: test_expect_success 'git ahead-behind without tips' '
     - 	test_must_be_empty err
     - '
     - 
     -+test_expect_success 'git ahead-behind --base=base' '
     -+	git ahead-behind --base=base base left right merge >actual &&
     -+
     -+	cat >expect <<-EOF &&
     -+	base 0 0
     -+	left 1 0
     -+	right 1 0
     -+	merge 3 0
     -+	EOF
     -+
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'git ahead-behind --base=left' '
     -+	git ahead-behind --base=left base left right merge >actual &&
     -+
     -+	cat >expect <<-EOF &&
     -+	base 0 1
     -+	left 0 0
     -+	right 1 1
     -+	merge 2 0
     -+	EOF
     -+
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'git ahead-behind --base=right' '
     -+	git ahead-behind --base=right base left right merge >actual &&
     -+
     -+	cat >expect <<-EOF &&
     -+	base 0 1
     -+	left 1 1
     -+	right 0 0
     -+	merge 2 0
     -+	EOF
     -+
     -+	test_cmp expect actual
     -+'
     -+
     -+test_expect_success 'git ahead-behind --base=merge' '
     -+	git ahead-behind --base=merge base left right merge >actual &&
     -+
     -+	cat >expect <<-EOF &&
     -+	base 0 3
     -+	left 0 2
     -+	right 0 2
     -+	merge 0 0
     -+	EOF
     -+
     -+	test_cmp expect actual
     -+'
     -+
     - test_done
     -
     - ## t/t6600-test-reach.sh ##
     -@@ t/t6600-test-reach.sh: test_expect_success 'get_reachable_subset:none' '
     - 	test_all_modes get_reachable_subset
     - '
     - 
     -+test_expect_success 'ahead-behind:linear' '
     -+	cat >input <<-\EOF &&
     -+	commit-1-1
     -+	commit-1-3
     -+	commit-1-5
     -+	commit-1-8
     -+	EOF
     -+	cat >expect <<-\EOF &&
     -+	commit-1-1 0 8
     -+	commit-1-3 0 6
     -+	commit-1-5 0 4
     -+	commit-1-8 0 1
     -+	EOF
     -+	run_all_modes git ahead-behind --base=commit-1-9 --stdin
     -+'
     -+
     -+test_expect_success 'ahead-behind:all' '
     -+	cat >input <<-\EOF &&
     -+	commit-1-1
     -+	commit-2-4
     -+	commit-4-2
     -+	commit-4-4
     -+	EOF
     -+	cat >expect <<-\EOF &&
     -+	commit-1-1 0 24
     -+	commit-2-4 0 17
     -+	commit-4-2 0 17
     -+	commit-4-4 0 9
     -+	EOF
     -+	run_all_modes git ahead-behind --base=commit-5-5 --stdin
     -+'
     -+
     -+test_expect_success 'ahead-behind:some' '
     -+	cat >input <<-\EOF &&
     -+	commit-1-1
     -+	commit-5-3
     -+	commit-4-8
     -+	commit-9-9
     -+	EOF
     -+	cat >expect <<-\EOF &&
     -+	commit-1-1 0 53
     -+	commit-5-3 0 39
     -+	commit-4-8 8 30
     -+	commit-9-9 27 0
     -+	EOF
     -+	run_all_modes git ahead-behind --base=commit-9-6 --stdin
     -+'
     -+
     -+test_expect_success 'ahead-behind:none' '
     -+	cat >input <<-\EOF &&
     -+	commit-7-5
     -+	commit-4-8
     -+	commit-9-9
     -+	EOF
     -+	cat >expect <<-\EOF &&
     -+	commit-7-5 7 4
     -+	commit-4-8 16 16
     -+	commit-9-9 49 0
     -+	EOF
     -+	run_all_modes git ahead-behind --base=commit-8-4 --stdin
     -+'
     -+
     - test_done
 -:  ----------- > 7:  82dd6f44a33 for-each-ref: add ahead-behind format atom
 8:  07eb2cbb699 ! 8:  f3fb6833bd7 ahead-behind: add --contains mode
     @@ Metadata
      Author: Derrick Stolee <[email protected]>
      
       ## Commit message ##
     -    ahead-behind: add --contains mode
     +    commit-reach: add tips_reachable_from_bases()
      
     -    The 'git ahead-behind' builtin can answer a list of questions that do
     -    not require the full ahead/behind counts. For example, instead of using
     -    'git branch --contains=<ref>' to get the full list of branches that
     -    contain the commit at <ref>, a list of tips could be passed to 'git
     -    ahead-behind --base=<ref>' and the rows that report a "behind" value of
     -    zero show which tips can reach <ref>.
     +    Both 'git for-each-ref --merged=<X>' and 'git branch --merged=<X>' use
     +    the ref-filter machinery to select references or branches (respectively)
     +    that are reachable from a set of commits presented by one or more
     +    --merged arguments. This happens within reach_filter(), which uses the
     +    revision-walk machinery to walk history in a standard way.
      
     -    By contract, the rows that report an "ahead" value of zero show which
     -    tips are reachable from the given base. This type of query does not have
     -    an existing equivalent for batching this request. While extracting the
     -    information from 'git ahead-behind' is not terribly difficult, it does
     -    more work than required to answer this query: it _counts_.
     +    However, the commit-reach.c file is full of custom searches that are
     +    more efficient, especially for reachability queries that can terminate
     +    early when reachability is discovered. Add a new
     +    tips_reachable_from_bases() method to commit-reach.c and call it from
     +    within reach_filter() in ref-filter.c. This affects both 'git branch'
     +    and 'git for-each-ref' as tested in p1500-graph-walks.sh.
      
     -    Add a new '--contains' mode to 'git ahead-behind' that removes the
     -    counting behavior and focuses instead on the reachability concern. The
     -    output of the builtin changes in this mode: instead of reporting "<tip>
     -    <ahead> <behind>" for every input tip, it will instead report "<tip>"
     -    for the input tips that are reachable from the specified base.
     +    For the Linux kernel repository, we take an already-fast algorithm and
     +    make it even faster:
     +
     +    Test                                            HEAD~1  HEAD
     +    -------------------------------------------------------------------
     +    1500.5: contains: git for-each-ref --merged     0.13    0.02 -84.6%
     +    1500.6: contains: git branch --merged           0.14    0.02 -85.7%
     +    1500.7: contains: git tag --merged              0.15    0.03 -80.0%
     +
     +    (Note that we remove the iterative 'git rev-list' test from p1500
     +    because it no longer makes sense as a comparison to 'git for-each-ref'
     +    and would just waste time running it for these comparisons.)
      
          The algorithm is implemented in commit-reach.c in the method
          tips_reachable_from_base(). This method takes a string_list of tips and
     @@ Commit message
          from the start, but we will walk only the necessary portion of the
          depth-first search for the reachable commits of lower generation.
      
     -    We can test this completely in the simple repo example in t4218 and more
     -    substantially in the larger repository example in t6600. We can also add
     -    a performance test to demonstrate the speedup relative to the 'git
     -    ahead-behind' builtin without the '--contains' option.
     -
     -    For the Git source code repository, I was able to measure a speedup,
     -    even though both are quite fast.
     -
     -    Test                                                       this tree
     -    --------------------------------------------------------------------------
     -    1500.2: ahead-behind counts: git ahead-behind              0.06(0.06+0.00)
     -    1500.3: ahead-behind counts: git rev-list                  1.08(0.90+0.18)
     -    1500.4: ahead-behind counts: git ahead-behind --contains   0.02(0.02+0.00)
     -
     -    In the Linux kernel repository, the impact is more pronounced:
     -
     -    Test                                                       this tree
     -    --------------------------------------------------------------------------
     -    1500.2: ahead-behind counts: git ahead-behind              0.26(0.25+0.01)
     -    1500.3: ahead-behind counts: git rev-list                  4.58(3.92+0.66)
     -    1500.4: ahead-behind counts: git ahead-behind --contains   0.02(0.00+0.02)
     +    Add extra tests for this behavior in t6600-test-reach.sh as the
     +    interesting data shape of that repository can sometimes demonstrate
     +    corner case bugs.
      
          Signed-off-by: Derrick Stolee <[email protected]>
      
     - ## Documentation/git-ahead-behind.txt ##
     -@@ Documentation/git-ahead-behind.txt: 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
     - -----------
     -@@ Documentation/git-ahead-behind.txt: 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
     - -------
     -@@ Documentation/git-ahead-behind.txt: 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
     -
     - ## builtin/ahead-behind.c ##
     -@@
     - #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
     - };
     - 
     -@@ builtin/ahead-behind.c: 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;
     -@@ builtin/ahead-behind.c: 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()
     - 	};
     - 
     -@@ builtin/ahead-behind.c: 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;
     - 
     -@@ builtin/ahead-behind.c: 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);
     - 
     -
       ## commit-reach.c ##
      @@ commit-reach.c: void ahead_behind(struct commit **commits, size_t commits_nr,
       	clear_bit_arrays(&bit_arrays);
     @@ commit-reach.c: void ahead_behind(struct commit **commits, size_t commits_nr,
      +	return 0;
      +}
      +
     -+void tips_reachable_from_base(struct commit *base,
     -+			      struct string_list *tips)
     ++void tips_reachable_from_bases(struct commit_list *bases,
     ++			       struct commit **tips, size_t tips_nr,
     ++			       int mark)
      +{
     -+	unsigned int i;
     ++	size_t 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)
     ++	if (!bases || !tips || !tips_nr)
      +		return;
      +
      +	/*
     -+	 * Do a depth-first search starting at 'base' to search for the
     ++	 * 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);
     ++	CALLOC_ARRAY(commits, tips_nr);
      +
     -+	for (i = 0; i < tips->nr; i++) {
     -+		commits[i].commit = lookup_commit_reference_by_name(tips->items[i].string);
     ++	for (i = 0; i < tips_nr; i++) {
     ++		commits[i].commit = tips[i];
      +		commits[i].index = i;
     -+		commits[i].generation = commit_graph_generation(commits[i].commit);
     ++		commits[i].generation = commit_graph_generation(tips[i]);
      +	}
      +
      +	/* Sort with generation number ascending. */
     -+	QSORT(commits, tips->nr, compare_commit_and_index_by_generation);
     ++	QSORT(commits, tips_nr, compare_commit_and_index_by_generation);
      +	min_generation = commits[0].generation;
      +
     -+	parse_commit(base);
     -+	commit_list_insert(base, &stack);
     ++	while (bases) {
     ++		parse_commit(bases->item);
     ++		commit_list_insert(bases->item, &stack);
     ++		bases = bases->next;
     ++	}
      +
      +	while (stack) {
      +		unsigned int j;
     @@ commit-reach.c: void ahead_behind(struct commit **commits, size_t commits_nr,
      +		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++) {
     ++		/* Does it match any of our tips? */
     ++		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;
     ++				tips[commits[j].index]->object.flags |= mark;
      +
      +				if (j == min_generation_index) {
      +					unsigned int k = j + 1;
     -+					while (k < tips->nr &&
     -+					       tips->items[commits[k].index].util)
     ++					while (k < tips_nr &&
     ++					       (tips[commits[k].index]->object.flags & mark))
      +						k++;
      +
      +					/* Terminate early if all found. */
     -+					if (k >= tips->nr)
     ++					if (k >= tips_nr)
      +						goto done;
      +
      +					min_generation_index = k;
     @@ commit-reach.h: struct ahead_behind_count {
       		  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?"
     ++ * 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_base(struct commit *base,
     -+			      struct string_list *tips);
     ++void tips_reachable_from_bases(struct commit_list *bases,
     ++			       struct commit **tips, size_t tips_nr,
     ++			       int mark);
      +
       #endif
      
     - ## t/perf/p1500-graph-walks.sh ##
     -@@ t/perf/p1500-graph-walks.sh: test_perf 'ahead-behind counts: git rev-list' '
     - 	done
     - '
     + ## ref-filter.c ##
     +@@ ref-filter.c: 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(check_reachable,
     ++				  to_clear, array->nr,
     ++				  UNINTERESTING);
     + 
     + 	old_nr = array->nr;
     + 	array->nr = 0;
     +@@ ref-filter.c: static void reach_filter(struct ref_array *array,
     + 		clear_commit_marks(merge_commit, ALL_REV_FLAGS);
     + 	}
     + 
     +-	release_revisions(&revs);
     + 	free(to_clear);
     + }
       
     -+test_perf 'ahead-behind counts: git ahead-behind --contains' '
     -+	git ahead-behind --contains --base=HEAD --stdin <refs
     -+'
     -+
     - test_done
      
     - ## t/t4218-ahead-behind.sh ##
     -@@ t/t4218-ahead-behind.sh: test_expect_success 'git ahead-behind with broken tip and --ignore-missing' '
     - 	test_must_be_empty out
     + ## t/perf/p1500-graph-walks.sh ##
     +@@ t/perf/p1500-graph-walks.sh: test_perf 'ahead-behind counts: git tag' '
     + 	xargs git tag -l --format="%(ahead-behind:HEAD)" <tags
       '
       
     -+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_perf 'ahead-behind counts: git rev-list' '
     +-	for r in $(cat refs)
     +-	do
     +-		git rev-list --count "HEAD..$r" || return 1
     +-	done
     ++test_perf 'contains: git for-each-ref --merged' '
     ++	git for-each-ref --merged=HEAD --stdin <refs
      +'
      +
     -+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_perf 'contains: git branch --merged' '
     ++	xargs git branch --merged=HEAD <branches
      +'
      +
     - test_expect_success 'git ahead-behind without tips' '
     - 	git ahead-behind --base=HEAD 2>err &&
     - 	test_must_be_empty err
     -@@ t/t4218-ahead-behind.sh: test_expect_success 'git ahead-behind --base=merge' '
     - 	test_cmp expect actual
     ++test_perf 'contains: git tag --merged' '
     ++	xargs git tag --merged=HEAD <tags
       '
       
     -+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
      
       ## t/t6600-test-reach.sh ##
     -@@ t/t6600-test-reach.sh: test_expect_success 'ahead-behind:none' '
     - 	run_all_modes git ahead-behind --base=commit-8-4 --stdin
     +@@ t/t6600-test-reach.sh: test_expect_success 'for-each-ref ahead-behind:none' '
     + 		--format="%(refname) %(ahead-behind:commit-8-4)" --stdin
       '
       
     -+test_expect_success 'ahead-behind--contains:all' '
     ++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 &&
     -+	commit-1-1
     -+	commit-2-4
     -+	commit-4-2
     -+	commit-4-4
     ++	refs/heads/commit-1-1
     ++	refs/heads/commit-2-4
     ++	refs/heads/commit-4-2
     ++	refs/heads/commit-4-4
      +	EOF
      +	cat >expect <<-\EOF &&
     -+	commit-1-1
     -+	commit-2-4
     -+	commit-4-2
     -+	commit-4-4
     ++	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 ahead-behind --contains --base=commit-5-5 \
     -+		--stdin --use-bitmap-index
     ++	run_all_modes git for-each-ref --merged=commit-5-5 \
     ++		--format="%(refname)" --stdin
      +'
      +
     -+test_expect_success 'ahead-behind--contains:some' '
     ++test_expect_success 'for-each-ref ahead-behind:some' '
      +	cat >input <<-\EOF &&
     -+	commit-1-1
     -+	commit-5-3
     -+	commit-4-8
     -+	commit-9-9
     ++	refs/heads/commit-1-1
     ++	refs/heads/commit-5-3
     ++	refs/heads/commit-4-8
     ++	refs/heads/commit-9-9
      +	EOF
      +	cat >expect <<-\EOF &&
     -+	commit-1-1
     -+	commit-5-3
     ++	refs/heads/commit-1-1
     ++	refs/heads/commit-5-3
      +	EOF
     -+	run_all_modes git ahead-behind --contains --base=commit-9-6 \
     -+		--stdin --use-bitmap-index
     ++	run_all_modes git for-each-ref --merged=commit-9-6 \
     ++		--format="%(refname)" --stdin
      +'
      +
     -+test_expect_success 'ahead-behind--contains:some, reordered' '
     ++test_expect_success 'for-each-ref merged:some, multibase' '
      +	cat >input <<-\EOF &&
     -+	commit-4-8
     -+	commit-5-3
     -+	commit-9-9
     -+	commit-1-1
     ++	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 &&
     -+	commit-5-3
     -+	commit-1-1
     ++	refs/heads/commit-1-1
     ++	refs/heads/commit-4-8
     ++	refs/heads/commit-5-3
      +	EOF
     -+	run_all_modes git ahead-behind --contains --base=commit-9-6 \
     -+		--stdin --use-bitmap-index
     ++	run_all_modes git for-each-ref \
     ++		--merged=commit-5-8 \
     ++		--merged=commit-8-5 \
     ++		--format="%(refname)" \
     ++		--stdin
      +'
      +
     -+test_expect_success 'ahead-behind--contains:none' '
     ++test_expect_success 'for-each-ref merged:none' '
      +	cat >input <<-\EOF &&
     -+	commit-7-5
     -+	commit-4-8
     -+	commit-9-9
     ++	refs/heads/commit-7-5
     ++	refs/heads/commit-4-8
     ++	refs/heads/commit-9-9
      +	EOF
      +	>expect &&
     -+	run_all_modes git ahead-behind --contains --base=commit-8-4 \
     -+		--stdin --use-bitmap-index
     ++	run_all_modes git for-each-ref --merged=commit-8-4 \
     ++		--format="%(refname)" --stdin
      +'
      +
       test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

When a user wishes to input a large list of patterns to 'git for-each-ref' (likely a long list of exact refs) there are frequently system limits on the number of command-line arguments.

Add a new --stdin option to instead read the patterns from standard input. Add tests that check that any unrecognized arguments are considered an error when --stdin is provided. Also, an empty pattern list is interpreted as the complete ref set.

When reading from stdin, we populate the filter.name_patterns array dynamically as opposed to pointing to the 'argv' array directly. This requires a careful cast while freeing the individual strings, conditioned on the --stdin option.

---
 Documentation/git-for-each-ref.txt |  7 +++++-
 builtin/for-each-ref.c             | 29 ++++++++++++++++++++++-
 t/t6300-for-each-ref.sh            | 37 ++++++++++++++++++++++++++++++
 3 files changed, 71 insertions(+), 2 deletions(-)

index 6da899c6296..ccdc2911bb9 100644
@@ -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

index 6f62f40d126..e005a7ef3ce 100644
@@ -25,6 +25,7 @@ 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 option opts[] = {
 		OPT_BIT('s', "shell", &format.quote_style,

@@ -49,6 +50,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,7 +77,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;
+		size_t nr = 0, alloc = 16;
+
+		if (argv[0])
+			die(_("unknown arguments supplied with --stdin"));
+
+		CALLOC_ARRAY(filter.name_patterns, alloc);
+
+		while (strbuf_getline(&line, stdin) != EOF) {
+			ALLOC_GROW(filter.name_patterns, nr + 1, alloc);
+			filter.name_patterns[nr++] = strbuf_detach(&line, NULL);
+		}
+
+		/* Add a terminating NULL string. */
+		ALLOC_GROW(filter.name_patterns, nr + 1, alloc);
+		filter.name_patterns[nr + 1] = NULL;
+	} else {
+		filter.name_patterns = argv;
+	}
+
 	filter.match_as_path = 1;
 	filter_refs(&array, &filter, FILTER_REFS_ALL);
 	ref_array_sort(sorting, &array);

@@ -97,5 +119,10 @@ 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);
+	if (from_stdin) {
+		for (size_t i = 0; filter.name_patterns[i]; i++)
+			free((char *)filter.name_patterns[i]);
+		free(filter.name_patterns);
+	}
 	return 0;
 }

index c466fd989f1..a58053a54c5 100755
@@ -1464,4 +1464,41 @@ 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_done

gitgitgadget

Indeed. Thanks for carefully describing the concerns you had.

Looking good. I'll read on.

Hi Stolee

I think what you've got here is fine, but if you wanted you could simplify it by using an strvec. Something like

	struct strvec vec = STRVEC_INIT;

	...

	if (from_stdin) {
		struct strbuf buf = STRBUF_INIT;

		if (argv[0])
			die(_("unknown arguments supplied with --stdin"));

		while (strbuf_getline(&line, stdin) != EOF)
			strvec_push(&vec, buf.buf);

		filter.name_patters = vec.v;
	} else {
		filter.name_patterns = argv;
	}

	...

	strvec_clear(&vec);

gets rid of the manual memory management with ALLOC_GROW() and the need to cast filter.name_patterns when free()ing. It is not immediately obvious from the name but struct strvec keeps the array NULL terminated.

Best Wishes

Phillip

Thanks, Philip. I like your version a lot and will use it in the next version.

-Stolee

Ditto. Thanks, both.

Thanks,
Taylor

Okey, and the current API assumes you just assign "argv" to this, but...

..sounds potentially nasty...

	diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
	index cf5ba6ffc12..13b75eff28c 100644
	--- a/builtin/for-each-ref.c
	+++ b/builtin/for-each-ref.c
	@@ -7,6 +7,7 @@
	 #include "parse-options.h"
	 #include "ref-filter.h"
	 #include "commit-reach.h"
	+#include "strvec.h"
	 
	 static char const * const for_each_ref_usage[] = {
	 	N_("git for-each-ref [<options>] [<pattern>]"),
	@@ -27,6 +28,7 @@ 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;
	+	struct strvec stdin_pat = STRVEC_INIT;
	 	int from_stdin = 0;
	 
	 	struct option opts[] = {
	@@ -81,21 +83,13 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
	 
	 	if (from_stdin) {
	 		struct strbuf line = STRBUF_INIT;
	-		size_t nr = 0, alloc = 16;
	 
	 		if (argv[0])
	 			die(_("unknown arguments supplied with --stdin"));
	 
	-		CALLOC_ARRAY(filter.name_patterns, alloc);
	-
	-		while (strbuf_getline(&line, stdin) != EOF) {
	-			ALLOC_GROW(filter.name_patterns, nr + 1, alloc);
	-			filter.name_patterns[nr++] = strbuf_detach(&line, NULL);
	-		}
	-
	-		/* Add a terminating NULL string. */
	-		ALLOC_GROW(filter.name_patterns, nr + 1, alloc);
	-		filter.name_patterns[nr + 1] = NULL;
	+		while (strbuf_getline(&line, stdin) != EOF)
	+			strvec_push(&stdin_pat, line.buf);
	+		filter.name_patterns = stdin_pat.v;
	 	} else {
	 		filter.name_patterns = argv;
	 	}
	@@ -123,10 +117,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);
	-	if (from_stdin) {
	-		for (size_t i = 0; filter.name_patterns[i]; i++)
	-			free(filter.name_patterns[i]);
	-		free(filter.name_patterns);
	-	}
	+	strvec_clear(&stdin_pat);
	 	return 0;
	 }

At first I thought you meant "extra allocation" here. But you really do mean an extra copy of the bytes.

The number of allocations is the same either way. In the original, we detach the strbuf in each iteration of the loop as it becomes the final entry in the array, but then have to allocate a new strbuf for the next iteration. With a strvec, we can reuse the same strbuf over and over, but make a new allocation when we add it to the strvec.

So yes, we end up with an extra memcpy() of the bytes. But the flip side is that the final allocations we store in the strvec are correctly sized, without the extra slop that the strbuf added while reading.

Yeah, I'd agree it is not important either way in this case. But I wanted to think it through above, just because it's not clear to me that even in a tight loop, the "allocate buffer and then attach to the strvec" approach would be the better tradeoff.

I guess it would make sense to wait for a case where it _does_ matter and then we could experiment with the two approaches. ;)

-Peff

This is a nice feature to have, but I suspect like other pattern features in Git (e.g., pathspecs), the matching is linear, and thus pre-expanding the set of refs you're interested in becomes accidentally quadratic.

And that seems to be the case here. If I have N refs and feed the whole set as patterns via --stdin:

-- >8 --
for i in 4000 8000 16000 32000; do
rm -rf repo
git init -q repo
(

    cd repo
    git commit --allow-empty -qm foo
    perl -e '
      my ($oid, $n) = @ARGV;
      print "create refs/heads/branch$_ $oid\n" for (1..$n);
    ' $(git rev-parse HEAD) $i |
    git update-ref --stdin
    git for-each-ref --format='%(refname)' >refs
    echo -n "$i: "
    command time -f %U \
      git.compile for-each-ref --stdin <refs 2>&1 >/dev/null

)
done
-- 8< --

then the result quadruples for every doubling of the refs.

4000: 0.32
8000: 1.33
16000: 5.10
32000: 20.90

That may or may not be a show-stopper for your use case, and if not, I don't think it's something we need to address immediately. But we may want some kind of "literal" mode, that takes in a list of refs rather than a list of patterns, and does a sorted-merge with the list of available refs (or uses a hash table, I guess, but for-each-ref also tries to avoid even being linear in the total number of refs, so you'd still want to find the lowest/highest to bound the iteration).

-Peff

Exactly.

I actually was wondering if "literal" mode can just take a list of <things>, and when a <thing> is not a refname, use it as if it were. I.e. %(refname) would parrot it, while %(refname:short) would not shorten and still parrot it, if the <thing> is 73876f4861c, but something like %(subject) would still work.

For that, I suspect ref-filter.c::filter_refs() would need to learn a different kind fo finter->kind that iterates over the literal "refs" that was fed from the standard input, instead of calling for_each_fullref_in() for the given hierarchy, but the new iterator should be able to reuse the ref_filter_hander() for the heavy lifting.

Yeah, I think that would nicely solve the quadratic issue _and_ the "we are stuck using only ref tips" issue. I like it.

Yeah, that sounds about right from my recollection of the code. I suspect there may be other sharp edges (e.g., asking for %(upstream) isn't meaningful for a non-ref). But softening those is actually something I think we want to do in the long run, as it helps with the long-term goal of sharing pretty-printing code between ref-filter, cat-file, and pretty.c.

-Peff

From: Derrick Stolee <[email protected]>

The for-each-ref builtin can take a list of ref patterns, but if none match, it still succeeds (but with no output). Add an explicit test that demonstrates that behavior.

---
 t/t6300-for-each-ref.sh | 13 +++++++++++++
 1 file changed, 13 insertions(+)

index a58053a54c5..6614469d2d6 100755
@@ -1501,4 +1501,17 @@ test_expect_success 'git for-each-ref --stdin: matches' '
 	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

gitgitgadget

From: Derrick Stolee <[email protected]>

This patch extracts the common code used to compute topological levels and corrected committer dates into a common routine, compute_reachable_generation_numbers_1().

This new routine dispatches to call the necessary functions to get and set the generation number for a given commit through a vtable (the compute_generation_info struct).

Computing the generation number itself is done in compute_generation_from_max(), which dispatches its implementation based on the generation version requested, or issuing a BUG() for unrecognized generation versions.

This patch cleans up the two places that currently compute topological levels and corrected commit dates by reducing the amount of duplicated code. It also makes it possible to introduce a function which dynamically computes those values for commits that aren't stored in a commit-graph, which will be required for the forthcoming ahead-behind rewrite.

---
 commit-graph.c | 171 +++++++++++++++++++++++++++++++------------------
 1 file changed, 107 insertions(+), 64 deletions(-)

index c11b59f28b3..deccf984a0d 100644
@@ -1446,24 +1446,53 @@ 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_1(
+			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;
+	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);
 
-		repo_parse_commit(ctx->r, c);
-		level = *topo_level_slab_at(ctx->topo_levels, c);
+		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);

@@ -1471,38 +1500,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;
+	display_progress(ctx->progress, ctx->progress_cnt + 1);
+}
+
+static void compute_topological_levels(struct write_commit_graph_context *ctx)
+{
+	struct compute_generation_info info = {
+		.r = ctx->r,
+		.progress = ctx->progress,
+		.commits = &ctx->commits,
+		.get_generation = get_topo_level,
+		.set_generation = set_topo_level,
+		.data = ctx,
+	};
+
+	if (ctx->report_progress)
+		ctx->progress = start_delayed_progress(
+					_("Computing commit graph topological levels"),
+					ctx->commits.nr);
+
+	compute_reachable_generation_numbers_1(&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 write_commit_graph_context *ctx = data;
+	struct commit_graph_data *g = commit_graph_data_at(c);
+	g->generation = (uint32_t)t;
+	display_progress(ctx->progress, ctx->progress_cnt + 1);
+}
+
 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,
+		.progress = ctx->progress,
+		.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(

@@ -1517,47 +1599,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_1(&info, 2);
 
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = ctx->commits.list[i];

@@ -1565,6 +1607,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX)
 			ctx->num_generation_data_overflows++;
 	}
+
 	stop_progress(&ctx->progress);
 }
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The commit_graph_generation() method used to report a value of GENERATION_NUMBER_INFINITY if the commit_graph_data_slab had an instance for the given commit but the graph_pos indicated the commit was not in the commit-graph file.

Instead, trust the 'generation' member if the commit has a value in the slab _and_ the 'generation' member is non-zero. Otherwise, treat it as GENERATION_NUMBER_INFINITY.

This only makes a difference for a very old case for the commit-graph:
the very first Git release to write commit-graph files wrote zeroes in the topological level positions. If we are parsing a commit-graph with all zeroes, those commits will now appear to have GENERATION_NUMBER_INFINITY (as if they were not parsed from the commit-graph).

I attempted several variations to work around the need for providing an uninitialized 'generation' member, but this was the best one I found. It does require a change to a verification test in t5318 because it reports a different error than the one about non-zero generation numbers.

---
 commit-graph.c          | 8 +++-----
 t/t5318-commit-graph.sh | 2 +-
 2 files changed, 4 insertions(+), 6 deletions(-)

index deccf984a0d..b4da4e05067 100644
@@ -116,12 +116,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)

index 049c5fc8ead..b6e12115786 100755
@@ -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' '

gitgitgadget

From: Taylor Blau <[email protected]>

Use the just-introduced compute_reachable_generation_numbers_1() to implement a function which dynamically computes topological levels (or corrected commit dates) for out-of-graph commits.

This will be useful for the ahead-behind algorithm we are about to introduce, which needs accurate topological levels on _all_ commits reachable from the tips in order to avoid over-counting.

---
 commit-graph.c | 29 +++++++++++++++++++++++++++++
 commit-graph.h |  7 +++++++
 2 files changed, 36 insertions(+)

index b4da4e05067..7311d62a110 100644
@@ -1609,6 +1609,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 commit **commits, size_t nr)
+{
+	struct repository *r = the_repository;
+	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_1(&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",

index 37faee6b66d..a529c62b518 100644
@@ -190,4 +190,11 @@ 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 commit **commits, size_t nr);
+
 #endif

gitgitgadget

From: Derrick Stolee <[email protected]>

Fully implement the commit-counting logic required to determine ahead/behind counts for a batch of commit pairs. This is a new library method within commit-reach.h. This method will be linked to the for-each-ref builtin in the next change.

The interface for ahead_behind() uses two arrays. The first array of commits contains the list of all starting points for the walk. This includes all tip commits _and_ base commits. The second array, using the new ahead_behind_count struct, indicates which commits from that initial array form the base/tip pair for the ahead/behind count it will store.

This implementation of ahead_behind() allows multiple bases, if desired. Even with multiple bases, there is only one commit walk used for counting the ahead/behind values, saving time when the base/tip ranges overlap significantly.

This interface for ahead_behind() also makes it very easy to call ensure_generations_valid() on the entire array of bases and tips. This call is necessary because it is critical that the walk that counts ahead/behind values never walks a commit more than once. Without generation numbers on every commit, there is a possibility that a commit date skew could cause the walk to revisit a commit and then double-count it. For this reason, it is strongly recommended that 'git ahead-behind' is only run in a repository with a commit-graph file that covers most of the reachable commits, storing precomputed generation numbers. If no commit-graph exists, this walk will be much slower as it must walk all reachable commits in ensure_generations_valid() before performing the counting logic.

It is possible to detect if generation numbers are available at run time and redirect the implementation to another algorithm that does not require this property. However, that implementation requires a commit walk per base/tip pair _and_ can be slower due to the commit date heuristics required. Such an implementation could be considered in the future if there is a reason to include it, but most Git hosts should already be generating a commit-graph file as part of repository maintenance. Most Git clients should also be generating commit-graph files as part of background maintenance or automatic GCs.

Now, let's discuss the ahead/behind counting algorithm.

Each commit in the input commit list is associated with a bit position indicating "the ith commit can reach this commit". Each of these commits is associated with a bitmap with its position flipped on and then placed in a queue for walking commit history. We walk commits by popping the commit with maximum generation number out of the queue, guaranteeing that we will never walk a child of that commit in any future steps.

As we walk, we load the bitmap for the current commit and perform two main steps. The _second_ step examines each parent of the current commit and adds the current commit's bitmap bits to each parent's bitmap. (We create a new bitmap for the parent if this is our first time seeing that parent.) After adding the bits to the parent's bitmap, the parent is added to the walk queue. Due to this passing of bits to parents, the current commit has a guarantee that the ith bit is enabled on its bitmap if and only if the ith commit can reach the current commit.

The first step of the walk is to examine the bitmask on the current commit and decide which ranges the commit is in or not. Due to the "bit pushing" in the second step, we have a guarantee that the ith bit of the current commit's bitmap is on if and only if the ith starting commit can reach it. For each ahead_behind_count struct, check the base_index and tip_index to see if those bits are enabled on the current bitmap. If exactly one bit is enabled, then increment the corresponding 'ahead' or 'behind' count. This increment is the reason we _absolutely need_ to walk commits at most once.

The only subtle thing to do with this walk is to check to see if a parent has all bits on in its bitmap, in which case it becomes "stale" and is marked with the STALE bit. This allows queue_has_nonstale() to be the terminating condition of the walk, which greatly reduces the number of commits walked if all of the commits are nearby in history. It avoids walking a large number of common commits when there is a deep history. We also use the helper method insert_no_dup() to add commits to the priority queue without adding them multiple times. This uses the PARENT2 flag. Thus, we must clear both the STALE and PARENT2 bits of all commits, in case ahead_behind() is called multiple times in the same process.

---
 commit-reach.c | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++
 commit-reach.h | 30 ++++++++++++++++
 2 files changed, 126 insertions(+)

index 2e33c599a82..338ca8084b2 100644
@@ -8,6 +8,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)

@@ -941,3 +942,98 @@ 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 *init_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 commit **commits, size_t commits_nr,
+		  struct ahead_behind_count *counts, size_t counts_nr)
+{
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+	size_t width = (commits_nr + BITS_IN_EWORD - 1) / BITS_IN_EWORD;
+	size_t i;
+
+	if (!commits_nr || !counts_nr)
+		return;
+
+	for (i = 0; i < counts_nr; i++) {
+		counts[i].ahead = 0;
+		counts[i].behind = 0;
+	}
+
+	ensure_generations_valid(commits, commits_nr);
+
+	init_bit_arrays(&bit_arrays);
+
+	for (i = 0; i < commits_nr; i++) {
+		struct commit *c = commits[i];
+		struct bitmap *bitmap = init_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 = init_bit_array(c, width);
+
+		for (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;
+
+			parse_commit(p->item);
+
+			bitmap_p = init_bit_array(p->item, width);
+			bitmap_or(bitmap_p, bitmap_c);
+
+			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(the_repository, PARENT2 | STALE);
+	clear_bit_arrays(&bit_arrays);
+	clear_prio_queue(&queue);
+}

index 148b56fea50..f871b5dcce9 100644
@@ -104,4 +104,34 @@ 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 commit **commits, size_t commits_nr,
+		  struct ahead_behind_count *counts, size_t counts_nr);
+
 #endif

gitgitgadget

I personally do not see a point in becoming so dogmatic. Plain (possibly) 32-bit integers have their places in the code.

In particular, we have 32-bit limits on the commit-graph due to it being unreasonable to have billions of commits in a repository.

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

The previous change implemented the ahead_behind() method, including an algorithm to compute the ahead/behind values for a number of commit tips relative to a number of commit bases. Now, integrate that algorithm as part of 'git for-each-ref' hidden behind a new format atom, ahead-behind. This naturally extends to 'git branch' and 'git tag' builtins, as well.

This format allows specifying multiple bases, if so desired, and all matching references are compared against all of those bases. For this reason, failing to read a reference provided from these atoms results in an error.

In order to translate the ahead_behind() method information to the format output code in ref-filter.c, we must populate arrays of ahead_behind_count structs. In struct ref_array, we store the full array that will be passed to ahead_behind(). In struct ref_array_item, we store an array of pointers that point to the relvant items within the full array. In this way, we can pull all relevant ahead/behind values directly when formatting output for a specific item. It also ensures the lifetime of the ahead_behind_count structs matches the time that the array is being used.

Add specific tests of the ahead/behind counts in t6600-test-reach.sh, as it has an interesting repository shape. In particular, its merging strategy and its use of different commit-graphs would demonstrate over- counting if the ahead_behind() method did not already account for that possibility.

Also add tests for the specific for-each-ref, branch, and tag builtins. In the case of 'git tag', there are intersting cases that happen when some of the selected tips are not commits. This requires careful logic around commits_nr in the second loop of filter_ahead_behind(). Also, the test in t7004 is carefully located to avoid being dependent on the GPG prereq. It also avoids using the test_commit helper, as that will add ticks to the time and disrupt the expected timestampes in later tag tests.

Also add performance tests in a new p1300-graph-walks.sh script. This will be useful for more uses in the future, but for now compare the ahead-behind counting algorithm in 'git for-each-ref' to the naive implementation by running 'git rev-list --count' processes for each input.

For the Git source code repository, the improvement is already obvious:

Test this tree
---------------------------------------------------------------

1500.2: ahead-behind counts: git for-each-ref   0.07(0.07+0.00)
1500.3: ahead-behind counts: git branch         0.07(0.06+0.00)
1500.4: ahead-behind counts: git tag            0.07(0.06+0.00)
1500.5: ahead-behind counts: git rev-list       1.32(1.04+0.27)

But the standard performance benchmark is the Linux kernel repository, which demosntrates a significant improvement:

Test this tree
---------------------------------------------------------------

1500.2: ahead-behind counts: git for-each-ref   0.27(0.24+0.02)
1500.3: ahead-behind counts: git branch         0.27(0.24+0.03)
1500.4: ahead-behind counts: git tag            0.28(0.27+0.01)
1500.5: ahead-behind counts: git rev-list       4.57(4.03+0.54)

The 'git rev-list' test exists in this change as a demonstration, but it will be removed in the next change to avoid wasting time on this comparison.

---
 Documentation/git-for-each-ref.txt |  5 ++
 builtin/branch.c                   |  1 +
 builtin/for-each-ref.c             |  3 ++
 builtin/tag.c                      |  1 +
 ref-filter.c                       | 70 ++++++++++++++++++++++++
 ref-filter.h                       | 25 ++++++++-
 t/perf/p1500-graph-walks.sh        | 45 ++++++++++++++++
 t/t3203-branch-output.sh           | 14 +++++
 t/t6301-for-each-ref-errors.sh     | 12 +++++
 t/t6600-test-reach.sh              | 86 ++++++++++++++++++++++++++++++
 t/t7004-tag.sh                     | 28 ++++++++++
 11 files changed, 289 insertions(+), 1 deletion(-)
 create mode 100755 t/perf/p1500-graph-walks.sh

index ccdc2911bb9..d5c3cda4228 100644
@@ -222,6 +222,11 @@ worktreepath::
 	out, if it is checked out in any linked worktree. Empty string
 	otherwise.
 
+ahead-behind:<ref>::
+	Two integers, separated by a space, demonstrating the number of
+	commits ahead and behind, respectively, when comparing the output
+	ref to the `<ref>` 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.

index f63fd45edb9..d46ca6147e3 100644
@@ -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(format, &array);
 	ref_array_sort(sorting, &array);
 
 	for (i = 0; i < array.nr; i++) {

index e005a7ef3ce..08945ad6802 100644
@@ -5,6 +5,7 @@
 #include "object.h"
 #include "parse-options.h"
 #include "ref-filter.h"
+#include "commit-reach.h"
 
 static char const * const for_each_ref_usage[] = {
 	N_("git for-each-ref [<options>] [<pattern>]"),

@@ -100,6 +101,8 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 
 	filter.match_as_path = 1;
 	filter_refs(&array, &filter, FILTER_REFS_ALL);
+	filter_ahead_behind(&format, &array);
+
 	ref_array_sort(sorting, &array);
 
 	if (!maxcount || array.nr < maxcount)

index d428c45dc8d..4f203a4ad21 100644
@@ -66,6 +66,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(format, &array);
 	ref_array_sort(sorting, &array);
 
 	for (i = 0; i < array.nr; i++) {

index aa0eea4ecf5..7e8bff3864e 100644
@@ -5,6 +5,7 @@
 #include "refs.h"
 #include "commit.h"
 #include "parse-options.h"
+#include "string-list.h"
 
 /* Quoting styles */
 #define QUOTE_NONE 0

@@ -24,6 +25,7 @@
 
 struct atom_value;
 struct ref_sorting;
+struct ahead_behind_count;
 
 enum ref_sorting_order {
 	REF_SORTING_REVERSE = 1<<0,

@@ -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,14 @@ 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 ref_format *format,
+			 struct ref_array *array);
+
 #endif /*  REF_FILTER_H  */

index d34d77f8934..1c0f7ea24e7 100755
@@ -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
 '

index bfda1f46ad2..7db1fc4d7b3 100755
@@ -54,4 +54,16 @@ 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 &&
+	grep "expected format: %(ahead-behind:<ref>)" err
+'
+
+test_expect_success 'missing ahead-behind base' '
+	test_must_fail git for-each-ref \
+		--format="%(ahead-behind:refs/heads/missing)" 2>err &&
+	grep "failed to find '\''refs/heads/missing'\''" err
+'
+
 test_done

index 9aa1660651b..d099e707efd 100755
@@ -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 whitepsace
+	# 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 \

gitgitgadget

Nice.