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