public abstract class Tree {

    /**
     * Toplevel nodes, of type TopLevel, representing entire source files.
     */
    public static final int TOPLEVEL = 1;

    /**
     * Import clauses, of type Import.
     */
    public static final int IMPORT = TOPLEVEL + 1;

    /**
     * Class definitions, of type ClassDef.
     */
    public static final int CLASSDEF = IMPORT + 1;

    /**
     * Method definitions, of type MethodDef.
     */
    public static final int METHODDEF = CLASSDEF + 1;

    /**
     * Variable definitions, of type VarDef.
     */
    public static final int VARDEF = METHODDEF + 1;

    /**
     * The no-op statement ";", of type Skip
     */
    public static final int SKIP = VARDEF + 1;

    /**
     * Blocks, of type Block.
     */
    public static final int BLOCK = SKIP + 1;

    /**
     * Do-while loops, of type DoLoop.
     */
    public static final int DOLOOP = BLOCK + 1;

    /**
     * While-loops, of type WhileLoop.
     */
    public static final int WHILELOOP = DOLOOP + 1;

    /**
     * For-loops, of type ForLoop.
     */
    public static final int FORLOOP = WHILELOOP + 1;

    /**
     * Labelled statements, of type Labelled.
     */
    public static final int LABELLED = FORLOOP + 1;

    /**
     * Switch statements, of type Switch.
     */
    public static final int SWITCH = LABELLED + 1;

    /**
     * Case parts in switch statements, of type Case.
     */
    public static final int CASE = SWITCH + 1;

    /**
     * Synchronized statements, of type Synchonized.
     */
    public static final int SYNCHRONIZED = CASE + 1;

    /**
     * Try statements, of type Try.
     */
    public static final int TRY = SYNCHRONIZED + 1;

    /**
     * Catch clauses in try statements, of type Catch.
     */
    public static final int CATCH = TRY + 1;

    /**
     * Conditional expressions, of type Conditional.
     */
    public static final int CONDEXPR = CATCH + 1;

    /**
     * Conditional statements, of type If.
     */
    public static final int IF = CONDEXPR + 1;

    /**
     * Expression statements, of type Exec.
     */
    public static final int EXEC = IF + 1;

    /**
     * Break statements, of type Break.
     */
    public static final int BREAK = EXEC + 1;

    /**
     * Continue statements, of type Continue.
     */
    public static final int CONTINUE = BREAK + 1;

    /**
     * Return statements, of type Return.
     */
    public static final int RETURN = CONTINUE + 1;

    /**
     * Throw statements, of type Throw.
     */
    public static final int THROW = RETURN + 1;

    /**
     * Assert statements, of type Assert.
     */
    public static final int ASSERT = THROW + 1;

    /**
     * Method invocation expressions, of type Apply.
     */
    public static final int APPLY = ASSERT + 1;

    /**
     * Class instance creation expressions, of type NewClass.
     */
    public static final int NEWCLASS = APPLY + 1;

    /**
     * Array creation expressions, of type NewArray.
     */
    public static final int NEWARRAY = NEWCLASS + 1;

    /**
     * Parenthesized subexpressions, of type Parens.
     */
    public static final int PARENS = NEWARRAY + 1;

    /**
     * Assignment expressions, of type Assign.
     */
    public static final int ASSIGN = PARENS + 1;

    /**
     * Type cast expressions, of type TypeCast.
     */
    public static final int TYPECAST = ASSIGN + 1;

    /**
     * Type test expressions, of type TypeTest.
     */
    public static final int TYPETEST = TYPECAST + 1;

    /**
     * Indexed array expressions, of type Indexed.
     */
    public static final int INDEXED = TYPETEST + 1;

    /**
     * Selections, of type Select.
     */
    public static final int SELECT = INDEXED + 1;

    /**
     * Simple identifiers, of type Ident.
     */
    public static final int IDENT = SELECT + 1;

    /**
     * Literals, of type Literal.
     */
    public static final int LITERAL = IDENT + 1;

    /**
     * Basic type identifiers, of type TypeIdent.
     */
    public static final int TYPEIDENT = LITERAL + 1;

    /**
     * Class types, of type TypeClass.
     */    
    public static final int TYPECLASS = TYPEIDENT + 1;

    /**
     * Array types, of type TypeArray.
     */
    public static final int TYPEARRAY = TYPECLASS + 1;

    /**
     * Parameterized types, of type TypeApply.
     */
    public static final int TYPEAPPLY = TYPEARRAY + 1;

    /**
     * Formal type parameters, of type TypeParameter.
     */
    public static final int TYPEPARAMETER = TYPEAPPLY + 1;

    /**
     * Error trees, of type Erroneous.
     */
    public static final int ERRONEOUS = TYPEPARAMETER + 1;

    /**
     * Unary operators, of type Unary.
     */
    public static final int POS = ERRONEOUS + 1;
    public static final int NEG = POS + 1;
    public static final int NOT = NEG + 1;
    public static final int COMPL = NOT + 1;
    public static final int PREINC = COMPL + 1;
    public static final int PREDEC = PREINC + 1;
    public static final int POSTINC = PREDEC + 1;
    public static final int POSTDEC = POSTINC + 1;

    /**
     * unary operator for null reference checks, only used internally.
     */
    public static final int NULLCHK = POSTDEC + 1;

    /**
     * Binary operators, of type Binary.
     */
    public static final int OR = NULLCHK + 1;
    public static final int AND = OR + 1;
    public static final int BITOR = AND + 1;
    public static final int BITXOR = BITOR + 1;
    public static final int BITAND = BITXOR + 1;
    public static final int EQ = BITAND + 1;
    public static final int NE = EQ + 1;
    public static final int LT = NE + 1;
    public static final int GT = LT + 1;
    public static final int LE = GT + 1;
    public static final int GE = LE + 1;
    public static final int SL = GE + 1;
    public static final int SR = SL + 1;
    public static final int USR = SR + 1;
    public static final int PLUS = USR + 1;
    public static final int MINUS = PLUS + 1;
    public static final int MUL = MINUS + 1;
    public static final int DIV = MUL + 1;
    public static final int MOD = DIV + 1;

    public static final int NULL = MOD + 1;
    public static final int CALLEXPR = NULL + 1;
    public static final int THISEXPR = CALLEXPR + 1;
    public static final int READINTEXPR = THISEXPR + 1;
    public static final int READLINEEXPR = READINTEXPR + 1;
    public static final int PRINT = READLINEEXPR + 1;
    
    /**
     * Tags for Literal and TypeLiteral
     */
    public static final int VOID = 0; 
    public static final int INT = VOID + 1; 
    public static final int BOOL = INT + 1; 
    public static final int STRING = BOOL + 1; 


    public Location loc;
    public Type type;
    public int tag;
    
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /**
     * Tag for repeat until loop
     * */
    public static final int REPEAT_UNTIL_LOOP = PRINT + 1;
    public static final int DOUBLE = STRING + 1;
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    

    /**
     * Initialize tree with given tag.
     */
    public Tree(int tag, Location loc) {
        super();
        this.tag = tag;
        this.loc = loc;
    }

	public Location getLocation() {
		return loc;
	}

    /**
      * Set type field and return this tree.
      */
    public Tree setType(Type type) {
        this.type = type;
        return this;
    }

    /**
      * Visit this tree with a given visitor.
      */
    public void accept(Visitor v) {
        v.visitTree(this);
    }

	public abstract void printTo(IndentPrintWriter pw);

    public static class TopLevel extends Tree {

		public List<ClassDef> classes;
		public Class main;
		public GlobalScope globalScope;
		
		public TopLevel(List<ClassDef> classes, Location loc) {
			super(TOPLEVEL, loc);
			this.classes = classes;
		}

    	@Override
        public void accept(Visitor v) {
            v.visitTopLevel(this);
        }

		@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("program");
    		pw.incIndent();
    		for (ClassDef d : classes) {
    			d.printTo(pw);
    		}
    		pw.decIndent();
    	}
    }

    public static class ClassDef extends Tree {
    	
    	public String name;
    	public String parent;
    	public List<Tree> fields;
    	public Class symbol;

        public ClassDef(String name, String parent, List<Tree> fields,
    			Location loc) {
    		super(CLASSDEF, loc);
    		this.name = name;
    		this.parent = parent;
    		this.fields = fields;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitClassDef(this);
        }
        
    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("class " + name + " "
    				+ (parent != null ? parent : "<empty>"));
    		pw.incIndent();
    		for (Tree f : fields) {
    			f.printTo(pw);
    		}
    		pw.decIndent();
    	}
   }

    public static class MethodDef extends Tree {
    	
    	public boolean statik;
    	public String name;
    	public TypeLiteral returnType;
    	public List<VarDef> formals;
    	public Block body;
    	public Function symbol;
    	
        public MethodDef(boolean statik, String name, TypeLiteral returnType,
        		List<VarDef> formals, Block body, Location loc) {
            super(METHODDEF, loc);
    		this.statik = statik;
    		this.name = name;
    		this.returnType = returnType;
    		this.formals = formals;
    		this.body = body;
       }

        public void accept(Visitor v) {
            v.visitMethodDef(this);
        }
    	
    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		if (statik) {
    			pw.print("static ");
    		}
    		pw.print("func " + name + " ");
    		returnType.printTo(pw);
    		pw.println();
    		pw.incIndent();
    		pw.println("formals");
    		pw.incIndent();
    		for (VarDef d : formals) {
    			d.printTo(pw);
    		}
    		pw.decIndent();
    		body.printTo(pw);
    		pw.decIndent();
    	}
    }

    public static class VarDef extends Tree {
    	
    	public String name;
    	public TypeLiteral type;
    	public Variable symbol;

        public VarDef(String name, TypeLiteral type, Location loc) {
            super(VARDEF, loc);
    		this.name = name;
    		this.type = type;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitVarDef(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.print("vardef " + name + " ");
    		type.printTo(pw);
    		pw.println();
    	}
    }

    /**
      * A no-op statement ";".
      */
    public static class Skip extends Tree {

        public Skip(Location loc) {
            super(SKIP, loc);
        }

    	@Override
        public void accept(Visitor v) {
            v.visitSkip(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		//print nothing
    	}
    }

    public static class Block extends Tree {

    	public List<Tree> block;
    	public LocalScope associatedScope;

        public Block(List<Tree> block, Location loc) {
            super(BLOCK, loc);
    		this.block = block;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitBlock(this);
        }
    	
    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("stmtblock");
    		pw.incIndent();
    		for (Tree s : block) {
    			s.printTo(pw);
    		}
    		pw.decIndent();
    	}
    }

    /**
      * A while loop
      */
    public static class WhileLoop extends Tree {

    	public Expr condition;
    	public Tree loopBody;

        public WhileLoop(Expr condition, Tree loopBody, Location loc) {
            super(WHILELOOP, loc);
            this.condition = condition;
            this.loopBody = loopBody;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitWhileLoop(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("while");
    		pw.incIndent();
    		condition.printTo(pw);
    		if (loopBody != null) {
    			loopBody.printTo(pw);
    		}
    		pw.decIndent();
    	}
   }

    
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /**
     * A repeat until loop
     * */
    public static class RepeatLoop extends Tree
    {
    	public Expr condition;
    	public Tree loopBody;
    	
		public RepeatLoop(Expr condition, Tree loopBody, Location loc)
		{
			super(REPEAT_UNTIL_LOOP, loc);
			this.condition = condition;
			this.loopBody = loopBody;
		}
		
		@Override
        public void accept(Visitor v) {
            v.visitRepeatLoop(this);
        }

		@Override
		public void printTo(IndentPrintWriter pw)
		{
			pw.println("repeatLoop");
    		pw.incIndent();
    		if (loopBody != null) {
    			loopBody.printTo(pw);
    		}
    		//pw.decIndent();
    		//pw.println("until");
    		//pw.incIndent();
    		condition.printTo(pw);
    		pw.decIndent();
		}
    	
    }
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    
    
    
    
    
    
    /**
      * A for loop.
      */
    public static class ForLoop extends Tree {

    	public Tree init;
    	public Expr condition;
    	public Tree update;
    	public Tree loopBody;

        public ForLoop(Tree init, Expr condition, Tree update,
        		Tree loopBody, Location loc) {
            super(FORLOOP, loc);
    		this.init = init;
    		this.condition = condition;
    		this.update = update;
    		this.loopBody = loopBody;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitForLoop(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("for");
    		pw.incIndent();
    		if (init != null) {
    			init.printTo(pw);
    		} else {
    			pw.println("<emtpy>");
    		}
    		condition.printTo(pw);
    		if (update != null) {
    			update.printTo(pw);
    		} else {
    			pw.println("<empty>");
    		}
    		if (loopBody != null) {
    			loopBody.printTo(pw);
    		}
    		pw.decIndent();
    	}
   }

    /**
      * An "if ( ) { } else { }" block
      */
    public static class If extends Tree {
    	
    	public Expr condition;
    	public Tree trueBranch;
    	public Tree falseBranch;

        public If(Expr condition, Tree trueBranch, Tree falseBranch,
    			Location loc) {
            super(IF, loc);
            this.condition = condition;
    		this.trueBranch = trueBranch;
    		this.falseBranch = falseBranch;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitIf(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("if");
    		pw.incIndent();
    		condition.printTo(pw);
    		if (trueBranch != null) {
    			trueBranch.printTo(pw);
    		}
    		pw.decIndent();
    		if (falseBranch != null) {
    			pw.println("else");
    			pw.incIndent();
    			falseBranch.printTo(pw);
    			pw.decIndent();
    		}
    	}
    }

    /**
      * an expression statement
      * @param expr expression structure
      */
    public static class Exec extends Tree {

    	public Expr expr;

        public Exec(Expr expr, Location loc) {
            super(EXEC, loc);
            this.expr = expr;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitExec(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		expr.printTo(pw);
    	}
    }

    /**
      * A break from a loop.
      */
    public static class Break extends Tree {

        public Break(Location loc) {
            super(BREAK, loc);
        }

    	@Override
        public void accept(Visitor v) {
            v.visitBreak(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("break");
    	}
    }

    /**
      * A return statement.
      */
    public static class Print extends Tree {

    	public List<Expr> exprs;

    	public Print(List<Expr> exprs, Location loc) {
    		super(PRINT, loc);
    		this.exprs = exprs;
    	}

        @Override
        public void accept(Visitor v) {
            v.visitPrint(this);
        }

        @Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("print");
    		pw.incIndent();
    		for (Expr e : exprs) {
    			e.printTo(pw);
    		}
    		pw.decIndent();
        }
    }

    /**
      * A return statement.
      */
    public static class Return extends Tree {

    	public Expr expr;

        public Return(Expr expr, Location loc) {
            super(RETURN, loc);
            this.expr = expr;
        }

        @Override
        public void accept(Visitor v) {
            v.visitReturn(this);
        }

        @Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("return");
    		if (expr != null) {
    			pw.incIndent();
    			expr.printTo(pw);
    			pw.decIndent();
    		}
    	}
    }

    public abstract static class Expr extends Tree {

    	public Type type;
		public Temp val;
    	public boolean isClass;
    	public boolean usedForRef;
    	
    	public Expr(int tag, Location loc) {
    		super(tag, loc);
    	}
    }

    /**
      * A method invocation
      */
    public static class Apply extends Expr {

    	public Expr receiver;
    	public String method;
    	public List<Expr> actuals;
    	public Function symbol;
    	public boolean isArrayLength;

        public Apply(Expr receiver, String method, List<Expr> actuals,
    			Location loc) {
            super(APPLY, loc);
    		this.receiver = receiver;
    		this.method = method;
    		this.actuals = actuals;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitApply(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("call " + method);
    		pw.incIndent();
    		if (receiver != null) {
    			receiver.printTo(pw);
    		} else {
    			pw.println("<empty>");
    		}
    		
    		for (Expr e : actuals) {
    			e.printTo(pw);
    		}
    		pw.decIndent();
    	}
    }

    /**
      * A new(...) operation.
      */
    public static class NewClass extends Expr {

    	public String className;
    	public Class symbol;

        public NewClass(String className, Location loc) {
            super(NEWCLASS, loc);
    		this.className = className;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitNewClass(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("newobj " + className);
    	}
    }

    /**
      * A new[...] operation.
      */
    public static class NewArray extends Expr {

    	public TypeLiteral elementType;
    	public Expr length;

        public NewArray(TypeLiteral elementType, Expr length, Location loc) {
            super(NEWARRAY, loc);
    		this.elementType = elementType;
    		this.length = length;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitNewArray(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.print("newarray ");
    		elementType.printTo(pw);
    		pw.println();
    		pw.incIndent();
    		length.printTo(pw);
    		pw.decIndent();
    	}
    }

    public abstract static class LValue extends Expr {

    	public enum Kind {
    		LOCAL_VAR, PARAM_VAR, MEMBER_VAR, ARRAY_ELEMENT
    	}
    	public Kind lvKind;
    	
    	LValue(int tag, Location loc) {
    		super(tag, loc);
    	}
    }

    /**
      * A assignment with "=".
      */
    public static class Assign extends Tree {

    	public LValue left;
    	public Expr expr;

        public Assign(LValue left, Expr expr, Location loc) {
            super(ASSIGN, loc);
    		this.left = left;
    		this.expr = expr;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitAssign(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("assign");
    		pw.incIndent();
    		left.printTo(pw);
    		expr.printTo(pw);
    		pw.decIndent();
    	}
    }

    /**
      * A unary operation.
      */
    public static class Unary extends Expr {

    	public Expr expr;

        public Unary(int kind, Expr expr, Location loc) {
            super(kind, loc);
    		this.expr = expr;
        }

    	private void unaryOperatorToString(IndentPrintWriter pw, String op) {
    		pw.println(op);
    		pw.incIndent();
    		expr.printTo(pw);
    		pw.decIndent();
    	}

    	@Override
        public void accept(Visitor v) {
            v.visitUnary(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		switch (tag) {
    		case NEG:
    			unaryOperatorToString(pw, "neg");
    			break;
    		case NOT:
    			unaryOperatorToString(pw, "not");
    			break;
			}
    	}
   }

    /**
      * A binary operation.
      */
    public static class Binary extends Expr {

    	public Expr left;
    	public Expr right;

        public Binary(int kind, Expr left, Expr right, Location loc) {
            super(kind, loc);
    		this.left = left;
    		this.right = right;
        }

    	private void binaryOperatorPrintTo(IndentPrintWriter pw, String op) {
    		pw.println(op);
    		pw.incIndent();
    		left.printTo(pw);
    		right.printTo(pw);
    		pw.decIndent();
    	}

    	@Override
    	public void accept(Visitor visitor) {
    		visitor.visitBinary(this);
    	}

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		switch (tag) {
    		case PLUS:
    			binaryOperatorPrintTo(pw, "add");
    			break;
    		case MINUS:
    			binaryOperatorPrintTo(pw, "sub");
    			break;
    		case MUL:
    			binaryOperatorPrintTo(pw, "mul");
    			break;
    		case DIV:
    			binaryOperatorPrintTo(pw, "div");
    			break;
    		case MOD:
    			binaryOperatorPrintTo(pw, "mod");
    			break;
    		case AND:
    			binaryOperatorPrintTo(pw, "and");
    			break;
    		case OR:
    			binaryOperatorPrintTo(pw, "or");
    			break;
    		case EQ:
    			binaryOperatorPrintTo(pw, "equ");
    			break;
    		case NE:
    			binaryOperatorPrintTo(pw, "neq");
    			break;
    		case LT:
    			binaryOperatorPrintTo(pw, "les");
    			break;
    		case LE:
    			binaryOperatorPrintTo(pw, "leq");
    			break;
    		case GT:
    			binaryOperatorPrintTo(pw, "gtr");
    			break;
    		case GE:
    			binaryOperatorPrintTo(pw, "geq");
    			break;
    		}
    	}
    }

    public static class CallExpr extends Expr {

    	public Expr receiver;

    	public String method;

    	public List<Expr> actuals;

    	public Function symbol;

    	public boolean isArrayLength;

    	public CallExpr(Expr receiver, String method, List<Expr> actuals,
    			Location loc) {
    		super(CALLEXPR, loc);
    		this.receiver = receiver;
    		this.method = method;
    		this.actuals = actuals;
    	}

    	@Override
    	public void accept(Visitor visitor) {
    		visitor.visitCallExpr(this);
    	}

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("call " + method);
    		pw.incIndent();
    		if (receiver != null) {
    			receiver.printTo(pw);
    		} else {
    			pw.println("<empty>");
    		}
    		
    		for (Expr e : actuals) {
    			e.printTo(pw);
    		}
    		pw.decIndent();
    	}
    }

    public static class ReadIntExpr extends Expr {

    	public ReadIntExpr(Location loc) {
    		super(READINTEXPR, loc);
    	}

    	@Override
    	public void accept(Visitor visitor) {
    		visitor.visitReadIntExpr(this);
    	}

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("readint");
    	}
   }

    public static class ReadLineExpr extends Expr {

    	public ReadLineExpr(Location loc) {
    		super(READLINEEXPR, loc);
    	}

    	@Override
    	public void accept(Visitor visitor) {
    		visitor.visitReadLineExpr(this);
    	}

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("readline");
    	}
   }

    public static class ThisExpr extends Expr {

    	public ThisExpr(Location loc) {
    		super(THISEXPR, loc);
    	}

    	@Override
    	public void accept(Visitor visitor) {
    		visitor.visitThisExpr(this);
    	}

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("this");
    	}
   }

    /**
      * A type cast.
      */
    public static class TypeCast extends Expr {

    	public String className;
    	public Expr expr;
    	public Class symbol;

        public TypeCast(String className, Expr expr, Location loc) {
            super(TYPECAST, loc);
    		this.className = className;
    		this.expr = expr;
       }

    	@Override
        public void accept(Visitor v) {
            v.visitTypeCast(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("classcast");
    		pw.incIndent();
    		pw.println(className);
    		expr.printTo(pw);
    		pw.decIndent();
    	}
    }

    /////////////////////////////////////////////////////////////////////////////////////////////////////////
//    /**
//      * instanceof expression
//      */
//    public static class TypeTest extends Expr {
//    	
//    	public Expr instance;
//    	public String className;
//    	public Class symbol;
//
//        public TypeTest(Expr instance, String className, Location loc) {
//            super(TYPETEST, loc);
//    		this.instance = instance;
//    		this.className = className;
//        }
//
//    	@Override
//        public void accept(Visitor v) {
//            v.visitTypeTest(this);
//        }
//
//    	@Override
//    	public void printTo(IndentPrintWriter pw) {
//    		pw.println("instanceof");
//    		pw.incIndent();
//    		instance.printTo(pw);
//    		pw.println(className);
//    		pw.decIndent();
//    	}
//    }
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////
    /**
      * An array selection
      */
    public static class Indexed extends LValue {

    	public Expr array;
    	public Expr index;

        public Indexed(Expr array, Expr index, Location loc) {
            super(INDEXED, loc);
    		this.array = array;
    		this.index = index;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitIndexed(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("arrref");
    		pw.incIndent();
    		array.printTo(pw);
    		index.printTo(pw);
    		pw.decIndent();
    	}
    }

    /**
      * An identifier
      */
    public static class Ident extends LValue {

    	public Expr owner;
    	public String name;
    	public Variable symbol;
    	public boolean isDefined;

        public Ident(Expr owner, String name, Location loc) {
            super(IDENT, loc);
    		this.owner = owner;
    		this.name = name;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitIdent(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.println("varref " + name);
    		if (owner != null) {
    			pw.incIndent();
    			owner.printTo(pw);
    			pw.decIndent();
    		}
    	}
    }

    /**
      * A constant value given literally.
      * @param value value representation
      */
    public static class Literal extends Expr {

    	public int typeTag;
        public Object value;

        public Literal(int typeTag, Object value, Location loc) {
            super(LITERAL, loc);
            this.typeTag = typeTag;
            this.value = value;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitLiteral(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		switch (typeTag) {
    		case INT:
    			pw.println("intconst " + value);
    			break;
    		case DOUBLE:
    			pw.println("doubleconst " + value);
    			break;
    		case BOOL:
    			pw.println("boolconst " + value);
    			break;
    		default:
    			pw.println("stringconst " + MiscUtils.quote((String)value));
    		}
    	}
    }
    public static class Null extends Expr {

        public Null(Location loc) {
            super(NULL, loc);
        }

    	@Override
        public void accept(Visitor v) {
            v.visitNull(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
  			pw.println("null");
    	}
    }

    public static abstract class TypeLiteral extends Tree {
    	
    	public Type type;
    	
    	public TypeLiteral(int tag, Location loc){
    		super(tag, loc);
    	}
    }
    
    /**
      * Identifies a basic type.
      * @param tag the basic type id
      * @see SemanticConstants
      */
    public static class TypeIdent extends TypeLiteral {
    	
        public int typeTag;

        public TypeIdent(int typeTag, Location loc) {
            super(TYPEIDENT, loc);
            this.typeTag = typeTag;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitTypeIdent(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		switch (typeTag){
    		case INT:
    			pw.print("inttype");
    			break;
    		case BOOL:
    			pw.print("booltype");
    			break;
    		case VOID:
    			pw.print("voidtype");
    			break;
    		case DOUBLE:
    			pw.print("doubletype");
    			break;
    		default:
    			pw.print("stringtype");
    		}
    	}
    }

    public static class TypeClass extends TypeLiteral {

    	public String name;

    	public TypeClass(String name, Location loc) {
    		super(TYPECLASS, loc);
    		this.name = name;
    	}

    	@Override
    	public void accept(Visitor visitor) {
    		visitor.visitTypeClass(this);
    	}

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.print("classtype " + name);
    	}
    }

    /**
      * An array type, A[]
      */
    public static class TypeArray extends TypeLiteral {

    	public TypeLiteral elementType;

        public TypeArray(TypeLiteral elementType, Location loc) {
            super(TYPEARRAY, loc);
    		this.elementType = elementType;
        }

    	@Override
        public void accept(Visitor v) {
            v.visitTypeArray(this);
        }

    	@Override
    	public void printTo(IndentPrintWriter pw) {
    		pw.print("arrtype ");
    		elementType.printTo(pw);
    	}
    }

    /**
      * A generic visitor class for trees.
      */
    public static abstract class Visitor {

        public Visitor() {
            super();
        }

        public void visitTopLevel(TopLevel that) {
            visitTree(that);
        }

        public void visitClassDef(ClassDef that) {
            visitTree(that);
        }

        public void visitMethodDef(MethodDef that) {
            visitTree(that);
        }

        public void visitVarDef(VarDef that) {
            visitTree(that);
        }

        public void visitSkip(Skip that) {
            visitTree(that);
        }

        public void visitBlock(Block that) {
            visitTree(that);
        }

        public void visitWhileLoop(WhileLoop that) {
            visitTree(that);
        }
        
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        public void visitRepeatLoop(RepeatLoop that)
		{
			visitTree(that);
		}
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        

        public void visitForLoop(ForLoop that) {
            visitTree(that);
        }

        public void visitIf(If that) {
            visitTree(that);
        }

        public void visitExec(Exec that) {
            visitTree(that);
        }

        public void visitBreak(Break that) {
            visitTree(that);
        }

        public void visitReturn(Return that) {
            visitTree(that);
        }

        public void visitApply(Apply that) {
            visitTree(that);
        }

        public void visitNewClass(NewClass that) {
            visitTree(that);
        }

        public void visitNewArray(NewArray that) {
            visitTree(that);
        }

        public void visitAssign(Assign that) {
            visitTree(that);
        }

        public void visitUnary(Unary that) {
            visitTree(that);
        }

        public void visitBinary(Binary that) {
            visitTree(that);
        }

        public void visitCallExpr(CallExpr that) {
            visitTree(that);
        }

        public void visitReadIntExpr(ReadIntExpr that) {
            visitTree(that);
        }

        public void visitReadLineExpr(ReadLineExpr that) {
            visitTree(that);
        }

        public void visitPrint(Print that) {
            visitTree(that);
        }

        public void visitThisExpr(ThisExpr that) {
            visitTree(that);
        }

        public void visitLValue(LValue that) {
            visitTree(that);
        }

        public void visitTypeCast(TypeCast that) {
            visitTree(that);
        }

        ///////////////////////////////////////////////////////////////////////////////////////////////////////////
//        public void visitTypeTest(TypeTest that) {
//            visitTree(that);
//        }
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////

        public void visitIndexed(Indexed that) {
            visitTree(that);
        }

        public void visitIdent(Ident that) {
            visitTree(that);
        }

        public void visitLiteral(Literal that) {
            visitTree(that);
        }

        public void visitNull(Null that) {
            visitTree(that);
        }

        public void visitTypeIdent(TypeIdent that) {
            visitTree(that);
        }

        public void visitTypeClass(TypeClass that) {
            visitTree(that);
        }

        public void visitTypeArray(TypeArray that) {
            visitTree(that);
        }

        public void visitTree(Tree that) {
            assert false;
        }
    }
} public final class Intrinsic {
	/**
	 * 分配内存，如果失败则自动退出程序<br>
	 * 参数: 为要分配的内存块大小（单位为字节）<br>
	 * 返回: 该内存块的首地址<br>
	 * 返回类型: 指针，需要用VarDecl的changeTypeTo()函数更改类型
	 */
	public static final Intrinsic ALLOCATE = new Intrinsic("_Alloc", 1,
			BaseType.INT);
	/**
	 * 读取一行字符串（最大63个字符）<br>
	 * 返回: 读到的字符串首地址<br>
	 * 返回类型: string
	 */
	public static final Intrinsic READ_LINE = new Intrinsic("_ReadLine", 0,
			BaseType.STRING);
	/**
	 * 读取一个整数<br>
	 * 返回: 读到的整数<br>
	 * 返回类型: int
	 */
	public static final Intrinsic READ_INT = new Intrinsic("_ReadInteger", 0,
			BaseType.INT);
	/**
	 * 比较两个字符串<br>
	 * 参数: 要比较的两个字符串的首地址<br>
	 * 返回: 若相等则返回true，否则返回false<br>
	 * 返回类型: bool
	 */
	public static final Intrinsic STRING_EQUAL = new Intrinsic("_StringEqual",
			2, BaseType.BOOL);
	/**
	 * 打印一个整数<br>
	 * 参数: 要打印的数字
	 */
	public static final Intrinsic PRINT_INT = new Intrinsic("_PrintInt", 1,
			BaseType.VOID);
	/**
	 * 打印一个字符串<br>
	 * 参数: 要打印的字符串
	 */
	public static final Intrinsic PRINT_STRING = new Intrinsic("_PrintString",
			1, BaseType.VOID);
	/**
	 * 打印一个布尔值<br>
	 * 参数: 要打印的布尔变量
	 */
	public static final Intrinsic PRINT_BOOL = new Intrinsic("_PrintBool", 1,
			BaseType.VOID);
	/**
	 * 结束程序<br>
	 * 可以作为子程序调用，也可以直接Goto
	 */
	public static final Intrinsic HALT = new Intrinsic("_Halt", 0,
			BaseType.VOID);
	/**
	 * 函数名字
	 */
	public final Label label;
	/**
	 * 函数的参数个数
	 */
	public final int numArgs;
	/**
	 * 函数返回值类型
	 */
	public final BaseType type;

	/**
	 * 构造一个预定义函数的信息
	 * 
	 * @param name
	 *            函数名字
	 * @param argc
	 *            参数个数
	 * @param type
	 *            返回类型
	 */
	private Intrinsic(String name, int numArgs, BaseType type) {
		this.label = Label.createLabel(name, false);
		this.numArgs = numArgs;
		this.type = type;
	}

} public class Class extends Symbol {

	private String parentName;

	private ClassScope associatedScope;

	private int order;

	private boolean check;

	private int numNonStaticFunc;

	private int numVar;

	private int size;

	public int getSize() {
		return size;
	}

	public void setSize(int size) {
		this.size = size;
	}

	public int getNumNonStaticFunc() {
		return numNonStaticFunc;
	}

	public void setNumNonStaticFunc(int numNonStaticFunc) {
		this.numNonStaticFunc = numNonStaticFunc;
	}

	public int getNumVar() {
		return numVar;
	}

	public void setNumVar(int numVar) {
		this.numVar = numVar;
	}

	public Class(String name, String parentName, Location location) {
		this.name = name;
		this.parentName = parentName;
		this.location = location;
		this.order = -1;
		this.check = false;
		this.numNonStaticFunc = -1;
		this.numVar = -1;
		this.associatedScope = new ClassScope(this);
	}

	public void createType() {
		Class p = getParent();
		if (p == null) {
			type = new ClassType(this, null);
		} else {
			if (p.getType() == null) {
				p.createType();
			}
			type = new ClassType(this, (ClassType) p.getType());
		}
	}

	@Override
	public ClassType getType() {
		if (type == null) {
			createType();
		}
		return (ClassType) type;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder(location + " -> class " + name);
		if (parentName != null) {
			sb.append(" : " + parentName);
		}
		return sb.toString();
	}

	public ClassScope getAssociatedScope() {
		return associatedScope;
	}

	public Class getParent() {
		return Driver.getDriver().getTable().lookupClass(parentName);
	}

	@Override
	public boolean isClass() {
		return true;
	}

	@Override
	public GlobalScope getScope() {
		return (GlobalScope) definedIn;
	}

	public int getOrder() {
		return order;
	}

	public void setOrder(int order) {
		this.order = order;
	}

	public void dettachParent() {
		parentName = null;
	}

	public boolean isCheck() {
		return check;
	}

	public void setCheck(boolean check) {
		this.check = check;
	}

	@Override
	public boolean isFunction() {
		return false;
	}

	@Override
	public boolean isVariable() {
		return false;
	}
} public class Function extends Symbol {

	private FormalScope associatedScope;

	private boolean statik;

	private boolean isMain;

	public boolean isMain() {
		return isMain;
	}

	public void setMain(boolean isMain) {
		this.isMain = isMain;
	}

	public boolean isStatik() {
		return statik;
	}

	public void setStatik(boolean statik) {
		this.statik = statik;
	}

	private int offset;

	public int getOffset() {
		return offset;
	}

	public void setOffset(int offset) {
		this.offset = offset;
	}

	public Function(boolean statik, String name, Type returnType,
			Block node, Location location) {
		this.name = name;
		this.location = location;

		type = new FuncType(returnType);
		associatedScope = new FormalScope(this, node);
		ClassScope cs = (ClassScope) Driver.getDriver().getTable()
				.lookForScope(Scope.Kind.CLASS);
		this.statik = statik;
		if (!statik) {
			Variable _this = new Variable("this", cs.getOwner().getType(),
					location);
			associatedScope.declare(_this);
			appendParam(_this);
		}

	}

	public FormalScope getAssociatedScope() {
		return associatedScope;
	}

	public Type getReturnType() {
		return getType().getReturnType();
	}

	public void appendParam(Variable arg) {
		arg.setOrder(getType().numOfParams());
		getType().appendParam(arg.getType());
	}

	@Override
	public ClassScope getScope() {
		return (ClassScope) definedIn;
	}

	@Override
	public FuncType getType() {
		return (FuncType) type;
	}

	@Override
	public boolean isFunction() {
		return true;
	}

	@Override
	public String toString() {
		return location + " -> " + (statik ? "static " : "") + "function "
				+ name + " : " + type;
	}

	@Override
	public boolean isClass() {
		return false;
	}

	@Override
	public boolean isVariable() {
		return false;
	}

} public abstract class Symbol {
	protected String name;

	protected Scope definedIn;

	protected Type type;

	protected int order;

	protected Location location;

	public static final Comparator<Symbol> LOCATION_COMPARATOR = new Comparator<Symbol>() {

		@Override
		public int compare(Symbol o1, Symbol o2) {
			return o1.location.compareTo(o2.location);
		}

	};

	public static final Comparator<Symbol> ORDER_COMPARATOR = new Comparator<Symbol>() {

		@Override
		public int compare(Symbol o1, Symbol o2) {
			return o1.order > o2.order ? 1 : o1.order == o2.order ? 0 : -1;
		}

	};

	public Scope getScope() {
		return definedIn;
	}

	public void setScope(Scope definedIn) {
		this.definedIn = definedIn;
	}

	public int getOrder() {
		return order;
	}

	public void setOrder(int order) {
		this.order = order;
	}

	public Location getLocation() {
		return location;
	}

	public void setLocation(Location location) {
		this.location = location;
	}

	public Type getType() {
		return type;
	}

	public String getName() {
		return name;
	}

	public abstract boolean isVariable();

	public abstract boolean isClass();

	public abstract boolean isFunction();

	public abstract String toString();
} public class Variable extends Symbol {
	
	private int offset;

	public int getOffset() {
		return offset;
	}

	public void setOffset(int offset) {
		this.offset = offset;
	}

	public Variable(String name, Type type, Location location) {
		this.name = name;
		this.type = type;
		this.location = location;
	}

	public boolean isLocalVar() {
		return definedIn.isLocalScope();
	}

	public boolean isMemberVar() {
		return definedIn.isClassScope();
	}

	@Override
	public boolean isVariable() {
		return true;
	}

	@Override
	public String toString() {
		return location + " -> variable " + (isParam() ? "@" : "") + name
				+ " : " + type;
	}

	public boolean isParam() {
		return definedIn.isFormalScope();
	}

	@Override
	public boolean isClass() {
		return false;
	}

	@Override
	public boolean isFunction() {
		return false;
	}

} public class Label {
	public int id;

	public String name;

	public boolean target;

	public Tac where;

	private static int labelCount = 0;

	public Label() {
	}

	public Label(int id, String name, boolean target) {
		this.id = id;
		this.name = name;
		this.target = target;
	}

	public static Label createLabel() {
		return createLabel(false);
	}

	public static Label createLabel(boolean target) {
		int id = labelCount++;
		return new Label(id, "_L" + id, target);
	}

	public static Label createLabel(String name, boolean target) {
		int id = labelCount++;
		return new Label(id, name, target);
	}

	@Override
	public String toString() {
		return name;
	}

} public class Tac {
	public enum Kind {
		ADD, SUB, MUL, DIV, MOD, NEG, LAND, LOR, LNOT, GTR, GEQ, EQU, NEQ, LEQ,
		LES, ASSIGN, LOAD_VTBL, INDIRECT_CALL, DIRECT_CALL, RETURN, BRANCH,
		BEQZ, BNEZ, LOAD, STORE, LOAD_IMM4, LOAD_STR_CONST, MEMO, MARK, PARM
	}

	public Kind opc;

	public boolean mark;

	public Tac prev;

	public Tac next;

	public Temp op0;

	public Temp op1;

	public Temp op2;

	public Label label;

	public VTable vt;

	public String str;

	public int bbNum;

	public Set<Temp> liveOut;
	
	public Set<Temp> saves;

	private Tac(Kind opc, Temp op0) {
		this(opc, op0, null, null);
	}

	private Tac(Kind opc, Temp op0, Temp op1) {
		this(opc, op0, op1, null);
	}

	private Tac(Kind opc, Temp op0, Temp op1, Temp op2) {
		this.opc = opc;
		this.op0 = op0;
		this.op1 = op1;
		this.op2 = op2;
	}

	private Tac(Kind opc, String str) {
		this.opc = opc;
		this.str = str;
	}

	private Tac(Kind opc, Temp op0, String str) {
		this.opc = opc;
		this.op0 = op0;
		this.str = str;
	}

	private Tac(Kind opc, Temp op0, VTable vt) {
		this.opc = opc;
		this.op0 = op0;
		this.vt = vt;
	}

	private Tac(Kind opc, Label label) {
		this.opc = opc;
		this.label = label;
	}

	private Tac(Kind opc, Temp op0, Label label) {
		this.opc = opc;
		this.op0 = op0;
		this.label = label;
	}

	public static Tac genAdd(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.ADD, dst, src1, src2);
	}

	public static Tac genSub(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.SUB, dst, src1, src2);
	}

	public static Tac genMul(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.MUL, dst, src1, src2);
	}

	public static Tac genDiv(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.DIV, dst, src1, src2);
	}

	public static Tac genMod(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.MOD, dst, src1, src2);
	}

	public static Tac genNeg(Temp dst, Temp src) {
		return new Tac(Kind.NEG, dst, src);
	}

	public static Tac genLAnd(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.LAND, dst, src1, src2);
	}

	public static Tac genLOr(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.LOR, dst, src1, src2);
	}

	public static Tac genLNot(Temp dst, Temp src) {
		return new Tac(Kind.LNOT, dst, src);
	}

	public static Tac genGtr(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.GTR, dst, src1, src2);
	}

	public static Tac genGeq(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.GEQ, dst, src1, src2);
	}

	public static Tac genEqu(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.EQU, dst, src1, src2);
	}

	public static Tac genNeq(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.NEQ, dst, src1, src2);
	}

	public static Tac genLeq(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.LEQ, dst, src1, src2);
	}

	public static Tac genLes(Temp dst, Temp src1, Temp src2) {
		return new Tac(Kind.LES, dst, src1, src2);
	}

	public static Tac genAssign(Temp dst, Temp src) {
		return new Tac(Kind.ASSIGN, dst, src);
	}

	public static Tac genLoadVtbl(Temp dst, VTable vt) {
		return new Tac(Kind.LOAD_VTBL, dst, vt);
	}

	public static Tac genIndirectCall(Temp dst, Temp func) {
		return new Tac(Kind.INDIRECT_CALL, dst, func);
	}

	public static Tac genDirectCall(Temp dst, Label func) {
		return new Tac(Kind.DIRECT_CALL, dst, func);
	}

	public static Tac genReturn(Temp src) {
		return new Tac(Kind.RETURN, src);
	}

	public static Tac genBranch(Label label) {
		label.target = true;
		return new Tac(Kind.BRANCH, label);
	}

	public static Tac genBeqz(Temp cond, Label label) {
		label.target = true;
		return new Tac(Kind.BEQZ, cond, label);
	}
	
	public static Tac genBnez(Temp cond, Label label) {
		label.target = true;
		return new Tac(Kind.BNEZ, cond, label);
	}

	public static Tac genLoad(Temp dst, Temp base, Temp offset) {
		if (!offset.isConst) {
			throw new IllegalArgumentException("offset must be const temp");
		}
		return new Tac(Kind.LOAD, dst, base, offset);
	}

	public static Tac genStore(Temp src, Temp base, Temp offset) {
		if (!offset.isConst) {
			throw new IllegalArgumentException("offset must be const temp");
		}
		return new Tac(Kind.STORE, src, base, offset);
	}

	public static Tac genLoadImm4(Temp dst, Temp val) {
		if (!val.isConst) {
			throw new IllegalArgumentException("val must be const temp");
		}
		return new Tac(Kind.LOAD_IMM4, dst, val);
	}

	public static Tac genLoadStrConst(Temp dst, String str) {
		return new Tac(Kind.LOAD_STR_CONST, dst, str);
	}

	public static Tac genMemo(String memo) {
		return new Tac(Kind.MEMO, memo);
	}

	public static Tac genMark(Label label) {
		Tac mark = new Tac(Kind.MARK, label);
		label.where = mark;
		return mark;
	}

	public static Tac genParm(Temp src) {
		return new Tac(Kind.PARM, src);
	}

	private String binanyOpToString(String op) {
		return op0.name + " = (" + op1.name + " " + op + " " + op2.name + ")";
	}

	private String unaryOpToString(String op) {
		return op0.name + " = " + op + " " + op1.name;
	}

	public String toString() {
		switch (opc) {
		case ADD:
			return binanyOpToString("+");
		case SUB:
			return binanyOpToString("-");
		case MUL:
			return binanyOpToString("*");
		case DIV:
			return binanyOpToString("/");
		case MOD:
			return binanyOpToString("%");
		case NEG:
			return unaryOpToString("-");
		case LAND:
			return binanyOpToString("&&");
		case LOR:
			return binanyOpToString("||");
		case LNOT:
			return unaryOpToString("!");
		case GTR:
			return binanyOpToString(">");
		case GEQ:
			return binanyOpToString(">=");
		case EQU:
			return binanyOpToString("==");
		case NEQ:
			return binanyOpToString("!=");
		case LEQ:
			return binanyOpToString("<=");
		case LES:
			return binanyOpToString("<");
		case ASSIGN:
			return op0.name + " = " + op1.name;
		case LOAD_VTBL:
			return op0.name + " = VTBL <" + vt.name + ">";
		case INDIRECT_CALL:
			if (op0 != null) {
				return op0.name + " = " + " call " + op1.name;
			} else {
				return "call " + op1.name;
			}
		case DIRECT_CALL:
			if (op0 != null) {
				return op0.name + " = " + " call " + label.name;
			} else {
				return "call " + label.name;
			}
		case RETURN:
			if (op0 != null) {
				return "return " + op0.name;
			} else {
				return "return <empty>";
			}
		case BRANCH:
			return "branch " + label.name;
		case BEQZ:
			return "if (" + op0.name + " == 0) branch " + label.name;
		case BNEZ:
			return "if (" + op0.name + " != 0) branch " + label.name;
		case LOAD:
			if (op2.value >= 0) {
				return op0.name + " = *(" + op1.name + " + " + op2.value + ")";
			} else {
				return op0.name + " = *(" + op1.name + " - " + (-op2.value)
						+ ")";
			}
		case STORE:
			if (op2.value >= 0) {
				return "*(" + op1.name + " + " + op2.value + ") = " + op0.name;
			} else {
				return "*(" + op1.name + " - " + (-op2.value) + ") = "
						+ op0.name;
			}
		case LOAD_IMM4:
			return op0.name + " = " + op1.value;
		case LOAD_STR_CONST:
			return op0.name + " = " + MiscUtils.quote(str);
		case MEMO:
			return "memo '" + str + "'";
		case MARK:
			return label.name + ":";
		case PARM:
			return "parm " + op0.name;
		default:
			throw new RuntimeException("unknown opc");
		}
	}
} public class Temp {
	public int id;

	public String name;

	public int offset = Integer.MAX_VALUE;

	public int size;

	public Variable sym;

	public boolean isConst;

	public int value;

	public boolean isParam;

	public boolean isLoaded;

	public Register reg;

	private static int tempCount = 0;

	public static final Comparator<Temp> ID_COMPARATOR = new Comparator<Temp>() {

		@Override
		public int compare(Temp o1, Temp o2) {
			return o1.id > o2.id ? 1 : o1.id == o2.id ? 0 : -1;
		}

	};

	public Temp() {
	}

	public Temp(int id, String name, int size, int offset) {
		this.id = id;
		this.name = name;
		this.size = size;
		this.offset = offset;
	}

	public static Temp createTempI4() {
		int id = tempCount++;
		return new Temp(id, "_T" + id, 4, Integer.MAX_VALUE);
	}

	private static Map<Integer, Temp> constTempPool = new HashMap<Integer, Temp>();

	public static Temp createConstTemp(int value) {
		Temp temp = constTempPool.get(value);
		if (temp == null) {
			temp = new Temp();
			temp.isConst = true;
			temp.value = value;
			temp.name = Integer.toString(value);
			constTempPool.put(value, temp);
		}
		return temp;
	}

	public boolean isOffsetFixed() {
		return offset != Integer.MAX_VALUE;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj instanceof Temp) {
			return id == ((Temp) obj).id;
		}
		return false;
	}

	@Override
	public int hashCode() {
		return id;
	}

	@Override
	public String toString() {
		return name;
	}

} public class VTable {
	public String name;
	
	////////////////////////////////////////////////////////////////////////////////////////
//	public VTable parent;
//	
	public String className;
	////////////////////////////////////////////////////////////////////////////////////////
	public Label[] entries;
} public class BaseType extends Type {

	private final String typeName;

	private BaseType(String typeName) {
		this.typeName = typeName;
	}

	public static final BaseType INT = new BaseType("int");
	
	public static final BaseType BOOL = new BaseType("bool");

	public static final BaseType NULL = new BaseType("null");

	public static final BaseType ERROR = new BaseType("Error");
	
	public static final BaseType STRING = new BaseType("string");
	
	public static final BaseType VOID = new BaseType("void");
	
	////////////////////////////////////////////////////////////////////////////////////////
	public static final BaseType DOUBLE = new BaseType("double");
	////////////////////////////////////////////////////////////////////////////////////////

	@Override
	public boolean isBaseType() {
		return true;
	}

	@Override
	public boolean compatible(Type type) {
		if (equal(ERROR) || type.equal(ERROR)) {
			return true;
		}
		if (equal(NULL) && type.isClassType()) {
			return true;
		}
		return equal(type);
	}

	@Override
	public boolean equal(Type type) {
		return this == type;
	}

	@Override
	public String toString() {
		return typeName;
	}

}
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import decaf.tree.Tree;
import decaf.backend.OffsetCounter;
import decaf.error.RuntimeError;
import decaf.machdesc.Intrinsic;
import decaf.scope.ClassScope;
import decaf.symbol.Class;
import decaf.symbol.Function;
import decaf.symbol.Symbol;
import decaf.symbol.Variable;
import decaf.tac.Functy;
import decaf.tac.Label;
import decaf.tac.Tac;
import decaf.tac.Temp;
import decaf.tac.VTable;
import decaf.type.BaseType;
import decaf.type.Type;
package decaf.translate;



public class Translater {
	private List<VTable> vtables;

	private List<Functy> funcs;

	private Functy currentFuncty;

	public Translater() {
		vtables = new ArrayList<VTable>();
		funcs = new ArrayList<Functy>();
	}

	public static Translater translate(Tree.TopLevel tree) {
		Translater tr = new Translater();
		TransPass1 tp1 = new TransPass1(tr);
		tp1.visitTopLevel(tree);
		TransPass2 tp2 = new TransPass2(tr);
		tp2.visitTopLevel(tree);
		return tr;
	}

	public void printTo(PrintWriter pw) {
		for (VTable vt : vtables) {
			pw.println("VTABLE(" + vt.name + ") {");
			if (vt.parent != null) {
				pw.println("    " + vt.parent.name);
			} else {
				pw.println("    <empty>");
			}
			pw.println("    " + vt.className);
			for (Label l : vt.entries) {
				pw.println("    " + l.name + ";");
			}
			pw.println("}");
			pw.println();
		}
		for (Functy ft : funcs) {
			pw.println("FUNCTION(" + ft.label.name + ") {");
			pw.println(ft.paramMemo);
			Tac tac = ft.head;
			while (tac != null) {
				if (tac.opc == Tac.Kind.MARK) {
					pw.println(tac);
				} else {
					pw.println("    " + tac);
				}
				tac = tac.next;
			}
			pw.println("}");
			pw.println();
		}
	}

	public List<VTable> getVtables() {
		return vtables;
	}

	public List<Functy> getFuncs() {
		return funcs;
	}

	public void createFuncty(Function func) {