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 do { 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 e = expr_eliminate_yn(e); 649 } while (trans_count); /* repeat until we get no more simplifications */ 650 trans_count = oldcount; 651 return e; 652 } 653 654 /* 655 * Performs various simplifications involving logical operators and 656 * comparisons. 657 * 658 * Allocates and returns a new expression. 659 */ 660 struct expr *expr_transform(struct expr *e) 661 { 662 struct expr *tmp; 663 664 if (!e) 665 return NULL; 666 switch (e->type) { 667 case E_EQUAL: 668 case E_GEQ: 669 case E_GTH: 670 case E_LEQ: 671 case E_LTH: 672 case E_UNEQUAL: 673 case E_SYMBOL: 674 break; 675 default: 676 e->left.expr = expr_transform(e->left.expr); 677 e->right.expr = expr_transform(e->right.expr); 678 } 679 680 switch (e->type) { 681 case E_EQUAL: 682 if (e->left.sym->type != S_BOOLEAN) 683 break; 684 if (e->right.sym == &symbol_no) { 685 e->type = E_NOT; 686 e->left.expr = expr_alloc_symbol(e->left.sym); 687 e->right.sym = NULL; 688 break; 689 } 690 if (e->right.sym == &symbol_mod) { 691 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); 692 e->type = E_SYMBOL; 693 e->left.sym = &symbol_no; 694 e->right.sym = NULL; 695 break; 696 } 697 if (e->right.sym == &symbol_yes) { 698 e->type = E_SYMBOL; 699 e->right.sym = NULL; 700 break; 701 } 702 break; 703 case E_UNEQUAL: 704 if (e->left.sym->type != S_BOOLEAN) 705 break; 706 if (e->right.sym == &symbol_no) { 707 e->type = E_SYMBOL; 708 e->right.sym = NULL; 709 break; 710 } 711 if (e->right.sym == &symbol_mod) { 712 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); 713 e->type = E_SYMBOL; 714 e->left.sym = &symbol_yes; 715 e->right.sym = NULL; 716 break; 717 } 718 if (e->right.sym == &symbol_yes) { 719 e->type = E_NOT; 720 e->left.expr = expr_alloc_symbol(e->left.sym); 721 e->right.sym = NULL; 722 break; 723 } 724 break; 725 case E_NOT: 726 switch (e->left.expr->type) { 727 case E_NOT: 728 // !!a -> a 729 tmp = e->left.expr->left.expr; 730 free(e->left.expr); 731 free(e); 732 e = tmp; 733 e = expr_transform(e); 734 break; 735 case E_EQUAL: 736 case E_UNEQUAL: 737 // !a='x' -> a!='x' 738 tmp = e->left.expr; 739 free(e); 740 e = tmp; 741 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL; 742 break; 743 case E_LEQ: 744 case E_GEQ: 745 // !a<='x' -> a>'x' 746 tmp = e->left.expr; 747 free(e); 748 e = tmp; 749 e->type = e->type == E_LEQ ? E_GTH : E_LTH; 750 break; 751 case E_LTH: 752 case E_GTH: 753 // !a<'x' -> a>='x' 754 tmp = e->left.expr; 755 free(e); 756 e = tmp; 757 e->type = e->type == E_LTH ? E_GEQ : E_LEQ; 758 break; 759 case E_OR: 760 // !(a || b) -> !a && !b 761 tmp = e->left.expr; 762 e->type = E_AND; 763 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); 764 tmp->type = E_NOT; 765 tmp->right.expr = NULL; 766 e = expr_transform(e); 767 break; 768 case E_AND: 769 // !(a && b) -> !a || !b 770 tmp = e->left.expr; 771 e->type = E_OR; 772 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); 773 tmp->type = E_NOT; 774 tmp->right.expr = NULL; 775 e = expr_transform(e); 776 break; 777 case E_SYMBOL: 778 if (e->left.expr->left.sym == &symbol_yes) { 779 // !'y' -> 'n' 780 tmp = e->left.expr; 781 free(e); 782 e = tmp; 783 e->type = E_SYMBOL; 784 e->left.sym = &symbol_no; 785 break; 786 } 787 if (e->left.expr->left.sym == &symbol_mod) { 788 // !'m' -> 'm' 789 tmp = e->left.expr; 790 free(e); 791 e = tmp; 792 e->type = E_SYMBOL; 793 e->left.sym = &symbol_mod; 794 break; 795 } 796 if (e->left.expr->left.sym == &symbol_no) { 797 // !'n' -> 'y' 798 tmp = e->left.expr; 799 free(e); 800 e = tmp; 801 e->type = E_SYMBOL; 802 e->left.sym = &symbol_yes; 803 break; 804 } 805 break; 806 default: 807 ; 808 } 809 break; 810 default: 811 ; 812 } 813 return e; 814 } 815 816 int expr_contains_symbol(struct expr *dep, struct symbol *sym) 817 { 818 if (!dep) 819 return 0; 820 821 switch (dep->type) { 822 case E_AND: 823 case E_OR: 824 return expr_contains_symbol(dep->left.expr, sym) || 825 expr_contains_symbol(dep->right.expr, sym); 826 case E_SYMBOL: 827 return dep->left.sym == sym; 828 case E_EQUAL: 829 case E_GEQ: 830 case E_GTH: 831 case E_LEQ: 832 case E_LTH: 833 case E_UNEQUAL: 834 return dep->left.sym == sym || 835 dep->right.sym == sym; 836 case E_NOT: 837 return expr_contains_symbol(dep->left.expr, sym); 838 default: 839 ; 840 } 841 return 0; 842 } 843 844 bool expr_depends_symbol(struct expr *dep, struct symbol *sym) 845 { 846 if (!dep) 847 return false; 848 849 switch (dep->type) { 850 case E_AND: 851 return expr_depends_symbol(dep->left.expr, sym) || 852 expr_depends_symbol(dep->right.expr, sym); 853 case E_SYMBOL: 854 return dep->left.sym == sym; 855 case E_EQUAL: 856 if (dep->left.sym == sym) { 857 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod) 858 return true; 859 } 860 break; 861 case E_UNEQUAL: 862 if (dep->left.sym == sym) { 863 if (dep->right.sym == &symbol_no) 864 return true; 865 } 866 break; 867 default: 868 ; 869 } 870 return false; 871 } 872 873 /* 874 * Inserts explicit comparisons of type 'type' to symbol 'sym' into the 875 * expression 'e'. 876 * 877 * Examples transformations for type == E_UNEQUAL, sym == &symbol_no: 878 * 879 * A -> A!=n 880 * !A -> A=n 881 * A && B -> !(A=n || B=n) 882 * A || B -> !(A=n && B=n) 883 * A && (B || C) -> !(A=n || (B=n && C=n)) 884 * 885 * Allocates and returns a new expression. 886 */ 887 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) 888 { 889 struct expr *e1, *e2; 890 891 if (!e) { 892 e = expr_alloc_symbol(sym); 893 if (type == E_UNEQUAL) 894 e = expr_alloc_one(E_NOT, e); 895 return e; 896 } 897 switch (e->type) { 898 case E_AND: 899 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); 900 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); 901 if (sym == &symbol_yes) 902 e = expr_alloc_two(E_AND, e1, e2); 903 if (sym == &symbol_no) 904 e = expr_alloc_two(E_OR, e1, e2); 905 if (type == E_UNEQUAL) 906 e = expr_alloc_one(E_NOT, e); 907 return e; 908 case E_OR: 909 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); 910 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); 911 if (sym == &symbol_yes) 912 e = expr_alloc_two(E_OR, e1, e2); 913 if (sym == &symbol_no) 914 e = expr_alloc_two(E_AND, e1, e2); 915 if (type == E_UNEQUAL) 916 e = expr_alloc_one(E_NOT, e); 917 return e; 918 case E_NOT: 919 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym); 920 case E_UNEQUAL: 921 case E_LTH: 922 case E_LEQ: 923 case E_GTH: 924 case E_GEQ: 925 case E_EQUAL: 926 if (type == E_EQUAL) { 927 if (sym == &symbol_yes) 928 return expr_copy(e); 929 if (sym == &symbol_mod) 930 return expr_alloc_symbol(&symbol_no); 931 if (sym == &symbol_no) 932 return expr_alloc_one(E_NOT, expr_copy(e)); 933 } else { 934 if (sym == &symbol_yes) 935 return expr_alloc_one(E_NOT, expr_copy(e)); 936 if (sym == &symbol_mod) 937 return expr_alloc_symbol(&symbol_yes); 938 if (sym == &symbol_no) 939 return expr_copy(e); 940 } 941 break; 942 case E_SYMBOL: 943 return expr_alloc_comp(type, e->left.sym, sym); 944 case E_RANGE: 945 case E_NONE: 946 /* panic */; 947 } 948 return NULL; 949 } 950 951 enum string_value_kind { 952 k_string, 953 k_signed, 954 k_unsigned, 955 }; 956 957 union string_value { 958 unsigned long long u; 959 signed long long s; 960 }; 961 962 static enum string_value_kind expr_parse_string(const char *str, 963 enum symbol_type type, 964 union string_value *val) 965 { 966 char *tail; 967 enum string_value_kind kind; 968 969 errno = 0; 970 switch (type) { 971 case S_BOOLEAN: 972 case S_TRISTATE: 973 val->s = !strcmp(str, "n") ? 0 : 974 !strcmp(str, "m") ? 1 : 975 !strcmp(str, "y") ? 2 : -1; 976 return k_signed; 977 case S_INT: 978 val->s = strtoll(str, &tail, 10); 979 kind = k_signed; 980 break; 981 case S_HEX: 982 val->u = strtoull(str, &tail, 16); 983 kind = k_unsigned; 984 break; 985 default: 986 val->s = strtoll(str, &tail, 0); 987 kind = k_signed; 988 break; 989 } 990 return !errno && !*tail && tail > str && isxdigit(tail[-1]) 991 ? kind : k_string; 992 } 993 994 tristate expr_calc_value(struct expr *e) 995 { 996 tristate val1, val2; 997 const char *str1, *str2; 998 enum string_value_kind k1 = k_string, k2 = k_string; 999 union string_value lval = {}, rval = {}; 1000 int res; 1001 1002 if (!e) 1003 return yes; 1004 1005 switch (e->type) { 1006 case E_SYMBOL: 1007 sym_calc_value(e->left.sym); 1008 return e->left.sym->curr.tri; 1009 case E_AND: 1010 val1 = expr_calc_value(e->left.expr); 1011 val2 = expr_calc_value(e->right.expr); 1012 return EXPR_AND(val1, val2); 1013 case E_OR: 1014 val1 = expr_calc_value(e->left.expr); 1015 val2 = expr_calc_value(e->right.expr); 1016 return EXPR_OR(val1, val2); 1017 case E_NOT: 1018 val1 = expr_calc_value(e->left.expr); 1019 return EXPR_NOT(val1); 1020 case E_EQUAL: 1021 case E_GEQ: 1022 case E_GTH: 1023 case E_LEQ: 1024 case E_LTH: 1025 case E_UNEQUAL: 1026 break; 1027 default: 1028 printf("expr_calc_value: %d?\n", e->type); 1029 return no; 1030 } 1031 1032 sym_calc_value(e->left.sym); 1033 sym_calc_value(e->right.sym); 1034 str1 = sym_get_string_value(e->left.sym); 1035 str2 = sym_get_string_value(e->right.sym); 1036 1037 if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) { 1038 k1 = expr_parse_string(str1, e->left.sym->type, &lval); 1039 k2 = expr_parse_string(str2, e->right.sym->type, &rval); 1040 } 1041 1042 if (k1 == k_string || k2 == k_string) 1043 res = strcmp(str1, str2); 1044 else if (k1 == k_unsigned || k2 == k_unsigned) 1045 res = (lval.u > rval.u) - (lval.u < rval.u); 1046 else /* if (k1 == k_signed && k2 == k_signed) */ 1047 res = (lval.s > rval.s) - (lval.s < rval.s); 1048 1049 switch(e->type) { 1050 case E_EQUAL: 1051 return res ? no : yes; 1052 case E_GEQ: 1053 return res >= 0 ? yes : no; 1054 case E_GTH: 1055 return res > 0 ? yes : no; 1056 case E_LEQ: 1057 return res <= 0 ? yes : no; 1058 case E_LTH: 1059 return res < 0 ? yes : no; 1060 case E_UNEQUAL: 1061 return res ? yes : no; 1062 default: 1063 printf("expr_calc_value: relation %d?\n", e->type); 1064 return no; 1065 } 1066 } 1067 1068 static int expr_compare_type(enum expr_type t1, enum expr_type t2) 1069 { 1070 if (t1 == t2) 1071 return 0; 1072 switch (t1) { 1073 case E_LEQ: 1074 case E_LTH: 1075 case E_GEQ: 1076 case E_GTH: 1077 if (t2 == E_EQUAL || t2 == E_UNEQUAL) 1078 return 1; 1079 /* fallthrough */ 1080 case E_EQUAL: 1081 case E_UNEQUAL: 1082 if (t2 == E_NOT) 1083 return 1; 1084 /* fallthrough */ 1085 case E_NOT: 1086 if (t2 == E_AND) 1087 return 1; 1088 /* fallthrough */ 1089 case E_AND: 1090 if (t2 == E_OR) 1091 return 1; 1092 /* fallthrough */ 1093 default: 1094 break; 1095 } 1096 return 0; 1097 } 1098 1099 void expr_print(struct expr *e, 1100 void (*fn)(void *, struct symbol *, const char *), 1101 void *data, int prevtoken) 1102 { 1103 if (!e) { 1104 fn(data, NULL, "y"); 1105 return; 1106 } 1107 1108 if (expr_compare_type(prevtoken, e->type) > 0) 1109 fn(data, NULL, "("); 1110 switch (e->type) { 1111 case E_SYMBOL: 1112 if (e->left.sym->name) 1113 fn(data, e->left.sym, e->left.sym->name); 1114 else 1115 fn(data, NULL, "<choice>"); 1116 break; 1117 case E_NOT: 1118 fn(data, NULL, "!"); 1119 expr_print(e->left.expr, fn, data, E_NOT); 1120 break; 1121 case E_EQUAL: 1122 if (e->left.sym->name) 1123 fn(data, e->left.sym, e->left.sym->name); 1124 else 1125 fn(data, NULL, "<choice>"); 1126 fn(data, NULL, "="); 1127 fn(data, e->right.sym, e->right.sym->name); 1128 break; 1129 case E_LEQ: 1130 case E_LTH: 1131 if (e->left.sym->name) 1132 fn(data, e->left.sym, e->left.sym->name); 1133 else 1134 fn(data, NULL, "<choice>"); 1135 fn(data, NULL, e->type == E_LEQ ? "<=" : "<"); 1136 fn(data, e->right.sym, e->right.sym->name); 1137 break; 1138 case E_GEQ: 1139 case E_GTH: 1140 if (e->left.sym->name) 1141 fn(data, e->left.sym, e->left.sym->name); 1142 else 1143 fn(data, NULL, "<choice>"); 1144 fn(data, NULL, e->type == E_GEQ ? ">=" : ">"); 1145 fn(data, e->right.sym, e->right.sym->name); 1146 break; 1147 case E_UNEQUAL: 1148 if (e->left.sym->name) 1149 fn(data, e->left.sym, e->left.sym->name); 1150 else 1151 fn(data, NULL, "<choice>"); 1152 fn(data, NULL, "!="); 1153 fn(data, e->right.sym, e->right.sym->name); 1154 break; 1155 case E_OR: 1156 expr_print(e->left.expr, fn, data, E_OR); 1157 fn(data, NULL, " || "); 1158 expr_print(e->right.expr, fn, data, E_OR); 1159 break; 1160 case E_AND: 1161 expr_print(e->left.expr, fn, data, E_AND); 1162 fn(data, NULL, " && "); 1163 expr_print(e->right.expr, fn, data, E_AND); 1164 break; 1165 case E_RANGE: 1166 fn(data, NULL, "["); 1167 fn(data, e->left.sym, e->left.sym->name); 1168 fn(data, NULL, " "); 1169 fn(data, e->right.sym, e->right.sym->name); 1170 fn(data, NULL, "]"); 1171 break; 1172 default: 1173 { 1174 char buf[32]; 1175 sprintf(buf, "<unknown type %d>", e->type); 1176 fn(data, NULL, buf); 1177 break; 1178 } 1179 } 1180 if (expr_compare_type(prevtoken, e->type) > 0) 1181 fn(data, NULL, ")"); 1182 } 1183 1184 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) 1185 { 1186 xfwrite(str, strlen(str), 1, data); 1187 } 1188 1189 void expr_fprint(struct expr *e, FILE *out) 1190 { 1191 expr_print(e, expr_print_file_helper, out, E_NONE); 1192 } 1193 1194 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) 1195 { 1196 struct gstr *gs = (struct gstr*)data; 1197 const char *sym_str = NULL; 1198 1199 if (sym) 1200 sym_str = sym_get_string_value(sym); 1201 1202 if (gs->max_width) { 1203 unsigned extra_length = strlen(str); 1204 const char *last_cr = strrchr(gs->s, '\n'); 1205 unsigned last_line_length; 1206 1207 if (sym_str) 1208 extra_length += 4 + strlen(sym_str); 1209 1210 if (!last_cr) 1211 last_cr = gs->s; 1212 1213 last_line_length = strlen(gs->s) - (last_cr - gs->s); 1214 1215 if ((last_line_length + extra_length) > gs->max_width) 1216 str_append(gs, "\\\n"); 1217 } 1218 1219 str_append(gs, str); 1220 if (sym && sym->type != S_UNKNOWN) 1221 str_printf(gs, " [=%s]", sym_str); 1222 } 1223 1224 void expr_gstr_print(struct expr *e, struct gstr *gs) 1225 { 1226 expr_print(e, expr_print_gstr_helper, gs, E_NONE); 1227 } 1228 1229 /* 1230 * Transform the top level "||" tokens into newlines and prepend each 1231 * line with a minus. This makes expressions much easier to read. 1232 * Suitable for reverse dependency expressions. 1233 */ 1234 static void expr_print_revdep(struct expr *e, 1235 void (*fn)(void *, struct symbol *, const char *), 1236 void *data, tristate pr_type, const char **title) 1237 { 1238 if (e->type == E_OR) { 1239 expr_print_revdep(e->left.expr, fn, data, pr_type, title); 1240 expr_print_revdep(e->right.expr, fn, data, pr_type, title); 1241 } else if (expr_calc_value(e) == pr_type) { 1242 if (*title) { 1243 fn(data, NULL, *title); 1244 *title = NULL; 1245 } 1246 1247 fn(data, NULL, " - "); 1248 expr_print(e, fn, data, E_NONE); 1249 fn(data, NULL, "\n"); 1250 } 1251 } 1252 1253 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs, 1254 tristate pr_type, const char *title) 1255 { 1256 expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title); 1257 } 1258