Merge branch 'jk/partial-clone-sparse-blob'
[git/git.git] / list-objects-filter.c
index 83c788e..1e8d4e7 100644 (file)
  */
 #define FILTER_SHOWN_BUT_REVISIT (1<<21)
 
-/*
- * A filter for list-objects to omit ALL blobs from the traversal.
- * And to OPTIONALLY collect a list of the omitted OIDs.
- */
-struct filter_blobs_none_data {
+struct subfilter {
+       struct filter *filter;
+       struct oidset seen;
+       struct oidset omits;
+       struct object_id skip_tree;
+       unsigned is_skipping_tree : 1;
+};
+
+struct filter {
+       enum list_objects_filter_result (*filter_object_fn)(
+               struct repository *r,
+               enum list_objects_filter_situation filter_situation,
+               struct object *obj,
+               const char *pathname,
+               const char *filename,
+               struct oidset *omits,
+               void *filter_data);
+
+       /*
+        * Optional. If this function is supplied and the filter needs
+        * to collect omits, then this function is called once before
+        * free_fn is called.
+        *
+        * This is required because the following two conditions hold:
+        *
+        *   a. A tree filter can add and remove objects as an object
+        *      graph is traversed.
+        *   b. A combine filter's omit set is the union of all its
+        *      subfilters, which may include tree: filters.
+        *
+        * As such, the omits sets must be separate sets, and can only
+        * be unioned after the traversal is completed.
+        */
+       void (*finalize_omits_fn)(struct oidset *omits, void *filter_data);
+
+       void (*free_fn)(void *filter_data);
+
+       void *filter_data;
+
+       /* If non-NULL, the filter collects a list of the omitted OIDs here. */
        struct oidset *omits;
 };
 
@@ -40,10 +75,9 @@ static enum list_objects_filter_result filter_blobs_none(
        struct object *obj,
        const char *pathname,
        const char *filename,
+       struct oidset *omits,
        void *filter_data_)
 {
-       struct filter_blobs_none_data *filter_data = filter_data_;
-
        switch (filter_situation) {
        default:
                BUG("unknown filter_situation: %d", filter_situation);
@@ -61,24 +95,18 @@ static enum list_objects_filter_result filter_blobs_none(
                assert(obj->type == OBJ_BLOB);
                assert((obj->flags & SEEN) == 0);
 
-               if (filter_data->omits)
-                       oidset_insert(filter_data->omits, &obj->oid);
+               if (omits)
+                       oidset_insert(omits, &obj->oid);
                return LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */
        }
 }
 
-static void *filter_blobs_none__init(
-       struct oidset *omitted,
+static void filter_blobs_none__init(
        struct list_objects_filter_options *filter_options,
-       filter_object_fn *filter_fn,
-       filter_free_fn *filter_free_fn)
+       struct filter *filter)
 {
-       struct filter_blobs_none_data *d = xcalloc(1, sizeof(*d));
-       d->omits = omitted;
-
-       *filter_fn = filter_blobs_none;
-       *filter_free_fn = free;
-       return d;
+       filter->filter_object_fn = filter_blobs_none;
+       filter->free_fn = free;
 }
 
 /*
@@ -86,8 +114,6 @@ static void *filter_blobs_none__init(
  * Can OPTIONALLY collect a list of the omitted OIDs.
  */
 struct filter_trees_depth_data {
-       struct oidset *omits;
-
        /*
         * Maps trees to the minimum depth at which they were seen. It is not
         * necessary to re-traverse a tree at deeper or equal depths than it has
@@ -110,16 +136,16 @@ struct seen_map_entry {
 /* 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,
+       struct oidset *omits,
        int include_it)
 {
-       if (!filter_data->omits)
+       if (!omits)
                return 0;
 
        if (include_it)
-               return oidset_remove(filter_data->omits, &obj->oid);
+               return oidset_remove(omits, &obj->oid);
        else
-               return oidset_insert(filter_data->omits, &obj->oid);
+               return oidset_insert(omits, &obj->oid);
 }
 
 static enum list_objects_filter_result filter_trees_depth(
@@ -128,6 +154,7 @@ static enum list_objects_filter_result filter_trees_depth(
        struct object *obj,
        const char *pathname,
        const char *filename,
+       struct oidset *omits,
        void *filter_data_)
 {
        struct filter_trees_depth_data *filter_data = filter_data_;
@@ -152,7 +179,7 @@ static enum list_objects_filter_result filter_trees_depth(
                return LOFR_ZERO;
 
        case LOFS_BLOB:
-               filter_trees_update_omits(obj, filter_data, include_it);
+               filter_trees_update_omits(obj, omits, include_it);
                return include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;
 
        case LOFS_BEGIN_TREE:
@@ -173,12 +200,12 @@ static enum list_objects_filter_result filter_trees_depth(
                        filter_res = LOFR_SKIP_TREE;
                } else {
                        int been_omitted = filter_trees_update_omits(
-                               obj, filter_data, include_it);
+                               obj, omits, include_it);
                        seen_info->depth = filter_data->current_depth;
 
                        if (include_it)
                                filter_res = LOFR_DO_SHOW;
-                       else if (filter_data->omits && !been_omitted)
+                       else if (omits && !been_omitted)
                                /*
                                 * Must update omit information of children
                                 * recursively; they have not been omitted yet.
@@ -201,21 +228,18 @@ static void filter_trees_free(void *filter_data) {
        free(d);
 }
 
-static void *filter_trees_depth__init(
-       struct oidset *omitted,
+static void filter_trees_depth__init(
        struct list_objects_filter_options *filter_options,
-       filter_object_fn *filter_fn,
-       filter_free_fn *filter_free_fn)
+       struct filter *filter)
 {
        struct filter_trees_depth_data *d = xcalloc(1, sizeof(*d));
-       d->omits = omitted;
        oidmap_init(&d->seen_at_depth, 0);
        d->exclude_depth = filter_options->tree_exclude_depth;
        d->current_depth = 0;
 
-       *filter_fn = filter_trees_depth;
-       *filter_free_fn = filter_trees_free;
-       return d;
+       filter->filter_data = d;
+       filter->filter_object_fn = filter_trees_depth;
+       filter->free_fn = filter_trees_free;
 }
 
 /*
@@ -223,7 +247,6 @@ static void *filter_trees_depth__init(
  * And to OPTIONALLY collect a list of the omitted OIDs.
  */
 struct filter_blobs_limit_data {
-       struct oidset *omits;
        unsigned long max_bytes;
 };
 
@@ -233,6 +256,7 @@ static enum list_objects_filter_result filter_blobs_limit(
        struct object *obj,
        const char *pathname,
        const char *filename,
+       struct oidset *omits,
        void *filter_data_)
 {
        struct filter_blobs_limit_data *filter_data = filter_data_;
@@ -270,30 +294,27 @@ static enum list_objects_filter_result filter_blobs_limit(
                if (object_length < filter_data->max_bytes)
                        goto include_it;
 
-               if (filter_data->omits)
-                       oidset_insert(filter_data->omits, &obj->oid);
+               if (omits)
+                       oidset_insert(omits, &obj->oid);
                return LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */
        }
 
 include_it:
-       if (filter_data->omits)
-               oidset_remove(filter_data->omits, &obj->oid);
+       if (omits)
+               oidset_remove(omits, &obj->oid);
        return LOFR_MARK_SEEN | LOFR_DO_SHOW;
 }
 
-static void *filter_blobs_limit__init(
-       struct oidset *omitted,
+static void filter_blobs_limit__init(
        struct list_objects_filter_options *filter_options,
-       filter_object_fn *filter_fn,
-       filter_free_fn *filter_free_fn)
+       struct filter *filter)
 {
        struct filter_blobs_limit_data *d = xcalloc(1, sizeof(*d));
-       d->omits = omitted;
        d->max_bytes = filter_options->blob_limit_value;
 
-       *filter_fn = filter_blobs_limit;
-       *filter_free_fn = free;
-       return d;
+       filter->filter_data = d;
+       filter->filter_object_fn = filter_blobs_limit;
+       filter->free_fn = free;
 }
 
 /*
@@ -307,12 +328,12 @@ static void *filter_blobs_limit__init(
  */
 struct frame {
        /*
-        * defval is the usual default include/exclude value that
+        * default_match is the usual default include/exclude value that
         * should be inherited as we recurse into directories based
         * upon pattern matching of the directory itself or of a
         * containing directory.
         */
-       int defval;
+       enum pattern_match_result default_match;
 
        /*
         * 1 if the directory (recursively) contains any provisionally
@@ -326,8 +347,7 @@ struct frame {
 };
 
 struct filter_sparse_data {
-       struct oidset *omits;
-       struct exclude_list el;
+       struct pattern_list pl;
 
        size_t nr, alloc;
        struct frame *array_frame;
@@ -339,11 +359,13 @@ static enum list_objects_filter_result filter_sparse(
        struct object *obj,
        const char *pathname,
        const char *filename,
+       struct oidset *omits,
        void *filter_data_)
 {
        struct filter_sparse_data *filter_data = filter_data_;
-       int val, dtype;
+       int dtype;
        struct frame *frame;
+       enum pattern_match_result match;
 
        switch (filter_situation) {
        default:
@@ -352,15 +374,15 @@ static enum list_objects_filter_result filter_sparse(
        case LOFS_BEGIN_TREE:
                assert(obj->type == OBJ_TREE);
                dtype = DT_DIR;
-               val = is_excluded_from_list(pathname, strlen(pathname),
-                                           filename, &dtype, &filter_data->el,
-                                           r->index);
-               if (val < 0)
-                       val = filter_data->array_frame[filter_data->nr - 1].defval;
+               match = path_matches_pattern_list(pathname, strlen(pathname),
+                                                 filename, &dtype, &filter_data->pl,
+                                                 r->index);
+               if (match == UNDECIDED)
+                       match = filter_data->array_frame[filter_data->nr - 1].default_match;
 
                ALLOC_GROW(filter_data->array_frame, filter_data->nr + 1,
                           filter_data->alloc);
-               filter_data->array_frame[filter_data->nr].defval = val;
+               filter_data->array_frame[filter_data->nr].default_match = match;
                filter_data->array_frame[filter_data->nr].child_prov_omit = 0;
                filter_data->nr++;
 
@@ -414,14 +436,14 @@ static enum list_objects_filter_result filter_sparse(
                frame = &filter_data->array_frame[filter_data->nr - 1];
 
                dtype = DT_REG;
-               val = is_excluded_from_list(pathname, strlen(pathname),
-                                           filename, &dtype, &filter_data->el,
+               match = path_matches_pattern_list(pathname, strlen(pathname),
+                                           filename, &dtype, &filter_data->pl,
                                            r->index);
-               if (val < 0)
-                       val = frame->defval;
-               if (val > 0) {
-                       if (filter_data->omits)
-                               oidset_remove(filter_data->omits, &obj->oid);
+               if (match == UNDECIDED)
+                       match = frame->default_match;
+               if (match == MATCHED) {
+                       if (omits)
+                               oidset_remove(omits, &obj->oid);
                        return LOFR_MARK_SEEN | LOFR_DO_SHOW;
                }
 
@@ -435,8 +457,8 @@ static enum list_objects_filter_result filter_sparse(
                 * Leave the LOFR_ bits unset so that if the blob appears
                 * again in the traversal, we will be asked again.
                 */
-               if (filter_data->omits)
-                       oidset_insert(filter_data->omits, &obj->oid);
+               if (omits)
+                       oidset_insert(omits, &obj->oid);
 
                /*
                 * Remember that at least 1 blob in this tree was
@@ -456,11 +478,9 @@ static void filter_sparse_free(void *filter_data)
        free(d);
 }
 
-static void *filter_sparse_oid__init(
-       struct oidset *omitted,
+static void filter_sparse_oid__init(
        struct list_objects_filter_options *filter_options,
-       filter_object_fn *filter_fn,
-       filter_free_fn *filter_free_fn)
+       struct filter *filter)
 {
        struct filter_sparse_data *d = xcalloc(1, sizeof(*d));
        struct object_context oc;
@@ -471,26 +491,156 @@ static void *filter_sparse_oid__init(
                                 GET_OID_BLOB, &sparse_oid, &oc))
                die(_("unable to access sparse blob in '%s'"),
                    filter_options->sparse_oid_name);
-       d->omits = omitted;
-       if (add_excludes_from_blob_to_list(&sparse_oid, "", 0, &d->el) < 0)
+       if (add_patterns_from_blob_to_list(&sparse_oid, "", 0, &d->pl) < 0)
                die(_("unable to parse sparse filter data in %s"),
                    oid_to_hex(&sparse_oid));
 
        ALLOC_GROW(d->array_frame, d->nr + 1, d->alloc);
-       d->array_frame[d->nr].defval = 0; /* default to include */
+       d->array_frame[d->nr].default_match = 0; /* default to include */
        d->array_frame[d->nr].child_prov_omit = 0;
        d->nr++;
 
-       *filter_fn = filter_sparse;
-       *filter_free_fn = filter_sparse_free;
-       return d;
+       filter->filter_data = d;
+       filter->filter_object_fn = filter_sparse;
+       filter->free_fn = filter_sparse_free;
 }
 
-typedef void *(*filter_init_fn)(
-       struct oidset *omitted,
+/* A filter which only shows objects shown by all sub-filters. */
+struct combine_filter_data {
+       struct subfilter *sub;
+       size_t nr;
+};
+
+static enum list_objects_filter_result process_subfilter(
+       struct repository *r,
+       enum list_objects_filter_situation filter_situation,
+       struct object *obj,
+       const char *pathname,
+       const char *filename,
+       struct subfilter *sub)
+{
+       enum list_objects_filter_result result;
+
+       /*
+        * Check and update is_skipping_tree before oidset_contains so
+        * that is_skipping_tree gets unset even when the object is
+        * marked as seen.  As of this writing, no filter uses
+        * LOFR_MARK_SEEN on trees that also uses LOFR_SKIP_TREE, so the
+        * ordering is only theoretically important. Be cautious if you
+        * change the order of the below checks and more filters have
+        * been added!
+        */
+       if (sub->is_skipping_tree) {
+               if (filter_situation == LOFS_END_TREE &&
+                   oideq(&obj->oid, &sub->skip_tree))
+                       sub->is_skipping_tree = 0;
+               else
+                       return LOFR_ZERO;
+       }
+       if (oidset_contains(&sub->seen, &obj->oid))
+               return LOFR_ZERO;
+
+       result = list_objects_filter__filter_object(
+               r, filter_situation, obj, pathname, filename, sub->filter);
+
+       if (result & LOFR_MARK_SEEN)
+               oidset_insert(&sub->seen, &obj->oid);
+
+       if (result & LOFR_SKIP_TREE) {
+               sub->is_skipping_tree = 1;
+               sub->skip_tree = obj->oid;
+       }
+
+       return result;
+}
+
+static enum list_objects_filter_result filter_combine(
+       struct repository *r,
+       enum list_objects_filter_situation filter_situation,
+       struct object *obj,
+       const char *pathname,
+       const char *filename,
+       struct oidset *omits,
+       void *filter_data)
+{
+       struct combine_filter_data *d = filter_data;
+       enum list_objects_filter_result combined_result =
+               LOFR_DO_SHOW | LOFR_MARK_SEEN | LOFR_SKIP_TREE;
+       size_t sub;
+
+       for (sub = 0; sub < d->nr; sub++) {
+               enum list_objects_filter_result sub_result = process_subfilter(
+                       r, filter_situation, obj, pathname, filename,
+                       &d->sub[sub]);
+               if (!(sub_result & LOFR_DO_SHOW))
+                       combined_result &= ~LOFR_DO_SHOW;
+               if (!(sub_result & LOFR_MARK_SEEN))
+                       combined_result &= ~LOFR_MARK_SEEN;
+               if (!d->sub[sub].is_skipping_tree)
+                       combined_result &= ~LOFR_SKIP_TREE;
+       }
+
+       return combined_result;
+}
+
+static void filter_combine__free(void *filter_data)
+{
+       struct combine_filter_data *d = filter_data;
+       size_t sub;
+       for (sub = 0; sub < d->nr; sub++) {
+               list_objects_filter__free(d->sub[sub].filter);
+               oidset_clear(&d->sub[sub].seen);
+               if (d->sub[sub].omits.set.size)
+                       BUG("expected oidset to be cleared already");
+       }
+       free(d->sub);
+}
+
+static void add_all(struct oidset *dest, struct oidset *src) {
+       struct oidset_iter iter;
+       struct object_id *src_oid;
+
+       oidset_iter_init(src, &iter);
+       while ((src_oid = oidset_iter_next(&iter)) != NULL)
+               oidset_insert(dest, src_oid);
+}
+
+static void filter_combine__finalize_omits(
+       struct oidset *omits,
+       void *filter_data)
+{
+       struct combine_filter_data *d = filter_data;
+       size_t sub;
+
+       for (sub = 0; sub < d->nr; sub++) {
+               add_all(omits, &d->sub[sub].omits);
+               oidset_clear(&d->sub[sub].omits);
+       }
+}
+
+static void filter_combine__init(
        struct list_objects_filter_options *filter_options,
-       filter_object_fn *filter_fn,
-       filter_free_fn *filter_free_fn);
+       struct filter* filter)
+{
+       struct combine_filter_data *d = xcalloc(1, sizeof(*d));
+       size_t sub;
+
+       d->nr = filter_options->sub_nr;
+       d->sub = xcalloc(d->nr, sizeof(*d->sub));
+       for (sub = 0; sub < d->nr; sub++)
+               d->sub[sub].filter = list_objects_filter__init(
+                       filter->omits ? &d->sub[sub].omits : NULL,
+                       &filter_options->sub[sub]);
+
+       filter->filter_data = d;
+       filter->filter_object_fn = filter_combine;
+       filter->free_fn = filter_combine__free;
+       filter->finalize_omits_fn = filter_combine__finalize_omits;
+}
+
+typedef void (*filter_init_fn)(
+       struct list_objects_filter_options *filter_options,
+       struct filter *filter);
 
 /*
  * Must match "enum list_objects_filter_choice".
@@ -501,14 +651,14 @@ static filter_init_fn s_filters[] = {
        filter_blobs_limit__init,
        filter_trees_depth__init,
        filter_sparse_oid__init,
+       filter_combine__init,
 };
 
-void *list_objects_filter__init(
+struct filter *list_objects_filter__init(
        struct oidset *omitted,
-       struct list_objects_filter_options *filter_options,
-       filter_object_fn *filter_fn,
-       filter_free_fn *filter_free_fn)
+       struct list_objects_filter_options *filter_options)
 {
+       struct filter *filter;
        filter_init_fn init_fn;
 
        assert((sizeof(s_filters) / sizeof(s_filters[0])) == LOFC__COUNT);
@@ -518,10 +668,44 @@ void *list_objects_filter__init(
                    filter_options->choice);
 
        init_fn = s_filters[filter_options->choice];
-       if (init_fn)
-               return init_fn(omitted, filter_options,
-                              filter_fn, filter_free_fn);
-       *filter_fn = NULL;
-       *filter_free_fn = NULL;
-       return NULL;
+       if (!init_fn)
+               return NULL;
+
+       filter = xcalloc(1, sizeof(*filter));
+       filter->omits = omitted;
+       init_fn(filter_options, filter);
+       return filter;
+}
+
+enum list_objects_filter_result list_objects_filter__filter_object(
+       struct repository *r,
+       enum list_objects_filter_situation filter_situation,
+       struct object *obj,
+       const char *pathname,
+       const char *filename,
+       struct filter *filter)
+{
+       if (filter && (obj->flags & NOT_USER_GIVEN))
+               return filter->filter_object_fn(r, filter_situation, obj,
+                                               pathname, filename,
+                                               filter->omits,
+                                               filter->filter_data);
+       /*
+        * No filter is active or user gave object explicitly. In this case,
+        * always show the object (except when LOFS_END_TREE, since this tree
+        * had already been shown when LOFS_BEGIN_TREE).
+        */
+       if (filter_situation == LOFS_END_TREE)
+               return 0;
+       return LOFR_MARK_SEEN | LOFR_DO_SHOW;
+}
+
+void list_objects_filter__free(struct filter *filter)
+{
+       if (!filter)
+               return;
+       if (filter->finalize_omits_fn && filter->omits)
+               filter->finalize_omits_fn(filter->omits, filter->filter_data);
+       filter->free_fn(filter->filter_data);
+       free(filter);
 }