Implement an iterative deepening mode (-ids)

5 files changed, 142 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index e81b509..718899a 100644
--- a/Makefile
+++ b/Makefile
@@ -100,6 +100,7 @@ tests/mksock: tests/mksock.o
 check: all
 	./tests.sh --bfs="$(realpath bfs)"
 	./tests.sh --bfs="$(realpath bfs) -dfs"
+	./tests.sh --bfs="$(realpath bfs) -ids"
 
 distcheck:
 	+$(MAKE) -Bs check CFLAGS="$(CFLAGS) -fsanitize=undefined -fsanitize=address"
diff --git a/bftw.c b/bftw.c
index 89ba083..6772408 100644
--- a/bftw.c
+++ b/bftw.c
@@ -39,6 +39,7 @@
 #include "bftw.h"
 #include "dstring.h"
 #include "stat.h"
+#include "trie.h"
 #include "util.h"
 #include <assert.h>
 #include <dirent.h>
@@ -1336,12 +1337,143 @@ static int bftw_dfs(const struct bftw_args *args) {
 	return ret;
 }
 
+/**
+ * Iterative deepening search state.
+ */
+struct bftw_ids_state {
+	/** The wrapped callback. */
+	bftw_callback *delegate;
+	/** The wrapped callback arguments. */
+	void *ptr;
+	/** Which visit this search corresponds to. */
+	enum bftw_visit visit;
+	/** The current target depth. */
+	size_t depth;
+	/** The set of pruned paths. */
+	struct trie *pruned;
+	/** An error code to report. */
+	int error;
+	/** Whether the bottom has been found. */
+	bool bottom;
+	/** Whether to quit the search. */
+	bool quit;
+};
+
+/** Iterative deepening callback function. */
+static enum bftw_action bftw_ids_callback(const struct BFTW *ftwbuf, void *ptr) {
+	struct bftw_ids_state *state = ptr;
+
+	struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
+	mutbuf->visit = state->visit;
+
+	if (ftwbuf->typeflag == BFTW_ERROR) {
+		if (state->depth - ftwbuf->depth <= 1) {
+			return state->delegate(ftwbuf, state->ptr);
+		} else {
+			return BFTW_SKIP_SUBTREE;
+		}
+	}
+
+	if (ftwbuf->depth < state->depth) {
+		if (trie_find_str(state->pruned, ftwbuf->path)) {
+			return BFTW_SKIP_SUBTREE;
+		} else {
+			return BFTW_CONTINUE;
+		}
+	} else if (state->visit == BFTW_POST) {
+		if (trie_find_str(state->pruned, ftwbuf->path)) {
+			return BFTW_SKIP_SUBTREE;
+		}
+	}
+
+	state->bottom = false;
+
+	enum bftw_action ret = state->delegate(ftwbuf, state->ptr);
+
+	switch (ret) {
+	case BFTW_CONTINUE:
+		ret = BFTW_SKIP_SUBTREE;
+		break;
+	case BFTW_SKIP_SIBLINGS:
+		// Can't be easily supported in this mode
+		state->error = EINVAL;
+		state->quit = true;
+		ret = BFTW_STOP;
+		break;
+	case BFTW_SKIP_SUBTREE:
+		if (ftwbuf->typeflag == BFTW_DIR) {
+			if (!trie_insert_str(state->pruned, ftwbuf->path)) {
+				state->error = errno;
+				state->quit = true;
+				ret = BFTW_STOP;
+			}
+		}
+		break;
+	case BFTW_STOP:
+		state->quit = true;
+		break;
+	}
+
+	return ret;
+}
+
+/**
+ * Iterative deepening bftw() wrapper.
+ */
+static int bftw_ids(const struct bftw_args *args) {
+	struct trie pruned;
+	trie_init(&pruned);
+
+	struct bftw_ids_state state = {
+		.delegate = args->callback,
+		.ptr = args->ptr,
+		.visit = BFTW_PRE,
+		.depth = 0,
+		.pruned = &pruned,
+		.bottom = false,
+	};
+
+	struct bftw_args ids_args = *args;
+	ids_args.callback = bftw_ids_callback;
+	ids_args.ptr = &state;
+	ids_args.flags &= ~BFTW_DEPTH;
+	ids_args.strategy = BFTW_DFS;
+
+	int ret = 0;
+
+	while (ret == 0 && !state.quit && !state.bottom) {
+		state.bottom = true;
+		ret = bftw_impl(&ids_args);
+		++state.depth;
+	}
+
+	if (args->flags & BFTW_DEPTH) {
+		state.visit = BFTW_POST;
+
+		while (ret == 0 && !state.quit && state.depth > 0) {
+			--state.depth;
+			ret = bftw_impl(&ids_args);
+		}
+	}
+
+	if (state.error) {
+		ret = -1;
+	} else {
+		state.error = errno;
+	}
+	trie_destroy(&pruned);
+	errno = state.error;
+	return ret;
+}
+
 int bftw(const struct bftw_args *args) {
 	switch (args->strategy) {
 	case BFTW_BFS:
 		return bftw_impl(args);
 	case BFTW_DFS:
 		return bftw_dfs(args);
+	case BFTW_IDS:
+		return bftw_ids(args);
 	}
 
 	errno = EINVAL;
diff --git a/bftw.h b/bftw.h
index f9d1aa0..570a79f 100644
--- a/bftw.h
+++ b/bftw.h
@@ -197,6 +197,8 @@ enum bftw_strategy {
 	BFTW_BFS,
 	/** Depth-first search. */
 	BFTW_DFS,
+	/** Iterative deepening search. */
+	BFTW_IDS,
 };
 
 /**
diff --git a/eval.c b/eval.c
index 6d13970..c075343 100644
--- a/eval.c
+++ b/eval.c
@@ -1228,7 +1228,7 @@ static enum bftw_action cmdline_callback(const struct BFTW *ftwbuf, void *ptr) {
 	// In -depth mode, only handle directories on the BFTW_POST visit
 	enum bftw_visit expected_visit = BFTW_PRE;
 	if ((cmdline->flags & BFTW_DEPTH)
-	    && ftwbuf->typeflag == BFTW_DIR
+	    && (cmdline->strategy == BFTW_IDS || ftwbuf->typeflag == BFTW_DIR)
 	    && ftwbuf->depth < cmdline->maxdepth) {
 		expected_visit = BFTW_POST;
 	}
@@ -1332,6 +1332,7 @@ static const char *dump_bftw_strategy(enum bftw_strategy strategy) {
 	static const char *strategies[] = {
 		DUMP_BFTW_MAP(BFTW_BFS),
 		DUMP_BFTW_MAP(BFTW_DFS),
+		DUMP_BFTW_MAP(BFTW_IDS),
 	};
 	return strategies[strategy];
 }
diff --git a/parse.c b/parse.c
index 7d98ffe..b8ef413 100644
--- a/parse.c
+++ b/parse.c
@@ -2150,7 +2150,7 @@ static struct expr *parse_samefile(struct parser_state *state, int arg1, int arg
 }
 
 /**
- * Parse -bfs, -dfs.
+ * Parse -bfs, -dfs, -ids.
  */
 static struct expr *parse_search_strategy(struct parser_state *state, int strategy, int arg2) {
 	struct cmdline *cmdline = state->cmdline;
@@ -2660,6 +2660,7 @@ static const struct table_entry parse_table[] = {
 	{"-group", false, parse_group},
 	{"-help", false, parse_help},
 	{"-hidden", false, parse_hidden},
+	{"-ids", false, parse_search_strategy, BFTW_IDS},
 	{"-ignore_readdir_race", false, parse_ignore_races, true},
 	{"-ilname", false, parse_lname, true},
 	{"-iname", false, parse_name, true},
@@ -3049,6 +3050,9 @@ void dump_cmdline(const struct cmdline *cmdline, bool verbose) {
 	case BFTW_DFS:
 		cfprintf(cerr, "${cyn}-dfs${rs} ");
 		break;
+	case BFTW_IDS:
+		cfprintf(cerr, "${cyn}-ids${rs} ");
+		break;
 	}
 
 	if (cmdline->flags & BFTW_LOGICAL) {