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 */ expr_lookup(enum expr_type type,void * l,void * r)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 expr_alloc_symbol(struct symbol * sym)57 struct expr *expr_alloc_symbol(struct symbol *sym) 58 { 59 return expr_lookup(E_SYMBOL, sym, NULL); 60 } 61 expr_alloc_one(enum expr_type type,struct expr * ce)62 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) 63 { 64 return expr_lookup(type, ce, NULL); 65 } 66 expr_alloc_two(enum expr_type type,struct expr * e1,struct expr * e2)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 expr_alloc_comp(enum expr_type type,struct symbol * s1,struct symbol * s2)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 expr_alloc_and(struct expr * e1,struct expr * e2)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 expr_alloc_or(struct expr * e1,struct expr * e2)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 */ __expr_eliminate_eq(enum expr_type type,struct expr ** ep1,struct expr ** ep2)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 */ expr_eliminate_eq(struct expr ** ep1,struct expr ** ep2)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 */ expr_eq(struct expr * e1,struct expr * e2)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 */ expr_eliminate_yn(struct expr * e)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 */ expr_join_or(struct expr * e1,struct expr * e2)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 expr_join_and(struct expr * e1,struct expr * e2)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 */ expr_eliminate_dups1(enum expr_type type,struct expr ** ep1,struct expr ** ep2)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 */ expr_eliminate_dups(struct expr * e)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 */ expr_transform(struct expr * e)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 expr_contains_symbol(struct expr * dep,struct symbol * sym)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 expr_depends_symbol(struct expr * dep,struct symbol * sym)741 bool expr_depends_symbol(struct expr *dep, struct symbol *sym) 742 { 743 if (!dep) 744 return false; 745 746 switch (dep->type) { 747 case E_AND: 748 return expr_depends_symbol(dep->left.expr, sym) || 749 expr_depends_symbol(dep->right.expr, sym); 750 case E_SYMBOL: 751 return dep->left.sym == sym; 752 case E_EQUAL: 753 if (dep->left.sym == sym) { 754 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod) 755 return true; 756 } 757 break; 758 case E_UNEQUAL: 759 if (dep->left.sym == sym) { 760 if (dep->right.sym == &symbol_no) 761 return true; 762 } 763 break; 764 default: 765 ; 766 } 767 return false; 768 } 769 770 /* 771 * Inserts explicit comparisons of type 'type' to symbol 'sym' into the 772 * expression 'e'. 773 * 774 * Examples transformations for type == E_UNEQUAL, sym == &symbol_no: 775 * 776 * A -> A!=n 777 * !A -> A=n 778 * A && B -> !(A=n || B=n) 779 * A || B -> !(A=n && B=n) 780 * A && (B || C) -> !(A=n || (B=n && C=n)) 781 * 782 * Allocates and returns a new expression. 783 */ expr_trans_compare(struct expr * e,enum expr_type type,struct symbol * sym)784 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) 785 { 786 struct expr *e1, *e2; 787 788 if (!e) { 789 e = expr_alloc_symbol(sym); 790 if (type == E_UNEQUAL) 791 e = expr_alloc_one(E_NOT, e); 792 return e; 793 } 794 switch (e->type) { 795 case E_AND: 796 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); 797 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); 798 if (sym == &symbol_yes) 799 e = expr_alloc_two(E_AND, e1, e2); 800 if (sym == &symbol_no) 801 e = expr_alloc_two(E_OR, e1, e2); 802 if (type == E_UNEQUAL) 803 e = expr_alloc_one(E_NOT, e); 804 return e; 805 case E_OR: 806 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); 807 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); 808 if (sym == &symbol_yes) 809 e = expr_alloc_two(E_OR, e1, e2); 810 if (sym == &symbol_no) 811 e = expr_alloc_two(E_AND, e1, e2); 812 if (type == E_UNEQUAL) 813 e = expr_alloc_one(E_NOT, e); 814 return e; 815 case E_NOT: 816 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym); 817 case E_UNEQUAL: 818 case E_LTH: 819 case E_LEQ: 820 case E_GTH: 821 case E_GEQ: 822 case E_EQUAL: 823 if (type == E_EQUAL) { 824 if (sym == &symbol_yes) 825 return e; 826 if (sym == &symbol_mod) 827 return expr_alloc_symbol(&symbol_no); 828 if (sym == &symbol_no) 829 return expr_alloc_one(E_NOT, e); 830 } else { 831 if (sym == &symbol_yes) 832 return expr_alloc_one(E_NOT, e); 833 if (sym == &symbol_mod) 834 return expr_alloc_symbol(&symbol_yes); 835 if (sym == &symbol_no) 836 return e; 837 } 838 break; 839 case E_SYMBOL: 840 return expr_alloc_comp(type, e->left.sym, sym); 841 case E_RANGE: 842 case E_NONE: 843 /* panic */; 844 } 845 return NULL; 846 } 847 848 enum string_value_kind { 849 k_string, 850 k_signed, 851 k_unsigned, 852 }; 853 854 union string_value { 855 unsigned long long u; 856 signed long long s; 857 }; 858 expr_parse_string(const char * str,enum symbol_type type,union string_value * val)859 static enum string_value_kind expr_parse_string(const char *str, 860 enum symbol_type type, 861 union string_value *val) 862 { 863 char *tail; 864 enum string_value_kind kind; 865 866 errno = 0; 867 switch (type) { 868 case S_BOOLEAN: 869 case S_TRISTATE: 870 val->s = !strcmp(str, "n") ? 0 : 871 !strcmp(str, "m") ? 1 : 872 !strcmp(str, "y") ? 2 : -1; 873 return k_signed; 874 case S_INT: 875 val->s = strtoll(str, &tail, 10); 876 kind = k_signed; 877 break; 878 case S_HEX: 879 val->u = strtoull(str, &tail, 16); 880 kind = k_unsigned; 881 break; 882 default: 883 val->s = strtoll(str, &tail, 0); 884 kind = k_signed; 885 break; 886 } 887 return !errno && !*tail && tail > str && isxdigit(tail[-1]) 888 ? kind : k_string; 889 } 890 __expr_calc_value(struct expr * e)891 static tristate __expr_calc_value(struct expr *e) 892 { 893 tristate val1, val2; 894 const char *str1, *str2; 895 enum string_value_kind k1 = k_string, k2 = k_string; 896 union string_value lval = {}, rval = {}; 897 int res; 898 899 switch (e->type) { 900 case E_SYMBOL: 901 sym_calc_value(e->left.sym); 902 return e->left.sym->curr.tri; 903 case E_AND: 904 val1 = expr_calc_value(e->left.expr); 905 val2 = expr_calc_value(e->right.expr); 906 return EXPR_AND(val1, val2); 907 case E_OR: 908 val1 = expr_calc_value(e->left.expr); 909 val2 = expr_calc_value(e->right.expr); 910 return EXPR_OR(val1, val2); 911 case E_NOT: 912 val1 = expr_calc_value(e->left.expr); 913 return EXPR_NOT(val1); 914 case E_EQUAL: 915 case E_GEQ: 916 case E_GTH: 917 case E_LEQ: 918 case E_LTH: 919 case E_UNEQUAL: 920 break; 921 default: 922 printf("expr_calc_value: %d?\n", e->type); 923 return no; 924 } 925 926 sym_calc_value(e->left.sym); 927 sym_calc_value(e->right.sym); 928 str1 = sym_get_string_value(e->left.sym); 929 str2 = sym_get_string_value(e->right.sym); 930 931 if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) { 932 k1 = expr_parse_string(str1, e->left.sym->type, &lval); 933 k2 = expr_parse_string(str2, e->right.sym->type, &rval); 934 } 935 936 if (k1 == k_string || k2 == k_string) 937 res = strcmp(str1, str2); 938 else if (k1 == k_unsigned || k2 == k_unsigned) 939 res = (lval.u > rval.u) - (lval.u < rval.u); 940 else /* if (k1 == k_signed && k2 == k_signed) */ 941 res = (lval.s > rval.s) - (lval.s < rval.s); 942 943 switch(e->type) { 944 case E_EQUAL: 945 return res ? no : yes; 946 case E_GEQ: 947 return res >= 0 ? yes : no; 948 case E_GTH: 949 return res > 0 ? yes : no; 950 case E_LEQ: 951 return res <= 0 ? yes : no; 952 case E_LTH: 953 return res < 0 ? yes : no; 954 case E_UNEQUAL: 955 return res ? yes : no; 956 default: 957 printf("expr_calc_value: relation %d?\n", e->type); 958 return no; 959 } 960 } 961 962 /** 963 * expr_calc_value - return the tristate value of the given expression 964 * @e: expression 965 * return: tristate value of the expression 966 */ expr_calc_value(struct expr * e)967 tristate expr_calc_value(struct expr *e) 968 { 969 if (!e) 970 return yes; 971 972 if (!e->val_is_valid) { 973 e->val = __expr_calc_value(e); 974 e->val_is_valid = true; 975 } 976 977 return e->val; 978 } 979 980 /** 981 * expr_invalidate_all - invalidate all cached expression values 982 */ expr_invalidate_all(void)983 void expr_invalidate_all(void) 984 { 985 struct expr *e; 986 987 hash_for_each(expr_hashtable, e, node) 988 e->val_is_valid = false; 989 } 990 expr_compare_type(enum expr_type t1,enum expr_type t2)991 static int expr_compare_type(enum expr_type t1, enum expr_type t2) 992 { 993 if (t1 == t2) 994 return 0; 995 switch (t1) { 996 case E_LEQ: 997 case E_LTH: 998 case E_GEQ: 999 case E_GTH: 1000 if (t2 == E_EQUAL || t2 == E_UNEQUAL) 1001 return 1; 1002 /* fallthrough */ 1003 case E_EQUAL: 1004 case E_UNEQUAL: 1005 if (t2 == E_NOT) 1006 return 1; 1007 /* fallthrough */ 1008 case E_NOT: 1009 if (t2 == E_AND) 1010 return 1; 1011 /* fallthrough */ 1012 case E_AND: 1013 if (t2 == E_OR) 1014 return 1; 1015 /* fallthrough */ 1016 default: 1017 break; 1018 } 1019 return 0; 1020 } 1021 expr_print(const struct expr * e,void (* fn)(void *,struct symbol *,const char *),void * data,int prevtoken)1022 void expr_print(const struct expr *e, 1023 void (*fn)(void *, struct symbol *, const char *), 1024 void *data, int prevtoken) 1025 { 1026 if (!e) { 1027 fn(data, NULL, "y"); 1028 return; 1029 } 1030 1031 if (expr_compare_type(prevtoken, e->type) > 0) 1032 fn(data, NULL, "("); 1033 switch (e->type) { 1034 case E_SYMBOL: 1035 if (e->left.sym->name) 1036 fn(data, e->left.sym, e->left.sym->name); 1037 else 1038 fn(data, NULL, "<choice>"); 1039 break; 1040 case E_NOT: 1041 fn(data, NULL, "!"); 1042 expr_print(e->left.expr, fn, data, E_NOT); 1043 break; 1044 case E_EQUAL: 1045 if (e->left.sym->name) 1046 fn(data, e->left.sym, e->left.sym->name); 1047 else 1048 fn(data, NULL, "<choice>"); 1049 fn(data, NULL, "="); 1050 fn(data, e->right.sym, e->right.sym->name); 1051 break; 1052 case E_LEQ: 1053 case E_LTH: 1054 if (e->left.sym->name) 1055 fn(data, e->left.sym, e->left.sym->name); 1056 else 1057 fn(data, NULL, "<choice>"); 1058 fn(data, NULL, e->type == E_LEQ ? "<=" : "<"); 1059 fn(data, e->right.sym, e->right.sym->name); 1060 break; 1061 case E_GEQ: 1062 case E_GTH: 1063 if (e->left.sym->name) 1064 fn(data, e->left.sym, e->left.sym->name); 1065 else 1066 fn(data, NULL, "<choice>"); 1067 fn(data, NULL, e->type == E_GEQ ? ">=" : ">"); 1068 fn(data, e->right.sym, e->right.sym->name); 1069 break; 1070 case E_UNEQUAL: 1071 if (e->left.sym->name) 1072 fn(data, e->left.sym, e->left.sym->name); 1073 else 1074 fn(data, NULL, "<choice>"); 1075 fn(data, NULL, "!="); 1076 fn(data, e->right.sym, e->right.sym->name); 1077 break; 1078 case E_OR: 1079 expr_print(e->left.expr, fn, data, E_OR); 1080 fn(data, NULL, " || "); 1081 expr_print(e->right.expr, fn, data, E_OR); 1082 break; 1083 case E_AND: 1084 expr_print(e->left.expr, fn, data, E_AND); 1085 fn(data, NULL, " && "); 1086 expr_print(e->right.expr, fn, data, E_AND); 1087 break; 1088 case E_RANGE: 1089 fn(data, NULL, "["); 1090 fn(data, e->left.sym, e->left.sym->name); 1091 fn(data, NULL, " "); 1092 fn(data, e->right.sym, e->right.sym->name); 1093 fn(data, NULL, "]"); 1094 break; 1095 default: 1096 { 1097 char buf[32]; 1098 sprintf(buf, "<unknown type %d>", e->type); 1099 fn(data, NULL, buf); 1100 break; 1101 } 1102 } 1103 if (expr_compare_type(prevtoken, e->type) > 0) 1104 fn(data, NULL, ")"); 1105 } 1106 expr_print_file_helper(void * data,struct symbol * sym,const char * str)1107 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) 1108 { 1109 xfwrite(str, strlen(str), 1, data); 1110 } 1111 expr_fprint(struct expr * e,FILE * out)1112 void expr_fprint(struct expr *e, FILE *out) 1113 { 1114 expr_print(e, expr_print_file_helper, out, E_NONE); 1115 } 1116 expr_print_gstr_helper(void * data,struct symbol * sym,const char * str)1117 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) 1118 { 1119 struct gstr *gs = (struct gstr*)data; 1120 const char *sym_str = NULL; 1121 1122 if (sym) 1123 sym_str = sym_get_string_value(sym); 1124 1125 if (gs->max_width) { 1126 unsigned extra_length = strlen(str); 1127 const char *last_cr = strrchr(gs->s, '\n'); 1128 unsigned last_line_length; 1129 1130 if (sym_str) 1131 extra_length += 4 + strlen(sym_str); 1132 1133 if (!last_cr) 1134 last_cr = gs->s; 1135 1136 last_line_length = strlen(gs->s) - (last_cr - gs->s); 1137 1138 if ((last_line_length + extra_length) > gs->max_width) 1139 str_append(gs, "\\\n"); 1140 } 1141 1142 str_append(gs, str); 1143 if (sym && sym->type != S_UNKNOWN) 1144 str_printf(gs, " [=%s]", sym_str); 1145 } 1146 expr_gstr_print(const struct expr * e,struct gstr * gs)1147 void expr_gstr_print(const struct expr *e, struct gstr *gs) 1148 { 1149 expr_print(e, expr_print_gstr_helper, gs, E_NONE); 1150 } 1151 1152 /* 1153 * Transform the top level "||" tokens into newlines and prepend each 1154 * line with a minus. This makes expressions much easier to read. 1155 * Suitable for reverse dependency expressions. 1156 */ expr_print_revdep(struct expr * e,void (* fn)(void *,struct symbol *,const char *),void * data,tristate pr_type,const char ** title)1157 static void expr_print_revdep(struct expr *e, 1158 void (*fn)(void *, struct symbol *, const char *), 1159 void *data, tristate pr_type, const char **title) 1160 { 1161 if (e->type == E_OR) { 1162 expr_print_revdep(e->left.expr, fn, data, pr_type, title); 1163 expr_print_revdep(e->right.expr, fn, data, pr_type, title); 1164 } else if (expr_calc_value(e) == pr_type) { 1165 if (*title) { 1166 fn(data, NULL, *title); 1167 *title = NULL; 1168 } 1169 1170 fn(data, NULL, " - "); 1171 expr_print(e, fn, data, E_NONE); 1172 fn(data, NULL, "\n"); 1173 } 1174 } 1175 expr_gstr_print_revdep(struct expr * e,struct gstr * gs,tristate pr_type,const char * title)1176 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs, 1177 tristate pr_type, const char *title) 1178 { 1179 expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title); 1180 } 1181