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