Partial clone part 1: object filtering

list-objects-filter-options.c new file +22 -0

+{
+	struct object_context oc;
+	struct object_id sparse_oid;
+	const char *v0;
+	const char *v1;
+
+	if (filter_options->choice)
+		die(_("multiple object filter types cannot be combined"));
+
+	/*
+	 * TODO consider rejecting 'arg' if it contains any
+	 * TODO injection characters (since we might send this
+	 * TODO to a sub-command or to the server and we don't
+	 * TODO want to deal with legacy quoting/escaping for
+	 * TODO a new feature).
+	 */
+
+	filter_options->raw_value = strdup(arg);
+
+	if (skip_prefix(arg, "blob:", &v0) || skip_prefix(arg, "blobs:", &v0)) {
+		if (!strcmp(v0, "none")) {
+			filter_options->choice = LOFC_BLOB_NONE;

list-objects-filter-options.c new file +27 -0

+				free((char *)filter_options->raw_value);
+				filter_options->raw_value =
+					xstrfmt("sparse:oid=%s",
+						oid_to_hex(&sparse_oid));
+				filter_options->sparse_oid_value =
+					oiddup(&sparse_oid);
+			} else {
+				/*
+				 * We could not turn the <oid-expr> into an
+				 * OID.  Leave the raw_value as is in case
+				 * the server can parse it.  (It may refer to
+				 * a branch, commit, or blob we don't have.)
+				 */
+			}
+			return 0;
+		}
+
+		if (skip_prefix(v0, "path=", &v1)) {
+			filter_options->choice = LOFC_SPARSE_PATH;
+			filter_options->sparse_path_value = strdup(v1);
+			return 0;
+		}
+	}
+
+	die(_("invalid filter expression '%s'"), arg);
+	return 0;
+}

list-objects-filter.c +5 -0

+static enum list_objects_filter_result filter_blobs_limit(
+	enum list_objects_filter_type filter_type,
+	struct object *obj,
+	const char *pathname,
+	const char *filename,

list-objects-filter.c +7 -0

+		return LOFR_ZERO;
+
+	case LOFT_BEGIN_TREE:
+		assert(obj->type == OBJ_TREE);
+		/* always include all tree objects */
+		return LOFR_MARK_SEEN | LOFR_SHOW;
+

list-objects-filter.c +52 -0

+		if (is_special_filename) {
+			/*
+			 * Alwayse include ".git*" special files (regardless
+			 * of size).
+			 *
+			 * (This may cause us to include blobs that we do
+			 * not have locally because we are only looking at
+			 * the filename and don't actually have to read
+			 * them.)
+			 */
+			goto include_it;
+		}
+
+		t = sha1_object_info(obj->oid.hash, &object_length);
+		if (t != OBJ_BLOB) { /* probably OBJ_NONE */
+			/*
+			 * We DO NOT have the blob locally, so we cannot
+			 * apply the size filter criteria.  Be conservative
+			 * and force show it (and let the caller deal with
+			 * the ambiguity).  (This matches the behavior above
+			 * when the special filename matches.)
+			 */
+			goto include_it;
+		}
+
+		if (object_length < filter_data->max_bytes)
+			goto include_it;
+
+		/*
+		 * Provisionally omit it.  We've already established
+		 * that this blob is too big and doesn't have a special
+		 * filename, so we *WANT* to omit it.  However, there
+		 * may be a special file elsewhere in the tree that
+		 * references this same blob, so we cannot reject it
+		 * just yet.  Leave the LOFR_ bits unset so that *IF*
+		 * the blob appears again in the traversal, we will
+		 * be asked again.
+		 *
+		 * If we are keeping a list of the ommitted objects,
+		 * provisionally add it to the list.
+		 */
+
+		if (filter_data->omits)
+			oidset_insert(filter_data->omits, &obj->oid);
+		return LOFR_ZERO;
+	}
+
+include_it:
+	if (filter_data->omits)
+		oidset_remove(filter_data->omits, &obj->oid);
+	return LOFR_MARK_SEEN | LOFR_SHOW;
+}

list-objects-filter.c +27 -0

+/*
+ * During list-object traversal we allow certain objects to be
+ * filtered (omitted) from the result.  The active filter uses
+ * these result values to guide list-objects.
+ *
+ * _ZERO      : Do nothing with the object at this time.  It may
+ *              be revisited if it appears in another place in
+ *              the tree or in another commit during the overall
+ *              traversal.
+ *
+ * _MARK_SEEN : Mark this object as "SEEN" in the object flags.
+ *              This will prevent it from being revisited during
+ *              the remainder of the traversal.  This DOES NOT
+ *              imply that it will be included in the results.
+ *
+ * _SHOW      : Show this object in the results (call show() on it).
+ *              In general, objects should only be shown once, but
+ *              this result DOES NOT imply that we mark it SEEN.
+ *
+ * Most of the time, you want the combination (_MARK_SEEN | _SHOW)
+ * but they can be used independently, such as when sparse-checkout
+ * pattern matching is being applied.
+ *
+ * A _MARK_SEEN without _SHOW can be called a hard-omit -- the
+ * object is not shown and will never be reconsidered (unless a
+ * previous iteration has already shown it).
+ *

list-objects-filter.c +9 -0

+void traverse_commit_list_filtered(
+	struct list_objects_filter_options *filter_options,
+	struct rev_info *revs,
+	show_commit_fn show_commit,
+	show_object_fn show_object,
+	void *show_data,
+	struct oidset *omitted)
+{
+	filter_object_fn filter_fn = NULL;

list-objects-filter-options.c line 23

Quoted 2 lines · On Thu, 2 Nov 2017 17:50:11 +0000 Jeff Hostetler <[email protected]> wrote:

list-objects-filter-options.c new file +2 -0

+int parse_list_objects_filter(struct list_objects_filter_options *filter_options,
+			      const char *arg)

Returning void is fine, I think. It seems that all your code paths either return 0 or die.

Hi Jonathan,

Quoted 3 lines · Jonathan Tan

On Thu, 2 Nov 2017 17:50:11 +0000
Jeff Hostetler <[email protected]> wrote:

Quoted 5 lines

list-objects-filter-options.c line 23

Quoted 2 lines

list-objects-filter-options.c new file +2 -0

+int parse_list_objects_filter(struct list_objects_filter_options *filter_options,
+			      const char *arg)

Returning void is fine, I think. It seems that all your code paths either return 0 or die.

Can we please start to encourage libified code, rather than discourage it?

list-objects-filter-options.c line 67

Quoted 12 lines · On Thu, 2 Nov 2017 17:50:11 +0000 Jeff Hostetler <[email protected]> wrote:

list-objects-filter-options.c new file +12 -0

+		if (skip_prefix(v0, "oid=", &v1)) {
+			filter_options->choice = LOFC_SPARSE_OID;
+			if (!get_oid_with_context(v1, GET_OID_BLOB,
+						  &sparse_oid, &oc)) {
+				/*
+				 * We successfully converted the <oid-expr>
+				 * into an actual OID.  Rewrite the raw_value
+				 * in canonoical form with just the OID.
+				 * (If we send this request to the server, we
+				 * want an absolute expression rather than a
+				 * local-ref-relative expression.)
+				 */

I think this would lead to confusing behavior - for example, a fetch with "--filter=oid=mybranch:sparseconfig" would have different results depending on whether "mybranch" refers to a valid object locally.

The way I see it, this should either (i) only accept full 40-character OIDs or (ii) retain the raw string to be interpreted only when the filtering is done. (i) is simpler and safer, but is not so useful. In both cases, if the user really wants client-side interpretation, they can still use "$(git rev-parse foo)" to make it explicit.

Quoted 28 lines

list-objects-filter-options.c new file +27 -0

+				free((char *)filter_options->raw_value);
+				filter_options->raw_value =
+					xstrfmt("sparse:oid=%s",
+						oid_to_hex(&sparse_oid));
+				filter_options->sparse_oid_value =
+					oiddup(&sparse_oid);
+			} else {
+				/*
+				 * We could not turn the <oid-expr> into an
+				 * OID.  Leave the raw_value as is in case
+				 * the server can parse it.  (It may refer to
+				 * a branch, commit, or blob we don't have.)
+				 */
+			}
+			return 0;
+		}
+
+		if (skip_prefix(v0, "path=", &v1)) {
+			filter_options->choice = LOFC_SPARSE_PATH;
+			filter_options->sparse_path_value = strdup(v1);
+			return 0;
+		}
+	}
+
+	die(_("invalid filter expression '%s'"), arg);
+	return 0;
+}

[snip]

list-objects-filter-options.c line 109

Quoted 3 lines

list-objects-filter-options.c new file +3 -0

+void arg_format_list_objects_filter(
+	struct argv_array *argv_array,
+	const struct list_objects_filter_options *filter_options)

Is this function used anywhere (in this patch or subsequent patches)?

list-objects-filter.c line 16

Quoted 3 lines

list-objects-filter.c +2 -0

+/* See object.h and revision.h */
+#define FILTER_REVISIT (1<<25)

Looking later in the code, this flag indicates that a tree has been SHOWN, so it might be better to just call this FILTER_SHOWN.

[snip]

list-objects-filter.c line 193

Quoted 2 lines

list-objects-filter.c +2 -0

+struct frame {
+	int defval;

Document this variable?

list-objects-filter.c line 194

Quoted 1 line

list-objects-filter.c +1 -0

+	int child_prov_omit : 1;

I think it's clearer if we use "unsigned" here. Also, document this (e.g. "1 if any descendant of this tree object was provisionally omitted").

list-objects-filter.c

Quoted 5 lines

list-objects-filter.c +5 -0

+enum list_objects_filter_type {
+	LOFT_BEGIN_TREE,
+	LOFT_END_TREE,
+	LOFT_BLOB
+};

Optional: probably a better name would be list_objects_filter_situation.

Quoted 14 lines

list-objects-filter.c +14 -0

+void traverse_commit_list_filtered(
+	struct list_objects_filter_options *filter_options,
+	struct rev_info *revs,
+	show_commit_fn show_commit,
+	show_object_fn show_object,
+	void *show_data,
+	struct oidset *omitted)
+{
+	filter_object_fn filter_fn = NULL;
+	filter_free_fn filter_free_fn = NULL;
+	void *filter_data = NULL;
+
+	filter_data = list_objects_filter__init(omitted, filter_options,
+						&filter_fn, &filter_free_fn);

list-objects-filter.c

Quoted 5 lines

list-objects-filter.c +5 -0

+	do_traverse(revs, show_commit, show_object, show_data,
+		    filter_fn, filter_data);
+	if (filter_data && filter_free_fn)
+		filter_free_fn(filter_data);
+}

This function traverse_commit_list_filtered() is in list-objects.c but in list-objects-filter.h, if I'm reading the diff correctly?

Overall, this looks like a good change. Object traversal was upgraded with the behaviors of MARK_SEEN and SHOW independently controllable and with the ability to do things post-tree (in addition to pre-tree and blob), and this was used to support a few types of filtering, which subsequent patches will allow the user to invoke through "--filter=".

From: Jeff Hostetler <[email protected]>

Create traverse_commit_list_filtered() and add filtering interface to allow certain objects to be omitted from the traversal.
...

list-objects-filter.c new file +0 -0

new file mode 100644
index 0000000..7f28425

Jonathan and I were talking off-list about the performance effects of inspecting the pathnames to identify the ".git*" special files. I added it in my first draft back in the spring, thinking that even if you set the blob-limit to a small number (or zero), you'd probably still always want the .gitattribute and .gitignore files. But now with the addition of the sparse filter and functional dynamic object fetching, I'm not sure I see the need for this.

Also, if the primary use of the blob-limit is to filter out giant binary assets, it is unlikely anyone is going to have a 1MB+ .git* file, so it is unlikely that the is_special_file would include anything that wouldn't already be included by the size criteria.

So, if there's no objections, I think I'll remove this and simplify the blob-limit filter function. (That would let me get rid of the provisional omit code here.)

From: Jeff Hostetler <[email protected]>

Here is V2 of the list-object filtering. It replaces [1] and reflect a refactoring and simplification of the original.

I've added "--filter-ignore-missing" parameter to rev-list and pack-objects to ignore missing objects rather than error out. This allows this patch series to better stand on its own eliminates the need in part 1 for "patch 9" from V1.

This is a brute force ignore all missing objects. Later, in part 2 or part 3 when --exclude-promisor-objects is introduced, we will be able to ignore EXPECTED missing objects.

Quoted 4 lines · On Thu, 2 Nov 2017 17:50:07 +0000 Jeff Hostetler <[email protected]> wrote:

From: Jeff Hostetler <[email protected]>

Here is V2 of the list-object filtering. It replaces [1] and reflect a refactoring and simplification of the original.

Thanks, overall this looks quite good. I reviewed patches 2-6 (skipping 1 since it's already in next), made my comments on 4, and don't have any for the rest (besides what's below).

Quoted 5 lines

I've added "--filter-ignore-missing" parameter to rev-list and pack-objects to ignore missing objects rather than error out. This allows this patch series to better stand on its own eliminates the need in part 1 for "patch 9" from V1.

Quoted 3 lines

This is a brute force ignore all missing objects. Later, in part 2 or part 3 when --exclude-promisor-objects is introduced, we will be able to ignore EXPECTED missing objects.

(This is regarding patches 5 and 6.) Is the intention to support both flags? (That is, --ignore-missing to ignore without checking whether the object being missing is not unexpected, and --exclude-promisor-objects to check and ignore.)

Yes, I thought we should have both (perhaps renamed or combined into 1 parameter with value, such as --exclude=missing vs --exclude=promisor) and let the user decide how strict they want to be.

Quoted 3 lines · Jeff Hostetler

Yes, I thought we should have both (perhaps renamed or combined into 1 parameter with value, such as --exclude=missing vs --exclude=promisor) and let the user decide how strict they want to be.

Assuming we eventually get promisor support working, would there be any use case where "any missing is OK" mode would be useful in a sense more reasonable than "because we could have such a mode" and "it is not our business to prevent users from playing with fire"?

Quoted 5 lines

Assuming we eventually get promisor support working, would there be any use case where "any missing is OK" mode would be useful in a sense more reasonable than "because we could have such a mode" and "it is not our business to prevent users from playing with fire"?

For now, I'd like to keep my "any missing is OK" option. I do think it has value all by itself.

We are essentially using something like that now with our GVFS users on the gigantic Windows repo and haven't had any issues.

But yes, when we get promisor support working, we could revisit the need for this parameter.

However, I do have some scaling concerns here. If for example, I have 100M missing blobs (because we did an only commits-and-trees clone), the cost to compute "promisor missing" vs "just missing" might be prohibitively expensive. It could be something we want fsck/gc to be aware of, but other commands may want to just assume any missing objects are expected and continue.

Hopefully, we won't have a scale problem, but we just don't know yet.

I can see some use for this parameter - for example, when doing a report for statistical purposes (percentage of objects missing, for example) or for a background task that downloads missing objects into a cache. Also, power users who know what they're doing (or normal users in an emergency) can use this option when they have no network connection if they really need to find something out from the local repo.

In these cases, the promisor check (after detecting that the object is missing) is indeed not so useful, I think. (Or we can do the --exclude=missing and --exclude=promisor idea that Jeff mentioned - --exclude=missing now, and --exclude=promisor after we add promisor support.)

Having said that, I would be OK if we didn't have tolerance (and/or reporting) of missing objects right now. As far as I know, for the initial implementation of partial clone, only the server performs any filtering, and we assume that the server possesses all objects (so it does not need to filter out any missing objects).

Quoted 7 lines · Jonathan Tan

I can see some use for this parameter - for example, when doing a report for statistical purposes (percentage of objects missing, for example) or for a background task that downloads missing objects into a cache. Also, power users who know what they're doing (or normal users in an emergency) can use this option when they have no network connection if they really need to find something out from the local repo.

Quoted 5 lines

In these cases, the promisor check (after detecting that the object is missing) is indeed not so useful, I think. (Or we can do the --exclude=missing and --exclude=promisor idea that Jeff mentioned - --exclude=missing now, and --exclude=promisor after we add promisor support.)

This sounds like a reasonable thing to have in the endgame state to me.

Quoted 6 lines

Having said that, I would be OK if we didn't have tolerance (and/or reporting) of missing objects right now. As far as I know, for the initial implementation of partial clone, only the server performs any filtering, and we assume that the server possesses all objects (so it does not need to filter out any missing objects).

True. It does not have to exist in an early part, but I do not think we would terribly mind if it does, if only to help debugging and development.

Thanks for thinking it through.