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 | static 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 | static 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 | if (e->left.sym->name) |
1038 | fn(data, e->left.sym, e->left.sym->name); |
1039 | else |
1040 | fn(data, NULL, "<choice>"); |
1041 | fn(data, NULL, "="); |
1042 | fn(data, e->right.sym, e->right.sym->name); |
1043 | break; |
1044 | case E_UNEQUAL: |
1045 | if (e->left.sym->name) |
1046 | fn(data, e->left.sym, e->left.sym->name); |
1047 | else |
1048 | fn(data, NULL, "<choice>"); |
1049 | fn(data, NULL, "!="); |
1050 | fn(data, e->right.sym, e->right.sym->name); |
1051 | break; |
1052 | case E_OR: |
1053 | expr_print(e->left.expr, fn, data, E_OR); |
1054 | fn(data, NULL, " || "); |
1055 | expr_print(e->right.expr, fn, data, E_OR); |
1056 | break; |
1057 | case E_AND: |
1058 | expr_print(e->left.expr, fn, data, E_AND); |
1059 | fn(data, NULL, " && "); |
1060 | expr_print(e->right.expr, fn, data, E_AND); |
1061 | break; |
1062 | case E_CHOICE: |
1063 | fn(data, e->right.sym, e->right.sym->name); |
1064 | if (e->left.expr) { |
1065 | fn(data, NULL, " ^ "); |
1066 | expr_print(e->left.expr, fn, data, E_CHOICE); |
1067 | } |
1068 | break; |
1069 | case E_RANGE: |
1070 | fn(data, NULL, "["); |
1071 | fn(data, e->left.sym, e->left.sym->name); |
1072 | fn(data, NULL, " "); |
1073 | fn(data, e->right.sym, e->right.sym->name); |
1074 | fn(data, NULL, "]"); |
1075 | break; |
1076 | default: |
1077 | { |
1078 | char buf[32]; |
1079 | sprintf(buf, "<unknown type %d>", e->type); |
1080 | fn(data, NULL, buf); |
1081 | break; |
1082 | } |
1083 | } |
1084 | if (expr_compare_type(prevtoken, e->type) > 0) |
1085 | fn(data, NULL, ")"); |
1086 | } |
1087 | |
1088 | static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) |
1089 | { |
1090 | fwrite(str, strlen(str), 1, data); |
1091 | } |
1092 | |
1093 | void expr_fprint(struct expr *e, FILE *out) |
1094 | { |
1095 | expr_print(e, expr_print_file_helper, out, E_NONE); |
1096 | } |
1097 | |
1098 | static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) |
1099 | { |
1100 | struct gstr *gs = (struct gstr*)data; |
1101 | const char *sym_str = NULL; |
1102 | |
1103 | if (sym) |
1104 | sym_str = sym_get_string_value(sym); |
1105 | |
1106 | if (gs->max_width) { |
1107 | unsigned extra_length = strlen(str); |
1108 | const char *last_cr = strrchr(gs->s, '\n'); |
1109 | unsigned last_line_length; |
1110 | |
1111 | if (sym_str) |
1112 | extra_length += 4 + strlen(sym_str); |
1113 | |
1114 | if (!last_cr) |
1115 | last_cr = gs->s; |
1116 | |
1117 | last_line_length = strlen(gs->s) - (last_cr - gs->s); |
1118 | |
1119 | if ((last_line_length + extra_length) > gs->max_width) |
1120 | str_append(gs, "\\\n"); |
1121 | } |
1122 | |
1123 | str_append(gs, str); |
1124 | if (sym && sym->type != S_UNKNOWN) |
1125 | str_printf(gs, " [=%s]", sym_str); |
1126 | } |
1127 | |
1128 | void expr_gstr_print(struct expr *e, struct gstr *gs) |
1129 | { |
1130 | expr_print(e, expr_print_gstr_helper, gs, E_NONE); |
1131 | } |
1132 | |