Martin Roth | be08c1d | 2024-02-16 09:12:33 -0700 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0-only |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 2 | /* |
| 3 | * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 4 | */ |
| 5 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 6 | #include <ctype.h> |
| 7 | #include <errno.h> |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 8 | #include <stdio.h> |
| 9 | #include <stdlib.h> |
| 10 | #include <string.h> |
| 11 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 12 | #include "lkc.h" |
| 13 | |
| 14 | #define DEBUG_EXPR 0 |
| 15 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 16 | static struct expr *expr_eliminate_yn(struct expr *e); |
| 17 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 18 | struct expr *expr_alloc_symbol(struct symbol *sym) |
| 19 | { |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 20 | struct expr *e = xcalloc(1, sizeof(*e)); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 21 | e->type = E_SYMBOL; |
| 22 | e->left.sym = sym; |
| 23 | return e; |
| 24 | } |
| 25 | |
| 26 | struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) |
| 27 | { |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 28 | struct expr *e = xcalloc(1, sizeof(*e)); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 29 | e->type = type; |
| 30 | e->left.expr = ce; |
| 31 | return e; |
| 32 | } |
| 33 | |
| 34 | struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2) |
| 35 | { |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 36 | struct expr *e = xcalloc(1, sizeof(*e)); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 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 | { |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 45 | struct expr *e = xcalloc(1, sizeof(*e)); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 46 | e->type = type; |
| 47 | e->left.sym = s1; |
| 48 | e->right.sym = s2; |
| 49 | return e; |
| 50 | } |
| 51 | |
| 52 | struct expr *expr_alloc_and(struct expr *e1, struct expr *e2) |
| 53 | { |
| 54 | if (!e1) |
| 55 | return e2; |
| 56 | return e2 ? expr_alloc_two(E_AND, e1, e2) : e1; |
| 57 | } |
| 58 | |
| 59 | struct expr *expr_alloc_or(struct expr *e1, struct expr *e2) |
| 60 | { |
| 61 | if (!e1) |
| 62 | return e2; |
| 63 | return e2 ? expr_alloc_two(E_OR, e1, e2) : e1; |
| 64 | } |
| 65 | |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 66 | struct expr *expr_copy(const struct expr *org) |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 67 | { |
| 68 | struct expr *e; |
| 69 | |
| 70 | if (!org) |
| 71 | return NULL; |
| 72 | |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 73 | e = xmalloc(sizeof(*org)); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 74 | memcpy(e, org, sizeof(*org)); |
| 75 | switch (org->type) { |
| 76 | case E_SYMBOL: |
| 77 | e->left = org->left; |
| 78 | break; |
| 79 | case E_NOT: |
| 80 | e->left.expr = expr_copy(org->left.expr); |
| 81 | break; |
| 82 | case E_EQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 83 | case E_GEQ: |
| 84 | case E_GTH: |
| 85 | case E_LEQ: |
| 86 | case E_LTH: |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 87 | case E_UNEQUAL: |
| 88 | e->left.sym = org->left.sym; |
| 89 | e->right.sym = org->right.sym; |
| 90 | break; |
| 91 | case E_AND: |
| 92 | case E_OR: |
| 93 | case E_LIST: |
| 94 | e->left.expr = expr_copy(org->left.expr); |
| 95 | e->right.expr = expr_copy(org->right.expr); |
| 96 | break; |
| 97 | default: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 98 | fprintf(stderr, "can't copy type %d\n", e->type); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 99 | free(e); |
| 100 | e = NULL; |
| 101 | break; |
| 102 | } |
| 103 | |
| 104 | return e; |
| 105 | } |
| 106 | |
| 107 | void expr_free(struct expr *e) |
| 108 | { |
| 109 | if (!e) |
| 110 | return; |
| 111 | |
| 112 | switch (e->type) { |
| 113 | case E_SYMBOL: |
| 114 | break; |
| 115 | case E_NOT: |
| 116 | expr_free(e->left.expr); |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 117 | break; |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 118 | case E_EQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 119 | case E_GEQ: |
| 120 | case E_GTH: |
| 121 | case E_LEQ: |
| 122 | case E_LTH: |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 123 | case E_UNEQUAL: |
| 124 | break; |
| 125 | case E_OR: |
| 126 | case E_AND: |
| 127 | expr_free(e->left.expr); |
| 128 | expr_free(e->right.expr); |
| 129 | break; |
| 130 | default: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 131 | fprintf(stderr, "how to free type %d?\n", e->type); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 132 | break; |
| 133 | } |
| 134 | free(e); |
| 135 | } |
| 136 | |
| 137 | static int trans_count; |
| 138 | |
| 139 | #define e1 (*ep1) |
| 140 | #define e2 (*ep2) |
| 141 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 142 | /* |
| 143 | * expr_eliminate_eq() helper. |
| 144 | * |
| 145 | * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does |
| 146 | * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared |
| 147 | * against all other leaves. Two equal leaves are both replaced with either 'y' |
| 148 | * or 'n' as appropriate for 'type', to be eliminated later. |
| 149 | */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 150 | static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) |
| 151 | { |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 152 | /* Recurse down to leaves */ |
| 153 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 154 | if (e1->type == type) { |
| 155 | __expr_eliminate_eq(type, &e1->left.expr, &e2); |
| 156 | __expr_eliminate_eq(type, &e1->right.expr, &e2); |
| 157 | return; |
| 158 | } |
| 159 | if (e2->type == type) { |
| 160 | __expr_eliminate_eq(type, &e1, &e2->left.expr); |
| 161 | __expr_eliminate_eq(type, &e1, &e2->right.expr); |
| 162 | return; |
| 163 | } |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 164 | |
| 165 | /* e1 and e2 are leaves. Compare them. */ |
| 166 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 167 | if (e1->type == E_SYMBOL && e2->type == E_SYMBOL && |
| 168 | e1->left.sym == e2->left.sym && |
| 169 | (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) |
| 170 | return; |
| 171 | if (!expr_eq(e1, e2)) |
| 172 | return; |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 173 | |
| 174 | /* e1 and e2 are equal leaves. Prepare them for elimination. */ |
| 175 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 176 | trans_count++; |
| 177 | expr_free(e1); expr_free(e2); |
| 178 | switch (type) { |
| 179 | case E_OR: |
| 180 | e1 = expr_alloc_symbol(&symbol_no); |
| 181 | e2 = expr_alloc_symbol(&symbol_no); |
| 182 | break; |
| 183 | case E_AND: |
| 184 | e1 = expr_alloc_symbol(&symbol_yes); |
| 185 | e2 = expr_alloc_symbol(&symbol_yes); |
| 186 | break; |
| 187 | default: |
| 188 | ; |
| 189 | } |
| 190 | } |
| 191 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 192 | /* |
| 193 | * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both. |
| 194 | * Example reductions: |
| 195 | * |
| 196 | * ep1: A && B -> ep1: y |
| 197 | * ep2: A && B && C -> ep2: C |
| 198 | * |
| 199 | * ep1: A || B -> ep1: n |
| 200 | * ep2: A || B || C -> ep2: C |
| 201 | * |
| 202 | * ep1: A && (B && FOO) -> ep1: FOO |
| 203 | * ep2: (BAR && B) && A -> ep2: BAR |
| 204 | * |
| 205 | * ep1: A && (B || C) -> ep1: y |
| 206 | * ep2: (C || B) && A -> ep2: y |
| 207 | * |
| 208 | * Comparisons are done between all operands at the same "level" of && or ||. |
| 209 | * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the |
| 210 | * following operands will be compared: |
| 211 | * |
| 212 | * - 'e1', 'e2 || e3', and 'e4 || e5', against each other |
| 213 | * - e2 against e3 |
| 214 | * - e4 against e5 |
| 215 | * |
| 216 | * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and |
| 217 | * '(e1 && e2) && e3' are both a single level. |
| 218 | * |
| 219 | * See __expr_eliminate_eq() as well. |
| 220 | */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 221 | void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) |
| 222 | { |
| 223 | if (!e1 || !e2) |
| 224 | return; |
| 225 | switch (e1->type) { |
| 226 | case E_OR: |
| 227 | case E_AND: |
| 228 | __expr_eliminate_eq(e1->type, ep1, ep2); |
| 229 | default: |
| 230 | ; |
| 231 | } |
| 232 | if (e1->type != e2->type) switch (e2->type) { |
| 233 | case E_OR: |
| 234 | case E_AND: |
| 235 | __expr_eliminate_eq(e2->type, ep1, ep2); |
| 236 | default: |
| 237 | ; |
| 238 | } |
| 239 | e1 = expr_eliminate_yn(e1); |
| 240 | e2 = expr_eliminate_yn(e2); |
| 241 | } |
| 242 | |
| 243 | #undef e1 |
| 244 | #undef e2 |
| 245 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 246 | /* |
| 247 | * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two |
| 248 | * &&/|| expressions are considered equal if every operand in one expression |
| 249 | * equals some operand in the other (operands do not need to appear in the same |
| 250 | * order), recursively. |
| 251 | */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 252 | int expr_eq(struct expr *e1, struct expr *e2) |
| 253 | { |
| 254 | int res, old_count; |
| 255 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 256 | /* |
| 257 | * A NULL expr is taken to be yes, but there's also a different way to |
| 258 | * represent yes. expr_is_yes() checks for either representation. |
| 259 | */ |
| 260 | if (!e1 || !e2) |
| 261 | return expr_is_yes(e1) && expr_is_yes(e2); |
| 262 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 263 | if (e1->type != e2->type) |
| 264 | return 0; |
| 265 | switch (e1->type) { |
| 266 | case E_EQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 267 | case E_GEQ: |
| 268 | case E_GTH: |
| 269 | case E_LEQ: |
| 270 | case E_LTH: |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 271 | case E_UNEQUAL: |
| 272 | return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym; |
| 273 | case E_SYMBOL: |
| 274 | return e1->left.sym == e2->left.sym; |
| 275 | case E_NOT: |
| 276 | return expr_eq(e1->left.expr, e2->left.expr); |
| 277 | case E_AND: |
| 278 | case E_OR: |
| 279 | e1 = expr_copy(e1); |
| 280 | e2 = expr_copy(e2); |
| 281 | old_count = trans_count; |
| 282 | expr_eliminate_eq(&e1, &e2); |
| 283 | res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL && |
| 284 | e1->left.sym == e2->left.sym); |
| 285 | expr_free(e1); |
| 286 | expr_free(e2); |
| 287 | trans_count = old_count; |
| 288 | return res; |
| 289 | case E_LIST: |
| 290 | case E_RANGE: |
| 291 | case E_NONE: |
| 292 | /* panic */; |
| 293 | } |
| 294 | |
| 295 | if (DEBUG_EXPR) { |
| 296 | expr_fprint(e1, stdout); |
| 297 | printf(" = "); |
| 298 | expr_fprint(e2, stdout); |
| 299 | printf(" ?\n"); |
| 300 | } |
| 301 | |
| 302 | return 0; |
| 303 | } |
| 304 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 305 | /* |
| 306 | * Recursively performs the following simplifications in-place (as well as the |
| 307 | * corresponding simplifications with swapped operands): |
| 308 | * |
| 309 | * expr && n -> n |
| 310 | * expr && y -> expr |
| 311 | * expr || n -> expr |
| 312 | * expr || y -> y |
| 313 | * |
| 314 | * Returns the optimized expression. |
| 315 | */ |
| 316 | static struct expr *expr_eliminate_yn(struct expr *e) |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 317 | { |
| 318 | struct expr *tmp; |
| 319 | |
| 320 | if (e) switch (e->type) { |
| 321 | case E_AND: |
| 322 | e->left.expr = expr_eliminate_yn(e->left.expr); |
| 323 | e->right.expr = expr_eliminate_yn(e->right.expr); |
| 324 | if (e->left.expr->type == E_SYMBOL) { |
| 325 | if (e->left.expr->left.sym == &symbol_no) { |
| 326 | expr_free(e->left.expr); |
| 327 | expr_free(e->right.expr); |
| 328 | e->type = E_SYMBOL; |
| 329 | e->left.sym = &symbol_no; |
| 330 | e->right.expr = NULL; |
| 331 | return e; |
| 332 | } else if (e->left.expr->left.sym == &symbol_yes) { |
| 333 | free(e->left.expr); |
| 334 | tmp = e->right.expr; |
| 335 | *e = *(e->right.expr); |
| 336 | free(tmp); |
| 337 | return e; |
| 338 | } |
| 339 | } |
| 340 | if (e->right.expr->type == E_SYMBOL) { |
| 341 | if (e->right.expr->left.sym == &symbol_no) { |
| 342 | expr_free(e->left.expr); |
| 343 | expr_free(e->right.expr); |
| 344 | e->type = E_SYMBOL; |
| 345 | e->left.sym = &symbol_no; |
| 346 | e->right.expr = NULL; |
| 347 | return e; |
| 348 | } else if (e->right.expr->left.sym == &symbol_yes) { |
| 349 | free(e->right.expr); |
| 350 | tmp = e->left.expr; |
| 351 | *e = *(e->left.expr); |
| 352 | free(tmp); |
| 353 | return e; |
| 354 | } |
| 355 | } |
| 356 | break; |
| 357 | case E_OR: |
| 358 | e->left.expr = expr_eliminate_yn(e->left.expr); |
| 359 | e->right.expr = expr_eliminate_yn(e->right.expr); |
| 360 | if (e->left.expr->type == E_SYMBOL) { |
| 361 | if (e->left.expr->left.sym == &symbol_no) { |
| 362 | free(e->left.expr); |
| 363 | tmp = e->right.expr; |
| 364 | *e = *(e->right.expr); |
| 365 | free(tmp); |
| 366 | return e; |
| 367 | } else if (e->left.expr->left.sym == &symbol_yes) { |
| 368 | expr_free(e->left.expr); |
| 369 | expr_free(e->right.expr); |
| 370 | e->type = E_SYMBOL; |
| 371 | e->left.sym = &symbol_yes; |
| 372 | e->right.expr = NULL; |
| 373 | return e; |
| 374 | } |
| 375 | } |
| 376 | if (e->right.expr->type == E_SYMBOL) { |
| 377 | if (e->right.expr->left.sym == &symbol_no) { |
| 378 | free(e->right.expr); |
| 379 | tmp = e->left.expr; |
| 380 | *e = *(e->left.expr); |
| 381 | free(tmp); |
| 382 | return e; |
| 383 | } else if (e->right.expr->left.sym == &symbol_yes) { |
| 384 | expr_free(e->left.expr); |
| 385 | expr_free(e->right.expr); |
| 386 | e->type = E_SYMBOL; |
| 387 | e->left.sym = &symbol_yes; |
| 388 | e->right.expr = NULL; |
| 389 | return e; |
| 390 | } |
| 391 | } |
| 392 | break; |
| 393 | default: |
| 394 | ; |
| 395 | } |
| 396 | return e; |
| 397 | } |
| 398 | |
| 399 | /* |
| 400 | * bool FOO!=n => FOO |
| 401 | */ |
| 402 | struct expr *expr_trans_bool(struct expr *e) |
| 403 | { |
| 404 | if (!e) |
| 405 | return NULL; |
| 406 | switch (e->type) { |
| 407 | case E_AND: |
| 408 | case E_OR: |
| 409 | case E_NOT: |
| 410 | e->left.expr = expr_trans_bool(e->left.expr); |
| 411 | e->right.expr = expr_trans_bool(e->right.expr); |
| 412 | break; |
| 413 | case E_UNEQUAL: |
| 414 | // FOO!=n -> FOO |
| 415 | if (e->left.sym->type == S_TRISTATE) { |
| 416 | if (e->right.sym == &symbol_no) { |
| 417 | e->type = E_SYMBOL; |
| 418 | e->right.sym = NULL; |
| 419 | } |
| 420 | } |
| 421 | break; |
| 422 | default: |
| 423 | ; |
| 424 | } |
| 425 | return e; |
| 426 | } |
| 427 | |
| 428 | /* |
| 429 | * e1 || e2 -> ? |
| 430 | */ |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 431 | static struct expr *expr_join_or(struct expr *e1, struct expr *e2) |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 432 | { |
| 433 | struct expr *tmp; |
| 434 | struct symbol *sym1, *sym2; |
| 435 | |
| 436 | if (expr_eq(e1, e2)) |
| 437 | return expr_copy(e1); |
| 438 | if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) |
| 439 | return NULL; |
| 440 | if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) |
| 441 | return NULL; |
| 442 | if (e1->type == E_NOT) { |
| 443 | tmp = e1->left.expr; |
| 444 | if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) |
| 445 | return NULL; |
| 446 | sym1 = tmp->left.sym; |
| 447 | } else |
| 448 | sym1 = e1->left.sym; |
| 449 | if (e2->type == E_NOT) { |
| 450 | if (e2->left.expr->type != E_SYMBOL) |
| 451 | return NULL; |
| 452 | sym2 = e2->left.expr->left.sym; |
| 453 | } else |
| 454 | sym2 = e2->left.sym; |
| 455 | if (sym1 != sym2) |
| 456 | return NULL; |
| 457 | if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) |
| 458 | return NULL; |
| 459 | if (sym1->type == S_TRISTATE) { |
| 460 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && |
| 461 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || |
| 462 | (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) { |
| 463 | // (a='y') || (a='m') -> (a!='n') |
| 464 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no); |
| 465 | } |
| 466 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && |
| 467 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || |
| 468 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) { |
| 469 | // (a='y') || (a='n') -> (a!='m') |
| 470 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod); |
| 471 | } |
| 472 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && |
| 473 | ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || |
| 474 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) { |
| 475 | // (a='m') || (a='n') -> (a!='y') |
| 476 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes); |
| 477 | } |
| 478 | } |
| 479 | if (sym1->type == S_BOOLEAN && sym1 == sym2) { |
| 480 | if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) || |
| 481 | (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL)) |
| 482 | return expr_alloc_symbol(&symbol_yes); |
| 483 | } |
| 484 | |
| 485 | if (DEBUG_EXPR) { |
| 486 | printf("optimize ("); |
| 487 | expr_fprint(e1, stdout); |
| 488 | printf(") || ("); |
| 489 | expr_fprint(e2, stdout); |
| 490 | printf(")?\n"); |
| 491 | } |
| 492 | return NULL; |
| 493 | } |
| 494 | |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 495 | static struct expr *expr_join_and(struct expr *e1, struct expr *e2) |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 496 | { |
| 497 | struct expr *tmp; |
| 498 | struct symbol *sym1, *sym2; |
| 499 | |
| 500 | if (expr_eq(e1, e2)) |
| 501 | return expr_copy(e1); |
| 502 | if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) |
| 503 | return NULL; |
| 504 | if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) |
| 505 | return NULL; |
| 506 | if (e1->type == E_NOT) { |
| 507 | tmp = e1->left.expr; |
| 508 | if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) |
| 509 | return NULL; |
| 510 | sym1 = tmp->left.sym; |
| 511 | } else |
| 512 | sym1 = e1->left.sym; |
| 513 | if (e2->type == E_NOT) { |
| 514 | if (e2->left.expr->type != E_SYMBOL) |
| 515 | return NULL; |
| 516 | sym2 = e2->left.expr->left.sym; |
| 517 | } else |
| 518 | sym2 = e2->left.sym; |
| 519 | if (sym1 != sym2) |
| 520 | return NULL; |
| 521 | if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) |
| 522 | return NULL; |
| 523 | |
| 524 | if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) || |
| 525 | (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes)) |
| 526 | // (a) && (a='y') -> (a='y') |
| 527 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); |
| 528 | |
| 529 | if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) || |
| 530 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no)) |
| 531 | // (a) && (a!='n') -> (a) |
| 532 | return expr_alloc_symbol(sym1); |
| 533 | |
| 534 | if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) || |
| 535 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod)) |
| 536 | // (a) && (a!='m') -> (a='y') |
| 537 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); |
| 538 | |
| 539 | if (sym1->type == S_TRISTATE) { |
| 540 | if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) { |
| 541 | // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' |
| 542 | sym2 = e1->right.sym; |
| 543 | if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) |
| 544 | return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) |
| 545 | : expr_alloc_symbol(&symbol_no); |
| 546 | } |
| 547 | if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) { |
| 548 | // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' |
| 549 | sym2 = e2->right.sym; |
| 550 | if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) |
| 551 | return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) |
| 552 | : expr_alloc_symbol(&symbol_no); |
| 553 | } |
| 554 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && |
| 555 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || |
| 556 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) |
| 557 | // (a!='y') && (a!='n') -> (a='m') |
| 558 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod); |
| 559 | |
| 560 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && |
| 561 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || |
| 562 | (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) |
| 563 | // (a!='y') && (a!='m') -> (a='n') |
| 564 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_no); |
| 565 | |
| 566 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && |
| 567 | ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || |
| 568 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) |
| 569 | // (a!='m') && (a!='n') -> (a='m') |
| 570 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); |
| 571 | |
| 572 | if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) || |
| 573 | (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) || |
| 574 | (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) || |
| 575 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes)) |
| 576 | return NULL; |
| 577 | } |
| 578 | |
| 579 | if (DEBUG_EXPR) { |
| 580 | printf("optimize ("); |
| 581 | expr_fprint(e1, stdout); |
| 582 | printf(") && ("); |
| 583 | expr_fprint(e2, stdout); |
| 584 | printf(")?\n"); |
| 585 | } |
| 586 | return NULL; |
| 587 | } |
| 588 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 589 | /* |
| 590 | * expr_eliminate_dups() helper. |
| 591 | * |
| 592 | * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does |
| 593 | * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared |
| 594 | * against all other leaves to look for simplifications. |
| 595 | */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 596 | static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2) |
| 597 | { |
| 598 | #define e1 (*ep1) |
| 599 | #define e2 (*ep2) |
| 600 | struct expr *tmp; |
| 601 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 602 | /* Recurse down to leaves */ |
| 603 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 604 | if (e1->type == type) { |
| 605 | expr_eliminate_dups1(type, &e1->left.expr, &e2); |
| 606 | expr_eliminate_dups1(type, &e1->right.expr, &e2); |
| 607 | return; |
| 608 | } |
| 609 | if (e2->type == type) { |
| 610 | expr_eliminate_dups1(type, &e1, &e2->left.expr); |
| 611 | expr_eliminate_dups1(type, &e1, &e2->right.expr); |
| 612 | return; |
| 613 | } |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 614 | |
| 615 | /* e1 and e2 are leaves. Compare and process them. */ |
| 616 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 617 | if (e1 == e2) |
| 618 | return; |
| 619 | |
| 620 | switch (e1->type) { |
| 621 | case E_OR: case E_AND: |
| 622 | expr_eliminate_dups1(e1->type, &e1, &e1); |
| 623 | default: |
| 624 | ; |
| 625 | } |
| 626 | |
| 627 | switch (type) { |
| 628 | case E_OR: |
| 629 | tmp = expr_join_or(e1, e2); |
| 630 | if (tmp) { |
| 631 | expr_free(e1); expr_free(e2); |
| 632 | e1 = expr_alloc_symbol(&symbol_no); |
| 633 | e2 = tmp; |
| 634 | trans_count++; |
| 635 | } |
| 636 | break; |
| 637 | case E_AND: |
| 638 | tmp = expr_join_and(e1, e2); |
| 639 | if (tmp) { |
| 640 | expr_free(e1); expr_free(e2); |
| 641 | e1 = expr_alloc_symbol(&symbol_yes); |
| 642 | e2 = tmp; |
| 643 | trans_count++; |
| 644 | } |
| 645 | break; |
| 646 | default: |
| 647 | ; |
| 648 | } |
| 649 | #undef e1 |
| 650 | #undef e2 |
| 651 | } |
| 652 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 653 | /* |
| 654 | * Rewrites 'e' in-place to remove ("join") duplicate and other redundant |
| 655 | * operands. |
| 656 | * |
| 657 | * Example simplifications: |
| 658 | * |
| 659 | * A || B || A -> A || B |
| 660 | * A && B && A=y -> A=y && B |
| 661 | * |
| 662 | * Returns the deduplicated expression. |
| 663 | */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 664 | struct expr *expr_eliminate_dups(struct expr *e) |
| 665 | { |
| 666 | int oldcount; |
| 667 | if (!e) |
| 668 | return e; |
| 669 | |
| 670 | oldcount = trans_count; |
| 671 | while (1) { |
| 672 | trans_count = 0; |
| 673 | switch (e->type) { |
| 674 | case E_OR: case E_AND: |
| 675 | expr_eliminate_dups1(e->type, &e, &e); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 676 | default: |
| 677 | ; |
| 678 | } |
| 679 | if (!trans_count) |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 680 | /* No simplifications done in this pass. We're done */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 681 | break; |
| 682 | e = expr_eliminate_yn(e); |
| 683 | } |
| 684 | trans_count = oldcount; |
| 685 | return e; |
| 686 | } |
| 687 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 688 | /* |
| 689 | * Performs various simplifications involving logical operators and |
| 690 | * comparisons. |
| 691 | * |
| 692 | * Allocates and returns a new expression. |
| 693 | */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 694 | struct expr *expr_transform(struct expr *e) |
| 695 | { |
| 696 | struct expr *tmp; |
| 697 | |
| 698 | if (!e) |
| 699 | return NULL; |
| 700 | switch (e->type) { |
| 701 | case E_EQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 702 | case E_GEQ: |
| 703 | case E_GTH: |
| 704 | case E_LEQ: |
| 705 | case E_LTH: |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 706 | case E_UNEQUAL: |
| 707 | case E_SYMBOL: |
| 708 | case E_LIST: |
| 709 | break; |
| 710 | default: |
| 711 | e->left.expr = expr_transform(e->left.expr); |
| 712 | e->right.expr = expr_transform(e->right.expr); |
| 713 | } |
| 714 | |
| 715 | switch (e->type) { |
| 716 | case E_EQUAL: |
| 717 | if (e->left.sym->type != S_BOOLEAN) |
| 718 | break; |
| 719 | if (e->right.sym == &symbol_no) { |
| 720 | e->type = E_NOT; |
| 721 | e->left.expr = expr_alloc_symbol(e->left.sym); |
| 722 | e->right.sym = NULL; |
| 723 | break; |
| 724 | } |
| 725 | if (e->right.sym == &symbol_mod) { |
| 726 | printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); |
| 727 | e->type = E_SYMBOL; |
| 728 | e->left.sym = &symbol_no; |
| 729 | e->right.sym = NULL; |
| 730 | break; |
| 731 | } |
| 732 | if (e->right.sym == &symbol_yes) { |
| 733 | e->type = E_SYMBOL; |
| 734 | e->right.sym = NULL; |
| 735 | break; |
| 736 | } |
| 737 | break; |
| 738 | case E_UNEQUAL: |
| 739 | if (e->left.sym->type != S_BOOLEAN) |
| 740 | break; |
| 741 | if (e->right.sym == &symbol_no) { |
| 742 | e->type = E_SYMBOL; |
| 743 | e->right.sym = NULL; |
| 744 | break; |
| 745 | } |
| 746 | if (e->right.sym == &symbol_mod) { |
| 747 | printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); |
| 748 | e->type = E_SYMBOL; |
| 749 | e->left.sym = &symbol_yes; |
| 750 | e->right.sym = NULL; |
| 751 | break; |
| 752 | } |
| 753 | if (e->right.sym == &symbol_yes) { |
| 754 | e->type = E_NOT; |
| 755 | e->left.expr = expr_alloc_symbol(e->left.sym); |
| 756 | e->right.sym = NULL; |
| 757 | break; |
| 758 | } |
| 759 | break; |
| 760 | case E_NOT: |
| 761 | switch (e->left.expr->type) { |
| 762 | case E_NOT: |
| 763 | // !!a -> a |
| 764 | tmp = e->left.expr->left.expr; |
| 765 | free(e->left.expr); |
| 766 | free(e); |
| 767 | e = tmp; |
| 768 | e = expr_transform(e); |
| 769 | break; |
| 770 | case E_EQUAL: |
| 771 | case E_UNEQUAL: |
| 772 | // !a='x' -> a!='x' |
| 773 | tmp = e->left.expr; |
| 774 | free(e); |
| 775 | e = tmp; |
| 776 | e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL; |
| 777 | break; |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 778 | case E_LEQ: |
| 779 | case E_GEQ: |
| 780 | // !a<='x' -> a>'x' |
| 781 | tmp = e->left.expr; |
| 782 | free(e); |
| 783 | e = tmp; |
| 784 | e->type = e->type == E_LEQ ? E_GTH : E_LTH; |
| 785 | break; |
| 786 | case E_LTH: |
| 787 | case E_GTH: |
| 788 | // !a<'x' -> a>='x' |
| 789 | tmp = e->left.expr; |
| 790 | free(e); |
| 791 | e = tmp; |
| 792 | e->type = e->type == E_LTH ? E_GEQ : E_LEQ; |
| 793 | break; |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 794 | case E_OR: |
| 795 | // !(a || b) -> !a && !b |
| 796 | tmp = e->left.expr; |
| 797 | e->type = E_AND; |
| 798 | e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); |
| 799 | tmp->type = E_NOT; |
| 800 | tmp->right.expr = NULL; |
| 801 | e = expr_transform(e); |
| 802 | break; |
| 803 | case E_AND: |
| 804 | // !(a && b) -> !a || !b |
| 805 | tmp = e->left.expr; |
| 806 | e->type = E_OR; |
| 807 | e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); |
| 808 | tmp->type = E_NOT; |
| 809 | tmp->right.expr = NULL; |
| 810 | e = expr_transform(e); |
| 811 | break; |
| 812 | case E_SYMBOL: |
| 813 | if (e->left.expr->left.sym == &symbol_yes) { |
| 814 | // !'y' -> 'n' |
| 815 | tmp = e->left.expr; |
| 816 | free(e); |
| 817 | e = tmp; |
| 818 | e->type = E_SYMBOL; |
| 819 | e->left.sym = &symbol_no; |
| 820 | break; |
| 821 | } |
| 822 | if (e->left.expr->left.sym == &symbol_mod) { |
| 823 | // !'m' -> 'm' |
| 824 | tmp = e->left.expr; |
| 825 | free(e); |
| 826 | e = tmp; |
| 827 | e->type = E_SYMBOL; |
| 828 | e->left.sym = &symbol_mod; |
| 829 | break; |
| 830 | } |
| 831 | if (e->left.expr->left.sym == &symbol_no) { |
| 832 | // !'n' -> 'y' |
| 833 | tmp = e->left.expr; |
| 834 | free(e); |
| 835 | e = tmp; |
| 836 | e->type = E_SYMBOL; |
| 837 | e->left.sym = &symbol_yes; |
| 838 | break; |
| 839 | } |
| 840 | break; |
| 841 | default: |
| 842 | ; |
| 843 | } |
| 844 | break; |
| 845 | default: |
| 846 | ; |
| 847 | } |
| 848 | return e; |
| 849 | } |
| 850 | |
| 851 | int expr_contains_symbol(struct expr *dep, struct symbol *sym) |
| 852 | { |
| 853 | if (!dep) |
| 854 | return 0; |
| 855 | |
| 856 | switch (dep->type) { |
| 857 | case E_AND: |
| 858 | case E_OR: |
| 859 | return expr_contains_symbol(dep->left.expr, sym) || |
| 860 | expr_contains_symbol(dep->right.expr, sym); |
| 861 | case E_SYMBOL: |
| 862 | return dep->left.sym == sym; |
| 863 | case E_EQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 864 | case E_GEQ: |
| 865 | case E_GTH: |
| 866 | case E_LEQ: |
| 867 | case E_LTH: |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 868 | case E_UNEQUAL: |
| 869 | return dep->left.sym == sym || |
| 870 | dep->right.sym == sym; |
| 871 | case E_NOT: |
| 872 | return expr_contains_symbol(dep->left.expr, sym); |
| 873 | default: |
| 874 | ; |
| 875 | } |
| 876 | return 0; |
| 877 | } |
| 878 | |
| 879 | bool expr_depends_symbol(struct expr *dep, struct symbol *sym) |
| 880 | { |
| 881 | if (!dep) |
| 882 | return false; |
| 883 | |
| 884 | switch (dep->type) { |
| 885 | case E_AND: |
| 886 | return expr_depends_symbol(dep->left.expr, sym) || |
| 887 | expr_depends_symbol(dep->right.expr, sym); |
| 888 | case E_SYMBOL: |
| 889 | return dep->left.sym == sym; |
| 890 | case E_EQUAL: |
| 891 | if (dep->left.sym == sym) { |
| 892 | if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod) |
| 893 | return true; |
| 894 | } |
| 895 | break; |
| 896 | case E_UNEQUAL: |
| 897 | if (dep->left.sym == sym) { |
| 898 | if (dep->right.sym == &symbol_no) |
| 899 | return true; |
| 900 | } |
| 901 | break; |
| 902 | default: |
| 903 | ; |
| 904 | } |
| 905 | return false; |
| 906 | } |
| 907 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 908 | /* |
| 909 | * Inserts explicit comparisons of type 'type' to symbol 'sym' into the |
| 910 | * expression 'e'. |
| 911 | * |
| 912 | * Examples transformations for type == E_UNEQUAL, sym == &symbol_no: |
| 913 | * |
| 914 | * A -> A!=n |
| 915 | * !A -> A=n |
| 916 | * A && B -> !(A=n || B=n) |
| 917 | * A || B -> !(A=n && B=n) |
| 918 | * A && (B || C) -> !(A=n || (B=n && C=n)) |
| 919 | * |
| 920 | * Allocates and returns a new expression. |
| 921 | */ |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 922 | struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) |
| 923 | { |
| 924 | struct expr *e1, *e2; |
| 925 | |
| 926 | if (!e) { |
| 927 | e = expr_alloc_symbol(sym); |
| 928 | if (type == E_UNEQUAL) |
| 929 | e = expr_alloc_one(E_NOT, e); |
| 930 | return e; |
| 931 | } |
| 932 | switch (e->type) { |
| 933 | case E_AND: |
| 934 | e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); |
| 935 | e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); |
| 936 | if (sym == &symbol_yes) |
| 937 | e = expr_alloc_two(E_AND, e1, e2); |
| 938 | if (sym == &symbol_no) |
| 939 | e = expr_alloc_two(E_OR, e1, e2); |
| 940 | if (type == E_UNEQUAL) |
| 941 | e = expr_alloc_one(E_NOT, e); |
| 942 | return e; |
| 943 | case E_OR: |
| 944 | e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); |
| 945 | e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); |
| 946 | if (sym == &symbol_yes) |
| 947 | e = expr_alloc_two(E_OR, e1, e2); |
| 948 | if (sym == &symbol_no) |
| 949 | e = expr_alloc_two(E_AND, e1, e2); |
| 950 | if (type == E_UNEQUAL) |
| 951 | e = expr_alloc_one(E_NOT, e); |
| 952 | return e; |
| 953 | case E_NOT: |
| 954 | return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym); |
| 955 | case E_UNEQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 956 | case E_LTH: |
| 957 | case E_LEQ: |
| 958 | case E_GTH: |
| 959 | case E_GEQ: |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 960 | case E_EQUAL: |
| 961 | if (type == E_EQUAL) { |
| 962 | if (sym == &symbol_yes) |
| 963 | return expr_copy(e); |
| 964 | if (sym == &symbol_mod) |
| 965 | return expr_alloc_symbol(&symbol_no); |
| 966 | if (sym == &symbol_no) |
| 967 | return expr_alloc_one(E_NOT, expr_copy(e)); |
| 968 | } else { |
| 969 | if (sym == &symbol_yes) |
| 970 | return expr_alloc_one(E_NOT, expr_copy(e)); |
| 971 | if (sym == &symbol_mod) |
| 972 | return expr_alloc_symbol(&symbol_yes); |
| 973 | if (sym == &symbol_no) |
| 974 | return expr_copy(e); |
| 975 | } |
| 976 | break; |
| 977 | case E_SYMBOL: |
| 978 | return expr_alloc_comp(type, e->left.sym, sym); |
| 979 | case E_LIST: |
| 980 | case E_RANGE: |
| 981 | case E_NONE: |
| 982 | /* panic */; |
| 983 | } |
| 984 | return NULL; |
| 985 | } |
| 986 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 987 | enum string_value_kind { |
| 988 | k_string, |
| 989 | k_signed, |
| 990 | k_unsigned, |
| 991 | }; |
| 992 | |
| 993 | union string_value { |
| 994 | unsigned long long u; |
| 995 | signed long long s; |
| 996 | }; |
| 997 | |
| 998 | static enum string_value_kind expr_parse_string(const char *str, |
| 999 | enum symbol_type type, |
| 1000 | union string_value *val) |
| 1001 | { |
| 1002 | char *tail; |
| 1003 | enum string_value_kind kind; |
| 1004 | |
| 1005 | errno = 0; |
| 1006 | switch (type) { |
| 1007 | case S_BOOLEAN: |
| 1008 | case S_TRISTATE: |
| 1009 | val->s = !strcmp(str, "n") ? 0 : |
| 1010 | !strcmp(str, "m") ? 1 : |
| 1011 | !strcmp(str, "y") ? 2 : -1; |
| 1012 | return k_signed; |
| 1013 | case S_INT: |
| 1014 | val->s = strtoll(str, &tail, 10); |
| 1015 | kind = k_signed; |
| 1016 | break; |
| 1017 | case S_HEX: |
| 1018 | val->u = strtoull(str, &tail, 16); |
| 1019 | kind = k_unsigned; |
| 1020 | break; |
| 1021 | default: |
| 1022 | val->s = strtoll(str, &tail, 0); |
| 1023 | kind = k_signed; |
| 1024 | break; |
| 1025 | } |
| 1026 | return !errno && !*tail && tail > str && isxdigit(tail[-1]) |
| 1027 | ? kind : k_string; |
| 1028 | } |
| 1029 | |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1030 | tristate expr_calc_value(struct expr *e) |
| 1031 | { |
| 1032 | tristate val1, val2; |
| 1033 | const char *str1, *str2; |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1034 | enum string_value_kind k1 = k_string, k2 = k_string; |
| 1035 | union string_value lval = {}, rval = {}; |
| 1036 | int res; |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1037 | |
| 1038 | if (!e) |
| 1039 | return yes; |
| 1040 | |
| 1041 | switch (e->type) { |
| 1042 | case E_SYMBOL: |
| 1043 | sym_calc_value(e->left.sym); |
| 1044 | return e->left.sym->curr.tri; |
| 1045 | case E_AND: |
| 1046 | val1 = expr_calc_value(e->left.expr); |
| 1047 | val2 = expr_calc_value(e->right.expr); |
| 1048 | return EXPR_AND(val1, val2); |
| 1049 | case E_OR: |
| 1050 | val1 = expr_calc_value(e->left.expr); |
| 1051 | val2 = expr_calc_value(e->right.expr); |
| 1052 | return EXPR_OR(val1, val2); |
| 1053 | case E_NOT: |
| 1054 | val1 = expr_calc_value(e->left.expr); |
| 1055 | return EXPR_NOT(val1); |
| 1056 | case E_EQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1057 | case E_GEQ: |
| 1058 | case E_GTH: |
| 1059 | case E_LEQ: |
| 1060 | case E_LTH: |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1061 | case E_UNEQUAL: |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1062 | break; |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1063 | default: |
| 1064 | printf("expr_calc_value: %d?\n", e->type); |
| 1065 | return no; |
| 1066 | } |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1067 | |
| 1068 | sym_calc_value(e->left.sym); |
| 1069 | sym_calc_value(e->right.sym); |
| 1070 | str1 = sym_get_string_value(e->left.sym); |
| 1071 | str2 = sym_get_string_value(e->right.sym); |
| 1072 | |
| 1073 | if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) { |
| 1074 | k1 = expr_parse_string(str1, e->left.sym->type, &lval); |
| 1075 | k2 = expr_parse_string(str2, e->right.sym->type, &rval); |
| 1076 | } |
| 1077 | |
| 1078 | if (k1 == k_string || k2 == k_string) |
| 1079 | res = strcmp(str1, str2); |
| 1080 | else if (k1 == k_unsigned || k2 == k_unsigned) |
| 1081 | res = (lval.u > rval.u) - (lval.u < rval.u); |
| 1082 | else /* if (k1 == k_signed && k2 == k_signed) */ |
| 1083 | res = (lval.s > rval.s) - (lval.s < rval.s); |
| 1084 | |
| 1085 | switch(e->type) { |
| 1086 | case E_EQUAL: |
| 1087 | return res ? no : yes; |
| 1088 | case E_GEQ: |
| 1089 | return res >= 0 ? yes : no; |
| 1090 | case E_GTH: |
| 1091 | return res > 0 ? yes : no; |
| 1092 | case E_LEQ: |
| 1093 | return res <= 0 ? yes : no; |
| 1094 | case E_LTH: |
| 1095 | return res < 0 ? yes : no; |
| 1096 | case E_UNEQUAL: |
| 1097 | return res ? yes : no; |
| 1098 | default: |
| 1099 | printf("expr_calc_value: relation %d?\n", e->type); |
| 1100 | return no; |
| 1101 | } |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1102 | } |
| 1103 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1104 | static int expr_compare_type(enum expr_type t1, enum expr_type t2) |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1105 | { |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1106 | if (t1 == t2) |
| 1107 | return 0; |
| 1108 | switch (t1) { |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1109 | case E_LEQ: |
| 1110 | case E_LTH: |
| 1111 | case E_GEQ: |
| 1112 | case E_GTH: |
| 1113 | if (t2 == E_EQUAL || t2 == E_UNEQUAL) |
| 1114 | return 1; |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1115 | case E_EQUAL: |
| 1116 | case E_UNEQUAL: |
| 1117 | if (t2 == E_NOT) |
| 1118 | return 1; |
| 1119 | case E_NOT: |
| 1120 | if (t2 == E_AND) |
| 1121 | return 1; |
| 1122 | case E_AND: |
| 1123 | if (t2 == E_OR) |
| 1124 | return 1; |
| 1125 | case E_OR: |
| 1126 | if (t2 == E_LIST) |
| 1127 | return 1; |
| 1128 | case E_LIST: |
| 1129 | if (t2 == 0) |
| 1130 | return 1; |
| 1131 | default: |
| 1132 | return -1; |
| 1133 | } |
| 1134 | printf("[%dgt%d?]", t1, t2); |
| 1135 | return 0; |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1136 | } |
| 1137 | |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1138 | void expr_print(struct expr *e, |
| 1139 | void (*fn)(void *, struct symbol *, const char *), |
| 1140 | void *data, int prevtoken) |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1141 | { |
| 1142 | if (!e) { |
| 1143 | fn(data, NULL, "y"); |
| 1144 | return; |
| 1145 | } |
| 1146 | |
| 1147 | if (expr_compare_type(prevtoken, e->type) > 0) |
| 1148 | fn(data, NULL, "("); |
| 1149 | switch (e->type) { |
| 1150 | case E_SYMBOL: |
| 1151 | if (e->left.sym->name) |
| 1152 | fn(data, e->left.sym, e->left.sym->name); |
| 1153 | else |
| 1154 | fn(data, NULL, "<choice>"); |
| 1155 | break; |
| 1156 | case E_NOT: |
| 1157 | fn(data, NULL, "!"); |
| 1158 | expr_print(e->left.expr, fn, data, E_NOT); |
| 1159 | break; |
| 1160 | case E_EQUAL: |
| 1161 | if (e->left.sym->name) |
| 1162 | fn(data, e->left.sym, e->left.sym->name); |
| 1163 | else |
| 1164 | fn(data, NULL, "<choice>"); |
| 1165 | fn(data, NULL, "="); |
| 1166 | fn(data, e->right.sym, e->right.sym->name); |
| 1167 | break; |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1168 | case E_LEQ: |
| 1169 | case E_LTH: |
| 1170 | if (e->left.sym->name) |
| 1171 | fn(data, e->left.sym, e->left.sym->name); |
| 1172 | else |
| 1173 | fn(data, NULL, "<choice>"); |
| 1174 | fn(data, NULL, e->type == E_LEQ ? "<=" : "<"); |
| 1175 | fn(data, e->right.sym, e->right.sym->name); |
| 1176 | break; |
| 1177 | case E_GEQ: |
| 1178 | case E_GTH: |
| 1179 | if (e->left.sym->name) |
| 1180 | fn(data, e->left.sym, e->left.sym->name); |
| 1181 | else |
| 1182 | fn(data, NULL, "<choice>"); |
| 1183 | fn(data, NULL, e->type == E_GEQ ? ">=" : ">"); |
| 1184 | fn(data, e->right.sym, e->right.sym->name); |
| 1185 | break; |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1186 | case E_UNEQUAL: |
| 1187 | if (e->left.sym->name) |
| 1188 | fn(data, e->left.sym, e->left.sym->name); |
| 1189 | else |
| 1190 | fn(data, NULL, "<choice>"); |
| 1191 | fn(data, NULL, "!="); |
| 1192 | fn(data, e->right.sym, e->right.sym->name); |
| 1193 | break; |
| 1194 | case E_OR: |
| 1195 | expr_print(e->left.expr, fn, data, E_OR); |
| 1196 | fn(data, NULL, " || "); |
| 1197 | expr_print(e->right.expr, fn, data, E_OR); |
| 1198 | break; |
| 1199 | case E_AND: |
| 1200 | expr_print(e->left.expr, fn, data, E_AND); |
| 1201 | fn(data, NULL, " && "); |
| 1202 | expr_print(e->right.expr, fn, data, E_AND); |
| 1203 | break; |
| 1204 | case E_LIST: |
| 1205 | fn(data, e->right.sym, e->right.sym->name); |
| 1206 | if (e->left.expr) { |
| 1207 | fn(data, NULL, " ^ "); |
| 1208 | expr_print(e->left.expr, fn, data, E_LIST); |
| 1209 | } |
| 1210 | break; |
| 1211 | case E_RANGE: |
| 1212 | fn(data, NULL, "["); |
| 1213 | fn(data, e->left.sym, e->left.sym->name); |
| 1214 | fn(data, NULL, " "); |
| 1215 | fn(data, e->right.sym, e->right.sym->name); |
| 1216 | fn(data, NULL, "]"); |
| 1217 | break; |
| 1218 | default: |
| 1219 | { |
| 1220 | char buf[32]; |
| 1221 | sprintf(buf, "<unknown type %d>", e->type); |
| 1222 | fn(data, NULL, buf); |
| 1223 | break; |
| 1224 | } |
| 1225 | } |
| 1226 | if (expr_compare_type(prevtoken, e->type) > 0) |
| 1227 | fn(data, NULL, ")"); |
| 1228 | } |
| 1229 | |
| 1230 | static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) |
| 1231 | { |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 1232 | xfwrite(str, strlen(str), 1, data); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1233 | } |
| 1234 | |
| 1235 | void expr_fprint(struct expr *e, FILE *out) |
| 1236 | { |
| 1237 | expr_print(e, expr_print_file_helper, out, E_NONE); |
| 1238 | } |
| 1239 | |
| 1240 | static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) |
| 1241 | { |
Patrick Georgi | d520840 | 2014-04-11 20:24:06 +0200 | [diff] [blame] | 1242 | struct gstr *gs = (struct gstr*)data; |
| 1243 | const char *sym_str = NULL; |
| 1244 | |
| 1245 | if (sym) |
| 1246 | sym_str = sym_get_string_value(sym); |
| 1247 | |
| 1248 | if (gs->max_width) { |
| 1249 | unsigned extra_length = strlen(str); |
| 1250 | const char *last_cr = strrchr(gs->s, '\n'); |
| 1251 | unsigned last_line_length; |
| 1252 | |
| 1253 | if (sym_str) |
| 1254 | extra_length += 4 + strlen(sym_str); |
| 1255 | |
| 1256 | if (!last_cr) |
| 1257 | last_cr = gs->s; |
| 1258 | |
| 1259 | last_line_length = strlen(gs->s) - (last_cr - gs->s); |
| 1260 | |
| 1261 | if ((last_line_length + extra_length) > gs->max_width) |
| 1262 | str_append(gs, "\\\n"); |
| 1263 | } |
| 1264 | |
| 1265 | str_append(gs, str); |
| 1266 | if (sym && sym->type != S_UNKNOWN) |
| 1267 | str_printf(gs, " [=%s]", sym_str); |
Patrick Georgi | 0588d19 | 2009-08-12 15:00:51 +0000 | [diff] [blame] | 1268 | } |
| 1269 | |
| 1270 | void expr_gstr_print(struct expr *e, struct gstr *gs) |
| 1271 | { |
| 1272 | expr_print(e, expr_print_gstr_helper, gs, E_NONE); |
| 1273 | } |
Patrick Georgi | 53ea1d4 | 2019-11-22 16:55:58 +0100 | [diff] [blame] | 1274 | |
| 1275 | /* |
| 1276 | * Transform the top level "||" tokens into newlines and prepend each |
| 1277 | * line with a minus. This makes expressions much easier to read. |
| 1278 | * Suitable for reverse dependency expressions. |
| 1279 | */ |
| 1280 | static void expr_print_revdep(struct expr *e, |
| 1281 | void (*fn)(void *, struct symbol *, const char *), |
| 1282 | void *data, tristate pr_type, const char **title) |
| 1283 | { |
| 1284 | if (e->type == E_OR) { |
| 1285 | expr_print_revdep(e->left.expr, fn, data, pr_type, title); |
| 1286 | expr_print_revdep(e->right.expr, fn, data, pr_type, title); |
| 1287 | } else if (expr_calc_value(e) == pr_type) { |
| 1288 | if (*title) { |
| 1289 | fn(data, NULL, *title); |
| 1290 | *title = NULL; |
| 1291 | } |
| 1292 | |
| 1293 | fn(data, NULL, " - "); |
| 1294 | expr_print(e, fn, data, E_NONE); |
| 1295 | fn(data, NULL, "\n"); |
| 1296 | } |
| 1297 | } |
| 1298 | |
| 1299 | void expr_gstr_print_revdep(struct expr *e, struct gstr *gs, |
| 1300 | tristate pr_type, const char *title) |
| 1301 | { |
| 1302 | expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title); |
| 1303 | } |