{"thread":{"id":"49543","subject":"[RFC PATCH 0/3] support for filtering trees and blobs based on depth","startedAt":"2018-10-11T23:09:13Z","lastAt":"2018-12-10T23:15:47Z","messageCount":14,"participants":["Matthew DeVore","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"360250","messageId":"cover.1539298957.git.matvore@google.com","threadId":"49543","inReplyTo":null,"subject":"[RFC PATCH 0/3] support for filtering trees and blobs based on depth","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-10-11T23:08:59Z","receivedAt":"2018-10-11T23:09:13Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"This adds support for depth >0 in the tree:<depth> filter. Before this patch,\nonly <depth>=0 is supported, which means all trees and blobs are filtered.\n\nThe purpose of this is to allow fetching of entire directories in a partial\nclone use case. If I do a partial clone of a repo with no objects and then want\nto do something like \"make\" it will be quite slow of we initiate a separate\nfetch for every file needed. Alternatively, fetching directories at a time -\nas soon as any file in a directory is accessed - is a reasonable approach.\n\nThank you,\n\nMatthew DeVore (3):\n  list-objects: support for skipping tree traversal\n  Documentation/git-rev-list: s/<commit>/<object>/\n  list-objects-filter: teach tree:# how to handle >0\n\n Documentation/git-rev-list.txt      | 21 ++++---\n Documentation/rev-list-options.txt  | 24 +++++---\n builtin/rev-list.c                  |  2 +-\n list-objects-filter-options.c       |  6 +-\n list-objects-filter-options.h       |  1 +\n list-objects-filter.c               | 52 +++++++++++++---\n list-objects-filter.h               |  6 ++\n list-objects.c                      |  5 +-\n t/t6112-rev-list-filters-objects.sh | 94 +++++++++++++++++++++++++++++\n 9 files changed, 178 insertions(+), 33 deletions(-)\n\n-- \n2.19.1.331.ge82ca0e54c-goog\n\n"},{"id":"360251","messageId":"fe4cf0841d500a46ad8f10c00818b467023d0ffc.1539298957.git.matvore@google.com","threadId":"49543","inReplyTo":"cover.1539298957.git.matvore@google.com","subject":"[RFC PATCH 1/3] list-objects: support for skipping tree traversal","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-10-11T23:09:00Z","receivedAt":"2018-10-11T23:09:23Z","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 | 10 ++++++++++\n 4 files changed, 29 insertions(+), 3 deletions(-)\n\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex 09b2b05d5..37fba456d 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}\n+\t\telse\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 \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 a6f6b4990..52b4a84da 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 7a1a0929d..d1e3d217c 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 08e0c7db6..efb1bee2e 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -244,6 +244,16 @@ 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+\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.331.ge82ca0e54c-goog\n\n"},{"id":"360252","messageId":"a1ddae16bae563dd904555661e2e916536f388d8.1539298957.git.matvore@google.com","threadId":"49543","inReplyTo":"cover.1539298957.git.matvore@google.com","subject":"[RFC PATCH 2/3] Documentation/git-rev-list: s/<commit>/<object>/","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-10-11T23:09:01Z","receivedAt":"2018-10-11T23:09:25Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"git-rev-list has a mode where it works on the granularity of trees and\nblobs, rather than commits only. When discussing this mode in\ndocumenation, it can get awkward to refer to the list of arguments that\nmay include blobs and trees as <commit>. It is especially awkward in a\nfollow-up patch, so prepare for that patch by renaming the argument.\n\nIn addition to simply renaming the argument, also reword documentation\nin some places such that we include non-commit objects in our\nterminology. In other words, s/commit/object/ in any prose where the\ncontext obviously applies to trees and blobs in a non-pathological way.\n\nSigned-off-by: Matthew DeVore <matvore@google.com>\n---\n Documentation/git-rev-list.txt     | 21 ++++++++++++---------\n Documentation/rev-list-options.txt | 16 ++++++++--------\n builtin/rev-list.c                 |  2 +-\n 3 files changed, 21 insertions(+), 18 deletions(-)\n\ndiff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt\nindex 88609ff43..b3357932c 100644\n--- a/Documentation/git-rev-list.txt\n+++ b/Documentation/git-rev-list.txt\n@@ -60,20 +60,23 @@ SYNOPSIS\n \t     [ --no-walk ] [ --do-walk ]\n \t     [ --count ]\n \t     [ --use-bitmap-index ]\n-\t     <commit>... [ \\-- <paths>... ]\n+\t     <object>... [ \\-- <paths>... ]\n \n DESCRIPTION\n -----------\n \n-List commits that are reachable by following the `parent` links from the\n-given commit(s), but exclude commits that are reachable from the one(s)\n-given with a '{caret}' in front of them.  The output is given in reverse\n-chronological order by default.\n+List objects that are reachable by following references from the given\n+object(s), but exclude objects that are reachable from the one(s) given\n+with a '{caret}' in front of them.\n \n-You can think of this as a set operation.  Commits given on the command\n-line form a set of commits that are reachable from any of them, and then\n-commits reachable from any of the ones given with '{caret}' in front are\n-subtracted from that set.  The remaining commits are what comes out in the\n+By default, only commit objects are shown, and the commits are shown in\n+reverse chronological order. The '--object' flag causes non-commit objects\n+to also be shown.\n+\n+You can think of this as a set operation.  Objects given on the command\n+line form a set of objects that are reachable from any of them, and then\n+objects reachable from any of the ones given with '{caret}' in front are\n+subtracted from that set.  The remaining objects are what come out in the\n command's output.  Various other options and paths parameters can be used\n to further limit the result.\n \ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 5f1672913..c2c1c40e6 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -139,29 +139,29 @@ parents) and `--max-parents=-1` (negative numbers denote no upper limit).\n \n --all::\n \tPretend as if all the refs in `refs/`, along with `HEAD`, are\n-\tlisted on the command line as '<commit>'.\n+\tlisted on the command line as '<object>'.\n \n --branches[=<pattern>]::\n \tPretend as if all the refs in `refs/heads` are listed\n-\ton the command line as '<commit>'. If '<pattern>' is given, limit\n+\ton the command line as '<object>'. If '<pattern>' is given, limit\n \tbranches to ones matching given shell glob. If pattern lacks '?',\n \t'{asterisk}', or '[', '/{asterisk}' at the end is implied.\n \n --tags[=<pattern>]::\n \tPretend as if all the refs in `refs/tags` are listed\n-\ton the command line as '<commit>'. If '<pattern>' is given, limit\n+\ton the command line as '<object>'. If '<pattern>' is given, limit\n \ttags to ones matching given shell glob. If pattern lacks '?', '{asterisk}',\n \tor '[', '/{asterisk}' at the end is implied.\n \n --remotes[=<pattern>]::\n \tPretend as if all the refs in `refs/remotes` are listed\n-\ton the command line as '<commit>'. If '<pattern>' is given, limit\n+\ton the command line as '<object>'. If '<pattern>' is given, limit\n \tremote-tracking branches to ones matching given shell glob.\n \tIf pattern lacks '?', '{asterisk}', or '[', '/{asterisk}' at the end is implied.\n \n --glob=<glob-pattern>::\n \tPretend as if all the refs matching shell glob '<glob-pattern>'\n-\tare listed on the command line as '<commit>'. Leading 'refs/',\n+\tare listed on the command line as '<object>'. Leading 'refs/',\n \tis automatically prepended if missing. If pattern lacks '?', '{asterisk}',\n \tor '[', '/{asterisk}' at the end is implied.\n \n@@ -182,7 +182,7 @@ explicitly.\n \n --reflog::\n \tPretend as if all objects mentioned by reflogs are listed on the\n-\tcommand line as `<commit>`.\n+\tcommand line as `<object>`.\n \n --single-worktree::\n \tBy default, all working trees will be examined by the\n@@ -205,9 +205,9 @@ ifndef::git-rev-list[]\n endif::git-rev-list[]\n \n --stdin::\n-\tIn addition to the '<commit>' listed on the command\n+\tIn addition to the '<object>' listed on the command\n \tline, read them from the standard input. If a `--` separator is\n-\tseen, stop reading commits and start reading paths to limit the\n+\tseen, stop reading objects and start reading paths to limit the\n \tresult.\n \n ifdef::git-rev-list[]\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 49d6deed7..9817e6747 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -21,7 +21,7 @@\n #include \"object-store.h\"\n \n static const char rev_list_usage[] =\n-\"git rev-list [OPTION] <commit-id>... [ -- paths... ]\\n\"\n+\"git rev-list [OPTION] <object-id>... [ -- paths... ]\\n\"\n \"  limiting output:\\n\"\n \"    --max-count=<n>\\n\"\n \"    --max-age=<epoch>\\n\"\n-- \n2.19.1.331.ge82ca0e54c-goog\n\n"},{"id":"360253","messageId":"e340f743e6749e65525e1342dc47faaa6540f04b.1539298957.git.matvore@google.com","threadId":"49543","inReplyTo":"cover.1539298957.git.matvore@google.com","subject":"[RFC PATCH 3/3] list-objects-filter: teach tree:# how to handle >0","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-10-11T23:09:02Z","receivedAt":"2018-10-11T23:09:28Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"Implement positive values for <depth> in the tree:<depth> filter. The\nexact semantics are described in Documentation/rev-list-options.txt.\n\nThe long-term goal at the end of this is to allow a partial clone to\neagerly fetch an entire directory of files by fetching a tree and\nspecifying <depth>=1. This, for instance, would make a build operation\nfast and convenient. It is fast because the partial clone does not need\nto fetch each file individually, and convenient because the user does\nnot need to supply a sparse-checkout specification.\n\nSigned-off-by: Matthew DeVore <matvore@google.com>\n---\n Documentation/rev-list-options.txt  |  8 ++-\n list-objects-filter-options.c       |  6 +--\n list-objects-filter-options.h       |  1 +\n list-objects-filter.c               | 49 +++++++++++++----\n t/t6112-rev-list-filters-objects.sh | 84 +++++++++++++++++++++++++++++\n 5 files changed, 132 insertions(+), 16 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex c2c1c40e6..c78985c41 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -734,8 +734,12 @@ specification contained in <path>.\n +\n The form '--filter=tree:<depth>' omits all blobs and trees whose depth\n from the root tree is >= <depth> (minimum depth if an object is located\n-at multiple depths in the commits traversed). Currently, only <depth>=0\n-is supported, which omits all blobs and trees.\n+at multiple depths in the commits traversed). <depth>=0 will not include\n+any trees or blobs unless included explicitly in <object>. <depth>=1\n+will include only the tree and blobs which are referenced directly by a\n+commit reachable from <object> or an object given in <object>. <depth>=2\n+is like <depth>=1 while also including trees and blobs one more level\n+removed from <object> or a reachable commit.\n \n --no-filter::\n \tTurn off any previous `--filter=` argument.\ndiff --git a/list-objects-filter-options.c b/list-objects-filter-options.c\nindex e8da2e858..9dc61d6e6 100644\n--- a/list-objects-filter-options.c\n+++ b/list-objects-filter-options.c\n@@ -50,12 +50,12 @@ static int gently_parse_list_objects_filter(\n \t\t}\n \n \t} else if (skip_prefix(arg, \"tree:\", &v0)) {\n-\t\tunsigned long depth;\n-\t\tif (!git_parse_ulong(v0, &depth) || depth != 0) {\n+\t\tif (!git_parse_ulong(v0,\n+\t\t\t\t     &filter_options->tree_depth_limit_value)) {\n \t\t\tif (errbuf) {\n \t\t\t\tstrbuf_addstr(\n \t\t\t\t\terrbuf,\n-\t\t\t\t\t_(\"only 'tree:0' is supported\"));\n+\t\t\t\t\t_(\"expected 'tree:<int>'\"));\n \t\t\t}\n \t\t\treturn 1;\n \t\t}\ndiff --git a/list-objects-filter-options.h b/list-objects-filter-options.h\nindex af64e5c66..c1ae70cd8 100644\n--- a/list-objects-filter-options.h\n+++ b/list-objects-filter-options.h\n@@ -44,6 +44,7 @@ struct list_objects_filter_options {\n \tstruct object_id *sparse_oid_value;\n \tchar *sparse_path_value;\n \tunsigned long blob_limit_value;\n+\tunsigned long tree_depth_limit_value;\n };\n \n /* Normalized command line arguments */\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex 37fba456d..e69fb9b82 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -83,53 +83,80 @@ static void *filter_blobs_none__init(\n  * A filter for list-objects to omit ALL trees and blobs from the traversal.\n  * Can OPTIONALLY collect a list of the omitted OIDs.\n  */\n-struct filter_trees_none_data {\n+struct filter_trees_depth_data {\n \tstruct oidset *omits;\n+\tunsigned long max_depth;\n+\tunsigned long current_depth;\n };\n \n-static enum list_objects_filter_result filter_trees_none(\n+static enum list_objects_filter_result filter_trees_depth(\n \tenum list_objects_filter_situation filter_situation,\n \tstruct object *obj,\n \tconst char *pathname,\n \tconst char *filename,\n \tvoid *filter_data_)\n {\n-\tstruct filter_trees_none_data *filter_data = filter_data_;\n+\tstruct filter_trees_depth_data *filter_data = filter_data_;\n+\n+\tint too_deep = filter_data->current_depth >= filter_data->max_depth;\n+\n+\t/*\n+\t * Note that we do not use _MARK_SEEN in order to allow re-traversal in\n+\t * case we encounter a tree or blob again at a shallower depth.\n+\t */\n \n \tswitch (filter_situation) {\n \tdefault:\n \t\tBUG(\"unknown filter_situation: %d\", filter_situation);\n \n-\tcase LOFS_BEGIN_TREE:\n \tcase LOFS_BLOB:\n+\t\tif (!too_deep) goto include_it;\n+\n+\t\tif (filter_data->omits)\n+\t\t\toidset_insert(filter_data->omits, &obj->oid);\n+\n+\t\treturn LOFR_ZERO;\n+\n+\tcase LOFS_BEGIN_TREE:\n+\t\tfilter_data->current_depth++;\n+\n+\t\tif (!too_deep) goto include_it;\n+\n \t\tif (filter_data->omits) {\n \t\t\toidset_insert(filter_data->omits, &obj->oid);\n-\t\t\t/* _MARK_SEEN but not _DO_SHOW (hard omit) */\n-\t\t\treturn LOFR_MARK_SEEN;\n+\t\t\treturn LOFR_ZERO;\n \t\t}\n \t\telse\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\treturn LOFR_SKIP_TREE;\n \n \tcase LOFS_END_TREE:\n \t\tassert(obj->type == OBJ_TREE);\n+\t\tfilter_data->current_depth--;\n \t\treturn LOFR_ZERO;\n \n \t}\n+\n+include_it:\n+\tif (filter_data->omits)\n+\t\toidset_remove(filter_data->omits, &obj->oid);\n+\treturn LOFR_MARK_SEEN | LOFR_DO_SHOW;\n }\n \n-static void* filter_trees_none__init(\n+static void* filter_trees_depth__init(\n \tstruct oidset *omitted,\n \tstruct list_objects_filter_options *filter_options,\n \tfilter_object_fn *filter_fn,\n \tfilter_free_fn *filter_free_fn)\n {\n-\tstruct filter_trees_none_data *d = xcalloc(1, sizeof(*d));\n+\tstruct filter_trees_depth_data *d = xcalloc(1, sizeof(*d));\n \td->omits = omitted;\n+\td->max_depth = filter_options->tree_depth_limit_value;\n+\td->current_depth = 0;\n \n-\t*filter_fn = filter_trees_none;\n+\t*filter_fn = filter_trees_depth;\n \t*filter_free_fn = free;\n \treturn d;\n }\n@@ -426,7 +453,7 @@ static filter_init_fn s_filters[] = {\n \tNULL,\n \tfilter_blobs_none__init,\n \tfilter_blobs_limit__init,\n-\tfilter_trees_none__init,\n+\tfilter_trees_depth__init,\n \tfilter_sparse_oid__init,\n \tfilter_sparse_path__init,\n };\ndiff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh\nindex efb1bee2e..43ee0df80 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -254,6 +254,90 @@ test_expect_success 'filter a GIANT tree through tree:0' '\n \ttest_line_count = 2 actual\n '\n \n+# Test tree:# filters.\n+\n+expect_has () {\n+\tcommit=$1 &&\n+\tname=$2 &&\n+\n+\thash=$(git -C r3 rev-parse $commit:$name) &&\n+\tgrep \"^$hash $name$\" actual\n+}\n+\n+test_expect_success 'verify tree:1 includes root trees' '\n+\tgit -C r3 rev-list --objects --filter=tree:1 HEAD >actual &&\n+\n+\t# We should get two root directories and two commits.\n+\texpect_has HEAD \"\" &&\n+\texpect_has HEAD~1 \"\"  &&\n+\ttest_line_count = 4 actual\n+'\n+\n+test_expect_success 'verify tree:2 includes root trees and immediate children' '\n+\tgit -C r3 rev-list --objects --filter=tree:2 HEAD >actual &&\n+\n+\texpect_has HEAD \"\" &&\n+\texpect_has HEAD~1 \"\" &&\n+\texpect_has HEAD dir1 &&\n+\texpect_has HEAD pattern &&\n+\texpect_has HEAD sparse1 &&\n+\texpect_has HEAD sparse2 &&\n+\n+\t# There are also 2 commit objects\n+\ttest_line_count = 8 actual\n+'\n+\n+test_expect_success 'verify tree:3 includes everything expected' '\n+\tgit -C r3 rev-list --objects --filter=tree:3 HEAD >actual &&\n+\n+\texpect_has HEAD \"\" &&\n+\texpect_has HEAD~1 \"\" &&\n+\texpect_has HEAD dir1 &&\n+\texpect_has HEAD dir1/sparse1 &&\n+\texpect_has HEAD dir1/sparse2 &&\n+\texpect_has HEAD pattern &&\n+\texpect_has HEAD sparse1 &&\n+\texpect_has HEAD sparse2 &&\n+\n+\t# There are also 2 commit objects\n+\ttest_line_count = 10 actual\n+'\n+\n+# Test provisional omit collection logic with a repo that has objects appearing\n+# at multiple depths - first deeper than the filter's threshold, then shallow.\n+\n+test_expect_success 'setup r4' '\n+\tgit init r4 &&\n+\n+\techo foo > r4/foo &&\n+\tmkdir r4/subdir &&\n+\techo bar > r4/subdir/bar &&\n+\n+\tmkdir r4/filt &&\n+\tcp -r r4/foo r4/subdir r4/filt &&\n+\n+\tgit -C r4 add foo subdir filt &&\n+\tgit -C r4 commit -m \"commit msg\"\n+'\n+\n+expect_has_with_different_name () {\n+\tcommit=$1 &&\n+\tname=$2 &&\n+\n+\thash=$(git -C r4 rev-parse $commit:$name) &&\n+\t! grep \"^$hash $name$\" actual &&\n+\tgrep \"^$hash \" actual &&\n+\t! grep \"~$hash\" actual\n+}\n+\n+test_expect_success 'test tree:# filter provisional omit for blob and tree' '\n+\tgit -C r4 rev-list --objects --filter-print-omitted --filter=tree:2 \\\n+\t\tHEAD >actual &&\n+\n+\texpect_has_with_different_name HEAD filt/foo &&\n+\texpect_has_with_different_name HEAD filt/subdir\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.331.ge82ca0e54c-goog\n\n"},{"id":"360435","messageId":"xmqqa7ng86i6.fsf@gitster-ct.c.googlers.com","threadId":"49543","inReplyTo":"fe4cf0841d500a46ad8f10c00818b467023d0ffc.1539298957.git.matvore@google.com","subject":"Re: [RFC PATCH 1/3] list-objects: support for skipping tree traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-14T23:15:29Z","receivedAt":"2018-10-14T23:15:35Z","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>  list-objects-filter.c               | 11 +++++++++--\n>  list-objects-filter.h               |  6 ++++++\n>  list-objects.c                      |  5 ++++-\n>  t/t6112-rev-list-filters-objects.sh | 10 ++++++++++\n>  4 files changed, 29 insertions(+), 3 deletions(-)\n\nThis step looks more like \"ow, we could have done the tree:0 support\nthat is in 'next' better\" than a part of \"here is a series to do\ntree:N for non zero value of N\".\n\nIf that is the case, I'd prefer to see this step polished enough\nbefore [2-3/3] of this RFC is worked on, so that we can merge the\ntree:0 (but not yet tree:N) support that is solid down to 'master'\nsoonish.\n\n> diff --git a/list-objects-filter.c b/list-objects-filter.c\n> index 09b2b05d5..37fba456d 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}\n> +\t\telse\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\nOK, so \"not collecting omits\" is synonymous to \"N==0, we aren't\ndoing tree at any level\", and at this point in the series before the\nsupport for N>0 is introduced, we'd always take this \"else\" clause\nbecause tree:0 is the only thing we support?\n\nStyle: our modern style is to use {} around the body which is a\nsingle statement on the else clause when the body of the\ncorresponding if clause needs {} around (and vice versa), so\n\n\tif (filter_data->omits) {\n\t\toidset_isnert(...);\n\t\treturn ...;\n\t} else {\n\t\treturn ...;\n\t}\n\n> diff --git a/list-objects-filter.h b/list-objects-filter.h\n> index a6f6b4990..52b4a84da 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 {\n> diff --git a/list-objects.c b/list-objects.c\n> index 7a1a0929d..d1e3d217c 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\nEven when failed_parse==true, i.e. we found that the tree object's\ndata cannot be understood, if we have skip-tree bit set, that means\nwe do not care---we won't be descending into its children anyway.\n\nMakes sense.\n\n> diff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh\n> index 08e0c7db6..efb1bee2e 100755\n> --- a/t/t6112-rev-list-filters-objects.sh\n> +++ b/t/t6112-rev-list-filters-objects.sh\n> @@ -244,6 +244,16 @@ 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\nHere you are not jus tmaking sure SKIP_TREE bit is set for some\ntree, but it is set when base->buf is an empty string (i.e. the top\nlevel tree)?  Which makes sense, and the next text makes sure that\nbetween the two commits, the number of total \"top level\" trees is 2,\nbut I wonder if it is more direct to also make sure that the code is\nnot even seeing or skipping any tree inside these top level trees\n(i.e. the same message but for \"\"!=base->buf should never appear in\nthe trace).\n\n> +\t# One line for each commit traversed.\n> +\ttest_line_count = 2 actual\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\nThanks.\n"},{"id":"360438","messageId":"xmqq4ldo861m.fsf@gitster-ct.c.googlers.com","threadId":"49543","inReplyTo":"a1ddae16bae563dd904555661e2e916536f388d8.1539298957.git.matvore@google.com","subject":"Re: [RFC PATCH 2/3] Documentation/git-rev-list: s/<commit>/<object>/","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-14T23:25:25Z","receivedAt":"2018-10-14T23:25:30Z","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> -List commits that are reachable by following the `parent` links from the\n> -given commit(s), but exclude commits that are reachable from the one(s)\n> -given with a '{caret}' in front of them.  The output is given in reverse\n> -chronological order by default.\n> +List objects that are reachable by following references from the given\n> +object(s), but exclude objects that are reachable from the one(s) given\n> +with a '{caret}' in front of them.\n>  \n> +By default, only commit objects are shown, and the commits are shown in\n> +reverse chronological order. The '--object' flag causes non-commit objects\n> +to also be shown.\n>\n> +You can think of this as a set operation.  Objects given on the command\n> +line form a set of objects that are reachable from any of them, and then\n> +objects reachable from any of the ones given with '{caret}' in front are\n> +subtracted from that set.  The remaining objects are what come out in the\n>  command's output.  Various other options and paths parameters can be used\n>  to further limit the result.\n\nI am not sure if this is a good rewrite.  It gives a false\nimpression as if you'd not see anything if I did this:\n\n\tgit rev-list --objects ^master md/filter-trees:t/valgrind\n\nespecially if you change the SYNOPSIS and make it claim that the\ncommand takes <object> as starting point.  Updating <commit> to\n<object> for those that are _shown_ is OK, but the s/commit/object/\nfor those that are given as the starting points is not a good change\nat all, if I understand what the code is designed to do correctly.\n\nIt is more like \"this is a set operation across commits.  We also\nshow objects that are reachable from the commits in the resulting\nset and are not reachable from the commits in the set that were\nexcluded when --objects option is given\".\n\n"},{"id":"360473","messageId":"xmqqlg706iv1.fsf@gitster-ct.c.googlers.com","threadId":"49543","inReplyTo":"e340f743e6749e65525e1342dc47faaa6540f04b.1539298957.git.matvore@google.com","subject":"Re: [RFC PATCH 3/3] list-objects-filter: teach tree:# how to handle >0","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-15T02:31:30Z","receivedAt":"2018-10-15T02:31:36Z","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 long-term goal at the end of this is to allow a partial clone to\n> eagerly fetch an entire directory of files by fetching a tree and\n> specifying <depth>=1. This, for instance, would make a build operation\n> fast and convenient\n\nThis would reduce round-trip, as you do not have to fetch the tree\nto see what its contents are before issuing another set of fetches\nfor them.  Those who are building virtual filesystem that let you\nmount a specific tree object, perhaps via fuse, may find it useful,\ntoo, even though I suspect that may not be your primary focus.\n\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index c2c1c40e6..c78985c41 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -734,8 +734,12 @@ specification contained in <path>.\n>  +\n>  The form '--filter=tree:<depth>' omits all blobs and trees whose depth\n>  from the root tree is >= <depth> (minimum depth if an object is located\n> -at multiple depths in the commits traversed). Currently, only <depth>=0\n> -is supported, which omits all blobs and trees.\n> +at multiple depths in the commits traversed). <depth>=0 will not include\n> +any trees or blobs unless included explicitly in <object>. <depth>=1\n\nHere, <object> refers to the objects directly requested on the\ncommand line (or --stdin)?  Triggering this question from me is a\nsign that this description may want to say a bit more to avoid the\nsame question from the real readers.  Perhaps replace \"included\nexplicitly in <object>\" with \"explicitly requested by listing them\non the command line or feeding them with `--stdin`\", or something\nlike that?\n\n> diff --git a/list-objects-filter-options.c b/list-objects-filter-options.c\n> index e8da2e858..9dc61d6e6 100644\n> --- a/list-objects-filter-options.c\n> +++ b/list-objects-filter-options.c\n> @@ -50,12 +50,12 @@ static int gently_parse_list_objects_filter(\n>  \t\t}\n>  \n>  \t} else if (skip_prefix(arg, \"tree:\", &v0)) {\n> -\t\tunsigned long depth;\n> -\t\tif (!git_parse_ulong(v0, &depth) || depth != 0) {\n> +\t\tif (!git_parse_ulong(v0,\n> +\t\t\t\t     &filter_options->tree_depth_limit_value)) {\n>  \t\t\tif (errbuf) {\n>  \t\t\t\tstrbuf_addstr(\n>  \t\t\t\t\terrbuf,\n> -\t\t\t\t\t_(\"only 'tree:0' is supported\"));\n> +\t\t\t\t\t_(\"expected 'tree:<int>'\"));\n\nWe do not accept \"tree:-1\", even though \"-1\" is an int.  Is it too\nobvious to worry about?  I do not think we want to say tree:<uint>\neven if we do want to make it clear we reject \"tree:-1\"\n\nI am wondering if \"expected 'tree:<depth>'\" would work better.\n\n> diff --git a/list-objects-filter-options.h b/list-objects-filter-options.h\n> index af64e5c66..c1ae70cd8 100644\n> --- a/list-objects-filter-options.h\n> +++ b/list-objects-filter-options.h\n> @@ -44,6 +44,7 @@ struct list_objects_filter_options {\n>  \tstruct object_id *sparse_oid_value;\n>  \tchar *sparse_path_value;\n>  \tunsigned long blob_limit_value;\n> +\tunsigned long tree_depth_limit_value;\n>  };\n\nThis change gets it right by adding \"depth\" in the field name and it\nis not a comment on this patch, but someday not in too distant\nfuture we should rename the \"blob_limit_value\" to make it clear that\nit is filtering by number of bytes, as other filtering criteria on\nblobs that can be expressed in ulong are quite possible.\n\n> -static enum list_objects_filter_result filter_trees_none(\n> +static enum list_objects_filter_result filter_trees_depth(\n>  \tenum list_objects_filter_situation filter_situation,\n>  \tstruct object *obj,\n>  \tconst char *pathname,\n>  \tconst char *filename,\n>  \tvoid *filter_data_)\n>  {\n> -\tstruct filter_trees_none_data *filter_data = filter_data_;\n> +\tstruct filter_trees_depth_data *filter_data = filter_data_;\n> +\n> +\tint too_deep = filter_data->current_depth >= filter_data->max_depth;\n\nDoes max mean \"maximum allowed\", or \"this and anything larger are\nrejected\".  The latter sound wrong, but I offhand do not know if\nyour current_depth counts from 0 or 1, so there may not be\noff-by-one.\n\n - dir.c::within_depth() that is used by pathspec matching that in turn\n   is used by \"grep --max-depth=1\" does \"if (depth > max_depth)\", which\n   sounds more in line with the usual convention, I would think.\n\n - pack-objects has max_delta_cache_size, which also is used as\n   \"maximum allowed\", not \"this is already too big\".  So is its\n   max_depth.\n\nThere may be other examples.  One existing violator I noticed was\nthe \"reject blobs that is this size or larger\" in this file; it is\ncalled \"max_bytes\", but it is apparently not \"maximum allowed\",\nwhich we probably would want to fix.\n\n> +\t/*\n> +\t * Note that we do not use _MARK_SEEN in order to allow re-traversal in\n> +\t * case we encounter a tree or blob again at a shallower depth.\n> +\t */\n\nHmph.  Earlier tree:0 support never even read the actual tree, so\nthis was not a problem.  We wouldn't have found a tree in deeper\nplaces first and then at a shallower depth, as we wouldn't have seen\nany tree in any depth deeper than the surface anyway.\n\nNow we need to worry about a tree that originally gets seen in a\ndeeper depth (that is still below the allowed maximum) to reappear\nat a shallower place, so a subtree within it that used to be too\ndeep may now be within the allowed maximum depth.\n\nStep 1 of these three patches made sure trees are not even opened\nunder \"tree:0\", so it was not just optimizing/shrinking the output\nof rev-list but also optimizing the traversal.  When we are\ncollecting omits, however, this one now returns _ZERO which means we\nstill traverse into the tree, even under \"tree:0\"?  I must be\nreading the code incorrectly (in general, when we are seeing a tree\nobject that itself is at the maximum allowed depth, trees found by\nreading its contents will never become eligible for output, even if\nthey are found at a shallower depth than their other copies were\npreviously found, I would think).\n\n>  \tswitch (filter_situation) {\n>  \tdefault:\n>  \t\tBUG(\"unknown filter_situation: %d\", filter_situation);\n>  \n> -\tcase LOFS_BEGIN_TREE:\n>  \tcase LOFS_BLOB:\n> +\t\tif (!too_deep) goto include_it;\n\nStyle: on two lines, like you did below for the next if() statement.\n\n> +\n> +\t\tif (filter_data->omits)\n> +\t\t\toidset_insert(filter_data->omits, &obj->oid);\n> +\n> +\t\treturn LOFR_ZERO;\n> +\n> +\tcase LOFS_BEGIN_TREE:\n> +\t\tfilter_data->current_depth++;\n> +\n> +\t\tif (!too_deep) goto include_it;\n> +\n>  \t\tif (filter_data->omits) {\n>  \t\t\toidset_insert(filter_data->omits, &obj->oid);\n> -\t\t\t/* _MARK_SEEN but not _DO_SHOW (hard omit) */\n> -\t\t\treturn LOFR_MARK_SEEN;\n> +\t\t\treturn LOFR_ZERO;\n>  \t\t}\n>  \t\telse\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\treturn LOFR_SKIP_TREE;\n>  \n>  \tcase LOFS_END_TREE:\n>  \t\tassert(obj->type == OBJ_TREE);\n> +\t\tfilter_data->current_depth--;\n>  \t\treturn LOFR_ZERO;\n>  \n>  \t}\n> +\n> +include_it:\n> +\tif (filter_data->omits)\n> +\t\toidset_remove(filter_data->omits, &obj->oid);\n> +\treturn LOFR_MARK_SEEN | LOFR_DO_SHOW;\n>  }\n"},{"id":"360797","messageId":"CAMfpvhK=CgamUGTa9b308WRA1Dw4w0Qbt8a4LiKVLFaW6nMwBQ@mail.gmail.com","threadId":"49543","inReplyTo":"xmqqa7ng86i6.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 1/3] list-objects: support for skipping tree traversal","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-10-18T00:25:51Z","receivedAt":"2018-10-18T00:26:06Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"On Sun, Oct 14, 2018 at 4:15 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> This step looks more like \"ow, we could have done the tree:0 support\n> that is in 'next' better\" than a part of \"here is a series to do\n> tree:N for non zero value of N\".\n>\n> If that is the case, I'd prefer to see this step polished enough\n> before [2-3/3] of this RFC is worked on, so that we can merge the\n> tree:0 (but not yet tree:N) support that is solid down to 'master'\n> soonish.\nThat's fair. So I will prioritize this patch above the rest of the\npatchset and send it separately in the future.\n\n> OK, so \"not collecting omits\" is synonymous to \"N==0, we aren't\n> doing tree at any level\", and at this point in the series before the\n> support for N>0 is introduced, we'd always take this \"else\" clause\n> because tree:0 is the only thing we support?\nActually \"not collecting omits\" and depth==0 are orthogonal concepts.\n\"Collect omits\" is the logic needed to implement the\n--filter-print-omitted flag on git rev-list. You can do this when\ndepth==0 (it will actually print all the trees and blobs recursively).\n\"Collect omits\" is tested *with* tree:0 in test t6112 in the test\nlabeled 'verify tree:0 includes trees in \"filtered\" output'\n\nIOW, both branches here are important even in this patch. If we are\ncollecting omits, then we can't skip the tree because omits collecting\nis recursive. Otherwise, we *can* skip the tree.\n\nBut maybe printing omits should not be recursive? The decision was\nnever discussed. The code to not be recursive is simpler, because we\ndon't need this if/else. Recursiveness is counter-intuitive since we\nwould \"skip\" a tree and at the same time print its contents.\n\n>\n> Style: our modern style is to use {} around the body which is a\n> single statement on the else clause when the body of the\n> corresponding if clause needs {} around (and vice versa), so\n>\nFixed, and I didn't realize I was supposed to be hugging \"else\" with\nthe curly braces. What you say is what CodingGuidelines says to do.\nThanks for pointing that out.\n\n>\n> Even when failed_parse==true, i.e. we found that the tree object's\n> data cannot be understood, if we have skip-tree bit set, that means\n> we do not care---we won't be descending into its children anyway.\n>\nYes.\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> > +     GIT_TRACE=1 git -C r3 rev-list \\\n> > +             --objects --filter=tree:0 HEAD 2>filter_trace &&\n> > +     grep \"Skipping contents of tree [.][.][.]\" filter_trace >actual &&\n>\n> Here you are not jus tmaking sure SKIP_TREE bit is set for some\n> tree, but it is set when base->buf is an empty string (i.e. the top\n> level tree)?  Which makes sense, and the next text makes sure that\n> between the two commits, the number of total \"top level\" trees is 2,\n> but I wonder if it is more direct to also make sure that the code is\n> not even seeing or skipping any tree inside these top level trees\n> (i.e. the same message but for \"\"!=base->buf should never appear in\n> the trace).\nMakes sense. I added another check in this test for other \"Skipping\" messages.\n\nThank you for reviewing.\n"},{"id":"360992","messageId":"CAMfpvh+CDc_jToDmZaAypqwXvrhJMO-_4sUWRcjXwwz6OHhAHA@mail.gmail.com","threadId":"49543","inReplyTo":"xmqq4ldo861m.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 2/3] Documentation/git-rev-list: s/<commit>/<object>/","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-10-20T00:03:56Z","receivedAt":"2018-10-20T00:04:11Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"On Sun, Oct 14, 2018 at 4:25 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Matthew DeVore <matvore@google.com> writes:\n>\n> > -List commits that are reachable by following the `parent` links from the\n> > -given commit(s), but exclude commits that are reachable from the one(s)\n> > -given with a '{caret}' in front of them.  The output is given in reverse\n> > -chronological order by default.\n> > +List objects that are reachable by following references from the given\n> > +object(s), but exclude objects that are reachable from the one(s) given\n> > +with a '{caret}' in front of them.\n> >\n> > +By default, only commit objects are shown, and the commits are shown in\n> > +reverse chronological order. The '--object' flag causes non-commit objects\n> > +to also be shown.\n> >\n> > +You can think of this as a set operation.  Objects given on the command\n> > +line form a set of objects that are reachable from any of them, and then\n> > +objects reachable from any of the ones given with '{caret}' in front are\n> > +subtracted from that set.  The remaining objects are what come out in the\n> >  command's output.  Various other options and paths parameters can be used\n> >  to further limit the result.\n>\n> I am not sure if this is a good rewrite.  It gives a false\n> impression as if you'd not see anything if I did this:\n>\n>         git rev-list --objects ^master md/filter-trees:t/valgrind\n>\nOh that's interesting. So my mental model conflicts with the command's\nbehavior. It actually is surprising behavior because:\n\n# this shows all files that were modified in the HEAD commit\ngit rev-list --objects ^HEAD~1^{tree} HEAD:\n\n# but this shows *all* files at HEAD\ngit rev-list --objects ^HEAD~1 HEAD:\n\nWhich means that ^commit and ^non-commit are treated inherently\ndifferently. Maybe I should fix this bug before clarifying this\ndocumentation...\n\n> It is more like \"this is a set operation across commits.  We also\n> show objects that are reachable from the commits in the resulting\n> set and are not reachable from the commits in the set that were\n> excluded when --objects option is given\".\n>\nThat would be correct though it wouldn't tell that you can use\n\"--objects ^foo-tree bar-tree.\" Without fixing the above bug, I could\nadd to your wording something to the effect of \"You can also use trees\nto include and exclude sets of objects rather than commits.\" Which\nimplies that mixing \"--objects ^commit tree\" on the command line is\nundefined.\n"},{"id":"361110","messageId":"xmqqo9bmyb56.fsf@gitster-ct.c.googlers.com","threadId":"49543","inReplyTo":"CAMfpvh+CDc_jToDmZaAypqwXvrhJMO-_4sUWRcjXwwz6OHhAHA@mail.gmail.com","subject":"Re: [RFC PATCH 2/3] Documentation/git-rev-list: s/<commit>/<object>/","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-10-22T02:21:09Z","receivedAt":"2018-10-22T02:21:15Z","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>> It is more like \"this is a set operation across commits.  We also\n>> show objects that are reachable from the commits in the resulting\n>> set and are not reachable from the commits in the set that were\n>> excluded when --objects option is given\".\n>>\n> That would be correct though it wouldn't tell that you can use\n> \"--objects ^foo-tree bar-tree.\"\n\nYeah, but quite honestly, I consider that it is working by accident,\nnot by design, in the current code (iow, you are looking at a\nbehaviour of whatever the code happens to do).  \"rev-list\" is pretty\nmuch set operation across commits, and anything that deals with a\nnon commit-ish given from the command line is an afterthought at\nbest, and happenstance in reality.\n\nI do not mean to say that the code must stay that way, though.\n"},{"id":"362684","messageId":"CAMfpvhK7FX717Cpnce4puytLFbd4G56qnhwgy5WG7vm3C31DiA@mail.gmail.com","threadId":"49543","inReplyTo":"xmqqlg706iv1.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 3/3] list-objects-filter: teach tree:# how to handle >0","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-11-08T00:47:47Z","receivedAt":"2018-11-08T00:48:04Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"A quick update: I've read Junio's comments on this patchset and\nbasically agree with them, but I haven't had a chance to apply them\nyet. I plan to pick this patchset up again (as well as the patch\n\"md/list-lazy-objects-fix\") once things settle down in my day job.\nOn Sun, Oct 14, 2018 at 7:31 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Matthew DeVore <matvore@google.com> writes:\n>\n> > The long-term goal at the end of this is to allow a partial clone to\n> > eagerly fetch an entire directory of files by fetching a tree and\n> > specifying <depth>=1. This, for instance, would make a build operation\n> > fast and convenient\n>\n> This would reduce round-trip, as you do not have to fetch the tree\n> to see what its contents are before issuing another set of fetches\n> for them.  Those who are building virtual filesystem that let you\n> mount a specific tree object, perhaps via fuse, may find it useful,\n> too, even though I suspect that may not be your primary focus.\n>\n> > diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> > index c2c1c40e6..c78985c41 100644\n> > --- a/Documentation/rev-list-options.txt\n> > +++ b/Documentation/rev-list-options.txt\n> > @@ -734,8 +734,12 @@ specification contained in <path>.\n> >  +\n> >  The form '--filter=tree:<depth>' omits all blobs and trees whose depth\n> >  from the root tree is >= <depth> (minimum depth if an object is located\n> > -at multiple depths in the commits traversed). Currently, only <depth>=0\n> > -is supported, which omits all blobs and trees.\n> > +at multiple depths in the commits traversed). <depth>=0 will not include\n> > +any trees or blobs unless included explicitly in <object>. <depth>=1\n>\n> Here, <object> refers to the objects directly requested on the\n> command line (or --stdin)?  Triggering this question from me is a\n> sign that this description may want to say a bit more to avoid the\n> same question from the real readers.  Perhaps replace \"included\n> explicitly in <object>\" with \"explicitly requested by listing them\n> on the command line or feeding them with `--stdin`\", or something\n> like that?\n>\n> > diff --git a/list-objects-filter-options.c b/list-objects-filter-options.c\n> > index e8da2e858..9dc61d6e6 100644\n> > --- a/list-objects-filter-options.c\n> > +++ b/list-objects-filter-options.c\n> > @@ -50,12 +50,12 @@ static int gently_parse_list_objects_filter(\n> >               }\n> >\n> >       } else if (skip_prefix(arg, \"tree:\", &v0)) {\n> > -             unsigned long depth;\n> > -             if (!git_parse_ulong(v0, &depth) || depth != 0) {\n> > +             if (!git_parse_ulong(v0,\n> > +                                  &filter_options->tree_depth_limit_value)) {\n> >                       if (errbuf) {\n> >                               strbuf_addstr(\n> >                                       errbuf,\n> > -                                     _(\"only 'tree:0' is supported\"));\n> > +                                     _(\"expected 'tree:<int>'\"));\n>\n> We do not accept \"tree:-1\", even though \"-1\" is an int.  Is it too\n> obvious to worry about?  I do not think we want to say tree:<uint>\n> even if we do want to make it clear we reject \"tree:-1\"\n>\n> I am wondering if \"expected 'tree:<depth>'\" would work better.\n>\n> > diff --git a/list-objects-filter-options.h b/list-objects-filter-options.h\n> > index af64e5c66..c1ae70cd8 100644\n> > --- a/list-objects-filter-options.h\n> > +++ b/list-objects-filter-options.h\n> > @@ -44,6 +44,7 @@ struct list_objects_filter_options {\n> >       struct object_id *sparse_oid_value;\n> >       char *sparse_path_value;\n> >       unsigned long blob_limit_value;\n> > +     unsigned long tree_depth_limit_value;\n> >  };\n>\n> This change gets it right by adding \"depth\" in the field name and it\n> is not a comment on this patch, but someday not in too distant\n> future we should rename the \"blob_limit_value\" to make it clear that\n> it is filtering by number of bytes, as other filtering criteria on\n> blobs that can be expressed in ulong are quite possible.\n>\n> > -static enum list_objects_filter_result filter_trees_none(\n> > +static enum list_objects_filter_result filter_trees_depth(\n> >       enum list_objects_filter_situation filter_situation,\n> >       struct object *obj,\n> >       const char *pathname,\n> >       const char *filename,\n> >       void *filter_data_)\n> >  {\n> > -     struct filter_trees_none_data *filter_data = filter_data_;\n> > +     struct filter_trees_depth_data *filter_data = filter_data_;\n> > +\n> > +     int too_deep = filter_data->current_depth >= filter_data->max_depth;\n>\n> Does max mean \"maximum allowed\", or \"this and anything larger are\n> rejected\".  The latter sound wrong, but I offhand do not know if\n> your current_depth counts from 0 or 1, so there may not be\n> off-by-one.\n>\n>  - dir.c::within_depth() that is used by pathspec matching that in turn\n>    is used by \"grep --max-depth=1\" does \"if (depth > max_depth)\", which\n>    sounds more in line with the usual convention, I would think.\n>\n>  - pack-objects has max_delta_cache_size, which also is used as\n>    \"maximum allowed\", not \"this is already too big\".  So is its\n>    max_depth.\n>\n> There may be other examples.  One existing violator I noticed was\n> the \"reject blobs that is this size or larger\" in this file; it is\n> called \"max_bytes\", but it is apparently not \"maximum allowed\",\n> which we probably would want to fix.\n>\n> > +     /*\n> > +      * Note that we do not use _MARK_SEEN in order to allow re-traversal in\n> > +      * case we encounter a tree or blob again at a shallower depth.\n> > +      */\n>\n> Hmph.  Earlier tree:0 support never even read the actual tree, so\n> this was not a problem.  We wouldn't have found a tree in deeper\n> places first and then at a shallower depth, as we wouldn't have seen\n> any tree in any depth deeper than the surface anyway.\n>\n> Now we need to worry about a tree that originally gets seen in a\n> deeper depth (that is still below the allowed maximum) to reappear\n> at a shallower place, so a subtree within it that used to be too\n> deep may now be within the allowed maximum depth.\n>\n> Step 1 of these three patches made sure trees are not even opened\n> under \"tree:0\", so it was not just optimizing/shrinking the output\n> of rev-list but also optimizing the traversal.  When we are\n> collecting omits, however, this one now returns _ZERO which means we\n> still traverse into the tree, even under \"tree:0\"?  I must be\n> reading the code incorrectly (in general, when we are seeing a tree\n> object that itself is at the maximum allowed depth, trees found by\n> reading its contents will never become eligible for output, even if\n> they are found at a shallower depth than their other copies were\n> previously found, I would think).\n>\n> >       switch (filter_situation) {\n> >       default:\n> >               BUG(\"unknown filter_situation: %d\", filter_situation);\n> >\n> > -     case LOFS_BEGIN_TREE:\n> >       case LOFS_BLOB:\n> > +             if (!too_deep) goto include_it;\n>\n> Style: on two lines, like you did below for the next if() statement.\n>\n> > +\n> > +             if (filter_data->omits)\n> > +                     oidset_insert(filter_data->omits, &obj->oid);\n> > +\n> > +             return LOFR_ZERO;\n> > +\n> > +     case LOFS_BEGIN_TREE:\n> > +             filter_data->current_depth++;\n> > +\n> > +             if (!too_deep) goto include_it;\n> > +\n> >               if (filter_data->omits) {\n> >                       oidset_insert(filter_data->omits, &obj->oid);\n> > -                     /* _MARK_SEEN but not _DO_SHOW (hard omit) */\n> > -                     return LOFR_MARK_SEEN;\n> > +                     return LOFR_ZERO;\n> >               }\n> >               else\n> >                       /*\n> >                        * Not collecting omits so no need to to traverse tree.\n> >                        */\n> > -                     return LOFR_SKIP_TREE | LOFR_MARK_SEEN;\n> > +                     return LOFR_SKIP_TREE;\n> >\n> >       case LOFS_END_TREE:\n> >               assert(obj->type == OBJ_TREE);\n> > +             filter_data->current_depth--;\n> >               return LOFR_ZERO;\n> >\n> >       }\n> > +\n> > +include_it:\n> > +     if (filter_data->omits)\n> > +             oidset_remove(filter_data->omits, &obj->oid);\n> > +     return LOFR_MARK_SEEN | LOFR_DO_SHOW;\n> >  }\n"},{"id":"364772","messageId":"CAMfpvh+6r65OqWpY-geOYHizs526A1004vakKSdxnO=fsahdAg@mail.gmail.com","threadId":"49543","inReplyTo":"xmqqo9bmyb56.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 2/3] Documentation/git-rev-list: s/<commit>/<object>/","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-12-07T22:55:25Z","receivedAt":"2018-12-07T22:59:20Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"On Sun, Oct 21, 2018 at 7:21 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Matthew DeVore <matvore@google.com> writes:\n>\n> >> It is more like \"this is a set operation across commits.  We also\n> >> show objects that are reachable from the commits in the resulting\n> >> set and are not reachable from the commits in the set that were\n> >> excluded when --objects option is given\".\n> >>\n> > That would be correct though it wouldn't tell that you can use\n> > \"--objects ^foo-tree bar-tree.\"\n>\n> Yeah, but quite honestly, I consider that it is working by accident,\n> not by design, in the current code (iow, you are looking at a\n> behaviour of whatever the code happens to do).  \"rev-list\" is pretty\n> much set operation across commits, and anything that deals with a\n> non commit-ish given from the command line is an afterthought at\n> best, and happenstance in reality.\n>\n> I do not mean to say that the code must stay that way, though.\n\nI tried fixing the issue of \"--objects ^commitobj treeobj\" not\nproperly excluding objects reachable from commitobj, but this ended up\ncausing t5616-partial-clone.sh to fail. In the test labeled \"manual\nprefetch of missing objects\", we create a clone of srv.bare without\nblobs called \"pc1\", then push some new commits to srv.bare (via a\nseparate \"local\" repo), and try to fetch missing blobs with this\ncommand:\n\n$ git -C pc1 fetch-pack --stdin \"file://$(pwd)/srv.bare\" <observed.oids\n\nWhere observed.oids contains all the blobs that were missing. It tells\nthe remote that it already has the \"refs/heads/master\" commit, which\nmeans it is excluded. Before, this worked fine, since it didn't mean\nthe blobs were excluded, only the commit itself. With the fix I\nnaively put together (and didn't share), because one of the blobs is\nreachable from \"refs/heads/master\" it wouldn't pull it. I guess I can\nchange it so that items given directly to stdin or argv are always\nfetched, though I'm not sure how easy that will be, and I'm not as\ninterested in fixing this as I once was. I just wanted the\ndocumentation to outline the object-enumeration capabilities. So I'll\nsend a re-roll which makes much more modest changes to the\ndocumentation.\n"},{"id":"364792","messageId":"xmqq1s6s8rj7.fsf@gitster-ct.c.googlers.com","threadId":"49543","inReplyTo":"CAMfpvh+6r65OqWpY-geOYHizs526A1004vakKSdxnO=fsahdAg@mail.gmail.com","subject":"Re: [RFC PATCH 2/3] Documentation/git-rev-list: s/<commit>/<object>/","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-12-08T06:24:28Z","receivedAt":"2018-12-08T06:27:41Z","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> $ git -C pc1 fetch-pack --stdin \"file://$(pwd)/srv.bare\" <observed.oids\n>\n> Where observed.oids contains all the blobs that were missing. It tells\n> the remote that it already has the \"refs/heads/master\" commit, which\n> means it is excluded. Before, this worked fine, since it didn't mean\n> the blobs were excluded, only the commit itself.\n\nSo 'master' has some blob in its tree, which is missing from the\nrepository, in this test?  Which means that such a repository is\n\"corrupt\" and does not pass connectivity check by fsck.\n\nI am of two minds.  If we claim that we have everything that is\nneeded to complete the commit sitting at the tip of 'master', I\nthink it is correct for the other side not to send a blob that is in\n'master' (or its ancestors), so your \"fix\" may (at least\ntechnically) be more correct than the status quo.  On the other\nhand, if possession of commit 'master' does not defeat an explicit\nrequest for a blob in it, that would actually be a good thing---it\nwould be a very straight-forward way to recover from such form of\nrepository corruption.\n\nFetching isolated objects without walking is also something that\nwould help backfill a lazily created clone, and I even vaguely\nrecall an effort to allow objects explicitly requested to be always\nfetched regardless of the connectivity, if I am not mistaken (JTan?)\n\nAnyway, thanks for a thoughtful response.\n"},{"id":"364989","messageId":"CAMfpvhJFtO_e99vdLiWX5W4E_7Ee27spBx6pi8dN0tUCXhftRA@mail.gmail.com","threadId":"49543","inReplyTo":"xmqqlg706iv1.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 3/3] list-objects-filter: teach tree:# how to handle >0","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-12-10T23:15:32Z","receivedAt":"2018-12-10T23:15:47Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"On Sun, Oct 14, 2018 at 7:31 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Matthew DeVore <matvore@google.com> writes:\n>\n> > The long-term goal at the end of this is to allow a partial clone to\n> > eagerly fetch an entire directory of files by fetching a tree and\n> > specifying <depth>=1. This, for instance, would make a build operation\n> > fast and convenient\n>\n> This would reduce round-trip, as you do not have to fetch the tree\n> to see what its contents are before issuing another set of fetches\n> for them.  Those who are building virtual filesystem that let you\n> mount a specific tree object, perhaps via fuse, may find it useful,\n> too, even though I suspect that may not be your primary focus.\n\nI added a paragraph mentioning the \"roundtrip\" aspect to the commit\nmessage, since this *may* help someone find a use for it.\n\n>\n> > diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> > index c2c1c40e6..c78985c41 100644\n> > --- a/Documentation/rev-list-options.txt\n> > +++ b/Documentation/rev-list-options.txt\n> > @@ -734,8 +734,12 @@ specification contained in <path>.\n> >  +\n> >  The form '--filter=tree:<depth>' omits all blobs and trees whose depth\n> >  from the root tree is >= <depth> (minimum depth if an object is located\n> > -at multiple depths in the commits traversed). Currently, only <depth>=0\n> > -is supported, which omits all blobs and trees.\n> > +at multiple depths in the commits traversed). <depth>=0 will not include\n> > +any trees or blobs unless included explicitly in <object>. <depth>=1\n>\n> Here, <object> refers to the objects directly requested on the\n> command line (or --stdin)?  Triggering this question from me is a\n> sign that this description may want to say a bit more to avoid the\n> same question from the real readers.  Perhaps replace \"included\n> explicitly in <object>\" with \"explicitly requested by listing them\n> on the command line or feeding them with `--stdin`\", or something\n> like that?\n\nI have reworded this to be more explicit about \"stdin,\" and also to\navoid directly admitting that trees are allowed in the <commit>\nargument, since I've dropped the s/<commit>/<object>/ patch.\n\nHere is the new paragraph:\n\nThe form '--filter=tree:<depth>' omits all blobs and trees whose depth\nfrom the root tree is >= <depth> (minimum depth if an object is located\nat multiple depths in the commits traversed). <depth>=0 will not include\nany trees or blobs unless included explicitly in the command-line (or\nstandard input when --stdin is used). <depth>=1 will include only the\ntree and blobs which are referenced directly by a commit reachable from\n<commit> or an explicitly-given object. <depth>=2 is like <depth>=1\nwhile also including trees and blobs one more level removed from an\nexplicitly-given commit or tree.\n\n> > +                                     _(\"expected 'tree:<int>'\"));\n>\n> We do not accept \"tree:-1\", even though \"-1\" is an int.  Is it too\n> obvious to worry about?  I do not think we want to say tree:<uint>\n> even if we do want to make it clear we reject \"tree:-1\"\n>\n> I am wondering if \"expected 'tree:<depth>'\" would work better.\n\nYes, I agree, <depth> is more helpful and not ambiguous in a\nsignificant way. Fixed.\n\n> > +     unsigned long tree_depth_limit_value;\n> >  };\n>\n> This change gets it right by adding \"depth\" in the field name and it\n> is not a comment on this patch, but someday not in too distant\n> future we should rename the \"blob_limit_value\" to make it clear that\n> it is filtering by number of bytes, as other filtering criteria on\n> blobs that can be expressed in ulong are quite possible.\n\nAgreed.\n\n>\n> > -static enum list_objects_filter_result filter_trees_none(\n> > +static enum list_objects_filter_result filter_trees_depth(\n> >       enum list_objects_filter_situation filter_situation,\n> >       struct object *obj,\n> >       const char *pathname,\n> >       const char *filename,\n> >       void *filter_data_)\n> >  {\n> > -     struct filter_trees_none_data *filter_data = filter_data_;\n> > +     struct filter_trees_depth_data *filter_data = filter_data_;\n> > +\n> > +     int too_deep = filter_data->current_depth >= filter_data->max_depth;\n>\n> Does max mean \"maximum allowed\", or \"this and anything larger are\n> rejected\".  The latter sound wrong, but I offhand do not know if\n> your current_depth counts from 0 or 1, so there may not be\n> off-by-one.\n>\nIt means \"this and anything larger are rejected.\" The documentation\nwords it similarly:\n\"\nThe form '--filter=tree:<depth>' omits all blobs and trees whose depth\nfrom the root tree is >= <depth> ...\n\"\n\nThere is no intuitive phrase to mean \"distance from root tree minus\none\" (left operand) and I don't want to change the filter option field\nto something different from what the user entered (right operand), so\nI think we'd best use \">=\" and I've renamed the field to\n\"exclusion_trigger_depth\".\n\n> There may be other examples.  One existing violator I noticed was\n> the \"reject blobs that is this size or larger\" in this file; it is\n> called \"max_bytes\", but it is apparently not \"maximum allowed\",\n> which we probably would want to fix.\n>\n\nThat's not ideal. The documentation suggests it means \"maximum\nallowed,\" and JGit apparently is interpreting the value as \"maximum\nallowed,\" so we should probably fix the semantics in Git. Or were you\nsuggesting to keep the behavior the same but fix the naming and docs?\n\n> > +     /*\n> > +      * Note that we do not use _MARK_SEEN in order to allow re-traversal in\n> > +      * case we encounter a tree or blob again at a shallower depth.\n> > +      */\n>\n> Hmph.  Earlier tree:0 support never even read the actual tree, so\n> this was not a problem.  We wouldn't have found a tree in deeper\n> places first and then at a shallower depth, as we wouldn't have seen\n> any tree in any depth deeper than the surface anyway.\n>\n> Now we need to worry about a tree that originally gets seen in a\n> deeper depth (that is still below the allowed maximum) to reappear\n> at a shallower place, so a subtree within it that used to be too\n> deep may now be within the allowed maximum depth.\n\nThat's true, and it points out the fact that we can't use\nLOFR_MARK_SEEN even if we do LOFR_DO_SHOW, since subtrees may or may\nnot be within the limit in the future. I've fixed that for v+1 of the\npatch, and added a corresponding test. I'm also refactoring the\nfilters_tree_depth function to not use goto. I think it is easier to\nfollow that way.\n\n>\n> Step 1 of these three patches made sure trees are not even opened\n> under \"tree:0\", so it was not just optimizing/shrinking the output\n> of rev-list but also optimizing the traversal.  When we are\n> collecting omits, however, this one now returns _ZERO which means we\n> still traverse into the tree, even under \"tree:0\"?  I must be\n> reading the code incorrectly (in general, when we are seeing a tree\n> object that itself is at the maximum allowed depth, trees found by\n> reading its contents will never become eligible for output, even if\n> they are found at a shallower depth than their other copies were\n> previously found, I would think).\n\nYou are reading the code right - when the tree is too deep, we\nsometimes return LOFR_ZERO, sometimes _SKIP_TREE - the latter if we\nare collecting omits. But as you observe, we don't need to traverse an\nomitted tree *if it has already been marked as omitted*, since that\nsuggests that its children have also been marked as omitted. So I've\nadded a new commit to this patchset which optimizes this case. The\nnext patchset will have 2 commits (subtracting the documentation\nrewrite one and ones that are already scheduled to merge):\n\nPatch 1/2 - implement tree:<depth> for positive depths\nPatch 2/2 - stop iterating through trees for collecting omits if the\nomits are already marked\n"}]}