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