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