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