public abstract class AST {
	
	public abstract <R> R accept(Visitor<R> v);
	
	@Override
	public String toString() {
		StringWriter out = new StringWriter();
		this.accept(new PrettyPrintVisitor(new PrintWriter(out)));
		return out.toString();
	}

} public class And extends Expression {

	public final Expression e1;
	public final Expression e2;
	
	public And(Expression e1, Expression e2) {
		super();
		super.setType(BooleanType.instance);
		this.e1 = e1;
		this.e2 = e2;
	}
	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

	
} public class ArrayAssign extends Statement {

	public final String name;
	public final Expression index;
	public final Expression value;
	
	public ArrayAssign(String name, Expression index, Expression value) {
		super();
		this.name = name;
		this.index = index;
		this.value = value;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class ArrayLength extends Expression {
	
	public final Expression array;
	
	public ArrayLength(Expression array) {
		super();
		super.setType(IntegerType.instance);
		this.array = array;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class ArrayLookup extends Expression {

	public final Expression array;
	public final Expression index;
	
	public ArrayLookup(Expression array, Expression index) {
		super();
		super.setType(IntegerType.instance);//all arrays contain integers
		this.array = array;
		this.index = index;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class Assign extends Statement {
	
	public final String name;
	public final Expression value;
	
	public Assign(String name, Expression value) {
		super();
		this.name = name;
		this.value = value;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class Block extends Statement {
	
	public final NodeList<Statement> statements;

	public Block(NodeList<Statement> statements) {
		super();
		this.statements = statements;
	}

	public Block(List<Statement> statements) {
		this(new NodeList<Statement>(statements));
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}
	
	

} public class BooleanLiteral extends Expression {
	
	public final boolean value;

	public BooleanLiteral(boolean value) {
		super();
		super.setType(BooleanType.instance);
		this.value = value;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class BooleanType extends Type {
	public static BooleanType instance = new BooleanType();
	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

	@Override
	public boolean equals(Object other) {
		return this.getClass()==other.getClass();
	}
	
} public class Call extends Expression {

	public final Expression receiver;
	public final String name;
	public final NodeList<Expression> rands;

	public Call(Expression receiver, String name, NodeList<Expression> rands) {
		super();
		this.receiver = receiver;
		this.name = name;
		this.rands = rands;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class ClassDecl extends AST {
	
	public final String name;
	public final String superName; //May be null!
	
	public final NodeList<VarDecl> vars;
	public final NodeList<MethodDecl> methods;
	
	public ClassDecl(String name, String superName, NodeList<VarDecl> vars,
			NodeList<MethodDecl> methods) {
		super();
		this.name = name;
		this.superName = superName;
		this.vars = vars;
		this.methods = methods;
	}

	public ClassDecl(String name, String superName, List<VarDecl> vars,
			List<MethodDecl> methods) {
		this(
			name, superName, 
			new NodeList<VarDecl>(vars), new NodeList<MethodDecl>(methods)
		);
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public abstract class Expression extends AST {
	
	/**
	 * The type of an expression is set by the type checking phase.
	 */
	public Type type;

	public Type getType() {
		Assert.assertNotNull("Was this AST typechecked?", type);
		return type;
	}
	
	public void setType(Type theType) {
		//Assert.assertNull(type); 
		//As our visitor is written, we expect the types of some nodes to be set multiple times.
		//as long as there is no conflict in these type settings, there is no problem, and the assertion has been
		//modified to reflect that.
		assert(type==null || type.equals(theType));		
		type = theType;
	}

} public class IdentifierExp extends Expression {

	public final String name;
	
	public IdentifierExp(String name) {
		super();
		this.name = name;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class If extends Statement {
	
	public final Expression tst;
	public final Statement thn;
	public final Statement els;
	
	public If(Expression tst, Statement thn, Statement els) {
		super();
		this.tst = tst;
		this.thn = thn;
		this.els = els;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}
	
} public class IntArrayType extends Type {
	public static IntArrayType instance = new IntArrayType();
	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}
	
	@Override
	public boolean equals(Object other) {
		return this.getClass()==other.getClass();
	}


} public class IntegerLiteral extends Expression {

	public final int value;

	public IntegerLiteral(int value) {
		super();
		super.setType(IntegerType.instance);
		this.value = value;
	}

	public IntegerLiteral(String image) {
		this(Integer.parseInt(image));
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class IntegerType extends Type {
	public static IntegerType instance = new IntegerType();
	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}
	
	@Override
	public boolean equals(Object other) {
		return this.getClass()==other.getClass();
	}

} public class LessThan extends Expression {

	public final Expression e1;
	public final Expression e2;
	
	public LessThan(Expression e1, Expression e2) {
		super();
		super.setType(BooleanType.instance);
		this.e1 = e1;
		this.e2 = e2;
	}
	
	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}


} public class MainClass extends AST {

	public final String className;
	public final String argName;
	public final Statement statement;

	public MainClass(String className, String argName, Statement statement) {
		super();
		this.className = className;
		this.argName = argName;
		this.statement = statement;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class MethodDecl extends AST {
	
	public final Type returnType;
	public final String name;
	public final NodeList<VarDecl> formals;
	public final NodeList<VarDecl> vars;
	public final NodeList<Statement> statements;
	public final Expression returnExp;
	
	public MethodDecl(Type returnType, String name, NodeList<VarDecl> formals,
			NodeList<VarDecl> vars, NodeList<Statement> statements, Expression returnExp) {
		super();
		this.returnType = returnType;
		this.name = name;
		this.formals = formals;
		this.vars = vars;
		this.statements = statements;
		this.returnExp = returnExp;
	}

	public MethodDecl(Type returnType, String name, List<VarDecl> formals,
			List<VarDecl> vars, List<Statement> statements, Expression returnExp) {
		this(
			returnType, name, new NodeList<VarDecl>(formals), 
			new NodeList<VarDecl>(vars),
			new NodeList<Statement>(statements),
			returnExp
		);
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class Minus extends Expression {

	public final Expression e1;
	public final Expression e2;

	public Minus(Expression e1, Expression e2) {
		super();
		super.setType(IntegerType.instance);
		this.e1 = e1;
		this.e2 = e2;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class NewArray extends Expression {

	public final Expression size;

	public NewArray(Expression size) {
		super();
		super.setType(IntArrayType.instance);
		this.size = size;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class NewObject extends Expression {

	public final String typeName;

	public NewObject(String typeName) {
		super();
		this.typeName = typeName;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class NodeList<T extends AST> extends AST {
	
	private List<T> nodes;

	public NodeList(List<T> nodes) {
		this.nodes = nodes;
	}

	public int size() {
		return nodes.size();
	}

	public T elementAt(int i) {
		return nodes.get(i);
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class Not extends Expression {

	public final Expression e;
	
	public Not(Expression e) {
		super();
		super.setType(BooleanType.instance);
		this.e = e;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class ObjectType extends Type {
	
	public final String name;

	public ObjectType(String name) {
		super();
		this.name = name;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

	@Override
	public boolean equals(Object other) {
		if (this.getClass()==other.getClass()) {
			return this.name.equals(((ObjectType)other).name);
		}
		return false;
	}
} public class Plus extends Expression {

	public final Expression e1;
	public final Expression e2;

	public Plus(Expression e1, Expression e2) {
		super();
		super.setType(IntegerType.instance);
		this.e1 = e1;
		this.e2 = e2;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class Print extends Statement {

	public final Expression exp;

	public Print(Expression exp) {
		super();
		this.exp = exp;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class Program extends AST {
	
	public final MainClass mainClass;
	public final NodeList<ClassDecl> classes;

	public Program(MainClass mainClass, NodeList<ClassDecl> otherClasses) {
		this.mainClass=mainClass;
		this.classes=otherClasses; 
	}

	public Program(MainClass m, List<ClassDecl> cs) {
		this(m, new NodeList<ClassDecl>(cs));
	}
	
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class This extends Expression {

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class Times extends Expression {

	public final Expression e1;
	public final Expression e2;

	public Times(Expression e1, Expression e2) {
		super();
		super.setType(IntegerType.instance);
		this.e1 = e1;
		this.e2 = e2;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public abstract class Type extends AST {
	
	@Override
	public abstract boolean equals(Object other);

} public class VarDecl extends AST {

	public static enum Kind {
		FIELD, LOCAL, FORMAL
	}

	public final Kind   kind;
	public final Type   type;
	public final String name;

	public VarDecl(Kind kind, Type type, String name) {
		super();
		this.kind = kind;
		this.type = type;
		this.name = name;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class While extends Statement {

	public final Expression tst;
	public final Statement body;
	
	public While(Expression tst, Statement body) {
		super();
		this.tst = tst;
		this.body = body;
	}

	@Override
	public <R> R accept(Visitor<R> v) {
		return v.visit(this);
	}

} public class ErrorReport {
	
	private ErrorMessage firstError = null;
	
	public ErrorReport() {}

	/**
	 * Add an error to the ErrorReport.
	 * <p>
	 * In this implementation the msg is simply printed to System.out. Also, the first message
	 * is saved, so it can be verified by unit tests.
	 */
	void report(ErrorMessage msg) {
		if (firstError==null) 
			firstError = msg;
		System.out.println(msg);
	}
	
	/**
	 * To allow processing all of the input (so that as many errors as possible can be
	 * reported) and raising an error only in the end
	 * this method is provided. You should call this method when you are done reporting
	 * errors.
	 * <p>
	 * This method will raise an Exception if the error report contains some errors, 
	 * otherwise the method will return normally.
	 * <p>
	 * @throws TypeCheckerException 
	 */
	public void close() throws TypeCheckerException {
		if (firstError!=null)
			throw new TypeCheckerException(firstError);
	}

	public void duplicateDefinition(String name) {
		report(ErrorMessage.duplicateDefinition(name));
	}

	public void undefinedId(String name) {
		report(ErrorMessage.undefinedId(name));
	}
	
	public void typeError(Expression exp, Type expected, Type actual) {
		report(ErrorMessage.typeError(exp,expected,actual));
	}

	public void typeErrorExpectObjectType(Expression exp, Type actual) {
		report(ErrorMessage.typeErrorExpectObject(exp,actual));
	}

	public void wrongNumberOfArguments(Call call, int expected) {
		report(ErrorMessage.wrongNumberOfArguments(call, expected));
	}

	public void fieldOverriding(ObjectType cls, String fieldName) {
		report(ErrorMessage.fieldOverriding(cls, fieldName));
	}
	public void badMethodOverriding(ObjectType cls, String methodName) {
		report(ErrorMessage.badMethodOverriding(cls, methodName));
	}

} public class ClassEntry implements Indentable {
	
	String parentName;
	ClassEntry parentClass;
	ImpTable<MethodEntry> methods;
	ImpTable<Type> fields;
	final String className;
	
	public String getClassName() {
		return className;
	}
	
	public ClassEntry (String className, String parentName) {
		methods = new ImpTable<MethodEntry>();
		fields = new ImpTable<Type>();
		this.className = className;
		this.parentName = parentName;
		this.parentClass = null;
	}

	public ImpTable<MethodEntry> getMethods() {
		return methods;
	}

	public void setMethods(ImpTable<MethodEntry> methods) {
		this.methods = methods;
	}

	public ImpTable<Type> getFields() {
		return fields;
	}

	public void setFields(ImpTable<Type> fields) {
		this.fields = fields;
	}
	
	public String getParentName() {
		return parentName;
	}
	
	public ClassEntry getParentClass() {
		return parentClass;
	}
	
	public void setParentClass(ClassEntry parentClass) {
		this.parentClass = parentClass;
	}
	
	public Type lookupVariable(String id) {
		Type field = fields.lookup(id);
		
		if (field == null && parentClass != null) {
			field = parentClass.lookupVariable(id);
		}
		
		return field;
	}

	public MethodEntry lookupMethod(String id) {
		MethodEntry method = methods.lookup(id);
		
		if (method == null && parentClass != null) {
			method = parentClass.lookupMethod(id);
		}
		
		return method;
	}
	
	@Override
	public void dump(IndentingWriter out) {
		out.println();
		out.indent();
		
		out.println("Methods:");
		out.indent();
		for (Entry<String, MethodEntry> entry : methods) {
			out.print(entry.getKey());
			out.print(": ");
			out.print(entry.getValue());
		}
		out.outdent();
		
		out.println("Fields:");
		out.indent();
		for (Entry<String, Type> entry : fields) {
			out.print(entry.getKey());
			out.print(": ");
			out.print(entry.getValue());
			out.println();
		}
		out.outdent();
		out.outdent();
	}
} public class MethodEntry implements Indentable {
	ClassEntry parent; 
	public ClassEntry getParent() {
		return parent;
	}
	List<Type> paramTypes = new ArrayList<Type>();
	ImpTable<Type> variables;
	ImpTable<Type> parameters;
	Type returnType;
	
	public MethodEntry(ClassEntry parent) {
		this.parent = parent;
		variables = new ImpTable<Type>();
		parameters = new ImpTable<Type>();
		returnType = null;
	}
	
	public ImpTable<Type> getVariables() {
		return variables;
	}
	
	public void setVariables(ImpTable<Type> variables) {
		this.variables = variables;
	}
	
	public ImpTable<Type> getParameters() {
		return parameters;
	}

	
	public List<Type> getParamTypes() {
		return paramTypes;
	}

	public Type getReturnType() {
		return returnType;
	}
	
	public void setReturnType(Type returnType) {
		this.returnType = returnType;
	}
	
	public Type lookupVariable(String id) {
		Type type = null;
		Type type1 = variables.lookup(id);
		Type type2 = parameters.lookup(id);
		
		if (type1 == null && type2 == null) {
			type = parent.lookupVariable(id);
		}
		else if (type1 == null) {
			type = type2;
		}
		else if (type2 == null) {
			type = type1;
		}
		
		return type;
	}
	
	public Type lookupMethod(String id) {
		Type type = null;	
		MethodEntry method = parent.lookupMethod(id);
		
		if (method != null) {
			type = method.getReturnType();
		}
		
		return type;
	}
	
	@Override
	public void dump(IndentingWriter out) {		
		out.indent();
		out.println();
		out.println("Parameters: ");
		
		out.indent();
		for (Entry<String, Type> varEntry : parameters) {
			out.print(varEntry.getKey());
			out.print(" :: ");
			out.print(varEntry.getValue());
			out.println();
		}
		out.outdent();
		
		out.println("Variables: ");
		out.indent();
		for (Entry<String, Type> varEntry : variables) {
			out.print(varEntry.getKey());
			out.print(" :: ");
			out.print(varEntry.getValue());
			out.println();
		}
		out.outdent();
		
		out.outdent();
	}
	
} public class ImpTable<V> extends DefaultIndentable 
implements Iterable<Entry<String, V>>, Lookup<V>
{
	
	public static class DuplicateException extends Exception {

		private static final long serialVersionUID = 8650830167061316305L;

		public DuplicateException(String arg0) {
			super(arg0);
		}

	}

	private Map<String, V> map = new HashMap<String, V>();

	@Override
	public Iterator<Entry<String,V>> iterator() {
		return map.entrySet().iterator();
	}
	
	/**
	 * Insert an entry into the table. This modifies the table.
	 * Duplicate entries (i.e. with the same id are not supported).
	 * When a duplicate id is being entered a DuplicatException is
	 * thrown.
	 * <p>
	 * Note: the name "put" different from the name "insert" in the
	 * FunTable is deliberate. This will make sure you get compile
	 * errors when you try to change code using imperative puts
	 * to use functional inserts instead.
	 */
	public void put(String id, V value) throws DuplicateException {
		Assert.assertNotNull(value);
		Assert.assertNotNull(id);
		V existing = map.get(id);
		if (existing!=null) throw new DuplicateException("Duplicate entry: "+id);
		map.put(id, value);
	}
	
	/**
	 * Find an entry in the table. If no entry is found, null is returned.
	 */
	public V lookup(String id) {
		return map.get(id);
	}

	@Override
	public void dump(IndentingWriter out) {
		out.println("Table {");
		out.indent();
		for (Entry<String, V> entry : this) {
			out.print(entry.getKey()+" = ");
			out.println(entry.getValue());
		}
		out.outdent();
		out.print("}");
	}

	public boolean isEmpty() {
		return size()==0;
	}

	@Override
	public int size() {
		return map.size();
	}

}
import java.util.List;
import minijava.ast.AST;
import minijava.ast.And;
import minijava.ast.ArrayAssign;
import minijava.ast.ArrayLength;
import minijava.ast.ArrayLookup;
import minijava.ast.Assign;
import minijava.ast.Block;
import minijava.ast.BooleanLiteral;
import minijava.ast.BooleanType;
import minijava.ast.Call;
import minijava.ast.ClassDecl;
import minijava.ast.Expression;
import minijava.ast.IdentifierExp;
import minijava.ast.If;
import minijava.ast.IntArrayType;
import minijava.ast.IntegerLiteral;
import minijava.ast.IntegerType;
import minijava.ast.LessThan;
import minijava.ast.MainClass;
import minijava.ast.MethodDecl;
import minijava.ast.Minus;
import minijava.ast.NewArray;
import minijava.ast.NewObject;
import minijava.ast.NodeList;
import minijava.ast.Not;
import minijava.ast.ObjectType;
import minijava.ast.Plus;
import minijava.ast.Print;
import minijava.ast.Program;
import minijava.ast.This;
import minijava.ast.Times;
import minijava.ast.Type;
import minijava.ast.VarDecl;
import minijava.ast.While;
import minijava.typechecker.ErrorReport;
import minijava.typechecker.implementation.ClassEntry;
import minijava.typechecker.implementation.MethodEntry;
import minijava.util.ImpTable;
package minijava.visitor;



public class TypeCheckerVisitor extends ReflectionVisitor {
	ImpTable<ClassEntry> classTable;
	ErrorReport reporter;
	
	public TypeCheckerVisitor(ImpTable<ClassEntry> classTable, ErrorReport reporter) {
		this.classTable = classTable;
		this.reporter = reporter;
	}
	
	public <T extends AST> void visit(NodeList<T> nodeList) {
		for (int i = 0; i < nodeList.size(); i++) {
			visit(nodeList.elementAt(i));
		}
	}
	
	public <T extends AST> void visit(NodeList<T> nodeList, ClassEntry entry) {
		for (int i = 0; i < nodeList.size(); i++) {
			visit(nodeList.elementAt(i), entry);
		}
	}
	
	public <T extends AST> void visit(NodeList<T> nodeList, MethodEntry entry) {
		for (int i = 0; i < nodeList.size(); i++) {
			visit(nodeList.elementAt(i), entry);
		}
	}

	public void visit(Program n) {
		visit(n.mainClass);
		visit(n.classes);
	}
	
	public void visit(MainClass n) {
		ClassEntry classEntry = classTable.lookup(n.className);
		if(classEntry == null)
			reporter.undefinedId(n.className);
		
		MethodEntry mainMethod = classEntry.lookupMethod("main");
		
		visit(n.statement,mainMethod);
	}

	public void visit(ClassDecl n) {
		ClassEntry classEntry = classTable.lookup(n.name);
		String parentName = classEntry.getParentName();

		if (classEntry == null)
			reporter.undefinedId(n.name);
		
		if (parentName != null) {
			ClassEntry parentEntry = classTable.lookup(parentName);
			if (parentEntry == null) {
				reporter.undefinedId(parentName);
			} 
		}

		visit(n.vars, classEntry);
		visit(n.methods, classEntry);
	}

	public void visit(MethodDecl n, ClassEntry entry) {	