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