expr.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
   4 */
   5
   6#include <ctype.h>
   7#include <errno.h>
   8#include <stdio.h>
   9#include <stdlib.h>
  10#include <string.h>
  11
  12#include <hash.h>
  13#include <xalloc.h>
  14#include "internal.h"
  15#include "lkc.h"
  16
  17#define DEBUG_EXPR	0
  18
  19HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE);
  20
  21static struct expr *expr_eliminate_yn(struct expr *e);
  22
  23/**
  24 * expr_lookup - return the expression with the given type and sub-nodes
  25 * This looks up an expression with the specified type and sub-nodes. If such
  26 * an expression is found in the hash table, it is returned. Otherwise, a new
  27 * expression node is allocated and added to the hash table.
  28 * @type: expression type
  29 * @l: left node
  30 * @r: right node
  31 * return: expression
  32 */
  33static struct expr *expr_lookup(enum expr_type type, void *l, void *r)
  34{
  35	struct expr *e;
  36	int hash;
  37
  38	hash = hash_32((unsigned int)type ^ hash_ptr(l) ^ hash_ptr(r));
  39
  40	hash_for_each_possible(expr_hashtable, e, node, hash) {
  41		if (e->type == type && e->left._initdata == l &&
  42		    e->right._initdata == r)
  43			return e;
  44	}
  45
  46	e = xmalloc(sizeof(*e));
  47	e->type = type;
  48	e->left._initdata = l;
  49	e->right._initdata = r;
  50	e->val_is_valid = false;
  51
  52	hash_add(expr_hashtable, &e->node, hash);
  53
  54	return e;
  55}
  56
  57struct expr *expr_alloc_symbol(struct symbol *sym)
  58{
  59	return expr_lookup(E_SYMBOL, sym, NULL);
  60}
  61
  62struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
  63{
  64	return expr_lookup(type, ce, NULL);
  65}
  66
  67struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
  68{
  69	return expr_lookup(type, e1, e2);
  70}
  71
  72struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
  73{
  74	return expr_lookup(type, s1, s2);
  75}
  76
  77struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
  78{
  79	if (!e1)
  80		return e2;
  81	return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
  82}
  83
  84struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
  85{
  86	if (!e1)
  87		return e2;
  88	return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
  89}
  90
  91static int trans_count;
  92
  93/*
  94 * expr_eliminate_eq() helper.
  95 *
  96 * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
  97 * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
  98 * against all other leaves. Two equal leaves are both replaced with either 'y'
  99 * or 'n' as appropriate for 'type', to be eliminated later.
 100 */
 101static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
 102{
 103	struct expr *l, *r;
 104
 105	/* Recurse down to leaves */
 106
 107	if ((*ep1)->type == type) {
 108		l = (*ep1)->left.expr;
 109		r = (*ep1)->right.expr;
 110		__expr_eliminate_eq(type, &l, ep2);
 111		__expr_eliminate_eq(type, &r, ep2);
 112		*ep1 = expr_alloc_two(type, l, r);
 113		return;
 114	}
 115	if ((*ep2)->type == type) {
 116		l = (*ep2)->left.expr;
 117		r = (*ep2)->right.expr;
 118		__expr_eliminate_eq(type, ep1, &l);
 119		__expr_eliminate_eq(type, ep1, &r);
 120		*ep2 = expr_alloc_two(type, l, r);
 121		return;
 122	}
 123
 124	/* *ep1 and *ep2 are leaves. Compare them. */
 125
 126	if ((*ep1)->type == E_SYMBOL && (*ep2)->type == E_SYMBOL &&
 127	    (*ep1)->left.sym == (*ep2)->left.sym &&
 128	    ((*ep1)->left.sym == &symbol_yes || (*ep1)->left.sym == &symbol_no))
 129		return;
 130	if (!expr_eq(*ep1, *ep2))
 131		return;
 132
 133	/* *ep1 and *ep2 are equal leaves. Prepare them for elimination. */
 134
 135	trans_count++;
 136	switch (type) {
 137	case E_OR:
 138		*ep1 = expr_alloc_symbol(&symbol_no);
 139		*ep2 = expr_alloc_symbol(&symbol_no);
 140		break;
 141	case E_AND:
 142		*ep1 = expr_alloc_symbol(&symbol_yes);
 143		*ep2 = expr_alloc_symbol(&symbol_yes);
 144		break;
 145	default:
 146		;
 147	}
 148}
 149
 150/*
 151 * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both.
 152 * Example reductions:
 153 *
 154 *	ep1: A && B           ->  ep1: y
 155 *	ep2: A && B && C      ->  ep2: C
 156 *
 157 *	ep1: A || B           ->  ep1: n
 158 *	ep2: A || B || C      ->  ep2: C
 159 *
 160 *	ep1: A && (B && FOO)  ->  ep1: FOO
 161 *	ep2: (BAR && B) && A  ->  ep2: BAR
 162 *
 163 *	ep1: A && (B || C)    ->  ep1: y
 164 *	ep2: (C || B) && A    ->  ep2: y
 165 *
 166 * Comparisons are done between all operands at the same "level" of && or ||.
 167 * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the
 168 * following operands will be compared:
 169 *
 170 *	- 'e1', 'e2 || e3', and 'e4 || e5', against each other
 171 *	- e2 against e3
 172 *	- e4 against e5
 173 *
 174 * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and
 175 * '(e1 && e2) && e3' are both a single level.
 176 *
 177 * See __expr_eliminate_eq() as well.
 178 */
 179void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
 180{
 181	if (!*ep1 || !*ep2)
 182		return;
 183	switch ((*ep1)->type) {
 184	case E_OR:
 185	case E_AND:
 186		__expr_eliminate_eq((*ep1)->type, ep1, ep2);
 187	default:
 188		;
 189	}
 190	if ((*ep1)->type != (*ep2)->type) switch ((*ep2)->type) {
 191	case E_OR:
 192	case E_AND:
 193		__expr_eliminate_eq((*ep2)->type, ep1, ep2);
 194	default:
 195		;
 196	}
 197	*ep1 = expr_eliminate_yn(*ep1);
 198	*ep2 = expr_eliminate_yn(*ep2);
 199}
 200
 201/*
 202 * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two
 203 * &&/|| expressions are considered equal if every operand in one expression
 204 * equals some operand in the other (operands do not need to appear in the same
 205 * order), recursively.
 206 */
 207bool expr_eq(struct expr *e1, struct expr *e2)
 208{
 209	int old_count;
 210	bool res;
 211
 212	/*
 213	 * A NULL expr is taken to be yes, but there's also a different way to
 214	 * represent yes. expr_is_yes() checks for either representation.
 215	 */
 216	if (!e1 || !e2)
 217		return expr_is_yes(e1) && expr_is_yes(e2);
 218
 219	if (e1->type != e2->type)
 220		return false;
 221	switch (e1->type) {
 222	case E_EQUAL:
 223	case E_GEQ:
 224	case E_GTH:
 225	case E_LEQ:
 226	case E_LTH:
 227	case E_UNEQUAL:
 228		return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
 229	case E_SYMBOL:
 230		return e1->left.sym == e2->left.sym;
 231	case E_NOT:
 232		return expr_eq(e1->left.expr, e2->left.expr);
 233	case E_AND:
 234	case E_OR:
 235		old_count = trans_count;
 236		expr_eliminate_eq(&e1, &e2);
 237		res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
 238		       e1->left.sym == e2->left.sym);
 239		trans_count = old_count;
 240		return res;
 241	case E_RANGE:
 242	case E_NONE:
 243		/* panic */;
 244	}
 245
 246	if (DEBUG_EXPR) {
 247		expr_fprint(e1, stdout);
 248		printf(" = ");
 249		expr_fprint(e2, stdout);
 250		printf(" ?\n");
 251	}
 252
 253	return false;
 254}
 255
 256/*
 257 * Recursively performs the following simplifications (as well as the
 258 * corresponding simplifications with swapped operands):
 259 *
 260 *	expr && n  ->  n
 261 *	expr && y  ->  expr
 262 *	expr || n  ->  expr
 263 *	expr || y  ->  y
 264 *
 265 * Returns the optimized expression.
 266 */
 267static struct expr *expr_eliminate_yn(struct expr *e)
 268{
 269	struct expr *l, *r;
 270
 271	if (e) switch (e->type) {
 272	case E_AND:
 273		l = expr_eliminate_yn(e->left.expr);
 274		r = expr_eliminate_yn(e->right.expr);
 275		if (l->type == E_SYMBOL) {
 276			if (l->left.sym == &symbol_no)
 277				return l;
 278			else if (l->left.sym == &symbol_yes)
 279				return r;
 280		}
 281		if (r->type == E_SYMBOL) {
 282			if (r->left.sym == &symbol_no)
 283				return r;
 284			else if (r->left.sym == &symbol_yes)
 285				return l;
 286		}
 287		break;
 288	case E_OR:
 289		l = expr_eliminate_yn(e->left.expr);
 290		r = expr_eliminate_yn(e->right.expr);
 291		if (l->type == E_SYMBOL) {
 292			if (l->left.sym == &symbol_no)
 293				return r;
 294			else if (l->left.sym == &symbol_yes)
 295				return l;
 296		}
 297		if (r->type == E_SYMBOL) {
 298			if (r->left.sym == &symbol_no)
 299				return l;
 300			else if (r->left.sym == &symbol_yes)
 301				return r;
 302		}
 303		break;
 304	default:
 305		;
 306	}
 307	return e;
 308}
 309
 310/*
 311 * e1 || e2 -> ?
 312 */
 313static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
 314{
 315	struct expr *tmp;
 316	struct symbol *sym1, *sym2;
 317
 318	if (expr_eq(e1, e2))
 319		return e1;
 320	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
 321		return NULL;
 322	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
 323		return NULL;
 324	if (e1->type == E_NOT) {
 325		tmp = e1->left.expr;
 326		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
 327			return NULL;
 328		sym1 = tmp->left.sym;
 329	} else
 330		sym1 = e1->left.sym;
 331	if (e2->type == E_NOT) {
 332		if (e2->left.expr->type != E_SYMBOL)
 333			return NULL;
 334		sym2 = e2->left.expr->left.sym;
 335	} else
 336		sym2 = e2->left.sym;
 337	if (sym1 != sym2)
 338		return NULL;
 339	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
 340		return NULL;
 341	if (sym1->type == S_TRISTATE) {
 342		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
 343		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
 344		     (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
 345			// (a='y') || (a='m') -> (a!='n')
 346			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
 347		}
 348		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
 349		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
 350		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
 351			// (a='y') || (a='n') -> (a!='m')
 352			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
 353		}
 354		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
 355		    ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
 356		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
 357			// (a='m') || (a='n') -> (a!='y')
 358			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
 359		}
 360	}
 361	if (sym1->type == S_BOOLEAN) {
 362		// a || !a -> y
 363		if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
 364		    (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
 365			return expr_alloc_symbol(&symbol_yes);
 366	}
 367
 368	if (DEBUG_EXPR) {
 369		printf("optimize (");
 370		expr_fprint(e1, stdout);
 371		printf(") || (");
 372		expr_fprint(e2, stdout);
 373		printf(")?\n");
 374	}
 375	return NULL;
 376}
 377
 378static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
 379{
 380	struct expr *tmp;
 381	struct symbol *sym1, *sym2;
 382
 383	if (expr_eq(e1, e2))
 384		return e1;
 385	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
 386		return NULL;
 387	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
 388		return NULL;
 389	if (e1->type == E_NOT) {
 390		tmp = e1->left.expr;
 391		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
 392			return NULL;
 393		sym1 = tmp->left.sym;
 394	} else
 395		sym1 = e1->left.sym;
 396	if (e2->type == E_NOT) {
 397		if (e2->left.expr->type != E_SYMBOL)
 398			return NULL;
 399		sym2 = e2->left.expr->left.sym;
 400	} else
 401		sym2 = e2->left.sym;
 402	if (sym1 != sym2)
 403		return NULL;
 404	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
 405		return NULL;
 406
 407	if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
 408	    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
 409		// (a) && (a='y') -> (a='y')
 410		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
 411
 412	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
 413	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
 414		// (a) && (a!='n') -> (a)
 415		return expr_alloc_symbol(sym1);
 416
 417	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
 418	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
 419		// (a) && (a!='m') -> (a='y')
 420		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
 421
 422	if (sym1->type == S_TRISTATE) {
 423		if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
 424			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
 425			sym2 = e1->right.sym;
 426			if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
 427				return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
 428							     : expr_alloc_symbol(&symbol_no);
 429		}
 430		if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
 431			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
 432			sym2 = e2->right.sym;
 433			if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
 434				return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
 435							     : expr_alloc_symbol(&symbol_no);
 436		}
 437		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
 438			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
 439			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
 440			// (a!='y') && (a!='n') -> (a='m')
 441			return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
 442
 443		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
 444			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
 445			    (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
 446			// (a!='y') && (a!='m') -> (a='n')
 447			return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
 448
 449		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
 450			   ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
 451			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
 452			// (a!='m') && (a!='n') -> (a='m')
 453			return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
 454
 455		if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
 456		    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
 457		    (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
 458		    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
 459			return NULL;
 460	}
 461
 462	if (DEBUG_EXPR) {
 463		printf("optimize (");
 464		expr_fprint(e1, stdout);
 465		printf(") && (");
 466		expr_fprint(e2, stdout);
 467		printf(")?\n");
 468	}
 469	return NULL;
 470}
 471
 472/*
 473 * expr_eliminate_dups() helper.
 474 *
 475 * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
 476 * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
 477 * against all other leaves to look for simplifications.
 478 */
 479static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
 480{
 481	struct expr *tmp, *l, *r;
 482
 483	/* Recurse down to leaves */
 484
 485	if ((*ep1)->type == type) {
 486		l = (*ep1)->left.expr;
 487		r = (*ep1)->right.expr;
 488		expr_eliminate_dups1(type, &l, ep2);
 489		expr_eliminate_dups1(type, &r, ep2);
 490		*ep1 = expr_alloc_two(type, l, r);
 491		return;
 492	}
 493	if ((*ep2)->type == type) {
 494		l = (*ep2)->left.expr;
 495		r = (*ep2)->right.expr;
 496		expr_eliminate_dups1(type, ep1, &l);
 497		expr_eliminate_dups1(type, ep1, &r);
 498		*ep2 = expr_alloc_two(type, l, r);
 499		return;
 500	}
 501
 502	/* *ep1 and *ep2 are leaves. Compare and process them. */
 503
 504	switch (type) {
 505	case E_OR:
 506		tmp = expr_join_or(*ep1, *ep2);
 507		if (tmp) {
 508			*ep1 = expr_alloc_symbol(&symbol_no);
 509			*ep2 = tmp;
 510			trans_count++;
 511		}
 512		break;
 513	case E_AND:
 514		tmp = expr_join_and(*ep1, *ep2);
 515		if (tmp) {
 516			*ep1 = expr_alloc_symbol(&symbol_yes);
 517			*ep2 = tmp;
 518			trans_count++;
 519		}
 520		break;
 521	default:
 522		;
 523	}
 524}
 525
 526/*
 527 * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
 528 * operands.
 529 *
 530 * Example simplifications:
 531 *
 532 *	A || B || A    ->  A || B
 533 *	A && B && A=y  ->  A=y && B
 534 *
 535 * Returns the deduplicated expression.
 536 */
 537struct expr *expr_eliminate_dups(struct expr *e)
 538{
 539	int oldcount;
 540	if (!e)
 541		return e;
 542
 543	oldcount = trans_count;
 544	do {
 545		struct expr *l, *r;
 546
 547		trans_count = 0;
 548		switch (e->type) {
 549		case E_OR: case E_AND:
 550			l = expr_eliminate_dups(e->left.expr);
 551			r = expr_eliminate_dups(e->right.expr);
 552			expr_eliminate_dups1(e->type, &l, &r);
 553			e = expr_alloc_two(e->type, l, r);
 554		default:
 555			;
 556		}
 557		e = expr_eliminate_yn(e);
 558	} while (trans_count); /* repeat until we get no more simplifications */
 559	trans_count = oldcount;
 560	return e;
 561}
 562
 563/*
 564 * Performs various simplifications involving logical operators and
 565 * comparisons.
 566 *
 567 *   For bool type:
 568 *     A=n        ->  !A
 569 *     A=m        ->  n
 570 *     A=y        ->  A
 571 *     A!=n       ->  A
 572 *     A!=m       ->  y
 573 *     A!=y       ->  !A
 574 *
 575 *   For any type:
 576 *     !!A        ->  A
 577 *     !(A=B)     ->  A!=B
 578 *     !(A!=B)    ->  A=B
 579 *     !(A<=B)    ->  A>B
 580 *     !(A>=B)    ->  A<B
 581 *     !(A<B)     ->  A>=B
 582 *     !(A>B)     ->  A<=B
 583 *     !(A || B)  ->  !A && !B
 584 *     !(A && B)  ->  !A || !B
 585 *
 586 *   For constant:
 587 *     !y         ->  n
 588 *     !m         ->  m
 589 *     !n         ->  y
 590 *
 591 * Allocates and returns a new expression.
 592 */
 593struct expr *expr_transform(struct expr *e)
 594{
 595	if (!e)
 596		return NULL;
 597	switch (e->type) {
 598	case E_EQUAL:
 599	case E_GEQ:
 600	case E_GTH:
 601	case E_LEQ:
 602	case E_LTH:
 603	case E_UNEQUAL:
 604	case E_SYMBOL:
 605		break;
 606	default:
 607		e = expr_alloc_two(e->type,
 608				   expr_transform(e->left.expr),
 609				   expr_transform(e->right.expr));
 610	}
 611
 612	switch (e->type) {
 613	case E_EQUAL:
 614		if (e->left.sym->type != S_BOOLEAN)
 615			break;
 616		if (e->right.sym == &symbol_no) {
 617			// A=n -> !A
 618			e = expr_alloc_one(E_NOT, expr_alloc_symbol(e->left.sym));
 619			break;
 620		}
 621		if (e->right.sym == &symbol_mod) {
 622			// A=m -> n
 623			printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
 624			e = expr_alloc_symbol(&symbol_no);
 625			break;
 626		}
 627		if (e->right.sym == &symbol_yes) {
 628			// A=y -> A
 629			e = expr_alloc_symbol(e->left.sym);
 630			break;
 631		}
 632		break;
 633	case E_UNEQUAL:
 634		if (e->left.sym->type != S_BOOLEAN)
 635			break;
 636		if (e->right.sym == &symbol_no) {
 637			// A!=n -> A
 638			e = expr_alloc_symbol(e->left.sym);
 639			break;
 640		}
 641		if (e->right.sym == &symbol_mod) {
 642			// A!=m -> y
 643			printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
 644			e = expr_alloc_symbol(&symbol_yes);
 645			break;
 646		}
 647		if (e->right.sym == &symbol_yes) {
 648			// A!=y -> !A
 649			e = expr_alloc_one(E_NOT, e->left.expr);
 650			break;
 651		}
 652		break;
 653	case E_NOT:
 654		switch (e->left.expr->type) {
 655		case E_NOT:
 656			// !!A -> A
 657			e = e->left.expr->left.expr;
 658			break;
 659		case E_EQUAL:
 660		case E_UNEQUAL:
 661			// !(A=B) -> A!=B
 662			e = expr_alloc_comp(e->left.expr->type == E_EQUAL ? E_UNEQUAL : E_EQUAL,
 663					    e->left.expr->left.sym,
 664					    e->left.expr->right.sym);
 665			break;
 666		case E_LEQ:
 667		case E_GEQ:
 668			// !(A<=B) -> A>B
 669			e = expr_alloc_comp(e->left.expr->type == E_LEQ ? E_GTH : E_LTH,
 670					    e->left.expr->left.sym,
 671					    e->left.expr->right.sym);
 672			break;
 673		case E_LTH:
 674		case E_GTH:
 675			// !(A<B) -> A>=B
 676			e = expr_alloc_comp(e->left.expr->type == E_LTH ? E_GEQ : E_LEQ,
 677					    e->left.expr->left.sym,
 678					    e->left.expr->right.sym);
 679			break;
 680		case E_OR:
 681			// !(A || B) -> !A && !B
 682			e = expr_alloc_and(expr_alloc_one(E_NOT, e->left.expr->left.expr),
 683					   expr_alloc_one(E_NOT, e->left.expr->right.expr));
 684			e = expr_transform(e);
 685			break;
 686		case E_AND:
 687			// !(A && B) -> !A || !B
 688			e = expr_alloc_or(expr_alloc_one(E_NOT, e->left.expr->left.expr),
 689					  expr_alloc_one(E_NOT, e->left.expr->right.expr));
 690			e = expr_transform(e);
 691			break;
 692		case E_SYMBOL:
 693			if (e->left.expr->left.sym == &symbol_yes)
 694				// !'y' -> 'n'
 695				e = expr_alloc_symbol(&symbol_no);
 696			else if (e->left.expr->left.sym == &symbol_mod)
 697				// !'m' -> 'm'
 698				e = expr_alloc_symbol(&symbol_mod);
 699			else if (e->left.expr->left.sym == &symbol_no)
 700				// !'n' -> 'y'
 701				e = expr_alloc_symbol(&symbol_yes);
 702			break;
 703		default:
 704			;
 705		}
 706		break;
 707	default:
 708		;
 709	}
 710	return e;
 711}
 712
 713bool expr_contains_symbol(struct expr *dep, struct symbol *sym)
 714{
 715	if (!dep)
 716		return false;
 717
 718	switch (dep->type) {
 719	case E_AND:
 720	case E_OR:
 721		return expr_contains_symbol(dep->left.expr, sym) ||
 722		       expr_contains_symbol(dep->right.expr, sym);
 723	case E_SYMBOL:
 724		return dep->left.sym == sym;
 725	case E_EQUAL:
 726	case E_GEQ:
 727	case E_GTH:
 728	case E_LEQ:
 729	case E_LTH:
 730	case E_UNEQUAL:
 731		return dep->left.sym == sym ||
 732		       dep->right.sym == sym;
 733	case E_NOT:
 734		return expr_contains_symbol(dep->left.expr, sym);
 735	default:
 736		;
 737	}
 738	return false;
 739}
 740
 741bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
 742{
 743	if (!dep)
 744		return false;
 745
 746	switch (dep->type) {
 747	case E_AND:
 748		return expr_depends_symbol(dep->left.expr, sym) ||
 749		       expr_depends_symbol(dep->right.expr, sym);
 750	case E_SYMBOL:
 751		return dep->left.sym == sym;
 752	case E_EQUAL:
 753		if (dep->left.sym == sym) {
 754			if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
 755				return true;
 756		}
 757		break;
 758	case E_UNEQUAL:
 759		if (dep->left.sym == sym) {
 760			if (dep->right.sym == &symbol_no)
 761				return true;
 762		}
 763		break;
 764	default:
 765		;
 766	}
 767 	return false;
 768}
 769
 770/*
 771 * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
 772 * expression 'e'.
 773 *
 774 * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
 775 *
 776 *	A              ->  A!=n
 777 *	!A             ->  A=n
 778 *	A && B         ->  !(A=n || B=n)
 779 *	A || B         ->  !(A=n && B=n)
 780 *	A && (B || C)  ->  !(A=n || (B=n && C=n))
 781 *
 782 * Allocates and returns a new expression.
 783 */
 784struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
 785{
 786	struct expr *e1, *e2;
 787
 788	if (!e) {
 789		e = expr_alloc_symbol(sym);
 790		if (type == E_UNEQUAL)
 791			e = expr_alloc_one(E_NOT, e);
 792		return e;
 793	}
 794	switch (e->type) {
 795	case E_AND:
 796		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
 797		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
 798		if (sym == &symbol_yes)
 799			e = expr_alloc_two(E_AND, e1, e2);
 800		if (sym == &symbol_no)
 801			e = expr_alloc_two(E_OR, e1, e2);
 802		if (type == E_UNEQUAL)
 803			e = expr_alloc_one(E_NOT, e);
 804		return e;
 805	case E_OR:
 806		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
 807		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
 808		if (sym == &symbol_yes)
 809			e = expr_alloc_two(E_OR, e1, e2);
 810		if (sym == &symbol_no)
 811			e = expr_alloc_two(E_AND, e1, e2);
 812		if (type == E_UNEQUAL)
 813			e = expr_alloc_one(E_NOT, e);
 814		return e;
 815	case E_NOT:
 816		return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
 817	case E_UNEQUAL:
 818	case E_LTH:
 819	case E_LEQ:
 820	case E_GTH:
 821	case E_GEQ:
 822	case E_EQUAL:
 823		if (type == E_EQUAL) {
 824			if (sym == &symbol_yes)
 825				return e;
 826			if (sym == &symbol_mod)
 827				return expr_alloc_symbol(&symbol_no);
 828			if (sym == &symbol_no)
 829				return expr_alloc_one(E_NOT, e);
 830		} else {
 831			if (sym == &symbol_yes)
 832				return expr_alloc_one(E_NOT, e);
 833			if (sym == &symbol_mod)
 834				return expr_alloc_symbol(&symbol_yes);
 835			if (sym == &symbol_no)
 836				return e;
 837		}
 838		break;
 839	case E_SYMBOL:
 840		return expr_alloc_comp(type, e->left.sym, sym);
 841	case E_RANGE:
 842	case E_NONE:
 843		/* panic */;
 844	}
 845	return NULL;
 846}
 847
 848enum string_value_kind {
 849	k_string,
 850	k_signed,
 851	k_unsigned,
 852};
 853
 854union string_value {
 855	unsigned long long u;
 856	signed long long s;
 857};
 858
 859static enum string_value_kind expr_parse_string(const char *str,
 860						enum symbol_type type,
 861						union string_value *val)
 862{
 863	char *tail;
 864	enum string_value_kind kind;
 865
 866	errno = 0;
 867	switch (type) {
 868	case S_BOOLEAN:
 869	case S_TRISTATE:
 870		val->s = !strcmp(str, "n") ? 0 :
 871			 !strcmp(str, "m") ? 1 :
 872			 !strcmp(str, "y") ? 2 : -1;
 873		return k_signed;
 874	case S_INT:
 875		val->s = strtoll(str, &tail, 10);
 876		kind = k_signed;
 877		break;
 878	case S_HEX:
 879		val->u = strtoull(str, &tail, 16);
 880		kind = k_unsigned;
 881		break;
 882	default:
 883		val->s = strtoll(str, &tail, 0);
 884		kind = k_signed;
 885		break;
 886	}
 887	return !errno && !*tail && tail > str && isxdigit(tail[-1])
 888	       ? kind : k_string;
 889}
 890
 891static tristate __expr_calc_value(struct expr *e)
 892{
 893	tristate val1, val2;
 894	const char *str1, *str2;
 895	enum string_value_kind k1 = k_string, k2 = k_string;
 896	union string_value lval = {}, rval = {};
 897	int res;
 898
 899	switch (e->type) {
 900	case E_SYMBOL:
 901		sym_calc_value(e->left.sym);
 902		return e->left.sym->curr.tri;
 903	case E_AND:
 904		val1 = expr_calc_value(e->left.expr);
 905		val2 = expr_calc_value(e->right.expr);
 906		return EXPR_AND(val1, val2);
 907	case E_OR:
 908		val1 = expr_calc_value(e->left.expr);
 909		val2 = expr_calc_value(e->right.expr);
 910		return EXPR_OR(val1, val2);
 911	case E_NOT:
 912		val1 = expr_calc_value(e->left.expr);
 913		return EXPR_NOT(val1);
 914	case E_EQUAL:
 915	case E_GEQ:
 916	case E_GTH:
 917	case E_LEQ:
 918	case E_LTH:
 919	case E_UNEQUAL:
 920		break;
 921	default:
 922		printf("expr_calc_value: %d?\n", e->type);
 923		return no;
 924	}
 925
 926	sym_calc_value(e->left.sym);
 927	sym_calc_value(e->right.sym);
 928	str1 = sym_get_string_value(e->left.sym);
 929	str2 = sym_get_string_value(e->right.sym);
 930
 931	if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
 932		k1 = expr_parse_string(str1, e->left.sym->type, &lval);
 933		k2 = expr_parse_string(str2, e->right.sym->type, &rval);
 934	}
 935
 936	if (k1 == k_string || k2 == k_string)
 937		res = strcmp(str1, str2);
 938	else if (k1 == k_unsigned || k2 == k_unsigned)
 939		res = (lval.u > rval.u) - (lval.u < rval.u);
 940	else /* if (k1 == k_signed && k2 == k_signed) */
 941		res = (lval.s > rval.s) - (lval.s < rval.s);
 942
 943	switch(e->type) {
 944	case E_EQUAL:
 945		return res ? no : yes;
 946	case E_GEQ:
 947		return res >= 0 ? yes : no;
 948	case E_GTH:
 949		return res > 0 ? yes : no;
 950	case E_LEQ:
 951		return res <= 0 ? yes : no;
 952	case E_LTH:
 953		return res < 0 ? yes : no;
 954	case E_UNEQUAL:
 955		return res ? yes : no;
 956	default:
 957		printf("expr_calc_value: relation %d?\n", e->type);
 958		return no;
 959	}
 960}
 961
 962/**
 963 * expr_calc_value - return the tristate value of the given expression
 964 * @e: expression
 965 * return: tristate value of the expression
 966 */
 967tristate expr_calc_value(struct expr *e)
 968{
 969	if (!e)
 970		return yes;
 971
 972	if (!e->val_is_valid) {
 973		e->val = __expr_calc_value(e);
 974		e->val_is_valid = true;
 975	}
 976
 977	return e->val;
 978}
 979
 980/**
 981 * expr_invalidate_all - invalidate all cached expression values
 982 */
 983void expr_invalidate_all(void)
 984{
 985	struct expr *e;
 986
 987	hash_for_each(expr_hashtable, e, node)
 988		e->val_is_valid = false;
 989}
 990
 991static int expr_compare_type(enum expr_type t1, enum expr_type t2)
 992{
 993	if (t1 == t2)
 994		return 0;
 995	switch (t1) {
 996	case E_LEQ:
 997	case E_LTH:
 998	case E_GEQ:
 999	case E_GTH:
1000		if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1001			return 1;
1002		/* fallthrough */
1003	case E_EQUAL:
1004	case E_UNEQUAL:
1005		if (t2 == E_NOT)
1006			return 1;
1007		/* fallthrough */
1008	case E_NOT:
1009		if (t2 == E_AND)
1010			return 1;
1011		/* fallthrough */
1012	case E_AND:
1013		if (t2 == E_OR)
1014			return 1;
1015		/* fallthrough */
1016	default:
1017		break;
1018	}
1019	return 0;
1020}
1021
1022void expr_print(const struct expr *e,
1023		void (*fn)(void *, struct symbol *, const char *),
1024		void *data, int prevtoken)
1025{
1026	if (!e) {
1027		fn(data, NULL, "y");
1028		return;
1029	}
1030
1031	if (expr_compare_type(prevtoken, e->type) > 0)
1032		fn(data, NULL, "(");
1033	switch (e->type) {
1034	case E_SYMBOL:
1035		if (e->left.sym->name)
1036			fn(data, e->left.sym, e->left.sym->name);
1037		else
1038			fn(data, NULL, "<choice>");
1039		break;
1040	case E_NOT:
1041		fn(data, NULL, "!");
1042		expr_print(e->left.expr, fn, data, E_NOT);
1043		break;
1044	case E_EQUAL:
1045		if (e->left.sym->name)
1046			fn(data, e->left.sym, e->left.sym->name);
1047		else
1048			fn(data, NULL, "<choice>");
1049		fn(data, NULL, "=");
1050		fn(data, e->right.sym, e->right.sym->name);
1051		break;
1052	case E_LEQ:
1053	case E_LTH:
1054		if (e->left.sym->name)
1055			fn(data, e->left.sym, e->left.sym->name);
1056		else
1057			fn(data, NULL, "<choice>");
1058		fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1059		fn(data, e->right.sym, e->right.sym->name);
1060		break;
1061	case E_GEQ:
1062	case E_GTH:
1063		if (e->left.sym->name)
1064			fn(data, e->left.sym, e->left.sym->name);
1065		else
1066			fn(data, NULL, "<choice>");
1067		fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1068		fn(data, e->right.sym, e->right.sym->name);
1069		break;
1070	case E_UNEQUAL:
1071		if (e->left.sym->name)
1072			fn(data, e->left.sym, e->left.sym->name);
1073		else
1074			fn(data, NULL, "<choice>");
1075		fn(data, NULL, "!=");
1076		fn(data, e->right.sym, e->right.sym->name);
1077		break;
1078	case E_OR:
1079		expr_print(e->left.expr, fn, data, E_OR);
1080		fn(data, NULL, " || ");
1081		expr_print(e->right.expr, fn, data, E_OR);
1082		break;
1083	case E_AND:
1084		expr_print(e->left.expr, fn, data, E_AND);
1085		fn(data, NULL, " && ");
1086		expr_print(e->right.expr, fn, data, E_AND);
1087		break;
1088	case E_RANGE:
1089		fn(data, NULL, "[");
1090		fn(data, e->left.sym, e->left.sym->name);
1091		fn(data, NULL, " ");
1092		fn(data, e->right.sym, e->right.sym->name);
1093		fn(data, NULL, "]");
1094		break;
1095	default:
1096	  {
1097		char buf[32];
1098		sprintf(buf, "<unknown type %d>", e->type);
1099		fn(data, NULL, buf);
1100		break;
1101	  }
1102	}
1103	if (expr_compare_type(prevtoken, e->type) > 0)
1104		fn(data, NULL, ")");
1105}
1106
1107static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1108{
1109	xfwrite(str, strlen(str), 1, data);
1110}
1111
1112void expr_fprint(struct expr *e, FILE *out)
1113{
1114	expr_print(e, expr_print_file_helper, out, E_NONE);
1115}
1116
1117static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1118{
1119	struct gstr *gs = (struct gstr*)data;
1120	const char *sym_str = NULL;
1121
1122	if (sym)
1123		sym_str = sym_get_string_value(sym);
1124
1125	if (gs->max_width) {
1126		unsigned extra_length = strlen(str);
1127		const char *last_cr = strrchr(gs->s, '\n');
1128		unsigned last_line_length;
1129
1130		if (sym_str)
1131			extra_length += 4 + strlen(sym_str);
1132
1133		if (!last_cr)
1134			last_cr = gs->s;
1135
1136		last_line_length = strlen(gs->s) - (last_cr - gs->s);
1137
1138		if ((last_line_length + extra_length) > gs->max_width)
1139			str_append(gs, "\\\n");
1140	}
1141
1142	str_append(gs, str);
1143	if (sym && sym->type != S_UNKNOWN)
1144		str_printf(gs, " [=%s]", sym_str);
1145}
1146
1147void expr_gstr_print(const struct expr *e, struct gstr *gs)
1148{
1149	expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1150}
1151
1152/*
1153 * Transform the top level "||" tokens into newlines and prepend each
1154 * line with a minus. This makes expressions much easier to read.
1155 * Suitable for reverse dependency expressions.
1156 */
1157static void expr_print_revdep(struct expr *e,
1158			      void (*fn)(void *, struct symbol *, const char *),
1159			      void *data, tristate pr_type, const char **title)
1160{
1161	if (e->type == E_OR) {
1162		expr_print_revdep(e->left.expr, fn, data, pr_type, title);
1163		expr_print_revdep(e->right.expr, fn, data, pr_type, title);
1164	} else if (expr_calc_value(e) == pr_type) {
1165		if (*title) {
1166			fn(data, NULL, *title);
1167			*title = NULL;
1168		}
1169
1170		fn(data, NULL, "  - ");
1171		expr_print(e, fn, data, E_NONE);
1172		fn(data, NULL, "\n");
1173	}
1174}
1175
1176void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
1177			    tristate pr_type, const char *title)
1178{
1179	expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);
1180}