00001
00002
00003
00004
00005
00006 #include <stdio.h>
00007 #include <stdlib.h>
00008 #include <string.h>
00009
00010 #define LKC_DIRECT_LINK
00011 #include "lkc.h"
00012
00013 struct expr *expr_alloc_symbol(struct symbol *sym)
00014 {
00015 struct expr *e = malloc(sizeof(*e));
00016 memset(e, 0, sizeof(*e));
00017 e->type = E_SYMBOL;
00018 e->left.sym = sym;
00019 return e;
00020 }
00021
00022 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
00023 {
00024 struct expr *e = malloc(sizeof(*e));
00025 memset(e, 0, sizeof(*e));
00026 e->type = type;
00027 e->left.expr = ce;
00028 return e;
00029 }
00030
00031 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
00032 {
00033 struct expr *e = malloc(sizeof(*e));
00034 memset(e, 0, sizeof(*e));
00035 e->type = type;
00036 e->left.expr = e1;
00037 e->right.expr = e2;
00038 return e;
00039 }
00040
00041 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
00042 {
00043 struct expr *e = malloc(sizeof(*e));
00044 memset(e, 0, sizeof(*e));
00045 e->type = type;
00046 e->left.sym = s1;
00047 e->right.sym = s2;
00048 return e;
00049 }
00050
00051 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
00052 {
00053 if (!e1)
00054 return e2;
00055 return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
00056 }
00057
00058 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
00059 {
00060 if (!e1)
00061 return e2;
00062 return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
00063 }
00064
00065 struct expr *expr_copy(struct expr *org)
00066 {
00067 struct expr *e;
00068
00069 if (!org)
00070 return NULL;
00071
00072 e = malloc(sizeof(*org));
00073 memcpy(e, org, sizeof(*org));
00074 switch (org->type) {
00075 case E_SYMBOL:
00076 e->left = org->left;
00077 break;
00078 case E_NOT:
00079 e->left.expr = expr_copy(org->left.expr);
00080 break;
00081 case E_EQUAL:
00082 case E_UNEQUAL:
00083 e->left.sym = org->left.sym;
00084 e->right.sym = org->right.sym;
00085 break;
00086 case E_AND:
00087 case E_OR:
00088 case E_CHOICE:
00089 e->left.expr = expr_copy(org->left.expr);
00090 e->right.expr = expr_copy(org->right.expr);
00091 break;
00092 default:
00093 printf("can't copy type %d\n", e->type);
00094 free(e);
00095 e = NULL;
00096 break;
00097 }
00098
00099 return e;
00100 }
00101
00102 void expr_free(struct expr *e)
00103 {
00104 if (!e)
00105 return;
00106
00107 switch (e->type) {
00108 case E_SYMBOL:
00109 break;
00110 case E_NOT:
00111 expr_free(e->left.expr);
00112 return;
00113 case E_EQUAL:
00114 case E_UNEQUAL:
00115 break;
00116 case E_OR:
00117 case E_AND:
00118 expr_free(e->left.expr);
00119 expr_free(e->right.expr);
00120 break;
00121 default:
00122 printf("how to free type %d?\n", e->type);
00123 break;
00124 }
00125 free(e);
00126 }
00127
00128 static int trans_count;
00129
00130 #define e1 (*ep1)
00131 #define e2 (*ep2)
00132
00133 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
00134 {
00135 if (e1->type == type) {
00136 __expr_eliminate_eq(type, &e1->left.expr, &e2);
00137 __expr_eliminate_eq(type, &e1->right.expr, &e2);
00138 return;
00139 }
00140 if (e2->type == type) {
00141 __expr_eliminate_eq(type, &e1, &e2->left.expr);
00142 __expr_eliminate_eq(type, &e1, &e2->right.expr);
00143 return;
00144 }
00145 if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
00146 e1->left.sym == e2->left.sym && (e1->left.sym->flags & (SYMBOL_YES|SYMBOL_NO)))
00147 return;
00148 if (!expr_eq(e1, e2))
00149 return;
00150 trans_count++;
00151 expr_free(e1); expr_free(e2);
00152 switch (type) {
00153 case E_OR:
00154 e1 = expr_alloc_symbol(&symbol_no);
00155 e2 = expr_alloc_symbol(&symbol_no);
00156 break;
00157 case E_AND:
00158 e1 = expr_alloc_symbol(&symbol_yes);
00159 e2 = expr_alloc_symbol(&symbol_yes);
00160 break;
00161 default:
00162 ;
00163 }
00164 }
00165
00166 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
00167 {
00168 if (!e1 || !e2)
00169 return;
00170 switch (e1->type) {
00171 case E_OR:
00172 case E_AND:
00173 __expr_eliminate_eq(e1->type, ep1, ep2);
00174 default:
00175 ;
00176 }
00177 if (e1->type != e2->type) switch (e2->type) {
00178 case E_OR:
00179 case E_AND:
00180 __expr_eliminate_eq(e2->type, ep1, ep2);
00181 default:
00182 ;
00183 }
00184 e1 = expr_eliminate_yn(e1);
00185 e2 = expr_eliminate_yn(e2);
00186 }
00187
00188 #undef e1
00189 #undef e2
00190
00191 int expr_eq(struct expr *e1, struct expr *e2)
00192 {
00193 int res, old_count;
00194
00195 if (e1->type != e2->type)
00196 return 0;
00197 switch (e1->type) {
00198 case E_EQUAL:
00199 case E_UNEQUAL:
00200 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
00201 case E_SYMBOL:
00202 return e1->left.sym == e2->left.sym;
00203 case E_NOT:
00204 return expr_eq(e1->left.expr, e2->left.expr);
00205 case E_AND:
00206 case E_OR:
00207 e1 = expr_copy(e1);
00208 e2 = expr_copy(e2);
00209 old_count = trans_count;
00210 expr_eliminate_eq(&e1, &e2);
00211 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
00212 e1->left.sym == e2->left.sym);
00213 expr_free(e1);
00214 expr_free(e2);
00215 trans_count = old_count;
00216 return res;
00217 case E_CHOICE:
00218 case E_RANGE:
00219 case E_NONE:
00220 ;
00221 }
00222
00223 print_expr(0, e1, 0);
00224 printf(" = ");
00225 print_expr(0, e2, 0);
00226 printf(" ?\n");
00227
00228 return 0;
00229 }
00230
00231 struct expr *expr_eliminate_yn(struct expr *e)
00232 {
00233 struct expr *tmp;
00234
00235 if (e) switch (e->type) {
00236 case E_AND:
00237 e->left.expr = expr_eliminate_yn(e->left.expr);
00238 e->right.expr = expr_eliminate_yn(e->right.expr);
00239 if (e->left.expr->type == E_SYMBOL) {
00240 if (e->left.expr->left.sym == &symbol_no) {
00241 expr_free(e->left.expr);
00242 expr_free(e->right.expr);
00243 e->type = E_SYMBOL;
00244 e->left.sym = &symbol_no;
00245 e->right.expr = NULL;
00246 return e;
00247 } else if (e->left.expr->left.sym == &symbol_yes) {
00248 free(e->left.expr);
00249 tmp = e->right.expr;
00250 *e = *(e->right.expr);
00251 free(tmp);
00252 return e;
00253 }
00254 }
00255 if (e->right.expr->type == E_SYMBOL) {
00256 if (e->right.expr->left.sym == &symbol_no) {
00257 expr_free(e->left.expr);
00258 expr_free(e->right.expr);
00259 e->type = E_SYMBOL;
00260 e->left.sym = &symbol_no;
00261 e->right.expr = NULL;
00262 return e;
00263 } else if (e->right.expr->left.sym == &symbol_yes) {
00264 free(e->right.expr);
00265 tmp = e->left.expr;
00266 *e = *(e->left.expr);
00267 free(tmp);
00268 return e;
00269 }
00270 }
00271 break;
00272 case E_OR:
00273 e->left.expr = expr_eliminate_yn(e->left.expr);
00274 e->right.expr = expr_eliminate_yn(e->right.expr);
00275 if (e->left.expr->type == E_SYMBOL) {
00276 if (e->left.expr->left.sym == &symbol_no) {
00277 free(e->left.expr);
00278 tmp = e->right.expr;
00279 *e = *(e->right.expr);
00280 free(tmp);
00281 return e;
00282 } else if (e->left.expr->left.sym == &symbol_yes) {
00283 expr_free(e->left.expr);
00284 expr_free(e->right.expr);
00285 e->type = E_SYMBOL;
00286 e->left.sym = &symbol_yes;
00287 e->right.expr = NULL;
00288 return e;
00289 }
00290 }
00291 if (e->right.expr->type == E_SYMBOL) {
00292 if (e->right.expr->left.sym == &symbol_no) {
00293 free(e->right.expr);
00294 tmp = e->left.expr;
00295 *e = *(e->left.expr);
00296 free(tmp);
00297 return e;
00298 } else if (e->right.expr->left.sym == &symbol_yes) {
00299 expr_free(e->left.expr);
00300 expr_free(e->right.expr);
00301 e->type = E_SYMBOL;
00302 e->left.sym = &symbol_yes;
00303 e->right.expr = NULL;
00304 return e;
00305 }
00306 }
00307 break;
00308 default:
00309 ;
00310 }
00311 return e;
00312 }
00313
00314
00315
00316
00317 struct expr *expr_trans_bool(struct expr *e)
00318 {
00319 if (!e)
00320 return NULL;
00321 switch (e->type) {
00322 case E_AND:
00323 case E_OR:
00324 case E_NOT:
00325 e->left.expr = expr_trans_bool(e->left.expr);
00326 e->right.expr = expr_trans_bool(e->right.expr);
00327 break;
00328 case E_UNEQUAL:
00329
00330 if (e->left.sym->type == S_TRISTATE) {
00331 if (e->right.sym == &symbol_no) {
00332 e->type = E_SYMBOL;
00333 e->right.sym = NULL;
00334 }
00335 }
00336 break;
00337 default:
00338 ;
00339 }
00340 return e;
00341 }
00342
00343
00344
00345
00346 struct expr *expr_join_or(struct expr *e1, struct expr *e2)
00347 {
00348 struct expr *tmp;
00349 struct symbol *sym1, *sym2;
00350
00351 if (expr_eq(e1, e2))
00352 return expr_copy(e1);
00353 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
00354 return NULL;
00355 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
00356 return NULL;
00357 if (e1->type == E_NOT) {
00358 tmp = e1->left.expr;
00359 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
00360 return NULL;
00361 sym1 = tmp->left.sym;
00362 } else
00363 sym1 = e1->left.sym;
00364 if (e2->type == E_NOT) {
00365 if (e2->left.expr->type != E_SYMBOL)
00366 return NULL;
00367 sym2 = e2->left.expr->left.sym;
00368 } else
00369 sym2 = e2->left.sym;
00370 if (sym1 != sym2)
00371 return NULL;
00372 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
00373 return NULL;
00374 if (sym1->type == S_TRISTATE) {
00375 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
00376 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
00377 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
00378
00379 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
00380 }
00381 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
00382 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
00383 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
00384
00385 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
00386 }
00387 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
00388 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
00389 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
00390
00391 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
00392 }
00393 }
00394 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
00395 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
00396 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
00397 return expr_alloc_symbol(&symbol_yes);
00398 }
00399
00400 printf("optimize ");
00401 print_expr(0, e1, 0);
00402 printf(" || ");
00403 print_expr(0, e2, 0);
00404 printf(" ?\n");
00405 return NULL;
00406 }
00407
00408 struct expr *expr_join_and(struct expr *e1, struct expr *e2)
00409 {
00410 struct expr *tmp;
00411 struct symbol *sym1, *sym2;
00412
00413 if (expr_eq(e1, e2))
00414 return expr_copy(e1);
00415 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
00416 return NULL;
00417 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
00418 return NULL;
00419 if (e1->type == E_NOT) {
00420 tmp = e1->left.expr;
00421 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
00422 return NULL;
00423 sym1 = tmp->left.sym;
00424 } else
00425 sym1 = e1->left.sym;
00426 if (e2->type == E_NOT) {
00427 if (e2->left.expr->type != E_SYMBOL)
00428 return NULL;
00429 sym2 = e2->left.expr->left.sym;
00430 } else
00431 sym2 = e2->left.sym;
00432 if (sym1 != sym2)
00433 return NULL;
00434 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
00435 return NULL;
00436
00437 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
00438 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
00439
00440 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
00441
00442 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
00443 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
00444
00445 return expr_alloc_symbol(sym1);
00446
00447 if (sym1->type == S_TRISTATE) {
00448 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
00449
00450 sym2 = e1->right.sym;
00451 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
00452 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
00453 : expr_alloc_symbol(&symbol_no);
00454 }
00455 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
00456
00457 sym2 = e2->right.sym;
00458 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
00459 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
00460 : expr_alloc_symbol(&symbol_no);
00461 }
00462 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
00463 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
00464 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
00465
00466 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
00467
00468 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
00469 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
00470 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
00471
00472 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
00473
00474 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
00475 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
00476 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
00477
00478 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
00479
00480 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
00481 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
00482 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
00483 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
00484 return NULL;
00485 }
00486 printf("optimize ");
00487 print_expr(0, e1, 0);
00488 printf(" && ");
00489 print_expr(0, e2, 0);
00490 printf(" ?\n");
00491 return NULL;
00492 }
00493
00494 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
00495 {
00496 #define e1 (*ep1)
00497 #define e2 (*ep2)
00498 struct expr *tmp;
00499
00500 if (e1->type == type) {
00501 expr_eliminate_dups1(type, &e1->left.expr, &e2);
00502 expr_eliminate_dups1(type, &e1->right.expr, &e2);
00503 return;
00504 }
00505 if (e2->type == type) {
00506 expr_eliminate_dups1(type, &e1, &e2->left.expr);
00507 expr_eliminate_dups1(type, &e1, &e2->right.expr);
00508 return;
00509 }
00510 if (e1 == e2)
00511 return;
00512
00513 switch (e1->type) {
00514 case E_OR: case E_AND:
00515 expr_eliminate_dups1(e1->type, &e1, &e1);
00516 default:
00517 ;
00518 }
00519
00520 switch (type) {
00521 case E_OR:
00522 tmp = expr_join_or(e1, e2);
00523 if (tmp) {
00524 expr_free(e1); expr_free(e2);
00525 e1 = expr_alloc_symbol(&symbol_no);
00526 e2 = tmp;
00527 trans_count++;
00528 }
00529 break;
00530 case E_AND:
00531 tmp = expr_join_and(e1, e2);
00532 if (tmp) {
00533 expr_free(e1); expr_free(e2);
00534 e1 = expr_alloc_symbol(&symbol_yes);
00535 e2 = tmp;
00536 trans_count++;
00537 }
00538 break;
00539 default:
00540 ;
00541 }
00542 #undef e1
00543 #undef e2
00544 }
00545
00546 static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
00547 {
00548 #define e1 (*ep1)
00549 #define e2 (*ep2)
00550 struct expr *tmp, *tmp1, *tmp2;
00551
00552 if (e1->type == type) {
00553 expr_eliminate_dups2(type, &e1->left.expr, &e2);
00554 expr_eliminate_dups2(type, &e1->right.expr, &e2);
00555 return;
00556 }
00557 if (e2->type == type) {
00558 expr_eliminate_dups2(type, &e1, &e2->left.expr);
00559 expr_eliminate_dups2(type, &e1, &e2->right.expr);
00560 }
00561 if (e1 == e2)
00562 return;
00563
00564 switch (e1->type) {
00565 case E_OR:
00566 expr_eliminate_dups2(e1->type, &e1, &e1);
00567
00568 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
00569 tmp2 = expr_copy(e2);
00570 tmp = expr_extract_eq_and(&tmp1, &tmp2);
00571 if (expr_is_yes(tmp1)) {
00572 expr_free(e1);
00573 e1 = expr_alloc_symbol(&symbol_no);
00574 trans_count++;
00575 }
00576 expr_free(tmp2);
00577 expr_free(tmp1);
00578 expr_free(tmp);
00579 break;
00580 case E_AND:
00581 expr_eliminate_dups2(e1->type, &e1, &e1);
00582
00583 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
00584 tmp2 = expr_copy(e2);
00585 tmp = expr_extract_eq_or(&tmp1, &tmp2);
00586 if (expr_is_no(tmp1)) {
00587 expr_free(e1);
00588 e1 = expr_alloc_symbol(&symbol_yes);
00589 trans_count++;
00590 }
00591 expr_free(tmp2);
00592 expr_free(tmp1);
00593 expr_free(tmp);
00594 break;
00595 default:
00596 ;
00597 }
00598 #undef e1
00599 #undef e2
00600 }
00601
00602 struct expr *expr_eliminate_dups(struct expr *e)
00603 {
00604 int oldcount;
00605 if (!e)
00606 return e;
00607
00608 oldcount = trans_count;
00609 while (1) {
00610 trans_count = 0;
00611 switch (e->type) {
00612 case E_OR: case E_AND:
00613 expr_eliminate_dups1(e->type, &e, &e);
00614 expr_eliminate_dups2(e->type, &e, &e);
00615 default:
00616 ;
00617 }
00618 if (!trans_count)
00619 break;
00620 e = expr_eliminate_yn(e);
00621 }
00622 trans_count = oldcount;
00623 return e;
00624 }
00625
00626 struct expr *expr_transform(struct expr *e)
00627 {
00628 struct expr *tmp;
00629
00630 if (!e)
00631 return NULL;
00632 switch (e->type) {
00633 case E_EQUAL:
00634 case E_UNEQUAL:
00635 case E_SYMBOL:
00636 case E_CHOICE:
00637 break;
00638 default:
00639 e->left.expr = expr_transform(e->left.expr);
00640 e->right.expr = expr_transform(e->right.expr);
00641 }
00642
00643 switch (e->type) {
00644 case E_EQUAL:
00645 if (e->left.sym->type != S_BOOLEAN)
00646 break;
00647 if (e->right.sym == &symbol_no) {
00648 e->type = E_NOT;
00649 e->left.expr = expr_alloc_symbol(e->left.sym);
00650 e->right.sym = NULL;
00651 break;
00652 }
00653 if (e->right.sym == &symbol_mod) {
00654 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
00655 e->type = E_SYMBOL;
00656 e->left.sym = &symbol_no;
00657 e->right.sym = NULL;
00658 break;
00659 }
00660 if (e->right.sym == &symbol_yes) {
00661 e->type = E_SYMBOL;
00662 e->right.sym = NULL;
00663 break;
00664 }
00665 break;
00666 case E_UNEQUAL:
00667 if (e->left.sym->type != S_BOOLEAN)
00668 break;
00669 if (e->right.sym == &symbol_no) {
00670 e->type = E_SYMBOL;
00671 e->right.sym = NULL;
00672 break;
00673 }
00674 if (e->right.sym == &symbol_mod) {
00675 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
00676 e->type = E_SYMBOL;
00677 e->left.sym = &symbol_yes;
00678 e->right.sym = NULL;
00679 break;
00680 }
00681 if (e->right.sym == &symbol_yes) {
00682 e->type = E_NOT;
00683 e->left.expr = expr_alloc_symbol(e->left.sym);
00684 e->right.sym = NULL;
00685 break;
00686 }
00687 break;
00688 case E_NOT:
00689 switch (e->left.expr->type) {
00690 case E_NOT:
00691
00692 tmp = e->left.expr->left.expr;
00693 free(e->left.expr);
00694 free(e);
00695 e = tmp;
00696 e = expr_transform(e);
00697 break;
00698 case E_EQUAL:
00699 case E_UNEQUAL:
00700
00701 tmp = e->left.expr;
00702 free(e);
00703 e = tmp;
00704 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
00705 break;
00706 case E_OR:
00707
00708 tmp = e->left.expr;
00709 e->type = E_AND;
00710 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
00711 tmp->type = E_NOT;
00712 tmp->right.expr = NULL;
00713 e = expr_transform(e);
00714 break;
00715 case E_AND:
00716
00717 tmp = e->left.expr;
00718 e->type = E_OR;
00719 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
00720 tmp->type = E_NOT;
00721 tmp->right.expr = NULL;
00722 e = expr_transform(e);
00723 break;
00724 case E_SYMBOL:
00725 if (e->left.expr->left.sym == &symbol_yes) {
00726
00727 tmp = e->left.expr;
00728 free(e);
00729 e = tmp;
00730 e->type = E_SYMBOL;
00731 e->left.sym = &symbol_no;
00732 break;
00733 }
00734 if (e->left.expr->left.sym == &symbol_mod) {
00735
00736 tmp = e->left.expr;
00737 free(e);
00738 e = tmp;
00739 e->type = E_SYMBOL;
00740 e->left.sym = &symbol_mod;
00741 break;
00742 }
00743 if (e->left.expr->left.sym == &symbol_no) {
00744
00745 tmp = e->left.expr;
00746 free(e);
00747 e = tmp;
00748 e->type = E_SYMBOL;
00749 e->left.sym = &symbol_yes;
00750 break;
00751 }
00752 break;
00753 default:
00754 ;
00755 }
00756 break;
00757 default:
00758 ;
00759 }
00760 return e;
00761 }
00762
00763 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
00764 {
00765 if (!dep)
00766 return 0;
00767
00768 switch (dep->type) {
00769 case E_AND:
00770 case E_OR:
00771 return expr_contains_symbol(dep->left.expr, sym) ||
00772 expr_contains_symbol(dep->right.expr, sym);
00773 case E_SYMBOL:
00774 return dep->left.sym == sym;
00775 case E_EQUAL:
00776 case E_UNEQUAL:
00777 return dep->left.sym == sym ||
00778 dep->right.sym == sym;
00779 case E_NOT:
00780 return expr_contains_symbol(dep->left.expr, sym);
00781 default:
00782 ;
00783 }
00784 return 0;
00785 }
00786
00787 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
00788 {
00789 if (!dep)
00790 return false;
00791
00792 switch (dep->type) {
00793 case E_AND:
00794 return expr_depends_symbol(dep->left.expr, sym) ||
00795 expr_depends_symbol(dep->right.expr, sym);
00796 case E_SYMBOL:
00797 return dep->left.sym == sym;
00798 case E_EQUAL:
00799 if (dep->left.sym == sym) {
00800 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
00801 return true;
00802 }
00803 break;
00804 case E_UNEQUAL:
00805 if (dep->left.sym == sym) {
00806 if (dep->right.sym == &symbol_no)
00807 return true;
00808 }
00809 break;
00810 default:
00811 ;
00812 }
00813 return false;
00814 }
00815
00816 struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
00817 {
00818 struct expr *tmp = NULL;
00819 expr_extract_eq(E_AND, &tmp, ep1, ep2);
00820 if (tmp) {
00821 *ep1 = expr_eliminate_yn(*ep1);
00822 *ep2 = expr_eliminate_yn(*ep2);
00823 }
00824 return tmp;
00825 }
00826
00827 struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
00828 {
00829 struct expr *tmp = NULL;
00830 expr_extract_eq(E_OR, &tmp, ep1, ep2);
00831 if (tmp) {
00832 *ep1 = expr_eliminate_yn(*ep1);
00833 *ep2 = expr_eliminate_yn(*ep2);
00834 }
00835 return tmp;
00836 }
00837
00838 void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
00839 {
00840 #define e1 (*ep1)
00841 #define e2 (*ep2)
00842 if (e1->type == type) {
00843 expr_extract_eq(type, ep, &e1->left.expr, &e2);
00844 expr_extract_eq(type, ep, &e1->right.expr, &e2);
00845 return;
00846 }
00847 if (e2->type == type) {
00848 expr_extract_eq(type, ep, ep1, &e2->left.expr);
00849 expr_extract_eq(type, ep, ep1, &e2->right.expr);
00850 return;
00851 }
00852 if (expr_eq(e1, e2)) {
00853 *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
00854 expr_free(e2);
00855 if (type == E_AND) {
00856 e1 = expr_alloc_symbol(&symbol_yes);
00857 e2 = expr_alloc_symbol(&symbol_yes);
00858 } else if (type == E_OR) {
00859 e1 = expr_alloc_symbol(&symbol_no);
00860 e2 = expr_alloc_symbol(&symbol_no);
00861 }
00862 }
00863 #undef e1
00864 #undef e2
00865 }
00866
00867 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
00868 {
00869 struct expr *e1, *e2;
00870
00871 if (!e) {
00872 e = expr_alloc_symbol(sym);
00873 if (type == E_UNEQUAL)
00874 e = expr_alloc_one(E_NOT, e);
00875 return e;
00876 }
00877 switch (e->type) {
00878 case E_AND:
00879 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
00880 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
00881 if (sym == &symbol_yes)
00882 e = expr_alloc_two(E_AND, e1, e2);
00883 if (sym == &symbol_no)
00884 e = expr_alloc_two(E_OR, e1, e2);
00885 if (type == E_UNEQUAL)
00886 e = expr_alloc_one(E_NOT, e);
00887 return e;
00888 case E_OR:
00889 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
00890 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
00891 if (sym == &symbol_yes)
00892 e = expr_alloc_two(E_OR, e1, e2);
00893 if (sym == &symbol_no)
00894 e = expr_alloc_two(E_AND, e1, e2);
00895 if (type == E_UNEQUAL)
00896 e = expr_alloc_one(E_NOT, e);
00897 return e;
00898 case E_NOT:
00899 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
00900 case E_UNEQUAL:
00901 case E_EQUAL:
00902 if (type == E_EQUAL) {
00903 if (sym == &symbol_yes)
00904 return expr_copy(e);
00905 if (sym == &symbol_mod)
00906 return expr_alloc_symbol(&symbol_no);
00907 if (sym == &symbol_no)
00908 return expr_alloc_one(E_NOT, expr_copy(e));
00909 } else {
00910 if (sym == &symbol_yes)
00911 return expr_alloc_one(E_NOT, expr_copy(e));
00912 if (sym == &symbol_mod)
00913 return expr_alloc_symbol(&symbol_yes);
00914 if (sym == &symbol_no)
00915 return expr_copy(e);
00916 }
00917 break;
00918 case E_SYMBOL:
00919 return expr_alloc_comp(type, e->left.sym, sym);
00920 case E_CHOICE:
00921 case E_RANGE:
00922 case E_NONE:
00923 ;
00924 }
00925 return NULL;
00926 }
00927
00928 tristate expr_calc_value(struct expr *e)
00929 {
00930 tristate val1, val2;
00931 const char *str1, *str2;
00932
00933 if (!e)
00934 return yes;
00935
00936 switch (e->type) {
00937 case E_SYMBOL:
00938 sym_calc_value(e->left.sym);
00939 return e->left.sym->curr.tri;
00940 case E_AND:
00941 val1 = expr_calc_value(e->left.expr);
00942 val2 = expr_calc_value(e->right.expr);
00943 return E_AND(val1, val2);
00944 case E_OR:
00945 val1 = expr_calc_value(e->left.expr);
00946 val2 = expr_calc_value(e->right.expr);
00947 return E_OR(val1, val2);
00948 case E_NOT:
00949 val1 = expr_calc_value(e->left.expr);
00950 return E_NOT(val1);
00951 case E_EQUAL:
00952 sym_calc_value(e->left.sym);
00953 sym_calc_value(e->right.sym);
00954 str1 = sym_get_string_value(e->left.sym);
00955 str2 = sym_get_string_value(e->right.sym);
00956 return !strcmp(str1, str2) ? yes : no;
00957 case E_UNEQUAL:
00958 sym_calc_value(e->left.sym);
00959 sym_calc_value(e->right.sym);
00960 str1 = sym_get_string_value(e->left.sym);
00961 str2 = sym_get_string_value(e->right.sym);
00962 return !strcmp(str1, str2) ? no : yes;
00963 default:
00964 printf("expr_calc_value: %d?\n", e->type);
00965 return no;
00966 }
00967 }
00968
00969 int expr_compare_type(enum expr_type t1, enum expr_type t2)
00970 {
00971 #if 0
00972 return 1;
00973 #else
00974 if (t1 == t2)
00975 return 0;
00976 switch (t1) {
00977 case E_EQUAL:
00978 case E_UNEQUAL:
00979 if (t2 == E_NOT)
00980 return 1;
00981 case E_NOT:
00982 if (t2 == E_AND)
00983 return 1;
00984 case E_AND:
00985 if (t2 == E_OR)
00986 return 1;
00987 case E_OR:
00988 if (t2 == E_CHOICE)
00989 return 1;
00990 case E_CHOICE:
00991 if (t2 == 0)
00992 return 1;
00993 default:
00994 return -1;
00995 }
00996 printf("[%dgt%d?]", t1, t2);
00997 return 0;
00998 #endif
00999 }
01000
01001 void expr_print(struct expr *e, void (*fn)(void *, const char *), void *data, int prevtoken)
01002 {
01003 if (!e) {
01004 fn(data, "y");
01005 return;
01006 }
01007
01008 if (expr_compare_type(prevtoken, e->type) > 0)
01009 fn(data, "(");
01010 switch (e->type) {
01011 case E_SYMBOL:
01012 if (e->left.sym->name)
01013 fn(data, e->left.sym->name);
01014 else
01015 fn(data, "<choice>");
01016 break;
01017 case E_NOT:
01018 fn(data, "!");
01019 expr_print(e->left.expr, fn, data, E_NOT);
01020 break;
01021 case E_EQUAL:
01022 fn(data, e->left.sym->name);
01023 fn(data, "=");
01024 fn(data, e->right.sym->name);
01025 break;
01026 case E_UNEQUAL:
01027 fn(data, e->left.sym->name);
01028 fn(data, "!=");
01029 fn(data, e->right.sym->name);
01030 break;
01031 case E_OR:
01032 expr_print(e->left.expr, fn, data, E_OR);
01033 fn(data, " || ");
01034 expr_print(e->right.expr, fn, data, E_OR);
01035 break;
01036 case E_AND:
01037 expr_print(e->left.expr, fn, data, E_AND);
01038 fn(data, " && ");
01039 expr_print(e->right.expr, fn, data, E_AND);
01040 break;
01041 case E_CHOICE:
01042 fn(data, e->right.sym->name);
01043 if (e->left.expr) {
01044 fn(data, " ^ ");
01045 expr_print(e->left.expr, fn, data, E_CHOICE);
01046 }
01047 break;
01048 case E_RANGE:
01049 fn(data, "[");
01050 fn(data, e->left.sym->name);
01051 fn(data, " ");
01052 fn(data, e->right.sym->name);
01053 fn(data, "]");
01054 break;
01055 default:
01056 {
01057 char buf[32];
01058 sprintf(buf, "<unknown type %d>", e->type);
01059 fn(data, buf);
01060 break;
01061 }
01062 }
01063 if (expr_compare_type(prevtoken, e->type) > 0)
01064 fn(data, ")");
01065 }
01066
01067 static void expr_print_file_helper(void *data, const char *str)
01068 {
01069 fwrite(str, strlen(str), 1, data);
01070 }
01071
01072 void expr_fprint(struct expr *e, FILE *out)
01073 {
01074 expr_print(e, expr_print_file_helper, out, E_NONE);
01075 }
01076
01077 void print_expr(int mask, struct expr *e, int prevtoken)
01078 {
01079 if (!(cdebug & mask))
01080 return;
01081 expr_fprint(e, stdout);
01082 }
01083