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