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