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