summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile2
-rw-r--r--bfs.h332
-rw-r--r--cmdline.h123
-rw-r--r--eval.c5
-rw-r--r--eval.h73
-rw-r--r--exec.c2
-rw-r--r--expr.h225
-rw-r--r--main.c2
-rw-r--r--opt.c410
-rw-r--r--parse.c347
-rw-r--r--printf.c3
11 files changed, 859 insertions, 665 deletions
diff --git a/Makefile b/Makefile
index 62d72f2..0704d57 100644
--- a/Makefile
+++ b/Makefile
@@ -49,7 +49,7 @@ ALL_LDFLAGS = $(ALL_CFLAGS) $(LDFLAGS)
all: bfs
-bfs: bftw.o color.o dstring.o eval.o exec.o main.o mtab.o parse.o printf.o typo.o util.o
+bfs: bftw.o color.o dstring.o eval.o exec.o main.o mtab.o opt.o parse.o printf.o typo.o util.o
$(CC) $(ALL_LDFLAGS) $^ -o $@
release: CFLAGS := -O3 -flto $(WFLAGS) -DNDEBUG -g
diff --git a/bfs.h b/bfs.h
index 9c79449..909e76f 100644
--- a/bfs.h
+++ b/bfs.h
@@ -17,17 +17,6 @@
#ifndef BFS_H
#define BFS_H
-#include "color.h"
-#include "exec.h"
-#include "printf.h"
-#include "mtab.h"
-#include <regex.h>
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdio.h>
-#include <sys/types.h>
-#include <time.h>
-
#ifndef BFS_VERSION
# define BFS_VERSION "1.1.2"
#endif
@@ -36,325 +25,4 @@
# define BFS_HOMEPAGE "https://github.com/tavianator/bfs"
#endif
-/**
- * A command line expression.
- */
-struct expr;
-
-/**
- * Ephemeral state for evaluating an expression.
- */
-struct eval_state;
-
-/**
- * Expression evaluation function.
- *
- * @param expr
- * The current expression.
- * @param state
- * The current evaluation state.
- * @return
- * The result of the test.
- */
-typedef bool eval_fn(const struct expr *expr, struct eval_state *state);
-
-/**
- * Various debugging flags.
- */
-enum debug_flags {
- /** Print cost estimates. */
- DEBUG_COST = 1 << 0,
- /** Print executed command details. */
- DEBUG_EXEC = 1 << 1,
- /** Print optimization details. */
- DEBUG_OPT = 1 << 2,
- /** Print rate information. */
- DEBUG_RATES = 1 << 3,
- /** Trace the filesystem traversal. */
- DEBUG_SEARCH = 1 << 4,
- /** Trace all stat() calls. */
- DEBUG_STAT = 1 << 5,
- /** Print the parse tree. */
- DEBUG_TREE = 1 << 6,
-};
-
-/**
- * A root path to explore.
- */
-struct root {
- /** The root path itself. */
- const char *path;
- /** The next path in the list. */
- struct root *next;
-};
-
-/**
- * The parsed command line.
- */
-struct cmdline {
- /** The unparsed command line arguments. */
- char **argv;
-
- /** The list of root paths. */
- struct root *roots;
-
- /** Color data. */
- struct colors *colors;
- /** Colored stdout. */
- CFILE *cout;
- /** Colored stderr. */
- CFILE *cerr;
-
- /** Table of mounted file systems. */
- struct bfs_mtab *mtab;
-
- /** -mindepth option. */
- int mindepth;
- /** -maxdepth option. */
- int maxdepth;
-
- /** bftw() flags. */
- enum bftw_flags flags;
-
- /** Optimization level. */
- int optlevel;
- /** Debugging flags. */
- enum debug_flags debug;
- /** Whether to only handle paths with xargs-safe characters. */
- bool xargs_safe;
- /** Whether to ignore deletions that race with bfs. */
- bool ignore_races;
-
- /** The command line expression. */
- struct expr *expr;
-
- /** The number of open files used by the expression tree. */
- int nopen_files;
-};
-
-/**
- * Possible types of numeric comparison.
- */
-enum cmp_flag {
- /** Exactly n. */
- CMP_EXACT,
- /** Less than n. */
- CMP_LESS,
- /** Greater than n. */
- CMP_GREATER,
-};
-
-/**
- * Possible types of mode comparison.
- */
-enum mode_cmp {
- /** Mode is an exact match (MODE). */
- MODE_EXACT,
- /** Mode has all these bits (-MODE). */
- MODE_ALL,
- /** Mode has any of these bits (/MODE). */
- MODE_ANY,
-};
-
-/**
- * Available struct stat time fields.
- */
-enum time_field {
- /** Access time. */
- ATIME,
- /** Status change time. */
- CTIME,
- /** Modification time. */
- MTIME,
-};
-
-/**
- * Possible time units.
- */
-enum time_unit {
- /** Minutes. */
- MINUTES,
- /** Days. */
- DAYS,
-};
-
-/**
- * Possible file size units.
- */
-enum size_unit {
- /** 512-byte blocks. */
- SIZE_BLOCKS,
- /** Single bytes. */
- SIZE_BYTES,
- /** Two-byte words. */
- SIZE_WORDS,
- /** Kibibytes. */
- SIZE_KB,
- /** Mebibytes. */
- SIZE_MB,
- /** Gibibytes. */
- SIZE_GB,
- /** Tebibytes. */
- SIZE_TB,
- /** Pebibytes. */
- SIZE_PB,
-};
-
-struct expr {
- /** The function that evaluates this expression. */
- eval_fn *eval;
-
- /** The left hand side of the expression. */
- struct expr *lhs;
- /** The right hand side of the expression. */
- struct expr *rhs;
-
- /** Whether this expression has no side effects. */
- bool pure;
- /** Whether this expression always evaluates to true. */
- bool always_true;
- /** Whether this expression always evaluates to false. */
- bool always_false;
-
- /** Estimated cost. */
- double cost;
- /** Estimated probability of success. */
- double probability;
- /** Number of times this predicate was executed. */
- size_t evaluations;
- /** Number of times this predicate succeeded. */
- size_t successes;
- /** Total time spent running this predicate. */
- struct timespec elapsed;
-
- /** The number of command line arguments for this expression. */
- size_t argc;
- /** The command line arguments comprising this expression. */
- char **argv;
-
- /** The optional comparison flag. */
- enum cmp_flag cmp_flag;
-
- /** The mode comparison flag. */
- enum mode_cmp mode_cmp;
- /** Mode to use for files. */
- mode_t file_mode;
- /** Mode to use for directories (different due to X). */
- mode_t dir_mode;
-
- /** The optional reference time. */
- struct timespec reftime;
- /** The optional time field. */
- enum time_field time_field;
- /** The optional time unit. */
- enum time_unit time_unit;
-
- /** The optional size unit. */
- enum size_unit size_unit;
-
- /** Optional device number for a target file. */
- dev_t dev;
- /** Optional inode number for a target file. */
- ino_t ino;
-
- /** File to output to. */
- CFILE *cfile;
-
- /** Optional compiled regex. */
- regex_t *regex;
-
- /** Optional exec command. */
- struct bfs_exec *execbuf;
-
- /** Optional printf command. */
- struct bfs_printf *printf;
-
- /** Optional integer data for this expression. */
- long long idata;
-
- /** Optional string data for this expression. */
- const char *sdata;
-};
-
-/**
- * @return Whether expr is known to always quit.
- */
-bool expr_never_returns(const struct expr *expr);
-
-/**
- * @return The result of the comparison for this expression.
- */
-bool expr_cmp(const struct expr *expr, long long n);
-
-/**
- * Parse the command line.
- */
-struct cmdline *parse_cmdline(int argc, char *argv[]);
-
-/**
- * Dump the parsed command line.
- */
-void dump_cmdline(const struct cmdline *cmdline, bool verbose);
-
-/**
- * Evaluate the command line.
- */
-int eval_cmdline(const struct cmdline *cmdline);
-
-/**
- * Free the parsed command line.
- */
-void free_cmdline(struct cmdline *cmdline);
-
-// Predicate evaluation functions
-bool eval_true(const struct expr *expr, struct eval_state *state);
-bool eval_false(const struct expr *expr, struct eval_state *state);
-
-bool eval_access(const struct expr *expr, struct eval_state *state);
-bool eval_perm(const struct expr *expr, struct eval_state *state);
-
-bool eval_acmtime(const struct expr *expr, struct eval_state *state);
-bool eval_acnewer(const struct expr *expr, struct eval_state *state);
-bool eval_used(const struct expr *expr, struct eval_state *state);
-
-bool eval_gid(const struct expr *expr, struct eval_state *state);
-bool eval_uid(const struct expr *expr, struct eval_state *state);
-bool eval_nogroup(const struct expr *expr, struct eval_state *state);
-bool eval_nouser(const struct expr *expr, struct eval_state *state);
-
-bool eval_depth(const struct expr *expr, struct eval_state *state);
-bool eval_empty(const struct expr *expr, struct eval_state *state);
-bool eval_fstype(const struct expr *expr, struct eval_state *state);
-bool eval_hidden(const struct expr *expr, struct eval_state *state);
-bool eval_inum(const struct expr *expr, struct eval_state *state);
-bool eval_links(const struct expr *expr, struct eval_state *state);
-bool eval_samefile(const struct expr *expr, struct eval_state *state);
-bool eval_size(const struct expr *expr, struct eval_state *state);
-bool eval_sparse(const struct expr *expr, struct eval_state *state);
-bool eval_type(const struct expr *expr, struct eval_state *state);
-bool eval_xtype(const struct expr *expr, struct eval_state *state);
-
-bool eval_lname(const struct expr *expr, struct eval_state *state);
-bool eval_name(const struct expr *expr, struct eval_state *state);
-bool eval_path(const struct expr *expr, struct eval_state *state);
-bool eval_regex(const struct expr *expr, struct eval_state *state);
-
-bool eval_delete(const struct expr *expr, struct eval_state *state);
-bool eval_exec(const struct expr *expr, struct eval_state *state);
-bool eval_exit(const struct expr *expr, struct eval_state *state);
-bool eval_nohidden(const struct expr *expr, struct eval_state *state);
-bool eval_fls(const struct expr *expr, struct eval_state *state);
-bool eval_fprint(const struct expr *expr, struct eval_state *state);
-bool eval_fprint0(const struct expr *expr, struct eval_state *state);
-bool eval_fprintf(const struct expr *expr, struct eval_state *state);
-bool eval_fprintx(const struct expr *expr, struct eval_state *state);
-bool eval_prune(const struct expr *expr, struct eval_state *state);
-bool eval_quit(const struct expr *expr, struct eval_state *state);
-
-// Operator evaluation functions
-bool eval_not(const struct expr *expr, struct eval_state *state);
-bool eval_and(const struct expr *expr, struct eval_state *state);
-bool eval_or(const struct expr *expr, struct eval_state *state);
-bool eval_comma(const struct expr *expr, struct eval_state *state);
-
#endif // BFS_H
diff --git a/cmdline.h b/cmdline.h
new file mode 100644
index 0000000..a1dadc3
--- /dev/null
+++ b/cmdline.h
@@ -0,0 +1,123 @@
+/****************************************************************************
+ * bfs *
+ * Copyright (C) 2015-2017 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted. *
+ * *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
+ ****************************************************************************/
+
+#ifndef CMDLINE_H
+#define CMDLINE_H
+
+#include "color.h"
+
+/**
+ * Various debugging flags.
+ */
+enum debug_flags {
+ /** Print cost estimates. */
+ DEBUG_COST = 1 << 0,
+ /** Print executed command details. */
+ DEBUG_EXEC = 1 << 1,
+ /** Print optimization details. */
+ DEBUG_OPT = 1 << 2,
+ /** Print rate information. */
+ DEBUG_RATES = 1 << 3,
+ /** Trace the filesystem traversal. */
+ DEBUG_SEARCH = 1 << 4,
+ /** Trace all stat() calls. */
+ DEBUG_STAT = 1 << 5,
+ /** Print the parse tree. */
+ DEBUG_TREE = 1 << 6,
+};
+
+/**
+ * A root path to explore.
+ */
+struct root {
+ /** The root path itself. */
+ const char *path;
+ /** The next path in the list. */
+ struct root *next;
+};
+
+/**
+ * The parsed command line.
+ */
+struct cmdline {
+ /** The unparsed command line arguments. */
+ char **argv;
+
+ /** The list of root paths. */
+ struct root *roots;
+
+ /** Color data. */
+ struct colors *colors;
+ /** Colored stdout. */
+ CFILE *cout;
+ /** Colored stderr. */
+ CFILE *cerr;
+
+ /** Table of mounted file systems. */
+ struct bfs_mtab *mtab;
+
+ /** -mindepth option. */
+ int mindepth;
+ /** -maxdepth option. */
+ int maxdepth;
+
+ /** bftw() flags. */
+ enum bftw_flags flags;
+
+ /** Optimization level. */
+ int optlevel;
+ /** Debugging flags. */
+ enum debug_flags debug;
+ /** Whether to only handle paths with xargs-safe characters. */
+ bool xargs_safe;
+ /** Whether to ignore deletions that race with bfs. */
+ bool ignore_races;
+
+ /** The command line expression. */
+ struct expr *expr;
+
+ /** The number of open files used by the expression tree. */
+ int nopen_files;
+};
+
+/**
+ * Optimize the parsed command line.
+ *
+ * @return 0 if successful, -1 on error.
+ */
+int optimize_cmdline(struct cmdline *cmdline);
+
+/**
+ * Parse the command line.
+ */
+struct cmdline *parse_cmdline(int argc, char *argv[]);
+
+/**
+ * Dump the parsed command line.
+ */
+void dump_cmdline(const struct cmdline *cmdline, bool verbose);
+
+/**
+ * Evaluate the command line.
+ */
+int eval_cmdline(const struct cmdline *cmdline);
+
+/**
+ * Free the parsed command line.
+ */
+void free_cmdline(struct cmdline *cmdline);
+
+#endif // CMDLINE_H
diff --git a/eval.c b/eval.c
index 340e9eb..5196b57 100644
--- a/eval.c
+++ b/eval.c
@@ -14,11 +14,14 @@
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
****************************************************************************/
-#include "bfs.h"
+#include "eval.h"
#include "bftw.h"
+#include "cmdline.h"
#include "color.h"
#include "dstring.h"
+#include "exec.h"
#include "mtab.h"
+#include "printf.h"
#include "util.h"
#include <assert.h>
#include <dirent.h>
diff --git a/eval.h b/eval.h
new file mode 100644
index 0000000..356f332
--- /dev/null
+++ b/eval.h
@@ -0,0 +1,73 @@
+/****************************************************************************
+ * bfs *
+ * Copyright (C) 2015-2017 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted. *
+ * *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
+ ****************************************************************************/
+
+#ifndef EVAL_H
+#define EVAL_H
+
+#include "expr.h"
+
+// Predicate evaluation functions
+bool eval_true(const struct expr *expr, struct eval_state *state);
+bool eval_false(const struct expr *expr, struct eval_state *state);
+
+bool eval_access(const struct expr *expr, struct eval_state *state);
+bool eval_perm(const struct expr *expr, struct eval_state *state);
+
+bool eval_acmtime(const struct expr *expr, struct eval_state *state);
+bool eval_acnewer(const struct expr *expr, struct eval_state *state);
+bool eval_used(const struct expr *expr, struct eval_state *state);
+
+bool eval_gid(const struct expr *expr, struct eval_state *state);
+bool eval_uid(const struct expr *expr, struct eval_state *state);
+bool eval_nogroup(const struct expr *expr, struct eval_state *state);
+bool eval_nouser(const struct expr *expr, struct eval_state *state);
+
+bool eval_depth(const struct expr *expr, struct eval_state *state);
+bool eval_empty(const struct expr *expr, struct eval_state *state);
+bool eval_fstype(const struct expr *expr, struct eval_state *state);
+bool eval_hidden(const struct expr *expr, struct eval_state *state);
+bool eval_inum(const struct expr *expr, struct eval_state *state);
+bool eval_links(const struct expr *expr, struct eval_state *state);
+bool eval_samefile(const struct expr *expr, struct eval_state *state);
+bool eval_size(const struct expr *expr, struct eval_state *state);
+bool eval_sparse(const struct expr *expr, struct eval_state *state);
+bool eval_type(const struct expr *expr, struct eval_state *state);
+bool eval_xtype(const struct expr *expr, struct eval_state *state);
+
+bool eval_lname(const struct expr *expr, struct eval_state *state);
+bool eval_name(const struct expr *expr, struct eval_state *state);
+bool eval_path(const struct expr *expr, struct eval_state *state);
+bool eval_regex(const struct expr *expr, struct eval_state *state);
+
+bool eval_delete(const struct expr *expr, struct eval_state *state);
+bool eval_exec(const struct expr *expr, struct eval_state *state);
+bool eval_exit(const struct expr *expr, struct eval_state *state);
+bool eval_nohidden(const struct expr *expr, struct eval_state *state);
+bool eval_fls(const struct expr *expr, struct eval_state *state);
+bool eval_fprint(const struct expr *expr, struct eval_state *state);
+bool eval_fprint0(const struct expr *expr, struct eval_state *state);
+bool eval_fprintf(const struct expr *expr, struct eval_state *state);
+bool eval_fprintx(const struct expr *expr, struct eval_state *state);
+bool eval_prune(const struct expr *expr, struct eval_state *state);
+bool eval_quit(const struct expr *expr, struct eval_state *state);
+
+// Operator evaluation functions
+bool eval_not(const struct expr *expr, struct eval_state *state);
+bool eval_and(const struct expr *expr, struct eval_state *state);
+bool eval_or(const struct expr *expr, struct eval_state *state);
+bool eval_comma(const struct expr *expr, struct eval_state *state);
+
+#endif // EVAL_H
diff --git a/exec.c b/exec.c
index 42deccf..4b34ab6 100644
--- a/exec.c
+++ b/exec.c
@@ -15,8 +15,8 @@
****************************************************************************/
#include "exec.h"
-#include "bfs.h"
#include "bftw.h"
+#include "cmdline.h"
#include "color.h"
#include "dstring.h"
#include "util.h"
diff --git a/expr.h b/expr.h
new file mode 100644
index 0000000..0eba0da
--- /dev/null
+++ b/expr.h
@@ -0,0 +1,225 @@
+/****************************************************************************
+ * bfs *
+ * Copyright (C) 2015-2017 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted. *
+ * *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
+ ****************************************************************************/
+
+#ifndef EXPR_H
+#define EXPR_H
+
+#include "color.h"
+#include "exec.h"
+#include "printf.h"
+#include <regex.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <sys/types.h>
+#include <time.h>
+
+/**
+ * A command line expression.
+ */
+struct expr;
+
+/**
+ * Ephemeral state for evaluating an expression.
+ */
+struct eval_state;
+
+/**
+ * Expression evaluation function.
+ *
+ * @param expr
+ * The current expression.
+ * @param state
+ * The current evaluation state.
+ * @return
+ * The result of the test.
+ */
+typedef bool eval_fn(const struct expr *expr, struct eval_state *state);
+
+/**
+ * Possible types of numeric comparison.
+ */
+enum cmp_flag {
+ /** Exactly n. */
+ CMP_EXACT,
+ /** Less than n. */
+ CMP_LESS,
+ /** Greater than n. */
+ CMP_GREATER,
+};
+
+/**
+ * Possible types of mode comparison.
+ */
+enum mode_cmp {
+ /** Mode is an exact match (MODE). */
+ MODE_EXACT,
+ /** Mode has all these bits (-MODE). */
+ MODE_ALL,
+ /** Mode has any of these bits (/MODE). */
+ MODE_ANY,
+};
+
+/**
+ * Available struct stat time fields.
+ */
+enum time_field {
+ /** Access time. */
+ ATIME,
+ /** Status change time. */
+ CTIME,
+ /** Modification time. */
+ MTIME,
+};
+
+/**
+ * Possible time units.
+ */
+enum time_unit {
+ /** Minutes. */
+ MINUTES,
+ /** Days. */
+ DAYS,
+};
+
+/**
+ * Possible file size units.
+ */
+enum size_unit {
+ /** 512-byte blocks. */
+ SIZE_BLOCKS,
+ /** Single bytes. */
+ SIZE_BYTES,
+ /** Two-byte words. */
+ SIZE_WORDS,
+ /** Kibibytes. */
+ SIZE_KB,
+ /** Mebibytes. */
+ SIZE_MB,
+ /** Gibibytes. */
+ SIZE_GB,
+ /** Tebibytes. */
+ SIZE_TB,
+ /** Pebibytes. */
+ SIZE_PB,
+};
+
+struct expr {
+ /** The function that evaluates this expression. */
+ eval_fn *eval;
+
+ /** The left hand side of the expression. */
+ struct expr *lhs;
+ /** The right hand side of the expression. */
+ struct expr *rhs;
+
+ /** Whether this expression has no side effects. */
+ bool pure;
+ /** Whether this expression always evaluates to true. */
+ bool always_true;
+ /** Whether this expression always evaluates to false. */
+ bool always_false;
+
+ /** Estimated cost. */
+ double cost;
+ /** Estimated probability of success. */
+ double probability;
+ /** Number of times this predicate was executed. */
+ size_t evaluations;
+ /** Number of times this predicate succeeded. */
+ size_t successes;
+ /** Total time spent running this predicate. */
+ struct timespec elapsed;
+
+ /** The number of command line arguments for this expression. */
+ size_t argc;
+ /** The command line arguments comprising this expression. */
+ char **argv;
+
+ /** The optional comparison flag. */
+ enum cmp_flag cmp_flag;
+
+ /** The mode comparison flag. */
+ enum mode_cmp mode_cmp;
+ /** Mode to use for files. */
+ mode_t file_mode;
+ /** Mode to use for directories (different due to X). */
+ mode_t dir_mode;
+
+ /** The optional reference time. */
+ struct timespec reftime;
+ /** The optional time field. */
+ enum time_field time_field;
+ /** The optional time unit. */
+ enum time_unit time_unit;
+
+ /** The optional size unit. */
+ enum size_unit size_unit;
+
+ /** Optional device number for a target file. */
+ dev_t dev;
+ /** Optional inode number for a target file. */
+ ino_t ino;
+
+ /** File to output to. */
+ CFILE *cfile;
+
+ /** Optional compiled regex. */
+ regex_t *regex;
+
+ /** Optional exec command. */
+ struct bfs_exec *execbuf;
+
+ /** Optional printf command. */
+ struct bfs_printf *printf;
+
+ /** Optional integer data for this expression. */
+ long long idata;
+
+ /** Optional string data for this expression. */
+ const char *sdata;
+};
+
+/** Singleton true expression instance. */
+extern struct expr expr_true;
+/** Singleton false expression instance. */
+extern struct expr expr_false;
+
+/**
+ * Create a new expression.
+ */
+struct expr *new_expr(eval_fn *eval, size_t argc, char **argv);
+
+/**
+ * @return Whether expr is known to always quit.
+ */
+bool expr_never_returns(const struct expr *expr);
+
+/**
+ * @return The result of the comparison for this expression.
+ */
+bool expr_cmp(const struct expr *expr, long long n);
+
+/**
+ * Dump a parsed expression.
+ */
+void dump_expr(CFILE *cfile, const struct expr *expr, bool verbose);
+
+/**
+ * Free an expression tree.
+ */
+void free_expr(struct expr *expr);
+
+#endif // EXPR_H
diff --git a/main.c b/main.c
index b5b9a99..9e8fdbf 100644
--- a/main.c
+++ b/main.c
@@ -14,7 +14,7 @@
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
****************************************************************************/
-#include "bfs.h"
+#include "cmdline.h"
#include "util.h"
#include <errno.h>
#include <fcntl.h>
diff --git a/opt.c b/opt.c
new file mode 100644
index 0000000..8074172
--- /dev/null
+++ b/opt.c
@@ -0,0 +1,410 @@
+/****************************************************************************
+ * bfs *
+ * Copyright (C) 2017 Tavian Barnes <tavianator@tavianator.com> *
+ * *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted. *
+ * *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
+ ****************************************************************************/
+
+#include "cmdline.h"
+#include "color.h"
+#include "eval.h"
+#include "expr.h"
+#include <assert.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+static char *fake_and_arg = "-a";
+static char *fake_or_arg = "-o";
+
+/**
+ * Log an optimization.
+ */
+static void debug_opt(const struct cmdline *cmdline, const char *format, ...) {
+ if (!(cmdline->debug & DEBUG_OPT)) {
+ return;
+ }
+
+ CFILE *cerr = cmdline->cerr;
+
+ va_list args;
+ va_start(args, format);
+
+ for (const char *i = format; *i != '\0'; ++i) {
+ if (*i == '%') {
+ switch (*++i) {
+ case 'e':
+ dump_expr(cerr, va_arg(args, const struct expr *), false);
+ break;
+
+ case 'g':
+ cfprintf(cerr, "%{ylw}%g%{rs}", va_arg(args, double));
+ break;
+ }
+ } else {
+ fputc(*i, stderr);
+ }
+ }
+
+ va_end(args);
+}
+
+/**
+ * Extract a child expression, freeing the outer expression.
+ */
+static struct expr *extract_child_expr(struct expr *expr, struct expr **child) {
+ struct expr *ret = *child;
+ *child = NULL;
+ free_expr(expr);
+ return ret;
+}
+
+/**
+ * Negate an expression.
+ */
+static struct expr *negate_expr(struct expr *rhs, char **argv) {
+ if (rhs->eval == eval_not) {
+ return extract_child_expr(rhs, &rhs->rhs);
+ }
+
+ struct expr *expr = new_expr(eval_not, 1, argv);
+ if (!expr) {
+ free_expr(rhs);
+ return NULL;
+ }
+
+ expr->rhs = rhs;
+ return expr;
+}
+
+static struct expr *optimize_not_expr(const struct cmdline *cmdline, struct expr *expr);
+static struct expr *optimize_and_expr(const struct cmdline *cmdline, struct expr *expr);
+static struct expr *optimize_or_expr(const struct cmdline *cmdline, struct expr *expr);
+
+/**
+ * Apply De Morgan's laws.
+ */
+static struct expr *de_morgan(const struct cmdline *cmdline, struct expr *expr, char **argv) {
+ debug_opt(cmdline, "-O1: De Morgan's laws: %e ", expr);
+
+ struct expr *parent = negate_expr(expr, argv);
+ if (!parent) {
+ return NULL;
+ }
+
+ bool has_parent = true;
+ if (parent->eval != eval_not) {
+ expr = parent;
+ has_parent = false;
+ }
+
+ if (expr->eval == eval_and) {
+ expr->eval = eval_or;
+ expr->argv = &fake_or_arg;
+ } else {
+ assert(expr->eval == eval_or);
+ expr->eval = eval_and;
+ expr->argv = &fake_and_arg;
+ }
+
+ expr->lhs = negate_expr(expr->lhs, argv);
+ expr->rhs = negate_expr(expr->rhs, argv);
+ if (!expr->lhs || !expr->rhs) {
+ free_expr(parent);
+ return NULL;
+ }
+
+ debug_opt(cmdline, "<==> %e\n", parent);
+
+ if (expr->lhs->eval == eval_not) {
+ expr->lhs = optimize_not_expr(cmdline, expr->lhs);
+ }
+ if (expr->rhs->eval == eval_not) {
+ expr->rhs = optimize_not_expr(cmdline, expr->rhs);
+ }
+ if (!expr->lhs || !expr->rhs) {
+ free_expr(parent);
+ return NULL;
+ }
+
+ if (expr->eval == eval_and) {
+ expr = optimize_and_expr(cmdline, expr);
+ } else {
+ expr = optimize_or_expr(cmdline, expr);
+ }
+ if (!expr) {
+ if (has_parent) {
+ parent->rhs = NULL;
+ free_expr(parent);
+ }
+ return NULL;
+ }
+
+ if (has_parent) {
+ parent = optimize_not_expr(cmdline, parent);
+ }
+ return parent;
+}
+
+/**
+ * Optimize a negation.
+ */
+static struct expr *optimize_not_expr(const struct cmdline *cmdline, struct expr *expr) {
+ assert(expr->eval == eval_not && !expr->lhs && expr->rhs);
+
+ struct expr *rhs = expr->rhs;
+
+ int optlevel = cmdline->optlevel;
+ if (optlevel >= 1) {
+ if (rhs == &expr_true) {
+ debug_opt(cmdline, "-O1: constant propagation: %e <==> %e\n", expr, &expr_false);
+ free_expr(expr);
+ return &expr_false;
+ } else if (rhs == &expr_false) {
+ debug_opt(cmdline, "-O1: constant propagation: %e <==> %e\n", expr, &expr_true);
+ free_expr(expr);
+ return &expr_true;
+ } else if (rhs->eval == eval_not) {
+ debug_opt(cmdline, "-O1: double negation: %e <==> %e\n", expr, rhs->rhs);
+ return extract_child_expr(expr, &rhs->rhs);
+ } else if (expr_never_returns(rhs)) {
+ debug_opt(cmdline, "-O1: reachability: %e <==> %e\n", expr, rhs);
+ return extract_child_expr(expr, &expr->rhs);
+ } else if ((rhs->eval == eval_and || rhs->eval == eval_or)
+ && (rhs->lhs->eval == eval_not || rhs->rhs->eval == eval_not)) {
+ return de_morgan(cmdline, expr, expr->argv);
+ }
+ }
+
+ expr->pure = rhs->pure;
+ expr->always_true = rhs->always_false;
+ expr->always_false = rhs->always_true;
+ expr->cost = rhs->cost;
+ expr->probability = 1.0 - rhs->probability;
+
+ return expr;
+}
+
+/**
+ * Optimize a conjunction.
+ */
+static struct expr *optimize_and_expr(const struct cmdline *cmdline, struct expr *expr) {
+ assert(expr->eval == eval_and && expr->lhs && expr->rhs);
+
+ struct expr *lhs = expr->lhs;
+ struct expr *rhs = expr->rhs;
+
+ int optlevel = cmdline->optlevel;
+ if (optlevel >= 1) {
+ if (lhs == &expr_true) {
+ debug_opt(cmdline, "-O1: conjunction elimination: %e <==> %e\n", expr, rhs);
+ return extract_child_expr(expr, &expr->rhs);
+ } else if (rhs == &expr_true) {
+ debug_opt(cmdline, "-O1: conjunction elimination: %e <==> %e\n", expr, lhs);
+ return extract_child_expr(expr, &expr->lhs);
+ } else if (lhs->always_false) {
+ debug_opt(cmdline, "-O1: short-circuit: %e <==> %e\n", expr, lhs);
+ return extract_child_expr(expr, &expr->lhs);
+ } else if (optlevel >= 2 && lhs->pure && rhs == &expr_false) {
+ debug_opt(cmdline, "-O2: purity: %e <==> %e\n", expr, rhs);
+ return extract_child_expr(expr, &expr->rhs);
+ } else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+ return de_morgan(cmdline, expr, expr->lhs->argv);
+ }
+ }
+
+ expr->pure = lhs->pure && rhs->pure;
+ expr->always_true = lhs->always_true && rhs->always_true;
+ expr->always_false = lhs->always_false || rhs->always_false;
+ expr->cost = lhs->cost + lhs->probability*rhs->cost;
+ expr->probability = lhs->probability*rhs->probability;
+
+ if (optlevel >= 3 && lhs->pure && rhs->pure) {
+ double swapped_cost = rhs->cost + rhs->probability*lhs->cost;
+ if (swapped_cost < expr->cost) {
+ debug_opt(cmdline, "-O3: cost: %e", expr);
+ expr->lhs = rhs;
+ expr->rhs = lhs;
+ debug_opt(cmdline, " <==> %e (~%g --> ~%g)\n", expr, expr->cost, swapped_cost);
+ expr->cost = swapped_cost;
+ }
+ }
+
+ return expr;
+}
+
+/**
+ * Optimize a disjunction.
+ */
+static struct expr *optimize_or_expr(const struct cmdline *cmdline, struct expr *expr) {
+ assert(expr->eval == eval_or && expr->lhs && expr->rhs);
+
+ struct expr *lhs = expr->lhs;
+ struct expr *rhs = expr->rhs;
+
+ int optlevel = cmdline->optlevel;
+ if (optlevel >= 1) {
+ if (lhs->always_true) {
+ debug_opt(cmdline, "-O1: short-circuit: %e <==> %e\n", expr, lhs);
+ return extract_child_expr(expr, &expr->lhs);
+ } else if (lhs == &expr_false) {
+ debug_opt(cmdline, "-O1: disjunctive syllogism: %e <==> %e\n", expr, rhs);
+ return extract_child_expr(expr, &expr->rhs);
+ } else if (rhs == &expr_false) {
+ debug_opt(cmdline, "-O1: disjunctive syllogism: %e <==> %e\n", expr, lhs);
+ return extract_child_expr(expr, &expr->lhs);
+ } else if (optlevel >= 2 && lhs->pure && rhs == &expr_true) {
+ debug_opt(cmdline, "-O2: purity: %e <==> %e\n", expr, rhs);
+ return extract_child_expr(expr, &expr->rhs);
+ } else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+ return de_morgan(cmdline, expr, expr->lhs->argv);
+ }
+ }
+
+ expr->pure = lhs->pure && rhs->pure;
+ expr->always_true = lhs->always_true || rhs->always_true;
+ expr->always_false = lhs->always_false && rhs->always_false;
+ expr->cost = lhs->cost + (1 - lhs->probability)*rhs->cost;
+ expr->probability = lhs->probability + rhs->probability - lhs->probability*rhs->probability;
+
+ if (optlevel >= 3 && lhs->pure && rhs->pure) {
+ double swapped_cost = rhs->cost + (1 - rhs->probability)*lhs->cost;
+ if (swapped_cost < expr->cost) {
+ debug_opt(cmdline, "-O3: cost: %e", expr);
+ expr->lhs = rhs;
+ expr->rhs = lhs;
+ debug_opt(cmdline, " <==> %e (~%g --> ~%g)\n", expr, expr->cost, swapped_cost);
+ expr->cost = swapped_cost;
+ }
+ }
+
+ return expr;
+}
+
+/**
+ * Optimize an expression in an ignored-result context.
+ */
+static struct expr *ignore_result(const struct cmdline *cmdline, struct expr *expr) {
+ int optlevel = cmdline->optlevel;
+
+ if (optlevel >= 1) {
+ while (true) {
+ if (expr->eval == eval_not) {
+ debug_opt(cmdline, "-O1: ignored result: %e --> %e\n", expr, expr->rhs);
+ expr = extract_child_expr(expr, &expr->rhs);
+ } else if (optlevel >= 2
+ && (expr->eval == eval_and || expr->eval == eval_or || expr->eval == eval_comma)
+ && expr->rhs->pure) {
+ debug_opt(cmdline, "-O2: ignored result: %e --> %e\n", expr, expr->lhs);
+ expr = extract_child_expr(expr, &expr->lhs);
+ } else {
+ break;
+ }
+ }
+ }
+
+ return expr;
+}
+
+/**
+ * Optimize a comma expression.
+ */
+static struct expr *optimize_comma_expr(const struct cmdline *cmdline, struct expr *expr) {
+ struct expr *lhs = expr->lhs;
+ struct expr *rhs = expr->rhs;
+
+ int optlevel = cmdline->optlevel;
+ if (optlevel >= 1) {
+ lhs = expr->lhs = ignore_result(cmdline, lhs);
+
+ if (expr_never_returns(lhs)) {
+ debug_opt(cmdline, "-O1: reachability: %e <==> %e\n", expr, lhs);
+ return extract_child_expr(expr, &expr->lhs);
+ }
+
+ if (optlevel >= 2 && lhs->pure) {
+ debug_opt(cmdline, "-O2: purity: %e <==> %e\n", expr, rhs);
+ return extract_child_expr(expr, &expr->rhs);
+ }
+ }
+
+ expr->pure = lhs->pure && rhs->pure;
+ expr->always_true = expr_never_returns(lhs) || rhs->always_true;
+ expr->always_false = expr_never_returns(lhs) || rhs->always_false;
+ expr->cost = lhs->cost + rhs->cost;
+ expr->probability = rhs->probability;
+
+ return expr;
+}
+
+/**
+ * Optimize an expression.
+ */
+static struct expr *optimize_expr(const struct cmdline *cmdline, struct expr *expr) {
+ if (expr->lhs) {
+ expr->lhs = optimize_expr(cmdline, expr->lhs);
+ if (!expr->lhs) {
+ goto fail;
+ }
+ }
+
+ if (expr->rhs) {
+ expr->rhs = optimize_expr(cmdline, expr->rhs);
+ if (!expr->rhs) {
+ goto fail;
+ }
+ }
+
+ if (expr->eval == eval_not) {
+ return optimize_not_expr(cmdline, expr);
+ } else if (expr->eval == eval_and) {
+ return optimize_and_expr(cmdline, expr);
+ } else if (expr->eval == eval_or) {
+ return optimize_or_expr(cmdline, expr);
+ } else if (expr->eval == eval_comma) {
+ return optimize_comma_expr(cmdline, expr);
+ } else {
+ return expr;
+ }
+
+fail:
+ free_expr(expr);
+ return NULL;
+}
+
+/**
+ * Apply top-level optimizations.
+ */
+static struct expr *optimize_whole_expr(const struct cmdline *cmdline, struct expr *expr) {
+ expr = optimize_expr(cmdline, expr);
+ if (!expr) {
+ return NULL;
+ }
+
+ expr = ignore_result(cmdline, expr);
+
+ if (cmdline->optlevel >= 4 && expr->pure && expr != &expr_false) {
+ debug_opt(cmdline, "-O4: top-level purity: %e --> %e\n", expr, &expr_false);
+ free_expr(expr);
+ expr = &expr_false;
+ }
+
+ return expr;
+}
+
+int optimize_cmdline(struct cmdline *cmdline) {
+ cmdline->expr = optimize_whole_expr(cmdline, cmdline->expr);
+ if (cmdline->expr) {
+ return 0;
+ } else {
+ return -1;
+ }
+}
diff --git a/parse.c b/parse.c
index f6cde7a..2e77b10 100644
--- a/parse.c
+++ b/parse.c
@@ -15,8 +15,12 @@
****************************************************************************/
#include "bfs.h"
+#include "cmdline.h"
#include "dstring.h"
+#include "eval.h"
#include "exec.h"
+#include "expr.h"
+#include "mtab.h"
#include "printf.h"
#include "typo.h"
#include "util.h"
@@ -41,7 +45,6 @@
// 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";
@@ -50,10 +53,7 @@ static char *fake_true_arg = "-true";
#define STAT_COST 1000.0
#define PRINT_COST 20000.0
-/**
- * Singleton true expression instance.
- */
-static struct expr expr_true = {
+struct expr expr_true = {
.eval = eval_true,
.lhs = NULL,
.rhs = NULL,
@@ -65,10 +65,7 @@ static struct expr expr_true = {
.argv = &fake_true_arg,
};
-/**
- * Singleton false expression instance.
- */
-static struct expr expr_false = {
+struct expr expr_false = {
.eval = eval_false,
.lhs = NULL,
.rhs = NULL,
@@ -83,7 +80,7 @@ static struct expr expr_false = {
/**
* Free an expression.
*/
-static void free_expr(struct expr *expr) {
+void free_expr(struct expr *expr) {
if (expr && expr != &expr_true && expr != &expr_false) {
if (expr->cfile && expr->cfile->close) {
if (cfclose(expr->cfile) != 0) {
@@ -105,11 +102,8 @@ static void free_expr(struct expr *expr) {
}
}
-/**
- * Create a new expression.
- */
-static struct expr *new_expr(eval_fn *eval, size_t argc, char **argv) {
- struct expr *expr = malloc(sizeof(struct expr));
+struct expr *new_expr(eval_fn *eval, size_t argc, char **argv) {
+ struct expr *expr = malloc(sizeof(*expr));
if (!expr) {
perror("malloc()");
return NULL;
@@ -192,7 +186,7 @@ static void expr_set_never_returns(struct expr *expr) {
/**
* Dump the parsed expression tree, for debugging.
*/
-static void dump_expr(CFILE *cfile, const struct expr *expr, bool verbose) {
+void dump_expr(CFILE *cfile, const struct expr *expr, bool verbose) {
fputs("(", cfile->file);
if (expr->lhs || expr->rhs) {
@@ -320,46 +314,6 @@ enum token_type {
};
/**
- * Log an optimization.
- */
-static void debug_opt(const struct parser_state *state, const char *format, ...) {
- if (!(state->cmdline->debug & DEBUG_OPT)) {
- return;
- }
-
- CFILE *cerr = state->cmdline->cerr;
-
- va_list args;
- va_start(args, format);
-
- for (const char *i = format; *i != '\0'; ++i) {
- if (*i == '%') {
- switch (*++i) {
- case '%':
- fputc('%', stderr);
- break;
-
- case 'e':
- dump_expr(cerr, va_arg(args, const struct expr *), false);
- break;
-
- case 'g':
- cfprintf(cerr, "%{ylw}%g%{rs}", va_arg(args, double));
- break;
-
- case 's':
- cfprintf(cerr, "%{red}%s%{rs}", va_arg(args, const char *));
- break;
- }
- } else {
- fputc(*i, stderr);
- }
- }
-
- va_end(args);
-}
-
-/**
* Fill in a "-print"-type expression.
*/
static void init_print_expr(struct parser_state *state, struct expr *expr) {
@@ -2578,76 +2532,6 @@ unexpected:
return NULL;
}
-static struct expr *new_and_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv);
-static struct expr *new_or_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv);
-
-/**
- * Extract a child expression, freeing the outer expression.
- */
-static struct expr *extract_child_expr(struct expr *expr, struct expr **child) {
- struct expr *ret = *child;
- *child = NULL;
- free_expr(expr);
- return ret;
-}
-
-/**
- * Create a "not" expression.
- */
-static struct expr *new_not_expr(const struct parser_state *state, struct expr *rhs, char **argv) {
- int optlevel = state->cmdline->optlevel;
- if (optlevel >= 1) {
- if (rhs == &expr_true) {
- debug_opt(state, "-O1: constant propagation: (%s %e) <==> %e\n", argv[0], rhs, &expr_false);
- return &expr_false;
- } else if (rhs == &expr_false) {
- debug_opt(state, "-O1: constant propagation: (%s %e) <==> %e\n", argv[0], rhs, &expr_true);
- return &expr_true;
- } else if (expr_never_returns(rhs)) {
- debug_opt(state, "-O1: reachability: (%s %e) <==> %e\n", argv[0], rhs, rhs);
- return rhs;
- } else if (rhs->eval == eval_not) {
- debug_opt(state, "-O1: double negation: (%s %e) <==> %e\n", argv[0], rhs, rhs->rhs);
- return extract_child_expr(rhs, &rhs->rhs);
- } else if ((rhs->eval == eval_and || rhs->eval == eval_or)
- && (rhs->lhs->eval == eval_not || rhs->rhs->eval == eval_not)) {
- bool other_and = rhs->eval == eval_or;
- char **other_arg = other_and ? &fake_and_arg : &fake_or_arg;
-
- debug_opt(state, "-O1: De Morgan's laws: (%s %e) <==> (%s (%s %e) (%s %e))\n",
- argv[0], rhs,
- *other_arg, argv[0], rhs->lhs, argv[0], rhs->rhs);
-
- struct expr *other_lhs = new_not_expr(state, rhs->lhs, argv);
- struct expr *other_rhs = new_not_expr(state, rhs->rhs, argv);
- rhs->rhs = NULL;
- rhs->lhs = NULL;
- free_expr(rhs);
- if (!other_lhs || !other_rhs) {
- free_expr(other_rhs);
- free_expr(other_lhs);
- return NULL;
- }
-
- if (other_and) {
- return new_and_expr(state, other_lhs, other_rhs, other_arg);
- } else {
- return new_or_expr(state, other_lhs, other_rhs, other_arg);
- }
- }
- }
-
- struct expr *expr = new_unary_expr(eval_not, rhs, argv);
- if (expr) {
- expr->pure = rhs->pure;
- expr->always_true = rhs->always_false;
- expr->always_false = rhs->always_true;
- expr->cost = rhs->cost;
- expr->probability = 1.0 - rhs->probability;
- }
- return expr;
-}
-
/**
* FACTOR : "(" EXPR ")"
* | "!" FACTOR | "-not" FACTOR
@@ -2696,76 +2580,13 @@ static struct expr *parse_factor(struct parser_state *state) {
return NULL;
}
- return new_not_expr(state, factor, argv);
+ return new_unary_expr(eval_not, factor, argv);
} else {
return parse_literal(state);
}
}
/**
- * Create an "and" expression.
- */
-static struct expr *new_and_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
- int optlevel = state->cmdline->optlevel;
- if (optlevel >= 1) {
- if (lhs == &expr_true) {
- debug_opt(state, "-O1: conjunction elimination: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
- return rhs;
- } else if (rhs == &expr_true) {
- debug_opt(state, "-O1: conjunction elimination: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
- return lhs;
- } else if (lhs->always_false) {
- debug_opt(state, "-O1: short-circuit: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
- free_expr(rhs);
- return lhs;
- } else if (optlevel >= 2 && lhs->pure && rhs == &expr_false) {
- debug_opt(state, "-O2: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
- free_expr(lhs);
- return rhs;
- } else if (lhs->eval == eval_not && rhs->eval == eval_not) {
- char **not_arg = lhs->argv;
- debug_opt(state, "-O1: De Morgan's laws: (%s %e %e) <==> (%s (%s %e %e))\n",
- argv[0], lhs, rhs,
- *not_arg, fake_or_arg, lhs->rhs, rhs->rhs);
-
- lhs = extract_child_expr(lhs, &lhs->rhs);
- rhs = extract_child_expr(rhs, &rhs->rhs);
-
- struct expr *or_expr = new_or_expr(state, lhs, rhs, &fake_or_arg);
- if (!or_expr) {
- return NULL;
- }
-
- return new_not_expr(state, or_expr, not_arg);
- }
- }
-
- struct expr *expr = new_binary_expr(eval_and, lhs, rhs, argv);
- if (!expr) {
- return NULL;
- }
-
- expr->pure = lhs->pure && rhs->pure;
- expr->always_true = lhs->always_true && rhs->always_true;
- expr->always_false = lhs->always_false || rhs->always_false;
- expr->cost = lhs->cost + lhs->probability*rhs->cost;
- expr->probability = lhs->probability*rhs->probability;
-
- if (optlevel >= 3 && lhs->pure && rhs->pure) {
- double swapped_cost = rhs->cost + rhs->probability*lhs->cost;
- if (swapped_cost < expr->cost) {
- debug_opt(state, "-O3: cost: %e <==> (%s %e %e) (~%g --> ~%g)\n",
- expr, argv[0], rhs, lhs, expr->cost, swapped_cost);
- expr->cost = swapped_cost;
- expr->lhs = rhs;
- expr->rhs = lhs;
- }
- }
-
- return expr;
-}
-
-/**
* TERM : FACTOR
* | TERM FACTOR
* | TERM "-a" FACTOR
@@ -2803,77 +2624,13 @@ static struct expr *parse_term(struct parser_state *state) {
return NULL;
}
- term = new_and_expr(state, lhs, rhs, argv);
+ term = new_binary_expr(eval_and, lhs, rhs, argv);
}
return term;
}
/**
- * Create an "or" expression.
- */
-static struct expr *new_or_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
- int optlevel = state->cmdline->optlevel;
- if (optlevel >= 1) {
- if (lhs->always_true) {
- debug_opt(state, "-O1: short-circuit: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
- free_expr(rhs);
- return lhs;
- } else if (lhs == &expr_false) {
- debug_opt(state, "-O1: disjunctive syllogism: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
- return rhs;
- } else if (rhs == &expr_false) {
- debug_opt(state, "-O1: disjunctive syllogism: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
- return lhs;
- } else if (optlevel >= 2 && lhs->pure && rhs == &expr_true) {
- debug_opt(state, "-O2: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
- free_expr(lhs);
- return rhs;
- } else if (lhs->eval == eval_not && rhs->eval == eval_not) {
- char **not_arg = lhs->argv;
- debug_opt(state, "-O1: De Morgan's laws: (%s %e %e) <==> (%s (%s %e %e))\n",
- argv[0], lhs, rhs,
- *not_arg, fake_and_arg, lhs->rhs, rhs->rhs);
-
- lhs = extract_child_expr(lhs, &lhs->rhs);
- rhs = extract_child_expr(rhs, &rhs->rhs);
-
- struct expr *and_expr = new_and_expr(state, lhs, rhs, &fake_and_arg);
- if (!and_expr) {
- return NULL;
- }
-
- return new_not_expr(state, and_expr, not_arg);
- }
- }
-
- struct expr *expr = new_binary_expr(eval_or, lhs, rhs, argv);
- if (!expr) {
- return NULL;
- }
-
- expr->pure = lhs->pure && rhs->pure;
- expr->always_true = lhs->always_true || rhs->always_true;
- expr->always_false = lhs->always_false && rhs->always_false;
- expr->cost = lhs->cost + (1 - lhs->probability)*rhs->cost;
- expr->probability = lhs->probability + rhs->probability - lhs->probability*rhs->probability;
-
- if (optlevel >= 3 && lhs->pure && rhs->pure) {
- double swapped_cost = rhs->cost + (1 - rhs->probability)*lhs->cost;
- if (swapped_cost < expr->cost) {
- debug_opt(state, "-O3: cost: %e <==> (%s %e %e) (~%g --> ~%g)\n",
- expr, argv[0], rhs, lhs, expr->cost, swapped_cost);
- expr->cost = swapped_cost;
- expr->lhs = rhs;
- expr->rhs = lhs;
- }
-
- }
-
- return expr;
-}
-
-/**
* CLAUSE : TERM
* | CLAUSE "-o" TERM
* | CLAUSE "-or" TERM
@@ -2905,50 +2662,13 @@ static struct expr *parse_clause(struct parser_state *state) {
return NULL;
}
- clause = new_or_expr(state, lhs, rhs, argv);
+ clause = new_binary_expr(eval_or, lhs, rhs, argv);
}
return clause;
}
/**
- * Create a "comma" expression.
- */
-static struct expr *new_comma_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
- int optlevel = state->cmdline->optlevel;
- if (optlevel >= 1) {
- if (lhs->eval == eval_not) {
- debug_opt(state, "-O1: ignored result: (%s %e %e) <==> (%s %e %e)\n",
- argv[0], lhs, rhs,
- argv[0], lhs->rhs, rhs);
- lhs = extract_child_expr(lhs, &lhs->rhs);
- }
-
- if (expr_never_returns(lhs)) {
- debug_opt(state, "-O1: reachability: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
- free_expr(rhs);
- return lhs;
- }
-
- if (optlevel >= 2 && lhs->pure) {
- debug_opt(state, "-O2: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
- free_expr(lhs);
- return rhs;
- }
- }
-
- struct expr *expr = new_binary_expr(eval_comma, lhs, rhs, argv);
- if (expr) {
- expr->pure = lhs->pure && rhs->pure;
- expr->always_true = expr_never_returns(lhs) || rhs->always_true;
- expr->always_false = expr_never_returns(lhs) || rhs->always_false;
- expr->cost = lhs->cost + rhs->cost;
- expr->probability = rhs->probability;
- }
- return expr;
-}
-
-/**
* EXPR : CLAUSE
* | EXPR "," CLAUSE
*/
@@ -2979,38 +2699,7 @@ static struct expr *parse_expr(struct parser_state *state) {
return NULL;
}
- expr = new_comma_expr(state, lhs, rhs, argv);
- }
-
- return expr;
-}
-
-/**
- * Apply top-level optimizations.
- */
-static struct expr *optimize_whole_expr(const struct parser_state *state, struct expr *expr) {
- int optlevel = state->cmdline->optlevel;
-
- if (optlevel >= 1) {
- while (true) {
- if (expr->eval == eval_not) {
- debug_opt(state, "-O1: ignored result: %e --> %e\n", expr, expr->rhs);
- expr = extract_child_expr(expr, &expr->rhs);
- } else if (optlevel >= 2
- && (expr->eval == eval_and || expr->eval == eval_or || expr->eval == eval_comma)
- && expr->rhs->pure) {
- debug_opt(state, "-O2: ignored result: %e --> %e\n", expr, expr->lhs);
- expr = extract_child_expr(expr, &expr->lhs);
- } else {
- break;
- }
- }
- }
-
- if (optlevel >= 4 && expr->pure && expr != &expr_false) {
- debug_opt(state, "-O4: top-level purity: %e --> %e\n", expr, &expr_false);
- free_expr(expr);
- expr = &expr_false;
+ expr = new_binary_expr(eval_comma, lhs, rhs, argv);
}
return expr;
@@ -3046,14 +2735,12 @@ static struct expr *parse_whole_expr(struct parser_state *state) {
}
init_print_expr(state, print);
- expr = new_and_expr(state, expr, print, &fake_and_arg);
+ expr = new_binary_expr(eval_and, expr, print, &fake_and_arg);
if (!expr) {
goto fail;
}
}
- expr = optimize_whole_expr(state, expr);
-
if (state->warn && state->depth_arg && state->prune_arg) {
cfprintf(cerr, "%{wr}warning: %s does not work in the presence of %s.%{rs}\n", state->prune_arg, state->depth_arg);
@@ -3252,6 +2939,10 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
}
}
+ if (optimize_cmdline(cmdline) != 0) {
+ goto fail;
+ }
+
if (!cmdline->roots) {
if (parse_root(&state, ".") != 0) {
goto fail;
diff --git a/printf.c b/printf.c
index da3f851..3c32108 100644
--- a/printf.c
+++ b/printf.c
@@ -15,9 +15,10 @@
****************************************************************************/
#include "printf.h"
-#include "bfs.h"
+#include "cmdline.h"
#include "color.h"
#include "dstring.h"
+#include "expr.h"
#include "mtab.h"
#include "util.h"
#include <assert.h>
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-29 11:43:46 +0000