[PATCH 0/7] rev-parse: implement object type filter

Hi,

I've recently had the usecase to retrieve all blobs introduces between
two versions which have a limit smaller than 200 bytes in order to find
all potential candidates for LFS pointers. This is currently done with
`git rev-list --objects --filter=blob:limit=200 <newrev> ^<oldrev>`, but
this is kind of inefficient: the resulting list is way too long as it
also potentially includes tags, commits and trees.

To be able to more efficiently answer this query, I've implemented
multiple things:

- A new object type filter `--filter=object:type=<type>` for
  git-rev-list(1), which is implemented both for normal graph walks and
  for the packfile bitmap index.

- Given that above usecase requires two filters (the object type
  and blob size filters), bitmap filters were extended to support
  combined filters.

- git-rev-list(1) doesn't filter user-provided objects and always prints
  them. I don't want the listed commits though and only their referenced
  potential LFS blobs. So I've added a new flag `--filter-provided`
  which marks all provided objects as not-user-provided such that they
  get filtered the same as all the other objects.

Altogether, this ends up with the following queries, both of which have
been executed in a well-packed linux.git repository:

    # Previous query which uses object names as a heuristic to filter
    # non-blob objects, which bars us from using bitmap indices because
    # they cannot print paths.
    $ time git rev-list --objects --filter=blob:limit=200 \
        --object-names --all | sed -r '/^.{,41}$/d' | wc -l
    4502300

    real 1m23.872s
    user 1m30.076s
    sys  0m6.002s

    # New query.
    $ time git rev-list --objects --filter-provided \
        --filter=object:type=blob --filter=blob:limit=200 \
        --use-bitmap-index --all | wc -l
    22585

    real 0m19.216s
    user 0m16.768s
    sys  0m2.450s

So with the new optimized query, we can both significantly reduce the
list of candidate LFS pointers and execution time.

Patrick

Patrick Steinhardt (7):
  revision: mark commit parents as NOT_USER_GIVEN
  list-objects: move tag processing into its own function
  list-objects: support filtering by tag and commit
  list-objects: implement object type filter
  pack-bitmap: implement object type filter
  pack-bitmap: implement combined filter
  rev-list: allow filtering of provided items

 Documentation/rev-list-options.txt  |   3 +
 builtin/rev-list.c                  |  14 ++++
 list-objects-filter-options.c       |  14 ++++
 list-objects-filter-options.h       |   8 ++
 list-objects-filter.c               | 116 ++++++++++++++++++++++++++++
 list-objects-filter.h               |   2 +
 list-objects.c                      |  32 +++++++-
 pack-bitmap.c                       |  71 +++++++++++++++--
 revision.c                          |   4 +-
 revision.h                          |   3 -
 t/t6112-rev-list-filters-objects.sh |  76 ++++++++++++++++++
 t/t6113-rev-list-bitmap-filters.sh  |  54 ++++++++++++-
 12 files changed, 380 insertions(+), 17 deletions(-)

-- 
2.30.1

Object filters currently only support filtering blobs or trees based on
some criteria. This commit lays the foundation to also allow filtering
of tags and commits.

No change in behaviour is expected from this commit given that there are
no filters yet for those object types.

Signed-off-by: Patrick Steinhardt <redacted>
---
 list-objects-filter.c | 40 ++++++++++++++++++++++++++++++++++++++++
 list-objects-filter.h |  2 ++
 list-objects.c        | 24 +++++++++++++++++++++---
 3 files changed, 63 insertions(+), 3 deletions(-)

diff --git a/list-objects-filter.c b/list-objects-filter.c
index 4ec0041cfb..7def039435 100644
--- a/list-objects-filter.c
+++ b/list-objects-filter.c

@@ -82,6 +82,16 @@ static enum list_objects_filter_result filter_blobs_none(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_BEGIN_TREE:
 		assert(obj->type == OBJ_TREE);
 		/* always include all tree objects */

@@ -173,6 +183,16 @@ static enum list_objects_filter_result filter_trees_depth(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_END_TREE:
 		assert(obj->type == OBJ_TREE);
 		filter_data->current_depth--;

@@ -267,6 +287,16 @@ static enum list_objects_filter_result filter_blobs_limit(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_BEGIN_TREE:
 		assert(obj->type == OBJ_TREE);
 		/* always include all tree objects */

@@ -371,6 +401,16 @@ static enum list_objects_filter_result filter_sparse(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_BEGIN_TREE:
 		assert(obj->type == OBJ_TREE);
 		dtype = DT_DIR;

diff --git a/list-objects-filter.h b/list-objects-filter.h
index cfd784e203..9e98814111 100644
--- a/list-objects-filter.h
+++ b/list-objects-filter.h

@@ -55,6 +55,8 @@ enum list_objects_filter_result {
 };
 
 enum list_objects_filter_situation {
+	LOFS_COMMIT,
+	LOFS_TAG,
 	LOFS_BEGIN_TREE,
 	LOFS_END_TREE,
 	LOFS_BLOB

diff --git a/list-objects.c b/list-objects.c
index 093adf85b1..3b63dfd4f2 100644
--- a/list-objects.c
+++ b/list-objects.c

@@ -218,8 +218,16 @@ static void process_tag(struct traversal_context *ctx,
 			struct strbuf *base,
 			const char *name)
 {
-	tag->object.flags |= SEEN;
-	ctx->show_object(&tag->object, name, ctx->show_data);
+	enum list_objects_filter_result r;
+
+	r = list_objects_filter__filter_object(ctx->revs->repo, LOFS_TAG,
+					       &tag->object, base->buf,
+					       &base->buf[base->len],
+					       ctx->filter);
+	if (r & LOFR_MARK_SEEN)
+		tag->object.flags |= SEEN;
+	if (r & LOFR_DO_SHOW)
+		ctx->show_object(&tag->object, name, ctx->show_data);
 }
 
 static void mark_edge_parents_uninteresting(struct commit *commit,

@@ -369,6 +377,12 @@ static void do_traverse(struct traversal_context *ctx)
 	strbuf_init(&csp, PATH_MAX);
 
 	while ((commit = get_revision(ctx->revs)) != NULL) {
+		enum list_objects_filter_result r;
+
+		r = list_objects_filter__filter_object(ctx->revs->repo,
+				LOFS_COMMIT, &commit->object,
+				NULL, NULL, ctx->filter);
+
 		/*
 		 * an uninteresting boundary commit may not have its tree
 		 * parsed yet, but we are not going to show them anyway

@@ -383,7 +397,11 @@ static void do_traverse(struct traversal_context *ctx)
 			die(_("unable to load root tree for commit %s"),
 			      oid_to_hex(&commit->object.oid));
 		}
-		ctx->show_commit(commit, ctx->show_data);
+
+		if (r & LOFR_MARK_SEEN)
+			commit->object.flags |= SEEN;
+		if (r & LOFR_DO_SHOW)
+			ctx->show_commit(commit, ctx->show_data);
 
 		if (ctx->revs->tree_blobs_in_commit_order)
 			/*

-- 
2.30.1

While it already is possible to filter objects by some criteria in
git-rev-list(1), it is not yet possible to filter out only a specific
type of objects. This makes some filters less useful. The `blob:limit`
filter for example filters blobs such that only those which are smaller
than the given limit are returned. But it is unfit to ask only for these
smallish blobs, given that git-rev-list(1) will continue to print tags,
commits and trees.

Now that we have the infrastructure in place to also filter tags and
commits, we can improve this situation by implementing a new filter
which selects objects based on their type. Above query can thus
trivially be implemented with the following command:

    $ git rev-list --objects --filter=object:type=blob \
        --filter=blob:limit=200

Furthermore, this filter allows to optimize for certain other cases: if
for example only tags or commits have been selected, there is no need to
walk down trees.

The new filter is not yet supported in bitmaps. This is going to be
implemented in a subsequent commit.

Signed-off-by: Patrick Steinhardt <redacted>
---
 Documentation/rev-list-options.txt  |  3 ++
 list-objects-filter-options.c       | 14 ++++++
 list-objects-filter-options.h       |  2 +
 list-objects-filter.c               | 76 +++++++++++++++++++++++++++++
 t/t6112-rev-list-filters-objects.sh | 48 ++++++++++++++++++
 5 files changed, 143 insertions(+)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index b1c8f86c6e..3afa8fffbd 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt

@@ -892,6 +892,9 @@ or units.  n may be zero.  The suffixes k, m, and g can be used to name
 units in KiB, MiB, or GiB.  For example, 'blob:limit=1k' is the same
 as 'blob:limit=1024'.
 +
+The form '--filter=object:type=(tag|commit|tree|blob)' omits all objects
+which are not of the requested type.
++
 The form '--filter=sparse:oid=<blob-ish>' uses a sparse-checkout
 specification contained in the blob (or blob-expression) '<blob-ish>'
 to omit blobs that would not be not required for a sparse checkout on

diff --git a/list-objects-filter-options.c b/list-objects-filter-options.c
index d2d1c81caf..bb6f6577d5 100644
--- a/list-objects-filter-options.c
+++ b/list-objects-filter-options.c

@@ -29,6 +29,8 @@ const char *list_object_filter_config_name(enum list_objects_filter_choice c)
 		return "tree";
 	case LOFC_SPARSE_OID:
 		return "sparse:oid";
+	case LOFC_OBJECT_TYPE:
+		return "object:type";
 	case LOFC_COMBINE:
 		return "combine";
 	case LOFC__COUNT:

@@ -97,6 +99,18 @@ static int gently_parse_list_objects_filter(
 		}
 		return 1;
 
+	} else if (skip_prefix(arg, "object:type=", &v0)) {
+		int type = type_from_string_gently(v0, -1, 1);
+		if (type < 0) {
+			strbuf_addstr(errbuf, _("expected 'object:type=<type>'"));
+			return 1;
+		}
+
+		filter_options->object_type = type;
+		filter_options->choice = LOFC_OBJECT_TYPE;
+
+		return 0;
+
 	} else if (skip_prefix(arg, "combine:", &v0)) {
 		return parse_combine_filter(filter_options, v0, errbuf);
 

diff --git a/list-objects-filter-options.h b/list-objects-filter-options.h
index 01767c3c96..4d0d0588cc 100644
--- a/list-objects-filter-options.h
+++ b/list-objects-filter-options.h

@@ -13,6 +13,7 @@ enum list_objects_filter_choice {
 	LOFC_BLOB_LIMIT,
 	LOFC_TREE_DEPTH,
 	LOFC_SPARSE_OID,
+	LOFC_OBJECT_TYPE,
 	LOFC_COMBINE,
 	LOFC__COUNT /* must be last */
 };

@@ -54,6 +55,7 @@ struct list_objects_filter_options {
 	char *sparse_oid_name;
 	unsigned long blob_limit_value;
 	unsigned long tree_exclude_depth;
+	enum object_type object_type;
 
 	/* LOFC_COMBINE values */
 

diff --git a/list-objects-filter.c b/list-objects-filter.c
index 7def039435..650a7c2c80 100644
--- a/list-objects-filter.c
+++ b/list-objects-filter.c

@@ -545,6 +545,81 @@ static void filter_sparse_oid__init(
 	filter->free_fn = filter_sparse_free;
 }
 
+/*
+ * A filter for list-objects to omit large blobs.
+ * And to OPTIONALLY collect a list of the omitted OIDs.
+ */
+struct filter_object_type_data {
+	enum object_type object_type;
+};
+
+static enum list_objects_filter_result filter_object_type(
+	struct repository *r,
+	enum list_objects_filter_situation filter_situation,
+	struct object *obj,
+	const char *pathname,
+	const char *filename,
+	struct oidset *omits,
+	void *filter_data_)
+{
+	struct filter_object_type_data *filter_data = filter_data_;
+
+	switch (filter_situation) {
+	default:
+		BUG("unknown filter_situation: %d", filter_situation);
+
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		if (filter_data->object_type == OBJ_TAG)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+		return LOFR_MARK_SEEN;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		if (filter_data->object_type == OBJ_COMMIT)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+		return LOFR_MARK_SEEN;
+
+	case LOFS_BEGIN_TREE:
+		assert(obj->type == OBJ_TREE);
+
+		/*
+		 * If we only want to show commits or tags, then there is no
+		 * need to walk down trees.
+		 */
+		if (filter_data->object_type == OBJ_COMMIT ||
+		    filter_data->object_type == OBJ_TAG)
+			return LOFR_SKIP_TREE;
+
+		if (filter_data->object_type == OBJ_TREE)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+		return LOFR_MARK_SEEN;
+
+	case LOFS_BLOB:
+		assert(obj->type == OBJ_BLOB);
+
+		if (filter_data->object_type == OBJ_BLOB)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+		return LOFR_MARK_SEEN;
+
+	case LOFS_END_TREE:
+		return LOFR_ZERO;
+	}
+}
+
+static void filter_object_type__init(
+	struct list_objects_filter_options *filter_options,
+	struct filter *filter)
+{
+	struct filter_object_type_data *d = xcalloc(1, sizeof(*d));
+	d->object_type = filter_options->object_type;
+
+	filter->filter_data = d;
+	filter->filter_object_fn = filter_object_type;
+	filter->free_fn = free;
+}
+
 /* A filter which only shows objects shown by all sub-filters. */
 struct combine_filter_data {
 	struct subfilter *sub;

@@ -691,6 +766,7 @@ static filter_init_fn s_filters[] = {
 	filter_blobs_limit__init,
 	filter_trees_depth__init,
 	filter_sparse_oid__init,
+	filter_object_type__init,
 	filter_combine__init,
 };
 

diff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh
index 31457d13b9..c79ec04060 100755
--- a/t/t6112-rev-list-filters-objects.sh
+++ b/t/t6112-rev-list-filters-objects.sh

@@ -159,6 +159,54 @@ test_expect_success 'verify blob:limit=1m' '
 	test_must_be_empty observed
 '
 
+# Test object:type=<type> filter.
+
+test_expect_success 'setup object-type' '
+	git init object-type &&
+	echo contents >object-type/blob &&
+	git -C object-type add blob &&
+	git -C object-type commit -m commit-message &&
+	git -C object-type tag tag -m tag-message
+'
+
+test_expect_success 'verify object:type= fails with invalid type' '
+	test_must_fail git -C object-type rev-list --objects --filter=object:type= HEAD &&
+	test_must_fail git -C object-type rev-list --objects --filter=object:type=invalid HEAD
+'
+
+test_expect_success 'verify object:type=blob prints blob and commit' '
+	(
+		git -C object-type rev-parse HEAD &&
+		printf "%s blob\n" $(git -C object-type rev-parse HEAD:blob)
+	) >expected &&
+	git -C object-type rev-list --objects --filter=object:type=blob HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=tree prints tree and commit' '
+	(
+		git -C object-type rev-parse HEAD &&
+		printf "%s \n" $(git -C object-type rev-parse HEAD^{tree})
+	) >expected &&
+	git -C object-type rev-list --objects --filter=object:type=tree HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=commit prints commit' '
+	git -C object-type rev-parse HEAD >expected &&
+	git -C object-type rev-list --objects --filter=object:type=commit HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=tag prints tag' '
+	(
+		git -C object-type rev-parse HEAD &&
+		printf "%s tag\n" $(git -C object-type rev-parse tag)
+	) >expected &&
+	git -C object-type rev-list --objects --filter=object:type=tag tag >actual &&
+	test_cmp expected actual
+'
+
 # Test sparse:path=<path> filter.
 # !!!!
 # NOTE: sparse:path filter support has been dropped for security reasons,

-- 
2.30.1

The NOT_USER_GIVEN flag of an object marks whether a flag was explicitly
provided by the user or not. The most important use case for this is
when filtering objects: only objects that were not explicitly requested
will get filtered.

The flag is currently only set for blobs and trees, which has been fine
given that there are no filters for tags or commits currently. We're
about to extend filtering capabilities to add object type filter though,
which requires us to set up the NOT_USER_GIVEN flag correctly -- if it's
not set, the object wouldn't get filtered at all.

Mark unseen commit parents as NOT_USER_GIVEN when processing parents.
Like this, explicitly provided parents stay user-given and thus
unfiltered, while parents which get loaded as part of the graph walk
can be filtered.

This commit shouldn't have any user-visible impact yet as there is no
logic to filter commits yet.

Signed-off-by: Patrick Steinhardt <redacted>
---
 revision.c | 4 ++--
 revision.h | 3 ---
 2 files changed, 2 insertions(+), 5 deletions(-)

diff --git a/revision.c b/revision.c
index b78733f508..26f422f50d 100644
--- a/revision.c
+++ b/revision.c

@@ -1123,7 +1123,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,
 				mark_parents_uninteresting(p);
 			if (p->object.flags & SEEN)
 				continue;
-			p->object.flags |= SEEN;
+			p->object.flags |= (SEEN | NOT_USER_GIVEN);
 			if (list)
 				commit_list_insert_by_date(p, list);
 			if (queue)

@@ -1165,7 +1165,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,
 		}
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
-			p->object.flags |= SEEN;
+			p->object.flags |= (SEEN | NOT_USER_GIVEN);
 			if (list)
 				commit_list_insert_by_date(p, list);
 			if (queue)

diff --git a/revision.h b/revision.h
index e6be3c845e..f1f324a19b 100644
--- a/revision.h
+++ b/revision.h

@@ -44,9 +44,6 @@
 /*
  * Indicates object was reached by traversal. i.e. not given by user on
  * command-line or stdin.
- * NEEDSWORK: NOT_USER_GIVEN doesn't apply to commits because we only support
- * filtering trees and blobs, but it may be useful to support filtering commits
- * in the future.
  */
 #define NOT_USER_GIVEN	(1u<<25)
 #define TRACK_LINEAR	(1u<<26)

-- 
2.30.1

Move processing of tags into its own function to make the logic easier
to extend when we're going to implement filtering for tags. No change in
behaviour is expected from this commit.

Signed-off-by: Patrick Steinhardt <redacted>
---
 list-objects.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/list-objects.c b/list-objects.c
index e19589baa0..093adf85b1 100644
--- a/list-objects.c
+++ b/list-objects.c

@@ -213,6 +213,15 @@ static void process_tree(struct traversal_context *ctx,
 	free_tree_buffer(tree);
 }
 
+static void process_tag(struct traversal_context *ctx,
+			struct tag *tag,
+			struct strbuf *base,
+			const char *name)
+{
+	tag->object.flags |= SEEN;
+	ctx->show_object(&tag->object, name, ctx->show_data);
+}
+
 static void mark_edge_parents_uninteresting(struct commit *commit,
 					    struct rev_info *revs,
 					    show_edge_fn show_edge)

@@ -334,8 +343,7 @@ static void traverse_trees_and_blobs(struct traversal_context *ctx,
 		if (obj->flags & (UNINTERESTING | SEEN))
 			continue;
 		if (obj->type == OBJ_TAG) {
-			obj->flags |= SEEN;
-			ctx->show_object(obj, name, ctx->show_data);
+			process_tag(ctx, (struct tag *)obj, base, name);
 			continue;
 		}
 		if (!path)

-- 
2.30.1

When the user has multiple objects filters specified, then this is
internally represented by having a "combined" filter. These combined
filters aren't yet supported by bitmap indices and can thus not be
accelerated.

Fix this by implementing support for these combined filters. The
implementation is quite trivial: when there's a combined filter, we
simply recurse into `filter_bitmap()` for all of the sub-filters.

Signed-off-by: Patrick Steinhardt <redacted>
---
 pack-bitmap.c                      | 40 +++++++++++++++++++++++++++---
 t/t6113-rev-list-bitmap-filters.sh |  7 ++++++
 2 files changed, 43 insertions(+), 4 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index 196d38c91d..e33805e076 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c

@@ -925,6 +925,29 @@ static void filter_bitmap_object_type(struct bitmap_index *bitmap_git,
 	}
 }
 
+static int filter_supported(struct list_objects_filter_options *filter)
+{
+	int i;
+
+	switch (filter->choice) {
+	case LOFC_BLOB_NONE:
+	case LOFC_BLOB_LIMIT:
+	case LOFC_OBJECT_TYPE:
+		return 1;
+	case LOFC_TREE_DEPTH:
+		if (filter->tree_exclude_depth == 0)
+			return 1;
+		return 0;
+	case LOFC_COMBINE:
+		for (i = 0; i < filter->sub_nr; i++)
+			if (!filter_supported(&filter->sub[i]))
+				return 0;
+		return 1;
+	default:
+		return 0;
+	}
+}
+
 static int filter_bitmap(struct bitmap_index *bitmap_git,
 			 struct object_list *tip_objects,
 			 struct bitmap *to_filter,

@@ -932,6 +955,8 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,
 {
 	if (!filter || filter->choice == LOFC_DISABLED)
 		return 0;
+	if (!filter_supported(filter))
+		return -1;
 
 	if (filter->choice == LOFC_BLOB_NONE) {
 		if (bitmap_git)

@@ -948,8 +973,7 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,
 		return 0;
 	}
 
-	if (filter->choice == LOFC_TREE_DEPTH &&
-	    filter->tree_exclude_depth == 0) {
+	if (filter->choice == LOFC_TREE_DEPTH) {
 		if (bitmap_git)
 			filter_bitmap_tree_depth(bitmap_git, tip_objects,
 						 to_filter,

@@ -965,8 +989,16 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,
 		return 0;
 	}
 
-	/* filter choice not handled */
-	return -1;
+	if (filter->choice == LOFC_COMBINE) {
+		int i;
+		for (i = 0; i < filter->sub_nr; i++) {
+			filter_bitmap(bitmap_git, tip_objects, to_filter,
+				      &filter->sub[i]);
+		}
+		return 0;
+	}
+
+	BUG("unsupported filter choice");
 }
 
 static int can_filter_bitmap(struct list_objects_filter_options *filter)

diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh
index fb66735ac8..cb9db7df6f 100755
--- a/t/t6113-rev-list-bitmap-filters.sh
+++ b/t/t6113-rev-list-bitmap-filters.sh

@@ -98,4 +98,11 @@ test_expect_success 'object:type filter' '
 	test_bitmap_traversal expect actual
 '
 
+test_expect_success 'combine filter' '
+	git rev-list --objects --filter=blob:limit=1000 --filter=object:type=blob tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=blob:limit=1000 --filter=object:type=blob tag >actual &&
+	test_bitmap_traversal expect actual
+'
+
 test_done

-- 
2.30.1

The preceding commit has added a new object filter for git-rev-list(1)
which allows to filter objects by type. Implement the equivalent filter
for packfile bitmaps so that we can answer these queries fast.

Signed-off-by: Patrick Steinhardt <redacted>
---
 pack-bitmap.c                      | 28 +++++++++++++++++++++++++---
 t/t6113-rev-list-bitmap-filters.sh | 25 ++++++++++++++++++++++++-
 2 files changed, 49 insertions(+), 4 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index 1f69b5fa85..196d38c91d 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c

@@ -779,9 +779,6 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
 	eword_t mask;
 	uint32_t i;
 
-	if (type != OBJ_BLOB && type != OBJ_TREE)
-		BUG("filter_bitmap_exclude_type: unsupported type '%d'", type);
-
 	/*
 	 * The non-bitmap version of this filter never removes
 	 * objects which the other side specifically asked for,

@@ -911,6 +908,23 @@ static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git,
 				   OBJ_BLOB);
 }
 
+static void filter_bitmap_object_type(struct bitmap_index *bitmap_git,
+				      struct object_list *tip_objects,
+				      struct bitmap *to_filter,
+				      enum object_type object_type)
+{
+	enum object_type t;
+
+	if (object_type < OBJ_COMMIT || object_type > OBJ_TAG)
+		BUG("filter_bitmap_object_type given invalid object");
+
+	for (t = OBJ_COMMIT; t <= OBJ_TAG; t++) {
+		if (t == object_type)
+			continue;
+		filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, t);
+	}
+}
+
 static int filter_bitmap(struct bitmap_index *bitmap_git,
 			 struct object_list *tip_objects,
 			 struct bitmap *to_filter,

@@ -943,6 +957,14 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,
 		return 0;
 	}
 
+	if (filter->choice == LOFC_OBJECT_TYPE) {
+		if (bitmap_git)
+			filter_bitmap_object_type(bitmap_git, tip_objects,
+						  to_filter,
+						  filter->object_type);
+		return 0;
+	}
+
 	/* filter choice not handled */
 	return -1;
 }

diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh
index 3f889949ca..fb66735ac8 100755
--- a/t/t6113-rev-list-bitmap-filters.sh
+++ b/t/t6113-rev-list-bitmap-filters.sh

@@ -10,7 +10,8 @@ test_expect_success 'set up bitmapped repo' '
 	test_commit much-larger-blob-one &&
 	git repack -adb &&
 	test_commit two &&
-	test_commit much-larger-blob-two
+	test_commit much-larger-blob-two &&
+	git tag tag
 '
 
 test_expect_success 'filters fallback to non-bitmap traversal' '

@@ -75,4 +76,26 @@ test_expect_success 'tree:1 filter' '
 	test_cmp expect actual
 '
 
+test_expect_success 'object:type filter' '
+	git rev-list --objects --filter=object:type=tag tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=tag tag >actual &&
+	test_cmp expect actual &&
+
+	git rev-list --objects --filter=object:type=commit tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=commit tag >actual &&
+	test_bitmap_traversal expect actual &&
+
+	git rev-list --objects --filter=object:type=tree tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=tree tag >actual &&
+	test_bitmap_traversal expect actual &&
+
+	git rev-list --objects --filter=object:type=blob tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=blob tag >actual &&
+	test_bitmap_traversal expect actual
+'
+
 test_done

-- 
2.30.1

When providing an object filter, it is currently impossible to also
filter provided items. E.g. when executing `git rev-list HEAD` , the
commit this reference points to will be treated as user-provided and is
thus excluded from the filtering mechanism. This makes it harder than
necessary to properly use the new `--filter=object:type` filter given
that even if the user wants to only see blobs, he'll still see commits
of provided references.

Improve this by introducing a new `--filter-provided` option to the
git-rev-parse(1) command. If given, then all user-provided references
will be subject to filtering.

Signed-off-by: Patrick Steinhardt <redacted>
---
 builtin/rev-list.c                  | 14 ++++++++++++++
 list-objects-filter-options.h       |  6 ++++++
 pack-bitmap.c                       |  3 ++-
 t/t6112-rev-list-filters-objects.sh | 28 ++++++++++++++++++++++++++++
 t/t6113-rev-list-bitmap-filters.sh  | 22 ++++++++++++++++++++++
 5 files changed, 72 insertions(+), 1 deletion(-)

diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index b4d8ea0a35..0f959b266d 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c

@@ -599,6 +599,10 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			list_objects_filter_set_no_filter(&filter_options);
 			continue;
 		}
+		if (!strcmp(arg, "--filter-provided")) {
+			filter_options.filter_wants = 1;
+			continue;
+		}
 		if (!strcmp(arg, "--filter-print-omitted")) {
 			arg_print_omitted = 1;
 			continue;

@@ -694,6 +698,16 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			return show_bisect_vars(&info, reaches, all);
 	}
 
+	if (filter_options.filter_wants) {
+		struct commit_list *c;
+		for (i = 0; i < revs.pending.nr; i++) {
+			struct object_array_entry *pending = revs.pending.objects + i;
+			pending->item->flags |= NOT_USER_GIVEN;
+		}
+		for (c = revs.commits; c; c = c->next)
+			c->item->object.flags |= NOT_USER_GIVEN;
+	}
+
 	if (arg_print_omitted)
 		oidset_init(&omitted_objects, DEFAULT_OIDSET_SIZE);
 	if (arg_missing_action == MA_PRINT)

diff --git a/list-objects-filter-options.h b/list-objects-filter-options.h
index 4d0d0588cc..5e609e307a 100644
--- a/list-objects-filter-options.h
+++ b/list-objects-filter-options.h

@@ -42,6 +42,12 @@ struct list_objects_filter_options {
 	 */
 	enum list_objects_filter_choice choice;
 
+	/*
+	 * "--filter-provided" was given by the user, instructing us to also
+	 * filter all explicitly provided objects.
+	 */
+	unsigned int filter_wants : 1;
+
 	/*
 	 * Choice is LOFC_DISABLED because "--no-filter" was requested.
 	 */

diff --git a/pack-bitmap.c b/pack-bitmap.c
index e33805e076..5ff800316b 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c

@@ -1101,7 +1101,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
 	if (haves_bitmap)
 		bitmap_and_not(wants_bitmap, haves_bitmap);
 
-	filter_bitmap(bitmap_git, wants, wants_bitmap, filter);
+	filter_bitmap(bitmap_git, (filter && filter->filter_wants) ? NULL : wants,
+		      wants_bitmap, filter);
 
 	bitmap_git->result = wants_bitmap;
 	bitmap_git->haves = haves_bitmap;

diff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh
index c79ec04060..47c558ab0e 100755
--- a/t/t6112-rev-list-filters-objects.sh
+++ b/t/t6112-rev-list-filters-objects.sh

@@ -207,6 +207,34 @@ test_expect_success 'verify object:type=tag prints tag' '
 	test_cmp expected actual
 '
 
+test_expect_success 'verify object:type=blob prints only blob with --filter-provided' '
+	printf "%s blob\n" $(git -C object-type rev-parse HEAD:blob) >expected &&
+	git -C object-type rev-list --objects \
+		--filter=object:type=blob --filter-provided HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=tree prints only tree with --filter-provided' '
+	printf "%s \n" $(git -C object-type rev-parse HEAD^{tree}) >expected &&
+	git -C object-type rev-list --objects \
+		--filter=object:type=tree HEAD --filter-provided >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=commit prints only commit with --filter-provided' '
+	git -C object-type rev-parse HEAD >expected &&
+	git -C object-type rev-list --objects \
+		--filter=object:type=commit --filter-provided HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=tag prints only tag with --filter-provided' '
+	printf "%s tag\n" $(git -C object-type rev-parse tag) >expected &&
+	git -C object-type rev-list --objects \
+		--filter=object:type=tag --filter-provided tag >actual &&
+	test_cmp expected actual
+'
+
 # Test sparse:path=<path> filter.
 # !!!!
 # NOTE: sparse:path filter support has been dropped for security reasons,

diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh
index cb9db7df6f..fe3df0ee14 100755
--- a/t/t6113-rev-list-bitmap-filters.sh
+++ b/t/t6113-rev-list-bitmap-filters.sh

@@ -98,6 +98,28 @@ test_expect_success 'object:type filter' '
 	test_bitmap_traversal expect actual
 '
 
+test_expect_success 'object:type filter with --filter-provided' '
+	git rev-list --objects --filter=object:type=tag --filter-provided tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=tag --filter-provided tag >actual &&
+	test_cmp expect actual &&
+
+	git rev-list --objects --filter=object:type=commit --filter-provided tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=commit --filter-provided tag >actual &&
+	test_bitmap_traversal expect actual &&
+
+	git rev-list --objects --filter=object:type=tree --filter-provided tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=tree --filter-provided tag >actual &&
+	test_bitmap_traversal expect actual &&
+
+	git rev-list --objects --filter=object:type=blob --filter-provided tag >expect &&
+	git rev-list --use-bitmap-index \
+		     --objects --filter=object:type=blob --filter-provided tag >actual &&
+	test_bitmap_traversal expect actual
+'
+
 test_expect_success 'combine filter' '
 	git rev-list --objects --filter=blob:limit=1000 --filter=object:type=blob tag >expect &&
 	git rev-list --use-bitmap-index \

-- 
2.30.1

On Mon, Mar 01, 2021 at 01:20:26PM +0100, Patrick Steinhardt wrote:

Altogether, this ends up with the following queries, both of which have
been executed in a well-packed linux.git repository:

    # Previous query which uses object names as a heuristic to filter
    # non-blob objects, which bars us from using bitmap indices because
    # they cannot print paths.
    $ time git rev-list --objects --filter=blob:limit=200 \
        --object-names --all | sed -r '/^.{,41}$/d' | wc -l
    4502300

    real 1m23.872s
    user 1m30.076s
    sys  0m6.002s

    # New query.
    $ time git rev-list --objects --filter-provided \
        --filter=object:type=blob --filter=blob:limit=200 \
        --use-bitmap-index --all | wc -l
    22585

    real 0m19.216s
    user 0m16.768s
    sys  0m2.450s

Those produce very different answers. I guess because in the first one,
you still have a bunch of tree objects, too. You'd do much better to get
the actual types from cat-file, and filter on that. That also lets you
use bitmaps for the traversal portion. E.g.:

  $ time git rev-list --use-bitmap-index --objects --filter=blob:limit=200 --all |
         git cat-file --buffer --batch-check='%(objecttype) %(objectname)' |
	 perl -lne 'print $1 if /^blob (.*)/' | wc -l
  14966
  
  real	0m6.248s
  user	0m7.810s
  sys	0m0.440s

which is faster than what you showed above (this is on linux.git, but my
result is different; maybe you have more refs than me?). But we should
be able to do better purely internally, so I suspect my computer is just
faster (or maybe your extra refs just aren't well-covered by bitmaps).
Running with your patches I get:

  $ time git rev-list --objects --use-bitmap-index --all \
             --filter-provided --filter=object:type=blob \
	     --filter=blob:limit=200 | wc -l
  16339

  real	0m1.309s
  user	0m1.234s
  sys	0m0.079s

which is indeed faster. It's quite curious that the answer is not the
same, though! I think yours has some bugs. If I sort and diff the
results, I see some commits mentioned in the output. Perhaps this is
--filter-provided not working, as they all seem to be ref tips.

To be able to more efficiently answer this query, I've implemented
multiple things:

- A new object type filter `--filter=object:type=<type>` for
  git-rev-list(1), which is implemented both for normal graph walks and
  for the packfile bitmap index.

- Given that above usecase requires two filters (the object type
  and blob size filters), bitmap filters were extended to support
  combined filters.

That's probably reasonable, especially because it lets us use bitmaps. I
do have a dream that we'll eventually be able to support more extensive
formatting via log/rev-list, which would allow:

  git rev-list --use-bitmap-index --objects --all \
               --format=%(objecttype) %(objectname) |
  perl -ne 'print $1 if /^blob (.*)/'

That should be faster than the separate cat-file (which has to re-lookup
each object, in addition to the extra pipe overhead), but I expect the
--filter solution should always be faster still, as it can very quickly
eliminate the majority of the objects at the bitmap level.

Yeah, this "user-provided" behavior was quite a surprise to me when I
started implementing the bitmap versions of the existing filters. It's
nice to have the option to specify which you want.

-Peff

On Mon, Mar 01, 2021 at 01:20:26PM +0100, Patrick Steinhardt wrote:

I understand what you're looking for here, but I worry that '--filter'
might be too leaky of an abstraction.

I was a little surprised to learn that you can clone a repository with
--filter=object:type=tree (excluding commits), but it does work. I'm
fine reusing a lot of the object filtering code if it makes this an
easier task, but I think it may be worthwhile to hide this new kind of
filter from upload-pack.

Nice. We didn't do this since the only previously supported filters were
blob:none and tree:0 (the latter implying the former), so there was no
need.

Thanks,
Taylor

On Wed, Mar 10, 2021 at 04:58:16PM -0500, Taylor Blau wrote:

On Mon, Mar 01, 2021 at 01:20:26PM +0100, Patrick Steinhardt wrote:

quoted

- A new object type filter `--filter=object:type=<type>` for
  git-rev-list(1), which is implemented both for normal graph walks and
  for the packfile bitmap index.

I understand what you're looking for here, but I worry that '--filter'
might be too leaky of an abstraction.

I was a little surprised to learn that you can clone a repository with
--filter=object:type=tree (excluding commits), but it does work. I'm
fine reusing a lot of the object filtering code if it makes this an
easier task, but I think it may be worthwhile to hide this new kind of
filter from upload-pack.

I had a similar thought, but wouldn't the existing uploadpackfilter
config take care of this?

I guess the catch-all "allow" option defaults to "true", so we'd support
any new filters that are added. Which seems like a poor choice in
general, but flipping it would mean that servers have to update their
config.

I do wonder if it's that bad for clients to be able to specify something
like this, though. Even though there's not that much use for it with a
regular partial clone, it could conceivably used for some special cases.
I do think it would be more useful if you could OR together multiple
types. Asking for "commits|tags|trees" is really the same as the already
useful "blob:none". And "commits|tags" is the same as tree:depth=0.

-Peff

On Wed, Mar 10, 2021 at 04:39:22PM -0500, Jeff King wrote:

On Mon, Mar 01, 2021 at 01:20:26PM +0100, Patrick Steinhardt wrote:

quoted

Altogether, this ends up with the following queries, both of which have
been executed in a well-packed linux.git repository:

    # Previous query which uses object names as a heuristic to filter
    # non-blob objects, which bars us from using bitmap indices because
    # they cannot print paths.
    $ time git rev-list --objects --filter=blob:limit=200 \
        --object-names --all | sed -r '/^.{,41}$/d' | wc -l
    4502300

    real 1m23.872s
    user 1m30.076s
    sys  0m6.002s

    # New query.
    $ time git rev-list --objects --filter-provided \
        --filter=object:type=blob --filter=blob:limit=200 \
        --use-bitmap-index --all | wc -l
    22585

    real 0m19.216s
    user 0m16.768s
    sys  0m2.450s

Those produce very different answers. I guess because in the first one,
you still have a bunch of tree objects, too. You'd do much better to get
the actual types from cat-file, and filter on that. That also lets you
use bitmaps for the traversal portion. E.g.:

They do provide different answers, and you're right that `--batch-check`
would have helped to filter by type. Your idea doesn't really work in my
usecase though to identify LFS pointers, at least not without additional
tooling on top of what you've provided. There'd at least need to be two
git-cat-file(1) processes: one to do the `--batch-check` thing to
actually filter by object type, and one to then read the actual LFS
pointer candidates from disk in order to see whether they are LFS
pointers or not.

Actually, we currently are doing something similar to that at GitLab: we
list all potential candidates via git-rev-list(1), write the output into
`git-cat-file --batch-check`, and anything that is a blob then gets
forwarded into `git-cat-file --batch`.

  $ time git rev-list --use-bitmap-index --objects --filter=blob:limit=200 --all |
         git cat-file --buffer --batch-check='%(objecttype) %(objectname)' |
	 perl -lne 'print $1 if /^blob (.*)/' | wc -l
  14966
  
  real	0m6.248s
  user	0m7.810s
  sys	0m0.440s

which is faster than what you showed above (this is on linux.git, but my
result is different; maybe you have more refs than me?). But we should
be able to do better purely internally, so I suspect my computer is just
faster (or maybe your extra refs just aren't well-covered by bitmaps).
Running with your patches I get:

I've got quite a beefy machine with a Ryzen 3 5800X, and I did do a `git
repack -Adfb` right before doig benchmarks. I do have the stable kernel
repository added though, which accounts for quite a lot of additional
references (3938) and objects (9.3M).

  $ time git rev-list --objects --use-bitmap-index --all \
             --filter-provided --filter=object:type=blob \
	     --filter=blob:limit=200 | wc -l
  16339

  real	0m1.309s
  user	0m1.234s
  sys	0m0.079s

which is indeed faster. It's quite curious that the answer is not the
same, though! I think yours has some bugs. If I sort and diff the
results, I see some commits mentioned in the output. Perhaps this is
--filter-provided not working, as they all seem to be ref tips.

I noticed it, too, and couldn't yet find an answer why that is.
Honestly, I found the NOT_USER_GIVEN flag quite confusing and I'm not at
all sure whether I've got all cases covered correctly. The previous was
how this was handled (`USER_GIVEN` instead of `NOT_USER_GIVEN`) would've
been easier to figure out for this specific usecase. But I guess it was
converted due to specific reasons.

I'll invest some more time to figure out what's happening here.

quoted

To be able to more efficiently answer this query, I've implemented
multiple things:

- A new object type filter `--filter=object:type=<type>` for
  git-rev-list(1), which is implemented both for normal graph walks and
  for the packfile bitmap index.

- Given that above usecase requires two filters (the object type
  and blob size filters), bitmap filters were extended to support
  combined filters.

That's probably reasonable, especially because it lets us use bitmaps. I
do have a dream that we'll eventually be able to support more extensive
formatting via log/rev-list, which would allow:

  git rev-list --use-bitmap-index --objects --all \
               --format=%(objecttype) %(objectname) |
  perl -ne 'print $1 if /^blob (.*)/'

That should be faster than the separate cat-file (which has to re-lookup
each object, in addition to the extra pipe overhead), but I expect the
--filter solution should always be faster still, as it can very quickly
eliminate the majority of the objects at the bitmap level.

That'd be nice, even though it wouldn't help in my particular usecase: I
need to read each candidate blob to see whether it's an LFS pointer or
not anyway.

quoted

- git-rev-list(1) doesn't filter user-provided objects and always prints
  them. I don't want the listed commits though and only their referenced
  potential LFS blobs. So I've added a new flag `--filter-provided`
  which marks all provided objects as not-user-provided such that they
  get filtered the same as all the other objects.

Yeah, this "user-provided" behavior was quite a surprise to me when I
started implementing the bitmap versions of the existing filters. It's
nice to have the option to specify which you want.

-Peff

Patrick

On Wed, Mar 10, 2021 at 05:19:44PM -0500, Jeff King wrote:

On Wed, Mar 10, 2021 at 04:58:16PM -0500, Taylor Blau wrote:

quoted

On Mon, Mar 01, 2021 at 01:20:26PM +0100, Patrick Steinhardt wrote:

quoted

- A new object type filter `--filter=object:type=<type>` for
  git-rev-list(1), which is implemented both for normal graph walks and
  for the packfile bitmap index.

I understand what you're looking for here, but I worry that '--filter'
might be too leaky of an abstraction.

I was a little surprised to learn that you can clone a repository with
--filter=object:type=tree (excluding commits), but it does work. I'm
fine reusing a lot of the object filtering code if it makes this an
easier task, but I think it may be worthwhile to hide this new kind of
filter from upload-pack.

I had a similar thought, but wouldn't the existing uploadpackfilter
config take care of this?

I guess the catch-all "allow" option defaults to "true", so we'd support
any new filters that are added. Which seems like a poor choice in
general, but flipping it would mean that servers have to update their
config.

I do wonder if it's that bad for clients to be able to specify something
like this, though. Even though there's not that much use for it with a
regular partial clone, it could conceivably used for some special cases.
I do think it would be more useful if you could OR together multiple
types. Asking for "commits|tags|trees" is really the same as the already
useful "blob:none". And "commits|tags" is the same as tree:depth=0.

I did waste a few thoughts on how this should be handled. I see two ways
of doing it:

    - We could just implement the new `object:type` filter such that it
      directly supports OR'ing. That's the easy way to do it, but it's
      inflexible.

    - We could extend combined filters to support OR-semantics in
      addition to the current AND-semantics. In the end, that'd be a
      much more flexible approach and potentially allow additional
      usecases.

I lean more towards the latter as it feels like the better design. But
it's more involved, and I'm not sure I want to do it as part of this
patch series.

Patrick

On Thu, Mar 11, 2021 at 03:38:11PM +0100, Patrick Steinhardt wrote:

quoted

Those produce very different answers. I guess because in the first one,
you still have a bunch of tree objects, too. You'd do much better to get
the actual types from cat-file, and filter on that. That also lets you
use bitmaps for the traversal portion. E.g.:

They do provide different answers, and you're right that `--batch-check`
would have helped to filter by type. Your idea doesn't really work in my
usecase though to identify LFS pointers, at least not without additional
tooling on top of what you've provided. There'd at least need to be two
git-cat-file(1) processes: one to do the `--batch-check` thing to
actually filter by object type, and one to then read the actual LFS
pointer candidates from disk in order to see whether they are LFS
pointers or not.

Actually, we currently are doing something similar to that at GitLab: we
list all potential candidates via git-rev-list(1), write the output into
`git-cat-file --batch-check`, and anything that is a blob then gets
forwarded into `git-cat-file --batch`.

You'd need that final cat-file with your patch, too, though. So I think
it makes sense to think about "generate the list of blobs" as the
primary action.

You can of course do the type and content dump as a single cat-file, but
in my experience that is much slower (because we waste time dumping
object content that the caller ultimately won't care about).

Thinking in the opposite direction, if we are filtering by type via
cat-file, we could do the size filter there, too. So:

  git rev-list --use-bitmap-index --objects --all |
  git cat-file --batch-check='%(objecttype) %(objectsize) %(objectname)' |
  perl -lne 'print $2 if /^blob (\d+) (.*)/ && $1 < 200'

which produces the same answer as my earlier:

quoted

  $ time git rev-list --use-bitmap-index --objects --filter=blob:limit=200 --all |
         git cat-file --buffer --batch-check='%(objecttype) %(objectname)' |
	 perl -lne 'print $1 if /^blob (.*)/' | wc -l

but takes about twice as long. Which is really just a roundabout way of
saying that yes, shoving things into "rev-list" can provide substantial
speedups. :)

quoted

which is faster than what you showed above (this is on linux.git, but my
result is different; maybe you have more refs than me?). But we should
be able to do better purely internally, so I suspect my computer is just
faster (or maybe your extra refs just aren't well-covered by bitmaps).
Running with your patches I get:

I've got quite a beefy machine with a Ryzen 3 5800X, and I did do a `git
repack -Adfb` right before doig benchmarks. I do have the stable kernel
repository added though, which accounts for quite a lot of additional
references (3938) and objects (9.3M).

Yeah, I wondered if it was something like that. Mine is just
torvalds/linux.git. Fetching stable/linux.git from kernel.org, running
"git repack -adb" on the result, and then repeating my timings gets me
numbers close to yours.

quoted

which is indeed faster. It's quite curious that the answer is not the
same, though! I think yours has some bugs. If I sort and diff the
results, I see some commits mentioned in the output. Perhaps this is
--filter-provided not working, as they all seem to be ref tips.

I noticed it, too, and couldn't yet find an answer why that is.
Honestly, I found the NOT_USER_GIVEN flag quite confusing and I'm not at
all sure whether I've got all cases covered correctly. The previous was
how this was handled (`USER_GIVEN` instead of `NOT_USER_GIVEN`) would've
been easier to figure out for this specific usecase. But I guess it was
converted due to specific reasons.

I'll invest some more time to figure out what's happening here.

Thanks. I also scratched my head at NOT_USER_GIVEN. I haven't looked at
this part of the filter code very much, but it seems like that is a
recipe for accidentally marking a commit as NOT_USER_GIVEN if we
traverse to it (even if it was originally _also_ given by the user).

-Peff

quoted

That's probably reasonable, especially because it lets us use bitmaps. I
do have a dream that we'll eventually be able to support more extensive
formatting via log/rev-list, which would allow:

  git rev-list --use-bitmap-index --objects --all \
               --format=%(objecttype) %(objectname) |
  perl -ne 'print $1 if /^blob (.*)/'

That should be faster than the separate cat-file (which has to re-lookup
each object, in addition to the extra pipe overhead), but I expect the
--filter solution should always be faster still, as it can very quickly
eliminate the majority of the objects at the bitmap level.

That'd be nice, even though it wouldn't help in my particular usecase: I
need to read each candidate blob to see whether it's an LFS pointer or
not anyway.

I think it works out roughly the same as the --filter solution, in the
sense that both generate a list of candidate blobs that you'd read with
"cat-file --batch" (but of course it's still slower).

-Peff

On Thu, Mar 11, 2021 at 03:43:39PM +0100, Patrick Steinhardt wrote:

quoted

I do wonder if it's that bad for clients to be able to specify something
like this, though. Even though there's not that much use for it with a
regular partial clone, it could conceivably used for some special cases.
I do think it would be more useful if you could OR together multiple
types. Asking for "commits|tags|trees" is really the same as the already
useful "blob:none". And "commits|tags" is the same as tree:depth=0.

I did waste a few thoughts on how this should be handled. I see two ways
of doing it:

    - We could just implement the new `object:type` filter such that it
      directly supports OR'ing. That's the easy way to do it, but it's
      inflexible.

    - We could extend combined filters to support OR-semantics in
      addition to the current AND-semantics. In the end, that'd be a
      much more flexible approach and potentially allow additional
      usecases.

I lean more towards the latter as it feels like the better design. But
it's more involved, and I'm not sure I want to do it as part of this
patch series.

Yeah, I don't think that needs to be part of this series. The only thing
to consider for this series is whether it's a problem for clients to be
able to ask for type=blob from a server which has blindly turned on
uploadpack.allowFilter without restricting the types.

My gut is to say yes. Even if we don't have a particular use, I don't
think it hurts (and in general, I think people running public servers
with bitmaps really ought to set uploadpackfilter.allow=false anyway,
because stuff like non-zero tree-depth filters are expensive).

-Peff

On Wed, Mar 10, 2021 at 04:39:22PM -0500, Jeff King wrote:

On Mon, Mar 01, 2021 at 01:20:26PM +0100, Patrick Steinhardt wrote:

quoted

Altogether, this ends up with the following queries, both of which have
been executed in a well-packed linux.git repository:

    # Previous query which uses object names as a heuristic to filter
    # non-blob objects, which bars us from using bitmap indices because
    # they cannot print paths.
    $ time git rev-list --objects --filter=blob:limit=200 \
        --object-names --all | sed -r '/^.{,41}$/d' | wc -l
    4502300

    real 1m23.872s
    user 1m30.076s
    sys  0m6.002s

    # New query.
    $ time git rev-list --objects --filter-provided \
        --filter=object:type=blob --filter=blob:limit=200 \
        --use-bitmap-index --all | wc -l
    22585

    real 0m19.216s
    user 0m16.768s
    sys  0m2.450s

Those produce very different answers. I guess because in the first one,
you still have a bunch of tree objects, too. You'd do much better to get
the actual types from cat-file, and filter on that. That also lets you
use bitmaps for the traversal portion. E.g.:

  $ time git rev-list --use-bitmap-index --objects --filter=blob:limit=200 --all |
         git cat-file --buffer --batch-check='%(objecttype) %(objectname)' |
	 perl -lne 'print $1 if /^blob (.*)/' | wc -l
  14966
  
  real	0m6.248s
  user	0m7.810s
  sys	0m0.440s

which is faster than what you showed above (this is on linux.git, but my
result is different; maybe you have more refs than me?). But we should
be able to do better purely internally, so I suspect my computer is just
faster (or maybe your extra refs just aren't well-covered by bitmaps).
Running with your patches I get:

  $ time git rev-list --objects --use-bitmap-index --all \
             --filter-provided --filter=object:type=blob \
	     --filter=blob:limit=200 | wc -l
  16339

  real	0m1.309s
  user	0m1.234s
  sys	0m0.079s

which is indeed faster. It's quite curious that the answer is not the
same, though! I think yours has some bugs. If I sort and diff the
results, I see some commits mentioned in the output. Perhaps this is
--filter-provided not working, as they all seem to be ref tips.

[snip]

I've found the issue: when converting filters to a combined filter via
`transform_to_combine_type()`, we reset the top-level filter via a call
to `memset()`. So for combined filters, the option wouldn't have taken
any effect because it got reset iff the `--filter-provided` option comes
before the second filter.

Patrick

Hi,

this is the second version of my patch series which implements a new
`object:type` filter for git-rev-parse(1) and git-upload-pack(1) and
extends support for bitmap indices to work with combined filters.

Changes compared to v1:

    - I've added a patch up front which changes the uploadpack
      documentation to explicitly document that setting
      `uploadpackfilter.allow=true` will enable all future filters. I'm
      not yet saying that this is the correct thing to do, but rather
      added this patch such that we have a proper place to discuss this
      topic. In the context of object-type filters, I do think though
      that it's not an issue to default-enable type filters: they're not
      expensive to compute anyway.

    - `uploadpackfilter.<filter>.allow` documentation was updated to
      mention the new filter.

    - A bug was fixed which caused us to reset `--filter-allowed` in
      case a normal filter was converted to a combined filter. I've
      added tests to more thoroughly verify that filters work as
      expected and also filter provided objects.

Please see the attached range-diff for more details.

Patrick

Patrick Steinhardt (8):
  uploadpack.txt: document implication of `uploadpackfilter.allow`
  revision: mark commit parents as NOT_USER_GIVEN
  list-objects: move tag processing into its own function
  list-objects: support filtering by tag and commit
  list-objects: implement object type filter
  pack-bitmap: implement object type filter
  pack-bitmap: implement combined filter
  rev-list: allow filtering of provided items

 Documentation/config/uploadpack.txt |   9 ++-
 Documentation/rev-list-options.txt  |   3 +
 builtin/rev-list.c                  |  14 ++++
 list-objects-filter-options.c       |  18 +++++
 list-objects-filter-options.h       |   8 ++
 list-objects-filter.c               | 116 ++++++++++++++++++++++++++++
 list-objects-filter.h               |   2 +
 list-objects.c                      |  32 +++++++-
 pack-bitmap.c                       |  71 +++++++++++++++--
 revision.c                          |   4 +-
 revision.h                          |   3 -
 t/t6112-rev-list-filters-objects.sh |  76 ++++++++++++++++++
 t/t6113-rev-list-bitmap-filters.sh  |  68 +++++++++++++++-
 13 files changed, 403 insertions(+), 21 deletions(-)

Range-diff against v1:
-:  ---------- > 1:  270ff80dac uploadpack.txt: document implication of `uploadpackfilter.allow`
1:  f2ce5dac89 = 2:  ddbec75986 revision: mark commit parents as NOT_USER_GIVEN
2:  9feadba124 = 3:  d8da0b24f4 list-objects: move tag processing into its own function
3:  4aa13ee83f = 4:  5545c189c5 list-objects: support filtering by tag and commit
4:  01b9fdbb9c ! 5:  acf01472af list-objects: implement object type filter
    @@ Commit message
     
         Signed-off-by: Patrick Steinhardt [off-list ref]
     
    + ## Documentation/config/uploadpack.txt ##
    +@@ Documentation/config/uploadpack.txt: uploadpackfilter.allow::
    + uploadpackfilter.<filter>.allow::
    + 	Explicitly allow or ban the object filter corresponding to
    + 	`<filter>`, where `<filter>` may be one of: `blob:none`,
    +-	`blob:limit`, `tree`, `sparse:oid`, or `combine`. If using
    +-	combined filters, both `combine` and all of the nested filter
    +-	kinds must be allowed. Defaults to `uploadpackfilter.allow`.
    ++	`blob:limit`, `object:type`, `tree`, `sparse:oid`, or `combine`.
    ++	If using combined filters, both `combine` and all of the nested
    ++	filter kinds must be allowed. Defaults to `uploadpackfilter.allow`.
    + 
    + uploadpackfilter.tree.maxDepth::
    + 	Only allow `--filter=tree:<n>` when `<n>` is no more than the value of
    +
      ## Documentation/rev-list-options.txt ##
     @@ Documentation/rev-list-options.txt: or units.  n may be zero.  The suffixes k, m, and g can be used to name
      units in KiB, MiB, or GiB.  For example, 'blob:limit=1k' is the same
5:  c97fd28d8f = 6:  8073ab665b pack-bitmap: implement object type filter
6:  fe2b7a1e55 = 7:  fac3477d97 pack-bitmap: implement combined filter
7:  b43bf401df ! 8:  0e26fee8b3 rev-list: allow filtering of provided items
    @@ builtin/rev-list.c: int cmd_rev_list(int argc, const char **argv, const char *pr
      		oidset_init(&omitted_objects, DEFAULT_OIDSET_SIZE);
      	if (arg_missing_action == MA_PRINT)
     
    + ## list-objects-filter-options.c ##
    +@@ list-objects-filter-options.c: static void transform_to_combine_type(
    + 		memset(filter_options, 0, sizeof(*filter_options));
    + 		filter_options->sub = sub_array;
    + 		filter_options->sub_alloc = initial_sub_alloc;
    ++		filter_options->filter_wants = sub_array[0].filter_wants;
    + 	}
    + 	filter_options->sub_nr = 1;
    + 	filter_options->choice = LOFC_COMBINE;
    +@@ list-objects-filter-options.c: void parse_list_objects_filter(
    + 		parse_error = gently_parse_list_objects_filter(
    + 			&filter_options->sub[filter_options->sub_nr - 1], arg,
    + 			&errbuf);
    ++		if (!parse_error)
    ++			filter_options->sub[filter_options->sub_nr - 1].filter_wants =
    ++				filter_options->filter_wants;
    + 	}
    + 	if (parse_error)
    + 		die("%s", errbuf.buf);
    +
      ## list-objects-filter-options.h ##
     @@ list-objects-filter-options.h: struct list_objects_filter_options {
      	 */
    @@ t/t6113-rev-list-bitmap-filters.sh: test_expect_success 'object:type filter' '
      '
      
     +test_expect_success 'object:type filter with --filter-provided' '
    -+	git rev-list --objects --filter=object:type=tag --filter-provided tag >expect &&
    ++	git rev-list --objects --filter-provided --filter=object:type=tag tag >expect &&
     +	git rev-list --use-bitmap-index \
    -+		     --objects --filter=object:type=tag --filter-provided tag >actual &&
    ++		     --objects --filter-provided --filter=object:type=tag tag >actual &&
     +	test_cmp expect actual &&
     +
    -+	git rev-list --objects --filter=object:type=commit --filter-provided tag >expect &&
    ++	git rev-list --objects --filter-provided --filter=object:type=commit tag >expect &&
     +	git rev-list --use-bitmap-index \
    -+		     --objects --filter=object:type=commit --filter-provided tag >actual &&
    ++		     --objects --filter-provided --filter=object:type=commit tag >actual &&
     +	test_bitmap_traversal expect actual &&
     +
    -+	git rev-list --objects --filter=object:type=tree --filter-provided tag >expect &&
    ++	git rev-list --objects --filter-provided --filter=object:type=tree tag >expect &&
     +	git rev-list --use-bitmap-index \
    -+		     --objects --filter=object:type=tree --filter-provided tag >actual &&
    ++		     --objects --filter-provided --filter=object:type=tree tag >actual &&
     +	test_bitmap_traversal expect actual &&
     +
    -+	git rev-list --objects --filter=object:type=blob --filter-provided tag >expect &&
    ++	git rev-list --objects --filter-provided --filter=object:type=blob tag >expect &&
     +	git rev-list --use-bitmap-index \
    -+		     --objects --filter=object:type=blob --filter-provided tag >actual &&
    ++		     --objects --filter-provided --filter=object:type=blob tag >actual &&
     +	test_bitmap_traversal expect actual
     +'
     +
      test_expect_success 'combine filter' '
      	git rev-list --objects --filter=blob:limit=1000 --filter=object:type=blob tag >expect &&
      	git rev-list --use-bitmap-index \
    +@@ t/t6113-rev-list-bitmap-filters.sh: test_expect_success 'combine filter' '
    + 	test_bitmap_traversal expect actual
    + '
    + 
    ++test_expect_success 'combine filter with --filter-provided' '
    ++	git rev-list --objects --filter-provided --filter=blob:limit=1000 --filter=object:type=blob tag >expect &&
    ++	git rev-list --use-bitmap-index \
    ++		     --objects --filter-provided --filter=blob:limit=1000 --filter=object:type=blob tag >actual &&
    ++	test_bitmap_traversal expect actual &&
    ++
    ++	git cat-file --batch-check="%(objecttype) %(objectsize)" <actual >objects &&
    ++	while read objecttype objectsize
    ++	do
    ++		test "$objecttype" = blob || return 1
    ++		test "$objectsize" -le 1000 || return 1
    ++	done <objects
    ++'
    ++
    + test_done
-- 
2.30.2

When `uploadpackfilter.allow` is set to `true`, it means that filters
are enabled by default except in the case where a filter is explicitly
disabled via `uploadpackilter.<filter>.allow`. This option will not only
enable the currently supported set of filters, but also any filters
which get added in the future. As such, an admin which wants to have
tight control over which filters are allowed and which aren't probably
shouldn't ever set `uploadpackfilter.allow=true`.

Amend the documentation to make the ramifications more explicit so that
admins are aware of this.

Signed-off-by: Patrick Steinhardt <redacted>
---
 Documentation/config/uploadpack.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/Documentation/config/uploadpack.txt b/Documentation/config/uploadpack.txt
index b0d761282c..6729a072ea 100644
--- a/Documentation/config/uploadpack.txt
+++ b/Documentation/config/uploadpack.txt

@@ -59,7 +59,8 @@ uploadpack.allowFilter::
 
 uploadpackfilter.allow::
 	Provides a default value for unspecified object filters (see: the
-	below configuration variable).
+	below configuration variable). If set to `true`, this will also
+	enable all filters which get added in the future.
 	Defaults to `true`.
 
 uploadpackfilter.<filter>.allow::

-- 
2.30.2

The NOT_USER_GIVEN flag of an object marks whether a flag was explicitly
provided by the user or not. The most important use case for this is
when filtering objects: only objects that were not explicitly requested
will get filtered.

The flag is currently only set for blobs and trees, which has been fine
given that there are no filters for tags or commits currently. We're
about to extend filtering capabilities to add object type filter though,
which requires us to set up the NOT_USER_GIVEN flag correctly -- if it's
not set, the object wouldn't get filtered at all.

Mark unseen commit parents as NOT_USER_GIVEN when processing parents.
Like this, explicitly provided parents stay user-given and thus
unfiltered, while parents which get loaded as part of the graph walk
can be filtered.

This commit shouldn't have any user-visible impact yet as there is no
logic to filter commits yet.

Signed-off-by: Patrick Steinhardt <redacted>
---
 revision.c | 4 ++--
 revision.h | 3 ---
 2 files changed, 2 insertions(+), 5 deletions(-)

diff --git a/revision.c b/revision.c
index b78733f508..26f422f50d 100644
--- a/revision.c
+++ b/revision.c

@@ -1123,7 +1123,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,
 				mark_parents_uninteresting(p);
 			if (p->object.flags & SEEN)
 				continue;
-			p->object.flags |= SEEN;
+			p->object.flags |= (SEEN | NOT_USER_GIVEN);
 			if (list)
 				commit_list_insert_by_date(p, list);
 			if (queue)

@@ -1165,7 +1165,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,
 		}
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
-			p->object.flags |= SEEN;
+			p->object.flags |= (SEEN | NOT_USER_GIVEN);
 			if (list)
 				commit_list_insert_by_date(p, list);
 			if (queue)

diff --git a/revision.h b/revision.h
index e6be3c845e..f1f324a19b 100644
--- a/revision.h
+++ b/revision.h

@@ -44,9 +44,6 @@
 /*
  * Indicates object was reached by traversal. i.e. not given by user on
  * command-line or stdin.
- * NEEDSWORK: NOT_USER_GIVEN doesn't apply to commits because we only support
- * filtering trees and blobs, but it may be useful to support filtering commits
- * in the future.
  */
 #define NOT_USER_GIVEN	(1u<<25)
 #define TRACK_LINEAR	(1u<<26)

-- 
2.30.2

Object filters currently only support filtering blobs or trees based on
some criteria. This commit lays the foundation to also allow filtering
of tags and commits.

No change in behaviour is expected from this commit given that there are
no filters yet for those object types.

Signed-off-by: Patrick Steinhardt <redacted>
---
 list-objects-filter.c | 40 ++++++++++++++++++++++++++++++++++++++++
 list-objects-filter.h |  2 ++
 list-objects.c        | 24 +++++++++++++++++++++---
 3 files changed, 63 insertions(+), 3 deletions(-)

diff --git a/list-objects-filter.c b/list-objects-filter.c
index 4ec0041cfb..7def039435 100644
--- a/list-objects-filter.c
+++ b/list-objects-filter.c

@@ -82,6 +82,16 @@ static enum list_objects_filter_result filter_blobs_none(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_BEGIN_TREE:
 		assert(obj->type == OBJ_TREE);
 		/* always include all tree objects */

@@ -173,6 +183,16 @@ static enum list_objects_filter_result filter_trees_depth(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_END_TREE:
 		assert(obj->type == OBJ_TREE);
 		filter_data->current_depth--;

@@ -267,6 +287,16 @@ static enum list_objects_filter_result filter_blobs_limit(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_BEGIN_TREE:
 		assert(obj->type == OBJ_TREE);
 		/* always include all tree objects */

@@ -371,6 +401,16 @@ static enum list_objects_filter_result filter_sparse(
 	default:
 		BUG("unknown filter_situation: %d", filter_situation);
 
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		/* always include all tag objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		/* always include all commit objects */
+		return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
 	case LOFS_BEGIN_TREE:
 		assert(obj->type == OBJ_TREE);
 		dtype = DT_DIR;

diff --git a/list-objects-filter.h b/list-objects-filter.h
index cfd784e203..9e98814111 100644
--- a/list-objects-filter.h
+++ b/list-objects-filter.h

@@ -55,6 +55,8 @@ enum list_objects_filter_result {
 };
 
 enum list_objects_filter_situation {
+	LOFS_COMMIT,
+	LOFS_TAG,
 	LOFS_BEGIN_TREE,
 	LOFS_END_TREE,
 	LOFS_BLOB

diff --git a/list-objects.c b/list-objects.c
index 093adf85b1..3b63dfd4f2 100644
--- a/list-objects.c
+++ b/list-objects.c

@@ -218,8 +218,16 @@ static void process_tag(struct traversal_context *ctx,
 			struct strbuf *base,
 			const char *name)
 {
-	tag->object.flags |= SEEN;
-	ctx->show_object(&tag->object, name, ctx->show_data);
+	enum list_objects_filter_result r;
+
+	r = list_objects_filter__filter_object(ctx->revs->repo, LOFS_TAG,
+					       &tag->object, base->buf,
+					       &base->buf[base->len],
+					       ctx->filter);
+	if (r & LOFR_MARK_SEEN)
+		tag->object.flags |= SEEN;
+	if (r & LOFR_DO_SHOW)
+		ctx->show_object(&tag->object, name, ctx->show_data);
 }
 
 static void mark_edge_parents_uninteresting(struct commit *commit,

@@ -369,6 +377,12 @@ static void do_traverse(struct traversal_context *ctx)
 	strbuf_init(&csp, PATH_MAX);
 
 	while ((commit = get_revision(ctx->revs)) != NULL) {
+		enum list_objects_filter_result r;
+
+		r = list_objects_filter__filter_object(ctx->revs->repo,
+				LOFS_COMMIT, &commit->object,
+				NULL, NULL, ctx->filter);
+
 		/*
 		 * an uninteresting boundary commit may not have its tree
 		 * parsed yet, but we are not going to show them anyway

@@ -383,7 +397,11 @@ static void do_traverse(struct traversal_context *ctx)
 			die(_("unable to load root tree for commit %s"),
 			      oid_to_hex(&commit->object.oid));
 		}
-		ctx->show_commit(commit, ctx->show_data);
+
+		if (r & LOFR_MARK_SEEN)
+			commit->object.flags |= SEEN;
+		if (r & LOFR_DO_SHOW)
+			ctx->show_commit(commit, ctx->show_data);
 
 		if (ctx->revs->tree_blobs_in_commit_order)
 			/*

-- 
2.30.2

Move processing of tags into its own function to make the logic easier
to extend when we're going to implement filtering for tags. No change in
behaviour is expected from this commit.

Signed-off-by: Patrick Steinhardt <redacted>
---
 list-objects.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/list-objects.c b/list-objects.c
index e19589baa0..093adf85b1 100644
--- a/list-objects.c
+++ b/list-objects.c

@@ -213,6 +213,15 @@ static void process_tree(struct traversal_context *ctx,
 	free_tree_buffer(tree);
 }
 
+static void process_tag(struct traversal_context *ctx,
+			struct tag *tag,
+			struct strbuf *base,
+			const char *name)
+{
+	tag->object.flags |= SEEN;
+	ctx->show_object(&tag->object, name, ctx->show_data);
+}
+
 static void mark_edge_parents_uninteresting(struct commit *commit,
 					    struct rev_info *revs,
 					    show_edge_fn show_edge)

@@ -334,8 +343,7 @@ static void traverse_trees_and_blobs(struct traversal_context *ctx,
 		if (obj->flags & (UNINTERESTING | SEEN))
 			continue;
 		if (obj->type == OBJ_TAG) {
-			obj->flags |= SEEN;
-			ctx->show_object(obj, name, ctx->show_data);
+			process_tag(ctx, (struct tag *)obj, base, name);
 			continue;
 		}
 		if (!path)

-- 
2.30.2

While it already is possible to filter objects by some criteria in
git-rev-list(1), it is not yet possible to filter out only a specific
type of objects. This makes some filters less useful. The `blob:limit`
filter for example filters blobs such that only those which are smaller
than the given limit are returned. But it is unfit to ask only for these
smallish blobs, given that git-rev-list(1) will continue to print tags,
commits and trees.

Now that we have the infrastructure in place to also filter tags and
commits, we can improve this situation by implementing a new filter
which selects objects based on their type. Above query can thus
trivially be implemented with the following command:

    $ git rev-list --objects --filter=object:type=blob \
        --filter=blob:limit=200

Furthermore, this filter allows to optimize for certain other cases: if
for example only tags or commits have been selected, there is no need to
walk down trees.

The new filter is not yet supported in bitmaps. This is going to be
implemented in a subsequent commit.

Signed-off-by: Patrick Steinhardt <redacted>
---
 Documentation/config/uploadpack.txt |  6 +--
 Documentation/rev-list-options.txt  |  3 ++
 list-objects-filter-options.c       | 14 ++++++
 list-objects-filter-options.h       |  2 +
 list-objects-filter.c               | 76 +++++++++++++++++++++++++++++
 t/t6112-rev-list-filters-objects.sh | 48 ++++++++++++++++++
 6 files changed, 146 insertions(+), 3 deletions(-)

diff --git a/Documentation/config/uploadpack.txt b/Documentation/config/uploadpack.txt
index 6729a072ea..32fad5bbe8 100644
--- a/Documentation/config/uploadpack.txt
+++ b/Documentation/config/uploadpack.txt

@@ -66,9 +66,9 @@ uploadpackfilter.allow::
 uploadpackfilter.<filter>.allow::
 	Explicitly allow or ban the object filter corresponding to
 	`<filter>`, where `<filter>` may be one of: `blob:none`,
-	`blob:limit`, `tree`, `sparse:oid`, or `combine`. If using
-	combined filters, both `combine` and all of the nested filter
-	kinds must be allowed. Defaults to `uploadpackfilter.allow`.
+	`blob:limit`, `object:type`, `tree`, `sparse:oid`, or `combine`.
+	If using combined filters, both `combine` and all of the nested
+	filter kinds must be allowed. Defaults to `uploadpackfilter.allow`.
 
 uploadpackfilter.tree.maxDepth::
 	Only allow `--filter=tree:<n>` when `<n>` is no more than the value of

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index b1c8f86c6e..3afa8fffbd 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt

@@ -892,6 +892,9 @@ or units.  n may be zero.  The suffixes k, m, and g can be used to name
 units in KiB, MiB, or GiB.  For example, 'blob:limit=1k' is the same
 as 'blob:limit=1024'.
 +
+The form '--filter=object:type=(tag|commit|tree|blob)' omits all objects
+which are not of the requested type.
++
 The form '--filter=sparse:oid=<blob-ish>' uses a sparse-checkout
 specification contained in the blob (or blob-expression) '<blob-ish>'
 to omit blobs that would not be not required for a sparse checkout on

diff --git a/list-objects-filter-options.c b/list-objects-filter-options.c
index d2d1c81caf..bb6f6577d5 100644
--- a/list-objects-filter-options.c
+++ b/list-objects-filter-options.c

@@ -29,6 +29,8 @@ const char *list_object_filter_config_name(enum list_objects_filter_choice c)
 		return "tree";
 	case LOFC_SPARSE_OID:
 		return "sparse:oid";
+	case LOFC_OBJECT_TYPE:
+		return "object:type";
 	case LOFC_COMBINE:
 		return "combine";
 	case LOFC__COUNT:

@@ -97,6 +99,18 @@ static int gently_parse_list_objects_filter(
 		}
 		return 1;
 
+	} else if (skip_prefix(arg, "object:type=", &v0)) {
+		int type = type_from_string_gently(v0, -1, 1);
+		if (type < 0) {
+			strbuf_addstr(errbuf, _("expected 'object:type=<type>'"));
+			return 1;
+		}
+
+		filter_options->object_type = type;
+		filter_options->choice = LOFC_OBJECT_TYPE;
+
+		return 0;
+
 	} else if (skip_prefix(arg, "combine:", &v0)) {
 		return parse_combine_filter(filter_options, v0, errbuf);
 

diff --git a/list-objects-filter-options.h b/list-objects-filter-options.h
index 01767c3c96..4d0d0588cc 100644
--- a/list-objects-filter-options.h
+++ b/list-objects-filter-options.h

@@ -13,6 +13,7 @@ enum list_objects_filter_choice {
 	LOFC_BLOB_LIMIT,
 	LOFC_TREE_DEPTH,
 	LOFC_SPARSE_OID,
+	LOFC_OBJECT_TYPE,
 	LOFC_COMBINE,
 	LOFC__COUNT /* must be last */
 };

@@ -54,6 +55,7 @@ struct list_objects_filter_options {
 	char *sparse_oid_name;
 	unsigned long blob_limit_value;
 	unsigned long tree_exclude_depth;
+	enum object_type object_type;
 
 	/* LOFC_COMBINE values */
 

diff --git a/list-objects-filter.c b/list-objects-filter.c
index 7def039435..650a7c2c80 100644
--- a/list-objects-filter.c
+++ b/list-objects-filter.c

@@ -545,6 +545,81 @@ static void filter_sparse_oid__init(
 	filter->free_fn = filter_sparse_free;
 }
 
+/*
+ * A filter for list-objects to omit large blobs.
+ * And to OPTIONALLY collect a list of the omitted OIDs.
+ */
+struct filter_object_type_data {
+	enum object_type object_type;
+};
+
+static enum list_objects_filter_result filter_object_type(
+	struct repository *r,
+	enum list_objects_filter_situation filter_situation,
+	struct object *obj,
+	const char *pathname,
+	const char *filename,
+	struct oidset *omits,
+	void *filter_data_)
+{
+	struct filter_object_type_data *filter_data = filter_data_;
+
+	switch (filter_situation) {
+	default:
+		BUG("unknown filter_situation: %d", filter_situation);
+
+	case LOFS_TAG:
+		assert(obj->type == OBJ_TAG);
+		if (filter_data->object_type == OBJ_TAG)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+		return LOFR_MARK_SEEN;
+
+	case LOFS_COMMIT:
+		assert(obj->type == OBJ_COMMIT);
+		if (filter_data->object_type == OBJ_COMMIT)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+		return LOFR_MARK_SEEN;
+
+	case LOFS_BEGIN_TREE:
+		assert(obj->type == OBJ_TREE);
+
+		/*
+		 * If we only want to show commits or tags, then there is no
+		 * need to walk down trees.
+		 */
+		if (filter_data->object_type == OBJ_COMMIT ||
+		    filter_data->object_type == OBJ_TAG)
+			return LOFR_SKIP_TREE;
+
+		if (filter_data->object_type == OBJ_TREE)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+
+		return LOFR_MARK_SEEN;
+
+	case LOFS_BLOB:
+		assert(obj->type == OBJ_BLOB);
+
+		if (filter_data->object_type == OBJ_BLOB)
+			return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+		return LOFR_MARK_SEEN;
+
+	case LOFS_END_TREE:
+		return LOFR_ZERO;
+	}
+}
+
+static void filter_object_type__init(
+	struct list_objects_filter_options *filter_options,
+	struct filter *filter)
+{
+	struct filter_object_type_data *d = xcalloc(1, sizeof(*d));
+	d->object_type = filter_options->object_type;
+
+	filter->filter_data = d;
+	filter->filter_object_fn = filter_object_type;
+	filter->free_fn = free;
+}
+
 /* A filter which only shows objects shown by all sub-filters. */
 struct combine_filter_data {
 	struct subfilter *sub;

@@ -691,6 +766,7 @@ static filter_init_fn s_filters[] = {
 	filter_blobs_limit__init,
 	filter_trees_depth__init,
 	filter_sparse_oid__init,
+	filter_object_type__init,
 	filter_combine__init,
 };
 

diff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh
index 31457d13b9..c79ec04060 100755
--- a/t/t6112-rev-list-filters-objects.sh
+++ b/t/t6112-rev-list-filters-objects.sh

@@ -159,6 +159,54 @@ test_expect_success 'verify blob:limit=1m' '
 	test_must_be_empty observed
 '
 
+# Test object:type=<type> filter.
+
+test_expect_success 'setup object-type' '
+	git init object-type &&
+	echo contents >object-type/blob &&
+	git -C object-type add blob &&
+	git -C object-type commit -m commit-message &&
+	git -C object-type tag tag -m tag-message
+'
+
+test_expect_success 'verify object:type= fails with invalid type' '
+	test_must_fail git -C object-type rev-list --objects --filter=object:type= HEAD &&
+	test_must_fail git -C object-type rev-list --objects --filter=object:type=invalid HEAD
+'
+
+test_expect_success 'verify object:type=blob prints blob and commit' '
+	(
+		git -C object-type rev-parse HEAD &&
+		printf "%s blob\n" $(git -C object-type rev-parse HEAD:blob)
+	) >expected &&
+	git -C object-type rev-list --objects --filter=object:type=blob HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=tree prints tree and commit' '
+	(
+		git -C object-type rev-parse HEAD &&
+		printf "%s \n" $(git -C object-type rev-parse HEAD^{tree})
+	) >expected &&
+	git -C object-type rev-list --objects --filter=object:type=tree HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=commit prints commit' '
+	git -C object-type rev-parse HEAD >expected &&
+	git -C object-type rev-list --objects --filter=object:type=commit HEAD >actual &&
+	test_cmp expected actual
+'
+
+test_expect_success 'verify object:type=tag prints tag' '
+	(
+		git -C object-type rev-parse HEAD &&
+		printf "%s tag\n" $(git -C object-type rev-parse tag)
+	) >expected &&
+	git -C object-type rev-list --objects --filter=object:type=tag tag >actual &&
+	test_cmp expected actual
+'
+
 # Test sparse:path=<path> filter.
 # !!!!
 # NOTE: sparse:path filter support has been dropped for security reasons,