summaryrefslogtreecommitdiffstats
path: root/scripts/kconfig/expr.c
diff options
context:
space:
mode:
Diffstat (limited to 'scripts/kconfig/expr.c')
-rw-r--r--scripts/kconfig/expr.c613
1 files changed, 245 insertions, 368 deletions
diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c
index a290de36307b..78738ef412de 100644
--- a/scripts/kconfig/expr.c
+++ b/scripts/kconfig/expr.c
@@ -9,44 +9,68 @@
#include <stdlib.h>
#include <string.h>
+#include <hash.h>
+#include <xalloc.h>
+#include "internal.h"
#include "lkc.h"
#define DEBUG_EXPR 0
+HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE);
+
static struct expr *expr_eliminate_yn(struct expr *e);
-struct expr *expr_alloc_symbol(struct symbol *sym)
+/**
+ * expr_lookup - return the expression with the given type and sub-nodes
+ * This looks up an expression with the specified type and sub-nodes. If such
+ * an expression is found in the hash table, it is returned. Otherwise, a new
+ * expression node is allocated and added to the hash table.
+ * @type: expression type
+ * @l: left node
+ * @r: right node
+ * return: expression
+ */
+static struct expr *expr_lookup(enum expr_type type, void *l, void *r)
{
- struct expr *e = xcalloc(1, sizeof(*e));
- e->type = E_SYMBOL;
- e->left.sym = sym;
+ struct expr *e;
+ int hash;
+
+ hash = hash_32((unsigned int)type ^ hash_ptr(l) ^ hash_ptr(r));
+
+ hash_for_each_possible(expr_hashtable, e, node, hash) {
+ if (e->type == type && e->left._initdata == l &&
+ e->right._initdata == r)
+ return e;
+ }
+
+ e = xmalloc(sizeof(*e));
+ e->type = type;
+ e->left._initdata = l;
+ e->right._initdata = r;
+
+ hash_add(expr_hashtable, &e->node, hash);
+
return e;
}
+struct expr *expr_alloc_symbol(struct symbol *sym)
+{
+ return expr_lookup(E_SYMBOL, sym, NULL);
+}
+
struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
{
- struct expr *e = xcalloc(1, sizeof(*e));
- e->type = type;
- e->left.expr = ce;
- return e;
+ return expr_lookup(type, ce, NULL);
}
struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
{
- struct expr *e = xcalloc(1, sizeof(*e));
- e->type = type;
- e->left.expr = e1;
- e->right.expr = e2;
- return e;
+ return expr_lookup(type, e1, e2);
}
struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
{
- struct expr *e = xcalloc(1, sizeof(*e));
- e->type = type;
- e->left.sym = s1;
- e->right.sym = s2;
- return e;
+ return expr_lookup(type, s1, s2);
}
struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
@@ -63,82 +87,8 @@ struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
}
-struct expr *expr_copy(const struct expr *org)
-{
- struct expr *e;
-
- if (!org)
- return NULL;
-
- e = xmalloc(sizeof(*org));
- memcpy(e, org, sizeof(*org));
- switch (org->type) {
- case E_SYMBOL:
- e->left = org->left;
- break;
- case E_NOT:
- 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_AND:
- case E_OR:
- case E_LIST:
- e->left.expr = expr_copy(org->left.expr);
- e->right.expr = expr_copy(org->right.expr);
- break;
- default:
- fprintf(stderr, "can't copy type %d\n", e->type);
- free(e);
- e = NULL;
- break;
- }
-
- return e;
-}
-
-void expr_free(struct expr *e)
-{
- if (!e)
- return;
-
- switch (e->type) {
- case E_SYMBOL:
- break;
- case E_NOT:
- expr_free(e->left.expr);
- break;
- case E_EQUAL:
- case E_GEQ:
- case E_GTH:
- case E_LEQ:
- case E_LTH:
- case E_UNEQUAL:
- break;
- case E_OR:
- case E_AND:
- expr_free(e->left.expr);
- expr_free(e->right.expr);
- break;
- default:
- fprintf(stderr, "how to free type %d?\n", e->type);
- break;
- }
- free(e);
-}
-
static int trans_count;
-#define e1 (*ep1)
-#define e2 (*ep2)
-
/*
* expr_eliminate_eq() helper.
*
@@ -149,40 +99,47 @@ static int trans_count;
*/
static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
{
+ struct expr *l, *r;
+
/* Recurse down to leaves */
- if (e1->type == type) {
- __expr_eliminate_eq(type, &e1->left.expr, &e2);
- __expr_eliminate_eq(type, &e1->right.expr, &e2);
+ if ((*ep1)->type == type) {
+ l = (*ep1)->left.expr;
+ r = (*ep1)->right.expr;
+ __expr_eliminate_eq(type, &l, ep2);
+ __expr_eliminate_eq(type, &r, ep2);
+ *ep1 = expr_alloc_two(type, l, r);
return;
}
- if (e2->type == type) {
- __expr_eliminate_eq(type, &e1, &e2->left.expr);
- __expr_eliminate_eq(type, &e1, &e2->right.expr);
+ if ((*ep2)->type == type) {
+ l = (*ep2)->left.expr;
+ r = (*ep2)->right.expr;
+ __expr_eliminate_eq(type, ep1, &l);
+ __expr_eliminate_eq(type, ep1, &r);
+ *ep2 = expr_alloc_two(type, l, r);
return;
}
- /* e1 and e2 are leaves. Compare them. */
+ /* *ep1 and *ep2 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))
+ if ((*ep1)->type == E_SYMBOL && (*ep2)->type == E_SYMBOL &&
+ (*ep1)->left.sym == (*ep2)->left.sym &&
+ ((*ep1)->left.sym == &symbol_yes || (*ep1)->left.sym == &symbol_no))
return;
- if (!expr_eq(e1, e2))
+ if (!expr_eq(*ep1, *ep2))
return;
- /* e1 and e2 are equal leaves. Prepare them for elimination. */
+ /* *ep1 and *ep2 are equal leaves. Prepare them for elimination. */
trans_count++;
- expr_free(e1); expr_free(e2);
switch (type) {
case E_OR:
- e1 = expr_alloc_symbol(&symbol_no);
- e2 = expr_alloc_symbol(&symbol_no);
+ *ep1 = expr_alloc_symbol(&symbol_no);
+ *ep2 = expr_alloc_symbol(&symbol_no);
break;
case E_AND:
- e1 = expr_alloc_symbol(&symbol_yes);
- e2 = expr_alloc_symbol(&symbol_yes);
+ *ep1 = expr_alloc_symbol(&symbol_yes);
+ *ep2 = expr_alloc_symbol(&symbol_yes);
break;
default:
;
@@ -220,38 +177,36 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e
*/
void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
{
- if (!e1 || !e2)
+ if (!*ep1 || !*ep2)
return;
- switch (e1->type) {
+ switch ((*ep1)->type) {
case E_OR:
case E_AND:
- __expr_eliminate_eq(e1->type, ep1, ep2);
+ __expr_eliminate_eq((*ep1)->type, ep1, ep2);
default:
;
}
- if (e1->type != e2->type) switch (e2->type) {
+ if ((*ep1)->type != (*ep2)->type) switch ((*ep2)->type) {
case E_OR:
case E_AND:
- __expr_eliminate_eq(e2->type, ep1, ep2);
+ __expr_eliminate_eq((*ep2)->type, ep1, ep2);
default:
;
}
- e1 = expr_eliminate_yn(e1);
- e2 = expr_eliminate_yn(e2);
+ *ep1 = expr_eliminate_yn(*ep1);
+ *ep2 = expr_eliminate_yn(*ep2);
}
-#undef e1
-#undef 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.
*/
-int expr_eq(struct expr *e1, struct expr *e2)
+bool expr_eq(struct expr *e1, struct expr *e2)
{
- int res, old_count;
+ int old_count;
+ bool res;
/*
* A NULL expr is taken to be yes, but there's also a different way to
@@ -261,7 +216,7 @@ int expr_eq(struct expr *e1, struct expr *e2)
return expr_is_yes(e1) && expr_is_yes(e2);
if (e1->type != e2->type)
- return 0;
+ return false;
switch (e1->type) {
case E_EQUAL:
case E_GEQ:
@@ -276,17 +231,12 @@ int expr_eq(struct expr *e1, struct expr *e2)
return expr_eq(e1->left.expr, e2->left.expr);
case E_AND:
case E_OR:
- e1 = expr_copy(e1);
- e2 = expr_copy(e2);
old_count = trans_count;
expr_eliminate_eq(&e1, &e2);
res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
e1->left.sym == e2->left.sym);
- expr_free(e1);
- expr_free(e2);
trans_count = old_count;
return res;
- case E_LIST:
case E_RANGE:
case E_NONE:
/* panic */;
@@ -299,11 +249,11 @@ int expr_eq(struct expr *e1, struct expr *e2)
printf(" ?\n");
}
- return 0;
+ return false;
}
/*
- * Recursively performs the following simplifications in-place (as well as the
+ * Recursively performs the following simplifications (as well as the
* corresponding simplifications with swapped operands):
*
* expr && n -> n
@@ -315,108 +265,39 @@ int expr_eq(struct expr *e1, struct expr *e2)
*/
static struct expr *expr_eliminate_yn(struct expr *e)
{
- struct expr *tmp;
+ struct expr *l, *r;
if (e) switch (e->type) {
case E_AND:
- e->left.expr = expr_eliminate_yn(e->left.expr);
- e->right.expr = expr_eliminate_yn(e->right.expr);
- if (e->left.expr->type == E_SYMBOL) {
- if (e->left.expr->left.sym == &symbol_no) {
- expr_free(e->left.expr);
- expr_free(e->right.expr);
- e->type = E_SYMBOL;
- e->left.sym = &symbol_no;
- e->right.expr = NULL;
- return e;
- } else if (e->left.expr->left.sym == &symbol_yes) {
- free(e->left.expr);
- tmp = e->right.expr;
- *e = *(e->right.expr);
- free(tmp);
- return e;
- }
+ l = expr_eliminate_yn(e->left.expr);
+ r = expr_eliminate_yn(e->right.expr);
+ if (l->type == E_SYMBOL) {
+ if (l->left.sym == &symbol_no)
+ return l;
+ else if (l->left.sym == &symbol_yes)
+ return r;
}
- if (e->right.expr->type == E_SYMBOL) {
- if (e->right.expr->left.sym == &symbol_no) {
- expr_free(e->left.expr);
- expr_free(e->right.expr);
- e->type = E_SYMBOL;
- e->left.sym = &symbol_no;
- e->right.expr = NULL;
- return e;
- } else if (e->right.expr->left.sym == &symbol_yes) {
- free(e->right.expr);
- tmp = e->left.expr;
- *e = *(e->left.expr);
- free(tmp);
- return e;
- }
+ if (r->type == E_SYMBOL) {
+ if (r->left.sym == &symbol_no)
+ return r;
+ else if (r->left.sym == &symbol_yes)
+ return l;
}
break;
case E_OR:
- e->left.expr = expr_eliminate_yn(e->left.expr);
- e->right.expr = expr_eliminate_yn(e->right.expr);
- if (e->left.expr->type == E_SYMBOL) {
- if (e->left.expr->left.sym == &symbol_no) {
- free(e->left.expr);
- tmp = e->right.expr;
- *e = *(e->right.expr);
- free(tmp);
- return e;
- } else if (e->left.expr->left.sym == &symbol_yes) {
- expr_free(e->left.expr);
- expr_free(e->right.expr);
- e->type = E_SYMBOL;
- e->left.sym = &symbol_yes;
- e->right.expr = NULL;
- return e;
- }
+ l = expr_eliminate_yn(e->left.expr);
+ r = expr_eliminate_yn(e->right.expr);
+ if (l->type == E_SYMBOL) {
+ if (l->left.sym == &symbol_no)
+ return r;
+ else if (l->left.sym == &symbol_yes)
+ return l;
}
- if (e->right.expr->type == E_SYMBOL) {
- if (e->right.expr->left.sym == &symbol_no) {
- free(e->right.expr);
- tmp = e->left.expr;
- *e = *(e->left.expr);
- free(tmp);
- return e;
- } else if (e->right.expr->left.sym == &symbol_yes) {
- expr_free(e->left.expr);
- expr_free(e->right.expr);
- e->type = E_SYMBOL;
- e->left.sym = &symbol_yes;
- e->right.expr = NULL;
- return e;
- }
- }
- break;
- default:
- ;
- }
- return e;
-}
-
-/*
- * bool FOO!=n => FOO
- */
-struct expr *expr_trans_bool(struct expr *e)
-{
- if (!e)
- return NULL;
- switch (e->type) {
- case E_AND:
- case E_OR:
- case E_NOT:
- e->left.expr = expr_trans_bool(e->left.expr);
- e->right.expr = expr_trans_bool(e->right.expr);
- break;
- case E_UNEQUAL:
- // FOO!=n -> FOO
- if (e->left.sym->type == S_TRISTATE) {
- if (e->right.sym == &symbol_no) {
- e->type = E_SYMBOL;
- e->right.sym = NULL;
- }
+ if (r->type == E_SYMBOL) {
+ if (r->left.sym == &symbol_no)
+ return l;
+ else if (r->left.sym == &symbol_yes)
+ return r;
}
break;
default:
@@ -434,7 +315,7 @@ static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
struct symbol *sym1, *sym2;
if (expr_eq(e1, e2))
- return expr_copy(e1);
+ return e1;
if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
return NULL;
if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
@@ -476,7 +357,8 @@ static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
}
}
- if (sym1->type == S_BOOLEAN && sym1 == sym2) {
+ if (sym1->type == S_BOOLEAN) {
+ // a || !a -> y
if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
(e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
return expr_alloc_symbol(&symbol_yes);
@@ -498,7 +380,7 @@ static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
struct symbol *sym1, *sym2;
if (expr_eq(e1, e2))
- return expr_copy(e1);
+ return e1;
if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
return NULL;
if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
@@ -595,59 +477,49 @@ static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
*/
static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
{
-#define e1 (*ep1)
-#define e2 (*ep2)
- struct expr *tmp;
+ struct expr *tmp, *l, *r;
/* Recurse down to leaves */
- if (e1->type == type) {
- expr_eliminate_dups1(type, &e1->left.expr, &e2);
- expr_eliminate_dups1(type, &e1->right.expr, &e2);
+ if ((*ep1)->type == type) {
+ l = (*ep1)->left.expr;
+ r = (*ep1)->right.expr;
+ expr_eliminate_dups1(type, &l, ep2);
+ expr_eliminate_dups1(type, &r, ep2);
+ *ep1 = expr_alloc_two(type, l, r);
return;
}
- if (e2->type == type) {
- expr_eliminate_dups1(type, &e1, &e2->left.expr);
- expr_eliminate_dups1(type, &e1, &e2->right.expr);
+ if ((*ep2)->type == type) {
+ l = (*ep2)->left.expr;
+ r = (*ep2)->right.expr;
+ expr_eliminate_dups1(type, ep1, &l);
+ expr_eliminate_dups1(type, ep1, &r);
+ *ep2 = expr_alloc_two(type, l, r);
return;
}
- /* e1 and e2 are leaves. Compare and process them. */
-
- if (e1 == e2)
- return;
-
- switch (e1->type) {
- case E_OR: case E_AND:
- expr_eliminate_dups1(e1->type, &e1, &e1);
- default:
- ;
- }
+ /* *ep1 and *ep2 are leaves. Compare and process them. */
switch (type) {
case E_OR:
- tmp = expr_join_or(e1, e2);
+ tmp = expr_join_or(*ep1, *ep2);
if (tmp) {
- expr_free(e1); expr_free(e2);
- e1 = expr_alloc_symbol(&symbol_no);
- e2 = tmp;
+ *ep1 = expr_alloc_symbol(&symbol_no);
+ *ep2 = tmp;
trans_count++;
}
break;
case E_AND:
- tmp = expr_join_and(e1, e2);
+ tmp = expr_join_and(*ep1, *ep2);
if (tmp) {
- expr_free(e1); expr_free(e2);
- e1 = expr_alloc_symbol(&symbol_yes);
- e2 = tmp;
+ *ep1 = expr_alloc_symbol(&symbol_yes);
+ *ep2 = tmp;
trans_count++;
}
break;
default:
;
}
-#undef e1
-#undef e2
}
/*
@@ -668,19 +540,21 @@ struct expr *expr_eliminate_dups(struct expr *e)
return e;
oldcount = trans_count;
- while (1) {
+ do {
+ struct expr *l, *r;
+
trans_count = 0;
switch (e->type) {
case E_OR: case E_AND:
- expr_eliminate_dups1(e->type, &e, &e);
+ l = expr_eliminate_dups(e->left.expr);
+ r = expr_eliminate_dups(e->right.expr);
+ expr_eliminate_dups1(e->type, &l, &r);
+ e = expr_alloc_two(e->type, l, r);
default:
;
}
- if (!trans_count)
- /* No simplifications done in this pass. We're done */
- break;
e = expr_eliminate_yn(e);
- }
+ } while (trans_count); /* repeat until we get no more simplifications */
trans_count = oldcount;
return e;
}
@@ -689,12 +563,34 @@ struct expr *expr_eliminate_dups(struct expr *e)
* Performs various simplifications involving logical operators and
* comparisons.
*
+ * For bool type:
+ * A=n -> !A
+ * A=m -> n
+ * A=y -> A
+ * A!=n -> A
+ * A!=m -> y
+ * A!=y -> !A
+ *
+ * For any type:
+ * !!A -> A
+ * !(A=B) -> A!=B
+ * !(A!=B) -> A=B
+ * !(A<=B) -> A>B
+ * !(A>=B) -> A<B
+ * !(A<B) -> A>=B
+ * !(A>B) -> A<=B
+ * !(A || B) -> !A && !B
+ * !(A && B) -> !A || !B
+ *
+ * For constant:
+ * !y -> n
+ * !m -> m
+ * !n -> y
+ *
* Allocates and returns a new expression.
*/
struct expr *expr_transform(struct expr *e)
{
- struct expr *tmp;
-
if (!e)
return NULL;
switch (e->type) {
@@ -705,11 +601,11 @@ struct expr *expr_transform(struct expr *e)
case E_LTH:
case E_UNEQUAL:
case E_SYMBOL:
- case E_LIST:
break;
default:
- e->left.expr = expr_transform(e->left.expr);
- e->right.expr = expr_transform(e->right.expr);
+ e = expr_alloc_two(e->type,
+ expr_transform(e->left.expr),
+ expr_transform(e->right.expr));
}
switch (e->type) {
@@ -717,21 +613,19 @@ struct expr *expr_transform(struct expr *e)
if (e->left.sym->type != S_BOOLEAN)
break;
if (e->right.sym == &symbol_no) {
- e->type = E_NOT;
- e->left.expr = expr_alloc_symbol(e->left.sym);
- e->right.sym = NULL;
+ // A=n -> !A
+ e = expr_alloc_one(E_NOT, expr_alloc_symbol(e->left.sym));
break;
}
if (e->right.sym == &symbol_mod) {
+ // A=m -> n
printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
- e->type = E_SYMBOL;
- e->left.sym = &symbol_no;
- e->right.sym = NULL;
+ e = expr_alloc_symbol(&symbol_no);
break;
}
if (e->right.sym == &symbol_yes) {
- e->type = E_SYMBOL;
- e->right.sym = NULL;
+ // A=y -> A
+ e = expr_alloc_symbol(e->left.sym);
break;
}
break;
@@ -739,104 +633,71 @@ struct expr *expr_transform(struct expr *e)
if (e->left.sym->type != S_BOOLEAN)
break;
if (e->right.sym == &symbol_no) {
- e->type = E_SYMBOL;
- e->right.sym = NULL;
+ // A!=n -> A
+ e = expr_alloc_symbol(e->left.sym);
break;
}
if (e->right.sym == &symbol_mod) {
+ // A!=m -> y
printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
- e->type = E_SYMBOL;
- e->left.sym = &symbol_yes;
- e->right.sym = NULL;
+ e = expr_alloc_symbol(&symbol_yes);
break;
}
if (e->right.sym == &symbol_yes) {
- e->type = E_NOT;
- e->left.expr = expr_alloc_symbol(e->left.sym);
- e->right.sym = NULL;
+ // A!=y -> !A
+ e = expr_alloc_one(E_NOT, e->left.expr);
break;
}
break;
case E_NOT:
switch (e->left.expr->type) {
case E_NOT:
- // !!a -> a
- tmp = e->left.expr->left.expr;
- free(e->left.expr);
- free(e);
- e = tmp;
- e = expr_transform(e);
+ // !!A -> A
+ e = e->left.expr->left.expr;
break;
case E_EQUAL:
case E_UNEQUAL:
- // !a='x' -> a!='x'
- tmp = e->left.expr;
- free(e);
- e = tmp;
- e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
+ // !(A=B) -> A!=B
+ e = expr_alloc_comp(e->left.expr->type == E_EQUAL ? E_UNEQUAL : E_EQUAL,
+ e->left.expr->left.sym,
+ e->left.expr->right.sym);
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;
+ // !(A<=B) -> A>B
+ e = expr_alloc_comp(e->left.expr->type == E_LEQ ? E_GTH : E_LTH,
+ e->left.expr->left.sym,
+ e->left.expr->right.sym);
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;
+ // !(A<B) -> A>=B
+ e = expr_alloc_comp(e->left.expr->type == E_LTH ? E_GEQ : E_LEQ,
+ e->left.expr->left.sym,
+ e->left.expr->right.sym);
break;
case E_OR:
- // !(a || b) -> !a && !b
- tmp = e->left.expr;
- e->type = E_AND;
- e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
- tmp->type = E_NOT;
- tmp->right.expr = NULL;
+ // !(A || B) -> !A && !B
+ e = expr_alloc_and(expr_alloc_one(E_NOT, e->left.expr->left.expr),
+ expr_alloc_one(E_NOT, e->left.expr->right.expr));
e = expr_transform(e);
break;
case E_AND:
- // !(a && b) -> !a || !b
- tmp = e->left.expr;
- e->type = E_OR;
- e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
- tmp->type = E_NOT;
- tmp->right.expr = NULL;
+ // !(A && B) -> !A || !B
+ e = expr_alloc_or(expr_alloc_one(E_NOT, e->left.expr->left.expr),
+ expr_alloc_one(E_NOT, e->left.expr->right.expr));
e = expr_transform(e);
break;
case E_SYMBOL:
- if (e->left.expr->left.sym == &symbol_yes) {
+ if (e->left.expr->left.sym == &symbol_yes)
// !'y' -> 'n'
- tmp = e->left.expr;
- free(e);
- e = tmp;
- e->type = E_SYMBOL;
- e->left.sym = &symbol_no;
- break;
- }
- if (e->left.expr->left.sym == &symbol_mod) {
+ e = expr_alloc_symbol(&symbol_no);
+ else if (e->left.expr->left.sym == &symbol_mod)
// !'m' -> 'm'
- tmp = e->left.expr;
- free(e);
- e = tmp;
- e->type = E_SYMBOL;
- e->left.sym = &symbol_mod;
- break;
- }
- if (e->left.expr->left.sym == &symbol_no) {
+ e = expr_alloc_symbol(&symbol_mod);
+ else if (e->left.expr->left.sym == &symbol_no)
// !'n' -> 'y'
- tmp = e->left.expr;
- free(e);
- e = tmp;
- e->type = E_SYMBOL;
- e->left.sym = &symbol_yes;
- break;
- }
+ e = expr_alloc_symbol(&symbol_yes);
break;
default:
;
@@ -848,10 +709,10 @@ struct expr *expr_transform(struct expr *e)
return e;
}
-int expr_contains_symbol(struct expr *dep, struct symbol *sym)
+bool expr_contains_symbol(struct expr *dep, struct symbol *sym)
{
if (!dep)
- return 0;
+ return false;
switch (dep->type) {
case E_AND:
@@ -873,7 +734,7 @@ int expr_contains_symbol(struct expr *dep, struct symbol *sym)
default:
;
}
- return 0;
+ return false;
}
bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
@@ -960,23 +821,22 @@ struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symb
case E_EQUAL:
if (type == E_EQUAL) {
if (sym == &symbol_yes)
- return expr_copy(e);
+ return e;
if (sym == &symbol_mod)
return expr_alloc_symbol(&symbol_no);
if (sym == &symbol_no)
- return expr_alloc_one(E_NOT, expr_copy(e));
+ return expr_alloc_one(E_NOT, e);
} else {
if (sym == &symbol_yes)
- return expr_alloc_one(E_NOT, expr_copy(e));
+ return expr_alloc_one(E_NOT, e);
if (sym == &symbol_mod)
return expr_alloc_symbol(&symbol_yes);
if (sym == &symbol_no)
- return expr_copy(e);
+ return e;
}
break;
case E_SYMBOL:
return expr_alloc_comp(type, e->left.sym, sym);
- case E_LIST:
case E_RANGE:
case E_NONE:
/* panic */;
@@ -1027,7 +887,7 @@ static enum string_value_kind expr_parse_string(const char *str,
? kind : k_string;
}
-tristate expr_calc_value(struct expr *e)
+static tristate __expr_calc_value(struct expr *e)
{
tristate val1, val2;
const char *str1, *str2;
@@ -1035,9 +895,6 @@ tristate expr_calc_value(struct expr *e)
union string_value lval = {}, rval = {};
int res;
- if (!e)
- return yes;
-
switch (e->type) {
case E_SYMBOL:
sym_calc_value(e->left.sym);
@@ -1101,6 +958,35 @@ tristate expr_calc_value(struct expr *e)
}
}
+/**
+ * expr_calc_value - return the tristate value of the given expression
+ * @e: expression
+ * return: tristate value of the expression
+ */
+tristate expr_calc_value(struct expr *e)
+{
+ if (!e)
+ return yes;
+
+ if (!e->val_is_valid) {
+ e->val = __expr_calc_value(e);
+ e->val_is_valid = true;
+ }
+
+ return e->val;
+}
+
+/**
+ * expr_invalidate_all - invalidate all cached expression values
+ */
+void expr_invalidate_all(void)
+{
+ struct expr *e;
+
+ hash_for_each(expr_hashtable, e, node)
+ e->val_is_valid = false;
+}
+
static int expr_compare_type(enum expr_type t1, enum expr_type t2)
{
if (t1 == t2)
@@ -1112,29 +998,27 @@ static int expr_compare_type(enum expr_type t1, enum expr_type t2)
case E_GTH:
if (t2 == E_EQUAL || t2 == E_UNEQUAL)
return 1;
+ /* fallthrough */
case E_EQUAL:
case E_UNEQUAL:
if (t2 == E_NOT)
return 1;
+ /* fallthrough */
case E_NOT:
if (t2 == E_AND)
return 1;
+ /* fallthrough */
case E_AND:
if (t2 == E_OR)
return 1;
- case E_OR:
- if (t2 == E_LIST)
- return 1;
- case E_LIST:
- if (t2 == 0)
- return 1;
+ /* fallthrough */
default:
- return -1;
+ break;
}
return 0;
}
-void expr_print(struct expr *e,
+void expr_print(const struct expr *e,
void (*fn)(void *, struct symbol *, const char *),
void *data, int prevtoken)
{
@@ -1200,13 +1084,6 @@ void expr_print(struct expr *e,
fn(data, NULL, " && ");
expr_print(e->right.expr, fn, data, E_AND);
break;
- case E_LIST:
- fn(data, e->right.sym, e->right.sym->name);
- if (e->left.expr) {
- fn(data, NULL, " ^ ");
- expr_print(e->left.expr, fn, data, E_LIST);
- }
- break;
case E_RANGE:
fn(data, NULL, "[");
fn(data, e->left.sym, e->left.sym->name);
@@ -1266,7 +1143,7 @@ static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *s
str_printf(gs, " [=%s]", sym_str);
}
-void expr_gstr_print(struct expr *e, struct gstr *gs)
+void expr_gstr_print(const struct expr *e, struct gstr *gs)
{
expr_print(e, expr_print_gstr_helper, gs, E_NONE);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-28 15:09:06 +0000