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