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