1
2
3
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 fprintf(stderr, "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 break;
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 fprintf(stderr, "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
141
142
143
144
145
146
147
148
149static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
150{
151
152
153 if (e1->type == type) {
154 __expr_eliminate_eq(type, &e1->left.expr, &e2);
155 __expr_eliminate_eq(type, &e1->right.expr, &e2);
156 return;
157 }
158 if (e2->type == type) {
159 __expr_eliminate_eq(type, &e1, &e2->left.expr);
160 __expr_eliminate_eq(type, &e1, &e2->right.expr);
161 return;
162 }
163
164
165
166 if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
167 e1->left.sym == e2->left.sym &&
168 (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
169 return;
170 if (!expr_eq(e1, e2))
171 return;
172
173
174
175 trans_count++;
176 expr_free(e1); expr_free(e2);
177 switch (type) {
178 case E_OR:
179 e1 = expr_alloc_symbol(&symbol_no);
180 e2 = expr_alloc_symbol(&symbol_no);
181 break;
182 case E_AND:
183 e1 = expr_alloc_symbol(&symbol_yes);
184 e2 = expr_alloc_symbol(&symbol_yes);
185 break;
186 default:
187 ;
188 }
189}
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
221{
222 if (!e1 || !e2)
223 return;
224 switch (e1->type) {
225 case E_OR:
226 case E_AND:
227 __expr_eliminate_eq(e1->type, ep1, ep2);
228 default:
229 ;
230 }
231 if (e1->type != e2->type) switch (e2->type) {
232 case E_OR:
233 case E_AND:
234 __expr_eliminate_eq(e2->type, ep1, ep2);
235 default:
236 ;
237 }
238 e1 = expr_eliminate_yn(e1);
239 e2 = expr_eliminate_yn(e2);
240}
241
242#undef e1
243#undef e2
244
245
246
247
248
249
250
251static int expr_eq(struct expr *e1, struct expr *e2)
252{
253 int res, old_count;
254
255 if (e1->type != e2->type)
256 return 0;
257 switch (e1->type) {
258 case E_EQUAL:
259 case E_GEQ:
260 case E_GTH:
261 case E_LEQ:
262 case E_LTH:
263 case E_UNEQUAL:
264 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
265 case E_SYMBOL:
266 return e1->left.sym == e2->left.sym;
267 case E_NOT:
268 return expr_eq(e1->left.expr, e2->left.expr);
269 case E_AND:
270 case E_OR:
271 e1 = expr_copy(e1);
272 e2 = expr_copy(e2);
273 old_count = trans_count;
274 expr_eliminate_eq(&e1, &e2);
275 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
276 e1->left.sym == e2->left.sym);
277 expr_free(e1);
278 expr_free(e2);
279 trans_count = old_count;
280 return res;
281 case E_LIST:
282 case E_RANGE:
283 case E_NONE:
284 ;
285 }
286
287 if (DEBUG_EXPR) {
288 expr_fprint(e1, stdout);
289 printf(" = ");
290 expr_fprint(e2, stdout);
291 printf(" ?\n");
292 }
293
294 return 0;
295}
296
297
298
299
300
301
302
303
304
305
306
307
308static struct expr *expr_eliminate_yn(struct expr *e)
309{
310 struct expr *tmp;
311
312 if (e) switch (e->type) {
313 case E_AND:
314 e->left.expr = expr_eliminate_yn(e->left.expr);
315 e->right.expr = expr_eliminate_yn(e->right.expr);
316 if (e->left.expr->type == E_SYMBOL) {
317 if (e->left.expr->left.sym == &symbol_no) {
318 expr_free(e->left.expr);
319 expr_free(e->right.expr);
320 e->type = E_SYMBOL;
321 e->left.sym = &symbol_no;
322 e->right.expr = NULL;
323 return e;
324 } else if (e->left.expr->left.sym == &symbol_yes) {
325 free(e->left.expr);
326 tmp = e->right.expr;
327 *e = *(e->right.expr);
328 free(tmp);
329 return e;
330 }
331 }
332 if (e->right.expr->type == E_SYMBOL) {
333 if (e->right.expr->left.sym == &symbol_no) {
334 expr_free(e->left.expr);
335 expr_free(e->right.expr);
336 e->type = E_SYMBOL;
337 e->left.sym = &symbol_no;
338 e->right.expr = NULL;
339 return e;
340 } else if (e->right.expr->left.sym == &symbol_yes) {
341 free(e->right.expr);
342 tmp = e->left.expr;
343 *e = *(e->left.expr);
344 free(tmp);
345 return e;
346 }
347 }
348 break;
349 case E_OR:
350 e->left.expr = expr_eliminate_yn(e->left.expr);
351 e->right.expr = expr_eliminate_yn(e->right.expr);
352 if (e->left.expr->type == E_SYMBOL) {
353 if (e->left.expr->left.sym == &symbol_no) {
354 free(e->left.expr);
355 tmp = e->right.expr;
356 *e = *(e->right.expr);
357 free(tmp);
358 return e;
359 } else if (e->left.expr->left.sym == &symbol_yes) {
360 expr_free(e->left.expr);
361 expr_free(e->right.expr);
362 e->type = E_SYMBOL;
363 e->left.sym = &symbol_yes;
364 e->right.expr = NULL;
365 return e;
366 }
367 }
368 if (e->right.expr->type == E_SYMBOL) {
369 if (e->right.expr->left.sym == &symbol_no) {
370 free(e->right.expr);
371 tmp = e->left.expr;
372 *e = *(e->left.expr);
373 free(tmp);
374 return e;
375 } else if (e->right.expr->left.sym == &symbol_yes) {
376 expr_free(e->left.expr);
377 expr_free(e->right.expr);
378 e->type = E_SYMBOL;
379 e->left.sym = &symbol_yes;
380 e->right.expr = NULL;
381 return e;
382 }
383 }
384 break;
385 default:
386 ;
387 }
388 return e;
389}
390
391
392
393
394struct expr *expr_trans_bool(struct expr *e)
395{
396 if (!e)
397 return NULL;
398 switch (e->type) {
399 case E_AND:
400 case E_OR:
401 case E_NOT:
402 e->left.expr = expr_trans_bool(e->left.expr);
403 e->right.expr = expr_trans_bool(e->right.expr);
404 break;
405 case E_UNEQUAL:
406
407 if (e->left.sym->type == S_TRISTATE) {
408 if (e->right.sym == &symbol_no) {
409 e->type = E_SYMBOL;
410 e->right.sym = NULL;
411 }
412 }
413 break;
414 default:
415 ;
416 }
417 return e;
418}
419
420
421
422
423static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
424{
425 struct expr *tmp;
426 struct symbol *sym1, *sym2;
427
428 if (expr_eq(e1, e2))
429 return expr_copy(e1);
430 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
431 return NULL;
432 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
433 return NULL;
434 if (e1->type == E_NOT) {
435 tmp = e1->left.expr;
436 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
437 return NULL;
438 sym1 = tmp->left.sym;
439 } else
440 sym1 = e1->left.sym;
441 if (e2->type == E_NOT) {
442 if (e2->left.expr->type != E_SYMBOL)
443 return NULL;
444 sym2 = e2->left.expr->left.sym;
445 } else
446 sym2 = e2->left.sym;
447 if (sym1 != sym2)
448 return NULL;
449 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
450 return NULL;
451 if (sym1->type == S_TRISTATE) {
452 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
453 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
454 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
455
456 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
457 }
458 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
459 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
460 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
461
462 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
463 }
464 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
465 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
466 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
467
468 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
469 }
470 }
471 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
472 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
473 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
474 return expr_alloc_symbol(&symbol_yes);
475 }
476
477 if (DEBUG_EXPR) {
478 printf("optimize (");
479 expr_fprint(e1, stdout);
480 printf(") || (");
481 expr_fprint(e2, stdout);
482 printf(")?\n");
483 }
484 return NULL;
485}
486
487static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
488{
489 struct expr *tmp;
490 struct symbol *sym1, *sym2;
491
492 if (expr_eq(e1, e2))
493 return expr_copy(e1);
494 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
495 return NULL;
496 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
497 return NULL;
498 if (e1->type == E_NOT) {
499 tmp = e1->left.expr;
500 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
501 return NULL;
502 sym1 = tmp->left.sym;
503 } else
504 sym1 = e1->left.sym;
505 if (e2->type == E_NOT) {
506 if (e2->left.expr->type != E_SYMBOL)
507 return NULL;
508 sym2 = e2->left.expr->left.sym;
509 } else
510 sym2 = e2->left.sym;
511 if (sym1 != sym2)
512 return NULL;
513 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
514 return NULL;
515
516 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
517 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
518
519 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
520
521 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
522 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
523
524 return expr_alloc_symbol(sym1);
525
526 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
527 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
528
529 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
530
531 if (sym1->type == S_TRISTATE) {
532 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
533
534 sym2 = e1->right.sym;
535 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
536 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
537 : expr_alloc_symbol(&symbol_no);
538 }
539 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
540
541 sym2 = e2->right.sym;
542 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
543 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
544 : expr_alloc_symbol(&symbol_no);
545 }
546 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
547 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
548 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
549
550 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
551
552 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
553 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
554 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
555
556 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
557
558 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
559 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
560 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
561
562 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
563
564 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
565 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
566 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
567 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
568 return NULL;
569 }
570
571 if (DEBUG_EXPR) {
572 printf("optimize (");
573 expr_fprint(e1, stdout);
574 printf(") && (");
575 expr_fprint(e2, stdout);
576 printf(")?\n");
577 }
578 return NULL;
579}
580
581
582
583
584
585
586
587
588static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
589{
590#define e1 (*ep1)
591#define e2 (*ep2)
592 struct expr *tmp;
593
594
595
596 if (e1->type == type) {
597 expr_eliminate_dups1(type, &e1->left.expr, &e2);
598 expr_eliminate_dups1(type, &e1->right.expr, &e2);
599 return;
600 }
601 if (e2->type == type) {
602 expr_eliminate_dups1(type, &e1, &e2->left.expr);
603 expr_eliminate_dups1(type, &e1, &e2->right.expr);
604 return;
605 }
606
607
608
609 if (e1 == e2)
610 return;
611
612 switch (e1->type) {
613 case E_OR: case E_AND:
614 expr_eliminate_dups1(e1->type, &e1, &e1);
615 default:
616 ;
617 }
618
619 switch (type) {
620 case E_OR:
621 tmp = expr_join_or(e1, e2);
622 if (tmp) {
623 expr_free(e1); expr_free(e2);
624 e1 = expr_alloc_symbol(&symbol_no);
625 e2 = tmp;
626 trans_count++;
627 }
628 break;
629 case E_AND:
630 tmp = expr_join_and(e1, e2);
631 if (tmp) {
632 expr_free(e1); expr_free(e2);
633 e1 = expr_alloc_symbol(&symbol_yes);
634 e2 = tmp;
635 trans_count++;
636 }
637 break;
638 default:
639 ;
640 }
641#undef e1
642#undef e2
643}
644
645
646
647
648
649
650
651
652
653
654
655
656struct expr *expr_eliminate_dups(struct expr *e)
657{
658 int oldcount;
659 if (!e)
660 return e;
661
662 oldcount = trans_count;
663 while (1) {
664 trans_count = 0;
665 switch (e->type) {
666 case E_OR: case E_AND:
667 expr_eliminate_dups1(e->type, &e, &e);
668 default:
669 ;
670 }
671 if (!trans_count)
672
673 break;
674 e = expr_eliminate_yn(e);
675 }
676 trans_count = oldcount;
677 return e;
678}
679
680
681
682
683
684
685
686struct expr *expr_transform(struct expr *e)
687{
688 struct expr *tmp;
689
690 if (!e)
691 return NULL;
692 switch (e->type) {
693 case E_EQUAL:
694 case E_GEQ:
695 case E_GTH:
696 case E_LEQ:
697 case E_LTH:
698 case E_UNEQUAL:
699 case E_SYMBOL:
700 case E_LIST:
701 break;
702 default:
703 e->left.expr = expr_transform(e->left.expr);
704 e->right.expr = expr_transform(e->right.expr);
705 }
706
707 switch (e->type) {
708 case E_EQUAL:
709 if (e->left.sym->type != S_BOOLEAN)
710 break;
711 if (e->right.sym == &symbol_no) {
712 e->type = E_NOT;
713 e->left.expr = expr_alloc_symbol(e->left.sym);
714 e->right.sym = NULL;
715 break;
716 }
717 if (e->right.sym == &symbol_mod) {
718 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
719 e->type = E_SYMBOL;
720 e->left.sym = &symbol_no;
721 e->right.sym = NULL;
722 break;
723 }
724 if (e->right.sym == &symbol_yes) {
725 e->type = E_SYMBOL;
726 e->right.sym = NULL;
727 break;
728 }
729 break;
730 case E_UNEQUAL:
731 if (e->left.sym->type != S_BOOLEAN)
732 break;
733 if (e->right.sym == &symbol_no) {
734 e->type = E_SYMBOL;
735 e->right.sym = NULL;
736 break;
737 }
738 if (e->right.sym == &symbol_mod) {
739 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
740 e->type = E_SYMBOL;
741 e->left.sym = &symbol_yes;
742 e->right.sym = NULL;
743 break;
744 }
745 if (e->right.sym == &symbol_yes) {
746 e->type = E_NOT;
747 e->left.expr = expr_alloc_symbol(e->left.sym);
748 e->right.sym = NULL;
749 break;
750 }
751 break;
752 case E_NOT:
753 switch (e->left.expr->type) {
754 case E_NOT:
755
756 tmp = e->left.expr->left.expr;
757 free(e->left.expr);
758 free(e);
759 e = tmp;
760 e = expr_transform(e);
761 break;
762 case E_EQUAL:
763 case E_UNEQUAL:
764
765 tmp = e->left.expr;
766 free(e);
767 e = tmp;
768 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
769 break;
770 case E_LEQ:
771 case E_GEQ:
772
773 tmp = e->left.expr;
774 free(e);
775 e = tmp;
776 e->type = e->type == E_LEQ ? E_GTH : E_LTH;
777 break;
778 case E_LTH:
779 case E_GTH:
780
781 tmp = e->left.expr;
782 free(e);
783 e = tmp;
784 e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
785 break;
786 case E_OR:
787
788 tmp = e->left.expr;
789 e->type = E_AND;
790 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
791 tmp->type = E_NOT;
792 tmp->right.expr = NULL;
793 e = expr_transform(e);
794 break;
795 case E_AND:
796
797 tmp = e->left.expr;
798 e->type = E_OR;
799 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
800 tmp->type = E_NOT;
801 tmp->right.expr = NULL;
802 e = expr_transform(e);
803 break;
804 case E_SYMBOL:
805 if (e->left.expr->left.sym == &symbol_yes) {
806
807 tmp = e->left.expr;
808 free(e);
809 e = tmp;
810 e->type = E_SYMBOL;
811 e->left.sym = &symbol_no;
812 break;
813 }
814 if (e->left.expr->left.sym == &symbol_mod) {
815
816 tmp = e->left.expr;
817 free(e);
818 e = tmp;
819 e->type = E_SYMBOL;
820 e->left.sym = &symbol_mod;
821 break;
822 }
823 if (e->left.expr->left.sym == &symbol_no) {
824
825 tmp = e->left.expr;
826 free(e);
827 e = tmp;
828 e->type = E_SYMBOL;
829 e->left.sym = &symbol_yes;
830 break;
831 }
832 break;
833 default:
834 ;
835 }
836 break;
837 default:
838 ;
839 }
840 return e;
841}
842
843int expr_contains_symbol(struct expr *dep, struct symbol *sym)
844{
845 if (!dep)
846 return 0;
847
848 switch (dep->type) {
849 case E_AND:
850 case E_OR:
851 return expr_contains_symbol(dep->left.expr, sym) ||
852 expr_contains_symbol(dep->right.expr, sym);
853 case E_SYMBOL:
854 return dep->left.sym == sym;
855 case E_EQUAL:
856 case E_GEQ:
857 case E_GTH:
858 case E_LEQ:
859 case E_LTH:
860 case E_UNEQUAL:
861 return dep->left.sym == sym ||
862 dep->right.sym == sym;
863 case E_NOT:
864 return expr_contains_symbol(dep->left.expr, sym);
865 default:
866 ;
867 }
868 return 0;
869}
870
871bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
872{
873 if (!dep)
874 return false;
875
876 switch (dep->type) {
877 case E_AND:
878 return expr_depends_symbol(dep->left.expr, sym) ||
879 expr_depends_symbol(dep->right.expr, sym);
880 case E_SYMBOL:
881 return dep->left.sym == sym;
882 case E_EQUAL:
883 if (dep->left.sym == sym) {
884 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
885 return true;
886 }
887 break;
888 case E_UNEQUAL:
889 if (dep->left.sym == sym) {
890 if (dep->right.sym == &symbol_no)
891 return true;
892 }
893 break;
894 default:
895 ;
896 }
897 return false;
898}
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
915{
916 struct expr *e1, *e2;
917
918 if (!e) {
919 e = expr_alloc_symbol(sym);
920 if (type == E_UNEQUAL)
921 e = expr_alloc_one(E_NOT, e);
922 return e;
923 }
924 switch (e->type) {
925 case E_AND:
926 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
927 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
928 if (sym == &symbol_yes)
929 e = expr_alloc_two(E_AND, e1, e2);
930 if (sym == &symbol_no)
931 e = expr_alloc_two(E_OR, e1, e2);
932 if (type == E_UNEQUAL)
933 e = expr_alloc_one(E_NOT, e);
934 return e;
935 case E_OR:
936 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
937 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
938 if (sym == &symbol_yes)
939 e = expr_alloc_two(E_OR, e1, e2);
940 if (sym == &symbol_no)
941 e = expr_alloc_two(E_AND, e1, e2);
942 if (type == E_UNEQUAL)
943 e = expr_alloc_one(E_NOT, e);
944 return e;
945 case E_NOT:
946 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
947 case E_UNEQUAL:
948 case E_LTH:
949 case E_LEQ:
950 case E_GTH:
951 case E_GEQ:
952 case E_EQUAL:
953 if (type == E_EQUAL) {
954 if (sym == &symbol_yes)
955 return expr_copy(e);
956 if (sym == &symbol_mod)
957 return expr_alloc_symbol(&symbol_no);
958 if (sym == &symbol_no)
959 return expr_alloc_one(E_NOT, expr_copy(e));
960 } else {
961 if (sym == &symbol_yes)
962 return expr_alloc_one(E_NOT, expr_copy(e));
963 if (sym == &symbol_mod)
964 return expr_alloc_symbol(&symbol_yes);
965 if (sym == &symbol_no)
966 return expr_copy(e);
967 }
968 break;
969 case E_SYMBOL:
970 return expr_alloc_comp(type, e->left.sym, sym);
971 case E_LIST:
972 case E_RANGE:
973 case E_NONE:
974 ;
975 }
976 return NULL;
977}
978
979enum string_value_kind {
980 k_string,
981 k_signed,
982 k_unsigned,
983 k_invalid
984};
985
986union string_value {
987 unsigned long long u;
988 signed long long s;
989};
990
991static enum string_value_kind expr_parse_string(const char *str,
992 enum symbol_type type,
993 union string_value *val)
994{
995 char *tail;
996 enum string_value_kind kind;
997
998 errno = 0;
999 switch (type) {
1000 case S_BOOLEAN:
1001 case S_TRISTATE:
1002 val->s = !strcmp(str, "n") ? 0 :
1003 !strcmp(str, "m") ? 1 :
1004 !strcmp(str, "y") ? 2 : -1;
1005 return k_signed;
1006 case S_INT:
1007 val->s = strtoll(str, &tail, 10);
1008 kind = k_signed;
1009 break;
1010 case S_HEX:
1011 val->u = strtoull(str, &tail, 16);
1012 kind = k_unsigned;
1013 break;
1014 case S_STRING:
1015 case S_UNKNOWN:
1016 val->s = strtoll(str, &tail, 0);
1017 kind = k_signed;
1018 break;
1019 default:
1020 return k_invalid;
1021 }
1022 return !errno && !*tail && tail > str && isxdigit(tail[-1])
1023 ? kind : k_string;
1024}
1025
1026tristate expr_calc_value(struct expr *e)
1027{
1028 tristate val1, val2;
1029 const char *str1, *str2;
1030 enum string_value_kind k1 = k_string, k2 = k_string;
1031 union string_value lval = {}, rval = {};
1032 int res;
1033
1034 if (!e)
1035 return yes;
1036
1037 switch (e->type) {
1038 case E_SYMBOL:
1039 sym_calc_value(e->left.sym);
1040 return e->left.sym->curr.tri;
1041 case E_AND:
1042 val1 = expr_calc_value(e->left.expr);
1043 val2 = expr_calc_value(e->right.expr);
1044 return EXPR_AND(val1, val2);
1045 case E_OR:
1046 val1 = expr_calc_value(e->left.expr);
1047 val2 = expr_calc_value(e->right.expr);
1048 return EXPR_OR(val1, val2);
1049 case E_NOT:
1050 val1 = expr_calc_value(e->left.expr);
1051 return EXPR_NOT(val1);
1052 case E_EQUAL:
1053 case E_GEQ:
1054 case E_GTH:
1055 case E_LEQ:
1056 case E_LTH:
1057 case E_UNEQUAL:
1058 break;
1059 default:
1060 printf("expr_calc_value: %d?\n", e->type);
1061 return no;
1062 }
1063
1064 sym_calc_value(e->left.sym);
1065 sym_calc_value(e->right.sym);
1066 str1 = sym_get_string_value(e->left.sym);
1067 str2 = sym_get_string_value(e->right.sym);
1068
1069 if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
1070 k1 = expr_parse_string(str1, e->left.sym->type, &lval);
1071 k2 = expr_parse_string(str2, e->right.sym->type, &rval);
1072 }
1073
1074 if (k1 == k_string || k2 == k_string)
1075 res = strcmp(str1, str2);
1076 else if (k1 == k_invalid || k2 == k_invalid) {
1077 if (e->type != E_EQUAL && e->type != E_UNEQUAL) {
1078 printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2);
1079 return no;
1080 }
1081 res = strcmp(str1, str2);
1082 } else if (k1 == k_unsigned || k2 == k_unsigned)
1083 res = (lval.u > rval.u) - (lval.u < rval.u);
1084 else
1085 res = (lval.s > rval.s) - (lval.s < rval.s);
1086
1087 switch(e->type) {
1088 case E_EQUAL:
1089 return res ? no : yes;
1090 case E_GEQ:
1091 return res >= 0 ? yes : no;
1092 case E_GTH:
1093 return res > 0 ? yes : no;
1094 case E_LEQ:
1095 return res <= 0 ? yes : no;
1096 case E_LTH:
1097 return res < 0 ? yes : no;
1098 case E_UNEQUAL:
1099 return res ? yes : no;
1100 default:
1101 printf("expr_calc_value: relation %d?\n", e->type);
1102 return no;
1103 }
1104}
1105
1106static int expr_compare_type(enum expr_type t1, enum expr_type t2)
1107{
1108 if (t1 == t2)
1109 return 0;
1110 switch (t1) {
1111 case E_LEQ:
1112 case E_LTH:
1113 case E_GEQ:
1114 case E_GTH:
1115 if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1116 return 1;
1117 case E_EQUAL:
1118 case E_UNEQUAL:
1119 if (t2 == E_NOT)
1120 return 1;
1121 case E_NOT:
1122 if (t2 == E_AND)
1123 return 1;
1124 case E_AND:
1125 if (t2 == E_OR)
1126 return 1;
1127 case E_OR:
1128 if (t2 == E_LIST)
1129 return 1;
1130 case E_LIST:
1131 if (t2 == 0)
1132 return 1;
1133 default:
1134 return -1;
1135 }
1136 printf("[%dgt%d?]", t1, t2);
1137 return 0;
1138}
1139
1140static inline struct expr *
1141expr_get_leftmost_symbol(const struct expr *e)
1142{
1143
1144 if (e == NULL)
1145 return NULL;
1146
1147 while (e->type != E_SYMBOL)
1148 e = e->left.expr;
1149
1150 return expr_copy(e);
1151}
1152
1153
1154
1155
1156
1157struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
1158{
1159 struct expr *ret;
1160
1161 switch (e1->type) {
1162 case E_OR:
1163 return expr_alloc_and(
1164 expr_simplify_unmet_dep(e1->left.expr, e2),
1165 expr_simplify_unmet_dep(e1->right.expr, e2));
1166 case E_AND: {
1167 struct expr *e;
1168 e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
1169 e = expr_eliminate_dups(e);
1170 ret = (!expr_eq(e, e1)) ? e1 : NULL;
1171 expr_free(e);
1172 break;
1173 }
1174 default:
1175 ret = e1;
1176 break;
1177 }
1178
1179 return expr_get_leftmost_symbol(ret);
1180}
1181
1182static void __expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken, bool revdep)
1183{
1184 if (!e) {
1185 fn(data, NULL, "y");
1186 return;
1187 }
1188
1189 if (expr_compare_type(prevtoken, e->type) > 0)
1190 fn(data, NULL, "(");
1191 switch (e->type) {
1192 case E_SYMBOL:
1193 if (e->left.sym->name)
1194 fn(data, e->left.sym, e->left.sym->name);
1195 else
1196 fn(data, NULL, "<choice>");
1197 break;
1198 case E_NOT:
1199 fn(data, NULL, "!");
1200 expr_print(e->left.expr, fn, data, E_NOT);
1201 break;
1202 case E_EQUAL:
1203 if (e->left.sym->name)
1204 fn(data, e->left.sym, e->left.sym->name);
1205 else
1206 fn(data, NULL, "<choice>");
1207 fn(data, NULL, "=");
1208 fn(data, e->right.sym, e->right.sym->name);
1209 break;
1210 case E_LEQ:
1211 case E_LTH:
1212 if (e->left.sym->name)
1213 fn(data, e->left.sym, e->left.sym->name);
1214 else
1215 fn(data, NULL, "<choice>");
1216 fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1217 fn(data, e->right.sym, e->right.sym->name);
1218 break;
1219 case E_GEQ:
1220 case E_GTH:
1221 if (e->left.sym->name)
1222 fn(data, e->left.sym, e->left.sym->name);
1223 else
1224 fn(data, NULL, "<choice>");
1225 fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1226 fn(data, e->right.sym, e->right.sym->name);
1227 break;
1228 case E_UNEQUAL:
1229 if (e->left.sym->name)
1230 fn(data, e->left.sym, e->left.sym->name);
1231 else
1232 fn(data, NULL, "<choice>");
1233 fn(data, NULL, "!=");
1234 fn(data, e->right.sym, e->right.sym->name);
1235 break;
1236 case E_OR:
1237 if (revdep && e->left.expr->type != E_OR)
1238 fn(data, NULL, "\n - ");
1239 __expr_print(e->left.expr, fn, data, E_OR, revdep);
1240 if (revdep)
1241 fn(data, NULL, "\n - ");
1242 else
1243 fn(data, NULL, " || ");
1244 __expr_print(e->right.expr, fn, data, E_OR, revdep);
1245 break;
1246 case E_AND:
1247 expr_print(e->left.expr, fn, data, E_AND);
1248 fn(data, NULL, " && ");
1249 expr_print(e->right.expr, fn, data, E_AND);
1250 break;
1251 case E_LIST:
1252 fn(data, e->right.sym, e->right.sym->name);
1253 if (e->left.expr) {
1254 fn(data, NULL, " ^ ");
1255 expr_print(e->left.expr, fn, data, E_LIST);
1256 }
1257 break;
1258 case E_RANGE:
1259 fn(data, NULL, "[");
1260 fn(data, e->left.sym, e->left.sym->name);
1261 fn(data, NULL, " ");
1262 fn(data, e->right.sym, e->right.sym->name);
1263 fn(data, NULL, "]");
1264 break;
1265 default:
1266 {
1267 char buf[32];
1268 sprintf(buf, "<unknown type %d>", e->type);
1269 fn(data, NULL, buf);
1270 break;
1271 }
1272 }
1273 if (expr_compare_type(prevtoken, e->type) > 0)
1274 fn(data, NULL, ")");
1275}
1276
1277void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1278{
1279 __expr_print(e, fn, data, prevtoken, false);
1280}
1281
1282static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1283{
1284 xfwrite(str, strlen(str), 1, data);
1285}
1286
1287void expr_fprint(struct expr *e, FILE *out)
1288{
1289 expr_print(e, expr_print_file_helper, out, E_NONE);
1290}
1291
1292static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1293{
1294 struct gstr *gs = (struct gstr*)data;
1295 const char *sym_str = NULL;
1296
1297 if (sym)
1298 sym_str = sym_get_string_value(sym);
1299
1300 if (gs->max_width) {
1301 unsigned extra_length = strlen(str);
1302 const char *last_cr = strrchr(gs->s, '\n');
1303 unsigned last_line_length;
1304
1305 if (sym_str)
1306 extra_length += 4 + strlen(sym_str);
1307
1308 if (!last_cr)
1309 last_cr = gs->s;
1310
1311 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1312
1313 if ((last_line_length + extra_length) > gs->max_width)
1314 str_append(gs, "\\\n");
1315 }
1316
1317 str_append(gs, str);
1318 if (sym && sym->type != S_UNKNOWN)
1319 str_printf(gs, " [=%s]", sym_str);
1320}
1321
1322void expr_gstr_print(struct expr *e, struct gstr *gs)
1323{
1324 expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1325}
1326
1327
1328
1329
1330
1331
1332void expr_gstr_print_revdep(struct expr *e, struct gstr *gs)
1333{
1334 __expr_print(e, expr_print_gstr_helper, gs, E_NONE, true);
1335}
1336