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