/**
 * A visitor class for the syntax checker. Returns null unless there is a syntax error.
 * On a syntax error, throws a SyntaxException.
 */
class CheckVisitor implements ASTVisitor<Void> {
    /**
     * Empty symbol table.
     */
    private static final Empty<Variable> emptyVars = new Empty<Variable>();

    /**
     * Symbol table to detect free variables.
     */
    PureList<Variable> env;

    /**
     * Visitor in initial state with empty symbol table.
     */
    public static final CheckVisitor INITIAL = new CheckVisitor(emptyVars);

    /**
     * Constructor for te check visitor.
     * @param e symbol table
     */
    CheckVisitor(PureList<Variable> e) {
        env = e;
    }

    /**
     * Case for IntConstants.
     * @param i host
     * @return always null
     */
    public Void forIntConstant(IntConstant i) {
        return null;
    }

    /**
     * Case for BoolConstants.
     * @param b host
     * @return always null
     */
    public Void forBoolConstant(BoolConstant b) {
        return null;
    }

    /**
     * Case for NullConstants.
     * @param n host
     * @return always null
     */
    public Void forNullConstant(NullConstant n) {
        return null;
    }

    /**
     * Case for Variables.
     * @param v host
     * @return null if variable in symbol table
     */
    public Void forVariable(Variable v) {
        Variable match = env.accept(new LookupVisitor<Variable>(v));
        if (match == null) {
            throw new SyntaxException("variable " + v + " is unbound");
        }
        return null;
    }

    /**
     * Case for PrimFuns.
     * @param f host
     * @return visitor-specific return value
     */
    public Void forPrimFun(PrimFun f) {
        return null;
    }

    /**
     * Case for UnOpApps.
     * @param u host
     * @return null if operand is ok
     */
    public Void forUnOpApp(UnOpApp u) {
        u.arg().accept(this);  // throws an exception on error
        return null;
    }

    /**
     * Case for BinOpApps.
     * @param b host
     * @return null if both operands are ok
     */
    public Void forBinOpApp(BinOpApp b) {
        b.arg1().accept(this); // throws an exception on error
        b.arg2().accept(this); // throws an exception on error
        return null;
    }

    /**
     * Case for Apps.
     * @param a host
     * @return null if rator and arguments are ok
     */
    public Void forApp(App a) {
        a.rator().accept(this); // throws an exception on error
        AST[] args = a.args();
        int n = args.length;
        for(int i = 0; i < n; i++) {
            args[i].accept(this); // throws an exception on error
        }
        return null;
    }

    /**
     * Case for Maps.
     * @param m host
     * @return null if no duplicate variables and body is ok
     */
    public Void forMap(Map m) {
        // Check for duplicates in Map vars & construct newEnv for Map body
        Variable[] vars = m.vars();
        PureList<Variable> varList = PureListClass.arrayToList(vars);
        // System.err.println("variable list is: " + varList);
        varList.accept(AnyDuplicatesVisitor.ONLY);  // throws exception on an error
        int n = vars.length;
        PureList<Variable> newEnv = env;
        for(int i = n - 1; i >= 0; i--) {
            newEnv = newEnv.cons(vars[i]);
        }
        m.body().accept(new CheckVisitor(newEnv));  // throws an exception on an error
        return null;
    }

    /**
     * Case for Ifs.
     * @param i host
     * @return null if all three subexpressions are ok
     */
    public Void forIf(If i) {
        i.test().accept(this);
        i.conseq().accept(this);
        i.alt().accept(this);
        return null;
    }

    /**
     * Case for Lets.
     * @param l host
     * @return null if no duplicates variables and right-hand sides and body are ok
     */
    public Void forLet(Let l) {
        // Check for duplicates in Let vars, check Let rhs's and construct newEnv
        // for let body
        Variable[] vars = l.vars();
        PureList<Variable> varList = PureListClass.arrayToList(vars);
        // System.err.println("variable list is: " + varList);
        varList.accept(AnyDuplicatesVisitor.ONLY);  // throws exception on an error
        AST[] exps = l.exps();
        int n = vars.length;
        PureList<Variable> newEnv = env;
        for(int i = n - 1; i >= 0; i--) {
            newEnv = newEnv.cons(vars[i]);
        }
        CheckVisitor newVisitor = new CheckVisitor(newEnv);
        for(int i = 0; i < n; i++) {
            exps[i].accept(newVisitor);
        }
        // throws an exception on error

        l.body().accept(newVisitor); // throws an exception on error
        return null;
    }

    /*
        public Void forBlock(Block b) {
        // Check each exp
        AST[] exps =  b.exps();
        int n = exps.length;
        for (int i = 0; i < n; i++) exps[i].accept(this);
          // throws an exception on error
        return null;
      } */
}

/**
 * Singleton visitor that checks for duplicate variables in a symbol table.
 * Throws an SyntaxException if it encounters such an error; otherwise returns null.
 */
class AnyDuplicatesVisitor implements PureListVisitor<Variable, Void> {
    /**
     * Singleton instance.
     */
    public static AnyDuplicatesVisitor ONLY = new AnyDuplicatesVisitor();

    /**
     * Singleton constructor.
     */
    private AnyDuplicatesVisitor() {
    }

    /**
     * Case for empty lists.
     * @param e host
     * @return always null
     */
    public Void forEmpty(Empty<Variable> e) {
        return null;
    }

    /**
     * Case for non-empty lists.
     * @param c host
     * @return null if the variable in first doesn't occur in rest
     */
    public Void forCons(Cons<Variable> c) {
        if (c.rest().hasMember(c.first())) {
            throw new
            SyntaxException(c.first() + " is declared twice in the same scope");
        }
        c.rest().accept(this);
        return null;
    }
}

/**
 * Exception thrown by the context-sensitive checker.
 */
class SyntaxException extends RuntimeException {
    /**
     * Constructor for this exception.
     * @param s description
     */
    SyntaxException(String s) {
        super(s);
    }
}