/*
   * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
   * Released under the terms of the GNU GPL v2.0.
   */
  
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>

  #include "lkc.h"
  
  #define DEBUG_EXPR	0

  static int expr_eq(struct expr *e1, struct expr *e2);
  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:
  		printf("can't copy type %d
  ", 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:
  		printf("how to free type %d?
  ", e->type);
  		break;
  	}
  	free(e);
  }
  
  static int trans_count;
  
  #define e1 (*ep1)
  #define e2 (*ep2)
  
  static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
  {
  	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;
  	}
  	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;
  	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:
  		;
  	}
  }
  
  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

  static int expr_eq(struct expr *e1, struct expr *e2)

  {
  	int res, old_count;
  
  	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(" ?
  ");
  	}
  
  	return 0;
  }

  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;
  }
  
  /*
   * bool FOO!=n => FOO
   */
  struct expr *expr_trans_bool(struct expr *e)
  {
  	if (!e)
  		return NULL;
  	switch (e->type) {
  	case E_AND:
  	case E_OR:
  	case E_NOT:
  		e->left.expr = expr_trans_bool(e->left.expr);
  		e->right.expr = expr_trans_bool(e->right.expr);
  		break;
  	case E_UNEQUAL:
  		// FOO!=n -> FOO
  		if (e->left.sym->type == S_TRISTATE) {
  			if (e->right.sym == &symbol_no) {
  				e->type = E_SYMBOL;
  				e->right.sym = NULL;
  			}
  		}
  		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 && sym1 == sym2) {
  		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(")?
  ");
  	}
  	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) ||
  	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
  		// (a) && (a!='n') -> (a)
  		return expr_alloc_symbol(sym1);
  
  	if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
  	    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
  		// (a) && (a!='m') -> (a='y')
  		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  
  	if (sym1->type == S_TRISTATE) {
  		if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
  			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
  			sym2 = e1->right.sym;
  			if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
  				return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
  							     : expr_alloc_symbol(&symbol_no);
  		}
  		if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
  			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
  			sym2 = e2->right.sym;
  			if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
  				return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
  							     : expr_alloc_symbol(&symbol_no);
  		}
  		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  			   ((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_EQUAL, sym1, &symbol_mod);
  
  		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  			   ((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_EQUAL, sym1, &symbol_no);
  
  		if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
  			   ((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='m')
  			return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
  
  		if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
  		    (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
  		    (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
  		    (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
  			return NULL;
  	}
  
  	if (DEBUG_EXPR) {
  		printf("optimize (");
  		expr_fprint(e1, stdout);
  		printf(") && (");
  		expr_fprint(e2, stdout);
  		printf(")?
  ");
  	}
  	return NULL;
  }
  
  static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
  {
  #define e1 (*ep1)
  #define e2 (*ep2)
  	struct expr *tmp;
  
  	if (e1->type == type) {
  		expr_eliminate_dups1(type, &e1->left.expr, &e2);
  		expr_eliminate_dups1(type, &e1->right.expr, &e2);
  		return;
  	}
  	if (e2->type == type) {
  		expr_eliminate_dups1(type, &e1, &e2->left.expr);
  		expr_eliminate_dups1(type, &e1, &e2->right.expr);
  		return;
  	}
  	if (e1 == e2)
  		return;
  
  	switch (e1->type) {
  	case E_OR: case E_AND:
  		expr_eliminate_dups1(e1->type, &e1, &e1);
  	default:
  		;
  	}
  
  	switch (type) {
  	case E_OR:
  		tmp = expr_join_or(e1, e2);
  		if (tmp) {
  			expr_free(e1); expr_free(e2);
  			e1 = expr_alloc_symbol(&symbol_no);
  			e2 = tmp;
  			trans_count++;
  		}
  		break;
  	case E_AND:
  		tmp = expr_join_and(e1, e2);
  		if (tmp) {
  			expr_free(e1); expr_free(e2);
  			e1 = expr_alloc_symbol(&symbol_yes);
  			e2 = tmp;
  			trans_count++;
  		}
  		break;
  	default:
  		;
  	}
  #undef e1
  #undef e2
  }

  struct expr *expr_eliminate_dups(struct expr *e)
  {
  	int oldcount;
  	if (!e)
  		return e;
  
  	oldcount = trans_count;
  	while (1) {
  		trans_count = 0;
  		switch (e->type) {
  		case E_OR: case E_AND:
  			expr_eliminate_dups1(e->type, &e, &e);

  		default:
  			;
  		}
  		if (!trans_count)
  			break;
  		e = expr_eliminate_yn(e);
  	}
  	trans_count = oldcount;
  	return e;
  }
  
  struct expr *expr_transform(struct expr *e)
  {
  	struct expr *tmp;
  
  	if (!e)
  		return NULL;
  	switch (e->type) {
  	case E_EQUAL:

  	case E_GEQ:
  	case E_GTH:
  	case E_LEQ:
  	case E_LTH:

  	case E_UNEQUAL:
  	case E_SYMBOL:

  	case E_LIST:

  		break;
  	default:
  		e->left.expr = expr_transform(e->left.expr);
  		e->right.expr = expr_transform(e->right.expr);
  	}
  
  	switch (e->type) {
  	case E_EQUAL:
  		if (e->left.sym->type != S_BOOLEAN)
  			break;
  		if (e->right.sym == &symbol_no) {
  			e->type = E_NOT;
  			e->left.expr = expr_alloc_symbol(e->left.sym);
  			e->right.sym = NULL;
  			break;
  		}
  		if (e->right.sym == &symbol_mod) {
  			printf("boolean symbol %s tested for 'm'? test forced to 'n'
  ", e->left.sym->name);
  			e->type = E_SYMBOL;
  			e->left.sym = &symbol_no;
  			e->right.sym = NULL;
  			break;
  		}
  		if (e->right.sym == &symbol_yes) {
  			e->type = E_SYMBOL;
  			e->right.sym = NULL;
  			break;
  		}
  		break;
  	case E_UNEQUAL:
  		if (e->left.sym->type != S_BOOLEAN)
  			break;
  		if (e->right.sym == &symbol_no) {
  			e->type = E_SYMBOL;
  			e->right.sym = NULL;
  			break;
  		}
  		if (e->right.sym == &symbol_mod) {
  			printf("boolean symbol %s tested for 'm'? test forced to 'y'
  ", e->left.sym->name);
  			e->type = E_SYMBOL;
  			e->left.sym = &symbol_yes;
  			e->right.sym = NULL;
  			break;
  		}
  		if (e->right.sym == &symbol_yes) {
  			e->type = E_NOT;
  			e->left.expr = expr_alloc_symbol(e->left.sym);
  			e->right.sym = NULL;
  			break;
  		}
  		break;
  	case E_NOT:
  		switch (e->left.expr->type) {
  		case E_NOT:
  			// !!a -> a
  			tmp = e->left.expr->left.expr;
  			free(e->left.expr);
  			free(e);
  			e = tmp;
  			e = expr_transform(e);
  			break;
  		case E_EQUAL:
  		case E_UNEQUAL:
  			// !a='x' -> a!='x'
  			tmp = e->left.expr;
  			free(e);
  			e = tmp;
  			e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
  			break;

  		case E_LEQ:
  		case E_GEQ:
  			// !a<='x' -> a>'x'
  			tmp = e->left.expr;
  			free(e);
  			e = tmp;
  			e->type = e->type == E_LEQ ? E_GTH : E_LTH;
  			break;
  		case E_LTH:
  		case E_GTH:
  			// !a<'x' -> a>='x'
  			tmp = e->left.expr;
  			free(e);
  			e = tmp;
  			e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
  			break;

  		case E_OR:
  			// !(a || b) -> !a && !b
  			tmp = e->left.expr;
  			e->type = E_AND;
  			e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
  			tmp->type = E_NOT;
  			tmp->right.expr = NULL;
  			e = expr_transform(e);
  			break;
  		case E_AND:
  			// !(a && b) -> !a || !b
  			tmp = e->left.expr;
  			e->type = E_OR;
  			e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
  			tmp->type = E_NOT;
  			tmp->right.expr = NULL;
  			e = expr_transform(e);
  			break;
  		case E_SYMBOL:
  			if (e->left.expr->left.sym == &symbol_yes) {
  				// !'y' -> 'n'
  				tmp = e->left.expr;
  				free(e);
  				e = tmp;
  				e->type = E_SYMBOL;
  				e->left.sym = &symbol_no;
  				break;
  			}
  			if (e->left.expr->left.sym == &symbol_mod) {
  				// !'m' -> 'm'
  				tmp = e->left.expr;
  				free(e);
  				e = tmp;
  				e->type = E_SYMBOL;
  				e->left.sym = &symbol_mod;
  				break;
  			}
  			if (e->left.expr->left.sym == &symbol_no) {
  				// !'n' -> 'y'
  				tmp = e->left.expr;
  				free(e);
  				e = tmp;
  				e->type = E_SYMBOL;
  				e->left.sym = &symbol_yes;
  				break;
  			}
  			break;
  		default:
  			;
  		}
  		break;
  	default:
  		;
  	}
  	return e;
  }
  
  int expr_contains_symbol(struct expr *dep, struct symbol *sym)
  {
  	if (!dep)
  		return 0;
  
  	switch (dep->type) {
  	case E_AND:
  	case E_OR:
  		return expr_contains_symbol(dep->left.expr, sym) ||
  		       expr_contains_symbol(dep->right.expr, sym);
  	case E_SYMBOL:
  		return dep->left.sym == sym;
  	case E_EQUAL:

  	case E_GEQ:
  	case E_GTH:
  	case E_LEQ:
  	case E_LTH:

  	case E_UNEQUAL:
  		return dep->left.sym == sym ||
  		       dep->right.sym == sym;
  	case E_NOT:
  		return expr_contains_symbol(dep->left.expr, sym);
  	default:
  		;
  	}
  	return 0;
  }
  
  bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
  {
  	if (!dep)
  		return false;
  
  	switch (dep->type) {
  	case E_AND:
  		return expr_depends_symbol(dep->left.expr, sym) ||
  		       expr_depends_symbol(dep->right.expr, sym);
  	case E_SYMBOL:
  		return dep->left.sym == sym;
  	case E_EQUAL:
  		if (dep->left.sym == sym) {
  			if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
  				return true;
  		}
  		break;
  	case E_UNEQUAL:
  		if (dep->left.sym == sym) {
  			if (dep->right.sym == &symbol_no)
  				return true;
  		}
  		break;
  	default:
  		;
  	}
   	return false;
  }

  struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
  {
  	struct expr *e1, *e2;
  
  	if (!e) {
  		e = expr_alloc_symbol(sym);
  		if (type == E_UNEQUAL)
  			e = expr_alloc_one(E_NOT, e);
  		return e;
  	}
  	switch (e->type) {
  	case E_AND:
  		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
  		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
  		if (sym == &symbol_yes)
  			e = expr_alloc_two(E_AND, e1, e2);
  		if (sym == &symbol_no)
  			e = expr_alloc_two(E_OR, e1, e2);
  		if (type == E_UNEQUAL)
  			e = expr_alloc_one(E_NOT, e);
  		return e;
  	case E_OR:
  		e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
  		e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
  		if (sym == &symbol_yes)
  			e = expr_alloc_two(E_OR, e1, e2);
  		if (sym == &symbol_no)
  			e = expr_alloc_two(E_AND, e1, e2);
  		if (type == E_UNEQUAL)
  			e = expr_alloc_one(E_NOT, e);
  		return e;
  	case E_NOT:
  		return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
  	case E_UNEQUAL:

  	case E_LTH:
  	case E_LEQ:
  	case E_GTH:
  	case E_GEQ:

  	case E_EQUAL:
  		if (type == E_EQUAL) {
  			if (sym == &symbol_yes)
  				return expr_copy(e);
  			if (sym == &symbol_mod)
  				return expr_alloc_symbol(&symbol_no);
  			if (sym == &symbol_no)
  				return expr_alloc_one(E_NOT, expr_copy(e));
  		} else {
  			if (sym == &symbol_yes)
  				return expr_alloc_one(E_NOT, expr_copy(e));
  			if (sym == &symbol_mod)
  				return expr_alloc_symbol(&symbol_yes);
  			if (sym == &symbol_no)
  				return expr_copy(e);
  		}
  		break;
  	case E_SYMBOL:
  		return expr_alloc_comp(type, e->left.sym, sym);

  	case E_LIST:

  	case E_RANGE:
  	case E_NONE:
  		/* panic */;
  	}
  	return NULL;
  }

  enum string_value_kind {
  	k_string,
  	k_signed,
  	k_unsigned,
  	k_invalid
  };
  
  union string_value {
  	unsigned long long u;
  	signed long long s;
  };
  
  static enum string_value_kind expr_parse_string(const char *str,
  						enum symbol_type type,
  						union string_value *val)
  {
  	char *tail;
  	enum string_value_kind kind;
  
  	errno = 0;
  	switch (type) {
  	case S_BOOLEAN:
  	case S_TRISTATE:
  		return k_string;
  	case S_INT:
  		val->s = strtoll(str, &tail, 10);
  		kind = k_signed;
  		break;
  	case S_HEX:
  		val->u = strtoull(str, &tail, 16);
  		kind = k_unsigned;
  		break;
  	case S_STRING:
  	case S_UNKNOWN:
  		val->s = strtoll(str, &tail, 0);
  		kind = k_signed;
  		break;
  	default:
  		return k_invalid;
  	}
  	return !errno && !*tail && tail > str && isxdigit(tail[-1])
  	       ? kind : k_string;
  }

  tristate expr_calc_value(struct expr *e)
  {
  	tristate val1, val2;
  	const char *str1, *str2;

  	enum string_value_kind k1 = k_string, k2 = k_string;
  	union string_value lval = {}, rval = {};
  	int res;

  
  	if (!e)
  		return yes;
  
  	switch (e->type) {
  	case E_SYMBOL:
  		sym_calc_value(e->left.sym);
  		return e->left.sym->curr.tri;
  	case E_AND:
  		val1 = expr_calc_value(e->left.expr);
  		val2 = expr_calc_value(e->right.expr);

  		return EXPR_AND(val1, val2);

  	case E_OR:
  		val1 = expr_calc_value(e->left.expr);
  		val2 = expr_calc_value(e->right.expr);

  		return EXPR_OR(val1, val2);

  	case E_NOT:
  		val1 = expr_calc_value(e->left.expr);

  		return EXPR_NOT(val1);

  	case E_EQUAL:

  	case E_GEQ:
  	case E_GTH:
  	case E_LEQ:
  	case E_LTH:

  	case E_UNEQUAL:

  		break;

  	default:
  		printf("expr_calc_value: %d?
  ", e->type);
  		return no;
  	}

  
  	sym_calc_value(e->left.sym);
  	sym_calc_value(e->right.sym);
  	str1 = sym_get_string_value(e->left.sym);
  	str2 = sym_get_string_value(e->right.sym);
  
  	if (e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
  		k1 = expr_parse_string(str1, e->left.sym->type, &lval);
  		k2 = expr_parse_string(str2, e->right.sym->type, &rval);
  	}
  
  	if (k1 == k_string || k2 == k_string)
  		res = strcmp(str1, str2);
  	else if (k1 == k_invalid || k2 == k_invalid) {
  		if (e->type != E_EQUAL && e->type != E_UNEQUAL) {
  			printf("Cannot compare \"%s\" and \"%s\"
  ", str1, str2);
  			return no;
  		}
  		res = strcmp(str1, str2);
  	} else if (k1 == k_unsigned || k2 == k_unsigned)
  		res = (lval.u > rval.u) - (lval.u < rval.u);
  	else /* if (k1 == k_signed && k2 == k_signed) */
  		res = (lval.s > rval.s) - (lval.s < rval.s);
  
  	switch(e->type) {
  	case E_EQUAL:
  		return res ? no : yes;
  	case E_GEQ:
  		return res >= 0 ? yes : no;
  	case E_GTH:
  		return res > 0 ? yes : no;
  	case E_LEQ:
  		return res <= 0 ? yes : no;
  	case E_LTH:
  		return res < 0 ? yes : no;
  	case E_UNEQUAL:
  		return res ? yes : no;
  	default:
  		printf("expr_calc_value: relation %d?
  ", e->type);
  		return no;
  	}

  }

  static int expr_compare_type(enum expr_type t1, enum expr_type t2)

  {

  	if (t1 == t2)
  		return 0;
  	switch (t1) {

  	case E_LEQ:
  	case E_LTH:
  	case E_GEQ:
  	case E_GTH:
  		if (t2 == E_EQUAL || t2 == E_UNEQUAL)
  			return 1;

  	case E_EQUAL:
  	case E_UNEQUAL:
  		if (t2 == E_NOT)
  			return 1;
  	case E_NOT:
  		if (t2 == E_AND)
  			return 1;
  	case E_AND:
  		if (t2 == E_OR)
  			return 1;
  	case E_OR:

  		if (t2 == E_LIST)

  			return 1;

  	case E_LIST:

  		if (t2 == 0)
  			return 1;
  	default:
  		return -1;
  	}
  	printf("[%dgt%d?]", t1, t2);
  	return 0;

  }

  static inline struct expr *
  expr_get_leftmost_symbol(const struct expr *e)
  {
  
  	if (e == NULL)
  		return NULL;
  
  	while (e->type != E_SYMBOL)
  		e = e->left.expr;
  
  	return expr_copy(e);
  }
  
  /*
   * Given expression `e1' and `e2', returns the leaf of the longest
   * sub-expression of `e1' not containing 'e2.
   */
  struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
  {
  	struct expr *ret;
  
  	switch (e1->type) {
  	case E_OR:
  		return expr_alloc_and(
  		    expr_simplify_unmet_dep(e1->left.expr, e2),
  		    expr_simplify_unmet_dep(e1->right.expr, e2));
  	case E_AND: {
  		struct expr *e;
  		e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
  		e = expr_eliminate_dups(e);
  		ret = (!expr_eq(e, e1)) ? e1 : NULL;
  		expr_free(e);
  		break;
  		}
  	default:
  		ret = e1;
  		break;
  	}
  
  	return expr_get_leftmost_symbol(ret);
  }

  void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)

  {
  	if (!e) {

  		fn(data, NULL, "y");

  		return;
  	}
  
  	if (expr_compare_type(prevtoken, e->type) > 0)

  		fn(data, NULL, "(");

  	switch (e->type) {
  	case E_SYMBOL:
  		if (e->left.sym->name)

  			fn(data, e->left.sym, e->left.sym->name);

  		else

  			fn(data, NULL, "<choice>");

  		break;
  	case E_NOT:

  		fn(data, NULL, "!");

  		expr_print(e->left.expr, fn, data, E_NOT);
  		break;
  	case E_EQUAL:

  		if (e->left.sym->name)
  			fn(data, e->left.sym, e->left.sym->name);
  		else
  			fn(data, NULL, "<choice>");

  		fn(data, NULL, "=");
  		fn(data, e->right.sym, e->right.sym->name);

  		break;
  	case E_LEQ:
  	case E_LTH:
  		if (e->left.sym->name)
  			fn(data, e->left.sym, e->left.sym->name);
  		else
  			fn(data, NULL, "<choice>");
  		fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
  		fn(data, e->right.sym, e->right.sym->name);
  		break;
  	case E_GEQ:
  	case E_GTH:
  		if (e->left.sym->name)
  			fn(data, e->left.sym, e->left.sym->name);
  		else
  			fn(data, NULL, "<choice>");

  		fn(data, NULL, e->type == E_GEQ ? ">=" : ">");

  		fn(data, e->right.sym, e->right.sym->name);

  		break;
  	case E_UNEQUAL:

  		if (e->left.sym->name)
  			fn(data, e->left.sym, e->left.sym->name);
  		else
  			fn(data, NULL, "<choice>");

  		fn(data, NULL, "!=");
  		fn(data, e->right.sym, e->right.sym->name);

  		break;
  	case E_OR:
  		expr_print(e->left.expr, fn, data, E_OR);

  		fn(data, NULL, " || ");

  		expr_print(e->right.expr, fn, data, E_OR);
  		break;
  	case E_AND:
  		expr_print(e->left.expr, fn, data, E_AND);

  		fn(data, NULL, " && ");

  		expr_print(e->right.expr, fn, data, E_AND);
  		break;

  	case E_LIST:

  		fn(data, e->right.sym, e->right.sym->name);

  		if (e->left.expr) {

  			fn(data, NULL, " ^ ");

  			expr_print(e->left.expr, fn, data, E_LIST);

  		}
  		break;
  	case E_RANGE:

  		fn(data, NULL, "[");
  		fn(data, e->left.sym, e->left.sym->name);
  		fn(data, NULL, " ");
  		fn(data, e->right.sym, e->right.sym->name);
  		fn(data, NULL, "]");

  		break;
  	default:
  	  {
  		char buf[32];
  		sprintf(buf, "<unknown type %d>", e->type);

  		fn(data, NULL, buf);

  		break;
  	  }
  	}
  	if (expr_compare_type(prevtoken, e->type) > 0)

  		fn(data, NULL, ")");

  }

  static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)

  {

  	xfwrite(str, strlen(str), 1, data);

  }
  
  void expr_fprint(struct expr *e, FILE *out)
  {
  	expr_print(e, expr_print_file_helper, out, E_NONE);
  }

  static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)

  {

  	struct gstr *gs = (struct gstr*)data;
  	const char *sym_str = NULL;
  
  	if (sym)
  		sym_str = sym_get_string_value(sym);
  
  	if (gs->max_width) {
  		unsigned extra_length = strlen(str);
  		const char *last_cr = strrchr(gs->s, '
  ');
  		unsigned last_line_length;
  
  		if (sym_str)
  			extra_length += 4 + strlen(sym_str);
  
  		if (!last_cr)
  			last_cr = gs->s;
  
  		last_line_length = strlen(gs->s) - (last_cr - gs->s);
  
  		if ((last_line_length + extra_length) > gs->max_width)
  			str_append(gs, "\\
  ");
  	}
  
  	str_append(gs, str);

  	if (sym && sym->type != S_UNKNOWN)

  		str_printf(gs, " [=%s]", sym_str);

  }
  
  void expr_gstr_print(struct expr *e, struct gstr *gs)
  {
  	expr_print(e, expr_print_gstr_helper, gs, E_NONE);
  }