summaryrefslogtreecommitdiffstats
path: root/src/opt.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt.c')
-rw-r--r--src/opt.c225
1 files changed, 146 insertions, 79 deletions
diff --git a/src/opt.c b/src/opt.c
index 9b091bd..9094794 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -25,8 +25,10 @@
* effects are reachable at all, skipping the traversal if not.
*/
-#include "prelude.h"
#include "opt.h"
+
+#include "bfs.h"
+#include "bfstd.h"
#include "bftw.h"
#include "bit.h"
#include "color.h"
@@ -38,6 +40,8 @@
#include "expr.h"
#include "list.h"
#include "pwcache.h"
+#include "xspawn.h"
+
#include <errno.h>
#include <limits.h>
#include <stdarg.h>
@@ -118,7 +122,7 @@ static const char *const pred_names[] = {
};
/**
- * A contrained integer range.
+ * A constrained integer range.
*/
struct df_range {
/** The (inclusive) minimum value. */
@@ -173,11 +177,17 @@ static void constrain_min(struct df_range *range, long long value) {
range->min = max_value(range->min, value);
}
-/** Contrain the maximum of a range. */
+/** Constrain the maximum of a range. */
static void constrain_max(struct df_range *range, long long value) {
range->max = min_value(range->max, value);
}
+/** Constrain a range to a single value. */
+static void constrain_range(struct df_range *range, long long value) {
+ constrain_min(range, value);
+ constrain_max(range, value);
+}
+
/** Remove a single value from a range. */
static void range_remove(struct df_range *range, long long value) {
if (range->min == value) {
@@ -364,7 +374,7 @@ struct bfs_opt {
};
/** Log an optimization. */
-attr(printf(2, 3))
+_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) {
@@ -382,7 +392,7 @@ static bool opt_debug(struct bfs_opt *opt, const char *format, ...) {
}
/** Log a recursive call. */
-attr(printf(2, 3))
+_printf(2, 3)
static bool opt_enter(struct bfs_opt *opt, const char *format, ...) {
int depth = opt->depth;
if (depth > 0) {
@@ -402,7 +412,7 @@ static bool opt_enter(struct bfs_opt *opt, const char *format, ...) {
}
/** Log a recursive return. */
-attr(printf(2, 3))
+_printf(2, 3)
static bool opt_leave(struct bfs_opt *opt, const char *format, ...) {
bool debug = false;
int depth = opt->depth;
@@ -426,7 +436,7 @@ static bool opt_leave(struct bfs_opt *opt, const char *format, ...) {
}
/** Log a shallow visit. */
-attr(printf(2, 3))
+_printf(2, 3)
static bool opt_visit(struct bfs_opt *opt, const char *format, ...) {
int depth = opt->depth;
if (depth > 0) {
@@ -446,7 +456,7 @@ static bool opt_visit(struct bfs_opt *opt, const char *format, ...) {
}
/** Log the deletion of an expression. */
-attr(printf(2, 3))
+_printf(2, 3)
static bool opt_delete(struct bfs_opt *opt, const char *format, ...) {
int depth = opt->depth;
@@ -608,22 +618,26 @@ static bool is_const(const struct bfs_expr *expr) {
}
/** 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, ...) {
+_printf(3, 4)
+static bool opt_warning(const struct bfs_opt *opt, const struct bfs_expr *expr, const char *format, ...) {
if (!opt->warn) {
- return;
+ return false;
}
if (bfs_expr_is_parent(expr) || is_const(expr)) {
- return;
+ return false;
}
- if (bfs_expr_warning(opt->ctx, expr)) {
- va_list args;
- va_start(args, format);
- bfs_vwarning(opt->ctx, format, args);
- va_end(args);
+ if (!bfs_expr_warning(opt->ctx, expr)) {
+ return false;
}
+
+ va_list args;
+ va_start(args, format);
+ bfs_vwarning(opt->ctx, format, args);
+ va_end(args);
+
+ return true;
}
/** Remove and return an expression's children. */
@@ -723,9 +737,7 @@ static struct bfs_expr *visit_and(struct bfs_opt *opt, struct bfs_expr *expr, co
df_init_bottom(&opt->after_false);
struct bfs_opt nested = *opt;
- while (!SLIST_EMPTY(&children)) {
- struct bfs_expr *child = SLIST_POP(&children);
-
+ drain_slist (struct bfs_expr, child, &children) {
if (SLIST_EMPTY(&children)) {
nested.ignore_result = opt->ignore_result;
} else {
@@ -757,9 +769,7 @@ static struct bfs_expr *visit_or(struct bfs_opt *opt, struct bfs_expr *expr, con
df_init_bottom(&opt->after_true);
struct bfs_opt nested = *opt;
- while (!SLIST_EMPTY(&children)) {
- struct bfs_expr *child = SLIST_POP(&children);
-
+ drain_slist (struct bfs_expr, child, &children) {
if (SLIST_EMPTY(&children)) {
nested.ignore_result = opt->ignore_result;
} else {
@@ -789,9 +799,7 @@ static struct bfs_expr *visit_comma(struct bfs_opt *opt, struct bfs_expr *expr,
struct bfs_opt nested = *opt;
- while (!SLIST_EMPTY(&children)) {
- struct bfs_expr *child = SLIST_POP(&children);
-
+ drain_slist (struct bfs_expr, child, &children) {
if (SLIST_EMPTY(&children)) {
nested.ignore_result = opt->ignore_result;
} else {
@@ -1327,7 +1335,7 @@ static struct bfs_expr *opt_const(struct bfs_opt *opt, bool value) {
static bfs_eval_fn *const fns[] = {eval_false, eval_true};
static char *fake_args[] = {"-false", "-true"};
- struct bfs_expr *expr = bfs_expr_new(opt->ctx, fns[value], 1, &fake_args[value]);
+ struct bfs_expr *expr = bfs_expr_new(opt->ctx, fns[value], 1, &fake_args[value], BFS_TEST);
return visit_shallow(opt, expr, &annotate);
}
@@ -1341,7 +1349,7 @@ static struct bfs_expr *negate_expr(struct bfs_opt *opt, struct bfs_expr *expr,
return opt_const(opt, true);
}
- struct bfs_expr *ret = bfs_expr_new(opt->ctx, eval_not, 1, argv);
+ struct bfs_expr *ret = bfs_expr_new(opt->ctx, eval_not, 1, argv, BFS_OPERATOR);
if (!ret) {
return NULL;
}
@@ -1370,8 +1378,7 @@ static struct bfs_expr *sink_not_andor(struct bfs_opt *opt, struct bfs_expr *exp
struct bfs_exprs children;
foster_children(expr, &children);
- struct bfs_expr *child;
- while ((child = SLIST_POP(&children))) {
+ drain_slist (struct bfs_expr, child, &children) {
opt_enter(opt, "%pe\n", child);
child = negate_expr(opt, child, argv);
@@ -1389,18 +1396,16 @@ static struct bfs_expr *sink_not_andor(struct bfs_opt *opt, struct bfs_expr *exp
/** Sink a negation into a comma expression. */
static struct bfs_expr *sink_not_comma(struct bfs_opt *opt, struct bfs_expr *expr) {
- bfs_assert(expr->eval_fn == eval_comma);
-
- opt_enter(opt, "%pe\n", expr);
-
char **argv = expr->argv;
expr = only_child(expr);
+ opt_enter(opt, "%pe\n", expr);
+
+ bfs_assert(expr->eval_fn == eval_comma);
struct bfs_exprs children;
foster_children(expr, &children);
- struct bfs_expr *child;
- while ((child = SLIST_POP(&children))) {
+ drain_slist (struct bfs_expr, child, &children) {
if (SLIST_EMPTY(&children)) {
opt_enter(opt, "%pe\n", child);
opt_debug(opt, "sink\n");
@@ -1428,7 +1433,6 @@ static struct bfs_expr *canonicalize_not(struct bfs_opt *opt, struct bfs_expr *e
if (rhs->eval_fn == eval_not) {
opt_debug(opt, "double negation\n");
- rhs = only_child(expr);
return only_child(rhs);
} else if (rhs->eval_fn == eval_and || rhs->eval_fn == eval_or) {
return sink_not_andor(opt, expr);
@@ -1450,8 +1454,7 @@ static struct bfs_expr *canonicalize_assoc(struct bfs_opt *opt, struct bfs_expr
struct bfs_exprs flat;
SLIST_INIT(&flat);
- struct bfs_expr *child;
- while ((child = SLIST_POP(&children))) {
+ drain_slist (struct bfs_expr, child, &children) {
if (child->eval_fn == expr->eval_fn) {
struct bfs_expr *head = SLIST_HEAD(&child->children);
struct bfs_expr *tail = SLIST_TAIL(&child->children);
@@ -1559,8 +1562,7 @@ static struct bfs_expr *reorder_andor(struct bfs_opt *opt, struct bfs_expr *expr
struct bfs_exprs pure;
SLIST_INIT(&pure);
- struct bfs_expr *child;
- while ((child = SLIST_POP(&children))) {
+ drain_slist (struct bfs_expr, child, &children) {
if (child->pure) {
SLIST_APPEND(&pure, child);
} else {
@@ -1601,8 +1603,7 @@ static void data_flow_icmp(struct bfs_opt *opt, const struct bfs_expr *expr, enu
switch (expr->int_cmp) {
case BFS_INT_EQUAL:
- constrain_min(true_range, value);
- constrain_max(true_range, value);
+ constrain_range(true_range, value);
range_remove(false_range, value);
break;
@@ -1622,14 +1623,31 @@ static void data_flow_icmp(struct bfs_opt *opt, const struct bfs_expr *expr, enu
/** Transfer function for -{execut,read,writ}able. */
static struct bfs_expr *data_flow_access(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) {
- if (expr->num & R_OK) {
+ switch (expr->num) {
+ case R_OK:
data_flow_pred(opt, READABLE_PRED, true);
- }
- if (expr->num & W_OK) {
+ break;
+ case W_OK:
data_flow_pred(opt, WRITABLE_PRED, true);
- }
- if (expr->num & X_OK) {
+ break;
+ case X_OK:
data_flow_pred(opt, EXECUTABLE_PRED, true);
+ break;
+ default:
+ bfs_bug("Unknown access() mode %lld", expr->num);
+ break;
+ }
+
+ return expr;
+}
+
+/** Transfer function for -empty. */
+static struct bfs_expr *data_flow_empty(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) {
+ opt->after_true.types &= (1 << BFS_REG) | (1 << BFS_DIR);
+
+ if (opt->before.types == (1 << BFS_REG)) {
+ constrain_range(&opt->after_true.ranges[SIZE_RANGE], 0);
+ range_remove(&opt->after_false.ranges[SIZE_RANGE], 0);
}
return expr;
@@ -1642,7 +1660,7 @@ static struct bfs_expr *data_flow_gid(struct bfs_opt *opt, struct bfs_expr *expr
gid_t gid = range->min;
bool nogroup = !bfs_getgrgid(opt->ctx->groups, gid);
if (errno == 0) {
- data_flow_pred(opt, NOGROUP_PRED, nogroup);
+ constrain_pred(&opt->after_true.preds[NOGROUP_PRED], nogroup);
}
}
@@ -1673,11 +1691,16 @@ static struct bfs_expr *data_flow_links(struct bfs_opt *opt, struct bfs_expr *ex
return expr;
}
+/** Transfer function for -lname. */
+static struct bfs_expr *data_flow_lname(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) {
+ opt->after_true.types &= 1 << BFS_LNK;
+ return expr;
+}
+
/** Transfer function for -samefile. */
static struct bfs_expr *data_flow_samefile(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) {
struct df_range *true_range = &opt->after_true.ranges[INUM_RANGE];
- constrain_min(true_range, expr->ino);
- constrain_max(true_range, expr->ino);
+ constrain_range(true_range, expr->ino);
struct df_range *false_range = &opt->after_false.ranges[INUM_RANGE];
range_remove(false_range, expr->ino);
@@ -1711,7 +1734,7 @@ static struct bfs_expr *data_flow_uid(struct bfs_opt *opt, struct bfs_expr *expr
uid_t uid = range->min;
bool nouser = !bfs_getpwuid(opt->ctx->users, uid);
if (errno == 0) {
- data_flow_pred(opt, NOUSER_PRED, nouser);
+ constrain_pred(&opt->after_true.preds[NOUSER_PRED], nouser);
}
}
@@ -1785,12 +1808,45 @@ static struct bfs_expr *data_flow_leave(struct bfs_opt *opt, struct bfs_expr *ex
return visit_leave(opt, expr, visitor);
}
-/** Data flow visitor function. */
-static struct bfs_expr *data_flow_visit(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) {
- if (opt->ignore_result && expr->pure) {
+/** Ignore an expression (and possibly warn/prompt). */
+static struct bfs_expr *opt_ignore(struct bfs_opt *opt, struct bfs_expr *expr, bool delete) {
+ if (delete) {
+ opt_delete(opt, "%pe [ignored result]\n", expr);
+ } else {
opt_debug(opt, "ignored result\n");
- opt_warning(opt, expr, "The result of this expression is ignored.\n\n");
+ }
+
+ if (expr->kind != BFS_TEST) {
+ goto done;
+ }
+
+ if (!opt_warning(opt, expr, "The result of this expression is ignored.\n")) {
+ goto done;
+ }
+
+ struct bfs_ctx *ctx = opt->ctx;
+ if (ctx->interactive && ctx->dangerous) {
+ bfs_warning(ctx, "Do you want to continue? ");
+ if (ynprompt() <= 0) {
+ errno = 0;
+ return NULL;
+ }
+ }
+
+ fprintf(stderr, "\n");
+
+done:
+ if (!delete && expr->pure) {
+ // If we're not deleting the expression entirely, replace it with -false
expr = opt_const(opt, false);
+ }
+ return expr;
+}
+
+/** Data flow visitor function. */
+static struct bfs_expr *data_flow_visit(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) {
+ if (opt->ignore_result) {
+ expr = opt_ignore(opt, expr, false);
if (!expr) {
return NULL;
}
@@ -1860,9 +1916,11 @@ static const struct visitor data_flow = {
.leave = data_flow_leave,
.table = (const struct visitor_table[]) {
{eval_access, data_flow_access},
+ {eval_empty, data_flow_empty},
{eval_gid, data_flow_gid},
{eval_inum, data_flow_inum},
{eval_links, data_flow_links},
+ {eval_lname, data_flow_lname},
{eval_samefile, data_flow_samefile},
{eval_size, data_flow_size},
{eval_type, data_flow_type},
@@ -1911,8 +1969,7 @@ static struct bfs_expr *lift_andor_not(struct bfs_opt *opt, struct bfs_expr *exp
struct bfs_exprs children;
foster_children(expr, &children);
- struct bfs_expr *child;
- while ((child = SLIST_POP(&children))) {
+ drain_slist (struct bfs_expr, child, &children) {
opt_enter(opt, "%pe\n", child);
child = negate_expr(opt, child, &fake_not_arg);
@@ -1925,6 +1982,10 @@ static struct bfs_expr *lift_andor_not(struct bfs_opt *opt, struct bfs_expr *exp
}
expr = visit_shallow(opt, expr, &annotate);
+ if (!expr) {
+ return NULL;
+ }
+
return negate_expr(opt, expr, &fake_not_arg);
}
@@ -1954,16 +2015,15 @@ static struct bfs_expr *simplify_and(struct bfs_opt *opt, struct bfs_expr *expr,
struct bfs_exprs children;
foster_children(expr, &children);
- while (!SLIST_EMPTY(&children)) {
- struct bfs_expr *child = SLIST_POP(&children);
-
+ drain_slist (struct bfs_expr, child, &children) {
if (child == ignorable) {
ignore = true;
}
if (ignore) {
- opt_delete(opt, "%pe [ignored result]\n", child);
- opt_warning(opt, child, "The result of this expression is ignored.\n\n");
+ if (!opt_ignore(opt, child, true)) {
+ return NULL;
+ }
continue;
}
@@ -1976,8 +2036,8 @@ static struct bfs_expr *simplify_and(struct bfs_opt *opt, struct bfs_expr *expr,
bfs_expr_append(expr, child);
if (child->always_false) {
- while ((child = SLIST_POP(&children))) {
- opt_delete(opt, "%pe [short-circuit]\n", child);
+ drain_slist (struct bfs_expr, dead, &children) {
+ opt_delete(opt, "%pe [short-circuit]\n", dead);
}
}
}
@@ -2002,16 +2062,15 @@ static struct bfs_expr *simplify_or(struct bfs_opt *opt, struct bfs_expr *expr,
struct bfs_exprs children;
foster_children(expr, &children);
- while (!SLIST_EMPTY(&children)) {
- struct bfs_expr *child = SLIST_POP(&children);
-
+ drain_slist (struct bfs_expr, child, &children) {
if (child == ignorable) {
ignore = true;
}
if (ignore) {
- opt_delete(opt, "%pe [ignored result]\n", child);
- opt_warning(opt, child, "The result of this expression is ignored.\n\n");
+ if (!opt_ignore(opt, child, true)) {
+ return NULL;
+ }
continue;
}
@@ -2024,8 +2083,8 @@ static struct bfs_expr *simplify_or(struct bfs_opt *opt, struct bfs_expr *expr,
bfs_expr_append(expr, child);
if (child->always_true) {
- while ((child = SLIST_POP(&children))) {
- opt_delete(opt, "%pe [short-circuit]\n", child);
+ drain_slist (struct bfs_expr, dead, &children) {
+ opt_delete(opt, "%pe [short-circuit]\n", dead);
}
}
}
@@ -2047,12 +2106,11 @@ static struct bfs_expr *simplify_comma(struct bfs_opt *opt, struct bfs_expr *exp
struct bfs_exprs children;
foster_children(expr, &children);
- while (!SLIST_EMPTY(&children)) {
- struct bfs_expr *child = SLIST_POP(&children);
-
+ drain_slist (struct bfs_expr, child, &children) {
if (opt->level >= 2 && child->pure && !SLIST_EMPTY(&children)) {
- opt_delete(opt, "%pe [ignored result]\n", child);
- opt_warning(opt, child, "The result of this expression is ignored.\n\n");
+ if (!opt_ignore(opt, child, true)) {
+ return NULL;
+ }
continue;
}
@@ -2103,6 +2161,8 @@ static struct bfs_expr *optimize(struct bfs_opt *opt, struct bfs_expr *expr) {
};
struct df_domain impure;
+ df_init_top(&opt->after_true);
+ df_init_top(&opt->after_false);
for (int i = 0; i < 3; ++i) {
struct bfs_opt nested = *opt;
@@ -2116,9 +2176,11 @@ static struct bfs_expr *optimize(struct bfs_opt *opt, struct bfs_expr *expr) {
continue;
}
+ const struct visitor *visitor = passes[j].visitor;
+
// Skip reordering the first time through the passes, to
// make warnings more understandable
- if (passes[j].visitor == &reorder) {
+ if (visitor == &reorder) {
if (i == 0) {
continue;
} else {
@@ -2126,10 +2188,15 @@ static struct bfs_expr *optimize(struct bfs_opt *opt, struct bfs_expr *expr) {
}
}
- expr = visit(&nested, expr, passes[j].visitor);
+ expr = visit(&nested, expr, visitor);
if (!expr) {
return NULL;
}
+
+ if (visitor == &data_flow) {
+ opt->after_true = nested.after_true;
+ opt->after_false = nested.after_false;
+ }
}
opt_leave(&nested, NULL);
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-04 13:01:11 +0000