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