Merge everything into one filesingle-file

1 files changed, 0 insertions, 1551 deletions

diff --git a/bftw.c b/bftw.c
deleted file mode 100644
index 510f7f3..0000000
--- a/bftw.c
+++ /dev/null
@@ -1,1551 +0,0 @@
-/****************************************************************************
- * bfs                                                                      *
- * 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.                           *
- *                                                                          *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
- ****************************************************************************/
-
-/**
- * The bftw() implementation consists of the following components:
- *
- * - struct bftw_file: A file that has been encountered during the traversal.
- *   They have reference-counted links to their parents in the directory tree.
- *
- * - struct bftw_cache: Holds bftw_file's with open file descriptors, used for
- *   openat() to minimize the amount of path re-traversals that need to happen.
- *   Currently implemented as a priority queue based on depth and reference
- *   count.
- *
- * - struct bftw_queue: The queue of bftw_file's left to explore.  Implemented
- *   as a simple circular buffer.
- *
- * - struct bftw_reader: A reader object that simplifies reading directories and
- *   reporting errors.
- *
- * - struct bftw_state: Represents the current state of the traversal, allowing
- *   various helper functions to take fewer parameters.
- */
-
-#include "bftw.h"
-#include "dstring.h"
-#include "stat.h"
-#include "trie.h"
-#include "util.h"
-#include <assert.h>
-#include <dirent.h>
-#include <errno.h>
-#include <fcntl.h>
-#include <limits.h>
-#include <stdbool.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-
-/**
- * A file.
- */
-struct bftw_file {
-	/** The parent directory, if any. */
-	struct bftw_file *parent;
-	/** This file's depth in the walk. */
-	size_t depth;
-	/** The root path this file was found from. */
-	const char *root;
-
-	/** The next file in the queue, if any. */
-	struct bftw_file *next;
-
-	/** Reference count. */
-	size_t refcount;
-	/** Index in the bftw_cache priority queue. */
-	size_t heap_index;
-
-	/** An open descriptor to this file, or -1. */
-	int fd;
-
-	/** This file's type, if known. */
-	enum bftw_typeflag typeflag;
-	/** The device number, for cycle detection. */
-	dev_t dev;
-	/** The inode number, for cycle detection. */
-	ino_t ino;
-
-	/** The offset of this file in the full path. */
-	size_t nameoff;
-	/** The length of the file's name. */
-	size_t namelen;
-	/** The file's name. */
-	char name[];
-};
-
-/**
- * A cache of open directories.
- */
-struct bftw_cache {
-	/** A min-heap of open directories. */
-	struct bftw_file **heap;
-	/** Current heap size. */
-	size_t size;
-	/** Maximum heap size. */
-	size_t capacity;
-};
-
-/** Initialize a cache. */
-static int bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
-	cache->heap = malloc(capacity*sizeof(*cache->heap));
-	if (!cache->heap) {
-		return -1;
-	}
-
-	cache->size = 0;
-	cache->capacity = capacity;
-	return 0;
-}
-
-/** Destroy a cache. */
-static void bftw_cache_destroy(struct bftw_cache *cache) {
-	assert(cache->size == 0);
-	free(cache->heap);
-}
-
-/** Check if two heap entries are in heap order. */
-static bool bftw_heap_check(const struct bftw_file *parent, const struct bftw_file *child) {
-	if (parent->depth > child->depth) {
-		return true;
-	} else if (parent->depth < child->depth) {
-		return false;
-	} else {
-		return parent->refcount <= child->refcount;
-	}
-}
-
-/** Move a bftw_file to a particular place in the heap. */
-static void bftw_heap_move(struct bftw_cache *cache, struct bftw_file *file, size_t i) {
-	cache->heap[i] = file;
-	file->heap_index = i;
-}
-
-/** Bubble an entry up the heap. */
-static void bftw_heap_bubble_up(struct bftw_cache *cache, struct bftw_file *file) {
-	size_t i = file->heap_index;
-
-	while (i > 0) {
-		size_t pi = (i - 1)/2;
-		struct bftw_file *parent = cache->heap[pi];
-		if (bftw_heap_check(parent, file)) {
-			break;
-		}
-
-		bftw_heap_move(cache, parent, i);
-		i = pi;
-	}
-
-	bftw_heap_move(cache, file, i);
-}
-
-/** Bubble an entry down the heap. */
-static void bftw_heap_bubble_down(struct bftw_cache *cache, struct bftw_file *file) {
-	size_t i = file->heap_index;
-
-	while (true) {
-		size_t ci = 2*i + 1;
-		if (ci >= cache->size) {
-			break;
-		}
-
-		struct bftw_file *child = cache->heap[ci];
-
-		size_t ri = ci + 1;
-		if (ri < cache->size) {
-			struct bftw_file *right = cache->heap[ri];
-			if (!bftw_heap_check(child, right)) {
-				ci = ri;
-				child = right;
-			}
-		}
-
-		if (bftw_heap_check(file, child)) {
-			break;
-		}
-
-		bftw_heap_move(cache, child, i);
-		i = ci;
-	}
-
-	bftw_heap_move(cache, file, i);
-}
-
-/** Bubble an entry up or down the heap. */
-static void bftw_heap_bubble(struct bftw_cache *cache, struct bftw_file *file) {
-	size_t i = file->heap_index;
-
-	if (i > 0) {
-		size_t pi = (i - 1)/2;
-		struct bftw_file *parent = cache->heap[pi];
-		if (!bftw_heap_check(parent, file)) {
-			bftw_heap_bubble_up(cache, file);
-			return;
-		}
-	}
-
-	bftw_heap_bubble_down(cache, file);
-}
-
-/** Increment a bftw_file's reference count. */
-static size_t bftw_file_incref(struct bftw_cache *cache, struct bftw_file *file) {
-	size_t ret = ++file->refcount;
-	if (file->fd >= 0) {
-		bftw_heap_bubble_down(cache, file);
-	}
-	return ret;
-}
-
-/** Decrement a bftw_file's reference count. */
-static size_t bftw_file_decref(struct bftw_cache *cache, struct bftw_file *file) {
-	size_t ret = --file->refcount;
-	if (file->fd >= 0) {
-		bftw_heap_bubble_up(cache, file);
-	}
-	return ret;
-}
-
-/** Add a bftw_file to the cache. */
-static void bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
-	assert(cache->size < cache->capacity);
-	assert(file->fd >= 0);
-
-	size_t size = cache->size++;
-	file->heap_index = size;
-	bftw_heap_bubble_up(cache, file);
-}
-
-/** Remove a bftw_file from the cache. */
-static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
-	assert(cache->size > 0);
-	assert(file->fd >= 0);
-
-	size_t size = --cache->size;
-	size_t i = file->heap_index;
-	if (i != size) {
-		struct bftw_file *end = cache->heap[size];
-		end->heap_index = i;
-		bftw_heap_bubble(cache, end);
-	}
-}
-
-/** Close a bftw_file. */
-static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
-	assert(file->fd >= 0);
-
-	bftw_cache_remove(cache, file);
-
-	close(file->fd);
-	file->fd = -1;
-}
-
-/** Pop a directory from the cache. */
-static void bftw_cache_pop(struct bftw_cache *cache) {
-	assert(cache->size > 0);
-	bftw_file_close(cache, cache->heap[0]);
-}
-
-/**
- * Shrink the cache, to recover from EMFILE.
- *
- * @param cache
- *         The cache in question.
- * @param saved
- *         A bftw_file that must be preserved.
- * @return
- *         0 if successfully shrunk, otherwise -1.
- */
-static int bftw_cache_shrink(struct bftw_cache *cache, const struct bftw_file *saved) {
-	int ret = -1;
-	struct bftw_file *file = NULL;
-
-	if (cache->size >= 1) {
-		file = cache->heap[0];
-		if (file == saved && cache->size >= 2) {
-			file = cache->heap[1];
-		}
-	}
-
-	if (file && file != saved) {
-		bftw_file_close(cache, file);
-		ret = 0;
-	}
-
-	cache->capacity = cache->size;
-	return ret;
-}
-
-/** Compute the name offset of a child path. */
-static size_t bftw_child_nameoff(const struct bftw_file *parent) {
-	size_t ret = parent->nameoff + parent->namelen;
-	if (parent->name[parent->namelen - 1] != '/') {
-		++ret;
-	}
-	return ret;
-}
-
-/** Create a new bftw_file. */
-static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_file *parent, const char *name) {
-	size_t namelen = strlen(name);
-	size_t size = sizeof(struct bftw_file) + namelen + 1;
-
-	struct bftw_file *file = malloc(size);
-	if (!file) {
-		return NULL;
-	}
-
-	file->parent = parent;
-
-	if (parent) {
-		file->depth = parent->depth + 1;
-		file->root = parent->root;
-		file->nameoff = bftw_child_nameoff(parent);
-		bftw_file_incref(cache, parent);
-	} else {
-		file->depth = 0;
-		file->root = name;
-		file->nameoff = 0;
-	}
-
-	file->next = NULL;
-
-	file->refcount = 1;
-	file->fd = -1;
-
-	file->typeflag = BFTW_UNKNOWN;
-	file->dev = -1;
-	file->ino = -1;
-
-	file->namelen = namelen;
-	memcpy(file->name, name, namelen + 1);
-
-	return file;
-}
-
-/**
- * Get the appropriate (fd, path) pair for the *at() family of functions.
- *
- * @param file
- *         The file being accessed.
- * @param[out] at_fd
- *         Will hold the appropriate file descriptor to use.
- * @param[in,out] at_path
- *         Will hold the appropriate path to use.
- * @return The closest open ancestor file.
- */
-static struct bftw_file *bftw_file_base(struct bftw_file *file, int *at_fd, const char **at_path) {
-	struct bftw_file *base = file;
-
-	do {
-		base = base->parent;
-	} while (base && base->fd < 0);
-
-	if (base) {
-		*at_fd = base->fd;
-		*at_path += bftw_child_nameoff(base);
-	}
-
-	return base;
-}
-
-/**
- * Open a bftw_file relative to another one.
- *
- * @param cache
- *         The cache to hold the file.
- * @param file
- *         The file to open.
- * @param base
- *         The base directory for the relative path (may be NULL).
- * @param at_fd
- *         The base file descriptor, AT_FDCWD if base == NULL.
- * @param at_path
- *         The relative path to the file.
- * @return
- *         The opened file descriptor, or negative on error.
- */
-static int bftw_file_openat(struct bftw_cache *cache, struct bftw_file *file, const struct bftw_file *base, int at_fd, const char *at_path) {
-	assert(file->fd < 0);
-
-	int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY;
-	int fd = openat(at_fd, at_path, flags);
-
-	if (fd < 0 && errno == EMFILE) {
-		if (bftw_cache_shrink(cache, base) == 0) {
-			fd = openat(base->fd, at_path, flags);
-		}
-	}
-
-	if (fd >= 0) {
-		if (cache->size == cache->capacity) {
-			bftw_cache_pop(cache);
-		}
-
-		file->fd = fd;
-		bftw_cache_add(cache, file);
-	}
-
-	return fd;
-}
-
-/**
- * Open a bftw_file.
- *
- * @param cache
- *         The cache to hold the file.
- * @param file
- *         The file to open.
- * @param path
- *         The full path to the file.
- * @return
- *         The opened file descriptor, or negative on error.
- */
-static int bftw_file_open(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
-	int at_fd = AT_FDCWD;
-	const char *at_path = path;
-	struct bftw_file *base = bftw_file_base(file, &at_fd, &at_path);
-
-	int fd = bftw_file_openat(cache, file, base, at_fd, at_path);
-	if (fd >= 0 || errno != ENAMETOOLONG) {
-		return fd;
-	}
-
-	// Handle ENAMETOOLONG by manually traversing the path component-by-component
-
-	// -1 to include the root, which has depth == 0
-	size_t offset = base ? base->depth : -1;
-	size_t levels = file->depth - offset;
-	if (levels < 2) {
-		return fd;
-	}
-
-	struct bftw_file **parents = malloc(levels * sizeof(*parents));
-	if (!parents) {
-		return fd;
-	}
-
-	struct bftw_file *parent = file;
-	for (size_t i = levels; i-- > 0;) {
-		parents[i] = parent;
-		parent = parent->parent;
-	}
-
-	for (size_t i = 0; i < levels; ++i) {
-		fd = bftw_file_openat(cache, parents[i], base, at_fd, parents[i]->name);
-		if (fd < 0) {
-			break;
-		}
-
-		base = parents[i];
-		at_fd = fd;
-	}
-
-	free(parents);
-	return fd;
-}
-
-/**
- * Open a DIR* for a bftw_file.
- *
- * @param cache
- *         The cache to hold the file.
- * @param file
- *         The directory to open.
- * @param path
- *         The full path to the directory.
- * @return
- *         The opened DIR *, or NULL on error.
- */
-static DIR *bftw_file_opendir(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
-	int fd = bftw_file_open(cache, file, path);
-	if (fd < 0) {
-		return NULL;
-	}
-
-	// Now we dup() the fd and pass it to fdopendir().  This way we can
-	// close the DIR* as soon as we're done with it, reducing the memory
-	// footprint significantly, while keeping the fd around for future
-	// openat() calls.
-
-	int dfd = dup_cloexec(fd);
-
-	if (dfd < 0 && errno == EMFILE) {
-		if (bftw_cache_shrink(cache, file) == 0) {
-			dfd = dup_cloexec(fd);
-		}
-	}
-
-	if (dfd < 0) {
-		return NULL;
-	}
-
-	DIR *ret = fdopendir(dfd);
-	if (!ret) {
-		int error = errno;
-		close(dfd);
-		errno = error;
-	}
-
-	return ret;
-}
-
-/** Free a bftw_file. */
-static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) {
-	assert(file->refcount == 0);
-
-	if (file->fd >= 0) {
-		bftw_file_close(cache, file);
-	}
-
-	free(file);
-}
-
-/**
- * A queue of bftw_file's to examine.
- */
-struct bftw_queue {
-	/** The head of the queue. */
-	struct bftw_file *head;
-	/** The tail of the queue. */
-	struct bftw_file *tail;
-};
-
-/** Initialize a bftw_queue. */
-static void bftw_queue_init(struct bftw_queue *queue) {
-	queue->head = NULL;
-	queue->tail = NULL;
-}
-
-/** Add a file to the tail of the bftw_queue. */
-static void bftw_queue_push(struct bftw_queue *queue, struct bftw_file *file) {
-	assert(file->next == NULL);
-
-	if (!queue->head) {
-		queue->head = file;
-	}
-	if (queue->tail) {
-		queue->tail->next = file;
-	}
-	queue->tail = file;
-}
-
-/** 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 file from the head of the queue. */
-static struct bftw_file *bftw_queue_pop(struct bftw_queue *queue) {
-	struct bftw_file *file = queue->head;
-	queue->head = file->next;
-	if (queue->tail == file) {
-		queue->tail = NULL;
-	}
-	file->next = NULL;
-	return file;
-}
-
-/**
- * A directory reader.
- */
-struct bftw_reader {
-	/** The open handle to the directory. */
-	DIR *dir;
-	/** The current directory entry. */
-	struct dirent *de;
-	/** Any error code that has occurred. */
-	int error;
-};
-
-/** Initialize a reader. */
-static void bftw_reader_init(struct bftw_reader *reader) {
-	reader->dir = NULL;
-	reader->de = NULL;
-	reader->error = 0;
-}
-
-/** Open a directory for reading. */
-static int bftw_reader_open(struct bftw_reader *reader, struct bftw_cache *cache, struct bftw_file *file, const char *path) {
-	assert(!reader->dir);
-	assert(!reader->de);
-
-	reader->error = 0;
-
-	reader->dir = bftw_file_opendir(cache, file, path);
-	if (!reader->dir) {
-		reader->error = errno;
-		return -1;
-	}
-
-	return 0;
-}
-
-/** Read a directory entry. */
-static int bftw_reader_read(struct bftw_reader *reader) {
-	if (!reader->dir) {
-		return -1;
-	}
-
-	if (xreaddir(reader->dir, &reader->de) != 0) {
-		reader->error = errno;
-		return -1;
-	} else if (reader->de) {
-		return 1;
-	} else {
-		return 0;
-	}
-}
-
-/** Close a directory. */
-static int bftw_reader_close(struct bftw_reader *reader) {
-	int ret = 0;
-	if (reader->dir && closedir(reader->dir) != 0) {
-		reader->error = errno;
-		ret = -1;
-	}
-
-	reader->de = NULL;
-	reader->dir = NULL;
-	return ret;
-}
-
-/**
- * Holds the current state of the bftw() traversal.
- */
-struct bftw_state {
-	/** bftw() callback. */
-	bftw_callback *callback;
-	/** bftw() callback data. */
-	void *ptr;
-	/** bftw() flags. */
-	enum bftw_flags flags;
-	/** Search strategy. */
-	enum bftw_strategy strategy;
-	/** The mount table. */
-	const struct bfs_mtab *mtab;
-
-	/** The appropriate errno value, if any. */
-	int error;
-
-	/** The cache of open directories. */
-	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;
-	/** The current file. */
-	struct bftw_file *file;
-	/** The previous file. */
-	struct bftw_file *previous;
-	/** The reader for the current directory. */
-	struct bftw_reader reader;
-
-	/** Extra data about the current file. */
-	struct BFTW ftwbuf;
-};
-
-/**
- * Initialize the bftw() state.
- */
-static int bftw_state_init(struct bftw_state *state, const struct bftw_args *args) {
-	state->callback = args->callback;
-	state->ptr = args->ptr;
-	state->flags = args->flags;
-	state->strategy = args->strategy;
-	state->mtab = args->mtab;
-
-	state->error = 0;
-
-	if (args->nopenfd < 2) {
-		errno = EMFILE;
-		goto err;
-	}
-
-	// Reserve 1 fd for the open DIR *
-	if (bftw_cache_init(&state->cache, args->nopenfd - 1) != 0) {
-		goto err;
-	}
-
-	bftw_queue_init(&state->queue);
-	bftw_queue_init(&state->prequeue);
-
-	state->path = dstralloc(0);
-	if (!state->path) {
-		goto err_cache;
-	}
-
-	state->file = NULL;
-	state->previous = NULL;
-	bftw_reader_init(&state->reader);
-
-	return 0;
-
-err_cache:
-	bftw_cache_destroy(&state->cache);
-err:
-	return -1;
-}
-
-enum bftw_typeflag bftw_mode_typeflag(mode_t mode) {
-	switch (mode & S_IFMT) {
-#ifdef S_IFBLK
-	case S_IFBLK:
-		return BFTW_BLK;
-#endif
-#ifdef S_IFCHR
-	case S_IFCHR:
-		return BFTW_CHR;
-#endif
-#ifdef S_IFDIR
-	case S_IFDIR:
-		return BFTW_DIR;
-#endif
-#ifdef S_IFDOOR
-	case S_IFDOOR:
-		return BFTW_DOOR;
-#endif
-#ifdef S_IFIFO
-	case S_IFIFO:
-		return BFTW_FIFO;
-#endif
-#ifdef S_IFLNK
-	case S_IFLNK:
-		return BFTW_LNK;
-#endif
-#ifdef S_IFPORT
-	case S_IFPORT:
-		return BFTW_PORT;
-#endif
-#ifdef S_IFREG
-	case S_IFREG:
-		return BFTW_REG;
-#endif
-#ifdef S_IFSOCK
-	case S_IFSOCK:
-		return BFTW_SOCK;
-#endif
-#ifdef S_IFWHT
-	case S_IFWHT:
-		return BFTW_WHT;
-#endif
-
-	default:
-		return BFTW_UNKNOWN;
-	}
-}
-
-static enum bftw_typeflag bftw_dirent_typeflag(const struct dirent *de) {
-#if defined(_DIRENT_HAVE_D_TYPE) || defined(DT_UNKNOWN)
-	switch (de->d_type) {
-#ifdef DT_BLK
-	case DT_BLK:
-		return BFTW_BLK;
-#endif
-#ifdef DT_CHR
-	case DT_CHR:
-		return BFTW_CHR;
-#endif
-#ifdef DT_DIR
-	case DT_DIR:
-		return BFTW_DIR;
-#endif
-#ifdef DT_DOOR
-	case DT_DOOR:
-		return BFTW_DOOR;
-#endif
-#ifdef DT_FIFO
-	case DT_FIFO:
-		return BFTW_FIFO;
-#endif
-#ifdef DT_LNK
-	case DT_LNK:
-		return BFTW_LNK;
-#endif
-#ifdef DT_PORT
-	case DT_PORT:
-		return BFTW_PORT;
-#endif
-#ifdef DT_REG
-	case DT_REG:
-		return BFTW_REG;
-#endif
-#ifdef DT_SOCK
-	case DT_SOCK:
-		return BFTW_SOCK;
-#endif
-#ifdef DT_WHT
-	case DT_WHT:
-		return BFTW_WHT;
-#endif
-	}
-#endif
-
-	return BFTW_UNKNOWN;
-}
-
-/** Cached bfs_stat(). */
-static const struct bfs_stat *bftw_stat_impl(struct BFTW *ftwbuf, struct bftw_stat *cache, enum bfs_stat_flag flags) {
-	if (!cache->buf) {
-		if (cache->error) {
-			errno = cache->error;
-		} else if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, flags, &cache->storage) == 0) {
-			cache->buf = &cache->storage;
-		} else {
-			cache->error = errno;
-		}
-	}
-
-	return cache->buf;
-}
-
-const struct bfs_stat *bftw_stat(const struct BFTW *ftwbuf, enum bfs_stat_flag flags) {
-	struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
-	const struct bfs_stat *ret;
-
-	if (flags & BFS_STAT_NOFOLLOW) {
-		ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
-		if (ret && !S_ISLNK(ret->mode) && !mutbuf->stat_cache.buf) {
-			// Non-link, so share stat info
-			mutbuf->stat_cache.buf = ret;
-		}
-	} else {
-		ret = bftw_stat_impl(mutbuf, &mutbuf->stat_cache, BFS_STAT_FOLLOW);
-		if (!ret && (flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(errno)) {
-			ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
-		}
-	}
-
-	return ret;
-}
-
-enum bftw_typeflag bftw_typeflag(const struct BFTW *ftwbuf, enum bfs_stat_flag flags) {
-	if (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW) {
-		if ((flags & BFS_STAT_NOFOLLOW) || ftwbuf->typeflag != BFTW_LNK) {
-			return ftwbuf->typeflag;
-		}
-	} else if ((flags & (BFS_STAT_NOFOLLOW | BFS_STAT_TRYFOLLOW)) == BFS_STAT_TRYFOLLOW || ftwbuf->typeflag == BFTW_LNK) {
-		return ftwbuf->typeflag;
-	}
-
-	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, flags);
-	if (statbuf) {
-		return bftw_mode_typeflag(statbuf->mode);
-	} else {
-		return BFTW_ERROR;
-	}
-}
-
-/**
- * Update the path for the current file.
- */
-static int bftw_update_path(struct bftw_state *state, const char *name) {
-	const struct bftw_file *file = state->file;
-	size_t length = file ? file->nameoff + file->namelen : 0;
-
-	assert(dstrlen(state->path) >= length);
-	dstresize(&state->path, length);
-
-	if (name) {
-		if (length > 0 && state->path[length - 1] != '/') {
-			if (dstrapp(&state->path, '/') != 0) {
-				return -1;
-			}
-		}
-		if (dstrcat(&state->path, name) != 0) {
-			return -1;
-		}
-	}
-
-	return 0;
-}
-
-/** Check if a stat() call is needed for this visit. */
-static bool bftw_need_stat(const struct bftw_state *state) {
-	if (state->flags & BFTW_STAT) {
-		return true;
-	}
-
-	const struct BFTW *ftwbuf = &state->ftwbuf;
-	if (ftwbuf->typeflag == BFTW_UNKNOWN) {
-		return true;
-	}
-
-	if (ftwbuf->typeflag == BFTW_LNK && !(ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
-		return true;
-	}
-
-	if (ftwbuf->typeflag == BFTW_DIR) {
-		if (state->flags & (BFTW_DETECT_CYCLES | BFTW_XDEV)) {
-			return true;
-		}
-#if __linux__
-	} else if (state->mtab) {
-		// Linux fills in d_type from the underlying inode, even when
-		// the directory entry is a bind mount point.  In that case, we
-		// need to stat() to get the correct type.  We don't need to
-		// check for directories because they can only be mounted over
-		// by other directories.
-		if (bfs_maybe_mount(state->mtab, ftwbuf->path)) {
-			return true;
-		}
-#endif
-	}
-
-	return false;
-}
-
-/** Initialize bftw_stat cache. */
-static void bftw_stat_init(struct bftw_stat *cache) {
-	cache->buf = NULL;
-	cache->error = 0;
-}
-
-/**
- * Open a file if necessary.
- *
- * @param file
- *         The file to open.
- * @param path
- *         The path to that file or one of its descendants.
- * @return
- *         The opened file descriptor, or -1 on error.
- */
-static int bftw_ensure_open(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
-	int ret = file->fd;
-
-	if (ret < 0) {
-		char *copy = strndup(path, file->nameoff + file->namelen);
-		if (!copy) {
-			return -1;
-		}
-
-		ret = bftw_file_open(cache, file, copy);
-		free(copy);
-	}
-
-	return ret;
-}
-
-/**
- * Initialize the buffers with data about the current path.
- */
-static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
-	struct bftw_file *file = state->file;
-	const struct bftw_reader *reader = &state->reader;
-	const struct dirent *de = reader->de;
-
-	struct BFTW *ftwbuf = &state->ftwbuf;
-	ftwbuf->path = state->path;
-	ftwbuf->root = file ? file->root : ftwbuf->path;
-	ftwbuf->depth = 0;
-	ftwbuf->visit = visit;
-	ftwbuf->typeflag = BFTW_UNKNOWN;
-	ftwbuf->error = reader->error;
-	ftwbuf->at_fd = AT_FDCWD;
-	ftwbuf->at_path = ftwbuf->path;
-	ftwbuf->stat_flags = BFS_STAT_NOFOLLOW;
-	bftw_stat_init(&ftwbuf->lstat_cache);
-	bftw_stat_init(&ftwbuf->stat_cache);
-
-	struct bftw_file *parent = NULL;
-	if (de) {
-		parent = file;
-		ftwbuf->depth = file->depth + 1;
-		ftwbuf->typeflag = bftw_dirent_typeflag(de);
-		ftwbuf->nameoff = bftw_child_nameoff(file);
-	} else if (file) {
-		parent = file->parent;
-		ftwbuf->depth = file->depth;
-		ftwbuf->typeflag = file->typeflag;
-		ftwbuf->nameoff = file->nameoff;
-	}
-
-	if (parent) {
-		// Try to ensure the immediate parent is open, to avoid ENAMETOOLONG
-		if (bftw_ensure_open(&state->cache, parent, state->path) >= 0) {
-			ftwbuf->at_fd = parent->fd;
-			ftwbuf->at_path += ftwbuf->nameoff;
-		} else {
-			ftwbuf->error = errno;
-		}
-	}
-
-	if (ftwbuf->depth == 0) {
-		// Compute the name offset for root paths like "foo/bar"
-		ftwbuf->nameoff = xbasename(ftwbuf->path) - ftwbuf->path;
-	}
-
-	if (ftwbuf->error != 0) {
-		ftwbuf->typeflag = BFTW_ERROR;
-		return;
-	}
-
-	int follow_flags = BFTW_LOGICAL;
-	if (ftwbuf->depth == 0) {
-		follow_flags |= BFTW_COMFOLLOW;
-	}
-	bool follow = state->flags & follow_flags;
-	if (follow) {
-		ftwbuf->stat_flags = BFS_STAT_TRYFOLLOW;
-	}
-
-	const struct bfs_stat *statbuf = NULL;
-	if (bftw_need_stat(state)) {
-		statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
-		if (statbuf) {
-			ftwbuf->typeflag = bftw_mode_typeflag(statbuf->mode);
-		} else {
-			ftwbuf->typeflag = BFTW_ERROR;
-			ftwbuf->error = errno;
-			return;
-		}
-	}
-
-	if (ftwbuf->typeflag == BFTW_DIR && (state->flags & BFTW_DETECT_CYCLES)) {
-		for (const struct bftw_file *parent = file; parent; parent = parent->parent) {
-			if (parent->depth == ftwbuf->depth) {
-				continue;
-			}
-			if (parent->dev == statbuf->dev && parent->ino == statbuf->ino) {
-				ftwbuf->typeflag = BFTW_ERROR;
-				ftwbuf->error = ELOOP;
-				return;
-			}
-		}
-	}
-}
-
-/** Fill file identity information from an ftwbuf. */
-static void bftw_fill_id(struct bftw_file *file, const struct BFTW *ftwbuf) {
-	const struct bfs_stat *statbuf = ftwbuf->stat_cache.buf;
-	if (!statbuf || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
-		statbuf = ftwbuf->lstat_cache.buf;
-	}
-	if (statbuf) {
-		file->dev = statbuf->dev;
-		file->ino = statbuf->ino;
-	}
-}
-
-/**
- * Visit a path, invoking the callback.
- */
-static enum bftw_action bftw_visit(struct bftw_state *state, const char *name, enum bftw_visit visit) {
-	if (bftw_update_path(state, name) != 0) {
-		state->error = errno;
-		return BFTW_STOP;
-	}
-
-	const struct BFTW *ftwbuf = &state->ftwbuf;
-	bftw_init_ftwbuf(state, visit);
-
-	// Never give the callback BFTW_ERROR unless BFTW_RECOVER is specified
-	if (ftwbuf->typeflag == BFTW_ERROR && !(state->flags & BFTW_RECOVER)) {
-		state->error = ftwbuf->error;
-		return BFTW_STOP;
-	}
-
-	enum bftw_action ret = state->callback(ftwbuf, state->ptr);
-	switch (ret) {
-	case BFTW_CONTINUE:
-		break;
-	case BFTW_PRUNE:
-	case BFTW_STOP:
-		goto done;
-	default:
-		state->error = EINVAL;
-		return BFTW_STOP;
-	}
-
-	if (visit != BFTW_PRE || ftwbuf->typeflag != BFTW_DIR) {
-		ret = BFTW_PRUNE;
-		goto done;
-	}
-
-	if (state->flags & BFTW_XDEV) {
-		const struct bftw_file *parent = state->file;
-		if (parent && !name) {
-			parent = parent->parent;
-		}
-
-		if (parent) {
-			const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
-			if (statbuf && statbuf->dev != parent->dev) {
-				ret = BFTW_PRUNE;
-				goto done;
-			}
-		}
-	}
-
-done:
-	if (state->file && !name) {
-		bftw_fill_id(state->file, ftwbuf);
-	}
-
-	return ret;
-}
-
-/**
- * Push a new file onto the queue.
- */
-static int bftw_push(struct bftw_state *state, const char *name, bool fill_id) {
-	struct bftw_file *parent = state->file;
-	struct bftw_file *file = bftw_file_new(&state->cache, parent, name);
-	if (!file) {
-		state->error = errno;
-		return -1;
-	}
-
-	struct dirent *de = state->reader.de;
-	if (de) {
-		file->typeflag = bftw_dirent_typeflag(de);
-	}
-
-	if (fill_id) {
-		bftw_fill_id(file, &state->ftwbuf);
-	}
-
-	if (state->strategy == BFTW_DFS) {
-		bftw_queue_push(&state->prequeue, file);
-	} else {
-		bftw_queue_push(&state->queue, file);
-	}
-
-	return 0;
-}
-
-/**
- * Build the path to the current file.
- */
-static int bftw_build_path(struct bftw_state *state) {
-	const struct bftw_file *file = state->file;
-
-	size_t pathlen = file->nameoff + file->namelen;
-	if (dstresize(&state->path, pathlen) != 0) {
-		state->error = errno;
-		return -1;
-	}
-
-	// Try to find a common ancestor with the existing path
-	const struct bftw_file *ancestor = state->previous;
-	while (ancestor && ancestor->depth > file->depth) {
-		ancestor = ancestor->parent;
-	}
-
-	// Build the path backwards
-	while (file && file != ancestor) {
-		if (file->nameoff > 0) {
-			state->path[file->nameoff - 1] = '/';
-		}
-		memcpy(state->path + file->nameoff, file->name, file->namelen);
-
-		if (ancestor && ancestor->depth == file->depth) {
-			ancestor = ancestor->parent;
-		}
-		file = file->parent;
-	}
-
-	state->previous = state->file;
-	return 0;
-}
-
-/**
- * Pop the next file from the queue.
- */
-static int bftw_pop(struct bftw_state *state) {
-	if (state->strategy == BFTW_DFS) {
-		bftw_queue_prepend(&state->prequeue, &state->queue);
-	}
-
-	if (!state->queue.head) {
-		return 0;
-	}
-
-	state->file = bftw_queue_pop(&state->queue);
-
-	if (bftw_build_path(state) != 0) {
-		return -1;
-	}
-
-	return 1;
-}
-
-/**
- * Open a reader for the current directory.
- */
-static struct bftw_reader *bftw_open(struct bftw_state *state) {
-	struct bftw_reader *reader = &state->reader;
-	bftw_reader_open(reader, &state->cache, state->file, state->path);
-	return reader;
-}
-
-/**
- * Close and release the reader.
- */
-static enum bftw_action bftw_release_reader(struct bftw_state *state, bool do_visit) {
-	enum bftw_action ret = BFTW_CONTINUE;
-
-	struct bftw_reader *reader = &state->reader;
-	bftw_reader_close(reader);
-
-	if (reader->error != 0) {
-		if (do_visit) {
-			if (bftw_visit(state, NULL, BFTW_PRE) == BFTW_STOP) {
-				ret = BFTW_STOP;
-			}
-		} else {
-			state->error = reader->error;
-		}
-		reader->error = 0;
-	}
-
-	return ret;
-}
-
-/**
- * Finalize and free a file we're done with.
- */
-static enum bftw_action bftw_release_file(struct bftw_state *state, bool visit_file, bool visit_parents) {
-	enum bftw_action ret = BFTW_CONTINUE;
-
-	if (!(state->flags & BFTW_DEPTH)) {
-		visit_file = false;
-		visit_parents = false;
-	}
-	bool do_visit = visit_file;
-
-	while (state->file) {
-		if (bftw_file_decref(&state->cache, state->file) > 0) {
-			state->file = NULL;
-			break;
-		}
-
-		if (do_visit) {
-			if (bftw_visit(state, NULL, BFTW_POST) == BFTW_STOP) {
-				ret = BFTW_STOP;
-				visit_parents = false;
-			}
-		}
-		do_visit = visit_parents;
-
-		struct bftw_file *parent = state->file->parent;
-		if (state->previous == state->file) {
-			state->previous = parent;
-		}
-		bftw_file_free(&state->cache, state->file);
-		state->file = parent;
-	}
-
-	return ret;
-}
-
-/**
- * Drain all the entries from a bftw_queue.
- */
-static void bftw_drain_queue(struct bftw_state *state, struct bftw_queue *queue) {
-	while (queue->head) {
-		state->file = bftw_queue_pop(queue);
-		bftw_release_file(state, false, false);
-	}
-}
-
-/**
- * Dispose of the bftw() state.
- *
- * @return
- *         The bftw() return value.
- */
-static int bftw_state_destroy(struct bftw_state *state) {
-	dstrfree(state->path);
-
-	bftw_release_reader(state, false);
-
-	bftw_release_file(state, false, false);
-	bftw_drain_queue(state, &state->prequeue);
-	bftw_drain_queue(state, &state->queue);
-
-	bftw_cache_destroy(&state->cache);
-
-	errno = state->error;
-	return state->error ? -1 : 0;
-}
-
-/**
- * Breadth-first bftw() implementation.
- */
-static int bftw_bfs(const struct bftw_args *args) {
-	struct bftw_state state;
-	if (bftw_state_init(&state, args) != 0) {
-		return -1;
-	}
-
-	for (size_t i = 0; i < args->npaths; ++i) {
-		const char *path = args->paths[i];
-
-		switch (bftw_visit(&state, path, BFTW_PRE)) {
-		case BFTW_CONTINUE:
-			break;
-		case BFTW_PRUNE:
-			continue;
-		case BFTW_STOP:
-			goto done;
-		}
-
-		if (bftw_push(&state, path, true) != 0) {
-			goto done;
-		}
-	}
-
-	while (bftw_pop(&state) > 0) {
-		struct bftw_reader *reader = bftw_open(&state);
-
-		while (bftw_reader_read(reader) > 0) {
-			const char *name = reader->de->d_name;
-
-			switch (bftw_visit(&state, name, BFTW_PRE)) {
-			case BFTW_CONTINUE:
-				break;
-			case BFTW_PRUNE:
-				continue;
-			case BFTW_STOP:
-				goto done;
-			}
-
-			if (bftw_push(&state, name, true) != 0) {
-				goto done;
-			}
-		}
-
-		if (bftw_release_reader(&state, true) == BFTW_STOP) {
-			goto done;
-		}
-		if (bftw_release_file(&state, true, true) == BFTW_STOP) {
-			goto done;
-		}
-	}
-
-done:
-	return bftw_state_destroy(&state);
-}
-
-/**
- * Depth-first bftw() implementation.
- */
-static int bftw_dfs(const struct bftw_args *args) {
-	struct bftw_state state;
-	if (bftw_state_init(&state, args) != 0) {
-		return -1;
-	}
-
-	for (size_t i = 0; i < args->npaths; ++i) {
-		if (bftw_push(&state, args->paths[i], false) != 0) {
-			goto done;
-		}
-	}
-
-	while (bftw_pop(&state) > 0) {
-		bool visit_post = true;
-
-		switch (bftw_visit(&state, NULL, BFTW_PRE)) {
-		case BFTW_CONTINUE:
-			break;
-		case BFTW_PRUNE:
-			visit_post = false;
-			goto next;
-		case BFTW_STOP:
-			goto done;
-		}
-
-		struct bftw_reader *reader = bftw_open(&state);
-
-		while (bftw_reader_read(reader) > 0) {
-			if (bftw_push(&state, reader->de->d_name, false) != 0) {
-				goto done;
-			}
-		}
-
-		if (bftw_release_reader(&state, true) == BFTW_STOP) {
-			goto done;
-		}
-
-	next:
-		if (bftw_release_file(&state, visit_post, true) == BFTW_STOP) {
-			goto done;
-		}
-	}
-
-done:
-	return bftw_state_destroy(&state);
-}
-
-/**
- * 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_PRUNE;
-		}
-	}
-
-	if (ftwbuf->depth < state->depth) {
-		if (trie_find_str(state->pruned, ftwbuf->path)) {
-			return BFTW_PRUNE;
-		} else {
-			return BFTW_CONTINUE;
-		}
-	} else if (state->visit == BFTW_POST) {
-		if (trie_find_str(state->pruned, ftwbuf->path)) {
-			return BFTW_PRUNE;
-		}
-	}
-
-	state->bottom = false;
-
-	enum bftw_action ret = state->delegate(ftwbuf, state->ptr);
-
-	switch (ret) {
-	case BFTW_CONTINUE:
-		ret = BFTW_PRUNE;
-		break;
-	case BFTW_PRUNE:
-		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;
-
-		// bftw_bfs() is more efficient than bftw_dfs() since it visits
-		// directory entries as it reads them.  With args->strategy ==
-		// BFTW_DFS, it gives a hybrid ordering that visits immediate
-		// children first, then deeper descendants depth-first.  This
-		// doesn't matter for iterative deepening since we only visit
-		// one level at a time.
-		ret = bftw_bfs(&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_bfs(&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_bfs(args);
-	case BFTW_DFS:
-		return bftw_dfs(args);
-	case BFTW_IDS:
-		return bftw_ids(args);
-	}
-
-	errno = EINVAL;
-	return -1;
-}