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