util/kconfig/expr.c

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