xref: /linux/scripts/kconfig/expr.c (revision e6a901a00822659181c93c86d8bbc2a17779fddc) 
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  * bool FOO!=n => FOO
401  */
402 struct expr *expr_trans_bool(struct expr *e)
403 {
404 	if (!e)
405 		return NULL;
406 	switch (e->type) {
407 	case E_AND:
408 	case E_OR:
409 	case E_NOT:
410 		e->left.expr = expr_trans_bool(e->left.expr);
411 		e->right.expr = expr_trans_bool(e->right.expr);
412 		break;
413 	case E_UNEQUAL:
414 		// FOO!=n -> FOO
415 		if (e->left.sym->type == S_TRISTATE) {
416 			if (e->right.sym == &symbol_no) {
417 				e->type = E_SYMBOL;
418 				e->right.sym = NULL;
419 			}
420 		}
421 		break;
422 	default:
423 		;
424 	}
425 	return e;
426 }
427 
428 /*
429  * e1 || e2 -> ?
430  */
431 static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
432 {
433 	struct expr *tmp;
434 	struct symbol *sym1, *sym2;
435 
436 	if (expr_eq(e1, e2))
437 		return expr_copy(e1);
438 	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
439 		return NULL;
440 	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
441 		return NULL;
442 	if (e1->type == E_NOT) {
443 		tmp = e1->left.expr;
444 		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
445 			return NULL;
446 		sym1 = tmp->left.sym;
447 	} else
448 		sym1 = e1->left.sym;
449 	if (e2->type == E_NOT) {
450 		if (e2->left.expr->type != E_SYMBOL)
451 			return NULL;
452 		sym2 = e2->left.expr->left.sym;
453 	} else
454 		sym2 = e2->left.sym;
455 	if (sym1 != sym2)
456 		return NULL;
457 	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
458 		return NULL;
459 	if (sym1->type == S_TRISTATE) {
460 		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
461 		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
462 		     (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
463 			// (a='y') || (a='m') -> (a!='n')
464 			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
465 		}
466 		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
467 		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
468 		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
469 			// (a='y') || (a='n') -> (a!='m')
470 			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
471 		}
472 		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
473 		    ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
474 		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
475 			// (a='m') || (a='n') -> (a!='y')
476 			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
477 		}
478 	}
479 	if (sym1->type == S_BOOLEAN && sym1 == sym2) {
480 		if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
481 		    (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
482 			return expr_alloc_symbol(&symbol_yes);
483 	}
484 
485 	if (DEBUG_EXPR) {
486 		printf("optimize (");
487 		expr_fprint(e1, stdout);
488 		printf(") || (");
489 		expr_fprint(e2, stdout);
490 		printf(")?\n");
491 	}
492 	return NULL;
493 }
494 
495 static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
496 {
497 	struct expr *tmp;
498 	struct symbol *sym1, *sym2;
499 
500 	if (expr_eq(e1, e2))
501 		return expr_copy(e1);
502 	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
503 		return NULL;
504 	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
505 		return NULL;
506 	if (e1->type == E_NOT) {
507 		tmp = e1->left.expr;
508 		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
509 			return NULL;
510 		sym1 = tmp->left.sym;
511 	} else
512 		sym1 = e1->left.sym;
513 	if (e2->type == E_NOT) {
514 		if (e2->left.expr->type != E_SYMBOL)
515 			return NULL;
516 		sym2 = e2->left.expr->left.sym;
517 	} else
518 		sym2 = e2->left.sym;
519 	if (sym1 != sym2)
520 		return NULL;
521 	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
522 		return NULL;
523 
524 	if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
525 	    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
526 		// (a) && (a='y') -> (a='y')
527 		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
528 
529 	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
530 	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
531 		// (a) && (a!='n') -> (a)
532 		return expr_alloc_symbol(sym1);
533 
534 	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
535 	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
536 		// (a) && (a!='m') -> (a='y')
537 		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
538 
539 	if (sym1->type == S_TRISTATE) {
540 		if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
541 			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
542 			sym2 = e1->right.sym;
543 			if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
544 				return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
545 							     : expr_alloc_symbol(&symbol_no);
546 		}
547 		if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
548 			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
549 			sym2 = e2->right.sym;
550 			if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
551 				return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
552 							     : expr_alloc_symbol(&symbol_no);
553 		}
554 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
555 			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
556 			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
557 			// (a!='y') && (a!='n') -> (a='m')
558 			return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
559 
560 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
561 			   ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
562 			    (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
563 			// (a!='y') && (a!='m') -> (a='n')
564 			return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
565 
566 		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
567 			   ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
568 			    (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
569 			// (a!='m') && (a!='n') -> (a='m')
570 			return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
571 
572 		if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
573 		    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
574 		    (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
575 		    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
576 			return NULL;
577 	}
578 
579 	if (DEBUG_EXPR) {
580 		printf("optimize (");
581 		expr_fprint(e1, stdout);
582 		printf(") && (");
583 		expr_fprint(e2, stdout);
584 		printf(")?\n");
585 	}
586 	return NULL;
587 }
588 
589 /*
590  * expr_eliminate_dups() helper.
591  *
592  * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
593  * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
594  * against all other leaves to look for simplifications.
595  */
596 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
597 {
598 #define e1 (*ep1)
599 #define e2 (*ep2)
600 	struct expr *tmp;
601 
602 	/* Recurse down to leaves */
603 
604 	if (e1->type == type) {
605 		expr_eliminate_dups1(type, &e1->left.expr, &e2);
606 		expr_eliminate_dups1(type, &e1->right.expr, &e2);
607 		return;
608 	}
609 	if (e2->type == type) {
610 		expr_eliminate_dups1(type, &e1, &e2->left.expr);
611 		expr_eliminate_dups1(type, &e1, &e2->right.expr);
612 		return;
613 	}
614 
615 	/* e1 and e2 are leaves. Compare and process them. */
616 
617 	if (e1 == e2)
618 		return;
619 
620 	switch (e1->type) {
621 	case E_OR: case E_AND:
622 		expr_eliminate_dups1(e1->type, &e1, &e1);
623 	default:
624 		;
625 	}
626 
627 	switch (type) {
628 	case E_OR:
629 		tmp = expr_join_or(e1, e2);
630 		if (tmp) {
631 			expr_free(e1); expr_free(e2);
632 			e1 = expr_alloc_symbol(&symbol_no);
633 			e2 = tmp;
634 			trans_count++;
635 		}
636 		break;
637 	case E_AND:
638 		tmp = expr_join_and(e1, e2);
639 		if (tmp) {
640 			expr_free(e1); expr_free(e2);
641 			e1 = expr_alloc_symbol(&symbol_yes);
642 			e2 = tmp;
643 			trans_count++;
644 		}
645 		break;
646 	default:
647 		;
648 	}
649 #undef e1
650 #undef e2
651 }
652 
653 /*
654  * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
655  * operands.
656  *
657  * Example simplifications:
658  *
659  *	A || B || A    ->  A || B
660  *	A && B && A=y  ->  A=y && B
661  *
662  * Returns the deduplicated expression.
663  */
664 struct expr *expr_eliminate_dups(struct expr *e)
665 {
666 	int oldcount;
667 	if (!e)
668 		return e;
669 
670 	oldcount = trans_count;
671 	while (1) {
672 		trans_count = 0;
673 		switch (e->type) {
674 		case E_OR: case E_AND:
675 			expr_eliminate_dups1(e->type, &e, &e);
676 		default:
677 			;
678 		}
679 		if (!trans_count)
680 			/* No simplifications done in this pass. We're done */
681 			break;
682 		e = expr_eliminate_yn(e);
683 	}
684 	trans_count = oldcount;
685 	return e;
686 }
687 
688 /*
689  * Performs various simplifications involving logical operators and
690  * comparisons.
691  *
692  * Allocates and returns a new expression.
693  */
694 struct expr *expr_transform(struct expr *e)
695 {
696 	struct expr *tmp;
697 
698 	if (!e)
699 		return NULL;
700 	switch (e->type) {
701 	case E_EQUAL:
702 	case E_GEQ:
703 	case E_GTH:
704 	case E_LEQ:
705 	case E_LTH:
706 	case E_UNEQUAL:
707 	case E_SYMBOL:
708 	case E_LIST:
709 		break;
710 	default:
711 		e->left.expr = expr_transform(e->left.expr);
712 		e->right.expr = expr_transform(e->right.expr);
713 	}
714 
715 	switch (e->type) {
716 	case E_EQUAL:
717 		if (e->left.sym->type != S_BOOLEAN)
718 			break;
719 		if (e->right.sym == &symbol_no) {
720 			e->type = E_NOT;
721 			e->left.expr = expr_alloc_symbol(e->left.sym);
722 			e->right.sym = NULL;
723 			break;
724 		}
725 		if (e->right.sym == &symbol_mod) {
726 			printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
727 			e->type = E_SYMBOL;
728 			e->left.sym = &symbol_no;
729 			e->right.sym = NULL;
730 			break;
731 		}
732 		if (e->right.sym == &symbol_yes) {
733 			e->type = E_SYMBOL;
734 			e->right.sym = NULL;
735 			break;
736 		}
737 		break;
738 	case E_UNEQUAL:
739 		if (e->left.sym->type != S_BOOLEAN)
740 			break;
741 		if (e->right.sym == &symbol_no) {
742 			e->type = E_SYMBOL;
743 			e->right.sym = NULL;
744 			break;
745 		}
746 		if (e->right.sym == &symbol_mod) {
747 			printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
748 			e->type = E_SYMBOL;
749 			e->left.sym = &symbol_yes;
750 			e->right.sym = NULL;
751 			break;
752 		}
753 		if (e->right.sym == &symbol_yes) {
754 			e->type = E_NOT;
755 			e->left.expr = expr_alloc_symbol(e->left.sym);
756 			e->right.sym = NULL;
757 			break;
758 		}
759 		break;
760 	case E_NOT:
761 		switch (e->left.expr->type) {
762 		case E_NOT:
763 			// !!a -> a
764 			tmp = e->left.expr->left.expr;
765 			free(e->left.expr);
766 			free(e);
767 			e = tmp;
768 			e = expr_transform(e);
769 			break;
770 		case E_EQUAL:
771 		case E_UNEQUAL:
772 			// !a='x' -> a!='x'
773 			tmp = e->left.expr;
774 			free(e);
775 			e = tmp;
776 			e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
777 			break;
778 		case E_LEQ:
779 		case E_GEQ:
780 			// !a<='x' -> a>'x'
781 			tmp = e->left.expr;
782 			free(e);
783 			e = tmp;
784 			e->type = e->type == E_LEQ ? E_GTH : E_LTH;
785 			break;
786 		case E_LTH:
787 		case E_GTH:
788 			// !a<'x' -> a>='x'
789 			tmp = e->left.expr;
790 			free(e);
791 			e = tmp;
792 			e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
793 			break;
794 		case E_OR:
795 			// !(a || b) -> !a && !b
796 			tmp = e->left.expr;
797 			e->type = E_AND;
798 			e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
799 			tmp->type = E_NOT;
800 			tmp->right.expr = NULL;
801 			e = expr_transform(e);
802 			break;
803 		case E_AND:
804 			// !(a && b) -> !a || !b
805 			tmp = e->left.expr;
806 			e->type = E_OR;
807 			e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
808 			tmp->type = E_NOT;
809 			tmp->right.expr = NULL;
810 			e = expr_transform(e);
811 			break;
812 		case E_SYMBOL:
813 			if (e->left.expr->left.sym == &symbol_yes) {
814 				// !'y' -> 'n'
815 				tmp = e->left.expr;
816 				free(e);
817 				e = tmp;
818 				e->type = E_SYMBOL;
819 				e->left.sym = &symbol_no;
820 				break;
821 			}
822 			if (e->left.expr->left.sym == &symbol_mod) {
823 				// !'m' -> 'm'
824 				tmp = e->left.expr;
825 				free(e);
826 				e = tmp;
827 				e->type = E_SYMBOL;
828 				e->left.sym = &symbol_mod;
829 				break;
830 			}
831 			if (e->left.expr->left.sym == &symbol_no) {
832 				// !'n' -> 'y'
833 				tmp = e->left.expr;
834 				free(e);
835 				e = tmp;
836 				e->type = E_SYMBOL;
837 				e->left.sym = &symbol_yes;
838 				break;
839 			}
840 			break;
841 		default:
842 			;
843 		}
844 		break;
845 	default:
846 		;
847 	}
848 	return e;
849 }
850 
851 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
852 {
853 	if (!dep)
854 		return 0;
855 
856 	switch (dep->type) {
857 	case E_AND:
858 	case E_OR:
859 		return expr_contains_symbol(dep->left.expr, sym) ||
860 		       expr_contains_symbol(dep->right.expr, sym);
861 	case E_SYMBOL:
862 		return dep->left.sym == sym;
863 	case E_EQUAL:
864 	case E_GEQ:
865 	case E_GTH:
866 	case E_LEQ:
867 	case E_LTH:
868 	case E_UNEQUAL:
869 		return dep->left.sym == sym ||
870 		       dep->right.sym == sym;
871 	case E_NOT:
872 		return expr_contains_symbol(dep->left.expr, sym);
873 	default:
874 		;
875 	}
876 	return 0;
877 }
878 
879 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
880 {
881 	if (!dep)
882 		return false;
883 
884 	switch (dep->type) {
885 	case E_AND:
886 		return expr_depends_symbol(dep->left.expr, sym) ||
887 		       expr_depends_symbol(dep->right.expr, sym);
888 	case E_SYMBOL:
889 		return dep->left.sym == sym;
890 	case E_EQUAL:
891 		if (dep->left.sym == sym) {
892 			if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
893 				return true;
894 		}
895 		break;
896 	case E_UNEQUAL:
897 		if (dep->left.sym == sym) {
898 			if (dep->right.sym == &symbol_no)
899 				return true;
900 		}
901 		break;
902 	default:
903 		;
904 	}
905  	return false;
906 }
907 
908 /*
909  * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
910  * expression 'e'.
911  *
912  * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
913  *
914  *	A              ->  A!=n
915  *	!A             ->  A=n
916  *	A && B         ->  !(A=n || B=n)
917  *	A || B         ->  !(A=n && B=n)
918  *	A && (B || C)  ->  !(A=n || (B=n && C=n))
919  *
920  * Allocates and returns a new expression.
921  */
922 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
923 {
924 	struct expr *e1, *e2;
925 
926 	if (!e) {
927 		e = expr_alloc_symbol(sym);
928 		if (type == E_UNEQUAL)
929 			e = expr_alloc_one(E_NOT, e);
930 		return e;
931 	}
932 	switch (e->type) {
933 	case E_AND:
934 		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
935 		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
936 		if (sym == &symbol_yes)
937 			e = expr_alloc_two(E_AND, e1, e2);
938 		if (sym == &symbol_no)
939 			e = expr_alloc_two(E_OR, e1, e2);
940 		if (type == E_UNEQUAL)
941 			e = expr_alloc_one(E_NOT, e);
942 		return e;
943 	case E_OR:
944 		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
945 		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
946 		if (sym == &symbol_yes)
947 			e = expr_alloc_two(E_OR, e1, e2);
948 		if (sym == &symbol_no)
949 			e = expr_alloc_two(E_AND, e1, e2);
950 		if (type == E_UNEQUAL)
951 			e = expr_alloc_one(E_NOT, e);
952 		return e;
953 	case E_NOT:
954 		return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
955 	case E_UNEQUAL:
956 	case E_LTH:
957 	case E_LEQ:
958 	case E_GTH:
959 	case E_GEQ:
960 	case E_EQUAL:
961 		if (type == E_EQUAL) {
962 			if (sym == &symbol_yes)
963 				return expr_copy(e);
964 			if (sym == &symbol_mod)
965 				return expr_alloc_symbol(&symbol_no);
966 			if (sym == &symbol_no)
967 				return expr_alloc_one(E_NOT, expr_copy(e));
968 		} else {
969 			if (sym == &symbol_yes)
970 				return expr_alloc_one(E_NOT, expr_copy(e));
971 			if (sym == &symbol_mod)
972 				return expr_alloc_symbol(&symbol_yes);
973 			if (sym == &symbol_no)
974 				return expr_copy(e);
975 		}
976 		break;
977 	case E_SYMBOL:
978 		return expr_alloc_comp(type, e->left.sym, sym);
979 	case E_LIST:
980 	case E_RANGE:
981 	case E_NONE:
982 		/* panic */;
983 	}
984 	return NULL;
985 }
986 
987 enum string_value_kind {
988 	k_string,
989 	k_signed,
990 	k_unsigned,
991 };
992 
993 union string_value {
994 	unsigned long long u;
995 	signed long long s;
996 };
997 
998 static enum string_value_kind expr_parse_string(const char *str,
999 						enum symbol_type type,
1000 						union string_value *val)
1001 {
1002 	char *tail;
1003 	enum string_value_kind kind;
1004 
1005 	errno = 0;
1006 	switch (type) {
1007 	case S_BOOLEAN:
1008 	case S_TRISTATE:
1009 		val->s = !strcmp(str, "n") ? 0 :
1010 			 !strcmp(str, "m") ? 1 :
1011 			 !strcmp(str, "y") ? 2 : -1;
1012 		return k_signed;
1013 	case S_INT:
1014 		val->s = strtoll(str, &tail, 10);
1015 		kind = k_signed;
1016 		break;
1017 	case S_HEX:
1018 		val->u = strtoull(str, &tail, 16);
1019 		kind = k_unsigned;
1020 		break;
1021 	default:
1022 		val->s = strtoll(str, &tail, 0);
1023 		kind = k_signed;
1024 		break;
1025 	}
1026 	return !errno && !*tail && tail > str && isxdigit(tail[-1])
1027 	       ? kind : k_string;
1028 }
1029 
1030 tristate expr_calc_value(struct expr *e)
1031 {
1032 	tristate val1, val2;
1033 	const char *str1, *str2;
1034 	enum string_value_kind k1 = k_string, k2 = k_string;
1035 	union string_value lval = {}, rval = {};
1036 	int res;
1037 
1038 	if (!e)
1039 		return yes;
1040 
1041 	switch (e->type) {
1042 	case E_SYMBOL:
1043 		sym_calc_value(e->left.sym);
1044 		return e->left.sym->curr.tri;
1045 	case E_AND:
1046 		val1 = expr_calc_value(e->left.expr);
1047 		val2 = expr_calc_value(e->right.expr);
1048 		return EXPR_AND(val1, val2);
1049 	case E_OR:
1050 		val1 = expr_calc_value(e->left.expr);
1051 		val2 = expr_calc_value(e->right.expr);
1052 		return EXPR_OR(val1, val2);
1053 	case E_NOT:
1054 		val1 = expr_calc_value(e->left.expr);
1055 		return EXPR_NOT(val1);
1056 	case E_EQUAL:
1057 	case E_GEQ:
1058 	case E_GTH:
1059 	case E_LEQ:
1060 	case E_LTH:
1061 	case E_UNEQUAL:
1062 		break;
1063 	default:
1064 		printf("expr_calc_value: %d?\n", e->type);
1065 		return no;
1066 	}
1067 
1068 	sym_calc_value(e->left.sym);
1069 	sym_calc_value(e->right.sym);
1070 	str1 = sym_get_string_value(e->left.sym);
1071 	str2 = sym_get_string_value(e->right.sym);
1072 
1073 	if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
1074 		k1 = expr_parse_string(str1, e->left.sym->type, &lval);
1075 		k2 = expr_parse_string(str2, e->right.sym->type, &rval);
1076 	}
1077 
1078 	if (k1 == k_string || k2 == k_string)
1079 		res = strcmp(str1, str2);
1080 	else if (k1 == k_unsigned || k2 == k_unsigned)
1081 		res = (lval.u > rval.u) - (lval.u < rval.u);
1082 	else /* if (k1 == k_signed && k2 == k_signed) */
1083 		res = (lval.s > rval.s) - (lval.s < rval.s);
1084 
1085 	switch(e->type) {
1086 	case E_EQUAL:
1087 		return res ? no : yes;
1088 	case E_GEQ:
1089 		return res >= 0 ? yes : no;
1090 	case E_GTH:
1091 		return res > 0 ? yes : no;
1092 	case E_LEQ:
1093 		return res <= 0 ? yes : no;
1094 	case E_LTH:
1095 		return res < 0 ? yes : no;
1096 	case E_UNEQUAL:
1097 		return res ? yes : no;
1098 	default:
1099 		printf("expr_calc_value: relation %d?\n", e->type);
1100 		return no;
1101 	}
1102 }
1103 
1104 static int expr_compare_type(enum expr_type t1, enum expr_type t2)
1105 {
1106 	if (t1 == t2)
1107 		return 0;
1108 	switch (t1) {
1109 	case E_LEQ:
1110 	case E_LTH:
1111 	case E_GEQ:
1112 	case E_GTH:
1113 		if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1114 			return 1;
1115 	case E_EQUAL:
1116 	case E_UNEQUAL:
1117 		if (t2 == E_NOT)
1118 			return 1;
1119 	case E_NOT:
1120 		if (t2 == E_AND)
1121 			return 1;
1122 	case E_AND:
1123 		if (t2 == E_OR)
1124 			return 1;
1125 	case E_OR:
1126 		if (t2 == E_LIST)
1127 			return 1;
1128 	case E_LIST:
1129 		if (t2 == 0)
1130 			return 1;
1131 	default:
1132 		return -1;
1133 	}
1134 	return 0;
1135 }
1136 
1137 void expr_print(struct expr *e,
1138 		void (*fn)(void *, struct symbol *, const char *),
1139 		void *data, int prevtoken)
1140 {
1141 	if (!e) {
1142 		fn(data, NULL, "y");
1143 		return;
1144 	}
1145 
1146 	if (expr_compare_type(prevtoken, e->type) > 0)
1147 		fn(data, NULL, "(");
1148 	switch (e->type) {
1149 	case E_SYMBOL:
1150 		if (e->left.sym->name)
1151 			fn(data, e->left.sym, e->left.sym->name);
1152 		else
1153 			fn(data, NULL, "<choice>");
1154 		break;
1155 	case E_NOT:
1156 		fn(data, NULL, "!");
1157 		expr_print(e->left.expr, fn, data, E_NOT);
1158 		break;
1159 	case E_EQUAL:
1160 		if (e->left.sym->name)
1161 			fn(data, e->left.sym, e->left.sym->name);
1162 		else
1163 			fn(data, NULL, "<choice>");
1164 		fn(data, NULL, "=");
1165 		fn(data, e->right.sym, e->right.sym->name);
1166 		break;
1167 	case E_LEQ:
1168 	case E_LTH:
1169 		if (e->left.sym->name)
1170 			fn(data, e->left.sym, e->left.sym->name);
1171 		else
1172 			fn(data, NULL, "<choice>");
1173 		fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1174 		fn(data, e->right.sym, e->right.sym->name);
1175 		break;
1176 	case E_GEQ:
1177 	case E_GTH:
1178 		if (e->left.sym->name)
1179 			fn(data, e->left.sym, e->left.sym->name);
1180 		else
1181 			fn(data, NULL, "<choice>");
1182 		fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1183 		fn(data, e->right.sym, e->right.sym->name);
1184 		break;
1185 	case E_UNEQUAL:
1186 		if (e->left.sym->name)
1187 			fn(data, e->left.sym, e->left.sym->name);
1188 		else
1189 			fn(data, NULL, "<choice>");
1190 		fn(data, NULL, "!=");
1191 		fn(data, e->right.sym, e->right.sym->name);
1192 		break;
1193 	case E_OR:
1194 		expr_print(e->left.expr, fn, data, E_OR);
1195 		fn(data, NULL, " || ");
1196 		expr_print(e->right.expr, fn, data, E_OR);
1197 		break;
1198 	case E_AND:
1199 		expr_print(e->left.expr, fn, data, E_AND);
1200 		fn(data, NULL, " && ");
1201 		expr_print(e->right.expr, fn, data, E_AND);
1202 		break;
1203 	case E_LIST:
1204 		fn(data, e->right.sym, e->right.sym->name);
1205 		if (e->left.expr) {
1206 			fn(data, NULL, " ^ ");
1207 			expr_print(e->left.expr, fn, data, E_LIST);
1208 		}
1209 		break;
1210 	case E_RANGE:
1211 		fn(data, NULL, "[");
1212 		fn(data, e->left.sym, e->left.sym->name);
1213 		fn(data, NULL, " ");
1214 		fn(data, e->right.sym, e->right.sym->name);
1215 		fn(data, NULL, "]");
1216 		break;
1217 	default:
1218 	  {
1219 		char buf[32];
1220 		sprintf(buf, "<unknown type %d>", e->type);
1221 		fn(data, NULL, buf);
1222 		break;
1223 	  }
1224 	}
1225 	if (expr_compare_type(prevtoken, e->type) > 0)
1226 		fn(data, NULL, ")");
1227 }
1228 
1229 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1230 {
1231 	xfwrite(str, strlen(str), 1, data);
1232 }
1233 
1234 void expr_fprint(struct expr *e, FILE *out)
1235 {
1236 	expr_print(e, expr_print_file_helper, out, E_NONE);
1237 }
1238 
1239 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1240 {
1241 	struct gstr *gs = (struct gstr*)data;
1242 	const char *sym_str = NULL;
1243 
1244 	if (sym)
1245 		sym_str = sym_get_string_value(sym);
1246 
1247 	if (gs->max_width) {
1248 		unsigned extra_length = strlen(str);
1249 		const char *last_cr = strrchr(gs->s, '\n');
1250 		unsigned last_line_length;
1251 
1252 		if (sym_str)
1253 			extra_length += 4 + strlen(sym_str);
1254 
1255 		if (!last_cr)
1256 			last_cr = gs->s;
1257 
1258 		last_line_length = strlen(gs->s) - (last_cr - gs->s);
1259 
1260 		if ((last_line_length + extra_length) > gs->max_width)
1261 			str_append(gs, "\\\n");
1262 	}
1263 
1264 	str_append(gs, str);
1265 	if (sym && sym->type != S_UNKNOWN)
1266 		str_printf(gs, " [=%s]", sym_str);
1267 }
1268 
1269 void expr_gstr_print(struct expr *e, struct gstr *gs)
1270 {
1271 	expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1272 }
1273 
1274 /*
1275  * Transform the top level "||" tokens into newlines and prepend each
1276  * line with a minus. This makes expressions much easier to read.
1277  * Suitable for reverse dependency expressions.
1278  */
1279 static void expr_print_revdep(struct expr *e,
1280 			      void (*fn)(void *, struct symbol *, const char *),
1281 			      void *data, tristate pr_type, const char **title)
1282 {
1283 	if (e->type == E_OR) {
1284 		expr_print_revdep(e->left.expr, fn, data, pr_type, title);
1285 		expr_print_revdep(e->right.expr, fn, data, pr_type, title);
1286 	} else if (expr_calc_value(e) == pr_type) {
1287 		if (*title) {
1288 			fn(data, NULL, *title);
1289 			*title = NULL;
1290 		}
1291 
1292 		fn(data, NULL, "  - ");
1293 		expr_print(e, fn, data, E_NONE);
1294 		fn(data, NULL, "\n");
1295 	}
1296 }
1297 
1298 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
1299 			    tristate pr_type, const char *title)
1300 {
1301 	expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);
1302 }
1303