source: branches/stable/mindi-busybox/scripts/config/expr.c @ 821

Last change on this file since 821 was 821, checked in by bruno, 13 years ago

Addition of busybox 1.2.1 as a mindi-busybox new package
This should avoid delivering binary files in mindi not built there (Fedora and Debian are quite serious about that)

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