From 30e55d140074749809c419bba2a1a9fd1a4c7de9 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Fri, 25 Mar 2022 13:53:47 -0400
Subject: expr: Store auxilliary data in a union

And rename struct expr to bfs_expr.
---
 color.c |  24 ++-
 color.h |   4 +-
 ctx.c   |   4 +-
 ctx.h   |   4 +-
 eval.c  | 236 +++++++++++------------
 eval.h  | 110 +++++------
 expr.h  | 232 +++++++++++++----------
 opt.c   | 321 +++++++++++++++----------------
 parse.c | 657 ++++++++++++++++++++++++++++++++--------------------------------
 9 files changed, 815 insertions(+), 777 deletions(-)

diff --git a/color.c b/color.c
index 144e93c..ec4c178 100644
--- a/color.c
+++ b/color.c
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2015-2021 Tavian Barnes <tavianator@tavianator.com>        *
+ * Copyright (C) 2015-2022 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.                           *
@@ -868,12 +868,18 @@ BFS_FORMATTER(2, 3)
 static int cbuff(CFILE *cfile, const char *format, ...);
 
 /** Dump a parsed expression tree, for debugging. */
-static int print_expr(CFILE *cfile, const struct expr *expr, bool verbose) {
+static int print_expr(CFILE *cfile, const struct bfs_expr *expr, bool verbose) {
 	if (dstrcat(&cfile->buffer, "(") != 0) {
 		return -1;
 	}
 
-	if (expr->lhs || expr->rhs) {
+	const struct bfs_expr *lhs = NULL;
+	const struct bfs_expr *rhs = NULL;
+
+	if (bfs_expr_has_children(expr)) {
+		lhs = expr->lhs;
+		rhs = expr->rhs;
+
 		if (cbuff(cfile, "${red}%s${rs}", expr->argv[0]) < 0) {
 			return -1;
 		}
@@ -901,20 +907,20 @@ static int print_expr(CFILE *cfile, const struct expr *expr, bool verbose) {
 		}
 	}
 
-	if (expr->lhs) {
+	if (lhs) {
 		if (dstrcat(&cfile->buffer, " ") != 0) {
 			return -1;
 		}
-		if (print_expr(cfile, expr->lhs, verbose) != 0) {
+		if (print_expr(cfile, lhs, verbose) != 0) {
 			return -1;
 		}
 	}
 
-	if (expr->rhs) {
+	if (rhs) {
 		if (dstrcat(&cfile->buffer, " ") != 0) {
 			return -1;
 		}
-		if (print_expr(cfile, expr->rhs, verbose) != 0) {
+		if (print_expr(cfile, rhs, verbose) != 0) {
 			return -1;
 		}
 	}
@@ -1007,12 +1013,12 @@ static int cvbuff(CFILE *cfile, const char *format, va_list args) {
 					break;
 
 				case 'e':
-					if (print_expr(cfile, va_arg(args, const struct expr *), false) != 0) {
+					if (print_expr(cfile, va_arg(args, const struct bfs_expr *), false) != 0) {
 						return -1;
 					}
 					break;
 				case 'E':
-					if (print_expr(cfile, va_arg(args, const struct expr *), true) != 0) {
+					if (print_expr(cfile, va_arg(args, const struct bfs_expr *), true) != 0) {
 						return -1;
 					}
 					break;
diff --git a/color.h b/color.h
index 997fe00..36450bf 100644
--- a/color.h
+++ b/color.h
@@ -103,8 +103,8 @@ int cfclose(CFILE *cfile);
  *         %pF: A colored file name, from a const struct BFTW * argument
  *         %pP: A colored file path, from a const struct BFTW * argument
  *         %pL: A colored link target, from a const struct BFTW * argument
- *         %pe: Dump a const struct expr *, for debugging.
- *         %pE: Dump a const struct expr * in verbose form, for debugging.
+ *         %pe: Dump a const struct bfs_expr *, for debugging.
+ *         %pE: Dump a const struct bfs_expr * in verbose form, for debugging.
  *         %%: A literal '%'
  *         ${cc}: Change the color to 'cc'
  *         $$: A literal '$'
diff --git a/ctx.c b/ctx.c
index 15e7f4b..8ba2f38 100644
--- a/ctx.c
+++ b/ctx.c
@@ -262,8 +262,8 @@ int bfs_ctx_free(struct bfs_ctx *ctx) {
 		CFILE *cout = ctx->cout;
 		CFILE *cerr = ctx->cerr;
 
-		free_expr(ctx->expr);
-		free_expr(ctx->exclude);
+		bfs_expr_free(ctx->exclude);
+		bfs_expr_free(ctx->expr);
 
 		bfs_mtab_free(ctx->mtab);
 
diff --git a/ctx.h b/ctx.h
index 8f8101d..5d0daba 100644
--- a/ctx.h
+++ b/ctx.h
@@ -62,9 +62,9 @@ struct bfs_ctx {
 	/** The root paths. */
 	const char **paths;
 	/** The main command line expression. */
-	struct expr *expr;
+	struct bfs_expr *expr;
 	/** An expression for files to filter out. */
-	struct expr *exclude;
+	struct bfs_expr *exclude;
 
 	/** -mindepth option. */
 	int mindepth;
diff --git a/eval.c b/eval.c
index 41892d0..527c42e 100644
--- a/eval.c
+++ b/eval.c
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2015-2021 Tavian Barnes <tavianator@tavianator.com>        *
+ * Copyright (C) 2015-2022 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.                           *
@@ -55,7 +55,7 @@
 #include <unistd.h>
 #include <wchar.h>
 
-struct eval_state {
+struct bfs_eval {
 	/** Data about the current file. */
 	const struct BFTW *ftwbuf;
 	/** The bfs context. */
@@ -72,7 +72,7 @@ struct eval_state {
  * Print an error message.
  */
 BFS_FORMATTER(2, 3)
-static void eval_error(struct eval_state *state, const char *format, ...) {
+static void eval_error(struct bfs_eval *state, const char *format, ...) {
 	// By POSIX, any errors should be accompanied by a non-zero exit status
 	*state->ret = EXIT_FAILURE;
 
@@ -92,7 +92,7 @@ static void eval_error(struct eval_state *state, const char *format, ...) {
 /**
  * Check if an error should be ignored.
  */
-static bool eval_should_ignore(const struct eval_state *state, int error) {
+static bool eval_should_ignore(const struct bfs_eval *state, int error) {
 	return state->ctx->ignore_races
 		&& is_nonexistence_error(error)
 		&& state->ftwbuf->depth > 0;
@@ -101,7 +101,7 @@ static bool eval_should_ignore(const struct eval_state *state, int error) {
 /**
  * Report an error that occurs during evaluation.
  */
-static void eval_report_error(struct eval_state *state) {
+static void eval_report_error(struct bfs_eval *state) {
 	if (!eval_should_ignore(state, errno)) {
 		eval_error(state, "%m.\n");
 	}
@@ -110,7 +110,7 @@ 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) {
+static const struct bfs_stat *eval_stat(struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
 	const struct bfs_stat *ret = bftw_stat(ftwbuf, ftwbuf->stat_flags);
 	if (!ret) {
@@ -130,45 +130,46 @@ static time_t timespec_diff(const struct timespec *lhs, const struct timespec *r
 	return ret;
 }
 
-bool expr_cmp(const struct expr *expr, long long n) {
-	switch (expr->cmp_flag) {
-	case CMP_EXACT:
-		return n == expr->idata;
-	case CMP_LESS:
-		return n < expr->idata;
-	case CMP_GREATER:
-		return n > expr->idata;
+bool bfs_expr_cmp(const struct bfs_expr *expr, long long n) {
+	switch (expr->int_cmp) {
+	case BFS_INT_EQUAL:
+		return n == expr->num;
+	case BFS_INT_LESS:
+		return n < expr->num;
+	case BFS_INT_GREATER:
+		return n > expr->num;
 	}
 
+	assert(!"Invalid comparison mode");
 	return false;
 }
 
 /**
  * -true test.
  */
-bool eval_true(const struct expr *expr, struct eval_state *state) {
+bool eval_true(const struct bfs_expr *expr, struct bfs_eval *state) {
 	return true;
 }
 
 /**
  * -false test.
  */
-bool eval_false(const struct expr *expr, struct eval_state *state) {
+bool eval_false(const struct bfs_expr *expr, struct bfs_eval *state) {
 	return false;
 }
 
 /**
  * -executable, -readable, -writable tests.
  */
-bool eval_access(const struct expr *expr, struct eval_state *state) {
+bool eval_access(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
-	return xfaccessat(ftwbuf->at_fd, ftwbuf->at_path, expr->idata) == 0;
+	return xfaccessat(ftwbuf->at_fd, ftwbuf->at_path, expr->num) == 0;
 }
 
 /**
  * -acl test.
  */
-bool eval_acl(const struct expr *expr, struct eval_state *state) {
+bool eval_acl(const struct bfs_expr *expr, struct bfs_eval *state) {
 	int ret = bfs_check_acl(state->ftwbuf);
 	if (ret >= 0) {
 		return ret;
@@ -181,7 +182,7 @@ bool eval_acl(const struct expr *expr, struct eval_state *state) {
 /**
  * -capable test.
  */
-bool eval_capable(const struct expr *expr, struct eval_state *state) {
+bool eval_capable(const struct bfs_expr *expr, struct bfs_eval *state) {
 	int ret = bfs_check_capabilities(state->ftwbuf);
 	if (ret >= 0) {
 		return ret;
@@ -194,7 +195,7 @@ bool eval_capable(const struct expr *expr, struct eval_state *state) {
 /**
  * Get the given timespec field out of a stat buffer.
  */
-static const struct timespec *eval_stat_time(const struct bfs_stat *statbuf, enum bfs_stat_field field, struct eval_state *state) {
+static const struct timespec *eval_stat_time(const struct bfs_stat *statbuf, enum bfs_stat_field field, struct bfs_eval *state) {
 	const struct timespec *ret = bfs_stat_time(statbuf, field);
 	if (!ret) {
 		eval_error(state, "Couldn't get file %s: %m.\n", bfs_stat_field_name(field));
@@ -205,7 +206,7 @@ static const struct timespec *eval_stat_time(const struct bfs_stat *statbuf, enu
 /**
  * -[aBcm]?newer tests.
  */
-bool eval_newer(const struct expr *expr, struct eval_state *state) {
+bool eval_newer(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -223,7 +224,7 @@ bool eval_newer(const struct expr *expr, struct eval_state *state) {
 /**
  * -[aBcm]{min,time} tests.
  */
-bool eval_time(const struct expr *expr, struct eval_state *state) {
+bool eval_time(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -236,23 +237,23 @@ bool eval_time(const struct expr *expr, struct eval_state *state) {
 
 	time_t diff = timespec_diff(&expr->reftime, time);
 	switch (expr->time_unit) {
-	case DAYS:
+	case BFS_DAYS:
 		diff /= 60*24;
 		BFS_FALLTHROUGH;
-	case MINUTES:
+	case BFS_MINUTES:
 		diff /= 60;
 		BFS_FALLTHROUGH;
-	case SECONDS:
+	case BFS_SECONDS:
 		break;
 	}
 
-	return expr_cmp(expr, diff);
+	return bfs_expr_cmp(expr, diff);
 }
 
 /**
  * -used test.
  */
-bool eval_used(const struct expr *expr, struct eval_state *state) {
+bool eval_used(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -271,37 +272,37 @@ bool eval_used(const struct expr *expr, struct eval_state *state) {
 
 	long long day_seconds = 60*60*24;
 	diff = (diff + day_seconds - 1) / day_seconds;
-	return expr_cmp(expr, diff);
+	return bfs_expr_cmp(expr, diff);
 }
 
 /**
  * -gid test.
  */
-bool eval_gid(const struct expr *expr, struct eval_state *state) {
+bool eval_gid(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
 	}
 
-	return expr_cmp(expr, statbuf->gid);
+	return bfs_expr_cmp(expr, statbuf->gid);
 }
 
 /**
  * -uid test.
  */
-bool eval_uid(const struct expr *expr, struct eval_state *state) {
+bool eval_uid(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
 	}
 
-	return expr_cmp(expr, statbuf->uid);
+	return bfs_expr_cmp(expr, statbuf->uid);
 }
 
 /**
  * -nogroup test.
  */
-bool eval_nogroup(const struct expr *expr, struct eval_state *state) {
+bool eval_nogroup(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -319,7 +320,7 @@ bool eval_nogroup(const struct expr *expr, struct eval_state *state) {
 /**
  * -nouser test.
  */
-bool eval_nouser(const struct expr *expr, struct eval_state *state) {
+bool eval_nouser(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -337,7 +338,7 @@ bool eval_nouser(const struct expr *expr, struct eval_state *state) {
 /**
  * -delete action.
  */
-bool eval_delete(const struct expr *expr, struct eval_state *state) {
+bool eval_delete(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
 
 	// Don't try to delete the current directory
@@ -365,28 +366,33 @@ bool eval_delete(const struct expr *expr, struct eval_state *state) {
 }
 
 /** Finish any pending -exec ... + operations. */
-static int eval_exec_finish(const struct expr *expr, const struct bfs_ctx *ctx) {
+static int eval_exec_finish(const struct bfs_expr *expr, const struct bfs_ctx *ctx) {
 	int ret = 0;
-	if (expr->execbuf && bfs_exec_finish(expr->execbuf) != 0) {
-		if (errno != 0) {
-			bfs_error(ctx, "%s %s: %m.\n", expr->argv[0], expr->argv[1]);
+
+	if (expr->eval_fn == eval_exec) {
+		if (bfs_exec_finish(expr->exec) != 0) {
+			if (errno != 0) {
+				bfs_error(ctx, "%s %s: %m.\n", expr->argv[0], expr->argv[1]);
+			}
+			ret = -1;
+		}
+	} else if (bfs_expr_has_children(expr)) {
+		if (expr->lhs && eval_exec_finish(expr->lhs, ctx) != 0) {
+			ret = -1;
+		}
+		if (expr->rhs && eval_exec_finish(expr->rhs, ctx) != 0) {
+			ret = -1;
 		}
-		ret = -1;
-	}
-	if (expr->lhs && eval_exec_finish(expr->lhs, ctx) != 0) {
-		ret = -1;
-	}
-	if (expr->rhs && eval_exec_finish(expr->rhs, ctx) != 0) {
-		ret = -1;
 	}
+
 	return ret;
 }
 
 /**
  * -exec[dir]/-ok[dir] actions.
  */
-bool eval_exec(const struct expr *expr, struct eval_state *state) {
-	bool ret = bfs_exec(expr->execbuf, state->ftwbuf) == 0;
+bool eval_exec(const struct bfs_expr *expr, struct bfs_eval *state) {
+	bool ret = bfs_exec(expr->exec, state->ftwbuf) == 0;
 	if (errno != 0) {
 		eval_error(state, "%s %s: %m.\n", expr->argv[0], expr->argv[1]);
 	}
@@ -396,9 +402,9 @@ bool eval_exec(const struct expr *expr, struct eval_state *state) {
 /**
  * -exit action.
  */
-bool eval_exit(const struct expr *expr, struct eval_state *state) {
+bool eval_exit(const struct bfs_expr *expr, struct bfs_eval *state) {
 	state->action = BFTW_STOP;
-	*state->ret = expr->idata;
+	*state->ret = expr->num;
 	state->quit = true;
 	return true;
 }
@@ -406,14 +412,14 @@ bool eval_exit(const struct expr *expr, struct eval_state *state) {
 /**
  * -depth N test.
  */
-bool eval_depth(const struct expr *expr, struct eval_state *state) {
-	return expr_cmp(expr, state->ftwbuf->depth);
+bool eval_depth(const struct bfs_expr *expr, struct bfs_eval *state) {
+	return bfs_expr_cmp(expr, state->ftwbuf->depth);
 }
 
 /**
  * -empty test.
  */
-bool eval_empty(const struct expr *expr, struct eval_state *state) {
+bool eval_empty(const struct bfs_expr *expr, struct bfs_eval *state) {
 	bool ret = false;
 	const struct BFTW *ftwbuf = state->ftwbuf;
 
@@ -446,7 +452,7 @@ done:
 /**
  * -flags test.
  */
-bool eval_flags(const struct expr *expr, struct eval_state *state) {
+bool eval_flags(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -461,14 +467,14 @@ bool eval_flags(const struct expr *expr, struct eval_state *state) {
 	unsigned long set = expr->set_flags;
 	unsigned long clear = expr->clear_flags;
 
-	switch (expr->mode_cmp) {
-	case MODE_EXACT:
+	switch (expr->flags_cmp) {
+	case BFS_MODE_EQUAL:
 		return flags == set && !(flags & clear);
 
-	case MODE_ALL:
+	case BFS_MODE_ALL:
 		return (flags & set) == set && !(flags & clear);
 
-	case MODE_ANY:
+	case BFS_MODE_ANY:
 		return (flags & set) || (flags & clear) != clear;
 	}
 
@@ -479,7 +485,7 @@ bool eval_flags(const struct expr *expr, struct eval_state *state) {
 /**
  * -fstype test.
  */
-bool eval_fstype(const struct expr *expr, struct eval_state *state) {
+bool eval_fstype(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -492,13 +498,13 @@ bool eval_fstype(const struct expr *expr, struct eval_state *state) {
 	}
 
 	const char *type = bfs_fstype(mtab, statbuf);
-	return strcmp(type, expr->sdata) == 0;
+	return strcmp(type, expr->argv[1]) == 0;
 }
 
 /**
  * -hidden test.
  */
-bool eval_hidden(const struct expr *expr, struct eval_state *state) {
+bool eval_hidden(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
 	const char *name = ftwbuf->path + ftwbuf->nameoff;
 
@@ -513,31 +519,31 @@ bool eval_hidden(const struct expr *expr, struct eval_state *state) {
 /**
  * -inum test.
  */
-bool eval_inum(const struct expr *expr, struct eval_state *state) {
+bool eval_inum(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
 	}
 
-	return expr_cmp(expr, statbuf->ino);
+	return bfs_expr_cmp(expr, statbuf->ino);
 }
 
 /**
  * -links test.
  */
-bool eval_links(const struct expr *expr, struct eval_state *state) {
+bool eval_links(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
 	}
 
-	return expr_cmp(expr, statbuf->nlink);
+	return bfs_expr_cmp(expr, statbuf->nlink);
 }
 
 /**
  * -i?lname test.
  */
-bool eval_lname(const struct expr *expr, struct eval_state *state) {
+bool eval_lname(const struct bfs_expr *expr, struct bfs_eval *state) {
 	bool ret = false;
 	char *name = NULL;
 
@@ -555,7 +561,7 @@ bool eval_lname(const struct expr *expr, struct eval_state *state) {
 		goto done;
 	}
 
-	ret = fnmatch(expr->sdata, name, expr->idata) == 0;
+	ret = fnmatch(expr->argv[1], name, expr->num) == 0;
 
 done:
 	free(name);
@@ -565,7 +571,7 @@ done:
 /**
  * -i?name test.
  */
-bool eval_name(const struct expr *expr, struct eval_state *state) {
+bool eval_name(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
 
 	const char *name = ftwbuf->path + ftwbuf->nameoff;
@@ -584,7 +590,7 @@ bool eval_name(const struct expr *expr, struct eval_state *state) {
 		}
 	}
 
-	bool ret = fnmatch(expr->sdata, name, expr->idata) == 0;
+	bool ret = fnmatch(expr->argv[1], name, expr->num) == 0;
 	free(copy);
 	return ret;
 }
@@ -592,15 +598,15 @@ bool eval_name(const struct expr *expr, struct eval_state *state) {
 /**
  * -i?path test.
  */
-bool eval_path(const struct expr *expr, struct eval_state *state) {
+bool eval_path(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
-	return fnmatch(expr->sdata, ftwbuf->path, expr->idata) == 0;
+	return fnmatch(expr->argv[1], ftwbuf->path, expr->num) == 0;
 }
 
 /**
  * -perm test.
  */
-bool eval_perm(const struct expr *expr, struct eval_state *state) {
+bool eval_perm(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -615,13 +621,13 @@ bool eval_perm(const struct expr *expr, struct eval_state *state) {
 	}
 
 	switch (expr->mode_cmp) {
-	case MODE_EXACT:
+	case BFS_MODE_EQUAL:
 		return (mode & 07777) == target;
 
-	case MODE_ALL:
+	case BFS_MODE_ALL:
 		return (mode & target) == target;
 
-	case MODE_ANY:
+	case BFS_MODE_ANY:
 		return !(mode & target) == !target;
 	}
 
@@ -632,7 +638,7 @@ bool eval_perm(const struct expr *expr, struct eval_state *state) {
 /**
  * -f?ls action.
  */
-bool eval_fls(const struct expr *expr, struct eval_state *state) {
+bool eval_fls(const struct bfs_expr *expr, struct bfs_eval *state) {
 	CFILE *cfile = expr->cfile;
 	FILE *file = cfile->file;
 	const struct bfs_users *users = bfs_ctx_users(state->ctx);
@@ -737,7 +743,7 @@ error:
 /**
  * -f?print action.
  */
-bool eval_fprint(const struct expr *expr, struct eval_state *state) {
+bool eval_fprint(const struct bfs_expr *expr, struct bfs_eval *state) {
 	if (cfprintf(expr->cfile, "%pP\n", state->ftwbuf) < 0) {
 		eval_report_error(state);
 	}
@@ -747,7 +753,7 @@ bool eval_fprint(const struct expr *expr, struct eval_state *state) {
 /**
  * -f?print0 action.
  */
-bool eval_fprint0(const struct expr *expr, struct eval_state *state) {
+bool eval_fprint0(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const char *path = state->ftwbuf->path;
 	size_t length = strlen(path) + 1;
 	if (fwrite(path, 1, length, expr->cfile->file) != length) {
@@ -759,7 +765,7 @@ 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) {
+bool eval_fprintf(const struct bfs_expr *expr, struct bfs_eval *state) {
 	if (bfs_printf(expr->cfile, expr->printf, state->ftwbuf) != 0) {
 		eval_report_error(state);
 	}
@@ -770,7 +776,7 @@ bool eval_fprintf(const struct expr *expr, struct eval_state *state) {
 /**
  * -printx action.
  */
-bool eval_fprintx(const struct expr *expr, struct eval_state *state) {
+bool eval_fprintx(const struct bfs_expr *expr, struct bfs_eval *state) {
 	FILE *file = expr->cfile->file;
 	const char *path = state->ftwbuf->path;
 
@@ -808,7 +814,7 @@ error:
 /**
  * -prune action.
  */
-bool eval_prune(const struct expr *expr, struct eval_state *state) {
+bool eval_prune(const struct bfs_expr *expr, struct bfs_eval *state) {
 	state->action = BFTW_PRUNE;
 	return true;
 }
@@ -816,7 +822,7 @@ bool eval_prune(const struct expr *expr, struct eval_state *state) {
 /**
  * -quit action.
  */
-bool eval_quit(const struct expr *expr, struct eval_state *state) {
+bool eval_quit(const struct bfs_expr *expr, struct bfs_eval *state) {
 	state->action = BFTW_STOP;
 	state->quit = true;
 	return true;
@@ -825,7 +831,7 @@ bool eval_quit(const struct expr *expr, struct eval_state *state) {
 /**
  * -i?regex test.
  */
-bool eval_regex(const struct expr *expr, struct eval_state *state) {
+bool eval_regex(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const char *path = state->ftwbuf->path;
 
 	int ret = bfs_regexec(expr->regex, path, BFS_REGEX_ANCHOR);
@@ -845,7 +851,7 @@ bool eval_regex(const struct expr *expr, struct eval_state *state) {
 /**
  * -samefile test.
  */
-bool eval_samefile(const struct expr *expr, struct eval_state *state) {
+bool eval_samefile(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -857,32 +863,32 @@ bool eval_samefile(const struct expr *expr, struct eval_state *state) {
 /**
  * -size test.
  */
-bool eval_size(const struct expr *expr, struct eval_state *state) {
+bool eval_size(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
 	}
 
 	static const off_t scales[] = {
-		[SIZE_BLOCKS] = 512,
-		[SIZE_BYTES] = 1,
-		[SIZE_WORDS] = 2,
-		[SIZE_KB] = 1LL << 10,
-		[SIZE_MB] = 1LL << 20,
-		[SIZE_GB] = 1LL << 30,
-		[SIZE_TB] = 1LL << 40,
-		[SIZE_PB] = 1LL << 50,
+		[BFS_BLOCKS] = 512,
+		[BFS_BYTES] = 1,
+		[BFS_WORDS] = 2,
+		[BFS_KB] = 1LL << 10,
+		[BFS_MB] = 1LL << 20,
+		[BFS_GB] = 1LL << 30,
+		[BFS_TB] = 1LL << 40,
+		[BFS_PB] = 1LL << 50,
 	};
 
 	off_t scale = scales[expr->size_unit];
 	off_t size = (statbuf->size + scale - 1)/scale; // Round up
-	return expr_cmp(expr, size);
+	return bfs_expr_cmp(expr, size);
 }
 
 /**
  * -sparse test.
  */
-bool eval_sparse(const struct expr *expr, struct eval_state *state) {
+bool eval_sparse(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -895,14 +901,14 @@ bool eval_sparse(const struct expr *expr, struct eval_state *state) {
 /**
  * -type test.
  */
-bool eval_type(const struct expr *expr, struct eval_state *state) {
-	return (1 << state->ftwbuf->type) & expr->idata;
+bool eval_type(const struct bfs_expr *expr, struct bfs_eval *state) {
+	return (1 << state->ftwbuf->type) & expr->num;
 }
 
 /**
  * -xattr test.
  */
-bool eval_xattr(const struct expr *expr, struct eval_state *state) {
+bool eval_xattr(const struct bfs_expr *expr, struct bfs_eval *state) {
 	int ret = bfs_check_xattrs(state->ftwbuf);
 	if (ret >= 0) {
 		return ret;
@@ -913,10 +919,10 @@ bool eval_xattr(const struct expr *expr, struct eval_state *state) {
 }
 
 /**
- * -xattr test.
+ * -xattrname test.
  */
-bool eval_xattrname(const struct expr *expr, struct eval_state *state) {
-	int ret = bfs_check_xattr_named(state->ftwbuf, expr->sdata);
+bool eval_xattrname(const struct bfs_expr *expr, struct bfs_eval *state) {
+	int ret = bfs_check_xattr_named(state->ftwbuf, expr->argv[1]);
 	if (ret >= 0) {
 		return ret;
 	} else {
@@ -928,7 +934,7 @@ bool eval_xattrname(const struct expr *expr, struct eval_state *state) {
 /**
  * -xtype test.
  */
-bool eval_xtype(const struct expr *expr, struct eval_state *state) {
+bool eval_xtype(const struct bfs_expr *expr, struct bfs_eval *state) {
 	const struct BFTW *ftwbuf = state->ftwbuf;
 	enum bfs_stat_flags flags = ftwbuf->stat_flags ^ (BFS_STAT_NOFOLLOW | BFS_STAT_TRYFOLLOW);
 	enum bfs_type type = bftw_type(ftwbuf, flags);
@@ -936,7 +942,7 @@ bool eval_xtype(const struct expr *expr, struct eval_state *state) {
 		eval_report_error(state);
 		return false;
 	} else {
-		return (1 << type) & expr->idata;
+		return (1 << type) & expr->num;
 	}
 }
 
@@ -949,7 +955,7 @@ bool eval_xtype(const struct expr *expr, struct eval_state *state) {
 /**
  * Call clock_gettime(), if available.
  */
-static int eval_gettime(struct eval_state *state, struct timespec *ts) {
+static int eval_gettime(struct bfs_eval *state, struct timespec *ts) {
 #ifdef BFS_CLOCK
 	int ret = clock_gettime(BFS_CLOCK, ts);
 	if (ret != 0) {
@@ -979,7 +985,7 @@ static void timespec_elapsed(struct timespec *elapsed, const struct timespec *st
 /**
  * Evaluate an expression.
  */
-static bool eval_expr(struct expr *expr, struct eval_state *state) {
+static bool eval_expr(struct bfs_expr *expr, struct bfs_eval *state) {
 	struct timespec start, end;
 	bool time = state->ctx->debug & DEBUG_RATES;
 	if (time) {
@@ -990,7 +996,7 @@ static bool eval_expr(struct expr *expr, struct eval_state *state) {
 
 	assert(!state->quit);
 
-	bool ret = expr->eval(expr, state);
+	bool ret = expr->eval_fn(expr, state);
 
 	if (time) {
 		if (eval_gettime(state, &end) == 0) {
@@ -1003,7 +1009,7 @@ static bool eval_expr(struct expr *expr, struct eval_state *state) {
 		++expr->successes;
 	}
 
-	if (expr_never_returns(expr)) {
+	if (bfs_expr_never_returns(expr)) {
 		assert(state->quit);
 	} else if (!state->quit) {
 		assert(!expr->always_true || ret);
@@ -1016,14 +1022,14 @@ static bool eval_expr(struct expr *expr, struct eval_state *state) {
 /**
  * Evaluate a negation.
  */
-bool eval_not(const struct expr *expr, struct eval_state *state) {
+bool eval_not(const struct bfs_expr *expr, struct bfs_eval *state) {
 	return !eval_expr(expr->rhs, state);
 }
 
 /**
  * Evaluate a conjunction.
  */
-bool eval_and(const struct expr *expr, struct eval_state *state) {
+bool eval_and(const struct bfs_expr *expr, struct bfs_eval *state) {
 	if (!eval_expr(expr->lhs, state)) {
 		return false;
 	}
@@ -1038,7 +1044,7 @@ bool eval_and(const struct expr *expr, struct eval_state *state) {
 /**
  * Evaluate a disjunction.
  */
-bool eval_or(const struct expr *expr, struct eval_state *state) {
+bool eval_or(const struct bfs_expr *expr, struct bfs_eval *state) {
 	if (eval_expr(expr->lhs, state)) {
 		return true;
 	}
@@ -1053,7 +1059,7 @@ bool eval_or(const struct expr *expr, struct eval_state *state) {
 /**
  * Evaluate the comma operator.
  */
-bool eval_comma(const struct expr *expr, struct eval_state *state) {
+bool eval_comma(const struct bfs_expr *expr, struct bfs_eval *state) {
 	eval_expr(expr->lhs, state);
 
 	if (state->quit) {
@@ -1064,7 +1070,7 @@ bool eval_comma(const struct expr *expr, struct eval_state *state) {
 }
 
 /** Update the status bar. */
-static void eval_status(struct eval_state *state, struct bfs_bar *bar, struct timespec *last_status, size_t count) {
+static void eval_status(struct bfs_eval *state, struct bfs_bar *bar, struct timespec *last_status, size_t count) {
 	struct timespec now;
 	if (eval_gettime(state, &now) == 0) {
 		struct timespec elapsed = {0};
@@ -1168,7 +1174,7 @@ out_rhs:
 }
 
 /** Check if we've seen a file before. */
-static bool eval_file_unique(struct eval_state *state, struct trie *seen) {
+static bool eval_file_unique(struct bfs_eval *state, struct trie *seen) {
 	const struct bfs_stat *statbuf = eval_stat(state);
 	if (!statbuf) {
 		return false;
@@ -1333,7 +1339,7 @@ static enum bftw_action eval_callback(const struct BFTW *ftwbuf, void *ptr) {
 
 	const struct bfs_ctx *ctx = args->ctx;
 
-	struct eval_state state;
+	struct bfs_eval state;
 	state.ftwbuf = ftwbuf;
 	state.ctx = ctx;
 	state.action = BFTW_CONTINUE;
diff --git a/eval.h b/eval.h
index 533857c..a1bbd2f 100644
--- a/eval.h
+++ b/eval.h
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2015-2018 Tavian Barnes <tavianator@tavianator.com>        *
+ * Copyright (C) 2015-2022 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.                           *
@@ -25,12 +25,12 @@
 #include <stdbool.h>
 
 struct bfs_ctx;
-struct expr;
+struct bfs_expr;
 
 /**
  * Ephemeral state for evaluating an expression.
  */
-struct eval_state;
+struct bfs_eval;
 
 /**
  * Expression evaluation function.
@@ -42,7 +42,7 @@ struct eval_state;
  * @return
  *         The result of the test.
  */
-typedef bool eval_fn(const struct expr *expr, struct eval_state *state);
+typedef bool bfs_eval_fn(const struct bfs_expr *expr, struct bfs_eval *state);
 
 /**
  * Evaluate the command line.
@@ -56,58 +56,58 @@ int bfs_eval(const struct bfs_ctx *ctx);
 
 // Predicate evaluation functions
 
-bool eval_true(const struct expr *expr, struct eval_state *state);
-bool eval_false(const struct expr *expr, struct eval_state *state);
-
-bool eval_access(const struct expr *expr, struct eval_state *state);
-bool eval_acl(const struct expr *expr, struct eval_state *state);
-bool eval_capable(const struct expr *expr, struct eval_state *state);
-bool eval_perm(const struct expr *expr, struct eval_state *state);
-bool eval_xattr(const struct expr *expr, struct eval_state *state);
-bool eval_xattrname(const struct expr *expr, struct eval_state *state);
-
-bool eval_newer(const struct expr *expr, struct eval_state *state);
-bool eval_time(const struct expr *expr, struct eval_state *state);
-bool eval_used(const struct expr *expr, struct eval_state *state);
-
-bool eval_gid(const struct expr *expr, struct eval_state *state);
-bool eval_uid(const struct expr *expr, struct eval_state *state);
-bool eval_nogroup(const struct expr *expr, struct eval_state *state);
-bool eval_nouser(const struct expr *expr, struct eval_state *state);
-
-bool eval_depth(const struct expr *expr, struct eval_state *state);
-bool eval_empty(const struct expr *expr, struct eval_state *state);
-bool eval_flags(const struct expr *expr, struct eval_state *state);
-bool eval_fstype(const struct expr *expr, struct eval_state *state);
-bool eval_hidden(const struct expr *expr, struct eval_state *state);
-bool eval_inum(const struct expr *expr, struct eval_state *state);
-bool eval_links(const struct expr *expr, struct eval_state *state);
-bool eval_samefile(const struct expr *expr, struct eval_state *state);
-bool eval_size(const struct expr *expr, struct eval_state *state);
-bool eval_sparse(const struct expr *expr, struct eval_state *state);
-bool eval_type(const struct expr *expr, struct eval_state *state);
-bool eval_xtype(const struct expr *expr, struct eval_state *state);
-
-bool eval_lname(const struct expr *expr, struct eval_state *state);
-bool eval_name(const struct expr *expr, struct eval_state *state);
-bool eval_path(const struct expr *expr, struct eval_state *state);
-bool eval_regex(const struct expr *expr, struct eval_state *state);
-
-bool eval_delete(const struct expr *expr, struct eval_state *state);
-bool eval_exec(const struct expr *expr, struct eval_state *state);
-bool eval_exit(const struct expr *expr, struct eval_state *state);
-bool eval_fls(const struct expr *expr, struct eval_state *state);
-bool eval_fprint(const struct expr *expr, struct eval_state *state);
-bool eval_fprint0(const struct expr *expr, struct eval_state *state);
-bool eval_fprintf(const struct expr *expr, struct eval_state *state);
-bool eval_fprintx(const struct expr *expr, struct eval_state *state);
-bool eval_prune(const struct expr *expr, struct eval_state *state);
-bool eval_quit(const struct expr *expr, struct eval_state *state);
+bool eval_true(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_false(const struct bfs_expr *expr, struct bfs_eval *state);
+
+bool eval_access(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_acl(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_capable(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_perm(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_xattr(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_xattrname(const struct bfs_expr *expr, struct bfs_eval *state);
+
+bool eval_newer(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_time(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_used(const struct bfs_expr *expr, struct bfs_eval *state);
+
+bool eval_gid(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_uid(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_nogroup(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_nouser(const struct bfs_expr *expr, struct bfs_eval *state);
+
+bool eval_depth(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_empty(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_flags(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_fstype(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_hidden(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_inum(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_links(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_samefile(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_size(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_sparse(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_type(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_xtype(const struct bfs_expr *expr, struct bfs_eval *state);
+
+bool eval_lname(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_name(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_path(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_regex(const struct bfs_expr *expr, struct bfs_eval *state);
+
+bool eval_delete(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_exec(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_exit(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_fls(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_fprint(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_fprint0(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_fprintf(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_fprintx(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_prune(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_quit(const struct bfs_expr *expr, struct bfs_eval *state);
 
 // Operator evaluation functions
-bool eval_not(const struct expr *expr, struct eval_state *state);
-bool eval_and(const struct expr *expr, struct eval_state *state);
-bool eval_or(const struct expr *expr, struct eval_state *state);
-bool eval_comma(const struct expr *expr, struct eval_state *state);
+bool eval_not(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_and(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_or(const struct bfs_expr *expr, struct bfs_eval *state);
+bool eval_comma(const struct bfs_expr *expr, struct bfs_eval *state);
 
 #endif // BFS_EVAL_H
diff --git a/expr.h b/expr.h
index 23a6f41..b825ca1 100644
--- a/expr.h
+++ b/expr.h
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2015-2018 Tavian Barnes <tavianator@tavianator.com>        *
+ * Copyright (C) 2015-2022 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.                           *
@@ -23,84 +23,86 @@
 
 #include "color.h"
 #include "eval.h"
-#include "exec.h"
-#include "printf.h"
 #include "stat.h"
-#include "xregex.h"
 #include <stdbool.h>
 #include <stddef.h>
 #include <sys/types.h>
 #include <time.h>
 
 /**
- * Possible types of numeric comparison.
+ * Integer comparison modes.
  */
-enum cmp_flag {
-	/** Exactly n. */
-	CMP_EXACT,
-	/** Less than n. */
-	CMP_LESS,
-	/** Greater than n. */
-	CMP_GREATER,
+enum bfs_int_cmp {
+	/** Exactly N. */
+	BFS_INT_EQUAL,
+	/** Less than N (-N). */
+	BFS_INT_LESS,
+	/** Greater than N (+N). */
+	BFS_INT_GREATER,
 };
 
 /**
- * Possible types of mode comparison.
+ * Permission comparison modes.
  */
-enum mode_cmp {
+enum bfs_mode_cmp {
 	/** Mode is an exact match (MODE). */
-	MODE_EXACT,
+	BFS_MODE_EQUAL,
 	/** Mode has all these bits (-MODE). */
-	MODE_ALL,
+	BFS_MODE_ALL,
 	/** Mode has any of these bits (/MODE). */
-	MODE_ANY,
+	BFS_MODE_ANY,
 };
 
 /**
  * Possible time units.
  */
-enum time_unit {
+enum bfs_time_unit {
 	/** Seconds. */
-	SECONDS,
+	BFS_SECONDS,
 	/** Minutes. */
-	MINUTES,
+	BFS_MINUTES,
 	/** Days. */
-	DAYS,
+	BFS_DAYS,
 };
 
 /**
  * Possible file size units.
  */
-enum size_unit {
+enum bfs_size_unit {
 	/** 512-byte blocks. */
-	SIZE_BLOCKS,
+	BFS_BLOCKS,
 	/** Single bytes. */
-	SIZE_BYTES,
+	BFS_BYTES,
 	/** Two-byte words. */
-	SIZE_WORDS,
+	BFS_WORDS,
 	/** Kibibytes. */
-	SIZE_KB,
+	BFS_KB,
 	/** Mebibytes. */
-	SIZE_MB,
+	BFS_MB,
 	/** Gibibytes. */
-	SIZE_GB,
+	BFS_GB,
 	/** Tebibytes. */
-	SIZE_TB,
+	BFS_TB,
 	/** Pebibytes. */
-	SIZE_PB,
+	BFS_PB,
 };
 
 /**
  * A command line expression.
  */
-struct expr {
+struct bfs_expr {
 	/** The function that evaluates this expression. */
-	eval_fn *eval;
+	bfs_eval_fn *eval_fn;
 
-	/** The left hand side of the expression. */
-	struct expr *lhs;
-	/** The right hand side of the expression. */
-	struct expr *rhs;
+	/** The number of command line arguments for this expression. */
+	size_t argc;
+	/** The command line arguments comprising this expression. */
+	char **argv;
+
+	/** The number of files this expression keeps open between evaluations. */
+	int persistent_fds;
+	/** The number of files this expression opens during evaluation. */
+	int ephemeral_fds;
 
 	/** Whether this expression has no side effects. */
 	bool pure;
@@ -110,98 +112,122 @@ struct expr {
 	bool always_false;
 
 	/** Estimated cost. */
-	double cost;
+	float cost;
 	/** Estimated probability of success. */
-	double probability;
-	/** Number of times this predicate was executed. */
+	float probability;
+	/** Number of times this predicate was evaluated. */
 	size_t evaluations;
 	/** Number of times this predicate succeeded. */
 	size_t successes;
 	/** Total time spent running this predicate. */
 	struct timespec elapsed;
 
-	/** The number of command line arguments for this expression. */
-	size_t argc;
-	/** The command line arguments comprising this expression. */
-	char **argv;
-
-	/** The optional comparison flag. */
-	enum cmp_flag cmp_flag;
-
-	/** The mode comparison flag. */
-	enum mode_cmp mode_cmp;
-	/** Mode to use for files. */
-	mode_t file_mode;
-	/** Mode to use for directories (different due to X). */
-	mode_t dir_mode;
-
-	/** Flags that should be set. */
-	unsigned long long set_flags;
-	/** Flags that should be cleared. */
-	unsigned long long clear_flags;
-
-	/** The optional stat field to look at. */
-	enum bfs_stat_field stat_field;
-	/** The optional reference time. */
-	struct timespec reftime;
-	/** The optional time unit. */
-	enum time_unit time_unit;
-
-	/** The optional size unit. */
-	enum size_unit size_unit;
-
-	/** Optional device number for a target file. */
-	dev_t dev;
-	/** Optional inode number for a target file. */
-	ino_t ino;
-
-	/** File to output to. */
-	CFILE *cfile;
-
-	/** Optional compiled regex. */
-	struct bfs_regex *regex;
-
-	/** Optional exec command. */
-	struct bfs_exec *execbuf;
-
-	/** Optional printf command. */
-	struct bfs_printf *printf;
-
-	/** Optional integer data for this expression. */
-	long long idata;
-
-	/** Optional string data for this expression. */
-	const char *sdata;
-
-	/** The number of files this expression keeps open between evaluations. */
-	int persistent_fds;
-	/** The number of files this expression opens during evaluation. */
-	int ephemeral_fds;
+	/** Auxilliary data for the evaluation function. */
+	union {
+		/** Child expressions. */
+		struct {
+			/** The left hand side of the expression. */
+			struct bfs_expr *lhs;
+			/** The right hand side of the expression. */
+			struct bfs_expr *rhs;
+		};
+
+		/** Integer comparisons. */
+		struct {
+			/** Integer for this comparison. */
+			long long num;
+			/** The comparison mode. */
+			enum bfs_int_cmp int_cmp;
+
+			/** Optional extra data. */
+			union {
+				/** -size data. */
+				enum bfs_size_unit size_unit;
+
+				/** Timestamp comparison data. */
+				struct {
+					/** The stat field to look at. */
+					enum bfs_stat_field stat_field;
+					/** The reference time. */
+					struct timespec reftime;
+					/** The time unit. */
+					enum bfs_time_unit time_unit;
+				};
+			};
+		};
+
+		/** Printing actions. */
+		struct {
+			/** The output stream. */
+			CFILE *cfile;
+			/** Optional -printf format. */
+			struct bfs_printf *printf;
+		};
+
+		/** -exec data. */
+		struct bfs_exec *exec;
+
+		/** -flags data. */
+		struct {
+			/** The comparison mode. */
+			enum bfs_mode_cmp flags_cmp;
+			/** Flags that should be set. */
+			unsigned long long set_flags;
+			/** Flags that should be cleared. */
+			unsigned long long clear_flags;
+		};
+
+		/** -perm data. */
+		struct {
+			/** The comparison mode. */
+			enum bfs_mode_cmp mode_cmp;
+			/** Mode to use for files. */
+			mode_t file_mode;
+			/** Mode to use for directories (different due to X). */
+			mode_t dir_mode;
+		};
+
+		/** -regex data. */
+		struct bfs_regex *regex;
+
+		/** -samefile data. */
+		struct {
+			/** Device number of the target file. */
+			dev_t dev;
+			/** Inode number of the target file. */
+			ino_t ino;
+		};
+	};
 };
 
 /** Singleton true expression instance. */
-extern struct expr expr_true;
+extern struct bfs_expr bfs_true;
 /** Singleton false expression instance. */
-extern struct expr expr_false;
+extern struct bfs_expr bfs_false;
 
 /**
  * Create a new expression.
  */
-struct expr *new_expr(eval_fn *eval, size_t argc, char **argv);
+struct bfs_expr *bfs_expr_new(bfs_eval_fn *eval, size_t argc, char **argv);
+
+/**
+ * @return Whether the expression has child expressions.
+ */
+bool bfs_expr_has_children(const struct bfs_expr *expr);
 
 /**
  * @return Whether expr is known to always quit.
  */
-bool expr_never_returns(const struct expr *expr);
+bool bfs_expr_never_returns(const struct bfs_expr *expr);
 
 /**
- * @return The result of the comparison for this expression.
+ * @return The result of the integer comparison for this expression.
  */
-bool expr_cmp(const struct expr *expr, long long n);
+bool bfs_expr_cmp(const struct bfs_expr *expr, long long n);
 
 /**
  * Free an expression tree.
  */
-void free_expr(struct expr *expr);
+void bfs_expr_free(struct bfs_expr *expr);
 
 #endif // BFS_EXPR_H
diff --git a/opt.c b/opt.c
index 96b99da..886c49a 100644
--- a/opt.c
+++ b/opt.c
@@ -1,6 +1,6 @@
 /****************************************************************************
  * bfs                                                                      *
- * Copyright (C) 2017-2020 Tavian Barnes <tavianator@tavianator.com>        *
+ * Copyright (C) 2017-2022 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.                           *
@@ -333,65 +333,66 @@ static bool debug_opt(const struct opt_state *state, int level, const char *form
 }
 
 /** Extract a child expression, freeing the outer expression. */
-static struct expr *extract_child_expr(struct expr *expr, struct expr **child) {
-	struct expr *ret = *child;
+static struct bfs_expr *extract_child_expr(struct bfs_expr *expr, struct bfs_expr **child) {
+	struct bfs_expr *ret = *child;
 	*child = NULL;
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return ret;
 }
 
 /**
  * Negate an expression.
  */
-static struct expr *negate_expr(struct expr *rhs, char **argv) {
-	if (rhs->eval == eval_not) {
+static struct bfs_expr *negate_expr(struct bfs_expr *rhs, char **argv) {
+	if (rhs->eval_fn == eval_not) {
 		return extract_child_expr(rhs, &rhs->rhs);
 	}
 
-	struct expr *expr = new_expr(eval_not, 1, argv);
+	struct bfs_expr *expr = bfs_expr_new(eval_not, 1, argv);
 	if (!expr) {
-		free_expr(rhs);
+		bfs_expr_free(rhs);
 		return NULL;
 	}
 
+	expr->lhs = NULL;
 	expr->rhs = rhs;
 	return expr;
 }
 
-static struct expr *optimize_not_expr(const struct opt_state *state, struct expr *expr);
-static struct expr *optimize_and_expr(const struct opt_state *state, struct expr *expr);
-static struct expr *optimize_or_expr(const struct opt_state *state, struct expr *expr);
+static struct bfs_expr *optimize_not_expr(const struct opt_state *state, struct bfs_expr *expr);
+static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct bfs_expr *expr);
+static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct bfs_expr *expr);
 
 /**
  * Apply De Morgan's laws.
  */
-static struct expr *de_morgan(const struct opt_state *state, struct expr *expr, char **argv) {
+static struct bfs_expr *de_morgan(const struct opt_state *state, struct bfs_expr *expr, char **argv) {
 	bool debug = debug_opt(state, 1, "De Morgan's laws: %pe ", expr);
 
-	struct expr *parent = negate_expr(expr, argv);
+	struct bfs_expr *parent = negate_expr(expr, argv);
 	if (!parent) {
 		return NULL;
 	}
 
 	bool has_parent = true;
-	if (parent->eval != eval_not) {
+	if (parent->eval_fn != eval_not) {
 		expr = parent;
 		has_parent = false;
 	}
 
-	assert(expr->eval == eval_and || expr->eval == eval_or);
-	if (expr->eval == eval_and) {
-		expr->eval = eval_or;
+	assert(expr->eval_fn == eval_and || expr->eval_fn == eval_or);
+	if (expr->eval_fn == eval_and) {
+		expr->eval_fn = eval_or;
 		expr->argv = &fake_or_arg;
 	} else {
-		expr->eval = eval_and;
+		expr->eval_fn = eval_and;
 		expr->argv = &fake_and_arg;
 	}
 
 	expr->lhs = negate_expr(expr->lhs, argv);
 	expr->rhs = negate_expr(expr->rhs, argv);
 	if (!expr->lhs || !expr->rhs) {
-		free_expr(parent);
+		bfs_expr_free(parent);
 		return NULL;
 	}
 
@@ -399,18 +400,18 @@ static struct expr *de_morgan(const struct opt_state *state, struct expr *expr,
 		cfprintf(state->ctx->cerr, "<==> %pe\n", parent);
 	}
 
-	if (expr->lhs->eval == eval_not) {
+	if (expr->lhs->eval_fn == eval_not) {
 		expr->lhs = optimize_not_expr(state, expr->lhs);
 	}
-	if (expr->rhs->eval == eval_not) {
+	if (expr->rhs->eval_fn == eval_not) {
 		expr->rhs = optimize_not_expr(state, expr->rhs);
 	}
 	if (!expr->lhs || !expr->rhs) {
-		free_expr(parent);
+		bfs_expr_free(parent);
 		return NULL;
 	}
 
-	if (expr->eval == eval_and) {
+	if (expr->eval_fn == eval_and) {
 		expr = optimize_and_expr(state, expr);
 	} else {
 		expr = optimize_or_expr(state, expr);
@@ -421,7 +422,7 @@ static struct expr *de_morgan(const struct opt_state *state, struct expr *expr,
 		parent = expr;
 	}
 	if (!expr) {
-		free_expr(parent);
+		bfs_expr_free(parent);
 		return NULL;
 	}
 
@@ -432,34 +433,34 @@ static struct expr *de_morgan(const struct opt_state *state, struct expr *expr,
 }
 
 /** Optimize an expression recursively. */
-static struct expr *optimize_expr_recursive(struct opt_state *state, struct expr *expr);
+static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct bfs_expr *expr);
 
 /**
  * Optimize a negation.
  */
-static struct expr *optimize_not_expr(const struct opt_state *state, struct expr *expr) {
-	assert(expr->eval == eval_not);
+static struct bfs_expr *optimize_not_expr(const struct opt_state *state, struct bfs_expr *expr) {
+	assert(expr->eval_fn == eval_not);
 
-	struct expr *rhs = expr->rhs;
+	struct bfs_expr *rhs = expr->rhs;
 
 	int optlevel = state->ctx->optlevel;
 	if (optlevel >= 1) {
-		if (rhs == &expr_true) {
-			debug_opt(state, 1, "constant propagation: %pe <==> %pe\n", expr, &expr_false);
-			free_expr(expr);
-			return &expr_false;
-		} else if (rhs == &expr_false) {
-			debug_opt(state, 1, "constant propagation: %pe <==> %pe\n", expr, &expr_true);
-			free_expr(expr);
-			return &expr_true;
-		} else if (rhs->eval == eval_not) {
+		if (rhs == &bfs_true) {
+			debug_opt(state, 1, "constant propagation: %pe <==> %pe\n", expr, &bfs_false);
+			bfs_expr_free(expr);
+			return &bfs_false;
+		} else if (rhs == &bfs_false) {
+			debug_opt(state, 1, "constant propagation: %pe <==> %pe\n", expr, &bfs_true);
+			bfs_expr_free(expr);
+			return &bfs_true;
+		} else if (rhs->eval_fn == eval_not) {
 			debug_opt(state, 1, "double negation: %pe <==> %pe\n", expr, rhs->rhs);
 			return extract_child_expr(expr, &rhs->rhs);
-		} else if (expr_never_returns(rhs)) {
+		} else if (bfs_expr_never_returns(rhs)) {
 			debug_opt(state, 1, "reachability: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
-		} else if ((rhs->eval == eval_and || rhs->eval == eval_or)
-			   && (rhs->lhs->eval == eval_not || rhs->rhs->eval == eval_not)) {
+		} else if ((rhs->eval_fn == eval_and || rhs->eval_fn == eval_or)
+			   && (rhs->lhs->eval_fn == eval_not || rhs->rhs->eval_fn == eval_not)) {
 			return de_morgan(state, expr, expr->argv);
 		}
 	}
@@ -474,7 +475,7 @@ static struct expr *optimize_not_expr(const struct opt_state *state, struct expr
 }
 
 /** Optimize a negation recursively. */
-static struct expr *optimize_not_expr_recursive(struct opt_state *state, struct expr *expr) {
+static struct bfs_expr *optimize_not_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
 	struct opt_state rhs_state = *state;
 	expr->rhs = optimize_expr_recursive(&rhs_state, expr->rhs);
 	if (!expr->rhs) {
@@ -487,41 +488,41 @@ static struct expr *optimize_not_expr_recursive(struct opt_state *state, struct
 	return optimize_not_expr(state, expr);
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /** Optimize a conjunction. */
-static struct expr *optimize_and_expr(const struct opt_state *state, struct expr *expr) {
-	assert(expr->eval == eval_and);
+static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct bfs_expr *expr) {
+	assert(expr->eval_fn == eval_and);
 
-	struct expr *lhs = expr->lhs;
-	struct expr *rhs = expr->rhs;
+	struct bfs_expr *lhs = expr->lhs;
+	struct bfs_expr *rhs = expr->rhs;
 
 	const struct bfs_ctx *ctx = state->ctx;
 	int optlevel = ctx->optlevel;
 	if (optlevel >= 1) {
-		if (lhs == &expr_true) {
+		if (lhs == &bfs_true) {
 			debug_opt(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
-		} else if (rhs == &expr_true) {
+		} else if (rhs == &bfs_true) {
 			debug_opt(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
 		} else if (lhs->always_false) {
 			debug_opt(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
-		} else if (lhs->always_true && rhs == &expr_false) {
+		} else if (lhs->always_true && rhs == &bfs_false) {
 			bool debug = debug_opt(state, 1, "strength reduction: %pe <==> ", expr);
-			struct expr *ret = extract_child_expr(expr, &expr->lhs);
+			struct bfs_expr *ret = extract_child_expr(expr, &expr->lhs);
 			ret = negate_expr(ret, &fake_not_arg);
 			if (debug && ret) {
 				cfprintf(ctx->cerr, "%pe\n", ret);
 			}
 			return ret;
-		} else if (optlevel >= 2 && lhs->pure && rhs == &expr_false) {
+		} else if (optlevel >= 2 && lhs->pure && rhs == &bfs_false) {
 			debug_opt(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
-		} else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+		} else if (lhs->eval_fn == eval_not && rhs->eval_fn == eval_not) {
 			return de_morgan(state, expr, expr->lhs->argv);
 		}
 	}
@@ -536,7 +537,7 @@ static struct expr *optimize_and_expr(const struct opt_state *state, struct expr
 }
 
 /** Optimize a conjunction recursively. */
-static struct expr *optimize_and_expr_recursive(struct opt_state *state, struct expr *expr) {
+static struct bfs_expr *optimize_and_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
 	struct opt_state lhs_state = *state;
 	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
 	if (!expr->lhs) {
@@ -556,16 +557,16 @@ static struct expr *optimize_and_expr_recursive(struct opt_state *state, struct
 	return optimize_and_expr(state, expr);
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /** Optimize a disjunction. */
-static struct expr *optimize_or_expr(const struct opt_state *state, struct expr *expr) {
-	assert(expr->eval == eval_or);
+static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct bfs_expr *expr) {
+	assert(expr->eval_fn == eval_or);
 
-	struct expr *lhs = expr->lhs;
-	struct expr *rhs = expr->rhs;
+	struct bfs_expr *lhs = expr->lhs;
+	struct bfs_expr *rhs = expr->rhs;
 
 	const struct bfs_ctx *ctx = state->ctx;
 	int optlevel = ctx->optlevel;
@@ -573,24 +574,24 @@ static struct expr *optimize_or_expr(const struct opt_state *state, struct expr
 		if (lhs->always_true) {
 			debug_opt(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
-		} else if (lhs == &expr_false) {
+		} else if (lhs == &bfs_false) {
 			debug_opt(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
-		} else if (rhs == &expr_false) {
+		} else if (rhs == &bfs_false) {
 			debug_opt(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
-		} else if (lhs->always_false && rhs == &expr_true) {
+		} else if (lhs->always_false && rhs == &bfs_true) {
 			bool debug = debug_opt(state, 1, "strength reduction: %pe <==> ", expr);
-			struct expr *ret = extract_child_expr(expr, &expr->lhs);
+			struct bfs_expr *ret = extract_child_expr(expr, &expr->lhs);
 			ret = negate_expr(ret, &fake_not_arg);
 			if (debug && ret) {
 				cfprintf(ctx->cerr, "%pe\n", ret);
 			}
 			return ret;
-		} else if (optlevel >= 2 && lhs->pure && rhs == &expr_true) {
+		} else if (optlevel >= 2 && lhs->pure && rhs == &bfs_true) {
 			debug_opt(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
-		} else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+		} else if (lhs->eval_fn == eval_not && rhs->eval_fn == eval_not) {
 			return de_morgan(state, expr, expr->lhs->argv);
 		}
 	}
@@ -605,7 +606,7 @@ static struct expr *optimize_or_expr(const struct opt_state *state, struct expr
 }
 
 /** Optimize a disjunction recursively. */
-static struct expr *optimize_or_expr_recursive(struct opt_state *state, struct expr *expr) {
+static struct bfs_expr *optimize_or_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
 	struct opt_state lhs_state = *state;
 	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
 	if (!expr->lhs) {
@@ -625,21 +626,21 @@ static struct expr *optimize_or_expr_recursive(struct opt_state *state, struct e
 	return optimize_or_expr(state, expr);
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /** Optimize an expression in an ignored-result context. */
-static struct expr *ignore_result(const struct opt_state *state, struct expr *expr) {
+static struct bfs_expr *ignore_result(const struct opt_state *state, struct bfs_expr *expr) {
 	int optlevel = state->ctx->optlevel;
 
 	if (optlevel >= 1) {
 		while (true) {
-			if (expr->eval == eval_not) {
+			if (expr->eval_fn == eval_not) {
 				debug_opt(state, 1, "ignored result: %pe --> %pe\n", expr, expr->rhs);
 				expr = extract_child_expr(expr, &expr->rhs);
 			} else if (optlevel >= 2
-			           && (expr->eval == eval_and || expr->eval == eval_or || expr->eval == eval_comma)
+			           && (expr->eval_fn == eval_and || expr->eval_fn == eval_or || expr->eval_fn == eval_comma)
 			           && expr->rhs->pure) {
 				debug_opt(state, 2, "ignored result: %pe --> %pe\n", expr, expr->lhs);
 				expr = extract_child_expr(expr, &expr->lhs);
@@ -648,10 +649,10 @@ static struct expr *ignore_result(const struct opt_state *state, struct expr *ex
 			}
 		}
 
-		if (optlevel >= 2 && expr->pure && expr != &expr_false) {
-			debug_opt(state, 2, "ignored result: %pe --> %pe\n", expr, &expr_false);
-			free_expr(expr);
-			expr = &expr_false;
+		if (optlevel >= 2 && expr->pure && expr != &bfs_false) {
+			debug_opt(state, 2, "ignored result: %pe --> %pe\n", expr, &bfs_false);
+			bfs_expr_free(expr);
+			expr = &bfs_false;
 		}
 	}
 
@@ -659,21 +660,21 @@ static struct expr *ignore_result(const struct opt_state *state, struct expr *ex
 }
 
 /** Optimize a comma expression. */
-static struct expr *optimize_comma_expr(const struct opt_state *state, struct expr *expr) {
-	assert(expr->eval == eval_comma);
+static struct bfs_expr *optimize_comma_expr(const struct opt_state *state, struct bfs_expr *expr) {
+	assert(expr->eval_fn == eval_comma);
 
-	struct expr *lhs = expr->lhs;
-	struct expr *rhs = expr->rhs;
+	struct bfs_expr *lhs = expr->lhs;
+	struct bfs_expr *rhs = expr->rhs;
 
 	int optlevel = state->ctx->optlevel;
 	if (optlevel >= 1) {
 		lhs = expr->lhs = ignore_result(state, lhs);
 
-		if (expr_never_returns(lhs)) {
+		if (bfs_expr_never_returns(lhs)) {
 			debug_opt(state, 1, "reachability: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
-		} else if ((lhs->always_true && rhs == &expr_true)
-			   || (lhs->always_false && rhs == &expr_false)) {
+		} else if ((lhs->always_true && rhs == &bfs_true)
+			   || (lhs->always_false && rhs == &bfs_false)) {
 			debug_opt(state, 1, "redundancy elimination: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
 		} else if (optlevel >= 2 && lhs->pure) {
@@ -683,8 +684,8 @@ static struct expr *optimize_comma_expr(const struct opt_state *state, struct ex
 	}
 
 	expr->pure = lhs->pure && rhs->pure;
-	expr->always_true = expr_never_returns(lhs) || rhs->always_true;
-	expr->always_false = expr_never_returns(lhs) || rhs->always_false;
+	expr->always_true = bfs_expr_never_returns(lhs) || rhs->always_true;
+	expr->always_false = bfs_expr_never_returns(lhs) || rhs->always_false;
 	expr->cost = lhs->cost + rhs->cost;
 	expr->probability = rhs->probability;
 
@@ -692,7 +693,7 @@ static struct expr *optimize_comma_expr(const struct opt_state *state, struct ex
 }
 
 /** Optimize a comma expression recursively. */
-static struct expr *optimize_comma_expr_recursive(struct opt_state *state, struct expr *expr) {
+static struct bfs_expr *optimize_comma_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
 	struct opt_state lhs_state = *state;
 	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
 	if (!expr->lhs) {
@@ -709,7 +710,7 @@ static struct expr *optimize_comma_expr_recursive(struct opt_state *state, struc
 	return optimize_comma_expr(state, expr);
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
@@ -720,38 +721,38 @@ static void infer_pred_facts(struct opt_state *state, enum pred_type pred) {
 }
 
 /** Infer data flow facts about an -{execut,read,writ}able expression. */
-static void infer_access_facts(struct opt_state *state, const struct expr *expr) {
-	if (expr->idata & R_OK) {
+static void infer_access_facts(struct opt_state *state, const struct bfs_expr *expr) {
+	if (expr->num & R_OK) {
 		infer_pred_facts(state, READABLE_PRED);
 	}
-	if (expr->idata & W_OK) {
+	if (expr->num & W_OK) {
 		infer_pred_facts(state, WRITABLE_PRED);
 	}
-	if (expr->idata & X_OK) {
+	if (expr->num & X_OK) {
 		infer_pred_facts(state, EXECUTABLE_PRED);
 	}
 }
 
 /** Infer data flow facts about an icmp-style ([+-]N) expression. */
-static void infer_icmp_facts(struct opt_state *state, const struct expr *expr, enum range_type type) {
+static void infer_icmp_facts(struct opt_state *state, const struct bfs_expr *expr, enum range_type type) {
 	struct range *range_when_true = &state->facts_when_true.ranges[type];
-	struct range *range_when_false =& state->facts_when_false.ranges[type];
-	long long value = expr->idata;
+	struct range *range_when_false = &state->facts_when_false.ranges[type];
+	long long value = expr->num;
 
-	switch (expr->cmp_flag) {
-	case CMP_EXACT:
+	switch (expr->int_cmp) {
+	case BFS_INT_EQUAL:
 		constrain_min(range_when_true, value);
 		constrain_max(range_when_true, value);
 		range_remove(range_when_false, value);
 		break;
 
-	case CMP_LESS:
+	case BFS_INT_LESS:
 		constrain_min(range_when_false, value);
 		constrain_max(range_when_true, value);
 		range_remove(range_when_true, value);
 		break;
 
-	case CMP_GREATER:
+	case BFS_INT_GREATER:
 		constrain_max(range_when_false, value);
 		constrain_min(range_when_true, value);
 		range_remove(range_when_true, value);
@@ -760,7 +761,7 @@ static void infer_icmp_facts(struct opt_state *state, const struct expr *expr, e
 }
 
 /** Infer data flow facts about a -gid expression. */
-static void infer_gid_facts(struct opt_state *state, const struct expr *expr) {
+static void infer_gid_facts(struct opt_state *state, const struct bfs_expr *expr) {
 	infer_icmp_facts(state, expr, GID_RANGE);
 
 	const struct bfs_groups *groups = bfs_ctx_groups(state->ctx);
@@ -773,7 +774,7 @@ static void infer_gid_facts(struct opt_state *state, const struct expr *expr) {
 }
 
 /** Infer data flow facts about a -uid expression. */
-static void infer_uid_facts(struct opt_state *state, const struct expr *expr) {
+static void infer_uid_facts(struct opt_state *state, const struct bfs_expr *expr) {
 	infer_icmp_facts(state, expr, UID_RANGE);
 
 	const struct bfs_users *users = bfs_ctx_users(state->ctx);
@@ -786,84 +787,84 @@ static void infer_uid_facts(struct opt_state *state, const struct expr *expr) {
 }
 
 /** Infer data flow facts about a -samefile expression. */
-static void infer_samefile_facts(struct opt_state *state, const struct expr *expr) {
+static void infer_samefile_facts(struct opt_state *state, const struct bfs_expr *expr) {
 	struct range *range_when_true = &state->facts_when_true.ranges[INUM_RANGE];
 	constrain_min(range_when_true, expr->ino);
 	constrain_max(range_when_true, expr->ino);
 }
 
 /** Infer data flow facts about a -type expression. */
-static void infer_type_facts(struct opt_state *state, const struct expr *expr) {
-	state->facts_when_true.types &= expr->idata;
-	state->facts_when_false.types &= ~expr->idata;
+static void infer_type_facts(struct opt_state *state, const struct bfs_expr *expr) {
+	state->facts_when_true.types &= expr->num;
+	state->facts_when_false.types &= ~expr->num;
 }
 
 /** Infer data flow facts about an -xtype expression. */
-static void infer_xtype_facts(struct opt_state *state, const struct expr *expr) {
-	state->facts_when_true.xtypes &= expr->idata;
-	state->facts_when_false.xtypes &= ~expr->idata;
+static void infer_xtype_facts(struct opt_state *state, const struct bfs_expr *expr) {
+	state->facts_when_true.xtypes &= expr->num;
+	state->facts_when_false.xtypes &= ~expr->num;
 }
 
-static struct expr *optimize_expr_recursive(struct opt_state *state, struct expr *expr) {
+static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
 	int optlevel = state->ctx->optlevel;
 
 	state->facts_when_true = state->facts;
 	state->facts_when_false = state->facts;
 
 	if (optlevel >= 2 && facts_are_impossible(&state->facts)) {
-		debug_opt(state, 2, "reachability: %pe --> %pe\n", expr, &expr_false);
-		free_expr(expr);
-		expr = &expr_false;
+		debug_opt(state, 2, "reachability: %pe --> %pe\n", expr, &bfs_false);
+		bfs_expr_free(expr);
+		expr = &bfs_false;
 		goto done;
 	}
 
-	if (!expr->rhs && !expr->pure) {
+	if (!bfs_expr_has_children(expr) && !expr->pure) {
 		facts_union(state->facts_when_impure, state->facts_when_impure, &state->facts);
 	}
 
-	if (expr->eval == eval_access) {
+	if (expr->eval_fn == eval_access) {
 		infer_access_facts(state, expr);
-	} else if (expr->eval == eval_acl) {
+	} else if (expr->eval_fn == eval_acl) {
 		infer_pred_facts(state, ACL_PRED);
-	} else if (expr->eval == eval_capable) {
+	} else if (expr->eval_fn == eval_capable) {
 		infer_pred_facts(state, CAPABLE_PRED);
-	} else if (expr->eval == eval_depth) {
+	} else if (expr->eval_fn == eval_depth) {
 		infer_icmp_facts(state, expr, DEPTH_RANGE);
-	} else if (expr->eval == eval_empty) {
+	} else if (expr->eval_fn == eval_empty) {
 		infer_pred_facts(state, EMPTY_PRED);
-	} else if (expr->eval == eval_gid) {
+	} else if (expr->eval_fn == eval_gid) {
 		infer_gid_facts(state, expr);
-	} else if (expr->eval == eval_hidden) {
+	} else if (expr->eval_fn == eval_hidden) {
 		infer_pred_facts(state, HIDDEN_PRED);
-	} else if (expr->eval == eval_inum) {
+	} else if (expr->eval_fn == eval_inum) {
 		infer_icmp_facts(state, expr, INUM_RANGE);
-	} else if (expr->eval == eval_links) {
+	} else if (expr->eval_fn == eval_links) {
 		infer_icmp_facts(state, expr, LINKS_RANGE);
-	} else if (expr->eval == eval_nogroup) {
+	} else if (expr->eval_fn == eval_nogroup) {
 		infer_pred_facts(state, NOGROUP_PRED);
-	} else if (expr->eval == eval_nouser) {
+	} else if (expr->eval_fn == eval_nouser) {
 		infer_pred_facts(state, NOUSER_PRED);
-	} else if (expr->eval == eval_samefile) {
+	} else if (expr->eval_fn == eval_samefile) {
 		infer_samefile_facts(state, expr);
-	} else if (expr->eval == eval_size) {
+	} else if (expr->eval_fn == eval_size) {
 		infer_icmp_facts(state, expr, SIZE_RANGE);
-	} else if (expr->eval == eval_sparse) {
+	} else if (expr->eval_fn == eval_sparse) {
 		infer_pred_facts(state, SPARSE_PRED);
-	} else if (expr->eval == eval_type) {
+	} else if (expr->eval_fn == eval_type) {
 		infer_type_facts(state, expr);
-	} else if (expr->eval == eval_uid) {
+	} else if (expr->eval_fn == eval_uid) {
 		infer_uid_facts(state, expr);
-	} else if (expr->eval == eval_xattr) {
+	} else if (expr->eval_fn == eval_xattr) {
 		infer_pred_facts(state, XATTR_PRED);
-	} else if (expr->eval == eval_xtype) {
+	} else if (expr->eval_fn == eval_xtype) {
 		infer_xtype_facts(state, expr);
-	} else if (expr->eval == eval_not) {
+	} else if (expr->eval_fn == eval_not) {
 		expr = optimize_not_expr_recursive(state, expr);
-	} else if (expr->eval == eval_and) {
+	} else if (expr->eval_fn == eval_and) {
 		expr = optimize_and_expr_recursive(state, expr);
-	} else if (expr->eval == eval_or) {
+	} else if (expr->eval_fn == eval_or) {
 		expr = optimize_or_expr_recursive(state, expr);
-	} else if (expr->eval == eval_comma) {
+	} else if (expr->eval_fn == eval_comma) {
 		expr = optimize_comma_expr_recursive(state, expr);
 	}
 
@@ -871,16 +872,18 @@ static struct expr *optimize_expr_recursive(struct opt_state *state, struct expr
 		goto done;
 	}
 
-	struct expr *lhs = expr->lhs;
-	struct expr *rhs = expr->rhs;
-	if (rhs) {
-		expr->persistent_fds = rhs->persistent_fds;
-		expr->ephemeral_fds = rhs->ephemeral_fds;
-	}
-	if (lhs) {
-		expr->persistent_fds += lhs->persistent_fds;
-		if (lhs->ephemeral_fds > expr->ephemeral_fds) {
-			expr->ephemeral_fds = lhs->ephemeral_fds;
+	if (bfs_expr_has_children(expr)) {
+		struct bfs_expr *lhs = expr->lhs;
+		struct bfs_expr *rhs = expr->rhs;
+		if (rhs) {
+			expr->persistent_fds = rhs->persistent_fds;
+			expr->ephemeral_fds = rhs->ephemeral_fds;
+		}
+		if (lhs) {
+			expr->persistent_fds += lhs->persistent_fds;
+			if (lhs->ephemeral_fds > expr->ephemeral_fds) {
+				expr->ephemeral_fds = lhs->ephemeral_fds;
+			}
 		}
 	}
 
@@ -891,24 +894,24 @@ static struct expr *optimize_expr_recursive(struct opt_state *state, struct expr
 		set_facts_impossible(&state->facts_when_true);
 	}
 
-	if (optlevel < 2 || expr == &expr_true || expr == &expr_false) {
+	if (optlevel < 2 || expr == &bfs_true || expr == &bfs_false) {
 		goto done;
 	}
 
 	if (facts_are_impossible(&state->facts_when_true)) {
 		if (expr->pure) {
-			debug_opt(state, 2, "data flow: %pe --> %pe\n", expr, &expr_false);
-			free_expr(expr);
-			expr = &expr_false;
+			debug_opt(state, 2, "data flow: %pe --> %pe\n", expr, &bfs_false);
+			bfs_expr_free(expr);
+			expr = &bfs_false;
 		} else {
 			expr->always_false = true;
 			expr->probability = 0.0;
 		}
 	} else if (facts_are_impossible(&state->facts_when_false)) {
 		if (expr->pure) {
-			debug_opt(state, 2, "data flow: %pe --> %pe\n", expr, &expr_true);
-			free_expr(expr);
-			expr = &expr_true;
+			debug_opt(state, 2, "data flow: %pe --> %pe\n", expr, &bfs_true);
+			bfs_expr_free(expr);
+			expr = &bfs_true;
 		} else {
 			expr->always_true = true;
 			expr->probability = 1.0;
@@ -920,10 +923,10 @@ done:
 }
 
 /** Swap the children of a binary expression if it would reduce the cost. */
-static bool reorder_expr(const struct opt_state *state, struct expr *expr, double swapped_cost) {
+static bool reorder_expr(const struct opt_state *state, struct bfs_expr *expr, double swapped_cost) {
 	if (swapped_cost < expr->cost) {
 		bool debug = debug_opt(state, 3, "cost: %pe <==> ", expr);
-		struct expr *lhs = expr->lhs;
+		struct bfs_expr *lhs = expr->lhs;
 		expr->lhs = expr->rhs;
 		expr->rhs = lhs;
 		if (debug) {
@@ -944,11 +947,15 @@ static bool reorder_expr(const struct opt_state *state, struct expr *expr, doubl
  * @return
  *         Whether any subexpression was reordered.
  */
-static bool reorder_expr_recursive(const struct opt_state *state, struct expr *expr) {
-	bool ret = false;
-	struct expr *lhs = expr->lhs;
-	struct expr *rhs = expr->rhs;
+static bool reorder_expr_recursive(const struct opt_state *state, struct bfs_expr *expr) {
+	if (!bfs_expr_has_children(expr)) {
+		return false;
+	}
 
+	struct bfs_expr *lhs = expr->lhs;
+	struct bfs_expr *rhs = expr->rhs;
+
+	bool ret = false;
 	if (lhs) {
 		ret |= reorder_expr_recursive(state, lhs);
 	}
@@ -956,9 +963,9 @@ static bool reorder_expr_recursive(const struct opt_state *state, struct expr *e
 		ret |= reorder_expr_recursive(state, rhs);
 	}
 
-	if (expr->eval == eval_and || expr->eval == eval_or) {
+	if (expr->eval_fn == eval_and || expr->eval_fn == eval_or) {
 		if (lhs->pure && rhs->pure) {
-			double rhs_prob = expr->eval == eval_and ? rhs->probability : 1.0 - rhs->probability;
+			double rhs_prob = expr->eval_fn == eval_and ? rhs->probability : 1.0 - rhs->probability;
 			double swapped_cost = rhs->cost + rhs_prob*lhs->cost;
 			ret |= reorder_expr(state, expr, swapped_cost);
 		}
@@ -970,7 +977,7 @@ static bool reorder_expr_recursive(const struct opt_state *state, struct expr *e
 /**
  * Optimize a top-level expression.
  */
-static struct expr *optimize_expr(struct opt_state *state, struct expr *expr) {
+static struct bfs_expr *optimize_expr(struct opt_state *state, struct bfs_expr *expr) {
 	struct opt_facts saved_impure = *state->facts_when_impure;
 
 	expr = optimize_expr_recursive(state, expr);
diff --git a/parse.c b/parse.c
index 04789da..2db2277 100644
--- a/parse.c
+++ b/parse.c
@@ -73,58 +73,57 @@ static char *fake_true_arg = "-true";
 #define STAT_COST   1000.0
 #define PRINT_COST 20000.0
 
-struct expr expr_true = {
-	.eval = eval_true,
-	.lhs = NULL,
-	.rhs = NULL,
+struct bfs_expr bfs_true = {
+	.eval_fn = eval_true,
+	.argc = 1,
+	.argv = &fake_true_arg,
 	.pure = true,
 	.always_true = true,
 	.cost = FAST_COST,
 	.probability = 1.0,
-	.argc = 1,
-	.argv = &fake_true_arg,
 };
 
-struct expr expr_false = {
-	.eval = eval_false,
-	.lhs = NULL,
-	.rhs = NULL,
+struct bfs_expr bfs_false = {
+	.eval_fn = eval_false,
+	.argc = 1,
+	.argv = &fake_false_arg,
 	.pure = true,
 	.always_false = true,
 	.cost = FAST_COST,
 	.probability = 0.0,
-	.argc = 1,
-	.argv = &fake_false_arg,
 };
 
-/**
- * Free an expression.
- */
-void free_expr(struct expr *expr) {
-	if (!expr || expr == &expr_true || expr == &expr_false) {
+void bfs_expr_free(struct bfs_expr *expr) {
+	if (!expr || expr == &bfs_true || expr == &bfs_false) {
 		return;
 	}
 
-	bfs_regfree(expr->regex);
-	bfs_printf_free(expr->printf);
-	bfs_exec_free(expr->execbuf);
-
-	free_expr(expr->lhs);
-	free_expr(expr->rhs);
+	if (bfs_expr_has_children(expr)) {
+		bfs_expr_free(expr->rhs);
+		bfs_expr_free(expr->lhs);
+	} else if (expr->eval_fn == eval_exec) {
+		bfs_exec_free(expr->exec);
+	} else if (expr->eval_fn == eval_fprintf) {
+		bfs_printf_free(expr->printf);
+	} else if (expr->eval_fn == eval_regex) {
+		bfs_regfree(expr->regex);
+	}
 
 	free(expr);
 }
 
-struct expr *new_expr(eval_fn *eval, size_t argc, char **argv) {
-	struct expr *expr = malloc(sizeof(*expr));
+struct bfs_expr *bfs_expr_new(bfs_eval_fn *eval_fn, size_t argc, char **argv) {
+	struct bfs_expr *expr = malloc(sizeof(*expr));
 	if (!expr) {
 		perror("malloc()");
 		return NULL;
 	}
 
-	expr->eval = eval;
-	expr->lhs = NULL;
-	expr->rhs = NULL;
+	expr->eval_fn = eval_fn;
+	expr->argc = argc;
+	expr->argv = argv;
+	expr->persistent_fds = 0;
+	expr->ephemeral_fds = 0;
 	expr->pure = false;
 	expr->always_true = false;
 	expr->always_false = false;
@@ -134,28 +133,23 @@ struct expr *new_expr(eval_fn *eval, size_t argc, char **argv) {
 	expr->successes = 0;
 	expr->elapsed.tv_sec = 0;
 	expr->elapsed.tv_nsec = 0;
-	expr->argc = argc;
-	expr->argv = argv;
-	expr->cfile = NULL;
-	expr->regex = NULL;
-	expr->execbuf = NULL;
-	expr->printf = NULL;
-	expr->persistent_fds = 0;
-	expr->ephemeral_fds = 0;
 	return expr;
 }
 
 /**
  * Create a new unary expression.
  */
-static struct expr *new_unary_expr(eval_fn *eval, struct expr *rhs, char **argv) {
-	struct expr *expr = new_expr(eval, 1, argv);
+static struct bfs_expr *new_unary_expr(bfs_eval_fn *eval_fn, struct bfs_expr *rhs, char **argv) {
+	struct bfs_expr *expr = bfs_expr_new(eval_fn, 1, argv);
 	if (!expr) {
-		free_expr(rhs);
+		bfs_expr_free(rhs);
 		return NULL;
 	}
 
+	expr->lhs = NULL;
 	expr->rhs = rhs;
+	assert(bfs_expr_has_children(expr));
+
 	expr->persistent_fds = rhs->persistent_fds;
 	expr->ephemeral_fds = rhs->ephemeral_fds;
 	return expr;
@@ -164,29 +158,36 @@ static struct expr *new_unary_expr(eval_fn *eval, struct expr *rhs, char **argv)
 /**
  * Create a new binary expression.
  */
-static struct expr *new_binary_expr(eval_fn *eval, struct expr *lhs, struct expr *rhs, char **argv) {
-	struct expr *expr = new_expr(eval, 1, argv);
+static struct bfs_expr *new_binary_expr(bfs_eval_fn *eval_fn, struct bfs_expr *lhs, struct bfs_expr *rhs, char **argv) {
+	struct bfs_expr *expr = bfs_expr_new(eval_fn, 1, argv);
 	if (!expr) {
-		free_expr(rhs);
-		free_expr(lhs);
+		bfs_expr_free(rhs);
+		bfs_expr_free(lhs);
 		return NULL;
 	}
 
 	expr->lhs = lhs;
 	expr->rhs = rhs;
+	assert(bfs_expr_has_children(expr));
+
 	expr->persistent_fds = lhs->persistent_fds + rhs->persistent_fds;
 	if (lhs->ephemeral_fds > rhs->ephemeral_fds) {
 		expr->ephemeral_fds = lhs->ephemeral_fds;
 	} else {
 		expr->ephemeral_fds = rhs->ephemeral_fds;
 	}
+
 	return expr;
 }
 
-/**
- * Check if an expression never returns.
- */
-bool expr_never_returns(const struct expr *expr) {
+bool bfs_expr_has_children(const struct bfs_expr *expr) {
+	return expr->eval_fn == eval_and
+		|| expr->eval_fn == eval_or
+		|| expr->eval_fn == eval_not
+		|| expr->eval_fn == eval_comma;
+}
+
+bool bfs_expr_never_returns(const struct bfs_expr *expr) {
 	// Expressions that never return are vacuously both always true and always false
 	return expr->always_true && expr->always_false;
 }
@@ -194,7 +195,7 @@ bool expr_never_returns(const struct expr *expr) {
 /**
  * Set an expression to always return true.
  */
-static void expr_set_always_true(struct expr *expr) {
+static void expr_set_always_true(struct bfs_expr *expr) {
 	expr->always_true = true;
 	expr->probability = 1.0;
 }
@@ -202,7 +203,7 @@ static void expr_set_always_true(struct expr *expr) {
 /**
  * Set an expression to never return.
  */
-static void expr_set_never_returns(struct expr *expr) {
+static void expr_set_never_returns(struct bfs_expr *expr) {
 	expr->always_true = expr->always_false = true;
 }
 
@@ -318,7 +319,7 @@ static bool parse_warning(const struct parser_state *state, const char *format,
 /**
  * Fill in a "-print"-type expression.
  */
-static void init_print_expr(struct parser_state *state, struct expr *expr) {
+static void init_print_expr(struct parser_state *state, struct bfs_expr *expr) {
 	expr_set_always_true(expr);
 	expr->cost = PRINT_COST;
 	expr->cfile = state->ctx->cout;
@@ -327,7 +328,7 @@ static void init_print_expr(struct parser_state *state, struct expr *expr) {
 /**
  * Open a file for an expression.
  */
-static int expr_open(struct parser_state *state, struct expr *expr, const char *path) {
+static int expr_open(struct parser_state *state, struct bfs_expr *expr, const char *path) {
 	struct bfs_ctx *ctx = state->ctx;
 
 	FILE *file = NULL;
@@ -368,15 +369,15 @@ fail:
 /**
  * Invoke bfs_stat() on an argument.
  */
-static int stat_arg(const struct parser_state *state, struct expr *expr, struct bfs_stat *sb) {
+static int stat_arg(const struct parser_state *state, struct bfs_expr *expr, const char *path, struct bfs_stat *sb) {
 	const struct bfs_ctx *ctx = state->ctx;
 
 	bool follow = ctx->flags & (BFTW_FOLLOW_ROOTS | BFTW_FOLLOW_ALL);
 	enum bfs_stat_flags flags = follow ? BFS_STAT_TRYFOLLOW : BFS_STAT_NOFOLLOW;
 
-	int ret = bfs_stat(AT_FDCWD, expr->sdata, flags, sb);
+	int ret = bfs_stat(AT_FDCWD, path, flags, sb);
 	if (ret != 0) {
-		parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: %m.\n", expr->argv[0], expr->sdata);
+		parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: %m.\n", expr->argv[0], path);
 	}
 	return ret;
 }
@@ -384,7 +385,7 @@ static int stat_arg(const struct parser_state *state, struct expr *expr, struct
 /**
  * Parse the expression specified on the command line.
  */
-static struct expr *parse_expr(struct parser_state *state);
+static struct bfs_expr *parse_expr(struct parser_state *state);
 
 /**
  * Advance by a single token.
@@ -567,22 +568,22 @@ range:
 /**
  * Parse an integer and a comparison flag.
  */
-static const char *parse_icmp(const struct parser_state *state, const char *str, struct expr *expr, enum int_flags flags) {
+static const char *parse_icmp(const struct parser_state *state, const char *str, struct bfs_expr *expr, enum int_flags flags) {
 	switch (str[0]) {
 	case '-':
-		expr->cmp_flag = CMP_LESS;
+		expr->int_cmp = BFS_INT_LESS;
 		++str;
 		break;
 	case '+':
-		expr->cmp_flag = CMP_GREATER;
+		expr->int_cmp = BFS_INT_GREATER;
 		++str;
 		break;
 	default:
-		expr->cmp_flag = CMP_EXACT;
+		expr->int_cmp = BFS_INT_EQUAL;
 		break;
 	}
 
-	return parse_int(state, str, &expr->idata, flags | IF_LONG_LONG | IF_UNSIGNED);
+	return parse_int(state, str, &expr->num, flags | IF_LONG_LONG | IF_UNSIGNED);
 }
 
 /**
@@ -604,29 +605,29 @@ static bool looks_like_icmp(const char *str) {
 /**
  * Parse a single flag.
  */
-static struct expr *parse_flag(struct parser_state *state, size_t argc) {
+static struct bfs_expr *parse_flag(struct parser_state *state, size_t argc) {
 	parser_advance(state, T_FLAG, argc);
-	return &expr_true;
+	return &bfs_true;
 }
 
 /**
  * Parse a flag that doesn't take a value.
  */
-static struct expr *parse_nullary_flag(struct parser_state *state) {
+static struct bfs_expr *parse_nullary_flag(struct parser_state *state) {
 	return parse_flag(state, 1);
 }
 
 /**
  * Parse a flag that takes a single value.
  */
-static struct expr *parse_unary_flag(struct parser_state *state) {
+static struct bfs_expr *parse_unary_flag(struct parser_state *state) {
 	return parse_flag(state, 2);
 }
 
 /**
  * Parse a single option.
  */
-static struct expr *parse_option(struct parser_state *state, size_t argc) {
+static struct bfs_expr *parse_option(struct parser_state *state, size_t argc) {
 	const char *arg = *parser_advance(state, T_OPTION, argc);
 
 	if (state->non_option_seen) {
@@ -636,51 +637,51 @@ static struct expr *parse_option(struct parser_state *state, size_t argc) {
 		              arg);
 	}
 
-	return &expr_true;
+	return &bfs_true;
 }
 
 /**
  * Parse an option that doesn't take a value.
  */
-static struct expr *parse_nullary_option(struct parser_state *state) {
+static struct bfs_expr *parse_nullary_option(struct parser_state *state) {
 	return parse_option(state, 1);
 }
 
 /**
  * Parse an option that takes a value.
  */
-static struct expr *parse_unary_option(struct parser_state *state) {
+static struct bfs_expr *parse_unary_option(struct parser_state *state) {
 	return parse_option(state, 2);
 }
 
 /**
  * Parse a single positional option.
  */
-static struct expr *parse_positional_option(struct parser_state *state, size_t argc) {
+static struct bfs_expr *parse_positional_option(struct parser_state *state, size_t argc) {
 	parser_advance(state, T_OPTION, argc);
-	return &expr_true;
+	return &bfs_true;
 }
 
 /**
  * Parse a positional option that doesn't take a value.
  */
-static struct expr *parse_nullary_positional_option(struct parser_state *state) {
+static struct bfs_expr *parse_nullary_positional_option(struct parser_state *state) {
 	return parse_positional_option(state, 1);
 }
 
 /**
  * Parse a positional option that takes a single value.
  */
-static struct expr *parse_unary_positional_option(struct parser_state *state) {
+static struct bfs_expr *parse_unary_positional_option(struct parser_state *state) {
 	return parse_positional_option(state, 2);
 }
 
 /**
  * Parse a single test.
  */
-static struct expr *parse_test(struct parser_state *state, eval_fn *eval, size_t argc) {
+static struct bfs_expr *parse_test(struct parser_state *state, bfs_eval_fn *eval_fn, size_t argc) {
 	char **argv = parser_advance(state, T_TEST, argc);
-	struct expr *expr = new_expr(eval, argc, argv);
+	struct bfs_expr *expr = bfs_expr_new(eval_fn, argc, argv);
 	if (expr) {
 		expr->pure = true;
 	}
@@ -690,14 +691,14 @@ static struct expr *parse_test(struct parser_state *state, eval_fn *eval, size_t
 /**
  * Parse a test that doesn't take a value.
  */
-static struct expr *parse_nullary_test(struct parser_state *state, eval_fn *eval) {
-	return parse_test(state, eval, 1);
+static struct bfs_expr *parse_nullary_test(struct parser_state *state, bfs_eval_fn *eval_fn) {
+	return parse_test(state, eval_fn, 1);
 }
 
 /**
  * Parse a test that takes a value.
  */
-static struct expr *parse_unary_test(struct parser_state *state, eval_fn *eval) {
+static struct bfs_expr *parse_unary_test(struct parser_state *state, bfs_eval_fn *eval_fn) {
 	const char *arg = state->argv[0];
 	const char *value = state->argv[1];
 	if (!value) {
@@ -705,17 +706,13 @@ static struct expr *parse_unary_test(struct parser_state *state, eval_fn *eval)
 		return NULL;
 	}
 
-	struct expr *expr = parse_test(state, eval, 2);
-	if (expr) {
-		expr->sdata = value;
-	}
-	return expr;
+	return parse_test(state, eval_fn, 2);
 }
 
 /**
  * Parse a single action.
  */
-static struct expr *parse_action(struct parser_state *state, eval_fn *eval, size_t argc) {
+static struct bfs_expr *parse_action(struct parser_state *state, bfs_eval_fn *eval_fn, size_t argc) {
 	char **argv = state->argv;
 
 	if (state->excluding) {
@@ -723,25 +720,25 @@ static struct expr *parse_action(struct parser_state *state, eval_fn *eval, size
 		return NULL;
 	}
 
-	if (eval != eval_prune && eval != eval_quit) {
+	if (eval_fn != eval_prune && eval_fn != eval_quit) {
 		state->implicit_print = false;
 	}
 
 	parser_advance(state, T_ACTION, argc);
-	return new_expr(eval, argc, argv);
+	return bfs_expr_new(eval_fn, argc, argv);
 }
 
 /**
  * Parse an action that takes no arguments.
  */
-static struct expr *parse_nullary_action(struct parser_state *state, eval_fn *eval) {
-	return parse_action(state, eval, 1);
+static struct bfs_expr *parse_nullary_action(struct parser_state *state, bfs_eval_fn *eval_fn) {
+	return parse_action(state, eval_fn, 1);
 }
 
 /**
  * Parse an action that takes one argument.
  */
-static struct expr *parse_unary_action(struct parser_state *state, eval_fn *eval) {
+static struct bfs_expr *parse_unary_action(struct parser_state *state, bfs_eval_fn *eval_fn) {
 	const char *arg = state->argv[0];
 	const char *value = state->argv[1];
 	if (!value) {
@@ -749,24 +746,20 @@ static struct expr *parse_unary_action(struct parser_state *state, eval_fn *eval
 		return NULL;
 	}
 
-	struct expr *expr = parse_action(state, eval, 2);
-	if (expr) {
-		expr->sdata = value;
-	}
-	return expr;
+	return parse_action(state, eval_fn, 2);
 }
 
 /**
  * Parse a test expression with integer data and a comparison flag.
  */
-static struct expr *parse_test_icmp(struct parser_state *state, eval_fn *eval) {
-	struct expr *expr = parse_unary_test(state, eval);
+static struct bfs_expr *parse_test_icmp(struct parser_state *state, bfs_eval_fn *eval_fn) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_fn);
 	if (!expr) {
 		return NULL;
 	}
 
-	if (!parse_icmp(state, expr->sdata, expr, 0)) {
-		free_expr(expr);
+	if (!parse_icmp(state, expr->argv[1], expr, 0)) {
+		bfs_expr_free(expr);
 		return NULL;
 	}
 
@@ -802,7 +795,7 @@ static bool parse_debug_flag(const char *flag, size_t len, const char *expected)
 /**
  * Parse -D FLAG.
  */
-static struct expr *parse_debug(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_debug(struct parser_state *state, int arg1, int arg2) {
 	struct bfs_ctx *ctx = state->ctx;
 
 	const char *arg = state->argv[0];
@@ -862,7 +855,7 @@ static struct expr *parse_debug(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -On.
  */
-static struct expr *parse_optlevel(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_optlevel(struct parser_state *state, int arg1, int arg2) {
 	int *optlevel = &state->ctx->optlevel;
 
 	if (strcmp(state->argv[0], "-Ofast") == 0) {
@@ -881,7 +874,7 @@ static struct expr *parse_optlevel(struct parser_state *state, int arg1, int arg
 /**
  * Parse -[PHL], -(no)?follow.
  */
-static struct expr *parse_follow(struct parser_state *state, int flags, int option) {
+static struct bfs_expr *parse_follow(struct parser_state *state, int flags, int option) {
 	struct bfs_ctx *ctx = state->ctx;
 	ctx->flags &= ~(BFTW_FOLLOW_ROOTS | BFTW_FOLLOW_ALL);
 	ctx->flags |= flags;
@@ -895,7 +888,7 @@ static struct expr *parse_follow(struct parser_state *state, int flags, int opti
 /**
  * Parse -X.
  */
-static struct expr *parse_xargs_safe(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_xargs_safe(struct parser_state *state, int arg1, int arg2) {
 	state->ctx->xargs_safe = true;
 	return parse_nullary_flag(state);
 }
@@ -903,13 +896,13 @@ static struct expr *parse_xargs_safe(struct parser_state *state, int arg1, int a
 /**
  * Parse -executable, -readable, -writable
  */
-static struct expr *parse_access(struct parser_state *state, int flag, int arg2) {
-	struct expr *expr = parse_nullary_test(state, eval_access);
+static struct bfs_expr *parse_access(struct parser_state *state, int flag, int arg2) {
+	struct bfs_expr *expr = parse_nullary_test(state, eval_access);
 	if (!expr) {
 		return NULL;
 	}
 
-	expr->idata = flag;
+	expr->num = flag;
 	expr->cost = STAT_COST;
 
 	switch (flag) {
@@ -930,9 +923,9 @@ static struct expr *parse_access(struct parser_state *state, int flag, int arg2)
 /**
  * Parse -acl.
  */
-static struct expr *parse_acl(struct parser_state *state, int flag, int arg2) {
+static struct bfs_expr *parse_acl(struct parser_state *state, int flag, int arg2) {
 #if BFS_CAN_CHECK_ACL
-	struct expr *expr = parse_nullary_test(state, eval_acl);
+	struct bfs_expr *expr = parse_nullary_test(state, eval_acl);
 	if (expr) {
 		expr->cost = STAT_COST;
 		expr->probability = 0.00002;
@@ -947,14 +940,14 @@ static struct expr *parse_acl(struct parser_state *state, int flag, int arg2) {
 /**
  * Parse -[aBcm]?newer.
  */
-static struct expr *parse_newer(struct parser_state *state, int field, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_newer);
+static struct bfs_expr *parse_newer(struct parser_state *state, int field, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_newer);
 	if (!expr) {
 		return NULL;
 	}
 
 	struct bfs_stat sb;
-	if (stat_arg(state, expr, &sb) != 0) {
+	if (stat_arg(state, expr, expr->argv[1], &sb) != 0) {
 		goto fail;
 	}
 
@@ -964,15 +957,15 @@ static struct expr *parse_newer(struct parser_state *state, int field, int arg2)
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -[aBcm]min.
  */
-static struct expr *parse_min(struct parser_state *state, int field, int arg2) {
-	struct expr *expr = parse_test_icmp(state, eval_time);
+static struct bfs_expr *parse_min(struct parser_state *state, int field, int arg2) {
+	struct bfs_expr *expr = parse_test_icmp(state, eval_time);
 	if (!expr) {
 		return NULL;
 	}
@@ -980,15 +973,15 @@ static struct expr *parse_min(struct parser_state *state, int field, int arg2) {
 	expr->cost = STAT_COST;
 	expr->reftime = state->now;
 	expr->stat_field = field;
-	expr->time_unit = MINUTES;
+	expr->time_unit = BFS_MINUTES;
 	return expr;
 }
 
 /**
  * Parse -[aBcm]time.
  */
-static struct expr *parse_time(struct parser_state *state, int field, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_time);
+static struct bfs_expr *parse_time(struct parser_state *state, int field, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_time);
 	if (!expr) {
 		return NULL;
 	}
@@ -997,18 +990,18 @@ static struct expr *parse_time(struct parser_state *state, int field, int arg2)
 	expr->reftime = state->now;
 	expr->stat_field = field;
 
-	const char *tail = parse_icmp(state, expr->sdata, expr, IF_PARTIAL_OK);
+	const char *tail = parse_icmp(state, expr->argv[1], expr, IF_PARTIAL_OK);
 	if (!tail) {
 		goto fail;
 	}
 
 	if (!*tail) {
-		expr->time_unit = DAYS;
+		expr->time_unit = BFS_DAYS;
 		return expr;
 	}
 
-	unsigned long long time = expr->idata;
-	expr->idata = 0;
+	unsigned long long time = expr->num;
+	expr->num = 0;
 
 	while (true) {
 		switch (*tail) {
@@ -1032,7 +1025,7 @@ static struct expr *parse_time(struct parser_state *state, int field, int arg2)
 			goto fail;
 		}
 
-		expr->idata += time;
+		expr->num += time;
 
 		if (!*++tail) {
 			break;
@@ -1049,20 +1042,20 @@ static struct expr *parse_time(struct parser_state *state, int field, int arg2)
 		}
 	}
 
-	expr->time_unit = SECONDS;
+	expr->time_unit = BFS_SECONDS;
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -capable.
  */
-static struct expr *parse_capable(struct parser_state *state, int flag, int arg2) {
+static struct bfs_expr *parse_capable(struct parser_state *state, int flag, int arg2) {
 #if BFS_CAN_CHECK_CAPABILITIES
-	struct expr *expr = parse_nullary_test(state, eval_capable);
+	struct bfs_expr *expr = parse_nullary_test(state, eval_capable);
 	if (expr) {
 		expr->cost = STAT_COST;
 		expr->probability = 0.000002;
@@ -1077,7 +1070,7 @@ static struct expr *parse_capable(struct parser_state *state, int flag, int arg2
 /**
  * Parse -(no)?color.
  */
-static struct expr *parse_color(struct parser_state *state, int color, int arg2) {
+static struct bfs_expr *parse_color(struct parser_state *state, int color, int arg2) {
 	struct bfs_ctx *ctx = state->ctx;
 	struct colors *colors = ctx->colors;
 
@@ -1102,15 +1095,15 @@ static struct expr *parse_color(struct parser_state *state, int color, int arg2)
 /**
  * Parse -{false,true}.
  */
-static struct expr *parse_const(struct parser_state *state, int value, int arg2) {
+static struct bfs_expr *parse_const(struct parser_state *state, int value, int arg2) {
 	parser_advance(state, T_TEST, 1);
-	return value ? &expr_true : &expr_false;
+	return value ? &bfs_true : &bfs_false;
 }
 
 /**
  * Parse -daystart.
  */
-static struct expr *parse_daystart(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_daystart(struct parser_state *state, int arg1, int arg2) {
 	struct tm tm;
 	if (xlocaltime(&state->now.tv_sec, &tm) != 0) {
 		parse_perror(state, "xlocaltime()");
@@ -1139,7 +1132,7 @@ static struct expr *parse_daystart(struct parser_state *state, int arg1, int arg
 /**
  * Parse -delete.
  */
-static struct expr *parse_delete(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_delete(struct parser_state *state, int arg1, int arg2) {
 	state->ctx->flags |= BFTW_POST_ORDER;
 	state->depth_arg = state->argv[0];
 	return parse_nullary_action(state, eval_delete);
@@ -1148,7 +1141,7 @@ static struct expr *parse_delete(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -d.
  */
-static struct expr *parse_depth(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_depth(struct parser_state *state, int arg1, int arg2) {
 	state->ctx->flags |= BFTW_POST_ORDER;
 	state->depth_arg = state->argv[0];
 	return parse_nullary_flag(state);
@@ -1157,7 +1150,7 @@ static struct expr *parse_depth(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -depth [N].
  */
-static struct expr *parse_depth_n(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_depth_n(struct parser_state *state, int arg1, int arg2) {
 	const char *arg = state->argv[1];
 	if (arg && looks_like_icmp(arg)) {
 		return parse_test_icmp(state, eval_depth);
@@ -1169,7 +1162,7 @@ static struct expr *parse_depth_n(struct parser_state *state, int arg1, int arg2
 /**
  * Parse -{min,max}depth N.
  */
-static struct expr *parse_depth_limit(struct parser_state *state, int is_min, int arg2) {
+static struct bfs_expr *parse_depth_limit(struct parser_state *state, int is_min, int arg2) {
 	struct bfs_ctx *ctx = state->ctx;
 	const char *arg = state->argv[0];
 	const char *value = state->argv[1];
@@ -1189,8 +1182,8 @@ static struct expr *parse_depth_limit(struct parser_state *state, int is_min, in
 /**
  * Parse -empty.
  */
-static struct expr *parse_empty(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_test(state, eval_empty);
+static struct bfs_expr *parse_empty(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_test(state, eval_empty);
 	if (!expr) {
 		return NULL;
 	}
@@ -1213,19 +1206,19 @@ static struct expr *parse_empty(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -exec(dir)?/-ok(dir)?.
  */
-static struct expr *parse_exec(struct parser_state *state, int flags, int arg2) {
+static struct bfs_expr *parse_exec(struct parser_state *state, int flags, int arg2) {
 	struct bfs_exec *execbuf = bfs_exec_parse(state->ctx, state->argv, flags);
 	if (!execbuf) {
 		return NULL;
 	}
 
-	struct expr *expr = parse_action(state, eval_exec, execbuf->tmpl_argc + 2);
+	struct bfs_expr *expr = parse_action(state, eval_exec, execbuf->tmpl_argc + 2);
 	if (!expr) {
 		bfs_exec_free(execbuf);
 		return NULL;
 	}
 
-	expr->execbuf = execbuf;
+	expr->exec = execbuf;
 
 	if (execbuf->flags & BFS_EXEC_MULTI) {
 		expr_set_always_true(expr);
@@ -1252,7 +1245,7 @@ static struct expr *parse_exec(struct parser_state *state, int flags, int arg2)
 /**
  * Parse -exit [STATUS].
  */
-static struct expr *parse_exit(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_exit(struct parser_state *state, int arg1, int arg2) {
 	size_t argc = 1;
 	const char *value = state->argv[1];
 
@@ -1261,10 +1254,10 @@ static struct expr *parse_exit(struct parser_state *state, int arg1, int arg2) {
 		argc = 2;
 	}
 
-	struct expr *expr = parse_action(state, eval_exit, argc);
+	struct bfs_expr *expr = parse_action(state, eval_exit, argc);
 	if (expr) {
 		expr_set_never_returns(expr);
-		expr->idata = status;
+		expr->num = status;
 	}
 	return expr;
 }
@@ -1272,7 +1265,7 @@ static struct expr *parse_exit(struct parser_state *state, int arg1, int arg2) {
 /**
  * Parse -f PATH.
  */
-static struct expr *parse_f(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_f(struct parser_state *state, int arg1, int arg2) {
 	parser_advance(state, T_FLAG, 1);
 
 	const char *path = state->argv[0];
@@ -1286,13 +1279,13 @@ static struct expr *parse_f(struct parser_state *state, int arg1, int arg2) {
 	}
 
 	parser_advance(state, T_PATH, 1);
-	return &expr_true;
+	return &bfs_true;
 }
 
 /**
  * Parse -files0-from PATH.
  */
-static struct expr *parse_files0_from(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_files0_from(struct parser_state *state, int arg1, int arg2) {
 	const char *arg = state->argv[0];
 	const char *from = state->argv[1];
 	if (!from) {
@@ -1311,7 +1304,7 @@ static struct expr *parse_files0_from(struct parser_state *state, int arg1, int
 		return NULL;
 	}
 
-	struct expr *expr = parse_unary_positional_option(state);
+	struct bfs_expr *expr = parse_unary_positional_option(state);
 
 	while (true) {
 		char *path = xgetdelim(file, '\0');
@@ -1344,24 +1337,24 @@ static struct expr *parse_files0_from(struct parser_state *state, int arg1, int
 /**
  * Parse -flags FLAGS.
  */
-static struct expr *parse_flags(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_flags);
+static struct bfs_expr *parse_flags(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_flags);
 	if (!expr) {
 		return NULL;
 	}
 
-	const char *flags = expr->sdata;
+	const char *flags = expr->argv[1];
 	switch (flags[0]) {
 	case '-':
-		expr->mode_cmp = MODE_ALL;
+		expr->flags_cmp = BFS_MODE_ALL;
 		++flags;
 		break;
 	case '+':
-		expr->mode_cmp = MODE_ANY;
+		expr->flags_cmp = BFS_MODE_ANY;
 		++flags;
 		break;
 	default:
-		expr->mode_cmp = MODE_EXACT;
+		expr->flags_cmp = BFS_MODE_EQUAL;
 		break;
 	}
 
@@ -1371,7 +1364,7 @@ static struct expr *parse_flags(struct parser_state *state, int arg1, int arg2)
 		} else {
 			parse_error(state, "${blu}%s${rs}: Invalid flags ${bld}%s${rs}.\n", expr->argv[0], flags);
 		}
-		free_expr(expr);
+		bfs_expr_free(expr);
 		return NULL;
 	}
 
@@ -1381,13 +1374,13 @@ static struct expr *parse_flags(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -fls FILE.
  */
-static struct expr *parse_fls(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_unary_action(state, eval_fls);
+static struct bfs_expr *parse_fls(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_unary_action(state, eval_fls);
 	if (!expr) {
 		goto fail;
 	}
 
-	if (expr_open(state, expr, expr->sdata) != 0) {
+	if (expr_open(state, expr, expr->argv[1]) != 0) {
 		goto fail;
 	}
 
@@ -1403,52 +1396,52 @@ static struct expr *parse_fls(struct parser_state *state, int arg1, int arg2) {
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -fprint FILE.
  */
-static struct expr *parse_fprint(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_unary_action(state, eval_fprint);
+static struct bfs_expr *parse_fprint(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_unary_action(state, eval_fprint);
 	if (expr) {
 		expr_set_always_true(expr);
 		expr->cost = PRINT_COST;
-		if (expr_open(state, expr, expr->sdata) != 0) {
+		if (expr_open(state, expr, expr->argv[1]) != 0) {
 			goto fail;
 		}
 	}
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -fprint0 FILE.
  */
-static struct expr *parse_fprint0(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_unary_action(state, eval_fprint0);
+static struct bfs_expr *parse_fprint0(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_unary_action(state, eval_fprint0);
 	if (expr) {
 		expr_set_always_true(expr);
 		expr->cost = PRINT_COST;
-		if (expr_open(state, expr, expr->sdata) != 0) {
+		if (expr_open(state, expr, expr->argv[1]) != 0) {
 			goto fail;
 		}
 	}
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -fprintf FILE FORMAT.
  */
-static struct expr *parse_fprintf(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_fprintf(struct parser_state *state, int arg1, int arg2) {
 	const char *arg = state->argv[0];
 
 	const char *file = state->argv[1];
@@ -1463,7 +1456,7 @@ static struct expr *parse_fprintf(struct parser_state *state, int arg1, int arg2
 		return NULL;
 	}
 
-	struct expr *expr = parse_action(state, eval_fprintf, 3);
+	struct bfs_expr *expr = parse_action(state, eval_fprintf, 3);
 	if (!expr) {
 		return NULL;
 	}
@@ -1484,20 +1477,20 @@ static struct expr *parse_fprintf(struct parser_state *state, int arg1, int arg2
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -fstype TYPE.
  */
-static struct expr *parse_fstype(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_fstype(struct parser_state *state, int arg1, int arg2) {
 	if (!bfs_ctx_mtab(state->ctx)) {
 		parse_error(state, "Couldn't parse the mount table: %m.\n");
 		return NULL;
 	}
 
-	struct expr *expr = parse_unary_test(state, eval_fstype);
+	struct bfs_expr *expr = parse_unary_test(state, eval_fstype);
 	if (expr) {
 		expr->cost = STAT_COST;
 	}
@@ -1507,7 +1500,7 @@ static struct expr *parse_fstype(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -gid/-group.
  */
-static struct expr *parse_group(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_group(struct parser_state *state, int arg1, int arg2) {
 	const struct bfs_groups *groups = bfs_ctx_groups(state->ctx);
 	if (!groups) {
 		parse_error(state, "Couldn't parse the group table: %m.\n");
@@ -1516,21 +1509,21 @@ static struct expr *parse_group(struct parser_state *state, int arg1, int arg2)
 
 	const char *arg = state->argv[0];
 
-	struct expr *expr = parse_unary_test(state, eval_gid);
+	struct bfs_expr *expr = parse_unary_test(state, eval_gid);
 	if (!expr) {
 		return NULL;
 	}
 
-	const struct group *grp = bfs_getgrnam(groups, expr->sdata);
+	const struct group *grp = bfs_getgrnam(groups, expr->argv[1]);
 	if (grp) {
-		expr->idata = grp->gr_gid;
-		expr->cmp_flag = CMP_EXACT;
-	} else if (looks_like_icmp(expr->sdata)) {
-		if (!parse_icmp(state, expr->sdata, expr, 0)) {
+		expr->num = grp->gr_gid;
+		expr->int_cmp = BFS_INT_EQUAL;
+	} else if (looks_like_icmp(expr->argv[1])) {
+		if (!parse_icmp(state, expr->argv[1], expr, 0)) {
 			goto fail;
 		}
 	} else {
-		parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: No such group.\n", arg, expr->sdata);
+		parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: No such group.\n", arg, expr->argv[1]);
 		goto fail;
 	}
 
@@ -1539,14 +1532,14 @@ static struct expr *parse_group(struct parser_state *state, int arg1, int arg2)
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -unique.
  */
-static struct expr *parse_unique(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_unique(struct parser_state *state, int arg1, int arg2) {
 	state->ctx->unique = true;
 	return parse_nullary_option(state);
 }
@@ -1554,8 +1547,8 @@ static struct expr *parse_unique(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -used N.
  */
-static struct expr *parse_used(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_test_icmp(state, eval_used);
+static struct bfs_expr *parse_used(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_test_icmp(state, eval_used);
 	if (expr) {
 		expr->cost = STAT_COST;
 	}
@@ -1565,7 +1558,7 @@ static struct expr *parse_used(struct parser_state *state, int arg1, int arg2) {
 /**
  * Parse -uid/-user.
  */
-static struct expr *parse_user(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_user(struct parser_state *state, int arg1, int arg2) {
 	const struct bfs_users *users = bfs_ctx_users(state->ctx);
 	if (!users) {
 		parse_error(state, "Couldn't parse the user table: %m.\n");
@@ -1574,21 +1567,21 @@ static struct expr *parse_user(struct parser_state *state, int arg1, int arg2) {
 
 	const char *arg = state->argv[0];
 
-	struct expr *expr = parse_unary_test(state, eval_uid);
+	struct bfs_expr *expr = parse_unary_test(state, eval_uid);
 	if (!expr) {
 		return NULL;
 	}
 
-	const struct passwd *pwd = bfs_getpwnam(users, expr->sdata);
+	const struct passwd *pwd = bfs_getpwnam(users, expr->argv[1]);
 	if (pwd) {
-		expr->idata = pwd->pw_uid;
-		expr->cmp_flag = CMP_EXACT;
-	} else if (looks_like_icmp(expr->sdata)) {
-		if (!parse_icmp(state, expr->sdata, expr, 0)) {
+		expr->num = pwd->pw_uid;
+		expr->int_cmp = BFS_INT_EQUAL;
+	} else if (looks_like_icmp(expr->argv[1])) {
+		if (!parse_icmp(state, expr->argv[1], expr, 0)) {
 			goto fail;
 		}
 	} else {
-		parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: No such user.\n", arg, expr->sdata);
+		parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: No such user.\n", arg, expr->argv[1]);
 		goto fail;
 	}
 
@@ -1597,15 +1590,15 @@ static struct expr *parse_user(struct parser_state *state, int arg1, int arg2) {
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -hidden.
  */
-static struct expr *parse_hidden(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_test(state, eval_hidden);
+static struct bfs_expr *parse_hidden(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_test(state, eval_hidden);
 	if (expr) {
 		expr->probability = 0.01;
 	}
@@ -1615,7 +1608,7 @@ static struct expr *parse_hidden(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -(no)?ignore_readdir_race.
  */
-static struct expr *parse_ignore_races(struct parser_state *state, int ignore, int arg2) {
+static struct bfs_expr *parse_ignore_races(struct parser_state *state, int ignore, int arg2) {
 	state->ctx->ignore_races = ignore;
 	return parse_nullary_option(state);
 }
@@ -1623,11 +1616,11 @@ static struct expr *parse_ignore_races(struct parser_state *state, int ignore, i
 /**
  * Parse -inum N.
  */
-static struct expr *parse_inum(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_test_icmp(state, eval_inum);
+static struct bfs_expr *parse_inum(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_test_icmp(state, eval_inum);
 	if (expr) {
 		expr->cost = STAT_COST;
-		expr->probability = expr->cmp_flag == CMP_EXACT ? 0.01 : 0.50;
+		expr->probability = expr->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50;
 	}
 	return expr;
 }
@@ -1635,11 +1628,11 @@ static struct expr *parse_inum(struct parser_state *state, int arg1, int arg2) {
 /**
  * Parse -links N.
  */
-static struct expr *parse_links(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_test_icmp(state, eval_links);
+static struct bfs_expr *parse_links(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_test_icmp(state, eval_links);
 	if (expr) {
 		expr->cost = STAT_COST;
-		expr->probability = expr_cmp(expr, 1) ? 0.99 : 0.01;
+		expr->probability = bfs_expr_cmp(expr, 1) ? 0.99 : 0.01;
 	}
 	return expr;
 }
@@ -1647,8 +1640,8 @@ static struct expr *parse_links(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -ls.
  */
-static struct expr *parse_ls(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_action(state, eval_fls);
+static struct bfs_expr *parse_ls(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_action(state, eval_fls);
 	if (!expr) {
 		return NULL;
 	}
@@ -1667,7 +1660,7 @@ static struct expr *parse_ls(struct parser_state *state, int arg1, int arg2) {
 /**
  * Parse -mount.
  */
-static struct expr *parse_mount(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_mount(struct parser_state *state, int arg1, int arg2) {
 	parse_warning(state,
 	              "In the future, ${blu}%s${rs} will skip mount points entirely, unlike\n"
 	              "${blu}-xdev${rs}, due to http://austingroupbugs.net/view.php?id=1133.\n\n",
@@ -1681,24 +1674,24 @@ static struct expr *parse_mount(struct parser_state *state, int arg1, int arg2)
 /**
  * Common code for fnmatch() tests.
  */
-static struct expr *parse_fnmatch(const struct parser_state *state, struct expr *expr, bool casefold) {
+static struct bfs_expr *parse_fnmatch(const struct parser_state *state, struct bfs_expr *expr, bool casefold) {
 	if (!expr) {
 		return NULL;
 	}
 
 	const char *arg = expr->argv[0];
-	const char *pattern = expr->sdata;
+	const char *pattern = expr->argv[1];
 
 	if (casefold) {
 #ifdef FNM_CASEFOLD
-		expr->idata = FNM_CASEFOLD;
+		expr->num = FNM_CASEFOLD;
 #else
 		parse_error(state, "${blu}%s${rs} is missing platform support.\n", arg);
-		free_expr(expr);
+		bfs_expr_free(expr);
 		return NULL;
 #endif
 	} else {
-		expr->idata = 0;
+		expr->num = 0;
 	}
 
 	// POSIX says, about fnmatch():
@@ -1715,8 +1708,8 @@ static struct expr *parse_fnmatch(const struct parser_state *state, struct expr
 	}
 	if (i % 2 != 0) {
 		parse_warning(state, "${blu}%s${rs} ${bld}%s${rs}: Unescaped trailing backslash.\n\n", arg, pattern);
-		free_expr(expr);
-		return &expr_false;
+		bfs_expr_free(expr);
+		return &bfs_false;
 	}
 
 	expr->cost = 400.0;
@@ -1733,24 +1726,24 @@ static struct expr *parse_fnmatch(const struct parser_state *state, struct expr
 /**
  * Parse -i?name.
  */
-static struct expr *parse_name(struct parser_state *state, int casefold, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_name);
+static struct bfs_expr *parse_name(struct parser_state *state, int casefold, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_name);
 	return parse_fnmatch(state, expr, casefold);
 }
 
 /**
  * Parse -i?path, -i?wholename.
  */
-static struct expr *parse_path(struct parser_state *state, int casefold, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_path);
+static struct bfs_expr *parse_path(struct parser_state *state, int casefold, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_path);
 	return parse_fnmatch(state, expr, casefold);
 }
 
 /**
  * Parse -i?lname.
  */
-static struct expr *parse_lname(struct parser_state *state, int casefold, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_lname);
+static struct bfs_expr *parse_lname(struct parser_state *state, int casefold, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_lname);
 	return parse_fnmatch(state, expr, casefold);
 }
 
@@ -1771,8 +1764,8 @@ static enum bfs_stat_field parse_newerxy_field(char c) {
 }
 
 /** Parse an explicit reference timestamp for -newerXt and -*since. */
-static int parse_reftime(const struct parser_state *state, struct expr *expr) {
-	if (parse_timestamp(expr->sdata, &expr->reftime) == 0) {
+static int parse_reftime(const struct parser_state *state, struct bfs_expr *expr) {
+	if (parse_timestamp(expr->argv[1], &expr->reftime) == 0) {
 		return 0;
 	} else if (errno != EINVAL) {
 		parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: %m.\n", expr->argv[0], expr->argv[1]);
@@ -1818,14 +1811,14 @@ static int parse_reftime(const struct parser_state *state, struct expr *expr) {
 /**
  * Parse -newerXY.
  */
-static struct expr *parse_newerxy(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_newerxy(struct parser_state *state, int arg1, int arg2) {
 	const char *arg = state->argv[0];
 	if (strlen(arg) != 8) {
 		parse_error(state, "Expected ${blu}-newer${bld}XY${rs}; found ${blu}-newer${bld}%s${rs}.\n", arg + 6);
 		return NULL;
 	}
 
-	struct expr *expr = parse_unary_test(state, eval_newer);
+	struct bfs_expr *expr = parse_unary_test(state, eval_newer);
 	if (!expr) {
 		goto fail;
 	}
@@ -1852,14 +1845,14 @@ static struct expr *parse_newerxy(struct parser_state *state, int arg1, int arg2
 		}
 
 		struct bfs_stat sb;
-		if (stat_arg(state, expr, &sb) != 0) {
+		if (stat_arg(state, expr, expr->argv[1], &sb) != 0) {
 			goto fail;
 		}
 
 
 		const struct timespec *reftime = bfs_stat_time(&sb, field);
 		if (!reftime) {
-			parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: Couldn't get file %s.\n", arg, expr->sdata, bfs_stat_field_name(field));
+			parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: Couldn't get file %s.\n", arg, expr->argv[1], bfs_stat_field_name(field));
 			goto fail;
 		}
 
@@ -1871,20 +1864,20 @@ static struct expr *parse_newerxy(struct parser_state *state, int arg1, int arg2
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -nogroup.
  */
-static struct expr *parse_nogroup(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_nogroup(struct parser_state *state, int arg1, int arg2) {
 	if (!bfs_ctx_groups(state->ctx)) {
 		parse_error(state, "Couldn't parse the group table: %m.\n");
 		return NULL;
 	}
 
-	struct expr *expr = parse_nullary_test(state, eval_nogroup);
+	struct bfs_expr *expr = parse_nullary_test(state, eval_nogroup);
 	if (expr) {
 		expr->cost = STAT_COST;
 		expr->probability = 0.01;
@@ -1895,8 +1888,8 @@ static struct expr *parse_nogroup(struct parser_state *state, int arg1, int arg2
 /**
  * Parse -nohidden.
  */
-static struct expr *parse_nohidden(struct parser_state *state, int arg1, int arg2) {
-	struct expr *hidden = new_expr(eval_hidden, 1, &fake_hidden_arg);
+static struct bfs_expr *parse_nohidden(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *hidden = bfs_expr_new(eval_hidden, 1, &fake_hidden_arg);
 	if (!hidden) {
 		return NULL;
 	}
@@ -1911,13 +1904,13 @@ static struct expr *parse_nohidden(struct parser_state *state, int arg1, int arg
 	}
 
 	parser_advance(state, T_OPTION, 1);
-	return &expr_true;
+	return &bfs_true;
 }
 
 /**
  * Parse -noleaf.
  */
-static struct expr *parse_noleaf(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_noleaf(struct parser_state *state, int arg1, int arg2) {
 	parse_warning(state, "${ex}bfs${rs} does not apply the optimization that ${blu}%s${rs} inhibits.\n\n", state->argv[0]);
 	return parse_nullary_option(state);
 }
@@ -1925,13 +1918,13 @@ static struct expr *parse_noleaf(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -nouser.
  */
-static struct expr *parse_nouser(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_nouser(struct parser_state *state, int arg1, int arg2) {
 	if (!bfs_ctx_users(state->ctx)) {
 		parse_error(state, "Couldn't parse the user table: %m.\n");
 		return NULL;
 	}
 
-	struct expr *expr = parse_nullary_test(state, eval_nouser);
+	struct bfs_expr *expr = parse_nullary_test(state, eval_nouser);
 	if (expr) {
 		expr->cost = STAT_COST;
 		expr->probability = 0.01;
@@ -1942,7 +1935,7 @@ static struct expr *parse_nouser(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse a permission mode like chmod(1).
  */
-static int parse_mode(const struct parser_state *state, const char *mode, struct expr *expr) {
+static int parse_mode(const struct parser_state *state, const char *mode, struct bfs_expr *expr) {
 	if (mode[0] >= '0' && mode[0] <= '9') {
 		unsigned int parsed;
 		if (!parse_int(state, mode, &parsed, 8 | IF_INT | IF_UNSIGNED | IF_QUIET)) {
@@ -2163,31 +2156,31 @@ fail:
 /**
  * Parse -perm MODE.
  */
-static struct expr *parse_perm(struct parser_state *state, int field, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_perm);
+static struct bfs_expr *parse_perm(struct parser_state *state, int field, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_perm);
 	if (!expr) {
 		return NULL;
 	}
 
-	const char *mode = expr->sdata;
+	const char *mode = expr->argv[1];
 	switch (mode[0]) {
 	case '-':
-		expr->mode_cmp = MODE_ALL;
+		expr->mode_cmp = BFS_MODE_ALL;
 		++mode;
 		break;
 	case '/':
-		expr->mode_cmp = MODE_ANY;
+		expr->mode_cmp = BFS_MODE_ANY;
 		++mode;
 		break;
 	case '+':
 		if (mode[1] >= '0' && mode[1] <= '9') {
-			expr->mode_cmp = MODE_ANY;
+			expr->mode_cmp = BFS_MODE_ANY;
 			++mode;
 			break;
 		}
 		BFS_FALLTHROUGH;
 	default:
-		expr->mode_cmp = MODE_EXACT;
+		expr->mode_cmp = BFS_MODE_EQUAL;
 		break;
 	}
 
@@ -2200,15 +2193,15 @@ static struct expr *parse_perm(struct parser_state *state, int field, int arg2)
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -print.
  */
-static struct expr *parse_print(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_action(state, eval_fprint);
+static struct bfs_expr *parse_print(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_action(state, eval_fprint);
 	if (expr) {
 		init_print_expr(state, expr);
 	}
@@ -2218,8 +2211,8 @@ static struct expr *parse_print(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -print0.
  */
-static struct expr *parse_print0(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_action(state, eval_fprint0);
+static struct bfs_expr *parse_print0(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_action(state, eval_fprint0);
 	if (expr) {
 		init_print_expr(state, expr);
 	}
@@ -2229,17 +2222,17 @@ static struct expr *parse_print0(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -printf FORMAT.
  */
-static struct expr *parse_printf(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_unary_action(state, eval_fprintf);
+static struct bfs_expr *parse_printf(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_unary_action(state, eval_fprintf);
 	if (!expr) {
 		return NULL;
 	}
 
 	init_print_expr(state, expr);
 
-	expr->printf = bfs_printf_parse(state->ctx, expr->sdata);
+	expr->printf = bfs_printf_parse(state->ctx, expr->argv[1]);
 	if (!expr->printf) {
-		free_expr(expr);
+		bfs_expr_free(expr);
 		return NULL;
 	}
 
@@ -2249,8 +2242,8 @@ static struct expr *parse_printf(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -printx.
  */
-static struct expr *parse_printx(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_action(state, eval_fprintx);
+static struct bfs_expr *parse_printx(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_action(state, eval_fprintx);
 	if (expr) {
 		init_print_expr(state, expr);
 	}
@@ -2260,10 +2253,10 @@ static struct expr *parse_printx(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -prune.
  */
-static struct expr *parse_prune(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_prune(struct parser_state *state, int arg1, int arg2) {
 	state->prune_arg = state->argv[0];
 
-	struct expr *expr = parse_nullary_action(state, eval_prune);
+	struct bfs_expr *expr = parse_nullary_action(state, eval_prune);
 	if (expr) {
 		expr_set_always_true(expr);
 	}
@@ -2273,8 +2266,8 @@ static struct expr *parse_prune(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -quit.
  */
-static struct expr *parse_quit(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_action(state, eval_quit);
+static struct bfs_expr *parse_quit(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_action(state, eval_quit);
 	if (expr) {
 		expr_set_never_returns(expr);
 	}
@@ -2284,13 +2277,13 @@ static struct expr *parse_quit(struct parser_state *state, int arg1, int arg2) {
 /**
  * Parse -i?regex.
  */
-static struct expr *parse_regex(struct parser_state *state, int flags, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_regex);
+static struct bfs_expr *parse_regex(struct parser_state *state, int flags, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_regex);
 	if (!expr) {
 		goto fail;
 	}
 
-	if (bfs_regcomp(&expr->regex, expr->sdata, state->regex_type, flags) != 0) {
+	if (bfs_regcomp(&expr->regex, expr->argv[1], state->regex_type, flags) != 0) {
 		if (!expr->regex) {
 			parse_perror(state, "bfs_regcomp()");
 			goto fail;
@@ -2310,14 +2303,14 @@ static struct expr *parse_regex(struct parser_state *state, int flags, int arg2)
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -E.
  */
-static struct expr *parse_regex_extended(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_regex_extended(struct parser_state *state, int arg1, int arg2) {
 	state->regex_type = BFS_REGEX_POSIX_EXTENDED;
 	return parse_nullary_flag(state);
 }
@@ -2325,7 +2318,7 @@ static struct expr *parse_regex_extended(struct parser_state *state, int arg1, i
 /**
  * Parse -regextype TYPE.
  */
-static struct expr *parse_regextype(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_regextype(struct parser_state *state, int arg1, int arg2) {
 	struct bfs_ctx *ctx = state->ctx;
 	CFILE *cfile = ctx->cerr;
 
@@ -2376,7 +2369,7 @@ list_types:
 /**
  * Parse -s.
  */
-static struct expr *parse_s(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_s(struct parser_state *state, int arg1, int arg2) {
 	state->ctx->flags |= BFTW_SORT;
 	return parse_nullary_flag(state);
 }
@@ -2384,15 +2377,15 @@ static struct expr *parse_s(struct parser_state *state, int arg1, int arg2) {
 /**
  * Parse -samefile FILE.
  */
-static struct expr *parse_samefile(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_samefile);
+static struct bfs_expr *parse_samefile(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_samefile);
 	if (!expr) {
 		return NULL;
 	}
 
 	struct bfs_stat sb;
-	if (stat_arg(state, expr, &sb) != 0) {
-		free_expr(expr);
+	if (stat_arg(state, expr, expr->argv[1], &sb) != 0) {
+		bfs_expr_free(expr);
 		return NULL;
 	}
 
@@ -2408,7 +2401,7 @@ static struct expr *parse_samefile(struct parser_state *state, int arg1, int arg
 /**
  * Parse -S STRATEGY.
  */
-static struct expr *parse_search_strategy(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_search_strategy(struct parser_state *state, int arg1, int arg2) {
 	struct bfs_ctx *ctx = state->ctx;
 	CFILE *cfile = ctx->cerr;
 
@@ -2451,8 +2444,8 @@ list_strategies:
 /**
  * Parse -[aBcm]?since.
  */
-static struct expr *parse_since(struct parser_state *state, int field, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_newer);
+static struct bfs_expr *parse_since(struct parser_state *state, int field, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_newer);
 	if (!expr) {
 		return NULL;
 	}
@@ -2466,20 +2459,20 @@ static struct expr *parse_since(struct parser_state *state, int field, int arg2)
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -size N[cwbkMGTP]?.
  */
-static struct expr *parse_size(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_unary_test(state, eval_size);
+static struct bfs_expr *parse_size(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_unary_test(state, eval_size);
 	if (!expr) {
 		return NULL;
 	}
 
-	const char *unit = parse_icmp(state, expr->sdata, expr, IF_PARTIAL_OK);
+	const char *unit = parse_icmp(state, expr->argv[1], expr, IF_PARTIAL_OK);
 	if (!unit) {
 		goto fail;
 	}
@@ -2491,28 +2484,28 @@ static struct expr *parse_size(struct parser_state *state, int arg1, int arg2) {
 	switch (*unit) {
 	case '\0':
 	case 'b':
-		expr->size_unit = SIZE_BLOCKS;
+		expr->size_unit = BFS_BLOCKS;
 		break;
 	case 'c':
-		expr->size_unit = SIZE_BYTES;
+		expr->size_unit = BFS_BYTES;
 		break;
 	case 'w':
-		expr->size_unit = SIZE_WORDS;
+		expr->size_unit = BFS_WORDS;
 		break;
 	case 'k':
-		expr->size_unit = SIZE_KB;
+		expr->size_unit = BFS_KB;
 		break;
 	case 'M':
-		expr->size_unit = SIZE_MB;
+		expr->size_unit = BFS_MB;
 		break;
 	case 'G':
-		expr->size_unit = SIZE_GB;
+		expr->size_unit = BFS_GB;
 		break;
 	case 'T':
-		expr->size_unit = SIZE_TB;
+		expr->size_unit = BFS_TB;
 		break;
 	case 'P':
-		expr->size_unit = SIZE_PB;
+		expr->size_unit = BFS_PB;
 		break;
 
 	default:
@@ -2520,7 +2513,7 @@ static struct expr *parse_size(struct parser_state *state, int arg1, int arg2) {
 	}
 
 	expr->cost = STAT_COST;
-	expr->probability = expr->cmp_flag == CMP_EXACT ? 0.01 : 0.50;
+	expr->probability = expr->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50;
 
 	return expr;
 
@@ -2528,15 +2521,15 @@ bad_unit:
 	parse_error(state, "${blu}%s${rs} ${bld}%s${rs}: Expected a size unit (one of ${bld}cwbkMGTP${rs}); found ${er}%s${rs}.\n",
 	            expr->argv[0], expr->argv[1], unit);
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -sparse.
  */
-static struct expr *parse_sparse(struct parser_state *state, int arg1, int arg2) {
-	struct expr *expr = parse_nullary_test(state, eval_sparse);
+static struct bfs_expr *parse_sparse(struct parser_state *state, int arg1, int arg2) {
+	struct bfs_expr *expr = parse_nullary_test(state, eval_sparse);
 	if (expr) {
 		expr->cost = STAT_COST;
 	}
@@ -2546,7 +2539,7 @@ static struct expr *parse_sparse(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -status.
  */
-static struct expr *parse_status(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_status(struct parser_state *state, int arg1, int arg2) {
 	state->ctx->status = true;
 	return parse_nullary_option(state);
 }
@@ -2554,9 +2547,9 @@ static struct expr *parse_status(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -x?type [bcdpflsD].
  */
-static struct expr *parse_type(struct parser_state *state, int x, int arg2) {
-	eval_fn *eval = x ? eval_xtype : eval_type;
-	struct expr *expr = parse_unary_test(state, eval);
+static struct bfs_expr *parse_type(struct parser_state *state, int x, int arg2) {
+	bfs_eval_fn *eval = x ? eval_xtype : eval_type;
+	struct bfs_expr *expr = parse_unary_test(state, eval);
 	if (!expr) {
 		return NULL;
 	}
@@ -2564,7 +2557,7 @@ static struct expr *parse_type(struct parser_state *state, int x, int arg2) {
 	unsigned int types = 0;
 	double probability = 0.0;
 
-	const char *c = expr->sdata;
+	const char *c = expr->argv[1];
 	while (true) {
 		enum bfs_type type;
 		double type_prob;
@@ -2635,7 +2628,7 @@ static struct expr *parse_type(struct parser_state *state, int x, int arg2) {
 		}
 	}
 
-	expr->idata = types;
+	expr->num = types;
 	expr->probability = probability;
 
 	if (x && state->ctx->optlevel < 4) {
@@ -2648,14 +2641,14 @@ static struct expr *parse_type(struct parser_state *state, int x, int arg2) {
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
 /**
  * Parse -(no)?warn.
  */
-static struct expr *parse_warn(struct parser_state *state, int warn, int arg2) {
+static struct bfs_expr *parse_warn(struct parser_state *state, int warn, int arg2) {
 	state->ctx->warn = warn;
 	return parse_nullary_positional_option(state);
 }
@@ -2663,9 +2656,9 @@ static struct expr *parse_warn(struct parser_state *state, int warn, int arg2) {
 /**
  * Parse -xattr.
  */
-static struct expr *parse_xattr(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_xattr(struct parser_state *state, int arg1, int arg2) {
 #if BFS_CAN_CHECK_XATTRS
-	struct expr *expr = parse_nullary_test(state, eval_xattr);
+	struct bfs_expr *expr = parse_nullary_test(state, eval_xattr);
 	if (expr) {
 		expr->cost = STAT_COST;
 		expr->probability = 0.01;
@@ -2680,9 +2673,9 @@ static struct expr *parse_xattr(struct parser_state *state, int arg1, int arg2)
 /**
  * Parse -xattrname.
  */
-static struct expr *parse_xattrname(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_xattrname(struct parser_state *state, int arg1, int arg2) {
 #if BFS_CAN_CHECK_XATTRS
-	struct expr *expr = parse_unary_test(state, eval_xattrname);
+	struct bfs_expr *expr = parse_unary_test(state, eval_xattrname);
 	if (expr) {
 		expr->cost = STAT_COST;
 		expr->probability = 0.01;
@@ -2697,7 +2690,7 @@ static struct expr *parse_xattrname(struct parser_state *state, int arg1, int ar
 /**
  * Parse -xdev.
  */
-static struct expr *parse_xdev(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_xdev(struct parser_state *state, int arg1, int arg2) {
 	state->ctx->flags |= BFTW_PRUNE_MOUNTS;
 	state->xdev_arg = state->argv[0];
 	return parse_nullary_option(state);
@@ -2800,7 +2793,7 @@ fail:
 /**
  * "Parse" -help.
  */
-static struct expr *parse_help(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_help(struct parser_state *state, int arg1, int arg2) {
 	CFILE *cout = state->ctx->cout;
 
 	pid_t pager = -1;
@@ -3063,7 +3056,7 @@ static struct expr *parse_help(struct parser_state *state, int arg1, int arg2) {
 /**
  * "Parse" -version.
  */
-static struct expr *parse_version(struct parser_state *state, int arg1, int arg2) {
+static struct bfs_expr *parse_version(struct parser_state *state, int arg1, int arg2) {
 	cfprintf(state->ctx->cout, "${ex}bfs${rs} ${bld}%s${rs}\n\n", BFS_VERSION);
 
 	printf("%s\n", BFS_HOMEPAGE);
@@ -3072,7 +3065,7 @@ static struct expr *parse_version(struct parser_state *state, int arg1, int arg2
 	return NULL;
 }
 
-typedef struct expr *parse_fn(struct parser_state *state, int arg1, int arg2);
+typedef struct bfs_expr *parse_fn(struct parser_state *state, int arg1, int arg2);
 
 /**
  * An entry in the parse table for literals.
@@ -3248,7 +3241,7 @@ static const struct table_entry *table_lookup_fuzzy(const char *arg) {
  *         | TEST
  *         | ACTION
  */
-static struct expr *parse_literal(struct parser_state *state) {
+static struct bfs_expr *parse_literal(struct parser_state *state) {
 	// Paths are already skipped at this point
 	const char *arg = state->argv[0];
 
@@ -3311,7 +3304,7 @@ unexpected:
  *        | "-exclude" FACTOR
  *        | LITERAL
  */
-static struct expr *parse_factor(struct parser_state *state) {
+static struct bfs_expr *parse_factor(struct parser_state *state) {
 	if (skip_paths(state) != 0) {
 		return NULL;
 	}
@@ -3325,20 +3318,20 @@ static struct expr *parse_factor(struct parser_state *state) {
 	if (strcmp(arg, "(") == 0) {
 		parser_advance(state, T_OPERATOR, 1);
 
-		struct expr *expr = parse_expr(state);
+		struct bfs_expr *expr = parse_expr(state);
 		if (!expr) {
 			return NULL;
 		}
 
 		if (skip_paths(state) != 0) {
-			free_expr(expr);
+			bfs_expr_free(expr);
 			return NULL;
 		}
 
 		arg = state->argv[0];
 		if (!arg || strcmp(arg, ")") != 0) {
 			parse_error(state, "Expected a ${red})${rs} after ${blu}%s${rs}.\n", state->argv[-1]);
-			free_expr(expr);
+			bfs_expr_free(expr);
 			return NULL;
 		}
 		parser_advance(state, T_OPERATOR, 1);
@@ -3353,7 +3346,7 @@ static struct expr *parse_factor(struct parser_state *state) {
 		}
 		state->excluding = true;
 
-		struct expr *factor = parse_factor(state);
+		struct bfs_expr *factor = parse_factor(state);
 		if (!factor) {
 			return NULL;
 		}
@@ -3366,11 +3359,11 @@ static struct expr *parse_factor(struct parser_state *state) {
 			return NULL;
 		}
 
-		return &expr_true;
+		return &bfs_true;
 	} else if (strcmp(arg, "!") == 0 || strcmp(arg, "-not") == 0) {
 		char **argv = parser_advance(state, T_OPERATOR, 1);
 
-		struct expr *factor = parse_factor(state);
+		struct bfs_expr *factor = parse_factor(state);
 		if (!factor) {
 			return NULL;
 		}
@@ -3387,12 +3380,12 @@ static struct expr *parse_factor(struct parser_state *state) {
  *      | TERM "-a" FACTOR
  *      | TERM "-and" FACTOR
  */
-static struct expr *parse_term(struct parser_state *state) {
-	struct expr *term = parse_factor(state);
+static struct bfs_expr *parse_term(struct parser_state *state) {
+	struct bfs_expr *term = parse_factor(state);
 
 	while (term) {
 		if (skip_paths(state) != 0) {
-			free_expr(term);
+			bfs_expr_free(term);
 			return NULL;
 		}
 
@@ -3412,10 +3405,10 @@ static struct expr *parse_term(struct parser_state *state) {
 			argv = parser_advance(state, T_OPERATOR, 1);
 		}
 
-		struct expr *lhs = term;
-		struct expr *rhs = parse_factor(state);
+		struct bfs_expr *lhs = term;
+		struct bfs_expr *rhs = parse_factor(state);
 		if (!rhs) {
-			free_expr(lhs);
+			bfs_expr_free(lhs);
 			return NULL;
 		}
 
@@ -3430,12 +3423,12 @@ static struct expr *parse_term(struct parser_state *state) {
  *        | CLAUSE "-o" TERM
  *        | CLAUSE "-or" TERM
  */
-static struct expr *parse_clause(struct parser_state *state) {
-	struct expr *clause = parse_term(state);
+static struct bfs_expr *parse_clause(struct parser_state *state) {
+	struct bfs_expr *clause = parse_term(state);
 
 	while (clause) {
 		if (skip_paths(state) != 0) {
-			free_expr(clause);
+			bfs_expr_free(clause);
 			return NULL;
 		}
 
@@ -3450,10 +3443,10 @@ static struct expr *parse_clause(struct parser_state *state) {
 
 		char **argv = parser_advance(state, T_OPERATOR, 1);
 
-		struct expr *lhs = clause;
-		struct expr *rhs = parse_term(state);
+		struct bfs_expr *lhs = clause;
+		struct bfs_expr *rhs = parse_term(state);
 		if (!rhs) {
-			free_expr(lhs);
+			bfs_expr_free(lhs);
 			return NULL;
 		}
 
@@ -3467,12 +3460,12 @@ static struct expr *parse_clause(struct parser_state *state) {
  * EXPR : CLAUSE
  *      | EXPR "," CLAUSE
  */
-static struct expr *parse_expr(struct parser_state *state) {
-	struct expr *expr = parse_clause(state);
+static struct bfs_expr *parse_expr(struct parser_state *state) {
+	struct bfs_expr *expr = parse_clause(state);
 
 	while (expr) {
 		if (skip_paths(state) != 0) {
-			free_expr(expr);
+			bfs_expr_free(expr);
 			return NULL;
 		}
 
@@ -3487,10 +3480,10 @@ static struct expr *parse_expr(struct parser_state *state) {
 
 		char **argv = parser_advance(state, T_OPERATOR, 1);
 
-		struct expr *lhs = expr;
-		struct expr *rhs = parse_clause(state);
+		struct bfs_expr *lhs = expr;
+		struct bfs_expr *rhs = parse_clause(state);
 		if (!rhs) {
-			free_expr(lhs);
+			bfs_expr_free(lhs);
 			return NULL;
 		}
 
@@ -3503,12 +3496,12 @@ static struct expr *parse_expr(struct parser_state *state) {
 /**
  * Parse the top-level expression.
  */
-static struct expr *parse_whole_expr(struct parser_state *state) {
+static struct bfs_expr *parse_whole_expr(struct parser_state *state) {
 	if (skip_paths(state) != 0) {
 		return NULL;
 	}
 
-	struct expr *expr = &expr_true;
+	struct bfs_expr *expr = &bfs_true;
 	if (state->argv[0]) {
 		expr = parse_expr(state);
 		if (!expr) {
@@ -3522,7 +3515,7 @@ static struct expr *parse_whole_expr(struct parser_state *state) {
 	}
 
 	if (state->implicit_print) {
-		struct expr *print = new_expr(eval_fprint, 1, &fake_print_arg);
+		struct bfs_expr *print = bfs_expr_new(eval_fprint, 1, &fake_print_arg);
 		if (!print) {
 			goto fail;
 		}
@@ -3559,7 +3552,7 @@ static struct expr *parse_whole_expr(struct parser_state *state) {
 	return expr;
 
 fail:
-	free_expr(expr);
+	bfs_expr_free(expr);
 	return NULL;
 }
 
@@ -3667,12 +3660,12 @@ void bfs_ctx_dump(const struct bfs_ctx *ctx, enum debug_flags flag) {
 	}
 
 	if (flag == DEBUG_RATES) {
-		if (ctx->exclude != &expr_false) {
+		if (ctx->exclude != &bfs_false) {
 			cfprintf(cerr, "(${red}-exclude${rs} %pE) ", ctx->exclude);
 		}
 		cfprintf(cerr, "%pE", ctx->expr);
 	} else {
-		if (ctx->exclude != &expr_false) {
+		if (ctx->exclude != &bfs_false) {
 			cfprintf(cerr, "(${red}-exclude${rs} %pe) ", ctx->exclude);
 		}
 		cfprintf(cerr, "%pe", ctx->expr);
@@ -3685,7 +3678,7 @@ void bfs_ctx_dump(const struct bfs_ctx *ctx, enum debug_flags flag) {
  * Dump the estimated costs.
  */
 static void dump_costs(const struct bfs_ctx *ctx) {
-	const struct expr *expr = ctx->expr;
+	const struct bfs_expr *expr = ctx->expr;
 	bfs_debug(ctx, DEBUG_COST, "       Cost: ~${ylw}%g${rs}\n", expr->cost);
 	bfs_debug(ctx, DEBUG_COST, "Probability: ~${ylw}%g%%${rs}\n", 100.0*expr->probability);
 }
@@ -3804,7 +3797,7 @@ struct bfs_ctx *bfs_parse_cmdline(int argc, char *argv[]) {
 		goto fail;
 	}
 
-	ctx->exclude = &expr_false;
+	ctx->exclude = &bfs_false;
 	ctx->expr = parse_whole_expr(&state);
 	if (!ctx->expr) {
 		if (state.just_info) {
-- 
cgit v1.2.3