diff options
Diffstat (limited to 'scripts/config/expr.c')
-rw-r--r-- | scripts/config/expr.c | 1100 |
1 files changed, 0 insertions, 1100 deletions
diff --git a/scripts/config/expr.c b/scripts/config/expr.c deleted file mode 100644 index 125573e77..000000000 --- a/scripts/config/expr.c +++ /dev/null | |||
@@ -1,1100 +0,0 @@ | |||
1 | /* vi: set sw=4 ts=4: */ | ||
2 | /* | ||
3 | * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> | ||
4 | * Released under the terms of the GNU GPL v2.0. | ||
5 | */ | ||
6 | |||
7 | #include <stdio.h> | ||
8 | #include <stdlib.h> | ||
9 | #include <string.h> | ||
10 | |||
11 | #define LKC_DIRECT_LINK | ||
12 | #include "lkc.h" | ||
13 | |||
14 | #define DEBUG_EXPR 0 | ||
15 | |||
16 | struct expr *expr_alloc_symbol(struct symbol *sym) | ||
17 | { | ||
18 | struct expr *e = malloc(sizeof(*e)); | ||
19 | memset(e, 0, sizeof(*e)); | ||
20 | e->type = E_SYMBOL; | ||
21 | e->left.sym = sym; | ||
22 | return e; | ||
23 | } | ||
24 | |||
25 | struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) | ||
26 | { | ||
27 | struct expr *e = malloc(sizeof(*e)); | ||
28 | memset(e, 0, sizeof(*e)); | ||
29 | e->type = type; | ||
30 | e->left.expr = ce; | ||
31 | return e; | ||
32 | } | ||
33 | |||
34 | struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2) | ||
35 | { | ||
36 | struct expr *e = malloc(sizeof(*e)); | ||
37 | memset(e, 0, sizeof(*e)); | ||
38 | e->type = type; | ||
39 | e->left.expr = e1; | ||
40 | e->right.expr = e2; | ||
41 | return e; | ||
42 | } | ||
43 | |||
44 | struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2) | ||
45 | { | ||
46 | struct expr *e = malloc(sizeof(*e)); | ||
47 | memset(e, 0, sizeof(*e)); | ||
48 | e->type = type; | ||
49 | e->left.sym = s1; | ||
50 | e->right.sym = s2; | ||
51 | return e; | ||
52 | } | ||
53 | |||
54 | struct 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 | |||
61 | struct 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 | |||
68 | struct expr *expr_copy(struct expr *org) | ||
69 | { | ||
70 | struct expr *e; | ||
71 | |||
72 | if (!org) | ||
73 | return NULL; | ||
74 | |||
75 | e = malloc(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_CHOICE: | ||
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 | |||
105 | void 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 | |||
131 | static int trans_count; | ||
132 | |||
133 | #define e1 (*ep1) | ||
134 | #define e2 (*ep2) | ||
135 | |||
136 | static 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 && (e1->left.sym->flags & (SYMBOL_YES|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 *, const char *), void *data, int prevtoken) | ||
1017 | { | ||
1018 | if (!e) { | ||
1019 | fn(data, "y"); | ||
1020 | return; | ||
1021 | } | ||
1022 | |||
1023 | if (expr_compare_type(prevtoken, e->type) > 0) | ||
1024 | fn(data, "("); | ||
1025 | switch (e->type) { | ||
1026 | case E_SYMBOL: | ||
1027 | if (e->left.sym->name) | ||
1028 | fn(data, e->left.sym->name); | ||
1029 | else | ||
1030 | fn(data, "<choice>"); | ||
1031 | break; | ||
1032 | case E_NOT: | ||
1033 | fn(data, "!"); | ||
1034 | expr_print(e->left.expr, fn, data, E_NOT); | ||
1035 | break; | ||
1036 | case E_EQUAL: | ||
1037 | fn(data, e->left.sym->name); | ||
1038 | fn(data, "="); | ||
1039 | fn(data, e->right.sym->name); | ||
1040 | break; | ||
1041 | case E_UNEQUAL: | ||
1042 | fn(data, e->left.sym->name); | ||
1043 | fn(data, "!="); | ||
1044 | fn(data, e->right.sym->name); | ||
1045 | break; | ||
1046 | case E_OR: | ||
1047 | expr_print(e->left.expr, fn, data, E_OR); | ||
1048 | fn(data, " || "); | ||
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, " && "); | ||
1054 | expr_print(e->right.expr, fn, data, E_AND); | ||
1055 | break; | ||
1056 | case E_CHOICE: | ||
1057 | fn(data, e->right.sym->name); | ||
1058 | if (e->left.expr) { | ||
1059 | fn(data, " ^ "); | ||
1060 | expr_print(e->left.expr, fn, data, E_CHOICE); | ||
1061 | } | ||
1062 | break; | ||
1063 | case E_RANGE: | ||
1064 | fn(data, "["); | ||
1065 | fn(data, e->left.sym->name); | ||
1066 | fn(data, " "); | ||
1067 | fn(data, e->right.sym->name); | ||
1068 | fn(data, "]"); | ||
1069 | break; | ||
1070 | default: | ||
1071 | { | ||
1072 | char buf[32]; | ||
1073 | sprintf(buf, "<unknown type %d>", e->type); | ||
1074 | fn(data, buf); | ||
1075 | break; | ||
1076 | } | ||
1077 | } | ||
1078 | if (expr_compare_type(prevtoken, e->type) > 0) | ||
1079 | fn(data, ")"); | ||
1080 | } | ||
1081 | |||
1082 | static void expr_print_file_helper(void *data, 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, 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 | } | ||