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