[WIP] bftw: Push all files onto the queue before visiting themqueue-files

4 files changed, 131 insertions, 186 deletions

diff --git a/bftw.c b/bftw.c
index aee3689..ca0b06d 100644
--- a/bftw.c
+++ b/bftw.c
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2015-2018 Tavian Barnes <tavianator@tavianator.com>        *
+ * Copyright (C) 2015-2019 Tavian Barnes <tavianator@tavianator.com>        *
  *                                                                          *
  * Permission to use, copy, modify, and/or distribute this software for any *
  * purpose with or without fee is hereby granted.                           *
@@ -67,6 +67,8 @@ struct bftw_file {
 	/** An open descriptor to this file, or -1. */
 	int fd;
 
+	/** The type of the file. */
+	enum bftw_typeflag typeflag;
 	/** The device number, for cycle detection. */
 	dev_t dev;
 	/** The inode number, for cycle detection. */
@@ -315,6 +317,7 @@ static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_fil
 	file->refcount = 1;
 	file->fd = -1;
 
+	file->typeflag = BFTW_UNKNOWN;
 	file->dev = -1;
 	file->ino = -1;
 
@@ -531,7 +534,7 @@ struct bftw_reader {
 	/** The file object. */
 	struct bftw_file *file;
 	/** The path to the directory. */
-	char *path;
+	const char *path;
 	/** The open handle to the directory. */
 	DIR *handle;
 	/** The current directory entry. */
@@ -541,17 +544,12 @@ struct bftw_reader {
 };
 
 /** Initialize a reader. */
-static int bftw_reader_init(struct bftw_reader *reader) {
-	reader->path = dstralloc(0);
-	if (!reader->path) {
-		return -1;
-	}
-
+static void bftw_reader_init(struct bftw_reader *reader) {
 	reader->file = NULL;
+	reader->path = NULL;
 	reader->handle = NULL;
 	reader->de = NULL;
 	reader->error = 0;
-	return 0;
 }
 
 /** Read a directory entry. */
@@ -565,20 +563,15 @@ static int bftw_reader_read(struct bftw_reader *reader) {
 }
 
 /** Open a directory for reading. */
-static int bftw_reader_open(struct bftw_reader *reader, struct bftw_cache *cache, struct bftw_file *file) {
+static int bftw_reader_open(struct bftw_reader *reader, struct bftw_cache *cache, struct bftw_file *file, const char *path) {
 	assert(!reader->handle);
 	assert(!reader->de);
 
 	reader->file = file;
+	reader->path = path;
 	reader->error = 0;
 
-	if (bftw_file_path(file, &reader->path) != 0) {
-		reader->error = errno;
-		dstresize(&reader->path, 0);
-		return -1;
-	}
-
-	reader->handle = bftw_file_opendir(cache, file, reader->path);
+	reader->handle = bftw_file_opendir(cache, file, path);
 	if (!reader->handle) {
 		reader->error = errno;
 		return -1;
@@ -608,8 +601,6 @@ static void bftw_reader_destroy(struct bftw_reader *reader) {
 	if (reader->handle) {
 		bftw_reader_close(reader);
 	}
-
-	dstrfree(reader->path);
 }
 
 /**
@@ -749,16 +740,6 @@ static enum bftw_typeflag bftw_dirent_typeflag(const struct dirent *de) {
 	return BFTW_UNKNOWN;
 }
 
-/** Call stat() and use the results. */
-static int bftw_stat(struct BFTW *ftwbuf, struct bfs_stat *sb) {
-	int ret = bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->at_flags, BFS_STAT_BROKEN_OK, sb);
-	if (ret == 0) {
-		ftwbuf->statbuf = sb;
-		ftwbuf->typeflag = bftw_mode_typeflag(sb->mode);
-	}
-	return ret;
-}
-
 /**
  * Holds the current state of the bftw() traversal.
  */
@@ -780,6 +761,10 @@ struct bftw_state {
 	/** The queue of files left to explore. */
 	struct bftw_queue queue;
 
+	/** The current file. */
+	struct bftw_file *file;
+	/** The current path. */
+	char *path;
 	/** The reader for the current directory. */
 	struct bftw_reader reader;
 	/** Whether the current visit is pre- or post-order. */
@@ -818,10 +803,15 @@ static int bftw_state_init(struct bftw_state *state, const char *root, const str
 
 	bftw_queue_init(&state->queue);
 
-	if (bftw_reader_init(&state->reader) != 0) {
+	state->file = NULL;
+
+	state->path = dstralloc(0);
+	if (!state->path) {
 		goto err_cache;
 	}
 
+	bftw_reader_init(&state->reader);
+
 	state->visit = BFTW_PRE;
 
 	return 0;
@@ -832,36 +822,6 @@ err:
 	return -1;
 }
 
-/**
- * Update the path for the current file.
- */
-static int bftw_update_path(struct bftw_state *state) {
-	struct bftw_reader *reader = &state->reader;
-	struct bftw_file *file = reader->file;
-	struct dirent *de = reader->de;
-
-	size_t length = file->nameoff + file->namelen;
-
-	if (dstrlen(reader->path) < length) {
-		errno = reader->error;
-		return -1;
-	}
-	dstresize(&reader->path, length);
-
-	if (de) {
-		if (reader->path[length - 1] != '/') {
-			if (dstrapp(&reader->path, '/') != 0) {
-				return -1;
-			}
-		}
-		if (dstrcat(&reader->path, reader->de->d_name) != 0) {
-			return -1;
-		}
-	}
-
-	return 0;
-}
-
 /** Check if a stat() call is needed for this visit. */
 static bool bftw_need_stat(struct bftw_state *state) {
 	if (state->flags & BFTW_STAT) {
@@ -897,54 +857,57 @@ static bool bftw_need_stat(struct bftw_state *state) {
 	return false;
 }
 
+/** Call stat() and use the results. */
+static int bftw_stat(struct bftw_state *state) {
+	struct BFTW *ftwbuf = &state->ftwbuf;
+	struct bfs_stat *statbuf = &state->statbuf;
+	struct bftw_file *file = state->file;
+
+	int ret = bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->at_flags, BFS_STAT_BROKEN_OK, statbuf);
+	if (ret == 0) {
+		ftwbuf->statbuf = statbuf;
+		ftwbuf->typeflag = bftw_mode_typeflag(statbuf->mode);
+		file->typeflag = ftwbuf->typeflag;
+		file->dev = statbuf->dev;
+		file->ino = statbuf->ino;
+	} else {
+		ftwbuf->typeflag = BFTW_ERROR;
+		ftwbuf->error = errno;
+	}
+	return ret;
+}
+
 /**
  * Initialize the buffers with data about the current path.
  */
 static void bftw_prepare_visit(struct bftw_state *state) {
+	struct bftw_file *file = state->file;
 	struct bftw_reader *reader = &state->reader;
-	struct bftw_file *file = reader->file;
-	struct dirent *de = reader->de;
 
 	struct BFTW *ftwbuf = &state->ftwbuf;
-	ftwbuf->path = file ? reader->path : state->root;
+	ftwbuf->path = state->path;
 	ftwbuf->root = state->root;
-	ftwbuf->depth = 0;
+	ftwbuf->depth = file->depth;
 	ftwbuf->visit = state->visit;
+	ftwbuf->typeflag = file->typeflag;
 	ftwbuf->error = reader->error;
 	ftwbuf->statbuf = NULL;
 	ftwbuf->at_fd = AT_FDCWD;
 	ftwbuf->at_path = ftwbuf->path;
 	ftwbuf->at_flags = AT_SYMLINK_NOFOLLOW;
 
-	if (file) {
-		ftwbuf->depth = file->depth;
-
-		if (de) {
-			ftwbuf->nameoff = bftw_child_nameoff(file);
-			++ftwbuf->depth;
-
-			ftwbuf->at_fd = file->fd;
-			ftwbuf->at_path += ftwbuf->nameoff;
-		} else {
-			ftwbuf->nameoff = file->nameoff;
-			bftw_file_base(file, &ftwbuf->at_fd, &ftwbuf->at_path);
-		}
-	}
-
 	if (ftwbuf->depth == 0) {
 		// Compute the name offset for root paths like "foo/bar"
 		ftwbuf->nameoff = xbasename(ftwbuf->path) - ftwbuf->path;
+	} else {
+		ftwbuf->nameoff = file->nameoff;
 	}
 
+	bftw_file_base(file, &ftwbuf->at_fd, &ftwbuf->at_path);
+
 	if (ftwbuf->error != 0) {
 		ftwbuf->typeflag = BFTW_ERROR;
 		return;
-	} else if (de) {
-		ftwbuf->typeflag = bftw_dirent_typeflag(de);
-	} else if (ftwbuf->depth > 0) {
-		ftwbuf->typeflag = BFTW_DIR;
-	} else {
-		ftwbuf->typeflag = BFTW_UNKNOWN;
 	}
 
 	int follow_flags = BFTW_LOGICAL;
@@ -957,9 +920,7 @@ static void bftw_prepare_visit(struct bftw_state *state) {
 	}
 
 	if (bftw_need_stat(state)) {
-		if (bftw_stat(ftwbuf, &state->statbuf) != 0) {
-			ftwbuf->typeflag = BFTW_ERROR;
-			ftwbuf->error = errno;
+		if (bftw_stat(state) != 0) {
 			return;
 		}
 	}
@@ -982,29 +943,24 @@ static void bftw_prepare_visit(struct bftw_state *state) {
 /**
  * Invoke the callback.
  */
-static enum bftw_action bftw_visit_path(struct bftw_state *state) {
-	if (state->reader.file) {
-		if (bftw_update_path(state) != 0) {
-			state->error = errno;
-			return BFTW_STOP;
-		}
-	}
+static enum bftw_action bftw_visit(struct bftw_state *state) {
+	const struct bftw_file *file = state->file;
+	size_t pathlen = file->nameoff + file->namelen;
+	dstresize(&state->path, pathlen);
 
 	bftw_prepare_visit(state);
 
-	// Never give the callback BFTW_ERROR unless BFTW_RECOVER is specified
-	if (state->ftwbuf.typeflag == BFTW_ERROR && !(state->flags & BFTW_RECOVER)) {
+	if (file->typeflag == BFTW_ERROR && !(state->flags & BFTW_RECOVER)) {
+		// Never give the callback BFTW_ERROR unless BFTW_RECOVER is specified
 		state->error = state->ftwbuf.error;
 		return BFTW_STOP;
 	}
 
-	// Defensive copy
-	struct BFTW ftwbuf = state->ftwbuf;
-
-	enum bftw_action action = state->callback(&ftwbuf, state->ptr);
+	enum bftw_action action = state->callback(&state->ftwbuf, state->ptr);
 	switch (action) {
 	case BFTW_CONTINUE:
-	case BFTW_SKIP_SIBLINGS:
+		break;
+
 	case BFTW_SKIP_SUBTREE:
 	case BFTW_STOP:
 		return action;
@@ -1013,23 +969,31 @@ static enum bftw_action bftw_visit_path(struct bftw_state *state) {
 		state->error = EINVAL;
 		return BFTW_STOP;
 	}
+
+	if (file->typeflag != BFTW_DIR) {
+		return BFTW_SKIP_SUBTREE;
+	}
+
+	if ((state->flags & BFTW_XDEV) && file->parent && file->dev != file->parent->dev) {
+		return BFTW_SKIP_SUBTREE;
+	}
+
+	return BFTW_CONTINUE;
 }
 
 /**
  * Push a new directory onto the queue.
  */
-static int bftw_push(struct bftw_state *state, const char *name) {
-	struct bftw_file *parent = state->reader.file;
+static int bftw_push(struct bftw_state *state, const char *name, struct dirent *de) {
+	struct bftw_file *parent = state->file;
 	struct bftw_file *file = bftw_file_new(&state->cache, parent, name);
 	if (!file) {
 		state->error = errno;
 		return -1;
 	}
 
-	const struct bfs_stat *statbuf = state->ftwbuf.statbuf;
-	if (statbuf) {
-		file->dev = statbuf->dev;
-		file->ino = statbuf->ino;
+	if (de) {
+		file->typeflag = bftw_dirent_typeflag(de);
 	}
 
 	bftw_queue_push(&state->queue, file);
@@ -1037,46 +1001,54 @@ static int bftw_push(struct bftw_state *state, const char *name) {
 }
 
 /**
- * Pop a directory from the queue and start reading it.
+ * Pop a file from the queue.
  */
-static struct bftw_reader *bftw_pop(struct bftw_state *state) {
-	struct bftw_reader *reader = &state->reader;
-	struct bftw_file *file = bftw_queue_pop(&state->queue);
-	bftw_reader_open(reader, &state->cache, file);
-	return reader;
+static struct bftw_file *bftw_pop(struct bftw_state *state) {
+	state->file = bftw_queue_pop(&state->queue);
+
+	if (bftw_file_path(state->file, &state->path) == 0) {
+		return state->file;
+	} else {
+		dstresize(&state->path, 0);
+		return NULL;
+	}
+}
+
+/**
+ * Open the current directory.
+ */
+static struct bftw_reader *bftw_open(struct bftw_state *state) {
+	bftw_reader_open(&state->reader, &state->cache, state->file, state->path);
+	return &state->reader;
 }
 
 /**
  * Finalize and free a file we're done with.
  */
-static enum bftw_action bftw_release_file(struct bftw_state *state, struct bftw_file *file, bool do_visit) {
+static enum bftw_action bftw_release_file(struct bftw_state *state, bool do_visit) {
 	enum bftw_action ret = BFTW_CONTINUE;
 
-	if (!(state->flags & BFTW_DEPTH)) {
-		do_visit = false;
-	}
-
 	state->visit = BFTW_POST;
 
-	while (file) {
-		bftw_file_decref(&state->cache, file);
-		if (file->refcount > 0) {
+	while (state->file) {
+		bftw_file_decref(&state->cache, state->file);
+		if (state->file->refcount > 0) {
 			break;
 		}
 
 		if (do_visit) {
-			state->reader.file = file;
-			if (bftw_visit_path(state) == BFTW_STOP) {
+			if (bftw_visit(state) == BFTW_STOP) {
 				ret = BFTW_STOP;
 				do_visit = false;
 			}
 		}
 
-		struct bftw_file *parent = file->parent;
-		bftw_file_free(&state->cache, file);
-		file = parent;
+		struct bftw_file *parent = state->file->parent;
+		bftw_file_free(&state->cache, state->file);
+		state->file = parent;
 	}
 
+	state->file = NULL;
 	state->visit = BFTW_PRE;
 	return ret;
 }
@@ -1094,20 +1066,13 @@ static enum bftw_action bftw_release_reader(struct bftw_state *state, bool do_vi
 
 	if (reader->error != 0) {
 		if (do_visit) {
-			if (bftw_visit_path(state) == BFTW_STOP) {
-				ret = BFTW_STOP;
-				do_visit = false;
-			}
+			ret = bftw_visit(state);
 		} else {
 			state->error = reader->error;
 		}
 		reader->error = 0;
 	}
 
-	if (bftw_release_file(state, reader->file, do_visit) == BFTW_STOP) {
-		ret = BFTW_STOP;
-	}
-
 	reader->file = NULL;
 
 	return ret;
@@ -1126,10 +1091,16 @@ static int bftw_state_destroy(struct bftw_state *state) {
 	}
 	bftw_reader_destroy(reader);
 
+	if (state->file) {
+		bftw_release_file(state, false);
+	}
+
+	dstrfree(state->path);
+
 	struct bftw_queue *queue = &state->queue;
 	while (queue->head) {
-		struct bftw_file *file = bftw_queue_pop(queue);
-		bftw_release_file(state, file, false);
+		state->file = bftw_queue_pop(queue);
+		bftw_release_file(state, false);
 	}
 
 	bftw_cache_destroy(&state->cache);
@@ -1148,69 +1119,48 @@ int bftw(const char *path, const struct bftw_args *args) {
 		return -1;
 	}
 
-	// Handle 'path' itself first
-	switch (bftw_visit_path(&state)) {
-	case BFTW_SKIP_SUBTREE:
-	case BFTW_STOP:
-		goto done;
-	default:
-		break;
-	}
-
-	if (state.ftwbuf.typeflag != BFTW_DIR) {
-		goto done;
-	}
-
-	// Now start the breadth-first search
-
-	if (bftw_push(&state, path) != 0) {
+	if (bftw_push(&state, path, NULL) != 0) {
 		goto done;
 	}
 
 	while (state.queue.head) {
-		struct bftw_reader *reader = bftw_pop(&state);
+		struct bftw_file *file = bftw_pop(&state);
+		if (!file) {
+			goto done;
+		}
 
+		switch (bftw_visit(&state)) {
+		case BFTW_CONTINUE:
+			break;
+		case BFTW_SKIP_SUBTREE:
+			goto next;
+		case BFTW_STOP:
+			goto done;
+		}
+
+		struct bftw_reader *reader = bftw_open(&state);
 		while (reader->de) {
 			const char *name = reader->de->d_name;
 			if (name[0] == '.' && (name[1] == '\0' || (name[1] == '.' && name[2] == '\0'))) {
 				goto read;
 			}
 
-			switch (bftw_visit_path(&state)) {
-			case BFTW_CONTINUE:
-				break;
-
-			case BFTW_SKIP_SIBLINGS:
-				goto next;
-
-			case BFTW_SKIP_SUBTREE:
-				goto read;
-
-			case BFTW_STOP:
+			if (bftw_push(&state, name, reader->de) != 0) {
 				goto done;
 			}
 
-			if (state.ftwbuf.typeflag == BFTW_DIR) {
-				const struct bfs_stat *statbuf = state.ftwbuf.statbuf;
-				if ((args->flags & BFTW_XDEV)
-				    && statbuf
-				    && statbuf->dev != reader->file->dev) {
-					goto read;
-				}
-
-				if (bftw_push(&state, name) != 0) {
-					goto done;
-				}
-			}
-
 		read:
 			bftw_reader_read(reader);
 		}
 
-	next:
 		if (bftw_release_reader(&state, true) == BFTW_STOP) {
 			break;
 		}
+
+	next:
+		if (bftw_release_file(&state, true) == BFTW_STOP) {
+			break;
+		}
 	}
 
 done:
diff --git a/bftw.h b/bftw.h
index e822523..eaeb92e 100644
--- a/bftw.h
+++ b/bftw.h
@@ -108,8 +108,6 @@ struct BFTW {
 enum bftw_action {
 	/** Keep walking. */
 	BFTW_CONTINUE,
-	/** Skip this path's siblings. */
-	BFTW_SKIP_SIBLINGS,
 	/** Skip this path's children. */
 	BFTW_SKIP_SUBTREE,
 	/** Stop walking. */
diff --git a/eval.c b/eval.c
index 341b289..3b054fa 100644
--- a/eval.c
+++ b/eval.c
@@ -1206,7 +1206,6 @@ static const char *dump_bftw_visit(enum bftw_visit visit) {
 static const char *dump_bftw_action(enum bftw_action action) {
 	static const char *actions[] = {
 		DUMP_BFTW_MAP(BFTW_CONTINUE),
-		DUMP_BFTW_MAP(BFTW_SKIP_SIBLINGS),
 		DUMP_BFTW_MAP(BFTW_SKIP_SUBTREE),
 		DUMP_BFTW_MAP(BFTW_STOP),
 	};
@@ -1273,11 +1272,8 @@ static enum bftw_action cmdline_callback(struct BFTW *ftwbuf, void *ptr) {
 		state.action = BFTW_SKIP_SUBTREE;
 	}
 
-	// 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
-	    && ftwbuf->depth < cmdline->maxdepth) {
+	if ((cmdline->flags & BFTW_DEPTH) && ftwbuf->depth < cmdline->maxdepth) {
 		expected_visit = BFTW_POST;
 	}
 
diff --git a/exec.c b/exec.c
index 3a35063..06703ad 100644
--- a/exec.c
+++ b/exec.c
@@ -265,6 +265,7 @@ static int bfs_exec_openwd(struct bfs_exec *execbuf, const struct BFTW *ftwbuf)
 	assert(execbuf->wd_fd < 0);
 	assert(!execbuf->wd_path);
 
+	assert(ftwbuf->depth == 0 || ftwbuf->at_path == xbasename(ftwbuf->path));
 	if (ftwbuf->at_fd != AT_FDCWD) {
 		execbuf->wd_fd = ftwbuf->at_fd;
 		if (!(execbuf->flags & BFS_EXEC_MULTI)) {