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