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