{"thread":{"id":"49999","subject":"[PATCH v2 0/2] support for filtering trees and blobs based on depth","startedAt":"2018-12-10T23:40:50Z","lastAt":"2019-01-17T18:44:28Z","messageCount":24,"participants":["Matthew DeVore","Junio C Hamano","Jonathan Tan","MATTHEW DEVORE"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"364992","messageId":"20181210234030.176178-1-matvore@google.com","threadId":"49999","inReplyTo":null,"subject":"[PATCH v2 0/2] support for filtering trees and blobs based on depth","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-12-10T23:40:28Z","receivedAt":"2018-12-10T23:40:50Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"This is a follow-up to the original patchset at\nhttps://public-inbox.org/git/cover.1539298957.git.matvore@google.com/ -\nthe purpose of that patchset and this one is to support positive integers for\ntree:<depth>. Some of the prior patchset's patches were either already queued\n(tree traversal optimization) or abandoned (documentation edit). This rendition\nof the patchset adds a commit which optimizes away tree traversal when\ncollecting omits when iterating over a tree a second time.\n\nThanks,\n\nMatthew DeVore (2):\n  list-objects-filter: teach tree:# how to handle >0\n  tree:<depth>: skip some trees even when collecting omits\n\n Documentation/rev-list-options.txt  |   9 ++-\n list-objects-filter-options.c       |   7 +-\n list-objects-filter-options.h       |   3 +-\n list-objects-filter.c               | 120 +++++++++++++++++++++++-----\n t/t6112-rev-list-filters-objects.sh | 115 +++++++++++++++++++++++++-\n 5 files changed, 225 insertions(+), 29 deletions(-)\n\n-- \n2.20.0.rc2.403.gdbc3b29805-goog\n\n"},{"id":"364993","messageId":"20181210234030.176178-2-matvore@google.com","threadId":"49999","inReplyTo":"20181210234030.176178-1-matvore@google.com","subject":"[PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-12-10T23:40:29Z","receivedAt":"2018-12-10T23:40:54Z","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\nAnother way of considering this feature is as a way to reduce\nround-trips, since the client can get any number of levels of\ndirectories in a single request, rather than wait for each level of tree\nobjects to come back, whose entries are used to construct a new request.\n\nSigned-off-by: Matthew DeVore <matvore@google.com>\n---\n Documentation/rev-list-options.txt  |   9 ++-\n list-objects-filter-options.c       |   7 +-\n list-objects-filter-options.h       |   3 +-\n list-objects-filter.c               | 115 +++++++++++++++++++++++-----\n t/t6112-rev-list-filters-objects.sh | 104 +++++++++++++++++++++++++\n 5 files changed, 210 insertions(+), 28 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex bab5f50b17..f8ab00f7c9 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -734,8 +734,13 @@ 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 the command-line (or\n+standard input when --stdin is used). <depth>=1 will include only the\n+tree and blobs which are referenced directly by a commit reachable from\n+<commit> or an explicitly-given object. <depth>=2 is like <depth>=1\n+while also including trees and blobs one more level removed from an\n+explicitly-given commit or tree.\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 e8da2e8581..5285e7674d 100644\n--- a/list-objects-filter-options.c\n+++ b/list-objects-filter-options.c\n@@ -50,16 +50,15 @@ 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, &filter_options->tree_exclude_depth)) {\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:<depth>'\"));\n \t\t\t}\n \t\t\treturn 1;\n \t\t}\n-\t\tfilter_options->choice = LOFC_TREE_NONE;\n+\t\tfilter_options->choice = LOFC_TREE_DEPTH;\n \t\treturn 0;\n \n \t} else if (skip_prefix(arg, \"sparse:oid=\", &v0)) {\ndiff --git a/list-objects-filter-options.h b/list-objects-filter-options.h\nindex af64e5c66f..477cd97029 100644\n--- a/list-objects-filter-options.h\n+++ b/list-objects-filter-options.h\n@@ -10,7 +10,7 @@ enum list_objects_filter_choice {\n \tLOFC_DISABLED = 0,\n \tLOFC_BLOB_NONE,\n \tLOFC_BLOB_LIMIT,\n-\tLOFC_TREE_NONE,\n+\tLOFC_TREE_DEPTH,\n \tLOFC_SPARSE_OID,\n \tLOFC_SPARSE_PATH,\n \tLOFC__COUNT /* must be last */\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_exclude_depth;\n };\n \n /* Normalized command line arguments */\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex a62624a1ce..ca99f0dd02 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -10,6 +10,7 @@\n #include \"list-objects.h\"\n #include \"list-objects-filter.h\"\n #include \"list-objects-filter-options.h\"\n+#include \"oidmap.h\"\n #include \"oidset.h\"\n #include \"object-store.h\"\n \n@@ -84,11 +85,43 @@ 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+\n+\t/*\n+\t * Maps trees to the minimum depth at which they were seen. It is not\n+\t * necessary to re-traverse a tree at deeper or equal depths than it has\n+\t * already been traversed.\n+\t *\n+\t * We can't use LOFR_MARK_SEEN for tree objects since this will prevent\n+\t * it from being traversed at shallower depths.\n+\t */\n+\tstruct oidmap seen_at_depth;\n+\n+\tunsigned long exclude_depth;\n+\tunsigned long current_depth;\n };\n \n-static enum list_objects_filter_result filter_trees_none(\n+struct seen_map_entry {\n+\tstruct oidmap_entry base;\n+\tsize_t depth;\n+};\n+\n+static void filter_trees_update_omits(\n+\tstruct object *obj,\n+\tstruct filter_trees_depth_data *filter_data,\n+\tint include_it)\n+{\n+\tif (!filter_data->omits)\n+\t\treturn;\n+\n+\tif (include_it)\n+\t\toidset_remove(filter_data->omits, &obj->oid);\n+\telse\n+\t\toidset_insert(filter_data->omits, &obj->oid);\n+}\n+\n+static enum list_objects_filter_result filter_trees_depth(\n \tstruct repository *r,\n \tenum list_objects_filter_situation filter_situation,\n \tstruct object *obj,\n@@ -96,43 +129,83 @@ static enum list_objects_filter_result filter_trees_none(\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+\tstruct seen_map_entry *seen_info;\n+\tint include_it = filter_data->current_depth <\n+\t\tfilter_data->exclude_depth;\n+\tint filter_res;\n+\tint already_seen;\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 (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} 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);\n+\t\tfilter_data->current_depth--;\n \t\treturn LOFR_ZERO;\n \n+\tcase LOFS_BLOB:\n+\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n+\t\treturn include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;\n+\n+\tcase LOFS_BEGIN_TREE:\n+\t\tseen_info = oidmap_get(\n+\t\t\t&filter_data->seen_at_depth, &obj->oid);\n+\t\tif (!seen_info) {\n+\t\t\tseen_info = xcalloc(1, sizeof(struct seen_map_entry));\n+\t\t\tseen_info->base.oid = obj->oid;\n+\t\t\tseen_info->depth = filter_data->current_depth;\n+\t\t\toidmap_put(&filter_data->seen_at_depth, seen_info);\n+\t\t\talready_seen = 0;\n+\t\t} else\n+\t\t\talready_seen =\n+\t\t\t\tfilter_data->current_depth >= seen_info->depth;\n+\n+\t\tif (already_seen)\n+\t\t\tfilter_res = LOFR_SKIP_TREE;\n+\t\telse {\n+\t\t\tseen_info->depth = filter_data->current_depth;\n+\t\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n+\n+\t\t\tif (include_it)\n+\t\t\t\tfilter_res = LOFR_DO_SHOW;\n+\t\t\telse if (filter_data->omits)\n+\t\t\t\tfilter_res = LOFR_ZERO;\n+\t\t\telse\n+\t\t\t\tfilter_res = LOFR_SKIP_TREE;\n+\t\t}\n+\n+\t\tfilter_data->current_depth++;\n+\t\treturn filter_res;\n \t}\n }\n \n-static void* filter_trees_none__init(\n+static void filter_trees_free(void *filter_data) {\n+\tstruct filter_trees_depth_data* d = filter_data;\n+\toidmap_free(&d->seen_at_depth, 1);\n+\tfree(d);\n+}\n+\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+\toidmap_init(&d->seen_at_depth, 0);\n+\td->exclude_depth = filter_options->tree_exclude_depth;\n+\td->current_depth = 0;\n \n-\t*filter_fn = filter_trees_none;\n-\t*filter_free_fn = free;\n+\t*filter_fn = filter_trees_depth;\n+\t*filter_free_fn = filter_trees_free;\n \treturn d;\n }\n \n@@ -430,7 +503,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 eb32505a6e..54e7096d40 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -294,6 +294,110 @@ test_expect_success 'filter a GIANT tree through tree:0' '\n \t! grep \"Skipping contents of tree [^.]\" filter_trace\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+\trepo=$1 &&\n+\tname=$2 &&\n+\n+\thash=$(git -C $repo rev-parse HEAD:$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+\texpect_has_with_different_name r4 filt/foo &&\n+\texpect_has_with_different_name r4 filt/subdir\n+'\n+\n+# Test tree:<depth> where a tree is iterated to twice - once where a subentry is\n+# too deep to be included, and again where the blob inside it is shallow enough\n+# to be included. This makes sure we don't use LOFR_MARK_SEEN incorrectly (we\n+# can't use it because a tree can be iterated over again at a lower depth).\n+\n+test_expect_success 'tree:<depth> where we iterate over tree at two levels' '\n+\tgit init r5 &&\n+\n+\tmkdir -p r5/a/subdir/b &&\n+\techo foo > r5/a/subdir/b/foo &&\n+\n+\tmkdir -p r5/subdir/b &&\n+\techo foo > r5/subdir/b/foo &&\n+\n+\tgit -C r5 add a subdir &&\n+\tgit -C r5 commit -m \"commit msg\" &&\n+\n+\tgit -C r5 rev-list --objects --filter=tree:4 HEAD >actual &&\n+\texpect_has_with_different_name r5 a/subdir/b/foo\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.20.0.rc2.403.gdbc3b29805-goog\n\n"},{"id":"364994","messageId":"20181210234030.176178-3-matvore@google.com","threadId":"49999","inReplyTo":"20181210234030.176178-1-matvore@google.com","subject":"[PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2018-12-10T23:40:30Z","receivedAt":"2018-12-10T23:40:56Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"If a tree has already been recorded as omitted, we don't need to\ntraverse it again just to collect its omits. Stop traversing trees a\nsecond time when collecting omits.\n\nSigned-off-by: Matthew DeVore <matvore@google.com>\n---\n list-objects-filter.c               | 17 +++++++++++------\n t/t6112-rev-list-filters-objects.sh | 11 ++++++++++-\n 2 files changed, 21 insertions(+), 7 deletions(-)\n\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex ca99f0dd02..3e9802c676 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -107,18 +107,18 @@ struct seen_map_entry {\n \tsize_t depth;\n };\n \n-static void filter_trees_update_omits(\n+static int filter_trees_update_omits(\n \tstruct object *obj,\n \tstruct filter_trees_depth_data *filter_data,\n \tint include_it)\n {\n \tif (!filter_data->omits)\n-\t\treturn;\n+\t\treturn 1;\n \n \tif (include_it)\n-\t\toidset_remove(filter_data->omits, &obj->oid);\n+\t\treturn oidset_remove(filter_data->omits, &obj->oid);\n \telse\n-\t\toidset_insert(filter_data->omits, &obj->oid);\n+\t\treturn oidset_insert(filter_data->omits, &obj->oid);\n }\n \n static enum list_objects_filter_result filter_trees_depth(\n@@ -170,12 +170,17 @@ static enum list_objects_filter_result filter_trees_depth(\n \t\tif (already_seen)\n \t\t\tfilter_res = LOFR_SKIP_TREE;\n \t\telse {\n+\t\t\tint been_omitted = filter_trees_update_omits(\n+\t\t\t\tobj, filter_data, include_it);\n \t\t\tseen_info->depth = filter_data->current_depth;\n-\t\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n \n \t\t\tif (include_it)\n \t\t\t\tfilter_res = LOFR_DO_SHOW;\n-\t\t\telse if (filter_data->omits)\n+\t\t\telse if (!been_omitted)\n+\t\t\t\t/*\n+\t\t\t\t * Must update omit information of children\n+\t\t\t\t * recursively; they have not been omitted yet.\n+\t\t\t\t */\n \t\t\t\tfilter_res = LOFR_ZERO;\n \t\t\telse\n \t\t\t\tfilter_res = LOFR_SKIP_TREE;\ndiff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh\nindex 54e7096d40..18b0b14d5a 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -283,7 +283,7 @@ test_expect_success 'verify tree:0 includes trees in \"filtered\" output' '\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+test_expect_success 'verify skipping tree iteration when not collecting omits' '\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@@ -377,6 +377,15 @@ test_expect_success 'test tree:# filter provisional omit for blob and tree' '\n \texpect_has_with_different_name r4 filt/subdir\n '\n \n+test_expect_success 'verify skipping tree iteration when collecting omits' '\n+\tGIT_TRACE=1 git -C r4 rev-list --filter-print-omitted \\\n+\t\t--objects --filter=tree:0 HEAD 2>filter_trace &&\n+\tgrep \"^Skipping contents of tree \" filter_trace >actual &&\n+\n+\techo \"Skipping contents of tree subdir/...\" >expect &&\n+\ttest_cmp expect actual\n+'\n+\n # Test tree:<depth> where a tree is iterated to twice - once where a subentry is\n # too deep to be included, and again where the blob inside it is shallow enough\n # to be included. This makes sure we don't use LOFR_MARK_SEEN incorrectly (we\n-- \n2.20.0.rc2.403.gdbc3b29805-goog\n\n"},{"id":"365045","messageId":"xmqq1s6oladv.fsf@gitster-ct.c.googlers.com","threadId":"49999","inReplyTo":"20181210234030.176178-1-matvore@google.com","subject":"Re: [PATCH v2 0/2] support for filtering trees and blobs based on depth","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-12-11T08:45:32Z","receivedAt":"2018-12-11T08:45:38Z","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> This is a follow-up to the original patchset at\n> https://public-inbox.org/git/cover.1539298957.git.matvore@google.com/ -\n> the purpose of that patchset and this one is to support positive integers for\n> tree:<depth>. Some of the prior patchset's patches were either already queued\n> (tree traversal optimization) or abandoned (documentation edit). This rendition\n> of the patchset adds a commit which optimizes away tree traversal when\n> collecting omits when iterating over a tree a second time.\n>\n> Thanks,\n>\n> Matthew DeVore (2):\n>   list-objects-filter: teach tree:# how to handle >0\n>   tree:<depth>: skip some trees even when collecting omits\n\nThis seems to require at least two topics still not in 'master';\nI've bookmarked the topic by merging sb/more-repo-in-api and\nnd/the-index into 'master' and then queueing these two patches on\ntop, to be able to merge it into 'pu' to see if there are bad\ninteractions with other topics and also give others easier access to\nthe topic in the integrated form.\n\nThanks.\n"},{"id":"366307","messageId":"50eeac4e-53e5-63c7-af8a-4067d92108e0@comcast.net","threadId":"49999","inReplyTo":"xmqq1s6oladv.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 0/2] support for filtering trees and blobs based on depth","fromName":"Matthew DeVore","fromEmail":"matvore@comcast.net","sentAt":"2019-01-08T00:56:46Z","receivedAt":"2019-01-08T00:57:19Z","isPatch":true,"sender":{"key":"matvore@comcast.net","avatar":"https://gravatar.com/avatar/550c64ce544f82818ad931e244dfb08bbb1febfa6d1ce3cfd65e76215ca0ac8a?d=mp&s=160"},"body":"\nOn 2018/12/11 0:45, Junio C Hamano wrote:\n> This seems to require at least two topics still not in 'master';\n> I've bookmarked the topic by merging sb/more-repo-in-api and\n> nd/the-index into 'master' and then queueing these two patches on\n> top, to be able to merge it into 'pu' to see if there are bad\n> interactions with other topics and also give others easier access to\n> the topic in the integrated form.\n>\n> Thanks.\n\nI'm re-reading the SubmittingPatches document and now I realize that I \nshould have based this on master. Thank you for merging things so that \nmy patch works. Let me know if it would be easier if I rebased this \npatch on top of master either now or on the next re-roll.\n\n\n"},{"id":"366308","messageId":"20190108015631.22727-1-jonathantanmy@google.com","threadId":"49999","inReplyTo":"20181210234030.176178-2-matvore@google.com","subject":"Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-01-08T01:56:31Z","receivedAt":"2019-01-08T01:56:38Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Thanks - as stated in your commit message, this adds quite a useful\npiece of functionality.\n\n> -\tcase LOFS_BEGIN_TREE:\n> -\tcase LOFS_BLOB:\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} 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);\n> +\t\tfilter_data->current_depth--;\n>  \t\treturn LOFR_ZERO;\n>  \n> +\tcase LOFS_BLOB:\n> +\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n> +\t\treturn include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;\n\nAny reason for moving \"case LOFS_BLOB\" (and \"case LOFS_BEGIN_TREE\"\nbelow) after LOFS_END_TREE?\n\nThis is drastically different from the previous case, but this makes\nsense - previously, all blobs accessed through traversal were not shown,\nbut now they are sometimes shown. Here, filter_trees_update_omits() is\nonly ever used to remove a blob from the omits set, since once this blob\nis encountered with include_it == true, it is marked as LOFR_MARK_SEEN\nand will not be traversed again.\n\n> +\tcase LOFS_BEGIN_TREE:\n> +\t\tseen_info = oidmap_get(\n> +\t\t\t&filter_data->seen_at_depth, &obj->oid);\n> +\t\tif (!seen_info) {\n> +\t\t\tseen_info = xcalloc(1, sizeof(struct seen_map_entry));\n\nUse sizeof(*seen_info).\n\n> +\t\t\tseen_info->base.oid = obj->oid;\n\nWe have been using oidcpy, but come to think of it, I'm not sure why...\n\n> +\t\t\tseen_info->depth = filter_data->current_depth;\n> +\t\t\toidmap_put(&filter_data->seen_at_depth, seen_info);\n> +\t\t\talready_seen = 0;\n> +\t\t} else\n> +\t\t\talready_seen =\n> +\t\t\t\tfilter_data->current_depth >= seen_info->depth;\n\nThere has been recently some clarification that if one branch of an\nif/else construct requires braces, braces should be put on all of them:\n1797dc5176 (\"CodingGuidelines: clarify multi-line brace style\",\n2017-01-17). Likewise below.\n\n> +\t\tif (already_seen)\n> +\t\t\tfilter_res = LOFR_SKIP_TREE;\n> +\t\telse {\n> +\t\t\tseen_info->depth = filter_data->current_depth;\n> +\t\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n> +\n> +\t\t\tif (include_it)\n> +\t\t\t\tfilter_res = LOFR_DO_SHOW;\n> +\t\t\telse if (filter_data->omits)\n> +\t\t\t\tfilter_res = LOFR_ZERO;\n> +\t\t\telse\n> +\t\t\t\tfilter_res = LOFR_SKIP_TREE;\n\nLooks straightforward. If we have already seen it at a shallower or\nequal depth, we can skip it (since we have already done the appropriate\nprocessing). Otherwise, we need to ensure that its \"omit\" is correctly\nset, and:\n - show it if include_it\n - don't do anything special if not include_it and we need the omit set\n - skip the tree if not include_it and we don't need the omit set\n\n> +static void filter_trees_free(void *filter_data) {\n> +\tstruct filter_trees_depth_data* d = filter_data;\n> +\toidmap_free(&d->seen_at_depth, 1);\n> +\tfree(d);\n> +}\n\nCheck for NULL-ness of filter_data too, to match the usual behavior of\nfree functions.\n\n> diff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh\n> index eb32505a6e..54e7096d40 100755\n> --- a/t/t6112-rev-list-filters-objects.sh\n> +++ b/t/t6112-rev-list-filters-objects.sh\n\n[snip]\n\nThanks for the tests that cover quite a wide range of cases. Can you\nalso demonstrate the case where a blob would normally be omitted\n(because it is too deep) but it is directly specified, so it is\nincluded.\n\n> +expect_has_with_different_name () {\n> +\trepo=$1 &&\n> +\tname=$2 &&\n> +\n> +\thash=$(git -C $repo rev-parse HEAD:$name) &&\n> +\t! grep \"^$hash $name$\" actual &&\n> +\tgrep \"^$hash \" actual &&\n> +\t! grep \"~$hash\" actual\n> +}\n\nShould we also check that a \"~\" entry appears with $name?\n"},{"id":"366309","messageId":"20190108020034.23648-1-jonathantanmy@google.com","threadId":"49999","inReplyTo":"20181210234030.176178-3-matvore@google.com","subject":"Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-01-08T02:00:34Z","receivedAt":"2019-01-08T02:00:39Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> -static void filter_trees_update_omits(\n> +static int filter_trees_update_omits(\n>  \tstruct object *obj,\n>  \tstruct filter_trees_depth_data *filter_data,\n>  \tint include_it)\n>  {\n>  \tif (!filter_data->omits)\n> -\t\treturn;\n> +\t\treturn 1;\n>  \n>  \tif (include_it)\n> -\t\toidset_remove(filter_data->omits, &obj->oid);\n> +\t\treturn oidset_remove(filter_data->omits, &obj->oid);\n>  \telse\n> -\t\toidset_insert(filter_data->omits, &obj->oid);\n> +\t\treturn oidset_insert(filter_data->omits, &obj->oid);\n>  }\n\nI think this function is getting too magical - if filter_data->omits is\nnot set, we pretend that we have omitted the tree, because we want the\nsame behavior when not needing omits and when the tree is omitted. Could\nthis be done another way?\n"},{"id":"366358","messageId":"54fba0d3-4b8e-1faf-4b2d-e67c1f5fbf02@comcast.net","threadId":"49999","inReplyTo":"20190108015631.22727-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Matthew DeVore","fromEmail":"matvore@comcast.net","sentAt":"2019-01-08T19:22:55Z","receivedAt":"2019-01-08T19:23:37Z","isPatch":true,"sender":{"key":"matvore@comcast.net","avatar":"https://gravatar.com/avatar/550c64ce544f82818ad931e244dfb08bbb1febfa6d1ce3cfd65e76215ca0ac8a?d=mp&s=160"},"body":"\nOn 2019/01/07 17:56, Jonathan Tan wrote:\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>> +\tcase LOFS_BLOB:\n>> +\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n>> +\t\treturn include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;\n> Any reason for moving \"case LOFS_BLOB\" (and \"case LOFS_BEGIN_TREE\"\n> below) after LOFS_END_TREE?\n\nI put LOFS_BLOB and after LOFS_END_TREE since that is the order in all \nthe other filter logic functions. I put LOFS_BEGIN_TREE at the end \n(which is different from the other filter logic functions) because it's \nusually better to put simpler things before longer or more complex \nthings. LOFS_BEGIN_TREE is much more complex and if it were not the last \nswitch section, it would tend to hide the sections that come after it.\n\nFWIW, I consider this the coding corollary of the end-weight problem in \nlinguistics - see https://www.thoughtco.com/end-weight-grammar-1690594 - \nthis is not my original idea, but something from the book Perl Best \nPractices, although that book only mentioned it in the context of \nordering clauses in single statements rather than ordering entire blocks.\n\n>\n> This is drastically different from the previous case, but this makes\n> sense - previously, all blobs accessed through traversal were not shown,\n> but now they are sometimes shown.\nYes.\n> Here, filter_trees_update_omits() is\n> only ever used to remove a blob from the omits set, since once this blob\n> is encountered with include_it == true, it is marked as LOFR_MARK_SEEN\n> and will not be traversed again.\nIt is possible that include_it can be false and then in a later \ninvocation it can be true. In that case, the blob will be added to the \nset and then removed from it.\n>\n>> +\tcase LOFS_BEGIN_TREE:\n>> +\t\tseen_info = oidmap_get(\n>> +\t\t\t&filter_data->seen_at_depth, &obj->oid);\n>> +\t\tif (!seen_info) {\n>> +\t\t\tseen_info = xcalloc(1, sizeof(struct seen_map_entry));\n> Use sizeof(*seen_info).\nDone.\n>\n>> +\t\t\tseen_info->base.oid = obj->oid;\n> We have been using oidcpy, but come to think of it, I'm not sure why...\nBecause the hash algorithm in use may not use the entire structure, \napparently. Or there are future improvements planned to the function and \nthey need to be picked up by all current hash-copying operations. Fixed.\n>\n>> +\t\t\tseen_info->depth = filter_data->current_depth;\n>> +\t\t\toidmap_put(&filter_data->seen_at_depth, seen_info);\n>> +\t\t\talready_seen = 0;\n>> +\t\t} else\n>> +\t\t\talready_seen =\n>> +\t\t\t\tfilter_data->current_depth >= seen_info->depth;\n> There has been recently some clarification that if one branch of an\n> if/else construct requires braces, braces should be put on all of them:\n> 1797dc5176 (\"CodingGuidelines: clarify multi-line brace style\",\n> 2017-01-17). Likewise below.\nDone, thank you - that's good to know.\n>\n>> +\t\tif (already_seen)\n>> +\t\t\tfilter_res = LOFR_SKIP_TREE;\n>> +\t\telse {\n>> +\t\t\tseen_info->depth = filter_data->current_depth;\n>> +\t\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n>> +\n>> +\t\t\tif (include_it)\n>> +\t\t\t\tfilter_res = LOFR_DO_SHOW;\n>> +\t\t\telse if (filter_data->omits)\n>> +\t\t\t\tfilter_res = LOFR_ZERO;\n>> +\t\t\telse\n>> +\t\t\t\tfilter_res = LOFR_SKIP_TREE;\n> Looks straightforward. If we have already seen it at a shallower or\n> equal depth, we can skip it (since we have already done the appropriate\n> processing). Otherwise, we need to ensure that its \"omit\" is correctly\n> set, and:\n>   - show it if include_it\n>   - don't do anything special if not include_it and we need the omit set\n>   - skip the tree if not include_it and we don't need the omit set\nRight.\n>\n>> +static void filter_trees_free(void *filter_data) {\n>> +\tstruct filter_trees_depth_data* d = filter_data;\n>> +\toidmap_free(&d->seen_at_depth, 1);\n>> +\tfree(d);\n>> +}\n> Check for NULL-ness of filter_data too, to match the usual behavior of\n> free functions.\n>\nDone.\n>> diff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh\n>> index eb32505a6e..54e7096d40 100755\n>> --- a/t/t6112-rev-list-filters-objects.sh\n>> +++ b/t/t6112-rev-list-filters-objects.sh\n> [snip]\n>\n> Thanks for the tests that cover quite a wide range of cases. Can you\n> also demonstrate the case where a blob would normally be omitted\n> (because it is too deep) but it is directly specified, so it is\n> included.\n\nI didn't exactly use TDD, but I did try to cover every line of code as \nwell as both branches of each ternary operator.\n\nAdded such a test.\n\n>\n>> +expect_has_with_different_name () {\n>> +\trepo=$1 &&\n>> +\tname=$2 &&\n>> +\n>> +\thash=$(git -C $repo rev-parse HEAD:$name) &&\n>> +\t! grep \"^$hash $name$\" actual &&\n>> +\tgrep \"^$hash \" actual &&\n>> +\t! grep \"~$hash\" actual\n>> +}\n> Should we also check that a \"~\" entry appears with $name?\n\nI don't believe there is a way to get the object names to appear next to \n~ entries (note that the names are not saved in the omits oidset).\n\nFor your reference, here is an interdiff for this particular patch after \napplying your comments:\n\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -158,18 +158,19 @@ static enum list_objects_filter_result \nfilter_trees_depth(\n          seen_info = oidmap_get(\n              &filter_data->seen_at_depth, &obj->oid);\n          if (!seen_info) {\n-            seen_info = xcalloc(1, sizeof(struct seen_map_entry));\n-            seen_info->base.oid = obj->oid;\n+            seen_info = xcalloc(1, sizeof(*seen_info));\n+            oidcpy(&seen_info->base.oid, &obj->oid);\n              seen_info->depth = filter_data->current_depth;\n              oidmap_put(&filter_data->seen_at_depth, seen_info);\n              already_seen = 0;\n-        } else\n+        } else {\n              already_seen =\n                  filter_data->current_depth >= seen_info->depth;\n+        }\n\n-        if (already_seen)\n+        if (already_seen) {\n              filter_res = LOFR_SKIP_TREE;\n-        else {\n+        } else {\n              int been_omitted = filter_trees_update_omits(\n                  obj, filter_data, include_it);\n              seen_info->depth = filter_data->current_depth;\n@@ -193,6 +194,8 @@ static enum list_objects_filter_result \nfilter_trees_depth(\n\n  static void filter_trees_free(void *filter_data) {\n      struct filter_trees_depth_data* d = filter_data;\n+    if (!d)\n+        return;\n      oidmap_free(&d->seen_at_depth, 1);\n      free(d);\n  }\ndiff --git a/t/'t6112-rev-list-filters-objects.sh \nb/t/'t6112-rev-list-filters-objects.sh\nnew file mode 100644\nindex 0000000000..e69de29bb2\ndiff --git a/t/t6112-rev-list-filters-objects.sh \nb/t/t6112-rev-list-filters-objects.sh\nindex 18b0b14d5a..d6edad6a01 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -407,6 +407,13 @@ test_expect_success 'tree:<depth> where we iterate \nover tree at two levels' '\n      expect_has_with_different_name r5 a/subdir/b/foo\n  '\n\n+test_expect_success 'tree:<depth> which filters out blob but given as \narg' '\n+    export blob_hash=$(git -C r4 rev-parse HEAD:subdir/bar) &&\n+\n+    git -C r4 rev-list --objects --filter=tree:1 HEAD $blob_hash >actual &&\n+    grep ^$blob_hash 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\n\n\n"},{"id":"366382","messageId":"20190108231945.36970-1-jonathantanmy@google.com","threadId":"49999","inReplyTo":"54fba0d3-4b8e-1faf-4b2d-e67c1f5fbf02@comcast.net","subject":"Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-01-08T23:19:45Z","receivedAt":"2019-01-08T23:19:51Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> > Any reason for moving \"case LOFS_BLOB\" (and \"case LOFS_BEGIN_TREE\"\n> > below) after LOFS_END_TREE?\n> \n> I put LOFS_BLOB and after LOFS_END_TREE since that is the order in all \n> the other filter logic functions. I put LOFS_BEGIN_TREE at the end \n> (which is different from the other filter logic functions) because it's \n> usually better to put simpler things before longer or more complex \n> things. LOFS_BEGIN_TREE is much more complex and if it were not the last \n> switch section, it would tend to hide the sections that come after it.\n> \n> FWIW, I consider this the coding corollary of the end-weight problem in \n> linguistics - see https://www.thoughtco.com/end-weight-grammar-1690594 - \n> this is not my original idea, but something from the book Perl Best \n> Practices, although that book only mentioned it in the context of \n> ordering clauses in single statements rather than ordering entire blocks.\n\nOK - my thinking was that we should minimize the diff, but this\nreasoning makes sense to me.\n\n> > Here, filter_trees_update_omits() is\n> > only ever used to remove a blob from the omits set, since once this blob\n> > is encountered with include_it == true, it is marked as LOFR_MARK_SEEN\n> > and will not be traversed again.\n> It is possible that include_it can be false and then in a later \n> invocation it can be true. In that case, the blob will be added to the \n> set and then removed from it.\n\nAh...yes, you're right.\n\n> For your reference, here is an interdiff for this particular patch after \n> applying your comments:\n\nThe interdiff looks good, thanks. All my issues are resolved.\n"},{"id":"366383","messageId":"20190108232251.37748-1-jonathantanmy@google.com","threadId":"49999","inReplyTo":"20190108020034.23648-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-01-08T23:22:51Z","receivedAt":"2019-01-08T23:22:56Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> > -static void filter_trees_update_omits(\n> > +static int filter_trees_update_omits(\n> >  \tstruct object *obj,\n> >  \tstruct filter_trees_depth_data *filter_data,\n> >  \tint include_it)\n> >  {\n> >  \tif (!filter_data->omits)\n> > -\t\treturn;\n> > +\t\treturn 1;\n> >  \n> >  \tif (include_it)\n> > -\t\toidset_remove(filter_data->omits, &obj->oid);\n> > +\t\treturn oidset_remove(filter_data->omits, &obj->oid);\n> >  \telse\n> > -\t\toidset_insert(filter_data->omits, &obj->oid);\n> > +\t\treturn oidset_insert(filter_data->omits, &obj->oid);\n> >  }\n> \n> I think this function is getting too magical - if filter_data->omits is\n> not set, we pretend that we have omitted the tree, because we want the\n> same behavior when not needing omits and when the tree is omitted. Could\n> this be done another way?\n\nGiving some more thought to this, since this is a static function, maybe\ndocumenting it as \"Returns 1 if the objects that this object references need to\nbe traversed for \"omits\" updates, and 0 otherwise\" (with the appropriate code\nupdates) would suffice.\n"},{"id":"366386","messageId":"xmqqftu24t80.fsf@gitster-ct.c.googlers.com","threadId":"49999","inReplyTo":"20190108231945.36970-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-08T23:36:47Z","receivedAt":"2019-01-08T23:36:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n>> For your reference, here is an interdiff for this particular patch after \n>> applying your comments:\n>\n> The interdiff looks good, thanks. All my issues are resolved.\n\nJust to make sure.  That's not \"v2 is good\", but \"v2 plus that\nproposed update, when materializes, would be good\", right?  I'll\nmark the topic as \"expecting a reroll\" then.\n\nThanks.\n"},{"id":"366387","messageId":"xmqqbm4q4t3j.fsf@gitster-ct.c.googlers.com","threadId":"49999","inReplyTo":"20190108015631.22727-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-08T23:39:28Z","receivedAt":"2019-01-08T23:39:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n>> +static void filter_trees_free(void *filter_data) {\n>> +\tstruct filter_trees_depth_data* d = filter_data;\n>> +\toidmap_free(&d->seen_at_depth, 1);\n>> +\tfree(d);\n>> +}\n>\n> Check for NULL-ness of filter_data too, to match the usual behavior of\n> free functions.\n\nAlso, the asterisk sticks to the variable, not type, i.e.\n\n\tstruct filter_trees_depth_data *d = filter_data;\n\n"},{"id":"366388","messageId":"20190108234140.41554-1-jonathantanmy@google.com","threadId":"49999","inReplyTo":"xmqqftu24t80.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-01-08T23:41:40Z","receivedAt":"2019-01-08T23:41:49Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Jonathan Tan <jonathantanmy@google.com> writes:\n> \n> >> For your reference, here is an interdiff for this particular patch after \n> >> applying your comments:\n> >\n> > The interdiff looks good, thanks. All my issues are resolved.\n> \n> Just to make sure.  That's not \"v2 is good\", but \"v2 plus that\n> proposed update, when materializes, would be good\", right?  I'll\n> mark the topic as \"expecting a reroll\" then.\n\nYes, that's right - there should be a reroll of this topic. Also,\nbesides the proposed update, I have a comment in patch 2 of this set.\n"},{"id":"366390","messageId":"8cb0dd36-4c49-228e-17ad-538fb377ffe4@comcast.net","threadId":"49999","inReplyTo":"20190108020034.23648-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits","fromName":"Matthew DeVore","fromEmail":"matvore@comcast.net","sentAt":"2019-01-09T00:29:52Z","receivedAt":"2019-01-09T00:30:23Z","isPatch":true,"sender":{"key":"matvore@comcast.net","avatar":"https://gravatar.com/avatar/550c64ce544f82818ad931e244dfb08bbb1febfa6d1ce3cfd65e76215ca0ac8a?d=mp&s=160"},"body":"Thank you for the review :) See below.\n\nOn 2019/01/07 18:00, Jonathan Tan wrote:\n>> -static void filter_trees_update_omits(\n>> +static int filter_trees_update_omits(\n>>   \tstruct object *obj,\n>>   \tstruct filter_trees_depth_data *filter_data,\n>>   \tint include_it)\n>>   {\n>>   \tif (!filter_data->omits)\n>> -\t\treturn;\n>> +\t\treturn 1;\n>>   \n>>   \tif (include_it)\n>> -\t\toidset_remove(filter_data->omits, &obj->oid);\n>> +\t\treturn oidset_remove(filter_data->omits, &obj->oid);\n>>   \telse\n>> -\t\toidset_insert(filter_data->omits, &obj->oid);\n>> +\t\treturn oidset_insert(filter_data->omits, &obj->oid);\n>>   }\n> I think this function is getting too magical - if filter_data->omits is\n> not set, we pretend that we have omitted the tree, because we want the\n> same behavior when not needing omits and when the tree is omitted. Could\n> this be done another way?\n\nYes, returning a manipulative lie when omits is NULL is rather \nconfusing. So I changed it to this (interdiff):\n\n+/* Returns 1 if the oid was in the omits set before it was invoked. */\n  static int filter_trees_update_omits(\n      struct object *obj,\n      struct filter_trees_depth_data *filter_data,\n      int include_it)\n  {\n      if (!filter_data->omits)\n-        return 1;\n+        return 0;\n\n      if (include_it)\n          return oidset_remove(filter_data->omits, &obj->oid);\n@@ -177,7 +178,7 @@ static enum list_objects_filter_result \nfilter_trees_depth(\n\n              if (include_it)\n                  filter_res = LOFR_DO_SHOW;\n-            else if (!been_omitted)\n+            else if (filter_data->omits && !been_omitted)\n                  /*\n                   * Must update omit information of children\n                   * recursively; they have not been omitted yet.\n\n"},{"id":"366392","messageId":"1568150001.183199.1547001781704@connect.xfinity.com","threadId":"49999","inReplyTo":"xmqqbm4q4t3j.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"MATTHEW DEVORE","fromEmail":"matvore@comcast.net","sentAt":"2019-01-09T02:43:01Z","receivedAt":"2019-01-09T02:43:04Z","isPatch":true,"sender":{"key":"matvore@comcast.net","avatar":"https://gravatar.com/avatar/550c64ce544f82818ad931e244dfb08bbb1febfa6d1ce3cfd65e76215ca0ac8a?d=mp&s=160"},"body":"\n> On January 8, 2019 at 3:39 PM Junio C Hamano <gitster@pobox.com> wrote:\n> \n> Also, the asterisk sticks to the variable, not type, i.e.\n> \n> \tstruct filter_trees_depth_data *d = filter_data;\n>\n\nFixed. Thanks.\n"},{"id":"366393","messageId":"1446107549.183303.1547002024564@connect.xfinity.com","threadId":"49999","inReplyTo":"20190108232251.37748-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits","fromName":"MATTHEW DEVORE","fromEmail":"matvore@comcast.net","sentAt":"2019-01-09T02:47:04Z","receivedAt":"2019-01-09T02:47:07Z","isPatch":true,"sender":{"key":"matvore@comcast.net","avatar":"https://gravatar.com/avatar/550c64ce544f82818ad931e244dfb08bbb1febfa6d1ce3cfd65e76215ca0ac8a?d=mp&s=160"},"body":"\n> On January 8, 2019 at 3:22 PM Jonathan Tan <jonathantanmy@google.com> wrote:\n> \n> \n> > > -static void filter_trees_update_omits(\n> > > +static int filter_trees_update_omits(\n> > >  \tstruct object *obj,\n> > >  \tstruct filter_trees_depth_data *filter_data,\n> > >  \tint include_it)\n> > >  {\n> > >  \tif (!filter_data->omits)\n> > > -\t\treturn;\n> > > +\t\treturn 1;\n> > >  \n> > >  \tif (include_it)\n> > > -\t\toidset_remove(filter_data->omits, &obj->oid);\n> > > +\t\treturn oidset_remove(filter_data->omits, &obj->oid);\n> > >  \telse\n> > > -\t\toidset_insert(filter_data->omits, &obj->oid);\n> > > +\t\treturn oidset_insert(filter_data->omits, &obj->oid);\n> > >  }\n> > \n> > I think this function is getting too magical - if filter_data->omits is\n> > not set, we pretend that we have omitted the tree, because we want the\n> > same behavior when not needing omits and when the tree is omitted. Could\n> > this be done another way?\n> \n> Giving some more thought to this, since this is a static function, maybe\n> documenting it as \"Returns 1 if the objects that this object references need to\n> be traversed for \"omits\" updates, and 0 otherwise\" (with the appropriate code\n> updates) would suffice.\n\nThat's not bad. But I sent a correction which is more like \"/* Returns 1 if the oid was in the omits set before it was invoked. */\" and returns 0 if omits was NULL. I thought it clearer when the function returns a value in terms of its own arguments and logic, rather than what the caller needs to do. The code I save going with your suggestion (vs. the one I just sent) is offset by the necessity of more detailed comments.\n"},{"id":"366394","messageId":"20190109025914.247473-1-matvore@google.com","threadId":"49999","inReplyTo":"20181210234030.176178-1-matvore@google.com","subject":"[PATCH v3 0/2] support for filtering trees and blobs based on depth","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2019-01-09T02:59:12Z","receivedAt":"2019-01-09T02:59:27Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"This applies suggestions from Jonathan Tan and Junio. These are mostly\nstylistic and readability changes, although there is also an added test case\nin t/t6112-rev-list-filters-objects.sh which checks for the scenario when\nfiltering which would exclude a blob, but the blob is given on the command\nline.\n\nThis has been rebased onto master, while the prior version was based on next.\n\nThank you,\n\nMatthew DeVore (2):\n  list-objects-filter: teach tree:# how to handle >0\n  tree:<depth>: skip some trees even when collecting omits\n\n Documentation/rev-list-options.txt  |   9 +-\n list-objects-filter-options.c       |   7 +-\n list-objects-filter-options.h       |   3 +-\n list-objects-filter.c               | 122 +++++++++++++++++++++++-----\n t/t6112-rev-list-filters-objects.sh | 122 +++++++++++++++++++++++++++-\n 5 files changed, 235 insertions(+), 28 deletions(-)\n\n-- \n2.20.1.97.g81188d93c3-goog\n\n"},{"id":"366395","messageId":"20190109025914.247473-2-matvore@google.com","threadId":"49999","inReplyTo":"20190109025914.247473-1-matvore@google.com","subject":"[PATCH v3 1/2] list-objects-filter: teach tree:# how to handle >0","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2019-01-09T02:59:13Z","receivedAt":"2019-01-09T02:59:30Z","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\nAnother way of considering this feature is as a way to reduce\nround-trips, since the client can get any number of levels of\ndirectories in a single request, rather than wait for each level of tree\nobjects to come back, whose entries are used to construct a new request.\n\nSigned-off-by: Matthew DeVore <matvore@google.com>\n---\n Documentation/rev-list-options.txt  |   9 ++-\n list-objects-filter-options.c       |   7 +-\n list-objects-filter-options.h       |   3 +-\n list-objects-filter.c               | 116 +++++++++++++++++++++++-----\n t/t6112-rev-list-filters-objects.sh | 111 ++++++++++++++++++++++++++\n 5 files changed, 219 insertions(+), 27 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex bab5f50b17..f8ab00f7c9 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -734,8 +734,13 @@ 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 the command-line (or\n+standard input when --stdin is used). <depth>=1 will include only the\n+tree and blobs which are referenced directly by a commit reachable from\n+<commit> or an explicitly-given object. <depth>=2 is like <depth>=1\n+while also including trees and blobs one more level removed from an\n+explicitly-given commit or tree.\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 e8da2e8581..5285e7674d 100644\n--- a/list-objects-filter-options.c\n+++ b/list-objects-filter-options.c\n@@ -50,16 +50,15 @@ 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, &filter_options->tree_exclude_depth)) {\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:<depth>'\"));\n \t\t\t}\n \t\t\treturn 1;\n \t\t}\n-\t\tfilter_options->choice = LOFC_TREE_NONE;\n+\t\tfilter_options->choice = LOFC_TREE_DEPTH;\n \t\treturn 0;\n \n \t} else if (skip_prefix(arg, \"sparse:oid=\", &v0)) {\ndiff --git a/list-objects-filter-options.h b/list-objects-filter-options.h\nindex af64e5c66f..477cd97029 100644\n--- a/list-objects-filter-options.h\n+++ b/list-objects-filter-options.h\n@@ -10,7 +10,7 @@ enum list_objects_filter_choice {\n \tLOFC_DISABLED = 0,\n \tLOFC_BLOB_NONE,\n \tLOFC_BLOB_LIMIT,\n-\tLOFC_TREE_NONE,\n+\tLOFC_TREE_DEPTH,\n \tLOFC_SPARSE_OID,\n \tLOFC_SPARSE_PATH,\n \tLOFC__COUNT /* must be last */\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_exclude_depth;\n };\n \n /* Normalized command line arguments */\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex a62624a1ce..786e0dd0b1 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -10,6 +10,7 @@\n #include \"list-objects.h\"\n #include \"list-objects-filter.h\"\n #include \"list-objects-filter-options.h\"\n+#include \"oidmap.h\"\n #include \"oidset.h\"\n #include \"object-store.h\"\n \n@@ -84,11 +85,43 @@ 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+\n+\t/*\n+\t * Maps trees to the minimum depth at which they were seen. It is not\n+\t * necessary to re-traverse a tree at deeper or equal depths than it has\n+\t * already been traversed.\n+\t *\n+\t * We can't use LOFR_MARK_SEEN for tree objects since this will prevent\n+\t * it from being traversed at shallower depths.\n+\t */\n+\tstruct oidmap seen_at_depth;\n+\n+\tunsigned long exclude_depth;\n+\tunsigned long current_depth;\n };\n \n-static enum list_objects_filter_result filter_trees_none(\n+struct seen_map_entry {\n+\tstruct oidmap_entry base;\n+\tsize_t depth;\n+};\n+\n+static void filter_trees_update_omits(\n+\tstruct object *obj,\n+\tstruct filter_trees_depth_data *filter_data,\n+\tint include_it)\n+{\n+\tif (!filter_data->omits)\n+\t\treturn;\n+\n+\tif (include_it)\n+\t\toidset_remove(filter_data->omits, &obj->oid);\n+\telse\n+\t\toidset_insert(filter_data->omits, &obj->oid);\n+}\n+\n+static enum list_objects_filter_result filter_trees_depth(\n \tstruct repository *r,\n \tenum list_objects_filter_situation filter_situation,\n \tstruct object *obj,\n@@ -96,43 +129,86 @@ static enum list_objects_filter_result filter_trees_none(\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+\tstruct seen_map_entry *seen_info;\n+\tint include_it = filter_data->current_depth <\n+\t\tfilter_data->exclude_depth;\n+\tint filter_res;\n+\tint already_seen;\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_END_TREE:\n+\t\tassert(obj->type == OBJ_TREE);\n+\t\tfilter_data->current_depth--;\n+\t\treturn LOFR_ZERO;\n+\n \tcase LOFS_BLOB:\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\tfilter_trees_update_omits(obj, filter_data, include_it);\n+\t\treturn include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;\n+\n+\tcase LOFS_BEGIN_TREE:\n+\t\tseen_info = oidmap_get(\n+\t\t\t&filter_data->seen_at_depth, &obj->oid);\n+\t\tif (!seen_info) {\n+\t\t\tseen_info = xcalloc(1, sizeof(*seen_info));\n+\t\t\toidcpy(&seen_info->base.oid, &obj->oid);\n+\t\t\tseen_info->depth = filter_data->current_depth;\n+\t\t\toidmap_put(&filter_data->seen_at_depth, seen_info);\n+\t\t\talready_seen = 0;\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\talready_seen =\n+\t\t\t\tfilter_data->current_depth >= seen_info->depth;\n \t\t}\n \n-\tcase LOFS_END_TREE:\n-\t\tassert(obj->type == OBJ_TREE);\n-\t\treturn LOFR_ZERO;\n+\t\tif (already_seen) {\n+\t\t\tfilter_res = LOFR_SKIP_TREE;\n+\t\t} else {\n+\t\t\tseen_info->depth = filter_data->current_depth;\n+\t\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n+\n+\t\t\tif (include_it)\n+\t\t\t\tfilter_res = LOFR_DO_SHOW;\n+\t\t\telse if (filter_data->omits)\n+\t\t\t\tfilter_res = LOFR_ZERO;\n+\t\t\telse\n+\t\t\t\tfilter_res = LOFR_SKIP_TREE;\n+\t\t}\n \n+\t\tfilter_data->current_depth++;\n+\t\treturn filter_res;\n \t}\n }\n \n-static void* filter_trees_none__init(\n+static void filter_trees_free(void *filter_data) {\n+\tstruct filter_trees_depth_data *d = filter_data;\n+\tif (!d)\n+\t\treturn;\n+\toidmap_free(&d->seen_at_depth, 1);\n+\tfree(d);\n+}\n+\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+\toidmap_init(&d->seen_at_depth, 0);\n+\td->exclude_depth = filter_options->tree_exclude_depth;\n+\td->current_depth = 0;\n \n-\t*filter_fn = filter_trees_none;\n-\t*filter_free_fn = free;\n+\t*filter_fn = filter_trees_depth;\n+\t*filter_free_fn = filter_trees_free;\n \treturn d;\n }\n \n@@ -430,7 +506,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 eb32505a6e..706845f1d9 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -294,6 +294,117 @@ test_expect_success 'filter a GIANT tree through tree:0' '\n \t! grep \"Skipping contents of tree [^.]\" filter_trace\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+\trepo=$1 &&\n+\tname=$2 &&\n+\n+\thash=$(git -C $repo rev-parse HEAD:$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+\texpect_has_with_different_name r4 filt/foo &&\n+\texpect_has_with_different_name r4 filt/subdir\n+'\n+\n+# Test tree:<depth> where a tree is iterated to twice - once where a subentry is\n+# too deep to be included, and again where the blob inside it is shallow enough\n+# to be included. This makes sure we don't use LOFR_MARK_SEEN incorrectly (we\n+# can't use it because a tree can be iterated over again at a lower depth).\n+\n+test_expect_success 'tree:<depth> where we iterate over tree at two levels' '\n+\tgit init r5 &&\n+\n+\tmkdir -p r5/a/subdir/b &&\n+\techo foo > r5/a/subdir/b/foo &&\n+\n+\tmkdir -p r5/subdir/b &&\n+\techo foo > r5/subdir/b/foo &&\n+\n+\tgit -C r5 add a subdir &&\n+\tgit -C r5 commit -m \"commit msg\" &&\n+\n+\tgit -C r5 rev-list --objects --filter=tree:4 HEAD >actual &&\n+\texpect_has_with_different_name r5 a/subdir/b/foo\n+'\n+\n+test_expect_success 'tree:<depth> which filters out blob but given as arg' '\n+\tblob_hash=$(git -C r4 rev-parse HEAD:subdir/bar) &&\n+\n+\tgit -C r4 rev-list --objects --filter=tree:1 HEAD $blob_hash >actual &&\n+\tgrep ^$blob_hash 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.20.1.97.g81188d93c3-goog\n\n"},{"id":"366396","messageId":"20190109025914.247473-3-matvore@google.com","threadId":"49999","inReplyTo":"20190109025914.247473-1-matvore@google.com","subject":"[PATCH v3 2/2] tree:<depth>: skip some trees even when collecting omits","fromName":"Matthew DeVore","fromEmail":"matvore@google.com","sentAt":"2019-01-09T02:59:14Z","receivedAt":"2019-01-09T02:59:33Z","isPatch":true,"sender":{"key":"matvore@google.com","avatar":"https://avatars.githubusercontent.com/u/946637?v=4"},"body":"If a tree has already been recorded as omitted, we don't need to\ntraverse it again just to collect its omits. Stop traversing trees a\nsecond time when collecting omits.\n\nSigned-off-by: Matthew DeVore <matvore@google.com>\n---\n list-objects-filter.c               | 18 ++++++++++++------\n t/t6112-rev-list-filters-objects.sh | 11 ++++++++++-\n 2 files changed, 22 insertions(+), 7 deletions(-)\n\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex 786e0dd0b1..ee449de3f7 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -107,18 +107,19 @@ struct seen_map_entry {\n \tsize_t depth;\n };\n \n-static void filter_trees_update_omits(\n+/* Returns 1 if the oid was in the omits set before it was invoked. */\n+static int filter_trees_update_omits(\n \tstruct object *obj,\n \tstruct filter_trees_depth_data *filter_data,\n \tint include_it)\n {\n \tif (!filter_data->omits)\n-\t\treturn;\n+\t\treturn 0;\n \n \tif (include_it)\n-\t\toidset_remove(filter_data->omits, &obj->oid);\n+\t\treturn oidset_remove(filter_data->omits, &obj->oid);\n \telse\n-\t\toidset_insert(filter_data->omits, &obj->oid);\n+\t\treturn oidset_insert(filter_data->omits, &obj->oid);\n }\n \n static enum list_objects_filter_result filter_trees_depth(\n@@ -171,12 +172,17 @@ static enum list_objects_filter_result filter_trees_depth(\n \t\tif (already_seen) {\n \t\t\tfilter_res = LOFR_SKIP_TREE;\n \t\t} else {\n+\t\t\tint been_omitted = filter_trees_update_omits(\n+\t\t\t\tobj, filter_data, include_it);\n \t\t\tseen_info->depth = filter_data->current_depth;\n-\t\t\tfilter_trees_update_omits(obj, filter_data, include_it);\n \n \t\t\tif (include_it)\n \t\t\t\tfilter_res = LOFR_DO_SHOW;\n-\t\t\telse if (filter_data->omits)\n+\t\t\telse if (filter_data->omits && !been_omitted)\n+\t\t\t\t/*\n+\t\t\t\t * Must update omit information of children\n+\t\t\t\t * recursively; they have not been omitted yet.\n+\t\t\t\t */\n \t\t\t\tfilter_res = LOFR_ZERO;\n \t\t\telse\n \t\t\t\tfilter_res = LOFR_SKIP_TREE;\ndiff --git a/t/t6112-rev-list-filters-objects.sh b/t/t6112-rev-list-filters-objects.sh\nindex 706845f1d9..eb9e4119e2 100755\n--- a/t/t6112-rev-list-filters-objects.sh\n+++ b/t/t6112-rev-list-filters-objects.sh\n@@ -283,7 +283,7 @@ test_expect_success 'verify tree:0 includes trees in \"filtered\" output' '\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+test_expect_success 'verify skipping tree iteration when not collecting omits' '\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@@ -377,6 +377,15 @@ test_expect_success 'test tree:# filter provisional omit for blob and tree' '\n \texpect_has_with_different_name r4 filt/subdir\n '\n \n+test_expect_success 'verify skipping tree iteration when collecting omits' '\n+\tGIT_TRACE=1 git -C r4 rev-list --filter-print-omitted \\\n+\t\t--objects --filter=tree:0 HEAD 2>filter_trace &&\n+\tgrep \"^Skipping contents of tree \" filter_trace >actual &&\n+\n+\techo \"Skipping contents of tree subdir/...\" >expect &&\n+\ttest_cmp expect actual\n+'\n+\n # Test tree:<depth> where a tree is iterated to twice - once where a subentry is\n # too deep to be included, and again where the blob inside it is shallow enough\n # to be included. This makes sure we don't use LOFR_MARK_SEEN incorrectly (we\n-- \n2.20.1.97.g81188d93c3-goog\n\n"},{"id":"366432","messageId":"20190109180633.10273-1-jonathantanmy@google.com","threadId":"49999","inReplyTo":"20190109025914.247473-1-matvore@google.com","subject":"Re: [PATCH v3 0/2] support for filtering trees and blobs based on depth","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-01-09T18:06:33Z","receivedAt":"2019-01-09T18:06:41Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> This applies suggestions from Jonathan Tan and Junio. These are mostly\n> stylistic and readability changes, although there is also an added test case\n> in t/t6112-rev-list-filters-objects.sh which checks for the scenario when\n> filtering which would exclude a blob, but the blob is given on the command\n> line.\n> \n> This has been rebased onto master, while the prior version was based on next.\n> \n> Thank you,\n\nThanks, these 2 patches are Reviewed-by: me.\n\nYour approach in the 2nd patch makes more sense, and I checked that both\noidset_insert() and oidset_remove() return 1 when the element in\nquestion was in the set (prior to invocation of the function), so that\nworks.\n"},{"id":"366783","messageId":"xmqqftttpk8w.fsf@gitster-ct.c.googlers.com","threadId":"49999","inReplyTo":"20190109180633.10273-1-jonathantanmy@google.com","subject":"Re: [PATCH v3 0/2] support for filtering trees and blobs based on depth","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-15T23:35:27Z","receivedAt":"2019-01-15T23:35:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n>> This applies suggestions from Jonathan Tan and Junio. These are mostly\n>> stylistic and readability changes, although there is also an added test case\n>> in t/t6112-rev-list-filters-objects.sh which checks for the scenario when\n>> filtering which would exclude a blob, but the blob is given on the command\n>> line.\n>> \n>> This has been rebased onto master, while the prior version was based on next.\n>> \n>> Thank you,\n>\n> Thanks, these 2 patches are Reviewed-by: me.\n>\n> Your approach in the 2nd patch makes more sense, and I checked that both\n> oidset_insert() and oidset_remove() return 1 when the element in\n> question was in the set (prior to invocation of the function), so that\n> works.\n\nThis is turning out to be messier than I like.\n\nThe topic is tangled with too many things in flight and I think I\nreduced its dependencies down to nd/the-index and\nsb/more-repo-in-api plus then-current tip of master (and that is why\nit is based on a1411cecc7), but it seems that it wants a bit more\nthan that; builtin/rebase.c at its tip does not even compile, so\nI'll need to wiggle the topic before it can go to 'next'.\n\nAnd worse yet, it seems that filter-options-should-use-plain-int\ntopic depends on this topic in turn as it wants to use\nLOFC_TREEE_DEPTH.\n\n"},{"id":"366784","messageId":"xmqqbm4hpjyg.fsf@gitster-ct.c.googlers.com","threadId":"49999","inReplyTo":"xmqqftttpk8w.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3 0/2] support for filtering trees and blobs based on depth","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-15T23:41:43Z","receivedAt":"2019-01-15T23:41:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> This is turning out to be messier than I like.\n>\n> The topic is tangled with too many things in flight and I think I\n> reduced its dependencies down to nd/the-index and\n> sb/more-repo-in-api plus then-current tip of master (and that is why\n> it is based on a1411cecc7), but it seems that it wants a bit more\n> than that; builtin/rebase.c at its tip does not even compile, so\n> I'll need to wiggle the topic before it can go to 'next'.\n\nHalf false alarm.  I do need to wiggle the topic, but that was not\nbecause the choice of base was bad.  It was that nd/the-index plus\nsb/more-repo-in-api had semantic merge conflicts with the then-current\nmaster.\n\n> And worse yet, it seems that filter-options-should-use-plain-int\n> topic depends on this topic in turn as it wants to use\n> LOFC_TREEE_DEPTH.\n\nThis part is still true.  The scaling-factor-over-the-wire topic\ndoes need to be rebuilt on top of this one.\n"},{"id":"366891","messageId":"04d6b46f-da87-bde2-1511-a9f2071bf034@comcast.net","threadId":"49999","inReplyTo":"xmqqbm4hpjyg.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3 0/2] support for filtering trees and blobs based on depth","fromName":"Matthew DeVore","fromEmail":"matvore@comcast.net","sentAt":"2019-01-17T00:14:56Z","receivedAt":"2019-01-17T00:15:16Z","isPatch":true,"sender":{"key":"matvore@comcast.net","avatar":"https://gravatar.com/avatar/550c64ce544f82818ad931e244dfb08bbb1febfa6d1ce3cfd65e76215ca0ac8a?d=mp&s=160"},"body":"\nOn 2019/01/15 15:41, Junio C Hamano wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n>\n>> This is turning out to be messier than I like.\n>>\n>> The topic is tangled with too many things in flight and I think I\n>> reduced its dependencies down to nd/the-index and\n>> sb/more-repo-in-api plus then-current tip of master (and that is why\n>> it is based on a1411cecc7), but it seems that it wants a bit more\n>> than that; builtin/rebase.c at its tip does not even compile, so\n>> I'll need to wiggle the topic before it can go to 'next'.\n> Half false alarm.  I do need to wiggle the topic, but that was not\n> because the choice of base was bad.  It was that nd/the-index plus\n> sb/more-repo-in-api had semantic merge conflicts with the then-current\n> master.\n\nIf I understand right, this is a product of the fact that you had to \nmerge these branches together and base my change on top of them, and \nthat is a result of that fact that I didn't work on top of master for \nthe first iterations of the patch.\n\n\nSorry about that. My last re-roll was based on master (commit 77556354) \nbut I guess before I sent that version of the patch set I had already \ndone some damage by working off of next for the earlier patches.\n\n\nI think my last version of the patch was fine since it was based off \nmaster. Let me know if I've misunderstood.\n\n\n>> And worse yet, it seems that filter-options-should-use-plain-int\n>> topic depends on this topic in turn as it wants to use\n>> LOFC_TREEE_DEPTH.\n> This part is still true.  The scaling-factor-over-the-wire topic\n> does need to be rebuilt on top of this one.\n\nThis seems like a easier problem to understand, but I'm not sure how to \navoid this issue in the future.\n\n\nThanks,\nMatt\n\n"},{"id":"367010","messageId":"xmqqef9bnmyg.fsf@gitster-ct.c.googlers.com","threadId":"49999","inReplyTo":"04d6b46f-da87-bde2-1511-a9f2071bf034@comcast.net","subject":"Re: [PATCH v3 0/2] support for filtering trees and blobs based on depth","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-17T18:44:23Z","receivedAt":"2019-01-17T18:44:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matthew DeVore <matvore@comcast.net> writes:\n\n> This seems like a easier problem to understand, but I'm not sure how\n> to avoid this issue in the future.\n\nSorry---I was mostly venting and it was not productive.\n\nThere isn't much individual contributors can do by themselves, other\nthan choosing the right place to base their topics on and\ncommunicate it accurately when sending the patches to the list.\n\nI think I made sure that all the topics in master..pu that have\ntricky dependencies are at least buildable (which involved a few\ntopics to be rebased on the right commit, sometimes rebuilding the\nbase that is a merge of a few topics in flight), so hopefully we are\nin good shape now.\n\nThanks.\n"}]}