Merge tag 'kconfig-v4.16' of git://git.kernel.org/pub/scm/linux/kernel/git/masahiroy...
[sfrench/cifs-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 static int expr_eq(struct expr *e1, struct expr *e2);
15 static struct expr *expr_eliminate_yn(struct expr *e);
16
17 struct expr *expr_alloc_symbol(struct symbol *sym)
18 {
19         struct expr *e = xcalloc(1, sizeof(*e));
20         e->type = E_SYMBOL;
21         e->left.sym = sym;
22         return e;
23 }
24
25 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
26 {
27         struct expr *e = xcalloc(1, 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 = xcalloc(1, 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 = xcalloc(1, sizeof(*e));
45         e->type = type;
46         e->left.sym = s1;
47         e->right.sym = s2;
48         return e;
49 }
50
51 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
52 {
53         if (!e1)
54                 return e2;
55         return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
56 }
57
58 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
59 {
60         if (!e1)
61                 return e2;
62         return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
63 }
64
65 struct expr *expr_copy(const struct expr *org)
66 {
67         struct expr *e;
68
69         if (!org)
70                 return NULL;
71
72         e = xmalloc(sizeof(*org));
73         memcpy(e, org, sizeof(*org));
74         switch (org->type) {
75         case E_SYMBOL:
76                 e->left = org->left;
77                 break;
78         case E_NOT:
79                 e->left.expr = expr_copy(org->left.expr);
80                 break;
81         case E_EQUAL:
82         case E_GEQ:
83         case E_GTH:
84         case E_LEQ:
85         case E_LTH:
86         case E_UNEQUAL:
87                 e->left.sym = org->left.sym;
88                 e->right.sym = org->right.sym;
89                 break;
90         case E_AND:
91         case E_OR:
92         case E_LIST:
93                 e->left.expr = expr_copy(org->left.expr);
94                 e->right.expr = expr_copy(org->right.expr);
95                 break;
96         default:
97                 printf("can't copy type %d\n", e->type);
98                 free(e);
99                 e = NULL;
100                 break;
101         }
102
103         return e;
104 }
105
106 void expr_free(struct expr *e)
107 {
108         if (!e)
109                 return;
110
111         switch (e->type) {
112         case E_SYMBOL:
113                 break;
114         case E_NOT:
115                 expr_free(e->left.expr);
116                 break;
117         case E_EQUAL:
118         case E_GEQ:
119         case E_GTH:
120         case E_LEQ:
121         case E_LTH:
122         case E_UNEQUAL:
123                 break;
124         case E_OR:
125         case E_AND:
126                 expr_free(e->left.expr);
127                 expr_free(e->right.expr);
128                 break;
129         default:
130                 printf("how to free type %d?\n", e->type);
131                 break;
132         }
133         free(e);
134 }
135
136 static int trans_count;
137
138 #define e1 (*ep1)
139 #define e2 (*ep2)
140
141 /*
142  * expr_eliminate_eq() helper.
143  *
144  * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
145  * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
146  * against all other leaves. Two equal leaves are both replaced with either 'y'
147  * or 'n' as appropriate for 'type', to be eliminated later.
148  */
149 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
150 {
151         /* Recurse down to leaves */
152
153         if (e1->type == type) {
154                 __expr_eliminate_eq(type, &e1->left.expr, &e2);
155                 __expr_eliminate_eq(type, &e1->right.expr, &e2);
156                 return;
157         }
158         if (e2->type == type) {
159                 __expr_eliminate_eq(type, &e1, &e2->left.expr);
160                 __expr_eliminate_eq(type, &e1, &e2->right.expr);
161                 return;
162         }
163
164         /* e1 and e2 are leaves. Compare them. */
165
166         if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
167             e1->left.sym == e2->left.sym &&
168             (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
169                 return;
170         if (!expr_eq(e1, e2))
171                 return;
172
173         /* e1 and e2 are equal leaves. Prepare them for elimination. */
174
175         trans_count++;
176         expr_free(e1); expr_free(e2);
177         switch (type) {
178         case E_OR:
179                 e1 = expr_alloc_symbol(&symbol_no);
180                 e2 = expr_alloc_symbol(&symbol_no);
181                 break;
182         case E_AND:
183                 e1 = expr_alloc_symbol(&symbol_yes);
184                 e2 = expr_alloc_symbol(&symbol_yes);
185                 break;
186         default:
187                 ;
188         }
189 }
190
191 /*
192  * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both.
193  * Example reductions:
194  *
195  *      ep1: A && B           ->  ep1: y
196  *      ep2: A && B && C      ->  ep2: C
197  *
198  *      ep1: A || B           ->  ep1: n
199  *      ep2: A || B || C      ->  ep2: C
200  *
201  *      ep1: A && (B && FOO)  ->  ep1: FOO
202  *      ep2: (BAR && B) && A  ->  ep2: BAR
203  *
204  *      ep1: A && (B || C)    ->  ep1: y
205  *      ep2: (C || B) && A    ->  ep2: y
206  *
207  * Comparisons are done between all operands at the same "level" of && or ||.
208  * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the
209  * following operands will be compared:
210  *
211  *      - 'e1', 'e2 || e3', and 'e4 || e5', against each other
212  *      - e2 against e3
213  *      - e4 against e5
214  *
215  * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and
216  * '(e1 && e2) && e3' are both a single level.
217  *
218  * See __expr_eliminate_eq() as well.
219  */
220 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
221 {
222         if (!e1 || !e2)
223                 return;
224         switch (e1->type) {
225         case E_OR:
226         case E_AND:
227                 __expr_eliminate_eq(e1->type, ep1, ep2);
228         default:
229                 ;
230         }
231         if (e1->type != e2->type) switch (e2->type) {
232         case E_OR:
233         case E_AND:
234                 __expr_eliminate_eq(e2->type, ep1, ep2);
235         default:
236                 ;
237         }
238         e1 = expr_eliminate_yn(e1);
239         e2 = expr_eliminate_yn(e2);
240 }
241
242 #undef e1
243 #undef e2
244
245 /*
246  * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two
247  * &&/|| expressions are considered equal if every operand in one expression
248  * equals some operand in the other (operands do not need to appear in the same
249  * order), recursively.
250  */
251 static int expr_eq(struct expr *e1, struct expr *e2)
252 {
253         int res, old_count;
254
255         if (e1->type != e2->type)
256                 return 0;
257         switch (e1->type) {
258         case E_EQUAL:
259         case E_GEQ:
260         case E_GTH:
261         case E_LEQ:
262         case E_LTH:
263         case E_UNEQUAL:
264                 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
265         case E_SYMBOL:
266                 return e1->left.sym == e2->left.sym;
267         case E_NOT:
268                 return expr_eq(e1->left.expr, e2->left.expr);
269         case E_AND:
270         case E_OR:
271                 e1 = expr_copy(e1);
272                 e2 = expr_copy(e2);
273                 old_count = trans_count;
274                 expr_eliminate_eq(&e1, &e2);
275                 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
276                        e1->left.sym == e2->left.sym);
277                 expr_free(e1);
278                 expr_free(e2);
279                 trans_count = old_count;
280                 return res;
281         case E_LIST:
282         case E_RANGE:
283         case E_NONE:
284                 /* panic */;
285         }
286
287         if (DEBUG_EXPR) {
288                 expr_fprint(e1, stdout);
289                 printf(" = ");
290                 expr_fprint(e2, stdout);
291                 printf(" ?\n");
292         }
293
294         return 0;
295 }
296
297 /*
298  * Recursively performs the following simplifications in-place (as well as the
299  * corresponding simplifications with swapped operands):
300  *
301  *      expr && n  ->  n
302  *      expr && y  ->  expr
303  *      expr || n  ->  expr
304  *      expr || y  ->  y
305  *
306  * Returns the optimized expression.
307  */
308 static struct expr *expr_eliminate_yn(struct expr *e)
309 {
310         struct expr *tmp;
311
312         if (e) switch (e->type) {
313         case E_AND:
314                 e->left.expr = expr_eliminate_yn(e->left.expr);
315                 e->right.expr = expr_eliminate_yn(e->right.expr);
316                 if (e->left.expr->type == E_SYMBOL) {
317                         if (e->left.expr->left.sym == &symbol_no) {
318                                 expr_free(e->left.expr);
319                                 expr_free(e->right.expr);
320                                 e->type = E_SYMBOL;
321                                 e->left.sym = &symbol_no;
322                                 e->right.expr = NULL;
323                                 return e;
324                         } else if (e->left.expr->left.sym == &symbol_yes) {
325                                 free(e->left.expr);
326                                 tmp = e->right.expr;
327                                 *e = *(e->right.expr);
328                                 free(tmp);
329                                 return e;
330                         }
331                 }
332                 if (e->right.expr->type == E_SYMBOL) {
333                         if (e->right.expr->left.sym == &symbol_no) {
334                                 expr_free(e->left.expr);
335                                 expr_free(e->right.expr);
336                                 e->type = E_SYMBOL;
337                                 e->left.sym = &symbol_no;
338                                 e->right.expr = NULL;
339                                 return e;
340                         } else if (e->right.expr->left.sym == &symbol_yes) {
341                                 free(e->right.expr);
342                                 tmp = e->left.expr;
343                                 *e = *(e->left.expr);
344                                 free(tmp);
345                                 return e;
346                         }
347                 }
348                 break;
349         case E_OR:
350                 e->left.expr = expr_eliminate_yn(e->left.expr);
351                 e->right.expr = expr_eliminate_yn(e->right.expr);
352                 if (e->left.expr->type == E_SYMBOL) {
353                         if (e->left.expr->left.sym == &symbol_no) {
354                                 free(e->left.expr);
355                                 tmp = e->right.expr;
356                                 *e = *(e->right.expr);
357                                 free(tmp);
358                                 return e;
359                         } else if (e->left.expr->left.sym == &symbol_yes) {
360                                 expr_free(e->left.expr);
361                                 expr_free(e->right.expr);
362                                 e->type = E_SYMBOL;
363                                 e->left.sym = &symbol_yes;
364                                 e->right.expr = NULL;
365                                 return e;
366                         }
367                 }
368                 if (e->right.expr->type == E_SYMBOL) {
369                         if (e->right.expr->left.sym == &symbol_no) {
370                                 free(e->right.expr);
371                                 tmp = e->left.expr;
372                                 *e = *(e->left.expr);
373                                 free(tmp);
374                                 return e;
375                         } else if (e->right.expr->left.sym == &symbol_yes) {
376                                 expr_free(e->left.expr);
377                                 expr_free(e->right.expr);
378                                 e->type = E_SYMBOL;
379                                 e->left.sym = &symbol_yes;
380                                 e->right.expr = NULL;
381                                 return e;
382                         }
383                 }
384                 break;
385         default:
386                 ;
387         }
388         return e;
389 }
390
391 /*
392  * bool FOO!=n => FOO
393  */
394 struct expr *expr_trans_bool(struct expr *e)
395 {
396         if (!e)
397                 return NULL;
398         switch (e->type) {
399         case E_AND:
400         case E_OR:
401         case E_NOT:
402                 e->left.expr = expr_trans_bool(e->left.expr);
403                 e->right.expr = expr_trans_bool(e->right.expr);
404                 break;
405         case E_UNEQUAL:
406                 // FOO!=n -> FOO
407                 if (e->left.sym->type == S_TRISTATE) {
408                         if (e->right.sym == &symbol_no) {
409                                 e->type = E_SYMBOL;
410                                 e->right.sym = NULL;
411                         }
412                 }
413                 break;
414         default:
415                 ;
416         }
417         return e;
418 }
419
420 /*
421  * e1 || e2 -> ?
422  */
423 static struct expr *expr_join_or(struct expr *e1, struct expr *e2)
424 {
425         struct expr *tmp;
426         struct symbol *sym1, *sym2;
427
428         if (expr_eq(e1, e2))
429                 return expr_copy(e1);
430         if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
431                 return NULL;
432         if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
433                 return NULL;
434         if (e1->type == E_NOT) {
435                 tmp = e1->left.expr;
436                 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
437                         return NULL;
438                 sym1 = tmp->left.sym;
439         } else
440                 sym1 = e1->left.sym;
441         if (e2->type == E_NOT) {
442                 if (e2->left.expr->type != E_SYMBOL)
443                         return NULL;
444                 sym2 = e2->left.expr->left.sym;
445         } else
446                 sym2 = e2->left.sym;
447         if (sym1 != sym2)
448                 return NULL;
449         if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
450                 return NULL;
451         if (sym1->type == S_TRISTATE) {
452                 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
453                     ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
454                      (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
455                         // (a='y') || (a='m') -> (a!='n')
456                         return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
457                 }
458                 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
459                     ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
460                      (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
461                         // (a='y') || (a='n') -> (a!='m')
462                         return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
463                 }
464                 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
465                     ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
466                      (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
467                         // (a='m') || (a='n') -> (a!='y')
468                         return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
469                 }
470         }
471         if (sym1->type == S_BOOLEAN && sym1 == sym2) {
472                 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
473                     (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
474                         return expr_alloc_symbol(&symbol_yes);
475         }
476
477         if (DEBUG_EXPR) {
478                 printf("optimize (");
479                 expr_fprint(e1, stdout);
480                 printf(") || (");
481                 expr_fprint(e2, stdout);
482                 printf(")?\n");
483         }
484         return NULL;
485 }
486
487 static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
488 {
489         struct expr *tmp;
490         struct symbol *sym1, *sym2;
491
492         if (expr_eq(e1, e2))
493                 return expr_copy(e1);
494         if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
495                 return NULL;
496         if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
497                 return NULL;
498         if (e1->type == E_NOT) {
499                 tmp = e1->left.expr;
500                 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
501                         return NULL;
502                 sym1 = tmp->left.sym;
503         } else
504                 sym1 = e1->left.sym;
505         if (e2->type == E_NOT) {
506                 if (e2->left.expr->type != E_SYMBOL)
507                         return NULL;
508                 sym2 = e2->left.expr->left.sym;
509         } else
510                 sym2 = e2->left.sym;
511         if (sym1 != sym2)
512                 return NULL;
513         if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
514                 return NULL;
515
516         if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
517             (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
518                 // (a) && (a='y') -> (a='y')
519                 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
520
521         if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
522             (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
523                 // (a) && (a!='n') -> (a)
524                 return expr_alloc_symbol(sym1);
525
526         if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
527             (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
528                 // (a) && (a!='m') -> (a='y')
529                 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
530
531         if (sym1->type == S_TRISTATE) {
532                 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
533                         // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
534                         sym2 = e1->right.sym;
535                         if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
536                                 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
537                                                              : expr_alloc_symbol(&symbol_no);
538                 }
539                 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
540                         // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
541                         sym2 = e2->right.sym;
542                         if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
543                                 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
544                                                              : expr_alloc_symbol(&symbol_no);
545                 }
546                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
547                            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
548                             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
549                         // (a!='y') && (a!='n') -> (a='m')
550                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
551
552                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
553                            ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
554                             (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
555                         // (a!='y') && (a!='m') -> (a='n')
556                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
557
558                 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
559                            ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
560                             (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
561                         // (a!='m') && (a!='n') -> (a='m')
562                         return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
563
564                 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
565                     (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
566                     (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
567                     (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
568                         return NULL;
569         }
570
571         if (DEBUG_EXPR) {
572                 printf("optimize (");
573                 expr_fprint(e1, stdout);
574                 printf(") && (");
575                 expr_fprint(e2, stdout);
576                 printf(")?\n");
577         }
578         return NULL;
579 }
580
581 /*
582  * expr_eliminate_dups() helper.
583  *
584  * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
585  * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
586  * against all other leaves to look for simplifications.
587  */
588 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
589 {
590 #define e1 (*ep1)
591 #define e2 (*ep2)
592         struct expr *tmp;
593
594         /* Recurse down to leaves */
595
596         if (e1->type == type) {
597                 expr_eliminate_dups1(type, &e1->left.expr, &e2);
598                 expr_eliminate_dups1(type, &e1->right.expr, &e2);
599                 return;
600         }
601         if (e2->type == type) {
602                 expr_eliminate_dups1(type, &e1, &e2->left.expr);
603                 expr_eliminate_dups1(type, &e1, &e2->right.expr);
604                 return;
605         }
606
607         /* e1 and e2 are leaves. Compare and process them. */
608
609         if (e1 == e2)
610                 return;
611
612         switch (e1->type) {
613         case E_OR: case E_AND:
614                 expr_eliminate_dups1(e1->type, &e1, &e1);
615         default:
616                 ;
617         }
618
619         switch (type) {
620         case E_OR:
621                 tmp = expr_join_or(e1, e2);
622                 if (tmp) {
623                         expr_free(e1); expr_free(e2);
624                         e1 = expr_alloc_symbol(&symbol_no);
625                         e2 = tmp;
626                         trans_count++;
627                 }
628                 break;
629         case E_AND:
630                 tmp = expr_join_and(e1, e2);
631                 if (tmp) {
632                         expr_free(e1); expr_free(e2);
633                         e1 = expr_alloc_symbol(&symbol_yes);
634                         e2 = tmp;
635                         trans_count++;
636                 }
637                 break;
638         default:
639                 ;
640         }
641 #undef e1
642 #undef e2
643 }
644
645 /*
646  * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
647  * operands.
648  *
649  * Example simplifications:
650  *
651  *      A || B || A    ->  A || B
652  *      A && B && A=y  ->  A=y && B
653  *
654  * Returns the deduplicated expression.
655  */
656 struct expr *expr_eliminate_dups(struct expr *e)
657 {
658         int oldcount;
659         if (!e)
660                 return e;
661
662         oldcount = trans_count;
663         while (1) {
664                 trans_count = 0;
665                 switch (e->type) {
666                 case E_OR: case E_AND:
667                         expr_eliminate_dups1(e->type, &e, &e);
668                 default:
669                         ;
670                 }
671                 if (!trans_count)
672                         /* No simplifications done in this pass. We're done */
673                         break;
674                 e = expr_eliminate_yn(e);
675         }
676         trans_count = oldcount;
677         return e;
678 }
679
680 /*
681  * Performs various simplifications involving logical operators and
682  * comparisons.
683  *
684  * Allocates and returns a new expression.
685  */
686 struct expr *expr_transform(struct expr *e)
687 {
688         struct expr *tmp;
689
690         if (!e)
691                 return NULL;
692         switch (e->type) {
693         case E_EQUAL:
694         case E_GEQ:
695         case E_GTH:
696         case E_LEQ:
697         case E_LTH:
698         case E_UNEQUAL:
699         case E_SYMBOL:
700         case E_LIST:
701                 break;
702         default:
703                 e->left.expr = expr_transform(e->left.expr);
704                 e->right.expr = expr_transform(e->right.expr);
705         }
706
707         switch (e->type) {
708         case E_EQUAL:
709                 if (e->left.sym->type != S_BOOLEAN)
710                         break;
711                 if (e->right.sym == &symbol_no) {
712                         e->type = E_NOT;
713                         e->left.expr = expr_alloc_symbol(e->left.sym);
714                         e->right.sym = NULL;
715                         break;
716                 }
717                 if (e->right.sym == &symbol_mod) {
718                         printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
719                         e->type = E_SYMBOL;
720                         e->left.sym = &symbol_no;
721                         e->right.sym = NULL;
722                         break;
723                 }
724                 if (e->right.sym == &symbol_yes) {
725                         e->type = E_SYMBOL;
726                         e->right.sym = NULL;
727                         break;
728                 }
729                 break;
730         case E_UNEQUAL:
731                 if (e->left.sym->type != S_BOOLEAN)
732                         break;
733                 if (e->right.sym == &symbol_no) {
734                         e->type = E_SYMBOL;
735                         e->right.sym = NULL;
736                         break;
737                 }
738                 if (e->right.sym == &symbol_mod) {
739                         printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
740                         e->type = E_SYMBOL;
741                         e->left.sym = &symbol_yes;
742                         e->right.sym = NULL;
743                         break;
744                 }
745                 if (e->right.sym == &symbol_yes) {
746                         e->type = E_NOT;
747                         e->left.expr = expr_alloc_symbol(e->left.sym);
748                         e->right.sym = NULL;
749                         break;
750                 }
751                 break;
752         case E_NOT:
753                 switch (e->left.expr->type) {
754                 case E_NOT:
755                         // !!a -> a
756                         tmp = e->left.expr->left.expr;
757                         free(e->left.expr);
758                         free(e);
759                         e = tmp;
760                         e = expr_transform(e);
761                         break;
762                 case E_EQUAL:
763                 case E_UNEQUAL:
764                         // !a='x' -> a!='x'
765                         tmp = e->left.expr;
766                         free(e);
767                         e = tmp;
768                         e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
769                         break;
770                 case E_LEQ:
771                 case E_GEQ:
772                         // !a<='x' -> a>'x'
773                         tmp = e->left.expr;
774                         free(e);
775                         e = tmp;
776                         e->type = e->type == E_LEQ ? E_GTH : E_LTH;
777                         break;
778                 case E_LTH:
779                 case E_GTH:
780                         // !a<'x' -> a>='x'
781                         tmp = e->left.expr;
782                         free(e);
783                         e = tmp;
784                         e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
785                         break;
786                 case E_OR:
787                         // !(a || b) -> !a && !b
788                         tmp = e->left.expr;
789                         e->type = E_AND;
790                         e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
791                         tmp->type = E_NOT;
792                         tmp->right.expr = NULL;
793                         e = expr_transform(e);
794                         break;
795                 case E_AND:
796                         // !(a && b) -> !a || !b
797                         tmp = e->left.expr;
798                         e->type = E_OR;
799                         e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
800                         tmp->type = E_NOT;
801                         tmp->right.expr = NULL;
802                         e = expr_transform(e);
803                         break;
804                 case E_SYMBOL:
805                         if (e->left.expr->left.sym == &symbol_yes) {
806                                 // !'y' -> 'n'
807                                 tmp = e->left.expr;
808                                 free(e);
809                                 e = tmp;
810                                 e->type = E_SYMBOL;
811                                 e->left.sym = &symbol_no;
812                                 break;
813                         }
814                         if (e->left.expr->left.sym == &symbol_mod) {
815                                 // !'m' -> 'm'
816                                 tmp = e->left.expr;
817                                 free(e);
818                                 e = tmp;
819                                 e->type = E_SYMBOL;
820                                 e->left.sym = &symbol_mod;
821                                 break;
822                         }
823                         if (e->left.expr->left.sym == &symbol_no) {
824                                 // !'n' -> 'y'
825                                 tmp = e->left.expr;
826                                 free(e);
827                                 e = tmp;
828                                 e->type = E_SYMBOL;
829                                 e->left.sym = &symbol_yes;
830                                 break;
831                         }
832                         break;
833                 default:
834                         ;
835                 }
836                 break;
837         default:
838                 ;
839         }
840         return e;
841 }
842
843 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
844 {
845         if (!dep)
846                 return 0;
847
848         switch (dep->type) {
849         case E_AND:
850         case E_OR:
851                 return expr_contains_symbol(dep->left.expr, sym) ||
852                        expr_contains_symbol(dep->right.expr, sym);
853         case E_SYMBOL:
854                 return dep->left.sym == sym;
855         case E_EQUAL:
856         case E_GEQ:
857         case E_GTH:
858         case E_LEQ:
859         case E_LTH:
860         case E_UNEQUAL:
861                 return dep->left.sym == sym ||
862                        dep->right.sym == sym;
863         case E_NOT:
864                 return expr_contains_symbol(dep->left.expr, sym);
865         default:
866                 ;
867         }
868         return 0;
869 }
870
871 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
872 {
873         if (!dep)
874                 return false;
875
876         switch (dep->type) {
877         case E_AND:
878                 return expr_depends_symbol(dep->left.expr, sym) ||
879                        expr_depends_symbol(dep->right.expr, sym);
880         case E_SYMBOL:
881                 return dep->left.sym == sym;
882         case E_EQUAL:
883                 if (dep->left.sym == sym) {
884                         if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
885                                 return true;
886                 }
887                 break;
888         case E_UNEQUAL:
889                 if (dep->left.sym == sym) {
890                         if (dep->right.sym == &symbol_no)
891                                 return true;
892                 }
893                 break;
894         default:
895                 ;
896         }
897         return false;
898 }
899
900 /*
901  * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
902  * expression 'e'.
903  *
904  * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
905  *
906  *      A              ->  A!=n
907  *      !A             ->  A=n
908  *      A && B         ->  !(A=n || B=n)
909  *      A || B         ->  !(A=n && B=n)
910  *      A && (B || C)  ->  !(A=n || (B=n && C=n))
911  *
912  * Allocates and returns a new expression.
913  */
914 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
915 {
916         struct expr *e1, *e2;
917
918         if (!e) {
919                 e = expr_alloc_symbol(sym);
920                 if (type == E_UNEQUAL)
921                         e = expr_alloc_one(E_NOT, e);
922                 return e;
923         }
924         switch (e->type) {
925         case E_AND:
926                 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
927                 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
928                 if (sym == &symbol_yes)
929                         e = expr_alloc_two(E_AND, e1, e2);
930                 if (sym == &symbol_no)
931                         e = expr_alloc_two(E_OR, e1, e2);
932                 if (type == E_UNEQUAL)
933                         e = expr_alloc_one(E_NOT, e);
934                 return e;
935         case E_OR:
936                 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
937                 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
938                 if (sym == &symbol_yes)
939                         e = expr_alloc_two(E_OR, e1, e2);
940                 if (sym == &symbol_no)
941                         e = expr_alloc_two(E_AND, e1, e2);
942                 if (type == E_UNEQUAL)
943                         e = expr_alloc_one(E_NOT, e);
944                 return e;
945         case E_NOT:
946                 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
947         case E_UNEQUAL:
948         case E_LTH:
949         case E_LEQ:
950         case E_GTH:
951         case E_GEQ:
952         case E_EQUAL:
953                 if (type == E_EQUAL) {
954                         if (sym == &symbol_yes)
955                                 return expr_copy(e);
956                         if (sym == &symbol_mod)
957                                 return expr_alloc_symbol(&symbol_no);
958                         if (sym == &symbol_no)
959                                 return expr_alloc_one(E_NOT, expr_copy(e));
960                 } else {
961                         if (sym == &symbol_yes)
962                                 return expr_alloc_one(E_NOT, expr_copy(e));
963                         if (sym == &symbol_mod)
964                                 return expr_alloc_symbol(&symbol_yes);
965                         if (sym == &symbol_no)
966                                 return expr_copy(e);
967                 }
968                 break;
969         case E_SYMBOL:
970                 return expr_alloc_comp(type, e->left.sym, sym);
971         case E_LIST:
972         case E_RANGE:
973         case E_NONE:
974                 /* panic */;
975         }
976         return NULL;
977 }
978
979 enum string_value_kind {
980         k_string,
981         k_signed,
982         k_unsigned,
983         k_invalid
984 };
985
986 union string_value {
987         unsigned long long u;
988         signed long long s;
989 };
990
991 static enum string_value_kind expr_parse_string(const char *str,
992                                                 enum symbol_type type,
993                                                 union string_value *val)
994 {
995         char *tail;
996         enum string_value_kind kind;
997
998         errno = 0;
999         switch (type) {
1000         case S_BOOLEAN:
1001         case S_TRISTATE:
1002                 val->s = !strcmp(str, "n") ? 0 :
1003                          !strcmp(str, "m") ? 1 :
1004                          !strcmp(str, "y") ? 2 : -1;
1005                 return k_signed;
1006         case S_INT:
1007                 val->s = strtoll(str, &tail, 10);
1008                 kind = k_signed;
1009                 break;
1010         case S_HEX:
1011                 val->u = strtoull(str, &tail, 16);
1012                 kind = k_unsigned;
1013                 break;
1014         case S_STRING:
1015         case S_UNKNOWN:
1016                 val->s = strtoll(str, &tail, 0);
1017                 kind = k_signed;
1018                 break;
1019         default:
1020                 return k_invalid;
1021         }
1022         return !errno && !*tail && tail > str && isxdigit(tail[-1])
1023                ? kind : k_string;
1024 }
1025
1026 tristate expr_calc_value(struct expr *e)
1027 {
1028         tristate val1, val2;
1029         const char *str1, *str2;
1030         enum string_value_kind k1 = k_string, k2 = k_string;
1031         union string_value lval = {}, rval = {};
1032         int res;
1033
1034         if (!e)
1035                 return yes;
1036
1037         switch (e->type) {
1038         case E_SYMBOL:
1039                 sym_calc_value(e->left.sym);
1040                 return e->left.sym->curr.tri;
1041         case E_AND:
1042                 val1 = expr_calc_value(e->left.expr);
1043                 val2 = expr_calc_value(e->right.expr);
1044                 return EXPR_AND(val1, val2);
1045         case E_OR:
1046                 val1 = expr_calc_value(e->left.expr);
1047                 val2 = expr_calc_value(e->right.expr);
1048                 return EXPR_OR(val1, val2);
1049         case E_NOT:
1050                 val1 = expr_calc_value(e->left.expr);
1051                 return EXPR_NOT(val1);
1052         case E_EQUAL:
1053         case E_GEQ:
1054         case E_GTH:
1055         case E_LEQ:
1056         case E_LTH:
1057         case E_UNEQUAL:
1058                 break;
1059         default:
1060                 printf("expr_calc_value: %d?\n", e->type);
1061                 return no;
1062         }
1063
1064         sym_calc_value(e->left.sym);
1065         sym_calc_value(e->right.sym);
1066         str1 = sym_get_string_value(e->left.sym);
1067         str2 = sym_get_string_value(e->right.sym);
1068
1069         if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
1070                 k1 = expr_parse_string(str1, e->left.sym->type, &lval);
1071                 k2 = expr_parse_string(str2, e->right.sym->type, &rval);
1072         }
1073
1074         if (k1 == k_string || k2 == k_string)
1075                 res = strcmp(str1, str2);
1076         else if (k1 == k_invalid || k2 == k_invalid) {
1077                 if (e->type != E_EQUAL && e->type != E_UNEQUAL) {
1078                         printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2);
1079                         return no;
1080                 }
1081                 res = strcmp(str1, str2);
1082         } else if (k1 == k_unsigned || k2 == k_unsigned)
1083                 res = (lval.u > rval.u) - (lval.u < rval.u);
1084         else /* if (k1 == k_signed && k2 == k_signed) */
1085                 res = (lval.s > rval.s) - (lval.s < rval.s);
1086
1087         switch(e->type) {
1088         case E_EQUAL:
1089                 return res ? no : yes;
1090         case E_GEQ:
1091                 return res >= 0 ? yes : no;
1092         case E_GTH:
1093                 return res > 0 ? yes : no;
1094         case E_LEQ:
1095                 return res <= 0 ? yes : no;
1096         case E_LTH:
1097                 return res < 0 ? yes : no;
1098         case E_UNEQUAL:
1099                 return res ? yes : no;
1100         default:
1101                 printf("expr_calc_value: relation %d?\n", e->type);
1102                 return no;
1103         }
1104 }
1105
1106 static int expr_compare_type(enum expr_type t1, enum expr_type t2)
1107 {
1108         if (t1 == t2)
1109                 return 0;
1110         switch (t1) {
1111         case E_LEQ:
1112         case E_LTH:
1113         case E_GEQ:
1114         case E_GTH:
1115                 if (t2 == E_EQUAL || t2 == E_UNEQUAL)
1116                         return 1;
1117         case E_EQUAL:
1118         case E_UNEQUAL:
1119                 if (t2 == E_NOT)
1120                         return 1;
1121         case E_NOT:
1122                 if (t2 == E_AND)
1123                         return 1;
1124         case E_AND:
1125                 if (t2 == E_OR)
1126                         return 1;
1127         case E_OR:
1128                 if (t2 == E_LIST)
1129                         return 1;
1130         case E_LIST:
1131                 if (t2 == 0)
1132                         return 1;
1133         default:
1134                 return -1;
1135         }
1136         printf("[%dgt%d?]", t1, t2);
1137         return 0;
1138 }
1139
1140 static inline struct expr *
1141 expr_get_leftmost_symbol(const struct expr *e)
1142 {
1143
1144         if (e == NULL)
1145                 return NULL;
1146
1147         while (e->type != E_SYMBOL)
1148                 e = e->left.expr;
1149
1150         return expr_copy(e);
1151 }
1152
1153 /*
1154  * Given expression `e1' and `e2', returns the leaf of the longest
1155  * sub-expression of `e1' not containing 'e2.
1156  */
1157 struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
1158 {
1159         struct expr *ret;
1160
1161         switch (e1->type) {
1162         case E_OR:
1163                 return expr_alloc_and(
1164                     expr_simplify_unmet_dep(e1->left.expr, e2),
1165                     expr_simplify_unmet_dep(e1->right.expr, e2));
1166         case E_AND: {
1167                 struct expr *e;
1168                 e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
1169                 e = expr_eliminate_dups(e);
1170                 ret = (!expr_eq(e, e1)) ? e1 : NULL;
1171                 expr_free(e);
1172                 break;
1173                 }
1174         default:
1175                 ret = e1;
1176                 break;
1177         }
1178
1179         return expr_get_leftmost_symbol(ret);
1180 }
1181
1182 static void __expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken, bool revdep)
1183 {
1184         if (!e) {
1185                 fn(data, NULL, "y");
1186                 return;
1187         }
1188
1189         if (expr_compare_type(prevtoken, e->type) > 0)
1190                 fn(data, NULL, "(");
1191         switch (e->type) {
1192         case E_SYMBOL:
1193                 if (e->left.sym->name)
1194                         fn(data, e->left.sym, e->left.sym->name);
1195                 else
1196                         fn(data, NULL, "<choice>");
1197                 break;
1198         case E_NOT:
1199                 fn(data, NULL, "!");
1200                 expr_print(e->left.expr, fn, data, E_NOT);
1201                 break;
1202         case E_EQUAL:
1203                 if (e->left.sym->name)
1204                         fn(data, e->left.sym, e->left.sym->name);
1205                 else
1206                         fn(data, NULL, "<choice>");
1207                 fn(data, NULL, "=");
1208                 fn(data, e->right.sym, e->right.sym->name);
1209                 break;
1210         case E_LEQ:
1211         case E_LTH:
1212                 if (e->left.sym->name)
1213                         fn(data, e->left.sym, e->left.sym->name);
1214                 else
1215                         fn(data, NULL, "<choice>");
1216                 fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
1217                 fn(data, e->right.sym, e->right.sym->name);
1218                 break;
1219         case E_GEQ:
1220         case E_GTH:
1221                 if (e->left.sym->name)
1222                         fn(data, e->left.sym, e->left.sym->name);
1223                 else
1224                         fn(data, NULL, "<choice>");
1225                 fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
1226                 fn(data, e->right.sym, e->right.sym->name);
1227                 break;
1228         case E_UNEQUAL:
1229                 if (e->left.sym->name)
1230                         fn(data, e->left.sym, e->left.sym->name);
1231                 else
1232                         fn(data, NULL, "<choice>");
1233                 fn(data, NULL, "!=");
1234                 fn(data, e->right.sym, e->right.sym->name);
1235                 break;
1236         case E_OR:
1237                 if (revdep && e->left.expr->type != E_OR)
1238                         fn(data, NULL, "\n  - ");
1239                 __expr_print(e->left.expr, fn, data, E_OR, revdep);
1240                 if (revdep)
1241                         fn(data, NULL, "\n  - ");
1242                 else
1243                         fn(data, NULL, " || ");
1244                 __expr_print(e->right.expr, fn, data, E_OR, revdep);
1245                 break;
1246         case E_AND:
1247                 expr_print(e->left.expr, fn, data, E_AND);
1248                 fn(data, NULL, " && ");
1249                 expr_print(e->right.expr, fn, data, E_AND);
1250                 break;
1251         case E_LIST:
1252                 fn(data, e->right.sym, e->right.sym->name);
1253                 if (e->left.expr) {
1254                         fn(data, NULL, " ^ ");
1255                         expr_print(e->left.expr, fn, data, E_LIST);
1256                 }
1257                 break;
1258         case E_RANGE:
1259                 fn(data, NULL, "[");
1260                 fn(data, e->left.sym, e->left.sym->name);
1261                 fn(data, NULL, " ");
1262                 fn(data, e->right.sym, e->right.sym->name);
1263                 fn(data, NULL, "]");
1264                 break;
1265         default:
1266           {
1267                 char buf[32];
1268                 sprintf(buf, "<unknown type %d>", e->type);
1269                 fn(data, NULL, buf);
1270                 break;
1271           }
1272         }
1273         if (expr_compare_type(prevtoken, e->type) > 0)
1274                 fn(data, NULL, ")");
1275 }
1276
1277 void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1278 {
1279         __expr_print(e, fn, data, prevtoken, false);
1280 }
1281
1282 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1283 {
1284         xfwrite(str, strlen(str), 1, data);
1285 }
1286
1287 void expr_fprint(struct expr *e, FILE *out)
1288 {
1289         expr_print(e, expr_print_file_helper, out, E_NONE);
1290 }
1291
1292 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1293 {
1294         struct gstr *gs = (struct gstr*)data;
1295         const char *sym_str = NULL;
1296
1297         if (sym)
1298                 sym_str = sym_get_string_value(sym);
1299
1300         if (gs->max_width) {
1301                 unsigned extra_length = strlen(str);
1302                 const char *last_cr = strrchr(gs->s, '\n');
1303                 unsigned last_line_length;
1304
1305                 if (sym_str)
1306                         extra_length += 4 + strlen(sym_str);
1307
1308                 if (!last_cr)
1309                         last_cr = gs->s;
1310
1311                 last_line_length = strlen(gs->s) - (last_cr - gs->s);
1312
1313                 if ((last_line_length + extra_length) > gs->max_width)
1314                         str_append(gs, "\\\n");
1315         }
1316
1317         str_append(gs, str);
1318         if (sym && sym->type != S_UNKNOWN)
1319                 str_printf(gs, " [=%s]", sym_str);
1320 }
1321
1322 void expr_gstr_print(struct expr *e, struct gstr *gs)
1323 {
1324         expr_print(e, expr_print_gstr_helper, gs, E_NONE);
1325 }
1326
1327 /*
1328  * Transform the top level "||" tokens into newlines and prepend each
1329  * line with a minus. This makes expressions much easier to read.
1330  * Suitable for reverse dependency expressions.
1331  */
1332 void expr_gstr_print_revdep(struct expr *e, struct gstr *gs)
1333 {
1334         __expr_print(e, expr_print_gstr_helper, gs, E_NONE, true);
1335 }