From da4b02f9d020f1d701e22921702b156d3c810f4c Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Sun, 30 Aug 2015 14:13:53 -0400
Subject: Parse command line expressions properly.

---
 bfs.c | 553 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 492 insertions(+), 61 deletions(-)

diff --git a/bfs.c b/bfs.c
index 6bbfa05..da9479c 100644
--- a/bfs.c
+++ b/bfs.c
@@ -18,6 +18,470 @@
 #include <sys/resource.h>
 #include <unistd.h>
 
+/**
+ * A command line expression.
+ */
+typedef struct expression expression;
+
+/**
+ * The parsed command line.
+ */
+typedef struct cmdline cmdline;
+
+/**
+ * Expression evaluation function.
+ *
+ * @param fpath
+ *         The path to the encountered file.
+ * @param ftwbuf
+ *         Additional data about the current file.
+ * @param cmdline
+ *         The parsed command line.
+ * @param expr
+ *         The current expression.
+ * @param ret
+ *         A pointer to the bftw() callback return value.
+ * @return
+ *         The result of the test.
+ */
+typedef bool eval_fn(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret);
+
+struct expression {
+	/** The left hand side of the expression. */
+	expression *lhs;
+	/** The right hand side of the expression. */
+	expression *rhs;
+	/** The function that evaluates this expression. */
+	eval_fn *eval;
+	/** Optional data for this expression. */
+	int data;
+};
+
+/**
+ * Create a new expression.
+ */
+static expression *new_expression(expression *lhs, expression *rhs, eval_fn *eval, int data) {
+	expression *expr = malloc(sizeof(expression));
+	if (!expr) {
+		perror("malloc()");
+		return NULL;
+	}
+
+	expr->lhs = lhs;
+	expr->rhs = rhs;
+	expr->eval = eval;
+	expr->data = data;
+	return expr;
+}
+
+/**
+ * Free an expression.
+ */
+static void free_expression(expression *expr) {
+	if (expr) {
+		free_expression(expr->lhs);
+		free_expression(expr->rhs);
+		free(expr);
+	}
+}
+
+struct cmdline {
+	/** The array of paths to start from. */
+	const char **roots;
+	/** The number of root paths. */
+	size_t nroots;
+
+	/** Color data. */
+	color_table *colors;
+	/** -color option. */
+	bool color;
+
+	/** bftw() flags. */
+	int flags;
+
+	/** The command line expression. */
+	expression *expr;
+};
+
+/**
+ * Free the parsed command line.
+ */
+static void free_cmdline(cmdline *cl) {
+	if (cl) {
+		free_expression(cl->expr);
+		free(cl->roots);
+		free(cl);
+	}
+}
+
+/**
+ * Add a root path to the cmdline.
+ */
+static bool cmdline_add_root(cmdline *cl, const char *root) {
+	size_t i = cl->nroots++;
+	const char **roots = realloc(cl->roots, cl->nroots*sizeof(const char *));
+	if (!roots) {
+		perror("realloc()");
+		return false;
+	}
+
+	roots[i] = root;
+	cl->roots = roots;
+	return true;
+}
+
+/**
+ * Ephemeral state for parsing the command line.
+ */
+typedef struct {
+	/** The command line being parsed. */
+	cmdline *cl;
+	/** The command line arguments. */
+	char **argv;
+	/** Current argument index. */
+	int i;
+
+	/** Whether a -print action is implied. */
+	bool implicit_print;
+} parser_state;
+
+/**
+ * Parse the expression specified on the command line.
+ */
+static expression *parse_expression(parser_state *state);
+
+/**
+ * While parsing an expression, skip any paths and add them to the cmdline.
+ */
+static const char *skip_paths(parser_state *state) {
+	while (true) {
+		const char *arg = state->argv[state->i];
+		if (!arg
+		    || arg[0] == '-'
+		    || strcmp(arg, "(") == 0
+		    || strcmp(arg, ")") == 0
+		    || strcmp(arg, "!") == 0
+		    || strcmp(arg, ",") == 0) {
+			return arg;
+		}
+
+		if (!cmdline_add_root(state->cl, arg)) {
+			return NULL;
+		}
+
+		++state->i;
+	}
+}
+
+/**
+ * Always true.
+ */
+static bool eval_true(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	return true;
+}
+
+/**
+ * -print action.
+ */
+static bool eval_print(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	pretty_print(cl->colors, fpath, ftwbuf->statbuf);
+	return true;
+}
+
+/**
+ * -prune action.
+ */
+static bool eval_prune(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	*ret = BFTW_SKIP_SUBTREE;
+	return true;
+}
+
+/**
+ * -hidden test.
+ */
+static bool eval_hidden(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	return ftwbuf->base > 0 && fpath[ftwbuf->base] == '.';
+}
+
+/**
+ * -nohidden action.
+ */
+static bool eval_nohidden(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	return !eval_hidden(fpath, ftwbuf, cl, expr, ret)
+		|| eval_prune(fpath, ftwbuf, cl, expr, ret);
+}
+
+/**
+ * LITERAL : OPTION
+ *         | TEST
+ *         | ACTION
+ */
+static expression *parse_literal(parser_state *state) {
+	// Paths are already skipped at this point
+	const char *arg = state->argv[state->i++];
+
+	if (strcmp(arg, "-color") == 0) {
+		state->cl->color = true;
+		return new_expression(NULL, NULL, eval_true, 0);
+	} else if (strcmp(arg, "-nocolor") == 0) {
+		state->cl->color = false;
+		return new_expression(NULL, NULL, eval_true, 0);
+	} else if (strcmp(arg, "-hidden") == 0) {
+		return new_expression(NULL, NULL, eval_hidden, 0);
+	} else if (strcmp(arg, "-nohidden") == 0) {
+		return new_expression(NULL, NULL, eval_nohidden, 0);
+	} else if (strcmp(arg, "-print") == 0) {
+		state->implicit_print = false;
+		return new_expression(NULL, NULL, eval_print, 0);
+	} else if (strcmp(arg, "-prune") == 0) {
+		return new_expression(NULL, NULL, eval_prune, 0);
+	} else {
+		fprintf(stderr,  "Unknown argument '%s'.\n", arg);
+		return NULL;
+	}
+}
+
+/**
+ * Evaluate a negation.
+ */
+static bool eval_not(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	return !expr->rhs->eval(fpath, ftwbuf, cl, expr->rhs, ret);
+}
+
+/**
+ * FACTOR : "(" EXPR ")"
+ *        | "!" FACTOR | "-not" FACTOR
+ *        | LITERAL
+ */
+static expression *parse_factor(parser_state *state) {
+	const char *arg = skip_paths(state);
+	if (!arg) {
+		fputs("Expression terminated prematurely.\n", stderr);
+		return NULL;
+	}
+
+	if (strcmp(arg, "(") == 0) {
+		++state->i;
+		expression *expr = parse_expression(state);
+		if (!expr) {
+			return NULL;
+		}
+
+		arg = skip_paths(state);
+		if (!arg || strcmp(arg, ")") != 0) {
+			fputs("Expected a ')'.\n", stderr);
+			free_expression(expr);
+			return NULL;
+		}
+		++state->i;
+
+		return expr;
+	} else if (strcmp(arg, "!") == 0 || strcmp(arg, "-not") == 0) {
+		++state->i;
+
+		expression *factor = parse_factor(state);
+		if (!factor) {
+			return NULL;
+		}
+
+		return new_expression(NULL, factor, eval_not, 0);
+	} else {
+		return parse_literal(state);
+	}
+}
+
+/**
+ * Evaluate a conjunction.
+ */
+static bool eval_and(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	return expr->lhs->eval(fpath, ftwbuf, cl, expr->lhs, ret)
+		&& expr->rhs->eval(fpath, ftwbuf, cl, expr->rhs, ret);
+}
+
+/**
+ * TERM : FACTOR
+ *      | TERM FACTOR
+ *      | TERM "-a" FACTOR
+ *      | TERM "-and" FACTOR
+ */
+static expression *parse_term(parser_state *state) {
+	expression *term = parse_factor(state);
+
+	while (term) {
+		const char *arg = skip_paths(state);
+		if (!arg) {
+			break;
+		}
+
+		if (strcmp(arg, "-a") == 0 || strcmp(arg, "-and") == 0) {
+			++state->i;
+		}
+
+		expression *lhs = term;
+		expression *rhs = parse_factor(state);
+		if (!rhs) {
+			return NULL;
+		}
+
+		term = new_expression(lhs, rhs, eval_and, 0);
+	}
+
+	return term;
+}
+
+/**
+ * Evaluate a disjunction.
+ */
+static bool eval_or(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	return expr->lhs->eval(fpath, ftwbuf, cl, expr->lhs, ret)
+		|| expr->rhs->eval(fpath, ftwbuf, cl, expr->rhs, ret);
+}
+
+/**
+ * CLAUSE : TERM
+ *        | CLAUSE "-o" TERM
+ *        | CLAUSE "-or" TERM
+ */
+static expression *parse_clause(parser_state *state) {
+	expression *clause = parse_term(state);
+
+	while (clause) {
+		const char *arg = skip_paths(state);
+		if (!arg) {
+			break;
+		}
+
+		if (strcmp(arg, "-o") != 0 && strcmp(arg, "-or") != 0) {
+			break;
+		}
+
+		++state->i;
+
+		expression *lhs = clause;
+		expression *rhs = parse_term(state);
+		if (!rhs) {
+			return NULL;
+		}
+
+		clause = new_expression(lhs, rhs, eval_or, 0);
+	}
+
+	return clause;
+}
+
+/**
+ * Evaluate the comma operator.
+ */
+static bool eval_comma(const char *fpath, const struct BFTW *ftwbuf, const cmdline *cl, const expression *expr, int *ret) {
+	expr->lhs->eval(fpath, ftwbuf, cl, expr->lhs, ret);
+	return expr->rhs->eval(fpath, ftwbuf, cl, expr->rhs, ret);
+}
+
+/**
+ * EXPR : CLAUSE
+ *      | EXPR "," CLAUSE
+ */
+static expression *parse_expression(parser_state *state) {
+	expression *expr = parse_clause(state);
+
+	while (expr) {
+		const char *arg = skip_paths(state);
+		if (!arg) {
+			break;
+		}
+
+		if (strcmp(arg, ",") != 0) {
+			break;
+		}
+
+		++state->i;
+
+		expression *lhs = expr;
+		expression *rhs = parse_clause(state);
+		if (!rhs) {
+			return NULL;
+		}
+
+		expr = new_expression(lhs, rhs, eval_comma, 0);
+	}
+
+	return expr;
+}
+
+/**
+ * Parse the command line.
+ */
+static cmdline *parse_cmdline(int argc, char *argv[]) {
+	cmdline *cl = malloc(sizeof(cmdline));
+	if (!cl) {
+		goto fail;
+	}
+
+	cl->roots = NULL;
+	cl->nroots = 0;
+	cl->colors = NULL;
+	cl->color = isatty(STDOUT_FILENO);
+	cl->flags = BFTW_RECOVER;
+
+	parser_state state = {
+		.cl = cl,
+		.argv = argv,
+		.i = 1,
+		.implicit_print = true,
+	};
+
+	if (skip_paths(&state)) {
+		cl->expr = parse_expression(&state);
+		if (!cl->expr) {
+			goto fail;
+		}
+	}
+
+	if (state.i < argc) {
+		fprintf(stderr, "Unexpected argument '%s'.\n", argv[state.i]);
+		goto fail;
+	}
+
+	if (state.implicit_print) {
+		expression *print = new_expression(NULL, NULL, eval_print, 0);
+		if (!print) {
+			goto fail;
+		}
+
+		if (cl->expr) {
+			expression *expr = new_expression(cl->expr, print, eval_and, 0);
+			if (!expr) {
+				free_expression(print);
+				goto fail;
+			}
+
+			cl->expr = expr;
+		} else {
+			cl->expr = print;
+		}
+	}
+
+	if (cl->nroots == 0) {
+		if (!cmdline_add_root(cl, ".")) {
+			goto fail;
+		}
+	}
+
+	if (cl->color) {
+		cl->colors = parse_colors(getenv("LS_COLORS"));
+		cl->flags |= BFTW_STAT;
+	}
+
+	return cl;
+
+fail:
+	free_cmdline(cl);
+	return NULL;
+}
+
+/**
+ * Infer the number of open file descriptors we're allowed to have.
+ */
 static int infer_nopenfd() {
 	int ret = 4096;
 
@@ -36,82 +500,49 @@ static int infer_nopenfd() {
 	return ret;
 }
 
-typedef struct {
-	const char *path;
-	color_table *colors;
-	bool hidden;
-} options;
-
-static int callback(const char *fpath, const struct BFTW *ftwbuf, void *ptr) {
-	const options *opts = ptr;
+/**
+ * bftw() callback.
+ */
+static int cmdline_callback(const char *fpath, const struct BFTW *ftwbuf, void *ptr) {
+	const cmdline *cl = ptr;
 
 	if (ftwbuf->typeflag == BFTW_ERROR) {
-		print_error(opts->colors, fpath, ftwbuf);
+		print_error(cl->colors, fpath, ftwbuf);
 		return BFTW_SKIP_SUBTREE;
 	}
 
-	if (!opts->hidden) {
-		if (ftwbuf->base > 0 && fpath[ftwbuf->base] == '.') {
-			return BFTW_SKIP_SUBTREE;
+	int ret = BFTW_CONTINUE;
+	cl->expr->eval(fpath, ftwbuf, cl, cl->expr, &ret);
+	return ret;
+}
+
+/**
+ * Evaluate the command line.
+ */
+static int cmdline_eval(cmdline *cl) {
+	int ret = 0;
+	int nopenfd = infer_nopenfd();
+
+	for (size_t i = 0; i < cl->nroots; ++i) {
+		if (bftw(cl->roots[i], cmdline_callback, nopenfd, cl->flags, cl) != 0) {
+			ret = -1;
+			perror("bftw()");
 		}
 	}
 
-	pretty_print(opts->colors, fpath, ftwbuf->statbuf);
-	return BFTW_CONTINUE;
+	return ret;
 }
 
 int main(int argc, char *argv[]) {
 	int ret = EXIT_FAILURE;
 
-	options opts;
-	opts.path = NULL;
-	opts.colors = NULL;
-	opts.hidden = true;
-
-	bool color = isatty(STDOUT_FILENO);
-
-	for (int i = 1; i < argc; ++i) {
-		const char *arg = argv[i];
-
-		if (strcmp(arg, "-color") == 0) {
-			color = true;
-		} else if (strcmp(arg, "-nocolor") == 0) {
-			color = false;
-		} else if (strcmp(arg, "-hidden") == 0) {
-			opts.hidden = true;
-		} else if (strcmp(arg, "-nohidden") == 0) {
-			opts.hidden = false;
-		} else if (arg[0] == '-') {
-			fprintf(stderr, "Unknown option `%s`.", arg);
-			goto done;
-		} else {
-			if (opts.path) {
-				fprintf(stderr, "Duplicate path `%s` on command line.", arg);
-				goto done;
-			}
-			opts.path = arg;
+	cmdline *cl = parse_cmdline(argc, argv);
+	if (cl) {
+		if (cmdline_eval(cl) == 0) {
+			ret = EXIT_SUCCESS;
 		}
 	}
 
-	if (!opts.path) {
-		opts.path = ".";
-	}
-
-	int flags = BFTW_RECOVER;
-
-	if (color) {
-		flags |= BFTW_STAT;
-		opts.colors = parse_colors(getenv("LS_COLORS"));
-	}
-
-	int nopenfd = infer_nopenfd();
-	if (bftw(opts.path, callback, nopenfd, flags, &opts) != 0) {
-		perror("bftw()");
-		goto done;
-	}
-
-	ret = EXIT_SUCCESS;
-done:
-	free_colors(opts.colors);
+	free_cmdline(cl);
 	return ret;
 }
-- 
cgit v1.2.3