public interface Expr extends Stmt {

	// =========================================================================
	// General Expressions
	// =========================================================================

	/**
	 * Represents a cast expression of the form "<code>(T) e</code>" where
	 * <code>T</code> is the <i>cast type</i> and <code>e</code> the
	 * <i>casted expression</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Cast extends AbstractSyntacticItem implements Expr {
		public Cast(Type type, Expr rhs) {
			super(EXPR_cast, type, rhs);
		}

		public Type getCastType() {
			return (Type) super.get(0);
		}

		public Expr getCastedExpr() {
			return (Expr) super.get(1);
		}

		@Override
		public Cast clone(SyntacticItem[] operands) {
			return new Cast((Type) operands[0], (Expr) operands[1]);
		}

		@Override
		public String toString() {
			return "(" + getCastType() + ") " + getCastedExpr();
		}
	}

	/**
	 * Represents the use of a constant within some expression. For example,
	 * in <code>x + 1</code> the expression <code>1</code> is a constant
	 * expression.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Constant extends AbstractSyntacticItem implements Expr {
		public Constant(Value value) {
			super(EXPR_const, value);
		}

		public Value getValue() {
			return (Value) get(0);
		}

		@Override
		public Constant clone(SyntacticItem[] operands) {
			return new Constant((Value) operands[0]);
		}

		@Override
		public String toString() {
			return getValue().toString();
		}
	}

	/**
	 * Represents a <i>type test expression</i> of the form
	 * "<code>e is T</code>" where <code>e</code> is the <i>test
	 * expression</i> and <code>T</code> is the <i>test type</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Is extends AbstractSyntacticItem implements Expr {
		public Is(Expr lhs, Type rhs) {
			super(EXPR_is, lhs, rhs);
		}

		public Expr getTestExpr() {
			return (Expr) get(0);
		}

		public Type getTestType() {
			return (Type) get(1);
		}

		@Override
		public Is clone(SyntacticItem[] operands) {
			return new Is((Expr) operands[0], (Type) operands[1]);
		}

		@Override
		public String toString() {
			return getTestExpr() + " is " + getTestType();
		}
	}

	/**
	 * Represents an invocation of the form "<code>x.y.f(e1,..en)</code>".
	 * Here, <code>x.y.f</code> constitute a <i>partially-</i> or
	 * <i>fully-qualified name</i> and <code>e1</code> ... <code>en</code>
	 * are the <i>argument expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Invoke extends AbstractSyntacticItem implements Expr {

		public Invoke(Type.FunctionOrMacroOrInvariant type, Name name, Integer selector, Expr[] arguments) {
			super(EXPR_invoke, new SyntacticItem[] { type, name,
					selector != null ? new Value.Int(selector) : null, new Tuple<>(arguments) });
		}

		public Invoke(Type.FunctionOrMacroOrInvariant type, Name name, Value.Int selector, Tuple<Expr> arguments) {
			super(EXPR_invoke, new SyntacticItem[] { type, name, selector, arguments });
		}

		public Type.FunctionOrMacroOrInvariant getSignatureType() {
			return (Type.FunctionOrMacroOrInvariant) get(0);
		}

		public void setSignatureType(Type.FunctionOrMacroOrInvariant type) {
			this.setOperand(0, type);
		}

		public Name getName() {
			return (Name) get(1);
		}

		public Value.Int getSelector() {
			return (Value.Int) get(2);
		}

		public Tuple<Expr> getArguments() {
			return (Tuple) get(3);
		}

		@Override
		public Invoke clone(SyntacticItem[] operands) {
			return new Invoke((Type.FunctionOrMacroOrInvariant) operands[0], (Name) operands[1],
					(Value.Int) operands[2], (Tuple) operands[3]);
		}

		@Override
		public String toString() {
			String r = getName().toString();
			r += getArguments();
			r += "#" + getSelector();
			return r;
		}
	}

	/**
	 * Represents an abstract operator expression over one or more
	 * <i>operand expressions</i>. For example. in <code>arr[i+1]</code> the
	 * expression <code>i+1</code> is an operator expression.
	 *
	 * @author David J. Pearce
	 *
	 */
	public abstract static class Operator extends AbstractSyntacticItem implements Expr {
		public Operator(int opcode, Expr... operands) {
			super(opcode, operands);
		}

		@Override
		public Expr get(int i) {
			return (Expr) super.get(i);
		}

		@Override
		public Expr[] getAll() {
			return (Expr[]) super.getAll();
		}

		@Override
		public abstract Expr clone(SyntacticItem[] operands);
	}

	/**
	 * Represents an abstract quantified expression of the form
	 * "<code>forall(T v1, ... T vn).e</code>" or
	 * "<code>exists(T v1, ... T vn).e</code>" where <code>T1 v1</code> ...
	 * <code>Tn vn</code> are the <i>quantified variable declarations</i>
	 * and <code>e</code> is the body.
	 *
	 * @author David J. Pearce
	 *
	 */
	public abstract static class Quantifier extends AbstractSyntacticItem implements Expr {
		public Quantifier(int opcode, VariableDeclaration[] parameters, Expr body) {
			super(opcode, new Tuple<>(parameters), body);
		}

		public Quantifier(int opcode, Tuple<VariableDeclaration> parameters, Expr body) {
			super(opcode, parameters, body);
		}

		public Tuple<VariableDeclaration> getParameters() {
			return (Tuple<VariableDeclaration>) get(0);
		}

		public Expr getBody() {
			return (Expr) get(1);
		}

		@Override
		public abstract Expr clone(SyntacticItem[] operands);
	}

	/**
	 * Represents an unbounded universally quantified expression of the form
	 * "<code>forall(T v1, ... T vn).e</code>" where <code>T1 v1</code> ...
	 * <code>Tn vn</code> are the <i>quantified variable declarations</i>
	 * and <code>e</code> is the body.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class UniversalQuantifier extends Quantifier {
		public UniversalQuantifier(VariableDeclaration[] parameters, Expr body) {
			super(EXPR_forall, new Tuple<>(parameters), body);
		}

		public UniversalQuantifier(Tuple<VariableDeclaration> parameters, Expr body) {
			super(EXPR_forall, parameters, body);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			return new UniversalQuantifier((Tuple<VariableDeclaration>) operands[0],
					(Expr) operands[1]);
		}

		@Override
		public String toString() {
			String r = "forall";
			r += getParameters();
			r += ".";
			r += getBody();
			return r;
		}
	}

	/**
	 * Represents an unbounded existentially quantified expression of the
	 * form "<code>some(T v1, ... T vn).e</code>" where <code>T1 v1</code>
	 * ... <code>Tn vn</code> are the <i>quantified variable
	 * declarations</i> and <code>e</code> is the body.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class ExistentialQuantifier extends Quantifier {
		public ExistentialQuantifier(VariableDeclaration[] parameters, Expr body) {
			super(EXPR_exists, new Tuple<>(parameters), body);
		}

		public ExistentialQuantifier(Tuple<VariableDeclaration> parameters, Expr body) {
			super(EXPR_exists, parameters, body);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			return new ExistentialQuantifier((Tuple<VariableDeclaration>) operands[0], (Expr) operands[1]);
		}

		@Override
		public String toString() {
			String r = "exists";
			r += getParameters();
			r += ".";
			r += getBody();
			return r;
		}
	}

	/**
	 * Represents a use of some variable within an expression. For example,
	 * in <code>x + 1</code> the expression <code>x</code> is a variable
	 * access expression. Every variable access is associated with a
	 * <i>variable declaration</i> that unique identifies which variable is
	 * being accessed.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class VariableAccess extends AbstractSyntacticItem implements Expr {
		public VariableAccess(VariableDeclaration decl) {
			super(EXPR_varcopy, decl);
		}

		public VariableDeclaration getVariableDeclaration() {
			return (VariableDeclaration) get(0);
		}

		@Override
		public VariableAccess clone(SyntacticItem[] operands) {
			return new VariableAccess((VariableDeclaration) operands[0]);
		}

		@Override
		public String toString() {
			return getVariableDeclaration().getVariableName().toString();
		}
	}


	public abstract static class InfixOperator extends Operator {
		public InfixOperator(int opcode, Expr... operands) {
			super(opcode, operands);
		}

		@Override
		public String toString() {
			String str = getOperatorString();
			String r = "";
			for (int i = 0; i != size(); ++i) {
				if (i != 0) {
					r += str;
				}
				r += get(i);
			}
			return r;
		}

		protected abstract String getOperatorString();
	}

	// =========================================================================
	// Logical Expressions
	// =========================================================================
	/**
	 * Represents a <i>logical conjunction</i> of the form
	 * "<code>e1 && .. && en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class LogicalAnd extends InfixOperator {
		public LogicalAnd(Expr... operands) {
			super(EXPR_and, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if(operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new LogicalAnd(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " && ";
		}
	}

	/**
	 * Represents a <i>logical disjunction</i> of the form
	 * "<code>e1 || .. || en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class LogicalOr extends InfixOperator {
		public LogicalOr(Expr... operands) {
			super(EXPR_or, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if(operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new LogicalOr(ArrayUtils.toArray(Expr.class, operands));
		}


		@Override
		protected String getOperatorString() {
			return " && ";
		}
	}

	/**
	 * Represents a <i>logical implication</i> of the form
	 * "<code>e1 ==> ... ==> en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class LogicalImplication extends InfixOperator {
		public LogicalImplication(Expr... operands) {
			super(EXPR_implies, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if(operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new LogicalImplication(ArrayUtils.toArray(Expr.class, operands));
		}


		@Override
		protected String getOperatorString() {
			return " ==> ";
		}
	}

	/**
	 * Represents a <i>logical biconditional</i> of the form
	 * "<code>e1 <==> ... <==> en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class LogicalIff extends InfixOperator {
		public LogicalIff(Expr... operands) {
			super(EXPR_iff, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if(operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new LogicalIff(ArrayUtils.toArray(Expr.class, operands));
		}


		@Override
		protected String getOperatorString() {
			return " <==> ";
		}
	}

	/**
	 * Represents a <i>logical negation</i> of the form "<code>!e</code>"
	 * where <code>e</code> is the <i>operand expression</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class LogicalNot extends Operator {
		public LogicalNot(Expr operand) {
			super(EXPR_not, operand);
		}

		public Expr getOperand() {
			return get(0);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if(operands.length != 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new LogicalNot((Expr) operands[0]);
		}
	}

	// =========================================================================
	// Comparator Expressions
	// =========================================================================

	/**
	 * Represents an equality expression of the form
	 * "<code>e1 == ... == en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Equal extends InfixOperator {
		public Equal(Expr... operands) {
			super(EXPR_eq, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if(operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Equal(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		public String getOperatorString() {
			return " == ";
		}
	}

	/**
	 * Represents an unequality expression of the form
	 * "<code>e1 != ... != en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class NotEqual extends InfixOperator {
		public NotEqual(Expr... operands) {
			super(EXPR_neq, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if(operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new NotEqual(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " != ";
		}
	}

	/**
	 * Represents a strict <i>inequality expression</i> of the form
	 * "<code>e1 < ... < en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class LessThan extends InfixOperator {
		public LessThan(Expr... operands) {
			super(EXPR_lt, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new LessThan(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " < ";
		}
	}

	/**
	 * Represents a non-strict <i>inequality expression</i> of the form
	 * "<code>e1 <= ... <= en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class LessThanOrEqual extends InfixOperator {
		public LessThanOrEqual(Expr... operands) {
			super(EXPR_lteq, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new LessThanOrEqual(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " <= ";
		}
	}

	/**
	 * Represents a strict <i>inequality expression</i> of the form
	 * "<code>e1 > ... > en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class GreaterThan extends InfixOperator {
		public GreaterThan(Expr... operands) {
			super(EXPR_gt, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new GreaterThan(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " > ";
		}
	}

	/**
	 * Represents a non-strict <i>inequality expression</i> of the form
	 * "<code>e1 >= ... >= en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class GreaterThanOrEqual extends InfixOperator {
		public GreaterThanOrEqual(Expr... operands) {
			super(EXPR_gteq, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new GreaterThanOrEqual(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " >= ";
		}
	}

	// =========================================================================
	// Arithmetic Expressions
	// =========================================================================

	/**
	 * Represents an arithmetic <i>addition expression</i> of the form
	 * "<code>e1 + ... + en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Addition extends InfixOperator {
		public Addition(Expr... operands) {
			super(EXPR_add, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Addition(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " + ";
		}
	}

	/**
	 * Represents an arithmetic <i>subtraction expression</i> of the form
	 * "<code>e1 - ... - en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Subtraction extends InfixOperator {
		public Subtraction(Expr... operands) {
			super(EXPR_sub, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Subtraction(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " - ";
		}
	}

	/**
	 * Represents an arithmetic <i>multiplication expression</i> of the form
	 * "<code>e1 * ... * en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Multiplication extends InfixOperator {
		public Multiplication(Expr... operands) {
			super(EXPR_mul, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Multiplication(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " * ";
		}
	}

	/**
	 * Represents an arithmetic <i>division expression</i> of the form
	 * "<code>e1 / ... / en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Division extends InfixOperator {
		public Division(Expr... operands) {
			super(EXPR_div, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Division(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " / ";
		}
	}

	/**
	 * Represents an arithmetic <i>remainder expression</i> of the form
	 * "<code>e1 / ... / en</code>" where <code>e1</code> ...
	 * <code>en</code> are the <i>operand expressions</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Remainder extends InfixOperator {
		public Remainder(Expr... operands) {
			super(EXPR_rem, operands);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length <= 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Remainder(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		protected String getOperatorString() {
			return " % ";
		}
	}

	/**
	 * Represents an arithmetic <i>negation expression</i> of the form
	 * "<code>-e</code>" where <code>e</code> is the <i>operand
	 * expression</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class Negation extends Operator {
		public Negation(Expr operand) {
			super(EXPR_neg, operand);
		}

		public Expr getOperand() {
			return get(0);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length != 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Negation((Expr) operands[0]);
		}


		@Override
		public String toString() {
			return "-" + getOperand();
		}
	}

	// =========================================================================
	// Reference Expressions
	// =========================================================================
	public static class Dereference extends Operator {
		public Dereference(Expr operand) {
			super(EXPR_deref, operand);
		}

		public Expr getOperand() {
			return get(0);
		}

		@Override
		public Expr clone(SyntacticItem[] operands) {
			if (operands.length != 1) {
				throw new IllegalArgumentException("invalid number of operands");
			}
			return new Dereference((Expr) operands[0]);
		}

		@Override
		public String toString() {
			return "*" + getOperand();
		}
	}

	// =========================================================================
	// Array Expressions
	// =========================================================================

	/**
	 * Represents an <i>array access expression</i> of the form
	 * "<code>arr[e]</code>" where <code>arr</code> is the <i>source
	 * array</i> and <code>e</code> the <i>subscript expression</i>. This
	 * returns the value held in the element determined by <code>e</code>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class ArrayAccess extends Expr.Operator {
		public ArrayAccess(Expr src, Expr index) {
			super(EXPR_arridx, src, index);
		}

		public Expr getSource() {
			return get(0);
		}

		public Expr getSubscript() {
			return get(1);
		}

		@Override
		public ArrayAccess clone(SyntacticItem[] operands) {
			return new ArrayAccess((Expr) operands[0], (Expr) operands[1]);
		}
	}

	/**
	 * Represents an <i>array update expression</i> of the form
	 * "<code>arr[e1:=e2]</code>" where <code>arr</code> is the <i>source
	 * array</i>, <code>e1</code> the <i>subscript expression</i> and
	 * <code>e2</code> is the value expression. This returns a new array
	 * which is equivalent to <code>arr</code> but where the element
	 * determined by <code>e1</code> has the value resulting from
	 * <code>e2</code>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class ArrayUpdate extends Expr.Operator {
		public ArrayUpdate(Expr src, Expr index, Expr value) {
			super(EXPR_arrupdt, src, index, value);
		}

		public Expr getSource() {
			return get(0);
		}

		public Expr getSubscript() {
			return get(1);
		}

		public Expr getValue() {
			return get(2);
		}

		@Override
		public ArrayUpdate clone(SyntacticItem[] operands) {
			return new ArrayUpdate((Expr) operands[0], (Expr) operands[1], (Expr) operands[2]);
		}

		@Override
		public String toString() {
			return getSource() + "[" + getSubscript() + ":=" + getValue() + "]";
		}
	}

	/**
	 * Represents an <i>array initialiser expression</i> of the form
	 * "<code>[e1,...,en]</code>" where <code>e1</code> ... <code>en</code>
	 * are the <i>initialiser expressions</i>. Thus returns a new array made
	 * up from those values resulting from the initialiser expressions.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class ArrayInitialiser extends Expr.Operator {
		public ArrayInitialiser(Expr... elements) {
			super(EXPR_arrinit, elements);
		}

		@Override
		public ArrayInitialiser clone(SyntacticItem[] operands) {
			return new ArrayInitialiser(ArrayUtils.toArray(Expr.class, operands));
		}

		@Override
		public String toString() {
			return Arrays.toString(getAll());
		}
	}

	/**
	 * Represents an <i>array generator expression</i> of the form
	 * "<code>[e1;e2]</code>" where <code>e1</code> is the <i>element
	 * expression</i> and <code>e2</code> is the <i>length expression</i>.
	 * This returns a new array whose length is determined by
	 * <code>e2</code> and where every element has contains the value
	 * determined by <code>e1</code>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class ArrayGenerator extends Expr.Operator {
		public ArrayGenerator(Expr value, Expr length) {
			super(EXPR_arrgen, value, length);
		}

		public Expr getValue() {
			return get(0);
		}

		public Expr getLength() {
			return get(1);
		}

		@Override
		public ArrayGenerator clone(SyntacticItem[] operands) {
			return new ArrayGenerator((Expr) operands[0], (Expr) operands[1]);
		}
	}

	/**
	 * Represents an <i>array length expression</i> of the form
	 * "<code>|arr|</code>" where <code>arr</code> is the <i>source
	 * array</i>. This simply returns the length of array <code>arr</code>.
	 * <code>e</code>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class ArrayLength extends Expr.Operator {
		public ArrayLength(Expr src) {
			super(EXPR_arrlen, src);
		}

		public Expr getSource() {
			return get(0);
		}

		@Override
		public ArrayLength clone(SyntacticItem[] operands) {
			return new ArrayLength((Expr) operands[0]);
		}

		@Override
		public String toString() {
			return "|" + getSource() + "|";
		}
	}

	// =========================================================================
	// Record Expressions
	// =========================================================================

	/**
	 * Represents a <i>record access expression</i> of the form
	 * "<code>rec.f</code>" where <code>rec</code> is the <i>source record</i>
	 * and <code>f</code> is the <i>field</i>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class RecordAccess extends AbstractSyntacticItem implements Expr {
		public RecordAccess(Expr lhs, Identifier rhs) {
			super(EXPR_recfield, lhs, rhs);
		}

		public Expr getSource() {
			return (Expr) get(0);
		}

		public Identifier getField() {
			return (Identifier) get(1);
		}

		@Override
		public RecordAccess clone(SyntacticItem[] operands) {
			return new RecordAccess((Expr) operands[0], (Identifier) operands[1]);
		}

		@Override
		public String toString() {
			return getSource() + "." + getField();
		}
	}

	/**
	 * Represents a <i>record initialiser</i> expression of the form
	 * <code>{ f1: e1, ..., fn: en }</code> where <code>f1: e1</code> ...
	 * <code>fn: en</code> are <i>field initialisers</code>. This returns a
	 * new record where each field holds the value resulting from its
	 * corresponding expression.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class RecordInitialiser extends AbstractSyntacticItem implements Expr {
		public RecordInitialiser(Pair<Identifier, Expr>... fields) {
			super(EXPR_recinit, fields);
		}

		public Pair<Identifier, Expr>[] getFields() {
			return ArrayUtils.toArray(Pair.class, getAll());
		}

		@Override
		public RecordInitialiser clone(SyntacticItem[] operands) {
			return new RecordInitialiser(ArrayUtils.toArray(Pair.class, operands));
		}
	}

	/**
	 * Represents a <i>record update expression</i> of the form
	 * "<code>rec[f:=e]</code>" where <code>rec</code> is the <i>source
	 * record</i>, <code>f</code> is the <i>field</i> and <code>e</code> is
	 * the <i>value expression</i>. This returns a new record which is
	 * equivalent to <code>rec</code> but where the element in field
	 * <code>f</code> has the value resulting from <code>e</code>.
	 *
	 * @author David J. Pearce
	 *
	 */
	public static class RecordUpdate extends AbstractSyntacticItem implements Expr {
		public RecordUpdate(Expr lhs, Identifier mhs, Expr rhs) {
			super(EXPR_recupdt, lhs, mhs, rhs);
		}

		public Expr getSource() {
			return (Expr) get(0);
		}

		public Identifier getField() {
			return (Identifier) get(1);
		}

		public Expr getValue() {
			return (Expr) get(2);
		}

		@Override
		public RecordUpdate clone(SyntacticItem[] operands) {
			return new RecordUpdate((Expr) operands[0], (Identifier) operands[1], (Expr) operands[2]);
		}

		@Override
		public String toString() {
			return getSource() + "{" + getField() + ":=" + getValue() + "}";
		}
	}
} public static class ResolutionError extends Exception {
	/**
	 *
	 */
	private static final long serialVersionUID = 1L;
	private final Name name;

	public ResolutionError(Name name, String message) {
		super(message);
		if (name == null) {
			throw new IllegalArgumentException("name is null");
		}
		this.name = name;
	}

	/**
	 * Get the name being resolved that lead to this error.
	 *
	 * @return
	 */
	public Name getName() {
		return name;
	}
} public interface Formula extends Expr {

	@Override
	public Formula clone(SyntacticItem[] children);

	public static class Truth extends Expr.Constant implements Formula {

		public Truth(boolean value) {
			super(new Value.Bool(value));
		}

		public Truth(Value.Bool value) {
			super(value);
		}

		public boolean holds() {
			return getValue().get();
		}

		@Override
		public Value.Bool getValue() {
			return (Value.Bool) super.getValue();
		}

		@Override
		public Truth clone(SyntacticItem[] children) {
			return new Truth((Value.Bool) children[0]);
		}
	}

	public static class Conjunct extends Expr.Operator implements Formula {

		public Conjunct(Formula... operands) {
			super(WyalFile.EXPR_and, operands);
		}

		@Override
		public Formula get(int i) {
			return (Formula) super.get(i);
		}

		@Override
		public Formula[] getAll() {
			return (Formula[]) super.getAll();
		}

		@Override
		public Conjunct clone(SyntacticItem[] children) {
			return new Conjunct(ArrayUtils.toArray(Formula.class, children));
		}

		@Override
		public String toString() {
			String r = "";
			for (int i = 0; i != size(); ++i) {
				if (i != 0) {
					r += " && ";
				}
				r += get(i);
			}
			return r;
		}
	}

	public static class Disjunct extends Expr.Operator implements Formula {

		public Disjunct(Formula... operands) {
			super(WyalFile.EXPR_or, operands);
		}

		@Override
		public Formula get(int i) {
			return (Formula) super.get(i);
		}

		@Override
		public Formula[] getAll() {
			return (Formula[]) super.getAll();
		}

		@Override
		public Disjunct clone(SyntacticItem[] children) {
			return new Disjunct(ArrayUtils.toArray(Formula.class, children));
		}

		@Override
		public String toString() {
			String r = "";
			for (int i = 0; i != size(); ++i) {
				if (i != 0) {
					r += " || ";
				}
				r += get(i);
			}
			return r;
		}
	}

	public static class Quantifier extends Expr.Quantifier implements Formula {
		public Quantifier(boolean sign, VariableDeclaration parameter, Formula body) {
			super(sign ? WyalFile.EXPR_forall : WyalFile.EXPR_exists, new Tuple<>(parameter), body);
		}

		public Quantifier(boolean sign, VariableDeclaration[] parameters, Formula body) {
			super(sign ? WyalFile.EXPR_forall : WyalFile.EXPR_exists,
					new Tuple<>(parameters), body);
		}

		public Quantifier(boolean sign, Tuple<VariableDeclaration> parameters, Formula body) {
			super(sign ? WyalFile.EXPR_forall : WyalFile.EXPR_exists, parameters, body);
		}

		public boolean getSign() {
			return getOpcode() == WyalFile.EXPR_forall;
		}

		@Override
		public Tuple<VariableDeclaration> getParameters() {
			return (Tuple<VariableDeclaration>) get(0);
		}

		@Override
		public Formula getBody() {
			return (Formula) get(1);
		}

		@Override
		public Formula.Quantifier clone(SyntacticItem[] children) {
			return new Formula.Quantifier(getSign(), (Tuple) children[0], (Formula) children[1]);
		}
	}

	public interface Equation extends Formula {
		@Override
		public Expr get(int i);

		@Override
		public Expr[] getAll();
	}

	public interface ArithmeticEquation extends Equation {
		@Override
		public Expr get(int i);

		@Override
		public Expr[] getAll();
	}

	public static class Inequality extends Expr.GreaterThanOrEqual implements ArithmeticEquation {

		public Inequality(Expr lhs, Expr rhs) {
			super(lhs, rhs);
		}

		@Override
		public Inequality clone(SyntacticItem[] children) {
			return new Inequality((Expr) children[0],(Expr) children[1]);
		}
	}

	public static class Equality extends Expr.Operator implements Equation {
		public Equality(boolean sign, Expr lhs, Expr rhs) {
			super(sign ? WyalFile.EXPR_eq : WyalFile.EXPR_neq, lhs, rhs);
		}

		public Equality(boolean sign, Expr[] arr) {
			super(sign ? WyalFile.EXPR_eq : WyalFile.EXPR_neq, arr);
		}

		public boolean getSign() {
			return getOpcode() == WyalFile.EXPR_eq;
		}

		@Override
		public Equality clone(SyntacticItem[] children) {
			return new Equality(getSign(),(Expr) children[0],(Expr) children[1]);
		}

		@Override
		public String toString() {
			String str = getSign() ? " == " : " != ";
			String r = "";
			for (int i = 0; i != size(); ++i) {
				if (i != 0) {
					r += str;
				}
				r += get(i);
			}
			return r;
		}
	}

	public static class ArithmeticEquality extends Equality implements ArithmeticEquation {
		public ArithmeticEquality(boolean sign, Expr lhs, Expr rhs) {
			super(sign, lhs, rhs);
		}

		@Override
		public ArithmeticEquality clone(SyntacticItem[] children) {
			return new ArithmeticEquality(getSign(),(Expr) children[0],(Expr) children[1]);
		}
	}

	public static class Invoke extends Expr.Invoke implements Formula {
		private boolean sign;

		public Invoke(boolean sign, Type.FunctionOrMacroOrInvariant type, Name name, Integer selector,
				Expr... arguments) {
			super(type, name, selector == null ? null : selector, arguments);
			this.sign = sign;
		}

		public Invoke(boolean sign, Type.FunctionOrMacroOrInvariant type, Name name, Value.Int selector,
				Tuple<Expr> arguments) {
			super(type, name, selector, arguments);
			this.sign = sign;
		}

		public boolean getSign() {
			return sign;
		}

		@Override
		public byte[] getData() {
			return new byte[sign?1:0];
		}

		@Override
		public boolean equals(Object o) {
			// FIXME: the need for this method is something of a hack.
			if(o instanceof Formula.Invoke) {
				Formula.Invoke i = (Formula.Invoke) o;
				return sign == i.sign && super.equals(o);
			} else if(o instanceof Expr.Invoke && !sign) {
				return false;
			} else {
				return super.equals(o);
			}
		}

		@Override
		public Formula.Invoke clone(SyntacticItem[] children) {
			return new Formula.Invoke(sign,(Type.FunctionOrMacroOrInvariant) children[0], (Name) children[1],
					(Value.Int) children[2], (Tuple) children[3]);
		}
	}

	public static class Is extends Expr.Is implements Formula {
		public Is(Expr lhs, Type rhs) {
			super(lhs,rhs);
		}

		@Override
		public Formula.Is clone(SyntacticItem[] children) {
			return new Formula.Is((Expr) children[0],(Type) children[1]);
		}
	}
} public interface Proof {

	/**
	 * Get the assertion to which this proof applies.
	 *
	 * @return
	 */
	public Declaration.Assert getAssertion();

	/**
	 * Determine whether or not the proof is complete. That is, whether or not
	 * the proof demonstrates that the given assertion is correct.
	 *
	 * @return
	 */
	public boolean isComplete();

	/**
	 * Determine the number of steps in this proof.
	 *
	 * @return
	 */
	public int size();

	/**
	 * Get the ith step in this proof.
	 *
	 * @param ith
	 * @return
	 */
	public State getState(int ith);

	/**
	 * Get the heap in which this proof is operating within.
	 *
	 * @return
	 */
	public SyntacticHeap getHeap();

	/**
	 * A proof branch considered of one or more states which were derived from
	 * an existing state using a given rule.
	 *
	 * @author David J. Peare
	 *
	 */
	public interface State {
		/**
		 * Get the enclosing proof for this step. Every step must be associated
		 * with a proof, and all connected steps must be in the same proof.
		 *
		 * @return
		 */
		Proof getProof();

		/**
		 * Get the parent (i.e. before) state for this step. This is
		 * <code>null</code> if this state represents the root of the proof.
		 *
		 * @return
		 */
		State getParent();

		/**
		 * Determine whether a truth is already known or not. Truths which are
		 * already known do not need to be reintroduced.
		 *
		 * @param truth
		 * @return
		 */
		boolean isKnown(Formula truth);

		/**
		 * Get the delta between this state and its parent.
		 *
		 * @return
		 */
		Delta getDelta();

		/**
		 * Get the delta between this state and an ancestor.
		 *
		 * @return
		 */
		Delta getDelta(State ancestor);

		/**
		 * Get the name of the rule used for this step.
		 *
		 * @return
		 */
		Rule getRule();

		/**
		 * Get the typing environment at this state in a given proof. The type
		 * environment gives the current type for all declared variables. The
		 * environment is not static as the type of a given variable can be
		 * refined at any given state as more facts become known.
		 *
		 * @return
		 */
		TypeInferer.Environment getTypeEnvironment();

		/**
		 * Get the formulae on which this step depends
		 *
		 * @return
		 */
		List<Formula> getDependencies();

		/**
		 * Get the number of child steps originating from this step
		 *
		 * @return
		 */
		int numberOfChildren();

		/**
		 * Get the child state resulting from this step
		 *
		 * @return
		 */
		State getChild(int ith);

		void applyBypass(State bypass);

		/**
		 * Apply a simple proof step which splits a given disjunct into several
		 * sub-states.
		 *
		 * @param disjunct
		 * @return
		 */
		State[] split(Formula.Disjunct disjunct);

		/**
		 * Subsume a given truth by a replacement.
		 *
		 * @param rule
		 * @param truth
		 * @param replacement
		 * @param dependencies
		 * @return
		 */
		State subsume(Proof.Rule rule, Formula truth, Formula replacement, Formula... dependencies);

		/**
		 * Infer a new fact from one or more existing facts.
		 *
		 * @param rule
		 * @param truth
		 * @param dependencies
		 * @return
		 */
		State infer(Proof.Rule rule, Formula truth, Formula... dependencies);

		/**
		 * Refine the type of a given variable in this state. That is, make the
		 * type more precise at this point.
		 *
		 * @param rule
		 *            The rule which is causing this particular refinement.
		 * @param variable
		 *            The variable whose type is being refined.
		 * @param type
		 *            The type which this variable is refined with.
		 * @param dependencies
		 *            The immediate dependencies needed to establish this
		 *            refinement.
		 *
		 * @return
		 */
		State refine(Proof.Rule rule, WyalFile.VariableDeclaration variable, WyalFile.Type type, Formula... dependencies);

		/**
		 * Ensure a given formula is properly allocated into this state.
		 *
		 * @param f
		 * @return
		 */
		Formula allocate(Formula f);
	}

	/**
	 * A proof delta represents a set of truths which have been introduced
	 * during one or more proof steps.
	 *
	 * @author David J. Pearce
	 *
	 */
	interface Delta {

		/**
		 * Check whether or not a given formula is in the additions set
		 *
		 * @param truth
		 * @return
		 */
		public boolean isAddition(Formula truth);

		/**
		 * Check whether or not a given formula is in the removals set
		 *
		 * @param truth
		 * @return
		 */
		public boolean isRemoval(Formula truth);

		/**
		 * Get the set of truths added to this delta
		 *
		 * @return
		 */
		public Set getAdditions();

		/**
		 * Get the set of truths removed from this delta
		 *
		 * @return
		 */
		public Set getRemovals();

		/**
		 * Add a new formula to this delta
		 *
		 * @param truth
		 * @return
		 */
		public Delta add(Formula truth);

		/**
		 * Remove a truth from this delta (e.g. because it has been processed).
		 *
		 * @param truth
		 * @return
		 */
		public Delta remove(Formula truth);

		/**
		 * Apply a given delta on top of this one.
		 *
		 * @param delta
		 * @return
		 */
		public Delta apply(Delta delta);

		/**
		 * A set of truths in a delta, either representing those added or those
		 * removed.
		 *
		 * @author David J. Pearce
		 *
		 */
		public interface Set {
			/**
			 * Determine the number of truths in this set
			 *
			 * @return
			 */
			public int size();

			/**
			 * Check whether the given formula is contained within this set or
			 * not.
			 *
			 * @param truth
			 * @return
			 */
			public boolean contains(Formula truth);

			/**
			 * Get the ith truth in this set
			 *
			 * @param ith
			 * @return
			 */
			public Formula get(int ith);

			/**
			 * Add a truth to this set.
			 *
			 * @param truth
			 * @return
			 */
			public Set add(Formula truth);

			/**
			 * Remove a formula from this set
			 *
			 * @param truth
			 * @return
			 */
			public Set remove(Formula truth);

			/**
			 * Union two sets together
			 *
			 * @param other
			 * @return
			 */
			public Set union(Proof.Delta.Set other);

			/**
			 * Remove the elements of one set from this
			 *
			 * @param other
			 * @return
			 */
			public Set remove(Proof.Delta.Set other);
		}
	}

	/**
	 * A proof rule represents the transformation of a given proof according to
	 * some logical inference.
	 *
	 * @author David J. Pearce
	 *
	 */
	interface Rule {
		/**
		 * Get the name of this rule
		 * @return
		 */
		public String getName();
	}

	interface LinearRule extends Rule {
		/**
		 * Apply a given rule to a given state, producing one potentially
		 * updated state. If the rule does not apply or produces no additional
		 * information, then the original state is returned untouched.
		 *
		 * @param current
		 *            The current state of truth. That is, everything which is
		 *            known to be true at this point.
		 * @param head
		 *            The current tip of the proof branch. This maybe some
		 *            distance in the future from the current state, and
		 *            identifies truths which have yet to be processed.
		 * @return One or more states representing the remaining states to be
		 *         discharged
		 */
		State apply(State current, State head) throws ResolutionError;
	}

	interface NonLinearRule extends Rule {
		/**
		 * Apply a given rule to a given state, producing one (or more)
		 * potentially updated states. If the rule does not apply or produces no
		 * additional information, then the original state is returned
		 * untouched.
		 *
		 * @param current
		 *            The current state of truth. That is, everything which is
		 *            known to be true at this point.
		 * @param head
		 *            The current tip of the proof branch. This maybe some
		 *            distance in the future from the current state, and
		 *            identifies truths which have yet to be processed.
		 * @return One or more states representing the remaining states to be
		 *         discharged
		 */
		State[] apply(State current, State head) throws ResolutionError;
	}
} public interface State {
	/**
	 * Get the enclosing proof for this step. Every step must be associated
	 * with a proof, and all connected steps must be in the same proof.
	 *
	 * @return
	 */
	Proof getProof();

	/**
	 * Get the parent (i.e. before) state for this step. This is
	 * <code>null</code> if this state represents the root of the proof.
	 *
	 * @return
	 */
	State getParent();

	/**
	 * Determine whether a truth is already known or not. Truths which are
	 * already known do not need to be reintroduced.
	 *
	 * @param truth
	 * @return
	 */
	boolean isKnown(Formula truth);

	/**
	 * Get the delta between this state and its parent.
	 *
	 * @return
	 */
	Delta getDelta();

	/**
	 * Get the delta between this state and an ancestor.
	 *
	 * @return
	 */
	Delta getDelta(State ancestor);

	/**
	 * Get the name of the rule used for this step.
	 *
	 * @return
	 */
	Rule getRule();

	/**
	 * Get the typing environment at this state in a given proof. The type
	 * environment gives the current type for all declared variables. The
	 * environment is not static as the type of a given variable can be
	 * refined at any given state as more facts become known.
	 *
	 * @return
	 */
	TypeInferer.Environment getTypeEnvironment();

	/**
	 * Get the formulae on which this step depends
	 *
	 * @return
	 */
	List<Formula> getDependencies();

	/**
	 * Get the number of child steps originating from this step
	 *
	 * @return
	 */
	int numberOfChildren();

	/**
	 * Get the child state resulting from this step
	 *
	 * @return
	 */
	State getChild(int ith);

	void applyBypass(State bypass);

	/**
	 * Apply a simple proof step which splits a given disjunct into several
	 * sub-states.
	 *
	 * @param disjunct
	 * @return
	 */
	State[] split(Formula.Disjunct disjunct);

	/**
	 * Subsume a given truth by a replacement.
	 *
	 * @param rule
	 * @param truth
	 * @param replacement
	 * @param dependencies
	 * @return
	 */
	State subsume(Proof.Rule rule, Formula truth, Formula replacement, Formula... dependencies);

	/**
	 * Infer a new fact from one or more existing facts.
	 *
	 * @param rule
	 * @param truth
	 * @param dependencies
	 * @return
	 */
	State infer(Proof.Rule rule, Formula truth, Formula... dependencies);

	/**
	 * Refine the type of a given variable in this state. That is, make the
	 * type more precise at this point.
	 *
	 * @param rule
	 *            The rule which is causing this particular refinement.
	 * @param variable
	 *            The variable whose type is being refined.
	 * @param type
	 *            The type which this variable is refined with.
	 * @param dependencies
	 *            The immediate dependencies needed to establish this
	 *            refinement.
	 *
	 * @return
	 */
	State refine(Proof.Rule rule, WyalFile.VariableDeclaration variable, WyalFile.Type type, Formula... dependencies);

	/**
	 * Ensure a given formula is properly allocated into this state.
	 *
	 * @param f
	 * @return
	 */
	Formula allocate(Formula f);
} public class Simplification extends AbstractProofRule implements Proof.LinearRule {

	private final static Formula TRUE = new Formula.Truth(true);
	private final static Formula FALSE = new Formula.Truth(false);

	public Simplification(TypeSystem types) {
		super(null,types);
	}

	@Override
	public String getName() {
		return "Simp";
	}


	@Override
	public State apply(State head, Formula truth) throws ResolutionError {
		Formula simplifiedTruth = simplify(truth);
		if(!simplifiedTruth.equals(truth)) {
			// FIXME: useful optimisation would be to support pointer equality
			// for the above test.
			head = head.subsume(this, truth, simplifiedTruth);
		}
		return head;
	}

	/**
	 * Recursively simplify a given formula by applying the "standard"
	 * simplifications for each kind. If no simplification is performed, this
	 * returns the original object in tact.
	 *
	 * @param f
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public Formula simplify(Formula f) throws ResolutionError {
		switch (f.getOpcode()) {
		case EXPR_const:
			return f;
		case EXPR_and:
			return simplifyConjunct((Formula.Conjunct) f);
		case EXPR_or:
			return simplifyDisjunct((Formula.Disjunct) f);
		case EXPR_exists:
		case EXPR_forall: {
			return simplifyQuantifier((Formula.Quantifier) f);
		}
		case EXPR_eq:
		case EXPR_neq: {
			if (f instanceof ArithmeticEquality) {
				return simplifyArithmeticEquality((Formula.ArithmeticEquality) f);
			} else {
				return simplifyEquality((Formula.Equality) f);
			}
		}
		case EXPR_lt:
		case EXPR_gteq: {
			return simplifyInequality((Formula.Inequality) f);
		}
		case EXPR_invoke: {
			return simplifyInvoke((Formula.Invoke) f);
		}
		case EXPR_is: {
			return simplifyIs((Formula.Is) f);
		}
		default:
			throw new IllegalArgumentException("invalid formula opcode: " + f.getOpcode());
		}
	}

	public Formula simplifyConjunct(Conjunct conjunct) throws ResolutionError {
		Formula[] children = conjunct.getAll();
		Formula[] nChildren = simplify(children);
		// Check whether contains false
		if (ArrayUtils.firstIndexOf(nChildren, FALSE) >= 0) {
			// Any conjunct containing false equals false
			return new Formula.Truth(false);
		}
		// Expand any nested conjuncts
		nChildren = inlineNestedConjuncts(nChildren);
		// Remove any duplicate types
		nChildren = ArrayUtils.removeDuplicates(nChildren);
		// Remove all occurrences of true
		nChildren = ArrayUtils.removeAll(nChildren, TRUE);
		//
		if(nChildren.length == 0) {
			return new Formula.Truth(true);
		} else if(nChildren.length == 1) {
			return nChildren[0];
		} else if(children == nChildren) {
			return conjunct;
		} else {
			return new Formula.Conjunct(nChildren);
		}
	}

	public Formula simplifyDisjunct(Disjunct disjunct) throws ResolutionError {
		Formula[] children = disjunct.getAll();
		Formula[] nChildren = simplify(children);
		// Check whether contains true
		if (ArrayUtils.firstIndexOf(nChildren, TRUE) >= 0) {
			// Any disjunct containing true equals true
			return new Formula.Truth(true);
		}
		// Expand any nested disjuncts
		nChildren = inlineNestedDisjuncts(nChildren);
		// Remove any duplicate types
		nChildren = ArrayUtils.removeDuplicates(nChildren);
		// Remove all occurrences of false
		nChildren = ArrayUtils.removeAll(nChildren, FALSE);
		//
		if(nChildren.length == 0) {
			return new Formula.Truth(false);
		} else if(nChildren.length == 1) {
			return nChildren[0];
		} else if(children == nChildren) {
			return disjunct;
		} else {
			return new Formula.Disjunct(nChildren);
		}
	}

	public Formula[] simplify(Formula[] children) throws ResolutionError {
		Formula[] nChildren = children;
		for (int i = 0; i != nChildren.length; ++i) {
			Formula child = children[i];
			Formula nChild = simplify(child);
			if (child != nChild && children == nChildren) {
				nChildren = Arrays.copyOf(children, children.length);
			}
			nChildren[i] = nChild;
		}
		return nChildren;
	}

	/**
	 * Simplify a quantified formula. In essence, if the body is a truth value
	 * then that is returned. For example, <code>forall x.true</code> is simply
	 * <code>true</code>.
	 *
	 * @param quantifier
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public Formula simplifyQuantifier(Quantifier quantifier) throws ResolutionError {
		Formula body = quantifier.getBody();
		Formula nBody = simplify(body);
		if (nBody instanceof Truth) {
			return nBody;
		} else if (nBody != body) {
			return new Quantifier(quantifier.getSign(), quantifier.getParameters(), nBody);
		} else {
			return quantifier;
		}
	}

	/**
	 * Simplify an inequality by canceling, evaluating and/or balancing:
	 * <ol>
	 * <li><b>Canceling</b> is the process of removing commons terms from both
	 * sides. For example, in <code>x+y < x</code> we can cancel <code>x</code>
	 * to give <code>y < 0</code>.</li>
	 * <li><b>Evaluating</b> is the process of reducing a constant inequality to
	 * either <code>true</code> or <code>false</code>. For example,
	 * <code>0 < 1</code> reduces to <code>true</code> whilst
	 * <code>1 >= 0</code> reduces to <code>false</code>.</li>
	 * <li><b>Balancing</b> is the process of eliminating negative terms and
	 * factorising. For example, <code>-x < 1</code> is balanced to
	 * <code>0 < 1 + x</code>. Likewise, <code>2*x < 6*y</code> is factorised to
	 * <code>x < 3*y</code>.</li>
	 * </ol>
	 *
	 * @param ieq
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public Formula simplifyInequality(Inequality ieq) throws ResolutionError {
		Expr lhs = ieq.get(0);
		Expr rhs = ieq.get(1);
		Expr nLhs = simplifyExpression(lhs);
		Expr nRhs = simplifyExpression(rhs);
		Pair<Expr, Expr> bs = normaliseBounds(nLhs, nRhs);
		nLhs = bs.getFirst();
		nRhs = bs.getSecond();
		//
		if (nLhs instanceof Expr.Constant && nRhs instanceof Expr.Constant) {
			Value.Int lhs_v = (Value.Int) ((Expr.Constant) nLhs).getValue();
			Value.Int rhs_v = (Value.Int) ((Expr.Constant) nRhs).getValue();
			return evaluateInequality(ieq.getOpcode(), lhs_v, rhs_v);
		} else if (nLhs.equals(nRhs)) {
			return new Formula.Truth(true);
		} else if(lhs.equals(nLhs) && rhs.equals(nRhs)) {
			return ieq;
		} else {
			return new Inequality(bs.getFirst(), bs.getSecond());
		}
	}

	/**
	 * Simplify an arithmetic equality by canceling, evaluating and/or
	 * balancing:
	 * <ol>
	 * <li><b>Canceling</b> is the process of removing commons terms from both
	 * sides. For example, in <code>x+y == x</code> we can cancel <code>x</code>
	 * to give <code>y == 0</code>.</li>
	 * <li><b>Evaluating</b> is the process of reducing a constant inequality to
	 * either <code>true</code> or <code>false</code>. For example,
	 * <code>0 == 0</code> reduces to <code>true</code> whilst
	 * <code>1 == 0</code> reduces to <code>false</code>.</li>
	 * <li><b>Balancing</b> is the process of eliminating negative terms and
	 * factorising. For example, <code>-x == 1</code> is balanced to
	 * <code>0 == 1 + x</code>. Likewise, <code>2*x == 6*y</code> is factorised
	 * to <code>x == 3*y</code>.</li>
	 * </ol>
	 *
	 * @param ieq
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public Formula simplifyArithmeticEquality(ArithmeticEquality eq) throws ResolutionError {
		Expr lhs = eq.get(0);
		Expr rhs = eq.get(1);
		Expr nLhs = simplifyExpression(lhs);
		Expr nRhs = simplifyExpression(rhs);
		Pair<Expr, Expr> bs = normaliseBounds(nLhs, nRhs);
		nLhs = bs.getFirst();
		nRhs = bs.getSecond();
		if (nLhs instanceof Expr.Constant && nRhs instanceof Expr.Constant) {
			Value lhs_v = ((Expr.Constant) nLhs).getValue();
			Value rhs_v = ((Expr.Constant) nRhs).getValue();
			return evaluateEquality(eq.getOpcode(), lhs_v, rhs_v);
		} else if (nLhs.equals(nRhs)) {
			return new Formula.Truth(eq.getSign());
		}
		Arithmetic.Polynomial difference = Arithmetic.asPolynomial(nLhs).subtract(Arithmetic.asPolynomial(nRhs));
		if(difference.isConstant()) {
			BigInteger constant = difference.toConstant();
			return new Formula.Truth(constant.equals(BigInteger.ZERO));
		}
		// Handle orientation
		if(nLhs.compareTo(nRhs) > 0) {
			Expr tmp = nLhs;
			nLhs = nRhs;
			nRhs = tmp;
		}
		if(nLhs.equals(lhs) && nRhs.equals(rhs)) {
			// FIXME: above could be more efficient
			return eq;
		} else {
			return new ArithmeticEquality(eq.getSign(), nLhs, nRhs);
		}
	}

	/**
	 * Simplify a non-arithmetic equality by attempting to evaluate it. For
	 * example, <code>true == false</code> reduces to <code>false</code>. In the
	 * case that neither side is a constant, then the original equality is
	 * returned.
	 *
	 * @param eq
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public Formula simplifyEquality(Equality eq) throws ResolutionError {
		Expr lhs = eq.get(0);
		Expr rhs = eq.get(1);
		Expr nLhs = simplifyExpression(lhs);
		Expr nRhs = simplifyExpression(rhs);
		if (nLhs instanceof Expr.Constant && nRhs instanceof Expr.Constant) {
			Value lhs_v = ((Expr.Constant) nLhs).getValue();
			Value rhs_v = ((Expr.Constant) nRhs).getValue();
			return evaluateEquality(eq.getOpcode(), lhs_v, rhs_v);
		} else if (nLhs.equals(nRhs)) {
			return new Formula.Truth(eq.getSign());
		}
		// Handle orientation
		if(nLhs.compareTo(nRhs) > 0) {
			Expr tmp = nLhs;
			nLhs = nRhs;
			nRhs = tmp;
		}
		// Now decide whether need to create a new equality or not.
		if(nLhs == lhs && nRhs == rhs) {
			return eq;
		} else {
			return new Equality(eq.getSign(),nLhs,nRhs);
		}
	}

	public Formula simplifyInvoke(Invoke ivk) throws ResolutionError {
		Tuple<Expr> args = ivk.getArguments();
		Expr[] nChildren = new Expr[args.size()];
		boolean changed = false;
		for (int i = 0; i != args.size(); ++i) {
			Expr child = args.get(i);
			Expr nChild = simplifyExpression(child);
			//
			changed |= (child != nChild);
			nChildren[i] = nChild;
		}
		if(!changed) {
			return ivk;
		} else {
			Tuple<Expr> nArgs = new Tuple<>(nChildren);
			return new Invoke(ivk.getSign(),ivk.getSignatureType(),ivk.getName(),ivk.getSelector(),nArgs);
		}
	}

	public Formula simplifyIs(Formula.Is e) throws ResolutionError {
		Expr lhs = e.getTestExpr();
		Expr nLhs = simplifyExpression(lhs);
		if(lhs != nLhs) {
			return new Formula.Is(nLhs, e.getTestType());
		} else {
			return e;
		}
	}


	public Expr[] simplifyExpressions(Expr[] children) throws ResolutionError {
		Expr[] nChildren = children;
		for (int i = 0; i != children.length; ++i) {
			Expr child = children[i];
			Expr nChild = simplifyExpression(child);
			if (child != nChild && children == nChildren) {
				nChildren = Arrays.copyOf(children, children.length);
			}
			nChildren[i] = nChild;
		}
		return nChildren;
	}

	/**
	 * Convert an arbitrary expression to an atom.
	 *
	 * @param e
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public Expr simplifyExpression(Expr e) throws ResolutionError {
		switch (e.getOpcode()) {
		case EXPR_varcopy:
			return e;
		case EXPR_const:
			return simplifyConstant((Expr.Constant) e);
		case EXPR_invoke:
			return simplifyInvoke((Expr.Invoke) e);
		case EXPR_arridx:
			return simplifyArrayIndex((Expr.Operator) e);
		case EXPR_arrupdt:
			return simplifyArrayUpdate((Expr.Operator) e);
		case EXPR_arrlen:
			return simplifyArrayLength((Expr.Operator)e);
		case EXPR_arrinit:
		case EXPR_arrgen:
		case EXPR_div: // temporary for now
		case EXPR_rem: // temporary for now
			return simplifyNonArithmetic((Expr.Operator) e);
		case EXPR_neg:
		case EXPR_add:
		case EXPR_mul:
		case EXPR_sub:
			return simplifyArithmetic((Expr.Operator) e);
		case EXPR_recinit:
			return simplifyRecordInitialiser((Expr.RecordInitialiser) e);
		case EXPR_recfield:
			return simplifyRecordAccess((Expr.RecordAccess) e);
		case EXPR_recupdt:
			return simplifyRecordUpdate((Expr.RecordUpdate) e);
		case EXPR_deref:
			return simplifyDereference((Expr.Dereference) e);
		case EXPR_not:
		case EXPR_and:
		case EXPR_or:
		case EXPR_exists:
		case EXPR_forall:
		case EXPR_eq:
		case EXPR_neq:
		case EXPR_lt:
		case EXPR_lteq:
		case EXPR_gt:
		case EXPR_gteq:
		case EXPR_is:
			if(e instanceof Formula) {
				return simplify((Formula) e);
			} else {
				// We need toFormula here because of the potential for arbitrarily
				// nested expressions to contain these constructs.
				return simplify(Formulae.toFormula(e,types));
			}
		default:
			throw new IllegalArgumentException("cannot convert expression to atom: " + e.getClass().getName());
		}
	}

	public Expr simplifyConstant(Expr.Constant e) {
		Value val = e.getValue();
		if (val instanceof Value.Bool) {
			Value.Bool b = (Value.Bool) val;
			return new Formula.Truth(b.get());
		} else {
			return e;
		}
	}

	public Expr simplifyRecordInitialiser(Expr.RecordInitialiser e) throws ResolutionError {
		Pair<Identifier,Expr>[] fields = e.getFields();
		Pair<Identifier,Expr>[] nFields = fields;
		for(int i=0;i!=fields.length;++i) {
			Expr ith = fields[i].getSecond();
			Expr nIth = simplifyExpression(ith);
			if(ith != nIth && fields == nFields) {
				nFields = Arrays.copyOf(fields, fields.length);
			}
			if(ith != nIth) {
				nFields[i] = new Pair<>(fields[i].getFirst(),nIth);
			}
		}
		if(fields == nFields) {
			return e;
		} else {
			return new Expr.RecordInitialiser(nFields);
		}
	}

	public Expr simplifyRecordAccess(Expr.RecordAccess e) throws ResolutionError {
		Expr source = e.getSource();
		Expr nSource = simplifyExpression(source);
		if(nSource instanceof Expr.RecordInitialiser) {
			Expr.RecordInitialiser ri = (Expr.RecordInitialiser) nSource;
			Pair<Identifier, Expr>[] fields = ri.getFields();
			for(int i=0;i!=fields.length;++i) {
				Pair<Identifier, Expr> field = fields[i];
				if(e.getField().equals(field.getFirst())) {
					return field.getSecond();
				}
			}
		} else if(nSource instanceof Expr.RecordUpdate) {
			Expr.RecordUpdate r = (Expr.RecordUpdate) nSource;
			if(e.getField().equals(r.getField())) {
				return r.getValue();
			} else {
				return new Expr.RecordAccess(r.getSource(), e.getField());
			}
		}
		//
		if(source == nSource) {
			return e;
		} else {
			return new Expr.RecordAccess(nSource, e.getField());
		}
	}

	public Expr simplifyRecordUpdate(Expr.RecordUpdate e) throws ResolutionError {
		Expr source = e.getSource();
		Expr value = e.getValue();
		Expr nSource = simplifyExpression(source);
		Expr nValue = simplifyExpression(value);
		//
		if(nSource instanceof Expr.RecordInitialiser) {
			Expr.RecordInitialiser ri = (Expr.RecordInitialiser) nSource;
			Pair<Identifier, Expr>[] oldFields = ri.getFields();
			Pair<Identifier, Expr>[] newFields = Arrays.copyOf(oldFields, oldFields.length);
			for(int i=0;i!=oldFields.length;++i) {
				Pair<Identifier, Expr> field = oldFields[i];
				if(e.getField().equals(field.getFirst())) {
					newFields[i] = new Pair<>(field.getFirst(),nValue);
				}
			}
			return new Expr.RecordInitialiser(newFields);
		}
		//
		if(source == nSource && value == nValue) {
			return e;
		} else {
			return new Expr.RecordUpdate(nSource, e.getField(), nValue);
		}
	}

	public Expr simplifyDereference(Expr.Dereference e) throws ResolutionError {
		Expr source = e.getOperand();
		Expr nSource = simplifyExpression(source);
		if (source == nSource) {
			return e;
		} else {
			return new Expr.Dereference(nSource);
		}
	}

	public Expr simplifyInvoke(Expr.Invoke ivk) throws ResolutionError {
		Tuple<Expr> args = ivk.getArguments();
		Expr[] nChildren = new Expr[args.size()];
		boolean changed = false;
		for (int i = 0; i != args.size(); ++i) {
			Expr child = args.get(i);
			Expr nChild = simplifyExpression(child);
			//
			changed |= (child != nChild);
			nChildren[i] = nChild;
		}
		if(!changed) {
			return ivk;
		} else {
			Tuple<Expr> nArgs = new Tuple<>(nChildren);
			return new Expr.Invoke(ivk.getSignatureType(),ivk.getName(),ivk.getSelector(),nArgs);
		}
	}

	public Expr simplifyArrayIndex(Expr.Operator e) throws ResolutionError {
		Expr source = e.get(0);
		Expr index = e.get(1);
		Expr nSource = simplifyExpression(source);
		Expr nIndex = simplifyExpression(index);
		//
		if (nSource instanceof Expr.Operator && nIndex instanceof Expr.Constant) {
			// We may have a constant index value into a constant array
			Expr.Operator arr = (Expr.Operator) nSource;
			if (arr.getOpcode() == EXPR_arrinit) {
				// We definitely have a constant index value into a constant
				// array
				BigInteger i = ((Value.Int) ((Expr.Constant) nIndex).getValue()).get();
				if (i.compareTo(BigInteger.ZERO) >= 0 && i.compareTo(BigInteger.valueOf(arr.size())) < 0) {
					// The constant index is within bounds
					return arr.get(i.intValue());
				}
			}
		}
		if(nSource.getOpcode() == EXPR_arrgen) {
			return (Expr) nSource.get(0);
		}
		// If we get here, then no simplification of the array access expression
		// was possible.
		if (source == nSource && index == nIndex) {
			return e;
		} else {
			return new Expr.ArrayAccess(nSource, nIndex);
		}
	}

	public Expr simplifyArrayUpdate(Expr.Operator e) throws ResolutionError {
		Expr source = e.get(0);
		Expr index = e.get(1);
		Expr value = e.get(2);
		Expr nSource = simplifyExpression(source);
		Expr nIndex = simplifyExpression(index);
		Expr nValue = simplifyExpression(value);
		//
		if(nIndex instanceof Expr.Constant && nSource.getOpcode() == EXPR_arrinit) {
			Expr.Operator src = (Expr.Operator) nSource;
			BigInteger b = ((Value.Int) ((Expr.Constant) nIndex).getValue()).get();
			if(b.compareTo(BigInteger.ZERO) >= 0 && b.compareTo(BigInteger.valueOf(nSource.size())) < 0) {
				int idx = b.intValue();
				Expr[] nChildren = Arrays.copyOf(src.getAll(),src.size());
				nChildren[idx] = nValue;
				return src.clone(nChildren);
			}
		}
		if (source == nSource && index == nIndex && value == nValue) {
			return e;
		} else {
			return new Expr.ArrayUpdate(nSource, nIndex, nValue);
		}
	}

	public Expr simplifyArrayLength(Expr.Operator e) throws ResolutionError {
		Expr r = simplifyNonArithmetic(e);
		if (r instanceof Expr.Operator) {
			Expr src = (Expr) r.get(0);
			if (src.getOpcode() == EXPR_arrinit) {
				return new Expr.Constant(new Value.Int(src.size()));
			} else if (src.getOpcode() == EXPR_arrgen) {
				return (Expr) src.get(1);
			} else if (src.getOpcode() == EXPR_arrupdt) {
				return simplifyArrayLength(new Expr.ArrayLength((Expr) src.get(0)));
			}
		}
		return r;
	}

	public Expr simplifyNonArithmetic(Expr.Operator e) throws ResolutionError {
		Expr[] children = e.getAll();
		Expr[] nChildren = simplifyExpressions(children);

		if (nChildren == children) {
			return e;
		} else {
			// FIXME: there are further simplifications that can be performed
			// here. For example, taking the field of a constant record;
			// likewise, taking a constant index into a constant array. Although
			// unlikely, they can arise through the use of e.g. configuration
			// constants, etc.
			return e.clone(nChildren);
		}
	}

	public Expr simplifyArithmetic(Expr.Operator e) throws ResolutionError {
		Expr[] children = e.getAll();
		Polynomial result = Arithmetic.asPolynomial(simplifyExpression(children[0]));
		switch (e.getOpcode()) {
		case EXPR_add: {
			for (int i = 1; i != children.length; ++i) {
				result = result.add(Arithmetic.asPolynomial(simplifyExpression(children[i])));
			}
			break;
		}
		case EXPR_sub: {
			for (int i = 1; i != children.length; ++i) {
				result = result.subtract(Arithmetic.asPolynomial(simplifyExpression(children[i])));
			}
			break;
		}
		case EXPR_mul: {
			for (int i = 1; i != children.length; ++i) {
				result = result.multiply(Arithmetic.asPolynomial(simplifyExpression(children[i])));
			}
			break;
		}
		case EXPR_neg: {
			result = result.negate();
			break;
		}
		default:
			throw new IllegalArgumentException("Unknown arithmetic opcode encountered");
		}
		return result.toExpression();
	}

	// ========================================================================
	// Equalities / Inequalities
	// ========================================================================

	/**
	 * Evaluate a given inequality whose bounds are known to be constant integer
	 * values. For example, <code>1 < 0</code> evaluates to <code>false</code>,
	 * etc.
	 *
	 * @param opcode
	 * @param lhs
	 * @param rhs
	 * @return
	 */
	public Formula.Truth evaluateInequality(int opcode, Value.Int lhs, Value.Int rhs) {
		boolean result;
		switch (opcode) {
		case EXPR_lt:
			result = lhs.compareTo(rhs) < 0;
			break;
		case EXPR_lteq:
			result = lhs.compareTo(rhs) <= 0;
			break;
		case EXPR_gt:
			result = lhs.compareTo(rhs) > 0;
			break;
		case EXPR_gteq:
			result = lhs.compareTo(rhs) >= 0;
			break;
		default:
			throw new IllegalArgumentException("Invalid inequality opcode: " + opcode);
		}
		return new Formula.Truth(result);
	}

	/**
	 * Evaluate a given equality whose bounds are known to be constant values of
	 * some sort. For example, <code>true == false</code> evaluates to
	 * <code>false</code>, etc.
	 *
	 * @param opcode
	 * @param lhs
	 * @param rhs
	 * @return
	 */
	public Formula.Truth evaluateEquality(int opcode, Value lhs, Value rhs) {
		boolean result;
		switch (opcode) {
		case EXPR_eq:
			result = lhs.equals(rhs);
			break;
		case EXPR_neq:
			result = !(lhs.equals(rhs));
			break;
		default:
			throw new IllegalArgumentException("Invalid equality opcode: " + opcode);
		}
		return new Formula.Truth(result);
	}

	/**
	 * Normalise bounds of an equation to be positive. For example, consider the
	 * inequality <code>x < y - z</code>. In this case, the right-hand side is
	 * not simplifyd because it contains a negative term. The simplifyd
	 * version of this inequality would be <code>x + z < y</code>.
	 *
	 * @param lhs
	 * @param rhs
	 * @return
	 */
	public Pair<Expr, Expr> normaliseBounds(Expr lhs, Expr rhs) {
		Polynomial left = Arithmetic.asPolynomial(lhs);
		Polynomial right = Arithmetic.asPolynomial(rhs);
		Polynomial bound = left.subtract(right).factorise();
		//
		Polynomial pos = filter(bound, true);
		Polynomial neg = filter(bound, false);
		return new Pair<>(pos.toExpression(), neg.toExpression());
	}

	public Polynomial filter(Polynomial p, boolean sign) {
		Polynomial result = Polynomial.ZERO;
		for (int i = 0; i != p.size(); ++i) {
			Polynomial.Term term = p.getTerm(i);
			BigInteger coefficient = term.getCoefficient();
			int c = coefficient.compareTo(BigInteger.ZERO);
			if (sign && c >= 0) {
				result = result.add(term);
			} else if (!sign && c < 0) {
				result = result.subtract(term);
			}
		}
		return result;
	}


	private Formula[] inlineNestedDisjuncts(Formula[] children) {
		Formula[] nChildren = children;
		for(int i=0;i!=nChildren.length;++i) {
			Formula child = nChildren[i];
			if(child instanceof Formula.Disjunct) {
				// We found a nested disjunct!
				Formula.Disjunct disjunct = (Formula.Disjunct) child;
				Formula[] nested = disjunct.getAll();
				// Inline the nested disjunct's operands
				nChildren = inlineNestedArray(nChildren,i,nested);
				// Can safely skip all elements in nested since disjunct already
				// in simplified form by construction.
				i += (nested.length - 1);
			}
		}
		return nChildren;
	}

	private Formula[] inlineNestedConjuncts(Formula[] children) {
		Formula[] nChildren = children;
		for (int i = 0; i != nChildren.length; ++i) {
			Formula child = nChildren[i];
			if (child instanceof Formula.Conjunct) {
				// We found a nested conjunct!
				Formula.Conjunct conjunct = (Formula.Conjunct) child;
				Formula[] nested = conjunct.getAll();
				// Inline the nested conjunct's operands
				nChildren = inlineNestedArray(nChildren, i, nested);
				// Can safely skip all elements in nested since conjunct already
				// in simplified form by construction.
				i += (nested.length - 1);
			}
		}
		return nChildren;
	}

	public <T> Formula[] inlineNestedArray(Formula[] parent, int index, Formula[] child) {
		Formula[] types = new Formula[parent.length + child.length - 1];
		System.arraycopy(parent, 0, types, 0, index);
		System.arraycopy(child, 0, types, index, child.length);
		System.arraycopy(parent, index + 1, types, index + child.length, parent.length - (index + 1));
		return types;
	}
} public abstract class AbstractClosureRule extends AbstractProofRule {
	public AbstractClosureRule(Simplification simp, TypeSystem types) {
		super(simp,types);
	}

	@Override
	public Proof.State apply(Proof.State current, Proof.State head) throws ResolutionError {
		Proof.Delta.Set additions = current.getDelta().getAdditions();
		if (additions.size() > 1) {
			throw new IllegalArgumentException("should be impossible to get here");
		} else if (additions.size() != 0) {
			Proof.Delta delta = head.getDelta(current);
			Formula truth = additions.get(0);
			if(!delta.isRemoval(truth)) {
				// Truth not yet subsumed by existing rule
				Proof.Delta.Set existingTruths = getExistingTruths(current);
				return apply(existingTruths, head, truth);
			}
		}
		// Default case: nothing to do
		return head;
	}

	@Override
	public final Proof.State apply(Proof.State head, Formula truth) {
		throw new UnsupportedOperationException();
	}

	public abstract Proof.State apply(Proof.Delta.Set existingTruths, Proof.State head, Formula truth)
			throws ResolutionError;

	protected Proof.Delta.Set getExistingTruths(Proof.State current) {
		Proof.Delta history = current.getDelta(null);
		Proof.Delta.Set existingTruths = history.getAdditions().remove(history.getRemovals());
		// We remove any additions from this state here to ensure that the new
		// truth being processed is not included in the list of existing truths.
		// However, we do want to keep any removals since these may corresponds
		// to existing truths which are subsumed by the new truth and we don't
		// to apply the new truth against a subsumed version of itself.
		return existingTruths.remove(current.getDelta().getAdditions());
	}
} public class Arithmetic {

	public static Polynomial asPolynomial(Expr e) {
		switch (e.getOpcode()) {
		case WyalFile.EXPR_const: {
			Expr.Constant c = (Expr.Constant) e;
			Value.Int i = (Value.Int) c.getValue();
			Polynomial.Term term = new Polynomial.Term(i.get());
			return new Polynomial(term);
		}
		case WyalFile.EXPR_add: {
			Polynomial result = asPolynomial((Expr) e.get(0));
			for(int i=1;i!=e.size();++i) {
				result = result.add(asPolynomial((Expr) e.get(i)));
			}
			return result;
		}
		case WyalFile.EXPR_sub: {
			Polynomial result = asPolynomial((Expr) e.get(0));
			for(int i=1;i!=e.size();++i) {
				result = result.subtract(asPolynomial((Expr) e.get(i)));
			}
			return result;
		}
		case WyalFile.EXPR_mul: {
			Polynomial result = asPolynomial((Expr) e.get(0));
			for(int i=1;i!=e.size();++i) {
				result = result.multiply(asPolynomial((Expr) e.get(i)));
			}
			return result;
		}
		case WyalFile.EXPR_div: {
			throw new IllegalArgumentException("need to support division");
		}
		default: {
			Polynomial.Term term = new Polynomial.Term(BigInteger.ONE, e);
			return new Polynomial(term);
		}
		}
	}
//
//	public class Rational {
//		public Polynomial getNumerator() {
//
//		}
//		public Polynomial getDenominator() {
//
//		}
//	}

	public static class Polynomial implements Comparable<Polynomial> {

		public static final Polynomial ZERO = new Polynomial(new Term(BigInteger.ZERO));

		private final Term[] terms;

		Polynomial(Term...terms) {
			this.terms = terms;
		}

		public int size() {
			return terms.length;
		}
		public boolean isConstant() {
			return (terms.length == 1 && terms[0].isConstant());
		}
		public BigInteger toConstant() {
			return terms[0].getCoefficient();
		}
		public Term getTerm(int i) {
			return terms[i];
		}
		public Polynomial negate() {
			Term[] newTerms = new Term[terms.length];
			for(int i=0;i!=terms.length;++i) {
				newTerms[i] = terms[i].negate();
			}
			return new Polynomial(newTerms);
		}

		/**
		 * <p>
		 * Add two polynomials together, producing a polynomial in normal form.
		 * To do this, we must add the coefficients for terms which have the
		 * same set of atoms, whilst other terms are incorporated as is. For
		 * example, consider adding <code>2+2x</code> with <code>1+3x+4y</code>.
		 * In this case, we have some terms in common, so the result becomes
		 * <code>(2+1) + (2x+3x) + 4y</code> which is simplified to
		 * <code>3 + 5x + 4y</code>.
		 * </p>
		 *
		 * @param poly
		 * @return
		 */
		public Polynomial add(Polynomial p) {
			Polynomial.Term[] combined = new Polynomial.Term[terms.length+p.terms.length];
			System.arraycopy(terms, 0, combined, 0, terms.length);
			System.arraycopy(p.terms, 0, combined, terms.length, p.terms.length);
			return construct(combined);
		}

		public Polynomial add(Polynomial.Term p) {
			Polynomial.Term[] combined = new Polynomial.Term[terms.length+1];
			System.arraycopy(terms, 0, combined, 0, terms.length);
			combined[terms.length] = p;
			return construct(combined);
		}

		public Polynomial subtract(Polynomial p) {
			return add(p.negate());
		}
		public Polynomial subtract(Polynomial.Term p) {
			return add(p.negate());
		}

		/**
		 * Multiply two polynomials together. This is done by reusing the add()
		 * function as much as possible, though this may not be the most
		 * efficient. In essence, to multiply one polynomial (e.g.
		 * <code>2+2x</code>) by another (e.g.<code>1+3x+4y</code>) it breaks it
		 * down into a series of multiplications over terms and additions. That
		 * is, we multiply each term from the first polynomial by the second
		 * (e.g. <code>2*(1+3x+4y)</code> and <code>2x*(1+3x+4y)</code>). Then,
		 * we add the results together (e.g.
		 * <code>(2+6x+8y) + (2x+6x2+8xy)</code>).
		 *
		 * @param p
		 * @return
		 */
		public Polynomial multiply(Polynomial p) {
			int lhs_size = terms.length;
			int rhs_size = p.terms.length;
			Polynomial.Term[] combined = new Polynomial.Term[lhs_size * rhs_size];

			for (int i = 0; i != lhs_size; ++i) {
				Polynomial.Term lhsTerm = terms[i];
				int j_base = i * rhs_size;
				for (int j = 0; j != rhs_size; ++j) {
					Polynomial.Term rhsTerm = p.terms[j];
					combined[j_base + j] = Arithmetic.multiply(lhsTerm, rhsTerm);
				}
			}

			return construct(combined);
		}

		public Polynomial multiply(Polynomial.Term rhs) {
			int lhs_size = terms.length;
			Polynomial.Term[] combined = new Polynomial.Term[lhs_size];

			for (int i = 0; i != lhs_size; ++i) {
				Polynomial.Term lhsTerm = terms[i];
				combined[i] = Arithmetic.multiply(lhsTerm, rhs);
			}

			return construct(combined);
		}

		public Polynomial multiply(BigInteger rhs) {
			int lhs_size = terms.length;
			Polynomial.Term[] combined = new Polynomial.Term[lhs_size];

			for (int i = 0; i != lhs_size; ++i) {
				combined[i] = terms[i].multiply(rhs);
			}

			return construct(combined);
		}


		/**
		 * Factorise a given polynomial. For example, <code>2x+2</code> is
		 * factorised to be <code>x+1</code>. Observe that this does not preseve the
		 * result of the polynomial. However, it is safe to do when simplifying
		 * equations. For example, <code>2x == 2y</code> can be safely factorised to
		 * <code>x == y</code>.
		 *
		 * @param p
		 * @return
		 */
		public Polynomial factorise() {
			BigInteger factor = terms[0].getCoefficient();
			// In case of just one coefficient which is negative, we need to compute
			// abs() here.
			factor = factor.abs();
			//
			for (int i = 1; i != terms.length; ++i) {
				BigInteger c = terms[i].getCoefficient();
				factor = factor.gcd(c);
			}
			if (factor.equals(BigInteger.ZERO) || factor.equals(BigInteger.ONE)) {
				// No useful factor discovered
				return this;
			} else {
				// Yes, we found a useful factor. Therefore, divide all coefficients
				// by this.
				Polynomial r = Polynomial.ZERO;
				for (int i = 0; i != terms.length; ++i) {
					Polynomial.Term t = terms[i];
					BigInteger c = t.getCoefficient();
					c = c.divide(factor);
					r = r.add(new Polynomial.Term(c, t.getAtoms()));
				}
				return r;
			}
		}

		@Override
		public int compareTo(Polynomial p) {
			int lengthDifference = terms.length - p.terms.length;
			if(lengthDifference != 0) {
				return lengthDifference;
			} else {
				for(int i=0;i!=terms.length;++i) {
					Polynomial.Term t1 = terms[i];
					Polynomial.Term t2 = p.terms[i];
					int c = t1.compareTo(t2);
					if(c != 0) {
						return c;
					}
				}
				return 0;
			}
		}

		@Override
		public boolean equals(Object o) {
			if(o instanceof Polynomial) {
				Polynomial p = (Polynomial) o;
				return Arrays.equals(terms, p.terms);
			}
			return false;
		}

		@Override
		public int hashCode() {
			return Arrays.hashCode(terms);
		}

		public Expr toExpression() {
			Expr[] muls = new Expr[terms.length];
			for(int i=0;i!=muls.length;++i) {
				muls[i] = terms[i].toExpression();
			}
			if(muls.length == 1) {
				return muls[0];
			} else {
				return new Expr.Addition(muls);
			}
		}

		@Override
		public String toString() {
			String r = "(";
			for(int i=0;i!=terms.length;++i) {
				if(i != 0) {
					r += " + ";
				}
				r += terms[i].toString();
			}
			return r + ")";
		}

		public static class Term implements Comparable<Term> {
			private final BigInteger coefficient;
			private final Expr[] atoms;

			Term(BigInteger coefficient, Expr...atoms) {
				if(coefficient.equals(BigInteger.ZERO) && atoms.length > 0) {
					throw new IllegalArgumentException("invalid zero term");
				}
				this.coefficient = coefficient;
				this.atoms = atoms;
			}
			public BigInteger getCoefficient() {
				return coefficient;
			}
			public boolean isConstant() {
				return atoms.length == 0;
			}
			public Expr[] getAtoms() {
				return atoms;
			}

			@Override
			public int compareTo(Term t) {
				int lengthDifference = atoms.length - t.atoms.length;
				if (lengthDifference != 0) {
					return lengthDifference;
				} else {
					for (int i = 0; i != atoms.length; ++i) {
						Expr t1 = atoms[i];
						Expr t2 = t.atoms[i];
						int c = t1.compareTo(t2);
						if (c != 0) {
							return c;
						}
					}
					return coefficient.compareTo(t.coefficient);
				}
			}

			@Override
			public boolean equals(Object o) {
				if(o instanceof Term) {
					Term t = (Term) o;
					return coefficient.equals(t.coefficient) && Arrays.equals(atoms, t.atoms);
				}
				return false;
			}

			@Override
			public int hashCode() {
				return coefficient.hashCode() ^ Arrays.hashCode(atoms);
			}

			public Term negate() {
				return new Term(coefficient.negate(),atoms);
			}

			public Term multiply(BigInteger rhs) {
				if (coefficient.equals(BigInteger.ZERO)) {
					return this;
				} else if (rhs.equals(BigInteger.ZERO)) {
					return new Polynomial.Term(rhs);
				} else {
					BigInteger coefficient = this.coefficient.multiply(rhs);
					return new Polynomial.Term(coefficient, atoms);
				}
			}

			public Expr toExpression() {
				if (atoms.length == 0) {
					return new Expr.Constant(new Value.Int(coefficient));
				} else if (coefficient.equals(BigInteger.ONE)) {
					if(atoms.length == 1) {
						return atoms[0];
					} else {
						return new Expr.Multiplication(atoms);
					}
				} else {
					Expr[] es = new Expr[atoms.length + 1];
					es[0] = new Expr.Constant(new Value.Int(coefficient));
					System.arraycopy(atoms, 0, es, 1, atoms.length);
					return new Expr.Multiplication(es);
				}
			}

			@Override
			public String toString() {
				String r = "";
				if(!coefficient.equals(BigInteger.ONE) || atoms.length == 0) {
					r += coefficient;
					if(atoms.length > 0) {
						r += "*";
					}
				}
				for(int i=0;i!=atoms.length;++i) {
					if(i != 0) {
						r += "*";
					}
					r += atoms[i];
				}
				return r;
			}
		}
	}

	private static Polynomial.Term multiply(Polynomial.Term lhs, Polynomial.Term rhs) {
		if (lhs.coefficient.equals(BigInteger.ZERO)) {
			return lhs;
		} else if (rhs.coefficient.equals(BigInteger.ZERO)) {
			return rhs;
		} else {
			BigInteger coefficient = lhs.getCoefficient().multiply(rhs.getCoefficient());
			Expr[] lhsAtoms = lhs.getAtoms();
			Expr[] rhsAtoms = rhs.getAtoms();
			Expr[] atoms = new Expr[lhsAtoms.length + rhsAtoms.length];
			System.arraycopy(lhsAtoms, 0, atoms, 0, lhsAtoms.length);
			System.arraycopy(rhsAtoms, 0, atoms, lhsAtoms.length, rhsAtoms.length);
			Arrays.sort(atoms);
			return new Polynomial.Term(coefficient, atoms);
		}
	}

	/**
	 * Given a list of unsorted and potentially overlapping terms, apply the
	 * necessary simplifications to produce a polynomial in normal form. For
	 * example, given <code>[2, 7x, 4y, -x]</code> we would end up with
	 * <code>[1, 3x, 2y]</code>.
	 *
	 * @param terms
	 * @return
	 */
	private static Polynomial construct(Polynomial.Term... terms) {
		terms = merge(terms);
		// In the case that all terms were eliminated as null, simply ensure
		// that zero is present. This can happen is all terms cancelled out.
		if (terms.length == 0) {
			// FIXME: can zero be represented using an empty term array?
			// This does make the manipulation of polynomials more awkward than
			// necessary.
			terms = new Polynomial.Term[] { new Polynomial.Term(BigInteger.ZERO) };
		}
		// Sort remaining terms
		Arrays.sort(terms);
		// Done
		return new Polynomial(terms);
	}

	private static boolean isZero(Polynomial.Term term) {
		BigInteger coefficient = term.getCoefficient();
		return coefficient.equals(BigInteger.ZERO);
	}

	/**
	 * Combine all terms which have the same set of atoms by adding the
	 * coefficients together. For example, [x,2x] is combined into [null,3x].
	 *
	 * @param terms
	 */
	private static Polynomial.Term[] merge(Polynomial.Term[] terms) {
		//
		for (int i = 0; i != terms.length; ++i) {
			Polynomial.Term ith = terms[i];
			if (ith != null) {
				if (isZero(ith)) {
					// Eliminate any zeros which may have arisen during the
					// calculation.
					terms[i] = null;
				} else {
					Expr[] ithAtoms = ith.getAtoms();
					for (int j = i + 1; j != terms.length; ++j) {
						Polynomial.Term jth = terms[j];
						if (jth != null && Arrays.equals(ithAtoms,jth.getAtoms())) {
							// We have two overlapping terms, namely i and j.
							// Add them together and assign the result to the
							// jth position.
							terms[j] = merge(ith,jth);
							terms[i] = null;
							break;
						}
					}
				}
			}
		}
		// Strip out null entries
		return ArrayUtils.removeAll(terms, null);
	}

	/**
	 * Merge two polynomial terms which are assumed to have the same set of
	 * atoms.
	 *
	 * @param lhs
	 * @param rhs
	 * @return
	 */
	private static Polynomial.Term merge(Polynomial.Term lhs, Polynomial.Term rhs) {
		BigInteger lhsCoeff = lhs.getCoefficient();
		BigInteger rhsCoeff = rhs.getCoefficient();
		BigInteger r = lhsCoeff.add(rhsCoeff);
		if (r.equals(BigInteger.ZERO)) {
			return null;
		} else {
			return new Polynomial.Term(r, lhs.getAtoms());
		}
	}
} public class Formulae {

	// ========================================================================
	// Conversions
	// ========================================================================

	/**
	 * <p>
	 * Take a tree of statements and expressions, and return a formula. This is
	 * the first part of the process in discharging a given assertion. The
	 * purpose of a formula is just to provide a more "structured" form of the
	 * logical expression. The interface Formula also provides useful functions
	 * form manipulating formulae.
	 * </p>
	 * <p>
	 * Observe that after this conversion the resulting formula is not
	 * necessarily in simplified form. For example, conjuncts may contain nested
	 * conjuncts or equations may be unbalanced.
	 * </p>
	 *
	 * @param stmt
	 *            The statement being converted into a formula
	 * @param types
	 *            The type system is required for the translation, as some
	 *            aspects depend upon the types of expressions involved.
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public static Formula toFormula(WyalFile.Stmt stmt, TypeSystem types) throws ResolutionError {
		switch (stmt.getOpcode()) {
		case WyalFile.STMT_block: {
			WyalFile.Stmt.Block b = (WyalFile.Stmt.Block) stmt;
			Formula[] operands = toFormulae(b.getAll(), types);
			return new Formula.Conjunct(operands);
		}
		case WyalFile.STMT_caseof: {
			WyalFile.Stmt.CaseOf b = (WyalFile.Stmt.CaseOf) stmt;
			Formula[] operands = toFormulae(b.getAll(), types);
			return new Formula.Disjunct(operands);
		}
		case WyalFile.STMT_ifthen: {
			WyalFile.Stmt.IfThen it = (WyalFile.Stmt.IfThen) stmt;
			Formula lhs = toFormula(it.getIfBody(), types);
			Formula rhs = toFormula(it.getThenBody(), types);
			return new Formula.Disjunct(invert(lhs), rhs);
		}
		case WyalFile.STMT_forall: {
			Stmt.Quantifier q = (WyalFile.Stmt.Quantifier) stmt;
			// Convert body of quantifier
			Formula body = toFormula(q.getBody(), types);
			// Done
			return new Formula.Quantifier(true, q.getParameters(), body);
		}
		case WyalFile.STMT_exists: {
			Stmt.Quantifier q = (WyalFile.Stmt.Quantifier) stmt;
			// Convert body of quantifier
			Formula body = toFormula(q.getBody(), types);
			// Done
			return new Formula.Quantifier(false, q.getParameters(), body);
		}
		case WyalFile.EXPR_forall: {
			Expr.Quantifier q = (WyalFile.Expr.Quantifier) stmt;
			// Convert body of quantifier
			Formula body = toFormula(q.getBody(), types);
			// Done
			return new Formula.Quantifier(true, q.getParameters(), body);
		}
		case WyalFile.EXPR_exists: {
			Expr.Quantifier q = (WyalFile.Expr.Quantifier) stmt;
			// Convert body of quantifier
			Formula body = toFormula(q.getBody(), types);
			// Done
			return new Formula.Quantifier(false, q.getParameters(), body);
		}
		case WyalFile.EXPR_and: {
			Expr.Operator b = (Expr.Operator) stmt;
			Formula[] operands = toFormulae(b.getAll(), types);
			return new Formula.Conjunct(operands);
		}
		case WyalFile.EXPR_or: {
			Expr.Operator b = (Expr.Operator) stmt;
			Formula[] operands = toFormulae(b.getAll(), types);
			return new Formula.Disjunct(operands);
		}
		case WyalFile.EXPR_implies: {
			WyalFile.Expr.Operator it = (Expr.Operator) stmt;
			Formula lhs = toFormula(it.get(0), types);
			Formula rhs = toFormula(it.get(1), types);
			return new Formula.Disjunct(invert(lhs), rhs);
		}
		case WyalFile.EXPR_iff: {
			WyalFile.Expr.Operator it = (Expr.Operator) stmt;
			Formula lhs = toFormula(it.get(0), types);
			Formula rhs = toFormula(it.get(1), types);
			Formula a1 = new Formula.Conjunct(lhs,rhs);
			Formula a2 = new Formula.Conjunct(invert(lhs),invert(rhs));
			return new Formula.Disjunct(a1, a2);
		}
		case WyalFile.EXPR_eq: {
			Expr.Operator operator = (Expr.Operator) stmt;
			Expr lhs = operator.get(0);
			Expr rhs = operator.get(1);
			Type lhs_t = types.inferType(new StdTypeEnvironment(),lhs);
			Type rhs_t = types.inferType(new StdTypeEnvironment(),rhs);
			if (types.isRawSubtype(new Type.Int(), lhs_t) && types.isRawSubtype(new Type.Int(), rhs_t)) {
				// Force arithmetic equality
				return new Formula.ArithmeticEquality(true, lhs, rhs);
			} else {
				return new Formula.Equality(true, lhs, rhs);
			}
		}
		case WyalFile.EXPR_neq: {
			Expr.Operator operator = (Expr.Operator) stmt;
			Expr lhs = operator.get(0);
			Expr rhs = operator.get(1);
			Type lhs_t = types.inferType(new StdTypeEnvironment(),lhs);
			Type rhs_t = types.inferType(new StdTypeEnvironment(),rhs);
			if (types.isRawSubtype(new Type.Int(), lhs_t) && types.isRawSubtype(new Type.Int(), rhs_t)) {
				// Force arithmetic equality
				return new Formula.ArithmeticEquality(false, lhs, rhs);
			} else {
				return new Formula.Equality(false, lhs, rhs);
			}
		}
		case WyalFile.EXPR_lt: {
			Expr.Operator operator = (Expr.Operator) stmt;
			Expr lhs = operator.get(0);
			Expr rhs = operator.get(1);
			return lessThan(lhs,rhs);
		}
		case WyalFile.EXPR_lteq: {
			Expr.Operator operator = (Expr.Operator) stmt;
			Expr lhs = operator.get(0);
			Expr rhs = operator.get(1);
			return greaterOrEqual(rhs,lhs);
		}
		case WyalFile.EXPR_gt: {
			Expr.Operator operator = (Expr.Operator) stmt;
			Expr lhs = operator.get(0);
			Expr rhs = operator.get(1);
			// lhs > rhs ==> lhs+1 >= rhs
			return lessThan(rhs,lhs);
		}
		case WyalFile.EXPR_gteq: {
			Expr.Operator operator = (Expr.Operator) stmt;
			Expr lhs = operator.get(0);
			Expr rhs = operator.get(1);
			return greaterOrEqual(lhs,rhs);
		}
		case WyalFile.EXPR_not: {
			Expr.Operator operator = (Expr.Operator) stmt;
			Formula f = toFormula(operator.get(0), types);
			return invert(f);
		}
		case WyalFile.EXPR_const: {
			Expr.Constant c = (Expr.Constant) stmt;
			Value.Bool b = (Value.Bool) c.getValue();
			return new Formula.Truth(b);
		}
		case WyalFile.EXPR_invoke: {
			Expr.Invoke ivk = (Expr.Invoke) stmt;
			if(ivk.getSignatureType() instanceof Type.Function) {
				Expr TRUE = new Formula.Truth(new Value.Bool(true));
				return new Formula.Equality(true, ivk, TRUE);
			} else {
				return new Formula.Invoke(true, ivk.getSignatureType(), ivk.getName(), ivk.getSelector(), ivk.getArguments());
			}
		}
		case WyalFile.EXPR_is: {
			Expr.Is operator = (Expr.Is) stmt;
			Expr lhs = operator.getTestExpr();
			Type lhs_t = types.inferType(new StdTypeEnvironment(),lhs);
			if(lhs_t != null && types.isRawSubtype(new Type.Bool(), lhs_t)) {
				lhs = toFormula(lhs,types);
			}
			return new Formula.Is(lhs,operator.getTestType());
		}
		default:
			if (stmt instanceof WyalFile.Expr) {
				Expr expr = (WyalFile.Expr) stmt;
				Expr TRUE = new Formula.Truth(new Value.Bool(true));
				return new Formula.Equality(true, expr, TRUE);
			} else {
				throw new IllegalArgumentException("unknown statement encountered: " + stmt.getOpcode());
			}
		}
	}

	/**
	 * Convert an array of statements into an array of (equivalent) formulae.
	 *
	 * @param stmts
	 * @return
	 * @throws AmbiguousNameError
	 * @throws NameNotFoundError
	 */
	public static Formula[] toFormulae(Stmt[] stmts, TypeSystem types) throws ResolutionError {
		Formula[] exprs = new Formula[stmts.length];
		for (int i = 0; i != exprs.length; ++i) {
			exprs[i] = toFormula(stmts[i], types);
		}
		return exprs;
	}

	public static Formula.Inequality lessThan(Expr lhs, Expr rhs) {
		// lhs < rhs ===> rhs >= (lhs+1)
		Expr one = new Expr.Constant(new Value.Int(1));
		Expr lhsP1 = new Expr.Addition(lhs, one);
		return new Formula.Inequality(rhs, lhsP1);
	}

	public static Formula.Inequality greaterOrEqual(Expr lhs, Expr rhs) {
		return new Formula.Inequality(lhs, rhs);
	}

	public static Formula implies(Formula lhs, Formula rhs) {
		return new Formula.Disjunct(invert(lhs),rhs);
	}

	public static Formula and(Formula lhs, Formula rhs) {
		return new Formula.Conjunct(lhs,rhs);
	}

	public static Formula or(Formula lhs, Formula rhs) {
		return new Formula.Disjunct(lhs,rhs);
	}

	// ========================================================================
	// Inversion
	// ========================================================================

	/**
	 * Logically invert a given formula. This pushes through all inversions as
	 * far as possible. For example, <code>!(x == 0 && y < x)</code> becomes
	 * <code>x != 0 || y >= x</code>. This method is useful (amongst other
	 * things) for beginning a proof-by-contradiction. In such a proof, we first
	 * invert the formula in question and then establish that this reduces to a
	 * contradiction.
	 *
	 * @param f
	 * @return
	 */
	public static Formula invert(Formula f) {
		switch (f.getOpcode()) {
		case WyalFile.EXPR_const: {
			Formula.Truth truth = (Formula.Truth) f;
			return new Formula.Truth(!truth.holds());
		}
		case WyalFile.EXPR_and: {
			Formula.Conjunct c = (Formula.Conjunct) f;
			return new Disjunct(invert(c.getAll()));
		}
		case WyalFile.EXPR_or: {
			Formula.Disjunct c = (Formula.Disjunct) f;
			return new Conjunct(invert(c.getAll()));
		}
		case WyalFile.EXPR_exists:
		case WyalFile.EXPR_forall: {
			Formula.Quantifier q = (Formula.Quantifier) f;
			// FIXME: it's perhaps a little strange that we invert the body
			// here?
			return new Formula.Quantifier(!q.getSign(), q.getParameters(), invert(q.getBody()));
		}
		case WyalFile.EXPR_eq:
		case WyalFile.EXPR_neq: {
			if (f instanceof ArithmeticEquality) {
				ArithmeticEquality e = (ArithmeticEquality) f;
				return new ArithmeticEquality(!e.getSign(), e.get(0), e.get(1));
			} else {
				Equality e = (Equality) f;
				return new Equality(!e.getSign(), e.get(0), e.get(1));
			}
		}
		case WyalFile.EXPR_gteq: {
			// !(lhs >= rhs) => lhs < rhs
			Inequality e = (Inequality) f;
			Expr lhs = e.get(0);
			Expr rhs = e.get(1);
			return lessThan(lhs,rhs);
		}
		case WyalFile.EXPR_invoke: {
			Invoke e = (Invoke) f;
			return new Formula.Invoke(!e.getSign(),e.getSignatureType(),e.getName(),e.getSelector(),e.getArguments());
		}
		case WyalFile.EXPR_is: {
			Formula.Is c = (Formula.Is) f;
			// FIXME: could simplify the type here I think
			return new Is(c.getTestExpr(), new Type.Negation(c.getTestType()));
		}
		default:
			throw new IllegalArgumentException("invalid formula opcode: " + f.getOpcode());
		}
	}

	private static Formula[] invert(Formula[] children) {
		Formula[] nChildren = new Formula[children.length];
		for (int i = 0; i != children.length; ++i) {
			nChildren[i] = invert(children[i]);
		}
		return nChildren;
	}
	// ========================================================================
	// Simplifications
	// ========================================================================

} public class TypeSystem {
	/**
	 * The "null" environment provides a simple environment which simply falls
	 * back to using the declared type for a given variable.
	 */
	public  final static TypeInferer.Environment NULL_ENVIRONMENT = new StdTypeEnvironment();
	//
	private final NameResolver resolver;
	private final SubtypeOperator coerciveSubtypeOperator;
	private final TypeExtractor<Type.Record,Object> readableRecordExtractor;
	private final TypeExtractor<Type.Array,Object> readableArrayExtractor;
	private final TypeExtractor<Type.Reference,Object> readableReferenceExtractor;
	private final TypeInvariantExtractor typeInvariantExtractor;
	private final TypeInferer typeInfererence;
	private final TypeRewriter typeSimplifier;

	public TypeSystem(Build.Project project) {
		this.resolver = new WyalFileResolver(project);
		this.coerciveSubtypeOperator = new CoerciveSubtypeOperator(resolver);
		this.readableRecordExtractor = new ReadableRecordExtractor(resolver,this);
		this.readableArrayExtractor = new ReadableArrayExtractor(resolver,this);
		this.readableReferenceExtractor = new ReadableReferenceExtractor(resolver,this);
		this.typeInvariantExtractor = new TypeInvariantExtractor(resolver);
		this.typeInfererence = new StdTypeInfererence(this);
		this.typeSimplifier = new StdTypeRewriter();
	}

	/**
	 * <p>
	 * Determine whether one type is a <i>raw subtype</i> of another.
	 * Specifically, whether the raw type of <code>rhs</code> is a subtype of
	 * <code>lhs</code>'s raw type (i.e.
	 * "<code>&lfloor;lhs&rfloor; :> &lfloor;rhs&rfloor;</code>"). The raw type
	 * is that which ignores any type invariants involved. Thus, one must be
	 * careful when interpreting the meaning of this operation. Specifically,
	 * "<code>&lfloor;lhs&rfloor; :> &lfloor;rhs&rfloor;</code>" <b>does not
	 * imply</b> that "<code>lhs :> rhs</code>" holds. However, if
	 * "<code>&lfloor;lhs&rfloor; :> &lfloor;rhs&rfloor;</code>" does not hold,
	 * then it <b>does follow</b> that "<code>lhs :> rhs</code>" also does not
	 * hold.
	 * </p>
	 *
	 * <p>
	 * Depending on the exact language of types involved, this can be a
	 * surprisingly complex operation. For example, in the presence of
	 * <i>union</i>, <i>intersection</i> and <i>negation</i> types, the subtype
	 * algorithm is surprisingly intricate.
	 * </p>
	 *
	 * @param lhs
	 *            The candidate "supertype". That is, lhs's raw type may be a
	 *            supertype of <code>rhs</code>'s raw type.
	 * @param rhs
	 *            The candidate "subtype". That is, rhs's raw type may be a
	 *            subtype of <code>lhs</code>'s raw type.
	 * @return
	 * @throws ResolutionError
	 *             Occurs when a nominal type is encountered whose name cannot
	 *             be resolved properly. For example, it resolves to more than
	 *             one possible matching declaration, or it cannot be resolved
	 *             to a corresponding type declaration.
	 */
	public boolean isRawSubtype(Type lhs, Type rhs) throws ResolutionError {
		return coerciveSubtypeOperator.isSubtype(lhs,rhs) != SubtypeOperator.Result.False;
	}

	/**
	 * For a given type, extract its effective record type. For example, the
	 * type <code>({int x, int y}|{int x, int z})</code> has effective record
	 * type <code>{int x, ...}</code>. The following illustrates some more
	 * cases:
	 *
	 * <pre>
	 * {int x, int y} | null    ==> null
	 * {int x, int y} | {int x} ==> null
	 * {int x, int y} | {int x, bool y} ==> {int x, int|bool y}
	 * {int x, int y} & null    ==> null
	 * {int x, int y} & {int x} ==> null
	 * {int x, int y} & {int x, int|bool y} ==> {int x, int y}
	 * </pre>
	 *
	 * @param type
	 * @return
	 * @throws ResolutionError
	 */
	public Type.Record extractReadableRecord(Type type) throws ResolutionError {
		return readableRecordExtractor.extract(type,null);
	}

	/**
	 * Extract the readable array type from a given type. For example, the type
	 * <code>(int[])|(bool[])</code> has a readable array type of
	 * <code>(int|bool)[]</code>.
	 *
	 * @param type
	 * @return
	 * @throws ResolutionError
	 */
	public Type.Array extractReadableArray(Type type) throws ResolutionError {
		return readableArrayExtractor.extract(type,null);
	}

	/**
	 * Extract the readable reference type from a given type. This is relatively
	 * straightforward. For example, <code>&int</code> is extracted as
	 * <code>&int</code>. However, <code>(&int)|(&bool)</code> is not extracted
	 * as as <code>&(int|bool)</code>.
	 *
	 * @param type
	 * @return
	 * @throws ResolutionError
	 */
	public Type.Reference extractReadableReference(Type type) throws ResolutionError {
		return readableReferenceExtractor.extract(type,null);
	}

	/**
	 * Extracting the invariant (if any) from a given type. For example,
	 * consider the following type declaration:
	 *
	 * <pre>
	 * type nat is (int x) where x >= 0
	 * </pre>
	 *
	 * Then, extracting the invariant from type <code>nat</code> gives
	 * <code>x >= 0</code>. Likewise, extracting the invariant from the type
	 * <code>bool|int</code> gives the invariant
	 * <code>(x is int) ==> (x >= 0)</code>. Finally, extracting the invariant
	 * from the type <code>nat[]</code> gives the invariant
	 * <code>forall(int i).(0 <= i
	 * && i < |xs| ==> xs[i] >= 0)</code>.
	 *
	 *
	 */
	public Formula extractInvariant(Type type, Expr root) throws ResolutionError {
		return typeInvariantExtractor.extract(type,root);
	}

	// ========================================================================
	// Inference
	// ========================================================================

	/**
	 * Get the type inferred for a given expression in a given environment.
	 *
	 * @param environment
	 * @param expression
	 * @return
	 * @throws ResolutionError
	 *             Occurs when a particular named type cannot be resolved.
	 */
	public Type inferType(TypeInferer.Environment environment, Expr expression) throws ResolutionError {
		return typeInfererence.getInferredType(environment, expression);
	}

	// ========================================================================
	// Resolution
	// ========================================================================

	public <T extends Declaration.Named> T resolveExactly(Name name, Class<T> kind)
			throws ResolutionError {
		return resolver.resolveExactly(name,kind);
	}

	public <T extends Declaration.Named> List<T> resolveAll(Name name, Class<T> kind)
			throws ResolutionError {
		return resolver.resolveAll(name,kind);
	}

	// ========================================================================
	// Simplification
	// ========================================================================

	public Type simplify(Type type) {
		return typeSimplifier.rewrite(type);
	}
} public static class Polynomial implements Comparable<Polynomial> {

	public static final Polynomial ZERO = new Polynomial(new Term(BigInteger.ZERO));

	private final Term[] terms;

	Polynomial(Term...terms) {
		this.terms = terms;
	}

	public int size() {
		return terms.length;
	}
	public boolean isConstant() {
		return (terms.length == 1 && terms[0].isConstant());
	}
	public BigInteger toConstant() {
		return terms[0].getCoefficient();
	}
	public Term getTerm(int i) {
		return terms[i];
	}
	public Polynomial negate() {
		Term[] newTerms = new Term[terms.length];
		for(int i=0;i!=terms.length;++i) {
			newTerms[i] = terms[i].negate();
		}
		return new Polynomial(newTerms);
	}

	/**
	 * <p>
	 * Add two polynomials together, producing a polynomial in normal form.
	 * To do this, we must add the coefficients for terms which have the
	 * same set of atoms, whilst other terms are incorporated as is. For
	 * example, consider adding <code>2+2x</code> with <code>1+3x+4y</code>.
	 * In this case, we have some terms in common, so the result becomes
	 * <code>(2+1) + (2x+3x) + 4y</code> which is simplified to
	 * <code>3 + 5x + 4y</code>.
	 * </p>
	 *
	 * @param poly
	 * @return
	 */
	public Polynomial add(Polynomial p) {
		Polynomial.Term[] combined = new Polynomial.Term[terms.length+p.terms.length];
		System.arraycopy(terms, 0, combined, 0, terms.length);
		System.arraycopy(p.terms, 0, combined, terms.length, p.terms.length);
		return construct(combined);
	}

	public Polynomial add(Polynomial.Term p) {
		Polynomial.Term[] combined = new Polynomial.Term[terms.length+1];
		System.arraycopy(terms, 0, combined, 0, terms.length);
		combined[terms.length] = p;
		return construct(combined);
	}

	public Polynomial subtract(Polynomial p) {
		return add(p.negate());
	}
	public Polynomial subtract(Polynomial.Term p) {
		return add(p.negate());
	}

	/**
	 * Multiply two polynomials together. This is done by reusing the add()
	 * function as much as possible, though this may not be the most
	 * efficient. In essence, to multiply one polynomial (e.g.
	 * <code>2+2x</code>) by another (e.g.<code>1+3x+4y</code>) it breaks it
	 * down into a series of multiplications over terms and additions. That
	 * is, we multiply each term from the first polynomial by the second
	 * (e.g. <code>2*(1+3x+4y)</code> and <code>2x*(1+3x+4y)</code>). Then,
	 * we add the results together (e.g.
	 * <code>(2+6x+8y) + (2x+6x2+8xy)</code>).
	 *
	 * @param p
	 * @return
	 */
	public Polynomial multiply(Polynomial p) {
		int lhs_size = terms.length;
		int rhs_size = p.terms.length;
		Polynomial.Term[] combined = new Polynomial.Term[lhs_size * rhs_size];

		for (int i = 0; i != lhs_size; ++i) {
			Polynomial.Term lhsTerm = terms[i];
			int j_base = i * rhs_size;
			for (int j = 0; j != rhs_size; ++j) {
				Polynomial.Term rhsTerm = p.terms[j];
				combined[j_base + j] = Arithmetic.multiply(lhsTerm, rhsTerm);
			}
		}

		return construct(combined);
	}

	public Polynomial multiply(Polynomial.Term rhs) {
		int lhs_size = terms.length;
		Polynomial.Term[] combined = new Polynomial.Term[lhs_size];

		for (int i = 0; i != lhs_size; ++i) {
			Polynomial.Term lhsTerm = terms[i];
			combined[i] = Arithmetic.multiply(lhsTerm, rhs);
		}

		return construct(combined);
	}

	public Polynomial multiply(BigInteger rhs) {
		int lhs_size = terms.length;
		Polynomial.Term[] combined = new Polynomial.Term[lhs_size];

		for (int i = 0; i != lhs_size; ++i) {
			combined[i] = terms[i].multiply(rhs);
		}

		return construct(combined);
	}


	/**
	 * Factorise a given polynomial. For example, <code>2x+2</code> is
	 * factorised to be <code>x+1</code>. Observe that this does not preseve the
	 * result of the polynomial. However, it is safe to do when simplifying
	 * equations. For example, <code>2x == 2y</code> can be safely factorised to
	 * <code>x == y</code>.
	 *
	 * @param p
	 * @return
	 */
	public Polynomial factorise() {
		BigInteger factor = terms[0].getCoefficient();
		// In case of just one coefficient which is negative, we need to compute
		// abs() here.
		factor = factor.abs();
		//
		for (int i = 1; i != terms.length; ++i) {
			BigInteger c = terms[i].getCoefficient();
			factor = factor.gcd(c);
		}
		if (factor.equals(BigInteger.ZERO) || factor.equals(BigInteger.ONE)) {
			// No useful factor discovered
			return this;
		} else {
			// Yes, we found a useful factor. Therefore, divide all coefficients
			// by this.
			Polynomial r = Polynomial.ZERO;
			for (int i = 0; i != terms.length; ++i) {
				Polynomial.Term t = terms[i];
				BigInteger c = t.getCoefficient();
				c = c.divide(factor);
				r = r.add(new Polynomial.Term(c, t.getAtoms()));
			}
			return r;
		}
	}

	@Override
	public int compareTo(Polynomial p) {
		int lengthDifference = terms.length - p.terms.length;
		if(lengthDifference != 0) {
			return lengthDifference;
		} else {
			for(int i=0;i!=terms.length;++i) {
				Polynomial.Term t1 = terms[i];
				Polynomial.Term t2 = p.terms[i];
				int c = t1.compareTo(t2);
				if(c != 0) {
					return c;
				}
			}
			return 0;
		}
	}

	@Override
	public boolean equals(Object o) {
		if(o instanceof Polynomial) {
			Polynomial p = (Polynomial) o;
			return Arrays.equals(terms, p.terms);
		}
		return false;
	}

	@Override
	public int hashCode() {
		return Arrays.hashCode(terms);
	}

	public Expr toExpression() {
		Expr[] muls = new Expr[terms.length];
		for(int i=0;i!=muls.length;++i) {
			muls[i] = terms[i].toExpression();
		}
		if(muls.length == 1) {
			return muls[0];
		} else {
			return new Expr.Addition(muls);
		}
	}

	@Override
	public String toString() {
		String r = "(";
		for(int i=0;i!=terms.length;++i) {
			if(i != 0) {
				r += " + ";
			}
			r += terms[i].toString();
		}
		return r + ")";
	}

	public static class Term implements Comparable<Term> {
		private final BigInteger coefficient;
		private final Expr[] atoms;

		Term(BigInteger coefficient, Expr...atoms) {
			if(coefficient.equals(BigInteger.ZERO) && atoms.length > 0) {
				throw new IllegalArgumentException("invalid zero term");
			}
			this.coefficient = coefficient;
			this.atoms = atoms;
		}
		public BigInteger getCoefficient() {
			return coefficient;
		}
		public boolean isConstant() {
			return atoms.length == 0;
		}
		public Expr[] getAtoms() {
			return atoms;
		}

		@Override
		public int compareTo(Term t) {
			int lengthDifference = atoms.length - t.atoms.length;
			if (lengthDifference != 0) {
				return lengthDifference;
			} else {
				for (int i = 0; i != atoms.length; ++i) {
					Expr t1 = atoms[i];
					Expr t2 = t.atoms[i];
					int c = t1.compareTo(t2);
					if (c != 0) {
						return c;
					}
				}
				return coefficient.compareTo(t.coefficient);
			}
		}

		@Override
		public boolean equals(Object o) {
			if(o instanceof Term) {
				Term t = (Term) o;
				return coefficient.equals(t.coefficient) && Arrays.equals(atoms, t.atoms);
			}
			return false;
		}

		@Override
		public int hashCode() {
			return coefficient.hashCode() ^ Arrays.hashCode(atoms);
		}

		public Term negate() {
			return new Term(coefficient.negate(),atoms);
		}

		public Term multiply(BigInteger rhs) {
			if (coefficient.equals(BigInteger.ZERO)) {
				return this;
			} else if (rhs.equals(BigInteger.ZERO)) {
				return new Polynomial.Term(rhs);
			} else {
				BigInteger coefficient = this.coefficient.multiply(rhs);
				return new Polynomial.Term(coefficient, atoms);
			}
		}

		public Expr toExpression() {
			if (atoms.length == 0) {
				return new Expr.Constant(new Value.Int(coefficient));
			} else if (coefficient.equals(BigInteger.ONE)) {
				if(atoms.length == 1) {
					return atoms[0];
				} else {
					return new Expr.Multiplication(atoms);
				}
			} else {
				Expr[] es = new Expr[atoms.length + 1];
				es[0] = new Expr.Constant(new Value.Int(coefficient));
				System.arraycopy(atoms, 0, es, 1, atoms.length);
				return new Expr.Multiplication(es);
			}
		}

		@Override
		public String toString() {
			String r = "";
			if(!coefficient.equals(BigInteger.ONE) || atoms.length == 0) {
				r += coefficient;
				if(atoms.length > 0) {
					r += "*";
				}
			}
			for(int i=0;i!=atoms.length;++i) {
				if(i != 0) {
					r += "*";
				}
				r += atoms[i];
			}
			return r;
		}
	}
}
import java.util.Arrays;
import wyal.lang.WyalFile.Expr;
import wyal.util.NameResolver.ResolutionError;
import wyfs.util.Pair;
import wytp.proof.Formula;
import wytp.proof.Proof;
import wytp.proof.Proof.State;
import wytp.proof.rules.Simplification;
import wytp.proof.util.AbstractClosureRule;
import wytp.proof.util.Arithmetic;
import wytp.proof.util.Formulae;
import wytp.types.TypeSystem;
import wytp.proof.util.Arithmetic.Polynomial;
// Copyright 2011 The Whiley Project Developers
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package wytp.proof.rules.arithmetic;



/**
 * Responsible for emplying a form of <i>transitive closure</i> over
 * inequalities. For example, if <code>x < y</code> and <code>y < z</code> then
 * this rule might infer that <code>x < z</code>. To reduce the number of
 * unnecessary inferences, the rule is selective about how to determine new
 * inequalities. Specifically, it relies on a lexiographic ordering of terms and
 * will only produce inferences for the least ordered term in any given pair of
 * inequualities.
 *
 * @author David J. Pearce
 *
 */
public class InequalityIntroduction extends AbstractClosureRule implements Proof.LinearRule {
	public InequalityIntroduction(Simplification simp,TypeSystem types) {
		super(simp,types);
	}

	@Override
	public String getName() {
		return "Ieq-I";
	}

	@Override
	public State apply(Proof.Delta.Set existingTruths, Proof.State state, Formula newTruth) throws ResolutionError {
		if(newTruth instanceof Formula.Inequality) {
			Formula.Inequality inequality = (Formula.Inequality) newTruth;
			// At this point, we have an inequality which potentially could be
			// closed with one or more other inequalities. Therefore, we need to
			// look back through the history to determine any inequalities which
			// are currently "active".
			for(int i=0;i!=existingTruths.size();++i) {
				Formula existingTruth = existingTruths.get(i);
				if(existingTruth instanceof Formula.Inequality) {
					state = closeOver(inequality,(Formula.Inequality)existingTruth,state);
				}
			}
		}
		// No change in the normal case
		return state;
	}

	private State closeOver(Formula.Inequality ith, Formula.Inequality jth, State state) throws ResolutionError {
		//
		Formula inferred = closeOver(ith, jth);
		if (inferred != null) {
			inferred = simp.simplify(inferred);
			state = state.infer(this, inferred, ith, jth);
		}
		inferred = closeOver(jth, ith);
		if (inferred != null) {
			inferred = simp.simplify(inferred);
			state = state.infer(this, inferred, ith, jth);
		}
		return state;
	}


	/**
	 * <p>
	 * Close over two inequalities. This may or may not produce a new inequality
	 * as a result. For example, closing over <code>3 < x</code> and
	 * <code>x < y</code> gives <code>3 < y</code>. Observe that, for this
	 * operation to succeed, there must exist a term common to both
	 * inequalities. In the case that multiple candidate terms exist, then the
	 * lexiographically least is selected.
	 * </p>
	 * <p>
	 * This operation always closes in the same direction. If ith is "p1 >= p2"
	 * and jth is "p3 >= p4" then it attempts to generate the inequality of the
	 * form "p1 >= p4", but never of the form "p4 >= p1". In otherwords, the ith
	 * inequality always provides the lower bound and the jth inequality always
	 * provides the upper bound.
	 * </p>
	 *
	 * <b>NOTE:</b> this currently assumes that the inequalities are balanced.
	 *
	 * @param ith
	 * @param jth
	 * @return
	 */
	public Formula closeOver(Formula.Inequality ith, Formula.Inequality jth) throws ResolutionError {
		Polynomial ithLowerBound = extractBound(false, ith);
		Polynomial ithUpperBound = extractBound(true, ith);
		Polynomial jthLowerBound = extractBound(false, jth);
		Polynomial jthUpperBound = extractBound(true, jth);
		// A language with destructuring would be nice here
		Pair<Polynomial.Term, Polynomial.Term> candidates = selectCandidateTerm(ithLowerBound, jthUpperBound);
		//
		if (candidates == null) {
			// No matching candidates were found for this orientation.
			return null;
		} else {
			Polynomial.Term ithCandidate = candidates.first();
			Polynomial.Term jthCandidate = candidates.second();
			Polynomial ithUpper = rearrangeForUpperBound(ithLowerBound, ithUpperBound, ithCandidate);
			Polynomial jthLower = rearrangeForLowerBound(jthLowerBound, jthUpperBound, jthCandidate);
			ithUpper = ithUpper.multiply(jthCandidate.getCoefficient());
			jthLower = jthLower.multiply(ithCandidate.getCoefficient());
			// 2 < 2x, 3x < 3
			//
			if (ithUpper.equals(jthLower)) {
				Polynomial.Term candidate = ithCandidate.multiply(jthCandidate.getCoefficient());
				return new Formula.ArithmeticEquality(true, candidate.toExpression(), ithUpper.toExpression());
			} else {
				return Formulae.greaterOrEqual(ithUpper.toExpression(),jthLower.toExpression());
			}
		}
	}

	/**
	 * Extract a given bound from the inequality. Here, true is upper and false
	 * is lower.
	 *
	 * @param sign
	 * @param inequality
	 * @return
	 */
	private static Polynomial extractBound(boolean sign, Formula.Inequality inequality) {
		int i = sign ? 0 : 1;
		return Arithmetic.asPolynomial(inequality.get(i));
	}

	/**
	 * <p>
	 * Determine a suitable term (if one exists) for rearranging the two
	 * inequalities. A candidate term must be common to both and involve at
	 * least one variable, and should appear on opposite sides of the
	 * inequalities. The selected candidate then has the lowest ordering of any
	 * possible term. For example, consider these two options:
	 * </p>
	 *
	 * <pre>
	 * x < y + z
	 * x + y > z
	 * </pre>
	 *
	 * <p>
	 * For these two equations, the candidate terms are <code>x</code> and
	 * <code>z</code>. Since <code>y</code> is an upper bound on both, it is not
	 * considered. Then, <code>x</code> is selected as the actual term for
	 * rearranging since it is lexiographically lower than <code>z</code>.
	 * </p>
	 *
	 * @param ith
	 * @param jth
	 * @return
	 */
	private static Pair<Polynomial.Term, Polynomial.Term> selectCandidateTerm(Polynomial lower, Polynomial upper) {
		for (int i = 0; i != lower.size(); ++i) {
			Polynomial.Term ith = lower.getTerm(i);
			Expr[] ithAtoms = ith.getAtoms();