1 /* 2 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> 3 * Released under the terms of the GNU GPL v2.0. 4 */ 5 6 #include <stdio.h> 7 #include <stdlib.h> 8 #include <string.h> 9 10 #include "lkc.h" 11 12 #define DEBUG_EXPR 0 13 14 static int expr_eq(struct expr *e1, struct expr *e2); 15 static struct expr *expr_eliminate_yn(struct expr *e); 16 17 struct expr *expr_alloc_symbol(struct symbol *sym) 18 { 19 struct expr *e = xcalloc(1, sizeof(*e)); 20 e->type = E_SYMBOL; 21 e->left.sym = sym; 22 return e; 23 } 24 25 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) 26 { 27 struct expr *e = xcalloc(1, 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 = xcalloc(1, sizeof(*e)); 36 e->type = type; 37 e->left.expr = e1; 38 e->right.expr = e2; 39 return e; 40 } 41 42 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2) 43 { 44 struct expr *e = xcalloc(1, sizeof(*e)); 45 e->type = type; 46 e->left.sym = s1; 47 e->right.sym = s2; 48 return e; 49 } 50 51 struct 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 58 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2) 59 { 60 if (!e1) 61 return e2; 62 return e2 ? expr_alloc_two(E_OR, e1, e2) : e1; 63 } 64 65 struct expr *expr_copy(const struct expr *org) 66 { 67 struct expr *e; 68 69 if (!org) 70 return NULL; 71 72 e = xmalloc(sizeof(*org)); 73 memcpy(e, org, sizeof(*org)); 74 switch (org->type) { 75 case E_SYMBOL: 76 e->left = org->left; 77 break; 78 case E_NOT: 79 e->left.expr = expr_copy(org->left.expr); 80 break; 81 case E_EQUAL: 82 case E_GEQ: 83 case E_GTH: 84 case E_LEQ: 85 case E_LTH: 86 case E_UNEQUAL: 87 e->left.sym = org->left.sym; 88 e->right.sym = org->right.sym; 89 break; 90 case E_AND: 91 case E_OR: 92 case E_LIST: 93 e->left.expr = expr_copy(org->left.expr); 94 e->right.expr = expr_copy(org->right.expr); 95 break; 96 default: 97 fprintf(stderr, "can't copy type %d\n", e->type); 98 free(e); 99 e = NULL; 100 break; 101 } 102 103 return e; 104 } 105 106 void expr_free(struct expr *e) 107 { 108 if (!e) 109 return; 110 111 switch (e->type) { 112 case E_SYMBOL: 113 break; 114 case E_NOT: 115 expr_free(e->left.expr); 116 break; 117 case E_EQUAL: 118 case E_GEQ: 119 case E_GTH: 120 case E_LEQ: 121 case E_LTH: 122 case E_UNEQUAL: 123 break; 124 case E_OR: 125 case E_AND: 126 expr_free(e->left.expr); 127 expr_free(e->right.expr); 128 break; 129 default: 130 fprintf(stderr, "how to free type %d?\n", e->type); 131 break; 132 } 133 free(e); 134 } 135 136 static int trans_count; 137 138 #define e1 (*ep1) 139 #define e2 (*ep2) 140 141 /* 142 * expr_eliminate_eq() helper. 143 * 144 * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does 145 * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared 146 * against all other leaves. Two equal leaves are both replaced with either 'y' 147 * or 'n' as appropriate for 'type', to be eliminated later. 148 */ 149 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) 150 { 151 /* Recurse down to leaves */ 152 153 if (e1->type == type) { 154 __expr_eliminate_eq(type, &e1->left.expr, &e2); 155 __expr_eliminate_eq(type, &e1->right.expr, &e2); 156 return; 157 } 158 if (e2->type == type) { 159 __expr_eliminate_eq(type, &e1, &e2->left.expr); 160 __expr_eliminate_eq(type, &e1, &e2->right.expr); 161 return; 162 } 163 164 /* e1 and e2 are leaves. Compare them. */ 165 166 if (e1->type == E_SYMBOL && e2->type == E_SYMBOL && 167 e1->left.sym == e2->left.sym && 168 (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) 169 return; 170 if (!expr_eq(e1, e2)) 171 return; 172 173 /* e1 and e2 are equal leaves. Prepare them for elimination. */ 174 175 trans_count++; 176 expr_free(e1); expr_free(e2); 177 switch (type) { 178 case E_OR: 179 e1 = expr_alloc_symbol(&symbol_no); 180 e2 = expr_alloc_symbol(&symbol_no); 181 break; 182 case E_AND: 183 e1 = expr_alloc_symbol(&symbol_yes); 184 e2 = expr_alloc_symbol(&symbol_yes); 185 break; 186 default: 187 ; 188 } 189 } 190 191 /* 192 * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both. 193 * Example reductions: 194 * 195 * ep1: A && B -> ep1: y 196 * ep2: A && B && C -> ep2: C 197 * 198 * ep1: A || B -> ep1: n 199 * ep2: A || B || C -> ep2: C 200 * 201 * ep1: A && (B && FOO) -> ep1: FOO 202 * ep2: (BAR && B) && A -> ep2: BAR 203 * 204 * ep1: A && (B || C) -> ep1: y 205 * ep2: (C || B) && A -> ep2: y 206 * 207 * Comparisons are done between all operands at the same "level" of && or ||. 208 * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the 209 * following operands will be compared: 210 * 211 * - 'e1', 'e2 || e3', and 'e4 || e5', against each other 212 * - e2 against e3 213 * - e4 against e5 214 * 215 * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and 216 * '(e1 && e2) && e3' are both a single level. 217 * 218 * See __expr_eliminate_eq() as well. 219 */ 220 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) 221 { 222 if (!e1 || !e2) 223 return; 224 switch (e1->type) { 225 case E_OR: 226 case E_AND: 227 __expr_eliminate_eq(e1->type, ep1, ep2); 228 default: 229 ; 230 } 231 if (e1->type != e2->type) switch (e2->type) { 232 case E_OR: 233 case E_AND: 234 __expr_eliminate_eq(e2->type, ep1, ep2); 235 default: 236 ; 237 } 238 e1 = expr_eliminate_yn(e1); 239 e2 = expr_eliminate_yn(e2); 240 } 241 242 #undef e1 243 #undef e2 244 245 /* 246 * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two 247 * &&/|| expressions are considered equal if every operand in one expression 248 * equals some operand in the other (operands do not need to appear in the same 249 * order), recursively. 250 */ 251 static int expr_eq(struct expr *e1, struct expr *e2) 252 { 253 int res, old_count; 254 255 if (e1->type != e2->type) 256 return 0; 257 switch (e1->type) { 258 case E_EQUAL: 259 case E_GEQ: 260 case E_GTH: 261 case E_LEQ: 262 case E_LTH: 263 case E_UNEQUAL: 264 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym; 265 case E_SYMBOL: 266 return e1->left.sym == e2->left.sym; 267 case E_NOT: 268 return expr_eq(e1->left.expr, e2->left.expr); 269 case E_AND: 270 case E_OR: 271 e1 = expr_copy(e1); 272 e2 = expr_copy(e2); 273 old_count = trans_count; 274 expr_eliminate_eq(&e1, &e2); 275 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL && 276 e1->left.sym == e2->left.sym); 277 expr_free(e1); 278 expr_free(e2); 279 trans_count = old_count; 280 return res; 281 case E_LIST: 282 case E_RANGE: 283 case E_NONE: 284 /* panic */; 285 } 286 287 if (DEBUG_EXPR) { 288 expr_fprint(e1, stdout); 289 printf(" = "); 290 expr_fprint(e2, stdout); 291 printf(" ?\n"); 292 } 293 294 return 0; 295 } 296 297 /* 298 * Recursively performs the following simplifications in-place (as well as the 299 * corresponding simplifications with swapped operands): 300 * 301 * expr && n -> n 302 * expr && y -> expr 303 * expr || n -> expr 304 * expr || y -> y 305 * 306 * Returns the optimized expression. 307 */ 308 static struct expr *expr_eliminate_yn(struct expr *e) 309 { 310 struct expr *tmp; 311 312 if (e) switch (e->type) { 313 case E_AND: 314 e->left.expr = expr_eliminate_yn(e->left.expr); 315 e->right.expr = expr_eliminate_yn(e->right.expr); 316 if (e->left.expr->type == E_SYMBOL) { 317 if (e->left.expr->left.sym == &symbol_no) { 318 expr_free(e->left.expr); 319 expr_free(e->right.expr); 320 e->type = E_SYMBOL; 321 e->left.sym = &symbol_no; 322 e->right.expr = NULL; 323 return e; 324 } else if (e->left.expr->left.sym == &symbol_yes) { 325 free(e->left.expr); 326 tmp = e->right.expr; 327 *e = *(e->right.expr); 328 free(tmp); 329 return e; 330 } 331 } 332 if (e->right.expr->type == E_SYMBOL) { 333 if (e->right.expr->left.sym == &symbol_no) { 334 expr_free(e->left.expr); 335 expr_free(e->right.expr); 336 e->type = E_SYMBOL; 337 e->left.sym = &symbol_no; 338 e->right.expr = NULL; 339 return e; 340 } else if (e->right.expr->left.sym == &symbol_yes) { 341 free(e->right.expr); 342 tmp = e->left.expr; 343 *e = *(e->left.expr); 344 free(tmp); 345 return e; 346 } 347 } 348 break; 349 case E_OR: 350 e->left.expr = expr_eliminate_yn(e->left.expr); 351 e->right.expr = expr_eliminate_yn(e->right.expr); 352 if (e->left.expr->type == E_SYMBOL) { 353 if (e->left.expr->left.sym == &symbol_no) { 354 free(e->left.expr); 355 tmp = e->right.expr; 356 *e = *(e->right.expr); 357 free(tmp); 358 return e; 359 } else if (e->left.expr->left.sym == &symbol_yes) { 360 expr_free(e->left.expr); 361 expr_free(e->right.expr); 362 e->type = E_SYMBOL; 363 e->left.sym = &symbol_yes; 364 e->right.expr = NULL; 365 return e; 366 } 367 } 368 if (e->right.expr->type == E_SYMBOL) { 369 if (e->right.expr->left.sym == &symbol_no) { 370 free(e->right.expr); 371 tmp = e->left.expr; 372 *e = *(e->left.expr); 373 free(tmp); 374 return e; 375 } else if (e->right.expr->left.sym == &symbol_yes) { 376 expr_free(e->left.expr); 377 expr_free(e->right.expr); 378 e->type = E_SYMBOL; 379 e->left.sym = &symbol_yes; 380 e->right.expr = NULL; 381 return e; 382 } 383 } 384 break; 385 default: 386 ; 387 } 388 return e; 389 } 390 391 /* 392 * bool FOO!=n => FOO 393 */ 394 struct expr *expr_trans_bool(struct expr *e) 395 { 396 if (!e) 397 return NULL; 398 switch (e->type) { 399 case E_AND: 400 case E_OR: 401 case E_NOT: 402 e->left.expr = expr_trans_bool(e->left.expr); 403 e->right.expr = expr_trans_bool(e->right.expr); 404 break; 405 case E_UNEQUAL: 406 // FOO!=n -> FOO 407 if (e->left.sym->type == S_TRISTATE) { 408 if (e->right.sym == &symbol_no) { 409 e->type = E_SYMBOL; 410 e->right.sym = NULL; 411 } 412 } 413 break; 414 default: 415 ; 416 } 417 return e; 418 } 419 420 /* 421 * e1 || e2 -> ? 422 */ 423 static struct expr *expr_join_or(struct expr *e1, struct expr *e2) 424 { 425 struct expr *tmp; 426 struct symbol *sym1, *sym2; 427 428 if (expr_eq(e1, e2)) 429 return expr_copy(e1); 430 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) 431 return NULL; 432 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) 433 return NULL; 434 if (e1->type == E_NOT) { 435 tmp = e1->left.expr; 436 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) 437 return NULL; 438 sym1 = tmp->left.sym; 439 } else 440 sym1 = e1->left.sym; 441 if (e2->type == E_NOT) { 442 if (e2->left.expr->type != E_SYMBOL) 443 return NULL; 444 sym2 = e2->left.expr->left.sym; 445 } else 446 sym2 = e2->left.sym; 447 if (sym1 != sym2) 448 return NULL; 449 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) 450 return NULL; 451 if (sym1->type == S_TRISTATE) { 452 if (e1->type == E_EQUAL && e2->type == E_EQUAL && 453 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || 454 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) { 455 // (a='y') || (a='m') -> (a!='n') 456 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no); 457 } 458 if (e1->type == E_EQUAL && e2->type == E_EQUAL && 459 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || 460 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) { 461 // (a='y') || (a='n') -> (a!='m') 462 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod); 463 } 464 if (e1->type == E_EQUAL && e2->type == E_EQUAL && 465 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || 466 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) { 467 // (a='m') || (a='n') -> (a!='y') 468 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes); 469 } 470 } 471 if (sym1->type == S_BOOLEAN && sym1 == sym2) { 472 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) || 473 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL)) 474 return expr_alloc_symbol(&symbol_yes); 475 } 476 477 if (DEBUG_EXPR) { 478 printf("optimize ("); 479 expr_fprint(e1, stdout); 480 printf(") || ("); 481 expr_fprint(e2, stdout); 482 printf(")?\n"); 483 } 484 return NULL; 485 } 486 487 static struct expr *expr_join_and(struct expr *e1, struct expr *e2) 488 { 489 struct expr *tmp; 490 struct symbol *sym1, *sym2; 491 492 if (expr_eq(e1, e2)) 493 return expr_copy(e1); 494 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) 495 return NULL; 496 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) 497 return NULL; 498 if (e1->type == E_NOT) { 499 tmp = e1->left.expr; 500 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) 501 return NULL; 502 sym1 = tmp->left.sym; 503 } else 504 sym1 = e1->left.sym; 505 if (e2->type == E_NOT) { 506 if (e2->left.expr->type != E_SYMBOL) 507 return NULL; 508 sym2 = e2->left.expr->left.sym; 509 } else 510 sym2 = e2->left.sym; 511 if (sym1 != sym2) 512 return NULL; 513 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) 514 return NULL; 515 516 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) || 517 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes)) 518 // (a) && (a='y') -> (a='y') 519 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); 520 521 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) || 522 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no)) 523 // (a) && (a!='n') -> (a) 524 return expr_alloc_symbol(sym1); 525 526 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) || 527 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod)) 528 // (a) && (a!='m') -> (a='y') 529 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); 530 531 if (sym1->type == S_TRISTATE) { 532 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) { 533 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' 534 sym2 = e1->right.sym; 535 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) 536 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) 537 : expr_alloc_symbol(&symbol_no); 538 } 539 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) { 540 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' 541 sym2 = e2->right.sym; 542 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) 543 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) 544 : expr_alloc_symbol(&symbol_no); 545 } 546 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && 547 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || 548 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) 549 // (a!='y') && (a!='n') -> (a='m') 550 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod); 551 552 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && 553 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || 554 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) 555 // (a!='y') && (a!='m') -> (a='n') 556 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no); 557 558 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && 559 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || 560 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) 561 // (a!='m') && (a!='n') -> (a='m') 562 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); 563 564 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) || 565 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) || 566 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) || 567 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes)) 568 return NULL; 569 } 570 571 if (DEBUG_EXPR) { 572 printf("optimize ("); 573 expr_fprint(e1, stdout); 574 printf(") && ("); 575 expr_fprint(e2, stdout); 576 printf(")?\n"); 577 } 578 return NULL; 579 } 580 581 /* 582 * expr_eliminate_dups() helper. 583 * 584 * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does 585 * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared 586 * against all other leaves to look for simplifications. 587 */ 588 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2) 589 { 590 #define e1 (*ep1) 591 #define e2 (*ep2) 592 struct expr *tmp; 593 594 /* Recurse down to leaves */ 595 596 if (e1->type == type) { 597 expr_eliminate_dups1(type, &e1->left.expr, &e2); 598 expr_eliminate_dups1(type, &e1->right.expr, &e2); 599 return; 600 } 601 if (e2->type == type) { 602 expr_eliminate_dups1(type, &e1, &e2->left.expr); 603 expr_eliminate_dups1(type, &e1, &e2->right.expr); 604 return; 605 } 606 607 /* e1 and e2 are leaves. Compare and process them. */ 608 609 if (e1 == e2) 610 return; 611 612 switch (e1->type) { 613 case E_OR: case E_AND: 614 expr_eliminate_dups1(e1->type, &e1, &e1); 615 default: 616 ; 617 } 618 619 switch (type) { 620 case E_OR: 621 tmp = expr_join_or(e1, e2); 622 if (tmp) { 623 expr_free(e1); expr_free(e2); 624 e1 = expr_alloc_symbol(&symbol_no); 625 e2 = tmp; 626 trans_count++; 627 } 628 break; 629 case E_AND: 630 tmp = expr_join_and(e1, e2); 631 if (tmp) { 632 expr_free(e1); expr_free(e2); 633 e1 = expr_alloc_symbol(&symbol_yes); 634 e2 = tmp; 635 trans_count++; 636 } 637 break; 638 default: 639 ; 640 } 641 #undef e1 642 #undef e2 643 } 644 645 /* 646 * Rewrites 'e' in-place to remove ("join") duplicate and other redundant 647 * operands. 648 * 649 * Example simplifications: 650 * 651 * A || B || A -> A || B 652 * A && B && A=y -> A=y && B 653 * 654 * Returns the deduplicated expression. 655 */ 656 struct expr *expr_eliminate_dups(struct expr *e) 657 { 658 int oldcount; 659 if (!e) 660 return e; 661 662 oldcount = trans_count; 663 while (1) { 664 trans_count = 0; 665 switch (e->type) { 666 case E_OR: case E_AND: 667 expr_eliminate_dups1(e->type, &e, &e); 668 default: 669 ; 670 } 671 if (!trans_count) 672 /* No simplifications done in this pass. We're done */ 673 break; 674 e = expr_eliminate_yn(e); 675 } 676 trans_count = oldcount; 677 return e; 678 } 679 680 /* 681 * Performs various simplifications involving logical operators and 682 * comparisons. 683 * 684 * Allocates and returns a new expression. 685 */ 686 struct expr *expr_transform(struct expr *e) 687 { 688 struct expr *tmp; 689 690 if (!e) 691 return NULL; 692 switch (e->type) { 693 case E_EQUAL: 694 case E_GEQ: 695 case E_GTH: 696 case E_LEQ: 697 case E_LTH: 698 case E_UNEQUAL: 699 case E_SYMBOL: 700 case E_LIST: 701 break; 702 default: 703 e->left.expr = expr_transform(e->left.expr); 704 e->right.expr = expr_transform(e->right.expr); 705 } 706 707 switch (e->type) { 708 case E_EQUAL: 709 if (e->left.sym->type != S_BOOLEAN) 710 break; 711 if (e->right.sym == &symbol_no) { 712 e->type = E_NOT; 713 e->left.expr = expr_alloc_symbol(e->left.sym); 714 e->right.sym = NULL; 715 break; 716 } 717 if (e->right.sym == &symbol_mod) { 718 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); 719 e->type = E_SYMBOL; 720 e->left.sym = &symbol_no; 721 e->right.sym = NULL; 722 break; 723 } 724 if (e->right.sym == &symbol_yes) { 725 e->type = E_SYMBOL; 726 e->right.sym = NULL; 727 break; 728 } 729 break; 730 case E_UNEQUAL: 731 if (e->left.sym->type != S_BOOLEAN) 732 break; 733 if (e->right.sym == &symbol_no) { 734 e->type = E_SYMBOL; 735 e->right.sym = NULL; 736 break; 737 } 738 if (e->right.sym == &symbol_mod) { 739 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); 740 e->type = E_SYMBOL; 741 e->left.sym = &symbol_yes; 742 e->right.sym = NULL; 743 break; 744 } 745 if (e->right.sym == &symbol_yes) { 746 e->type = E_NOT; 747 e->left.expr = expr_alloc_symbol(e->left.sym); 748 e->right.sym = NULL; 749 break; 750 } 751 break; 752 case E_NOT: 753 switch (e->left.expr->type) { 754 case E_NOT: 755 // !!a -> a 756 tmp = e->left.expr->left.expr; 757 free(e->left.expr); 758 free(e); 759 e = tmp; 760 e = expr_transform(e); 761 break; 762 case E_EQUAL: 763 case E_UNEQUAL: 764 // !a='x' -> a!='x' 765 tmp = e->left.expr; 766 free(e); 767 e = tmp; 768 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL; 769 break; 770 case E_LEQ: 771 case E_GEQ: 772 // !a<='x' -> a>'x' 773 tmp = e->left.expr; 774 free(e); 775 e = tmp; 776 e->type = e->type == E_LEQ ? E_GTH : E_LTH; 777 break; 778 case E_LTH: 779 case E_GTH: 780 // !a<'x' -> a>='x' 781 tmp = e->left.expr; 782 free(e); 783 e = tmp; 784 e->type = e->type == E_LTH ? E_GEQ : E_LEQ; 785 break; 786 case E_OR: 787 // !(a || b) -> !a && !b 788 tmp = e->left.expr; 789 e->type = E_AND; 790 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); 791 tmp->type = E_NOT; 792 tmp->right.expr = NULL; 793 e = expr_transform(e); 794 break; 795 case E_AND: 796 // !(a && b) -> !a || !b 797 tmp = e->left.expr; 798 e->type = E_OR; 799 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); 800 tmp->type = E_NOT; 801 tmp->right.expr = NULL; 802 e = expr_transform(e); 803 break; 804 case E_SYMBOL: 805 if (e->left.expr->left.sym == &symbol_yes) { 806 // !'y' -> 'n' 807 tmp = e->left.expr; 808 free(e); 809 e = tmp; 810 e->type = E_SYMBOL; 811 e->left.sym = &symbol_no; 812 break; 813 } 814 if (e->left.expr->left.sym == &symbol_mod) { 815 // !'m' -> 'm' 816 tmp = e->left.expr; 817 free(e); 818 e = tmp; 819 e->type = E_SYMBOL; 820 e->left.sym = &symbol_mod; 821 break; 822 } 823 if (e->left.expr->left.sym == &symbol_no) { 824 // !'n' -> 'y' 825 tmp = e->left.expr; 826 free(e); 827 e = tmp; 828 e->type = E_SYMBOL; 829 e->left.sym = &symbol_yes; 830 break; 831 } 832 break; 833 default: 834 ; 835 } 836 break; 837 default: 838 ; 839 } 840 return e; 841 } 842 843 int expr_contains_symbol(struct expr *dep, struct symbol *sym) 844 { 845 if (!dep) 846 return 0; 847 848 switch (dep->type) { 849 case E_AND: 850 case E_OR: 851 return expr_contains_symbol(dep->left.expr, sym) || 852 expr_contains_symbol(dep->right.expr, sym); 853 case E_SYMBOL: 854 return dep->left.sym == sym; 855 case E_EQUAL: 856 case E_GEQ: 857 case E_GTH: 858 case E_LEQ: 859 case E_LTH: 860 case E_UNEQUAL: 861 return dep->left.sym == sym || 862 dep->right.sym == sym; 863 case E_NOT: 864 return expr_contains_symbol(dep->left.expr, sym); 865 default: 866 ; 867 } 868 return 0; 869 } 870 871 bool expr_depends_symbol(struct expr *dep, struct symbol *sym) 872 { 873 if (!dep) 874 return false; 875 876 switch (dep->type) { 877 case E_AND: 878 return expr_depends_symbol(dep->left.expr, sym) || 879 expr_depends_symbol(dep->right.expr, sym); 880 case E_SYMBOL: 881 return dep->left.sym == sym; 882 case E_EQUAL: 883 if (dep->left.sym == sym) { 884 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod) 885 return true; 886 } 887 break; 888 case E_UNEQUAL: 889 if (dep->left.sym == sym) { 890 if (dep->right.sym == &symbol_no) 891 return true; 892 } 893 break; 894 default: 895 ; 896 } 897 return false; 898 } 899 900 /* 901 * Inserts explicit comparisons of type 'type' to symbol 'sym' into the 902 * expression 'e'. 903 * 904 * Examples transformations for type == E_UNEQUAL, sym == &symbol_no: 905 * 906 * A -> A!=n 907 * !A -> A=n 908 * A && B -> !(A=n || B=n) 909 * A || B -> !(A=n && B=n) 910 * A && (B || C) -> !(A=n || (B=n && C=n)) 911 * 912 * Allocates and returns a new expression. 913 */ 914 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) 915 { 916 struct expr *e1, *e2; 917 918 if (!e) { 919 e = expr_alloc_symbol(sym); 920 if (type == E_UNEQUAL) 921 e = expr_alloc_one(E_NOT, e); 922 return e; 923 } 924 switch (e->type) { 925 case E_AND: 926 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); 927 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); 928 if (sym == &symbol_yes) 929 e = expr_alloc_two(E_AND, e1, e2); 930 if (sym == &symbol_no) 931 e = expr_alloc_two(E_OR, e1, e2); 932 if (type == E_UNEQUAL) 933 e = expr_alloc_one(E_NOT, e); 934 return e; 935 case E_OR: 936 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); 937 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); 938 if (sym == &symbol_yes) 939 e = expr_alloc_two(E_OR, e1, e2); 940 if (sym == &symbol_no) 941 e = expr_alloc_two(E_AND, e1, e2); 942 if (type == E_UNEQUAL) 943 e = expr_alloc_one(E_NOT, e); 944 return e; 945 case E_NOT: 946 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym); 947 case E_UNEQUAL: 948 case E_LTH: 949 case E_LEQ: 950 case E_GTH: 951 case E_GEQ: 952 case E_EQUAL: 953 if (type == E_EQUAL) { 954 if (sym == &symbol_yes) 955 return expr_copy(e); 956 if (sym == &symbol_mod) 957 return expr_alloc_symbol(&symbol_no); 958 if (sym == &symbol_no) 959 return expr_alloc_one(E_NOT, expr_copy(e)); 960 } else { 961 if (sym == &symbol_yes) 962 return expr_alloc_one(E_NOT, expr_copy(e)); 963 if (sym == &symbol_mod) 964 return expr_alloc_symbol(&symbol_yes); 965 if (sym == &symbol_no) 966 return expr_copy(e); 967 } 968 break; 969 case E_SYMBOL: 970 return expr_alloc_comp(type, e->left.sym, sym); 971 case E_LIST: 972 case E_RANGE: 973 case E_NONE: 974 /* panic */; 975 } 976 return NULL; 977 } 978 979 enum string_value_kind { 980 k_string, 981 k_signed, 982 k_unsigned, 983 k_invalid 984 }; 985 986 union string_value { 987 unsigned long long u; 988 signed long long s; 989 }; 990 991 static enum string_value_kind expr_parse_string(const char *str, 992 enum symbol_type type, 993 union string_value *val) 994 { 995 char *tail; 996 enum string_value_kind kind; 997 998 errno = 0; 999 switch (type) { 1000 case S_BOOLEAN: 1001 case S_TRISTATE: 1002 val->s = !strcmp(str, "n") ? 0 : 1003 !strcmp(str, "m") ? 1 : 1004 !strcmp(str, "y") ? 2 : -1; 1005 return k_signed; 1006 case S_INT: 1007 val->s = strtoll(str, &tail, 10); 1008 kind = k_signed; 1009 break; 1010 case S_HEX: 1011 val->u = strtoull(str, &tail, 16); 1012 kind = k_unsigned; 1013 break; 1014 case S_STRING: 1015 case S_UNKNOWN: 1016 val->s = strtoll(str, &tail, 0); 1017 kind = k_signed; 1018 break; 1019 default: 1020 return k_invalid; 1021 } 1022 return !errno && !*tail && tail > str && isxdigit(tail[-1]) 1023 ? kind : k_string; 1024 } 1025 1026 tristate expr_calc_value(struct expr *e) 1027 { 1028 tristate val1, val2; 1029 const char *str1, *str2; 1030 enum string_value_kind k1 = k_string, k2 = k_string; 1031 union string_value lval = {}, rval = {}; 1032 int res; 1033 1034 if (!e) 1035 return yes; 1036 1037 switch (e->type) { 1038 case E_SYMBOL: 1039 sym_calc_value(e->left.sym); 1040 return e->left.sym->curr.tri; 1041 case E_AND: 1042 val1 = expr_calc_value(e->left.expr); 1043 val2 = expr_calc_value(e->right.expr); 1044 return EXPR_AND(val1, val2); 1045 case E_OR: 1046 val1 = expr_calc_value(e->left.expr); 1047 val2 = expr_calc_value(e->right.expr); 1048 return EXPR_OR(val1, val2); 1049 case E_NOT: 1050 val1 = expr_calc_value(e->left.expr); 1051 return EXPR_NOT(val1); 1052 case E_EQUAL: 1053 case E_GEQ: 1054 case E_GTH: 1055 case E_LEQ: 1056 case E_LTH: 1057 case E_UNEQUAL: 1058 break; 1059 default: 1060 printf("expr_calc_value: %d?\n", e->type); 1061 return no; 1062 } 1063 1064 sym_calc_value(e->left.sym); 1065 sym_calc_value(e->right.sym); 1066 str1 = sym_get_string_value(e->left.sym); 1067 str2 = sym_get_string_value(e->right.sym); 1068 1069 if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) { 1070 k1 = expr_parse_string(str1, e->left.sym->type, &lval); 1071 k2 = expr_parse_string(str2, e->right.sym->type, &rval); 1072 } 1073 1074 if (k1 == k_string || k2 == k_string) 1075 res = strcmp(str1, str2); 1076 else if (k1 == k_invalid || k2 == k_invalid) { 1077 if (e->type != E_EQUAL && e->type != E_UNEQUAL) { 1078 printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2); 1079 return no; 1080 } 1081 res = strcmp(str1, str2); 1082 } else if (k1 == k_unsigned || k2 == k_unsigned) 1083 res = (lval.u > rval.u) - (lval.u < rval.u); 1084 else /* if (k1 == k_signed && k2 == k_signed) */ 1085 res = (lval.s > rval.s) - (lval.s < rval.s); 1086 1087 switch(e->type) { 1088 case E_EQUAL: 1089 return res ? no : yes; 1090 case E_GEQ: 1091 return res >= 0 ? yes : no; 1092 case E_GTH: 1093 return res > 0 ? yes : no; 1094 case E_LEQ: 1095 return res <= 0 ? yes : no; 1096 case E_LTH: 1097 return res < 0 ? yes : no; 1098 case E_UNEQUAL: 1099 return res ? yes : no; 1100 default: 1101 printf("expr_calc_value: relation %d?\n", e->type); 1102 return no; 1103 } 1104 } 1105 1106 static int expr_compare_type(enum expr_type t1, enum expr_type t2) 1107 { 1108 if (t1 == t2) 1109 return 0; 1110 switch (t1) { 1111 case E_LEQ: 1112 case E_LTH: 1113 case E_GEQ: 1114 case E_GTH: 1115 if (t2 == E_EQUAL || t2 == E_UNEQUAL) 1116 return 1; 1117 case E_EQUAL: 1118 case E_UNEQUAL: 1119 if (t2 == E_NOT) 1120 return 1; 1121 case E_NOT: 1122 if (t2 == E_AND) 1123 return 1; 1124 case E_AND: 1125 if (t2 == E_OR) 1126 return 1; 1127 case E_OR: 1128 if (t2 == E_LIST) 1129 return 1; 1130 case E_LIST: 1131 if (t2 == 0) 1132 return 1; 1133 default: 1134 return -1; 1135 } 1136 printf("[%dgt%d?]", t1, t2); 1137 return 0; 1138 } 1139 1140 void expr_print(struct expr *e, 1141 void (*fn)(void *, struct symbol *, const char *), 1142 void *data, int prevtoken) 1143 { 1144 if (!e) { 1145 fn(data, NULL, "y"); 1146 return; 1147 } 1148 1149 if (expr_compare_type(prevtoken, e->type) > 0) 1150 fn(data, NULL, "("); 1151 switch (e->type) { 1152 case E_SYMBOL: 1153 if (e->left.sym->name) 1154 fn(data, e->left.sym, e->left.sym->name); 1155 else 1156 fn(data, NULL, "<choice>"); 1157 break; 1158 case E_NOT: 1159 fn(data, NULL, "!"); 1160 expr_print(e->left.expr, fn, data, E_NOT); 1161 break; 1162 case E_EQUAL: 1163 if (e->left.sym->name) 1164 fn(data, e->left.sym, e->left.sym->name); 1165 else 1166 fn(data, NULL, "<choice>"); 1167 fn(data, NULL, "="); 1168 fn(data, e->right.sym, e->right.sym->name); 1169 break; 1170 case E_LEQ: 1171 case E_LTH: 1172 if (e->left.sym->name) 1173 fn(data, e->left.sym, e->left.sym->name); 1174 else 1175 fn(data, NULL, "<choice>"); 1176 fn(data, NULL, e->type == E_LEQ ? "<=" : "<"); 1177 fn(data, e->right.sym, e->right.sym->name); 1178 break; 1179 case E_GEQ: 1180 case E_GTH: 1181 if (e->left.sym->name) 1182 fn(data, e->left.sym, e->left.sym->name); 1183 else 1184 fn(data, NULL, "<choice>"); 1185 fn(data, NULL, e->type == E_GEQ ? ">=" : ">"); 1186 fn(data, e->right.sym, e->right.sym->name); 1187 break; 1188 case E_UNEQUAL: 1189 if (e->left.sym->name) 1190 fn(data, e->left.sym, e->left.sym->name); 1191 else 1192 fn(data, NULL, "<choice>"); 1193 fn(data, NULL, "!="); 1194 fn(data, e->right.sym, e->right.sym->name); 1195 break; 1196 case E_OR: 1197 expr_print(e->left.expr, fn, data, E_OR); 1198 fn(data, NULL, " || "); 1199 expr_print(e->right.expr, fn, data, E_OR); 1200 break; 1201 case E_AND: 1202 expr_print(e->left.expr, fn, data, E_AND); 1203 fn(data, NULL, " && "); 1204 expr_print(e->right.expr, fn, data, E_AND); 1205 break; 1206 case E_LIST: 1207 fn(data, e->right.sym, e->right.sym->name); 1208 if (e->left.expr) { 1209 fn(data, NULL, " ^ "); 1210 expr_print(e->left.expr, fn, data, E_LIST); 1211 } 1212 break; 1213 case E_RANGE: 1214 fn(data, NULL, "["); 1215 fn(data, e->left.sym, e->left.sym->name); 1216 fn(data, NULL, " "); 1217 fn(data, e->right.sym, e->right.sym->name); 1218 fn(data, NULL, "]"); 1219 break; 1220 default: 1221 { 1222 char buf[32]; 1223 sprintf(buf, "<unknown type %d>", e->type); 1224 fn(data, NULL, buf); 1225 break; 1226 } 1227 } 1228 if (expr_compare_type(prevtoken, e->type) > 0) 1229 fn(data, NULL, ")"); 1230 } 1231 1232 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) 1233 { 1234 xfwrite(str, strlen(str), 1, data); 1235 } 1236 1237 void expr_fprint(struct expr *e, FILE *out) 1238 { 1239 expr_print(e, expr_print_file_helper, out, E_NONE); 1240 } 1241 1242 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) 1243 { 1244 struct gstr *gs = (struct gstr*)data; 1245 const char *sym_str = NULL; 1246 1247 if (sym) 1248 sym_str = sym_get_string_value(sym); 1249 1250 if (gs->max_width) { 1251 unsigned extra_length = strlen(str); 1252 const char *last_cr = strrchr(gs->s, '\n'); 1253 unsigned last_line_length; 1254 1255 if (sym_str) 1256 extra_length += 4 + strlen(sym_str); 1257 1258 if (!last_cr) 1259 last_cr = gs->s; 1260 1261 last_line_length = strlen(gs->s) - (last_cr - gs->s); 1262 1263 if ((last_line_length + extra_length) > gs->max_width) 1264 str_append(gs, "\\\n"); 1265 } 1266 1267 str_append(gs, str); 1268 if (sym && sym->type != S_UNKNOWN) 1269 str_printf(gs, " [=%s]", sym_str); 1270 } 1271 1272 void expr_gstr_print(struct expr *e, struct gstr *gs) 1273 { 1274 expr_print(e, expr_print_gstr_helper, gs, E_NONE); 1275 } 1276 1277 /* 1278 * Transform the top level "||" tokens into newlines and prepend each 1279 * line with a minus. This makes expressions much easier to read. 1280 * Suitable for reverse dependency expressions. 1281 */ 1282 static void expr_print_revdep(struct expr *e, 1283 void (*fn)(void *, struct symbol *, const char *), 1284 void *data, tristate pr_type, const char **title) 1285 { 1286 if (e->type == E_OR) { 1287 expr_print_revdep(e->left.expr, fn, data, pr_type, title); 1288 expr_print_revdep(e->right.expr, fn, data, pr_type, title); 1289 } else if (expr_calc_value(e) == pr_type) { 1290 if (*title) { 1291 fn(data, NULL, *title); 1292 *title = NULL; 1293 } 1294 1295 fn(data, NULL, " - "); 1296 expr_print(e, fn, data, E_NONE); 1297 fn(data, NULL, "\n"); 1298 } 1299 } 1300 1301 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs, 1302 tristate pr_type, const char *title) 1303 { 1304 expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title); 1305 } 1306