expr: Make expressions variadic

Rather than only unary/binary expressions, we now support an arbitrary
number of children.  The optimizer has been re-written almost completely
and now supports optimal reordering of longer expression chains, rather
than just arm-swapping.

Fixes #85.

8 files changed, 1719 insertions, 890 deletions

diff --git a/src/color.c b/src/color.c
index 5247cbf..1f10c04 100644
--- a/src/color.c
+++ b/src/color.c
@@ -1109,7 +1109,11 @@ attr(printf(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 bfs_expr *expr, bool verbose) {
+static int print_expr(CFILE *cfile, const struct bfs_expr *expr, bool verbose, int depth) {
+	if (depth >= 2) {
+		return dstrcat(&cfile->buffer, "(...)");
+	}
+
 	if (!expr) {
 		return dstrcat(&cfile->buffer, "(null)");
 	}
@@ -1118,13 +1122,7 @@ static int print_expr(CFILE *cfile, const struct bfs_expr *expr, bool verbose) {
 		return -1;
 	}
 
-	const struct bfs_expr *lhs = NULL;
-	const struct bfs_expr *rhs = NULL;
-
 	if (bfs_expr_is_parent(expr)) {
-		lhs = expr->lhs;
-		rhs = expr->rhs;
-
 		if (cbuff(cfile, "${red}%pq${rs}", expr->argv[0]) < 0) {
 			return -1;
 		}
@@ -1152,21 +1150,20 @@ static int print_expr(CFILE *cfile, const struct bfs_expr *expr, bool verbose) {
 		}
 	}
 
-	if (lhs) {
-		if (dstrcat(&cfile->buffer, " ") != 0) {
-			return -1;
-		}
-		if (print_expr(cfile, lhs, verbose) != 0) {
-			return -1;
-		}
-	}
-
-	if (rhs) {
+	int count = 0;
+	for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
 		if (dstrcat(&cfile->buffer, " ") != 0) {
 			return -1;
 		}
-		if (print_expr(cfile, rhs, verbose) != 0) {
-			return -1;
+		if (++count >= 3) {
+			if (dstrcat(&cfile->buffer, "...") != 0) {
+				return -1;
+			}
+			break;
+		} else {
+			if (print_expr(cfile, child, verbose, depth + 1) != 0) {
+				return -1;
+			}
 		}
 	}
 
@@ -1276,12 +1273,12 @@ static int cvbuff(CFILE *cfile, const char *format, va_list args) {
 					break;
 
 				case 'e':
-					if (print_expr(cfile, va_arg(args, const struct bfs_expr *), false) != 0) {
+					if (print_expr(cfile, va_arg(args, const struct bfs_expr *), false, 0) != 0) {
 						return -1;
 					}
 					break;
 				case 'E':
-					if (print_expr(cfile, va_arg(args, const struct bfs_expr *), true) != 0) {
+					if (print_expr(cfile, va_arg(args, const struct bfs_expr *), true, 0) != 0) {
 						return -1;
 					}
 					break;
diff --git a/src/ctx.c b/src/ctx.c
index a3c5140..1f3e72e 100644
--- a/src/ctx.c
+++ b/src/ctx.c
@@ -241,7 +241,7 @@ int bfs_ctx_free(struct bfs_ctx *ctx) {
 
 		free_colors(ctx->colors);
 
-		for_slist (struct bfs_expr, expr, &ctx->expr_list) {
+		for_slist (struct bfs_expr, expr, &ctx->expr_list, freelist) {
 			bfs_expr_clear(expr);
 		}
 		arena_destroy(&ctx->expr_arena);
diff --git a/src/diag.c b/src/diag.c
index bf2343d..efa7ebd 100644
--- a/src/diag.c
+++ b/src/diag.c
@@ -158,9 +158,8 @@ static bool highlight_expr_recursive(const struct bfs_ctx *ctx, const struct bfs
 		}
 	}
 
-	if (bfs_expr_is_parent(expr)) {
-		ret |= highlight_expr_recursive(ctx, expr->lhs, args);
-		ret |= highlight_expr_recursive(ctx, expr->rhs, args);
+	for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+		ret |= highlight_expr_recursive(ctx, child, args);
 	}
 
 	return ret;
diff --git a/src/eval.c b/src/eval.c
index 372fcf5..49c4aff 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -372,11 +372,10 @@ static int eval_exec_finish(const struct bfs_expr *expr, const struct bfs_ctx *c
 			}
 			ret = -1;
 		}
-	} else if (bfs_expr_is_parent(expr)) {
-		if (expr->lhs && eval_exec_finish(expr->lhs, ctx) != 0) {
-			ret = -1;
-		}
-		if (expr->rhs && eval_exec_finish(expr->rhs, ctx) != 0) {
+	}
+
+	for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+		if (eval_exec_finish(child, ctx) != 0) {
 			ret = -1;
 		}
 	}
@@ -1045,50 +1044,48 @@ static bool eval_expr(struct bfs_expr *expr, struct bfs_eval *state) {
  * Evaluate a negation.
  */
 bool eval_not(const struct bfs_expr *expr, struct bfs_eval *state) {
-	return !eval_expr(expr->rhs, state);
+	return !eval_expr(bfs_expr_children(expr), state);
 }
 
 /**
  * Evaluate a conjunction.
  */
 bool eval_and(const struct bfs_expr *expr, struct bfs_eval *state) {
-	if (!eval_expr(expr->lhs, state)) {
-		return false;
-	}
-
-	if (state->quit) {
-		return false;
+	for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+		if (!eval_expr(child, state) || state->quit) {
+			return false;
+		}
 	}
 
-	return eval_expr(expr->rhs, state);
+	return true;
 }
 
 /**
  * Evaluate a disjunction.
  */
 bool eval_or(const struct bfs_expr *expr, struct bfs_eval *state) {
-	if (eval_expr(expr->lhs, state)) {
-		return true;
-	}
-
-	if (state->quit) {
-		return false;
+	for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+		if (eval_expr(child, state) || state->quit) {
+			return true;
+		}
 	}
 
-	return eval_expr(expr->rhs, state);
+	return false;
 }
 
 /**
  * Evaluate the comma operator.
  */
 bool eval_comma(const struct bfs_expr *expr, struct bfs_eval *state) {
-	eval_expr(expr->lhs, state);
-
-	if (state->quit) {
-		return false;
+	bool ret;
+	for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+		ret = eval_expr(child, state);
+		if (state->quit) {
+			break;
+		}
 	}
 
-	return eval_expr(expr->rhs, state);
+	return ret;
 }
 
 /** Update the status bar. */
@@ -1571,12 +1568,8 @@ static bool eval_must_buffer(const struct bfs_expr *expr) {
 		return true;
 	}
 
-	if (bfs_expr_is_parent(expr)) {
-		if (expr->lhs && eval_must_buffer(expr->lhs)) {
-			return true;
-		}
-
-		if (expr->rhs && eval_must_buffer(expr->rhs)) {
+	for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+		if (eval_must_buffer(child)) {
 			return true;
 		}
 	}
diff --git a/src/expr.c b/src/expr.c
index 2002fc7..3e0033f 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -23,7 +23,12 @@ struct bfs_expr *bfs_expr_new(struct bfs_ctx *ctx, bfs_eval_fn *eval_fn, size_t
 	expr->argc = argc;
 	expr->argv = argv;
 	expr->probability = 0.5;
-	SLIST_PREPEND(&ctx->expr_list, expr);
+	SLIST_PREPEND(&ctx->expr_list, expr, freelist);
+
+	if (bfs_expr_is_parent(expr)) {
+		SLIST_INIT(&expr->children);
+	}
+
 	return expr;
 }
 
@@ -34,6 +39,36 @@ bool bfs_expr_is_parent(const struct bfs_expr *expr) {
 		|| expr->eval_fn == eval_comma;
 }
 
+struct bfs_expr *bfs_expr_children(const struct bfs_expr *expr) {
+	if (bfs_expr_is_parent(expr)) {
+		return expr->children.head;
+	} else {
+		return NULL;
+	}
+}
+
+void bfs_expr_append(struct bfs_expr *expr, struct bfs_expr *child) {
+	bfs_assert(bfs_expr_is_parent(expr));
+
+	SLIST_APPEND(&expr->children, child);
+
+	if (!child->pure) {
+		expr->pure = false;
+	}
+
+	expr->persistent_fds += child->persistent_fds;
+	if (expr->ephemeral_fds < child->ephemeral_fds) {
+		expr->ephemeral_fds = child->ephemeral_fds;
+	}
+}
+
+void bfs_expr_extend(struct bfs_expr *expr, struct bfs_exprs *children) {
+	while (!SLIST_EMPTY(children)) {
+		struct bfs_expr *child = SLIST_POP(children);
+		bfs_expr_append(expr, child);
+	}
+}
+
 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;
diff --git a/src/expr.h b/src/expr.h
index 290f1f8..4d607a4 100644
--- a/src/expr.h
+++ b/src/expr.h
@@ -86,8 +86,10 @@ struct bfs_exprs {
  * A command line expression.
  */
 struct bfs_expr {
-	/** The next allocated expression. */
+	/** This expression's next sibling, if any. */
 	struct bfs_expr *next;
+	/** The next allocated expression. */
+	struct { struct bfs_expr *next; } freelist;
 
 	/** The function that evaluates this expression. */
 	bfs_eval_fn *eval_fn;
@@ -123,12 +125,7 @@ struct bfs_expr {
 	/** 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;
-		};
+		struct bfs_exprs children;
 
 		/** Integer comparisons. */
 		struct {
@@ -218,11 +215,26 @@ struct bfs_ctx;
 struct bfs_expr *bfs_expr_new(struct bfs_ctx *ctx, bfs_eval_fn *eval, size_t argc, char **argv);
 
 /**
- * @return Whether the expression has child expressions.
+ * @return Whether this type of expression has children.
  */
 bool bfs_expr_is_parent(const struct bfs_expr *expr);
 
 /**
+ * @return The first child of this expression, or NULL if it has none.
+ */
+struct bfs_expr *bfs_expr_children(const struct bfs_expr *expr);
+
+/**
+ * Add a child to an expression.
+ */
+void bfs_expr_append(struct bfs_expr *expr, struct bfs_expr *child);
+
+/**
+ * Add a list of children to an expression.
+ */
+void bfs_expr_extend(struct bfs_expr *expr, struct bfs_exprs *children);
+
+/**
  * @return Whether expr is known to always quit.
  */
 bool bfs_expr_never_returns(const struct bfs_expr *expr);
diff --git a/src/opt.c b/src/opt.c
index 1dc985a..7203c61 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -21,11 +21,12 @@
  * -bar is likely to return false.
  *
  * -O4/-Ofast: aggressive optimizations that may affect correctness in corner
- * cases.  The main effect is to use impure to determine if any side-effects are
- * reachable at all, and skipping the traversal if not.
+ * cases.  The main effect is to use opt->impure to determine if any side-
+ * effects are reachable at all, skipping the traversal if not.
  */
 
 #include "opt.h"
+#include "bit.h"
 #include "color.h"
 #include "config.h"
 #include "ctx.h"
@@ -33,6 +34,7 @@
 #include "eval.h"
 #include "exec.h"
 #include "expr.h"
+#include "list.h"
 #include "pwcache.h"
 #include <errno.h>
 #include <limits.h>
@@ -41,9 +43,9 @@
 #include <string.h>
 #include <unistd.h>
 
-static char *fake_and_arg = "-a";
-static char *fake_or_arg = "-o";
-static char *fake_not_arg = "!";
+static char *fake_and_arg = "-and";
+static char *fake_or_arg = "-or";
+static char *fake_not_arg = "-not";
 
 /**
  * The data flow domain for predicates.
@@ -70,6 +72,70 @@ static void pred_join(enum df_pred *dest, enum df_pred src) {
 }
 
 /**
+ * Types of predicates we track.
+ */
+enum pred_type {
+	/** -readable */
+	READABLE_PRED,
+	/** -writable */
+	WRITABLE_PRED,
+	/** -executable */
+	EXECUTABLE_PRED,
+	/** -acl */
+	ACL_PRED,
+	/** -capable */
+	CAPABLE_PRED,
+	/** -empty */
+	EMPTY_PRED,
+	/** -hidden */
+	HIDDEN_PRED,
+	/** -nogroup */
+	NOGROUP_PRED,
+	/** -nouser */
+	NOUSER_PRED,
+	/** -sparse */
+	SPARSE_PRED,
+	/** -xattr */
+	XATTR_PRED,
+	/** The number of pred_types. */
+	PRED_TYPES,
+};
+
+/** Get the name of a predicate type. */
+static const char *pred_type_name(enum pred_type type) {
+	switch (type) {
+	case READABLE_PRED:
+		return "-readable";
+	case WRITABLE_PRED:
+		return "-writable";
+	case EXECUTABLE_PRED:
+		return "-executable";
+	case ACL_PRED:
+		return "-acl";
+	case CAPABLE_PRED:
+		return "-capable";
+	case EMPTY_PRED:
+		return "-empty";
+	case HIDDEN_PRED:
+		return "-hidden";
+	case NOGROUP_PRED:
+		return "-nogroup";
+	case NOUSER_PRED:
+		return "-nouser";
+	case SPARSE_PRED:
+		return "-sparse";
+	case XATTR_PRED:
+		return "-xattr";
+
+	case PRED_TYPES:
+		break;
+	}
+
+	bfs_bug("Unknown predicate %d", (int)type);
+	return "???";
+}
+
+/**
  * A contrained integer range.
  */
 struct df_range {
@@ -97,6 +163,11 @@ static void range_init_top(struct df_range *range) {
 	range->max = LLONG_MAX;
 }
 
+/** Check for an infinite range. */
+static bool range_is_top(const struct df_range *range) {
+	return range->min == 0 && range->max == LLONG_MAX;
+}
+
 /** Compute the minimum of two values. */
 static long long min_value(long long a, long long b) {
 	if (a < b) {
@@ -170,35 +241,29 @@ enum range_type {
 	RANGE_TYPES,
 };
 
-/**
- * Types of predicates we track.
- */
-enum pred_type {
-	/** -readable */
-	READABLE_PRED,
-	/** -writable */
-	WRITABLE_PRED,
-	/** -executable */
-	EXECUTABLE_PRED,
-	/** -acl */
-	ACL_PRED,
-	/** -capable */
-	CAPABLE_PRED,
-	/** -empty */
-	EMPTY_PRED,
-	/** -hidden */
-	HIDDEN_PRED,
-	/** -nogroup */
-	NOGROUP_PRED,
-	/** -nouser */
-	NOUSER_PRED,
-	/** -sparse */
-	SPARSE_PRED,
-	/** -xattr */
-	XATTR_PRED,
-	/** The number of pred_types. */
-	PRED_TYPES,
-};
+/** Get the name of a range type. */
+static const char *range_type_name(enum range_type type) {
+	switch (type) {
+	case DEPTH_RANGE:
+		return "-depth";
+	case GID_RANGE:
+		return "-gid";
+	case INUM_RANGE:
+		return "-inum";
+	case LINKS_RANGE:
+		return "-links";
+	case SIZE_RANGE:
+		return "-size";
+	case UID_RANGE:
+		return "-uid";
+
+	case RANGE_TYPES:
+		break;
+	}
+
+	bfs_bug("Unknown range %d", (int)type);
+	return "???";
+}
 
 /**
  * The data flow analysis domain.
@@ -210,9 +275,9 @@ struct df_domain {
 	/** The value ranges we track. */
 	struct df_range ranges[RANGE_TYPES];
 
-	/** Bitmask of possible file types. */
+	/** Bitmask of possible -types. */
 	unsigned int types;
-	/** Bitmask of possible link target types. */
+	/** Bitmask of possible -xtypes. */
 	unsigned int xtypes;
 };
 
@@ -265,6 +330,31 @@ static void df_init_top(struct df_domain *value) {
 	value->xtypes = ~0;
 }
 
+/** Check for the top element. */
+static bool df_is_top(const struct df_domain *value) {
+        for (int i = 0; i < PRED_TYPES; ++i) {
+                if (value->preds[i] != PRED_TOP) {
+                        return false;
+                }
+        }
+
+        for (int i = 0; i < RANGE_TYPES; ++i) {
+                if (!range_is_top(&value->ranges[i])) {
+                        return false;
+                }
+        }
+
+        if (value->types != ~0U) {
+                return false;
+        }
+
+        if (value->xtypes != ~0U) {
+                return false;
+        }
+
+        return true;
+}
+
 /** Compute the union of two fact sets. */
 static void df_join(struct df_domain *dest, const struct df_domain *src) {
 	for (int i = 0; i < PRED_TYPES; ++i) {
@@ -285,6 +375,15 @@ static void df_join(struct df_domain *dest, const struct df_domain *src) {
 struct bfs_opt {
 	/** The context we're optimizing. */
 	struct bfs_ctx *ctx;
+	/** Optimization level (ctx->optlevel). */
+	int level;
+	/** Recursion depth. */
+	int depth;
+
+	/** Whether to produce warnings. */
+	bool warn;
+	/** Whether the result of this expression is ignored. */
+	bool ignore_result;
 
 	/** Data flow state before this expression is evaluated. */
 	struct df_domain before;
@@ -296,18 +395,14 @@ struct bfs_opt {
 	struct df_domain *impure;
 };
 
-/** Constrain the value of a predicate. */
-static void opt_constrain_pred(struct bfs_opt *opt, enum pred_type type, bool value) {
-	constrain_pred(&opt->after_true.preds[type], value);
-	constrain_pred(&opt->after_false.preds[type], !value);
-}
-
 /** Log an optimization. */
-attr(printf(3, 4))
-static bool opt_debug(const struct bfs_opt *opt, int level, const char *format, ...) {
-	bfs_assert(opt->ctx->optlevel >= level);
+attr(printf(2, 3))
+static bool opt_debug(struct bfs_opt *opt, const char *format, ...) {
+	if (bfs_debug_prefix(opt->ctx, DEBUG_OPT)) {
+		for (int i = 0; i < opt->depth; ++i) {
+			cfprintf(opt->ctx->cerr, "│ ");
+		}
 
-	if (bfs_debug(opt->ctx, DEBUG_OPT, "${cyn}-O%d${rs}: ", level)) {
 		va_list args;
 		va_start(args, format);
 		cvfprintf(opt->ctx->cerr, format, args);
@@ -318,535 +413,590 @@ static bool opt_debug(const struct bfs_opt *opt, int level, const char *format,
 	}
 }
 
-/** Warn about an expression. */
-attr(printf(3, 4))
-static void opt_warning(const struct bfs_opt *opt, const struct bfs_expr *expr, const char *format, ...) {
-	if (bfs_expr_warning(opt->ctx, expr)) {
+/** Log a recursive call. */
+attr(printf(2, 3))
+static bool opt_enter(struct bfs_opt *opt, const char *format, ...) {
+	int depth = opt->depth;
+	if (depth > 0) {
+		--opt->depth;
+	}
+
+	bool debug = opt_debug(opt, "%s", depth > 0 ? "├─╮ " : "");
+	if (debug) {
 		va_list args;
 		va_start(args, format);
-		bfs_vwarning(opt->ctx, format, args);
+		cvfprintf(opt->ctx->cerr, format, args);
 		va_end(args);
 	}
-}
 
-/** Create a constant expression. */
-static struct bfs_expr *opt_const(const struct bfs_opt *opt, bool value) {
-	static bfs_eval_fn *fns[] = {eval_false, eval_true};
-	static char *fake_args[] = {"-false", "-true"};
-	return bfs_expr_new(opt->ctx, fns[value], 1, &fake_args[value]);
+	opt->depth = depth + 1;
+	return debug;
 }
 
-/**
- * Negate an expression.
- */
-static struct bfs_expr *negate_expr(const struct bfs_opt *opt, struct bfs_expr *rhs, char **argv) {
-	if (rhs->eval_fn == eval_not) {
-		return rhs->rhs;
-	}
+/** Log a recursive return. */
+attr(printf(2, 3))
+static bool opt_leave(struct bfs_opt *opt, const char *format, ...) {
+	bool debug = false;
+	int depth = opt->depth;
 
-	struct bfs_expr *expr = bfs_expr_new(opt->ctx, eval_not, 1, argv);
-	if (!expr) {
-		return NULL;
+	if (format) {
+		if (depth > 1) {
+			opt->depth -= 2;
+		}
+
+		debug = opt_debug(opt, "%s", depth > 1 ? "├─╯ " : "");
+		if (debug) {
+			va_list args;
+			va_start(args, format);
+			cvfprintf(opt->ctx->cerr, format, args);
+			va_end(args);
+		}
 	}
 
-	expr->lhs = NULL;
-	expr->rhs = rhs;
-	return expr;
+	opt->depth = depth - 1;
+	return debug;
 }
 
-static struct bfs_expr *optimize_not_expr(const struct bfs_opt *opt, struct bfs_expr *expr);
-static struct bfs_expr *optimize_and_expr(const struct bfs_opt *opt, struct bfs_expr *expr);
-static struct bfs_expr *optimize_or_expr(const struct bfs_opt *opt, struct bfs_expr *expr);
-
-/**
- * Apply De Morgan's laws.
- */
-static struct bfs_expr *de_morgan(const struct bfs_opt *opt, struct bfs_expr *expr, char **argv) {
-	bool debug = opt_debug(opt, 1, "De Morgan's laws: %pe ", expr);
-
-	struct bfs_expr *parent = negate_expr(opt, expr, argv);
-	if (!parent) {
-		return NULL;
+/** Log a shallow visit. */
+attr(printf(2, 3))
+static bool opt_visit(struct bfs_opt *opt, const char *format, ...) {
+	int depth = opt->depth;
+	if (depth > 0) {
+		--opt->depth;
 	}
 
-	bool has_parent = true;
-	if (parent->eval_fn != eval_not) {
-		expr = parent;
-		has_parent = false;
+	bool debug = opt_debug(opt, "%s", depth > 0 ? "├─◯ " : "");
+	if (debug) {
+		va_list args;
+		va_start(args, format);
+		cvfprintf(opt->ctx->cerr, format, args);
+		va_end(args);
 	}
 
-	bfs_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_fn = eval_and;
-		expr->argv = &fake_and_arg;
-	}
+	opt->depth = depth;
+	return debug;
+}
 
-	expr->lhs = negate_expr(opt, expr->lhs, argv);
-	expr->rhs = negate_expr(opt, expr->rhs, argv);
-	if (!expr->lhs || !expr->rhs) {
-		return NULL;
+/** Log the deletion of an expression. */
+attr(printf(2, 3))
+static bool opt_delete(struct bfs_opt *opt, const char *format, ...) {
+	int depth = opt->depth;
+
+	if (depth > 0) {
+		--opt->depth;
 	}
 
+	bool debug = opt_debug(opt, "%s", depth > 0 ? "├─✘ " : "");
 	if (debug) {
-		cfprintf(opt->ctx->cerr, "<==> %pe\n", parent);
+		va_list args;
+		va_start(args, format);
+		cvfprintf(opt->ctx->cerr, format, args);
+		va_end(args);
 	}
 
-	if (expr->lhs->eval_fn == eval_not) {
-		expr->lhs = optimize_not_expr(opt, expr->lhs);
-	}
-	if (expr->rhs->eval_fn == eval_not) {
-		expr->rhs = optimize_not_expr(opt, expr->rhs);
-	}
-	if (!expr->lhs || !expr->rhs) {
-		return NULL;
+	opt->depth = depth;
+	return debug;
+}
+
+typedef bool dump_fn(struct bfs_opt *opt, const char *format, ...);
+
+/** Print a df_pred. */
+static void pred_dump(dump_fn *dump, struct bfs_opt *opt, const struct df_domain *value, enum pred_type type) {
+	dump(opt, "${blu}%s${rs}: ", pred_type_name(type));
+
+	FILE *file = opt->ctx->cerr->file;
+	switch (value->preds[type]) {
+	case PRED_BOTTOM:
+		fprintf(file, "⊥\n");
+		break;
+	case PRED_TOP:
+		fprintf(file, "⊤\n");
+		break;
+	case PRED_TRUE:
+		fprintf(file, "true\n");
+		break;
+	case PRED_FALSE:
+		fprintf(file, "false\n");
+		break;
 	}
+}
 
-	if (expr->eval_fn == eval_and) {
-		expr = optimize_and_expr(opt, expr);
+/** Print a df_range. */
+static void range_dump(dump_fn *dump, struct bfs_opt *opt, const struct df_domain *value, enum range_type type) {
+	dump(opt, "${blu}%s${rs}: ", range_type_name(type));
+
+	FILE *file = opt->ctx->cerr->file;
+	const struct df_range *range = &value->ranges[type];
+	if (range_is_bottom(range)) {
+		fprintf(file, "⊥\n");
+	} else if (range_is_top(range)) {
+		fprintf(file, "⊤\n");
+	} else if (range->min == range->max) {
+		fprintf(file, "%lld\n", range->min);
 	} else {
-		expr = optimize_or_expr(opt, expr);
+		if (range->min == LLONG_MIN) {
+			fprintf(file, "(-∞, ");
+		} else {
+			fprintf(file, "[%lld, ", range->min);
+		}
+		if (range->max == LLONG_MAX) {
+			fprintf(file, "∞)\n");
+		} else {
+			fprintf(file, "%lld]\n", range->max);
+		}
 	}
-	if (has_parent) {
-		parent->rhs = expr;
+}
+
+/** Print a set of types. */
+static void types_dump(dump_fn *dump, struct bfs_opt *opt, const char *name, unsigned int types) {
+	dump(opt, "${blu}%s${rs}: ", name);
+
+	FILE *file = opt->ctx->cerr->file;
+	if (types == 0) {
+		fprintf(file, " ⊥\n");
+	} else if (types == ~0U) {
+		fprintf(file, " ⊤\n");
+	} else if (count_ones(types) < count_ones(~types)) {
+		fprintf(file, " 0x%X\n", types);
 	} else {
-		parent = expr;
+		fprintf(file, "~0x%X\n", ~types);
 	}
-	if (!expr) {
-		return NULL;
+}
+
+/** Calculate the number of lines of df_dump() output. */
+static int df_dump_lines(const struct df_domain *value) {
+	int lines = 0;
+
+	for (int i = 0; i < PRED_TYPES; ++i) {
+		lines += value->preds[i] != PRED_TOP;
 	}
 
-	if (has_parent) {
-		parent = optimize_not_expr(opt, parent);
+	for (int i = 0; i < RANGE_TYPES; ++i) {
+		lines += !range_is_top(&value->ranges[i]);
 	}
-	return parent;
+
+	lines += value->types != ~0U;
+	lines += value->xtypes != ~0U;
+
+	return lines;
 }
 
-/** Optimize an expression recursively. */
-static struct bfs_expr *optimize_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr);
+/** Get the right debugging function for a df_dump() line. */
+static dump_fn *df_dump_line(int lines, int *line) {
+	++*line;
 
-/**
- * Optimize a negation.
- */
-static struct bfs_expr *optimize_not_expr(const struct bfs_opt *opt, struct bfs_expr *expr) {
-	bfs_assert(expr->eval_fn == eval_not);
-
-	struct bfs_expr *rhs = expr->rhs;
-
-	int optlevel = opt->ctx->optlevel;
-	if (optlevel >= 1) {
-		if (rhs->eval_fn == eval_true || rhs->eval_fn == eval_false) {
-			struct bfs_expr *ret = opt_const(opt, rhs->eval_fn == eval_false);
-			opt_debug(opt, 1, "constant propagation: %pe <==> %pe\n", expr, ret);
-			return ret;
-		} else if (rhs->eval_fn == eval_not) {
-			opt_debug(opt, 1, "double negation: %pe <==> %pe\n", expr, rhs->rhs);
-			return rhs->rhs;
-		} else if (bfs_expr_never_returns(rhs)) {
-			opt_debug(opt, 1, "reachability: %pe <==> %pe\n", expr, rhs);
-			return expr->rhs;
-		} 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(opt, expr, expr->argv);
-		}
+	if (lines == 1) {
+		return opt_visit;
+	} else if (*line == 1) {
+		return opt_enter;
+	} else if (*line == lines) {
+		return opt_leave;
+	} else {
+		return opt_debug;
 	}
+}
 
-	expr->pure = rhs->pure;
-	expr->always_true = rhs->always_false;
-	expr->always_false = rhs->always_true;
-	expr->cost = rhs->cost;
-	expr->probability = 1.0 - rhs->probability;
+/** Print a data flow value. */
+static void df_dump(struct bfs_opt *opt, const char *str, const struct df_domain *value) {
+	if (df_is_bottom(value)) {
+		opt_debug(opt, "%s: ⊥\n", str);
+		return;
+	} else if (df_is_top(value)) {
+		opt_debug(opt, "%s: ⊤\n", str);
+		return;
+	}
 
-	return expr;
-}
+	if (!opt_debug(opt, "%s:\n", str)) {
+		return;
+	}
 
-/** Optimize a negation recursively. */
-static struct bfs_expr *optimize_not_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
-	struct bfs_opt rhs_state = *opt;
-	expr->rhs = optimize_expr_recursive(&rhs_state, expr->rhs);
-	if (!expr->rhs) {
-		return NULL;
+	int lines = df_dump_lines(value);
+	int line = 0;
+
+	for (int i = 0; i < PRED_TYPES; ++i) {
+		if (value->preds[i] != PRED_TOP) {
+			pred_dump(df_dump_line(lines, &line), opt, value, i);
+		}
 	}
 
-	opt->after_true = rhs_state.after_false;
-	opt->after_false = rhs_state.after_true;
-
-	return optimize_not_expr(opt, expr);
-}
-
-/** Optimize a conjunction. */
-static struct bfs_expr *optimize_and_expr(const struct bfs_opt *opt, struct bfs_expr *expr) {
-	bfs_assert(expr->eval_fn == eval_and);
-
-	struct bfs_expr *lhs = expr->lhs;
-	struct bfs_expr *rhs = expr->rhs;
-
-	const struct bfs_ctx *ctx = opt->ctx;
-	int optlevel = ctx->optlevel;
-	if (optlevel >= 1) {
-		if (lhs->eval_fn == eval_true) {
-			opt_debug(opt, 1, "conjunction elimination: %pe <==> %pe\n", expr, rhs);
-			return expr->rhs;
-		} else if (rhs->eval_fn == eval_true) {
-			opt_debug(opt, 1, "conjunction elimination: %pe <==> %pe\n", expr, lhs);
-			return expr->lhs;
-		} else if (lhs->always_false) {
-			opt_debug(opt, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
-			opt_warning(opt, expr->rhs, "This expression is unreachable.\n\n");
-			return expr->lhs;
-		} else if (lhs->always_true && rhs->eval_fn == eval_false) {
-			bool debug = opt_debug(opt, 1, "strength reduction: %pe <==> ", expr);
-			struct bfs_expr *ret = expr->lhs;
-			ret = negate_expr(opt, ret, &fake_not_arg);
-			if (debug && ret) {
-				cfprintf(ctx->cerr, "%pe\n", ret);
-			}
-			return ret;
-		} else if (optlevel >= 2 && lhs->pure && rhs->eval_fn == eval_false) {
-			opt_debug(opt, 2, "purity: %pe <==> %pe\n", expr, rhs);
-			opt_warning(opt, expr->lhs, "The result of this expression is ignored.\n\n");
-			return expr->rhs;
-		} else if (lhs->eval_fn == eval_not && rhs->eval_fn == eval_not) {
-			return de_morgan(opt, expr, expr->lhs->argv);
+	for (int i = 0; i < RANGE_TYPES; ++i) {
+		if (!range_is_top(&value->ranges[i])) {
+			range_dump(df_dump_line(lines, &line), opt, value, i);
 		}
 	}
 
-	expr->pure = lhs->pure && rhs->pure;
-	expr->always_true = lhs->always_true && rhs->always_true;
-	expr->always_false = lhs->always_false || rhs->always_false;
-	expr->cost = lhs->cost + lhs->probability * rhs->cost;
-	expr->probability = lhs->probability * rhs->probability;
+	if (value->types != ~0U) {
+		types_dump(df_dump_line(lines, &line), opt, "-type", value->types);
+	}
 
-	return expr;
+	if (value->xtypes != ~0U) {
+		types_dump(df_dump_line(lines, &line), opt, "-xtype", value->xtypes);
+	}
 }
 
-/** Optimize a conjunction recursively. */
-static struct bfs_expr *optimize_and_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
-	struct bfs_opt lhs_state = *opt;
-	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
-	if (!expr->lhs) {
-		return NULL;
+/** Check if an expression is constant. */
+static bool is_const(const struct bfs_expr *expr) {
+	return expr->eval_fn == eval_true || expr->eval_fn == eval_false;
+}
+
+/** Warn about an expression. */
+attr(printf(3, 4))
+static void opt_warning(const struct bfs_opt *opt, const struct bfs_expr *expr, const char *format, ...) {
+	if (!opt->warn) {
+		return;
 	}
 
-	struct bfs_opt rhs_state = *opt;
-	rhs_state.before = lhs_state.after_true;
-	expr->rhs = optimize_expr_recursive(&rhs_state, expr->rhs);
-	if (!expr->rhs) {
-		return NULL;
+	if (bfs_expr_is_parent(expr) || is_const(expr)) {
+		return;
 	}
 
-	opt->after_true = rhs_state.after_true;
-	opt->after_false = lhs_state.after_false;
-	df_join(&opt->after_false, &rhs_state.after_false);
-
-	return optimize_and_expr(opt, expr);
-}
-
-/** Optimize a disjunction. */
-static struct bfs_expr *optimize_or_expr(const struct bfs_opt *opt, struct bfs_expr *expr) {
-	bfs_assert(expr->eval_fn == eval_or);
-
-	struct bfs_expr *lhs = expr->lhs;
-	struct bfs_expr *rhs = expr->rhs;
-
-	const struct bfs_ctx *ctx = opt->ctx;
-	int optlevel = ctx->optlevel;
-	if (optlevel >= 1) {
-		if (lhs->always_true) {
-			opt_debug(opt, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
-			opt_warning(opt, expr->rhs, "This expression is unreachable.\n\n");
-			return expr->lhs;
-		} else if (lhs->eval_fn == eval_false) {
-			opt_debug(opt, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, rhs);
-			return expr->rhs;
-		} else if (rhs->eval_fn == eval_false) {
-			opt_debug(opt, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, lhs);
-			return expr->lhs;
-		} else if (lhs->always_false && rhs->eval_fn == eval_true) {
-			bool debug = opt_debug(opt, 1, "strength reduction: %pe <==> ", expr);
-			struct bfs_expr *ret = expr->lhs;
-			ret = negate_expr(opt, ret, &fake_not_arg);
-			if (debug && ret) {
-				cfprintf(ctx->cerr, "%pe\n", ret);
-			}
-			return ret;
-		} else if (optlevel >= 2 && lhs->pure && rhs->eval_fn == eval_true) {
-			opt_debug(opt, 2, "purity: %pe <==> %pe\n", expr, rhs);
-			opt_warning(opt, expr->lhs, "The result of this expression is ignored.\n\n");
-			return expr->rhs;
-		} else if (lhs->eval_fn == eval_not && rhs->eval_fn == eval_not) {
-			return de_morgan(opt, expr, expr->lhs->argv);
-		}
+	if (bfs_expr_warning(opt->ctx, expr)) {
+		va_list args;
+		va_start(args, format);
+		bfs_vwarning(opt->ctx, format, args);
+		va_end(args);
 	}
+}
 
-	expr->pure = lhs->pure && rhs->pure;
-	expr->always_true = lhs->always_true || rhs->always_true;
-	expr->always_false = lhs->always_false && rhs->always_false;
-	expr->cost = lhs->cost + (1 - lhs->probability) * rhs->cost;
-	expr->probability = lhs->probability + rhs->probability - lhs->probability * rhs->probability;
+/** Remove and return an expression's children. */
+static void foster_children(struct bfs_expr *expr, struct bfs_exprs *children) {
+	bfs_assert(bfs_expr_is_parent(expr));
 
-	return expr;
+	SLIST_INIT(children);
+	SLIST_EXTEND(children, &expr->children);
+
+	expr->persistent_fds = 0;
+	expr->ephemeral_fds = 0;
+	expr->pure = true;
 }
 
-/** Optimize a disjunction recursively. */
-static struct bfs_expr *optimize_or_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
-	struct bfs_opt lhs_state = *opt;
-	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
-	if (!expr->lhs) {
-		return NULL;
+/** Return an expression's only child. */
+static struct bfs_expr *only_child(struct bfs_expr *expr) {
+	bfs_assert(bfs_expr_is_parent(expr));
+	struct bfs_expr *child = bfs_expr_children(expr);
+	bfs_assert(child && !child->next);
+	return child;
+}
+
+/** Foster an expression's only child. */
+static struct bfs_expr *foster_only_child(struct bfs_expr *expr) {
+	struct bfs_expr *child = only_child(expr);
+	struct bfs_exprs children;
+	foster_children(expr, &children);