![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to expr.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Qemu by Fabrice Bellard] / qemu / roms / seabios / tools / kconfig|
Return to expr.c CVS log | Up to [Qemu by Fabrice Bellard] / qemu / roms / seabios / tools / kconfig |
1.1 ! root 1: /* ! 2: * Copyright (C) 2002 Roman Zippel <[email protected]> ! 3: * Released under the terms of the GNU GPL v2.0. ! 4: */ ! 5: ! 6: #include <stdio.h> ! 7: #include <stdlib.h> ! 8: #include <string.h> ! 9: ! 10: #define LKC_DIRECT_LINK ! 11: #include "lkc.h" ! 12: ! 13: #define DEBUG_EXPR 0 ! 14: ! 15: struct expr *expr_alloc_symbol(struct symbol *sym) ! 16: { ! 17: struct expr *e = malloc(sizeof(*e)); ! 18: memset(e, 0, sizeof(*e)); ! 19: e->type = E_SYMBOL; ! 20: e->left.sym = sym; ! 21: return e; ! 22: } ! 23: ! 24: struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) ! 25: { ! 26: struct expr *e = malloc(sizeof(*e)); ! 27: memset(e, 0, sizeof(*e)); ! 28: e->type = type; ! 29: e->left.expr = ce; ! 30: return e; ! 31: } ! 32: ! 33: struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2) ! 34: { ! 35: struct expr *e = malloc(sizeof(*e)); ! 36: memset(e, 0, sizeof(*e)); ! 37: e->type = type; ! 38: e->left.expr = e1; ! 39: e->right.expr = e2; ! 40: return e; ! 41: } ! 42: ! 43: struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2) ! 44: { ! 45: struct expr *e = malloc(sizeof(*e)); ! 46: memset(e, 0, sizeof(*e)); ! 47: e->type = type; ! 48: e->left.sym = s1; ! 49: e->right.sym = s2; ! 50: return e; ! 51: } ! 52: ! 53: struct expr *expr_alloc_and(struct expr *e1, struct expr *e2) ! 54: { ! 55: if (!e1) ! 56: return e2; ! 57: return e2 ? expr_alloc_two(E_AND, e1, e2) : e1; ! 58: } ! 59: ! 60: struct expr *expr_alloc_or(struct expr *e1, struct expr *e2) ! 61: { ! 62: if (!e1) ! 63: return e2; ! 64: return e2 ? expr_alloc_two(E_OR, e1, e2) : e1; ! 65: } ! 66: ! 67: struct expr *expr_copy(const struct expr *org) ! 68: { ! 69: struct expr *e; ! 70: ! 71: if (!org) ! 72: return NULL; ! 73: ! 74: e = malloc(sizeof(*org)); ! 75: memcpy(e, org, sizeof(*org)); ! 76: switch (org->type) { ! 77: case E_SYMBOL: ! 78: e->left = org->left; ! 79: break; ! 80: case E_NOT: ! 81: e->left.expr = expr_copy(org->left.expr); ! 82: break; ! 83: case E_EQUAL: ! 84: case E_UNEQUAL: ! 85: e->left.sym = org->left.sym; ! 86: e->right.sym = org->right.sym; ! 87: break; ! 88: case E_AND: ! 89: case E_OR: ! 90: case E_LIST: ! 91: e->left.expr = expr_copy(org->left.expr); ! 92: e->right.expr = expr_copy(org->right.expr); ! 93: break; ! 94: default: ! 95: printf("can't copy type %d\n", e->type); ! 96: free(e); ! 97: e = NULL; ! 98: break; ! 99: } ! 100: ! 101: return e; ! 102: } ! 103: ! 104: void expr_free(struct expr *e) ! 105: { ! 106: if (!e) ! 107: return; ! 108: ! 109: switch (e->type) { ! 110: case E_SYMBOL: ! 111: break; ! 112: case E_NOT: ! 113: expr_free(e->left.expr); ! 114: return; ! 115: case E_EQUAL: ! 116: case E_UNEQUAL: ! 117: break; ! 118: case E_OR: ! 119: case E_AND: ! 120: expr_free(e->left.expr); ! 121: expr_free(e->right.expr); ! 122: break; ! 123: default: ! 124: printf("how to free type %d?\n", e->type); ! 125: break; ! 126: } ! 127: free(e); ! 128: } ! 129: ! 130: static int trans_count; ! 131: ! 132: #define e1 (*ep1) ! 133: #define e2 (*ep2) ! 134: ! 135: static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) ! 136: { ! 137: if (e1->type == type) { ! 138: __expr_eliminate_eq(type, &e1->left.expr, &e2); ! 139: __expr_eliminate_eq(type, &e1->right.expr, &e2); ! 140: return; ! 141: } ! 142: if (e2->type == type) { ! 143: __expr_eliminate_eq(type, &e1, &e2->left.expr); ! 144: __expr_eliminate_eq(type, &e1, &e2->right.expr); ! 145: return; ! 146: } ! 147: if (e1->type == E_SYMBOL && e2->type == E_SYMBOL && ! 148: e1->left.sym == e2->left.sym && ! 149: (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) ! 150: return; ! 151: if (!expr_eq(e1, e2)) ! 152: return; ! 153: trans_count++; ! 154: expr_free(e1); expr_free(e2); ! 155: switch (type) { ! 156: case E_OR: ! 157: e1 = expr_alloc_symbol(&symbol_no); ! 158: e2 = expr_alloc_symbol(&symbol_no); ! 159: break; ! 160: case E_AND: ! 161: e1 = expr_alloc_symbol(&symbol_yes); ! 162: e2 = expr_alloc_symbol(&symbol_yes); ! 163: break; ! 164: default: ! 165: ; ! 166: } ! 167: } ! 168: ! 169: void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) ! 170: { ! 171: if (!e1 || !e2) ! 172: return; ! 173: switch (e1->type) { ! 174: case E_OR: ! 175: case E_AND: ! 176: __expr_eliminate_eq(e1->type, ep1, ep2); ! 177: default: ! 178: ; ! 179: } ! 180: if (e1->type != e2->type) switch (e2->type) { ! 181: case E_OR: ! 182: case E_AND: ! 183: __expr_eliminate_eq(e2->type, ep1, ep2); ! 184: default: ! 185: ; ! 186: } ! 187: e1 = expr_eliminate_yn(e1); ! 188: e2 = expr_eliminate_yn(e2); ! 189: } ! 190: ! 191: #undef e1 ! 192: #undef e2 ! 193: ! 194: int expr_eq(struct expr *e1, struct expr *e2) ! 195: { ! 196: int res, old_count; ! 197: ! 198: if (e1->type != e2->type) ! 199: return 0; ! 200: switch (e1->type) { ! 201: case E_EQUAL: ! 202: case E_UNEQUAL: ! 203: return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym; ! 204: case E_SYMBOL: ! 205: return e1->left.sym == e2->left.sym; ! 206: case E_NOT: ! 207: return expr_eq(e1->left.expr, e2->left.expr); ! 208: case E_AND: ! 209: case E_OR: ! 210: e1 = expr_copy(e1); ! 211: e2 = expr_copy(e2); ! 212: old_count = trans_count; ! 213: expr_eliminate_eq(&e1, &e2); ! 214: res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL && ! 215: e1->left.sym == e2->left.sym); ! 216: expr_free(e1); ! 217: expr_free(e2); ! 218: trans_count = old_count; ! 219: return res; ! 220: case E_LIST: ! 221: case E_RANGE: ! 222: case E_NONE: ! 223: /* panic */; ! 224: } ! 225: ! 226: if (DEBUG_EXPR) { ! 227: expr_fprint(e1, stdout); ! 228: printf(" = "); ! 229: expr_fprint(e2, stdout); ! 230: printf(" ?\n"); ! 231: } ! 232: ! 233: return 0; ! 234: } ! 235: ! 236: struct expr *expr_eliminate_yn(struct expr *e) ! 237: { ! 238: struct expr *tmp; ! 239: ! 240: if (e) switch (e->type) { ! 241: case E_AND: ! 242: e->left.expr = expr_eliminate_yn(e->left.expr); ! 243: e->right.expr = expr_eliminate_yn(e->right.expr); ! 244: if (e->left.expr->type == E_SYMBOL) { ! 245: if (e->left.expr->left.sym == &symbol_no) { ! 246: expr_free(e->left.expr); ! 247: expr_free(e->right.expr); ! 248: e->type = E_SYMBOL; ! 249: e->left.sym = &symbol_no; ! 250: e->right.expr = NULL; ! 251: return e; ! 252: } else if (e->left.expr->left.sym == &symbol_yes) { ! 253: free(e->left.expr); ! 254: tmp = e->right.expr; ! 255: *e = *(e->right.expr); ! 256: free(tmp); ! 257: return e; ! 258: } ! 259: } ! 260: if (e->right.expr->type == E_SYMBOL) { ! 261: if (e->right.expr->left.sym == &symbol_no) { ! 262: expr_free(e->left.expr); ! 263: expr_free(e->right.expr); ! 264: e->type = E_SYMBOL; ! 265: e->left.sym = &symbol_no; ! 266: e->right.expr = NULL; ! 267: return e; ! 268: } else if (e->right.expr->left.sym == &symbol_yes) { ! 269: free(e->right.expr); ! 270: tmp = e->left.expr; ! 271: *e = *(e->left.expr); ! 272: free(tmp); ! 273: return e; ! 274: } ! 275: } ! 276: break; ! 277: case E_OR: ! 278: e->left.expr = expr_eliminate_yn(e->left.expr); ! 279: e->right.expr = expr_eliminate_yn(e->right.expr); ! 280: if (e->left.expr->type == E_SYMBOL) { ! 281: if (e->left.expr->left.sym == &symbol_no) { ! 282: free(e->left.expr); ! 283: tmp = e->right.expr; ! 284: *e = *(e->right.expr); ! 285: free(tmp); ! 286: return e; ! 287: } else if (e->left.expr->left.sym == &symbol_yes) { ! 288: expr_free(e->left.expr); ! 289: expr_free(e->right.expr); ! 290: e->type = E_SYMBOL; ! 291: e->left.sym = &symbol_yes; ! 292: e->right.expr = NULL; ! 293: return e; ! 294: } ! 295: } ! 296: if (e->right.expr->type == E_SYMBOL) { ! 297: if (e->right.expr->left.sym == &symbol_no) { ! 298: free(e->right.expr); ! 299: tmp = e->left.expr; ! 300: *e = *(e->left.expr); ! 301: free(tmp); ! 302: return e; ! 303: } else if (e->right.expr->left.sym == &symbol_yes) { ! 304: expr_free(e->left.expr); ! 305: expr_free(e->right.expr); ! 306: e->type = E_SYMBOL; ! 307: e->left.sym = &symbol_yes; ! 308: e->right.expr = NULL; ! 309: return e; ! 310: } ! 311: } ! 312: break; ! 313: default: ! 314: ; ! 315: } ! 316: return e; ! 317: } ! 318: ! 319: /* ! 320: * bool FOO!=n => FOO ! 321: */ ! 322: struct expr *expr_trans_bool(struct expr *e) ! 323: { ! 324: if (!e) ! 325: return NULL; ! 326: switch (e->type) { ! 327: case E_AND: ! 328: case E_OR: ! 329: case E_NOT: ! 330: e->left.expr = expr_trans_bool(e->left.expr); ! 331: e->right.expr = expr_trans_bool(e->right.expr); ! 332: break; ! 333: case E_UNEQUAL: ! 334: // FOO!=n -> FOO ! 335: if (e->left.sym->type == S_TRISTATE) { ! 336: if (e->right.sym == &symbol_no) { ! 337: e->type = E_SYMBOL; ! 338: e->right.sym = NULL; ! 339: } ! 340: } ! 341: break; ! 342: default: ! 343: ; ! 344: } ! 345: return e; ! 346: } ! 347: ! 348: /* ! 349: * e1 || e2 -> ? ! 350: */ ! 351: static struct expr *expr_join_or(struct expr *e1, struct expr *e2) ! 352: { ! 353: struct expr *tmp; ! 354: struct symbol *sym1, *sym2; ! 355: ! 356: if (expr_eq(e1, e2)) ! 357: return expr_copy(e1); ! 358: if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) ! 359: return NULL; ! 360: if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) ! 361: return NULL; ! 362: if (e1->type == E_NOT) { ! 363: tmp = e1->left.expr; ! 364: if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) ! 365: return NULL; ! 366: sym1 = tmp->left.sym; ! 367: } else ! 368: sym1 = e1->left.sym; ! 369: if (e2->type == E_NOT) { ! 370: if (e2->left.expr->type != E_SYMBOL) ! 371: return NULL; ! 372: sym2 = e2->left.expr->left.sym; ! 373: } else ! 374: sym2 = e2->left.sym; ! 375: if (sym1 != sym2) ! 376: return NULL; ! 377: if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) ! 378: return NULL; ! 379: if (sym1->type == S_TRISTATE) { ! 380: if (e1->type == E_EQUAL && e2->type == E_EQUAL && ! 381: ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || ! 382: (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) { ! 383: // (a='y') || (a='m') -> (a!='n') ! 384: return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no); ! 385: } ! 386: if (e1->type == E_EQUAL && e2->type == E_EQUAL && ! 387: ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || ! 388: (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) { ! 389: // (a='y') || (a='n') -> (a!='m') ! 390: return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod); ! 391: } ! 392: if (e1->type == E_EQUAL && e2->type == E_EQUAL && ! 393: ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || ! 394: (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) { ! 395: // (a='m') || (a='n') -> (a!='y') ! 396: return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes); ! 397: } ! 398: } ! 399: if (sym1->type == S_BOOLEAN && sym1 == sym2) { ! 400: if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) || ! 401: (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL)) ! 402: return expr_alloc_symbol(&symbol_yes); ! 403: } ! 404: ! 405: if (DEBUG_EXPR) { ! 406: printf("optimize ("); ! 407: expr_fprint(e1, stdout); ! 408: printf(") || ("); ! 409: expr_fprint(e2, stdout); ! 410: printf(")?\n"); ! 411: } ! 412: return NULL; ! 413: } ! 414: ! 415: static struct expr *expr_join_and(struct expr *e1, struct expr *e2) ! 416: { ! 417: struct expr *tmp; ! 418: struct symbol *sym1, *sym2; ! 419: ! 420: if (expr_eq(e1, e2)) ! 421: return expr_copy(e1); ! 422: if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) ! 423: return NULL; ! 424: if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) ! 425: return NULL; ! 426: if (e1->type == E_NOT) { ! 427: tmp = e1->left.expr; ! 428: if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) ! 429: return NULL; ! 430: sym1 = tmp->left.sym; ! 431: } else ! 432: sym1 = e1->left.sym; ! 433: if (e2->type == E_NOT) { ! 434: if (e2->left.expr->type != E_SYMBOL) ! 435: return NULL; ! 436: sym2 = e2->left.expr->left.sym; ! 437: } else ! 438: sym2 = e2->left.sym; ! 439: if (sym1 != sym2) ! 440: return NULL; ! 441: if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) ! 442: return NULL; ! 443: ! 444: if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) || ! 445: (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes)) ! 446: // (a) && (a='y') -> (a='y') ! 447: return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); ! 448: ! 449: if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) || ! 450: (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no)) ! 451: // (a) && (a!='n') -> (a) ! 452: return expr_alloc_symbol(sym1); ! 453: ! 454: if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) || ! 455: (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod)) ! 456: // (a) && (a!='m') -> (a='y') ! 457: return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); ! 458: ! 459: if (sym1->type == S_TRISTATE) { ! 460: if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) { ! 461: // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' ! 462: sym2 = e1->right.sym; ! 463: if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) ! 464: return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) ! 465: : expr_alloc_symbol(&symbol_no); ! 466: } ! 467: if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) { ! 468: // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' ! 469: sym2 = e2->right.sym; ! 470: if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) ! 471: return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) ! 472: : expr_alloc_symbol(&symbol_no); ! 473: } ! 474: if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && ! 475: ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || ! 476: (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) ! 477: // (a!='y') && (a!='n') -> (a='m') ! 478: return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod); ! 479: ! 480: if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && ! 481: ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || ! 482: (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) ! 483: // (a!='y') && (a!='m') -> (a='n') ! 484: return expr_alloc_comp(E_EQUAL, sym1, &symbol_no); ! 485: ! 486: if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && ! 487: ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || ! 488: (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) ! 489: // (a!='m') && (a!='n') -> (a='m') ! 490: return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); ! 491: ! 492: if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) || ! 493: (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) || ! 494: (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) || ! 495: (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes)) ! 496: return NULL; ! 497: } ! 498: ! 499: if (DEBUG_EXPR) { ! 500: printf("optimize ("); ! 501: expr_fprint(e1, stdout); ! 502: printf(") && ("); ! 503: expr_fprint(e2, stdout); ! 504: printf(")?\n"); ! 505: } ! 506: return NULL; ! 507: } ! 508: ! 509: static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2) ! 510: { ! 511: #define e1 (*ep1) ! 512: #define e2 (*ep2) ! 513: struct expr *tmp; ! 514: ! 515: if (e1->type == type) { ! 516: expr_eliminate_dups1(type, &e1->left.expr, &e2); ! 517: expr_eliminate_dups1(type, &e1->right.expr, &e2); ! 518: return; ! 519: } ! 520: if (e2->type == type) { ! 521: expr_eliminate_dups1(type, &e1, &e2->left.expr); ! 522: expr_eliminate_dups1(type, &e1, &e2->right.expr); ! 523: return; ! 524: } ! 525: if (e1 == e2) ! 526: return; ! 527: ! 528: switch (e1->type) { ! 529: case E_OR: case E_AND: ! 530: expr_eliminate_dups1(e1->type, &e1, &e1); ! 531: default: ! 532: ; ! 533: } ! 534: ! 535: switch (type) { ! 536: case E_OR: ! 537: tmp = expr_join_or(e1, e2); ! 538: if (tmp) { ! 539: expr_free(e1); expr_free(e2); ! 540: e1 = expr_alloc_symbol(&symbol_no); ! 541: e2 = tmp; ! 542: trans_count++; ! 543: } ! 544: break; ! 545: case E_AND: ! 546: tmp = expr_join_and(e1, e2); ! 547: if (tmp) { ! 548: expr_free(e1); expr_free(e2); ! 549: e1 = expr_alloc_symbol(&symbol_yes); ! 550: e2 = tmp; ! 551: trans_count++; ! 552: } ! 553: break; ! 554: default: ! 555: ; ! 556: } ! 557: #undef e1 ! 558: #undef e2 ! 559: } ! 560: ! 561: static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2) ! 562: { ! 563: #define e1 (*ep1) ! 564: #define e2 (*ep2) ! 565: struct expr *tmp, *tmp1, *tmp2; ! 566: ! 567: if (e1->type == type) { ! 568: expr_eliminate_dups2(type, &e1->left.expr, &e2); ! 569: expr_eliminate_dups2(type, &e1->right.expr, &e2); ! 570: return; ! 571: } ! 572: if (e2->type == type) { ! 573: expr_eliminate_dups2(type, &e1, &e2->left.expr); ! 574: expr_eliminate_dups2(type, &e1, &e2->right.expr); ! 575: } ! 576: if (e1 == e2) ! 577: return; ! 578: ! 579: switch (e1->type) { ! 580: case E_OR: ! 581: expr_eliminate_dups2(e1->type, &e1, &e1); ! 582: // (FOO || BAR) && (!FOO && !BAR) -> n ! 583: tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1))); ! 584: tmp2 = expr_copy(e2); ! 585: tmp = expr_extract_eq_and(&tmp1, &tmp2); ! 586: if (expr_is_yes(tmp1)) { ! 587: expr_free(e1); ! 588: e1 = expr_alloc_symbol(&symbol_no); ! 589: trans_count++; ! 590: } ! 591: expr_free(tmp2); ! 592: expr_free(tmp1); ! 593: expr_free(tmp); ! 594: break; ! 595: case E_AND: ! 596: expr_eliminate_dups2(e1->type, &e1, &e1); ! 597: // (FOO && BAR) || (!FOO || !BAR) -> y ! 598: tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1))); ! 599: tmp2 = expr_copy(e2); ! 600: tmp = expr_extract_eq_or(&tmp1, &tmp2); ! 601: if (expr_is_no(tmp1)) { ! 602: expr_free(e1); ! 603: e1 = expr_alloc_symbol(&symbol_yes); ! 604: trans_count++; ! 605: } ! 606: expr_free(tmp2); ! 607: expr_free(tmp1); ! 608: expr_free(tmp); ! 609: break; ! 610: default: ! 611: ; ! 612: } ! 613: #undef e1 ! 614: #undef e2 ! 615: } ! 616: ! 617: struct expr *expr_eliminate_dups(struct expr *e) ! 618: { ! 619: int oldcount; ! 620: if (!e) ! 621: return e; ! 622: ! 623: oldcount = trans_count; ! 624: while (1) { ! 625: trans_count = 0; ! 626: switch (e->type) { ! 627: case E_OR: case E_AND: ! 628: expr_eliminate_dups1(e->type, &e, &e); ! 629: expr_eliminate_dups2(e->type, &e, &e); ! 630: default: ! 631: ; ! 632: } ! 633: if (!trans_count) ! 634: break; ! 635: e = expr_eliminate_yn(e); ! 636: } ! 637: trans_count = oldcount; ! 638: return e; ! 639: } ! 640: ! 641: struct expr *expr_transform(struct expr *e) ! 642: { ! 643: struct expr *tmp; ! 644: ! 645: if (!e) ! 646: return NULL; ! 647: switch (e->type) { ! 648: case E_EQUAL: ! 649: case E_UNEQUAL: ! 650: case E_SYMBOL: ! 651: case E_LIST: ! 652: break; ! 653: default: ! 654: e->left.expr = expr_transform(e->left.expr); ! 655: e->right.expr = expr_transform(e->right.expr); ! 656: } ! 657: ! 658: switch (e->type) { ! 659: case E_EQUAL: ! 660: if (e->left.sym->type != S_BOOLEAN) ! 661: break; ! 662: if (e->right.sym == &symbol_no) { ! 663: e->type = E_NOT; ! 664: e->left.expr = expr_alloc_symbol(e->left.sym); ! 665: e->right.sym = NULL; ! 666: break; ! 667: } ! 668: if (e->right.sym == &symbol_mod) { ! 669: printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); ! 670: e->type = E_SYMBOL; ! 671: e->left.sym = &symbol_no; ! 672: e->right.sym = NULL; ! 673: break; ! 674: } ! 675: if (e->right.sym == &symbol_yes) { ! 676: e->type = E_SYMBOL; ! 677: e->right.sym = NULL; ! 678: break; ! 679: } ! 680: break; ! 681: case E_UNEQUAL: ! 682: if (e->left.sym->type != S_BOOLEAN) ! 683: break; ! 684: if (e->right.sym == &symbol_no) { ! 685: e->type = E_SYMBOL; ! 686: e->right.sym = NULL; ! 687: break; ! 688: } ! 689: if (e->right.sym == &symbol_mod) { ! 690: printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); ! 691: e->type = E_SYMBOL; ! 692: e->left.sym = &symbol_yes; ! 693: e->right.sym = NULL; ! 694: break; ! 695: } ! 696: if (e->right.sym == &symbol_yes) { ! 697: e->type = E_NOT; ! 698: e->left.expr = expr_alloc_symbol(e->left.sym); ! 699: e->right.sym = NULL; ! 700: break; ! 701: } ! 702: break; ! 703: case E_NOT: ! 704: switch (e->left.expr->type) { ! 705: case E_NOT: ! 706: // !!a -> a ! 707: tmp = e->left.expr->left.expr; ! 708: free(e->left.expr); ! 709: free(e); ! 710: e = tmp; ! 711: e = expr_transform(e); ! 712: break; ! 713: case E_EQUAL: ! 714: case E_UNEQUAL: ! 715: // !a='x' -> a!='x' ! 716: tmp = e->left.expr; ! 717: free(e); ! 718: e = tmp; ! 719: e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL; ! 720: break; ! 721: case E_OR: ! 722: // !(a || b) -> !a && !b ! 723: tmp = e->left.expr; ! 724: e->type = E_AND; ! 725: e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); ! 726: tmp->type = E_NOT; ! 727: tmp->right.expr = NULL; ! 728: e = expr_transform(e); ! 729: break; ! 730: case E_AND: ! 731: // !(a && b) -> !a || !b ! 732: tmp = e->left.expr; ! 733: e->type = E_OR; ! 734: e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); ! 735: tmp->type = E_NOT; ! 736: tmp->right.expr = NULL; ! 737: e = expr_transform(e); ! 738: break; ! 739: case E_SYMBOL: ! 740: if (e->left.expr->left.sym == &symbol_yes) { ! 741: // !'y' -> 'n' ! 742: tmp = e->left.expr; ! 743: free(e); ! 744: e = tmp; ! 745: e->type = E_SYMBOL; ! 746: e->left.sym = &symbol_no; ! 747: break; ! 748: } ! 749: if (e->left.expr->left.sym == &symbol_mod) { ! 750: // !'m' -> 'm' ! 751: tmp = e->left.expr; ! 752: free(e); ! 753: e = tmp; ! 754: e->type = E_SYMBOL; ! 755: e->left.sym = &symbol_mod; ! 756: break; ! 757: } ! 758: if (e->left.expr->left.sym == &symbol_no) { ! 759: // !'n' -> 'y' ! 760: tmp = e->left.expr; ! 761: free(e); ! 762: e = tmp; ! 763: e->type = E_SYMBOL; ! 764: e->left.sym = &symbol_yes; ! 765: break; ! 766: } ! 767: break; ! 768: default: ! 769: ; ! 770: } ! 771: break; ! 772: default: ! 773: ; ! 774: } ! 775: return e; ! 776: } ! 777: ! 778: int expr_contains_symbol(struct expr *dep, struct symbol *sym) ! 779: { ! 780: if (!dep) ! 781: return 0; ! 782: ! 783: switch (dep->type) { ! 784: case E_AND: ! 785: case E_OR: ! 786: return expr_contains_symbol(dep->left.expr, sym) || ! 787: expr_contains_symbol(dep->right.expr, sym); ! 788: case E_SYMBOL: ! 789: return dep->left.sym == sym; ! 790: case E_EQUAL: ! 791: case E_UNEQUAL: ! 792: return dep->left.sym == sym || ! 793: dep->right.sym == sym; ! 794: case E_NOT: ! 795: return expr_contains_symbol(dep->left.expr, sym); ! 796: default: ! 797: ; ! 798: } ! 799: return 0; ! 800: } ! 801: ! 802: bool expr_depends_symbol(struct expr *dep, struct symbol *sym) ! 803: { ! 804: if (!dep) ! 805: return false; ! 806: ! 807: switch (dep->type) { ! 808: case E_AND: ! 809: return expr_depends_symbol(dep->left.expr, sym) || ! 810: expr_depends_symbol(dep->right.expr, sym); ! 811: case E_SYMBOL: ! 812: return dep->left.sym == sym; ! 813: case E_EQUAL: ! 814: if (dep->left.sym == sym) { ! 815: if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod) ! 816: return true; ! 817: } ! 818: break; ! 819: case E_UNEQUAL: ! 820: if (dep->left.sym == sym) { ! 821: if (dep->right.sym == &symbol_no) ! 822: return true; ! 823: } ! 824: break; ! 825: default: ! 826: ; ! 827: } ! 828: return false; ! 829: } ! 830: ! 831: struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2) ! 832: { ! 833: struct expr *tmp = NULL; ! 834: expr_extract_eq(E_AND, &tmp, ep1, ep2); ! 835: if (tmp) { ! 836: *ep1 = expr_eliminate_yn(*ep1); ! 837: *ep2 = expr_eliminate_yn(*ep2); ! 838: } ! 839: return tmp; ! 840: } ! 841: ! 842: struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2) ! 843: { ! 844: struct expr *tmp = NULL; ! 845: expr_extract_eq(E_OR, &tmp, ep1, ep2); ! 846: if (tmp) { ! 847: *ep1 = expr_eliminate_yn(*ep1); ! 848: *ep2 = expr_eliminate_yn(*ep2); ! 849: } ! 850: return tmp; ! 851: } ! 852: ! 853: void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2) ! 854: { ! 855: #define e1 (*ep1) ! 856: #define e2 (*ep2) ! 857: if (e1->type == type) { ! 858: expr_extract_eq(type, ep, &e1->left.expr, &e2); ! 859: expr_extract_eq(type, ep, &e1->right.expr, &e2); ! 860: return; ! 861: } ! 862: if (e2->type == type) { ! 863: expr_extract_eq(type, ep, ep1, &e2->left.expr); ! 864: expr_extract_eq(type, ep, ep1, &e2->right.expr); ! 865: return; ! 866: } ! 867: if (expr_eq(e1, e2)) { ! 868: *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1; ! 869: expr_free(e2); ! 870: if (type == E_AND) { ! 871: e1 = expr_alloc_symbol(&symbol_yes); ! 872: e2 = expr_alloc_symbol(&symbol_yes); ! 873: } else if (type == E_OR) { ! 874: e1 = expr_alloc_symbol(&symbol_no); ! 875: e2 = expr_alloc_symbol(&symbol_no); ! 876: } ! 877: } ! 878: #undef e1 ! 879: #undef e2 ! 880: } ! 881: ! 882: struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) ! 883: { ! 884: struct expr *e1, *e2; ! 885: ! 886: if (!e) { ! 887: e = expr_alloc_symbol(sym); ! 888: if (type == E_UNEQUAL) ! 889: e = expr_alloc_one(E_NOT, e); ! 890: return e; ! 891: } ! 892: switch (e->type) { ! 893: case E_AND: ! 894: e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); ! 895: e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); ! 896: if (sym == &symbol_yes) ! 897: e = expr_alloc_two(E_AND, e1, e2); ! 898: if (sym == &symbol_no) ! 899: e = expr_alloc_two(E_OR, e1, e2); ! 900: if (type == E_UNEQUAL) ! 901: e = expr_alloc_one(E_NOT, e); ! 902: return e; ! 903: case E_OR: ! 904: e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); ! 905: e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); ! 906: if (sym == &symbol_yes) ! 907: e = expr_alloc_two(E_OR, e1, e2); ! 908: if (sym == &symbol_no) ! 909: e = expr_alloc_two(E_AND, e1, e2); ! 910: if (type == E_UNEQUAL) ! 911: e = expr_alloc_one(E_NOT, e); ! 912: return e; ! 913: case E_NOT: ! 914: return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym); ! 915: case E_UNEQUAL: ! 916: case E_EQUAL: ! 917: if (type == E_EQUAL) { ! 918: if (sym == &symbol_yes) ! 919: return expr_copy(e); ! 920: if (sym == &symbol_mod) ! 921: return expr_alloc_symbol(&symbol_no); ! 922: if (sym == &symbol_no) ! 923: return expr_alloc_one(E_NOT, expr_copy(e)); ! 924: } else { ! 925: if (sym == &symbol_yes) ! 926: return expr_alloc_one(E_NOT, expr_copy(e)); ! 927: if (sym == &symbol_mod) ! 928: return expr_alloc_symbol(&symbol_yes); ! 929: if (sym == &symbol_no) ! 930: return expr_copy(e); ! 931: } ! 932: break; ! 933: case E_SYMBOL: ! 934: return expr_alloc_comp(type, e->left.sym, sym); ! 935: case E_LIST: ! 936: case E_RANGE: ! 937: case E_NONE: ! 938: /* panic */; ! 939: } ! 940: return NULL; ! 941: } ! 942: ! 943: tristate expr_calc_value(struct expr *e) ! 944: { ! 945: tristate val1, val2; ! 946: const char *str1, *str2; ! 947: ! 948: if (!e) ! 949: return yes; ! 950: ! 951: switch (e->type) { ! 952: case E_SYMBOL: ! 953: sym_calc_value(e->left.sym); ! 954: return e->left.sym->curr.tri; ! 955: case E_AND: ! 956: val1 = expr_calc_value(e->left.expr); ! 957: val2 = expr_calc_value(e->right.expr); ! 958: return EXPR_AND(val1, val2); ! 959: case E_OR: ! 960: val1 = expr_calc_value(e->left.expr); ! 961: val2 = expr_calc_value(e->right.expr); ! 962: return EXPR_OR(val1, val2); ! 963: case E_NOT: ! 964: val1 = expr_calc_value(e->left.expr); ! 965: return EXPR_NOT(val1); ! 966: case E_EQUAL: ! 967: sym_calc_value(e->left.sym); ! 968: sym_calc_value(e->right.sym); ! 969: str1 = sym_get_string_value(e->left.sym); ! 970: str2 = sym_get_string_value(e->right.sym); ! 971: return !strcmp(str1, str2) ? yes : no; ! 972: case E_UNEQUAL: ! 973: sym_calc_value(e->left.sym); ! 974: sym_calc_value(e->right.sym); ! 975: str1 = sym_get_string_value(e->left.sym); ! 976: str2 = sym_get_string_value(e->right.sym); ! 977: return !strcmp(str1, str2) ? no : yes; ! 978: default: ! 979: printf("expr_calc_value: %d?\n", e->type); ! 980: return no; ! 981: } ! 982: } ! 983: ! 984: int expr_compare_type(enum expr_type t1, enum expr_type t2) ! 985: { ! 986: #if 0 ! 987: return 1; ! 988: #else ! 989: if (t1 == t2) ! 990: return 0; ! 991: switch (t1) { ! 992: case E_EQUAL: ! 993: case E_UNEQUAL: ! 994: if (t2 == E_NOT) ! 995: return 1; ! 996: case E_NOT: ! 997: if (t2 == E_AND) ! 998: return 1; ! 999: case E_AND: ! 1000: if (t2 == E_OR) ! 1001: return 1; ! 1002: case E_OR: ! 1003: if (t2 == E_LIST) ! 1004: return 1; ! 1005: case E_LIST: ! 1006: if (t2 == 0) ! 1007: return 1; ! 1008: default: ! 1009: return -1; ! 1010: } ! 1011: printf("[%dgt%d?]", t1, t2); ! 1012: return 0; ! 1013: #endif ! 1014: } ! 1015: ! 1016: static inline struct expr * ! 1017: expr_get_leftmost_symbol(const struct expr *e) ! 1018: { ! 1019: ! 1020: if (e == NULL) ! 1021: return NULL; ! 1022: ! 1023: while (e->type != E_SYMBOL) ! 1024: e = e->left.expr; ! 1025: ! 1026: return expr_copy(e); ! 1027: } ! 1028: ! 1029: /* ! 1030: * Given expression `e1' and `e2', returns the leaf of the longest ! 1031: * sub-expression of `e1' not containing 'e2. ! 1032: */ ! 1033: struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2) ! 1034: { ! 1035: struct expr *ret; ! 1036: ! 1037: switch (e1->type) { ! 1038: case E_OR: ! 1039: return expr_alloc_and( ! 1040: expr_simplify_unmet_dep(e1->left.expr, e2), ! 1041: expr_simplify_unmet_dep(e1->right.expr, e2)); ! 1042: case E_AND: { ! 1043: struct expr *e; ! 1044: e = expr_alloc_and(expr_copy(e1), expr_copy(e2)); ! 1045: e = expr_eliminate_dups(e); ! 1046: ret = (!expr_eq(e, e1)) ? e1 : NULL; ! 1047: expr_free(e); ! 1048: break; ! 1049: } ! 1050: default: ! 1051: ret = e1; ! 1052: break; ! 1053: } ! 1054: ! 1055: return expr_get_leftmost_symbol(ret); ! 1056: } ! 1057: ! 1058: void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken) ! 1059: { ! 1060: if (!e) { ! 1061: fn(data, NULL, "y"); ! 1062: return; ! 1063: } ! 1064: ! 1065: if (expr_compare_type(prevtoken, e->type) > 0) ! 1066: fn(data, NULL, "("); ! 1067: switch (e->type) { ! 1068: case E_SYMBOL: ! 1069: if (e->left.sym->name) ! 1070: fn(data, e->left.sym, e->left.sym->name); ! 1071: else ! 1072: fn(data, NULL, "<choice>"); ! 1073: break; ! 1074: case E_NOT: ! 1075: fn(data, NULL, "!"); ! 1076: expr_print(e->left.expr, fn, data, E_NOT); ! 1077: break; ! 1078: case E_EQUAL: ! 1079: if (e->left.sym->name) ! 1080: fn(data, e->left.sym, e->left.sym->name); ! 1081: else ! 1082: fn(data, NULL, "<choice>"); ! 1083: fn(data, NULL, "="); ! 1084: fn(data, e->right.sym, e->right.sym->name); ! 1085: break; ! 1086: case E_UNEQUAL: ! 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, "!="); ! 1092: fn(data, e->right.sym, e->right.sym->name); ! 1093: break; ! 1094: case E_OR: ! 1095: expr_print(e->left.expr, fn, data, E_OR); ! 1096: fn(data, NULL, " || "); ! 1097: expr_print(e->right.expr, fn, data, E_OR); ! 1098: break; ! 1099: case E_AND: ! 1100: expr_print(e->left.expr, fn, data, E_AND); ! 1101: fn(data, NULL, " && "); ! 1102: expr_print(e->right.expr, fn, data, E_AND); ! 1103: break; ! 1104: case E_LIST: ! 1105: fn(data, e->right.sym, e->right.sym->name); ! 1106: if (e->left.expr) { ! 1107: fn(data, NULL, " ^ "); ! 1108: expr_print(e->left.expr, fn, data, E_LIST); ! 1109: } ! 1110: break; ! 1111: case E_RANGE: ! 1112: fn(data, NULL, "["); ! 1113: fn(data, e->left.sym, e->left.sym->name); ! 1114: fn(data, NULL, " "); ! 1115: fn(data, e->right.sym, e->right.sym->name); ! 1116: fn(data, NULL, "]"); ! 1117: break; ! 1118: default: ! 1119: { ! 1120: char buf[32]; ! 1121: sprintf(buf, "<unknown type %d>", e->type); ! 1122: fn(data, NULL, buf); ! 1123: break; ! 1124: } ! 1125: } ! 1126: if (expr_compare_type(prevtoken, e->type) > 0) ! 1127: fn(data, NULL, ")"); ! 1128: } ! 1129: ! 1130: static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) ! 1131: { ! 1132: xfwrite(str, strlen(str), 1, data); ! 1133: } ! 1134: ! 1135: void expr_fprint(struct expr *e, FILE *out) ! 1136: { ! 1137: expr_print(e, expr_print_file_helper, out, E_NONE); ! 1138: } ! 1139: ! 1140: static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) ! 1141: { ! 1142: struct gstr *gs = (struct gstr*)data; ! 1143: const char *sym_str = NULL; ! 1144: ! 1145: if (sym) ! 1146: sym_str = sym_get_string_value(sym); ! 1147: ! 1148: if (gs->max_width) { ! 1149: unsigned extra_length = strlen(str); ! 1150: const char *last_cr = strrchr(gs->s, '\n'); ! 1151: unsigned last_line_length; ! 1152: ! 1153: if (sym_str) ! 1154: extra_length += 4 + strlen(sym_str); ! 1155: ! 1156: if (!last_cr) ! 1157: last_cr = gs->s; ! 1158: ! 1159: last_line_length = strlen(gs->s) - (last_cr - gs->s); ! 1160: ! 1161: if ((last_line_length + extra_length) > gs->max_width) ! 1162: str_append(gs, "\\\n"); ! 1163: } ! 1164: ! 1165: str_append(gs, str); ! 1166: if (sym && sym->type != S_UNKNOWN) ! 1167: str_printf(gs, " [=%s]", sym_str); ! 1168: } ! 1169: ! 1170: void expr_gstr_print(struct expr *e, struct gstr *gs) ! 1171: { ! 1172: expr_print(e, expr_print_gstr_helper, gs, E_NONE); ! 1173: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.