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