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