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