Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
0004  */
0005 
0006 #include <ctype.h>
0007 #include <errno.h>
0008 #include <stdio.h>
0009 #include <stdlib.h>
0010 #include <string.h>
0011 
0012 #include "lkc.h"
0013 
0014 #define DEBUG_EXPR  0
0015 
0016 static struct expr *expr_eliminate_yn(struct expr *e);
0017 
0018 struct expr *expr_alloc_symbol(struct symbol *sym)
0019 {
0020     struct expr *e = xcalloc(1, sizeof(*e));
0021     e->type = E_SYMBOL;
0022     e->left.sym = sym;
0023     return e;
0024 }
0025 
0026 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
0027 {
0028     struct expr *e = xcalloc(1, sizeof(*e));
0029     e->type = type;
0030     e->left.expr = ce;
0031     return e;
0032 }
0033 
0034 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
0035 {
0036     struct expr *e = xcalloc(1, sizeof(*e));
0037     e->type = type;
0038     e->left.expr = e1;
0039     e->right.expr = e2;
0040     return e;
0041 }
0042 
0043 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
0044 {
0045     struct expr *e = xcalloc(1, sizeof(*e));
0046     e->type = type;
0047     e->left.sym = s1;
0048     e->right.sym = s2;
0049     return e;
0050 }
0051 
0052 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
0053 {
0054     if (!e1)
0055         return e2;
0056     return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
0057 }
0058 
0059 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
0060 {
0061     if (!e1)
0062         return e2;
0063     return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
0064 }
0065 
0066 struct expr *expr_copy(const struct expr *org)
0067 {
0068     struct expr *e;
0069 
0070     if (!org)
0071         return NULL;
0072 
0073     e = xmalloc(sizeof(*org));
0074     memcpy(e, org, sizeof(*org));
0075     switch (org->type) {
0076     case E_SYMBOL:
0077         e->left = org->left;
0078         break;
0079     case E_NOT:
0080         e->left.expr = expr_copy(org->left.expr);
0081         break;
0082     case E_EQUAL:
0083     case E_GEQ:
0084     case E_GTH:
0085     case E_LEQ:
0086     case E_LTH:
0087     case E_UNEQUAL:
0088         e->left.sym = org->left.sym;
0089         e->right.sym = org->right.sym;
0090         break;
0091     case E_AND:
0092     case E_OR:
0093     case E_LIST:
0094         e->left.expr = expr_copy(org->left.expr);
0095         e->right.expr = expr_copy(org->right.expr);
0096         break;
0097     default:
0098         fprintf(stderr, "can't copy type %d\n", e->type);
0099         free(e);
0100         e = NULL;
0101         break;
0102     }
0103 
0104     return e;
0105 }
0106 
0107 void expr_free(struct expr *e)
0108 {
0109     if (!e)
0110         return;
0111 
0112     switch (e->type) {
0113     case E_SYMBOL:
0114         break;
0115     case E_NOT:
0116         expr_free(e->left.expr);
0117         break;
0118     case E_EQUAL:
0119     case E_GEQ:
0120     case E_GTH:
0121     case E_LEQ:
0122     case E_LTH:
0123     case E_UNEQUAL:
0124         break;
0125     case E_OR:
0126     case E_AND:
0127         expr_free(e->left.expr);
0128         expr_free(e->right.expr);
0129         break;
0130     default:
0131         fprintf(stderr, "how to free type %d?\n", e->type);
0132         break;
0133     }
0134     free(e);
0135 }
0136 
0137 static int trans_count;
0138 
0139 #define e1 (*ep1)
0140 #define e2 (*ep2)
0141 
0142 /*
0143  * expr_eliminate_eq() helper.
0144  *
0145  * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
0146  * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
0147  * against all other leaves. Two equal leaves are both replaced with either 'y'
0148  * or 'n' as appropriate for 'type', to be eliminated later.
0149  */
0150 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
0151 {
0152     /* Recurse down to leaves */
0153 
0154     if (e1->type == type) {
0155         __expr_eliminate_eq(type, &e1->left.expr, &e2);
0156         __expr_eliminate_eq(type, &e1->right.expr, &e2);
0157         return;
0158     }
0159     if (e2->type == type) {
0160         __expr_eliminate_eq(type, &e1, &e2->left.expr);
0161         __expr_eliminate_eq(type, &e1, &e2->right.expr);
0162         return;
0163     }
0164 
0165     /* e1 and e2 are leaves. Compare them. */
0166 
0167     if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
0168         e1->left.sym == e2->left.sym &&
0169         (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
0170         return;
0171     if (!expr_eq(e1, e2))
0172         return;
0173 
0174     /* e1 and e2 are equal leaves. Prepare them for elimination. */
0175 
0176     trans_count++;
0177     expr_free(e1); expr_free(e2);
0178     switch (type) {
0179     case E_OR:
0180         e1 = expr_alloc_symbol(&symbol_no);
0181         e2 = expr_alloc_symbol(&symbol_no);
0182         break;
0183     case E_AND:
0184         e1 = expr_alloc_symbol(&symbol_yes);
0185         e2 = expr_alloc_symbol(&symbol_yes);
0186         break;
0187     default:
0188         ;
0189     }
0190 }
0191 
0192 /*
0193  * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both.
0194  * Example reductions:
0195  *
0196  *  ep1: A && B           ->  ep1: y
0197  *  ep2: A && B && C      ->  ep2: C
0198  *
0199  *  ep1: A || B           ->  ep1: n
0200  *  ep2: A || B || C      ->  ep2: C
0201  *
0202  *  ep1: A && (B && FOO)  ->  ep1: FOO
0203  *  ep2: (BAR && B) && A  ->  ep2: BAR
0204  *
0205  *  ep1: A && (B || C)    ->  ep1: y
0206  *  ep2: (C || B) && A    ->  ep2: y
0207  *
0208  * Comparisons are done between all operands at the same "level" of && or ||.
0209  * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the
0210  * following operands will be compared:
0211  *
0212  *  - 'e1', 'e2 || e3', and 'e4 || e5', against each other
0213  *  - e2 against e3
0214  *  - e4 against e5
0215  *
0216  * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and
0217  * '(e1 && e2) && e3' are both a single level.
0218  *
0219  * See __expr_eliminate_eq() as well.
0220  */
0221 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
0222 {
0223     if (!e1 || !e2)
0224         return;
0225     switch (e1->type) {
0226     case E_OR:
0227     case E_AND:
0228         __expr_eliminate_eq(e1->type, ep1, ep2);
0229     default:
0230         ;
0231     }
0232     if (e1->type != e2->type) switch (e2->type) {
0233     case E_OR:
0234     case E_AND:
0235         __expr_eliminate_eq(e2->type, ep1, ep2);
0236     default:
0237         ;
0238     }
0239     e1 = expr_eliminate_yn(e1);
0240     e2 = expr_eliminate_yn(e2);
0241 }
0242 
0243 #undef e1
0244 #undef e2
0245 
0246 /*
0247  * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two
0248  * &&/|| expressions are considered equal if every operand in one expression
0249  * equals some operand in the other (operands do not need to appear in the same
0250  * order), recursively.
0251  */
0252 int expr_eq(struct expr *e1, struct expr *e2)
0253 {
0254     int res, old_count;
0255 
0256     /*
0257      * A NULL expr is taken to be yes, but there's also a different way to
0258      * represent yes. expr_is_yes() checks for either representation.
0259      */
0260     if (!e1 || !e2)
0261         return expr_is_yes(e1) && expr_is_yes(e2);
0262 
0263     if (e1->type != e2->type)
0264         return 0;
0265     switch (e1->type) {
0266     case E_EQUAL:
0267     case E_GEQ:
0268     case E_GTH:
0269     case E_LEQ:
0270     case E_LTH:
0271     case E_UNEQUAL:
0272         return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
0273     case E_SYMBOL:
0274         return e1->left.sym == e2->left.sym;
0275     case E_NOT:
0276         return expr_eq(e1->left.expr, e2->left.expr);
0277     case E_AND:
0278     case E_OR:
0279         e1 = expr_copy(e1);
0280         e2 = expr_copy(e2);
0281         old_count = trans_count;
0282         expr_eliminate_eq(&e1, &e2);
0283         res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
0284                e1->left.sym == e2->left.sym);
0285         expr_free(e1);
0286         expr_free(e2);
0287         trans_count = old_count;
0288         return res;
0289     case E_LIST:
0290     case E_RANGE:
0291     case E_NONE:
0292         /* panic */;
0293     }
0294 
0295     if (DEBUG_EXPR) {
0296         expr_fprint(e1, stdout);
0297         printf(" = ");
0298         expr_fprint(e2, stdout);
0299         printf(" ?\n");
0300     }
0301 
0302     return 0;
0303 }
0304 
0305 /*
0306  * Recursively performs the following simplifications in-place (as well as the
0307  * corresponding simplifications with swapped operands):
0308  *
0309  *  expr && n  ->  n
0310  *  expr && y  ->  expr
0311  *  expr || n  ->  expr
0312  *  expr || y  ->  y
0313  *
0314  * Returns the optimized expression.
0315  */
0316 static struct expr *expr_eliminate_yn(struct expr *e)
0317 {
0318     struct expr *tmp;
0319 
0320     if (e) switch (e->type) {
0321     case E_AND:
0322         e->left.expr = expr_eliminate_yn(e->left.expr);
0323         e->right.expr = expr_eliminate_yn(e->right.expr);
0324         if (e->left.expr->type == E_SYMBOL) {
0325             if (e->left.expr->left.sym == &symbol_no) {
0326                 expr_free(e->left.expr);
0327                 expr_free(e->right.expr);
0328                 e->type = E_SYMBOL;
0329                 e->left.sym = &symbol_no;
0330                 e->right.expr = NULL;
0331                 return e;
0332             } else if (e->left.expr->left.sym == &symbol_yes) {
0333                 free(e->left.expr);
0334                 tmp = e->right.expr;
0335                 *e = *(e->right.expr);
0336                 free(tmp);
0337                 return e;
0338             }
0339         }
0340         if (e->right.expr->type == E_SYMBOL) {
0341             if (e->right.expr->left.sym == &symbol_no) {
0342                 expr_free(e->left.expr);
0343                 expr_free(e->right.expr);
0344                 e->type = E_SYMBOL;
0345                 e->left.sym = &symbol_no;
0346                 e->right.expr = NULL;
0347                 return e;
0348             } else if (e->right.expr->left.sym == &symbol_yes) {
0349                 free(e->right.expr);
0350                 tmp = e->left.expr;
0351                 *e = *(e->left.expr);
0352                 free(tmp);
0353                 return e;
0354             }
0355         }
0356         break;
0357     case E_OR:
0358         e->left.expr = expr_eliminate_yn(e->left.expr);
0359         e->right.expr = expr_eliminate_yn(e->right.expr);
0360         if (e->left.expr->type == E_SYMBOL) {
0361             if (e->left.expr->left.sym == &symbol_no) {
0362                 free(e->left.expr);
0363                 tmp = e->right.expr;
0364                 *e = *(e->right.expr);
0365                 free(tmp);
0366                 return e;
0367             } else if (e->left.expr->left.sym == &symbol_yes) {
0368                 expr_free(e->left.expr);
0369                 expr_free(e->right.expr);
0370                 e->type = E_SYMBOL;
0371                 e->left.sym = &symbol_yes;
0372                 e->right.expr = NULL;
0373                 return e;
0374             }
0375         }
0376         if (e->right.expr->type == E_SYMBOL) {
0377             if (e->right.expr->left.sym == &symbol_no) {
0378                 free(e->right.expr);
0379                 tmp = e->left.expr;
0380                 *e = *(e->left.expr);
0381                 free(tmp);
0382                 return e;
0383             } else if (e->right.expr->left.sym == &symbol_yes) {
0384                 expr_free(e->left.expr);
0385                 expr_free(e->right.expr);
0386                 e->type = E_SYMBOL;
0387                 e->left.sym = &symbol_yes;
0388                 e->right.expr = NULL;
0389                 return e;
0390             }
0391         }
0392         break;
0393     default:
0394         ;
0395     }
0396     return e;
0397 }
0398 
0399 /*
0400  * bool FOO!=n => FOO
0401  */
0402 struct expr *expr_trans_bool(struct expr *e)
0403 {
0404     if (!e)
0405         return NULL;
0406     switch (e->type) {
0407     case E_AND:
0408     case E_OR:
0409     case E_NOT:
0410         e->left.expr = expr_trans_bool(e->left.expr);
0411         e->right.expr = expr_trans_bool(e->right.expr);
0412         break;
0413     case E_UNEQUAL:
0414         // FOO!=n -> FOO
0415         if (e->left.sym->type == S_TRISTATE) {
0416             if (e->right.sym == &symbol_no) {
0417                 e->type = E_SYMBOL;
0418                 e->right.sym = NULL;
0419             }
0420         }
0421         break;
0422     default:
0423         ;
0424     }
0425     return e;
0426 }
0427 
0428 /*
0429  * e1 || e2 -> ?
0430  */
0431 static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
0432 {
0433     struct expr *tmp;
0434     struct symbol *sym1, *sym2;
0435 
0436     if (expr_eq(e1, e2))
0437         return expr_copy(e1);
0438     if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
0439         return NULL;
0440     if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
0441         return NULL;
0442     if (e1->type == E_NOT) {
0443         tmp = e1->left.expr;
0444         if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
0445             return NULL;
0446         sym1 = tmp->left.sym;
0447     } else
0448         sym1 = e1->left.sym;
0449     if (e2->type == E_NOT) {
0450         if (e2->left.expr->type != E_SYMBOL)
0451             return NULL;
0452         sym2 = e2->left.expr->left.sym;
0453     } else
0454         sym2 = e2->left.sym;
0455     if (sym1 != sym2)
0456         return NULL;
0457     if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
0458         return NULL;
0459     if (sym1->type == S_TRISTATE) {
0460         if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
0461             ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
0462              (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
0463             // (a='y') || (a='m') -> (a!='n')
0464             return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
0465         }
0466         if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
0467             ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
0468              (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
0469             // (a='y') || (a='n') -> (a!='m')
0470             return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
0471         }
0472         if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
0473             ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
0474              (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
0475             // (a='m') || (a='n') -> (a!='y')
0476             return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
0477         }
0478     }
0479     if (sym1->type == S_BOOLEAN && sym1 == sym2) {
0480         if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
0481             (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
0482             return expr_alloc_symbol(&symbol_yes);
0483     }
0484 
0485     if (DEBUG_EXPR) {
0486         printf("optimize (");
0487         expr_fprint(e1, stdout);
0488         printf(") || (");
0489         expr_fprint(e2, stdout);
0490         printf(")?\n");
0491     }
0492     return NULL;
0493 }
0494 
0495 static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
0496 {
0497     struct expr *tmp;
0498     struct symbol *sym1, *sym2;
0499 
0500     if (expr_eq(e1, e2))
0501         return expr_copy(e1);
0502     if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
0503         return NULL;
0504     if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
0505         return NULL;
0506     if (e1->type == E_NOT) {
0507         tmp = e1->left.expr;
0508         if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
0509             return NULL;
0510         sym1 = tmp->left.sym;
0511     } else
0512         sym1 = e1->left.sym;
0513     if (e2->type == E_NOT) {
0514         if (e2->left.expr->type != E_SYMBOL)
0515             return NULL;
0516         sym2 = e2->left.expr->left.sym;
0517     } else
0518         sym2 = e2->left.sym;
0519     if (sym1 != sym2)
0520         return NULL;
0521     if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
0522         return NULL;
0523 
0524     if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
0525         (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
0526         // (a) && (a='y') -> (a='y')
0527         return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
0528 
0529     if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
0530         (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
0531         // (a) && (a!='n') -> (a)
0532         return expr_alloc_symbol(sym1);
0533 
0534     if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
0535         (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
0536         // (a) && (a!='m') -> (a='y')
0537         return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
0538 
0539     if (sym1->type == S_TRISTATE) {
0540         if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
0541             // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
0542             sym2 = e1->right.sym;
0543             if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
0544                 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
0545                                  : expr_alloc_symbol(&symbol_no);
0546         }
0547         if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
0548             // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
0549             sym2 = e2->right.sym;
0550             if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
0551                 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
0552                                  : expr_alloc_symbol(&symbol_no);
0553         }
0554         if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
0555                ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
0556                 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
0557             // (a!='y') && (a!='n') -> (a='m')
0558             return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
0559 
0560         if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
0561                ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
0562                 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
0563             // (a!='y') && (a!='m') -> (a='n')
0564             return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
0565 
0566         if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
0567                ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
0568                 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
0569             // (a!='m') && (a!='n') -> (a='m')
0570             return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
0571 
0572         if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
0573             (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
0574             (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
0575             (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
0576             return NULL;
0577     }
0578 
0579     if (DEBUG_EXPR) {
0580         printf("optimize (");
0581         expr_fprint(e1, stdout);
0582         printf(") && (");
0583         expr_fprint(e2, stdout);
0584         printf(")?\n");
0585     }
0586     return NULL;
0587 }
0588 
0589 /*
0590  * expr_eliminate_dups() helper.
0591  *
0592  * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
0593  * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
0594  * against all other leaves to look for simplifications.
0595  */
0596 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
0597 {
0598 #define e1 (*ep1)
0599 #define e2 (*ep2)
0600     struct expr *tmp;
0601 
0602     /* Recurse down to leaves */
0603 
0604     if (e1->type == type) {
0605         expr_eliminate_dups1(type, &e1->left.expr, &e2);
0606         expr_eliminate_dups1(type, &e1->right.expr, &e2);
0607         return;
0608     }
0609     if (e2->type == type) {
0610         expr_eliminate_dups1(type, &e1, &e2->left.expr);
0611         expr_eliminate_dups1(type, &e1, &e2->right.expr);
0612         return;
0613     }
0614 
0615     /* e1 and e2 are leaves. Compare and process them. */
0616 
0617     if (e1 == e2)
0618         return;
0619 
0620     switch (e1->type) {
0621     case E_OR: case E_AND:
0622         expr_eliminate_dups1(e1->type, &e1, &e1);
0623     default:
0624         ;
0625     }
0626 
0627     switch (type) {
0628     case E_OR:
0629         tmp = expr_join_or(e1, e2);
0630         if (tmp) {
0631             expr_free(e1); expr_free(e2);
0632             e1 = expr_alloc_symbol(&symbol_no);
0633             e2 = tmp;
0634             trans_count++;
0635         }
0636         break;
0637     case E_AND:
0638         tmp = expr_join_and(e1, e2);
0639         if (tmp) {
0640             expr_free(e1); expr_free(e2);
0641             e1 = expr_alloc_symbol(&symbol_yes);
0642             e2 = tmp;
0643             trans_count++;
0644         }
0645         break;
0646     default:
0647         ;
0648     }
0649 #undef e1
0650 #undef e2
0651 }
0652 
0653 /*
0654  * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
0655  * operands.
0656  *
0657  * Example simplifications:
0658  *
0659  *  A || B || A    ->  A || B
0660  *  A && B && A=y  ->  A=y && B
0661  *
0662  * Returns the deduplicated expression.
0663  */
0664 struct expr *expr_eliminate_dups(struct expr *e)
0665 {
0666     int oldcount;
0667     if (!e)
0668         return e;
0669 
0670     oldcount = trans_count;
0671     while (1) {
0672         trans_count = 0;
0673         switch (e->type) {
0674         case E_OR: case E_AND:
0675             expr_eliminate_dups1(e->type, &e, &e);
0676         default:
0677             ;
0678         }
0679         if (!trans_count)
0680             /* No simplifications done in this pass. We're done */
0681             break;
0682         e = expr_eliminate_yn(e);
0683     }
0684     trans_count = oldcount;
0685     return e;
0686 }
0687 
0688 /*
0689  * Performs various simplifications involving logical operators and
0690  * comparisons.
0691  *
0692  * Allocates and returns a new expression.
0693  */
0694 struct expr *expr_transform(struct expr *e)
0695 {
0696     struct expr *tmp;
0697 
0698     if (!e)
0699         return NULL;
0700     switch (e->type) {
0701     case E_EQUAL:
0702     case E_GEQ:
0703     case E_GTH:
0704     case E_LEQ:
0705     case E_LTH:
0706     case E_UNEQUAL:
0707     case E_SYMBOL:
0708     case E_LIST:
0709         break;
0710     default:
0711         e->left.expr = expr_transform(e->left.expr);
0712         e->right.expr = expr_transform(e->right.expr);
0713     }
0714 
0715     switch (e->type) {
0716     case E_EQUAL:
0717         if (e->left.sym->type != S_BOOLEAN)
0718             break;
0719         if (e->right.sym == &symbol_no) {
0720             e->type = E_NOT;
0721             e->left.expr = expr_alloc_symbol(e->left.sym);
0722             e->right.sym = NULL;
0723             break;
0724         }
0725         if (e->right.sym == &symbol_mod) {
0726             printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
0727             e->type = E_SYMBOL;
0728             e->left.sym = &symbol_no;
0729             e->right.sym = NULL;
0730             break;
0731         }
0732         if (e->right.sym == &symbol_yes) {
0733             e->type = E_SYMBOL;
0734             e->right.sym = NULL;
0735             break;
0736         }
0737         break;
0738     case E_UNEQUAL:
0739         if (e->left.sym->type != S_BOOLEAN)
0740             break;
0741         if (e->right.sym == &symbol_no) {
0742             e->type = E_SYMBOL;
0743             e->right.sym = NULL;
0744             break;
0745         }
0746         if (e->right.sym == &symbol_mod) {
0747             printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
0748             e->type = E_SYMBOL;
0749             e->left.sym = &symbol_yes;
0750             e->right.sym = NULL;
0751             break;
0752         }
0753         if (e->right.sym == &symbol_yes) {
0754             e->type = E_NOT;
0755             e->left.expr = expr_alloc_symbol(e->left.sym);
0756             e->right.sym = NULL;
0757             break;
0758         }
0759         break;
0760     case E_NOT:
0761         switch (e->left.expr->type) {
0762         case E_NOT:
0763             // !!a -> a
0764             tmp = e->left.expr->left.expr;
0765             free(e->left.expr);
0766             free(e);
0767             e = tmp;
0768             e = expr_transform(e);
0769             break;
0770         case E_EQUAL:
0771         case E_UNEQUAL:
0772             // !a='x' -> a!='x'
0773             tmp = e->left.expr;
0774             free(e);
0775             e = tmp;
0776             e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
0777             break;
0778         case E_LEQ:
0779         case E_GEQ:
0780             // !a<='x' -> a>'x'
0781             tmp = e->left.expr;
0782             free(e);
0783             e = tmp;
0784             e->type = e->type == E_LEQ ? E_GTH : E_LTH;
0785             break;
0786         case E_LTH:
0787         case E_GTH:
0788             // !a<'x' -> a>='x'
0789             tmp = e->left.expr;
0790             free(e);
0791             e = tmp;
0792             e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
0793             break;
0794         case E_OR:
0795             // !(a || b) -> !a && !b
0796             tmp = e->left.expr;
0797             e->type = E_AND;
0798             e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
0799             tmp->type = E_NOT;
0800             tmp->right.expr = NULL;
0801             e = expr_transform(e);
0802             break;
0803         case E_AND:
0804             // !(a && b) -> !a || !b
0805             tmp = e->left.expr;
0806             e->type = E_OR;
0807             e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
0808             tmp->type = E_NOT;
0809             tmp->right.expr = NULL;
0810             e = expr_transform(e);
0811             break;
0812         case E_SYMBOL:
0813             if (e->left.expr->left.sym == &symbol_yes) {
0814                 // !'y' -> 'n'
0815                 tmp = e->left.expr;
0816                 free(e);
0817                 e = tmp;
0818                 e->type = E_SYMBOL;
0819                 e->left.sym = &symbol_no;
0820                 break;
0821             }
0822             if (e->left.expr->left.sym == &symbol_mod) {
0823                 // !'m' -> 'm'
0824                 tmp = e->left.expr;
0825                 free(e);
0826                 e = tmp;
0827                 e->type = E_SYMBOL;
0828                 e->left.sym = &symbol_mod;
0829                 break;
0830             }
0831             if (e->left.expr->left.sym == &symbol_no) {
0832                 // !'n' -> 'y'
0833                 tmp = e->left.expr;
0834                 free(e);
0835                 e = tmp;
0836                 e->type = E_SYMBOL;
0837                 e->left.sym = &symbol_yes;
0838                 break;
0839             }
0840             break;
0841         default:
0842             ;
0843         }
0844         break;
0845     default:
0846         ;
0847     }
0848     return e;
0849 }
0850 
0851 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
0852 {
0853     if (!dep)
0854         return 0;
0855 
0856     switch (dep->type) {
0857     case E_AND:
0858     case E_OR:
0859         return expr_contains_symbol(dep->left.expr, sym) ||
0860                expr_contains_symbol(dep->right.expr, sym);
0861     case E_SYMBOL:
0862         return dep->left.sym == sym;
0863     case E_EQUAL:
0864     case E_GEQ:
0865     case E_GTH:
0866     case E_LEQ:
0867     case E_LTH:
0868     case E_UNEQUAL:
0869         return dep->left.sym == sym ||
0870                dep->right.sym == sym;
0871     case E_NOT:
0872         return expr_contains_symbol(dep->left.expr, sym);
0873     default:
0874         ;
0875     }
0876     return 0;
0877 }
0878 
0879 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
0880 {
0881     if (!dep)
0882         return false;
0883 
0884     switch (dep->type) {
0885     case E_AND:
0886         return expr_depends_symbol(dep->left.expr, sym) ||
0887                expr_depends_symbol(dep->right.expr, sym);
0888     case E_SYMBOL:
0889         return dep->left.sym == sym;
0890     case E_EQUAL:
0891         if (dep->left.sym == sym) {
0892             if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
0893                 return true;
0894         }
0895         break;
0896     case E_UNEQUAL:
0897         if (dep->left.sym == sym) {
0898             if (dep->right.sym == &symbol_no)
0899                 return true;
0900         }
0901         break;
0902     default:
0903         ;
0904     }
0905     return false;
0906 }
0907 
0908 /*
0909  * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
0910  * expression 'e'.
0911  *
0912  * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
0913  *
0914  *  A              ->  A!=n
0915  *  !A             ->  A=n
0916  *  A && B         ->  !(A=n || B=n)
0917  *  A || B         ->  !(A=n && B=n)
0918  *  A && (B || C)  ->  !(A=n || (B=n && C=n))
0919  *
0920  * Allocates and returns a new expression.
0921  */
0922 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
0923 {
0924     struct expr *e1, *e2;
0925 
0926     if (!e) {
0927         e = expr_alloc_symbol(sym);
0928         if (type == E_UNEQUAL)
0929             e = expr_alloc_one(E_NOT, e);
0930         return e;
0931     }
0932     switch (e->type) {
0933     case E_AND:
0934         e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
0935         e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
0936         if (sym == &symbol_yes)
0937             e = expr_alloc_two(E_AND, e1, e2);
0938         if (sym == &symbol_no)
0939             e = expr_alloc_two(E_OR, e1, e2);
0940         if (type == E_UNEQUAL)
0941             e = expr_alloc_one(E_NOT, e);
0942         return e;
0943     case E_OR:
0944         e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
0945         e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
0946         if (sym == &symbol_yes)
0947             e = expr_alloc_two(E_OR, e1, e2);
0948         if (sym == &symbol_no)
0949             e = expr_alloc_two(E_AND, e1, e2);
0950         if (type == E_UNEQUAL)
0951             e = expr_alloc_one(E_NOT, e);
0952         return e;
0953     case E_NOT:
0954         return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
0955     case E_UNEQUAL:
0956     case E_LTH:
0957     case E_LEQ:
0958     case E_GTH:
0959     case E_GEQ:
0960     case E_EQUAL:
0961         if (type == E_EQUAL) {
0962             if (sym == &symbol_yes)
0963                 return expr_copy(e);
0964             if (sym == &symbol_mod)
0965                 return expr_alloc_symbol(&symbol_no);
0966             if (sym == &symbol_no)
0967                 return expr_alloc_one(E_NOT, expr_copy(e));
0968         } else {
0969             if (sym == &symbol_yes)
0970                 return expr_alloc_one(E_NOT, expr_copy(e));
0971             if (sym == &symbol_mod)
0972                 return expr_alloc_symbol(&symbol_yes);
0973             if (sym == &symbol_no)
0974                 return expr_copy(e);
0975         }
0976         break;
0977     case E_SYMBOL:
0978         return expr_alloc_comp(type, e->left.sym, sym);
0979     case E_LIST:
0980     case E_RANGE:
0981     case E_NONE:
0982         /* panic */;
0983     }
0984     return NULL;
0985 }
0986 
0987 enum string_value_kind {
0988     k_string,
0989     k_signed,
0990     k_unsigned,
0991 };
0992 
0993 union string_value {
0994     unsigned long long u;
0995     signed long long s;
0996 };
0997 
0998 static enum string_value_kind expr_parse_string(const char *str,
0999                         enum symbol_type type,
1000                         union string_value *val)
1001 {
1002     char *tail;
1003     enum string_value_kind kind;
1004 
1005     errno = 0;
1006     switch (type) {
1007     case S_BOOLEAN:
1008     case S_TRISTATE:
1009         val->s = !strcmp(str, "n") ? 0 :
1010              !strcmp(str, "m") ? 1 :
1011              !strcmp(str, "y") ? 2 : -1;
1012         return k_signed;
1013     case S_INT:
1014         val->s = strtoll(str, &tail, 10);
1015         kind = k_signed;
1016         break;
1017     case S_HEX:
1018         val->u = strtoull(str, &tail, 16);
1019         kind = k_unsigned;
1020         break;
1021     default:
1022         val->s = strtoll(str, &tail, 0);
1023         kind = k_signed;
1024         break;
1025     }
1026     return !errno && !*tail && tail > str && isxdigit(tail[-1])
1027            ? kind : k_string;
1028 }
1029 
1030 tristate expr_calc_value(struct expr *e)
1031 {
1032     tristate val1, val2;
1033     const char *str1, *str2;
1034     enum string_value_kind k1 = k_string, k2 = k_string;
1035     union string_value lval = {}, rval = {};
1036     int res;
1037 
1038     if (!e)
1039         return yes;
1040 
1041     switch (e->type) {
1042     case E_SYMBOL:
1043         sym_calc_value(e->left.sym);
1044         return e->left.sym->curr.tri;
1045     case E_AND:
1046         val1 = expr_calc_value(e->left.expr);
1047         val2 = expr_calc_value(e->right.expr);
1048         return EXPR_AND(val1, val2);
1049     case E_OR:
1050         val1 = expr_calc_value(e->left.expr);
1051         val2 = expr_calc_value(e->right.expr);
1052         return EXPR_OR(val1, val2);
1053     case E_NOT:
1054         val1 = expr_calc_value(e->left.expr);
1055         return EXPR_NOT(val1);
1056     case E_EQUAL:
1057     case E_GEQ:
1058     case E_GTH:
1059     case E_LEQ:
1060     case E_LTH:
1061     case E_UNEQUAL:
1062         break;
1063     default:
1064         printf("expr_calc_value: %d?\n", e->type);
1065         return no;
1066     }
1067 
1068     sym_calc_value(e->left.sym);
1069     sym_calc_value(e->right.sym);
1070     str1 = sym_get_string_value(e->left.sym);
1071     str2 = sym_get_string_value(e->right.sym);
1072 
1073     if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
1074         k1 = expr_parse_string(str1, e->left.sym->type, &lval);
1075         k2 = expr_parse_string(str2, e->right.sym->type, &rval);
1076     }
1077 
1078     if (k1 == k_string || k2 == k_string)
1079         res = strcmp(str1, str2);
1080     else if (k1 == k_unsigned || k2 == k_unsigned)
1081         res = (lval.u > rval.u) - (lval.u < rval.u);
1082     else /* if (k1 == k_signed && k2 == k_signed) */
1083         res = (lval.s > rval.s) - (lval.s < rval.s);
1084 
1085     switch(e->type) {
1086     case E_EQUAL:
1087         return res ? no : yes;
1088     case E_GEQ:
1089         return res >= 0 ? yes : no;
1090     case E_GTH:
1091         return res > 0 ? yes : no;
1092     case E_LEQ:
1093         return res <= 0 ? yes : no;
1094     case E_LTH:
1095         return res < 0 ? yes : no;
1096     case E_UNEQUAL:
1097         return res ? yes : no;
1098     default:
1099         printf("expr_calc_value: relation %d?\n", e->type);
1100         return no;
1101     }
1102 }
1103 
1104 static int expr_compare_type(enum expr_type t1, enum expr_type t2)
1105 {
1106     if (t1 == t2)
1107         return 0;
1108     switch (t1) {
1109     case E_LEQ:
1110     case E_LTH:
1111     case E_GEQ:
1112     case E_GTH:
1113         if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1114             return 1;
1115     case E_EQUAL:
1116     case E_UNEQUAL:
1117         if (t2 == E_NOT)
1118             return 1;
1119     case E_NOT:
1120         if (t2 == E_AND)
1121             return 1;
1122     case E_AND:
1123         if (t2 == E_OR)
1124             return 1;
1125     case E_OR:
1126         if (t2 == E_LIST)
1127             return 1;
1128     case E_LIST:
1129         if (t2 == 0)
1130             return 1;
1131     default:
1132         return -1;
1133     }
1134     printf("[%dgt%d?]", t1, t2);
1135     return 0;
1136 }
1137 
1138 void expr_print(struct expr *e,
1139         void (*fn)(void *, struct symbol *, const char *),
1140         void *data, int prevtoken)
1141 {
1142     if (!e) {
1143         fn(data, NULL, "y");
1144         return;
1145     }
1146 
1147     if (expr_compare_type(prevtoken, e->type) > 0)
1148         fn(data, NULL, "(");
1149     switch (e->type) {
1150     case E_SYMBOL:
1151         if (e->left.sym->name)
1152             fn(data, e->left.sym, e->left.sym->name);
1153         else
1154             fn(data, NULL, "<choice>");
1155         break;
1156     case E_NOT:
1157         fn(data, NULL, "!");
1158         expr_print(e->left.expr, fn, data, E_NOT);
1159         break;
1160     case E_EQUAL:
1161         if (e->left.sym->name)
1162             fn(data, e->left.sym, e->left.sym->name);
1163         else
1164             fn(data, NULL, "<choice>");
1165         fn(data, NULL, "=");
1166         fn(data, e->right.sym, e->right.sym->name);
1167         break;
1168     case E_LEQ:
1169     case E_LTH:
1170         if (e->left.sym->name)
1171             fn(data, e->left.sym, e->left.sym->name);
1172         else
1173             fn(data, NULL, "<choice>");
1174         fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1175         fn(data, e->right.sym, e->right.sym->name);
1176         break;
1177     case E_GEQ:
1178     case E_GTH:
1179         if (e->left.sym->name)
1180             fn(data, e->left.sym, e->left.sym->name);
1181         else
1182             fn(data, NULL, "<choice>");
1183         fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1184         fn(data, e->right.sym, e->right.sym->name);
1185         break;
1186     case E_UNEQUAL:
1187         if (e->left.sym->name)
1188             fn(data, e->left.sym, e->left.sym->name);
1189         else
1190             fn(data, NULL, "<choice>");
1191         fn(data, NULL, "!=");
1192         fn(data, e->right.sym, e->right.sym->name);
1193         break;
1194     case E_OR:
1195         expr_print(e->left.expr, fn, data, E_OR);
1196         fn(data, NULL, " || ");
1197         expr_print(e->right.expr, fn, data, E_OR);
1198         break;
1199     case E_AND:
1200         expr_print(e->left.expr, fn, data, E_AND);
1201         fn(data, NULL, " && ");
1202         expr_print(e->right.expr, fn, data, E_AND);
1203         break;
1204     case E_LIST:
1205         fn(data, e->right.sym, e->right.sym->name);
1206         if (e->left.expr) {
1207             fn(data, NULL, " ^ ");
1208             expr_print(e->left.expr, fn, data, E_LIST);
1209         }
1210         break;
1211     case E_RANGE:
1212         fn(data, NULL, "[");
1213         fn(data, e->left.sym, e->left.sym->name);
1214         fn(data, NULL, " ");
1215         fn(data, e->right.sym, e->right.sym->name);
1216         fn(data, NULL, "]");
1217         break;
1218     default:
1219       {
1220         char buf[32];
1221         sprintf(buf, "<unknown type %d>", e->type);
1222         fn(data, NULL, buf);
1223         break;
1224       }
1225     }
1226     if (expr_compare_type(prevtoken, e->type) > 0)
1227         fn(data, NULL, ")");
1228 }
1229 
1230 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1231 {
1232     xfwrite(str, strlen(str), 1, data);
1233 }
1234 
1235 void expr_fprint(struct expr *e, FILE *out)
1236 {
1237     expr_print(e, expr_print_file_helper, out, E_NONE);
1238 }
1239 
1240 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1241 {
1242     struct gstr *gs = (struct gstr*)data;
1243     const char *sym_str = NULL;
1244 
1245     if (sym)
1246         sym_str = sym_get_string_value(sym);
1247 
1248     if (gs->max_width) {
1249         unsigned extra_length = strlen(str);
1250         const char *last_cr = strrchr(gs->s, '\n');
1251         unsigned last_line_length;
1252 
1253         if (sym_str)
1254             extra_length += 4 + strlen(sym_str);
1255 
1256         if (!last_cr)
1257             last_cr = gs->s;
1258 
1259         last_line_length = strlen(gs->s) - (last_cr - gs->s);
1260 
1261         if ((last_line_length + extra_length) > gs->max_width)
1262             str_append(gs, "\\\n");
1263     }
1264 
1265     str_append(gs, str);
1266     if (sym && sym->type != S_UNKNOWN)
1267         str_printf(gs, " [=%s]", sym_str);
1268 }
1269 
1270 void expr_gstr_print(struct expr *e, struct gstr *gs)
1271 {
1272     expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1273 }
1274 
1275 /*
1276  * Transform the top level "||" tokens into newlines and prepend each
1277  * line with a minus. This makes expressions much easier to read.
1278  * Suitable for reverse dependency expressions.
1279  */
1280 static void expr_print_revdep(struct expr *e,
1281                   void (*fn)(void *, struct symbol *, const char *),
1282                   void *data, tristate pr_type, const char **title)
1283 {
1284     if (e->type == E_OR) {
1285         expr_print_revdep(e->left.expr, fn, data, pr_type, title);
1286         expr_print_revdep(e->right.expr, fn, data, pr_type, title);
1287     } else if (expr_calc_value(e) == pr_type) {
1288         if (*title) {
1289             fn(data, NULL, *title);
1290             *title = NULL;
1291         }
1292 
1293         fn(data, NULL, "  - ");
1294         expr_print(e, fn, data, E_NONE);
1295         fn(data, NULL, "\n");
1296     }
1297 }
1298 
1299 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
1300                 tristate pr_type, const char *title)
1301 {
1302     expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);
1303 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!