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