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