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