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