xref: /linux/scripts/kconfig/expr.c (revision d39d0ed196aa1685bb24771e92f78633c66ac9cb) 
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_LIST:
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_LIST:
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 static 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 static 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_LIST:
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_LIST:
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 EXPR_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 EXPR_OR(val1, val2);
963 	case E_NOT:
964 		val1 = expr_calc_value(e->left.expr);
965 		return EXPR_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_LIST)
1004 			return 1;
1005 	case E_LIST:
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 		if (e->left.sym->name)
1038 			fn(data, e->left.sym, e->left.sym->name);
1039 		else
1040 			fn(data, NULL, "<choice>");
1041 		fn(data, NULL, "=");
1042 		fn(data, e->right.sym, e->right.sym->name);
1043 		break;
1044 	case E_UNEQUAL:
1045 		if (e->left.sym->name)
1046 			fn(data, e->left.sym, e->left.sym->name);
1047 		else
1048 			fn(data, NULL, "<choice>");
1049 		fn(data, NULL, "!=");
1050 		fn(data, e->right.sym, e->right.sym->name);
1051 		break;
1052 	case E_OR:
1053 		expr_print(e->left.expr, fn, data, E_OR);
1054 		fn(data, NULL, " || ");
1055 		expr_print(e->right.expr, fn, data, E_OR);
1056 		break;
1057 	case E_AND:
1058 		expr_print(e->left.expr, fn, data, E_AND);
1059 		fn(data, NULL, " && ");
1060 		expr_print(e->right.expr, fn, data, E_AND);
1061 		break;
1062 	case E_LIST:
1063 		fn(data, e->right.sym, e->right.sym->name);
1064 		if (e->left.expr) {
1065 			fn(data, NULL, " ^ ");
1066 			expr_print(e->left.expr, fn, data, E_LIST);
1067 		}
1068 		break;
1069 	case E_RANGE:
1070 		fn(data, NULL, "[");
1071 		fn(data, e->left.sym, e->left.sym->name);
1072 		fn(data, NULL, " ");
1073 		fn(data, e->right.sym, e->right.sym->name);
1074 		fn(data, NULL, "]");
1075 		break;
1076 	default:
1077 	  {
1078 		char buf[32];
1079 		sprintf(buf, "<unknown type %d>", e->type);
1080 		fn(data, NULL, buf);
1081 		break;
1082 	  }
1083 	}
1084 	if (expr_compare_type(prevtoken, e->type) > 0)
1085 		fn(data, NULL, ")");
1086 }
1087 
1088 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1089 {
1090 	xfwrite(str, strlen(str), 1, data);
1091 }
1092 
1093 void expr_fprint(struct expr *e, FILE *out)
1094 {
1095 	expr_print(e, expr_print_file_helper, out, E_NONE);
1096 }
1097 
1098 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1099 {
1100 	struct gstr *gs = (struct gstr*)data;
1101 	const char *sym_str = NULL;
1102 
1103 	if (sym)
1104 		sym_str = sym_get_string_value(sym);
1105 
1106 	if (gs->max_width) {
1107 		unsigned extra_length = strlen(str);
1108 		const char *last_cr = strrchr(gs->s, '\n');
1109 		unsigned last_line_length;
1110 
1111 		if (sym_str)
1112 			extra_length += 4 + strlen(sym_str);
1113 
1114 		if (!last_cr)
1115 			last_cr = gs->s;
1116 
1117 		last_line_length = strlen(gs->s) - (last_cr - gs->s);
1118 
1119 		if ((last_line_length + extra_length) > gs->max_width)
1120 			str_append(gs, "\\\n");
1121 	}
1122 
1123 	str_append(gs, str);
1124 	if (sym && sym->type != S_UNKNOWN)
1125 		str_printf(gs, " [=%s]", sym_str);
1126 }
1127 
1128 void expr_gstr_print(struct expr *e, struct gstr *gs)
1129 {
1130 	expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1131 }
1132