9 files changed, 432 insertions, 343 deletions
diff --git a/bftw.c b/bftw.c
index 8229612..98ed341 100644
--- a/bftw.c
+++ b/bftw.c
@@ -749,16 +749,57 @@ 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->stat_flags, sb);
-	if (ret == 0) {
-		ftwbuf->statbuf = sb;
-		ftwbuf->typeflag = bftw_mode_typeflag(sb->mode);
+/** 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(struct BFTW *ftwbuf, enum bfs_stat_flag flags) {
+	const struct bfs_stat *ret;
+
+	if (flags & BFS_STAT_NOFOLLOW) {
+		ret = bftw_stat_impl(ftwbuf, &ftwbuf->lstat_cache, BFS_STAT_NOFOLLOW);
+		if (ret && !S_ISLNK(ret->mode) && !ftwbuf->stat_cache.buf) {
+			// Non-link, so share stat info
+			ftwbuf->stat_cache.buf = ret;
+		}
+	} else {
+		ret = bftw_stat_impl(ftwbuf, &ftwbuf->stat_cache, BFS_STAT_FOLLOW);
+		if (!ret && (flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(errno)) {
+			ret = bftw_stat_impl(ftwbuf, &ftwbuf->lstat_cache, BFS_STAT_NOFOLLOW);
+		}
+	}
+
 	return ret;
 }
 
+enum bftw_typeflag bftw_typeflag(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;
+	}
+}
+
 /**
  * Holds the current state of the bftw() traversal.
  */
@@ -790,8 +831,6 @@ struct bftw_state {
 
 	/** Extra data about the current file. */
 	struct BFTW ftwbuf;
-	/** bfs_stat() buffer for the current file. */
-	struct bfs_stat statbuf;
 };
 
 /**
@@ -901,6 +940,12 @@ static bool bftw_need_stat(struct bftw_state *state) {
 	return false;
 }
 
+/** Initialize bftw_stat cache. */
+static void bftw_stat_init(struct bftw_stat *cache) {
+	cache->buf = NULL;
+	cache->error = 0;
+}
+
 /**
  * Initialize the buffers with data about the current path.
  */
@@ -915,10 +960,11 @@ static void bftw_prepare_visit(struct bftw_state *state) {
 	ftwbuf->depth = 0;
 	ftwbuf->visit = state->visit;
 	ftwbuf->error = reader->error;
-	ftwbuf->statbuf = NULL;
 	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);
 
 	if (dir) {
 		ftwbuf->nameoff = dir->nameoff;
@@ -960,8 +1006,12 @@ static void bftw_prepare_visit(struct bftw_state *state) {
 		ftwbuf->stat_flags = BFS_STAT_TRYFOLLOW;
 	}
 
+	const struct bfs_stat *statbuf = NULL;
 	if (bftw_need_stat(state)) {
-		if (bftw_stat(ftwbuf, &state->statbuf) != 0) {
+		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;
@@ -969,7 +1019,6 @@ static void bftw_prepare_visit(struct bftw_state *state) {
 	}
 
 	if (ftwbuf->typeflag == BFTW_DIR && (state->flags & BFTW_DETECT_CYCLES)) {
-		const struct bfs_stat *statbuf = ftwbuf->statbuf;
 		for (const struct bftw_dir *parent = dir; parent; parent = parent->parent) {
 			if (parent->depth == ftwbuf->depth) {
 				continue;
@@ -1030,7 +1079,11 @@ static int bftw_push(struct bftw_state *state, const char *name) {
 		return -1;
 	}
 
-	const struct bfs_stat *statbuf = state->ftwbuf.statbuf;
+	const struct BFTW *ftwbuf = &state->ftwbuf;
+	const struct bfs_stat *statbuf = ftwbuf->stat_cache.buf;
+	if (!statbuf) {
+		statbuf = ftwbuf->lstat_cache.buf;
+	}
 	if (statbuf) {
 		dir->dev = statbuf->dev;
 		dir->ino = statbuf->ino;
@@ -1194,17 +1247,19 @@ int bftw(const char *path, const struct bftw_args *args) {
 				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->dir->dev) {
+			if (state.ftwbuf.typeflag != BFTW_DIR) {
+				goto read;
+			}
+
+			if (args->flags & BFTW_XDEV) {
+				const struct bfs_stat *statbuf = bftw_stat(&state.ftwbuf, state.ftwbuf.stat_flags);
+				if (statbuf && statbuf->dev != reader->dir->dev) {
 					goto read;
 				}
+			}
 
-				if (bftw_push(&state, name) != 0) {
-					goto done;
-				}
+			if (bftw_push(&state, name) != 0) {
+				goto done;
 			}
 
 		read:
diff --git a/bftw.h b/bftw.h
index e0f02d9..626a6d8 100644
--- a/bftw.h
+++ b/bftw.h
@@ -71,6 +71,18 @@ enum bftw_visit {
 };
 
 /**
+ * Cached bfs_stat() info for a file.
+ */
+struct bftw_stat {
+	/** A pointer to the bfs_stat() buffer, if available. */
+	const struct bfs_stat *buf;
+	/** Storage for the bfs_stat() buffer, if needed. */
+	struct bfs_stat storage;
+	/** The cached error code, if any. */
+	int error;
+};
+
+/**
  * Data about the current file for the bftw() callback.
  */
 struct BFTW {
@@ -91,18 +103,47 @@ struct BFTW {
 	/** The errno that occurred, if typeflag == BFTW_ERROR. */
 	int error;
 
-	/** A bfs_stat() buffer; may be NULL if no stat() call was needed. */
-	const struct bfs_stat *statbuf;
-
 	/** A parent file descriptor for the *at() family of calls. */
 	int at_fd;
 	/** The path relative to at_fd for the *at() family of calls. */
 	const char *at_path;
+
 	/** Flags for bfs_stat(). */
 	enum bfs_stat_flag stat_flags;
+	/** Cached bfs_stat() info for BFS_STAT_NOFOLLOW. */
+	struct bftw_stat lstat_cache;
+	/** Cached bfs_stat() info for BFS_STAT_FOLLOW. */
+	struct bftw_stat stat_cache;
 };
 
 /**
+ * Get bfs_stat() info for a file encountered during bftw(), caching the result
+ * whenever possible.
+ *
+ * @param ftwbuf
+ *         bftw() data for the file to stat.
+ * @param flags
+ *         flags for bfs_stat().  Pass ftwbuf->stat_flags for the default flags.
+ * @return
+ *         A pointer to a bfs_stat() buffer, or NULL if the call failed.
+ */
+const struct bfs_stat *bftw_stat(struct BFTW *ftwbuf, enum bfs_stat_flag flags);
+
+/**
+ * Get the type of a file encountered during bftw(), with flags controlling
+ * whether to follow links.  This function will avoid calling bfs_stat() if
+ * possible.
+ *
+ * @param ftwbuf
+ *         bftw() data for the file to check.
+ * @param flags
+ *         flags for bfs_stat().  Pass ftwbuf->stat_flags for the default flags.
+ * @return
+ *         The type of the file, or BFTW_ERROR if an error occurred.
+ */
+enum bftw_typeflag bftw_typeflag(struct BFTW *ftwbuf, enum bfs_stat_flag flags);
+
+/**
  * Walk actions returned by the bftw() callback.
  */
 enum bftw_action {
diff --git a/color.c b/color.c
index 726c40f..188e7ed 100644
--- a/color.c
+++ b/color.c
@@ -550,8 +550,8 @@ static bool is_link_broken(const struct BFTW *ftwbuf) {
 }
 
 /** Get the color for a file. */
-static const char *file_color(const struct colors *colors, const char *filename, const struct BFTW *ftwbuf) {
-	const struct bfs_stat *sb = ftwbuf->statbuf;
+static const char *file_color(const struct colors *colors, const char *filename, struct BFTW *ftwbuf, enum bfs_stat_flag flags) {
+	const struct bfs_stat *sb = bftw_stat(ftwbuf, flags);
 	if (!sb) {
 		if (colors->missing) {
 			return colors->missing;
@@ -692,54 +692,54 @@ static int print_colored(const struct colors *colors, const char *esc, const cha
 }
 
 /** Print a path with colors. */
-static int print_path_colored(CFILE *cfile, const struct BFTW *ftwbuf) {
+static int print_path_colored(CFILE *cfile, const char *path, struct BFTW *ftwbuf, enum bfs_stat_flag flags) {
 	const struct colors *colors = cfile->colors;
 	FILE *file = cfile->file;
-	const char *path = ftwbuf->path;
 
-	if (ftwbuf->nameoff > 0) {
-		if (print_colored(colors, colors->directory, path, ftwbuf->nameoff, file) != 0) {
+	size_t nameoff;
+	if (path == ftwbuf->path) {
+		nameoff = ftwbuf->nameoff;
+	} else {
+		nameoff = xbasename(path) - path;
+	}
+
+	if (nameoff > 0) {
+		if (print_colored(colors, colors->directory, path, nameoff, file) != 0) {
 			return -1;
 		}
 	}
 
-	const char *filename = path + ftwbuf->nameoff;
-	const char *color = file_color(colors, filename, ftwbuf);
+	const char *filename = path + nameoff;
+	const char *color = file_color(colors, filename, ftwbuf, flags);
 	return print_colored(colors, color, filename, strlen(filename), file);
 }
 
-/** Call stat() again to resolve a link target. */
-static void restat(struct BFTW *ftwbuf, struct bfs_stat *statbuf) {
-	if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->stat_flags, statbuf) == 0) {
-		ftwbuf->statbuf = statbuf;
-	}
-}
-
 /** Print the path to a file with the appropriate colors. */
-static int print_path(CFILE *cfile, const struct BFTW *ftwbuf) {
+static int print_path(CFILE *cfile, struct BFTW *ftwbuf) {
 	const struct colors *colors = cfile->colors;
 	if (!colors) {
 		return fputs(ftwbuf->path, cfile->file) == EOF ? -1 : 0;
 	}
 
-	if (colors && colors->link_as_target) {
-		if (ftwbuf->typeflag == BFTW_LNK && (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
-			struct BFTW altbuf = *ftwbuf;
-			altbuf.stat_flags = BFS_STAT_FOLLOW;
-			struct bfs_stat statbuf;
-			restat(&altbuf, &statbuf);
-			return print_path_colored(cfile, &altbuf);
-		}
+	enum bfs_stat_flag flags = ftwbuf->stat_flags;
+	if (colors && colors->link_as_target && ftwbuf->typeflag == BFTW_LNK) {
+		flags = BFS_STAT_TRYFOLLOW;
 	}
 
-	return print_path_colored(cfile, ftwbuf);
+	return print_path_colored(cfile, ftwbuf->path, ftwbuf, flags);
 }
 
 /** Print a link target with the appropriate colors. */
-static int print_link_target(CFILE *cfile, const struct BFTW *ftwbuf) {
+static int print_link_target(CFILE *cfile, struct BFTW *ftwbuf) {
 	int ret = -1;
 
-	char *target = xreadlinkat(ftwbuf->at_fd, ftwbuf->at_path, 0);
+	size_t len = 0;
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, BFS_STAT_NOFOLLOW);
+	if (statbuf) {
+		len = statbuf->size;
+	}
+
+	char *target = xreadlinkat(ftwbuf->at_fd, ftwbuf->at_path, len);
 	if (!target) {
 		goto done;
 	}
@@ -749,16 +749,7 @@ static int print_link_target(CFILE *cfile, const struct BFTW *ftwbuf) {
 		goto done;
 	}
 
-	struct BFTW altbuf = *ftwbuf;
-	altbuf.path = target;
-	altbuf.nameoff = xbasename(target) - target;
-	altbuf.stat_flags = BFS_STAT_FOLLOW;
-	altbuf.statbuf = NULL;
-
-	struct bfs_stat statbuf;
-	restat(&altbuf, &statbuf);
-
-	ret = print_path_colored(cfile, &altbuf);
+	ret = print_path_colored(cfile, target, ftwbuf, BFS_STAT_FOLLOW);
 
 done:
 	free(target);
@@ -837,13 +828,13 @@ int cvfprintf(CFILE *cfile, const char *format, va_list args) {
 			case 'p':
 				switch (*++i) {
 				case 'P':
-					if (print_path(cfile, va_arg(args, const struct BFTW *)) != 0) {
+					if (print_path(cfile, va_arg(args, struct BFTW *)) != 0) {
 						return -1;
 					}
 					break;
 
 				case 'L':
-					if (print_link_target(cfile, va_arg(args, const struct BFTW *)) != 0) {
+					if (print_link_target(cfile, va_arg(args, struct BFTW *)) != 0) {
 						return -1;
 					}
 					break;
diff --git a/color.h b/color.h
index 7df3785..946358a 100644
--- a/color.h
+++ b/color.h
@@ -106,8 +106,8 @@ int cfclose(CFILE *cfile);
  *         %s: A string
  *         %zu: A size_t
  *         %m: strerror(errno)
- *         %pP: A colored file path, from a const struct BFTW * argument
- *         %pL: A colored link target, from a const struct BFTW * argument
+ *         %pP: A colored file path, from a struct BFTW * argument
+ *         %pL: A colored link target, from a struct BFTW * argument
  *         %%: A literal '%'
  *         ${cc}: Change the color to 'cc'
  *         $$: A literal '$'
diff --git a/eval.c b/eval.c
index 1c4ff80..3bcdfeb 100644
--- a/eval.c
+++ b/eval.c
@@ -59,79 +59,8 @@ struct eval_state {
 	int *ret;
 	/** Whether to quit immediately. */
 	bool *quit;
-	/** A bfs_stat() buffer, if necessary. */
-	struct bfs_stat statbuf;
-	/** A bfs_stat() buffer for -xtype style tests. */
-	struct bfs_stat xstatbuf;
 };
 
-#define DEBUG_FLAG(flags, flag)				\
-	do {						\
-		if ((flags & flag) || flags == flag) {	\
-			fputs(#flag, stderr);		\
-			flags ^= flag;			\
-			if (flags) {			\
-				fputs(" | ", stderr);	\
-			}				\
-		}					\
-	} while (0)
-
-/**
- * Debug stat() calls.
- */
-static void debug_stat(const struct eval_state *state, enum bfs_stat_flag flags) {
-	if (!(state->cmdline->debug & DEBUG_STAT)) {
-		return;
-	}
-
-	struct BFTW *ftwbuf = state->ftwbuf;
-
-	fprintf(stderr, "bfs_stat(");
-	if (ftwbuf->at_fd == AT_FDCWD) {
-		fprintf(stderr, "AT_FDCWD");
-	} else {
-		size_t baselen = strlen(ftwbuf->path) - strlen(ftwbuf->at_path);
-		fprintf(stderr, "\"");
-		fwrite(ftwbuf->path, 1, baselen, stderr);
-		fprintf(stderr, "\"");
-	}
-
-	fprintf(stderr, ", \"%s\", ", ftwbuf->at_path);
-
-	DEBUG_FLAG(flags, BFS_STAT_FOLLOW);
-	DEBUG_FLAG(flags, BFS_STAT_NOFOLLOW);
-	DEBUG_FLAG(flags, BFS_STAT_TRYFOLLOW);
-
-	fprintf(stderr, ")\n");
-}
-
-/**
- * Perform a bfs_stat() call if necessary.
- */
-static const struct bfs_stat *eval_try_stat(struct eval_state *state) {
-	struct BFTW *ftwbuf = state->ftwbuf;
-
-	if (ftwbuf->statbuf) {
-		goto done;
-	}
-
-	if (ftwbuf->error) {
-		errno = ftwbuf->error;
-		goto done;
-	}
-
-	debug_stat(state, ftwbuf->stat_flags);
-
-	if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, ftwbuf->stat_flags, &state->statbuf) == 0) {
-		ftwbuf->statbuf = &state->statbuf;
-	} else {
-		ftwbuf->error = errno;
-	}
-
-done:
-	return ftwbuf->statbuf;
-}
-
 /**
  * Print an error message.
  */
@@ -141,10 +70,6 @@ static void eval_error(struct eval_state *state, const char *format, ...) {
 	const struct cmdline *cmdline = state->cmdline;
 	CFILE *cerr = cmdline->cerr;
 
-	if (cerr->colors) {
-		eval_try_stat(state);
-	}
-
 	bfs_error(cmdline, "%pP: ", state->ftwbuf);
 
 	va_list args;
@@ -177,7 +102,8 @@ static void eval_report_error(struct eval_state *state) {
  * Perform a bfs_stat() call if necessary.
  */
 static const struct bfs_stat *eval_stat(struct eval_state *state) {
-	const struct bfs_stat *ret = eval_try_stat(state);
+	struct BFTW *ftwbuf = state->ftwbuf;
+	const struct bfs_stat *ret = bftw_stat(ftwbuf, ftwbuf->stat_flags);
 	if (!ret) {
 		eval_report_error(state);
 	}
@@ -185,22 +111,6 @@ static const struct bfs_stat *eval_stat(struct eval_state *state) {
 }
 
 /**
- * Perform a bfs_stat() call for tests that flip the follow flag, like -xtype.
- */
-static const struct bfs_stat *eval_xstat(struct eval_state *state) {
-	struct BFTW *ftwbuf = state->ftwbuf;
-	struct bfs_stat *statbuf = &state->xstatbuf;
-	if (!statbuf->mask) {
-		enum bfs_stat_flag flags = ftwbuf->stat_flags ^ (BFS_STAT_NOFOLLOW | BFS_STAT_TRYFOLLOW);
-		debug_stat(state, flags);
-		if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, flags, statbuf) != 0) {
-			return NULL;
-		}
-	}
-	return statbuf;
-}
-
-/**
  * Get the difference (in seconds) between two struct timespecs.
  */
 static time_t timespec_diff(const struct timespec *lhs, const struct timespec *rhs) {
@@ -415,21 +325,14 @@ bool eval_delete(const struct expr *expr, struct eval_state *state) {
 	}
 
 	int flag = 0;
-	if (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW) {
-		if (ftwbuf->typeflag == BFTW_DIR) {
-			flag |= AT_REMOVEDIR;
-		}
-	} else if (ftwbuf->typeflag != BFTW_LNK) {
-		// We need to know the actual type of the path, not what it points to
-		const struct bfs_stat *statbuf = eval_xstat(state);
-		if (statbuf) {
-			if (S_ISDIR(statbuf->mode)) {
-				flag |= AT_REMOVEDIR;
-			}
-		} else {
-			eval_report_error(state);
-			return false;
-		}
+
+	// We need to know the actual type of the path, not what it points to
+	enum bftw_typeflag type = bftw_typeflag(ftwbuf, BFS_STAT_NOFOLLOW);
+	if (type == BFTW_DIR) {
+		flag |= AT_REMOVEDIR;
+	} else if (type == BFTW_ERROR) {
+		eval_report_error(state);
+		return false;
 	}
 
 	if (unlinkat(ftwbuf->at_fd, ftwbuf->at_path, flag) != 0) {
@@ -698,7 +601,7 @@ bool eval_perm(const struct expr *expr, struct eval_state *state) {
 bool eval_fls(const struct expr *expr, struct eval_state *state) {
 	CFILE *cfile = expr->cfile;
 	FILE *file = cfile->file;
-	const struct BFTW *ftwbuf = state->ftwbuf;
+	struct BFTW *ftwbuf = state->ftwbuf;
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		goto done;
@@ -825,17 +728,10 @@ bool eval_fprint0(const struct expr *expr, struct eval_state *state) {
  * -f?printf action.
  */
 bool eval_fprintf(const struct expr *expr, struct eval_state *state) {
-	if (expr->printf->needs_stat) {
-		if (!eval_stat(state)) {
-			goto done;
-		}
-	}
-
 	if (bfs_printf(expr->cfile->file, expr->printf, state->ftwbuf) != 0) {
 		eval_report_error(state);
 	}
 
-done:
 	return true;
 }
 
@@ -989,22 +885,13 @@ bool eval_type(const struct expr *expr, struct eval_state *state) {
  */
 bool eval_xtype(const struct expr *expr, struct eval_state *state) {
 	struct BFTW *ftwbuf = state->ftwbuf;
-
-	bool follow = !(ftwbuf->stat_flags & BFS_STAT_NOFOLLOW);
-	bool is_link = ftwbuf->typeflag == BFTW_LNK;
-	if (follow == is_link) {
-		return eval_type(expr, state);
-	}
-
-	const struct bfs_stat *statbuf = eval_xstat(state);
-	if (statbuf) {
-		return bftw_mode_typeflag(statbuf->mode) & expr->idata;
-	} else if (!follow && is_nonexistence_error(errno)) {
-		// Broken symlink
-		return eval_type(expr, state);
-	} else {
+	enum bfs_stat_flag flags = ftwbuf->stat_flags ^ (BFS_STAT_NOFOLLOW | BFS_STAT_TRYFOLLOW);
+	enum bftw_typeflag type = bftw_typeflag(ftwbuf, flags);
+	if (type == BFTW_ERROR) {
 		eval_report_error(state);
 		return false;
+	} else {
+		return type & expr->idata;
 	}
 }
 
@@ -1156,6 +1043,61 @@ static bool eval_file_unique(struct eval_state *state, struct trie *seen) {
 	}
 }
 
+#define DEBUG_FLAG(flags, flag)				\
+	do {						\
+		if ((flags & flag) || flags == flag) {	\
+			fputs(#flag, stderr);		\
+			flags ^= flag;			\
+			if (flags) {			\
+				fputs(" | ", stderr);	\
+			}				\
+		}					\
+	} while (0)
+
+/**
+ * Log a stat() call.
+ */
+static void debug_stat(const struct BFTW *ftwbuf, const struct bftw_stat *cache, enum bfs_stat_flag flags) {
+	fprintf(stderr, "bfs_stat(");
+	if (ftwbuf->at_fd == AT_FDCWD) {
+		fprintf(stderr, "AT_FDCWD");
+	} else {
+		size_t baselen = strlen(ftwbuf->path) - strlen(ftwbuf->at_path);
+		fprintf(stderr, "\"");
+		fwrite(ftwbuf->path, 1, baselen, stderr);
+		fprintf(stderr, "\"");
+	}
+
+	fprintf(stderr, ", \"%s\", ", ftwbuf->at_path);
+
+	DEBUG_FLAG(flags, BFS_STAT_FOLLOW);
+	DEBUG_FLAG(flags, BFS_STAT_NOFOLLOW);
+	DEBUG_FLAG(flags, BFS_STAT_TRYFOLLOW);
+
+	fprintf(stderr, ") == %d", cache->buf ? 0 : -1);
+
+	if (cache->error) {
+		fprintf(stderr, " [%d]", cache->error);
+	}
+
+	fprintf(stderr, "\n");
+}
+
+/**
+ * Log any stat() calls that happened.
+ */
+static void debug_stats(const struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = ftwbuf->stat_cache.buf;
+	if (statbuf || ftwbuf->stat_cache.error) {
+		debug_stat(ftwbuf, &ftwbuf->stat_cache, BFS_STAT_FOLLOW);
+	}
+
+	const struct bfs_stat *lstatbuf = ftwbuf->lstat_cache.buf;
+	if ((lstatbuf && lstatbuf != statbuf) || ftwbuf->lstat_cache.error) {
+		debug_stat(ftwbuf, &ftwbuf->lstat_cache, BFS_STAT_NOFOLLOW);
+	}
+}
+
 /**
  * Dump the bftw_typeflag for -D search.
  */
@@ -1237,11 +1179,6 @@ static enum bftw_action cmdline_callback(struct BFTW *ftwbuf, void *ptr) {
 	state.action = BFTW_CONTINUE;
 	state.ret = &args->ret;
 	state.quit = &args->quit;
-	state.xstatbuf.mask = 0;
-
-	if (ftwbuf->statbuf) {
-		debug_stat(&state, ftwbuf->stat_flags);
-	}
 
 	if (ftwbuf->typeflag == BFTW_ERROR) {
 		if (!eval_should_ignore(&state, ftwbuf->error)) {
@@ -1284,6 +1221,10 @@ static enum bftw_action cmdline_callback(struct BFTW *ftwbuf, void *ptr) {
 	}
 
 done:
+	if (cmdline->debug & DEBUG_STAT) {
+		debug_stats(ftwbuf);
+	}
+
 	if (cmdline->debug & DEBUG_SEARCH) {
 		fprintf(stderr,
 		        "cmdline_callback({ "
diff --git a/printf.c b/printf.c
index b2463e1..f77ff92 100644
--- a/printf.c
+++ b/printf.c
@@ -33,12 +33,9 @@
 #include <string.h>
 #include <time.h>
 
-typedef int bfs_printf_fn(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf);
+typedef int bfs_printf_fn(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf);
 
-/**
- * A single directive in a printf command.
- */
-struct bfs_printf_directive {
+struct bfs_printf {
 	/** The printing function to invoke. */
 	bfs_printf_fn *fn;
 	/** String data associated with this directive. */
@@ -50,11 +47,11 @@ struct bfs_printf_directive {
 	/** The current mount table. */
 	const struct bfs_mtab *mtab;
 	/** The next printf directive in the chain. */
-	struct bfs_printf_directive *next;
+	struct bfs_printf *next;
 };
 
 /** Print some text as-is. */
-static int bfs_printf_literal(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_literal(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	size_t len = dstrlen(directive->str);
 	if (fwrite(directive->str, 1, len, file) == len) {
 		return 0;
@@ -64,7 +61,7 @@ static int bfs_printf_literal(FILE *file, const struct bfs_printf_directive *dir
 }
 
 /** \c: flush */
-static int bfs_printf_flush(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_flush(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	return fflush(file);
 }
 
@@ -78,12 +75,17 @@ static int bfs_printf_flush(FILE *file, const struct bfs_printf_directive *direc
 	(void)ret
 
 /** %a, %c, %t: ctime() */
-static int bfs_printf_ctime(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_ctime(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	// Not using ctime() itself because GNU find adds nanoseconds
 	static const char *days[] = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
 	static const char *months[] = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
 
-	const struct timespec *ts = bfs_stat_time(ftwbuf->statbuf, directive->stat_field);
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	const struct timespec *ts = bfs_stat_time(statbuf, directive->stat_field);
 	if (!ts) {
 		return -1;
 	}
@@ -107,8 +109,13 @@ static int bfs_printf_ctime(FILE *file, const struct bfs_printf_directive *direc
 }
 
 /** %A, %B/%W, %C, %T: strftime() */
-static int bfs_printf_strftime(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	const struct timespec *ts = bfs_stat_time(ftwbuf->statbuf, directive->stat_field);
+static int bfs_printf_strftime(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	const struct timespec *ts = bfs_stat_time(statbuf, directive->stat_field);
 	if (!ts) {
 		return -1;
 	}
@@ -170,43 +177,68 @@ static int bfs_printf_strftime(FILE *file, const struct bfs_printf_directive *di
 }
 
 /** %b: blocks */
-static int bfs_printf_b(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	uintmax_t blocks = ((uintmax_t)ftwbuf->statbuf->blocks*BFS_STAT_BLKSIZE + 511)/512;
+static int bfs_printf_b(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	uintmax_t blocks = ((uintmax_t)statbuf->blocks*BFS_STAT_BLKSIZE + 511)/512;
 	BFS_PRINTF_BUF(buf, "%ju", blocks);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %d: depth */
-static int bfs_printf_d(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_d(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	return fprintf(file, directive->str, (intmax_t)ftwbuf->depth);
 }
 
 /** %D: device */
-static int bfs_printf_D(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)ftwbuf->statbuf->dev);
+static int bfs_printf_D(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)statbuf->dev);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %f: file name */
-static int bfs_printf_f(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_f(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	return fprintf(file, directive->str, ftwbuf->path + ftwbuf->nameoff);
 }
 
 /** %F: file system type */
-static int bfs_printf_F(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	const char *type = bfs_fstype(directive->mtab, ftwbuf->statbuf);
+static int bfs_printf_F(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	const char *type = bfs_fstype(directive->mtab, statbuf);
 	return fprintf(file, directive->str, type);
 }
 
 /** %G: gid */
-static int bfs_printf_G(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)ftwbuf->statbuf->gid);
+static int bfs_printf_G(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)statbuf->gid);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %g: group name */
-static int bfs_printf_g(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	struct group *grp = getgrgid(ftwbuf->statbuf->gid);
+static int bfs_printf_g(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	struct group *grp = getgrgid(statbuf->gid);
 	if (!grp) {
 		return bfs_printf_G(file, directive, ftwbuf);
 	}
@@ -215,7 +247,7 @@ static int bfs_printf_g(FILE *file, const struct bfs_printf_directive *directive
 }
 
 /** %h: leading directories */
-static int bfs_printf_h(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_h(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	char *copy = NULL;
 	const char *buf;
 
@@ -242,25 +274,35 @@ static int bfs_printf_h(FILE *file, const struct bfs_printf_directive *directive
 }
 
 /** %H: current root */
-static int bfs_printf_H(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_H(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	return fprintf(file, directive->str, ftwbuf->root);
 }
 
 /** %i: inode */
-static int bfs_printf_i(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)ftwbuf->statbuf->ino);
+static int bfs_printf_i(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)statbuf->ino);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %k: 1K blocks */
-static int bfs_printf_k(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	uintmax_t blocks = ((uintmax_t)ftwbuf->statbuf->blocks*BFS_STAT_BLKSIZE + 1023)/1024;
+static int bfs_printf_k(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	uintmax_t blocks = ((uintmax_t)statbuf->blocks*BFS_STAT_BLKSIZE + 1023)/1024;
 	BFS_PRINTF_BUF(buf, "%ju", blocks);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %l: link target */
-static int bfs_printf_l(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_l(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	if (ftwbuf->typeflag != BFTW_LNK) {
 		return 0;
 	}
@@ -276,30 +318,45 @@ static int bfs_printf_l(FILE *file, const struct bfs_printf_directive *directive
 }
 
 /** %m: mode */
-static int bfs_printf_m(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	return fprintf(file, directive->str, (unsigned int)(ftwbuf->statbuf->mode & 07777));
+static int bfs_printf_m(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	return fprintf(file, directive->str, (unsigned int)(statbuf->mode & 07777));
 }
 
 /** %M: symbolic mode */
-static int bfs_printf_M(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_M(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
 	char buf[11];
-	format_mode(ftwbuf->statbuf->mode, buf);
+	format_mode(statbuf->mode, buf);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %n: link count */
-static int bfs_printf_n(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)ftwbuf->statbuf->nlink);
+static int bfs_printf_n(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)statbuf->nlink);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %p: full path */
-static int bfs_printf_p(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_p(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	return fprintf(file, directive->str, ftwbuf->path);
 }
 
 /** %P: path after root */
-static int bfs_printf_P(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_P(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	const char *path = ftwbuf->path + strlen(ftwbuf->root);
 	if (path[0] == '/') {
 		++path;
@@ -308,32 +365,51 @@ static int bfs_printf_P(FILE *file, const struct bfs_printf_directive *directive
 }
 
 /** %s: size */
-static int bfs_printf_s(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)ftwbuf->statbuf->size);
+static int bfs_printf_s(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)statbuf->size);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %S: sparseness */
-static int bfs_printf_S(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_S(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
 	double sparsity;
-	const struct bfs_stat *sb = ftwbuf->statbuf;
-	if (sb->size == 0 && sb->blocks == 0) {
+	if (statbuf->size == 0 && statbuf->blocks == 0) {
 		sparsity = 1.0;
 	} else {
-		sparsity = (double)BFS_STAT_BLKSIZE*sb->blocks/sb->size;
+		sparsity = (double)BFS_STAT_BLKSIZE*statbuf->blocks/statbuf->size;
 	}
 	return fprintf(file, directive->str, sparsity);
 }
 
 /** %U: uid */
-static int bfs_printf_U(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)ftwbuf->statbuf->uid);
+static int bfs_printf_U(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	BFS_PRINTF_BUF(buf, "%ju", (uintmax_t)statbuf->uid);
 	return fprintf(file, directive->str, buf);
 }
 
 /** %u: user name */
-static int bfs_printf_u(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
-	struct passwd *pwd = getpwuid(ftwbuf->statbuf->uid);
+static int bfs_printf_u(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
+	if (!statbuf) {
+		return -1;
+	}
+
+	struct passwd *pwd = getpwuid(statbuf->uid);
 	if (!pwd) {
 		return bfs_printf_U(file, directive, ftwbuf);
 	}
@@ -365,13 +441,13 @@ static const char *bfs_printf_type(enum bftw_typeflag typeflag) {
 }
 
 /** %y: type */
-static int bfs_printf_y(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_y(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	const char *type = bfs_printf_type(ftwbuf->typeflag);
 	return fprintf(file, directive->str, type);
 }
 
 /** %Y: target type */
-static int bfs_printf_Y(FILE *file, const struct bfs_printf_directive *directive, const struct BFTW *ftwbuf) {
+static int bfs_printf_Y(FILE *file, const struct bfs_printf *directive, struct BFTW *ftwbuf) {
 	int error = 0;
 
 	if (ftwbuf->typeflag != BFTW_LNK) {
@@ -380,9 +456,9 @@ static int bfs_printf_Y(FILE *file, const struct bfs_printf_directive *directive
 
 	const char *type = "U";
 
-	struct bfs_stat sb;
-	if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, BFS_STAT_FOLLOW, &sb) == 0) {
-		type = bfs_printf_type(bftw_mode_typeflag(sb.mode));
+	const struct bfs_stat *statbuf = bftw_stat(ftwbuf, BFS_STAT_FOLLOW);
+	if (statbuf) {
+		type = bfs_printf_type(bftw_mode_typeflag(statbuf->mode));
 	} else {
 		switch (errno) {
 		case ELOOP:
@@ -410,7 +486,7 @@ static int bfs_printf_Y(FILE *file, const struct bfs_printf_directive *directive
 /**
  * Free a printf directive.
  */
-static void free_directive(struct bfs_printf_directive *directive) {
+static void free_directive(struct bfs_printf *directive) {
 	if (directive) {
 		dstrfree(directive->str);
 		free(directive);
@@ -420,14 +496,14 @@ static void free_directive(struct bfs_printf_directive *directive) {
 /**
  * Create a new printf directive.
  */
-static struct bfs_printf_directive *new_directive(void) {
-	struct bfs_printf_directive *directive = malloc(sizeof(*directive));
+static struct bfs_printf *new_directive(bfs_printf_fn *fn) {
+	struct bfs_printf *directive = malloc(sizeof(*directive));
 	if (!directive) {
 		perror("malloc()");
 		goto error;
 	}
 
-	directive->fn = NULL;
+	directive->fn = fn;
 	directive->str = dstralloc(2);
 	if (!directive->str) {
 		perror("dstralloc()");
@@ -447,47 +523,30 @@ error:
 /**
  * Append a printf directive to the chain.
  */
-static void append_directive(struct bfs_printf_directive ***tail, struct bfs_printf_directive *directive) {
-	**tail = directive;
-	*tail = &directive->next;
+static struct bfs_printf **append_directive(struct bfs_printf **tail, struct bfs_printf *directive) {
+	assert(directive);
+	*tail = directive;
+	return &directive->next;
 }
 
 /**
  * Append a literal string to the chain.
  */
-static int append_literal(struct bfs_printf_directive ***tail, struct bfs_printf_directive **literal, bool last) {
-	struct bfs_printf_directive *directive = *literal;
-	if (!directive || dstrlen(directive->str) == 0) {
-		return 0;
-	}
-
-	directive->fn = bfs_printf_literal;
-	append_directive(tail, directive);
-
-	if (last) {
+static struct bfs_printf **append_literal(struct bfs_printf **tail, struct bfs_printf **literal) {
+	struct bfs_printf *directive = *literal;
+	if (directive && dstrlen(directive->str) > 0) {
 		*literal = NULL;
+		return append_directive(tail, directive);
 	} else {
-		*literal = new_directive();
-		if (!*literal) {
-			return -1;
-		}
+		return tail;
 	}
-
-	return 0;
 }
 
 struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline) {
-	struct bfs_printf *command = malloc(sizeof(*command));
-	if (!command) {
-		perror("malloc()");
-		return NULL;
-	}
+	struct bfs_printf *head = NULL;
+	struct bfs_printf **tail = &head;
 
-	command->directives = NULL;
-	command->needs_stat = false;
-	struct bfs_printf_directive **tail = &command->directives;
-
-	struct bfs_printf_directive *literal = new_directive();
+	struct bfs_printf *literal = new_directive(bfs_printf_literal);
 	if (!literal) {
 		goto error;
 	}
@@ -519,15 +578,12 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 			case '\\': c = '\\'; break;
 
 			case 'c':
-				if (append_literal(&tail, &literal, true) != 0) {
-					goto error;
-				}
-				struct bfs_printf_directive *directive = new_directive();
+				tail = append_literal(tail, &literal);
+				struct bfs_printf *directive = new_directive(bfs_printf_flush);
 				if (!directive) {
 					goto error;
 				}
-				directive->fn = bfs_printf_flush;
-				append_directive(&tail, directive);
+				tail = append_directive(tail, directive);
 				goto done;
 
 			case '\0':
@@ -544,7 +600,7 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 				goto one_char;
 			}
 
-			struct bfs_printf_directive *directive = new_directive();
+			struct bfs_printf *directive = new_directive(NULL);
 			if (!directive) {
 				goto directive_error;
 			}
@@ -606,16 +662,13 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 			case 'a':
 				directive->fn = bfs_printf_ctime;
 				directive->stat_field = BFS_STAT_ATIME;
-				command->needs_stat = true;
 				break;
 			case 'b':
 				directive->fn = bfs_printf_b;
-				command->needs_stat = true;
 				break;
 			case 'c':
 				directive->fn = bfs_printf_ctime;
 				directive->stat_field = BFS_STAT_CTIME;
-				command->needs_stat = true;
 				break;
 			case 'd':
 				directive->fn = bfs_printf_d;
@@ -623,7 +676,6 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 				break;
 			case 'D':
 				directive->fn = bfs_printf_D;
-				command->needs_stat = true;
 				break;
 			case 'f':
 				directive->fn = bfs_printf_f;
@@ -635,15 +687,12 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 				}
 				directive->fn = bfs_printf_F;
 				directive->mtab = cmdline->mtab;
-				command->needs_stat = true;
 				break;
 			case 'g':
 				directive->fn = bfs_printf_g;
-				command->needs_stat = true;
 				break;
 			case 'G':
 				directive->fn = bfs_printf_G;
-				command->needs_stat = true;
 				break;
 			case 'h':
 				directive->fn = bfs_printf_h;
@@ -653,11 +702,9 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 				break;
 			case 'i':
 				directive->fn = bfs_printf_i;
-				command->needs_stat = true;
 				break;
 			case 'k':
 				directive->fn = bfs_printf_k;
-				command->needs_stat = true;
 				break;
 			case 'l':
 				directive->fn = bfs_printf_l;
@@ -665,15 +712,12 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 			case 'm':
 				directive->fn = bfs_printf_m;
 				specifier = "o";
-				command->needs_stat = true;
 				break;
 			case 'M':
 				directive->fn = bfs_printf_M;
-				command->needs_stat = true;
 				break;
 			case 'n':
 				directive->fn = bfs_printf_n;
-				command->needs_stat = true;
 				break;
 			case 'p':
 				directive->fn = bfs_printf_p;
@@ -683,30 +727,24 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 				break;
 			case 's':
 				directive->fn = bfs_printf_s;
-				command->needs_stat = true;
 				break;
 			case 'S':
 				directive->fn = bfs_printf_S;
 				specifier = "g";
-				command->needs_stat = true;
 				break;
 			case 't':
 				directive->fn = bfs_printf_ctime;
 				directive->stat_field = BFS_STAT_MTIME;
-				command->needs_stat = true;
 				break;
 			case 'u':
 				directive->fn = bfs_printf_u;
-				command->needs_stat = true;
 				break;
 			case 'U':
 				directive->fn = bfs_printf_U;
-				command->needs_stat = true;
 				break;
 			case 'w':
 				directive->fn = bfs_printf_ctime;
 				directive->stat_field = BFS_STAT_BTIME;
-				command->needs_stat = true;
 				break;
 			case 'y':
 				directive->fn = bfs_printf_y;
@@ -731,7 +769,6 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 
 			directive_strftime:
 				directive->fn = bfs_printf_strftime;
-				command->needs_stat = true;
 				c = *++i;
 				if (!c) {
 					bfs_error(cmdline, "'%s': Incomplete time specifier '%s%c'.\n", format, directive->str, i[-1]);
@@ -763,10 +800,16 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 				goto directive_error;
 			}
 
-			if (append_literal(&tail, &literal, false) != 0) {
-				goto directive_error;
+			tail = append_literal(tail, &literal);
+			tail = append_directive(tail, directive);
+
+			if (!literal) {
+				literal = new_directive(bfs_printf_literal);
+				if (!literal) {
+					goto error;
+				}
 			}
-			append_directive(&tail, directive);
+
 			continue;
 
 		directive_error:
@@ -782,23 +825,24 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
 	}
 
 done:
-	if (append_literal(&tail, &literal, true) != 0) {
-		goto error;
+	tail = append_literal(tail, &literal);
+	if (head) {
+		free_directive(literal);
+		return head;
+	} else {
+		return literal;
 	}
 
-	free_directive(literal);
-	return command;
-
 error:
 	free_directive(literal);
-	free_bfs_printf(command);
+	free_bfs_printf(head);
 	return NULL;
 }
 
-int bfs_printf(FILE *file, const struct bfs_printf *command, const struct BFTW *ftwbuf) {
+int bfs_printf(FILE *file, const struct bfs_printf *command, struct BFTW *ftwbuf) {
 	int ret = 0, error = 0;
 
-	for (struct bfs_printf_directive *directive = command->directives; directive; directive = directive->next) {
+	for (const struct bfs_printf *directive = command; directive; directive = directive->next) {
 		if (directive->fn(file, directive, ftwbuf) < 0) {
 			ret = -1;
 			error = errno;
@@ -810,14 +854,9 @@ int bfs_printf(FILE *file, const struct bfs_printf *command, const struct BFTW *
 }
 
 void free_bfs_printf(struct bfs_printf *command) {
-	if (command) {
-		struct bfs_printf_directive *directive = command->directives;
-		while (directive) {
-			struct bfs_printf_directive *next = directive->next;
-			free_directive(directive);
-			directive = next;
-		}
-
-		free(command);
+	while (command) {
+		struct bfs_printf *next = command->next;
+		free_directive(command);
+		command = next;
 	}
 }
diff --git a/printf.h b/printf.h
index 1c3957e..d62770e 100644
--- a/printf.h
+++ b/printf.h
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2017-2018 Tavian Barnes <tavianator@tavianator.com>        *
+ * Copyright (C) 2017-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.                           *
@@ -22,22 +22,14 @@
 #define BFS_PRINTF_H
 
 #include "bftw.h"
-#include "color.h"
+#include "cmdline.h"
 #include <stdbool.h>
 #include <stdio.h>
 
-struct cmdline;
-struct bfs_printf_directive;
-
 /**
  * A printf command, the result of parsing a single format string.
  */
-struct bfs_printf {
-	/** The chain of printf directives. */
-	struct bfs_printf_directive *directives;
-	/** Whether the struct bfs_stat must be filled in. */
-	bool needs_stat;
-};
+struct bfs_printf;
 
 /**
  * Parse a -printf format string.
@@ -62,7 +54,7 @@ struct bfs_printf *parse_bfs_printf(const char *format, struct cmdline *cmdline)
  *         must be non-NULL.
  * @return 0 on success, -1 on failure.
  */
-int bfs_printf(FILE *file, const struct bfs_printf *command, const struct BFTW *ftwbuf);
+int bfs_printf(FILE *file, const struct bfs_printf *command, struct BFTW *ftwbuf);
 
 /**
  * Free a parsed format string.
diff --git a/tests.sh b/tests.sh
index d47d573..8716639 100755
--- a/tests.sh
+++ b/tests.sh
@@ -504,6 +504,7 @@ gnu_tests=(
     test_print_error
 
     test_printf
+    test_printf_empty
     test_printf_slash
     test_printf_slashes
     test_printf_trailing_slash
@@ -585,6 +586,7 @@ bfs_tests=(
     test_color_escapes
     test_color_nul
     test_color_ln_target
+    test_color_L_ln_target
     test_color_mh
     test_color_mh0
     test_color_or
@@ -1777,6 +1779,10 @@ function test_printf() {
     bfs_diff basic -printf '%%p(%p) %%d(%d) %%f(%f) %%h(%h) %%H(%H) %%P(%P) %%m(%m) %%M(%M) %%y(%y)\n'
 }
 
+function test_printf_empty() {
+    bfs_diff basic -printf ''
+}
+
 function test_printf_slash() {
     bfs_diff / -maxdepth 0 -printf '(%h)/(%f)\n'
 }
@@ -1954,6 +1960,10 @@ function test_color_ln_target() {
     LS_COLORS="ln=target:or=01;31:mi=01;33:" bfs_diff rainbow -color
 }
 
+function test_color_L_ln_target() {
+    LS_COLORS="ln=target:or=01;31:mi=01;33:" bfs_diff -L rainbow -color
+}
+
 function test_color_mh() {
     LS_COLORS="mh=01:" bfs_diff rainbow -color
 }
diff --git a/tests/test_color_L_ln_target.out b/tests/test_color_L_ln_target.out
new file mode 100644
index 0000000..cd4ec5e
--- /dev/null
+++ b/tests/test_color_L_ln_target.out
@@ -0,0 +1,20 @@
+[01;34mrainbow[0m
+[01;34mrainbow/[0m[01;31mbroken[0m
+[01;34mrainbow/[0m[01;32mexec.sh[0m
+[01;34mrainbow/[0m[01;33mchardev_link[0m
+[01;34mrainbow/[0m[01;35msocket[0m
+[01;34mrainbow/[0m[30;42msticky_ow[0m
+[01;34mrainbow/[0m[30;43msgid[0m
+[01;34mrainbow/[0m[33mpipe[0m
+[01;34mrainbow/[0m[34;42mow[0m
+[01;34mrainbow/[0m[37;41msugid[0m
+[01;34mrainbow/[0m[37;41msuid[0m
+[01;34mrainbow/[0m[37;44msticky[0m
+[01;34mrainbow/[0mfile.dat
+[01;34mrainbow/[0mfile.txt
+[01;34mrainbow/[0mlink.txt
+[01;34mrainbow/[0mmh1
+[01;34mrainbow/[0mmh2
+[01;34mrainbow/[0mstar.gz
+[01;34mrainbow/[0mstar.tar
+[01;34mrainbow/[0mstar.tar.gz