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