projects/linux·blob 4563243e · refs

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