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