support for filtering trees and blobs based on depth
v2 cover support for filtering trees and blobs based on depth
This is a follow-up to the original patchset at
https://public-inbox.org/git/[email protected]/ - the purpose of that patchset and this one is to support positive integers for tree:<depth>. Some of the prior patchset's patches were either already queued (tree traversal optimization) or abandoned (documentation edit). This rendition of the patchset adds a commit which optimizes away tree traversal when collecting omits when iterating over a tree a second time.
Thanks,
Matthew DeVore (2):
list-objects-filter: teach tree:# how to handle >0 tree:<depth>: skip some trees even when collecting omits
Documentation/rev-list-options.txt | 9 ++- list-objects-filter-options.c | 7 +- list-objects-filter-options.h | 3 +- list-objects-filter.c | 120 +++++++++++++++++++++++----- t/t6112-rev-list-filters-objects.sh | 115 +++++++++++++++++++++++++- 5 files changed, 225 insertions(+), 29 deletions(-)
Signature · 1 line
2.20.0.rc2.403.gdbc3b29805-goog
PATCH v2 1/2 list-objects-filter: teach tree:# how to handle >0
Implement positive values for <depth> in the tree:<depth> filter. The exact semantics are described in Documentation/rev-list-options.txt.
The long-term goal at the end of this is to allow a partial clone to eagerly fetch an entire directory of files by fetching a tree and specifying <depth>=1. This, for instance, would make a build operation fast and convenient. It is fast because the partial clone does not need to fetch each file individually, and convenient because the user does not need to supply a sparse-checkout specification.
Another way of considering this feature is as a way to reduce round-trips, since the client can get any number of levels of directories in a single request, rather than wait for each level of tree objects to come back, whose entries are used to construct a new request.
--- Documentation/rev-list-options.txt | 9 ++- list-objects-filter-options.c | 7 +- list-objects-filter-options.h | 3 +- list-objects-filter.c | 115 +++++++++++++++++++++++----- t/t6112-rev-list-filters-objects.sh | 104 +++++++++++++++++++++++++ 5 files changed, 210 insertions(+), 28 deletions(-)
Documentation/rev-list-options.txt +7 -2
@@ -734,8 +734,13 @@ specification contained in <path>. + The form '--filter=tree:<depth>' omits all blobs and trees whose depth from the root tree is >= <depth> (minimum depth if an object is located -at multiple depths in the commits traversed). Currently, only <depth>=0 -is supported, which omits all blobs and trees. +at multiple depths in the commits traversed). <depth>=0 will not include +any trees or blobs unless included explicitly in the command-line (or +standard input when --stdin is used). <depth>=1 will include only the +tree and blobs which are referenced directly by a commit reachable from +<commit> or an explicitly-given object. <depth>=2 is like <depth>=1 +while also including trees and blobs one more level removed from an +explicitly-given commit or tree. --no-filter:: Turn off any previous `--filter=` argument.
list-objects-filter-options.c +3 -4
@@ -50,16 +50,15 @@ static int gently_parse_list_objects_filter( } }else if (skip_prefix (arg,"tree:" , &v0)) { -unsigned long depth; -if (!git_parse_ulong (v0, &depth) || depth !=0 ) { +if (!git_parse_ulong (v0, &filter_options->tree_exclude_depth)) {if (errbuf) {strbuf_addstr ( errbuf, -_ ("only 'tree:0' is supported" )); +_ ("expected 'tree:<depth>'" )); }return 1 ; } - filter_options->choice =LOFC_TREE_NONE ; + filter_options->choice =LOFC_TREE_DEPTH ;return 0 ; }else if (skip_prefix (arg,"sparse:oid=" , &v0)) {
list-objects-filter-options.h +2 -1
@@ -10,7 +10,7 @@ enum list_objects_filter_choice {LOFC_DISABLED =0 ,LOFC_BLOB_NONE ,LOFC_BLOB_LIMIT , -LOFC_TREE_NONE , +LOFC_TREE_DEPTH ,LOFC_SPARSE_OID ,LOFC_SPARSE_PATH ,LOFC__COUNT /* must be last */
@@ -44,6 +44,7 @@ struct list_objects_filter_options {struct object_id *sparse_oid_value;char *sparse_path_value;unsigned long blob_limit_value; +unsigned long tree_exclude_depth; };/* Normalized command line arguments */
list-objects-filter.c +94 -21
161 lines not on this page · raw message
t/t6112-rev-list-filters-objects.sh +104 -0
110 lines not on this page · raw message
Signature · 1 line
2.20.0.rc2.403.gdbc3b29805-goog
Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0
Thanks - as stated in your commit message, this adds quite a useful piece of functionality.
Quoted 11 lines
list-objects-filter.c +0
-11-case LOFS_BEGIN_TREE : -case LOFS_BLOB : -if (filter_data->omits) { -oidset_insert (filter_data->omits, &obj->oid); -/* _MARK_SEEN but not _DO_SHOW (hard omit) */ -return LOFR_MARK_SEEN ; - }else { -/* -* Not collecting omits so no need to to traverse tree. -*/ -return LOFR_SKIP_TREE |LOFR_MARK_SEEN ;
list-objects-filter.c static enum list_objects_filter_result filter_trees_none( · line 155
Quoted 10 lines
list-objects-filter.c +4
-2- } -case LOFS_END_TREE :assert (obj->type ==OBJ_TREE ); + filter_data->current_depth--;return LOFR_ZERO ; +case LOFS_BLOB : +filter_trees_update_omits (obj, filter_data, include_it); +return include_it ?LOFR_MARK_SEEN |LOFR_DO_SHOW :LOFR_ZERO ;
Any reason for moving "case LOFS_BLOB" (and "case LOFS_BEGIN_TREE" below) after LOFS_END_TREE?
This is drastically different from the previous case, but this makes sense - previously, all blobs accessed through traversal were not shown, but now they are sometimes shown. Here, filter_trees_update_omits() is only ever used to remove a blob from the omits set, since once this blob is encountered with include_it == true, it is marked as LOFR_MARK_SEEN and will not be traversed again.
list-objects-filter.c static enum list_objects_filter_result filter_trees_none( · line 161
Quoted 5 lines
list-objects-filter.c +5
-0+case LOFS_BEGIN_TREE : + seen_info =oidmap_get ( + &filter_data->seen_at_depth, &obj->oid); +if (!seen_info) { + seen_info =xcalloc (1 ,sizeof (struct seen_map_entry ));
Use sizeof(*seen_info).
list-objects-filter.c static enum list_objects_filter_result filter_trees_none( · line 162
Quoted 1 line
list-objects-filter.c +1
-0+ seen_info->base.oid = obj->oid;
We have been using oidcpy, but come to think of it, I'm not sure why...
list-objects-filter.c static enum list_objects_filter_result filter_trees_none( · line 168
Quoted 6 lines
list-objects-filter.c +6
-0+ seen_info->depth = filter_data->current_depth; +oidmap_put (&filter_data->seen_at_depth, seen_info); + already_seen =0 ; + }else + already_seen = + filter_data->current_depth >= seen_info->depth;
There has been recently some clarification that if one branch of an if/else construct requires braces, braces should be put on all of them:1797dc5176 ("CodingGuidelines: clarify multi-line brace style", 2017-01-17). Likewise below.
list-objects-filter.c static enum list_objects_filter_result filter_trees_none( · line 181
Quoted 12 lines
list-objects-filter.c +12
-0+if (already_seen) + filter_res =LOFR_SKIP_TREE ; +else { + seen_info->depth = filter_data->current_depth; +filter_trees_update_omits (obj, filter_data, include_it); + +if (include_it) + filter_res =LOFR_DO_SHOW ; +else if (filter_data->omits) + filter_res =LOFR_ZERO ; +else + filter_res =LOFR_SKIP_TREE ;
Looks straightforward. If we have already seen it at a shallower or equal depth, we can skip it (since we have already done the appropriate processing). Otherwise, we need to ensure that its "omit" is correctly set, and:
- show it if include_it
- don't do anything special if not include_it and we need the omit set
- skip the tree if not include_it and we don't need the omit set
list-objects-filter.c static enum list_objects_filter_result filter_trees_none( · line 193
Quoted 5 lines
list-objects-filter.c +5
-0+static void filter_trees_free (void *filter_data) { +struct filter_trees_depth_data * d = filter_data; +oidmap_free (&d->seen_at_depth,1 ); +free (d); +}
Check for NULL-ness of filter_data too, to match the usual behavior of free functions.
t/t6112-rev-list-filters-objects.sh
Quoted 4 lines
t/t6112-rev-list-filters-objects.sh +0
-0
[snip]
Thanks for the tests that cover quite a wide range of cases. Can you also demonstrate the case where a blob would normally be omitted (because it is too deep) but it is directly specified, so it is included.
t/t6112-rev-list-filters-objects.sh test_expect_success 'filter a GIANT tree through tree:0' ' · line 371
Quoted 9 lines
t/t6112-rev-list-filters-objects.sh +9
-0+expect_has_with_different_name () { + repo=$1 && + name=$2 && + + hash=$(git -C $repo rev-parse HEAD:$name) && + ! grep "^$hash $name$" actual && + grep "^$hash " actual && + ! grep "~$hash" actual +}
Should we also check that a "~" entry appears with $name?
Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0
Quoted 10 lines · Jonathan Tan
Review
Quoted 8 lines
case LOFS_END_TREE: assert(obj->type == OBJ_TREE);(quoted diff) +4
-0+ filter_data->current_depth--; return LOFR_ZERO; + case LOFS_BLOB: + filter_trees_update_omits(obj, filter_data, include_it); + return include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;Any reason for moving "case
LOFS_BLOB" (and "caseLOFS_BEGIN_TREE" below) afterLOFS_END_TREE?
I put LOFS_BLOB and after LOFS_END_TREE since that is the order in all the other filter logic functions. I put LOFS_BEGIN_TREE at the end (which is different from the other filter logic functions) because it's usually better to put simpler things before longer or more complex things. LOFS_BEGIN_TREE is much more complex and if it were not the last switch section, it would tend to hide the sections that come after it.
FWIW, I consider this the coding corollary of the end-weight problem in linguistics - see https://www.thoughtco.com/end-weight-grammar-1690594 - this is not my original idea, but something from the book Perl Best Practices, although that book only mentioned it in the context of ordering clauses in single statements rather than ordering entire blocks.
Quoted 4 lines
This is drastically different from the previous case, but this makes sense - previously, all blobs accessed through traversal were not shown, but now they are sometimes shown.
Yes.
Quoted 4 lines
Here,
filter_trees_update_omits()is
only ever used to remove a blob from the omits set, since once this blob is encountered withinclude_it== true, it is marked asLOFR_MARK_SEENand will not be traversed again.
It is possible that include_it can be false and then in a later invocation it can be true. In that case, the blob will be added to the set and then removed from it.
Quoted 7 lines
Review
Quoted 6 lines
(quoted diff) +5
-0+ case LOFS_BEGIN_TREE: + seen_info = oidmap_get( + &filter_data->seen_at_depth, &obj->oid); + if (!seen_info) { + seen_info = xcalloc(1, sizeof(struct seen_map_entry));Use
sizeof(*seen_info).
Done.
Quoted 3 lines
Review
Quoted 2 lines
(quoted diff) +1
-0+ seen_info->base.oid = obj->oid;We have been using oidcpy, but come to think of it, I'm not sure why...
Because the hash algorithm in use may not use the entire structure, apparently. Or there are future improvements planned to the function and they need to be picked up by all current hash-copying operations. Fixed.
Quoted 11 lines
Review
Quoted 7 lines
(quoted diff) +6
-0+ seen_info->depth = filter_data->current_depth; + oidmap_put(&filter_data->seen_at_depth, seen_info); + already_seen = 0; + } else + already_seen = + filter_data->current_depth >= seen_info->depth;There has been recently some clarification that if one branch of an if/else construct requires braces, braces should be put on all of them:
1797dc5176("CodingGuidelines: clarify multi-line brace style", 2017-01-17). Likewise below.
Done, thank you - that's good to know.
Quoted 12 lines
Quoted 12 lines
(quoted diff) +11
-0+ if (already_seen) + filter_res = LOFR_SKIP_TREE; + else { + seen_info->depth = filter_data->current_depth; + filter_trees_update_omits(obj, filter_data, include_it); + + if (include_it) + filter_res = LOFR_DO_SHOW; + else if (filter_data->omits) + filter_res = LOFR_ZERO; + else
Quoted 8 lines
Review
Quoted 1 line
(quoted diff) +1
-0+ filter_res = LOFR_SKIP_TREE;Looks straightforward. If we have already seen it at a shallower or equal depth, we can skip it (since we have already done the appropriate processing). Otherwise, we need to ensure that its "omit" is correctly set, and:
- show it ifinclude_it
- don't do anything special if notinclude_itand we need the omit set
- skip the tree if notinclude_itand we don't need the omit set
Right.
Quoted 9 lines
Review
Quoted 6 lines
(quoted diff) +5
-0+static void filter_trees_free(void *filter_data) { + struct filter_trees_depth_data* d = filter_data; + oidmap_free(&d->seen_at_depth, 1); + free(d); +}Check for NULL-ness of
filter_datatoo, to match the usual behavior of free functions.
Done.
Quoted 10 lines
t/t6112-rev-list-filters-objects.sh
Quoted 4 lines
t/t6112-rev-list-filters-objects.sh +0
-0[snip]
Thanks for the tests that cover quite a wide range of cases. Can you also demonstrate the case where a blob would normally be omitted (because it is too deep) but it is directly specified, so it is included.
I didn't exactly use TDD, but I did try to cover every line of code as well as both branches of each ternary operator.
Added such a test.
Quoted 11 lines
t/t6112-rev-list-filters-objects.sh
Quoted 10 lines
t/t6112-rev-list-filters-objects.sh +9
-0+expect_has_with_different_name () { + repo=$1 && + name=$2 && + + hash=$(git -C $repo rev-parse HEAD:$name) && + ! grep "^$hash $name$" actual && + grep "^$hash " actual && + ! grep "~$hash" actual +}Should we also check that a "~" entry appears with $name?
I don't believe there is a way to get the object names to appear next to ~ entries (note that the names are not saved in the omits oidset).
For your reference, here is an interdiff for this particular patch after applying your comments:
list-objects-filter.c +0 -0
@@ -158,18 +158,19 @@ static enum list_objects_filter_result filter_trees_depth(
seen_info = oidmap_get( &filter_data->seen_at_depth, &obj->oid);
if (!seen_info) {
- seen_info = xcalloc(1, sizeof(struct seen_map_entry)); - seen_info->base.oid = obj->oid;
+ seen_info = xcalloc(1, sizeof(*seen_info)); + oidcpy(&seen_info->base.oid, &obj->oid); seen_info->depth = filter_data->current_depth; oidmap_put(&filter_data->seen_at_depth, seen_info); already_seen = 0;
- } else
+ } else {
already_seen =
filter_data->current_depth >= seen_info->depth; + }
- if (already_seen)
+ if (already_seen) {
filter_res = LOFR_SKIP_TREE;
- else {
+ } else {
int been_omitted = filter_trees_update_omits(
obj, filter_data, include_it);
seen_info->depth = filter_data->current_depth;
@@ -193,6 +194,8 @@ static enum list_objects_filter_result filter_trees_depth(
static void filter_trees_free(void *filter_data) { struct filter_trees_depth_data* d = filter_data; + if (!d)
+ return; oidmap_free(&d->seen_at_depth, 1); free(d);
}
t/'t6112-rev-list-filters-objects.sh new file +0 -0
t/t6112-rev-list-filters-objects.sh +0 -0
@@ -407,6 +407,13 @@ test_expect_success 'tree:<depth> where we iterate over tree at two levels' '
expect_has_with_different_name r5 a/subdir/b/foo '
+test_expect_success 'tree:<depth> which filters out blob but given as arg' ' + export blob_hash=$(git -C r4 rev-parse HEAD:subdir/bar) &&
+
+ git -C r4 rev-list --objects --filter=tree:1 HEAD $blob_hash >actual && + grep ^$blob_hash actual
+'
+
# Delete some loose objects and use rev-list, but WITHOUT any filtering. # This models previously omitted objects that we did not receive.
Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0
Quoted 10 lines
Quoted 2 lines
Any reason for moving "case
LOFS_BLOB" (and "caseLOFS_BEGIN_TREE" below) afterLOFS_END_TREE?I put
LOFS_BLOBand afterLOFS_END_TREEsince that is the order in all the other filter logic functions. I putLOFS_BEGIN_TREEat the end (which is different from the other filter logic functions) because it's usually better to put simpler things before longer or more complex things.LOFS_BEGIN_TREEis much more complex and if it were not the last switch section, it would tend to hide the sections that come after it.
Quoted 5 lines
FWIW, I consider this the coding corollary of the end-weight problem in linguistics - see https://www.thoughtco.com/end-weight-grammar-1690594 - this is not my original idea, but something from the book Perl Best Practices, although that book only mentioned it in the context of ordering clauses in single statements rather than ordering entire blocks.
OK - my thinking was that we should minimize the diff, but this reasoning makes sense to me.
Quoted 7 lines
Quoted 4 lines
Here,
filter_trees_update_omits()is
only ever used to remove a blob from the omits set, since once this blob is encountered withinclude_it== true, it is marked asLOFR_MARK_SEENand will not be traversed again.It is possible that
include_itcan be false and then in a later invocation it can be true. In that case, the blob will be added to the set and then removed from it.
Ah...yes, you're right.
Quoted 2 lines
For your reference, here is an interdiff for this particular patch after applying your comments:
The interdiff looks good, thanks. All my issues are resolved.
Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0
Quoted 4 lines · Jonathan Tan
Quoted 2 lines
For your reference, here is an interdiff for this particular patch after applying your comments:
The interdiff looks good, thanks. All my issues are resolved.
Just to make sure. That's not "v2 is good", but "v2 plus that proposed update, when materializes, would be good", right? I'll mark the topic as "expecting a reroll" then.
Thanks.
Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0
Quoted 10 lines
Quoted 4 lines · Jonathan Tan
Quoted 2 lines
For your reference, here is an interdiff for this particular patch after applying your comments:
The interdiff looks good, thanks. All my issues are resolved.
Just to make sure. That's not "v2 is good", but "v2 plus that proposed update, when materializes, would be good", right? I'll mark the topic as "expecting a reroll" then.
Yes, that's right - there should be a reroll of this topic. Also, besides the proposed update, I have a comment in patch 2 of this set.
Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0
In reply to Jonathan TanQuoted 8 lines · Jonathan Tan
list-objects-filter.c static enum list_objects_filter_result filter_trees_none( · line 193
Quoted 5 lines
list-objects-filter.c +5
-0+static void filter_trees_free (void *filter_data) { +struct filter_trees_depth_data * d = filter_data; +oidmap_free (&d->seen_at_depth,1 ); +free (d); +}Check for NULL-ness of
filter_datatoo, to match the usual behavior of free functions.
Also, the asterisk sticks to the variable, not type, i.e.
struct filter_trees_depth_data *d = filter_data;
Re: [PATCH v2 1/2] list-objects-filter: teach tree:# how to handle >0
Quoted 7 lines · Junio C Hamano
Also, the asterisk sticks to the variable, not type, i.e.
struct filter_trees_depth_data *d = filter_data;
Fixed. Thanks.
PATCH v2 2/2 tree:<depth>: skip some trees even when collecting omits
In reply to Matthew DeVoreIf a tree has already been recorded as omitted, we don't need to traverse it again just to collect its omits. Stop traversing trees a second time when collecting omits.
--- list-objects-filter.c | 17 +++++++++++------ t/t6112-rev-list-filters-objects.sh | 11 ++++++++++- 2 files changed, 21 insertions(+), 7 deletions(-)
list-objects-filter.c +11 -6
@@ -107,18 +107,18 @@ struct seen_map_entry {size_t depth; }; -static void filter_trees_update_omits ( +static int filter_trees_update_omits (struct object *obj,struct filter_trees_depth_data *filter_data,int include_it) {if (!filter_data->omits) -return ; +return 1 ;if (include_it) -oidset_remove (filter_data->omits, &obj->oid); +return oidset_remove (filter_data->omits, &obj->oid);else -oidset_insert (filter_data->omits, &obj->oid); +return oidset_insert (filter_data->omits, &obj->oid); } static enum list_objects_filter_result filter_trees_depth(
@@ -170,12 +170,17 @@ static enum list_objects_filter_result filter_trees_depth(if (already_seen) filter_res =LOFR_SKIP_TREE ;else { +int been_omitted =filter_trees_update_omits ( + obj, filter_data, include_it); seen_info->depth = filter_data->current_depth; -filter_trees_update_omits (obj, filter_data, include_it);if (include_it) filter_res =LOFR_DO_SHOW ; -else if (filter_data->omits) +else if (!been_omitted) +/* +* Must update omit information of children +* recursively; they have not been omitted yet. +*/ filter_res =LOFR_ZERO ;else filter_res =LOFR_SKIP_TREE ;
t/t6112-rev-list-filters-objects.sh +10 -1
@@ -283,7 +283,7 @@ test_expect_success 'verify tree:0 includes trees in "filtered" output' ' # Make sure tree:0 does not iterate through any trees. -test_expect_success 'filter a GIANT tree through tree:0' ' +test_expect_success 'verify skipping tree iteration when not collecting omits' ' GIT_TRACE=1 git -C r3 rev-list \ --objects --filter=tree:0 HEAD 2>filter_trace && grep "Skipping contents of tree [.][.][.]" filter_trace >actual &&
@@ -377,6 +377,15 @@ test_expect_success 'test tree:# filter provisional omit for blob and tree' ' expect_has_with_different_name r4 filt/subdir ' +test_expect_success 'verify skipping tree iteration when collecting omits' ' + GIT_TRACE=1 git -C r4 rev-list --filter-print-omitted \ + --objects --filter=tree:0 HEAD 2>filter_trace && + grep "^Skipping contents of tree " filter_trace >actual && + + echo "Skipping contents of tree subdir/..." >expect && + test_cmp expect actual +' + # Test tree:<depth> where a tree is iterated to twice - once where a subentry is # too deep to be included, and again where the blob inside it is shallow enough # to be included. This makes sure we don't use LOFR_MARK_SEEN incorrectly (we
Signature · 1 line
2.20.0.rc2.403.gdbc3b29805-goog
Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits
Quoted 7 lines
list-objects-filter.c +1
-1-static void filter_trees_update_omits ( +static int filter_trees_update_omits (struct object *obj,struct filter_trees_depth_data *filter_data,int include_it) {if (!filter_data->omits)
list-objects-filter.c struct seen_map_entry { · line 122
Quoted 10 lines
list-objects-filter.c +3
-3-return ; +return 1 ;if (include_it) -oidset_remove (filter_data->omits, &obj->oid); +return oidset_remove (filter_data->omits, &obj->oid);else -oidset_insert (filter_data->omits, &obj->oid); +return oidset_insert (filter_data->omits, &obj->oid); }
I think this function is getting too magical - if filter_data->omits is not set, we pretend that we have omitted the tree, because we want the same behavior when not needing omits and when the tree is omitted. Could this be done another way?
Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits
Quoted 10 lines
Quoted 10 lines
list-objects-filter.c +2
-2-static void filter_trees_update_omits ( +static int filter_trees_update_omits (struct object *obj,struct filter_trees_depth_data *filter_data,int include_it) {if (!filter_data->omits) -return ; +return 1 ;
Quoted 12 lines
list-objects-filter.c struct seen_map_entry { · line 122
Quoted 7 lines
list-objects-filter.c +2
-2if (include_it) -oidset_remove (filter_data->omits, &obj->oid); +return oidset_remove (filter_data->omits, &obj->oid);else -oidset_insert (filter_data->omits, &obj->oid); +return oidset_insert (filter_data->omits, &obj->oid); }I think this function is getting too magical - if
filter_data->omitsis not set, we pretend that we have omitted the tree, because we want the same behavior when not needing omits and when the tree is omitted. Could this be done another way?
Giving some more thought to this, since this is a static function, maybe documenting it as "Returns 1 if the objects that this object references need to be traversed for "omits" updates, and 0 otherwise" (with the appropriate code updates) would suffice.
Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits
Quoted 27 lines · Jonathan Tan
Quoted 12 lines
Quoted 12 lines
list-objects-filter.c +2
-2-static void filter_trees_update_omits ( +static int filter_trees_update_omits (struct object *obj,struct filter_trees_depth_data *filter_data,int include_it) {if (!filter_data->omits) -return ; +return 1 ;Quoted 12 lines
list-objects-filter.c struct seen_map_entry { · line 122
Quoted 7 lines
list-objects-filter.c +2
-2if (include_it) -oidset_remove (filter_data->omits, &obj->oid); +return oidset_remove (filter_data->omits, &obj->oid);else -oidset_insert (filter_data->omits, &obj->oid); +return oidset_insert (filter_data->omits, &obj->oid); }I think this function is getting too magical - if
filter_data->omitsis not set, we pretend that we have omitted the tree, because we want the same behavior when not needing omits and when the tree is omitted. Could this be done another way?
Quoted 4 lines
Giving some more thought to this, since this is a static function, maybe documenting it as "Returns 1 if the objects that this object references need to be traversed for "omits" updates, and 0 otherwise" (with the appropriate code updates) would suffice.
That'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.
Re: [PATCH v2 2/2] tree:<depth>: skip some trees even when collecting omits
In reply to Jonathan TanThank you for the review :) See below.
Quoted 10 lines · Jonathan Tan
Quoted 10 lines
list-objects-filter.c +2
-2-static void filter_trees_update_omits ( +static int filter_trees_update_omits (struct object *obj,struct filter_trees_depth_data *filter_data,int include_it) {if (!filter_data->omits) -return ; +return 1 ;
Quoted 11 lines
list-objects-filter.c struct seen_map_entry { · line 122
Quoted 7 lines
if (
include_it)list-objects-filter.c +2
-2-oidset_remove (filter_data->omits, &obj->oid); +return oidset_remove (filter_data->omits, &obj->oid); else - oidset_insert(filter_data->omits, &obj->oid); + return oidset_insert(filter_data->omits, &obj->oid); }I think this function is getting too magical - if
filter_data->omitsis not set, we pretend that we have omitted the tree, because we want the same behavior when not needing omits and when the tree is omitted. Could this be done another way?
Yes, returning a manipulative lie when omits is NULL is rather confusing. So I changed it to this (interdiff):
+/* Returns 1 if the oid was in the omits set before it was invoked. */ static int filter_trees_update_omits(
struct object *obj,
struct filter_trees_depth_data *filter_data,
int include_it)
{
if (!filter_data->omits)
- return 1;
+ return 0;
if (include_it)
return oidset_remove(filter_data->omits, &obj->oid);
@@ -177,7 +178,7 @@ static enum list_objects_filter_result filter_trees_depth(
if (include_it)
filter_res = LOFR_DO_SHOW;
- else if (!been_omitted)
+ else if (filter_data->omits && !been_omitted) /*
* Must update omit information of children
* recursively; they have not been omitted yet.
Quoted 8 lines · Matthew DeVore
This is a follow-up to the original patchset at
https://public-inbox.org/git/[email protected]/ - the purpose of that patchset and this one is to support positive integers for tree:<depth>. Some of the prior patchset's patches were either already queued (tree traversal optimization) or abandoned (documentation edit). This rendition of the patchset adds a commit which optimizes away tree traversal when collecting omits when iterating over a tree a second time.
Quoted 5 lines
Thanks,
Matthew DeVore (2):
list-objects-filter: teach tree:# how to handle >0 tree:<depth>: skip some trees even when collecting omits
This seems to require at least two topics still not in 'master'; I've bookmarked the topic by merging sb/more-repo-in-api and nd/the-index into 'master' and then queueing these two patches on top, to be able to merge it into 'pu' to see if there are bad interactions with other topics and also give others easier access to the topic in the integrated form.
Thanks.
Quoted 8 lines · Junio C Hamano
This seems to require at least two topics still not in 'master'; I've bookmarked the topic by merging sb/more-repo-in-api and nd/the-index into 'master' and then queueing these two patches on top, to be able to merge it into 'pu' to see if there are bad interactions with other topics and also give others easier access to the topic in the integrated form.
Thanks.
I'm re-reading the SubmittingPatches document and now I realize that I should have based this on master. Thank you for merging things so that my patch works. Let me know if it would be easier if I rebased this patch on top of master either now or on the next re-roll.
v3 cover support for filtering trees and blobs based on depth
In reply to Matthew DeVoreThis applies suggestions from Jonathan Tan and Junio. These are mostly stylistic and readability changes, although there is also an added test case in t/t6112-rev-list-filters-objects.sh which checks for the scenario when filtering which would exclude a blob, but the blob is given on the command line.
This has been rebased onto master, while the prior version was based on next.
Thank you,
Matthew DeVore (2):
list-objects-filter: teach tree:# how to handle >0 tree:<depth>: skip some trees even when collecting omits
Documentation/rev-list-options.txt | 9 +- list-objects-filter-options.c | 7 +- list-objects-filter-options.h | 3 +- list-objects-filter.c | 122 +++++++++++++++++++++++----- t/t6112-rev-list-filters-objects.sh | 122 +++++++++++++++++++++++++++- 5 files changed, 235 insertions(+), 28 deletions(-)
Signature · 1 line
2.20.1.97.g81188d93c3-goog
PATCH v3 1/2 list-objects-filter: teach tree:# how to handle >0
Implement positive values for <depth> in the tree:<depth> filter. The exact semantics are described in Documentation/rev-list-options.txt.
The long-term goal at the end of this is to allow a partial clone to eagerly fetch an entire directory of files by fetching a tree and specifying <depth>=1. This, for instance, would make a build operation fast and convenient. It is fast because the partial clone does not need to fetch each file individually, and convenient because the user does not need to supply a sparse-checkout specification.
Another way of considering this feature is as a way to reduce round-trips, since the client can get any number of levels of directories in a single request, rather than wait for each level of tree objects to come back, whose entries are used to construct a new request.
--- Documentation/rev-list-options.txt | 9 ++- list-objects-filter-options.c | 7 +- list-objects-filter-options.h | 3 +- list-objects-filter.c | 116 +++++++++++++++++++++++----- t/t6112-rev-list-filters-objects.sh | 111 ++++++++++++++++++++++++++ 5 files changed, 219 insertions(+), 27 deletions(-)
Documentation/rev-list-options.txt +7 -2
@@ -734,8 +734,13 @@ specification contained in <path>. + The form '--filter=tree:<depth>' omits all blobs and trees whose depth from the root tree is >= <depth> (minimum depth if an object is located -at multiple depths in the commits traversed). Currently, only <depth>=0 -is supported, which omits all blobs and trees. +at multiple depths in the commits traversed). <depth>=0 will not include +any trees or blobs unless included explicitly in the command-line (or +standard input when --stdin is used). <depth>=1 will include only the +tree and blobs which are referenced directly by a commit reachable from +<commit> or an explicitly-given object. <depth>=2 is like <depth>=1 +while also including trees and blobs one more level removed from an +explicitly-given commit or tree. --no-filter:: Turn off any previous `--filter=` argument.
list-objects-filter-options.c +3 -4
@@ -50,16 +50,15 @@ static int gently_parse_list_objects_filter( } }else if (skip_prefix (arg,"tree:" , &v0)) { -unsigned long depth; -if (!git_parse_ulong (v0, &depth) || depth !=0 ) { +if (!git_parse_ulong (v0, &filter_options->tree_exclude_depth)) {if (errbuf) {strbuf_addstr ( errbuf, -_ ("only 'tree:0' is supported" )); +_ ("expected 'tree:<depth>'" )); }return 1 ; } - filter_options->choice =LOFC_TREE_NONE ; + filter_options->choice =LOFC_TREE_DEPTH ;return 0 ; }else if (skip_prefix (arg,"sparse:oid=" , &v0)) {
list-objects-filter-options.h +2 -1
@@ -10,7 +10,7 @@ enum list_objects_filter_choice {LOFC_DISABLED =0 ,LOFC_BLOB_NONE ,LOFC_BLOB_LIMIT , -LOFC_TREE_NONE , +LOFC_TREE_DEPTH ,LOFC_SPARSE_OID ,LOFC_SPARSE_PATH ,LOFC__COUNT /* must be last */
@@ -44,6 +44,7 @@ struct list_objects_filter_options {struct object_id *sparse_oid_value;char *sparse_path_value;unsigned long blob_limit_value; +unsigned long tree_exclude_depth; };/* Normalized command line arguments */
list-objects-filter.c +96 -20
163 lines not on this page · raw message
t/t6112-rev-list-filters-objects.sh +111 -0
117 lines not on this page · raw message
Signature · 1 line
2.20.1.97.g81188d93c3-goog
PATCH v3 2/2 tree:<depth>: skip some trees even when collecting omits
In reply to Matthew DeVoreIf a tree has already been recorded as omitted, we don't need to traverse it again just to collect its omits. Stop traversing trees a second time when collecting omits.
--- list-objects-filter.c | 18 ++++++++++++------ t/t6112-rev-list-filters-objects.sh | 11 ++++++++++- 2 files changed, 22 insertions(+), 7 deletions(-)
list-objects-filter.c +12 -6
@@ -107,18 +107,19 @@ struct seen_map_entry {size_t depth; }; -static void filter_trees_update_omits ( +/* Returns 1 if the oid was in the omits set before it was invoked. */ +static int filter_trees_update_omits (struct object *obj,struct filter_trees_depth_data *filter_data,int include_it) {if (!filter_data->omits) -return ; +return 0 ;if (include_it) -oidset_remove (filter_data->omits, &obj->oid); +return oidset_remove (filter_data->omits, &obj->oid);else -oidset_insert (filter_data->omits, &obj->oid); +return oidset_insert (filter_data->omits, &obj->oid); } static enum list_objects_filter_result filter_trees_depth(
@@ -171,12 +172,17 @@ static enum list_objects_filter_result filter_trees_depth(if (already_seen) { filter_res =LOFR_SKIP_TREE ; }else { +int been_omitted =filter_trees_update_omits ( + obj, filter_data, include_it); seen_info->depth = filter_data->current_depth; -filter_trees_update_omits (obj, filter_data, include_it);if (include_it) filter_res =LOFR_DO_SHOW ; -else if (filter_data->omits) +else if (filter_data->omits && !been_omitted) +/* +* Must update omit information of children +* recursively; they have not been omitted yet. +*/ filter_res =LOFR_ZERO ;else filter_res =LOFR_SKIP_TREE ;
t/t6112-rev-list-filters-objects.sh +10 -1
@@ -283,7 +283,7 @@ test_expect_success 'verify tree:0 includes trees in "filtered" output' ' # Make sure tree:0 does not iterate through any trees. -test_expect_success 'filter a GIANT tree through tree:0' ' +test_expect_success 'verify skipping tree iteration when not collecting omits' ' GIT_TRACE=1 git -C r3 rev-list \ --objects --filter=tree:0 HEAD 2>filter_trace && grep "Skipping contents of tree [.][.][.]" filter_trace >actual &&
@@ -377,6 +377,15 @@ test_expect_success 'test tree:# filter provisional omit for blob and tree' ' expect_has_with_different_name r4 filt/subdir ' +test_expect_success 'verify skipping tree iteration when collecting omits' ' + GIT_TRACE=1 git -C r4 rev-list --filter-print-omitted \ + --objects --filter=tree:0 HEAD 2>filter_trace && + grep "^Skipping contents of tree " filter_trace >actual && + + echo "Skipping contents of tree subdir/..." >expect && + test_cmp expect actual +' + # Test tree:<depth> where a tree is iterated to twice - once where a subentry is # too deep to be included, and again where the blob inside it is shallow enough # to be included. This makes sure we don't use LOFR_MARK_SEEN incorrectly (we
Signature · 1 line
2.20.1.97.g81188d93c3-goog
Quoted 9 lines
This applies suggestions from Jonathan Tan and Junio. These are mostly stylistic and readability changes, although there is also an added test case in
t/t6112-rev-list-filters-objects.shwhich checks for the scenario when filtering which would exclude a blob, but the blob is given on the command line.This has been rebased onto master, while the prior version was based on next.
Thank you,
Thanks, these 2 patches are Reviewed-by: me.
Your approach in the 2nd patch makes more sense, and I checked that both oidset_insert() and oidset_remove() return 1 when the element in question was in the set (prior to invocation of the function), so that works.
Quoted 8 lines · Jonathan Tan
Quoted 8 lines
This applies suggestions from Jonathan Tan and Junio. These are mostly stylistic and readability changes, although there is also an added test case in
t/t6112-rev-list-filters-objects.shwhich checks for the scenario when filtering which would exclude a blob, but the blob is given on the command line.This has been rebased onto master, while the prior version was based on next.
Quoted 8 lines
Quoted 1 line
Thank you,
Thanks, these 2 patches are Reviewed-by: me.
Your approach in the 2nd patch makes more sense, and I checked that both
oidset_insert()andoidset_remove()return 1 when the element in question was in the set (prior to invocation of the function), so that works.
This is turning out to be messier than I like.
The topic is tangled with too many things in flight and I think I reduced its dependencies down to nd/the-index and sb/more-repo-in-api plus then-current tip of master (and that is why it is based on a1411cecc7), but it seems that it wants a bit more than that; builtin/rebase.c at its tip does not even compile, so I'll need to wiggle the topic before it can go to 'next'.
And worse yet, it seems that filter-options-should-use-plain-int topic depends on this topic in turn as it wants to use LOFC_TREEE_DEPTH.
Quoted 8 lines · Junio C Hamano
This is turning out to be messier than I like.
The topic is tangled with too many things in flight and I think I reduced its dependencies down to nd/the-index and sb/more-repo-in-api plus then-current tip of master (and that is why it is based on
a1411cecc7), but it seems that it wants a bit more than that;builtin/rebase.cat its tip does not even compile, so I'll need to wiggle the topic before it can go to 'next'.
Half false alarm. I do need to wiggle the topic, but that was not because the choice of base was bad. It was that nd/the-index plus sb/more-repo-in-api had semantic merge conflicts with the then-current master.
Quoted 3 lines
And worse yet, it seems that filter-options-should-use-plain-int topic depends on this topic in turn as it wants to use
LOFC_TREEE_DEPTH.
This part is still true. The scaling-factor-over-the-wire topic does need to be rebuilt on top of this one.
Quoted 10 lines · Junio C Hamano
Quoted 8 lines · Junio C Hamano
This is turning out to be messier than I like.
The topic is tangled with too many things in flight and I think I reduced its dependencies down to nd/the-index and sb/more-repo-in-api plus then-current tip of master (and that is why it is based on
a1411cecc7), but it seems that it wants a bit more than that;builtin/rebase.cat its tip does not even compile, so I'll need to wiggle the topic before it can go to 'next'.
Quoted 4 lines
Half false alarm. I do need to wiggle the topic, but that was not because the choice of base was bad. It was that nd/the-index plus sb/more-repo-in-api had semantic merge conflicts with the then-current master.
If I understand right, this is a product of the fact that you had to merge these branches together and base my change on top of them, and that is a result of that fact that I didn't work on top of master for the first iterations of the patch.
Sorry about that. My last re-roll was based on master (commit 77556354) but I guess before I sent that version of the patch set I had already done some damage by working off of next for the earlier patches.
I think my last version of the patch was fine since it was based off master. Let me know if I've misunderstood.
Quoted 5 lines
Quoted 3 lines
And worse yet, it seems that filter-options-should-use-plain-int topic depends on this topic in turn as it wants to use
LOFC_TREEE_DEPTH.This part is still true. The scaling-factor-over-the-wire topic does need to be rebuilt on top of this one.
This seems like a easier problem to understand, but I'm not sure how to avoid this issue in the future.
Thanks,
Matt
Quoted 2 lines · Matthew DeVore
This seems like a easier problem to understand, but I'm not sure how to avoid this issue in the future.
Sorry---I was mostly venting and it was not productive.
There isn't much individual contributors can do by themselves, other than choosing the right place to base their topics on and communicate it accurately when sending the patches to the list.
I think I made sure that all the topics in master..pu that have tricky dependencies are at least buildable (which involved a few topics to be rebased on the right commit, sometimes rebuilding the base that is a merge of a few topics in flight), so hopefully we are in good shape now.
Thanks.