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