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