scripts/kconfig/expr.c

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