Filter combination

The next patch will create and manage filters in a new way, which means that this bundle of data will have to be managed at a new callsite. Make this bundle of data more manageable by putting it in a struct and making it part of the list-objects-filter module's API.

list-objects-filter.c +1 -3

-static void *filter_blobs_none__init(
-	struct oidset *omitted,
+static void filter_blobs_none__init(
 	struct list_objects_filter_options *filter_options,
-	filter_object_fn *filter_fn,

}

};

This commit message might read more easily on its own if you define "this bundle of data" at least once. Since there are things being moved from both list-objects-filter.c (filter_blobs_none_data) and list-objects-filter.h (list_objects_filter_result and filter_free_fn) into the new struct in list-objects-filter.h, it's not immediately clear to me from the diff what's going on.

Quoted 11 lines

list-objects-filter.c +2 -7

-static void *filter_blobs_none__init(
-	struct oidset *omitted,
+static void filter_blobs_none__init(
 	struct list_objects_filter_options *filter_options,
-	filter_object_fn *filter_fn,
-	filter_free_fn *filter_free_fn)
+	struct filter_context *ctx)
 {
-	struct filter_blobs_none_data *d = xcalloc(1, sizeof(*d));
-	d->omits = omitted;
-

list-objects-filter.c line 64

Quoted 4 lines

list-objects-filter.c +1 -3

-	*filter_fn = filter_blobs_none;
-	*filter_free_fn = free;
-	return d;
+	ctx->filter_fn = filter_blobs_none;

I think you want to set ctx->free_fn here too, right? It seems like you're not setting ctx->omitted anymore because you'd be reading that information in from ctx->omitted (so it's redundant).

Simplify the filter execution data logic and structs by putting all execution data for all filter types in a single struct. This results in a tiny overhead for each filter instance, and in exchange, invoking filters is not only easier but the list-objects-filter public API is simpler and more opaque.

list-objects-filter.c +27 -0

+struct filter_data {
+	/* Used by all filter types. */
 	struct oidset *omits;
+
+	enum list_objects_filter_result (*filter_object_fn)(
+		struct repository *r,
+		enum list_objects_filter_situation filter_situation,
+		struct object *obj,
+		const char *pathname,
+		const char *filename,
+		struct filter_data *filter_data);
+
+	/* BEGIN tree:<depth> filter data */
+
+	/*
+	 * Maps trees to the minimum depth at which they were seen. It is not
+	 * necessary to re-traverse a tree at deeper or equal depths than it has
+	 * already been traversed.
+	 *
+	 * We can't use LOFR_MARK_SEEN for tree objects since this will prevent
+	 * it from being traversed at shallower depths.
+	 */
+	struct oidmap seen_at_depth;
+
+	unsigned long exclude_depth;
+	unsigned long current_depth;
+
+	/* BEGIN blobs:limit=<limit> filter data */

Quoted 5 lines · Matthew DeVore

Simplify the filter execution data logic and structs by putting all execution data for all filter types in a single struct. This results in a tiny overhead for each filter instance, and in exchange, invoking filters is not only easier but the list-objects-filter public API is simpler and more opaque.

Hmmm...

Quoted 28 lines

list-objects-filter.c +27 -0

+struct filter_data {
+	/* Used by all filter types. */
  	struct oidset *omits;
+
+	enum list_objects_filter_result (*filter_object_fn)(
+		struct repository *r,
+		enum list_objects_filter_situation filter_situation,
+		struct object *obj,
+		const char *pathname,
+		const char *filename,
+		struct filter_data *filter_data);
+
+	/* BEGIN tree:<depth> filter data */
+
+	/*
+	 * Maps trees to the minimum depth at which they were seen. It is not
+	 * necessary to re-traverse a tree at deeper or equal depths than it has
+	 * already been traversed.
+	 *
+	 * We can't use LOFR_MARK_SEEN for tree objects since this will prevent
+	 * it from being traversed at shallower depths.
+	 */
+	struct oidmap seen_at_depth;
+
+	unsigned long exclude_depth;
+	unsigned long current_depth;
+
+	/* BEGIN blobs:limit=<limit> filter data */

list-objects-filter.c line 66

Quoted 10 lines

list-objects-filter.c +9 -0

+
+	unsigned long max_bytes;
+
+	/* BEGIN sparse:... filter data */
+
+	struct exclude_list el;
+
+	size_t nr, alloc;
+	struct frame *array_frame;
  };

I am hoping that I am not misreading the intention but you do not plan to use the above so that you can say "apply 'tree:depth=4' and 'blobs:limit=1G' at the same time" by filling the fields in a single struct, do you? For combined filter, you'll still have multiple instances of filter_data struct, strung together in a list that says "all of these must be satisfied" or something like that, right?

And if that is the case, I am not sure why the above "struct with all these fields" is a good idea. If these three (and probably we will have more as the system evolves) sets of fields in this outer struct for different filters were enclosed in a union, that would be a different story, though.

Quoted 6 lines

I am hoping that I am not misreading the intention but you do not plan to use the above so that you can say "apply 'tree:depth=4' and 'blobs:limit=1G' at the same time" by filling the fields in a single struct, do you? For combined filter, you'll still have multiple instances of filter_data struct, strung together in a list that says "all of these must be satisfied" or something like that, right?

I'm not sure I like the combined structure as proposed. But let's think about it.

I think part of problem with my original version was putting the filter_fn and filter_free_fn in the traversal_context rather than inside the filter_*_data structure.

I did a simple combined structure for the list_objects_filter_options and kind of regretted it because it wasn't obvious which data fields were defined or undefined in each filter constructor. But it was convenient when parsing the command line.

I think having a combined structure with a union enclosing a structure for the data fields in each filter type would be worth considering. That way you have a somewhat self-documenting sub-structure for each filter type that indicates which fields are defined.

I'd also suggest keeping the "oidset omits" inside each of the sub-structures, but that's just me.

BTW, I don't see a free_fn. That may collapse out with your proposal but I wanted to ask.

list-objects-filter.c +20 -0

+struct filter_data {
+	/* Used by all filter types. */
 	struct oidset *omits;
+
+	enum list_objects_filter_result (*filter_object_fn)(
+		struct repository *r,
+		enum list_objects_filter_situation filter_situation,
+		struct object *obj,
+		const char *pathname,
+		const char *filename,
+		struct filter_data *filter_data);
+
+	void (*filter_clear_fn)(struct filter_data *filter_data);
+
+	union {
+		struct {
+			/*
+			 * Maps trees to the minimum depth at which they were
+			 * seen. It is not necessary to re-traverse a tree at
+			 * deeper or equal depths than it has already been
+			 * traversed.

list-objects-filter.c +11 -0

+		struct {
+			unsigned long max_bytes;
+		};
+
+		struct {
+			struct exclude_list el;
+
+			size_t nr, alloc;
+			struct frame *array_frame;
+		};
+	};
 };

Review

Quoted 2 lines

(quoted diff) +2 -0

+	union {
+		struct {

Name this, and the ohter two union members, and the union itself as one member inside the outer struct; some compilers would be unhappy with the GCC extension that allows you to refer to the member in this struct as ((struct filter_data *)p)->seen_at_depth, no?

I'd also suggest keeping the "oidset omits" inside each of the sub-structures, but that's just me.

The "invalid filter-spec" message is user-facing and not a BUG, so make it localizeable.

Signed-off-by Matthew DeVore <[email protected]>

---
 list-objects-filter-options.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

list-objects-filter-options.c +1 -1

index c0036f7378..e46ea467bc 100644
@@ -81,21 +81,21 @@ static int gently_parse_list_objects_filter(
 		filter_options->choice = LOFC_SPARSE_PATH;
 		filter_options->sparse_path_value = strdup(v0);
 		return 0;
 	}
 	/*
 	 * Please update _git_fetch() in git-completion.bash when you
 	 * add new filters
 	 */
 
 	if (errbuf)
-		strbuf_addf(errbuf, "invalid filter-spec '%s'", arg);
+		strbuf_addf(errbuf, _("invalid filter-spec '%s'"), arg);
 
 	memset(filter_options, 0, sizeof(*filter_options));
 	return 1;
 }
 
 int parse_list_objects_filter(struct list_objects_filter_options *filter_options,
 			      const char *arg)
 {
 	struct strbuf buf = STRBUF_INIT;
 	if (gently_parse_list_objects_filter(filter_options, arg, &buf))

Signature · 1 line

2.21.0

What does it look like? Is it human-readable in its current form? I ask because (without having looked ahead) I think you're going to move it

Allow combining filters such that only objects accepted by all filters are shown. The motivation for this is to allow getting directory listings without also fetching blobs. This can be done by combining blob:none with tree:<depth>. There are massive repositories that have larger-than-expected trees - even if you include only a single commit.

The current usage requires passing the filter to rev-list, or sending it over the wire, as:

	combine:<FILTER1>+<FILTER2>

Only objects which are accepted by every filter are

Documentation/rev-list-options.txt +5 -0

+included. Filters are joined by '{plus}' and individual filters are %-encoded
+(i.e. URL-encoded). Besides the '{plus}' and '%' characters, the following
+characters are reserved and also must be encoded:
+`~!@#$^&*()[]{}\;",<>?`+&#39;&#96;+ as well as all characters with ASCII code
+&lt;= `0x20`, which includes space and newline.

list-objects-filter.c +59 -0

index 8e8616b9b8..b97277a46f 100644
@@ -453,34 +453,148 @@ static void filter_sparse_path__init(
 
  	ALLOC_GROW(d->array_frame, d->nr + 1, d->alloc);
  	d->array_frame[d->nr].defval = 0; /* default to include */
  	d->array_frame[d->nr].child_prov_omit = 0;
 
  	ctx->filter_fn = filter_sparse;
  	ctx->free_fn = filter_sparse_free;
  	ctx->data = d;
  }
 
+struct filter_combine_data {
+	/* sub[0] corresponds to lhs, sub[1] to rhs. */
+	struct {
+		struct filter_context ctx;
+		struct oidset seen;
+		struct object_id skip_tree;
+		unsigned is_skipping_tree : 1;
+	} sub[2];
+
+	struct oidset rhs_omits;
+};
+
+static void add_all(struct oidset *dest, struct oidset *src) {
+	struct oidset_iter iter;
+	struct object_id *src_oid;
+
+	oidset_iter_init(src, &iter);
+	while ((src_oid = oidset_iter_next(&iter)) != NULL)
+		oidset_insert(dest, src_oid);
+}
+
+static void filter_combine_free(void *filter_data)
+{
+	struct filter_combine_data *d = filter_data;
+	int i;
+
+	/* Anything omitted by rhs should be added to the overall omits set. */
+	if (d->sub[0].ctx.omits)
+		add_all(d->sub[0].ctx.omits, d->sub[1].ctx.omits);
+
+	for (i = 0; i < 2; i++) {
+		list_objects_filter__release(&d->sub[i].ctx);
+		oidset_clear(&d->sub[i].seen);
+	}
+	oidset_clear(&d->rhs_omits);
+	free(d);
+}
+
+static int should_delegate(enum list_objects_filter_situation filter_situation,
+			   struct object *obj,
+			   struct filter_combine_data *d,
+			   int side)
+{
+	if (!d->sub[side].is_skipping_tree)
+		return 1;
+	if (filter_situation == LOFS_END_TREE &&
+		oideq(&obj->oid, &d->sub[side].skip_tree)) {
+		d->sub[side].is_skipping_tree = 0;
+		return 1;
+	}
+	return 0;
+}
+
+static enum list_objects_filter_result filter_combine(
+	struct repository *r,
+	enum list_objects_filter_situation filter_situation,
+	struct object *obj,
+	const char *pathname,
+	const char *filename,

In the RFC version, there was discussion [2] of the wire format and the need to be backwards compatible with existing servers and so use the "combine:" syntax so that we only have a single filter line on the wire. Would it be better to have compliant servers advertise a "filters" (plural) capability in addition to the existing "filter" (singular) capability? Then the client would know that it could send a series of filter lines using the existing syntax. Likewise, if the "filters" capability was omitted, the client could error out without the extra round-trip.

Quoted 5 lines · Jeff Hostetler

In the RFC version, there was discussion [2] of the wire format and the need to be backwards compatible with existing servers and so use the "combine:" syntax so that we only have a single filter line on the wire. Would it be better to have compliant servers advertise a "filters" (plural) capability in addition to the

Quoted 4 lines

existing "filter" (singular) capability? Then the client would know that it could send a series of filter lines using the existing syntax. Likewise, if the "filters" capability was omitted, the client could error out without the extra round-trip.

All good ideas.

Quoted 7 lines · Junio C Hamano

Quoted 5 lines · Jeff Hostetler

In the RFC version, there was discussion [2] of the wire format and the need to be backwards compatible with existing servers and so use the "combine:" syntax so that we only have a single filter line on the wire. Would it be better to have compliant servers advertise a "filters" (plural) capability in addition to the

This is a good idea and I hadn't considered it. It does seem to make the repeated filter lines a safer bet than I though.

Quoted 6 lines

Quoted 4 lines

existing "filter" (singular) capability? Then the client would know that it could send a series of filter lines using the existing syntax. Likewise, if the "filters" capability was omitted, the client could error out without the extra round-trip.

All good ideas.

After hacking the code halfway together to make the above idea work, and learning quite a lot in the process, I saw set_git_option in transport.c and realized that all existing transport options are assumed to be ? (0 or 1) rather than * (0 or more). So "filter" would be the first transport option that is repeated.

Even though multiple reviewers have weighed in supporting repeated filter lines, I'm still conflicted about it. It seems the drawback to the + syntax is the requirement for encoding the individual filters, but this encoding is no longer required since the sparse:path=... filter no longer has to be supported. And the URL encoding, if it is ever reintroduced, is just boilerplate and is unlikely to change later or cause a significant maintainance burden.

The essence of the repeated filter line is that we need additional high-level machinery just for the sake of making the lower-level machinery... marginally simpler, hopefully? And if we ever need to add new filter combinations (like OR or XOR rather than AND) this repeated filter line thing will be a legacy annoyance (users will wonder why does repeated "filter" mean AND rather than one of the other supported combination methods?). Repeating filter lines seems like a leaky abstraction to me.

I would be helped if someone re-iterated why the repeated filter lines are a good idea in light of the fact that URL escaping is no longer required to make it work.

Was sparse:path filter the only reason for needing all the URL encoding? The sparse:oid form allows values <ref>:<path> and these (or at least the <path> portion) may contain special characters. So don't we need to URL encode this form too?

Quoted 4 lines · Jeff Hostetler

Was sparse:path filter the only reason for needing all the URL encoding? The sparse:oid form allows values <ref>:<path> and these (or at least the <path> portion) may contain special characters. So don't we need to URL encode this form too?

Oh, I missed this. I was only thinking an oid was allowed after "sparse:". So as I suspected I was overlooking something obvious.

Now I just want to understand the objection to URL encoding a little better. I haven't worked with in a project that requires a lot of boilerplate before, so I may be asking obvious things again. If so, sorry in advance.

So the objections, as I interpret them so far, are that:

a the URL encoding/decoding complicates the code base
b explaining the URL encoding, while it allows for future expansion, requires
some verbose documentation in git-rev-list that is potentially distracting or confusing
c there may be a better way to allow for future expansion that does not require
URL encoding
d the URL encoding is unpleasant to use (note that my patchset makes it
optional for the user to use and it is only mandatory in sending it over the wire)

I think these are reasonable and I'm willing to stop digging my heels in :) Does the above sum everything up?

BTW, I don't think I've seen this mentioned anywhere and I don't remember if this got into the code or not. But we discussed having a repo-local config setting to remember the filter-spec used by the partial clone that would be inherited by a subsequent (partial) fetch. Or would be set by the first partial fetch following a normal clone. Having a single composite filter spec would help with this.

Quoted 6 lines · Jeff Hostetler

BTW, I don't think I've seen this mentioned anywhere and I don't remember if this got into the code or not. But we discussed having a repo-local config setting to remember the filter-spec used by the partial clone that would be inherited by a subsequent (partial) fetch. Or would be set by the first partial fetch following a normal clone. Having a single composite filter spec would help with this.

Isn't that what the partial_clone_get_default_filter_spec function is for? I forgot about that. Perhaps with Emily's suggestion to use parsing functions in the C library and the other cleanups I've applied since the first roll-up, using the URL encoding will seem nicer. Let me try that...

We are allowing an unlimited number of filters in the composition. In the code, the compose filter data has space for a LHS and RHS, so I'm assuming we're mapping

    --filter=f1 --filter=f2 --filter=f3 --filter=f4
or  --filter=combine:f1+f2+f3+f4
into basically
    (compose f1 (compose f2 (compose (f3 f4)))

I wonder if it would be easier to understand if we just built an array or linked list, but I'll read on.

Should we swap the order of the terms in the || so that we always clear the d->sub[i].is_skipping_tree on LOFS_END_TREE ?

list-objects-filter.c static void filter_sparse_path__init( · line 541

Quoted 11 lines

list-objects-filter.c +10 -0

+			result[i] = LOFR_ZERO;
+			continue;
+		}
+
+		result[i] = d->sub[i].ctx.filter_fn(
+			r, filter_situation, obj, pathname, filename,
+			&d->sub[i].ctx);
+
+		if (result[i] & LOFR_MARK_SEEN)
+			oidset_insert(&d->sub[i].seen, &obj->oid);

So filter[i] has said it never wants to show this object (hard omit). And the guard at the top of the loop will prevent future invocations from checking it again if the object is revisited.

list-objects-filter.c static void filter_sparse_path__init( · line 545

Quoted 4 lines

list-objects-filter.c +4 -0

+
+		if (result[i] & LOFR_SKIP_TREE) {
+			d->sub[i].is_skipping_tree = 1;
+			d->sub[i].skip_tree = obj->oid;

So this marks the tree object at the top of the skip as far as filter[i] is concerned.

list-objects-filter.c static void filter_sparse_path__init( · line 552

Quoted 7 lines

list-objects-filter.c +7 -0

+		}
+	}
+
+	if ((result[0] & LOFR_DO_SHOW) && (result[1] & LOFR_DO_SHOW))
+		combined_result |= LOFR_DO_SHOW;
+	if (d->sub[0].is_skipping_tree && d->sub[1].is_skipping_tree)
+		combined_result |= LOFR_SKIP_TREE;

Something about the above bothers me, but I can't quite say what it is.

Do we need to do:

    if ((result[0] & LOFR_MARK_SEEN) && (result[1] & LOFR_MARK_SEEN))
        combined_result |= LOFR_MARK_SEEN;

I'm out of time now, will pick this up again next week.

Allow combining filters such that only objects accepted by all filters are shown. The motivation for this is to allow getting directory listings without also fetching blobs. This can be done by combining blob:none with tree:<depth>. There are massive repositories that have larger-than-expected trees - even if you include only a single commit.

The current usage requires passing the filter to rev-list, or sending it over the wire, as:

	combine:<FILTER1>+<FILTER2>

(i.e.: git rev-list --filter=combine:tree:2+blob:limit=32k). This is potentially awkward because individual filters must be URL-encoded if they contain + or %. This can potentially be improved by supporting a repeated flag syntax, e.g.:

	$ git rev-list --filter=tree:2 --filter=blob:limit=32k

Such usage is currently an error, so giving it a meaning is backwards- compatible.

Signed-off-by Matthew DeVore <[email protected]>

---
 Documentation/rev-list-options.txt     |  12 ++
 contrib/completion/git-completion.bash |   2 +-
 list-objects-filter-options.c          | 161 ++++++++++++++++++++++++-
 list-objects-filter-options.h          |  14 ++-
 list-objects-filter.c                  | 114 +++++++++++++++++
 t/t6112-rev-list-filters-objects.sh    | 159 +++++++++++++++++++++++-
 6 files changed, 455 insertions(+), 7 deletions(-)

Documentation/rev-list-options.txt +12 -0

index ddbc1de43f..4fb0c4fbb0 100644
@@ -730,20 +730,32 @@ specification contained in <path>.
 +
 The form '--filter=tree:<depth>' omits all blobs and trees whose depth
 from the root tree is >= <depth> (minimum depth if an object is located
 at multiple depths in the commits traversed). <depth>=0 will not include
 any trees or blobs unless included explicitly in the command-line (or
 standard input when --stdin is used). <depth>=1 will include only the
 tree and blobs which are referenced directly by a commit reachable from
 <commit> or an explicitly-given object. <depth>=2 is like <depth>=1
 while also including trees and blobs one more level removed from an
 explicitly-given commit or tree.
++
+The form '--filter=combine:<filter1>+<filter2>+...<filterN>' combines
+several filters. Only objects which are accepted by every filter are
+included. Filters are joined by '{plus}' and individual filters are %-encoded
+(i.e. URL-encoded). Besides the '{plus}' and '%' characters, the following
+characters are reserved and also must be encoded:
+`~!@#$^&*()[]{}\;",<>?`+&#39;&#96;+ as well as all characters with ASCII code
+&lt;= `0x20`, which includes space and newline.
++
+Other arbitrary characters can also be encoded. For instance,
+'combine:tree:3+blob:none' and 'combine:tree%3A2+blob%3Anone' are
+equivalent.
 
 --no-filter::
 	Turn off any previous `--filter=` argument.
 
 --filter-print-omitted::
 	Only useful with `--filter=`; prints a list of the objects omitted
 	by the filter.  Object IDs are prefixed with a ``~'' character.
 
 --missing=<missing-action>::
 	A debug option to help with future "partial clone" development.

contrib/completion/git-completion.bash +1 -1

index 3eefbabdb1..0fd0a10d0c 100644
@@ -1529,21 +1529,21 @@ _git_difftool ()
 __git_fetch_recurse_submodules="yes on-demand no"
 
 _git_fetch ()
 {
 	case "$cur" in
 	--recurse-submodules=*)
 		__gitcomp "$__git_fetch_recurse_submodules" "" "${cur##--recurse-submodules=}"
 		return
 		;;
 	--filter=*)
-		__gitcomp "blob:none blob:limit= sparse:oid= sparse:path=" "" "${cur##--filter=}"
+		__gitcomp "blob:none blob:limit= sparse:oid= sparse:path= combine: tree:" "" "${cur##--filter=}"
 		return
 		;;
 	--*)
 		__gitcomp_builtin fetch
 		return
 		;;
 	esac
 	__git_complete_remote_or_refspec
 }
 

list-objects-filter-options.c +5 -2

index e46ea467bc..d7a1516188 100644
@@ -1,19 +1,24 @@
 #include "cache.h"
 #include "commit.h"
 #include "config.h"
 #include "revision.h"
 #include "argv-array.h"
 #include "list-objects.h"
 #include "list-objects-filter.h"
 #include "list-objects-filter-options.h"
 
+static int parse_combine_filter(
+	struct list_objects_filter_options *filter_options,
+	const char *arg,
+	struct strbuf *errbuf);
+
 /*
  * Parse value of the argument to the "filter" keyword.
  * On the command line this looks like:
  *       --filter=<arg>
  * and in the pack protocol as:
  *       "filter" SP <arg>
  *
  * The filter keyword will be used by many commands.
  * See Documentation/rev-list-options.txt for allowed values for <arg>.
  *

@@ -31,22 +36,20 @@ static int gently_parse_list_objects_filter(
 
 	if (filter_options->choice) {
 		if (errbuf) {
 			strbuf_addstr(
 				errbuf,
 				_("multiple filter-specs cannot be combined"));
 		}
 		return 1;
 	}
 
-	filter_options->filter_spec = strdup(arg);
-
 	if (!strcmp(arg, "blob:none")) {
 		filter_options->choice = LOFC_BLOB_NONE;
 		return 0;
 
 	} else if (skip_prefix(arg, "blob:limit=", &v0)) {
 		if (git_parse_ulong(v0, &filter_options->blob_limit_value)) {
 			filter_options->choice = LOFC_BLOB_LIMIT;
 			return 0;
 		}
 

@@ -74,37 +77,183 @@ static int gently_parse_list_objects_filter(
 		if (!get_oid_with_context(the_repository, v0, GET_OID_BLOB,
 					  &sparse_oid, &oc))
 			filter_options->sparse_oid_value = oiddup(&sparse_oid);
 		filter_options->choice = LOFC_SPARSE_OID;
 		return 0;
 
 	} else if (skip_prefix(arg, "sparse:path=", &v0)) {

list-objects-filter-options.c +1 -0

+
 	}
 	/*
 	 * Please update _git_fetch() in git-completion.bash when you
 	 * add new filters
 	 */
 
 	if (errbuf)
 		strbuf_addf(errbuf, _("invalid filter-spec '%s'"), arg);
 
 	memset(filter_options, 0, sizeof(*filter_options));

list-objects-filter-options.c +51 -0

+
+	if (!errbuf)
+		return -1;
+
+	strbuf_addf(errbuf, _("error in filter-spec - "));
+	if (c)
+		strbuf_addf(
+			errbuf,
+			_("expect two hex digits after %%, but got: '%c'"),
+			c);
+	else
+		strbuf_addf(
+			errbuf,
+			_("not enough hex digits after %%; expected two"));
+
+	return -1;
+}
+
+static int url_decode(struct strbuf *s, struct strbuf *errbuf) {
+	char *dest = s->buf;
+	char *src = s->buf;
+	size_t new_len;
+
+	while (*src) {
+		int digit_value_0, digit_value_1;
+
+		if (src[0] != '%') {
+			*dest++ = *src++;
+			continue;
+		}
+		src++;
+
+		digit_value_0 = digit_value(*src++, errbuf);
+		if (digit_value_0 < 0)
+			return 1;
+		digit_value_1 = digit_value(*src++, errbuf);
+		if (digit_value_1 < 0)
+			return 1;
+		*dest++ = digit_value_0 * 16 + digit_value_1;
+	}
+	new_len = dest - s->buf;
+	strbuf_remove(s, new_len, s->len - new_len);
+
+	return 0;
+}
+
+static const char *RESERVED_NON_WS = "~`!@#$^&*()[]{}\\;'\",<>?";
+
+static int has_reserved_character(
+	struct strbuf *sub_spec, struct strbuf *errbuf)
+{

list-objects-filter-options.c +49 -0

+	if (errbuf)
+		strbuf_addf(errbuf,
+			    "must escape char in sub-filter-spec: '%c'",
+			    *c);
+	return 1;
+}
+
+static int parse_combine_filter(
+	struct list_objects_filter_options *filter_options,
+	const char *arg,
+	struct strbuf *errbuf)
+{
+	struct strbuf **sub_specs = strbuf_split_str(arg, '+', 2);
+	int result;
+
+	if (!sub_specs[0]) {
+		if (errbuf)
+			strbuf_addf(errbuf,
+				    _("expected something after combine:"));
+		result = 1;
+		goto cleanup;
+	}
+
+	result = has_reserved_character(sub_specs[0], errbuf);
+	if (result)
+		goto cleanup;
+
+	/*
+	 * Only decode the first sub-filter, since the rest will be decoded on
+	 * the recursive call.
+	 */
+	result = url_decode(sub_specs[0], errbuf);
+	if (result)
+		goto cleanup;
+
+	if (!sub_specs[1]) {
+		/*
+		 * There is only one sub-filter, so we don't need the
+		 * combine: - just parse it as a non-composite filter.
+		 */
+		result = gently_parse_list_objects_filter(
+			filter_options, sub_specs[0]->buf, errbuf);
+		goto cleanup;
+	}
+
+	/* Remove trailing "+" so we can parse it. */
+	assert(sub_specs[0]->buf[sub_specs[0]->len - 1] == '+');
+	strbuf_remove(sub_specs[0], sub_specs[0]->len - 1, 1);
+

list-objects-filter-options.c +11 -0

+
+cleanup:
+	strbuf_list_free(sub_specs);
+	if (result) {
+		list_objects_filter_release(filter_options);
+		memset(filter_options, 0, sizeof(*filter_options));
+	}
+	return result;
+}
+
 int parse_list_objects_filter(struct list_objects_filter_options *filter_options,
 			      const char *arg)
 {
 	struct strbuf buf = STRBUF_INIT;
+	filter_options->filter_spec = strdup(arg);
 	if (gently_parse_list_objects_filter(filter_options, arg, &buf))
 		die("%s", buf.buf);
 	return 0;
 }
 
 int opt_parse_list_objects_filter(const struct option *opt,
 				  const char *arg, int unset)
 {
 	struct list_objects_filter_options *filter_options = opt->value;
 

@@ -127,23 +276,29 @@ void expand_list_objects_filter_spec(
 	else if (filter->choice == LOFC_TREE_DEPTH)
 		strbuf_addf(expanded_spec, "tree:%lu",
 			    filter->tree_exclude_depth);
 	else
 		strbuf_addstr(expanded_spec, filter->filter_spec);
 }
 
 void list_objects_filter_release(
 	struct list_objects_filter_options *filter_options)

list-objects-filter-options.c +2 -0

 	memset(filter_options, 0, sizeof(*filter_options));
 }
 
 void partial_clone_register(
 	const char *remote,
 	const struct list_objects_filter_options *filter_options)
 {
 	/*
 	 * Record the name of the partial clone remote in the
 	 * config and in the global variable -- the latter is

@@ -171,14 +326,16 @@ void partial_clone_register(
 }
 
 void partial_clone_get_default_filter_spec(
 	struct list_objects_filter_options *filter_options)
 {
 	/*
 	 * Parse default value, but silently ignore it if it is invalid.
 	 */
 	if (!core_partial_clone_filter_default)
 		return;
+
+	filter_options->filter_spec = strdup(core_partial_clone_filter_default);
 	gently_parse_list_objects_filter(filter_options,
 					 core_partial_clone_filter_default,
 					 NULL);
 }

list-objects-filter-options.h +11 -3

index e3adc78ebf..6c0f0ecd08 100644
@@ -7,20 +7,21 @@
 /*
  * The list of defined filters for list-objects.
  */
 enum list_objects_filter_choice {
 	LOFC_DISABLED = 0,
 	LOFC_BLOB_NONE,
 	LOFC_BLOB_LIMIT,
 	LOFC_TREE_DEPTH,
 	LOFC_SPARSE_OID,
 	LOFC_SPARSE_PATH,
+	LOFC_COMBINE,
 	LOFC__COUNT /* must be last */
 };
 
 struct list_objects_filter_options {
 	/*
 	 * 'filter_spec' is the raw argument value given on the command line
 	 * or protocol request.  (The part after the "--keyword=".)  For
 	 * commands that launch filtering sub-processes, or for communication
 	 * over the network, don't use this value; use the result of
 	 * expand_list_objects_filter_spec() instead.

@@ -32,28 +33,35 @@ struct list_objects_filter_options {
 	 * the filtering algorithm to use.
 	 */
 	enum list_objects_filter_choice choice;
 
 	/*
 	 * Choice is LOFC_DISABLED because "--no-filter" was requested.
 	 */
 	unsigned int no_filter : 1;
 
 	/*
-	 * Parsed values (fields) from within the filter-spec.  These are
-	 * choice-specific; not all values will be defined for any given
-	 * choice.
+	 * BEGIN choice-specific parsed values from within the filter-spec. Only
+	 * some values will be defined for any given choice.
 	 */
+
 	struct object_id *sparse_oid_value;
 	char *sparse_path_value;
 	unsigned long blob_limit_value;
 	unsigned long tree_exclude_depth;
+
+	/* LOFC_COMBINE values */
+	struct list_objects_filter_options *lhs, *rhs;
+
+	/*
+	 * END choice-specific parsed values.
+	 */
 };
 
 /* Normalized command line arguments */
 #define CL_ARG__FILTER "filter"
 
 int parse_list_objects_filter(
 	struct list_objects_filter_options *filter_options,
 	const char *arg);
 
 int opt_parse_list_objects_filter(const struct option *opt,

list-objects-filter.c +0 -0

index 8e8616b9b8..b97277a46f 100644
@@ -453,34 +453,148 @@ static void filter_sparse_path__init(
 
 	ALLOC_GROW(d->array_frame, d->nr + 1, d->alloc);

list-objects-filter.c +55 -0

+	struct {
+		struct filter_context ctx;
+		struct oidset seen;
+		struct object_id skip_tree;
+		unsigned is_skipping_tree : 1;
+	} sub[2];
+
+	struct oidset rhs_omits;
+};
+
+static void add_all(struct oidset *dest, struct oidset *src) {
+	struct oidset_iter iter;
+	struct object_id *src_oid;
+
+	oidset_iter_init(src, &iter);
+	while ((src_oid = oidset_iter_next(&iter)) != NULL)
+		oidset_insert(dest, src_oid);
+}
+
+static void filter_combine_free(void *filter_data)
+{
+	struct filter_combine_data *d = filter_data;
+	int i;
+
+	/* Anything omitted by rhs should be added to the overall omits set. */
+	if (d->sub[0].ctx.omits)
+		add_all(d->sub[0].ctx.omits, d->sub[1].ctx.omits);
+
+	for (i = 0; i < 2; i++) {
+		list_objects_filter__release(&d->sub[i].ctx);
+		oidset_clear(&d->sub[i].seen);
+	}
+	oidset_clear(&d->rhs_omits);
+	free(d);
+}
+
+static int should_delegate(enum list_objects_filter_situation filter_situation,
+			   struct object *obj,
+			   struct filter_combine_data *d,
+			   int side)
+{
+	if (!d->sub[side].is_skipping_tree)
+		return 1;
+	if (filter_situation == LOFS_END_TREE &&
+		oideq(&obj->oid, &d->sub[side].skip_tree)) {
+		d->sub[side].is_skipping_tree = 0;
+		return 1;
+	}
+	return 0;
+}
+
+static enum list_objects_filter_result filter_combine(
+	struct repository *r,
+	enum list_objects_filter_situation filter_situation,
+	struct object *obj,

list-objects-filter.c +16 -0

+		if (oidset_contains(&d->sub[i].seen, &obj->oid) ||
+			!should_delegate(filter_situation, obj, d, i)) {
+			result[i] = LOFR_ZERO;
+			continue;
+		}
+
+		result[i] = d->sub[i].ctx.filter_fn(
+			r, filter_situation, obj, pathname, filename,
+			&d->sub[i].ctx);
+
+		if (result[i] & LOFR_MARK_SEEN)
+			oidset_insert(&d->sub[i].seen, &obj->oid);
+
+		if (result[i] & LOFR_SKIP_TREE) {
+			d->sub[i].is_skipping_tree = 1;
+			d->sub[i].skip_tree = obj->oid;

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 93

Quoted 6 lines

list-objects-filter-options.c +6 -0

+	} else if (skip_prefix(arg, "combine:", &v0)) {
+		int sub_parse_res = parse_combine_filter(
+			filter_options, v0, errbuf);
+		if (sub_parse_res)
+			return sub_parse_res;
+		return 0;

Couldn't the three lines above be said more succinctly as "return sub_parse_res;"?

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 114

Quoted 7 lines

list-objects-filter-options.c +7 -0

+static int digit_value(int c, struct strbuf *errbuf) {
+	if (c >= '0' && c <= '9')
+		return c - '0';
+	if (c >= 'a' && c <= 'f')
+		return c - 'a' + 10;
+	if (c >= 'A' && c <= 'F')
+		return c - 'A' + 10;

I'm sure there's something I'm missing here. But why are you manually decoding hex instead of using strtol or sscanf or something?

Quoted 8 lines

list-objects-filter-options.c +8 -0

+static int has_reserved_character(
+	struct strbuf *sub_spec, struct strbuf *errbuf)
+{
+	const char *c = sub_spec->buf;
+	while (*c) {
+		if (*c <= ' ' || strchr(RESERVED_NON_WS, *c))
+			goto found_reserved;
+		c++;

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 175

Quoted 5 lines

list-objects-filter-options.c +5 -0

+	}
+
+	return 0;
+
+found_reserved:

What's the value of doing this in a goto instead of embedded in the while loop?

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 234

Quoted 7 lines

list-objects-filter-options.c +7 -0

+
+	result = gently_parse_list_objects_filter(filter_options->lhs,
+						  sub_specs[0]->buf,
+						  errbuf) ||
+		parse_combine_filter(filter_options->rhs,
+				      sub_specs[1]->buf,
+				      errbuf);

I guess you're recursing to combine filter 2 onto filter 1 which has been combined onto filter 0 here. But why not just use a list or array?

Quoted 10 lines

void list_objects_filter_release(

list-objects-filter-options.c +3 -0

 	struct list_objects_filter_options *filter_options)
 {
+	if (!filter_options)
+		return;
 	free(filter_options->filter_spec);
 	free(filter_options->sparse_oid_value);
 	free(filter_options->sparse_path_value);
+	list_objects_filter_release(filter_options->lhs);

list-objects-filter-options.c void expand_list_objects_filter_spec( · line 294

Quoted 3 lines

list-objects-filter-options.c +3 -0

+	free(filter_options->lhs);
+	list_objects_filter_release(filter_options->rhs);
+	free(filter_options->rhs);

Is there a reason that the free shouldn't be included in list_objects_filter_release()? Maybe this is a common style guideline I've missed, but it seems to me like I'd expect a magic memory cleanup function to do it all, and not leave it to me to free.

Jeff H had a comment about this too, but this seems unwieldy for >2 filters. (I also personally don't like using set index to incidate lhs/rhs.) Why not an array of multiple struct sub? There's a macro utility to generate types and helpers for an array of arbitrary struct that may suit...

Quoted 11 lines

list-objects-filter.c +11 -0

+static enum list_objects_filter_result filter_combine(
+	struct repository *r,
+	enum list_objects_filter_situation filter_situation,
+	struct object *obj,
+	const char *pathname,
+	const char *filename,
+	struct filter_context *ctx)
+{
+	struct filter_combine_data *d = ctx->data;
+	enum list_objects_filter_result result[2];
+	enum list_objects_filter_result combined_result = LOFR_ZERO;

list-objects-filter.c static void filter_sparse_path__init( · line 493

Quoted 3 lines

list-objects-filter.c +3 -0

+	int i;
+
+	for (i = 0; i < 2; i++) {

I suppose your lhs and rhs are in sub[0] and sub[1] in part for the sake of this loop. But I think it would be easier to understand what is going on if you were to perform the loop contents in a helper function (as the name of the function would provide some more documentation).

I see that you tested that >2 filters works okay. But by doing it the way you have it seems like you're setting up to need recursion all over the place to check against all the filters. I suppose I don't see the benefit of doing all this recursively, as compared to doing it iteratively.

Quoted 11 lines

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 114

Quoted 7 lines

list-objects-filter-options.c +7 -0

+static int digit_value(int c, struct strbuf *errbuf) {
+	if (c >= '0' && c <= '9')
+		return c - '0';
+	if (c >= 'a' && c <= 'f')
+		return c - 'a' + 10;
+	if (c >= 'A' && c <= 'F')
+		return c - 'A' + 10;

I'm sure there's something I'm missing here. But why are you manually decoding hex instead of using strtol or sscanf or something?

I'll have to give this a try. Thank you for the suggestion.

Quoted 12 lines · Matthew DeVore

Quoted 11 lines

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 114

Quoted 7 lines

list-objects-filter-options.c +7 -0

+static int digit_value(int c, struct strbuf *errbuf) {
+	if (c >= '0' && c <= '9')
+		return c - '0';
+	if (c >= 'a' && c <= 'f')
+		return c - 'a' + 10;
+	if (c >= 'A' && c <= 'F')
+		return c - 'A' + 10;

I'm sure there's something I'm missing here. But why are you manually decoding hex instead of using strtol or sscanf or something?

Quoted 1 line

I'll have to give this a try. Thank you for the suggestion.

Try our hex_to_bytes() helper (or if you really want to go low-level, your conditionals can be replaced by lookups in the hexval table).

-Peff

Quoted 14 lines · Jeff King

Quoted 12 lines · Matthew DeVore

Quoted 11 lines

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 114

Quoted 7 lines

list-objects-filter-options.c +7 -0

+static int digit_value(int c, struct strbuf *errbuf) {
+	if (c >= '0' && c <= '9')
+		return c - '0';
+	if (c >= 'a' && c <= 'f')
+		return c - 'a' + 10;
+	if (c >= 'A' && c <= 'F')
+		return c - 'A' + 10;

I'm sure there's something I'm missing here. But why are you manually decoding hex instead of using strtol or sscanf or something?

Quoted 4 lines

Quoted 1 line

I'll have to give this a try. Thank you for the suggestion.

Try our hex_to_bytes() helper (or if you really want to go low-level, your conditionals can be replaced by lookups in the hexval table).

Using hex_to_bytes worked out quite nicely, thanks!

Great. We might want to stop there, but it's possible could reuse even more code. I didn't look closely before, but it seems this code is decoding a URL. We already have a url_decode() routine in url.c. Could it be reused?

Quoted 4 lines · Jeff King

Great. We might want to stop there, but it's possible could reuse even more code. I didn't look closely before, but it seems this code is decoding a URL. We already have a url_decode() routine in url.c. Could it be reused?

Very nice. Here is an interdiff and the changes will be included in v3 of my patchset:

list-objects-filter-options.c static int has_reserved_character( · line 124

Quoted 5 lines

list-objects-filter-options.c +1 -4

-	return has_reserved_character(subspec, errbuf) ||
-		url_decode(subspec, errbuf) ||
-		gently_parse_list_objects_filter(
-			&filter_options->sub[new_index], subspec->buf, errbuf);
+	decoded = url_percent_decode(subspec->buf);

I think you can get rid of has_reserved_character() now, too.

The reserved character list is still used on the encoding side. But I think you could switch to strbuf_add_urlencode() there?

Quoted 7 lines · Jeff King

list-objects-filter-options.c static int has_reserved_character( · line 124

Quoted 5 lines

list-objects-filter-options.c +1 -4

-	return has_reserved_character(subspec, errbuf) ||
-		url_decode(subspec, errbuf) ||
-		gently_parse_list_objects_filter(
-			&filter_options->sub[new_index], subspec->buf, errbuf);
+	decoded = url_percent_decode(subspec->buf);

I think you can get rid of has_reserved_character() now, too.

The purpose of has_reserved_character is to allow for future extensibility if someone decides to implement a more sophisticated DSL and give meaning to these characters. That may be a long-shot, but it seems worth it.

Quoted 2 lines

The reserved character list is still used on the encoding side. But I think you could switch to strbuf_add_urlencode() there?

strbuf_addstr_urlencode will either escape or not escape all rfc3986 reserved characters, and that set includes both : and +. The former should not require escaping since it's a common character in filter specs, and I would like the hand-encoded combine specs to be relatively easy to type and read. The + must be escaped since it is used as part of the combine:... syntax to delimit sub filters. So strbuf_addstr_url_encode would have to be more customizable to make it work for this context. I'd like to add a parameterizable should_escape predicate (iow function pointer) which strbuf_addstr_urlencode accepts. I actually think this will be more readable than the current strbuf API.

Quoted 4 lines

The purpose of has_reserved_character is to allow for future extensibility if someone decides to implement a more sophisticated DSL and give meaning to these characters. That may be a long-shot, but it seems worth it.

I think you'll find that -Wunused-function complains, though, if nobody is calling it. I wasn't sure if what you showed in the interdiff was meant to be final (I had to add a few other variable declarations to make it compile, too).

Quoted 10 lines

strbuf_addstr_urlencode will either escape or not escape all rfc3986 reserved characters, and that set includes both : and +. The former should not require escaping since it's a common character in filter specs, and I would like the hand-encoded combine specs to be relatively easy to type and read. The + must be escaped since it is used as part of the combine:... syntax to delimit sub filters. So strbuf_addstr_url_encode would have to be more customizable to make it work for this context. I'd like to add a parameterizable should_escape predicate (iow function pointer) which strbuf_addstr_urlencode accepts. I actually think this will be more readable than the current strbuf API.

That makes some sense, and I agree that readability is a good goal. Do we not need to be escaping colons in other URLs? Or are the strings you're generating not true by-the-book URLs? I'm just wondering if we could take this opportunity to improve the URLs we output elsewhere, too.

Quoted 4 lines

I think you'll find that -Wunused-function complains, though, if nobody is calling it. I wasn't sure if what you showed in the interdiff was meant to be final (I had to add a few other variable declarations to make it compile, too).

Sorry, my last interdiff was a mess because I made a mistake during git rebase -i. It was missing a call to has_reserved_char. Below is another diff that fixes the problems:

Quoted 5 lines

That makes some sense, and I agree that readability is a good goal. Do we not need to be escaping colons in other URLs? Or are the strings you're generating not true by-the-book URLs? I'm just wondering if we could take this opportunity to improve the URLs we output elsewhere, too.

The strings I'm generating are not URLs. Also, in http.c, we have to use : to delimit a username and password:

	strbuf_addstr_urlencode(&s, proxy_auth.username, 1);
	strbuf_addch(&s, ':');
	strbuf_addstr_urlencode(&s, proxy_auth.password, 1);

I think this is dictated by libcurl and is not flexible.

Right, that has to be a real colon because it's syntactically significant (but a colon in the username _must_ be encoded). That strbuf function doesn't really understand whole URLs, and it's up to the caller to assemble the parts.

Anyway, we've veered off of your patch series enough. Yeah, it sounds like using strbuf's url-encoding is not quite what you want.