{"thread":{"id":"49602","subject":"[PATCH v2] list-objects: support for skipping tree traversal","startedAt":"2018-10-18T00:39:30Z","lastAt":"2018-10-18T04:40:16Z","messageCount":2,"participants":["Matthew DeVore","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"360798","messageId":"20181018003915.60237-1-matvore@google.com","threadId":"49602","inReplyTo":null,"subject":"[PATCH v2] list-objects: support for skipping tree traversal","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-10-18T00:39:15Z","receivedAt":"2018-10-18T00:39:30Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"The tree:0 filter does not need to traverse the trees that it has\nfiltered out, so optimize list-objects and list-objects-filter to skip\ntraversing the trees entirely. Before this patch, we iterated over all\nchildren of the tree, and did nothing for all of them, which was\nwasteful.\n\nSigned-off-by: Matthew DeVore <matvore@google.com>\n---\n list-objects-filter.c               | 11 +++++++++--\n list-objects-filter.h               |  6 ++++++\n list-objects.c                      |  5 ++++-\n t/t6112-rev-list-filters-objects.sh | 13 +++++++++++++\n 4 files changed, 32 insertions(+), 3 deletions(-)\n\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex 09b2b05d54..765f3df3b0 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -102,9 +102,16 @@ static enum list_objects_filter_result filter_trees_none(\n \n \tcase LOFS_BEGIN_TREE:\n \tcase LOFS_BLOB:\n-\t\tif (filter_data->omits)\n+\t\tif (filter_data->omits) {\n \t\t\toidset_insert(filter_data->omits, &obj->oid);\n-\t\treturn LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */\n+\t\t\t/* _MARK_SEEN but not _DO_SHOW (hard omit) */\n+\t\t\treturn LOFR_MARK_SEEN;\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * Not collecting omits so no need to to traverse tree.\n+\t\t\t */\n+\t\t\treturn LOFR_SKIP_TREE | LOFR_MARK_SEEN;\n+\t\t}\n \n \tcase LOFS_END_TREE:\n \t\tassert(obj->type == OBJ_TREE);\ndiff --git a/list-objects-filter.h b/list-objects-filter.h\nindex a6f6b4990b..52b4a84da9 100644\n--- a/list-objects-filter.h\n+++ b/list-objects-filter.h\n@@ -24,6 +24,11 @@ struct oidset;\n  *              In general, objects should only be shown once, but\n  *              this result DOES NOT imply that we mark it SEEN.\n  *\n+ * _SKIP_TREE : Used in LOFS_BEGIN_TREE situation - indicates that\n+ *              the tree's children should not be iterated over. This\n+ *              is used as an optimization when all children will\n+ *              definitely be ignored.\n+ *\n  * Most of the time, you want the combination (_MARK_SEEN | _DO_SHOW)\n  * but they can be used independently, such as when sparse-checkout\n  * pattern matching is being applied.\n@@ -45,6 +50,7 @@ enum list_objects_filter_result {\n \tLOFR_ZERO      = 0,\n \tLOFR_MARK_SEEN = 1<<0,\n \tLOFR_DO_SHOW   = 1<<1,\n+\tLOFR_SKIP_TREE = 1<<2,\n };\n \n enum list_objects_filter_situation {\ndiff --git a/list-objects.c b/list-objects.c\nindex c2c5dd98ce..c41cc80db5 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -11,6 +11,7 @@\n #include \"list-objects-filter-options.h\"\n #include \"packfile.h\"\n #include \"object-store.h\"\n+#include \"trace.h\"\n \n struct traversal_context {\n \tstruct rev_info *revs;\n@@ -184,7 +185,9 @@ static void process_tree(struct traversal_context *ctx,\n \tif (base->len)\n \t\tstrbuf_addch(base, '/');\n \n-\tif (!failed_parse)\n+\tif (r & LOFR_SKIP_TREE)\n+\t\ttrace_printf(\"Skipping contents of tree %s...\\n\", base->buf);\n+\telse if (!failed_parse)\n \t\tprocess_tree_contents(ctx, tree, base);\n \n \tif ((obj->flags & NOT_USER_GIVEN) && ctx->filter_fn) {\ndiff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh\nindex c2c2d5bea1..bb8ce66050 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -281,6 +281,19 @@ test_expect_success 'verify tree:0 includes trees in \"filtered\" output' '\n \ttest_cmp expected filtered_types\n '\n \n+# Make sure tree:0 does not iterate through any trees.\n+\n+test_expect_success 'filter a GIANT tree through tree:0' '\n+\tGIT_TRACE=1 git -C r3 rev-list \\\n+\t\t--objects --filter=tree:0 HEAD 2>filter_trace &&\n+\tgrep \"Skipping contents of tree [.][.][.]\" filter_trace >actual &&\n+\t# One line for each commit traversed.\n+\ttest_line_count = 2 actual &&\n+\n+\t# Make sure no other trees were considered besides the root.\n+\t! grep \"Skipping contents of tree [^.]\" filter_trace\n+'\n+\n # Delete some loose objects and use rev-list, but WITHOUT any filtering.\n # This models previously omitted objects that we did not receive.\n \n-- \n2.19.1.568.g152ad8e336-goog\n\n"},{"id":"360812","messageId":"xmqqh8hjvpec.fsf@gitster-ct.c.googlers.com","threadId":"49602","inReplyTo":"20181018003915.60237-1-matvore@google.com","subject":"Re: [PATCH v2] list-objects: support for skipping tree traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-18T04:40:11Z","receivedAt":"2018-10-18T04:40:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matthew DeVore <matvore@google.com> writes:\n\n> The tree:0 filter does not need to traverse the trees that it has\n> filtered out, so optimize list-objects and list-objects-filter to skip\n> traversing the trees entirely. Before this patch, we iterated over all\n> children of the tree, and did nothing for all of them, which was\n> wasteful.\n>\n> Signed-off-by: Matthew DeVore <matvore@google.com>\n> ---\n\nThanks, will queue.\n"}]}