Implement -exclude, a special form for convenient exclusions

Fixes #8.

10 files changed, 146 insertions, 21 deletions

diff --git a/README.md b/README.md
index 1fcebbd..5cb0ca4 100644
--- a/README.md
+++ b/README.md
@@ -94,9 +94,9 @@ $ <strong>bfs</strong> -L <em>haystack</em> -name 'needle'
 </pre>
 
 `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
--- /dev/null
+++ b/tests/test_exclude_mindepth.out
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