Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


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