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