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