#include "list-objects.h"
#include "list-objects-filter.h"
#include "list-objects-filter-options.h"
+#include "oidmap.h"
#include "oidset.h"
#include "object-store.h"
* A filter for list-objects to omit ALL trees and blobs from the traversal.
* Can OPTIONALLY collect a list of the omitted OIDs.
*/
-struct filter_trees_none_data {
+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
+ * already been traversed.
+ *
+ * We can't use LOFR_MARK_SEEN for tree objects since this will prevent
+ * it from being traversed at shallower depths.
+ */
+ struct oidmap seen_at_depth;
+
+ unsigned long exclude_depth;
+ unsigned long current_depth;
+};
+
+struct seen_map_entry {
+ struct oidmap_entry base;
+ size_t depth;
};
-static enum list_objects_filter_result filter_trees_none(
+/* 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 0;
+
+ if (include_it)
+ return oidset_remove(filter_data->omits, &obj->oid);
+ else
+ return oidset_insert(filter_data->omits, &obj->oid);
+}
+
+static enum list_objects_filter_result filter_trees_depth(
struct repository *r,
enum list_objects_filter_situation filter_situation,
struct object *obj,
const char *filename,
void *filter_data_)
{
- struct filter_trees_none_data *filter_data = filter_data_;
+ struct filter_trees_depth_data *filter_data = filter_data_;
+ struct seen_map_entry *seen_info;
+ int include_it = filter_data->current_depth <
+ filter_data->exclude_depth;
+ int filter_res;
+ int already_seen;
+
+ /*
+ * 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.
+ */
switch (filter_situation) {
default:
BUG("unknown filter_situation: %d", filter_situation);
- case LOFS_BEGIN_TREE:
+ case LOFS_END_TREE:
+ assert(obj->type == OBJ_TREE);
+ filter_data->current_depth--;
+ return LOFR_ZERO;
+
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;
+ filter_trees_update_omits(obj, filter_data, include_it);
+ return include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;
+
+ case LOFS_BEGIN_TREE:
+ seen_info = oidmap_get(
+ &filter_data->seen_at_depth, &obj->oid);
+ if (!seen_info) {
+ 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 {
- /*
- * Not collecting omits so no need to to traverse tree.
- */
- return LOFR_SKIP_TREE | LOFR_MARK_SEEN;
+ already_seen =
+ filter_data->current_depth >= seen_info->depth;
}
- case LOFS_END_TREE:
- assert(obj->type == OBJ_TREE);
- return LOFR_ZERO;
+ 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;
+
+ if (include_it)
+ filter_res = LOFR_DO_SHOW;
+ 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;
+ }
+ filter_data->current_depth++;
+ return filter_res;
}
}
-static void* filter_trees_none__init(
+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);
+}
+
+static void *filter_trees_depth__init(
struct oidset *omitted,
struct list_objects_filter_options *filter_options,
filter_object_fn *filter_fn,
filter_free_fn *filter_free_fn)
{
- struct filter_trees_none_data *d = xcalloc(1, sizeof(*d));
+ 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_none;
- *filter_free_fn = free;
+ *filter_fn = filter_trees_depth;
+ *filter_free_fn = filter_trees_free;
return d;
}
filename, &dtype, &filter_data->el,
r->index);
if (val < 0)
- val = filter_data->array_frame[filter_data->nr].defval;
+ val = filter_data->array_frame[filter_data->nr - 1].defval;
ALLOC_GROW(filter_data->array_frame, filter_data->nr + 1,
filter_data->alloc);
- filter_data->nr++;
filter_data->array_frame[filter_data->nr].defval = val;
filter_data->array_frame[filter_data->nr].child_prov_omit = 0;
+ filter_data->nr++;
/*
* A directory with this tree OID may appear in multiple
case LOFS_END_TREE:
assert(obj->type == OBJ_TREE);
- assert(filter_data->nr > 0);
+ assert(filter_data->nr > 1);
- frame = &filter_data->array_frame[filter_data->nr];
- filter_data->nr--;
+ frame = &filter_data->array_frame[--filter_data->nr];
/*
* Tell our parent directory if any of our children were
* provisionally omitted.
*/
- filter_data->array_frame[filter_data->nr].child_prov_omit |=
+ filter_data->array_frame[filter_data->nr - 1].child_prov_omit |=
frame->child_prov_omit;
/*
assert(obj->type == OBJ_BLOB);
assert((obj->flags & SEEN) == 0);
- frame = &filter_data->array_frame[filter_data->nr];
+ frame = &filter_data->array_frame[filter_data->nr - 1];
dtype = DT_REG;
val = is_excluded_from_list(pathname, strlen(pathname),
static void filter_sparse_free(void *filter_data)
{
struct filter_sparse_data *d = filter_data;
- /* TODO free contents of 'd' */
+ free(d->array_frame);
free(d);
}
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].child_prov_omit = 0;
-
- *filter_fn = filter_sparse;
- *filter_free_fn = filter_sparse_free;
- return d;
-}
-
-static void *filter_sparse_path__init(
- struct oidset *omitted,
- struct list_objects_filter_options *filter_options,
- filter_object_fn *filter_fn,
- filter_free_fn *filter_free_fn)
-{
- struct filter_sparse_data *d = xcalloc(1, sizeof(*d));
- d->omits = omitted;
- if (add_excludes_from_file_to_list(filter_options->sparse_path_value,
- NULL, 0, &d->el, NULL) < 0)
- die("could not load filter specification");
-
- 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].child_prov_omit = 0;
+ d->nr++;
*filter_fn = filter_sparse;
*filter_free_fn = filter_sparse_free;
NULL,
filter_blobs_none__init,
filter_blobs_limit__init,
- filter_trees_none__init,
+ filter_trees_depth__init,
filter_sparse_oid__init,
- filter_sparse_path__init,
};
void *list_objects_filter__init(