]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> | |
3 | * Released under the terms of the GNU GPL v2.0. | |
4 | */ | |
5 | ||
6 | #include <stdio.h> | |
7 | #include <stdlib.h> | |
8 | #include <string.h> | |
9 | ||
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 | } |