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