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