support for filtering trees and blobs based on depth

The tree:0 filter does not need to traverse the trees that it has filtered out, so optimize list-objects and list-objects-filter to skip traversing the trees entirely. Before this patch, we iterated over all children of the tree, and did nothing for all of them, which was wasteful.

Signed-off-by Matthew DeVore <[email protected]>

---
 list-objects-filter.c               | 11 +++++++++--
 list-objects-filter.h               |  6 ++++++
 list-objects.c                      |  5 ++++-
 t/t6112-rev-list-filters-objects.sh | 10 ++++++++++
 4 files changed, 29 insertions(+), 3 deletions(-)

list-objects-filter.c +1 -1

index 09b2b05d5..37fba456d 100644
@@ -102,9 +102,16 @@ static enum list_objects_filter_result filter_trees_none(
 
 	case LOFS_BEGIN_TREE:
 	case LOFS_BLOB:
-		if (filter_data->omits)
+		if (filter_data->omits) {

list-objects-filter.h +6 -0

index a6f6b4990..52b4a84da 100644
@@ -24,6 +24,11 @@ struct oidset;
  *              In general, objects should only be shown once, but
  *              this result DOES NOT imply that we mark it SEEN.
  *
+ * _SKIP_TREE : Used in LOFS_BEGIN_TREE situation - indicates that
+ *              the tree's children should not be iterated over. This
+ *              is used as an optimization when all children will
+ *              definitely be ignored.
+ *
  * Most of the time, you want the combination (_MARK_SEEN | _DO_SHOW)
  * but they can be used independently, such as when sparse-checkout
  * pattern matching is being applied.

@@ -45,6 +50,7 @@ enum list_objects_filter_result {
 	LOFR_ZERO      = 0,
 	LOFR_MARK_SEEN = 1<<0,
 	LOFR_DO_SHOW   = 1<<1,
+	LOFR_SKIP_TREE = 1<<2,
 };
 
 enum list_objects_filter_situation {

list-objects.c +1 -0

index 7a1a0929d..d1e3d217c 100644
@@ -11,6 +11,7 @@
 #include "list-objects-filter-options.h"
 #include "packfile.h"
 #include "object-store.h"
+#include "trace.h"
 
 struct traversal_context {
 	struct rev_info *revs;

t/t6112-rev-list-filters-objects.sh +0 -0

index 08e0c7db6..efb1bee2e 100755

This step looks more like "ow, we could have done the tree:0 support that is in 'next' better" than a part of "here is a series to do tree:N for non zero value of N".

If that is the case, I'd prefer to see this step polished enough before [2-3/3] of this RFC is worked on, so that we can merge the tree:0 (but not yet tree:N) support that is solid down to 'master' soonish.

OK, so "not collecting omits" is synonymous to "N==0, we aren't doing tree at any level", and at this point in the series before the support for N>0 is introduced, we'd always take this "else" clause because tree:0 is the only thing we support?

Style: our modern style is to use {} around the body which is a single statement on the else clause when the body of the corresponding if clause needs {} around (and vice versa), so

Even when failed_parse==true, i.e. we found that the tree object's data cannot be understood, if we have skip-tree bit set, that means we do not care---we won't be descending into its children anyway.

t/t6112-rev-list-filters-objects.sh test_expect_success 'verify tree:0 includes trees in "filtered" output' ' · line 252

Quoted 6 lines

t/t6112-rev-list-filters-objects.sh +6 -0

+# Make sure tree:0 does not iterate through any trees.
+
+test_expect_success 'filter a GIANT tree through tree:0' '
+     GIT_TRACE=1 git -C r3 rev-list \
+             --objects --filter=tree:0 HEAD 2>filter_trace &&
+     grep "Skipping contents of tree [.][.][.]" filter_trace >actual &&

Here you are not jus tmaking sure SKIP_TREE bit is set for some tree, but it is set when base->buf is an empty string (i.e. the top level tree)? Which makes sense, and the next text makes sure that between the two commits, the number of total "top level" trees is 2, but I wonder if it is more direct to also make sure that the code is not even seeing or skipping any tree inside these top level trees (i.e. the same message but for ""!=base->buf should never appear in the trace).

Documentation/git-rev-list.txt +3 -4

-List commits that are reachable by following the `parent` links from the
-given commit(s), but exclude commits that are reachable from the one(s)
-given with a '{caret}' in front of them.  The output is given in reverse
-chronological order by default.
+List objects that are reachable by following references from the given
+object(s), but exclude objects that are reachable from the one(s) given
+with a '{caret}' in front of them.
 

Quoted 8 lines · Matthew DeVore

Documentation/git-rev-list.txt +3 -4

-List commits that are reachable by following the `parent` links from the
-given commit(s), but exclude commits that are reachable from the one(s)
-given with a '{caret}' in front of them.  The output is given in reverse
-chronological order by default.
+List objects that are reachable by following references from the given
+object(s), but exclude objects that are reachable from the one(s) given
+with a '{caret}' in front of them.
 

Documentation/git-rev-list.txt SYNOPSIS

Quoted 10 lines

Documentation/git-rev-list.txt +7 -0

+By default, only commit objects are shown, and the commits are shown in
+reverse chronological order. The '--object' flag causes non-commit objects
+to also be shown.
 
+You can think of this as a set operation.  Objects given on the command
+line form a set of objects that are reachable from any of them, and then
+objects reachable from any of the ones given with '{caret}' in front are
+subtracted from that set.  The remaining objects are what come out in the
 command's output.  Various other options and paths parameters can be used
 to further limit the result.

I am not sure if this is a good rewrite. It gives a false impression as if you'd not see anything if I did this:

        git rev-list --objects ^master md/filter-trees:t/valgrind

It is more like "this is a set operation across commits. We also show objects that are reachable from the commits in the resulting set and are not reachable from the commits in the set that were excluded when --objects option is given".

Quoted 5 lines

It is more like "this is a set operation across commits. We also show objects that are reachable from the commits in the resulting set and are not reachable from the commits in the set that were excluded when --objects option is given".

That would be correct though it wouldn't tell that you can use "--objects ^foo-tree bar-tree."

Quoted 7 lines · Matthew DeVore

Quoted 5 lines

It is more like "this is a set operation across commits. We also show objects that are reachable from the commits in the resulting set and are not reachable from the commits in the set that were excluded when --objects option is given".

That would be correct though it wouldn't tell that you can use "--objects ^foo-tree bar-tree."

Yeah, but quite honestly, I consider that it is working by accident, not by design, in the current code (iow, you are looking at a behaviour of whatever the code happens to do). "rev-list" is pretty much set operation across commits, and anything that deals with a non commit-ish given from the command line is an afterthought at best, and happenstance in reality.

I do not mean to say that the code must stay that way, though.

$ git -C pc1 fetch-pack --stdin "file://$(pwd)/srv.bare" <observed.oids

Where observed.oids contains all the blobs that were missing. It tells the remote that it already has the "refs/heads/master" commit, which means it is excluded. Before, this worked fine, since it didn't mean the blobs were excluded, only the commit itself.

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

list-objects-filter-options.c +0 -0

index e8da2e858..9dc61d6e6 100644
@@ -50,12 +50,12 @@ static int gently_parse_list_objects_filter(
 		}
 

list-objects-filter-options.h +19 -3

+
+		if (filter_data->omits)
+			oidset_insert(filter_data->omits, &obj->oid);
+
+		return LOFR_ZERO;
+
+	case LOFS_BEGIN_TREE:
+		filter_data->current_depth++;
+
+		if (!too_deep) goto include_it;
+
 		if (filter_data->omits) {
 			oidset_insert(filter_data->omits, &obj->oid);
-			/* _MARK_SEEN but not _DO_SHOW (hard omit) */
-			return LOFR_MARK_SEEN;
+			return LOFR_ZERO;
 		}
 		else
 			/*
 			 * Not collecting omits so no need to to traverse tree.
 			 */
-			return LOFR_SKIP_TREE | LOFR_MARK_SEEN;
+			return LOFR_SKIP_TREE;
 
 	case LOFS_END_TREE:
 		assert(obj->type == OBJ_TREE);
+		filter_data->current_depth--;
 		return LOFR_ZERO;
 
 	}
+
+include_it:
+	if (filter_data->omits)
+		oidset_remove(filter_data->omits, &obj->oid);
+	return LOFR_MARK_SEEN | LOFR_DO_SHOW;
 }

Quoted 4 lines · Matthew DeVore

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

This would reduce round-trip, as you do not have to fetch the tree to see what its contents are before issuing another set of fetches for them. Those who are building virtual filesystem that let you mount a specific tree object, perhaps via fuse, may find it useful, too, even though I suspect that may not be your primary focus.

Documentation/rev-list-options.txt specification contained in <path>. · line 738

Quoted 12 lines

Documentation/rev-list-options.txt +2 -2

index c2c1c40e6..c78985c41 100644
@@ -734,8 +734,12 @@ 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 <object>. <depth>=1

Here, <object> refers to the objects directly requested on the command line (or --stdin)? Triggering this question from me is a sign that this description may want to say a bit more to avoid the same question from the real readers. Perhaps replace "included explicitly in <object>" with "explicitly requested by listing them on the command line or feeding them with --stdin", or something like that?

Quoted 7 lines

list-objects-filter-options.c +0 -0

index e8da2e858..9dc61d6e6 100644
@@ -50,12 +50,12 @@ static int gently_parse_list_objects_filter(
              }
 

list-objects-filter-options.c static int gently_parse_list_objects_filter( · line 58

Quoted 10 lines

list-objects-filter-options.c +3 -3

      } 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_depth_limit_value)) {
                      if (errbuf) {
                              strbuf_addstr(
                                      errbuf,
-                                     _("only 'tree:0' is supported"));
+                                     _("expected 'tree:<int>'"));

We do not accept "tree:-1", even though "-1" is an int. Is it too obvious to worry about? I do not think we want to say tree:<uint> even if we do want to make it clear we reject "tree:-1"

I am wondering if "expected 'tree:<depth>'" would work better.

list-objects-filter-options.h struct list_objects_filter_options { · line 48

Quoted 10 lines

list-objects-filter-options.h +1 -0

index af64e5c66..c1ae70cd8 100644
@@ -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_depth_limit_value;
 };

This change gets it right by adding "depth" in the field name and it is not a comment on this patch, but someday not in too distant future we should rename the "blob_limit_value" to make it clear that it is filtering by number of bytes, as other filtering criteria on blobs that can be expressed in ulong are quite possible.

list-objects-filter-options.h

Quoted 12 lines

list-objects-filter-options.h +1 -1

-static enum list_objects_filter_result filter_trees_none(
+static enum list_objects_filter_result filter_trees_depth(
      enum list_objects_filter_situation filter_situation,

struct object *obj,
const char *pathname,
const char *filename,
void *filter_data_)
{

list-objects-filter-options.h +3 -1

-     struct filter_trees_none_data *filter_data = filter_data_;
+     struct filter_trees_depth_data *filter_data = filter_data_;
+
+     int too_deep = filter_data->current_depth >= filter_data->max_depth;

Does max mean "maximum allowed", or "this and anything larger are rejected". The latter sound wrong, but I offhand do not know if your current_depth counts from 0 or 1, so there may not be off-by-one.

- dir.c::within_depth() that is used by pathspec matching that in turn is used by "grep --max-depth=1" does "if (depth > max_depth)", which sounds more in line with the usual convention, I would think.

- pack-objects has max_delta_cache_size, which also is used as "maximum allowed", not "this is already too big". So is its max_depth.

There may be other examples. One existing violator I noticed was the "reject blobs that is this size or larger" in this file; it is called "max_bytes", but it is apparently not "maximum allowed", which we probably would want to fix.

list-objects-filter-options.h

Quoted 4 lines

list-objects-filter-options.h +4 -0

+     /*
+      * Note that we do not use _MARK_SEEN in order to allow re-traversal in
+      * case we encounter a tree or blob again at a shallower depth.
+      */

Hmph. Earlier tree:0 support never even read the actual tree, so this was not a problem. We wouldn't have found a tree in deeper places first and then at a shallower depth, as we wouldn't have seen any tree in any depth deeper than the surface anyway.

Now we need to worry about a tree that originally gets seen in a deeper depth (that is still below the allowed maximum) to reappear at a shallower place, so a subtree within it that used to be too deep may now be within the allowed maximum depth.

Step 1 of these three patches made sure trees are not even opened under "tree:0", so it was not just optimizing/shrinking the output of rev-list but also optimizing the traversal. When we are collecting omits, however, this one now returns _ZERO which means we still traverse into the tree, even under "tree:0"? I must be reading the code incorrectly (in general, when we are seeing a tree object that itself is at the maximum allowed depth, trees found by reading its contents will never become eligible for output, even if they are found at a shallower depth than their other copies were previously found, I would think).

list-objects-filter-options.h

Quoted 7 lines

      switch (filter_situation) {
      default:
              BUG("unknown filter_situation: %d", filter_situation);

list-objects-filter-options.h +1 -1

-     case LOFS_BEGIN_TREE:
      case LOFS_BLOB:
+             if (!too_deep) goto include_it;

Style: on two lines, like you did below for the next if() statement.

Quoted 36 lines

list-objects-filter-options.h +19 -3

+
+             if (filter_data->omits)
+                     oidset_insert(filter_data->omits, &obj->oid);
+
+             return LOFR_ZERO;
+
+     case LOFS_BEGIN_TREE:
+             filter_data->current_depth++;
+
+             if (!too_deep) goto include_it;
+
              if (filter_data->omits) {
                      oidset_insert(filter_data->omits, &obj->oid);
-                     /* _MARK_SEEN but not _DO_SHOW (hard omit) */
-                     return LOFR_MARK_SEEN;
+                     return LOFR_ZERO;
              }
              else
                      /*
                       * Not collecting omits so no need to to traverse tree.
                       */
-                     return LOFR_SKIP_TREE | LOFR_MARK_SEEN;
+                     return LOFR_SKIP_TREE;
 
      case LOFS_END_TREE:
              assert(obj->type == OBJ_TREE);
+             filter_data->current_depth--;
              return LOFR_ZERO;
 
      }
+
+include_it:
+     if (filter_data->omits)
+             oidset_remove(filter_data->omits, &obj->oid);
+     return LOFR_MARK_SEEN | LOFR_DO_SHOW;
 }

Quoted 4 lines · Matthew DeVore

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

This would reduce round-trip, as you do not have to fetch the tree to see what its contents are before issuing another set of fetches for them. Those who are building virtual filesystem that let you mount a specific tree object, perhaps via fuse, may find it useful, too, even though I suspect that may not be your primary focus.

Documentation/rev-list-options.txt specification contained in <path>. · line 738

Quoted 13 lines

Documentation/rev-list-options.txt +2 -2

index c2c1c40e6..c78985c41 100644
@@ -734,8 +734,12 @@ 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 <object>. <depth>=1

Here, <object> refers to the objects directly requested on the command line (or --stdin)? Triggering this question from me is a sign that this description may want to say a bit more to avoid the same question from the real readers. Perhaps replace "included explicitly in <object>" with "explicitly requested by listing them on the command line or feeding them with --stdin", or something like that?

Documentation/rev-list-options.txt specification contained in <path>. · line 739

Quoted 1 line

Documentation/rev-list-options.txt +1 -0

+                                     _("expected 'tree:<int>'"));

We do not accept "tree:-1", even though "-1" is an int. Is it too obvious to worry about? I do not think we want to say tree:<uint> even if we do want to make it clear we reject "tree:-1"

I am wondering if "expected 'tree:<depth>'" would work better.

Documentation/rev-list-options.txt specification contained in <path>. · line 741

Quoted 2 lines

Documentation/rev-list-options.txt +1 -0

+     unsigned long tree_depth_limit_value;
 };

This change gets it right by adding "depth" in the field name and it is not a comment on this patch, but someday not in too distant future we should rename the "blob_limit_value" to make it clear that it is filtering by number of bytes, as other filtering criteria on blobs that can be expressed in ulong are quite possible.

Quoted 10 lines

Documentation/rev-list-options.txt +1 -2

-static enum list_objects_filter_result filter_trees_none(
+static enum list_objects_filter_result filter_trees_depth(
      enum list_objects_filter_situation filter_situation,
      struct object *obj,
      const char *pathname,
      const char *filename,
      void *filter_data_)
 {
-     struct filter_trees_none_data *filter_data = filter_data_;

Documentation/rev-list-options.txt

Quoted 3 lines

Documentation/rev-list-options.txt +3 -0

+     struct filter_trees_depth_data *filter_data = filter_data_;
+
+     int too_deep = filter_data->current_depth >= filter_data->max_depth;

Does max mean "maximum allowed", or "this and anything larger are rejected". The latter sound wrong, but I offhand do not know if your current_depth counts from 0 or 1, so there may not be off-by-one.

There may be other examples. One existing violator I noticed was the "reject blobs that is this size or larger" in this file; it is called "max_bytes", but it is apparently not "maximum allowed", which we probably would want to fix.

Documentation/rev-list-options.txt

Quoted 4 lines

Documentation/rev-list-options.txt +4 -0

+     /*
+      * Note that we do not use _MARK_SEEN in order to allow re-traversal in
+      * case we encounter a tree or blob again at a shallower depth.
+      */

Hmph. Earlier tree:0 support never even read the actual tree, so this was not a problem. We wouldn't have found a tree in deeper places first and then at a shallower depth, as we wouldn't have seen any tree in any depth deeper than the surface anyway.

Now we need to worry about a tree that originally gets seen in a deeper depth (that is still below the allowed maximum) to reappear at a shallower place, so a subtree within it that used to be too deep may now be within the allowed maximum depth.

Step 1 of these three patches made sure trees are not even opened under "tree:0", so it was not just optimizing/shrinking the output of rev-list but also optimizing the traversal. When we are collecting omits, however, this one now returns _ZERO which means we still traverse into the tree, even under "tree:0"? I must be reading the code incorrectly (in general, when we are seeing a tree object that itself is at the maximum allowed depth, trees found by reading its contents will never become eligible for output, even if they are found at a shallower depth than their other copies were previously found, I would think).