From 1bce3b33acbfcfbfa03f1174d6e00c125cd8625d Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sun, 7 Jun 2020 14:04:20 -0400 Subject: Implement -exclude, a special form for convenient exclusions Fixes #8. --- README.md | 4 +-- bfs.1 | 22 +++++++++++++--- cmdline.h | 4 ++- eval.c | 5 ++++ opt.c | 57 +++++++++++++++++++++++++++++++---------- parse.c | 31 ++++++++++++++++++++++ tests.sh | 18 +++++++++++++ tests/test_exclude_depth.out | 13 ++++++++++ tests/test_exclude_mindepth.out | 0 tests/test_exclude_name.out | 13 ++++++++++ 10 files changed, 146 insertions(+), 21 deletions(-) create mode 100644 tests/test_exclude_depth.out create mode 100644 tests/test_exclude_mindepth.out create mode 100644 tests/test_exclude_name.out diff --git a/README.md b/README.md index 1fcebbd..5cb0ca4 100644 --- a/README.md +++ b/README.md @@ -94,9 +94,9 @@ $ bfs -L haystack -name 'needle' `bfs` also adds some extra options that make some common tasks easier. -Compare `bfs -nohidden` to +Compare `bfs -name config -exclude -name .git` to - find -name '.?*' -prune -o -print + find ! \( -name '.git' -prune \) -name config Try it! diff --git a/bfs.1 b/bfs.1 index 64c03b2..f308961 100644 --- a/bfs.1 +++ b/bfs.1 @@ -154,7 +154,7 @@ Use .IR d eepening .IR s earch (default: -.B -S +.B \-S .IR bfs ). .RE .SH OPERATORS @@ -211,6 +211,20 @@ The "comma" operator: evaluates the left-hand .I expression but discards the result, returning the right-hand .IR expression . +.SH SPECIAL FORMS +.TP +\fB\-exclude \fIexpression\fR +Exclude all paths matching the +.I expression +from the search. +This is more powerful than +.BR \-prune , +because it applies even when the expression wouldn't otherwise be evaluated, due to +.B \-depth +or +.B \-mindepth +for example. +Exclusions are always applied before other expressions, so it may be least confusing to put them first on the command line. .SH OPTIONS .PP .B \-color @@ -607,7 +621,7 @@ Like but use the null character ('\\0') as a separator rather than newlines. Useful in conjunction with .B xargs -.IR -0 . +.IR \-0 . .TP \fB\-printf \fIFORMAT\fR Print according to a format string (see @@ -662,7 +676,7 @@ is quoted to ensure the glob is processed by .B bfs rather than the shell. .TP -\fBbfs \-name access_log -L \fI/var\fR +\fBbfs \-name access_log \-L \fI/var\fR Finds all files named .B access_log under @@ -677,7 +691,7 @@ Prints all files in your home directory not owned by you. .B bfs \-xtype l Finds broken symbolic links. .TP -.B bfs \-name .git \-prune \-false \-o \-name config +.B bfs \-name config \-exclude \-name .git Finds all files named .BR config, skipping every diff --git a/cmdline.h b/cmdline.h index 29da3fa..309dfa3 100644 --- a/cmdline.h +++ b/cmdline.h @@ -100,7 +100,9 @@ struct cmdline { /** Whether to only handle paths with xargs-safe characters (-X). */ bool xargs_safe; - /** The command line expression. */ + /** An expression for files to filter out. */ + struct expr *exclude; + /** The main command line expression. */ struct expr *expr; /** All the open files owned by the command line. */ diff --git a/eval.c b/eval.c index 114bb53..41e0377 100644 --- a/eval.c +++ b/eval.c @@ -1193,6 +1193,11 @@ static enum bftw_action cmdline_callback(const struct BFTW *ftwbuf, void *ptr) { } } + if (eval_expr(cmdline->exclude, &state)) { + state.action = BFTW_PRUNE; + goto done; + } + if (cmdline->xargs_safe && strpbrk(ftwbuf->path, " \t\n\'\"\\")) { args->ret = EXIT_FAILURE; eval_error(&state, "Path is not safe for xargs.\n"); diff --git a/opt.c b/opt.c index 820f421..6a62790 100644 --- a/opt.c +++ b/opt.c @@ -803,6 +803,13 @@ static struct expr *optimize_expr_recursive(struct opt_state *state, struct expr state->facts_when_true = state->facts; state->facts_when_false = state->facts; + if (facts_are_impossible(&state->facts)) { + debug_opt(state, 2, "reachability: %pe --> %pe\n", expr, &expr_false); + free_expr(expr); + expr = &expr_false; + goto done; + } + if (!expr->rhs && !expr->pure) { facts_union(state->facts_when_impure, state->facts_when_impure, &state->facts); } @@ -953,6 +960,29 @@ static bool reorder_expr_recursive(const struct opt_state *state, struct expr *e return ret; } +/** + * Optimize a top-level expression. + */ +static struct expr *optimize_expr(struct opt_state *state, struct expr *expr) { + struct opt_facts saved_impure = *state->facts_when_impure; + + expr = optimize_expr_recursive(state, expr); + if (!expr) { + return NULL; + } + + if (state->cmdline->optlevel >= 3 && reorder_expr_recursive(state, expr)) { + // Re-do optimizations to account for the new ordering + *state->facts_when_impure = saved_impure; + expr = optimize_expr_recursive(state, expr); + if (!expr) { + return NULL; + } + } + + return expr; +} + int optimize_cmdline(struct cmdline *cmdline) { struct opt_facts facts_when_impure; set_facts_impossible(&facts_when_impure); @@ -963,32 +993,31 @@ int optimize_cmdline(struct cmdline *cmdline) { }; facts_init(&state.facts); - struct range *depth = &state.facts.ranges[DEPTH_RANGE]; - depth->min = cmdline->mindepth; - depth->max = cmdline->maxdepth; + cmdline->exclude = optimize_expr(&state, cmdline->exclude); + if (!cmdline->exclude) { + return -1; + } - int optlevel = cmdline->optlevel; + // Only non-excluded files are evaluated + state.facts = state.facts_when_false; + + struct range *depth = &state.facts.ranges[DEPTH_RANGE]; + constrain_min(depth, cmdline->mindepth); + constrain_max(depth, cmdline->maxdepth); - cmdline->expr = optimize_expr_recursive(&state, cmdline->expr); + cmdline->expr = optimize_expr(&state, cmdline->expr); if (!cmdline->expr) { return -1; } - if (optlevel >= 3 && reorder_expr_recursive(&state, cmdline->expr)) { - // Re-do optimizations to account for the new ordering - set_facts_impossible(&facts_when_impure); - cmdline->expr = optimize_expr_recursive(&state, cmdline->expr); - if (!cmdline->expr) { - return -1; - } - } - cmdline->expr = ignore_result(&state, cmdline->expr); const struct range *depth_when_impure = &facts_when_impure.ranges[DEPTH_RANGE]; long long mindepth = depth_when_impure->min; long long maxdepth = depth_when_impure->max; + int optlevel = cmdline->optlevel; + if (optlevel >= 2 && mindepth > cmdline->mindepth) { if (mindepth > INT_MAX) { mindepth = INT_MAX; diff --git a/parse.c b/parse.c index 301e5df..23aefba 100644 --- a/parse.c +++ b/parse.c @@ -61,6 +61,7 @@ // Strings printed by -D tree for "fake" expressions static char *fake_and_arg = "-a"; static char *fake_false_arg = "-false"; +static char *fake_or_arg = "-o"; static char *fake_print_arg = "-print"; static char *fake_true_arg = "-true"; @@ -227,6 +228,7 @@ int free_cmdline(struct cmdline *cmdline) { CFILE *cerr = cmdline->cerr; free_expr(cmdline->expr); + free_expr(cmdline->exclude); free_bfs_mtab(cmdline->mtab); @@ -2651,6 +2653,11 @@ static struct expr *parse_help(struct parser_state *state, int arg1, int arg2) { cfprintf(cout, " ${blu}expression${rs} ${red},${rs} ${blu}expression${rs}\n\n"); + cfprintf(cout, "${bld}Special forms:${rs}\n\n"); + + cfprintf(cout, " ${red}-exclude${rs} ${blu}expression${rs}\n"); + cfprintf(cout, " Exclude all paths matching the ${blu}expression${rs} from the search.\n\n"); + cfprintf(cout, "${bld}Options:${rs}\n\n"); cfprintf(cout, " ${blu}-color${rs}\n"); @@ -2904,6 +2911,7 @@ static const struct table_entry parse_table[] = { {"-delete", T_ACTION, parse_delete}, {"-depth", T_OPTION, parse_depth_n}, {"-empty", T_TEST, parse_empty}, + {"-exclude", T_OPERATOR}, {"-exec", T_ACTION, parse_exec, 0}, {"-execdir", T_ACTION, parse_exec, BFS_EXEC_CHDIR}, {"-executable", T_TEST, parse_access, X_OK}, @@ -3084,6 +3092,7 @@ unexpected: /** * FACTOR : "(" EXPR ")" * | "!" FACTOR | "-not" FACTOR + * | "-exclude" FACTOR * | LITERAL */ static struct expr *parse_factor(struct parser_state *state) { @@ -3119,6 +3128,21 @@ static struct expr *parse_factor(struct parser_state *state) { parser_advance(state, T_OPERATOR, 1); return expr; + } else if (strcmp(arg, "-exclude") == 0) { + parser_advance(state, T_OPERATOR, 1); + + struct expr *factor = parse_factor(state); + if (!factor) { + return NULL; + } + + struct cmdline *cmdline = state->cmdline; + cmdline->exclude = new_binary_expr(eval_or, cmdline->exclude, factor, &fake_or_arg); + if (!cmdline->exclude) { + return NULL; + } + + return &expr_true; } else if (strcmp(arg, "!") == 0 || strcmp(arg, "-not") == 0) { char **argv = parser_advance(state, T_OPERATOR, 1); @@ -3411,8 +3435,14 @@ void dump_cmdline(const struct cmdline *cmdline, enum debug_flags flag) { } if (flag == DEBUG_RATES) { + if (cmdline->exclude != &expr_false) { + cfprintf(cerr, "${red}-exclude${rs} %pE ", cmdline->exclude); + } cfprintf(cerr, "%pE", cmdline->expr); } else { + if (cmdline->exclude != &expr_false) { + cfprintf(cerr, "${red}-exclude${rs} %pe ", cmdline->exclude); + } cfprintf(cerr, "%pe", cmdline->expr); } @@ -3482,6 +3512,7 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) { cmdline->unique = false; cmdline->warn = false; cmdline->xargs_safe = false; + cmdline->exclude = &expr_false; cmdline->expr = &expr_true; cmdline->nopen_files = 0; diff --git a/tests.sh b/tests.sh index c84907c..c428c65 100755 --- a/tests.sh +++ b/tests.sh @@ -596,6 +596,12 @@ bfs_tests=( test_S_dfs test_S_ids + # Special forms + + test_exclude_name + test_exclude_depth + test_exclude_mindepth + # Primaries test_color @@ -2630,6 +2636,18 @@ function test_S_ids() { test_S ids } +function test_exclude_name() { + bfs_diff basic -exclude -name foo +} + +function test_exclude_depth() { + bfs_diff basic -depth -exclude -name foo +} + +function test_exclude_mindepth() { + bfs_diff basic -mindepth 3 -exclude -name foo +} + BOL= EOL='\n' diff --git a/tests/test_exclude_depth.out b/tests/test_exclude_depth.out new file mode 100644 index 0000000..40e2ea0 --- /dev/null +++ b/tests/test_exclude_depth.out @@ -0,0 +1,13 @@ +basic +basic/a +basic/b +basic/c +basic/e +basic/g +basic/i +basic/j +basic/k +basic/l +basic/c/d +basic/e/f +basic/g/h diff --git a/tests/test_exclude_mindepth.out b/tests/test_exclude_mindepth.out new file mode 100644 index 0000000..e69de29 diff --git a/tests/test_exclude_name.out b/tests/test_exclude_name.out new file mode 100644 index 0000000..40e2ea0 --- /dev/null +++ b/tests/test_exclude_name.out @@ -0,0 +1,13 @@ +basic +basic/a +basic/b +basic/c +basic/e +basic/g +basic/i +basic/j +basic/k +basic/l +basic/c/d +basic/e/f +basic/g/h -- cgit v1.2.3