diff options
Diffstat (limited to 'scripts/config/expr.c')
| -rw-r--r-- | scripts/config/expr.c | 216 |
1 files changed, 61 insertions, 155 deletions
diff --git a/scripts/config/expr.c b/scripts/config/expr.c index 81ebf8108c..8cee597d33 100644 --- a/scripts/config/expr.c +++ b/scripts/config/expr.c @@ -1,10 +1,8 @@ -// 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> @@ -13,6 +11,7 @@ #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) @@ -95,7 +94,7 @@ struct expr *expr_copy(const struct expr *org) e->right.expr = expr_copy(org->right.expr); break; default: - fprintf(stderr, "can't copy type %d\n", e->type); + printf("can't copy type %d\n", e->type); free(e); e = NULL; break; @@ -114,7 +113,7 @@ void expr_free(struct expr *e) break; case E_NOT: expr_free(e->left.expr); - break; + return; case E_EQUAL: case E_GEQ: case E_GTH: @@ -128,7 +127,7 @@ void expr_free(struct expr *e) expr_free(e->right.expr); break; default: - fprintf(stderr, "how to free type %d?\n", e->type); + printf("how to free type %d?\n", e->type); break; } free(e); @@ -139,18 +138,8 @@ 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); @@ -161,18 +150,12 @@ 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) { @@ -189,35 +172,6 @@ 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) @@ -243,23 +197,10 @@ void expr_eliminate_eq(struct expr **ep1, struct expr **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) +static 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) { @@ -302,17 +243,6 @@ 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; @@ -586,21 +516,12 @@ 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); @@ -611,9 +532,6 @@ 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; @@ -650,17 +568,6 @@ 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; @@ -677,7 +584,6 @@ 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); } @@ -685,12 +591,6 @@ 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; @@ -905,20 +805,6 @@ 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; @@ -988,6 +874,7 @@ enum string_value_kind { k_string, k_signed, k_unsigned, + k_invalid }; union string_value { @@ -1018,10 +905,13 @@ static enum string_value_kind expr_parse_string(const char *str, val->u = strtoull(str, &tail, 16); kind = k_unsigned; break; - default: + 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; @@ -1077,7 +967,13 @@ tristate expr_calc_value(struct expr *e) if (k1 == k_string || k2 == k_string) res = strcmp(str1, str2); - else if (k1 == k_unsigned || k2 == k_unsigned) + 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); @@ -1135,9 +1031,49 @@ static int expr_compare_type(enum expr_type t1, enum expr_type t2) return 0; } -void expr_print(struct expr *e, - void (*fn)(void *, struct symbol *, const char *), - void *data, int prevtoken) +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) { if (!e) { fn(data, NULL, "y"); @@ -1271,33 +1207,3 @@ 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); -} |