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