#define DEBUG_EXPR 0
+static int expr_eq(struct expr *e1, struct expr *e2);
+static struct expr *expr_eliminate_yn(struct expr *e);
+
struct expr *expr_alloc_symbol(struct symbol *sym)
{
struct expr *e = xcalloc(1, sizeof(*e));
e->left.expr = expr_copy(org->left.expr);
break;
case E_EQUAL:
+ case E_GEQ:
+ case E_GTH:
+ case E_LEQ:
+ case E_LTH:
case E_UNEQUAL:
e->left.sym = org->left.sym;
e->right.sym = org->right.sym;
break;
case E_NOT:
expr_free(e->left.expr);
- return;
+ break;
case E_EQUAL:
+ case E_GEQ:
+ case E_GTH:
+ case E_LEQ:
+ case E_LTH:
case E_UNEQUAL:
break;
case E_OR:
#define e1 (*ep1)
#define e2 (*ep2)
+/*
+ * expr_eliminate_eq() helper.
+ *
+ * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
+ * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
+ * against all other leaves. Two equal leaves are both replaced with either 'y'
+ * or 'n' as appropriate for 'type', to be eliminated later.
+ */
static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
{
+ /* Recurse down to leaves */
+
if (e1->type == type) {
__expr_eliminate_eq(type, &e1->left.expr, &e2);
__expr_eliminate_eq(type, &e1->right.expr, &e2);
__expr_eliminate_eq(type, &e1, &e2->right.expr);
return;
}
+
+ /* e1 and e2 are leaves. Compare them. */
+
if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
e1->left.sym == e2->left.sym &&
(e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
return;
if (!expr_eq(e1, e2))
return;
+
+ /* e1 and e2 are equal leaves. Prepare them for elimination. */
+
trans_count++;
expr_free(e1); expr_free(e2);
switch (type) {
}
}
+/*
+ * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both.
+ * Example reductions:
+ *
+ * ep1: A && B -> ep1: y
+ * ep2: A && B && C -> ep2: C
+ *
+ * ep1: A || B -> ep1: n
+ * ep2: A || B || C -> ep2: C
+ *
+ * ep1: A && (B && FOO) -> ep1: FOO
+ * ep2: (BAR && B) && A -> ep2: BAR
+ *
+ * ep1: A && (B || C) -> ep1: y
+ * ep2: (C || B) && A -> ep2: y
+ *
+ * Comparisons are done between all operands at the same "level" of && or ||.
+ * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the
+ * following operands will be compared:
+ *
+ * - 'e1', 'e2 || e3', and 'e4 || e5', against each other
+ * - e2 against e3
+ * - e4 against e5
+ *
+ * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and
+ * '(e1 && e2) && e3' are both a single level.
+ *
+ * See __expr_eliminate_eq() as well.
+ */
void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
{
if (!e1 || !e2)
#undef e1
#undef e2
-int expr_eq(struct expr *e1, struct expr *e2)
+/*
+ * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two
+ * &&/|| expressions are considered equal if every operand in one expression
+ * equals some operand in the other (operands do not need to appear in the same
+ * order), recursively.
+ */
+static int expr_eq(struct expr *e1, struct expr *e2)
{
int res, old_count;
return 0;
switch (e1->type) {
case E_EQUAL:
+ case E_GEQ:
+ case E_GTH:
+ case E_LEQ:
+ case E_LTH:
case E_UNEQUAL:
return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
case E_SYMBOL:
return 0;
}
-struct expr *expr_eliminate_yn(struct expr *e)
+/*
+ * Recursively performs the following simplifications in-place (as well as the
+ * corresponding simplifications with swapped operands):
+ *
+ * expr && n -> n
+ * expr && y -> expr
+ * expr || n -> expr
+ * expr || y -> y
+ *
+ * Returns the optimized expression.
+ */
+static struct expr *expr_eliminate_yn(struct expr *e)
{
struct expr *tmp;
return NULL;
}
+/*
+ * expr_eliminate_dups() helper.
+ *
+ * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
+ * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
+ * against all other leaves to look for simplifications.
+ */
static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
{
#define e1 (*ep1)
#define e2 (*ep2)
struct expr *tmp;
+ /* Recurse down to leaves */
+
if (e1->type == type) {
expr_eliminate_dups1(type, &e1->left.expr, &e2);
expr_eliminate_dups1(type, &e1->right.expr, &e2);
expr_eliminate_dups1(type, &e1, &e2->right.expr);
return;
}
+
+ /* e1 and e2 are leaves. Compare and process them. */
+
if (e1 == e2)
return;
#undef e2
}
-static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
-{
-#define e1 (*ep1)
-#define e2 (*ep2)
- struct expr *tmp, *tmp1, *tmp2;
-
- if (e1->type == type) {
- expr_eliminate_dups2(type, &e1->left.expr, &e2);
- expr_eliminate_dups2(type, &e1->right.expr, &e2);
- return;
- }
- if (e2->type == type) {
- expr_eliminate_dups2(type, &e1, &e2->left.expr);
- expr_eliminate_dups2(type, &e1, &e2->right.expr);
- }
- if (e1 == e2)
- return;
-
- switch (e1->type) {
- case E_OR:
- expr_eliminate_dups2(e1->type, &e1, &e1);
- // (FOO || BAR) && (!FOO && !BAR) -> n
- tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
- tmp2 = expr_copy(e2);
- tmp = expr_extract_eq_and(&tmp1, &tmp2);
- if (expr_is_yes(tmp1)) {
- expr_free(e1);
- e1 = expr_alloc_symbol(&symbol_no);
- trans_count++;
- }
- expr_free(tmp2);
- expr_free(tmp1);
- expr_free(tmp);
- break;
- case E_AND:
- expr_eliminate_dups2(e1->type, &e1, &e1);
- // (FOO && BAR) || (!FOO || !BAR) -> y
- tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
- tmp2 = expr_copy(e2);
- tmp = expr_extract_eq_or(&tmp1, &tmp2);
- if (expr_is_no(tmp1)) {
- expr_free(e1);
- e1 = expr_alloc_symbol(&symbol_yes);
- trans_count++;
- }
- expr_free(tmp2);
- expr_free(tmp1);
- expr_free(tmp);
- break;
- default:
- ;
- }
-#undef e1
-#undef e2
-}
-
+/*
+ * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
+ * operands.
+ *
+ * Example simplifications:
+ *
+ * A || B || A -> A || B
+ * A && B && A=y -> A=y && B
+ *
+ * Returns the deduplicated expression.
+ */
struct expr *expr_eliminate_dups(struct expr *e)
{
int oldcount;
switch (e->type) {
case E_OR: case E_AND:
expr_eliminate_dups1(e->type, &e, &e);
- expr_eliminate_dups2(e->type, &e, &e);
default:
;
}
if (!trans_count)
+ /* No simplifications done in this pass. We're done */
break;
e = expr_eliminate_yn(e);
}
return e;
}
+/*
+ * Performs various simplifications involving logical operators and
+ * comparisons.
+ *
+ * Allocates and returns a new expression.
+ */
struct expr *expr_transform(struct expr *e)
{
struct expr *tmp;
return NULL;
switch (e->type) {
case E_EQUAL:
+ case E_GEQ:
+ case E_GTH:
+ case E_LEQ:
+ case E_LTH:
case E_UNEQUAL:
case E_SYMBOL:
case E_LIST:
e = tmp;
e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
break;
+ case E_LEQ:
+ case E_GEQ:
+ // !a<='x' -> a>'x'
+ tmp = e->left.expr;
+ free(e);
+ e = tmp;
+ e->type = e->type == E_LEQ ? E_GTH : E_LTH;
+ break;
+ case E_LTH:
+ case E_GTH:
+ // !a<'x' -> a>='x'
+ tmp = e->left.expr;
+ free(e);
+ e = tmp;
+ e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
+ break;
case E_OR:
// !(a || b) -> !a && !b
tmp = e->left.expr;
case E_SYMBOL:
return dep->left.sym == sym;
case E_EQUAL:
+ case E_GEQ:
+ case E_GTH:
+ case E_LEQ:
+ case E_LTH:
case E_UNEQUAL:
return dep->left.sym == sym ||
dep->right.sym == sym;
return false;
}
-struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
-{
- struct expr *tmp = NULL;
- expr_extract_eq(E_AND, &tmp, ep1, ep2);
- if (tmp) {
- *ep1 = expr_eliminate_yn(*ep1);
- *ep2 = expr_eliminate_yn(*ep2);
- }
- return tmp;
-}
-
-struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
-{
- struct expr *tmp = NULL;
- expr_extract_eq(E_OR, &tmp, ep1, ep2);
- if (tmp) {
- *ep1 = expr_eliminate_yn(*ep1);
- *ep2 = expr_eliminate_yn(*ep2);
- }
- return tmp;
-}
-
-void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
-{
-#define e1 (*ep1)
-#define e2 (*ep2)
- if (e1->type == type) {
- expr_extract_eq(type, ep, &e1->left.expr, &e2);
- expr_extract_eq(type, ep, &e1->right.expr, &e2);
- return;
- }
- if (e2->type == type) {
- expr_extract_eq(type, ep, ep1, &e2->left.expr);
- expr_extract_eq(type, ep, ep1, &e2->right.expr);
- return;
- }
- if (expr_eq(e1, e2)) {
- *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
- expr_free(e2);
- if (type == E_AND) {
- e1 = expr_alloc_symbol(&symbol_yes);
- e2 = expr_alloc_symbol(&symbol_yes);
- } else if (type == E_OR) {
- e1 = expr_alloc_symbol(&symbol_no);
- e2 = expr_alloc_symbol(&symbol_no);
- }
- }
-#undef e1
-#undef e2
-}
-
+/*
+ * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
+ * expression 'e'.
+ *
+ * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
+ *
+ * A -> A!=n
+ * !A -> A=n
+ * A && B -> !(A=n || B=n)
+ * A || B -> !(A=n && B=n)
+ * A && (B || C) -> !(A=n || (B=n && C=n))
+ *
+ * Allocates and returns a new expression.
+ */
struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
{
struct expr *e1, *e2;
case E_NOT:
return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
case E_UNEQUAL:
+ case E_LTH:
+ case E_LEQ:
+ case E_GTH:
+ case E_GEQ:
case E_EQUAL:
if (type == E_EQUAL) {
if (sym == &symbol_yes)
return NULL;
}
+enum string_value_kind {
+ k_string,
+ k_signed,
+ k_unsigned,
+ k_invalid
+};
+
+union string_value {
+ unsigned long long u;
+ signed long long s;
+};
+
+static enum string_value_kind expr_parse_string(const char *str,
+ enum symbol_type type,
+ union string_value *val)
+{
+ char *tail;
+ enum string_value_kind kind;
+
+ errno = 0;
+ switch (type) {
+ case S_BOOLEAN:
+ case S_TRISTATE:
+ val->s = !strcmp(str, "n") ? 0 :
+ !strcmp(str, "m") ? 1 :
+ !strcmp(str, "y") ? 2 : -1;
+ return k_signed;
+ case S_INT:
+ val->s = strtoll(str, &tail, 10);
+ kind = k_signed;
+ break;
+ case S_HEX:
+ val->u = strtoull(str, &tail, 16);
+ kind = k_unsigned;
+ break;
+ case S_STRING:
+ case S_UNKNOWN:
+ val->s = strtoll(str, &tail, 0);
+ kind = k_signed;
+ break;
+ default:
+ return k_invalid;
+ }
+ return !errno && !*tail && tail > str && isxdigit(tail[-1])
+ ? kind : k_string;
+}
+
tristate expr_calc_value(struct expr *e)
{
tristate val1, val2;
const char *str1, *str2;
+ enum string_value_kind k1 = k_string, k2 = k_string;
+ union string_value lval = {}, rval = {};
+ int res;
if (!e)
return yes;
val1 = expr_calc_value(e->left.expr);
return EXPR_NOT(val1);
case E_EQUAL:
- sym_calc_value(e->left.sym);
- sym_calc_value(e->right.sym);
- str1 = sym_get_string_value(e->left.sym);
- str2 = sym_get_string_value(e->right.sym);
- return !strcmp(str1, str2) ? yes : no;
+ case E_GEQ:
+ case E_GTH:
+ case E_LEQ:
+ case E_LTH:
case E_UNEQUAL:
- sym_calc_value(e->left.sym);
- sym_calc_value(e->right.sym);
- str1 = sym_get_string_value(e->left.sym);
- str2 = sym_get_string_value(e->right.sym);
- return !strcmp(str1, str2) ? no : yes;
+ break;
default:
printf("expr_calc_value: %d?\n", e->type);
return no;
}
+
+ sym_calc_value(e->left.sym);
+ sym_calc_value(e->right.sym);
+ str1 = sym_get_string_value(e->left.sym);
+ str2 = sym_get_string_value(e->right.sym);
+
+ if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
+ k1 = expr_parse_string(str1, e->left.sym->type, &lval);
+ k2 = expr_parse_string(str2, e->right.sym->type, &rval);
+ }
+
+ if (k1 == k_string || k2 == k_string)
+ res = strcmp(str1, str2);
+ else if (k1 == k_invalid || k2 == k_invalid) {
+ if (e->type != E_EQUAL && e->type != E_UNEQUAL) {
+ printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2);
+ return no;
+ }
+ res = strcmp(str1, str2);
+ } else if (k1 == k_unsigned || k2 == k_unsigned)
+ res = (lval.u > rval.u) - (lval.u < rval.u);
+ else /* if (k1 == k_signed && k2 == k_signed) */
+ res = (lval.s > rval.s) - (lval.s < rval.s);
+
+ switch(e->type) {
+ case E_EQUAL:
+ return res ? no : yes;
+ case E_GEQ:
+ return res >= 0 ? yes : no;
+ case E_GTH:
+ return res > 0 ? yes : no;
+ case E_LEQ:
+ return res <= 0 ? yes : no;
+ case E_LTH:
+ return res < 0 ? yes : no;
+ case E_UNEQUAL:
+ return res ? yes : no;
+ default:
+ printf("expr_calc_value: relation %d?\n", e->type);
+ return no;
+ }
}
-int expr_compare_type(enum expr_type t1, enum expr_type t2)
+static int expr_compare_type(enum expr_type t1, enum expr_type t2)
{
-#if 0
- return 1;
-#else
if (t1 == t2)
return 0;
switch (t1) {
+ case E_LEQ:
+ case E_LTH:
+ case E_GEQ:
+ case E_GTH:
+ if (t2 == E_EQUAL || t2 == E_UNEQUAL)
+ return 1;
case E_EQUAL:
case E_UNEQUAL:
if (t2 == E_NOT)
}
printf("[%dgt%d?]", t1, t2);
return 0;
-#endif
}
static inline struct expr *
return expr_get_leftmost_symbol(ret);
}
-void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
+static void __expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken, bool revdep)
{
if (!e) {
fn(data, NULL, "y");
fn(data, NULL, "=");
fn(data, e->right.sym, e->right.sym->name);
break;
+ case E_LEQ:
+ case E_LTH:
+ if (e->left.sym->name)
+ fn(data, e->left.sym, e->left.sym->name);
+ else
+ fn(data, NULL, "<choice>");
+ fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
+ fn(data, e->right.sym, e->right.sym->name);
+ break;
+ case E_GEQ:
+ case E_GTH:
+ if (e->left.sym->name)
+ fn(data, e->left.sym, e->left.sym->name);
+ else
+ fn(data, NULL, "<choice>");
+ fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
+ fn(data, e->right.sym, e->right.sym->name);
+ break;
case E_UNEQUAL:
if (e->left.sym->name)
fn(data, e->left.sym, e->left.sym->name);
fn(data, e->right.sym, e->right.sym->name);
break;
case E_OR:
- expr_print(e->left.expr, fn, data, E_OR);
- fn(data, NULL, " || ");
- expr_print(e->right.expr, fn, data, E_OR);
+ if (revdep && e->left.expr->type != E_OR)
+ fn(data, NULL, "\n - ");
+ __expr_print(e->left.expr, fn, data, E_OR, revdep);
+ if (revdep)
+ fn(data, NULL, "\n - ");
+ else
+ fn(data, NULL, " || ");
+ __expr_print(e->right.expr, fn, data, E_OR, revdep);
break;
case E_AND:
expr_print(e->left.expr, fn, data, E_AND);
fn(data, NULL, ")");
}
+void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
+{
+ __expr_print(e, fn, data, prevtoken, false);
+}
+
static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
{
xfwrite(str, strlen(str), 1, data);
{
expr_print(e, expr_print_gstr_helper, gs, E_NONE);
}
+
+/*
+ * Transform the top level "||" tokens into newlines and prepend each
+ * line with a minus. This makes expressions much easier to read.
+ * Suitable for reverse dependency expressions.
+ */
+void expr_gstr_print_revdep(struct expr *e, struct gstr *gs)
+{
+ __expr_print(e, expr_print_gstr_helper, gs, E_NONE, true);
+}
projects / carl9170fw.git / blobdiff