diff options
Diffstat (limited to 'kconfig/expr.c')
| -rw-r--r-- | kconfig/expr.c | 221 |
1 files changed, 159 insertions, 62 deletions
diff --git a/kconfig/expr.c b/kconfig/expr.c index cbf4996..81ebf81 100644 --- a/kconfig/expr.c +++ b/kconfig/expr.c @@ -1,8 +1,10 @@ +// SPDX-License-Identifier: GPL-2.0 /* * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> - * Released under the terms of the GNU GPL v2.0. */ +#include <ctype.h> +#include <errno.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -11,7 +13,6 @@ #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) @@ -94,7 +95,7 @@ struct expr *expr_copy(const struct expr *org) e->right.expr = expr_copy(org->right.expr); break; default: - printf("can't copy type %d\n", e->type); + fprintf(stderr, "can't copy type %d\n", e->type); free(e); e = NULL; break; @@ -113,7 +114,7 @@ void expr_free(struct expr *e) break; case E_NOT: expr_free(e->left.expr); - return; + break; case E_EQUAL: case E_GEQ: case E_GTH: @@ -127,7 +128,7 @@ void expr_free(struct expr *e) expr_free(e->right.expr); break; default: - printf("how to free type %d?\n", e->type); + fprintf(stderr, "how to free type %d?\n", e->type); break; } free(e); @@ -138,8 +139,18 @@ static int trans_count; #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); @@ -150,12 +161,18 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e __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) { @@ -172,6 +189,35 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e } } +/* + * 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) @@ -197,10 +243,23 @@ void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) #undef e1 #undef e2 -static 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. + */ +int expr_eq(struct expr *e1, struct expr *e2) { int res, old_count; + /* + * A NULL expr is taken to be yes, but there's also a different way to + * represent yes. expr_is_yes() checks for either representation. + */ + if (!e1 || !e2) + return expr_is_yes(e1) && expr_is_yes(e2); + if (e1->type != e2->type) return 0; switch (e1->type) { @@ -243,6 +302,17 @@ static int expr_eq(struct expr *e1, struct expr *e2) return 0; } +/* + * 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; @@ -516,12 +586,21 @@ static struct expr *expr_join_and(struct expr *e1, struct expr *e2) 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); @@ -532,6 +611,9 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr_eliminate_dups1(type, &e1, &e2->right.expr); return; } + + /* e1 and e2 are leaves. Compare and process them. */ + if (e1 == e2) return; @@ -568,6 +650,17 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct #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; @@ -584,6 +677,7 @@ struct expr *expr_eliminate_dups(struct expr *e) ; } if (!trans_count) + /* No simplifications done in this pass. We're done */ break; e = expr_eliminate_yn(e); } @@ -591,6 +685,12 @@ struct expr *expr_eliminate_dups(struct expr *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; @@ -805,6 +905,20 @@ bool expr_depends_symbol(struct expr *dep, struct symbol *sym) return false; } +/* + * 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; @@ -874,7 +988,6 @@ enum string_value_kind { k_string, k_signed, k_unsigned, - k_invalid }; union string_value { @@ -893,7 +1006,10 @@ static enum string_value_kind expr_parse_string(const char *str, switch (type) { case S_BOOLEAN: case S_TRISTATE: - return k_string; + 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; @@ -902,13 +1018,10 @@ static enum string_value_kind expr_parse_string(const char *str, val->u = strtoull(str, &tail, 16); kind = k_unsigned; break; - case S_STRING: - case S_UNKNOWN: + default: 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; @@ -964,13 +1077,7 @@ tristate expr_calc_value(struct expr *e) 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) + 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); @@ -1028,49 +1135,9 @@ static int expr_compare_type(enum expr_type t1, enum expr_type t2) return 0; } -static inline struct expr * -expr_get_leftmost_symbol(const struct expr *e) -{ - - if (e == NULL) - return NULL; - - while (e->type != E_SYMBOL) - e = e->left.expr; - - return expr_copy(e); -} - -/* - * Given expression `e1' and `e2', returns the leaf of the longest - * sub-expression of `e1' not containing 'e2. - */ -struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2) -{ - struct expr *ret; - - switch (e1->type) { - case E_OR: - return expr_alloc_and( - expr_simplify_unmet_dep(e1->left.expr, e2), - expr_simplify_unmet_dep(e1->right.expr, e2)); - case E_AND: { - struct expr *e; - e = expr_alloc_and(expr_copy(e1), expr_copy(e2)); - e = expr_eliminate_dups(e); - ret = (!expr_eq(e, e1)) ? e1 : NULL; - expr_free(e); - break; - } - default: - ret = e1; - break; - } - - return expr_get_leftmost_symbol(ret); -} - -void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken) +void expr_print(struct expr *e, + void (*fn)(void *, struct symbol *, const char *), + void *data, int prevtoken) { if (!e) { fn(data, NULL, "y"); @@ -1204,3 +1271,33 @@ void expr_gstr_print(struct expr *e, struct gstr *gs) { 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. + */ +static void expr_print_revdep(struct expr *e, + void (*fn)(void *, struct symbol *, const char *), + void *data, tristate pr_type, const char **title) +{ + if (e->type == E_OR) { + expr_print_revdep(e->left.expr, fn, data, pr_type, title); + expr_print_revdep(e->right.expr, fn, data, pr_type, title); + } else if (expr_calc_value(e) == pr_type) { + if (*title) { + fn(data, NULL, *title); + *title = NULL; + } + + fn(data, NULL, " - "); + expr_print(e, fn, data, E_NONE); + fn(data, NULL, "\n"); + } +} + +void expr_gstr_print_revdep(struct expr *e, struct gstr *gs, + tristate pr_type, const char *title) +{ + expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title); +} |