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 struct expr *expr_eliminate_yn(struct expr *e);
17
expr_alloc_symbol(struct symbol * sym)18 struct expr *expr_alloc_symbol(struct symbol *sym)
19 {
20 struct expr *e = xcalloc(1, sizeof(*e));
21 e->type = E_SYMBOL;
22 e->left.sym = sym;
23 return e;
24 }
25
expr_alloc_one(enum expr_type type,struct expr * ce)26 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
27 {
28 struct expr *e = xcalloc(1, sizeof(*e));
29 e->type = type;
30 e->left.expr = ce;
31 return e;
32 }
33
expr_alloc_two(enum expr_type type,struct expr * e1,struct expr * e2)34 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
35 {
36 struct expr *e = xcalloc(1, sizeof(*e));
37 e->type = type;
38 e->left.expr = e1;
39 e->right.expr = e2;
40 return e;
41 }
42
expr_alloc_comp(enum expr_type type,struct symbol * s1,struct symbol * s2)43 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
44 {
45 struct expr *e = xcalloc(1, sizeof(*e));
46 e->type = type;
47 e->left.sym = s1;
48 e->right.sym = s2;
49 return e;
50 }
51
expr_alloc_and(struct expr * e1,struct expr * e2)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
expr_alloc_or(struct expr * e1,struct expr * e2)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
expr_copy(const struct expr * org)66 struct expr *expr_copy(const struct expr *org)
67 {
68 struct expr *e;
69
70 if (!org)
71 return NULL;
72
73 e = xmalloc(sizeof(*org));
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:
83 case E_GEQ:
84 case E_GTH:
85 case E_LEQ:
86 case E_LTH:
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:
98 fprintf(stderr, "can't copy type %d\n", e->type);
99 free(e);
100 e = NULL;
101 break;
102 }
103
104 return e;
105 }
106
expr_free(struct expr * e)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);
117 break;
118 case E_EQUAL:
119 case E_GEQ:
120 case E_GTH:
121 case E_LEQ:
122 case E_LTH:
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:
131 fprintf(stderr, "how to free type %d?\n", e->type);
132 break;
133 }
134 free(e);
135 }
136
137 static int trans_count;
138
139 #define e1 (*ep1)
140 #define e2 (*ep2)
141
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 */
__expr_eliminate_eq(enum expr_type type,struct expr ** ep1,struct expr ** ep2)150 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
151 {
152 /* Recurse down to leaves */
153
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 }
164
165 /* e1 and e2 are leaves. Compare them. */
166
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;
173
174 /* e1 and e2 are equal leaves. Prepare them for elimination. */
175
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
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 */
expr_eliminate_eq(struct expr ** ep1,struct expr ** ep2)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
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 */
expr_eq(struct expr * e1,struct expr * e2)252 int expr_eq(struct expr *e1, struct expr *e2)
253 {
254 int res, old_count;
255
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
263 if (e1->type != e2->type)
264 return 0;
265 switch (e1->type) {
266 case E_EQUAL:
267 case E_GEQ:
268 case E_GTH:
269 case E_LEQ:
270 case E_LTH:
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
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 */
expr_eliminate_yn(struct expr * e)316 static struct expr *expr_eliminate_yn(struct expr *e)
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 * e1 || e2 -> ?
401 */
expr_join_or(struct expr * e1,struct expr * e2)402 static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
403 {
404 struct expr *tmp;
405 struct symbol *sym1, *sym2;
406
407 if (expr_eq(e1, e2))
408 return expr_copy(e1);
409 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
410 return NULL;
411 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
412 return NULL;
413 if (e1->type == E_NOT) {
414 tmp = e1->left.expr;
415 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
416 return NULL;
417 sym1 = tmp->left.sym;
418 } else
419 sym1 = e1->left.sym;
420 if (e2->type == E_NOT) {
421 if (e2->left.expr->type != E_SYMBOL)
422 return NULL;
423 sym2 = e2->left.expr->left.sym;
424 } else
425 sym2 = e2->left.sym;
426 if (sym1 != sym2)
427 return NULL;
428 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
429 return NULL;
430 if (sym1->type == S_TRISTATE) {
431 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
432 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
433 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
434 // (a='y') || (a='m') -> (a!='n')
435 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
436 }
437 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
438 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
439 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
440 // (a='y') || (a='n') -> (a!='m')
441 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
442 }
443 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
444 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
445 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
446 // (a='m') || (a='n') -> (a!='y')
447 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
448 }
449 }
450 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
451 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
452 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
453 return expr_alloc_symbol(&symbol_yes);
454 }
455
456 if (DEBUG_EXPR) {
457 printf("optimize (");
458 expr_fprint(e1, stdout);
459 printf(") || (");
460 expr_fprint(e2, stdout);
461 printf(")?\n");
462 }
463 return NULL;
464 }
465
expr_join_and(struct expr * e1,struct expr * e2)466 static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
467 {
468 struct expr *tmp;
469 struct symbol *sym1, *sym2;
470
471 if (expr_eq(e1, e2))
472 return expr_copy(e1);
473 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
474 return NULL;
475 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
476 return NULL;
477 if (e1->type == E_NOT) {
478 tmp = e1->left.expr;
479 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
480 return NULL;
481 sym1 = tmp->left.sym;
482 } else
483 sym1 = e1->left.sym;
484 if (e2->type == E_NOT) {
485 if (e2->left.expr->type != E_SYMBOL)
486 return NULL;
487 sym2 = e2->left.expr->left.sym;
488 } else
489 sym2 = e2->left.sym;
490 if (sym1 != sym2)
491 return NULL;
492 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
493 return NULL;
494
495 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
496 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
497 // (a) && (a='y') -> (a='y')
498 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
499
500 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
501 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
502 // (a) && (a!='n') -> (a)
503 return expr_alloc_symbol(sym1);
504
505 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
506 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
507 // (a) && (a!='m') -> (a='y')
508 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
509
510 if (sym1->type == S_TRISTATE) {
511 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
512 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
513 sym2 = e1->right.sym;
514 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
515 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
516 : expr_alloc_symbol(&symbol_no);
517 }
518 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
519 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
520 sym2 = e2->right.sym;
521 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
522 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
523 : expr_alloc_symbol(&symbol_no);
524 }
525 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
526 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
527 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
528 // (a!='y') && (a!='n') -> (a='m')
529 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
530
531 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
532 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
533 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
534 // (a!='y') && (a!='m') -> (a='n')
535 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
536
537 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
538 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
539 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
540 // (a!='m') && (a!='n') -> (a='m')
541 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
542
543 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
544 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
545 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
546 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
547 return NULL;
548 }
549
550 if (DEBUG_EXPR) {
551 printf("optimize (");
552 expr_fprint(e1, stdout);
553 printf(") && (");
554 expr_fprint(e2, stdout);
555 printf(")?\n");
556 }
557 return NULL;
558 }
559
560 /*
561 * expr_eliminate_dups() helper.
562 *
563 * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
564 * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
565 * against all other leaves to look for simplifications.
566 */
expr_eliminate_dups1(enum expr_type type,struct expr ** ep1,struct expr ** ep2)567 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
568 {
569 #define e1 (*ep1)
570 #define e2 (*ep2)
571 struct expr *tmp;
572
573 /* Recurse down to leaves */
574
575 if (e1->type == type) {
576 expr_eliminate_dups1(type, &e1->left.expr, &e2);
577 expr_eliminate_dups1(type, &e1->right.expr, &e2);
578 return;
579 }
580 if (e2->type == type) {
581 expr_eliminate_dups1(type, &e1, &e2->left.expr);
582 expr_eliminate_dups1(type, &e1, &e2->right.expr);
583 return;
584 }
585
586 /* e1 and e2 are leaves. Compare and process them. */
587
588 if (e1 == e2)
589 return;
590
591 switch (e1->type) {
592 case E_OR: case E_AND:
593 expr_eliminate_dups1(e1->type, &e1, &e1);
594 default:
595 ;
596 }
597
598 switch (type) {
599 case E_OR:
600 tmp = expr_join_or(e1, e2);
601 if (tmp) {
602 expr_free(e1); expr_free(e2);
603 e1 = expr_alloc_symbol(&symbol_no);
604 e2 = tmp;
605 trans_count++;
606 }
607 break;
608 case E_AND:
609 tmp = expr_join_and(e1, e2);
610 if (tmp) {
611 expr_free(e1); expr_free(e2);
612 e1 = expr_alloc_symbol(&symbol_yes);
613 e2 = tmp;
614 trans_count++;
615 }
616 break;
617 default:
618 ;
619 }
620 #undef e1
621 #undef e2
622 }
623
624 /*
625 * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
626 * operands.
627 *
628 * Example simplifications:
629 *
630 * A || B || A -> A || B
631 * A && B && A=y -> A=y && B
632 *
633 * Returns the deduplicated expression.
634 */
expr_eliminate_dups(struct expr * e)635 struct expr *expr_eliminate_dups(struct expr *e)
636 {
637 int oldcount;
638 if (!e)
639 return e;
640
641 oldcount = trans_count;
642 while (1) {
643 trans_count = 0;
644 switch (e->type) {
645 case E_OR: case E_AND:
646 expr_eliminate_dups1(e->type, &e, &e);
647 default:
648 ;
649 }
650 if (!trans_count)
651 /* No simplifications done in this pass. We're done */
652 break;
653 e = expr_eliminate_yn(e);
654 }
655 trans_count = oldcount;
656 return e;
657 }
658
659 /*
660 * Performs various simplifications involving logical operators and
661 * comparisons.
662 *
663 * Allocates and returns a new expression.
664 */
expr_transform(struct expr * e)665 struct expr *expr_transform(struct expr *e)
666 {
667 struct expr *tmp;
668
669 if (!e)
670 return NULL;
671 switch (e->type) {
672 case E_EQUAL:
673 case E_GEQ:
674 case E_GTH:
675 case E_LEQ:
676 case E_LTH:
677 case E_UNEQUAL:
678 case E_SYMBOL:
679 case E_LIST:
680 break;
681 default:
682 e->left.expr = expr_transform(e->left.expr);
683 e->right.expr = expr_transform(e->right.expr);
684 }
685
686 switch (e->type) {
687 case E_EQUAL:
688 if (e->left.sym->type != S_BOOLEAN)
689 break;
690 if (e->right.sym == &symbol_no) {
691 e->type = E_NOT;
692 e->left.expr = expr_alloc_symbol(e->left.sym);
693 e->right.sym = NULL;
694 break;
695 }
696 if (e->right.sym == &symbol_mod) {
697 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
698 e->type = E_SYMBOL;
699 e->left.sym = &symbol_no;
700 e->right.sym = NULL;
701 break;
702 }
703 if (e->right.sym == &symbol_yes) {
704 e->type = E_SYMBOL;
705 e->right.sym = NULL;
706 break;
707 }
708 break;
709 case E_UNEQUAL:
710 if (e->left.sym->type != S_BOOLEAN)
711 break;
712 if (e->right.sym == &symbol_no) {
713 e->type = E_SYMBOL;
714 e->right.sym = NULL;
715 break;
716 }
717 if (e->right.sym == &symbol_mod) {
718 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
719 e->type = E_SYMBOL;
720 e->left.sym = &symbol_yes;
721 e->right.sym = NULL;
722 break;
723 }
724 if (e->right.sym == &symbol_yes) {
725 e->type = E_NOT;
726 e->left.expr = expr_alloc_symbol(e->left.sym);
727 e->right.sym = NULL;
728 break;
729 }
730 break;
731 case E_NOT:
732 switch (e->left.expr->type) {
733 case E_NOT:
734 // !!a -> a
735 tmp = e->left.expr->left.expr;
736 free(e->left.expr);
737 free(e);
738 e = tmp;
739 e = expr_transform(e);
740 break;
741 case E_EQUAL:
742 case E_UNEQUAL:
743 // !a='x' -> a!='x'
744 tmp = e->left.expr;
745 free(e);
746 e = tmp;
747 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
748 break;
749 case E_LEQ:
750 case E_GEQ:
751 // !a<='x' -> a>'x'
752 tmp = e->left.expr;
753 free(e);
754 e = tmp;
755 e->type = e->type == E_LEQ ? E_GTH : E_LTH;
756 break;
757 case E_LTH:
758 case E_GTH:
759 // !a<'x' -> a>='x'
760 tmp = e->left.expr;
761 free(e);
762 e = tmp;
763 e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
764 break;
765 case E_OR:
766 // !(a || b) -> !a && !b
767 tmp = e->left.expr;
768 e->type = E_AND;
769 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
770 tmp->type = E_NOT;
771 tmp->right.expr = NULL;
772 e = expr_transform(e);
773 break;
774 case E_AND:
775 // !(a && b) -> !a || !b
776 tmp = e->left.expr;
777 e->type = E_OR;
778 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
779 tmp->type = E_NOT;
780 tmp->right.expr = NULL;
781 e = expr_transform(e);
782 break;
783 case E_SYMBOL:
784 if (e->left.expr->left.sym == &symbol_yes) {
785 // !'y' -> 'n'
786 tmp = e->left.expr;
787 free(e);
788 e = tmp;
789 e->type = E_SYMBOL;
790 e->left.sym = &symbol_no;
791 break;
792 }
793 if (e->left.expr->left.sym == &symbol_mod) {
794 // !'m' -> 'm'
795 tmp = e->left.expr;
796 free(e);
797 e = tmp;
798 e->type = E_SYMBOL;
799 e->left.sym = &symbol_mod;
800 break;
801 }
802 if (e->left.expr->left.sym == &symbol_no) {
803 // !'n' -> 'y'
804 tmp = e->left.expr;
805 free(e);
806 e = tmp;
807 e->type = E_SYMBOL;
808 e->left.sym = &symbol_yes;
809 break;
810 }
811 break;
812 default:
813 ;
814 }
815 break;
816 default:
817 ;
818 }
819 return e;
820 }
821
expr_contains_symbol(struct expr * dep,struct symbol * sym)822 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
823 {
824 if (!dep)
825 return 0;
826
827 switch (dep->type) {
828 case E_AND:
829 case E_OR:
830 return expr_contains_symbol(dep->left.expr, sym) ||
831 expr_contains_symbol(dep->right.expr, sym);
832 case E_SYMBOL:
833 return dep->left.sym == sym;
834 case E_EQUAL:
835 case E_GEQ:
836 case E_GTH:
837 case E_LEQ:
838 case E_LTH:
839 case E_UNEQUAL:
840 return dep->left.sym == sym ||
841 dep->right.sym == sym;
842 case E_NOT:
843 return expr_contains_symbol(dep->left.expr, sym);
844 default:
845 ;
846 }
847 return 0;
848 }
849
expr_depends_symbol(struct expr * dep,struct symbol * sym)850 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
851 {
852 if (!dep)
853 return false;
854
855 switch (dep->type) {
856 case E_AND:
857 return expr_depends_symbol(dep->left.expr, sym) ||
858 expr_depends_symbol(dep->right.expr, sym);
859 case E_SYMBOL:
860 return dep->left.sym == sym;
861 case E_EQUAL:
862 if (dep->left.sym == sym) {
863 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
864 return true;
865 }
866 break;
867 case E_UNEQUAL:
868 if (dep->left.sym == sym) {
869 if (dep->right.sym == &symbol_no)
870 return true;
871 }
872 break;
873 default:
874 ;
875 }
876 return false;
877 }
878
879 /*
880 * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
881 * expression 'e'.
882 *
883 * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
884 *
885 * A -> A!=n
886 * !A -> A=n
887 * A && B -> !(A=n || B=n)
888 * A || B -> !(A=n && B=n)
889 * A && (B || C) -> !(A=n || (B=n && C=n))
890 *
891 * Allocates and returns a new expression.
892 */
expr_trans_compare(struct expr * e,enum expr_type type,struct symbol * sym)893 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
894 {
895 struct expr *e1, *e2;
896
897 if (!e) {
898 e = expr_alloc_symbol(sym);
899 if (type == E_UNEQUAL)
900 e = expr_alloc_one(E_NOT, e);
901 return e;
902 }
903 switch (e->type) {
904 case E_AND:
905 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
906 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
907 if (sym == &symbol_yes)
908 e = expr_alloc_two(E_AND, e1, e2);
909 if (sym == &symbol_no)
910 e = expr_alloc_two(E_OR, e1, e2);
911 if (type == E_UNEQUAL)
912 e = expr_alloc_one(E_NOT, e);
913 return e;
914 case E_OR:
915 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
916 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
917 if (sym == &symbol_yes)
918 e = expr_alloc_two(E_OR, e1, e2);
919 if (sym == &symbol_no)
920 e = expr_alloc_two(E_AND, e1, e2);
921 if (type == E_UNEQUAL)
922 e = expr_alloc_one(E_NOT, e);
923 return e;
924 case E_NOT:
925 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
926 case E_UNEQUAL:
927 case E_LTH:
928 case E_LEQ:
929 case E_GTH:
930 case E_GEQ:
931 case E_EQUAL:
932 if (type == E_EQUAL) {
933 if (sym == &symbol_yes)
934 return expr_copy(e);
935 if (sym == &symbol_mod)
936 return expr_alloc_symbol(&symbol_no);
937 if (sym == &symbol_no)
938 return expr_alloc_one(E_NOT, expr_copy(e));
939 } else {
940 if (sym == &symbol_yes)
941 return expr_alloc_one(E_NOT, expr_copy(e));
942 if (sym == &symbol_mod)
943 return expr_alloc_symbol(&symbol_yes);
944 if (sym == &symbol_no)
945 return expr_copy(e);
946 }
947 break;
948 case E_SYMBOL:
949 return expr_alloc_comp(type, e->left.sym, sym);
950 case E_LIST:
951 case E_RANGE:
952 case E_NONE:
953 /* panic */;
954 }
955 return NULL;
956 }
957
958 enum string_value_kind {
959 k_string,
960 k_signed,
961 k_unsigned,
962 };
963
964 union string_value {
965 unsigned long long u;
966 signed long long s;
967 };
968
expr_parse_string(const char * str,enum symbol_type type,union string_value * val)969 static enum string_value_kind expr_parse_string(const char *str,
970 enum symbol_type type,
971 union string_value *val)
972 {
973 char *tail;
974 enum string_value_kind kind;
975
976 errno = 0;
977 switch (type) {
978 case S_BOOLEAN:
979 case S_TRISTATE:
980 val->s = !strcmp(str, "n") ? 0 :
981 !strcmp(str, "m") ? 1 :
982 !strcmp(str, "y") ? 2 : -1;
983 return k_signed;
984 case S_INT:
985 val->s = strtoll(str, &tail, 10);
986 kind = k_signed;
987 break;
988 case S_HEX:
989 val->u = strtoull(str, &tail, 16);
990 kind = k_unsigned;
991 break;
992 default:
993 val->s = strtoll(str, &tail, 0);
994 kind = k_signed;
995 break;
996 }
997 return !errno && !*tail && tail > str && isxdigit(tail[-1])
998 ? kind : k_string;
999 }
1000
expr_calc_value(struct expr * e)1001 tristate expr_calc_value(struct expr *e)
1002 {
1003 tristate val1, val2;
1004 const char *str1, *str2;
1005 enum string_value_kind k1 = k_string, k2 = k_string;
1006 union string_value lval = {}, rval = {};
1007 int res;
1008
1009 if (!e)
1010 return yes;
1011
1012 switch (e->type) {
1013 case E_SYMBOL:
1014 sym_calc_value(e->left.sym);
1015 return e->left.sym->curr.tri;
1016 case E_AND:
1017 val1 = expr_calc_value(e->left.expr);
1018 val2 = expr_calc_value(e->right.expr);
1019 return EXPR_AND(val1, val2);
1020 case E_OR:
1021 val1 = expr_calc_value(e->left.expr);
1022 val2 = expr_calc_value(e->right.expr);
1023 return EXPR_OR(val1, val2);
1024 case E_NOT:
1025 val1 = expr_calc_value(e->left.expr);
1026 return EXPR_NOT(val1);
1027 case E_EQUAL:
1028 case E_GEQ:
1029 case E_GTH:
1030 case E_LEQ:
1031 case E_LTH:
1032 case E_UNEQUAL:
1033 break;
1034 default:
1035 printf("expr_calc_value: %d?\n", e->type);
1036 return no;
1037 }
1038
1039 sym_calc_value(e->left.sym);
1040 sym_calc_value(e->right.sym);
1041 str1 = sym_get_string_value(e->left.sym);
1042 str2 = sym_get_string_value(e->right.sym);
1043
1044 if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
1045 k1 = expr_parse_string(str1, e->left.sym->type, &lval);
1046 k2 = expr_parse_string(str2, e->right.sym->type, &rval);
1047 }
1048
1049 if (k1 == k_string || k2 == k_string)
1050 res = strcmp(str1, str2);
1051 else if (k1 == k_unsigned || k2 == k_unsigned)
1052 res = (lval.u > rval.u) - (lval.u < rval.u);
1053 else /* if (k1 == k_signed && k2 == k_signed) */
1054 res = (lval.s > rval.s) - (lval.s < rval.s);
1055
1056 switch(e->type) {
1057 case E_EQUAL:
1058 return res ? no : yes;
1059 case E_GEQ:
1060 return res >= 0 ? yes : no;
1061 case E_GTH:
1062 return res > 0 ? yes : no;
1063 case E_LEQ:
1064 return res <= 0 ? yes : no;
1065 case E_LTH:
1066 return res < 0 ? yes : no;
1067 case E_UNEQUAL:
1068 return res ? yes : no;
1069 default:
1070 printf("expr_calc_value: relation %d?\n", e->type);
1071 return no;
1072 }
1073 }
1074
expr_compare_type(enum expr_type t1,enum expr_type t2)1075 static int expr_compare_type(enum expr_type t1, enum expr_type t2)
1076 {
1077 if (t1 == t2)
1078 return 0;
1079 switch (t1) {
1080 case E_LEQ:
1081 case E_LTH:
1082 case E_GEQ:
1083 case E_GTH:
1084 if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1085 return 1;
1086 case E_EQUAL:
1087 case E_UNEQUAL:
1088 if (t2 == E_NOT)
1089 return 1;
1090 case E_NOT:
1091 if (t2 == E_AND)
1092 return 1;
1093 case E_AND:
1094 if (t2 == E_OR)
1095 return 1;
1096 case E_OR:
1097 if (t2 == E_LIST)
1098 return 1;
1099 case E_LIST:
1100 if (t2 == 0)
1101 return 1;
1102 default:
1103 return -1;
1104 }
1105 printf("[%dgt%d?]", t1, t2);
1106 return 0;
1107 }
1108
expr_print(struct expr * e,void (* fn)(void *,struct symbol *,const char *),void * data,int prevtoken)1109 void expr_print(struct expr *e,
1110 void (*fn)(void *, struct symbol *, const char *),
1111 void *data, int prevtoken)
1112 {
1113 if (!e) {
1114 fn(data, NULL, "y");
1115 return;
1116 }
1117
1118 if (expr_compare_type(prevtoken, e->type) > 0)
1119 fn(data, NULL, "(");
1120 switch (e->type) {
1121 case E_SYMBOL:
1122 if (e->left.sym->name)
1123 fn(data, e->left.sym, e->left.sym->name);
1124 else
1125 fn(data, NULL, "<choice>");
1126 break;
1127 case E_NOT:
1128 fn(data, NULL, "!");
1129 expr_print(e->left.expr, fn, data, E_NOT);
1130 break;
1131 case E_EQUAL:
1132 if (e->left.sym->name)
1133 fn(data, e->left.sym, e->left.sym->name);
1134 else
1135 fn(data, NULL, "<choice>");
1136 fn(data, NULL, "=");
1137 fn(data, e->right.sym, e->right.sym->name);
1138 break;
1139 case E_LEQ:
1140 case E_LTH:
1141 if (e->left.sym->name)
1142 fn(data, e->left.sym, e->left.sym->name);
1143 else
1144 fn(data, NULL, "<choice>");
1145 fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1146 fn(data, e->right.sym, e->right.sym->name);
1147 break;
1148 case E_GEQ:
1149 case E_GTH:
1150 if (e->left.sym->name)
1151 fn(data, e->left.sym, e->left.sym->name);
1152 else
1153 fn(data, NULL, "<choice>");
1154 fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1155 fn(data, e->right.sym, e->right.sym->name);
1156 break;
1157 case E_UNEQUAL:
1158 if (e->left.sym->name)
1159 fn(data, e->left.sym, e->left.sym->name);
1160 else
1161 fn(data, NULL, "<choice>");
1162 fn(data, NULL, "!=");
1163 fn(data, e->right.sym, e->right.sym->name);
1164 break;
1165 case E_OR:
1166 expr_print(e->left.expr, fn, data, E_OR);
1167 fn(data, NULL, " || ");
1168 expr_print(e->right.expr, fn, data, E_OR);
1169 break;
1170 case E_AND:
1171 expr_print(e->left.expr, fn, data, E_AND);
1172 fn(data, NULL, " && ");
1173 expr_print(e->right.expr, fn, data, E_AND);
1174 break;
1175 case E_LIST:
1176 fn(data, e->right.sym, e->right.sym->name);
1177 if (e->left.expr) {
1178 fn(data, NULL, " ^ ");
1179 expr_print(e->left.expr, fn, data, E_LIST);
1180 }
1181 break;
1182 case E_RANGE:
1183 fn(data, NULL, "[");
1184 fn(data, e->left.sym, e->left.sym->name);
1185 fn(data, NULL, " ");
1186 fn(data, e->right.sym, e->right.sym->name);
1187 fn(data, NULL, "]");
1188 break;
1189 default:
1190 {
1191 char buf[32];
1192 sprintf(buf, "<unknown type %d>", e->type);
1193 fn(data, NULL, buf);
1194 break;
1195 }
1196 }
1197 if (expr_compare_type(prevtoken, e->type) > 0)
1198 fn(data, NULL, ")");
1199 }
1200
expr_print_file_helper(void * data,struct symbol * sym,const char * str)1201 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1202 {
1203 xfwrite(str, strlen(str), 1, data);
1204 }
1205
expr_fprint(struct expr * e,FILE * out)1206 void expr_fprint(struct expr *e, FILE *out)
1207 {
1208 expr_print(e, expr_print_file_helper, out, E_NONE);
1209 }
1210
expr_print_gstr_helper(void * data,struct symbol * sym,const char * str)1211 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1212 {
1213 struct gstr *gs = (struct gstr*)data;
1214 const char *sym_str = NULL;
1215
1216 if (sym)
1217 sym_str = sym_get_string_value(sym);
1218
1219 if (gs->max_width) {
1220 unsigned extra_length = strlen(str);
1221 const char *last_cr = strrchr(gs->s, '\n');
1222 unsigned last_line_length;
1223
1224 if (sym_str)
1225 extra_length += 4 + strlen(sym_str);
1226
1227 if (!last_cr)
1228 last_cr = gs->s;
1229
1230 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1231
1232 if ((last_line_length + extra_length) > gs->max_width)
1233 str_append(gs, "\\\n");
1234 }
1235
1236 str_append(gs, str);
1237 if (sym && sym->type != S_UNKNOWN)
1238 str_printf(gs, " [=%s]", sym_str);
1239 }
1240
expr_gstr_print(struct expr * e,struct gstr * gs)1241 void expr_gstr_print(struct expr *e, struct gstr *gs)
1242 {
1243 expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1244 }
1245
1246 /*
1247 * Transform the top level "||" tokens into newlines and prepend each
1248 * line with a minus. This makes expressions much easier to read.
1249 * Suitable for reverse dependency expressions.
1250 */
expr_print_revdep(struct expr * e,void (* fn)(void *,struct symbol *,const char *),void * data,tristate pr_type,const char ** title)1251 static void expr_print_revdep(struct expr *e,
1252 void (*fn)(void *, struct symbol *, const char *),
1253 void *data, tristate pr_type, const char **title)
1254 {
1255 if (e->type == E_OR) {
1256 expr_print_revdep(e->left.expr, fn, data, pr_type, title);
1257 expr_print_revdep(e->right.expr, fn, data, pr_type, title);
1258 } else if (expr_calc_value(e) == pr_type) {
1259 if (*title) {
1260 fn(data, NULL, *title);
1261 *title = NULL;
1262 }
1263
1264 fn(data, NULL, " - ");
1265 expr_print(e, fn, data, E_NONE);
1266 fn(data, NULL, "\n");
1267 }
1268 }
1269
expr_gstr_print_revdep(struct expr * e,struct gstr * gs,tristate pr_type,const char * title)1270 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs,
1271 tristate pr_type, const char *title)
1272 {
1273 expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title);
1274 }
1275