-// 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>
#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)
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;
break;
case E_NOT:
expr_free(e->left.expr);
- break;
+ return;
case E_EQUAL:
case E_GEQ:
case E_GTH:
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);
#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
-/*
- * 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) {
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;
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
}
-/*
- * 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;
;
}
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 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;
k_string,
k_signed,
k_unsigned,
+ k_invalid
};
union string_value {
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;
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);
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");
{
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);
-}