From: Matthew DeVore <matvore@google.com>
To: git@vger.kernel.org
Cc: Matthew DeVore <matvore@google.com>,
sbeller@google.com, git@jeffhostetler.com,
jeffhost@microsoft.com, peff@peff.net, stefanbeller@gmail.com,
jonathantanmy@google.com, gitster@pobox.com, pclouds@gmail.com
Subject: [RFC PATCH 1/3] list-objects: support for skipping tree traversal
Date: Thu, 11 Oct 2018 16:09:00 -0700 [thread overview]
Message-ID: <fe4cf0841d500a46ad8f10c00818b467023d0ffc.1539298957.git.matvore@google.com> (raw)
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
next prev parent reply other threads:[~2018-10-11 23:09 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-11 23:08 [RFC PATCH 0/3] support for filtering trees and blobs based on depth Matthew DeVore
2018-10-11 23:09 ` Matthew DeVore [this message]
2018-10-14 23:15 ` [RFC PATCH 1/3] list-objects: support for skipping tree traversal Junio C Hamano
2018-10-18 0:25 ` Matthew DeVore
2018-10-11 23:09 ` [RFC PATCH 2/3] Documentation/git-rev-list: s/<commit>/<object>/ Matthew DeVore
2018-10-14 23:25 ` Junio C Hamano
2018-10-20 0:03 ` Matthew DeVore
2018-10-22 2:21 ` Junio C Hamano
2018-12-07 22:55 ` Matthew DeVore
2018-12-08 6:24 ` Junio C Hamano
2018-10-11 23:09 ` [RFC PATCH 3/3] list-objects-filter: teach tree:# how to handle >0 Matthew DeVore
2018-10-15 2:31 ` Junio C Hamano
2018-11-08 0:47 ` Matthew DeVore
2018-12-10 23:15 ` Matthew DeVore
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=fe4cf0841d500a46ad8f10c00818b467023d0ffc.1539298957.git.matvore@google.com \
--to=matvore@google.com \
--cc=git@jeffhostetler.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=jeffhost@microsoft.com \
--cc=jonathantanmy@google.com \
--cc=pclouds@gmail.com \
--cc=peff@peff.net \
--cc=sbeller@google.com \
--cc=stefanbeller@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).