From cb3805257092cea2fa6d1fce8d2f99f6b01f44ed Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Tue, 24 Jan 2023 17:17:06 -0500
Subject: opt: Move costs out of the parser

---
 src/opt.c   | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/parse.c | 54 +++---------------------------------------------------
 2 files changed, 57 insertions(+), 51 deletions(-)

diff --git a/src/opt.c b/src/opt.c
index c80d584..1daf390 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -804,6 +804,8 @@ static struct bfs_expr *optimize_empty(struct opt_state *state, struct bfs_expr
 static struct bfs_expr *optimize_exec(struct opt_state *state, struct bfs_expr *expr) {
 	if (expr->exec->flags & BFS_EXEC_MULTI) {
 		expr->always_true = true;
+	} else {
+		expr->cost = 1000000.0;
 	}
 
 	return expr;
@@ -929,6 +931,50 @@ static bfs_eval_fn *const opt_always_false[] = {
 	eval_quit,
 };
 
+#define FAST_COST       40.0
+#define FNMATCH_COST   400.0
+#define STAT_COST     1000.0
+#define PRINT_COST   20000.0
+
+/**
+ * Table of expression costs.
+ */
+static const struct {
+	/** The evaluation function with this cost. */
+	bfs_eval_fn *eval_fn;
+	/** The matching cost. */
+	float cost;
+} opt_costs[] = {
+	{eval_access,    STAT_COST},
+	{eval_acl,       STAT_COST},
+	{eval_capable,   STAT_COST},
+	{eval_empty, 2 * STAT_COST}, // readdir() is worse than stat()
+	{eval_fls,      PRINT_COST},
+	{eval_fprint,   PRINT_COST},
+	{eval_fprint0,  PRINT_COST},
+	{eval_fprintf,  PRINT_COST},
+	{eval_fprintx,  PRINT_COST},
+	{eval_fstype,    STAT_COST},
+	{eval_gid,       STAT_COST},
+	{eval_inum,      STAT_COST},
+	{eval_links,     STAT_COST},
+	{eval_lname,  FNMATCH_COST},
+	{eval_name,   FNMATCH_COST},
+	{eval_newer,     STAT_COST},
+	{eval_nogroup,   STAT_COST},
+	{eval_nouser,    STAT_COST},
+	{eval_path,   FNMATCH_COST},
+	{eval_perm,      STAT_COST},
+	{eval_samefile,  STAT_COST},
+	{eval_size,      STAT_COST},
+	{eval_sparse,    STAT_COST},
+	{eval_time,      STAT_COST},
+	{eval_uid,       STAT_COST},
+	{eval_used,      STAT_COST},
+	{eval_xattr,     STAT_COST},
+	{eval_xattrname, STAT_COST},
+};
+
 /**
  * Table of simple predicates.
  */
@@ -1017,6 +1063,14 @@ static struct bfs_expr *optimize_expr_lookup(struct opt_state *state, struct bfs
 		}
 	}
 
+	expr->cost = FAST_COST;
+	for (size_t i = 0; i < BFS_COUNTOF(opt_costs); ++i) {
+		if (opt_costs[i].eval_fn == expr->eval_fn) {
+			expr->cost = opt_costs[i].cost;
+			break;
+		}
+	}
+
 	for (size_t i = 0; i < BFS_COUNTOF(opt_preds); ++i) {
 		if (opt_preds[i].eval_fn == expr->eval_fn) {
 			infer_pred_facts(state, opt_preds[i].pred);
diff --git a/src/parse.c b/src/parse.c
index 5766237..eee185b 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -68,11 +68,6 @@ static char *fake_or_arg = "-o";
 static char *fake_print_arg = "-print";
 static char *fake_true_arg = "-true";
 
-// Cost estimation constants
-#define FAST_COST     40.0
-#define STAT_COST   1000.0
-#define PRINT_COST 20000.0
-
 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) {
@@ -88,7 +83,7 @@ struct bfs_expr *bfs_expr_new(bfs_eval_fn *eval_fn, size_t argc, char **argv) {
 	expr->pure = false;
 	expr->always_true = false;
 	expr->always_false = false;
-	expr->cost = FAST_COST;
+	expr->cost = 0.0;
 	expr->probability = 0.5;
 	expr->evaluations = 0;
 	expr->successes = 0;
@@ -436,7 +431,6 @@ static bool parse_expr_warning(const struct parser_state *state, const struct bf
  * Fill in a "-print"-type expression.
  */
 static void init_print_expr(struct parser_state *state, struct bfs_expr *expr) {
-	expr->cost = PRINT_COST;
 	expr->cfile = state->ctx->cout;
 	expr->path = NULL;
 }
@@ -1021,7 +1015,6 @@ static struct bfs_expr *parse_access(struct parser_state *state, int flag, int a
 	}
 
 	expr->num = flag;
-	expr->cost = STAT_COST;
 
 	switch (flag) {
 	case R_OK:
@@ -1045,7 +1038,6 @@ static struct bfs_expr *parse_acl(struct parser_state *state, int flag, int arg2
 #if BFS_CAN_CHECK_ACL
 	struct bfs_expr *expr = parse_nullary_test(state, eval_acl);
 	if (expr) {
-		expr->cost = STAT_COST;
 		expr->probability = 0.00002;
 	}
 	return expr;
@@ -1069,7 +1061,6 @@ static struct bfs_expr *parse_newer(struct parser_state *state, int field, int a
 		goto fail;
 	}
 
-	expr->cost = STAT_COST;
 	expr->reftime = sb.mtime;
 	expr->stat_field = field;
 	return expr;
@@ -1088,7 +1079,6 @@ static struct bfs_expr *parse_min(struct parser_state *state, int field, int arg
 		return NULL;
 	}
 
-	expr->cost = STAT_COST;
 	expr->reftime = state->now;
 	expr->stat_field = field;
 	expr->time_unit = BFS_MINUTES;
@@ -1104,7 +1094,6 @@ static struct bfs_expr *parse_time(struct parser_state *state, int field, int ar
 		return NULL;
 	}
 
-	expr->cost = STAT_COST;
 	expr->reftime = state->now;
 	expr->stat_field = field;
 
@@ -1173,7 +1162,6 @@ static struct bfs_expr *parse_capable(struct parser_state *state, int flag, int
 #if BFS_CAN_CHECK_CAPABILITIES
 	struct bfs_expr *expr = parse_nullary_test(state, eval_capable);
 	if (expr) {
-		expr->cost = STAT_COST;
 		expr->probability = 0.000002;
 	}
 	return expr;
@@ -1309,7 +1297,6 @@ static struct bfs_expr *parse_empty(struct parser_state *state, int arg1, int ar
 		return NULL;
 	}
 
-	expr->cost = 2000.0;
 	expr->probability = 0.01;
 	expr->ephemeral_fds = 1;
 	return expr;
@@ -1332,10 +1319,6 @@ static struct bfs_expr *parse_exec(struct parser_state *state, int flags, int ar
 
 	expr->exec = execbuf;
 
-	if (!(execbuf->flags & BFS_EXEC_MULTI)) {
-		expr->cost = 1000000.0;
-	}
-
 	expr->ephemeral_fds = 2;
 	if (execbuf->flags & BFS_EXEC_CHDIR) {
 		if (execbuf->flags & BFS_EXEC_MULTI) {
@@ -1495,7 +1478,6 @@ static struct bfs_expr *parse_fls(struct parser_state *state, int arg1, int arg2
 		goto fail;
 	}
 
-	expr->cost = PRINT_COST;
 	return expr;
 
 fail:
@@ -1509,7 +1491,6 @@ fail:
 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->cost = PRINT_COST;
 		if (expr_open(state, expr, expr->argv[1]) != 0) {
 			goto fail;
 		}
@@ -1527,7 +1508,6 @@ fail:
 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->cost = PRINT_COST;
 		if (expr_open(state, expr, expr->argv[1]) != 0) {
 			goto fail;
 		}
@@ -1562,8 +1542,6 @@ static struct bfs_expr *parse_fprintf(struct parser_state *state, int arg1, int
 		return NULL;
 	}
 
-	expr->cost = PRINT_COST;
-
 	if (expr_open(state, expr, file) != 0) {
 		goto fail;
 	}
@@ -1594,7 +1572,6 @@ static struct bfs_expr *parse_fstype(struct parser_state *state, int arg1, int a
 		return NULL;
 	}
 
-	expr->cost = STAT_COST;
 	return expr;
 }
 
@@ -1623,7 +1600,6 @@ static struct bfs_expr *parse_group(struct parser_state *state, int arg1, int ar
 		goto fail;
 	}
 
-	expr->cost = STAT_COST;
 	return expr;
 
 fail:
@@ -1643,11 +1619,7 @@ static struct bfs_expr *parse_unique(struct parser_state *state, int arg1, int a
  * Parse -used N.
  */
 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;
-	}
-	return expr;
+	return parse_test_icmp(state, eval_used);
 }
 
 /**
@@ -1675,7 +1647,6 @@ static struct bfs_expr *parse_user(struct parser_state *state, int arg1, int arg
 		goto fail;
 	}
 
-	expr->cost = STAT_COST;
 	return expr;
 
 fail:
@@ -1708,7 +1679,6 @@ static struct bfs_expr *parse_ignore_races(struct parser_state *state, int ignor
 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->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50;
 	}
 	return expr;
@@ -1720,7 +1690,6 @@ static struct bfs_expr *parse_inum(struct parser_state *state, int arg1, int arg
 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 = bfs_expr_cmp(expr, 1) ? 0.99 : 0.01;
 	}
 	return expr;
@@ -1795,8 +1764,6 @@ static struct bfs_expr *parse_fnmatch(const struct parser_state *state, struct b
 		return expr;
 	}
 
-	expr->cost = 400.0;
-
 	if (strchr(pattern, '*')) {
 		expr->probability = 0.5;
 	} else {
@@ -1942,8 +1909,6 @@ static struct bfs_expr *parse_newerxy(struct parser_state *state, int arg1, int
 		expr->reftime = *reftime;
 	}
 
-	expr->cost = STAT_COST;
-
 	return expr;
 
 fail:
@@ -1960,7 +1925,6 @@ static struct bfs_expr *parse_nogroup(struct parser_state *state, int arg1, int
 		return NULL;
 	}
 
-	expr->cost = STAT_COST;
 	expr->probability = 0.01;
 
 	// Who knows how many FDs getgrgid_r() needs?  Probably at least one for
@@ -2006,7 +1970,6 @@ static struct bfs_expr *parse_nouser(struct parser_state *state, int arg1, int a
 		return NULL;
 	}
 
-	expr->cost = STAT_COST;
 	expr->probability = 0.01;
 
 	// Who knows how many FDs getpwuid_r() needs?  Probably at least one for
@@ -2272,8 +2235,6 @@ static struct bfs_expr *parse_perm(struct parser_state *state, int field, int ar
 		goto fail;
 	}
 
-	expr->cost = STAT_COST;
-
 	return expr;
 
 fail:
@@ -2468,7 +2429,6 @@ static struct bfs_expr *parse_samefile(struct parser_state *state, int arg1, int
 	expr->dev = sb.dev;
 	expr->ino = sb.ino;
 
-	expr->cost = STAT_COST;
 	expr->probability = 0.01;
 
 	return expr;
@@ -2531,7 +2491,6 @@ static struct bfs_expr *parse_since(struct parser_state *state, int field, int a
 		goto fail;
 	}
 
-	expr->cost = STAT_COST;
 	expr->stat_field = field;
 	return expr;
 
@@ -2589,7 +2548,6 @@ static struct bfs_expr *parse_size(struct parser_state *state, int arg1, int arg
 		goto bad_unit;
 	}
 
-	expr->cost = STAT_COST;
 	expr->probability = expr->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50;
 
 	return expr;
@@ -2605,11 +2563,7 @@ fail:
  * Parse -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;
-	}
-	return expr;
+	return parse_nullary_test(state, eval_sparse);
 }
 
 /**
@@ -2728,7 +2682,6 @@ static struct bfs_expr *parse_xattr(struct parser_state *state, int arg1, int ar
 #if BFS_CAN_CHECK_XATTRS
 	struct bfs_expr *expr = parse_nullary_test(state, eval_xattr);
 	if (expr) {
-		expr->cost = STAT_COST;
 		expr->probability = 0.01;
 	}
 	return expr;
@@ -2745,7 +2698,6 @@ static struct bfs_expr *parse_xattrname(struct parser_state *state, int arg1, in
 #if BFS_CAN_CHECK_XATTRS
 	struct bfs_expr *expr = parse_unary_test(state, eval_xattrname);
 	if (expr) {
-		expr->cost = STAT_COST;
 		expr->probability = 0.01;
 	}
 	return expr;
-- 
cgit v1.2.3