[v2,6/8] pack-bitmap: implement object type filter

Commit Message

Patrick Steinhardt March 15, 2021, 1:14 p.m. UTC

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 <[e-mail]>
---
 pack-bitmap.c                      | 28 +++++++++++++++++++++++++---
 t/t6113-rev-list-bitmap-filters.sh | 25 ++++++++++++++++++++++++-
 2 files changed, 49 insertions(+), 4 deletions(-)

Comments

Jeff King April 6, 2021, 5:48 p.m. UTC | #1

On Mon, Mar 15, 2021 at 02:14:55PM +0100, Patrick Steinhardt wrote:

> 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.

Makes sense. The implementation looks pretty sensible. One observation:

> +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);
> +	}
> +}

The OBJ_* constants are a contiguous set between COMMIT and TAG, and it
has to remain this way (because we use them to decipher the type fields
in pack files). But I don't think we've generally baked that assumption
into the code in this way.

Writing it out long-hand would be something like:

  if (t != OBJ_COMMIT)
	filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_COMMIT);
  if (t != OBJ_TREE)
	filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_TREE);

and so on, which isn't too bad. I dunno. That may be overly picky.

-Peff

Patch

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