scripts/kconfig/expr.c

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