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