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