scripts/config/expr.c

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