projects/linux·blob v3.12-rc1 · refs

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