source: menu/expr.c@ ba72197

experimental
Last change on this file since ba72197 was 613d46b, checked in by George Boudreau <georgeb@…>, 18 years ago

Added new configuration tool.. <make> menuconfig. Needs work, especially inline help text
  • Property mode set to 100644
File size: 24.9 KB
Line 
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#define LKC_DIRECT_LINK
11#include "lkc.h"
12
13#define DEBUG_EXPR 0
14
15struct expr *expr_alloc_symbol(struct symbol *sym)
16{
17 struct expr *e = malloc(sizeof(*e));
18 memset(e, 0, sizeof(*e));
19 e->type = E_SYMBOL;
20 e->left.sym = sym;
21 return e;
22}
23
24struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
25{
26 struct expr *e = malloc(sizeof(*e));
27 memset(e, 0, sizeof(*e));
28 e->type = type;
29 e->left.expr = ce;
30 return e;
31}
32
33struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
34{
35 struct expr *e = malloc(sizeof(*e));
36 memset(e, 0, sizeof(*e));
37 e->type = type;
38 e->left.expr = e1;
39 e->right.expr = e2;
40 return e;
41}
42
43struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
44{
45 struct expr *e = malloc(sizeof(*e));
46 memset(e, 0, sizeof(*e));
47 e->type = type;
48 e->left.sym = s1;
49 e->right.sym = s2;
50 return e;
51}
52
53struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
54{
55 if (!e1)
56 return e2;
57 return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
58}
59
60struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
61{
62 if (!e1)
63 return e2;
64 return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
65}
66
67struct expr *expr_copy(struct expr *org)
68{
69 struct expr *e;
70
71 if (!org)
72 return NULL;
73
74 e = malloc(sizeof(*org));
75 memcpy(e, org, sizeof(*org));
76 switch (org->type) {
77 case E_SYMBOL:
78 e->left = org->left;
79 break;
80 case E_NOT:
81 e->left.expr = expr_copy(org->left.expr);
82 break;
83 case E_EQUAL:
84 case E_UNEQUAL:
85 e->left.sym = org->left.sym;
86 e->right.sym = org->right.sym;
87 break;
88 case E_AND:
89 case E_OR:
90 case E_CHOICE:
91 e->left.expr = expr_copy(org->left.expr);
92 e->right.expr = expr_copy(org->right.expr);
93 break;
94 default:
95 printf("can't copy type %d\n", e->type);
96 free(e);
97 e = NULL;
98 break;
99 }
100
101 return e;
102}
103
104void expr_free(struct expr *e)
105{
106 if (!e)
107 return;
108
109 switch (e->type) {
110 case E_SYMBOL:
111 break;
112 case E_NOT:
113 expr_free(e->left.expr);
114 return;
115 case E_EQUAL:
116 case E_UNEQUAL:
117 break;
118 case E_OR:
119 case E_AND:
120 expr_free(e->left.expr);
121 expr_free(e->right.expr);
122 break;
123 default:
124 printf("how to free type %d?\n", e->type);
125 break;
126 }
127 free(e);
128}
129
130static int trans_count;
131
132#define e1 (*ep1)
133#define e2 (*ep2)
134
135static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
136{
137 if (e1->type == type) {
138 __expr_eliminate_eq(type, &e1->left.expr, &e2);
139 __expr_eliminate_eq(type, &e1->right.expr, &e2);
140 return;
141 }
142 if (e2->type == type) {
143 __expr_eliminate_eq(type, &e1, &e2->left.expr);
144 __expr_eliminate_eq(type, &e1, &e2->right.expr);
145 return;
146 }
147 if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
148 e1->left.sym == e2->left.sym && (e1->left.sym->flags & (SYMBOL_YES|SYMBOL_NO)))
149 return;
150 if (!expr_eq(e1, e2))
151 return;
152 trans_count++;
153 expr_free(e1); expr_free(e2);
154 switch (type) {
155 case E_OR:
156 e1 = expr_alloc_symbol(&symbol_no);
157 e2 = expr_alloc_symbol(&symbol_no);
158 break;
159 case E_AND:
160 e1 = expr_alloc_symbol(&symbol_yes);
161 e2 = expr_alloc_symbol(&symbol_yes);
162 break;
163 default:
164 ;
165 }
166}
167
168void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
169{
170 if (!e1 || !e2)
171 return;
172 switch (e1->type) {
173 case E_OR:
174 case E_AND:
175 __expr_eliminate_eq(e1->type, ep1, ep2);
176 default:
177 ;
178 }
179 if (e1->type != e2->type) switch (e2->type) {
180 case E_OR:
181 case E_AND:
182 __expr_eliminate_eq(e2->type, ep1, ep2);
183 default:
184 ;
185 }
186 e1 = expr_eliminate_yn(e1);
187 e2 = expr_eliminate_yn(e2);
188}
189
190#undef e1
191#undef e2
192
193int expr_eq(struct expr *e1, struct expr *e2)
194{
195 int res, old_count;
196
197 if (e1->type != e2->type)
198 return 0;
199 switch (e1->type) {
200 case E_EQUAL:
201 case E_UNEQUAL:
202 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
203 case E_SYMBOL:
204 return e1->left.sym == e2->left.sym;
205 case E_NOT:
206 return expr_eq(e1->left.expr, e2->left.expr);
207 case E_AND:
208 case E_OR:
209 e1 = expr_copy(e1);
210 e2 = expr_copy(e2);
211 old_count = trans_count;
212 expr_eliminate_eq(&e1, &e2);
213 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
214 e1->left.sym == e2->left.sym);
215 expr_free(e1);
216 expr_free(e2);
217 trans_count = old_count;
218 return res;
219 case E_CHOICE:
220 case E_RANGE:
221 case E_NONE:
222 /* panic */;
223 }
224
225 if (DEBUG_EXPR) {
226 expr_fprint(e1, stdout);
227 printf(" = ");
228 expr_fprint(e2, stdout);
229 printf(" ?\n");
230 }
231
232 return 0;
233}
234
235struct expr *expr_eliminate_yn(struct expr *e)
236{
237 struct expr *tmp;
238
239 if (e) switch (e->type) {
240 case E_AND:
241 e->left.expr = expr_eliminate_yn(e->left.expr);
242 e->right.expr = expr_eliminate_yn(e->right.expr);
243 if (e->left.expr->type == E_SYMBOL) {
244 if (e->left.expr->left.sym == &symbol_no) {
245 expr_free(e->left.expr);
246 expr_free(e->right.expr);
247 e->type = E_SYMBOL;
248 e->left.sym = &symbol_no;
249 e->right.expr = NULL;
250 return e;
251 } else if (e->left.expr->left.sym == &symbol_yes) {
252 free(e->left.expr);
253 tmp = e->right.expr;
254 *e = *(e->right.expr);
255 free(tmp);
256 return e;
257 }
258 }
259 if (e->right.expr->type == E_SYMBOL) {
260 if (e->right.expr->left.sym == &symbol_no) {
261 expr_free(e->left.expr);
262 expr_free(e->right.expr);
263 e->type = E_SYMBOL;
264 e->left.sym = &symbol_no;
265 e->right.expr = NULL;
266 return e;
267 } else if (e->right.expr->left.sym == &symbol_yes) {
268 free(e->right.expr);
269 tmp = e->left.expr;
270 *e = *(e->left.expr);
271 free(tmp);
272 return e;
273 }
274 }
275 break;
276 case E_OR:
277 e->left.expr = expr_eliminate_yn(e->left.expr);
278 e->right.expr = expr_eliminate_yn(e->right.expr);
279 if (e->left.expr->type == E_SYMBOL) {
280 if (e->left.expr->left.sym == &symbol_no) {
281 free(e->left.expr);
282 tmp = e->right.expr;
283 *e = *(e->right.expr);
284 free(tmp);
285 return e;
286 } else if (e->left.expr->left.sym == &symbol_yes) {
287 expr_free(e->left.expr);
288 expr_free(e->right.expr);
289 e->type = E_SYMBOL;
290 e->left.sym = &symbol_yes;
291 e->right.expr = NULL;
292 return e;
293 }
294 }
295 if (e->right.expr->type == E_SYMBOL) {
296 if (e->right.expr->left.sym == &symbol_no) {
297 free(e->right.expr);
298 tmp = e->left.expr;
299 *e = *(e->left.expr);
300 free(tmp);
301 return e;
302 } else if (e->right.expr->left.sym == &symbol_yes) {
303 expr_free(e->left.expr);
304 expr_free(e->right.expr);
305 e->type = E_SYMBOL;
306 e->left.sym = &symbol_yes;
307 e->right.expr = NULL;
308 return e;
309 }
310 }
311 break;
312 default:
313 ;
314 }
315 return e;
316}
317
318/*
319 * bool FOO!=n => FOO
320 */
321struct expr *expr_trans_bool(struct expr *e)
322{
323 if (!e)
324 return NULL;
325 switch (e->type) {
326 case E_AND:
327 case E_OR:
328 case E_NOT:
329 e->left.expr = expr_trans_bool(e->left.expr);
330 e->right.expr = expr_trans_bool(e->right.expr);
331 break;
332 case E_UNEQUAL:
333 // FOO!=n -> FOO
334 if (e->left.sym->type == S_TRISTATE) {
335 if (e->right.sym == &symbol_no) {
336 e->type = E_SYMBOL;
337 e->right.sym = NULL;
338 }
339 }
340 break;
341 default:
342 ;
343 }
344 return e;
345}
346
347/*
348 * e1 || e2 -> ?
349 */
350struct expr *expr_join_or(struct expr *e1, struct expr *e2)
351{
352 struct expr *tmp;
353 struct symbol *sym1, *sym2;
354
355 if (expr_eq(e1, e2))
356 return expr_copy(e1);
357 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
358 return NULL;
359 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
360 return NULL;
361 if (e1->type == E_NOT) {
362 tmp = e1->left.expr;
363 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
364 return NULL;
365 sym1 = tmp->left.sym;
366 } else
367 sym1 = e1->left.sym;
368 if (e2->type == E_NOT) {
369 if (e2->left.expr->type != E_SYMBOL)
370 return NULL;
371 sym2 = e2->left.expr->left.sym;
372 } else
373 sym2 = e2->left.sym;
374 if (sym1 != sym2)
375 return NULL;
376 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
377 return NULL;
378 if (sym1->type == S_TRISTATE) {
379 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
380 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
381 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
382 // (a='y') || (a='m') -> (a!='n')
383 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
384 }
385 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
386 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
387 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
388 // (a='y') || (a='n') -> (a!='m')
389 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
390 }
391 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
392 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
393 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
394 // (a='m') || (a='n') -> (a!='y')
395 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
396 }
397 }
398 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
399 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
400 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
401 return expr_alloc_symbol(&symbol_yes);
402 }
403
404 if (DEBUG_EXPR) {
405 printf("optimize (");
406 expr_fprint(e1, stdout);
407 printf(") || (");
408 expr_fprint(e2, stdout);
409 printf(")?\n");
410 }
411 return NULL;
412}
413
414struct expr *expr_join_and(struct expr *e1, struct expr *e2)
415{
416 struct expr *tmp;
417 struct symbol *sym1, *sym2;
418
419 if (expr_eq(e1, e2))
420 return expr_copy(e1);
421 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
422 return NULL;
423 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
424 return NULL;
425 if (e1->type == E_NOT) {
426 tmp = e1->left.expr;
427 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
428 return NULL;
429 sym1 = tmp->left.sym;
430 } else
431 sym1 = e1->left.sym;
432 if (e2->type == E_NOT) {
433 if (e2->left.expr->type != E_SYMBOL)
434 return NULL;
435 sym2 = e2->left.expr->left.sym;
436 } else
437 sym2 = e2->left.sym;
438 if (sym1 != sym2)
439 return NULL;
440 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
441 return NULL;
442
443 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
444 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
445 // (a) && (a='y') -> (a='y')
446 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
447
448 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
449 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
450 // (a) && (a!='n') -> (a)
451 return expr_alloc_symbol(sym1);
452
453 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
454 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
455 // (a) && (a!='m') -> (a='y')
456 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
457
458 if (sym1->type == S_TRISTATE) {
459 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
460 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
461 sym2 = e1->right.sym;
462 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
463 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
464 : expr_alloc_symbol(&symbol_no);
465 }
466 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
467 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
468 sym2 = e2->right.sym;
469 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
470 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
471 : expr_alloc_symbol(&symbol_no);
472 }
473 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
474 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
475 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
476 // (a!='y') && (a!='n') -> (a='m')
477 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
478
479 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
480 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
481 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
482 // (a!='y') && (a!='m') -> (a='n')
483 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
484
485 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
486 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
487 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
488 // (a!='m') && (a!='n') -> (a='m')
489 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
490
491 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
492 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
493 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
494 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
495 return NULL;
496 }
497
498 if (DEBUG_EXPR) {
499 printf("optimize (");
500 expr_fprint(e1, stdout);
501 printf(") && (");
502 expr_fprint(e2, stdout);
503 printf(")?\n");
504 }
505 return NULL;
506}
507
508static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
509{
510#define e1 (*ep1)
511#define e2 (*ep2)
512 struct expr *tmp;
513
514 if (e1->type == type) {
515 expr_eliminate_dups1(type, &e1->left.expr, &e2);
516 expr_eliminate_dups1(type, &e1->right.expr, &e2);
517 return;
518 }
519 if (e2->type == type) {
520 expr_eliminate_dups1(type, &e1, &e2->left.expr);
521 expr_eliminate_dups1(type, &e1, &e2->right.expr);
522 return;
523 }
524 if (e1 == e2)
525 return;
526
527 switch (e1->type) {
528 case E_OR: case E_AND:
529 expr_eliminate_dups1(e1->type, &e1, &e1);
530 default:
531 ;
532 }
533
534 switch (type) {
535 case E_OR:
536 tmp = expr_join_or(e1, e2);
537 if (tmp) {
538 expr_free(e1); expr_free(e2);
539 e1 = expr_alloc_symbol(&symbol_no);
540 e2 = tmp;
541 trans_count++;
542 }
543 break;
544 case E_AND:
545 tmp = expr_join_and(e1, e2);
546 if (tmp) {
547 expr_free(e1); expr_free(e2);
548 e1 = expr_alloc_symbol(&symbol_yes);
549 e2 = tmp;
550 trans_count++;
551 }
552 break;
553 default:
554 ;
555 }
556#undef e1
557#undef e2
558}
559
560static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
561{
562#define e1 (*ep1)
563#define e2 (*ep2)
564 struct expr *tmp, *tmp1, *tmp2;
565
566 if (e1->type == type) {
567 expr_eliminate_dups2(type, &e1->left.expr, &e2);
568 expr_eliminate_dups2(type, &e1->right.expr, &e2);
569 return;
570 }
571 if (e2->type == type) {
572 expr_eliminate_dups2(type, &e1, &e2->left.expr);
573 expr_eliminate_dups2(type, &e1, &e2->right.expr);
574 }
575 if (e1 == e2)
576 return;
577
578 switch (e1->type) {
579 case E_OR:
580 expr_eliminate_dups2(e1->type, &e1, &e1);
581 // (FOO || BAR) && (!FOO && !BAR) -> n
582 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
583 tmp2 = expr_copy(e2);
584 tmp = expr_extract_eq_and(&tmp1, &tmp2);
585 if (expr_is_yes(tmp1)) {
586 expr_free(e1);
587 e1 = expr_alloc_symbol(&symbol_no);
588 trans_count++;
589 }
590 expr_free(tmp2);
591 expr_free(tmp1);
592 expr_free(tmp);
593 break;
594 case E_AND:
595 expr_eliminate_dups2(e1->type, &e1, &e1);
596 // (FOO && BAR) || (!FOO || !BAR) -> y
597 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
598 tmp2 = expr_copy(e2);
599 tmp = expr_extract_eq_or(&tmp1, &tmp2);
600 if (expr_is_no(tmp1)) {
601 expr_free(e1);
602 e1 = expr_alloc_symbol(&symbol_yes);
603 trans_count++;
604 }
605 expr_free(tmp2);
606 expr_free(tmp1);
607 expr_free(tmp);
608 break;
609 default:
610 ;
611 }
612#undef e1
613#undef e2
614}
615
616struct expr *expr_eliminate_dups(struct expr *e)
617{
618 int oldcount;
619 if (!e)
620 return e;
621
622 oldcount = trans_count;
623 while (1) {
624 trans_count = 0;
625 switch (e->type) {
626 case E_OR: case E_AND:
627 expr_eliminate_dups1(e->type, &e, &e);
628 expr_eliminate_dups2(e->type, &e, &e);
629 default:
630 ;
631 }
632 if (!trans_count)
633 break;
634 e = expr_eliminate_yn(e);
635 }
636 trans_count = oldcount;
637 return e;
638}
639
640struct expr *expr_transform(struct expr *e)
641{
642 struct expr *tmp;
643
644 if (!e)
645 return NULL;
646 switch (e->type) {
647 case E_EQUAL:
648 case E_UNEQUAL:
649 case E_SYMBOL:
650 case E_CHOICE:
651 break;
652 default:
653 e->left.expr = expr_transform(e->left.expr);
654 e->right.expr = expr_transform(e->right.expr);
655 }
656
657 switch (e->type) {
658 case E_EQUAL:
659 if (e->left.sym->type != S_BOOLEAN)
660 break;
661 if (e->right.sym == &symbol_no) {
662 e->type = E_NOT;
663 e->left.expr = expr_alloc_symbol(e->left.sym);
664 e->right.sym = NULL;
665 break;
666 }
667 if (e->right.sym == &symbol_mod) {
668 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
669 e->type = E_SYMBOL;
670 e->left.sym = &symbol_no;
671 e->right.sym = NULL;
672 break;
673 }
674 if (e->right.sym == &symbol_yes) {
675 e->type = E_SYMBOL;
676 e->right.sym = NULL;
677 break;
678 }
679 break;
680 case E_UNEQUAL:
681 if (e->left.sym->type != S_BOOLEAN)
682 break;
683 if (e->right.sym == &symbol_no) {
684 e->type = E_SYMBOL;
685 e->right.sym = NULL;
686 break;
687 }
688 if (e->right.sym == &symbol_mod) {
689 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
690 e->type = E_SYMBOL;
691 e->left.sym = &symbol_yes;
692 e->right.sym = NULL;
693 break;
694 }
695 if (e->right.sym == &symbol_yes) {
696 e->type = E_NOT;
697 e->left.expr = expr_alloc_symbol(e->left.sym);
698 e->right.sym = NULL;
699 break;
700 }
701 break;
702 case E_NOT:
703 switch (e->left.expr->type) {
704 case E_NOT:
705 // !!a -> a
706 tmp = e->left.expr->left.expr;
707 free(e->left.expr);
708 free(e);
709 e = tmp;
710 e = expr_transform(e);
711 break;
712 case E_EQUAL:
713 case E_UNEQUAL:
714 // !a='x' -> a!='x'
715 tmp = e->left.expr;
716 free(e);
717 e = tmp;
718 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
719 break;
720 case E_OR:
721 // !(a || b) -> !a && !b
722 tmp = e->left.expr;
723 e->type = E_AND;
724 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
725 tmp->type = E_NOT;
726 tmp->right.expr = NULL;
727 e = expr_transform(e);
728 break;
729 case E_AND:
730 // !(a && b) -> !a || !b
731 tmp = e->left.expr;
732 e->type = E_OR;
733 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
734 tmp->type = E_NOT;
735 tmp->right.expr = NULL;
736 e = expr_transform(e);
737 break;
738 case E_SYMBOL:
739 if (e->left.expr->left.sym == &symbol_yes) {
740 // !'y' -> 'n'
741 tmp = e->left.expr;
742 free(e);
743 e = tmp;
744 e->type = E_SYMBOL;
745 e->left.sym = &symbol_no;
746 break;
747 }
748 if (e->left.expr->left.sym == &symbol_mod) {
749 // !'m' -> 'm'
750 tmp = e->left.expr;
751 free(e);
752 e = tmp;
753 e->type = E_SYMBOL;
754 e->left.sym = &symbol_mod;
755 break;
756 }
757 if (e->left.expr->left.sym == &symbol_no) {
758 // !'n' -> 'y'
759 tmp = e->left.expr;
760 free(e);
761 e = tmp;
762 e->type = E_SYMBOL;
763 e->left.sym = &symbol_yes;
764 break;
765 }
766 break;
767 default:
768 ;
769 }
770 break;
771 default:
772 ;
773 }
774 return e;
775}
776
777int expr_contains_symbol(struct expr *dep, struct symbol *sym)
778{
779 if (!dep)
780 return 0;
781
782 switch (dep->type) {
783 case E_AND:
784 case E_OR:
785 return expr_contains_symbol(dep->left.expr, sym) ||
786 expr_contains_symbol(dep->right.expr, sym);
787 case E_SYMBOL:
788 return dep->left.sym == sym;
789 case E_EQUAL:
790 case E_UNEQUAL:
791 return dep->left.sym == sym ||
792 dep->right.sym == sym;
793 case E_NOT:
794 return expr_contains_symbol(dep->left.expr, sym);
795 default:
796 ;
797 }
798 return 0;
799}
800
801bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
802{
803 if (!dep)
804 return false;
805
806 switch (dep->type) {
807 case E_AND:
808 return expr_depends_symbol(dep->left.expr, sym) ||
809 expr_depends_symbol(dep->right.expr, sym);
810 case E_SYMBOL:
811 return dep->left.sym == sym;
812 case E_EQUAL:
813 if (dep->left.sym == sym) {
814 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
815 return true;
816 }
817 break;
818 case E_UNEQUAL:
819 if (dep->left.sym == sym) {
820 if (dep->right.sym == &symbol_no)
821 return true;
822 }
823 break;
824 default:
825 ;
826 }
827 return false;
828}
829
830struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
831{
832 struct expr *tmp = NULL;
833 expr_extract_eq(E_AND, &tmp, ep1, ep2);
834 if (tmp) {
835 *ep1 = expr_eliminate_yn(*ep1);
836 *ep2 = expr_eliminate_yn(*ep2);
837 }
838 return tmp;
839}
840
841struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
842{
843 struct expr *tmp = NULL;
844 expr_extract_eq(E_OR, &tmp, ep1, ep2);
845 if (tmp) {
846 *ep1 = expr_eliminate_yn(*ep1);
847 *ep2 = expr_eliminate_yn(*ep2);
848 }
849 return tmp;
850}
851
852void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
853{
854#define e1 (*ep1)
855#define e2 (*ep2)
856 if (e1->type == type) {
857 expr_extract_eq(type, ep, &e1->left.expr, &e2);
858 expr_extract_eq(type, ep, &e1->right.expr, &e2);
859 return;
860 }
861 if (e2->type == type) {
862 expr_extract_eq(type, ep, ep1, &e2->left.expr);
863 expr_extract_eq(type, ep, ep1, &e2->right.expr);
864 return;
865 }
866 if (expr_eq(e1, e2)) {
867 *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
868 expr_free(e2);
869 if (type == E_AND) {
870 e1 = expr_alloc_symbol(&symbol_yes);
871 e2 = expr_alloc_symbol(&symbol_yes);
872 } else if (type == E_OR) {
873 e1 = expr_alloc_symbol(&symbol_no);
874 e2 = expr_alloc_symbol(&symbol_no);
875 }
876 }
877#undef e1
878#undef e2
879}
880
881struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
882{
883 struct expr *e1, *e2;
884
885 if (!e) {
886 e = expr_alloc_symbol(sym);
887 if (type == E_UNEQUAL)
888 e = expr_alloc_one(E_NOT, e);
889 return e;
890 }
891 switch (e->type) {
892 case E_AND:
893 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
894 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
895 if (sym == &symbol_yes)
896 e = expr_alloc_two(E_AND, e1, e2);
897 if (sym == &symbol_no)
898 e = expr_alloc_two(E_OR, e1, e2);
899 if (type == E_UNEQUAL)
900 e = expr_alloc_one(E_NOT, e);
901 return e;
902 case E_OR:
903 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
904 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
905 if (sym == &symbol_yes)
906 e = expr_alloc_two(E_OR, e1, e2);
907 if (sym == &symbol_no)
908 e = expr_alloc_two(E_AND, e1, e2);
909 if (type == E_UNEQUAL)
910 e = expr_alloc_one(E_NOT, e);
911 return e;
912 case E_NOT:
913 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
914 case E_UNEQUAL:
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_CHOICE:
935 case E_RANGE:
936 case E_NONE:
937 /* panic */;
938 }
939 return NULL;
940}
941
942tristate expr_calc_value(struct expr *e)
943{
944 tristate val1, val2;
945 const char *str1, *str2;
946
947 if (!e)
948 return yes;
949
950 switch (e->type) {
951 case E_SYMBOL:
952 sym_calc_value(e->left.sym);
953 return e->left.sym->curr.tri;
954 case E_AND:
955 val1 = expr_calc_value(e->left.expr);
956 val2 = expr_calc_value(e->right.expr);
957 return E_AND(val1, val2);
958 case E_OR:
959 val1 = expr_calc_value(e->left.expr);
960 val2 = expr_calc_value(e->right.expr);
961 return E_OR(val1, val2);
962 case E_NOT:
963 val1 = expr_calc_value(e->left.expr);
964 return E_NOT(val1);
965 case E_EQUAL:
966 sym_calc_value(e->left.sym);
967 sym_calc_value(e->right.sym);
968 str1 = sym_get_string_value(e->left.sym);
969 str2 = sym_get_string_value(e->right.sym);
970 return !strcmp(str1, str2) ? yes : no;
971 case E_UNEQUAL:
972 sym_calc_value(e->left.sym);
973 sym_calc_value(e->right.sym);
974 str1 = sym_get_string_value(e->left.sym);
975 str2 = sym_get_string_value(e->right.sym);
976 return !strcmp(str1, str2) ? no : yes;
977 default:
978 printf("expr_calc_value: %d?\n", e->type);
979 return no;
980 }
981}
982
983int expr_compare_type(enum expr_type t1, enum expr_type t2)
984{
985#if 0
986 return 1;
987#else
988 if (t1 == t2)
989 return 0;
990 switch (t1) {
991 case E_EQUAL:
992 case E_UNEQUAL:
993 if (t2 == E_NOT)
994 return 1;
995 case E_NOT:
996 if (t2 == E_AND)
997 return 1;
998 case E_AND:
999 if (t2 == E_OR)
1000 return 1;
1001 case E_OR:
1002 if (t2 == E_CHOICE)
1003 return 1;
1004 case E_CHOICE:
1005 if (t2 == 0)
1006 return 1;
1007 default:
1008 return -1;
1009 }
1010 printf("[%dgt%d?]", t1, t2);
1011 return 0;
1012#endif
1013}
1014
1015void expr_print(struct expr *e, void (*fn)(void *, const char *), void *data, int prevtoken)
1016{
1017 if (!e) {
1018 fn(data, "y");
1019 return;
1020 }
1021
1022 if (expr_compare_type(prevtoken, e->type) > 0)
1023 fn(data, "(");
1024 switch (e->type) {
1025 case E_SYMBOL:
1026 if (e->left.sym->name)
1027 fn(data, e->left.sym->name);
1028 else
1029 fn(data, "<choice>");
1030 break;
1031 case E_NOT:
1032 fn(data, "!");
1033 expr_print(e->left.expr, fn, data, E_NOT);
1034 break;
1035 case E_EQUAL:
1036 fn(data, e->left.sym->name);
1037 fn(data, "=");
1038 fn(data, e->right.sym->name);
1039 break;
1040 case E_UNEQUAL:
1041 fn(data, e->left.sym->name);
1042 fn(data, "!=");
1043 fn(data, e->right.sym->name);
1044 break;
1045 case E_OR:
1046 expr_print(e->left.expr, fn, data, E_OR);
1047 fn(data, " || ");
1048 expr_print(e->right.expr, fn, data, E_OR);
1049 break;
1050 case E_AND:
1051 expr_print(e->left.expr, fn, data, E_AND);
1052 fn(data, " && ");
1053 expr_print(e->right.expr, fn, data, E_AND);
1054 break;
1055 case E_CHOICE:
1056 fn(data, e->right.sym->name);
1057 if (e->left.expr) {
1058 fn(data, " ^ ");
1059 expr_print(e->left.expr, fn, data, E_CHOICE);
1060 }
1061 break;
1062 case E_RANGE:
1063 fn(data, "[");
1064 fn(data, e->left.sym->name);
1065 fn(data, " ");
1066 fn(data, e->right.sym->name);
1067 fn(data, "]");
1068 break;
1069 default:
1070 {
1071 char buf[32];
1072 sprintf(buf, "<unknown type %d>", e->type);
1073 fn(data, buf);
1074 break;
1075 }
1076 }
1077 if (expr_compare_type(prevtoken, e->type) > 0)
1078 fn(data, ")");
1079}
1080
1081static void expr_print_file_helper(void *data, const char *str)
1082{
1083 fwrite(str, strlen(str), 1, data);
1084}
1085
1086void expr_fprint(struct expr *e, FILE *out)
1087{
1088 expr_print(e, expr_print_file_helper, out, E_NONE);
1089}
1090
1091static void expr_print_gstr_helper(void *data, const char *str)
1092{
1093 str_append((struct gstr*)data, str);
1094}
1095
1096void expr_gstr_print(struct expr *e, struct gstr *gs)
1097{
1098 expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1099}
Note: See TracBrowser for help on using the repository browser.