kconfig: Only generate config_is_xxx for bool and tristate options
[linux-2.6.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(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 }