source: trunk/scripts/config/expr.c @ 5059

Last change on this file since 5059 was 3682, checked in by nbd, 10 years ago

add kconfig from linux 2.6 to scripts/config

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.