scripts/kconfig/expr.c

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