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 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_GEQ:
  83         case E_GTH:
  84         case E_LEQ:
  85         case E_LTH:
  86         case E_UNEQUAL:
  87                 e->left.sym = org->left.sym;
  88                 e->right.sym = org->right.sym;
  89                 break;
  90         case E_AND:
  91         case E_OR:
  92         case E_LIST:
  93                 e->left.expr = expr_copy(org->left.expr);
  94                 e->right.expr = expr_copy(org->right.expr);
  95                 break;
  96         default:
  97                 fprintf(stderr, "can't copy type %d\n", e->type);
  98                 free(e);
  99                 e = NULL;
 100                 break;
 101         }
 102
 103         return e;
 104 }
 105
 106 void expr_free(struct expr *e)
 107 {
 108         if (!e)
 109                 return;
 110
 111         switch (e->type) {
 112         case E_SYMBOL:
 113                 break;
 114         case E_NOT:
 115                 expr_free(e->left.expr);
 116                 break;
 117         case E_EQUAL:
 118         case E_GEQ:
 119         case E_GTH:
 120         case E_LEQ:
 121         case E_LTH:
 122         case E_UNEQUAL:
 123                 break;
 124         case E_OR:
 125         case E_AND:
 126                 expr_free(e->left.expr);
 127                 expr_free(e->right.expr);
 128                 break;
 129         default:
 130                 fprintf(stderr, "how to free type %d?\n", e->type);
 131                 break;
 132         }
 133         free(e);
 134 }
 135
 136 static int trans_count;
 137
 138 #define e1 (*ep1)
 139 #define e2 (*ep2)
 140
 141 /*
 142  * expr_eliminate_eq() helper.
 143  *
 144  * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
 145  * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
 146  * against all other leaves. Two equal leaves are both replaced with either 'y'
 147  * or 'n' as appropriate for 'type', to be eliminated later.
 148  */
 149 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
 150 {
 151         /* Recurse down to leaves */
 152
 153         if (e1->type == type) {
 154                 __expr_eliminate_eq(type, &e1->left.expr, &e2);
 155                 __expr_eliminate_eq(type, &e1->right.expr, &e2);
 156                 return;
 157         }
 158         if (e2->type == type) {
 159                 __expr_eliminate_eq(type, &e1, &e2->left.expr);
 160                 __expr_eliminate_eq(type, &e1, &e2->right.expr);
 161                 return;
 162         }
 163
 164         /* e1 and e2 are leaves. Compare them. */
 165
 166         if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
 167             e1->left.sym == e2->left.sym &&
 168             (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
 169                 return;
 170         if (!expr_eq(e1, e2))
 171                 return;
 172
 173         /* e1 and e2 are equal leaves. Prepare them for elimination. */
 174
 175         trans_count++;
 176         expr_free(e1); expr_free(e2);
 177         switch (type) {
 178         case E_OR:
 179                 e1 = expr_alloc_symbol(&symbol_no);
 180                 e2 = expr_alloc_symbol(&symbol_no);
 181                 break;
 182         case E_AND:
 183                 e1 = expr_alloc_symbol(&symbol_yes);
 184                 e2 = expr_alloc_symbol(&symbol_yes);
 185                 break;
 186         default:
 187                 ;
 188         }
 189 }
 190
 191 /*
 192  * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both.
 193  * Example reductions:
 194  *
 195  *      ep1: A && B           ->  ep1: y
 196  *      ep2: A && B && C      ->  ep2: C
 197  *
 198  *      ep1: A || B           ->  ep1: n
 199  *      ep2: A || B || C      ->  ep2: C
 200  *
 201  *      ep1: A && (B && FOO)  ->  ep1: FOO
 202  *      ep2: (BAR && B) && A  ->  ep2: BAR
 203  *
 204  *      ep1: A && (B || C)    ->  ep1: y
 205  *      ep2: (C || B) && A    ->  ep2: y
 206  *
 207  * Comparisons are done between all operands at the same "level" of && or ||.
 208  * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the
 209  * following operands will be compared:
 210  *
 211  *      - 'e1', 'e2 || e3', and 'e4 || e5', against each other
 212  *      - e2 against e3
 213  *      - e4 against e5
 214  *
 215  * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and
 216  * '(e1 && e2) && e3' are both a single level.
 217  *
 218  * See __expr_eliminate_eq() as well.
 219  */
 220 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
 221 {
 222         if (!e1 || !e2)
 223                 return;
 224         switch (e1->type) {
 225         case E_OR:
 226         case E_AND:
 227                 __expr_eliminate_eq(e1->type, ep1, ep2);
 228         default:
 229                 ;
 230         }
 231         if (e1->type != e2->type) switch (e2->type) {
 232         case E_OR:
 233         case E_AND:
 234                 __expr_eliminate_eq(e2->type, ep1, ep2);
 235         default:
 236                 ;
 237         }
 238         e1 = expr_eliminate_yn(e1);
 239         e2 = expr_eliminate_yn(e2);
 240 }
 241
 242 #undef e1
 243 #undef e2
 244
 245 /*
 246  * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two
 247  * &&/|| expressions are considered equal if every operand in one expression
 248  * equals some operand in the other (operands do not need to appear in the same
 249  * order), recursively.
 250  */
 251 static int expr_eq(struct expr *e1, struct expr *e2)
 252 {
 253         int res, old_count;
 254
 255         /*
 256          * A NULL expr is taken to be yes, but there's also a different way to
 257          * represent yes. expr_is_yes() checks for either representation.
 258          */
 259         if (!e1 || !e2)
 260                 return expr_is_yes(e1) && expr_is_yes(e2);
 261
 262         if (e1->type != e2->type)
 263                 return 0;
 264         switch (e1->type) {
 265         case E_EQUAL:
 266         case E_GEQ:
 267         case E_GTH:
 268         case E_LEQ:
 269         case E_LTH:
 270         case E_UNEQUAL:
 271                 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
 272         case E_SYMBOL:
 273                 return e1->left.sym == e2->left.sym;
 274         case E_NOT:
 275                 return expr_eq(e1->left.expr, e2->left.expr);
 276         case E_AND:
 277         case E_OR:
 278                 e1 = expr_copy(e1);
 279                 e2 = expr_copy(e2);
 280                 old_count = trans_count;
 281                 expr_eliminate_eq(&e1, &e2);
 282                 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
 283                        e1->left.sym == e2->left.sym);
 284                 expr_free(e1);
 285                 expr_free(e2);
 286                 trans_count = old_count;
 287                 return res;
 288         case E_LIST:
 289         case E_RANGE:
 290         case E_NONE:
 291                 /* panic */;
 292         }
 293
 294         if (DEBUG_EXPR) {
 295                 expr_fprint(e1, stdout);
 296                 printf(" = ");
 297                 expr_fprint(e2, stdout);
 298                 printf(" ?\n");
 299         }
 300
 301         return 0;
 302 }
 303
 304 /*
 305  * Recursively performs the following simplifications in-place (as well as the
 306  * corresponding simplifications with swapped operands):
 307  *
 308  *      expr && n  ->  n
 309  *      expr && y  ->  expr
 310  *      expr || n  ->  expr
 311  *      expr || y  ->  y
 312  *
 313  * Returns the optimized expression.
 314  */
 315 static struct expr *expr_eliminate_yn(struct expr *e)
 316 {
 317         struct expr *tmp;
 318
 319         if (e) switch (e->type) {
 320         case E_AND:
 321                 e->left.expr = expr_eliminate_yn(e->left.expr);
 322                 e->right.expr = expr_eliminate_yn(e->right.expr);
 323                 if (e->left.expr->type == E_SYMBOL) {
 324                         if (e->left.expr->left.sym == &symbol_no) {
 325                                 expr_free(e->left.expr);
 326                                 expr_free(e->right.expr);
 327                                 e->type = E_SYMBOL;
 328                                 e->left.sym = &symbol_no;
 329                                 e->right.expr = NULL;
 330                                 return e;
 331                         } else if (e->left.expr->left.sym == &symbol_yes) {
 332                                 free(e->left.expr);
 333                                 tmp = e->right.expr;
 334                                 *e = *(e->right.expr);
 335                                 free(tmp);
 336                                 return e;
 337                         }
 338                 }
 339                 if (e->right.expr->type == E_SYMBOL) {
 340                         if (e->right.expr->left.sym == &symbol_no) {
 341                                 expr_free(e->left.expr);
 342                                 expr_free(e->right.expr);
 343                                 e->type = E_SYMBOL;
 344                                 e->left.sym = &symbol_no;
 345                                 e->right.expr = NULL;
 346                                 return e;
 347                         } else if (e->right.expr->left.sym == &symbol_yes) {
 348                                 free(e->right.expr);
 349                                 tmp = e->left.expr;
 350                                 *e = *(e->left.expr);
 351                                 free(tmp);
 352                                 return e;
 353                         }
 354                 }
 355                 break;
 356         case E_OR:
 357                 e->left.expr = expr_eliminate_yn(e->left.expr);
 358                 e->right.expr = expr_eliminate_yn(e->right.expr);
 359                 if (e->left.expr->type == E_SYMBOL) {
 360                         if (e->left.expr->left.sym == &symbol_no) {
 361                                 free(e->left.expr);
 362                                 tmp = e->right.expr;
 363                                 *e = *(e->right.expr);
 364                                 free(tmp);
 365                                 return e;
 366                         } else if (e->left.expr->left.sym == &symbol_yes) {
 367                                 expr_free(e->left.expr);
 368                                 expr_free(e->right.expr);
 369                                 e->type = E_SYMBOL;
 370                                 e->left.sym = &symbol_yes;
 371                                 e->right.expr = NULL;
 372                                 return e;
 373                         }
 374                 }
 375                 if (e->right.expr->type == E_SYMBOL) {
 376                         if (e->right.expr->left.sym == &symbol_no) {
 377                                 free(e->right.expr);
 378                                 tmp = e->left.expr;
 379                                 *e = *(e->left.expr);
 380                                 free(tmp);
 381                                 return e;
 382                         } else if (e->right.expr->left.sym == &symbol_yes) {
 383                                 expr_free(e->left.expr);
 384                                 expr_free(e->right.expr);
 385                                 e->type = E_SYMBOL;
 386                                 e->left.sym = &symbol_yes;
 387                                 e->right.expr = NULL;
 388                                 return e;
 389                         }
 390                 }
 391                 break;
 392         default:
 393                 ;
 394         }
 395         return e;
 396 }
 397
 398 /*
 399  * bool FOO!=n => FOO
 400  */
 401 struct expr *expr_trans_bool(struct expr *e)
 402 {
 403         if (!e)
 404                 return NULL;
 405         switch (e->type) {
 406         case E_AND:
 407         case E_OR:
 408         case E_NOT:
 409                 e->left.expr = expr_trans_bool(e->left.expr);
 410                 e->right.expr = expr_trans_bool(e->right.expr);
 411                 break;
 412         case E_UNEQUAL:
 413                 // FOO!=n -> FOO
 414                 if (e->left.sym->type == S_TRISTATE) {
 415                         if (e->right.sym == &symbol_no) {
 416                                 e->type = E_SYMBOL;
 417                                 e->right.sym = NULL;
 418                         }
 419                 }
 420                 break;
 421         default:
 422                 ;
 423         }
 424         return e;
 425 }
 426
 427 /*
 428  * e1 || e2 -> ?
 429  */
 430 static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
 431 {
 432         struct expr *tmp;
 433         struct symbol *sym1, *sym2;
 434
 435         if (expr_eq(e1, e2))
 436                 return expr_copy(e1);
 437         if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
 438                 return NULL;
 439         if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
 440                 return NULL;
 441         if (e1->type == E_NOT) {
 442                 tmp = e1->left.expr;
 443                 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
 444                         return NULL;
 445                 sym1 = tmp->left.sym;
 446         } else
 447                 sym1 = e1->left.sym;
 448         if (e2->type == E_NOT) {
 449                 if (e2->left.expr->type != E_SYMBOL)
 450                         return NULL;
 451                 sym2 = e2->left.expr->left.sym;
 452         } else
 453                 sym2 = e2->left.sym;
 454         if (sym1 != sym2)
 455                 return NULL;
 456         if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
 457                 return NULL;
 458         if (sym1->type == S_TRISTATE) {
 459                 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
 460                     ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
 461                      (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
 462                         // (a='y') || (a='m') -> (a!='n')
 463                         return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
 464                 }
 465                 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
 466                     ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
 467                      (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
 468                         // (a='y') || (a='n') -> (a!='m')
 469                         return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
 470                 }
 471                 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
 472                     ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
 473                      (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
 474                         // (a='m') || (a='n') -> (a!='y')
 475                         return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
 476                 }
 477         }
 478         if (sym1->type == S_BOOLEAN && sym1 == sym2) {
 479                 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
 480                     (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
 481                         return expr_alloc_symbol(&symbol_yes);
 482         }
 483
 484         if (DEBUG_EXPR) {
 485                 printf("optimize (");
 486                 expr_fprint(e1, stdout);
 487                 printf(") || (");
 488                 expr_fprint(e2, stdout);
 489                 printf(")?\n");
 490         }
 491         return NULL;
 492 }
 493
 494 static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
 495 {
 496         struct expr *tmp;
 497         struct symbol *sym1, *sym2;
 498
 499         if (expr_eq(e1, e2))
 500                 return expr_copy(e1);
 501         if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
 502                 return NULL;
 503         if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
 504                 return NULL;
 505         if (e1->type == E_NOT) {
 506                 tmp = e1->left.expr;
 507                 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
 508                         return NULL;
 509                 sym1 = tmp->left.sym;
 510         } else
 511                 sym1 = e1->left.sym;
 512         if (e2->type == E_NOT) {
 513                 if (e2->left.expr->type != E_SYMBOL)
 514                         return NULL;
 515                 sym2 = e2->left.expr->left.sym;
 516         } else
 517                 sym2 = e2->left.sym;
 518         if (sym1 != sym2)
 519                 return NULL;
 520         if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
 521                 return NULL;
 522
 523         if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
 524             (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
 525                 // (a) && (a='y') -> (a='y')
 526                 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
 527
 528         if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
 529             (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
 530                 // (a) && (a!='n') -> (a)
 531                 return expr_alloc_symbol(sym1);
 532
 533         if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
 534             (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
 535                 // (a) && (a!='m') -> (a='y')
 536                 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
 537
 538         if (sym1->type == S_TRISTATE) {
 539                 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
 540                         // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
 541                         sym2 = e1->right.sym;
 542                         if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
 543                                 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
 544                                                              : expr_alloc_symbol(&symbol_no);
 545                 }
 546                 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
 547                         // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
 548                         sym2 = e2->right.sym;
 549                         if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
 550                                 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
 551                                                              : expr_alloc_symbol(&symbol_no);
 552                 }
 553                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
 554                            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
 555                             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
 556                         // (a!='y') && (a!='n') -> (a='m')
 557                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
 558
 559                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
 560                            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
 561                             (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
 562                         // (a!='y') && (a!='m') -> (a='n')
 563                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
 564
 565                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
 566                            ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
 567                             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
 568                         // (a!='m') && (a!='n') -> (a='m')
 569                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
 570
 571                 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
 572                     (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
 573                     (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
 574                     (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
 575                         return NULL;
 576         }
 577
 578         if (DEBUG_EXPR) {
 579                 printf("optimize (");
 580                 expr_fprint(e1, stdout);
 581                 printf(") && (");
 582                 expr_fprint(e2, stdout);
 583                 printf(")?\n");
 584         }
 585         return NULL;
 586 }
 587
 588 /*
 589  * expr_eliminate_dups() helper.
 590  *
 591  * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
 592  * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
 593  * against all other leaves to look for simplifications.
 594  */
 595 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
 596 {
 597 #define e1 (*ep1)
 598 #define e2 (*ep2)
 599         struct expr *tmp;
 600
 601         /* Recurse down to leaves */
 602
 603         if (e1->type == type) {
 604                 expr_eliminate_dups1(type, &e1->left.expr, &e2);
 605                 expr_eliminate_dups1(type, &e1->right.expr, &e2);
 606                 return;
 607         }
 608         if (e2->type == type) {
 609                 expr_eliminate_dups1(type, &e1, &e2->left.expr);
 610                 expr_eliminate_dups1(type, &e1, &e2->right.expr);
 611                 return;
 612         }
 613
 614         /* e1 and e2 are leaves. Compare and process them. */
 615
 616         if (e1 == e2)
 617                 return;
 618
 619         switch (e1->type) {
 620         case E_OR: case E_AND:
 621                 expr_eliminate_dups1(e1->type, &e1, &e1);
 622         default:
 623                 ;
 624         }
 625
 626         switch (type) {
 627         case E_OR:
 628                 tmp = expr_join_or(e1, e2);
 629                 if (tmp) {
 630                         expr_free(e1); expr_free(e2);
 631                         e1 = expr_alloc_symbol(&symbol_no);
 632                         e2 = tmp;
 633                         trans_count++;
 634                 }
 635                 break;
 636         case E_AND:
 637                 tmp = expr_join_and(e1, e2);
 638                 if (tmp) {
 639                         expr_free(e1); expr_free(e2);
 640                         e1 = expr_alloc_symbol(&symbol_yes);
 641                         e2 = tmp;
 642                         trans_count++;
 643                 }
 644                 break;
 645         default:
 646                 ;
 647         }
 648 #undef e1
 649 #undef e2
 650 }
 651
 652 /*
 653  * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
 654  * operands.
 655  *
 656  * Example simplifications:
 657  *
 658  *      A || B || A    ->  A || B
 659  *      A && B && A=y  ->  A=y && B
 660  *
 661  * Returns the deduplicated expression.
 662  */
 663 struct expr *expr_eliminate_dups(struct expr *e)
 664 {
 665         int oldcount;
 666         if (!e)
 667                 return e;
 668
 669         oldcount = trans_count;
 670         while (1) {
 671                 trans_count = 0;
 672                 switch (e->type) {
 673                 case E_OR: case E_AND:
 674                         expr_eliminate_dups1(e->type, &e, &e);
 675                 default:
 676                         ;
 677                 }
 678                 if (!trans_count)
 679                         /* No simplifications done in this pass. We're done */
 680                         break;
 681                 e = expr_eliminate_yn(e);
 682         }
 683         trans_count = oldcount;
 684         return e;
 685 }
 686
 687 /*
 688  * Performs various simplifications involving logical operators and
 689  * comparisons.
 690  *
 691  * Allocates and returns a new expression.
 692  */
 693 struct expr *expr_transform(struct expr *e)
 694 {
 695         struct expr *tmp;
 696
 697         if (!e)
 698                 return NULL;
 699         switch (e->type) {
 700         case E_EQUAL:
 701         case E_GEQ:
 702         case E_GTH:
 703         case E_LEQ:
 704         case E_LTH:
 705         case E_UNEQUAL:
 706         case E_SYMBOL:
 707         case E_LIST:
 708                 break;
 709         default:
 710                 e->left.expr = expr_transform(e->left.expr);
 711                 e->right.expr = expr_transform(e->right.expr);
 712         }
 713
 714         switch (e->type) {
 715         case E_EQUAL:
 716                 if (e->left.sym->type != S_BOOLEAN)
 717                         break;
 718                 if (e->right.sym == &symbol_no) {
 719                         e->type = E_NOT;
 720                         e->left.expr = expr_alloc_symbol(e->left.sym);
 721                         e->right.sym = NULL;
 722                         break;
 723                 }
 724                 if (e->right.sym == &symbol_mod) {
 725                         printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
 726                         e->type = E_SYMBOL;
 727                         e->left.sym = &symbol_no;
 728                         e->right.sym = NULL;
 729                         break;
 730                 }
 731                 if (e->right.sym == &symbol_yes) {
 732                         e->type = E_SYMBOL;
 733                         e->right.sym = NULL;
 734                         break;
 735                 }
 736                 break;
 737         case E_UNEQUAL:
 738                 if (e->left.sym->type != S_BOOLEAN)
 739                         break;
 740                 if (e->right.sym == &symbol_no) {
 741                         e->type = E_SYMBOL;
 742                         e->right.sym = NULL;
 743                         break;
 744                 }
 745                 if (e->right.sym == &symbol_mod) {
 746                         printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
 747                         e->type = E_SYMBOL;
 748                         e->left.sym = &symbol_yes;
 749                         e->right.sym = NULL;
 750                         break;
 751                 }
 752                 if (e->right.sym == &symbol_yes) {
 753                         e->type = E_NOT;
 754                         e->left.expr = expr_alloc_symbol(e->left.sym);
 755                         e->right.sym = NULL;
 756                         break;
 757                 }
 758                 break;
 759         case E_NOT:
 760                 switch (e->left.expr->type) {
 761                 case E_NOT:
 762                         // !!a -> a
 763                         tmp = e->left.expr->left.expr;
 764                         free(e->left.expr);
 765                         free(e);
 766                         e = tmp;
 767                         e = expr_transform(e);
 768                         break;
 769                 case E_EQUAL:
 770                 case E_UNEQUAL:
 771                         // !a='x' -> a!='x'
 772                         tmp = e->left.expr;
 773                         free(e);
 774                         e = tmp;
 775                         e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
 776                         break;
 777                 case E_LEQ:
 778                 case E_GEQ:
 779                         // !a<='x' -> a>'x'
 780                         tmp = e->left.expr;
 781                         free(e);
 782                         e = tmp;
 783                         e->type = e->type == E_LEQ ? E_GTH : E_LTH;
 784                         break;
 785                 case E_LTH:
 786                 case E_GTH:
 787                         // !a<'x' -> a>='x'
 788                         tmp = e->left.expr;
 789                         free(e);
 790                         e = tmp;
 791                         e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
 792                         break;
 793                 case E_OR:
 794                         // !(a || b) -> !a && !b
 795                         tmp = e->left.expr;
 796                         e->type = E_AND;
 797                         e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
 798                         tmp->type = E_NOT;
 799                         tmp->right.expr = NULL;
 800                         e = expr_transform(e);
 801                         break;
 802                 case E_AND:
 803                         // !(a && b) -> !a || !b
 804                         tmp = e->left.expr;
 805                         e->type = E_OR;
 806                         e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
 807                         tmp->type = E_NOT;
 808                         tmp->right.expr = NULL;
 809                         e = expr_transform(e);
 810                         break;
 811                 case E_SYMBOL:
 812                         if (e->left.expr->left.sym == &symbol_yes) {
 813                                 // !'y' -> 'n'
 814                                 tmp = e->left.expr;
 815                                 free(e);
 816                                 e = tmp;
 817                                 e->type = E_SYMBOL;
 818                                 e->left.sym = &symbol_no;
 819                                 break;
 820                         }
 821                         if (e->left.expr->left.sym == &symbol_mod) {
 822                                 // !'m' -> 'm'
 823                                 tmp = e->left.expr;
 824                                 free(e);
 825                                 e = tmp;
 826                                 e->type = E_SYMBOL;
 827                                 e->left.sym = &symbol_mod;
 828                                 break;
 829                         }
 830                         if (e->left.expr->left.sym == &symbol_no) {
 831                                 // !'n' -> 'y'
 832                                 tmp = e->left.expr;
 833                                 free(e);
 834                                 e = tmp;
 835                                 e->type = E_SYMBOL;
 836                                 e->left.sym = &symbol_yes;
 837                                 break;
 838                         }
 839                         break;
 840                 default:
 841                         ;
 842                 }
 843                 break;
 844         default:
 845                 ;
 846         }
 847         return e;
 848 }
 849
 850 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
 851 {
 852         if (!dep)
 853                 return 0;
 854
 855         switch (dep->type) {
 856         case E_AND:
 857         case E_OR:
 858                 return expr_contains_symbol(dep->left.expr, sym) ||
 859                        expr_contains_symbol(dep->right.expr, sym);
 860         case E_SYMBOL:
 861                 return dep->left.sym == sym;
 862         case E_EQUAL:
 863         case E_GEQ:
 864         case E_GTH:
 865         case E_LEQ:
 866         case E_LTH:
 867         case E_UNEQUAL:
 868                 return dep->left.sym == sym ||
 869                        dep->right.sym == sym;
 870         case E_NOT:
 871                 return expr_contains_symbol(dep->left.expr, sym);
 872         default:
 873                 ;
 874         }
 875         return 0;
 876 }
 877
 878 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
 879 {
 880         if (!dep)
 881                 return false;
 882
 883         switch (dep->type) {
 884         case E_AND:
 885                 return expr_depends_symbol(dep->left.expr, sym) ||
 886                        expr_depends_symbol(dep->right.expr, sym);
 887         case E_SYMBOL:
 888                 return dep->left.sym == sym;
 889         case E_EQUAL:
 890                 if (dep->left.sym == sym) {
 891                         if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
 892                                 return true;
 893                 }
 894                 break;
 895         case E_UNEQUAL:
 896                 if (dep->left.sym == sym) {
 897                         if (dep->right.sym == &symbol_no)
 898                                 return true;
 899                 }
 900                 break;
 901         default:
 902                 ;
 903         }
 904         return false;
 905 }
 906
 907 /*
 908  * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
 909  * expression 'e'.
 910  *
 911  * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
 912  *
 913  *      A              ->  A!=n
 914  *      !A             ->  A=n
 915  *      A && B         ->  !(A=n || B=n)
 916  *      A || B         ->  !(A=n && B=n)
 917  *      A && (B || C)  ->  !(A=n || (B=n && C=n))
 918  *
 919  * Allocates and returns a new expression.
 920  */
 921 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
 922 {
 923         struct expr *e1, *e2;
 924
 925         if (!e) {
 926                 e = expr_alloc_symbol(sym);
 927                 if (type == E_UNEQUAL)
 928                         e = expr_alloc_one(E_NOT, e);
 929                 return e;
 930         }
 931         switch (e->type) {
 932         case E_AND:
 933                 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
 934                 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
 935                 if (sym == &symbol_yes)
 936                         e = expr_alloc_two(E_AND, e1, e2);
 937                 if (sym == &symbol_no)
 938                         e = expr_alloc_two(E_OR, e1, e2);
 939                 if (type == E_UNEQUAL)
 940                         e = expr_alloc_one(E_NOT, e);
 941                 return e;
 942         case E_OR:
 943                 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
 944                 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
 945                 if (sym == &symbol_yes)
 946                         e = expr_alloc_two(E_OR, e1, e2);
 947                 if (sym == &symbol_no)
 948                         e = expr_alloc_two(E_AND, e1, e2);
 949                 if (type == E_UNEQUAL)
 950                         e = expr_alloc_one(E_NOT, e);
 951                 return e;
 952         case E_NOT:
 953                 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
 954         case E_UNEQUAL:
 955         case E_LTH:
 956         case E_LEQ:
 957         case E_GTH:
 958         case E_GEQ:
 959         case E_EQUAL:
 960                 if (type == E_EQUAL) {
 961                         if (sym == &symbol_yes)
 962                                 return expr_copy(e);
 963                         if (sym == &symbol_mod)
 964                                 return expr_alloc_symbol(&symbol_no);
 965                         if (sym == &symbol_no)
 966                                 return expr_alloc_one(E_NOT, expr_copy(e));
 967                 } else {
 968                         if (sym == &symbol_yes)
 969                                 return expr_alloc_one(E_NOT, expr_copy(e));
 970                         if (sym == &symbol_mod)
 971                                 return expr_alloc_symbol(&symbol_yes);
 972                         if (sym == &symbol_no)
 973                                 return expr_copy(e);
 974                 }
 975                 break;
 976         case E_SYMBOL:
 977                 return expr_alloc_comp(type, e->left.sym, sym);
 978         case E_LIST:
 979         case E_RANGE:
 980         case E_NONE:
 981                 /* panic */;
 982         }
 983         return NULL;
 984 }
 985
 986 enum string_value_kind {
 987         k_string,
 988         k_signed,
 989         k_unsigned,
 990         k_invalid
 991 };
 992
 993 union string_value {
 994         unsigned long long u;
 995         signed long long s;
 996 };
 997
 998 static enum string_value_kind expr_parse_string(const char *str,
 999                                                 enum symbol_type type,
1000                                                 union string_value *val)
1001 {
1002         char *tail;
1003         enum string_value_kind kind;
1004
1005         errno = 0;
1006         switch (type) {
1007         case S_BOOLEAN:
1008         case S_TRISTATE:
1009                 val->s = !strcmp(str, "n") ? 0 :
1010                          !strcmp(str, "m") ? 1 :
1011                          !strcmp(str, "y") ? 2 : -1;
1012                 return k_signed;
1013         case S_INT:
1014                 val->s = strtoll(str, &tail, 10);
1015                 kind = k_signed;
1016                 break;
1017         case S_HEX:
1018                 val->u = strtoull(str, &tail, 16);
1019                 kind = k_unsigned;
1020                 break;
1021         case S_STRING:
1022         case S_UNKNOWN:
1023                 val->s = strtoll(str, &tail, 0);
1024                 kind = k_signed;
1025                 break;
1026         default:
1027                 return k_invalid;
1028         }
1029         return !errno && !*tail && tail > str && isxdigit(tail[-1])
1030                ? kind : k_string;
1031 }
1032
1033 tristate expr_calc_value(struct expr *e)
1034 {
1035         tristate val1, val2;
1036         const char *str1, *str2;
1037         enum string_value_kind k1 = k_string, k2 = k_string;
1038         union string_value lval = {}, rval = {};
1039         int res;
1040
1041         if (!e)
1042                 return yes;
1043
1044         switch (e->type) {
1045         case E_SYMBOL:
1046                 sym_calc_value(e->left.sym);
1047                 return e->left.sym->curr.tri;
1048         case E_AND:
1049                 val1 = expr_calc_value(e->left.expr);
1050                 val2 = expr_calc_value(e->right.expr);
1051                 return EXPR_AND(val1, val2);
1052         case E_OR:
1053                 val1 = expr_calc_value(e->left.expr);
1054                 val2 = expr_calc_value(e->right.expr);
1055                 return EXPR_OR(val1, val2);
1056         case E_NOT:
1057                 val1 = expr_calc_value(e->left.expr);
1058                 return EXPR_NOT(val1);
1059         case E_EQUAL:
1060         case E_GEQ:
1061         case E_GTH:
1062         case E_LEQ:
1063         case E_LTH:
1064         case E_UNEQUAL:
1065                 break;
1066         default:
1067                 printf("expr_calc_value: %d?\n", e->type);
1068                 return no;
1069         }
1070
1071         sym_calc_value(e->left.sym);
1072         sym_calc_value(e->right.sym);
1073         str1 = sym_get_string_value(e->left.sym);
1074         str2 = sym_get_string_value(e->right.sym);
1075
1076         if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
1077                 k1 = expr_parse_string(str1, e->left.sym->type, &lval);
1078                 k2 = expr_parse_string(str2, e->right.sym->type, &rval);
1079         }
1080
1081         if (k1 == k_string || k2 == k_string)
1082                 res = strcmp(str1, str2);
1083         else if (k1 == k_invalid || k2 == k_invalid) {
1084                 if (e->type != E_EQUAL && e->type != E_UNEQUAL) {
1085                         printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2);
1086                         return no;
1087                 }
1088                 res = strcmp(str1, str2);
1089         } else if (k1 == k_unsigned || k2 == k_unsigned)
1090                 res = (lval.u > rval.u) - (lval.u < rval.u);
1091         else /* if (k1 == k_signed && k2 == k_signed) */
1092                 res = (lval.s > rval.s) - (lval.s < rval.s);
1093
1094         switch(e->type) {
1095         case E_EQUAL:
1096                 return res ? no : yes;
1097         case E_GEQ:
1098                 return res >= 0 ? yes : no;
1099         case E_GTH:
1100                 return res > 0 ? yes : no;
1101         case E_LEQ:
1102                 return res <= 0 ? yes : no;
1103         case E_LTH:
1104                 return res < 0 ? yes : no;
1105         case E_UNEQUAL:
1106                 return res ? yes : no;
1107         default:
1108                 printf("expr_calc_value: relation %d?\n", e->type);
1109                 return no;
1110         }
1111 }
1112
1113 static int expr_compare_type(enum expr_type t1, enum expr_type t2)
1114 {
1115         if (t1 == t2)
1116                 return 0;
1117         switch (t1) {
1118         case E_LEQ:
1119         case E_LTH:
1120         case E_GEQ:
1121         case E_GTH:
1122                 if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1123                         return 1;
1124         case E_EQUAL:
1125         case E_UNEQUAL:
1126                 if (t2 == E_NOT)
1127                         return 1;
1128         case E_NOT:
1129                 if (t2 == E_AND)
1130                         return 1;
1131         case E_AND:
1132                 if (t2 == E_OR)
1133                         return 1;
1134         case E_OR:
1135                 if (t2 == E_LIST)
1136                         return 1;
1137         case E_LIST:
1138                 if (t2 == 0)
1139                         return 1;
1140         default:
1141                 return -1;
1142         }
1143         printf("[%dgt%d?]", t1, t2);
1144         return 0;
1145 }
1146
1147 void expr_print(struct expr *e,
1148                 void (*fn)(void *, struct symbol *, const char *),
1149                 void *data, int prevtoken)
1150 {
1151         if (!e) {
1152                 fn(data, NULL, "y");
1153                 return;
1154         }
1155
1156         if (expr_compare_type(prevtoken, e->type) > 0)
1157                 fn(data, NULL, "(");
1158         switch (e->type) {
1159         case E_SYMBOL:
1160                 if (e->left.sym->name)
1161                         fn(data, e->left.sym, e->left.sym->name);
1162                 else
1163                         fn(data, NULL, "<choice>");
1164                 break;
1165         case E_NOT:
1166                 fn(data, NULL, "!");
1167                 expr_print(e->left.expr, fn, data, E_NOT);
1168                 break;
1169         case E_EQUAL:
1170                 if (e->left.sym->name)
1171                         fn(data, e->left.sym, e->left.sym->name);
1172                 else
1173                         fn(data, NULL, "<choice>");
1174                 fn(data, NULL, "=");
1175                 fn(data, e->right.sym, e->right.sym->name);
1176                 break;
1177         case E_LEQ:
1178         case E_LTH:
1179                 if (e->left.sym->name)
1180                         fn(data, e->left.sym, e->left.sym->name);
1181                 else
1182                         fn(data, NULL, "<choice>");
1183                 fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1184                 fn(data, e->right.sym, e->right.sym->name);
1185                 break;
1186         case E_GEQ:
1187         case E_GTH:
1188                 if (e->left.sym->name)
1189                         fn(data, e->left.sym, e->left.sym->name);
1190                 else
1191                         fn(data, NULL, "<choice>");
1192                 fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1193                 fn(data, e->right.sym, e->right.sym->name);
1194                 break;
1195         case E_UNEQUAL:
1196                 if (e->left.sym->name)
1197                         fn(data, e->left.sym, e->left.sym->name);
1198                 else
1199                         fn(data, NULL, "<choice>");
1200                 fn(data, NULL, "!=");
1201                 fn(data, e->right.sym, e->right.sym->name);
1202                 break;
1203         case E_OR:
1204                 expr_print(e->left.expr, fn, data, E_OR);
1205                 fn(data, NULL, " || ");
1206                 expr_print(e->right.expr, fn, data, E_OR);
1207                 break;
1208         case E_AND:
1209                 expr_print(e->left.expr, fn, data, E_AND);
1210                 fn(data, NULL, " && ");
1211                 expr_print(e->right.expr, fn, data, E_AND);
1212                 break;
1213         case E_LIST:
1214                 fn(data, e->right.sym, e->right.sym->name);
1215                 if (e->left.expr) {
1216                         fn(data, NULL, " ^ ");
1217                         expr_print(e->left.expr, fn, data, E_LIST);
1218                 }
1219                 break;
1220         case E_RANGE:
1221                 fn(data, NULL, "[");
1222                 fn(data, e->left.sym, e->left.sym->name);
1223                 fn(data, NULL, " ");
1224                 fn(data, e->right.sym, e->right.sym->name);
1225                 fn(data, NULL, "]");
1226                 break;
1227         default:
1228           {
1229                 char buf[32];
1230                 sprintf(buf, "<unknown type %d>", e->type);
1231                 fn(data, NULL, buf);
1232                 break;
1233           }
1234         }
1235         if (expr_compare_type(prevtoken, e->type) > 0)
1236                 fn(data, NULL, ")");
1237 }
1238
1239 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1240 {
1241         xfwrite(str, strlen(str), 1, data);
1242 }
1243
1244 void expr_fprint(struct expr *e, FILE *out)
1245 {
1246         expr_print(e, expr_print_file_helper, out, E_NONE);
1247 }
1248
1249 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1250 {
1251         struct gstr *gs = (struct gstr*)data;
1252         const char *sym_str = NULL;
1253
1254         if (sym)
1255                 sym_str = sym_get_string_value(sym);
1256
1257         if (gs->max_width) {
1258                 unsigned extra_length = strlen(str);
1259                 const char *last_cr = strrchr(gs->s, '\n');
1260                 unsigned last_line_length;
1261
1262                 if (sym_str)
1263                         extra_length += 4 + strlen(sym_str);
1264
1265                 if (!last_cr)
1266                         last_cr = gs->s;
1267
1268                 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1269
1270                 if ((last_line_length + extra_length) > gs->max_width)
1271                         str_append(gs, "\\\n");
1272         }
1273
1274         str_append(gs, str);
1275         if (sym && sym->type != S_UNKNOWN)
1276                 str_printf(gs, " [=%s]", sym_str);
1277 }
1278
1279 void expr_gstr_print(struct expr *e, struct gstr *gs)
1280 {
1281         expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1282 }
1283
1284 /*
1285  * Transform the top level "||" tokens into newlines and prepend each
1286  * line with a minus. This makes expressions much easier to read.
1287  * Suitable for reverse dependency expressions.
1288  */
1289 static void expr_print_revdep(struct expr *e,
1290                               void (*fn)(void *, struct symbol *, const char *),
1291                               void *data, tristate pr_type, const char **title)
1292 {
1293         if (e->type == E_OR) {
1294                 expr_print_revdep(e->left.expr, fn, data, pr_type, title);
1295                 expr_print_revdep(e->right.expr, fn, data, pr_type, title);
1296         } else if (expr_calc_value(e) == pr_type) {
1297                 if (*title) {
1298                         fn(data, NULL, *title);
1299                         *title = NULL;
1300                 }
1301
1302                 fn(data, NULL, "  - ");
1303                 expr_print(e, fn, data, E_NONE);
1304                 fn(data, NULL, "\n");
1305         }
1306 }
1307
1308 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
1309                             tristate pr_type, const char *title)
1310 {
1311         expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);
1312 }