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