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