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