Implement a depth-first mode (-dfs)

6 files changed, 170 insertions, 14 deletions

diff --git a/Makefile b/Makefile
index 73ca0a1..e81b509 100644
--- a/Makefile
+++ b/Makefile
@@ -98,7 +98,8 @@ tests/mksock: tests/mksock.o
 	$(CC) $(ALL_CFLAGS) -c $< -o $@
 
 check: all
-	./tests.sh
+	./tests.sh --bfs="$(realpath bfs)"
+	./tests.sh --bfs="$(realpath bfs) -dfs"
 
 distcheck:
 	+$(MAKE) -Bs check CFLAGS="$(CFLAGS) -fsanitize=undefined -fsanitize=address"
diff --git a/bftw.c b/bftw.c
index 9016aba..89ba083 100644
--- a/bftw.c
+++ b/bftw.c
@@ -547,7 +547,7 @@ static void bftw_queue_init(struct bftw_queue *queue) {
 	queue->tail = NULL;
 }
 
-/** Add a directory to the bftw_queue. */
+/** Add a directory to the tail of the bftw_queue. */
 static void bftw_queue_push(struct bftw_queue *queue, struct bftw_dir *dir) {
 	assert(dir->next == NULL);
 
@@ -560,7 +560,22 @@ static void bftw_queue_push(struct bftw_queue *queue, struct bftw_dir *dir) {
 	queue->tail = dir;
 }
 
-/** Pop the next directory from the queue. */
+/** Prepend a queue to the head of another one. */
+static void bftw_queue_prepend(struct bftw_queue *head, struct bftw_queue *tail) {
+	if (head->tail) {
+		head->tail->next = tail->head;
+	}
+	if (head->head) {
+		tail->head = head->head;
+	}
+	if (!tail->tail) {
+		tail->tail = head->tail;
+	}
+	head->head = NULL;
+	head->tail = NULL;
+}
+
+/** Pop the next directory from the head of the queue. */
 static struct bftw_dir *bftw_queue_pop(struct bftw_queue *queue) {
 	struct bftw_dir *dir = queue->head;
 	queue->head = dir->next;
@@ -651,6 +666,8 @@ struct bftw_state {
 	void *ptr;
 	/** bftw() flags. */
 	enum bftw_flags flags;
+	/** Search strategy. */
+	enum bftw_strategy strategy;
 	/** The mount table. */
 	const struct bfs_mtab *mtab;
 
@@ -661,6 +678,8 @@ struct bftw_state {
 	struct bftw_cache cache;
 	/** The queue of directories left to explore. */
 	struct bftw_queue queue;
+	/** An intermediate queue used for depth-first searches. */
+	struct bftw_queue prequeue;
 
 	/** The current path. */
 	char *path;
@@ -678,6 +697,7 @@ static int bftw_state_init(struct bftw_state *state, const struct bftw_args *arg
 	state->callback = args->callback;
 	state->ptr = args->ptr;
 	state->flags = args->flags;
+	state->strategy = args->strategy;
 	state->mtab = args->mtab;
 
 	state->error = 0;
@@ -693,6 +713,7 @@ static int bftw_state_init(struct bftw_state *state, const struct bftw_args *arg
 	}
 
 	bftw_queue_init(&state->queue);
+	bftw_queue_init(&state->prequeue);
 
 	state->path = dstralloc(0);
 	if (!state->path) {
@@ -1079,7 +1100,11 @@ static int bftw_push(struct bftw_state *state, const char *name) {
 		dir->ino = statbuf->ino;
 	}
 
-	bftw_queue_push(&state->queue, dir);
+	if (state->strategy == BFTW_DFS) {
+		bftw_queue_push(&state->prequeue, dir);
+	} else {
+		bftw_queue_push(&state->queue, dir);
+	}
 	return 0;
 }
 
@@ -1087,6 +1112,14 @@ static int bftw_push(struct bftw_state *state, const char *name) {
  * Pop a directory from the queue and start reading it.
  */
 static struct bftw_reader *bftw_pop(struct bftw_state *state) {
+	if (state->strategy == BFTW_DFS) {
+		bftw_queue_prepend(&state->prequeue, &state->queue);
+	}
+
+	if (!state->queue.head) {
+		return NULL;
+	}
+
 	struct bftw_reader *reader = &state->reader;
 	struct bftw_dir *dir = state->queue.head;
 	if (bftw_dir_path(dir, &state->path) != 0) {
@@ -1160,6 +1193,16 @@ static enum bftw_action bftw_release_reader(struct bftw_state *state, bool do_vi
 }
 
 /**
+ * Drain all the entries from a bftw_queue.
+ */
+static void bftw_drain_queue(struct bftw_state *state, struct bftw_queue *queue) {
+	while (queue->head) {
+		struct bftw_dir *dir = bftw_queue_pop(queue);
+		bftw_release_dir(state, dir, false);
+	}
+}
+
+/**
  * Dispose of the bftw() state.
  *
  * @return
@@ -1169,11 +1212,8 @@ static int bftw_state_destroy(struct bftw_state *state) {
 	bftw_release_reader(state, false);
 	dstrfree(state->path);
 
-	struct bftw_queue *queue = &state->queue;
-	while (queue->head) {
-		struct bftw_dir *dir = bftw_queue_pop(queue);
-		bftw_release_dir(state, dir, false);
-	}
+	bftw_drain_queue(state, &state->prequeue);
+	bftw_drain_queue(state, &state->queue);
 
 	bftw_cache_destroy(&state->cache);
 
@@ -1181,7 +1221,10 @@ static int bftw_state_destroy(struct bftw_state *state) {
 	return state->error ? -1 : 0;
 }
 
-int bftw(const struct bftw_args *args) {
+/**
+ * bftw() implementation for breadth- and depth-first search.
+ */
+static int bftw_impl(const struct bftw_args *args) {
 	struct bftw_state state;
 	if (bftw_state_init(&state, args) != 0) {
 		return -1;
@@ -1207,7 +1250,7 @@ int bftw(const struct bftw_args *args) {
 	}
 
 start:
-	while (state.queue.head) {
+	while (true) {
 		struct bftw_reader *reader = bftw_pop(&state);
 		if (!reader) {
 			goto done;
@@ -1244,3 +1287,63 @@ start:
 done:
 	return bftw_state_destroy(&state);
 }
+
+/**
+ * Depth-first search state.
+ */
+struct bftw_dfs_state {
+	/** The wrapped callback. */
+	bftw_callback *delegate;
+	/** The wrapped callback arguments. */
+	void *ptr;
+	/** Whether to quit the search. */
+	bool quit;
+};
+
+/** Depth-first callback function. */
+static enum bftw_action bftw_dfs_callback(const struct BFTW *ftwbuf, void *ptr) {
+	struct bftw_dfs_state *state = ptr;
+	enum bftw_action ret = state->delegate(ftwbuf, state->ptr);
+	if (ret == BFTW_STOP || (ret == BFTW_SKIP_SIBLINGS && ftwbuf->depth == 0)) {
+		state->quit = true;
+	}
+	return ret;
+}
+
+/**
+ * Depth-first bftw() wrapper.
+ */
+static int bftw_dfs(const struct bftw_args *args) {
+	// bftw_impl() will process all the roots first, but we don't want that
+	// for depth-first searches
+
+	struct bftw_dfs_state state = {
+		.delegate = args->callback,
+		.ptr = args->ptr,
+		.quit = false,
+	};
+
+	struct bftw_args dfs_args = *args;
+	dfs_args.npaths = 1;
+	dfs_args.callback = bftw_dfs_callback;
+	dfs_args.ptr = &state;
+
+	int ret = 0;
+	for (size_t i = 0; i < args->npaths && ret == 0 && !state.quit; ++i) {
+		ret = bftw_impl(&dfs_args);
+		++dfs_args.paths;
+	}
+	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);
+	}
+
+	errno = EINVAL;
+	return -1;
+}
diff --git a/bftw.h b/bftw.h
index 6f5ad6d..f9d1aa0 100644
--- a/bftw.h
+++ b/bftw.h
@@ -190,6 +190,16 @@ enum bftw_flags {
 };
 
 /**
+ * Tree search strategies for bftw().
+ */
+enum bftw_strategy {
+	/** Breadth-first search. */
+	BFTW_BFS,
+	/** Depth-first search. */
+	BFTW_DFS,
+};
+
+/**
  * Structure for holding the arguments passed to bftw().
  */
 struct bftw_args {
@@ -205,6 +215,8 @@ struct bftw_args {
 	int nopenfd;
 	/** Flags that control bftw() behaviour. */
 	enum bftw_flags flags;
+	/** The search strategy to use. */
+	enum bftw_strategy strategy;
 	/** The parsed mount table, if available. */
 	const struct bfs_mtab *mtab;
 };
@@ -213,8 +225,7 @@ struct bftw_args {
  * Breadth First Tree Walk (or Better File Tree Walk).
  *
  * Like ftw(3) and nftw(3), this function walks a directory tree recursively,
- * and invokes a callback for each path it encounters.  However, bftw() operates
- * breadth-first.
+ * and invokes a callback for each path it encounters.
  *
  * @param args
  *         The arguments that control the walk.
diff --git a/cmdline.h b/cmdline.h
index e1811fd..29c8d25 100644
--- a/cmdline.h
+++ b/cmdline.h
@@ -77,6 +77,8 @@ struct cmdline {
 
 	/** bftw() flags. */
 	enum bftw_flags flags;
+	/** bftw() search strategy. */
+	enum bftw_strategy strategy;
 
 	/** Optimization level. */
 	int optlevel;
diff --git a/eval.c b/eval.c
index 5784219..6d13970 100644
--- a/eval.c
+++ b/eval.c
@@ -1326,6 +1326,17 @@ static void dump_bftw_flags(enum bftw_flags flags) {
 }
 
 /**
+ * Dump the bftw_strategy for -D search.
+ */
+static const char *dump_bftw_strategy(enum bftw_strategy strategy) {
+	static const char *strategies[] = {
+		DUMP_BFTW_MAP(BFTW_BFS),
+		DUMP_BFTW_MAP(BFTW_DFS),
+	};
+	return strategies[strategy];
+}
+
+/**
  * Evaluate the command line.
  */
 int eval_cmdline(const struct cmdline *cmdline) {
@@ -1352,6 +1363,7 @@ int eval_cmdline(const struct cmdline *cmdline) {
 		.ptr = &args,
 		.nopenfd = infer_fdlimit(cmdline),
 		.flags = cmdline->flags,
+		.strategy = cmdline->strategy,
 		.mtab = cmdline->mtab,
 	};
 
@@ -1368,7 +1380,8 @@ int eval_cmdline(const struct cmdline *cmdline) {
 		fprintf(stderr, "\t.nopenfd = %d,\n", bftw_args.nopenfd);
 		fprintf(stderr, "\t.flags = ");
 		dump_bftw_flags(bftw_args.flags);
-		fprintf(stderr, ",\n\t.mtab = ");
+		fprintf(stderr, ",\n\t.strategy = %s,\n", dump_bftw_strategy(bftw_args.strategy));
+		fprintf(stderr, "\t.mtab = ");
 		if (bftw_args.mtab) {
 			fprintf(stderr, "cmdline->mtab");
 		} else {
diff --git a/parse.c b/parse.c
index 7ca50ae..7d98ffe 100644
--- a/parse.c
+++ b/parse.c
@@ -2150,6 +2150,15 @@ static struct expr *parse_samefile(struct parser_state *state, int arg1, int arg
 }
 
 /**
+ * Parse -bfs, -dfs.
+ */
+static struct expr *parse_search_strategy(struct parser_state *state, int strategy, int arg2) {
+	struct cmdline *cmdline = state->cmdline;
+	cmdline->strategy = strategy;
+	return parse_nullary_flag(state);
+}
+
+/**
  * Parse -size N[cwbkMGTP]?.
  */
 static struct expr *parse_size(struct parser_state *state, int arg1, int arg2) {
@@ -2623,6 +2632,7 @@ static const struct table_entry parse_table[] = {
 	{"-and"},
 	{"-anewer", false, parse_newer, BFS_STAT_ATIME},
 	{"-atime", false, parse_time, BFS_STAT_ATIME, DAYS},
+	{"-bfs", false, parse_search_strategy, BFTW_BFS},
 	{"-capable", false, parse_capable},
 	{"-cmin", false, parse_time, BFS_STAT_CTIME, MINUTES},
 	{"-cnewer", false, parse_newer, BFS_STAT_CTIME},
@@ -2632,6 +2642,7 @@ static const struct table_entry parse_table[] = {
 	{"-daystart", false, parse_daystart},
 	{"-delete", false, parse_delete},
 	{"-depth", false, parse_depth_n},
+	{"-dfs", false, parse_search_strategy, BFTW_DFS},
 	{"-empty", false, parse_empty},
 	{"-exec", false, parse_exec, 0},
 	{"-execdir", false, parse_exec, BFS_EXEC_CHDIR},
@@ -3031,6 +3042,15 @@ void dump_cmdline(const struct cmdline *cmdline, bool verbose) {
 
 	cfprintf(cerr, "${ex}%s${rs} ", cmdline->argv[0]);
 
+	switch (cmdline->strategy) {
+	case BFTW_BFS:
+		cfprintf(cerr, "${cyn}-bfs${rs} ");
+		break;
+	case BFTW_DFS:
+		cfprintf(cerr, "${cyn}-dfs${rs} ");
+		break;
+	}
+
 	if (cmdline->flags & BFTW_LOGICAL) {
 		cfprintf(cerr, "${cyn}-L${rs} ");
 	} else if (cmdline->flags & BFTW_COMFOLLOW) {
@@ -3152,6 +3172,7 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 	cmdline->mindepth = 0;
 	cmdline->maxdepth = INT_MAX;
 	cmdline->flags = BFTW_RECOVER;
+	cmdline->strategy = BFTW_BFS;
 	cmdline->optlevel = 3;
 	cmdline->debug = 0;
 	cmdline->xargs_safe = false;
@@ -3215,6 +3236,11 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 		.prune_arg = NULL,
 	};
 
+	if (strcmp(xbasename(state.command), "find") == 0) {
+		// Operate depth-first when invoked as "find"
+		cmdline->strategy = BFTW_DFS;
+	}
+
 	if (parse_gettime(&state.now) != 0) {
 		goto fail;
 	}