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