projects/linux·blob master · refs

1213 lines · 29.4 KiB

1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2002 Roman Zippel <[email protected]>
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
19HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE);
20
21static 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 */
33static 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
57struct expr *expr_alloc_symbol(struct symbol *sym)
58{
59 return expr_lookup(E_SYMBOL, sym, NULL);
60}
61
62struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
63{
64 return expr_lookup(type, ce, NULL);
65}
66
67struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
68{
69 return expr_lookup(type, e1, e2);
70}
71
72struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
73{
74 return expr_lookup(type, s1, s2);
75}
76
77struct 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
84struct 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
91static 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 */
101static 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 */
179void 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 */
207bool 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 */
267static 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 */
313static 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
378static 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 */
479static 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 */
537struct 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 */
593struct 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
713bool 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
741/*
742 * Check if the expression references 'sym' in a way that is satisfiable
743 * with 'sym' disabled, e.g.'sym!=y'.
744 *
745 * Expects that expr_transform() was already called on 'expr'.
746 */
747bool expr_contains_symbol_negated(struct expr *dep, struct symbol *sym)
748{
749 if (!dep)
750 return false;
751
752 switch (dep->type) {
753 case E_AND:
754 case E_OR:
755 return expr_contains_symbol_negated(dep->left.expr, sym) ||
756 expr_contains_symbol_negated(dep->right.expr, sym);
757 case E_NOT:
758 return dep->left.expr->type == E_SYMBOL &&
759 dep->left.expr->left.sym == sym;
760 case E_EQUAL:
761 /* sym=n */
762 return dep->left.sym == sym && dep->right.sym == &symbol_no;
763 case E_UNEQUAL:
764 /* sym!=y, sym!=m */
765 return dep->left.sym == sym &&
766 (dep->right.sym == &symbol_yes ||
767 dep->right.sym == &symbol_mod);
768 default:
769 break;
770 }
771 return false;
772}
773
774bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
775{
776 if (!dep)
777 return false;
778
779 switch (dep->type) {
780 case E_AND:
781 return expr_depends_symbol(dep->left.expr, sym) ||
782 expr_depends_symbol(dep->right.expr, sym);
783 case E_SYMBOL:
784 return dep->left.sym == sym;
785 case E_EQUAL:
786 if (dep->left.sym == sym) {
787 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
788 return true;
789 }
790 break;
791 case E_UNEQUAL:
792 if (dep->left.sym == sym) {
793 if (dep->right.sym == &symbol_no)
794 return true;
795 }
796 break;
797 default:
798 ;
799 }
800 return false;
801}
802
803/*
804 * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
805 * expression 'e'.
806 *
807 * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
808 *
809 * A -> A!=n
810 * !A -> A=n
811 * A && B -> !(A=n || B=n)
812 * A || B -> !(A=n && B=n)
813 * A && (B || C) -> !(A=n || (B=n && C=n))
814 *
815 * Allocates and returns a new expression.
816 */
817struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
818{
819 struct expr *e1, *e2;
820
821 if (!e) {
822 e = expr_alloc_symbol(sym);
823 if (type == E_UNEQUAL)
824 e = expr_alloc_one(E_NOT, e);
825 return e;
826 }
827 switch (e->type) {
828 case E_AND:
829 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
830 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
831 if (sym == &symbol_yes)
832 e = expr_alloc_two(E_AND, e1, e2);
833 if (sym == &symbol_no)
834 e = expr_alloc_two(E_OR, e1, e2);
835 if (type == E_UNEQUAL)
836 e = expr_alloc_one(E_NOT, e);
837 return e;
838 case E_OR:
839 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
840 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
841 if (sym == &symbol_yes)
842 e = expr_alloc_two(E_OR, e1, e2);
843 if (sym == &symbol_no)
844 e = expr_alloc_two(E_AND, e1, e2);
845 if (type == E_UNEQUAL)
846 e = expr_alloc_one(E_NOT, e);
847 return e;
848 case E_NOT:
849 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
850 case E_UNEQUAL:
851 case E_LTH:
852 case E_LEQ:
853 case E_GTH:
854 case E_GEQ:
855 case E_EQUAL:
856 if (type == E_EQUAL) {
857 if (sym == &symbol_yes)
858 return e;
859 if (sym == &symbol_mod)
860 return expr_alloc_symbol(&symbol_no);
861 if (sym == &symbol_no)
862 return expr_alloc_one(E_NOT, e);
863 } else {
864 if (sym == &symbol_yes)
865 return expr_alloc_one(E_NOT, e);
866 if (sym == &symbol_mod)
867 return expr_alloc_symbol(&symbol_yes);
868 if (sym == &symbol_no)
869 return e;
870 }
871 break;
872 case E_SYMBOL:
873 return expr_alloc_comp(type, e->left.sym, sym);
874 case E_RANGE:
875 case E_NONE:
876 /* panic */;
877 }
878 return NULL;
879}
880
881enum string_value_kind {
882 k_string,
883 k_signed,
884 k_unsigned,
885};
886
887union string_value {
888 unsigned long long u;
889 signed long long s;
890};
891
892static enum string_value_kind expr_parse_string(const char *str,
893 enum symbol_type type,
894 union string_value *val)
895{
896 char *tail;
897 enum string_value_kind kind;
898
899 errno = 0;
900 switch (type) {
901 case S_BOOLEAN:
902 case S_TRISTATE:
903 val->s = !strcmp(str, "n") ? 0 :
904 !strcmp(str, "m") ? 1 :
905 !strcmp(str, "y") ? 2 : -1;
906 return k_signed;
907 case S_INT:
908 val->s = strtoll(str, &tail, 10);
909 kind = k_signed;
910 break;
911 case S_HEX:
912 val->u = strtoull(str, &tail, 16);
913 kind = k_unsigned;
914 break;
915 default:
916 val->s = strtoll(str, &tail, 0);
917 kind = k_signed;
918 break;
919 }
920 return !errno && !*tail && tail > str && isxdigit(tail[-1])
921 ? kind : k_string;
922}
923
924static tristate __expr_calc_value(struct expr *e)
925{
926 tristate val1, val2;
927 const char *str1, *str2;
928 enum string_value_kind k1 = k_string, k2 = k_string;
929 union string_value lval = {}, rval = {};
930 int res;
931
932 switch (e->type) {
933 case E_SYMBOL:
934 sym_calc_value(e->left.sym);
935 return e->left.sym->curr.tri;
936 case E_AND:
937 val1 = expr_calc_value(e->left.expr);
938 val2 = expr_calc_value(e->right.expr);
939 return EXPR_AND(val1, val2);
940 case E_OR:
941 val1 = expr_calc_value(e->left.expr);
942 val2 = expr_calc_value(e->right.expr);
943 return EXPR_OR(val1, val2);
944 case E_NOT:
945 val1 = expr_calc_value(e->left.expr);
946 return EXPR_NOT(val1);
947 case E_EQUAL:
948 case E_GEQ:
949 case E_GTH:
950 case E_LEQ:
951 case E_LTH:
952 case E_UNEQUAL:
953 break;
954 default:
955 printf("expr_calc_value: %d?\n", e->type);
956 return no;
957 }
958
959 sym_calc_value(e->left.sym);
960 sym_calc_value(e->right.sym);
961 str1 = sym_get_string_value(e->left.sym);
962 str2 = sym_get_string_value(e->right.sym);
963
964 if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
965 k1 = expr_parse_string(str1, e->left.sym->type, &lval);
966 k2 = expr_parse_string(str2, e->right.sym->type, &rval);
967 }
968
969 if (k1 == k_string || k2 == k_string)
970 res = strcmp(str1, str2);
971 else if (k1 == k_unsigned || k2 == k_unsigned)
972 res = (lval.u > rval.u) - (lval.u < rval.u);
973 else /* if (k1 == k_signed && k2 == k_signed) */
974 res = (lval.s > rval.s) - (lval.s < rval.s);
975
976 switch(e->type) {
977 case E_EQUAL:
978 return res ? no : yes;
979 case E_GEQ:
980 return res >= 0 ? yes : no;
981 case E_GTH:
982 return res > 0 ? yes : no;
983 case E_LEQ:
984 return res <= 0 ? yes : no;
985 case E_LTH:
986 return res < 0 ? yes : no;
987 case E_UNEQUAL:
988 return res ? yes : no;
989 default:
990 printf("expr_calc_value: relation %d?\n", e->type);
991 return no;
992 }
993}
994
995/**
996 * expr_calc_value - return the tristate value of the given expression
997 * @e: expression
998 * return: tristate value of the expression
999 */
1000tristate expr_calc_value(struct expr *e)
1001{
1002 if (!e)
1003 return yes;
1004
1005 if (!e->val_is_valid) {
1006 e->val = __expr_calc_value(e);
1007 e->val_is_valid = true;
1008 }
1009
1010 return e->val;
1011}
1012
1013/**
1014 * expr_invalidate_all - invalidate all cached expression values
1015 */
1016void expr_invalidate_all(void)
1017{
1018 struct expr *e;
1019
1020 hash_for_each(expr_hashtable, e, node)
1021 e->val_is_valid = false;
1022}
1023
1024static int expr_compare_type(enum expr_type t1, enum expr_type t2)
1025{
1026 if (t1 == t2)
1027 return 0;
1028 switch (t1) {
1029 case E_LEQ:
1030 case E_LTH:
1031 case E_GEQ:
1032 case E_GTH:
1033 if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1034 return 1;
1035 /* fallthrough */
1036 case E_EQUAL:
1037 case E_UNEQUAL:
1038 if (t2 == E_NOT)
1039 return 1;
1040 /* fallthrough */
1041 case E_NOT:
1042 if (t2 == E_AND)
1043 return 1;
1044 /* fallthrough */
1045 case E_AND:
1046 if (t2 == E_OR)
1047 return 1;
1048 /* fallthrough */
1049 default:
1050 break;
1051 }
1052 return 0;
1053}
1054
1055void expr_print(const struct expr *e,
1056 void (*fn)(void *, struct symbol *, const char *),
1057 void *data, int prevtoken)
1058{
1059 if (!e) {
1060 fn(data, NULL, "y");
1061 return;
1062 }
1063
1064 if (expr_compare_type(prevtoken, e->type) > 0)
1065 fn(data, NULL, "(");
1066 switch (e->type) {
1067 case E_SYMBOL:
1068 if (e->left.sym->name)
1069 fn(data, e->left.sym, e->left.sym->name);
1070 else
1071 fn(data, NULL, "<choice>");
1072 break;
1073 case E_NOT:
1074 fn(data, NULL, "!");
1075 expr_print(e->left.expr, fn, data, E_NOT);
1076 break;
1077 case E_EQUAL:
1078 if (e->left.sym->name)
1079 fn(data, e->left.sym, e->left.sym->name);
1080 else
1081 fn(data, NULL, "<choice>");
1082 fn(data, NULL, "=");
1083 fn(data, e->right.sym, e->right.sym->name);
1084 break;
1085 case E_LEQ:
1086 case E_LTH:
1087 if (e->left.sym->name)
1088 fn(data, e->left.sym, e->left.sym->name);
1089 else
1090 fn(data, NULL, "<choice>");
1091 fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1092 fn(data, e->right.sym, e->right.sym->name);
1093 break;
1094 case E_GEQ:
1095 case E_GTH:
1096 if (e->left.sym->name)
1097 fn(data, e->left.sym, e->left.sym->name);
1098 else
1099 fn(data, NULL, "<choice>");
1100 fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1101 fn(data, e->right.sym, e->right.sym->name);
1102 break;
1103 case E_UNEQUAL:
1104 if (e->left.sym->name)
1105 fn(data, e->left.sym, e->left.sym->name);
1106 else
1107 fn(data, NULL, "<choice>");
1108 fn(data, NULL, "!=");
1109 fn(data, e->right.sym, e->right.sym->name);
1110 break;
1111 case E_OR:
1112 expr_print(e->left.expr, fn, data, E_OR);
1113 fn(data, NULL, " || ");
1114 expr_print(e->right.expr, fn, data, E_OR);
1115 break;
1116 case E_AND:
1117 expr_print(e->left.expr, fn, data, E_AND);
1118 fn(data, NULL, " && ");
1119 expr_print(e->right.expr, fn, data, E_AND);
1120 break;
1121 case E_RANGE:
1122 fn(data, NULL, "[");
1123 fn(data, e->left.sym, e->left.sym->name);
1124 fn(data, NULL, " ");
1125 fn(data, e->right.sym, e->right.sym->name);
1126 fn(data, NULL, "]");
1127 break;
1128 default:
1129 {
1130 char buf[32];
1131 sprintf(buf, "<unknown type %d>", e->type);
1132 fn(data, NULL, buf);
1133 break;
1134 }
1135 }
1136 if (expr_compare_type(prevtoken, e->type) > 0)
1137 fn(data, NULL, ")");
1138}
1139
1140static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1141{
1142 xfwrite(str, strlen(str), 1, data);
1143}
1144
1145void expr_fprint(struct expr *e, FILE *out)
1146{
1147 expr_print(e, expr_print_file_helper, out, E_NONE);
1148}
1149
1150static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1151{
1152 struct gstr *gs = (struct gstr*)data;
1153 const char *sym_str = NULL;
1154
1155 if (sym)
1156 sym_str = sym_get_string_value(sym);
1157
1158 if (gs->max_width) {
1159 unsigned extra_length = strlen(str);
1160 const char *last_cr = strrchr(gs->s, '\n');
1161 unsigned last_line_length;
1162
1163 if (sym_str)
1164 extra_length += 4 + strlen(sym_str);
1165
1166 if (!last_cr)
1167 last_cr = gs->s;
1168
1169 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1170
1171 if ((last_line_length + extra_length) > gs->max_width)
1172 str_append(gs, "\\\n");
1173 }
1174
1175 str_append(gs, str);
1176 if (sym && sym->type != S_UNKNOWN)
1177 str_printf(gs, " [=%s]", sym_str);
1178}
1179
1180void expr_gstr_print(const struct expr *e, struct gstr *gs)
1181{
1182 expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1183}
1184
1185/*
1186 * Transform the top level "||" tokens into newlines and prepend each
1187 * line with a minus. This makes expressions much easier to read.
1188 * Suitable for reverse dependency expressions.
1189 */
1190static void expr_print_revdep(struct expr *e,
1191 void (*fn)(void *, struct symbol *, const char *),
1192 void *data, tristate pr_type, const char **title)
1193{
1194 if (e->type == E_OR) {
1195 expr_print_revdep(e->left.expr, fn, data, pr_type, title);
1196 expr_print_revdep(e->right.expr, fn, data, pr_type, title);
1197 } else if (expr_calc_value(e) == pr_type) {
1198 if (*title) {
1199 fn(data, NULL, *title);
1200 *title = NULL;
1201 }
1202
1203 fn(data, NULL, " - ");
1204 expr_print(e, fn, data, E_NONE);
1205 fn(data, NULL, "\n");
1206 }
1207}
1208
1209void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
1210 tristate pr_type, const char *title)
1211{
1212 expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);
1213}