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