scripts/kconfig/expr.c

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