Commit | Line | Data |
---|---|---|
0c874100 | 1 | // SPDX-License-Identifier: GPL-2.0 |
1da177e4 LT |
2 | /* |
3 | * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> | |
1da177e4 LT |
4 | */ |
5 | ||
558e78e3 MY |
6 | #include <ctype.h> |
7 | #include <errno.h> | |
1da177e4 LT |
8 | #include <stdio.h> |
9 | #include <stdlib.h> | |
10 | #include <string.h> | |
11 | ||
1da177e4 LT |
12 | #include "lkc.h" |
13 | ||
14 | #define DEBUG_EXPR 0 | |
15 | ||
ad8d40cd MM |
16 | static int expr_eq(struct expr *e1, struct expr *e2); |
17 | static struct expr *expr_eliminate_yn(struct expr *e); | |
ad8d40cd | 18 | |
1da177e4 LT |
19 | struct expr *expr_alloc_symbol(struct symbol *sym) |
20 | { | |
177acf78 | 21 | struct expr *e = xcalloc(1, sizeof(*e)); |
1da177e4 LT |
22 | e->type = E_SYMBOL; |
23 | e->left.sym = sym; | |
24 | return e; | |
25 | } | |
26 | ||
27 | struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) | |
28 | { | |
177acf78 | 29 | struct expr *e = xcalloc(1, sizeof(*e)); |
1da177e4 LT |
30 | e->type = type; |
31 | e->left.expr = ce; | |
32 | return e; | |
33 | } | |
34 | ||
35 | struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2) | |
36 | { | |
177acf78 | 37 | struct expr *e = xcalloc(1, sizeof(*e)); |
1da177e4 LT |
38 | e->type = type; |
39 | e->left.expr = e1; | |
40 | e->right.expr = e2; | |
41 | return e; | |
42 | } | |
43 | ||
44 | struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2) | |
45 | { | |
177acf78 | 46 | struct expr *e = xcalloc(1, sizeof(*e)); |
1da177e4 LT |
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 | ||
17742dc7 | 67 | struct expr *expr_copy(const struct expr *org) |
1da177e4 LT |
68 | { |
69 | struct expr *e; | |
70 | ||
71 | if (!org) | |
72 | return NULL; | |
73 | ||
177acf78 | 74 | e = xmalloc(sizeof(*org)); |
1da177e4 LT |
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: | |
31847b67 JB |
84 | case E_GEQ: |
85 | case E_GTH: | |
86 | case E_LEQ: | |
87 | case E_LTH: | |
1da177e4 LT |
88 | case E_UNEQUAL: |
89 | e->left.sym = org->left.sym; | |
90 | e->right.sym = org->right.sym; | |
91 | break; | |
92 | case E_AND: | |
93 | case E_OR: | |
7a962923 | 94 | case E_LIST: |
1da177e4 LT |
95 | e->left.expr = expr_copy(org->left.expr); |
96 | e->right.expr = expr_copy(org->right.expr); | |
97 | break; | |
98 | default: | |
9e3e10c7 | 99 | fprintf(stderr, "can't copy type %d\n", e->type); |
1da177e4 LT |
100 | free(e); |
101 | e = NULL; | |
102 | break; | |
103 | } | |
104 | ||
105 | return e; | |
106 | } | |
107 | ||
108 | void expr_free(struct expr *e) | |
109 | { | |
110 | if (!e) | |
111 | return; | |
112 | ||
113 | switch (e->type) { | |
114 | case E_SYMBOL: | |
115 | break; | |
116 | case E_NOT: | |
117 | expr_free(e->left.expr); | |
5b1374b3 | 118 | break; |
1da177e4 | 119 | case E_EQUAL: |
31847b67 JB |
120 | case E_GEQ: |
121 | case E_GTH: | |
122 | case E_LEQ: | |
123 | case E_LTH: | |
1da177e4 LT |
124 | case E_UNEQUAL: |
125 | break; | |
126 | case E_OR: | |
127 | case E_AND: | |
128 | expr_free(e->left.expr); | |
129 | expr_free(e->right.expr); | |
130 | break; | |
131 | default: | |
9e3e10c7 | 132 | fprintf(stderr, "how to free type %d?\n", e->type); |
1da177e4 LT |
133 | break; |
134 | } | |
135 | free(e); | |
136 | } | |
137 | ||
138 | static int trans_count; | |
139 | ||
140 | #define e1 (*ep1) | |
141 | #define e2 (*ep2) | |
142 | ||
0735f7e5 UM |
143 | /* |
144 | * expr_eliminate_eq() helper. | |
145 | * | |
146 | * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does | |
147 | * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared | |
148 | * against all other leaves. Two equal leaves are both replaced with either 'y' | |
149 | * or 'n' as appropriate for 'type', to be eliminated later. | |
150 | */ | |
1da177e4 LT |
151 | static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) |
152 | { | |
0735f7e5 UM |
153 | /* Recurse down to leaves */ |
154 | ||
1da177e4 LT |
155 | if (e1->type == type) { |
156 | __expr_eliminate_eq(type, &e1->left.expr, &e2); | |
157 | __expr_eliminate_eq(type, &e1->right.expr, &e2); | |
158 | return; | |
159 | } | |
160 | if (e2->type == type) { | |
161 | __expr_eliminate_eq(type, &e1, &e2->left.expr); | |
162 | __expr_eliminate_eq(type, &e1, &e2->right.expr); | |
163 | return; | |
164 | } | |
0735f7e5 UM |
165 | |
166 | /* e1 and e2 are leaves. Compare them. */ | |
167 | ||
1da177e4 | 168 | if (e1->type == E_SYMBOL && e2->type == E_SYMBOL && |
c0e150ac RZ |
169 | e1->left.sym == e2->left.sym && |
170 | (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) | |
1da177e4 LT |
171 | return; |
172 | if (!expr_eq(e1, e2)) | |
173 | return; | |
0735f7e5 UM |
174 | |
175 | /* e1 and e2 are equal leaves. Prepare them for elimination. */ | |
176 | ||
1da177e4 LT |
177 | trans_count++; |
178 | expr_free(e1); expr_free(e2); | |
179 | switch (type) { | |
180 | case E_OR: | |
181 | e1 = expr_alloc_symbol(&symbol_no); | |
182 | e2 = expr_alloc_symbol(&symbol_no); | |
183 | break; | |
184 | case E_AND: | |
185 | e1 = expr_alloc_symbol(&symbol_yes); | |
186 | e2 = expr_alloc_symbol(&symbol_yes); | |
187 | break; | |
188 | default: | |
189 | ; | |
190 | } | |
191 | } | |
192 | ||
0735f7e5 UM |
193 | /* |
194 | * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both. | |
195 | * Example reductions: | |
196 | * | |
197 | * ep1: A && B -> ep1: y | |
198 | * ep2: A && B && C -> ep2: C | |
199 | * | |
200 | * ep1: A || B -> ep1: n | |
201 | * ep2: A || B || C -> ep2: C | |
202 | * | |
203 | * ep1: A && (B && FOO) -> ep1: FOO | |
204 | * ep2: (BAR && B) && A -> ep2: BAR | |
205 | * | |
206 | * ep1: A && (B || C) -> ep1: y | |
207 | * ep2: (C || B) && A -> ep2: y | |
208 | * | |
209 | * Comparisons are done between all operands at the same "level" of && or ||. | |
210 | * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the | |
211 | * following operands will be compared: | |
212 | * | |
213 | * - 'e1', 'e2 || e3', and 'e4 || e5', against each other | |
214 | * - e2 against e3 | |
215 | * - e4 against e5 | |
216 | * | |
217 | * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and | |
218 | * '(e1 && e2) && e3' are both a single level. | |
219 | * | |
220 | * See __expr_eliminate_eq() as well. | |
221 | */ | |
1da177e4 LT |
222 | void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) |
223 | { | |
224 | if (!e1 || !e2) | |
225 | return; | |
226 | switch (e1->type) { | |
227 | case E_OR: | |
228 | case E_AND: | |
229 | __expr_eliminate_eq(e1->type, ep1, ep2); | |
230 | default: | |
231 | ; | |
232 | } | |
233 | if (e1->type != e2->type) switch (e2->type) { | |
234 | case E_OR: | |
235 | case E_AND: | |
236 | __expr_eliminate_eq(e2->type, ep1, ep2); | |
237 | default: | |
238 | ; | |
239 | } | |
240 | e1 = expr_eliminate_yn(e1); | |
241 | e2 = expr_eliminate_yn(e2); | |
242 | } | |
243 | ||
244 | #undef e1 | |
245 | #undef e2 | |
246 | ||
0735f7e5 UM |
247 | /* |
248 | * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two | |
249 | * &&/|| expressions are considered equal if every operand in one expression | |
250 | * equals some operand in the other (operands do not need to appear in the same | |
251 | * order), recursively. | |
252 | */ | |
ad8d40cd | 253 | static int expr_eq(struct expr *e1, struct expr *e2) |
1da177e4 LT |
254 | { |
255 | int res, old_count; | |
256 | ||
257 | if (e1->type != e2->type) | |
258 | return 0; | |
259 | switch (e1->type) { | |
260 | case E_EQUAL: | |
31847b67 JB |
261 | case E_GEQ: |
262 | case E_GTH: | |
263 | case E_LEQ: | |
264 | case E_LTH: | |
1da177e4 LT |
265 | case E_UNEQUAL: |
266 | return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym; | |
267 | case E_SYMBOL: | |
268 | return e1->left.sym == e2->left.sym; | |
269 | case E_NOT: | |
270 | return expr_eq(e1->left.expr, e2->left.expr); | |
271 | case E_AND: | |
272 | case E_OR: | |
273 | e1 = expr_copy(e1); | |
274 | e2 = expr_copy(e2); | |
275 | old_count = trans_count; | |
276 | expr_eliminate_eq(&e1, &e2); | |
277 | res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL && | |
278 | e1->left.sym == e2->left.sym); | |
279 | expr_free(e1); | |
280 | expr_free(e2); | |
281 | trans_count = old_count; | |
282 | return res; | |
7a962923 | 283 | case E_LIST: |
1da177e4 LT |
284 | case E_RANGE: |
285 | case E_NONE: | |
286 | /* panic */; | |
287 | } | |
288 | ||
289 | if (DEBUG_EXPR) { | |
290 | expr_fprint(e1, stdout); | |
291 | printf(" = "); | |
292 | expr_fprint(e2, stdout); | |
293 | printf(" ?\n"); | |
294 | } | |
295 | ||
296 | return 0; | |
297 | } | |
298 | ||
0735f7e5 UM |
299 | /* |
300 | * Recursively performs the following simplifications in-place (as well as the | |
301 | * corresponding simplifications with swapped operands): | |
302 | * | |
303 | * expr && n -> n | |
304 | * expr && y -> expr | |
305 | * expr || n -> expr | |
306 | * expr || y -> y | |
307 | * | |
308 | * Returns the optimized expression. | |
309 | */ | |
ad8d40cd | 310 | static struct expr *expr_eliminate_yn(struct expr *e) |
1da177e4 LT |
311 | { |
312 | struct expr *tmp; | |
313 | ||
314 | if (e) switch (e->type) { | |
315 | case E_AND: | |
316 | e->left.expr = expr_eliminate_yn(e->left.expr); | |
317 | e->right.expr = expr_eliminate_yn(e->right.expr); | |
318 | if (e->left.expr->type == E_SYMBOL) { | |
319 | if (e->left.expr->left.sym == &symbol_no) { | |
320 | expr_free(e->left.expr); | |
321 | expr_free(e->right.expr); | |
322 | e->type = E_SYMBOL; | |
323 | e->left.sym = &symbol_no; | |
324 | e->right.expr = NULL; | |
325 | return e; | |
326 | } else if (e->left.expr->left.sym == &symbol_yes) { | |
327 | free(e->left.expr); | |
328 | tmp = e->right.expr; | |
329 | *e = *(e->right.expr); | |
330 | free(tmp); | |
331 | return e; | |
332 | } | |
333 | } | |
334 | if (e->right.expr->type == E_SYMBOL) { | |
335 | if (e->right.expr->left.sym == &symbol_no) { | |
336 | expr_free(e->left.expr); | |
337 | expr_free(e->right.expr); | |
338 | e->type = E_SYMBOL; | |
339 | e->left.sym = &symbol_no; | |
340 | e->right.expr = NULL; | |
341 | return e; | |
342 | } else if (e->right.expr->left.sym == &symbol_yes) { | |
343 | free(e->right.expr); | |
344 | tmp = e->left.expr; | |
345 | *e = *(e->left.expr); | |
346 | free(tmp); | |
347 | return e; | |
348 | } | |
349 | } | |
350 | break; | |
351 | case E_OR: | |
352 | e->left.expr = expr_eliminate_yn(e->left.expr); | |
353 | e->right.expr = expr_eliminate_yn(e->right.expr); | |
354 | if (e->left.expr->type == E_SYMBOL) { | |
355 | if (e->left.expr->left.sym == &symbol_no) { | |
356 | free(e->left.expr); | |
357 | tmp = e->right.expr; | |
358 | *e = *(e->right.expr); | |
359 | free(tmp); | |
360 | return e; | |
361 | } else if (e->left.expr->left.sym == &symbol_yes) { | |
362 | expr_free(e->left.expr); | |
363 | expr_free(e->right.expr); | |
364 | e->type = E_SYMBOL; | |
365 | e->left.sym = &symbol_yes; | |
366 | e->right.expr = NULL; | |
367 | return e; | |
368 | } | |
369 | } | |
370 | if (e->right.expr->type == E_SYMBOL) { | |
371 | if (e->right.expr->left.sym == &symbol_no) { | |
372 | free(e->right.expr); | |
373 | tmp = e->left.expr; | |
374 | *e = *(e->left.expr); | |
375 | free(tmp); | |
376 | return e; | |
377 | } else if (e->right.expr->left.sym == &symbol_yes) { | |
378 | expr_free(e->left.expr); | |
379 | expr_free(e->right.expr); | |
380 | e->type = E_SYMBOL; | |
381 | e->left.sym = &symbol_yes; | |
382 | e->right.expr = NULL; | |
383 | return e; | |
384 | } | |
385 | } | |
386 | break; | |
387 | default: | |
388 | ; | |
389 | } | |
390 | return e; | |
391 | } | |
392 | ||
393 | /* | |
394 | * bool FOO!=n => FOO | |
395 | */ | |
396 | struct expr *expr_trans_bool(struct expr *e) | |
397 | { | |
398 | if (!e) | |
399 | return NULL; | |
400 | switch (e->type) { | |
401 | case E_AND: | |
402 | case E_OR: | |
403 | case E_NOT: | |
404 | e->left.expr = expr_trans_bool(e->left.expr); | |
405 | e->right.expr = expr_trans_bool(e->right.expr); | |
406 | break; | |
407 | case E_UNEQUAL: | |
408 | // FOO!=n -> FOO | |
409 | if (e->left.sym->type == S_TRISTATE) { | |
410 | if (e->right.sym == &symbol_no) { | |
411 | e->type = E_SYMBOL; | |
412 | e->right.sym = NULL; | |
413 | } | |
414 | } | |
415 | break; | |
416 | default: | |
417 | ; | |
418 | } | |
419 | return e; | |
420 | } | |
421 | ||
422 | /* | |
423 | * e1 || e2 -> ? | |
424 | */ | |
4356f489 | 425 | static struct expr *expr_join_or(struct expr *e1, struct expr *e2) |
1da177e4 LT |
426 | { |
427 | struct expr *tmp; | |
428 | struct symbol *sym1, *sym2; | |
429 | ||
430 | if (expr_eq(e1, e2)) | |
431 | return expr_copy(e1); | |
432 | if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) | |
433 | return NULL; | |
434 | if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) | |
435 | return NULL; | |
436 | if (e1->type == E_NOT) { | |
437 | tmp = e1->left.expr; | |
438 | if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) | |
439 | return NULL; | |
440 | sym1 = tmp->left.sym; | |
441 | } else | |
442 | sym1 = e1->left.sym; | |
443 | if (e2->type == E_NOT) { | |
444 | if (e2->left.expr->type != E_SYMBOL) | |
445 | return NULL; | |
446 | sym2 = e2->left.expr->left.sym; | |
447 | } else | |
448 | sym2 = e2->left.sym; | |
449 | if (sym1 != sym2) | |
450 | return NULL; | |
451 | if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) | |
452 | return NULL; | |
453 | if (sym1->type == S_TRISTATE) { | |
454 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && | |
455 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || | |
456 | (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) { | |
457 | // (a='y') || (a='m') -> (a!='n') | |
458 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no); | |
459 | } | |
460 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && | |
461 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || | |
462 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) { | |
463 | // (a='y') || (a='n') -> (a!='m') | |
464 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod); | |
465 | } | |
466 | if (e1->type == E_EQUAL && e2->type == E_EQUAL && | |
467 | ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || | |
468 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) { | |
469 | // (a='m') || (a='n') -> (a!='y') | |
470 | return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes); | |
471 | } | |
472 | } | |
473 | if (sym1->type == S_BOOLEAN && sym1 == sym2) { | |
474 | if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) || | |
475 | (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL)) | |
476 | return expr_alloc_symbol(&symbol_yes); | |
477 | } | |
478 | ||
479 | if (DEBUG_EXPR) { | |
480 | printf("optimize ("); | |
481 | expr_fprint(e1, stdout); | |
482 | printf(") || ("); | |
483 | expr_fprint(e2, stdout); | |
484 | printf(")?\n"); | |
485 | } | |
486 | return NULL; | |
487 | } | |
488 | ||
4356f489 | 489 | static struct expr *expr_join_and(struct expr *e1, struct expr *e2) |
1da177e4 LT |
490 | { |
491 | struct expr *tmp; | |
492 | struct symbol *sym1, *sym2; | |
493 | ||
494 | if (expr_eq(e1, e2)) | |
495 | return expr_copy(e1); | |
496 | if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) | |
497 | return NULL; | |
498 | if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) | |
499 | return NULL; | |
500 | if (e1->type == E_NOT) { | |
501 | tmp = e1->left.expr; | |
502 | if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) | |
503 | return NULL; | |
504 | sym1 = tmp->left.sym; | |
505 | } else | |
506 | sym1 = e1->left.sym; | |
507 | if (e2->type == E_NOT) { | |
508 | if (e2->left.expr->type != E_SYMBOL) | |
509 | return NULL; | |
510 | sym2 = e2->left.expr->left.sym; | |
511 | } else | |
512 | sym2 = e2->left.sym; | |
513 | if (sym1 != sym2) | |
514 | return NULL; | |
515 | if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) | |
516 | return NULL; | |
517 | ||
518 | if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) || | |
519 | (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes)) | |
520 | // (a) && (a='y') -> (a='y') | |
521 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); | |
522 | ||
523 | if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) || | |
524 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no)) | |
525 | // (a) && (a!='n') -> (a) | |
526 | return expr_alloc_symbol(sym1); | |
527 | ||
528 | if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) || | |
529 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod)) | |
530 | // (a) && (a!='m') -> (a='y') | |
531 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); | |
532 | ||
533 | if (sym1->type == S_TRISTATE) { | |
534 | if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) { | |
535 | // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' | |
536 | sym2 = e1->right.sym; | |
537 | if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) | |
538 | return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) | |
539 | : expr_alloc_symbol(&symbol_no); | |
540 | } | |
541 | if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) { | |
542 | // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b' | |
543 | sym2 = e2->right.sym; | |
544 | if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST)) | |
545 | return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2) | |
546 | : expr_alloc_symbol(&symbol_no); | |
547 | } | |
548 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && | |
549 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || | |
550 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) | |
551 | // (a!='y') && (a!='n') -> (a='m') | |
552 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod); | |
553 | ||
554 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && | |
555 | ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || | |
556 | (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) | |
557 | // (a!='y') && (a!='m') -> (a='n') | |
558 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_no); | |
559 | ||
560 | if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL && | |
561 | ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || | |
562 | (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) | |
563 | // (a!='m') && (a!='n') -> (a='m') | |
564 | return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); | |
565 | ||
566 | if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) || | |
567 | (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) || | |
568 | (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) || | |
569 | (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes)) | |
570 | return NULL; | |
571 | } | |
572 | ||
573 | if (DEBUG_EXPR) { | |
574 | printf("optimize ("); | |
575 | expr_fprint(e1, stdout); | |
576 | printf(") && ("); | |
577 | expr_fprint(e2, stdout); | |
578 | printf(")?\n"); | |
579 | } | |
580 | return NULL; | |
581 | } | |
582 | ||
0735f7e5 UM |
583 | /* |
584 | * expr_eliminate_dups() helper. | |
585 | * | |
586 | * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does | |
587 | * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared | |
588 | * against all other leaves to look for simplifications. | |
589 | */ | |
1da177e4 LT |
590 | static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2) |
591 | { | |
592 | #define e1 (*ep1) | |
593 | #define e2 (*ep2) | |
594 | struct expr *tmp; | |
595 | ||
0735f7e5 UM |
596 | /* Recurse down to leaves */ |
597 | ||
1da177e4 LT |
598 | if (e1->type == type) { |
599 | expr_eliminate_dups1(type, &e1->left.expr, &e2); | |
600 | expr_eliminate_dups1(type, &e1->right.expr, &e2); | |
601 | return; | |
602 | } | |
603 | if (e2->type == type) { | |
604 | expr_eliminate_dups1(type, &e1, &e2->left.expr); | |
605 | expr_eliminate_dups1(type, &e1, &e2->right.expr); | |
606 | return; | |
607 | } | |
0735f7e5 UM |
608 | |
609 | /* e1 and e2 are leaves. Compare and process them. */ | |
610 | ||
1da177e4 LT |
611 | if (e1 == e2) |
612 | return; | |
613 | ||
614 | switch (e1->type) { | |
615 | case E_OR: case E_AND: | |
616 | expr_eliminate_dups1(e1->type, &e1, &e1); | |
617 | default: | |
618 | ; | |
619 | } | |
620 | ||
621 | switch (type) { | |
622 | case E_OR: | |
623 | tmp = expr_join_or(e1, e2); | |
624 | if (tmp) { | |
625 | expr_free(e1); expr_free(e2); | |
626 | e1 = expr_alloc_symbol(&symbol_no); | |
627 | e2 = tmp; | |
628 | trans_count++; | |
629 | } | |
630 | break; | |
631 | case E_AND: | |
632 | tmp = expr_join_and(e1, e2); | |
633 | if (tmp) { | |
634 | expr_free(e1); expr_free(e2); | |
635 | e1 = expr_alloc_symbol(&symbol_yes); | |
636 | e2 = tmp; | |
637 | trans_count++; | |
638 | } | |
639 | break; | |
640 | default: | |
641 | ; | |
642 | } | |
643 | #undef e1 | |
644 | #undef e2 | |
645 | } | |
646 | ||
0735f7e5 UM |
647 | /* |
648 | * Rewrites 'e' in-place to remove ("join") duplicate and other redundant | |
649 | * operands. | |
650 | * | |
651 | * Example simplifications: | |
652 | * | |
653 | * A || B || A -> A || B | |
654 | * A && B && A=y -> A=y && B | |
655 | * | |
656 | * Returns the deduplicated expression. | |
657 | */ | |
1da177e4 LT |
658 | struct expr *expr_eliminate_dups(struct expr *e) |
659 | { | |
660 | int oldcount; | |
661 | if (!e) | |
662 | return e; | |
663 | ||
664 | oldcount = trans_count; | |
665 | while (1) { | |
666 | trans_count = 0; | |
667 | switch (e->type) { | |
668 | case E_OR: case E_AND: | |
669 | expr_eliminate_dups1(e->type, &e, &e); | |
1da177e4 LT |
670 | default: |
671 | ; | |
672 | } | |
673 | if (!trans_count) | |
0735f7e5 | 674 | /* No simplifications done in this pass. We're done */ |
1da177e4 LT |
675 | break; |
676 | e = expr_eliminate_yn(e); | |
677 | } | |
678 | trans_count = oldcount; | |
679 | return e; | |
680 | } | |
681 | ||
0735f7e5 UM |
682 | /* |
683 | * Performs various simplifications involving logical operators and | |
684 | * comparisons. | |
685 | * | |
686 | * Allocates and returns a new expression. | |
687 | */ | |
1da177e4 LT |
688 | struct expr *expr_transform(struct expr *e) |
689 | { | |
690 | struct expr *tmp; | |
691 | ||
692 | if (!e) | |
693 | return NULL; | |
694 | switch (e->type) { | |
695 | case E_EQUAL: | |
31847b67 JB |
696 | case E_GEQ: |
697 | case E_GTH: | |
698 | case E_LEQ: | |
699 | case E_LTH: | |
1da177e4 LT |
700 | case E_UNEQUAL: |
701 | case E_SYMBOL: | |
7a962923 | 702 | case E_LIST: |
1da177e4 LT |
703 | break; |
704 | default: | |
705 | e->left.expr = expr_transform(e->left.expr); | |
706 | e->right.expr = expr_transform(e->right.expr); | |
707 | } | |
708 | ||
709 | switch (e->type) { | |
710 | case E_EQUAL: | |
711 | if (e->left.sym->type != S_BOOLEAN) | |
712 | break; | |
713 | if (e->right.sym == &symbol_no) { | |
714 | e->type = E_NOT; | |
715 | e->left.expr = expr_alloc_symbol(e->left.sym); | |
716 | e->right.sym = NULL; | |
717 | break; | |
718 | } | |
719 | if (e->right.sym == &symbol_mod) { | |
720 | printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name); | |
721 | e->type = E_SYMBOL; | |
722 | e->left.sym = &symbol_no; | |
723 | e->right.sym = NULL; | |
724 | break; | |
725 | } | |
726 | if (e->right.sym == &symbol_yes) { | |
727 | e->type = E_SYMBOL; | |
728 | e->right.sym = NULL; | |
729 | break; | |
730 | } | |
731 | break; | |
732 | case E_UNEQUAL: | |
733 | if (e->left.sym->type != S_BOOLEAN) | |
734 | break; | |
735 | if (e->right.sym == &symbol_no) { | |
736 | e->type = E_SYMBOL; | |
737 | e->right.sym = NULL; | |
738 | break; | |
739 | } | |
740 | if (e->right.sym == &symbol_mod) { | |
741 | printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name); | |
742 | e->type = E_SYMBOL; | |
743 | e->left.sym = &symbol_yes; | |
744 | e->right.sym = NULL; | |
745 | break; | |
746 | } | |
747 | if (e->right.sym == &symbol_yes) { | |
748 | e->type = E_NOT; | |
749 | e->left.expr = expr_alloc_symbol(e->left.sym); | |
750 | e->right.sym = NULL; | |
751 | break; | |
752 | } | |
753 | break; | |
754 | case E_NOT: | |
755 | switch (e->left.expr->type) { | |
756 | case E_NOT: | |
757 | // !!a -> a | |
758 | tmp = e->left.expr->left.expr; | |
759 | free(e->left.expr); | |
760 | free(e); | |
761 | e = tmp; | |
762 | e = expr_transform(e); | |
763 | break; | |
764 | case E_EQUAL: | |
765 | case E_UNEQUAL: | |
766 | // !a='x' -> a!='x' | |
767 | tmp = e->left.expr; | |
768 | free(e); | |
769 | e = tmp; | |
770 | e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL; | |
771 | break; | |
31847b67 JB |
772 | case E_LEQ: |
773 | case E_GEQ: | |
774 | // !a<='x' -> a>'x' | |
775 | tmp = e->left.expr; | |
776 | free(e); | |
777 | e = tmp; | |
778 | e->type = e->type == E_LEQ ? E_GTH : E_LTH; | |
779 | break; | |
780 | case E_LTH: | |
781 | case E_GTH: | |
782 | // !a<'x' -> a>='x' | |
783 | tmp = e->left.expr; | |
784 | free(e); | |
785 | e = tmp; | |
786 | e->type = e->type == E_LTH ? E_GEQ : E_LEQ; | |
787 | break; | |
1da177e4 LT |
788 | case E_OR: |
789 | // !(a || b) -> !a && !b | |
790 | tmp = e->left.expr; | |
791 | e->type = E_AND; | |
792 | e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); | |
793 | tmp->type = E_NOT; | |
794 | tmp->right.expr = NULL; | |
795 | e = expr_transform(e); | |
796 | break; | |
797 | case E_AND: | |
798 | // !(a && b) -> !a || !b | |
799 | tmp = e->left.expr; | |
800 | e->type = E_OR; | |
801 | e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr); | |
802 | tmp->type = E_NOT; | |
803 | tmp->right.expr = NULL; | |
804 | e = expr_transform(e); | |
805 | break; | |
806 | case E_SYMBOL: | |
807 | if (e->left.expr->left.sym == &symbol_yes) { | |
808 | // !'y' -> 'n' | |
809 | tmp = e->left.expr; | |
810 | free(e); | |
811 | e = tmp; | |
812 | e->type = E_SYMBOL; | |
813 | e->left.sym = &symbol_no; | |
814 | break; | |
815 | } | |
816 | if (e->left.expr->left.sym == &symbol_mod) { | |
817 | // !'m' -> 'm' | |
818 | tmp = e->left.expr; | |
819 | free(e); | |
820 | e = tmp; | |
821 | e->type = E_SYMBOL; | |
822 | e->left.sym = &symbol_mod; | |
823 | break; | |
824 | } | |
825 | if (e->left.expr->left.sym == &symbol_no) { | |
826 | // !'n' -> 'y' | |
827 | tmp = e->left.expr; | |
828 | free(e); | |
829 | e = tmp; | |
830 | e->type = E_SYMBOL; | |
831 | e->left.sym = &symbol_yes; | |
832 | break; | |
833 | } | |
834 | break; | |
835 | default: | |
836 | ; | |
837 | } | |
838 | break; | |
839 | default: | |
840 | ; | |
841 | } | |
842 | return e; | |
843 | } | |
844 | ||
845 | int expr_contains_symbol(struct expr *dep, struct symbol *sym) | |
846 | { | |
847 | if (!dep) | |
848 | return 0; | |
849 | ||
850 | switch (dep->type) { | |
851 | case E_AND: | |
852 | case E_OR: | |
853 | return expr_contains_symbol(dep->left.expr, sym) || | |
854 | expr_contains_symbol(dep->right.expr, sym); | |
855 | case E_SYMBOL: | |
856 | return dep->left.sym == sym; | |
857 | case E_EQUAL: | |
31847b67 JB |
858 | case E_GEQ: |
859 | case E_GTH: | |
860 | case E_LEQ: | |
861 | case E_LTH: | |
1da177e4 LT |
862 | case E_UNEQUAL: |
863 | return dep->left.sym == sym || | |
864 | dep->right.sym == sym; | |
865 | case E_NOT: | |
866 | return expr_contains_symbol(dep->left.expr, sym); | |
867 | default: | |
868 | ; | |
869 | } | |
870 | return 0; | |
871 | } | |
872 | ||
873 | bool expr_depends_symbol(struct expr *dep, struct symbol *sym) | |
874 | { | |
875 | if (!dep) | |
876 | return false; | |
877 | ||
878 | switch (dep->type) { | |
879 | case E_AND: | |
880 | return expr_depends_symbol(dep->left.expr, sym) || | |
881 | expr_depends_symbol(dep->right.expr, sym); | |
882 | case E_SYMBOL: | |
883 | return dep->left.sym == sym; | |
884 | case E_EQUAL: | |
885 | if (dep->left.sym == sym) { | |
886 | if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod) | |
887 | return true; | |
888 | } | |
889 | break; | |
890 | case E_UNEQUAL: | |
891 | if (dep->left.sym == sym) { | |
892 | if (dep->right.sym == &symbol_no) | |
893 | return true; | |
894 | } | |
895 | break; | |
896 | default: | |
897 | ; | |
898 | } | |
899 | return false; | |
900 | } | |
901 | ||
0735f7e5 UM |
902 | /* |
903 | * Inserts explicit comparisons of type 'type' to symbol 'sym' into the | |
904 | * expression 'e'. | |
905 | * | |
906 | * Examples transformations for type == E_UNEQUAL, sym == &symbol_no: | |
907 | * | |
908 | * A -> A!=n | |
909 | * !A -> A=n | |
910 | * A && B -> !(A=n || B=n) | |
911 | * A || B -> !(A=n && B=n) | |
912 | * A && (B || C) -> !(A=n || (B=n && C=n)) | |
913 | * | |
914 | * Allocates and returns a new expression. | |
915 | */ | |
1da177e4 LT |
916 | struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) |
917 | { | |
918 | struct expr *e1, *e2; | |
919 | ||
920 | if (!e) { | |
921 | e = expr_alloc_symbol(sym); | |
922 | if (type == E_UNEQUAL) | |
923 | e = expr_alloc_one(E_NOT, e); | |
924 | return e; | |
925 | } | |
926 | switch (e->type) { | |
927 | case E_AND: | |
928 | e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); | |
929 | e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); | |
930 | if (sym == &symbol_yes) | |
931 | e = expr_alloc_two(E_AND, e1, e2); | |
932 | if (sym == &symbol_no) | |
933 | e = expr_alloc_two(E_OR, e1, e2); | |
934 | if (type == E_UNEQUAL) | |
935 | e = expr_alloc_one(E_NOT, e); | |
936 | return e; | |
937 | case E_OR: | |
938 | e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym); | |
939 | e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym); | |
940 | if (sym == &symbol_yes) | |
941 | e = expr_alloc_two(E_OR, e1, e2); | |
942 | if (sym == &symbol_no) | |
943 | e = expr_alloc_two(E_AND, e1, e2); | |
944 | if (type == E_UNEQUAL) | |
945 | e = expr_alloc_one(E_NOT, e); | |
946 | return e; | |
947 | case E_NOT: | |
948 | return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym); | |
949 | case E_UNEQUAL: | |
31847b67 JB |
950 | case E_LTH: |
951 | case E_LEQ: | |
952 | case E_GTH: | |
953 | case E_GEQ: | |
1da177e4 LT |
954 | case E_EQUAL: |
955 | if (type == E_EQUAL) { | |
956 | if (sym == &symbol_yes) | |
957 | return expr_copy(e); | |
958 | if (sym == &symbol_mod) | |
959 | return expr_alloc_symbol(&symbol_no); | |
960 | if (sym == &symbol_no) | |
961 | return expr_alloc_one(E_NOT, expr_copy(e)); | |
962 | } else { | |
963 | if (sym == &symbol_yes) | |
964 | return expr_alloc_one(E_NOT, expr_copy(e)); | |
965 | if (sym == &symbol_mod) | |
966 | return expr_alloc_symbol(&symbol_yes); | |
967 | if (sym == &symbol_no) | |
968 | return expr_copy(e); | |
969 | } | |
970 | break; | |
971 | case E_SYMBOL: | |
972 | return expr_alloc_comp(type, e->left.sym, sym); | |
7a962923 | 973 | case E_LIST: |
1da177e4 LT |
974 | case E_RANGE: |
975 | case E_NONE: | |
976 | /* panic */; | |
977 | } | |
978 | return NULL; | |
979 | } | |
980 | ||
31847b67 JB |
981 | enum string_value_kind { |
982 | k_string, | |
983 | k_signed, | |
984 | k_unsigned, | |
31847b67 JB |
985 | }; |
986 | ||
987 | union string_value { | |
988 | unsigned long long u; | |
989 | signed long long s; | |
990 | }; | |
991 | ||
992 | static enum string_value_kind expr_parse_string(const char *str, | |
993 | enum symbol_type type, | |
994 | union string_value *val) | |
995 | { | |
996 | char *tail; | |
997 | enum string_value_kind kind; | |
998 | ||
999 | errno = 0; | |
1000 | switch (type) { | |
1001 | case S_BOOLEAN: | |
1002 | case S_TRISTATE: | |
9059a349 NP |
1003 | val->s = !strcmp(str, "n") ? 0 : |
1004 | !strcmp(str, "m") ? 1 : | |
1005 | !strcmp(str, "y") ? 2 : -1; | |
1006 | return k_signed; | |
31847b67 JB |
1007 | case S_INT: |
1008 | val->s = strtoll(str, &tail, 10); | |
1009 | kind = k_signed; | |
1010 | break; | |
1011 | case S_HEX: | |
1012 | val->u = strtoull(str, &tail, 16); | |
1013 | kind = k_unsigned; | |
1014 | break; | |
0cbe3ac4 | 1015 | default: |
31847b67 JB |
1016 | val->s = strtoll(str, &tail, 0); |
1017 | kind = k_signed; | |
1018 | break; | |
31847b67 JB |
1019 | } |
1020 | return !errno && !*tail && tail > str && isxdigit(tail[-1]) | |
1021 | ? kind : k_string; | |
1022 | } | |
1023 | ||
1da177e4 LT |
1024 | tristate expr_calc_value(struct expr *e) |
1025 | { | |
1026 | tristate val1, val2; | |
1027 | const char *str1, *str2; | |
31847b67 JB |
1028 | enum string_value_kind k1 = k_string, k2 = k_string; |
1029 | union string_value lval = {}, rval = {}; | |
1030 | int res; | |
1da177e4 LT |
1031 | |
1032 | if (!e) | |
1033 | return yes; | |
1034 | ||
1035 | switch (e->type) { | |
1036 | case E_SYMBOL: | |
1037 | sym_calc_value(e->left.sym); | |
1038 | return e->left.sym->curr.tri; | |
1039 | case E_AND: | |
1040 | val1 = expr_calc_value(e->left.expr); | |
1041 | val2 = expr_calc_value(e->right.expr); | |
d6ee3576 | 1042 | return EXPR_AND(val1, val2); |
1da177e4 LT |
1043 | case E_OR: |
1044 | val1 = expr_calc_value(e->left.expr); | |
1045 | val2 = expr_calc_value(e->right.expr); | |
d6ee3576 | 1046 | return EXPR_OR(val1, val2); |
1da177e4 LT |
1047 | case E_NOT: |
1048 | val1 = expr_calc_value(e->left.expr); | |
d6ee3576 | 1049 | return EXPR_NOT(val1); |
1da177e4 | 1050 | case E_EQUAL: |
31847b67 JB |
1051 | case E_GEQ: |
1052 | case E_GTH: | |
1053 | case E_LEQ: | |
1054 | case E_LTH: | |
1da177e4 | 1055 | case E_UNEQUAL: |
31847b67 | 1056 | break; |
1da177e4 LT |
1057 | default: |
1058 | printf("expr_calc_value: %d?\n", e->type); | |
1059 | return no; | |
1060 | } | |
31847b67 JB |
1061 | |
1062 | sym_calc_value(e->left.sym); | |
1063 | sym_calc_value(e->right.sym); | |
1064 | str1 = sym_get_string_value(e->left.sym); | |
1065 | str2 = sym_get_string_value(e->right.sym); | |
1066 | ||
1067 | if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) { | |
1068 | k1 = expr_parse_string(str1, e->left.sym->type, &lval); | |
1069 | k2 = expr_parse_string(str2, e->right.sym->type, &rval); | |
1070 | } | |
1071 | ||
1072 | if (k1 == k_string || k2 == k_string) | |
1073 | res = strcmp(str1, str2); | |
0cbe3ac4 | 1074 | else if (k1 == k_unsigned || k2 == k_unsigned) |
31847b67 JB |
1075 | res = (lval.u > rval.u) - (lval.u < rval.u); |
1076 | else /* if (k1 == k_signed && k2 == k_signed) */ | |
1077 | res = (lval.s > rval.s) - (lval.s < rval.s); | |
1078 | ||
1079 | switch(e->type) { | |
1080 | case E_EQUAL: | |
1081 | return res ? no : yes; | |
1082 | case E_GEQ: | |
1083 | return res >= 0 ? yes : no; | |
1084 | case E_GTH: | |
1085 | return res > 0 ? yes : no; | |
1086 | case E_LEQ: | |
1087 | return res <= 0 ? yes : no; | |
1088 | case E_LTH: | |
1089 | return res < 0 ? yes : no; | |
1090 | case E_UNEQUAL: | |
1091 | return res ? yes : no; | |
1092 | default: | |
1093 | printf("expr_calc_value: relation %d?\n", e->type); | |
1094 | return no; | |
1095 | } | |
1da177e4 LT |
1096 | } |
1097 | ||
ad8d40cd | 1098 | static int expr_compare_type(enum expr_type t1, enum expr_type t2) |
1da177e4 | 1099 | { |
1da177e4 LT |
1100 | if (t1 == t2) |
1101 | return 0; | |
1102 | switch (t1) { | |
31847b67 JB |
1103 | case E_LEQ: |
1104 | case E_LTH: | |
1105 | case E_GEQ: | |
1106 | case E_GTH: | |
1107 | if (t2 == E_EQUAL || t2 == E_UNEQUAL) | |
1108 | return 1; | |
1da177e4 LT |
1109 | case E_EQUAL: |
1110 | case E_UNEQUAL: | |
1111 | if (t2 == E_NOT) | |
1112 | return 1; | |
1113 | case E_NOT: | |
1114 | if (t2 == E_AND) | |
1115 | return 1; | |
1116 | case E_AND: | |
1117 | if (t2 == E_OR) | |
1118 | return 1; | |
1119 | case E_OR: | |
7a962923 | 1120 | if (t2 == E_LIST) |
1da177e4 | 1121 | return 1; |
7a962923 | 1122 | case E_LIST: |
1da177e4 LT |
1123 | if (t2 == 0) |
1124 | return 1; | |
1125 | default: | |
1126 | return -1; | |
1127 | } | |
1128 | printf("[%dgt%d?]", t1, t2); | |
1129 | return 0; | |
1da177e4 LT |
1130 | } |
1131 | ||
9a47ceec MY |
1132 | void expr_print(struct expr *e, |
1133 | void (*fn)(void *, struct symbol *, const char *), | |
1134 | void *data, int prevtoken) | |
1da177e4 LT |
1135 | { |
1136 | if (!e) { | |
ab45d190 | 1137 | fn(data, NULL, "y"); |
1da177e4 LT |
1138 | return; |
1139 | } | |
1140 | ||
1141 | if (expr_compare_type(prevtoken, e->type) > 0) | |
ab45d190 | 1142 | fn(data, NULL, "("); |
1da177e4 LT |
1143 | switch (e->type) { |
1144 | case E_SYMBOL: | |
1145 | if (e->left.sym->name) | |
ab45d190 | 1146 | fn(data, e->left.sym, e->left.sym->name); |
1da177e4 | 1147 | else |
ab45d190 | 1148 | fn(data, NULL, "<choice>"); |
1da177e4 LT |
1149 | break; |
1150 | case E_NOT: | |
ab45d190 | 1151 | fn(data, NULL, "!"); |
1da177e4 LT |
1152 | expr_print(e->left.expr, fn, data, E_NOT); |
1153 | break; | |
1154 | case E_EQUAL: | |
f5eaa323 JB |
1155 | if (e->left.sym->name) |
1156 | fn(data, e->left.sym, e->left.sym->name); | |
1157 | else | |
1158 | fn(data, NULL, "<choice>"); | |
ab45d190 RZ |
1159 | fn(data, NULL, "="); |
1160 | fn(data, e->right.sym, e->right.sym->name); | |
31847b67 JB |
1161 | break; |
1162 | case E_LEQ: | |
1163 | case E_LTH: | |
1164 | if (e->left.sym->name) | |
1165 | fn(data, e->left.sym, e->left.sym->name); | |
1166 | else | |
1167 | fn(data, NULL, "<choice>"); | |
1168 | fn(data, NULL, e->type == E_LEQ ? "<=" : "<"); | |
1169 | fn(data, e->right.sym, e->right.sym->name); | |
1170 | break; | |
1171 | case E_GEQ: | |
1172 | case E_GTH: | |
1173 | if (e->left.sym->name) | |
1174 | fn(data, e->left.sym, e->left.sym->name); | |
1175 | else | |
1176 | fn(data, NULL, "<choice>"); | |
f6aad261 | 1177 | fn(data, NULL, e->type == E_GEQ ? ">=" : ">"); |
31847b67 | 1178 | fn(data, e->right.sym, e->right.sym->name); |
1da177e4 LT |
1179 | break; |
1180 | case E_UNEQUAL: | |
f5eaa323 JB |
1181 | if (e->left.sym->name) |
1182 | fn(data, e->left.sym, e->left.sym->name); | |
1183 | else | |
1184 | fn(data, NULL, "<choice>"); | |
ab45d190 RZ |
1185 | fn(data, NULL, "!="); |
1186 | fn(data, e->right.sym, e->right.sym->name); | |
1da177e4 LT |
1187 | break; |
1188 | case E_OR: | |
9a47ceec MY |
1189 | expr_print(e->left.expr, fn, data, E_OR); |
1190 | fn(data, NULL, " || "); | |
1191 | expr_print(e->right.expr, fn, data, E_OR); | |
1da177e4 LT |
1192 | break; |
1193 | case E_AND: | |
1194 | expr_print(e->left.expr, fn, data, E_AND); | |
ab45d190 | 1195 | fn(data, NULL, " && "); |
1da177e4 LT |
1196 | expr_print(e->right.expr, fn, data, E_AND); |
1197 | break; | |
7a962923 | 1198 | case E_LIST: |
ab45d190 | 1199 | fn(data, e->right.sym, e->right.sym->name); |
1da177e4 | 1200 | if (e->left.expr) { |
ab45d190 | 1201 | fn(data, NULL, " ^ "); |
7a962923 | 1202 | expr_print(e->left.expr, fn, data, E_LIST); |
1da177e4 LT |
1203 | } |
1204 | break; | |
1205 | case E_RANGE: | |
ab45d190 RZ |
1206 | fn(data, NULL, "["); |
1207 | fn(data, e->left.sym, e->left.sym->name); | |
1208 | fn(data, NULL, " "); | |
1209 | fn(data, e->right.sym, e->right.sym->name); | |
1210 | fn(data, NULL, "]"); | |
1da177e4 LT |
1211 | break; |
1212 | default: | |
1213 | { | |
1214 | char buf[32]; | |
1215 | sprintf(buf, "<unknown type %d>", e->type); | |
ab45d190 | 1216 | fn(data, NULL, buf); |
1da177e4 LT |
1217 | break; |
1218 | } | |
1219 | } | |
1220 | if (expr_compare_type(prevtoken, e->type) > 0) | |
ab45d190 | 1221 | fn(data, NULL, ")"); |
1da177e4 LT |
1222 | } |
1223 | ||
ab45d190 | 1224 | static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) |
1da177e4 | 1225 | { |
bf5e327a | 1226 | xfwrite(str, strlen(str), 1, data); |
1da177e4 LT |
1227 | } |
1228 | ||
1229 | void expr_fprint(struct expr *e, FILE *out) | |
1230 | { | |
1231 | expr_print(e, expr_print_file_helper, out, E_NONE); | |
1232 | } | |
1233 | ||
ab45d190 | 1234 | static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str) |
1da177e4 | 1235 | { |
da60fbbc VB |
1236 | struct gstr *gs = (struct gstr*)data; |
1237 | const char *sym_str = NULL; | |
1238 | ||
1239 | if (sym) | |
1240 | sym_str = sym_get_string_value(sym); | |
1241 | ||
1242 | if (gs->max_width) { | |
1243 | unsigned extra_length = strlen(str); | |
1244 | const char *last_cr = strrchr(gs->s, '\n'); | |
1245 | unsigned last_line_length; | |
1246 | ||
1247 | if (sym_str) | |
1248 | extra_length += 4 + strlen(sym_str); | |
1249 | ||
1250 | if (!last_cr) | |
1251 | last_cr = gs->s; | |
1252 | ||
1253 | last_line_length = strlen(gs->s) - (last_cr - gs->s); | |
1254 | ||
1255 | if ((last_line_length + extra_length) > gs->max_width) | |
1256 | str_append(gs, "\\\n"); | |
1257 | } | |
1258 | ||
1259 | str_append(gs, str); | |
70ed0747 | 1260 | if (sym && sym->type != S_UNKNOWN) |
da60fbbc | 1261 | str_printf(gs, " [=%s]", sym_str); |
1da177e4 LT |
1262 | } |
1263 | ||
1264 | void expr_gstr_print(struct expr *e, struct gstr *gs) | |
1265 | { | |
1266 | expr_print(e, expr_print_gstr_helper, gs, E_NONE); | |
1267 | } | |
1ccb2714 PV |
1268 | |
1269 | /* | |
1270 | * Transform the top level "||" tokens into newlines and prepend each | |
1271 | * line with a minus. This makes expressions much easier to read. | |
1272 | * Suitable for reverse dependency expressions. | |
1273 | */ | |
9a47ceec MY |
1274 | static void expr_print_revdep(struct expr *e, |
1275 | void (*fn)(void *, struct symbol *, const char *), | |
d9119b59 | 1276 | void *data, tristate pr_type, const char **title) |
9a47ceec MY |
1277 | { |
1278 | if (e->type == E_OR) { | |
d9119b59 ER |
1279 | expr_print_revdep(e->left.expr, fn, data, pr_type, title); |
1280 | expr_print_revdep(e->right.expr, fn, data, pr_type, title); | |
1281 | } else if (expr_calc_value(e) == pr_type) { | |
1282 | if (*title) { | |
1283 | fn(data, NULL, *title); | |
1284 | *title = NULL; | |
1285 | } | |
1286 | ||
9a47ceec MY |
1287 | fn(data, NULL, " - "); |
1288 | expr_print(e, fn, data, E_NONE); | |
1289 | fn(data, NULL, "\n"); | |
1290 | } | |
1291 | } | |
1292 | ||
d9119b59 ER |
1293 | void expr_gstr_print_revdep(struct expr *e, struct gstr *gs, |
1294 | tristate pr_type, const char *title) | |
1ccb2714 | 1295 | { |
d9119b59 | 1296 | expr_print_revdep(e, expr_print_gstr_helper, gs, pr_type, &title); |
1ccb2714 | 1297 | } |