Root/scripts/config/expr.c

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#define LKC_DIRECT_LINK
11#include "lkc.h"
12
13#define DEBUG_EXPR 0
14
15struct expr *expr_alloc_symbol(struct symbol *sym)
16{
17    struct expr *e = malloc(sizeof(*e));
18    memset(e, 0, sizeof(*e));
19    e->type = E_SYMBOL;
20    e->left.sym = sym;
21    return e;
22}
23
24struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
25{
26    struct expr *e = malloc(sizeof(*e));
27    memset(e, 0, 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 = malloc(sizeof(*e));
36    memset(e, 0, sizeof(*e));
37    e->type = type;
38    e->left.expr = e1;
39    e->right.expr = e2;
40    return e;
41}
42
43struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
44{
45    struct expr *e = malloc(sizeof(*e));
46    memset(e, 0, 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(struct expr *org)
68{
69    struct expr *e;
70
71    if (!org)
72        return NULL;
73
74    e = malloc(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_UNEQUAL:
85        e->left.sym = org->left.sym;
86        e->right.sym = org->right.sym;
87        break;
88    case E_AND:
89    case E_OR:
90    case E_CHOICE:
91        e->left.expr = expr_copy(org->left.expr);
92        e->right.expr = expr_copy(org->right.expr);
93        break;
94    default:
95        printf("can't copy type %d\n", e->type);
96        free(e);
97        e = NULL;
98        break;
99    }
100
101    return e;
102}
103
104void expr_free(struct expr *e)
105{
106    if (!e)
107        return;
108
109    switch (e->type) {
110    case E_SYMBOL:
111        break;
112    case E_NOT:
113        expr_free(e->left.expr);
114        return;
115    case E_EQUAL:
116    case E_UNEQUAL:
117        break;
118    case E_OR:
119    case E_AND:
120        expr_free(e->left.expr);
121        expr_free(e->right.expr);
122        break;
123    default:
124        printf("how to free type %d?\n", e->type);
125        break;
126    }
127    free(e);
128}
129
130static int trans_count;
131
132#define e1 (*ep1)
133#define e2 (*ep2)
134
135static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
136{
137    if (e1->type == type) {
138        __expr_eliminate_eq(type, &e1->left.expr, &e2);
139        __expr_eliminate_eq(type, &e1->right.expr, &e2);
140        return;
141    }
142    if (e2->type == type) {
143        __expr_eliminate_eq(type, &e1, &e2->left.expr);
144        __expr_eliminate_eq(type, &e1, &e2->right.expr);
145        return;
146    }
147    if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
148        e1->left.sym == e2->left.sym &&
149        (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
150        return;
151    if (!expr_eq(e1, e2))
152        return;
153    trans_count++;
154    expr_free(e1); expr_free(e2);
155    switch (type) {
156    case E_OR:
157        e1 = expr_alloc_symbol(&symbol_no);
158        e2 = expr_alloc_symbol(&symbol_no);
159        break;
160    case E_AND:
161        e1 = expr_alloc_symbol(&symbol_yes);
162        e2 = expr_alloc_symbol(&symbol_yes);
163        break;
164    default:
165        ;
166    }
167}
168
169void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
170{
171    if (!e1 || !e2)
172        return;
173    switch (e1->type) {
174    case E_OR:
175    case E_AND:
176        __expr_eliminate_eq(e1->type, ep1, ep2);
177    default:
178        ;
179    }
180    if (e1->type != e2->type) switch (e2->type) {
181    case E_OR:
182    case E_AND:
183        __expr_eliminate_eq(e2->type, ep1, ep2);
184    default:
185        ;
186    }
187    e1 = expr_eliminate_yn(e1);
188    e2 = expr_eliminate_yn(e2);
189}
190
191#undef e1
192#undef e2
193
194int expr_eq(struct expr *e1, struct expr *e2)
195{
196    int res, old_count;
197
198    if (e1->type != e2->type)
199        return 0;
200    switch (e1->type) {
201    case E_EQUAL:
202    case E_UNEQUAL:
203        return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
204    case E_SYMBOL:
205        return e1->left.sym == e2->left.sym;
206    case E_NOT:
207        return expr_eq(e1->left.expr, e2->left.expr);
208    case E_AND:
209    case E_OR:
210        e1 = expr_copy(e1);
211        e2 = expr_copy(e2);
212        old_count = trans_count;
213        expr_eliminate_eq(&e1, &e2);
214        res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
215               e1->left.sym == e2->left.sym);
216        expr_free(e1);
217        expr_free(e2);
218        trans_count = old_count;
219        return res;
220    case E_CHOICE:
221    case E_RANGE:
222    case E_NONE:
223        /* panic */;
224    }
225
226    if (DEBUG_EXPR) {
227        expr_fprint(e1, stdout);
228        printf(" = ");
229        expr_fprint(e2, stdout);
230        printf(" ?\n");
231    }
232
233    return 0;
234}
235
236struct expr *expr_eliminate_yn(struct expr *e)
237{
238    struct expr *tmp;
239
240    if (e) switch (e->type) {
241    case E_AND:
242        e->left.expr = expr_eliminate_yn(e->left.expr);
243        e->right.expr = expr_eliminate_yn(e->right.expr);
244        if (e->left.expr->type == E_SYMBOL) {
245            if (e->left.expr->left.sym == &symbol_no) {
246                expr_free(e->left.expr);
247                expr_free(e->right.expr);
248                e->type = E_SYMBOL;
249                e->left.sym = &symbol_no;
250                e->right.expr = NULL;
251                return e;
252            } else if (e->left.expr->left.sym == &symbol_yes) {
253                free(e->left.expr);
254                tmp = e->right.expr;
255                *e = *(e->right.expr);
256                free(tmp);
257                return e;
258            }
259        }
260        if (e->right.expr->type == E_SYMBOL) {
261            if (e->right.expr->left.sym == &symbol_no) {
262                expr_free(e->left.expr);
263                expr_free(e->right.expr);
264                e->type = E_SYMBOL;
265                e->left.sym = &symbol_no;
266                e->right.expr = NULL;
267                return e;
268            } else if (e->right.expr->left.sym == &symbol_yes) {
269                free(e->right.expr);
270                tmp = e->left.expr;
271                *e = *(e->left.expr);
272                free(tmp);
273                return e;
274            }
275        }
276        break;
277    case E_OR:
278        e->left.expr = expr_eliminate_yn(e->left.expr);
279        e->right.expr = expr_eliminate_yn(e->right.expr);
280        if (e->left.expr->type == E_SYMBOL) {
281            if (e->left.expr->left.sym == &symbol_no) {
282                free(e->left.expr);
283                tmp = e->right.expr;
284                *e = *(e->right.expr);
285                free(tmp);
286                return e;
287            } else if (e->left.expr->left.sym == &symbol_yes) {
288                expr_free(e->left.expr);
289                expr_free(e->right.expr);
290                e->type = E_SYMBOL;
291                e->left.sym = &symbol_yes;
292                e->right.expr = NULL;
293                return e;
294            }
295        }
296        if (e->right.expr->type == E_SYMBOL) {
297            if (e->right.expr->left.sym == &symbol_no) {
298                free(e->right.expr);
299                tmp = e->left.expr;
300                *e = *(e->left.expr);
301                free(tmp);
302                return e;
303            } else if (e->right.expr->left.sym == &symbol_yes) {
304                expr_free(e->left.expr);
305                expr_free(e->right.expr);
306                e->type = E_SYMBOL;
307                e->left.sym = &symbol_yes;
308                e->right.expr = NULL;
309                return e;
310            }
311        }
312        break;
313    default:
314        ;
315    }
316    return e;
317}
318
319/*
320 * bool FOO!=n => FOO
321 */
322struct expr *expr_trans_bool(struct expr *e)
323{
324    if (!e)
325        return NULL;
326    switch (e->type) {
327    case E_AND:
328    case E_OR:
329    case E_NOT:
330        e->left.expr = expr_trans_bool(e->left.expr);
331        e->right.expr = expr_trans_bool(e->right.expr);
332        break;
333    case E_UNEQUAL:
334        // FOO!=n -> FOO
335        if (e->left.sym->type == S_TRISTATE) {
336            if (e->right.sym == &symbol_no) {
337                e->type = E_SYMBOL;
338                e->right.sym = NULL;
339            }
340        }
341        break;
342    default:
343        ;
344    }
345    return e;
346}
347
348/*
349 * e1 || e2 -> ?
350 */
351static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
352{
353    struct expr *tmp;
354    struct symbol *sym1, *sym2;
355
356    if (expr_eq(e1, e2))
357        return expr_copy(e1);
358    if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
359        return NULL;
360    if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
361        return NULL;
362    if (e1->type == E_NOT) {
363        tmp = e1->left.expr;
364        if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
365            return NULL;
366        sym1 = tmp->left.sym;
367    } else
368        sym1 = e1->left.sym;
369    if (e2->type == E_NOT) {
370        if (e2->left.expr->type != E_SYMBOL)
371            return NULL;
372        sym2 = e2->left.expr->left.sym;
373    } else
374        sym2 = e2->left.sym;
375    if (sym1 != sym2)
376        return NULL;
377    if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
378        return NULL;
379    if (sym1->type == S_TRISTATE) {
380        if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
381            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
382             (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
383            // (a='y') || (a='m') -> (a!='n')
384            return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
385        }
386        if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
387            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
388             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
389            // (a='y') || (a='n') -> (a!='m')
390            return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
391        }
392        if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
393            ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
394             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
395            // (a='m') || (a='n') -> (a!='y')
396            return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
397        }
398    }
399    if (sym1->type == S_BOOLEAN && sym1 == sym2) {
400        if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
401            (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
402            return expr_alloc_symbol(&symbol_yes);
403    }
404
405    if (DEBUG_EXPR) {
406        printf("optimize (");
407        expr_fprint(e1, stdout);
408        printf(") || (");
409        expr_fprint(e2, stdout);
410        printf(")?\n");
411    }
412    return NULL;
413}
414
415static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
416{
417    struct expr *tmp;
418    struct symbol *sym1, *sym2;
419
420    if (expr_eq(e1, e2))
421        return expr_copy(e1);
422    if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
423        return NULL;
424    if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
425        return NULL;
426    if (e1->type == E_NOT) {
427        tmp = e1->left.expr;
428        if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
429            return NULL;
430        sym1 = tmp->left.sym;
431    } else
432        sym1 = e1->left.sym;
433    if (e2->type == E_NOT) {
434        if (e2->left.expr->type != E_SYMBOL)
435            return NULL;
436        sym2 = e2->left.expr->left.sym;
437    } else
438        sym2 = e2->left.sym;
439    if (sym1 != sym2)
440        return NULL;
441    if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
442        return NULL;
443
444    if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
445        (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
446        // (a) && (a='y') -> (a='y')
447        return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
448
449    if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
450        (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
451        // (a) && (a!='n') -> (a)
452        return expr_alloc_symbol(sym1);
453
454    if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
455        (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
456        // (a) && (a!='m') -> (a='y')
457        return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
458
459    if (sym1->type == S_TRISTATE) {
460        if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
461            // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
462            sym2 = e1->right.sym;
463            if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
464                return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
465                                 : expr_alloc_symbol(&symbol_no);
466        }
467        if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
468            // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
469            sym2 = e2->right.sym;
470            if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
471                return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
472                                 : expr_alloc_symbol(&symbol_no);
473        }
474        if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
475               ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
476                (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
477            // (a!='y') && (a!='n') -> (a='m')
478            return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
479
480        if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
481               ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
482                (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
483            // (a!='y') && (a!='m') -> (a='n')
484            return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
485
486        if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
487               ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
488                (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
489            // (a!='m') && (a!='n') -> (a='m')
490            return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
491
492        if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
493            (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
494            (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
495            (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
496            return NULL;
497    }
498
499    if (DEBUG_EXPR) {
500        printf("optimize (");
501        expr_fprint(e1, stdout);
502        printf(") && (");
503        expr_fprint(e2, stdout);
504        printf(")?\n");
505    }
506    return NULL;
507}
508
509static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
510{
511#define e1 (*ep1)
512#define e2 (*ep2)
513    struct expr *tmp;
514
515    if (e1->type == type) {
516        expr_eliminate_dups1(type, &e1->left.expr, &e2);
517        expr_eliminate_dups1(type, &e1->right.expr, &e2);
518        return;
519    }
520    if (e2->type == type) {
521        expr_eliminate_dups1(type, &e1, &e2->left.expr);
522        expr_eliminate_dups1(type, &e1, &e2->right.expr);
523        return;
524    }
525    if (e1 == e2)
526        return;
527
528    switch (e1->type) {
529    case E_OR: case E_AND:
530        expr_eliminate_dups1(e1->type, &e1, &e1);
531    default:
532        ;
533    }
534
535    switch (type) {
536    case E_OR:
537        tmp = expr_join_or(e1, e2);
538        if (tmp) {
539            expr_free(e1); expr_free(e2);
540            e1 = expr_alloc_symbol(&symbol_no);
541            e2 = tmp;
542            trans_count++;
543        }
544        break;
545    case E_AND:
546        tmp = expr_join_and(e1, e2);
547        if (tmp) {
548            expr_free(e1); expr_free(e2);
549            e1 = expr_alloc_symbol(&symbol_yes);
550            e2 = tmp;
551            trans_count++;
552        }
553        break;
554    default:
555        ;
556    }
557#undef e1
558#undef e2
559}
560
561static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
562{
563#define e1 (*ep1)
564#define e2 (*ep2)
565    struct expr *tmp, *tmp1, *tmp2;
566
567    if (e1->type == type) {
568        expr_eliminate_dups2(type, &e1->left.expr, &e2);
569        expr_eliminate_dups2(type, &e1->right.expr, &e2);
570        return;
571    }
572    if (e2->type == type) {
573        expr_eliminate_dups2(type, &e1, &e2->left.expr);
574        expr_eliminate_dups2(type, &e1, &e2->right.expr);
575    }
576    if (e1 == e2)
577        return;
578
579    switch (e1->type) {
580    case E_OR:
581        expr_eliminate_dups2(e1->type, &e1, &e1);
582        // (FOO || BAR) && (!FOO && !BAR) -> n
583        tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
584        tmp2 = expr_copy(e2);
585        tmp = expr_extract_eq_and(&tmp1, &tmp2);
586        if (expr_is_yes(tmp1)) {
587            expr_free(e1);
588            e1 = expr_alloc_symbol(&symbol_no);
589            trans_count++;
590        }
591        expr_free(tmp2);
592        expr_free(tmp1);
593        expr_free(tmp);
594        break;
595    case E_AND:
596        expr_eliminate_dups2(e1->type, &e1, &e1);
597        // (FOO && BAR) || (!FOO || !BAR) -> y
598        tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
599        tmp2 = expr_copy(e2);
600        tmp = expr_extract_eq_or(&tmp1, &tmp2);
601        if (expr_is_no(tmp1)) {
602            expr_free(e1);
603            e1 = expr_alloc_symbol(&symbol_yes);
604            trans_count++;
605        }
606        expr_free(tmp2);
607        expr_free(tmp1);
608        expr_free(tmp);
609        break;
610    default:
611        ;
612    }
613#undef e1
614#undef e2
615}
616
617struct expr *expr_eliminate_dups(struct expr *e)
618{
619    int oldcount;
620    if (!e)
621        return e;
622
623    oldcount = trans_count;
624    while (1) {
625        trans_count = 0;
626        switch (e->type) {
627        case E_OR: case E_AND:
628            expr_eliminate_dups1(e->type, &e, &e);
629            expr_eliminate_dups2(e->type, &e, &e);
630        default:
631            ;
632        }
633        if (!trans_count)
634            break;
635        e = expr_eliminate_yn(e);
636    }
637    trans_count = oldcount;
638    return e;
639}
640
641struct expr *expr_transform(struct expr *e)
642{
643    struct expr *tmp;
644
645    if (!e)
646        return NULL;
647    switch (e->type) {
648    case E_EQUAL:
649    case E_UNEQUAL:
650    case E_SYMBOL:
651    case E_CHOICE:
652        break;
653    default:
654        e->left.expr = expr_transform(e->left.expr);
655        e->right.expr = expr_transform(e->right.expr);
656    }
657
658    switch (e->type) {
659    case E_EQUAL:
660        if (e->left.sym->type != S_BOOLEAN)
661            break;
662        if (e->right.sym == &symbol_no) {
663            e->type = E_NOT;
664            e->left.expr = expr_alloc_symbol(e->left.sym);
665            e->right.sym = NULL;
666            break;
667        }
668        if (e->right.sym == &symbol_mod) {
669            printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
670            e->type = E_SYMBOL;
671            e->left.sym = &symbol_no;
672            e->right.sym = NULL;
673            break;
674        }
675        if (e->right.sym == &symbol_yes) {
676            e->type = E_SYMBOL;
677            e->right.sym = NULL;
678            break;
679        }
680        break;
681    case E_UNEQUAL:
682        if (e->left.sym->type != S_BOOLEAN)
683            break;
684        if (e->right.sym == &symbol_no) {
685            e->type = E_SYMBOL;
686            e->right.sym = NULL;
687            break;
688        }
689        if (e->right.sym == &symbol_mod) {
690            printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
691            e->type = E_SYMBOL;
692            e->left.sym = &symbol_yes;
693            e->right.sym = NULL;
694            break;
695        }
696        if (e->right.sym == &symbol_yes) {
697            e->type = E_NOT;
698            e->left.expr = expr_alloc_symbol(e->left.sym);
699            e->right.sym = NULL;
700            break;
701        }
702        break;
703    case E_NOT:
704        switch (e->left.expr->type) {
705        case E_NOT:
706            // !!a -> a
707            tmp = e->left.expr->left.expr;
708            free(e->left.expr);
709            free(e);
710            e = tmp;
711            e = expr_transform(e);
712            break;
713        case E_EQUAL:
714        case E_UNEQUAL:
715            // !a='x' -> a!='x'
716            tmp = e->left.expr;
717            free(e);
718            e = tmp;
719            e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
720            break;
721        case E_OR:
722            // !(a || b) -> !a && !b
723            tmp = e->left.expr;
724            e->type = E_AND;
725            e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
726            tmp->type = E_NOT;
727            tmp->right.expr = NULL;
728            e = expr_transform(e);
729            break;
730        case E_AND:
731            // !(a && b) -> !a || !b
732            tmp = e->left.expr;
733            e->type = E_OR;
734            e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
735            tmp->type = E_NOT;
736            tmp->right.expr = NULL;
737            e = expr_transform(e);
738            break;
739        case E_SYMBOL:
740            if (e->left.expr->left.sym == &symbol_yes) {
741                // !'y' -> 'n'
742                tmp = e->left.expr;
743                free(e);
744                e = tmp;
745                e->type = E_SYMBOL;
746                e->left.sym = &symbol_no;
747                break;
748            }
749            if (e->left.expr->left.sym == &symbol_mod) {
750                // !'m' -> 'm'
751                tmp = e->left.expr;
752                free(e);
753                e = tmp;
754                e->type = E_SYMBOL;
755                e->left.sym = &symbol_mod;
756                break;
757            }
758            if (e->left.expr->left.sym == &symbol_no) {
759                // !'n' -> 'y'
760                tmp = e->left.expr;
761                free(e);
762                e = tmp;
763                e->type = E_SYMBOL;
764                e->left.sym = &symbol_yes;
765                break;
766            }
767            break;
768        default:
769            ;
770        }
771        break;
772    default:
773        ;
774    }
775    return e;
776}
777
778int expr_contains_symbol(struct expr *dep, struct symbol *sym)
779{
780    if (!dep)
781        return 0;
782
783    switch (dep->type) {
784    case E_AND:
785    case E_OR:
786        return expr_contains_symbol(dep->left.expr, sym) ||
787               expr_contains_symbol(dep->right.expr, sym);
788    case E_SYMBOL:
789        return dep->left.sym == sym;
790    case E_EQUAL:
791    case E_UNEQUAL:
792        return dep->left.sym == sym ||
793               dep->right.sym == sym;
794    case E_NOT:
795        return expr_contains_symbol(dep->left.expr, sym);
796    default:
797        ;
798    }
799    return 0;
800}
801
802bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
803{
804    if (!dep)
805        return false;
806
807    switch (dep->type) {
808    case E_AND:
809        return expr_depends_symbol(dep->left.expr, sym) ||
810               expr_depends_symbol(dep->right.expr, sym);
811    case E_SYMBOL:
812        return dep->left.sym == sym;
813    case E_EQUAL:
814        if (dep->left.sym == sym) {
815            if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
816                return true;
817        }
818        break;
819    case E_UNEQUAL:
820        if (dep->left.sym == sym) {
821            if (dep->right.sym == &symbol_no)
822                return true;
823        }
824        break;
825    default:
826        ;
827    }
828     return false;
829}
830
831struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
832{
833    struct expr *tmp = NULL;
834    expr_extract_eq(E_AND, &tmp, ep1, ep2);
835    if (tmp) {
836        *ep1 = expr_eliminate_yn(*ep1);
837        *ep2 = expr_eliminate_yn(*ep2);
838    }
839    return tmp;
840}
841
842struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
843{
844    struct expr *tmp = NULL;
845    expr_extract_eq(E_OR, &tmp, ep1, ep2);
846    if (tmp) {
847        *ep1 = expr_eliminate_yn(*ep1);
848        *ep2 = expr_eliminate_yn(*ep2);
849    }
850    return tmp;
851}
852
853void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
854{
855#define e1 (*ep1)
856#define e2 (*ep2)
857    if (e1->type == type) {
858        expr_extract_eq(type, ep, &e1->left.expr, &e2);
859        expr_extract_eq(type, ep, &e1->right.expr, &e2);
860        return;
861    }
862    if (e2->type == type) {
863        expr_extract_eq(type, ep, ep1, &e2->left.expr);
864        expr_extract_eq(type, ep, ep1, &e2->right.expr);
865        return;
866    }
867    if (expr_eq(e1, e2)) {
868        *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
869        expr_free(e2);
870        if (type == E_AND) {
871            e1 = expr_alloc_symbol(&symbol_yes);
872            e2 = expr_alloc_symbol(&symbol_yes);
873        } else if (type == E_OR) {
874            e1 = expr_alloc_symbol(&symbol_no);
875            e2 = expr_alloc_symbol(&symbol_no);
876        }
877    }
878#undef e1
879#undef e2
880}
881
882struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
883{
884    struct expr *e1, *e2;
885
886    if (!e) {
887        e = expr_alloc_symbol(sym);
888        if (type == E_UNEQUAL)
889            e = expr_alloc_one(E_NOT, e);
890        return e;
891    }
892    switch (e->type) {
893    case E_AND:
894        e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
895        e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
896        if (sym == &symbol_yes)
897            e = expr_alloc_two(E_AND, e1, e2);
898        if (sym == &symbol_no)
899            e = expr_alloc_two(E_OR, e1, e2);
900        if (type == E_UNEQUAL)
901            e = expr_alloc_one(E_NOT, e);
902        return e;
903    case E_OR:
904        e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
905        e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
906        if (sym == &symbol_yes)
907            e = expr_alloc_two(E_OR, e1, e2);
908        if (sym == &symbol_no)
909            e = expr_alloc_two(E_AND, e1, e2);
910        if (type == E_UNEQUAL)
911            e = expr_alloc_one(E_NOT, e);
912        return e;
913    case E_NOT:
914        return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
915    case E_UNEQUAL:
916    case E_EQUAL:
917        if (type == E_EQUAL) {
918            if (sym == &symbol_yes)
919                return expr_copy(e);
920            if (sym == &symbol_mod)
921                return expr_alloc_symbol(&symbol_no);
922            if (sym == &symbol_no)
923                return expr_alloc_one(E_NOT, expr_copy(e));
924        } else {
925            if (sym == &symbol_yes)
926                return expr_alloc_one(E_NOT, expr_copy(e));
927            if (sym == &symbol_mod)
928                return expr_alloc_symbol(&symbol_yes);
929            if (sym == &symbol_no)
930                return expr_copy(e);
931        }
932        break;
933    case E_SYMBOL:
934        return expr_alloc_comp(type, e->left.sym, sym);
935    case E_CHOICE:
936    case E_RANGE:
937    case E_NONE:
938        /* panic */;
939    }
940    return NULL;
941}
942
943tristate expr_calc_value(struct expr *e)
944{
945    tristate val1, val2;
946    const char *str1, *str2;
947
948    if (!e)
949        return yes;
950
951    switch (e->type) {
952    case E_SYMBOL:
953        sym_calc_value(e->left.sym);
954        return e->left.sym->curr.tri;
955    case E_AND:
956        val1 = expr_calc_value(e->left.expr);
957        val2 = expr_calc_value(e->right.expr);
958        return E_AND(val1, val2);
959    case E_OR:
960        val1 = expr_calc_value(e->left.expr);
961        val2 = expr_calc_value(e->right.expr);
962        return E_OR(val1, val2);
963    case E_NOT:
964        val1 = expr_calc_value(e->left.expr);
965        return E_NOT(val1);
966    case E_EQUAL:
967        sym_calc_value(e->left.sym);
968        sym_calc_value(e->right.sym);
969        str1 = sym_get_string_value(e->left.sym);
970        str2 = sym_get_string_value(e->right.sym);
971        return !strcmp(str1, str2) ? yes : no;
972    case E_UNEQUAL:
973        sym_calc_value(e->left.sym);
974        sym_calc_value(e->right.sym);
975        str1 = sym_get_string_value(e->left.sym);
976        str2 = sym_get_string_value(e->right.sym);
977        return !strcmp(str1, str2) ? no : yes;
978    default:
979        printf("expr_calc_value: %d?\n", e->type);
980        return no;
981    }
982}
983
984int expr_compare_type(enum expr_type t1, enum expr_type t2)
985{
986#if 0
987    return 1;
988#else
989    if (t1 == t2)
990        return 0;
991    switch (t1) {
992    case E_EQUAL:
993    case E_UNEQUAL:
994        if (t2 == E_NOT)
995            return 1;
996    case E_NOT:
997        if (t2 == E_AND)
998            return 1;
999    case E_AND:
1000        if (t2 == E_OR)
1001            return 1;
1002    case E_OR:
1003        if (t2 == E_CHOICE)
1004            return 1;
1005    case E_CHOICE:
1006        if (t2 == 0)
1007            return 1;
1008    default:
1009        return -1;
1010    }
1011    printf("[%dgt%d?]", t1, t2);
1012    return 0;
1013#endif
1014}
1015
1016void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1017{
1018    if (!e) {
1019        fn(data, NULL, "y");
1020        return;
1021    }
1022
1023    if (expr_compare_type(prevtoken, e->type) > 0)
1024        fn(data, NULL, "(");
1025    switch (e->type) {
1026    case E_SYMBOL:
1027        if (e->left.sym->name)
1028            fn(data, e->left.sym, e->left.sym->name);
1029        else
1030            fn(data, NULL, "<choice>");
1031        break;
1032    case E_NOT:
1033        fn(data, NULL, "!");
1034        expr_print(e->left.expr, fn, data, E_NOT);
1035        break;
1036    case E_EQUAL:
1037        if (e->left.sym->name)
1038            fn(data, e->left.sym, e->left.sym->name);
1039        else
1040            fn(data, NULL, "<choice>");
1041        fn(data, NULL, "=");
1042        fn(data, e->right.sym, e->right.sym->name);
1043        break;
1044    case E_UNEQUAL:
1045        if (e->left.sym->name)
1046            fn(data, e->left.sym, e->left.sym->name);
1047        else
1048            fn(data, NULL, "<choice>");
1049        fn(data, NULL, "!=");
1050        fn(data, e->right.sym, e->right.sym->name);
1051        break;
1052    case E_OR:
1053        expr_print(e->left.expr, fn, data, E_OR);
1054        fn(data, NULL, " || ");
1055        expr_print(e->right.expr, fn, data, E_OR);
1056        break;
1057    case E_AND:
1058        expr_print(e->left.expr, fn, data, E_AND);
1059        fn(data, NULL, " && ");
1060        expr_print(e->right.expr, fn, data, E_AND);
1061        break;
1062    case E_CHOICE:
1063        fn(data, e->right.sym, e->right.sym->name);
1064        if (e->left.expr) {
1065            fn(data, NULL, " ^ ");
1066            expr_print(e->left.expr, fn, data, E_CHOICE);
1067        }
1068        break;
1069    case E_RANGE:
1070        fn(data, NULL, "[");
1071        fn(data, e->left.sym, e->left.sym->name);
1072        fn(data, NULL, " ");
1073        fn(data, e->right.sym, e->right.sym->name);
1074        fn(data, NULL, "]");
1075        break;
1076    default:
1077      {
1078        char buf[32];
1079        sprintf(buf, "<unknown type %d>", e->type);
1080        fn(data, NULL, buf);
1081        break;
1082      }
1083    }
1084    if (expr_compare_type(prevtoken, e->type) > 0)
1085        fn(data, NULL, ")");
1086}
1087
1088static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1089{
1090    fwrite(str, strlen(str), 1, data);
1091}
1092
1093void expr_fprint(struct expr *e, FILE *out)
1094{
1095    expr_print(e, expr_print_file_helper, out, E_NONE);
1096}
1097
1098static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1099{
1100    struct gstr *gs = (struct gstr*)data;
1101    const char *sym_str = NULL;
1102
1103    if (sym)
1104        sym_str = sym_get_string_value(sym);
1105
1106    if (gs->max_width) {
1107        unsigned extra_length = strlen(str);
1108        const char *last_cr = strrchr(gs->s, '\n');
1109        unsigned last_line_length;
1110
1111        if (sym_str)
1112            extra_length += 4 + strlen(sym_str);
1113
1114        if (!last_cr)
1115            last_cr = gs->s;
1116
1117        last_line_length = strlen(gs->s) - (last_cr - gs->s);
1118
1119        if ((last_line_length + extra_length) > gs->max_width)
1120            str_append(gs, "\\\n");
1121    }
1122
1123    str_append(gs, str);
1124    if (sym && sym->type != S_UNKNOWN)
1125        str_printf(gs, " [=%s]", sym_str);
1126}
1127
1128void expr_gstr_print(struct expr *e, struct gstr *gs)
1129{
1130    expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1131}
1132

Archive Download this file



interactive