Root/
Source at commit HEAD created 5 years 6 days ago. By ifabio, Few update to kernelPatcher (Credits to CrazyBirdy) | |
---|---|
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(const 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_LIST:␊ |
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_LIST:␊ |
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_LIST:␊ |
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_LIST:␊ |
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 EXPR_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 EXPR_OR(val1, val2);␊ |
963 | ␉case E_NOT:␊ |
964 | ␉␉val1 = expr_calc_value(e->left.expr);␊ |
965 | ␉␉return EXPR_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_LIST)␊ |
1004 | ␉␉␉return 1;␊ |
1005 | ␉case E_LIST:␊ |
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 | static inline struct expr *␊ |
1017 | expr_get_leftmost_symbol(const struct expr *e)␊ |
1018 | {␊ |
1019 | ␊ |
1020 | ␉if (e == NULL)␊ |
1021 | ␉␉return NULL;␊ |
1022 | ␊ |
1023 | ␉while (e->type != E_SYMBOL)␊ |
1024 | ␉␉e = e->left.expr;␊ |
1025 | ␊ |
1026 | ␉return expr_copy(e);␊ |
1027 | }␊ |
1028 | ␊ |
1029 | /*␊ |
1030 | * Given expression `e1' and `e2', returns the leaf of the longest␊ |
1031 | * sub-expression of `e1' not containing 'e2.␊ |
1032 | */␊ |
1033 | struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)␊ |
1034 | {␊ |
1035 | ␉struct expr *ret;␊ |
1036 | ␊ |
1037 | ␉switch (e1->type) {␊ |
1038 | ␉case E_OR:␊ |
1039 | ␉␉return expr_alloc_and(␊ |
1040 | ␉␉ expr_simplify_unmet_dep(e1->left.expr, e2),␊ |
1041 | ␉␉ expr_simplify_unmet_dep(e1->right.expr, e2));␊ |
1042 | ␉case E_AND: {␊ |
1043 | ␉␉struct expr *e;␊ |
1044 | ␉␉e = expr_alloc_and(expr_copy(e1), expr_copy(e2));␊ |
1045 | ␉␉e = expr_eliminate_dups(e);␊ |
1046 | ␉␉ret = (!expr_eq(e, e1)) ? e1 : NULL;␊ |
1047 | ␉␉expr_free(e);␊ |
1048 | ␉␉break;␊ |
1049 | ␉␉}␊ |
1050 | ␉default:␊ |
1051 | ␉␉ret = e1;␊ |
1052 | ␉␉break;␊ |
1053 | ␉}␊ |
1054 | ␊ |
1055 | ␉return expr_get_leftmost_symbol(ret);␊ |
1056 | }␊ |
1057 | ␊ |
1058 | void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)␊ |
1059 | {␊ |
1060 | ␉if (!e) {␊ |
1061 | ␉␉fn(data, NULL, "y");␊ |
1062 | ␉␉return;␊ |
1063 | ␉}␊ |
1064 | ␊ |
1065 | ␉if (expr_compare_type(prevtoken, e->type) > 0)␊ |
1066 | ␉␉fn(data, NULL, "(");␊ |
1067 | ␉switch (e->type) {␊ |
1068 | ␉case E_SYMBOL:␊ |
1069 | ␉␉if (e->left.sym->name)␊ |
1070 | ␉␉␉fn(data, e->left.sym, e->left.sym->name);␊ |
1071 | ␉␉else␊ |
1072 | ␉␉␉fn(data, NULL, "<choice>");␊ |
1073 | ␉␉break;␊ |
1074 | ␉case E_NOT:␊ |
1075 | ␉␉fn(data, NULL, "!");␊ |
1076 | ␉␉expr_print(e->left.expr, fn, data, E_NOT);␊ |
1077 | ␉␉break;␊ |
1078 | ␉case E_EQUAL:␊ |
1079 | ␉␉if (e->left.sym->name)␊ |
1080 | ␉␉␉fn(data, e->left.sym, e->left.sym->name);␊ |
1081 | ␉␉else␊ |
1082 | ␉␉␉fn(data, NULL, "<choice>");␊ |
1083 | ␉␉fn(data, NULL, "=");␊ |
1084 | ␉␉fn(data, e->right.sym, e->right.sym->name);␊ |
1085 | ␉␉break;␊ |
1086 | ␉case E_UNEQUAL:␊ |
1087 | ␉␉if (e->left.sym->name)␊ |
1088 | ␉␉␉fn(data, e->left.sym, e->left.sym->name);␊ |
1089 | ␉␉else␊ |
1090 | ␉␉␉fn(data, NULL, "<choice>");␊ |
1091 | ␉␉fn(data, NULL, "!=");␊ |
1092 | ␉␉fn(data, e->right.sym, e->right.sym->name);␊ |
1093 | ␉␉break;␊ |
1094 | ␉case E_OR:␊ |
1095 | ␉␉expr_print(e->left.expr, fn, data, E_OR);␊ |
1096 | ␉␉fn(data, NULL, " || ");␊ |
1097 | ␉␉expr_print(e->right.expr, fn, data, E_OR);␊ |
1098 | ␉␉break;␊ |
1099 | ␉case E_AND:␊ |
1100 | ␉␉expr_print(e->left.expr, fn, data, E_AND);␊ |
1101 | ␉␉fn(data, NULL, " && ");␊ |
1102 | ␉␉expr_print(e->right.expr, fn, data, E_AND);␊ |
1103 | ␉␉break;␊ |
1104 | ␉case E_LIST:␊ |
1105 | ␉␉fn(data, e->right.sym, e->right.sym->name);␊ |
1106 | ␉␉if (e->left.expr) {␊ |
1107 | ␉␉␉fn(data, NULL, " ^ ");␊ |
1108 | ␉␉␉expr_print(e->left.expr, fn, data, E_LIST);␊ |
1109 | ␉␉}␊ |
1110 | ␉␉break;␊ |
1111 | ␉case E_RANGE:␊ |
1112 | ␉␉fn(data, NULL, "[");␊ |
1113 | ␉␉fn(data, e->left.sym, e->left.sym->name);␊ |
1114 | ␉␉fn(data, NULL, " ");␊ |
1115 | ␉␉fn(data, e->right.sym, e->right.sym->name);␊ |
1116 | ␉␉fn(data, NULL, "]");␊ |
1117 | ␉␉break;␊ |
1118 | ␉default:␊ |
1119 | ␉ {␊ |
1120 | ␉␉char buf[32];␊ |
1121 | ␉␉sprintf(buf, "<unknown type %d>", e->type);␊ |
1122 | ␉␉fn(data, NULL, buf);␊ |
1123 | ␉␉break;␊ |
1124 | ␉ }␊ |
1125 | ␉}␊ |
1126 | ␉if (expr_compare_type(prevtoken, e->type) > 0)␊ |
1127 | ␉␉fn(data, NULL, ")");␊ |
1128 | }␊ |
1129 | ␊ |
1130 | static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)␊ |
1131 | {␊ |
1132 | ␉xfwrite(str, strlen(str), 1, data);␊ |
1133 | }␊ |
1134 | ␊ |
1135 | void expr_fprint(struct expr *e, FILE *out)␊ |
1136 | {␊ |
1137 | ␉expr_print(e, expr_print_file_helper, out, E_NONE);␊ |
1138 | }␊ |
1139 | ␊ |
1140 | static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)␊ |
1141 | {␊ |
1142 | ␉struct gstr *gs = (struct gstr*)data;␊ |
1143 | ␉const char *sym_str = NULL;␊ |
1144 | ␊ |
1145 | ␉if (sym)␊ |
1146 | ␉␉sym_str = sym_get_string_value(sym);␊ |
1147 | ␊ |
1148 | ␉if (gs->max_width) {␊ |
1149 | ␉␉unsigned extra_length = strlen(str);␊ |
1150 | ␉␉const char *last_cr = strrchr(gs->s, '\n');␊ |
1151 | ␉␉unsigned last_line_length;␊ |
1152 | ␊ |
1153 | ␉␉if (sym_str)␊ |
1154 | ␉␉␉extra_length += 4 + strlen(sym_str);␊ |
1155 | ␊ |
1156 | ␉␉if (!last_cr)␊ |
1157 | ␉␉␉last_cr = gs->s;␊ |
1158 | ␊ |
1159 | ␉␉last_line_length = strlen(gs->s) - (last_cr - gs->s);␊ |
1160 | ␊ |
1161 | ␉␉if ((last_line_length + extra_length) > gs->max_width)␊ |
1162 | ␉␉␉str_append(gs, "\\\n");␊ |
1163 | ␉}␊ |
1164 | ␊ |
1165 | ␉str_append(gs, str);␊ |
1166 | ␉if (sym && sym->type != S_UNKNOWN)␊ |
1167 | ␉␉str_printf(gs, " [=%s]", sym_str);␊ |
1168 | }␊ |
1169 | ␊ |
1170 | void expr_gstr_print(struct expr *e, struct gstr *gs)␊ |
1171 | {␊ |
1172 | ␉expr_print(e, expr_print_gstr_helper, gs, E_NONE);␊ |
1173 | }␊ |
1174 |