Adding upstream version 4.19.249.upstream/4.19.249upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1312 insertions, 0 deletions

diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c
new file mode 100644
index 000000000..7e38070ee
--- /dev/null
+++ b/scripts/kconfig/expr.c
@@ -0,0 +1,1312 @@
+/*
+ * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
+ * Released under the terms of the GNU GPL v2.0.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "lkc.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)
+{
+	struct expr *e = xcalloc(1, sizeof(*e));
+	e->type = E_SYMBOL;
+	e->left.sym = sym;
+	return e;
+}
+
+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;
+}
+
+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;
+}
+
+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;
+}
+
+struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
+{
+	if (!e1)
+		return e2;
+	return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
+}
+
+struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
+{
+	if (!e1)
+		return 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.
+ *
+ * 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);
+		return;
+	}
+	if (e2->type == type) {
+		__expr_eliminate_eq(type, &e1, &e2->left.expr);
+		__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) {
+	case E_OR:
+		e1 = expr_alloc_symbol(&symbol_no);
+		e2 = expr_alloc_symbol(&symbol_no);
+		break;
+	case E_AND:
+		e1 = expr_alloc_symbol(&symbol_yes);
+		e2 = expr_alloc_symbol(&symbol_yes);
+		break;
+	default:
+		;
+	}
+}
+
+/*
+ * 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)
+		return;
+	switch (e1->type) {
+	case E_OR:
+	case E_AND:
+		__expr_eliminate_eq(e1->type, ep1, ep2);
+	default:
+		;
+	}
+	if (e1->type != e2->type) switch (e2->type) {
+	case E_OR:
+	case E_AND:
+		__expr_eliminate_eq(e2->type, ep1, ep2);
+	default:
+		;
+	}
+	e1 = expr_eliminate_yn(e1);
+	e2 = expr_eliminate_yn(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.
+ */
+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) {
+	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 e1->left.sym == e2->left.sym;
+	case E_NOT:
+		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 */;
+	}
+
+	if (DEBUG_EXPR) {
+		expr_fprint(e1, stdout);
+		printf(" = ");
+		expr_fprint(e2, stdout);
+		printf(" ?\n");
+	}
+
+	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;
+
+	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;
+			}
+		}
+		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;
+			}
+		}
+		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;
+			}
+		}
+		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;
+			}
+		}
+		break;
+	default:
+		;
+	}
+	return e;
+}
+
+/*
+ * e1 || e2 -> ?
+ */
+static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
+{
+	struct expr *tmp;
+	struct symbol *sym1, *sym2;
+
+	if (expr_eq(e1, e2))
+		return expr_copy(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)
+		return NULL;
+	if (e1->type == E_NOT) {
+		tmp = e1->left.expr;
+		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
+			return NULL;
+		sym1 = tmp->left.sym;
+	} else
+		sym1 = e1->left.sym;
+	if (e2->type == E_NOT) {
+		if (e2->left.expr->type != E_SYMBOL)
+			return NULL;
+		sym2 = e2->left.expr->left.sym;
+	} else
+		sym2 = e2->left.sym;
+	if (sym1 != sym2)
+		return NULL;
+	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
+		return NULL;
+	if (sym1->type == S_TRISTATE) {
+		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
+		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
+		     (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
+			// (a='y') || (a='m') -> (a!='n')
+			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
+		}
+		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
+		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
+		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
+			// (a='y') || (a='n') -> (a!='m')
+			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
+		}
+		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
+		    ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
+		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
+			// (a='m') || (a='n') -> (a!='y')
+			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
+		}
+	}
+	if (sym1->type == S_BOOLEAN && sym1 == sym2) {
+		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);
+	}
+
+	if (DEBUG_EXPR) {
+		printf("optimize (");
+		expr_fprint(e1, stdout);
+		printf(") || (");
+		expr_fprint(e2, stdout);
+		printf(")?\n");
+	}
+	return NULL;
+}
+
+static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
+{
+	struct expr *tmp;
+	struct symbol *sym1, *sym2;
+
+	if (expr_eq(e1, e2))
+		return expr_copy(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)
+		return NULL;
+	if (e1->type == E_NOT) {
+		tmp = e1->left.expr;
+		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
+			return NULL;
+		sym1 = tmp->left.sym;
+	} else
+		sym1 = e1->left.sym;
+	if (e2->type == E_NOT) {
+		if (e2->left.expr->type != E_SYMBOL)
+			return NULL;
+		sym2 = e2->left.expr->left.sym;
+	} else
+		sym2 = e2->left.sym;
+	if (sym1 != sym2)
+		return NULL;
+	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
+		return NULL;
+
+	if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
+	    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
+		// (a) && (a='y') -> (a='y')
+		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
+
+	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
+	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
+		// (a) && (a!='n') -> (a)
+		return expr_alloc_symbol(sym1);
+
+	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
+	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
+		// (a) && (a!='m') -> (a='y')
+		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
+
+	if (sym1->type == S_TRISTATE) {
+		if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
+			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
+			sym2 = e1->right.sym;
+			if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
+				return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
+							     : expr_alloc_symbol(&symbol_no);
+		}
+		if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
+			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
+			sym2 = e2->right.sym;
+			if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
+				return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
+							     : expr_alloc_symbol(&symbol_no);
+		}
+		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
+			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
+			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
+			// (a!='y') && (a!='n') -> (a='m')
+			return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
+
+		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
+			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
+			    (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
+			// (a!='y') && (a!='m') -> (a='n')
+			return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
+
+		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
+			   ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
+			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
+			// (a!='m') && (a!='n') -> (a='m')
+			return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
+
+		if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
+		    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
+		    (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
+		    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
+			return NULL;
+	}
+
+	if (DEBUG_EXPR) {
+		printf("optimize (");
+		expr_fprint(e1, stdout);
+		printf(") && (");
+		expr_fprint(e2, stdout);
+		printf(")?\n");
+	}
+	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);
+		return;
+	}
+	if (e2->type == type) {
+		expr_eliminate_dups1(type, &e1, &e2->left.expr);
+		expr_eliminate_dups1(type, &e1, &e2->right.expr);
+		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:
+		;
+	}
+
+	switch (type) {
+	case E_OR:
+		tmp = expr_join_or(e1, e2);
+		if (tmp) {
+			expr_free(e1); expr_free(e2);
+			e1 = expr_alloc_symbol(&symbol_no);
+			e2 = tmp;
+			trans_count++;
+		}
+		break;
+	case E_AND:
+		tmp = expr_join_and(e1, e2);
+		if (tmp) {
+			expr_free(e1); expr_free(e2);
+			e1 = expr_alloc_symbol(&symbol_yes);
+			e2 = tmp;
+			trans_count++;
+		}
+		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;
+	if (!e)
+		return e;
+
+	oldcount = trans_count;
+	while (1) {
+		trans_count = 0;
+		switch (e->type) {
+		case E_OR: case E_AND:
+			expr_eliminate_dups1(e->type, &e, &e);
+		default:
+			;
+		}
+		if (!trans_count)
+			/* No simplifications done in this pass. We're done */
+			break;
+		e = expr_eliminate_yn(e);
+	}
+	trans_count = oldcount;
+	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;
+
+	if (!e)
+		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:
+		break;
+	default:
+		e->left.expr = expr_transform(e->left.expr);
+		e->right.expr = expr_transform(e->right.expr);
+	}
+
+	switch (e->type) {
+	case E_EQUAL:
+		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;
+			break;
+		}
+		if (e->right.sym == &symbol_mod) {
+			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;
+			break;
+		}
+		if (e->right.sym == &symbol_yes) {
+			e->type = E_SYMBOL;
+			e->right.sym = NULL;
+			break;
+		}
+		break;
+	case E_UNEQUAL:
+		if (e->left.sym->type != S_BOOLEAN)
+			break;
+		if (e->right.sym == &symbol_no) {
+			e->type = E_SYMBOL;
+			e->right.sym = NULL;
+			break;
+		}
+		if (e->right.sym == &symbol_mod) {
+			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;
+			break;
+		}
+		if (e->right.sym == &symbol_yes) {
+			e->type = E_NOT;
+			e->left.expr = expr_alloc_symbol(e->left.sym);
+			e->right.sym = NULL;
+			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);
+			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;
+			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;
+			e->type = E_AND;
+			e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
+			tmp->type = E_NOT;
+			tmp->right.expr = NULL;
+			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;
+			e = expr_transform(e);
+			break;
+		case E_SYMBOL:
+			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) {
+				// !'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) {
+				// !'n' -> 'y'
+				tmp = e->left.expr;
+				free(e);
+				e = tmp;
+				e->type = E_SYMBOL;
+				e->left.sym = &symbol_yes;
+				break;
+			}
+			break;
+		default:
+			;
+		}
+		break;
+	default:
+		;
+	}
+	return e;
+}
+
+int expr_contains_symbol(struct expr *dep, struct symbol *sym)
+{
+	if (!dep)
+		return 0;
+
+	switch (dep->type) {
+	case E_AND:
+	case E_OR:
+		return expr_contains_symbol(dep->left.expr, sym) ||
+		       expr_contains_symbol(dep->right.expr, sym);
+	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;
+	case E_NOT:
+		return expr_contains_symbol(dep->left.expr, sym);
+	default:
+		;
+	}
+	return 0;
+}
+
+bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
+{
+	if (!dep)
+		return false;
+
+	switch (dep->type) {
+	case E_AND:
+		return expr_depends_symbol(dep->left.expr, sym) ||
+		       expr_depends_symbol(dep->right.expr, sym);
+	case E_SYMBOL:
+		return dep->left.sym == sym;
+	case E_EQUAL:
+		if (dep->left.sym == sym) {
+			if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
+				return true;
+		}
+		break;
+	case E_UNEQUAL:
+		if (dep->left.sym == sym) {
+			if (dep->right.sym == &symbol_no)
+				return true;
+		}
+		break;
+	default:
+		;
+	}
+ 	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;
+
+	if (!e) {
+		e = expr_alloc_symbol(sym);
+		if (type == E_UNEQUAL)
+			e = expr_alloc_one(E_NOT, e);
+		return e;
+	}
+	switch (e->type) {
+	case E_AND:
+		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
+		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
+		if (sym == &symbol_yes)
+			e = expr_alloc_two(E_AND, e1, e2);
+		if (sym == &symbol_no)
+			e = expr_alloc_two(E_OR, e1, e2);
+		if (type == E_UNEQUAL)
+			e = expr_alloc_one(E_NOT, e);
+		return e;
+	case E_OR:
+		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
+		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
+		if (sym == &symbol_yes)
+			e = expr_alloc_two(E_OR, e1, e2);
+		if (sym == &symbol_no)
+			e = expr_alloc_two(E_AND, e1, e2);
+		if (type == E_UNEQUAL)
+			e = expr_alloc_one(E_NOT, e);
+		return e;
+	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 expr_copy(e);
+			if (sym == &symbol_mod)
+				return expr_alloc_symbol(&symbol_no);
+			if (sym == &symbol_no)
+				return expr_alloc_one(E_NOT, expr_copy(e));
+		} else {
+			if (sym == &symbol_yes)
+				return expr_alloc_one(E_NOT, expr_copy(e));
+			if (sym == &symbol_mod)
+				return expr_alloc_symbol(&symbol_yes);
+			if (sym == &symbol_no)
+				return expr_copy(e);
+		}
+		break;
+	case E_SYMBOL:
+		return expr_alloc_comp(type, e->left.sym, sym);
+	case E_LIST:
+	case E_RANGE:
+	case E_NONE:
+		/* panic */;
+	}
+	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;
+
+	switch (e->type) {
+	case E_SYMBOL:
+		sym_calc_value(e->left.sym);
+		return e->left.sym->curr.tri;
+	case E_AND:
+		val1 = expr_calc_value(e->left.expr);
+		val2 = expr_calc_value(e->right.expr);
+		return EXPR_AND(val1, val2);
+	case E_OR:
+		val1 = expr_calc_value(e->left.expr);
+		val2 = expr_calc_value(e->right.expr);
+		return EXPR_OR(val1, val2);
+	case E_NOT:
+		val1 = expr_calc_value(e->left.expr);
+		return EXPR_NOT(val1);
+	case E_EQUAL:
+	case E_GEQ:
+	case E_GTH:
+	case E_LEQ:
+	case E_LTH:
+	case E_UNEQUAL:
+		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;
+	}
+}
+
+static int expr_compare_type(enum expr_type t1, enum expr_type t2)
+{
+	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)
+			return 1;
+	case E_NOT:
+		if (t2 == E_AND)
+			return 1;
+	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;
+	default:
+		return -1;
+	}
+	printf("[%dgt%d?]", t1, t2);
+	return 0;
+}
+
+void expr_print(struct expr *e,
+		void (*fn)(void *, struct symbol *, const char *),
+		void *data, int prevtoken)
+{
+	if (!e) {
+		fn(data, NULL, "y");
+		return;
+	}
+
+	if (expr_compare_type(prevtoken, e->type) > 0)
+		fn(data, NULL, "(");
+	switch (e->type) {
+	case E_SYMBOL:
+		if (e->left.sym->name)
+			fn(data, e->left.sym, e->left.sym->name);
+		else
+			fn(data, NULL, "<choice>");
+		break;
+	case E_NOT:
+		fn(data, NULL, "!");
+		expr_print(e->left.expr, fn, data, E_NOT);
+		break;
+	case E_EQUAL:
+		if (e->left.sym->name)
+			fn(data, e->left.sym, e->left.sym->name);
+		else
+			fn(data, NULL, "<choice>");
+		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);
+		else
+			fn(data, NULL, "<choice>");
+		fn(data, NULL, "!=");
+		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);
+		break;
+	case E_AND:
+		expr_print(e->left.expr, fn, data, E_AND);
+		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);
+		fn(data, NULL, " ");
+		fn(data, e->right.sym, e->right.sym->name);
+		fn(data, NULL, "]");
+		break;
+	default:
+	  {
+		char buf[32];
+		sprintf(buf, "<unknown type %d>", e->type);
+		fn(data, NULL, buf);
+		break;
+	  }
+	}
+	if (expr_compare_type(prevtoken, e->type) > 0)
+		fn(data, NULL, ")");
+}
+
+static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
+{
+	xfwrite(str, strlen(str), 1, data);
+}
+
+void expr_fprint(struct expr *e, FILE *out)
+{
+	expr_print(e, expr_print_file_helper, out, E_NONE);
+}
+
+static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
+{
+	struct gstr *gs = (struct gstr*)data;
+	const char *sym_str = NULL;
+
+	if (sym)
+		sym_str = sym_get_string_value(sym);
+
+	if (gs->max_width) {
+		unsigned extra_length = strlen(str);
+		const char *last_cr = strrchr(gs->s, '\n');
+		unsigned last_line_length;
+
+		if (sym_str)
+			extra_length += 4 + strlen(sym_str);
+
+		if (!last_cr)
+			last_cr = gs->s;
+
+		last_line_length = strlen(gs->s) - (last_cr - gs->s);
+
+		if ((last_line_length + extra_length) > gs->max_width)
+			str_append(gs, "\\\n");
+	}
+
+	str_append(gs, str);
+	if (sym && sym->type != S_UNKNOWN)
+		str_printf(gs, " [=%s]", sym_str);
+}
+
+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);
+}