summaryrefslogtreecommitdiffstats
path: root/bfs.c
diff options
context:
space:
mode:
Diffstat (limited to 'bfs.c')
-rw-r--r--bfs.c553
1 files 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;
}