3f15ae859a5b291a657a8b2f00a6325250378710
[people/mcb30/busybox.git] / scripts / config / expr.c
1 /*
2  * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
3  * Released under the terms of the GNU GPL v2.0.
4  */
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10 #define LKC_DIRECT_LINK
11 #include "lkc.h"
12
13 struct 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
22 struct 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
31 struct 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
41 struct 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
51 struct 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
58 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
59 {
60         if (!e1)
61                 return e2;
62         return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
63 }
64
65 struct expr *expr_copy(struct expr *org)
66 {
67         struct expr *e;
68
69         if (!org)
70                 return NULL;
71
72         e = malloc(sizeof(*org));
73         memcpy(e, org, sizeof(*org));
74         switch (org->type) {
75         case E_SYMBOL:
76                 e->left = org->left;
77                 break;
78         case E_NOT:
79                 e->left.expr = expr_copy(org->left.expr);
80                 break;
81         case E_EQUAL:
82         case E_UNEQUAL:
83                 e->left.sym = org->left.sym;
84                 e->right.sym = org->right.sym;
85                 break;
86         case E_AND:
87         case E_OR:
88         case E_CHOICE:
89                 e->left.expr = expr_copy(org->left.expr);
90                 e->right.expr = expr_copy(org->right.expr);
91                 break;
92         default:
93                 printf("can't copy type %d\n", e->type);
94                 free(e);
95                 e = NULL;
96                 break;
97         }
98
99         return e;
100 }
101
102 void expr_free(struct expr *e)
103 {
104         if (!e)
105                 return;
106
107         switch (e->type) {
108         case E_SYMBOL:
109                 break;
110         case E_NOT:
111                 expr_free(e->left.expr);
112                 return;
113         case E_EQUAL:
114         case E_UNEQUAL:
115                 break;
116         case E_OR:
117         case E_AND:
118                 expr_free(e->left.expr);
119                 expr_free(e->right.expr);
120                 break;
121         default:
122                 printf("how to free type %d?\n", e->type);
123                 break;
124         }
125         free(e);
126 }
127
128 static int trans_count;
129
130 #define e1 (*ep1)
131 #define e2 (*ep2)
132
133 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
134 {
135         if (e1->type == type) {
136                 __expr_eliminate_eq(type, &e1->left.expr, &e2);
137                 __expr_eliminate_eq(type, &e1->right.expr, &e2);
138                 return;
139         }
140         if (e2->type == type) {
141                 __expr_eliminate_eq(type, &e1, &e2->left.expr);
142                 __expr_eliminate_eq(type, &e1, &e2->right.expr);
143                 return;
144         }
145         if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
146             e1->left.sym == e2->left.sym && (e1->left.sym->flags & (SYMBOL_YES|SYMBOL_NO)))
147                 return;
148         if (!expr_eq(e1, e2))
149                 return;
150         trans_count++;
151         expr_free(e1); expr_free(e2);
152         switch (type) {
153         case E_OR:
154                 e1 = expr_alloc_symbol(&symbol_no);
155                 e2 = expr_alloc_symbol(&symbol_no);
156                 break;
157         case E_AND:
158                 e1 = expr_alloc_symbol(&symbol_yes);
159                 e2 = expr_alloc_symbol(&symbol_yes);
160                 break;
161         default:
162                 ;
163         }
164 }
165
166 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
167 {
168         if (!e1 || !e2)
169                 return;
170         switch (e1->type) {
171         case E_OR:
172         case E_AND:
173                 __expr_eliminate_eq(e1->type, ep1, ep2);
174         default:
175                 ;
176         }
177         if (e1->type != e2->type) switch (e2->type) {
178         case E_OR:
179         case E_AND:
180                 __expr_eliminate_eq(e2->type, ep1, ep2);
181         default:
182                 ;
183         }
184         e1 = expr_eliminate_yn(e1);
185         e2 = expr_eliminate_yn(e2);
186 }
187
188 #undef e1
189 #undef e2
190
191 int expr_eq(struct expr *e1, struct expr *e2)
192 {
193         int res, old_count;
194
195         if (e1->type != e2->type)
196                 return 0;
197         switch (e1->type) {
198         case E_EQUAL:
199         case E_UNEQUAL:
200                 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
201         case E_SYMBOL:
202                 return e1->left.sym == e2->left.sym;
203         case E_NOT:
204                 return expr_eq(e1->left.expr, e2->left.expr);
205         case E_AND:
206         case E_OR:
207                 e1 = expr_copy(e1);
208                 e2 = expr_copy(e2);
209                 old_count = trans_count;
210                 expr_eliminate_eq(&e1, &e2);
211                 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
212                        e1->left.sym == e2->left.sym);
213                 expr_free(e1);
214                 expr_free(e2);
215                 trans_count = old_count;
216                 return res;
217         case E_CHOICE:
218         case E_RANGE:
219         case E_NONE:
220                 /* panic */;
221         }
222
223         print_expr(0, e1, 0);
224         printf(" = ");
225         print_expr(0, e2, 0);
226         printf(" ?\n");
227
228         return 0;
229 }
230
231 struct 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  */
317 struct 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  */
346 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         printf("optimize ");
401         print_expr(0, e1, 0);
402         printf(" || ");
403         print_expr(0, e2, 0);
404         printf(" ?\n");
405         return NULL;
406 }
407
408 struct expr *expr_join_and(struct expr *e1, struct expr *e2)
409 {
410         struct expr *tmp;
411         struct symbol *sym1, *sym2;
412
413         if (expr_eq(e1, e2))
414                 return expr_copy(e1);
415         if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
416                 return NULL;
417         if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
418                 return NULL;
419         if (e1->type == E_NOT) {
420                 tmp = e1->left.expr;
421                 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
422                         return NULL;
423                 sym1 = tmp->left.sym;
424         } else
425                 sym1 = e1->left.sym;
426         if (e2->type == E_NOT) {
427                 if (e2->left.expr->type != E_SYMBOL)
428                         return NULL;
429                 sym2 = e2->left.expr->left.sym;
430         } else
431                 sym2 = e2->left.sym;
432         if (sym1 != sym2)
433                 return NULL;
434         if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
435                 return NULL;
436
437         if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
438             (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
439                 // (a) && (a='y') -> (a='y')
440                 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
441
442         if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
443             (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
444                 // (a) && (a!='n') -> (a)
445                 return expr_alloc_symbol(sym1);
446
447         if (sym1->type == S_TRISTATE) {
448                 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
449                         // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
450                         sym2 = e1->right.sym;
451                         if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
452                                 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
453                                                              : expr_alloc_symbol(&symbol_no);
454                 }
455                 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
456                         // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
457                         sym2 = e2->right.sym;
458                         if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
459                                 return sym2 != e1->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_UNEQUAL &&
463                            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
464                             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
465                         // (a!='y') && (a!='n') -> (a='m')
466                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
467
468                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
469                            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
470                             (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
471                         // (a!='y') && (a!='m') -> (a='n')
472                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
473
474                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
475                            ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
476                             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
477                         // (a!='m') && (a!='n') -> (a='m')
478                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
479
480                 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
481                     (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
482                     (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
483                     (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
484                         return NULL;
485         }
486         printf("optimize ");
487         print_expr(0, e1, 0);
488         printf(" && ");
489         print_expr(0, e2, 0);
490         printf(" ?\n");
491         return NULL;
492 }
493
494 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
495 {
496 #define e1 (*ep1)
497 #define e2 (*ep2)
498         struct expr *tmp;
499
500         if (e1->type == type) {
501                 expr_eliminate_dups1(type, &e1->left.expr, &e2);
502                 expr_eliminate_dups1(type, &e1->right.expr, &e2);
503                 return;
504         }
505         if (e2->type == type) {
506                 expr_eliminate_dups1(type, &e1, &e2->left.expr);
507                 expr_eliminate_dups1(type, &e1, &e2->right.expr);
508                 return;
509         }
510         if (e1 == e2)
511                 return;
512
513         switch (e1->type) {
514         case E_OR: case E_AND:
515                 expr_eliminate_dups1(e1->type, &e1, &e1);
516         default:
517                 ;
518         }
519
520         switch (type) {
521         case E_OR:
522                 tmp = expr_join_or(e1, e2);
523                 if (tmp) {
524                         expr_free(e1); expr_free(e2);
525                         e1 = expr_alloc_symbol(&symbol_no);
526                         e2 = tmp;
527                         trans_count++;
528                 }
529                 break;
530         case E_AND:
531                 tmp = expr_join_and(e1, e2);
532                 if (tmp) {
533                         expr_free(e1); expr_free(e2);
534                         e1 = expr_alloc_symbol(&symbol_yes);
535                         e2 = tmp;
536                         trans_count++;
537                 }
538                 break;
539         default:
540                 ;
541         }
542 #undef e1
543 #undef e2
544 }
545
546 static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
547 {
548 #define e1 (*ep1)
549 #define e2 (*ep2)
550         struct expr *tmp, *tmp1, *tmp2;
551
552         if (e1->type == type) {
553                 expr_eliminate_dups2(type, &e1->left.expr, &e2);
554                 expr_eliminate_dups2(type, &e1->right.expr, &e2);
555                 return;
556         }
557         if (e2->type == type) {
558                 expr_eliminate_dups2(type, &e1, &e2->left.expr);
559                 expr_eliminate_dups2(type, &e1, &e2->right.expr);
560         }
561         if (e1 == e2)
562                 return;
563
564         switch (e1->type) {
565         case E_OR:
566                 expr_eliminate_dups2(e1->type, &e1, &e1);
567                 // (FOO || BAR) && (!FOO && !BAR) -> n
568                 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
569                 tmp2 = expr_copy(e2);
570                 tmp = expr_extract_eq_and(&tmp1, &tmp2);
571                 if (expr_is_yes(tmp1)) {
572                         expr_free(e1);
573                         e1 = expr_alloc_symbol(&symbol_no);
574                         trans_count++;
575                 }
576                 expr_free(tmp2);
577                 expr_free(tmp1);
578                 expr_free(tmp);
579                 break;
580         case E_AND:
581                 expr_eliminate_dups2(e1->type, &e1, &e1);
582                 // (FOO && BAR) || (!FOO || !BAR) -> y
583                 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
584                 tmp2 = expr_copy(e2);
585                 tmp = expr_extract_eq_or(&tmp1, &tmp2);
586                 if (expr_is_no(tmp1)) {
587                         expr_free(e1);
588                         e1 = expr_alloc_symbol(&symbol_yes);
589                         trans_count++;
590                 }
591                 expr_free(tmp2);
592                 expr_free(tmp1);
593                 expr_free(tmp);
594                 break;
595         default:
596                 ;
597         }
598 #undef e1
599 #undef e2
600 }
601
602 struct expr *expr_eliminate_dups(struct expr *e)
603 {
604         int oldcount;
605         if (!e)
606                 return e;
607
608         oldcount = trans_count;
609         while (1) {
610                 trans_count = 0;
611                 switch (e->type) {
612                 case E_OR: case E_AND:
613                         expr_eliminate_dups1(e->type, &e, &e);
614                         expr_eliminate_dups2(e->type, &e, &e);
615                 default:
616                         ;
617                 }
618                 if (!trans_count)
619                         break;
620                 e = expr_eliminate_yn(e);
621         }
622         trans_count = oldcount;
623         return e;
624 }
625
626 struct expr *expr_transform(struct expr *e)
627 {
628         struct expr *tmp;
629
630         if (!e)
631                 return NULL;
632         switch (e->type) {
633         case E_EQUAL:
634         case E_UNEQUAL:
635         case E_SYMBOL:
636         case E_CHOICE:
637                 break;
638         default:
639                 e->left.expr = expr_transform(e->left.expr);
640                 e->right.expr = expr_transform(e->right.expr);
641         }
642
643         switch (e->type) {
644         case E_EQUAL:
645                 if (e->left.sym->type != S_BOOLEAN)
646                         break;
647                 if (e->right.sym == &symbol_no) {
648                         e->type = E_NOT;
649                         e->left.expr = expr_alloc_symbol(e->left.sym);
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 'n'\n", e->left.sym->name);
655                         e->type = E_SYMBOL;
656                         e->left.sym = &symbol_no;
657                         e->right.sym = NULL;
658                         break;
659                 }
660                 if (e->right.sym == &symbol_yes) {
661                         e->type = E_SYMBOL;
662                         e->right.sym = NULL;
663                         break;
664                 }
665                 break;
666         case E_UNEQUAL:
667                 if (e->left.sym->type != S_BOOLEAN)
668                         break;
669                 if (e->right.sym == &symbol_no) {
670                         e->type = E_SYMBOL;
671                         e->right.sym = NULL;
672                         break;
673                 }
674                 if (e->right.sym == &symbol_mod) {
675                         printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
676                         e->type = E_SYMBOL;
677                         e->left.sym = &symbol_yes;
678                         e->right.sym = NULL;
679                         break;
680                 }
681                 if (e->right.sym == &symbol_yes) {
682                         e->type = E_NOT;
683                         e->left.expr = expr_alloc_symbol(e->left.sym);
684                         e->right.sym = NULL;
685                         break;
686                 }
687                 break;
688         case E_NOT:
689                 switch (e->left.expr->type) {
690                 case E_NOT:
691                         // !!a -> a
692                         tmp = e->left.expr->left.expr;
693                         free(e->left.expr);
694                         free(e);
695                         e = tmp;
696                         e = expr_transform(e);
697                         break;
698                 case E_EQUAL:
699                 case E_UNEQUAL:
700                         // !a='x' -> a!='x'
701                         tmp = e->left.expr;
702                         free(e);
703                         e = tmp;
704                         e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
705                         break;
706                 case E_OR:
707                         // !(a || b) -> !a && !b
708                         tmp = e->left.expr;
709                         e->type = E_AND;
710                         e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
711                         tmp->type = E_NOT;
712                         tmp->right.expr = NULL;
713                         e = expr_transform(e);
714                         break;
715                 case E_AND:
716                         // !(a && b) -> !a || !b
717                         tmp = e->left.expr;
718                         e->type = E_OR;
719                         e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
720                         tmp->type = E_NOT;
721                         tmp->right.expr = NULL;
722                         e = expr_transform(e);
723                         break;
724                 case E_SYMBOL:
725                         if (e->left.expr->left.sym == &symbol_yes) {
726                                 // !'y' -> 'n'
727                                 tmp = e->left.expr;
728                                 free(e);
729                                 e = tmp;
730                                 e->type = E_SYMBOL;
731                                 e->left.sym = &symbol_no;
732                                 break;
733                         }
734                         if (e->left.expr->left.sym == &symbol_mod) {
735                                 // !'m' -> 'm'
736                                 tmp = e->left.expr;
737                                 free(e);
738                                 e = tmp;
739                                 e->type = E_SYMBOL;
740                                 e->left.sym = &symbol_mod;
741                                 break;
742                         }
743                         if (e->left.expr->left.sym == &symbol_no) {
744                                 // !'n' -> 'y'
745                                 tmp = e->left.expr;
746                                 free(e);
747                                 e = tmp;
748                                 e->type = E_SYMBOL;
749                                 e->left.sym = &symbol_yes;
750                                 break;
751                         }
752                         break;
753                 default:
754                         ;
755                 }
756                 break;
757         default:
758                 ;
759         }
760         return e;
761 }
762
763 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
764 {
765         if (!dep)
766                 return 0;
767
768         switch (dep->type) {
769         case E_AND:
770         case E_OR:
771                 return expr_contains_symbol(dep->left.expr, sym) ||
772                        expr_contains_symbol(dep->right.expr, sym);
773         case E_SYMBOL:
774                 return dep->left.sym == sym;
775         case E_EQUAL:
776         case E_UNEQUAL:
777                 return dep->left.sym == sym ||
778                        dep->right.sym == sym;
779         case E_NOT:
780                 return expr_contains_symbol(dep->left.expr, sym);
781         default:
782                 ;
783         }
784         return 0;
785 }
786
787 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
788 {
789         if (!dep)
790                 return false;
791
792         switch (dep->type) {
793         case E_AND:
794                 return expr_depends_symbol(dep->left.expr, sym) ||
795                        expr_depends_symbol(dep->right.expr, sym);
796         case E_SYMBOL:
797                 return dep->left.sym == sym;
798         case E_EQUAL:
799                 if (dep->left.sym == sym) {
800                         if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
801                                 return true;
802                 }
803                 break;
804         case E_UNEQUAL:
805                 if (dep->left.sym == sym) {
806                         if (dep->right.sym == &symbol_no)
807                                 return true;
808                 }
809                 break;
810         default:
811                 ;
812         }
813         return false;
814 }
815
816 struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
817 {
818         struct expr *tmp = NULL;
819         expr_extract_eq(E_AND, &tmp, ep1, ep2);
820         if (tmp) {
821                 *ep1 = expr_eliminate_yn(*ep1);
822                 *ep2 = expr_eliminate_yn(*ep2);
823         }
824         return tmp;
825 }
826
827 struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
828 {
829         struct expr *tmp = NULL;
830         expr_extract_eq(E_OR, &tmp, ep1, ep2);
831         if (tmp) {
832                 *ep1 = expr_eliminate_yn(*ep1);
833                 *ep2 = expr_eliminate_yn(*ep2);
834         }
835         return tmp;
836 }
837
838 void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
839 {
840 #define e1 (*ep1)
841 #define e2 (*ep2)
842         if (e1->type == type) {
843                 expr_extract_eq(type, ep, &e1->left.expr, &e2);
844                 expr_extract_eq(type, ep, &e1->right.expr, &e2);
845                 return;
846         }
847         if (e2->type == type) {
848                 expr_extract_eq(type, ep, ep1, &e2->left.expr);
849                 expr_extract_eq(type, ep, ep1, &e2->right.expr);
850                 return;
851         }
852         if (expr_eq(e1, e2)) {
853                 *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
854                 expr_free(e2);
855                 if (type == E_AND) {
856                         e1 = expr_alloc_symbol(&symbol_yes);
857                         e2 = expr_alloc_symbol(&symbol_yes);
858                 } else if (type == E_OR) {
859                         e1 = expr_alloc_symbol(&symbol_no);
860                         e2 = expr_alloc_symbol(&symbol_no);
861                 }
862         }
863 #undef e1
864 #undef e2
865 }
866
867 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
868 {
869         struct expr *e1, *e2;
870
871         if (!e) {
872                 e = expr_alloc_symbol(sym);
873                 if (type == E_UNEQUAL)
874                         e = expr_alloc_one(E_NOT, e);
875                 return e;
876         }
877         switch (e->type) {
878         case E_AND:
879                 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
880                 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
881                 if (sym == &symbol_yes)
882                         e = expr_alloc_two(E_AND, e1, e2);
883                 if (sym == &symbol_no)
884                         e = expr_alloc_two(E_OR, e1, e2);
885                 if (type == E_UNEQUAL)
886                         e = expr_alloc_one(E_NOT, e);
887                 return e;
888         case E_OR:
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_OR, e1, e2);
893                 if (sym == &symbol_no)
894                         e = expr_alloc_two(E_AND, e1, e2);
895                 if (type == E_UNEQUAL)
896                         e = expr_alloc_one(E_NOT, e);
897                 return e;
898         case E_NOT:
899                 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
900         case E_UNEQUAL:
901         case E_EQUAL:
902                 if (type == E_EQUAL) {
903                         if (sym == &symbol_yes)
904                                 return expr_copy(e);
905                         if (sym == &symbol_mod)
906                                 return expr_alloc_symbol(&symbol_no);
907                         if (sym == &symbol_no)
908                                 return expr_alloc_one(E_NOT, expr_copy(e));
909                 } else {
910                         if (sym == &symbol_yes)
911                                 return expr_alloc_one(E_NOT, expr_copy(e));
912                         if (sym == &symbol_mod)
913                                 return expr_alloc_symbol(&symbol_yes);
914                         if (sym == &symbol_no)
915                                 return expr_copy(e);
916                 }
917                 break;
918         case E_SYMBOL:
919                 return expr_alloc_comp(type, e->left.sym, sym);
920         case E_CHOICE:
921         case E_RANGE:
922         case E_NONE:
923                 /* panic */;
924         }
925         return NULL;
926 }
927
928 tristate expr_calc_value(struct expr *e)
929 {
930         tristate val1, val2;
931         const char *str1, *str2;
932
933         if (!e)
934                 return yes;
935
936         switch (e->type) {
937         case E_SYMBOL:
938                 sym_calc_value(e->left.sym);
939                 return e->left.sym->curr.tri;
940         case E_AND:
941                 val1 = expr_calc_value(e->left.expr);
942                 val2 = expr_calc_value(e->right.expr);
943                 return E_AND(val1, val2);
944         case E_OR:
945                 val1 = expr_calc_value(e->left.expr);
946                 val2 = expr_calc_value(e->right.expr);
947                 return E_OR(val1, val2);
948         case E_NOT:
949                 val1 = expr_calc_value(e->left.expr);
950                 return E_NOT(val1);
951         case E_EQUAL:
952                 sym_calc_value(e->left.sym);
953                 sym_calc_value(e->right.sym);
954                 str1 = sym_get_string_value(e->left.sym);
955                 str2 = sym_get_string_value(e->right.sym);
956                 return !strcmp(str1, str2) ? yes : no;
957         case E_UNEQUAL:
958                 sym_calc_value(e->left.sym);
959                 sym_calc_value(e->right.sym);
960                 str1 = sym_get_string_value(e->left.sym);
961                 str2 = sym_get_string_value(e->right.sym);
962                 return !strcmp(str1, str2) ? no : yes;
963         default:
964                 printf("expr_calc_value: %d?\n", e->type);
965                 return no;
966         }
967 }
968
969 int expr_compare_type(enum expr_type t1, enum expr_type t2)
970 {
971 #if 0
972         return 1;
973 #else
974         if (t1 == t2)
975                 return 0;
976         switch (t1) {
977         case E_EQUAL:
978         case E_UNEQUAL:
979                 if (t2 == E_NOT)
980                         return 1;
981         case E_NOT:
982                 if (t2 == E_AND)
983                         return 1;
984         case E_AND:
985                 if (t2 == E_OR)
986                         return 1;
987         case E_OR:
988                 if (t2 == E_CHOICE)
989                         return 1;
990         case E_CHOICE:
991                 if (t2 == 0)
992                         return 1;
993         default:
994                 return -1;
995         }
996         printf("[%dgt%d?]", t1, t2);
997         return 0;
998 #endif
999 }
1000
1001 void expr_print(struct expr *e, void (*fn)(void *, const char *), void *data, int prevtoken)
1002 {
1003         if (!e) {
1004                 fn(data, "y");
1005                 return;
1006         }
1007
1008         if (expr_compare_type(prevtoken, e->type) > 0)
1009                 fn(data, "(");
1010         switch (e->type) {
1011         case E_SYMBOL:
1012                 if (e->left.sym->name)
1013                         fn(data, e->left.sym->name);
1014                 else
1015                         fn(data, "<choice>");
1016                 break;
1017         case E_NOT:
1018                 fn(data, "!");
1019                 expr_print(e->left.expr, fn, data, E_NOT);
1020                 break;
1021         case E_EQUAL:
1022                 fn(data, e->left.sym->name);
1023                 fn(data, "=");
1024                 fn(data, e->right.sym->name);
1025                 break;
1026         case E_UNEQUAL:
1027                 fn(data, e->left.sym->name);
1028                 fn(data, "!=");
1029                 fn(data, e->right.sym->name);
1030                 break;
1031         case E_OR:
1032                 expr_print(e->left.expr, fn, data, E_OR);
1033                 fn(data, " || ");
1034                 expr_print(e->right.expr, fn, data, E_OR);
1035                 break;
1036         case E_AND:
1037                 expr_print(e->left.expr, fn, data, E_AND);
1038                 fn(data, " && ");
1039                 expr_print(e->right.expr, fn, data, E_AND);
1040                 break;
1041         case E_CHOICE:
1042                 fn(data, e->right.sym->name);
1043                 if (e->left.expr) {
1044                         fn(data, " ^ ");
1045                         expr_print(e->left.expr, fn, data, E_CHOICE);
1046                 }
1047                 break;
1048         case E_RANGE:
1049                 fn(data, "[");
1050                 fn(data, e->left.sym->name);
1051                 fn(data, " ");
1052                 fn(data, e->right.sym->name);
1053                 fn(data, "]");
1054                 break;
1055         default:
1056           {
1057                 char buf[32];
1058                 sprintf(buf, "<unknown type %d>", e->type);
1059                 fn(data, buf);
1060                 break;
1061           }
1062         }
1063         if (expr_compare_type(prevtoken, e->type) > 0)
1064                 fn(data, ")");
1065 }
1066
1067 static void expr_print_file_helper(void *data, const char *str)
1068 {
1069         fwrite(str, strlen(str), 1, data);
1070 }
1071
1072 void expr_fprint(struct expr *e, FILE *out)
1073 {
1074         expr_print(e, expr_print_file_helper, out, E_NONE);
1075 }
1076
1077 void print_expr(int mask, struct expr *e, int prevtoken)
1078 {
1079         if (!(cdebug & mask))
1080                 return;
1081         expr_fprint(e, stdout);
1082 }
1083