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