1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/kconfig/expr.c Mon Jul 28 21:32:33 2008 +0000
1.3 @@ -0,0 +1,1100 @@
1.4 +/*
1.5 + * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
1.6 + * Released under the terms of the GNU GPL v2.0.
1.7 + */
1.8 +
1.9 +#include <stdio.h>
1.10 +#include <stdlib.h>
1.11 +#include <string.h>
1.12 +
1.13 +#define LKC_DIRECT_LINK
1.14 +#include "lkc.h"
1.15 +
1.16 +#define DEBUG_EXPR 0
1.17 +
1.18 +struct expr *expr_alloc_symbol(struct symbol *sym)
1.19 +{
1.20 + struct expr *e = malloc(sizeof(*e));
1.21 + memset(e, 0, sizeof(*e));
1.22 + e->type = E_SYMBOL;
1.23 + e->left.sym = sym;
1.24 + return e;
1.25 +}
1.26 +
1.27 +struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
1.28 +{
1.29 + struct expr *e = malloc(sizeof(*e));
1.30 + memset(e, 0, sizeof(*e));
1.31 + e->type = type;
1.32 + e->left.expr = ce;
1.33 + return e;
1.34 +}
1.35 +
1.36 +struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
1.37 +{
1.38 + struct expr *e = malloc(sizeof(*e));
1.39 + memset(e, 0, sizeof(*e));
1.40 + e->type = type;
1.41 + e->left.expr = e1;
1.42 + e->right.expr = e2;
1.43 + return e;
1.44 +}
1.45 +
1.46 +struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
1.47 +{
1.48 + struct expr *e = malloc(sizeof(*e));
1.49 + memset(e, 0, sizeof(*e));
1.50 + e->type = type;
1.51 + e->left.sym = s1;
1.52 + e->right.sym = s2;
1.53 + return e;
1.54 +}
1.55 +
1.56 +struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
1.57 +{
1.58 + if (!e1)
1.59 + return e2;
1.60 + return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
1.61 +}
1.62 +
1.63 +struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
1.64 +{
1.65 + if (!e1)
1.66 + return e2;
1.67 + return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
1.68 +}
1.69 +
1.70 +struct expr *expr_copy(struct expr *org)
1.71 +{
1.72 + struct expr *e;
1.73 +
1.74 + if (!org)
1.75 + return NULL;
1.76 +
1.77 + e = malloc(sizeof(*org));
1.78 + memcpy(e, org, sizeof(*org));
1.79 + switch (org->type) {
1.80 + case E_SYMBOL:
1.81 + e->left = org->left;
1.82 + break;
1.83 + case E_NOT:
1.84 + e->left.expr = expr_copy(org->left.expr);
1.85 + break;
1.86 + case E_EQUAL:
1.87 + case E_UNEQUAL:
1.88 + e->left.sym = org->left.sym;
1.89 + e->right.sym = org->right.sym;
1.90 + break;
1.91 + case E_AND:
1.92 + case E_OR:
1.93 + case E_CHOICE:
1.94 + e->left.expr = expr_copy(org->left.expr);
1.95 + e->right.expr = expr_copy(org->right.expr);
1.96 + break;
1.97 + default:
1.98 + printf("can't copy type %d\n", e->type);
1.99 + free(e);
1.100 + e = NULL;
1.101 + break;
1.102 + }
1.103 +
1.104 + return e;
1.105 +}
1.106 +
1.107 +void expr_free(struct expr *e)
1.108 +{
1.109 + if (!e)
1.110 + return;
1.111 +
1.112 + switch (e->type) {
1.113 + case E_SYMBOL:
1.114 + break;
1.115 + case E_NOT:
1.116 + expr_free(e->left.expr);
1.117 + return;
1.118 + case E_EQUAL:
1.119 + case E_UNEQUAL:
1.120 + break;
1.121 + case E_OR:
1.122 + case E_AND:
1.123 + expr_free(e->left.expr);
1.124 + expr_free(e->right.expr);
1.125 + break;
1.126 + default:
1.127 + printf("how to free type %d?\n", e->type);
1.128 + break;
1.129 + }
1.130 + free(e);
1.131 +}
1.132 +
1.133 +static int trans_count;
1.134 +
1.135 +#define e1 (*ep1)
1.136 +#define e2 (*ep2)
1.137 +
1.138 +static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
1.139 +{
1.140 + if (e1->type == type) {
1.141 + __expr_eliminate_eq(type, &e1->left.expr, &e2);
1.142 + __expr_eliminate_eq(type, &e1->right.expr, &e2);
1.143 + return;
1.144 + }
1.145 + if (e2->type == type) {
1.146 + __expr_eliminate_eq(type, &e1, &e2->left.expr);
1.147 + __expr_eliminate_eq(type, &e1, &e2->right.expr);
1.148 + return;
1.149 + }
1.150 + if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
1.151 + e1->left.sym == e2->left.sym &&
1.152 + (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
1.153 + return;
1.154 + if (!expr_eq(e1, e2))
1.155 + return;
1.156 + trans_count++;
1.157 + expr_free(e1); expr_free(e2);
1.158 + switch (type) {
1.159 + case E_OR:
1.160 + e1 = expr_alloc_symbol(&symbol_no);
1.161 + e2 = expr_alloc_symbol(&symbol_no);
1.162 + break;
1.163 + case E_AND:
1.164 + e1 = expr_alloc_symbol(&symbol_yes);
1.165 + e2 = expr_alloc_symbol(&symbol_yes);
1.166 + break;
1.167 + default:
1.168 + ;
1.169 + }
1.170 +}
1.171 +
1.172 +void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
1.173 +{
1.174 + if (!e1 || !e2)
1.175 + return;
1.176 + switch (e1->type) {
1.177 + case E_OR:
1.178 + case E_AND:
1.179 + __expr_eliminate_eq(e1->type, ep1, ep2);
1.180 + default:
1.181 + ;
1.182 + }
1.183 + if (e1->type != e2->type) switch (e2->type) {
1.184 + case E_OR:
1.185 + case E_AND:
1.186 + __expr_eliminate_eq(e2->type, ep1, ep2);
1.187 + default:
1.188 + ;
1.189 + }
1.190 + e1 = expr_eliminate_yn(e1);
1.191 + e2 = expr_eliminate_yn(e2);
1.192 +}
1.193 +
1.194 +#undef e1
1.195 +#undef e2
1.196 +
1.197 +int expr_eq(struct expr *e1, struct expr *e2)
1.198 +{
1.199 + int res, old_count;
1.200 +
1.201 + if (e1->type != e2->type)
1.202 + return 0;
1.203 + switch (e1->type) {
1.204 + case E_EQUAL:
1.205 + case E_UNEQUAL:
1.206 + return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
1.207 + case E_SYMBOL:
1.208 + return e1->left.sym == e2->left.sym;
1.209 + case E_NOT:
1.210 + return expr_eq(e1->left.expr, e2->left.expr);
1.211 + case E_AND:
1.212 + case E_OR:
1.213 + e1 = expr_copy(e1);
1.214 + e2 = expr_copy(e2);
1.215 + old_count = trans_count;
1.216 + expr_eliminate_eq(&e1, &e2);
1.217 + res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
1.218 + e1->left.sym == e2->left.sym);
1.219 + expr_free(e1);
1.220 + expr_free(e2);
1.221 + trans_count = old_count;
1.222 + return res;
1.223 + case E_CHOICE:
1.224 + case E_RANGE:
1.225 + case E_NONE:
1.226 + /* panic */;
1.227 + }
1.228 +
1.229 + if (DEBUG_EXPR) {
1.230 + expr_fprint(e1, stdout);
1.231 + printf(" = ");
1.232 + expr_fprint(e2, stdout);
1.233 + printf(" ?\n");
1.234 + }
1.235 +
1.236 + return 0;
1.237 +}
1.238 +
1.239 +struct expr *expr_eliminate_yn(struct expr *e)
1.240 +{
1.241 + struct expr *tmp;
1.242 +
1.243 + if (e) switch (e->type) {
1.244 + case E_AND:
1.245 + e->left.expr = expr_eliminate_yn(e->left.expr);
1.246 + e->right.expr = expr_eliminate_yn(e->right.expr);
1.247 + if (e->left.expr->type == E_SYMBOL) {
1.248 + if (e->left.expr->left.sym == &symbol_no) {
1.249 + expr_free(e->left.expr);
1.250 + expr_free(e->right.expr);
1.251 + e->type = E_SYMBOL;
1.252 + e->left.sym = &symbol_no;
1.253 + e->right.expr = NULL;
1.254 + return e;
1.255 + } else if (e->left.expr->left.sym == &symbol_yes) {
1.256 + free(e->left.expr);
1.257 + tmp = e->right.expr;
1.258 + *e = *(e->right.expr);
1.259 + free(tmp);
1.260 + return e;
1.261 + }
1.262 + }
1.263 + if (e->right.expr->type == E_SYMBOL) {
1.264 + if (e->right.expr->left.sym == &symbol_no) {
1.265 + expr_free(e->left.expr);
1.266 + expr_free(e->right.expr);
1.267 + e->type = E_SYMBOL;
1.268 + e->left.sym = &symbol_no;
1.269 + e->right.expr = NULL;
1.270 + return e;
1.271 + } else if (e->right.expr->left.sym == &symbol_yes) {
1.272 + free(e->right.expr);
1.273 + tmp = e->left.expr;
1.274 + *e = *(e->left.expr);
1.275 + free(tmp);
1.276 + return e;
1.277 + }
1.278 + }
1.279 + break;
1.280 + case E_OR:
1.281 + e->left.expr = expr_eliminate_yn(e->left.expr);
1.282 + e->right.expr = expr_eliminate_yn(e->right.expr);
1.283 + if (e->left.expr->type == E_SYMBOL) {
1.284 + if (e->left.expr->left.sym == &symbol_no) {
1.285 + free(e->left.expr);
1.286 + tmp = e->right.expr;
1.287 + *e = *(e->right.expr);
1.288 + free(tmp);
1.289 + return e;
1.290 + } else if (e->left.expr->left.sym == &symbol_yes) {
1.291 + expr_free(e->left.expr);
1.292 + expr_free(e->right.expr);
1.293 + e->type = E_SYMBOL;
1.294 + e->left.sym = &symbol_yes;
1.295 + e->right.expr = NULL;
1.296 + return e;
1.297 + }
1.298 + }
1.299 + if (e->right.expr->type == E_SYMBOL) {
1.300 + if (e->right.expr->left.sym == &symbol_no) {
1.301 + free(e->right.expr);
1.302 + tmp = e->left.expr;
1.303 + *e = *(e->left.expr);
1.304 + free(tmp);
1.305 + return e;
1.306 + } else if (e->right.expr->left.sym == &symbol_yes) {
1.307 + expr_free(e->left.expr);
1.308 + expr_free(e->right.expr);
1.309 + e->type = E_SYMBOL;
1.310 + e->left.sym = &symbol_yes;
1.311 + e->right.expr = NULL;
1.312 + return e;
1.313 + }
1.314 + }
1.315 + break;
1.316 + default:
1.317 + ;
1.318 + }
1.319 + return e;
1.320 +}
1.321 +
1.322 +/*
1.323 + * bool FOO!=n => FOO
1.324 + */
1.325 +struct expr *expr_trans_bool(struct expr *e)
1.326 +{
1.327 + if (!e)
1.328 + return NULL;
1.329 + switch (e->type) {
1.330 + case E_AND:
1.331 + case E_OR:
1.332 + case E_NOT:
1.333 + e->left.expr = expr_trans_bool(e->left.expr);
1.334 + e->right.expr = expr_trans_bool(e->right.expr);
1.335 + break;
1.336 + case E_UNEQUAL:
1.337 + // FOO!=n -> FOO
1.338 + if (e->left.sym->type == S_TRISTATE) {
1.339 + if (e->right.sym == &symbol_no) {
1.340 + e->type = E_SYMBOL;
1.341 + e->right.sym = NULL;
1.342 + }
1.343 + }
1.344 + break;
1.345 + default:
1.346 + ;
1.347 + }
1.348 + return e;
1.349 +}
1.350 +
1.351 +/*
1.352 + * e1 || e2 -> ?
1.353 + */
1.354 +struct expr *expr_join_or(struct expr *e1, struct expr *e2)
1.355 +{
1.356 + struct expr *tmp;
1.357 + struct symbol *sym1, *sym2;
1.358 +
1.359 + if (expr_eq(e1, e2))
1.360 + return expr_copy(e1);
1.361 + if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
1.362 + return NULL;
1.363 + if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
1.364 + return NULL;
1.365 + if (e1->type == E_NOT) {
1.366 + tmp = e1->left.expr;
1.367 + if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
1.368 + return NULL;
1.369 + sym1 = tmp->left.sym;
1.370 + } else
1.371 + sym1 = e1->left.sym;
1.372 + if (e2->type == E_NOT) {
1.373 + if (e2->left.expr->type != E_SYMBOL)
1.374 + return NULL;
1.375 + sym2 = e2->left.expr->left.sym;
1.376 + } else
1.377 + sym2 = e2->left.sym;
1.378 + if (sym1 != sym2)
1.379 + return NULL;
1.380 + if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
1.381 + return NULL;
1.382 + if (sym1->type == S_TRISTATE) {
1.383 + if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
1.384 + ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
1.385 + (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
1.386 + // (a='y') || (a='m') -> (a!='n')
1.387 + return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
1.388 + }
1.389 + if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
1.390 + ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
1.391 + (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
1.392 + // (a='y') || (a='n') -> (a!='m')
1.393 + return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
1.394 + }
1.395 + if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
1.396 + ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
1.397 + (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
1.398 + // (a='m') || (a='n') -> (a!='y')
1.399 + return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
1.400 + }
1.401 + }
1.402 + if (sym1->type == S_BOOLEAN && sym1 == sym2) {
1.403 + if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
1.404 + (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
1.405 + return expr_alloc_symbol(&symbol_yes);
1.406 + }
1.407 +
1.408 + if (DEBUG_EXPR) {
1.409 + printf("optimize (");
1.410 + expr_fprint(e1, stdout);
1.411 + printf(") || (");
1.412 + expr_fprint(e2, stdout);
1.413 + printf(")?\n");
1.414 + }
1.415 + return NULL;
1.416 +}
1.417 +
1.418 +struct expr *expr_join_and(struct expr *e1, struct expr *e2)
1.419 +{
1.420 + struct expr *tmp;
1.421 + struct symbol *sym1, *sym2;
1.422 +
1.423 + if (expr_eq(e1, e2))
1.424 + return expr_copy(e1);
1.425 + if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
1.426 + return NULL;
1.427 + if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
1.428 + return NULL;
1.429 + if (e1->type == E_NOT) {
1.430 + tmp = e1->left.expr;
1.431 + if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
1.432 + return NULL;
1.433 + sym1 = tmp->left.sym;
1.434 + } else
1.435 + sym1 = e1->left.sym;
1.436 + if (e2->type == E_NOT) {
1.437 + if (e2->left.expr->type != E_SYMBOL)
1.438 + return NULL;
1.439 + sym2 = e2->left.expr->left.sym;
1.440 + } else
1.441 + sym2 = e2->left.sym;
1.442 + if (sym1 != sym2)
1.443 + return NULL;
1.444 + if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
1.445 + return NULL;
1.446 +
1.447 + if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
1.448 + (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
1.449 + // (a) && (a='y') -> (a='y')
1.450 + return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
1.451 +
1.452 + if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
1.453 + (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
1.454 + // (a) && (a!='n') -> (a)
1.455 + return expr_alloc_symbol(sym1);
1.456 +
1.457 + if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
1.458 + (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
1.459 + // (a) && (a!='m') -> (a='y')
1.460 + return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
1.461 +
1.462 + if (sym1->type == S_TRISTATE) {
1.463 + if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
1.464 + // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
1.465 + sym2 = e1->right.sym;
1.466 + if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
1.467 + return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
1.468 + : expr_alloc_symbol(&symbol_no);
1.469 + }
1.470 + if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
1.471 + // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
1.472 + sym2 = e2->right.sym;
1.473 + if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
1.474 + return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
1.475 + : expr_alloc_symbol(&symbol_no);
1.476 + }
1.477 + if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
1.478 + ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
1.479 + (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
1.480 + // (a!='y') && (a!='n') -> (a='m')
1.481 + return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
1.482 +
1.483 + if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
1.484 + ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
1.485 + (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
1.486 + // (a!='y') && (a!='m') -> (a='n')
1.487 + return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
1.488 +
1.489 + if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
1.490 + ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
1.491 + (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
1.492 + // (a!='m') && (a!='n') -> (a='m')
1.493 + return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
1.494 +
1.495 + if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
1.496 + (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
1.497 + (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
1.498 + (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
1.499 + return NULL;
1.500 + }
1.501 +
1.502 + if (DEBUG_EXPR) {
1.503 + printf("optimize (");
1.504 + expr_fprint(e1, stdout);
1.505 + printf(") && (");
1.506 + expr_fprint(e2, stdout);
1.507 + printf(")?\n");
1.508 + }
1.509 + return NULL;
1.510 +}
1.511 +
1.512 +static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
1.513 +{
1.514 +#define e1 (*ep1)
1.515 +#define e2 (*ep2)
1.516 + struct expr *tmp;
1.517 +
1.518 + if (e1->type == type) {
1.519 + expr_eliminate_dups1(type, &e1->left.expr, &e2);
1.520 + expr_eliminate_dups1(type, &e1->right.expr, &e2);
1.521 + return;
1.522 + }
1.523 + if (e2->type == type) {
1.524 + expr_eliminate_dups1(type, &e1, &e2->left.expr);
1.525 + expr_eliminate_dups1(type, &e1, &e2->right.expr);
1.526 + return;
1.527 + }
1.528 + if (e1 == e2)
1.529 + return;
1.530 +
1.531 + switch (e1->type) {
1.532 + case E_OR: case E_AND:
1.533 + expr_eliminate_dups1(e1->type, &e1, &e1);
1.534 + default:
1.535 + ;
1.536 + }
1.537 +
1.538 + switch (type) {
1.539 + case E_OR:
1.540 + tmp = expr_join_or(e1, e2);
1.541 + if (tmp) {
1.542 + expr_free(e1); expr_free(e2);
1.543 + e1 = expr_alloc_symbol(&symbol_no);
1.544 + e2 = tmp;
1.545 + trans_count++;
1.546 + }
1.547 + break;
1.548 + case E_AND:
1.549 + tmp = expr_join_and(e1, e2);
1.550 + if (tmp) {
1.551 + expr_free(e1); expr_free(e2);
1.552 + e1 = expr_alloc_symbol(&symbol_yes);
1.553 + e2 = tmp;
1.554 + trans_count++;
1.555 + }
1.556 + break;
1.557 + default:
1.558 + ;
1.559 + }
1.560 +#undef e1
1.561 +#undef e2
1.562 +}
1.563 +
1.564 +static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
1.565 +{
1.566 +#define e1 (*ep1)
1.567 +#define e2 (*ep2)
1.568 + struct expr *tmp, *tmp1, *tmp2;
1.569 +
1.570 + if (e1->type == type) {
1.571 + expr_eliminate_dups2(type, &e1->left.expr, &e2);
1.572 + expr_eliminate_dups2(type, &e1->right.expr, &e2);
1.573 + return;
1.574 + }
1.575 + if (e2->type == type) {
1.576 + expr_eliminate_dups2(type, &e1, &e2->left.expr);
1.577 + expr_eliminate_dups2(type, &e1, &e2->right.expr);
1.578 + }
1.579 + if (e1 == e2)
1.580 + return;
1.581 +
1.582 + switch (e1->type) {
1.583 + case E_OR:
1.584 + expr_eliminate_dups2(e1->type, &e1, &e1);
1.585 + // (FOO || BAR) && (!FOO && !BAR) -> n
1.586 + tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
1.587 + tmp2 = expr_copy(e2);
1.588 + tmp = expr_extract_eq_and(&tmp1, &tmp2);
1.589 + if (expr_is_yes(tmp1)) {
1.590 + expr_free(e1);
1.591 + e1 = expr_alloc_symbol(&symbol_no);
1.592 + trans_count++;
1.593 + }
1.594 + expr_free(tmp2);
1.595 + expr_free(tmp1);
1.596 + expr_free(tmp);
1.597 + break;
1.598 + case E_AND:
1.599 + expr_eliminate_dups2(e1->type, &e1, &e1);
1.600 + // (FOO && BAR) || (!FOO || !BAR) -> y
1.601 + tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
1.602 + tmp2 = expr_copy(e2);
1.603 + tmp = expr_extract_eq_or(&tmp1, &tmp2);
1.604 + if (expr_is_no(tmp1)) {
1.605 + expr_free(e1);
1.606 + e1 = expr_alloc_symbol(&symbol_yes);
1.607 + trans_count++;
1.608 + }
1.609 + expr_free(tmp2);
1.610 + expr_free(tmp1);
1.611 + expr_free(tmp);
1.612 + break;
1.613 + default:
1.614 + ;
1.615 + }
1.616 +#undef e1
1.617 +#undef e2
1.618 +}
1.619 +
1.620 +struct expr *expr_eliminate_dups(struct expr *e)
1.621 +{
1.622 + int oldcount;
1.623 + if (!e)
1.624 + return e;
1.625 +
1.626 + oldcount = trans_count;
1.627 + while (1) {
1.628 + trans_count = 0;
1.629 + switch (e->type) {
1.630 + case E_OR: case E_AND:
1.631 + expr_eliminate_dups1(e->type, &e, &e);
1.632 + expr_eliminate_dups2(e->type, &e, &e);
1.633 + default:
1.634 + ;
1.635 + }
1.636 + if (!trans_count)
1.637 + break;
1.638 + e = expr_eliminate_yn(e);
1.639 + }
1.640 + trans_count = oldcount;
1.641 + return e;
1.642 +}
1.643 +
1.644 +struct expr *expr_transform(struct expr *e)
1.645 +{
1.646 + struct expr *tmp;
1.647 +
1.648 + if (!e)
1.649 + return NULL;
1.650 + switch (e->type) {
1.651 + case E_EQUAL:
1.652 + case E_UNEQUAL:
1.653 + case E_SYMBOL:
1.654 + case E_CHOICE:
1.655 + break;
1.656 + default:
1.657 + e->left.expr = expr_transform(e->left.expr);
1.658 + e->right.expr = expr_transform(e->right.expr);
1.659 + }
1.660 +
1.661 + switch (e->type) {
1.662 + case E_EQUAL:
1.663 + if (e->left.sym->type != S_BOOLEAN)
1.664 + break;
1.665 + if (e->right.sym == &symbol_no) {
1.666 + e->type = E_NOT;
1.667 + e->left.expr = expr_alloc_symbol(e->left.sym);
1.668 + e->right.sym = NULL;
1.669 + break;
1.670 + }
1.671 + if (e->right.sym == &symbol_mod) {
1.672 + printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
1.673 + e->type = E_SYMBOL;
1.674 + e->left.sym = &symbol_no;
1.675 + e->right.sym = NULL;
1.676 + break;
1.677 + }
1.678 + if (e->right.sym == &symbol_yes) {
1.679 + e->type = E_SYMBOL;
1.680 + e->right.sym = NULL;
1.681 + break;
1.682 + }
1.683 + break;
1.684 + case E_UNEQUAL:
1.685 + if (e->left.sym->type != S_BOOLEAN)
1.686 + break;
1.687 + if (e->right.sym == &symbol_no) {
1.688 + e->type = E_SYMBOL;
1.689 + e->right.sym = NULL;
1.690 + break;
1.691 + }
1.692 + if (e->right.sym == &symbol_mod) {
1.693 + printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
1.694 + e->type = E_SYMBOL;
1.695 + e->left.sym = &symbol_yes;
1.696 + e->right.sym = NULL;
1.697 + break;
1.698 + }
1.699 + if (e->right.sym == &symbol_yes) {
1.700 + e->type = E_NOT;
1.701 + e->left.expr = expr_alloc_symbol(e->left.sym);
1.702 + e->right.sym = NULL;
1.703 + break;
1.704 + }
1.705 + break;
1.706 + case E_NOT:
1.707 + switch (e->left.expr->type) {
1.708 + case E_NOT:
1.709 + // !!a -> a
1.710 + tmp = e->left.expr->left.expr;
1.711 + free(e->left.expr);
1.712 + free(e);
1.713 + e = tmp;
1.714 + e = expr_transform(e);
1.715 + break;
1.716 + case E_EQUAL:
1.717 + case E_UNEQUAL:
1.718 + // !a='x' -> a!='x'
1.719 + tmp = e->left.expr;
1.720 + free(e);
1.721 + e = tmp;
1.722 + e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
1.723 + break;
1.724 + case E_OR:
1.725 + // !(a || b) -> !a && !b
1.726 + tmp = e->left.expr;
1.727 + e->type = E_AND;
1.728 + e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
1.729 + tmp->type = E_NOT;
1.730 + tmp->right.expr = NULL;
1.731 + e = expr_transform(e);
1.732 + break;
1.733 + case E_AND:
1.734 + // !(a && b) -> !a || !b
1.735 + tmp = e->left.expr;
1.736 + e->type = E_OR;
1.737 + e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
1.738 + tmp->type = E_NOT;
1.739 + tmp->right.expr = NULL;
1.740 + e = expr_transform(e);
1.741 + break;
1.742 + case E_SYMBOL:
1.743 + if (e->left.expr->left.sym == &symbol_yes) {
1.744 + // !'y' -> 'n'
1.745 + tmp = e->left.expr;
1.746 + free(e);
1.747 + e = tmp;
1.748 + e->type = E_SYMBOL;
1.749 + e->left.sym = &symbol_no;
1.750 + break;
1.751 + }
1.752 + if (e->left.expr->left.sym == &symbol_mod) {
1.753 + // !'m' -> 'm'
1.754 + tmp = e->left.expr;
1.755 + free(e);
1.756 + e = tmp;
1.757 + e->type = E_SYMBOL;
1.758 + e->left.sym = &symbol_mod;
1.759 + break;
1.760 + }
1.761 + if (e->left.expr->left.sym == &symbol_no) {
1.762 + // !'n' -> 'y'
1.763 + tmp = e->left.expr;
1.764 + free(e);
1.765 + e = tmp;
1.766 + e->type = E_SYMBOL;
1.767 + e->left.sym = &symbol_yes;
1.768 + break;
1.769 + }
1.770 + break;
1.771 + default:
1.772 + ;
1.773 + }
1.774 + break;
1.775 + default:
1.776 + ;
1.777 + }
1.778 + return e;
1.779 +}
1.780 +
1.781 +int expr_contains_symbol(struct expr *dep, struct symbol *sym)
1.782 +{
1.783 + if (!dep)
1.784 + return 0;
1.785 +
1.786 + switch (dep->type) {
1.787 + case E_AND:
1.788 + case E_OR:
1.789 + return expr_contains_symbol(dep->left.expr, sym) ||
1.790 + expr_contains_symbol(dep->right.expr, sym);
1.791 + case E_SYMBOL:
1.792 + return dep->left.sym == sym;
1.793 + case E_EQUAL:
1.794 + case E_UNEQUAL:
1.795 + return dep->left.sym == sym ||
1.796 + dep->right.sym == sym;
1.797 + case E_NOT:
1.798 + return expr_contains_symbol(dep->left.expr, sym);
1.799 + default:
1.800 + ;
1.801 + }
1.802 + return 0;
1.803 +}
1.804 +
1.805 +bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
1.806 +{
1.807 + if (!dep)
1.808 + return false;
1.809 +
1.810 + switch (dep->type) {
1.811 + case E_AND:
1.812 + return expr_depends_symbol(dep->left.expr, sym) ||
1.813 + expr_depends_symbol(dep->right.expr, sym);
1.814 + case E_SYMBOL:
1.815 + return dep->left.sym == sym;
1.816 + case E_EQUAL:
1.817 + if (dep->left.sym == sym) {
1.818 + if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
1.819 + return true;
1.820 + }
1.821 + break;
1.822 + case E_UNEQUAL:
1.823 + if (dep->left.sym == sym) {
1.824 + if (dep->right.sym == &symbol_no)
1.825 + return true;
1.826 + }
1.827 + break;
1.828 + default:
1.829 + ;
1.830 + }
1.831 + return false;
1.832 +}
1.833 +
1.834 +struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
1.835 +{
1.836 + struct expr *tmp = NULL;
1.837 + expr_extract_eq(E_AND, &tmp, ep1, ep2);
1.838 + if (tmp) {
1.839 + *ep1 = expr_eliminate_yn(*ep1);
1.840 + *ep2 = expr_eliminate_yn(*ep2);
1.841 + }
1.842 + return tmp;
1.843 +}
1.844 +
1.845 +struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
1.846 +{
1.847 + struct expr *tmp = NULL;
1.848 + expr_extract_eq(E_OR, &tmp, ep1, ep2);
1.849 + if (tmp) {
1.850 + *ep1 = expr_eliminate_yn(*ep1);
1.851 + *ep2 = expr_eliminate_yn(*ep2);
1.852 + }
1.853 + return tmp;
1.854 +}
1.855 +
1.856 +void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
1.857 +{
1.858 +#define e1 (*ep1)
1.859 +#define e2 (*ep2)
1.860 + if (e1->type == type) {
1.861 + expr_extract_eq(type, ep, &e1->left.expr, &e2);
1.862 + expr_extract_eq(type, ep, &e1->right.expr, &e2);
1.863 + return;
1.864 + }
1.865 + if (e2->type == type) {
1.866 + expr_extract_eq(type, ep, ep1, &e2->left.expr);
1.867 + expr_extract_eq(type, ep, ep1, &e2->right.expr);
1.868 + return;
1.869 + }
1.870 + if (expr_eq(e1, e2)) {
1.871 + *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
1.872 + expr_free(e2);
1.873 + if (type == E_AND) {
1.874 + e1 = expr_alloc_symbol(&symbol_yes);
1.875 + e2 = expr_alloc_symbol(&symbol_yes);
1.876 + } else if (type == E_OR) {
1.877 + e1 = expr_alloc_symbol(&symbol_no);
1.878 + e2 = expr_alloc_symbol(&symbol_no);
1.879 + }
1.880 + }
1.881 +#undef e1
1.882 +#undef e2
1.883 +}
1.884 +
1.885 +struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
1.886 +{
1.887 + struct expr *e1, *e2;
1.888 +
1.889 + if (!e) {
1.890 + e = expr_alloc_symbol(sym);
1.891 + if (type == E_UNEQUAL)
1.892 + e = expr_alloc_one(E_NOT, e);
1.893 + return e;
1.894 + }
1.895 + switch (e->type) {
1.896 + case E_AND:
1.897 + e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
1.898 + e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
1.899 + if (sym == &symbol_yes)
1.900 + e = expr_alloc_two(E_AND, e1, e2);
1.901 + if (sym == &symbol_no)
1.902 + e = expr_alloc_two(E_OR, e1, e2);
1.903 + if (type == E_UNEQUAL)
1.904 + e = expr_alloc_one(E_NOT, e);
1.905 + return e;
1.906 + case E_OR:
1.907 + e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
1.908 + e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
1.909 + if (sym == &symbol_yes)
1.910 + e = expr_alloc_two(E_OR, e1, e2);
1.911 + if (sym == &symbol_no)
1.912 + e = expr_alloc_two(E_AND, e1, e2);
1.913 + if (type == E_UNEQUAL)
1.914 + e = expr_alloc_one(E_NOT, e);
1.915 + return e;
1.916 + case E_NOT:
1.917 + return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
1.918 + case E_UNEQUAL:
1.919 + case E_EQUAL:
1.920 + if (type == E_EQUAL) {
1.921 + if (sym == &symbol_yes)
1.922 + return expr_copy(e);
1.923 + if (sym == &symbol_mod)
1.924 + return expr_alloc_symbol(&symbol_no);
1.925 + if (sym == &symbol_no)
1.926 + return expr_alloc_one(E_NOT, expr_copy(e));
1.927 + } else {
1.928 + if (sym == &symbol_yes)
1.929 + return expr_alloc_one(E_NOT, expr_copy(e));
1.930 + if (sym == &symbol_mod)
1.931 + return expr_alloc_symbol(&symbol_yes);
1.932 + if (sym == &symbol_no)
1.933 + return expr_copy(e);
1.934 + }
1.935 + break;
1.936 + case E_SYMBOL:
1.937 + return expr_alloc_comp(type, e->left.sym, sym);
1.938 + case E_CHOICE:
1.939 + case E_RANGE:
1.940 + case E_NONE:
1.941 + /* panic */;
1.942 + }
1.943 + return NULL;
1.944 +}
1.945 +
1.946 +tristate expr_calc_value(struct expr *e)
1.947 +{
1.948 + tristate val1, val2;
1.949 + const char *str1, *str2;
1.950 +
1.951 + if (!e)
1.952 + return yes;
1.953 +
1.954 + switch (e->type) {
1.955 + case E_SYMBOL:
1.956 + sym_calc_value(e->left.sym);
1.957 + return e->left.sym->curr.tri;
1.958 + case E_AND:
1.959 + val1 = expr_calc_value(e->left.expr);
1.960 + val2 = expr_calc_value(e->right.expr);
1.961 + return E_AND(val1, val2);
1.962 + case E_OR:
1.963 + val1 = expr_calc_value(e->left.expr);
1.964 + val2 = expr_calc_value(e->right.expr);
1.965 + return E_OR(val1, val2);
1.966 + case E_NOT:
1.967 + val1 = expr_calc_value(e->left.expr);
1.968 + return E_NOT(val1);
1.969 + case E_EQUAL:
1.970 + sym_calc_value(e->left.sym);
1.971 + sym_calc_value(e->right.sym);
1.972 + str1 = sym_get_string_value(e->left.sym);
1.973 + str2 = sym_get_string_value(e->right.sym);
1.974 + return !strcmp(str1, str2) ? yes : no;
1.975 + case E_UNEQUAL:
1.976 + sym_calc_value(e->left.sym);
1.977 + sym_calc_value(e->right.sym);
1.978 + str1 = sym_get_string_value(e->left.sym);
1.979 + str2 = sym_get_string_value(e->right.sym);
1.980 + return !strcmp(str1, str2) ? no : yes;
1.981 + default:
1.982 + printf("expr_calc_value: %d?\n", e->type);
1.983 + return no;
1.984 + }
1.985 +}
1.986 +
1.987 +int expr_compare_type(enum expr_type t1, enum expr_type t2)
1.988 +{
1.989 +#if 0
1.990 + return 1;
1.991 +#else
1.992 + if (t1 == t2)
1.993 + return 0;
1.994 + switch (t1) {
1.995 + case E_EQUAL:
1.996 + case E_UNEQUAL:
1.997 + if (t2 == E_NOT)
1.998 + return 1;
1.999 + case E_NOT:
1.1000 + if (t2 == E_AND)
1.1001 + return 1;
1.1002 + case E_AND:
1.1003 + if (t2 == E_OR)
1.1004 + return 1;
1.1005 + case E_OR:
1.1006 + if (t2 == E_CHOICE)
1.1007 + return 1;
1.1008 + case E_CHOICE:
1.1009 + if (t2 == 0)
1.1010 + return 1;
1.1011 + default:
1.1012 + return -1;
1.1013 + }
1.1014 + printf("[%dgt%d?]", t1, t2);
1.1015 + return 0;
1.1016 +#endif
1.1017 +}
1.1018 +
1.1019 +void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1.1020 +{
1.1021 + if (!e) {
1.1022 + fn(data, NULL, "y");
1.1023 + return;
1.1024 + }
1.1025 +
1.1026 + if (expr_compare_type(prevtoken, e->type) > 0)
1.1027 + fn(data, NULL, "(");
1.1028 + switch (e->type) {
1.1029 + case E_SYMBOL:
1.1030 + if (e->left.sym->name)
1.1031 + fn(data, e->left.sym, e->left.sym->name);
1.1032 + else
1.1033 + fn(data, NULL, "<choice>");
1.1034 + break;
1.1035 + case E_NOT:
1.1036 + fn(data, NULL, "!");
1.1037 + expr_print(e->left.expr, fn, data, E_NOT);
1.1038 + break;
1.1039 + case E_EQUAL:
1.1040 + fn(data, e->left.sym, e->left.sym->name);
1.1041 + fn(data, NULL, "=");
1.1042 + fn(data, e->right.sym, e->right.sym->name);
1.1043 + break;
1.1044 + case E_UNEQUAL:
1.1045 + fn(data, e->left.sym, e->left.sym->name);
1.1046 + fn(data, NULL, "!=");
1.1047 + fn(data, e->right.sym, e->right.sym->name);
1.1048 + break;
1.1049 + case E_OR:
1.1050 + expr_print(e->left.expr, fn, data, E_OR);
1.1051 + fn(data, NULL, " || ");
1.1052 + expr_print(e->right.expr, fn, data, E_OR);
1.1053 + break;
1.1054 + case E_AND:
1.1055 + expr_print(e->left.expr, fn, data, E_AND);
1.1056 + fn(data, NULL, " && ");
1.1057 + expr_print(e->right.expr, fn, data, E_AND);
1.1058 + break;
1.1059 + case E_CHOICE:
1.1060 + fn(data, e->right.sym, e->right.sym->name);
1.1061 + if (e->left.expr) {
1.1062 + fn(data, NULL, " ^ ");
1.1063 + expr_print(e->left.expr, fn, data, E_CHOICE);
1.1064 + }
1.1065 + break;
1.1066 + case E_RANGE:
1.1067 + fn(data, NULL, "[");
1.1068 + fn(data, e->left.sym, e->left.sym->name);
1.1069 + fn(data, NULL, " ");
1.1070 + fn(data, e->right.sym, e->right.sym->name);
1.1071 + fn(data, NULL, "]");
1.1072 + break;
1.1073 + default:
1.1074 + {
1.1075 + char buf[32];
1.1076 + sprintf(buf, "<unknown type %d>", e->type);
1.1077 + fn(data, NULL, buf);
1.1078 + break;
1.1079 + }
1.1080 + }
1.1081 + if (expr_compare_type(prevtoken, e->type) > 0)
1.1082 + fn(data, NULL, ")");
1.1083 +}
1.1084 +
1.1085 +static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1.1086 +{
1.1087 + fwrite(str, strlen(str), 1, data);
1.1088 +}
1.1089 +
1.1090 +void expr_fprint(struct expr *e, FILE *out)
1.1091 +{
1.1092 + expr_print(e, expr_print_file_helper, out, E_NONE);
1.1093 +}
1.1094 +
1.1095 +static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1.1096 +{
1.1097 + str_append((struct gstr*)data, str);
1.1098 +}
1.1099 +
1.1100 +void expr_gstr_print(struct expr *e, struct gstr *gs)
1.1101 +{
1.1102 + expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1.1103 +}