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