projects/linux·blob v2.6.37 · refs

1131 lines · 25.8 KiB

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