kconfig/gconf: kill deadcode
[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 #include "lkc.h"
11
12 #define DEBUG_EXPR      0
13
14 struct expr *expr_alloc_symbol(struct symbol *sym)
15 {
16         struct expr *e = malloc(sizeof(*e));
17         memset(e, 0, sizeof(*e));
18         e->type = E_SYMBOL;
19         e->left.sym = sym;
20         return e;
21 }
22
23 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
24 {
25         struct expr *e = malloc(sizeof(*e));
26         memset(e, 0, sizeof(*e));
27         e->type = type;
28         e->left.expr = ce;
29         return e;
30 }
31
32 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
33 {
34         struct expr *e = malloc(sizeof(*e));
35         memset(e, 0, sizeof(*e));
36         e->type = type;
37         e->left.expr = e1;
38         e->right.expr = e2;
39         return e;
40 }
41
42 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
43 {
44         struct expr *e = malloc(sizeof(*e));
45         memset(e, 0, sizeof(*e));
46         e->type = type;
47         e->left.sym = s1;
48         e->right.sym = s2;
49         return e;
50 }
51
52 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
53 {
54         if (!e1)
55                 return e2;
56         return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
57 }
58
59 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
60 {
61         if (!e1)
62                 return e2;
63         return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
64 }
65
66 struct expr *expr_copy(const struct expr *org)
67 {
68         struct expr *e;
69
70         if (!org)
71                 return NULL;
72
73         e = malloc(sizeof(*org));
74         memcpy(e, org, sizeof(*org));
75         switch (org->type) {
76         case E_SYMBOL:
77                 e->left = org->left;
78                 break;
79         case E_NOT:
80                 e->left.expr = expr_copy(org->left.expr);
81                 break;
82         case E_EQUAL:
83         case E_UNEQUAL:
84                 e->left.sym = org->left.sym;
85                 e->right.sym = org->right.sym;
86                 break;
87         case E_AND:
88         case E_OR:
89         case E_LIST:
90                 e->left.expr = expr_copy(org->left.expr);
91                 e->right.expr = expr_copy(org->right.expr);
92                 break;
93         default:
94                 printf("can't copy type %d\n", e->type);
95                 free(e);
96                 e = NULL;
97                 break;
98         }
99
100         return e;
101 }
102
103 void expr_free(struct expr *e)
104 {
105         if (!e)
106                 return;
107
108         switch (e->type) {
109         case E_SYMBOL:
110                 break;
111         case E_NOT:
112                 expr_free(e->left.expr);
113                 return;
114         case E_EQUAL:
115         case E_UNEQUAL:
116                 break;
117         case E_OR:
118         case E_AND:
119                 expr_free(e->left.expr);
120                 expr_free(e->right.expr);
121                 break;
122         default:
123                 printf("how to free type %d?\n", e->type);
124                 break;
125         }
126         free(e);
127 }
128
129 static int trans_count;
130
131 #define e1 (*ep1)
132 #define e2 (*ep2)
133
134 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
135 {
136         if (e1->type == type) {
137                 __expr_eliminate_eq(type, &e1->left.expr, &e2);
138                 __expr_eliminate_eq(type, &e1->right.expr, &e2);
139                 return;
140         }
141         if (e2->type == type) {
142                 __expr_eliminate_eq(type, &e1, &e2->left.expr);
143                 __expr_eliminate_eq(type, &e1, &e2->right.expr);
144                 return;
145         }
146         if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
147             e1->left.sym == e2->left.sym &&
148             (e1->left.sym == &symbol_yes || e1->left.sym == &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_LIST:
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 static 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 static 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_LIST:
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_LIST:
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 EXPR_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 EXPR_OR(val1, val2);
962         case E_NOT:
963                 val1 = expr_calc_value(e->left.expr);
964                 return EXPR_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_LIST)
1003                         return 1;
1004         case E_LIST:
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 static inline struct expr *
1016 expr_get_leftmost_symbol(const struct expr *e)
1017 {
1018
1019         if (e == NULL)
1020                 return NULL;
1021
1022         while (e->type != E_SYMBOL)
1023                 e = e->left.expr;
1024
1025         return expr_copy(e);
1026 }
1027
1028 /*
1029  * Given expression `e1' and `e2', returns the leaf of the longest
1030  * sub-expression of `e1' not containing 'e2.
1031  */
1032 struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
1033 {
1034         struct expr *ret;
1035
1036         switch (e1->type) {
1037         case E_OR:
1038                 return expr_alloc_and(
1039                     expr_simplify_unmet_dep(e1->left.expr, e2),
1040                     expr_simplify_unmet_dep(e1->right.expr, e2));
1041         case E_AND: {
1042                 struct expr *e;
1043                 e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
1044                 e = expr_eliminate_dups(e);
1045                 ret = (!expr_eq(e, e1)) ? e1 : NULL;
1046                 expr_free(e);
1047                 break;
1048                 }
1049         default:
1050                 ret = e1;
1051                 break;
1052         }
1053
1054         return expr_get_leftmost_symbol(ret);
1055 }
1056
1057 void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1058 {
1059         if (!e) {
1060                 fn(data, NULL, "y");
1061                 return;
1062         }
1063
1064         if (expr_compare_type(prevtoken, e->type) > 0)
1065                 fn(data, NULL, "(");
1066         switch (e->type) {
1067         case E_SYMBOL:
1068                 if (e->left.sym->name)
1069                         fn(data, e->left.sym, e->left.sym->name);
1070                 else
1071                         fn(data, NULL, "<choice>");
1072                 break;
1073         case E_NOT:
1074                 fn(data, NULL, "!");
1075                 expr_print(e->left.expr, fn, data, E_NOT);
1076                 break;
1077         case E_EQUAL:
1078                 if (e->left.sym->name)
1079                         fn(data, e->left.sym, e->left.sym->name);
1080                 else
1081                         fn(data, NULL, "<choice>");
1082                 fn(data, NULL, "=");
1083                 fn(data, e->right.sym, e->right.sym->name);
1084                 break;
1085         case E_UNEQUAL:
1086                 if (e->left.sym->name)
1087                         fn(data, e->left.sym, e->left.sym->name);
1088                 else
1089                         fn(data, NULL, "<choice>");
1090                 fn(data, NULL, "!=");
1091                 fn(data, e->right.sym, e->right.sym->name);
1092                 break;
1093         case E_OR:
1094                 expr_print(e->left.expr, fn, data, E_OR);
1095                 fn(data, NULL, " || ");
1096                 expr_print(e->right.expr, fn, data, E_OR);
1097                 break;
1098         case E_AND:
1099                 expr_print(e->left.expr, fn, data, E_AND);
1100                 fn(data, NULL, " && ");
1101                 expr_print(e->right.expr, fn, data, E_AND);
1102                 break;
1103         case E_LIST:
1104                 fn(data, e->right.sym, e->right.sym->name);
1105                 if (e->left.expr) {
1106                         fn(data, NULL, " ^ ");
1107                         expr_print(e->left.expr, fn, data, E_LIST);
1108                 }
1109                 break;
1110         case E_RANGE:
1111                 fn(data, NULL, "[");
1112                 fn(data, e->left.sym, e->left.sym->name);
1113                 fn(data, NULL, " ");
1114                 fn(data, e->right.sym, e->right.sym->name);
1115                 fn(data, NULL, "]");
1116                 break;
1117         default:
1118           {
1119                 char buf[32];
1120                 sprintf(buf, "<unknown type %d>", e->type);
1121                 fn(data, NULL, buf);
1122                 break;
1123           }
1124         }
1125         if (expr_compare_type(prevtoken, e->type) > 0)
1126                 fn(data, NULL, ")");
1127 }
1128
1129 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1130 {
1131         xfwrite(str, strlen(str), 1, data);
1132 }
1133
1134 void expr_fprint(struct expr *e, FILE *out)
1135 {
1136         expr_print(e, expr_print_file_helper, out, E_NONE);
1137 }
1138
1139 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1140 {
1141         struct gstr *gs = (struct gstr*)data;
1142         const char *sym_str = NULL;
1143
1144         if (sym)
1145                 sym_str = sym_get_string_value(sym);
1146
1147         if (gs->max_width) {
1148                 unsigned extra_length = strlen(str);
1149                 const char *last_cr = strrchr(gs->s, '\n');
1150                 unsigned last_line_length;
1151
1152                 if (sym_str)
1153                         extra_length += 4 + strlen(sym_str);
1154
1155                 if (!last_cr)
1156                         last_cr = gs->s;
1157
1158                 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1159
1160                 if ((last_line_length + extra_length) > gs->max_width)
1161                         str_append(gs, "\\\n");
1162         }
1163
1164         str_append(gs, str);
1165         if (sym && sym->type != S_UNKNOWN)
1166                 str_printf(gs, " [=%s]", sym_str);
1167 }
1168
1169 void expr_gstr_print(struct expr *e, struct gstr *gs)
1170 {
1171         expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1172 }