release/src/router/config/expr.c

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