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