xref: /openbmc/linux/scripts/kconfig/expr.c (revision 2c684d89) 
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 		return k_string;
897 	case S_INT:
898 		val->s = strtoll(str, &tail, 10);
899 		kind = k_signed;
900 		break;
901 	case S_HEX:
902 		val->u = strtoull(str, &tail, 16);
903 		kind = k_unsigned;
904 		break;
905 	case S_STRING:
906 	case S_UNKNOWN:
907 		val->s = strtoll(str, &tail, 0);
908 		kind = k_signed;
909 		break;
910 	default:
911 		return k_invalid;
912 	}
913 	return !errno && !*tail && tail > str && isxdigit(tail[-1])
914 	       ? kind : k_string;
915 }
916 
917 tristate expr_calc_value(struct expr *e)
918 {
919 	tristate val1, val2;
920 	const char *str1, *str2;
921 	enum string_value_kind k1 = k_string, k2 = k_string;
922 	union string_value lval = {}, rval = {};
923 	int res;
924 
925 	if (!e)
926 		return yes;
927 
928 	switch (e->type) {
929 	case E_SYMBOL:
930 		sym_calc_value(e->left.sym);
931 		return e->left.sym->curr.tri;
932 	case E_AND:
933 		val1 = expr_calc_value(e->left.expr);
934 		val2 = expr_calc_value(e->right.expr);
935 		return EXPR_AND(val1, val2);
936 	case E_OR:
937 		val1 = expr_calc_value(e->left.expr);
938 		val2 = expr_calc_value(e->right.expr);
939 		return EXPR_OR(val1, val2);
940 	case E_NOT:
941 		val1 = expr_calc_value(e->left.expr);
942 		return EXPR_NOT(val1);
943 	case E_EQUAL:
944 	case E_GEQ:
945 	case E_GTH:
946 	case E_LEQ:
947 	case E_LTH:
948 	case E_UNEQUAL:
949 		break;
950 	default:
951 		printf("expr_calc_value: %d?\n", e->type);
952 		return no;
953 	}
954 
955 	sym_calc_value(e->left.sym);
956 	sym_calc_value(e->right.sym);
957 	str1 = sym_get_string_value(e->left.sym);
958 	str2 = sym_get_string_value(e->right.sym);
959 
960 	if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
961 		k1 = expr_parse_string(str1, e->left.sym->type, &lval);
962 		k2 = expr_parse_string(str2, e->right.sym->type, &rval);
963 	}
964 
965 	if (k1 == k_string || k2 == k_string)
966 		res = strcmp(str1, str2);
967 	else if (k1 == k_invalid || k2 == k_invalid) {
968 		if (e->type != E_EQUAL && e->type != E_UNEQUAL) {
969 			printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2);
970 			return no;
971 		}
972 		res = strcmp(str1, str2);
973 	} else if (k1 == k_unsigned || k2 == k_unsigned)
974 		res = (lval.u > rval.u) - (lval.u < rval.u);
975 	else /* if (k1 == k_signed && k2 == k_signed) */
976 		res = (lval.s > rval.s) - (lval.s < rval.s);
977 
978 	switch(e->type) {
979 	case E_EQUAL:
980 		return res ? no : yes;
981 	case E_GEQ:
982 		return res >= 0 ? yes : no;
983 	case E_GTH:
984 		return res > 0 ? yes : no;
985 	case E_LEQ:
986 		return res <= 0 ? yes : no;
987 	case E_LTH:
988 		return res < 0 ? yes : no;
989 	case E_UNEQUAL:
990 		return res ? yes : no;
991 	default:
992 		printf("expr_calc_value: relation %d?\n", e->type);
993 		return no;
994 	}
995 }
996 
997 static int expr_compare_type(enum expr_type t1, enum expr_type t2)
998 {
999 	if (t1 == t2)
1000 		return 0;
1001 	switch (t1) {
1002 	case E_LEQ:
1003 	case E_LTH:
1004 	case E_GEQ:
1005 	case E_GTH:
1006 		if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1007 			return 1;
1008 	case E_EQUAL:
1009 	case E_UNEQUAL:
1010 		if (t2 == E_NOT)
1011 			return 1;
1012 	case E_NOT:
1013 		if (t2 == E_AND)
1014 			return 1;
1015 	case E_AND:
1016 		if (t2 == E_OR)
1017 			return 1;
1018 	case E_OR:
1019 		if (t2 == E_LIST)
1020 			return 1;
1021 	case E_LIST:
1022 		if (t2 == 0)
1023 			return 1;
1024 	default:
1025 		return -1;
1026 	}
1027 	printf("[%dgt%d?]", t1, t2);
1028 	return 0;
1029 }
1030 
1031 static inline struct expr *
1032 expr_get_leftmost_symbol(const struct expr *e)
1033 {
1034 
1035 	if (e == NULL)
1036 		return NULL;
1037 
1038 	while (e->type != E_SYMBOL)
1039 		e = e->left.expr;
1040 
1041 	return expr_copy(e);
1042 }
1043 
1044 /*
1045  * Given expression `e1' and `e2', returns the leaf of the longest
1046  * sub-expression of `e1' not containing 'e2.
1047  */
1048 struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
1049 {
1050 	struct expr *ret;
1051 
1052 	switch (e1->type) {
1053 	case E_OR:
1054 		return expr_alloc_and(
1055 		    expr_simplify_unmet_dep(e1->left.expr, e2),
1056 		    expr_simplify_unmet_dep(e1->right.expr, e2));
1057 	case E_AND: {
1058 		struct expr *e;
1059 		e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
1060 		e = expr_eliminate_dups(e);
1061 		ret = (!expr_eq(e, e1)) ? e1 : NULL;
1062 		expr_free(e);
1063 		break;
1064 		}
1065 	default:
1066 		ret = e1;
1067 		break;
1068 	}
1069 
1070 	return expr_get_leftmost_symbol(ret);
1071 }
1072 
1073 void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1074 {
1075 	if (!e) {
1076 		fn(data, NULL, "y");
1077 		return;
1078 	}
1079 
1080 	if (expr_compare_type(prevtoken, e->type) > 0)
1081 		fn(data, NULL, "(");
1082 	switch (e->type) {
1083 	case E_SYMBOL:
1084 		if (e->left.sym->name)
1085 			fn(data, e->left.sym, e->left.sym->name);
1086 		else
1087 			fn(data, NULL, "<choice>");
1088 		break;
1089 	case E_NOT:
1090 		fn(data, NULL, "!");
1091 		expr_print(e->left.expr, fn, data, E_NOT);
1092 		break;
1093 	case E_EQUAL:
1094 		if (e->left.sym->name)
1095 			fn(data, e->left.sym, e->left.sym->name);
1096 		else
1097 			fn(data, NULL, "<choice>");
1098 		fn(data, NULL, "=");
1099 		fn(data, e->right.sym, e->right.sym->name);
1100 		break;
1101 	case E_LEQ:
1102 	case E_LTH:
1103 		if (e->left.sym->name)
1104 			fn(data, e->left.sym, e->left.sym->name);
1105 		else
1106 			fn(data, NULL, "<choice>");
1107 		fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1108 		fn(data, e->right.sym, e->right.sym->name);
1109 		break;
1110 	case E_GEQ:
1111 	case E_GTH:
1112 		if (e->left.sym->name)
1113 			fn(data, e->left.sym, e->left.sym->name);
1114 		else
1115 			fn(data, NULL, "<choice>");
1116 		fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1117 		fn(data, e->right.sym, e->right.sym->name);
1118 		break;
1119 	case E_UNEQUAL:
1120 		if (e->left.sym->name)
1121 			fn(data, e->left.sym, e->left.sym->name);
1122 		else
1123 			fn(data, NULL, "<choice>");
1124 		fn(data, NULL, "!=");
1125 		fn(data, e->right.sym, e->right.sym->name);
1126 		break;
1127 	case E_OR:
1128 		expr_print(e->left.expr, fn, data, E_OR);
1129 		fn(data, NULL, " || ");
1130 		expr_print(e->right.expr, fn, data, E_OR);
1131 		break;
1132 	case E_AND:
1133 		expr_print(e->left.expr, fn, data, E_AND);
1134 		fn(data, NULL, " && ");
1135 		expr_print(e->right.expr, fn, data, E_AND);
1136 		break;
1137 	case E_LIST:
1138 		fn(data, e->right.sym, e->right.sym->name);
1139 		if (e->left.expr) {
1140 			fn(data, NULL, " ^ ");
1141 			expr_print(e->left.expr, fn, data, E_LIST);
1142 		}
1143 		break;
1144 	case E_RANGE:
1145 		fn(data, NULL, "[");
1146 		fn(data, e->left.sym, e->left.sym->name);
1147 		fn(data, NULL, " ");
1148 		fn(data, e->right.sym, e->right.sym->name);
1149 		fn(data, NULL, "]");
1150 		break;
1151 	default:
1152 	  {
1153 		char buf[32];
1154 		sprintf(buf, "<unknown type %d>", e->type);
1155 		fn(data, NULL, buf);
1156 		break;
1157 	  }
1158 	}
1159 	if (expr_compare_type(prevtoken, e->type) > 0)
1160 		fn(data, NULL, ")");
1161 }
1162 
1163 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1164 {
1165 	xfwrite(str, strlen(str), 1, data);
1166 }
1167 
1168 void expr_fprint(struct expr *e, FILE *out)
1169 {
1170 	expr_print(e, expr_print_file_helper, out, E_NONE);
1171 }
1172 
1173 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1174 {
1175 	struct gstr *gs = (struct gstr*)data;
1176 	const char *sym_str = NULL;
1177 
1178 	if (sym)
1179 		sym_str = sym_get_string_value(sym);
1180 
1181 	if (gs->max_width) {
1182 		unsigned extra_length = strlen(str);
1183 		const char *last_cr = strrchr(gs->s, '\n');
1184 		unsigned last_line_length;
1185 
1186 		if (sym_str)
1187 			extra_length += 4 + strlen(sym_str);
1188 
1189 		if (!last_cr)
1190 			last_cr = gs->s;
1191 
1192 		last_line_length = strlen(gs->s) - (last_cr - gs->s);
1193 
1194 		if ((last_line_length + extra_length) > gs->max_width)
1195 			str_append(gs, "\\\n");
1196 	}
1197 
1198 	str_append(gs, str);
1199 	if (sym && sym->type != S_UNKNOWN)
1200 		str_printf(gs, " [=%s]", sym_str);
1201 }
1202 
1203 void expr_gstr_print(struct expr *e, struct gstr *gs)
1204 {
1205 	expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1206 }
1207