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