[RFC PATCH 1/3] list-objects: support for skipping tree traversal
- From
Matthew DeVore <matvore@google.com>
- Date
- Oct 11, 2018, 23:09 UTC
- Message-ID
- <fe4cf0841d500a46ad8f10c00818b467023d0ffc.1539298957.git.matvore@google.com>
- In-Reply-To
- <cover.1539298957.git.matvore@google.com>
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> --- list-objects-filter.c | 11 +++++++++-- list-objects-filter.h | 6 ++++++ list-objects.c | 5 ++++- t/t6112-rev-list-filters-objects.sh | 10 ++++++++++ 4 files changed, 29 insertions(+), 3 deletions(-)
diff --git a/list-objects-filter.c b/list-objects-filter.c index 09b2b05d5..37fba456d 100644 --- 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 a6f6b4990..52b4a84da 100644 --- a/list-objects-filter.h +++ b/list-objects-filter.h @@ -24,6 +24,11 @@ struct oidset; * 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. @@ -45,6 +50,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 7a1a0929d..d1e3d217c 100644 --- 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 08e0c7db6..efb1bee2e 100755 --- a/t/t6112-rev-list-filters-objects.sh +++ b/t/t6112-rev-list-filters-objects.sh @@ -244,6 +244,16 @@ 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 +' + # Delete some loose objects and use rev-list, but WITHOUT any filtering. # This models previously omitted objects that we did not receive.
-- 2.19.1.331.ge82ca0e54c-goog