1 files changed, 117 insertions, 53 deletions

diff --git a/list-objects-filter.c b/list-objects-filter.c
index 765f3df3b0..36e1f774bc 100644
--- a/list-objects-filter.c
+++ b/list-objects-filter.c
@@ -10,6 +10,7 @@
 #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"
 
@@ -34,6 +35,7 @@ struct filter_blobs_none_data {
 };
 
 static enum list_objects_filter_result filter_blobs_none(
+	struct repository *r,
 	enum list_objects_filter_situation filter_situation,
 	struct object *obj,
 	const char *pathname,
@@ -83,54 +85,136 @@ static void *filter_blobs_none__init(
  * 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 *pathname,
 	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;
 }
 
@@ -144,6 +228,7 @@ struct filter_blobs_limit_data {
 };
 
 static enum list_objects_filter_result filter_blobs_limit(
+	struct repository *r,
 	enum list_objects_filter_situation filter_situation,
 	struct object *obj,
 	const char *pathname,
@@ -171,7 +256,7 @@ static enum list_objects_filter_result filter_blobs_limit(
 		assert(obj->type == OBJ_BLOB);
 		assert((obj->flags & SEEN) == 0);
 
-		t = oid_object_info(the_repository, &obj->oid, &object_length);
+		t = oid_object_info(r, &obj->oid, &object_length);
 		if (t != OBJ_BLOB) { /* probably OBJ_NONE */
 			/*
 			 * We DO NOT have the blob locally, so we cannot
@@ -249,6 +334,7 @@ struct filter_sparse_data {
 };
 
 static enum list_objects_filter_result filter_sparse(
+	struct repository *r,
 	enum list_objects_filter_situation filter_situation,
 	struct object *obj,
 	const char *pathname,
@@ -268,15 +354,15 @@ static enum list_objects_filter_result filter_sparse(
 		dtype = DT_DIR;
 		val = is_excluded_from_list(pathname, strlen(pathname),
 					    filename, &dtype, &filter_data->el,
-					    &the_index);
+					    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
@@ -301,16 +387,15 @@ static enum list_objects_filter_result filter_sparse(
 
 	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;
 
 		/*
@@ -326,12 +411,12 @@ static enum list_objects_filter_result filter_sparse(
 		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),
 					    filename, &dtype, &filter_data->el,
-					    &the_index);
+					    r->index);
 		if (val < 0)
 			val = frame->defval;
 		if (val > 0) {
@@ -367,7 +452,7 @@ static enum list_objects_filter_result filter_sparse(
 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);
 }
 
@@ -386,27 +471,7 @@ static void *filter_sparse_oid__init(
 	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;
@@ -426,9 +491,8 @@ static filter_init_fn s_filters[] = {
 	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(