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