// SPDX-License-Identifier: GPL-2.0/* * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org> */ #include <ctype.h>#include <errno.h>#include <stdio.h>#include <stdlib.h>#include <string.h> #include "lkc.h" #define DEBUG_EXPR	0 static struct expr *expr_eliminate_yn(struct expr *e); struct expr *expr_alloc_symbol(struct symbol *sym){	struct expr *e = xcalloc(1, sizeof(*e));	e->type = E_SYMBOL;	e->left.sym = sym;	return e;} struct expr *expr_alloc_one(enum expr_type type, struct expr *ce){	struct expr *e = xcalloc(1, sizeof(*e));	e->type = type;	e->left.expr = ce;	return e;} struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2){	struct expr *e = xcalloc(1, sizeof(*e));	e->type = type;	e->left.expr = e1;	e->right.expr = e2;	return e;} struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2){	struct expr *e = xcalloc(1, sizeof(*e));	e->type = type;	e->left.sym = s1;	e->right.sym = s2;	return e;} struct expr *expr_alloc_and(struct expr *e1, struct expr *e2){	if (!e1)		return e2;	return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;} struct expr *expr_alloc_or(struct expr *e1, struct expr *e2){	if (!e1)		return e2;	return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;} struct expr *expr_copy(const struct expr *org){	struct expr *e; 	if (!org)		return NULL; 	e = xmalloc(sizeof(*org));	memcpy(e, org, sizeof(*org));	switch (org->type) {	case E_SYMBOL:		e->left = org->left;		break;	case E_NOT:		e->left.expr = expr_copy(org->left.expr);		break;	case E_EQUAL:	case E_GEQ:	case E_GTH:	case E_LEQ:	case E_LTH:	case E_UNEQUAL:		e->left.sym = org->left.sym;		e->right.sym = org->right.sym;		break;	case E_AND:	case E_OR:	case E_LIST:		e->left.expr = expr_copy(org->left.expr);		e->right.expr = expr_copy(org->right.expr);		break;	default:		fprintf(stderr, "can't copy type %d\n", e->type);		free(e);		e = NULL;		break;	} 	return e;} void expr_free(struct expr *e){	if (!e)		return; 	switch (e->type) {	case E_SYMBOL:		break;	case E_NOT:		expr_free(e->left.expr);		break;	case E_EQUAL:	case E_GEQ:	case E_GTH:	case E_LEQ:	case E_LTH:	case E_UNEQUAL:		break;	case E_OR:	case E_AND:		expr_free(e->left.expr);		expr_free(e->right.expr);		break;	default:		fprintf(stderr, "how to free type %d?\n", e->type);		break;	}	free(e);} static int trans_count; #define e1 (*ep1)#define e2 (*ep2) /* * expr_eliminate_eq() helper. * * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared * against all other leaves. Two equal leaves are both replaced with either 'y' * or 'n' as appropriate for 'type', to be eliminated later. */static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2){	/* Recurse down to leaves */ 	if (e1->type == type) {		__expr_eliminate_eq(type, &e1->left.expr, &e2);		__expr_eliminate_eq(type, &e1->right.expr, &e2);		return;	}	if (e2->type == type) {		__expr_eliminate_eq(type, &e1, &e2->left.expr);		__expr_eliminate_eq(type, &e1, &e2->right.expr);		return;	} 	/* e1 and e2 are leaves. Compare them. */ 	if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&	    e1->left.sym == e2->left.sym &&	    (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))		return;	if (!expr_eq(e1, e2))		return; 	/* e1 and e2 are equal leaves. Prepare them for elimination. */ 	trans_count++;	expr_free(e1); expr_free(e2);	switch (type) {	case E_OR:		e1 = expr_alloc_symbol(&symbol_no);		e2 = expr_alloc_symbol(&symbol_no);		break;	case E_AND:		e1 = expr_alloc_symbol(&symbol_yes);		e2 = expr_alloc_symbol(&symbol_yes);		break;	default:		;	}} /* * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both. * Example reductions: * *	ep1: A && B           ->  ep1: y *	ep2: A && B && C      ->  ep2: C * *	ep1: A || B           ->  ep1: n *	ep2: A || B || C      ->  ep2: C * *	ep1: A && (B && FOO)  ->  ep1: FOO *	ep2: (BAR && B) && A  ->  ep2: BAR * *	ep1: A && (B || C)    ->  ep1: y *	ep2: (C || B) && A    ->  ep2: y * * Comparisons are done between all operands at the same "level" of && or ||. * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the * following operands will be compared: * *	- 'e1', 'e2 || e3', and 'e4 || e5', against each other *	- e2 against e3 *	- e4 against e5 * * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and * '(e1 && e2) && e3' are both a single level. * * See __expr_eliminate_eq() as well. */void expr_eliminate_eq(struct expr **ep1, struct expr **ep2){	if (!e1 || !e2)		return;	switch (e1->type) {	case E_OR:	case E_AND:		__expr_eliminate_eq(e1->type, ep1, ep2);	default:		;	}	if (e1->type != e2->type) switch (e2->type) {	case E_OR:	case E_AND:		__expr_eliminate_eq(e2->type, ep1, ep2);	default:		;	}	e1 = expr_eliminate_yn(e1);	e2 = expr_eliminate_yn(e2);} #undef e1#undef e2 /* * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two * &&/|| expressions are considered equal if every operand in one expression * equals some operand in the other (operands do not need to appear in the same * order), recursively. */int expr_eq(struct expr *e1, struct expr *e2){	int res, old_count; 	/*	 * A NULL expr is taken to be yes, but there's also a different way to	 * represent yes. expr_is_yes() checks for either representation.	 */	if (!e1 || !e2)		return expr_is_yes(e1) && expr_is_yes(e2); 	if (e1->type != e2->type)		return 0;	switch (e1->type) {	case E_EQUAL:	case E_GEQ:	case E_GTH:	case E_LEQ:	case E_LTH:	case E_UNEQUAL:		return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;	case E_SYMBOL:		return e1->left.sym == e2->left.sym;	case E_NOT:		return expr_eq(e1->left.expr, e2->left.expr);	case E_AND:	case E_OR:		e1 = expr_copy(e1);		e2 = expr_copy(e2);		old_count = trans_count;		expr_eliminate_eq(&e1, &e2);		res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&		       e1->left.sym == e2->left.sym);		expr_free(e1);		expr_free(e2);		trans_count = old_count;		return res;	case E_LIST:	case E_RANGE:	case E_NONE:		/* panic */;	} 	if (DEBUG_EXPR) {		expr_fprint(e1, stdout);		printf(" = ");		expr_fprint(e2, stdout);		printf(" ?\n");	} 	return 0;} /* * Recursively performs the following simplifications in-place (as well as the * corresponding simplifications with swapped operands): * *	expr && n  ->  n *	expr && y  ->  expr *	expr || n  ->  expr *	expr || y  ->  y * * Returns the optimized expression. */static struct expr *expr_eliminate_yn(struct expr *e){	struct expr *tmp; 	if (e) switch (e->type) {	case E_AND:		e->left.expr = expr_eliminate_yn(e->left.expr);		e->right.expr = expr_eliminate_yn(e->right.expr);		if (e->left.expr->type == E_SYMBOL) {			if (e->left.expr->left.sym == &symbol_no) {				expr_free(e->left.expr);				expr_free(e->right.expr);				e->type = E_SYMBOL;				e->left.sym = &symbol_no;				e->right.expr = NULL;				return e;			} else if (e->left.expr->left.sym == &symbol_yes) {				free(e->left.expr);				tmp = e->right.expr;				*e = *(e->right.expr);				free(tmp);				return e;			}		}		if (e->right.expr->type == E_SYMBOL) {			if (e->right.expr->left.sym == &symbol_no) {				expr_free(e->left.expr);				expr_free(e->right.expr);				e->type = E_SYMBOL;				e->left.sym = &symbol_no;				e->right.expr = NULL;				return e;			} else if (e->right.expr->left.sym == &symbol_yes) {				free(e->right.expr);				tmp = e->left.expr;				*e = *(e->left.expr);				free(tmp);				return e;			}		}		break;	case E_OR:		e->left.expr = expr_eliminate_yn(e->left.expr);		e->right.expr = expr_eliminate_yn(e->right.expr);		if (e->left.expr->type == E_SYMBOL) {			if (e->left.expr->left.sym == &symbol_no) {				free(e->left.expr);				tmp = e->right.expr;				*e = *(e->right.expr);				free(tmp);				return e;			} else if (e->left.expr->left.sym == &symbol_yes) {				expr_free(e->left.expr);				expr_free(e->right.expr);				e->type = E_SYMBOL;				e->left.sym = &symbol_yes;				e->right.expr = NULL;				return e;			}		}		if (e->right.expr->type == E_SYMBOL) {			if (e->right.expr->left.sym == &symbol_no) {				free(e->right.expr);				tmp = e->left.expr;				*e = *(e->left.expr);				free(tmp);				return e;			} else if (e->right.expr->left.sym == &symbol_yes) {				expr_free(e->left.expr);				expr_free(e->right.expr);				e->type = E_SYMBOL;				e->left.sym = &symbol_yes;				e->right.expr = NULL;				return e;			}		}		break;	default:		;	}	return e;} /* * e1 || e2 -> ? */static struct expr *expr_join_or(struct expr *e1, struct expr *e2){	struct expr *tmp;	struct symbol *sym1, *sym2; 	if (expr_eq(e1, e2))		return expr_copy(e1);	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)		return NULL;	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)		return NULL;	if (e1->type == E_NOT) {		tmp = e1->left.expr;		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)			return NULL;		sym1 = tmp->left.sym;	} else		sym1 = e1->left.sym;	if (e2->type == E_NOT) {		if (e2->left.expr->type != E_SYMBOL)			return NULL;		sym2 = e2->left.expr->left.sym;	} else		sym2 = e2->left.sym;	if (sym1 != sym2)		return NULL;	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)		return NULL;	if (sym1->type == S_TRISTATE) {		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||		     (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {			// (a='y') || (a='m') -> (a!='n')			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);		}		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&		    ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {			// (a='y') || (a='n') -> (a!='m')			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);		}		if (e1->type == E_EQUAL && e2->type == E_EQUAL &&		    ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||		     (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {			// (a='m') || (a='n') -> (a!='y')			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);		}	}	if (sym1->type == S_BOOLEAN) {		if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||		    (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))			return expr_alloc_symbol(&symbol_yes);	} 	if (DEBUG_EXPR) {		printf("optimize (");		expr_fprint(e1, stdout);		printf(") || (");		expr_fprint(e2, stdout);		printf(")?\n");	}	return NULL;} static struct expr *expr_join_and(struct expr *e1, struct expr *e2){	struct expr *tmp;	struct symbol *sym1, *sym2; 	if (expr_eq(e1, e2))		return expr_copy(e1);	if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)		return NULL;	if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)		return NULL;	if (e1->type == E_NOT) {		tmp = e1->left.expr;		if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)			return NULL;		sym1 = tmp->left.sym;	} else		sym1 = e1->left.sym;	if (e2->type == E_NOT) {		if (e2->left.expr->type != E_SYMBOL)			return NULL;		sym2 = e2->left.expr->left.sym;	} else		sym2 = e2->left.sym;	if (sym1 != sym2)		return NULL;	if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)		return NULL; 	if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||	    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))		// (a) && (a='y') -> (a='y')		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); 	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||

Lines 1–500 of 1273. Load more