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