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