]>
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: | |
7a962923 | 90 | case E_LIST: |
1da177e4 LT |
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 && | |
c0e150ac RZ |
148 | e1->left.sym == e2->left.sym && |
149 | (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) | |
1da177e4 LT |
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; | |
7a962923 | 220 | case E_LIST: |
1da177e4 LT |
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: | |
7a962923 | 651 | case E_LIST: |
1da177e4 LT |
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); | |
7a962923 | 935 | case E_LIST: |
1da177e4 LT |
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); | |
d6ee3576 | 958 | return EXPR_AND(val1, val2); |
1da177e4 LT |
959 | case E_OR: |
960 | val1 = expr_calc_value(e->left.expr); | |
961 | val2 = expr_calc_value(e->right.expr); | |
d6ee3576 | 962 | return EXPR_OR(val1, val2); |
1da177e4 LT |
963 | case E_NOT: |
964 | val1 = expr_calc_value(e->left.expr); | |
d6ee3576 | 965 | return EXPR_NOT(val1); |
1da177e4 LT |
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: | |
7a962923 | 1003 | if (t2 == E_LIST) |
1da177e4 | 1004 | return 1; |
7a962923 | 1005 | case E_LIST: |
1da177e4 LT |
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 | ||
ab45d190 | 1016 | void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken) |
1da177e4 LT |
1017 | { |
1018 | if (!e) { | |
ab45d190 | 1019 | fn(data, NULL, "y"); |
1da177e4 LT |
1020 | return; |
1021 | } | |
1022 | ||
1023 | if (expr_compare_type(prevtoken, e->type) > 0) | |
ab45d190 | 1024 | fn(data, NULL, "("); |
1da177e4 LT |
1025 | switch (e->type) { |
1026 | case E_SYMBOL: | |
1027 | if (e->left.sym->name) | |
ab45d190 | 1028 | fn(data, e->left.sym, e->left.sym->name); |
1da177e4 | 1029 | else |
ab45d190 | 1030 | fn(data, NULL, "<choice>"); |
1da177e4 LT |
1031 | break; |
1032 | case E_NOT: | |
ab45d190 | 1033 | fn(data, NULL, "!"); |
1da177e4 LT |
1034 | expr_print(e->left.expr, fn, data, E_NOT); |
1035 | break; | |
1036 | case E_EQUAL: | |
f5eaa323 JB |
1037 | if (e->left.sym->name) |
1038 | fn(data, e->left.sym, e->left.sym->name); | |
1039 | else | |
1040 | fn(data, NULL, "<choice>"); | |
ab45d190 RZ |
1041 | fn(data, NULL, "="); |
1042 | fn(data, e->right.sym, e->right.sym->name); | |
1da177e4 LT |
1043 | break; |
1044 | case E_UNEQUAL: | |
f5eaa323 JB |
1045 | if (e->left.sym->name) |
1046 | fn(data, e->left.sym, e->left.sym->name); | |
1047 | else | |
1048 | fn(data, NULL, "<choice>"); | |
ab45d190 RZ |
1049 | fn(data, NULL, "!="); |
1050 | fn(data, e->right.sym, e->right.sym->name); | |
1da177e4 LT |
1051 | break; |
1052 | case E_OR: | |
1053 | expr_print(e->left.expr, fn, data, E_OR); | |
ab45d190 | 1054 | fn(data, NULL, " || "); |
1da177e4 LT |
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); | |
ab45d190 | 1059 | fn(data, NULL, " && "); |
1da177e4 LT |
1060 | expr_print(e->right.expr, fn, data, E_AND); |
1061 | break; | |
7a962923 | 1062 | case E_LIST: |
ab45d190 | 1063 | fn(data, e->right.sym, e->right.sym->name); |
1da177e4 | 1064 | if (e->left.expr) { |
ab45d190 | 1065 | fn(data, NULL, " ^ "); |
7a962923 | 1066 | expr_print(e->left.expr, fn, data, E_LIST); |
1da177e4 LT |
1067 | } |
1068 | break; | |
1069 | case E_RANGE: | |
ab45d190 RZ |
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, "]"); | |
1da177e4 LT |
1075 | break; |
1076 | default: | |
1077 | { | |
1078 | char buf[32]; | |
1079 | sprintf(buf, "<unknown type %d>", e->type); | |
ab45d190 | 1080 | fn(data, NULL, buf); |
1da177e4 LT |
1081 | break; |
1082 | } | |
1083 | } | |
1084 | if (expr_compare_type(prevtoken, e->type) > 0) | |
ab45d190 | 1085 | fn(data, NULL, ")"); |
1da177e4 LT |
1086 | } |
1087 | ||
ab45d190 | 1088 | static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) |
1da177e4 LT |
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 | ||
ab45d190 | 1098 | static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) |
1da177e4 LT |
1099 | { |
1100 | str_append((struct gstr*)data, str); | |
544e433a CR |
1101 | if (sym) |
1102 | str_printf((struct gstr*)data, " [=%s]", sym_get_string_value(sym)); | |
1da177e4 LT |
1103 | } |
1104 | ||
1105 | void expr_gstr_print(struct expr *e, struct gstr *gs) | |
1106 | { | |
1107 | expr_print(e, expr_print_gstr_helper, gs, E_NONE); | |
1108 | } |