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