scripts/kconfig/expr.c

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