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