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