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