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