kconfig/expr.c
author "Yann E. MORIN" <yann.morin.1998@anciens.enib.fr>
Sat Feb 24 11:00:05 2007 +0000 (2007-02-24)
changeset 1 eeea35fbf182
child 943 1cca90ce0481
permissions -rw-r--r--
Add the full crosstool-NG sources to the new repository of its own.
You might just say: 'Yeah! crosstool-NG's got its own repo!".
Unfortunately, that's because the previous repo got damaged beyond repair and I had no backup.
That means I'm putting backups in place in the afternoon.
That also means we've lost history... :-(
     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 #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 }