list-objects: support for skipping tree traversal

The tree:0 filter does not need to traverse the trees that it has
filtered out, so optimize list-objects and list-objects-filter to skip
traversing the trees entirely. Before this patch, we iterated over all
children of the tree, and did nothing for all of them, which was
wasteful.

Signed-off-by: Matthew DeVore <matvore@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/list-objects-filter.c b/list-objects-filter.c
index 09b2b05d5462318353aee9133e36bd5924cfa409..765f3df3b067c5df7b98402ef4fc953edcd9179b 100644 (file)
--- a/list-objects-filter.c
+++ b/list-objects-filter.c
@@ -102,9 +102,16 @@ static enum list_objects_filter_result filter_trees_none(
 
        case LOFS_BEGIN_TREE:
        case LOFS_BLOB:
-               if (filter_data->omits)
+               if (filter_data->omits) {
                        oidset_insert(filter_data->omits, &obj->oid);
-               return LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */
+                       /* _MARK_SEEN but not _DO_SHOW (hard omit) */
+                       return LOFR_MARK_SEEN;
+               } else {
+                       /*
+                        * Not collecting omits so no need to to traverse tree.
+                        */
+                       return LOFR_SKIP_TREE | LOFR_MARK_SEEN;
+               }
 
        case LOFS_END_TREE:
                assert(obj->type == OBJ_TREE);

diff --git a/list-objects-filter.h b/list-objects-filter.h
index a963d0274ceb1ea80c9b4ba2003dfb4dd0226116..9c19875a4100d36d48237aa3aa52943647bbe5c6 100644 (file)
--- a/list-objects-filter.h
+++ b/list-objects-filter.h
@@ -20,6 +20,11 @@
  *              In general, objects should only be shown once, but
  *              this result DOES NOT imply that we mark it SEEN.
  *
+ * _SKIP_TREE : Used in LOFS_BEGIN_TREE situation - indicates that
+ *              the tree's children should not be iterated over. This
+ *              is used as an optimization when all children will
+ *              definitely be ignored.
+ *
  * Most of the time, you want the combination (_MARK_SEEN | _DO_SHOW)
  * but they can be used independently, such as when sparse-checkout
  * pattern matching is being applied.
@@ -41,6 +46,7 @@ enum list_objects_filter_result {
        LOFR_ZERO      = 0,
        LOFR_MARK_SEEN = 1<<0,
        LOFR_DO_SHOW   = 1<<1,
+       LOFR_SKIP_TREE = 1<<2,
 };
 
 enum list_objects_filter_situation {

diff --git a/list-objects.c b/list-objects.c
index 7a1a0929db99bdcab29deb8539467c174e6d1c07..d1e3d217c561c9a4829c94f2837b3d837599365f 100644 (file)
--- a/list-objects.c
+++ b/list-objects.c
@@ -11,6 +11,7 @@
 #include "list-objects-filter-options.h"
 #include "packfile.h"
 #include "object-store.h"
+#include "trace.h"
 
 struct traversal_context {
        struct rev_info *revs;
@@ -184,7 +185,9 @@ static void process_tree(struct traversal_context *ctx,
        if (base->len)
                strbuf_addch(base, '/');
 
-       if (!failed_parse)
+       if (r & LOFR_SKIP_TREE)
+               trace_printf("Skipping contents of tree %s...\n", base->buf);
+       else if (!failed_parse)
                process_tree_contents(ctx, tree, base);
 
        if ((obj->flags & NOT_USER_GIVEN) && ctx->filter_fn) {

diff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh
index d24f9d5b5a48544708213c4c9cbd920953dcfee2..c6aae93b572cdc7108d7201832bb46ad4b968a84 100755 (executable)
--- a/t/t6112-rev-list-filters-objects.sh
+++ b/t/t6112-rev-list-filters-objects.sh
@@ -245,6 +245,19 @@ test_expect_success 'verify tree:0 includes trees in "filtered" output' '
        test_cmp expected filtered_types
 '
 
+# Make sure tree:0 does not iterate through any trees.
+
+test_expect_success 'filter a GIANT tree through tree:0' '
+       GIT_TRACE=1 git -C r3 rev-list \
+               --objects --filter=tree:0 HEAD 2>filter_trace &&
+       grep "Skipping contents of tree [.][.][.]" filter_trace >actual &&
+       # One line for each commit traversed.
+       test_line_count = 2 actual &&
+
+       # Make sure no other trees were considered besides the root.
+       ! grep "Skipping contents of tree [^.]" filter_trace
+'
+
 # Delete some loose objects and use rev-list, but WITHOUT any filtering.
 # This models previously omitted objects that we did not receive.