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