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_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 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 && 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 169 void 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 194 int 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 236 struct 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 */ 322 struct 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 */ 351 static 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 415 static 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 509 static 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 561 static 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 617 struct 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 641 struct 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 778 int 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 802 bool 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 831 struct 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 842 struct 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 853 void 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 882 struct 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 943 tristate 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 984 int 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 1016 void 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 1088 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) 1089 { 1090 fwrite(str, strlen(str), 1, data); 1091 } 1092 1093 void expr_fprint(struct expr *e, FILE *out) 1094 { 1095 expr_print(e, expr_print_file_helper, out, E_NONE); 1096 } 1097 1098 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) 1099 { 1100 str_append((struct gstr*)data, str); 1101 if (sym) 1102 str_printf((struct gstr*)data, " [=%s]", sym_get_string_value(sym)); 1103 } 1104 1105 void expr_gstr_print(struct expr *e, struct gstr *gs) 1106 { 1107 expr_print(e, expr_print_gstr_helper, gs, E_NONE); 1108 } 1109