Re: [PATCH 6/6] refs/reftable: wire up support for exclude patterns

> hidden refs. The following benchmark prints one reference with 1 million
> hidden references:
>
>     Benchmark 1: HEAD~
>       Time (mean ± σ):      93.3 ms ±   2.1 ms    [User: 90.3 ms, System: 2.5 ms]
>       Range (min … max):    89.8 ms …  97.2 ms    33 runs
>
>     Benchmark 2: HEAD
>       Time (mean ± σ):       4.2 ms ±   0.6 ms    [User: 2.2 ms, System: 1.8 ms]
>       Range (min … max):     3.1 ms …   8.1 ms    765 runs
>
>     Summary
>       HEAD ran
>        22.15 ± 3.19 times faster than HEAD~
>

> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
>  refs/reftable-backend.c | 125 +++++++++++++++++++++++++++++++++++++++-
>  t/t1419-exclude-refs.sh |  33 ++++++++---
>  trace2.h                |   1 +
>  trace2/tr2_ctr.c        |   5 ++
>  4 files changed, 152 insertions(+), 12 deletions(-)
>
> diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c
> index 1c4b19e737f..5c241097a4e 100644
> --- a/refs/reftable-backend.c
> +++ b/refs/reftable-backend.c
> @@ -21,6 +21,7 @@
>  #include "../reftable/reftable-iterator.h"
>  #include "../setup.h"
>  #include "../strmap.h"
> +#include "../trace2.h"
>  #include "parse.h"
>  #include "refs-internal.h"
>
> @@ -447,10 +448,81 @@ struct reftable_ref_iterator {
>
>  	const char *prefix;
>  	size_t prefix_len;
> +	char **exclude_patterns;
> +	size_t exclude_patterns_index;
> +	size_t exclude_patterns_strlen;
>  	unsigned int flags;
>  	int err;
>  };
>
> +/*
> + * Handle exclude patterns. Returns either `1`, which tells the caller that the
> + * current reference shall not be shown. Or `0`, which indicates that it should
> + * be shown.
> + */
> +static int should_exclude_current_ref(struct reftable_ref_iterator *iter)
> +{
> +	while (iter->exclude_patterns[iter->exclude_patterns_index]) {
> +		const char *pattern = iter->exclude_patterns[iter->exclude_patterns_index];
> +		char *ref_after_pattern;
> +		int cmp;
> +
> +		/*
> +		 * Lazily cache the pattern length so that we don't have to
> +		 * recompute it every time this function is called.
> +		 */
> +		if (!iter->exclude_patterns_strlen)
> +			iter->exclude_patterns_strlen = strlen(pattern);
> +
> +		/*
> +		 * When the reference name is lexicographically bigger than the
> +		 * current exclude pattern we know that it won't ever match any
> +		 * of the following references, either. We thus advance to the
> +		 * next pattern and re-check whether it matches.

> +		 * Otherwise, if it's smaller, then we do not have a match and
> +		 * thus want to show the current reference.
> +		 */
> +		cmp = strncmp(iter->ref.refname, pattern,
> +			      iter->exclude_patterns_strlen);
> +		if (cmp > 0) {
> +			iter->exclude_patterns_index++;
> +			iter->exclude_patterns_strlen = 0;
> +			continue;
> +		}
> +		if (cmp < 0)
> +			return 0;
> +
> +		/*
> +		 * The reference shares a prefix with the exclude pattern and
> +		 * shall thus be omitted. We skip all references that match the
> +		 * pattern by seeking to the first reference after the block of
> +		 * matches.
> +		 *
> +		 * This is done by appending the highest possible character to
> +		 * the pattern. Consequently, all references that have the
> +		 * pattern as prefix and whose suffix starts with anything in
> +		 * the range [0x00, 0xfe] are skipped. And given that 0xff is a
> +		 * non-printable character that shouldn't ever be in a ref name,
> +		 * we'd not yield any such record, either.
> +		 *

> +		ref_after_pattern = xstrfmt("%s%c", pattern, 0xff);
> +		iter->err = reftable_iterator_seek_ref(&iter->iter, ref_after_pattern);
> +		iter->exclude_patterns_index++;
> +		iter->exclude_patterns_strlen = 0;
> +		trace2_counter_add(TRACE2_COUNTER_ID_REFTABLE_RESEEKS, 1);
> +
> +		free(ref_after_pattern);
> +		return 1;
> +	}
> +
> +	return 0;
> +}
> +
>  static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)
>  {
>  	struct reftable_ref_iterator *iter =
> @@ -481,6 +553,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)
>  			break;
>  		}
>
> +		if (iter->exclude_patterns && should_exclude_current_ref(iter))
> +			continue;
> +
>  		if (iter->flags & DO_FOR_EACH_PER_WORKTREE_ONLY &&
>  		    parse_worktree_ref(iter->ref.refname, NULL, NULL, NULL) !=
>  			    REF_WORKTREE_CURRENT)
> @@ -570,6 +645,11 @@ static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator)
>  		(struct reftable_ref_iterator *)ref_iterator;
>  	reftable_ref_record_release(&iter->ref);
>  	reftable_iterator_destroy(&iter->iter);
> +	if (iter->exclude_patterns) {
> +		for (size_t i = 0; iter->exclude_patterns[i]; i++)
> +			free(iter->exclude_patterns[i]);
> +		free(iter->exclude_patterns);
> +	}
>  	free(iter);
>  	return ITER_DONE;
>  }
> @@ -580,9 +660,45 @@ static struct ref_iterator_vtable reftable_ref_iterator_vtable = {
>  	.abort = reftable_ref_iterator_abort
>  };
>
> +static char **filter_exclude_patterns(const char **exclude_patterns)
> +{
> +	size_t filtered_size = 0, filtered_alloc = 0;
> +	char **filtered = NULL;
> +
> +	if (!exclude_patterns)
> +		return NULL;
> +
> +	for (size_t i = 0; ; i++) {
> +		const char *exclude_pattern = exclude_patterns[i];
> +		int has_glob = 0;
> +
> +		if (!exclude_pattern)
> +			break;
> +
> +		for (const char *p = exclude_pattern; *p; p++) {
> +			has_glob = is_glob_special(*p);
> +			if (has_glob)
> +				break;
> +		}