![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to expr.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Qemu by Fabrice Bellard] / qemu / roms / seabios / tools / kconfig|
Return to expr.c CVS log | Up to [Qemu by Fabrice Bellard] / qemu / roms / seabios / tools / kconfig |
1.1 root 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:
15: struct 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:
24: struct 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:
33: struct 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:
43: struct 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:
53: struct 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:
60: struct 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:
67: struct expr *expr_copy(const 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:
104: void 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:
130: static int trans_count;
131:
132: #define e1 (*ep1)
133: #define e2 (*ep2)
134:
135: static 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:
169: void 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:
194: int 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:
236: struct 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: */
322: struct 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: */
351: static 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:
415: static 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:
509: static 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:
561: static 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:
617: struct 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:
641: struct 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:
778: int 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:
802: bool 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:
831: struct 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:
842: struct 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:
853: void 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:
882: struct 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:
943: tristate 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:
984: int 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:
1016: static inline struct expr *
1017: expr_get_leftmost_symbol(const struct expr *e)
1018: {
1019:
1020: if (e == NULL)
1021: return NULL;
1022:
1023: while (e->type != E_SYMBOL)
1024: e = e->left.expr;
1025:
1026: return expr_copy(e);
1027: }
1028:
1029: /*
1030: * Given expression `e1' and `e2', returns the leaf of the longest
1031: * sub-expression of `e1' not containing 'e2.
1032: */
1033: struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
1034: {
1035: struct expr *ret;
1036:
1037: switch (e1->type) {
1038: case E_OR:
1039: return expr_alloc_and(
1040: expr_simplify_unmet_dep(e1->left.expr, e2),
1041: expr_simplify_unmet_dep(e1->right.expr, e2));
1042: case E_AND: {
1043: struct expr *e;
1044: e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
1045: e = expr_eliminate_dups(e);
1046: ret = (!expr_eq(e, e1)) ? e1 : NULL;
1047: expr_free(e);
1048: break;
1049: }
1050: default:
1051: ret = e1;
1052: break;
1053: }
1054:
1055: return expr_get_leftmost_symbol(ret);
1056: }
1057:
1058: void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1059: {
1060: if (!e) {
1061: fn(data, NULL, "y");
1062: return;
1063: }
1064:
1065: if (expr_compare_type(prevtoken, e->type) > 0)
1066: fn(data, NULL, "(");
1067: switch (e->type) {
1068: case E_SYMBOL:
1069: if (e->left.sym->name)
1070: fn(data, e->left.sym, e->left.sym->name);
1071: else
1072: fn(data, NULL, "<choice>");
1073: break;
1074: case E_NOT:
1075: fn(data, NULL, "!");
1076: expr_print(e->left.expr, fn, data, E_NOT);
1077: break;
1078: case E_EQUAL:
1079: if (e->left.sym->name)
1080: fn(data, e->left.sym, e->left.sym->name);
1081: else
1082: fn(data, NULL, "<choice>");
1083: fn(data, NULL, "=");
1084: fn(data, e->right.sym, e->right.sym->name);
1085: break;
1086: case E_UNEQUAL:
1087: if (e->left.sym->name)
1088: fn(data, e->left.sym, e->left.sym->name);
1089: else
1090: fn(data, NULL, "<choice>");
1091: fn(data, NULL, "!=");
1092: fn(data, e->right.sym, e->right.sym->name);
1093: break;
1094: case E_OR:
1095: expr_print(e->left.expr, fn, data, E_OR);
1096: fn(data, NULL, " || ");
1097: expr_print(e->right.expr, fn, data, E_OR);
1098: break;
1099: case E_AND:
1100: expr_print(e->left.expr, fn, data, E_AND);
1101: fn(data, NULL, " && ");
1102: expr_print(e->right.expr, fn, data, E_AND);
1103: break;
1104: case E_LIST:
1105: fn(data, e->right.sym, e->right.sym->name);
1106: if (e->left.expr) {
1107: fn(data, NULL, " ^ ");
1108: expr_print(e->left.expr, fn, data, E_LIST);
1109: }
1110: break;
1111: case E_RANGE:
1112: fn(data, NULL, "[");
1113: fn(data, e->left.sym, e->left.sym->name);
1114: fn(data, NULL, " ");
1115: fn(data, e->right.sym, e->right.sym->name);
1116: fn(data, NULL, "]");
1117: break;
1118: default:
1119: {
1120: char buf[32];
1121: sprintf(buf, "<unknown type %d>", e->type);
1122: fn(data, NULL, buf);
1123: break;
1124: }
1125: }
1126: if (expr_compare_type(prevtoken, e->type) > 0)
1127: fn(data, NULL, ")");
1128: }
1129:
1130: static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1131: {
1132: xfwrite(str, strlen(str), 1, data);
1133: }
1134:
1135: void expr_fprint(struct expr *e, FILE *out)
1136: {
1137: expr_print(e, expr_print_file_helper, out, E_NONE);
1138: }
1139:
1140: static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1141: {
1142: struct gstr *gs = (struct gstr*)data;
1143: const char *sym_str = NULL;
1144:
1145: if (sym)
1146: sym_str = sym_get_string_value(sym);
1147:
1148: if (gs->max_width) {
1149: unsigned extra_length = strlen(str);
1150: const char *last_cr = strrchr(gs->s, '\n');
1151: unsigned last_line_length;
1152:
1153: if (sym_str)
1154: extra_length += 4 + strlen(sym_str);
1155:
1156: if (!last_cr)
1157: last_cr = gs->s;
1158:
1159: last_line_length = strlen(gs->s) - (last_cr - gs->s);
1160:
1161: if ((last_line_length + extra_length) > gs->max_width)
1162: str_append(gs, "\\\n");
1163: }
1164:
1165: str_append(gs, str);
1166: if (sym && sym->type != S_UNKNOWN)
1167: str_printf(gs, " [=%s]", sym_str);
1168: }
1169:
1170: void expr_gstr_print(struct expr *e, struct gstr *gs)
1171: {
1172: expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1173: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.