scripts/kconfig/expr.c

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