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