path: root/sources/scalac/checkers/TreeChecker.java

/*     ____ ____  ____ ____  ______                                     *\
**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2002, LAMP/EPFL              **
** /_____/\____/\___/\____/____/                                        **
\*                                                                      */

// $Id$

package scalac.checkers;

import java.util.Iterator;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

import ch.epfl.lamp.util.Position;

import scalac.Unit;
import scalac.ast.Tree;
import scalac.ast.Tree.AbsTypeDef;
import scalac.ast.Tree.Ident;
import scalac.ast.Tree.Template;
import scalac.ast.Tree.ValDef;
import scalac.ast.TreeInfo;
import scalac.symtab.Definitions;
import scalac.symtab.Symbol;
import scalac.symtab.Type;
import scalac.util.Debug;

/**
 * This checker checks that trees are well-formed. It checks both the
 * shape and the attribution of the trees. WARNING: currently, the
 * checks are valid only for trees generated by phase AddConstructors.
 */
public class TreeChecker {

    //########################################################################
    // Private Fields

    /** The global definitions */
    private final Definitions definitions;

    /** The stack of current units */
    private final Stack/*<Unit>*/ units = new Stack();

    /** The stack of current classes */
    private final Stack/*<Symbol>*/ classes = new Stack();

    /** The stack of current members */
    private final Stack/*<Symbol>*/ members = new Stack();

    /** The stack of current owners */
    private final Stack/*<Symbol>*/ owners = new Stack();

    /** The currently visible type variables */
    private final Set/*<Symbol>*/ tvars = new HashSet();

    /** The currently visible value variables */
    private final Set/*<Symbol>*/ vvars = new HashSet();

    /** The currently visible labels */
    private final Set/*<Symbol>*/ labels = new HashSet();

    /** The currently defined symbols */
    private final Set/*<Symbol>*/ symbols = new HashSet();

    //########################################################################
    // Public Constructors

    /** Initializes this instance. */
    public TreeChecker(Definitions definitions) {
        this.definitions = definitions;
    }

    //########################################################################
    // Public Methods - Checking units

    /** Checks the unit. Returns true. */
    public boolean check(Unit unit) {
        pushUnit(unit);
        template(unit.body);
        popUnit();
        return true;
    }

    //########################################################################
    // Private Methods - Checking templates

    /** Checks the templates. Returns true. */
    private boolean template(Tree[] trees) {
        for (int i = 0; i < trees.length; i++) template(trees[i]);
        return true;
    }

    /** Checks the template. Returns true. */
    private boolean template(Tree tree) {
        switch (tree) {

        case Empty:
            return true;

        case ClassDef(_, _, AbsTypeDef[] tparams, ValDef[][] vparams, _, Template(_, Tree[] body)):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isClass(): show(tree);
            assert vparams.length == 1: show(tree);
            containSymbols(tparams, symbol.typeParams());
            containSymbols(vparams[0],symbol.valueParams());
            registerSymbol(symbol);
            scopeInsertParametersOf(symbol);
            pushClass(symbol);
            member(body);
            popClass();
            scopeRemoveParametersOf(symbol);
            return true;

        case PackageDef(Tree packaged, Template(Tree[] bases, Tree[] body)):
            Symbol symbol = packaged.symbol();
            assert symbol != null && symbol.isPackage(): show(packaged);
            assert bases.length == 0: show(tree);
            pushOwner(symbol);
            template(body);
            popOwner();
            return true;

        default:
            throw Debug.abort("illegal case", tree);
        }
    }

    //########################################################################
    // Private Methods - Checking members

    /** Checks the members. Returns true. */
    private boolean member(Tree[] trees) {
        for (int i = 0; i < trees.length; i++) member(trees[i]);
        return true;
    }

    /** Checks the member. Returns true. */
    private boolean member(Tree tree) {
        switch (tree) {

        case Empty:
            return true;

        case ClassDef(_, _, _, _, _, _):
            return template(tree);

        case ValDef(_, _, _, Tree rhs):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isTerm(): show(tree);
            assert rhs == Tree.Empty: show(tree);
            registerSymbol(symbol);
            pushMember(symbol);
            popMember();
            return true;

        case DefDef(_, _, AbsTypeDef[]tparams, ValDef[][]vparams, _, Tree rhs):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isMethod(): show(tree);
            assert vparams.length == 1: show(tree);
            containSymbols(tparams, symbol.typeParams());
            containSymbols(vparams[0],symbol.valueParams());
            assert symbol.isDeferred() == (rhs == Tree.Empty): show(tree);
            registerSymbol(symbol);
            scopeInsertParametersOf(symbol);
            pushMember(symbol);
            if (!symbol.isDeferred()) expression(rhs, symbol.resultType());
            popMember();
            scopeRemoveParametersOf(symbol);
            return true;

        default:
            throw Debug.abort("illegal case", tree);
        }
    }

    //########################################################################
    // Private Methods - Checking statements

    /** Checks the statement. Returns true. */
    private boolean statement(Set locals, Tree tree) {
        switch (tree) {

        case Empty:
            return true;

        case ValDef(_, _, _, Tree rhs):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isTerm(): show(tree);
            scopeInsertVVariable(symbol, false);
            locals.add(symbol);
            pushOwner(symbol);
            expression(rhs, symbol.type());
            popOwner();
            return true;

        default:
            return expression(tree, tree.type());
        }
    }

    //########################################################################
    // Private Methods - Checking expressions

    /** Checks the expression of given expected type. Returns true. */
    private boolean expression(Tree tree, Type expected) {
        // !!! conforms(tree, expected);
        expected = tree.type();
        switch (tree) {

        case LabelDef(_, Ident[] idents, Tree rhs):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isLabel(): show(tree);
            Symbol[] params = symbol.type().valueParams();
            assert params.length == idents.length: show(tree)
                + format("params", Debug.show(params));
            for (int i = 0; i < idents.length; i++) {
                location(idents[i]);
                conforms(idents[i], definitions.ANY_TYPE(), params[i].type());
                Symbol local = idents[i].symbol();
                assert local != null && !local.isModule(): show(idents[i]);
            }
            conforms(tree, symbol.resultType());
            scopeInsertLabel(symbol);
            expression(rhs, symbol.resultType());
            scopeRemoveLabel(symbol);
            return true;

        case Block(Tree[] statements, Tree value):
            Set locals = new HashSet();
            for (int i = 0; i < statements.length; i++)
                statement(locals, statements[i]);
            expression(value, expected);
            for (Iterator i = locals.iterator(); i.hasNext(); )
                scopeRemoveVVariable((Symbol)i.next());
            return true;

        case Assign(Tree lhs, Tree rhs):
            location(lhs);
            expression(rhs, lhs.type().widen());
            return true;

        case If(Tree cond, Tree thenp, Tree elsep):
            expression(cond, definitions.BOOLEAN_TYPE());
            expression(thenp, expected);
            expression(elsep, expected);
            return true;

        case Switch(Tree test, _, Tree[] bodies, Tree otherwise):
            expression(test, definitions.INT_TYPE());
            for (int i = 0; i < bodies.length; i++)
                expression(bodies[i], expected);
            expression(otherwise, expected);
            return true;

        case Return(Tree value):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isMethod(): show(tree);
            assert currentMember() == symbol: show(tree);
            return expression(value, currentMember().resultType());

        case Throw(Tree value):
            return expression(value, definitions.JAVA_THROWABLE_TYPE());

        case New(Template(Tree[] bases, Tree[] body)):
            assert bases.length == 1 && body.length == 0: show(tree);
            Tree fun = TreeInfo.methPart(bases[0]);
            assert fun instanceof Tree.Ident: show(tree);
            Symbol symbol = fun.symbol();
            assert symbol != null && symbol.isInitializer(): show(tree);
            return expression(bases[0], definitions.UNIT_TYPE());

        case Apply(Tree vfun, Tree[] vargs):
            vapply(tree, vfun.type(), vargs);
            switch (vfun) {
            case TypeApply(Tree tfun, Tree[] targs):
                Symbol symbol = tfun.symbol();
                assert symbol != null && !symbol.isLabel(): show(tree);
                tapply(tree, tfun.type(), targs);
                return function(tfun);
            default:
                return function(vfun);
            }

        case Super(_, _):
        case This(_):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isClass(): show(tree);
            assert symbol == currentClass(): show(tree);
            return true;

        case Select(_, _):
        case Ident(_):
            return location(tree);

        case Literal(_):
            return true;

        default:
            throw Debug.abort("illegal case", tree);
        }
    }

    /** Checks the type application. Returns true. */
    private boolean tapply(Tree tree, Type function, Tree[] args) {
        Symbol[] params = function.typeParams();
        assert params.length == args.length: show(tree)
            + format("params", Debug.show(params));
        Type.Map subst = Type.getSubst(params, Tree.typeOf(args));
        for (int i = 0; i < args.length; i++) {
            Type expected = subst.apply(params[i].info());
            Type loBound = subst.apply(params[i].loBound());
            conforms(args[i], expected, loBound);
        }
        conforms(tree, subst.apply(function.resultType()));
        return true;
    }

    /** Checks the value application. Returns true. */
    private boolean vapply(Tree tree, Type function, Tree[] args) {
        Symbol[] params = function.valueParams();
        assert params.length == args.length: show(tree)
            + format("params", Debug.show(params));
        for (int i = 0; i < args.length; i++)
            expression(args[i], params[i].type());
        conforms(tree, function.resultType());
        return true;
    }

    //########################################################################
    // Private Methods - Checking functions

    /** Checks the function. Returns true. */
    private boolean function(Tree tree) {
        Symbol symbol = tree.symbol();
        assert symbol != null && symbol.isTerm(): show(tree);
        assert symbol.isMethod(): show(tree);
        switch (tree) {

        case Select(Tree qualifier, _):
            return selection(tree);

        case Ident(_):
            if (symbol.isInitializer()) return true;
            assert labels.contains(symbol): show(tree);
            assert symbol.owner() == currentMember(): show(tree);
            return true;

        default:
            throw Debug.abort("illegal case", tree);
        }
    }

    /** Checks the location. Returns true. */
    private boolean location(Tree tree) {
        Symbol symbol = tree.symbol();
        assert symbol != null && symbol.isTerm(): show(tree);
        assert !symbol.isMethod(): show(tree);
        switch (tree) {

        case Select(_, _):
            return selection(tree);

        case Ident(_):
            if (symbol.isModule()) return true;
            assert vvars.contains(symbol): show(tree);
            assert symbol.owner() == currentMember(): show(tree);
            return true;

        default:
            throw Debug.abort("illegal case", tree);
        }
    }

    //########################################################################
    // Private Methods - Checking selection

    /** Checks the selection. Returns true. */
    private boolean selection(Tree tree) {
        switch (tree) {

        case Select(Tree qualifier, _):
            Symbol symbol = tree.symbol();
            assert symbol != null && symbol.isTerm(): show(tree);
            Symbol owner = symbol.owner();
            assert owner.isClassType(): show(tree);
            assert qualifier.type().baseType(owner) != Type.NoType: show(tree);
            return expression(qualifier, qualifier.type());

        default:
            throw Debug.abort("illegal case", tree);
        }
    }

    //########################################################################
    // Private Methods - Checking helpers

    /** Do the trees contain the given symbols? */
    private void containSymbols(Tree[] trees, Symbol[] symbols) {
        boolean ok = trees.length == symbols.length;
        for (int i = 0; ok && i < trees.length; i++)
            ok &= trees[i].symbol() == symbols[i];
        assert ok: show() + format("trees", trees) + format("symbols",symbols);
    }

    /** Does the type conform to the expected type and lower bound? */
    private void conforms(Tree tree, Type expected, Type loBound) {
        conforms(tree, expected);
        if (false && !loBound.isSubType(tree.type())) { // !!! false &&
            Type.explainSwitch = true;
            assert loBound.isSubType(tree.type()): show(tree)
                + format("loBound", expected);
            Type.explainSwitch = false;
        }
    }

    /** Does the type conform to the expected type? */
    private void conforms(Tree tree, Type expected) {
        if (!tree.type().isSubType(expected)) {
            Type.explainSwitch = true;
            assert tree.type().isSubType(expected): show(tree)
                + format("expected", expected);
            Type.explainSwitch = false;
        }
    }

    //########################################################################
    // Private Methods - Declaring symbols

    /** Remove parameters of symbol from current scope. */
    private void scopeInsertParametersOf(Symbol symbol) {
        Symbol[] tparams = symbol.typeParams();
        for (int i = 0; i < tparams.length; i++)
            scopeInsertTVariable(tparams[i], true);
        Symbol[] vparams = symbol.valueParams();
        for (int i = 0; i < vparams.length; i++)
            scopeInsertVVariable(vparams[i], true);
    }

    /** Adds the type variable to the current scope. */
    private void scopeInsertTVariable(Symbol symbol, boolean isParameter) {
        assert !symbol.owner().isClass(): show(symbol);
        assert symbol.isParameter() == isParameter: show(symbol);
        registerSymbol(symbol);
        tvars.add(symbol);
    }

    /** Adds the value variable to the current scope. */
    private void scopeInsertVVariable(Symbol symbol, boolean isParameter) {
        assert !symbol.owner().isClass(): show(symbol);
        assert symbol.isParameter() == isParameter: show(symbol);
        registerSymbol(symbol);
        vvars.add(symbol);
    }

    /** Adds the label to current scope. */
    private void scopeInsertLabel(Symbol symbol) {
        assert !symbol.owner().isClass(): show(symbol);
        registerSymbol(symbol);
        labels.add(symbol);
    }

    /** Remove parameters of symbol from current scope. */
    private void scopeRemoveParametersOf(Symbol symbol) {
        Symbol[] tparams = symbol.typeParams();
        for (int i = 0; i < tparams.length; i++)
            scopeRemoveTVariable(tparams[i]);
        Symbol[] vparams = symbol.valueParams();
        for (int i = 0; i < vparams.length; i++)
            scopeRemoveVVariable(vparams[i]);
    }

    /** Removes the type variable from current scope. */
    private void scopeRemoveTVariable(Symbol symbol) {
        boolean removed = tvars.remove(symbol);
        assert removed: show(symbol);
    }

    /** Removes the value variable from current scope. */
    private void scopeRemoveVVariable(Symbol symbol) {
        boolean removed = vvars.remove(symbol);
        assert removed: show(symbol);
    }

    /** Removes the label symbol from current scope. */
    private void scopeRemoveLabel(Symbol symbol) {
        boolean removed = labels.remove(symbol);
        assert removed: show(symbol);
    }

    /** Registers the symbol. */
    private void registerSymbol(Symbol symbol) {
        boolean added = symbols.add(symbol);
        assert added: show(symbol);
    }

    //########################################################################
    // Private Methods - Managing current context

    /** Returns the current unit. */
    private Unit currentUnit() {
        return units.size() > 0 ? (Unit)units.peek() : null;
    }

    /** Returns the current class. */
    private Symbol currentClass() {
        return classes.size() > 0 ? (Symbol)classes.peek() : null;
    }

    /** Returns the current member. */
    private Symbol currentMember() {
        return members.size() > 0 ? (Symbol)members.peek() : null;
    }

    /** Returns the current owner. */
    private Symbol currentOwner() {
        return owners.size() > 0 ? (Symbol)owners.peek() : null;
    }

    /** Sets the current unit to the given one. */
    private void pushUnit(Unit unit) {
        assert units.size() == 0: showPush(unit);
        assert classes.size() == 0: showPush(unit);
        assert members.size() == 0: showPush(unit);
        units.push(unit);
    }

    /** Sets the current class to the given one. */
    private void pushClass(Symbol clasz) {
        assert clasz.isClass(): showPush(clasz);
        assert members.size() == 0: showPush(clasz);
        classes.push(clasz);
        pushOwner(clasz);
    }

    /** Sets the current member to the given one. */
    private void pushMember(Symbol member) {
        assert member.isTerm(): showPush(member);
        assert members.size() == 0: showPush(member);
        assert member.owner() == currentClass(): showPush(member);
        members.push(member);
        pushOwner(member);
    }

    /** Sets the current owner to the given one. */
    private void pushOwner(Symbol owner) {
        owners.push(owner);
    }

    /** Sets the current unit to the previous one. */
    private void popUnit() {
        assert units.size() > 0: show();
        units.pop();
    }

    /** Sets the current class to the previous one. */
    private void popClass() {
        assert members.size() == 0: show();
        assert classes.size() > 0: show();
        popOwner();
        classes.pop();
    }

    /** Sets the current member to the previous one. */
    private void popMember() {
        assert members.size() > 0: show();
        popOwner();
        members.pop();
    }

    /** Sets the current owner to the previous one. */
    private void popOwner() {
        assert owners.size() > 0: show();
        owners.pop();
    }

    //########################################################################
    // Private Methods - Showing errors

    /** Returns the current position. */
    private String show() {
        return format("unit", currentUnit())
            + format("clasz", currentClass())
            + format("member", currentMember())
            + format("owner", currentOwner());
    }

    /** Returns the current position and given header and value. */
    private String show(String header, Object value) {
        return show() + format(header, value);
    }

    /** Returns the current position and given symbol. */
    private String show(Symbol symbol) {
        return show("symbol", symbol)
            + format("symbol.pos", Position.toString(symbol.pos))
            + format("symbol.info", symbol.info());
    }

    /** Returns the current position and given tree. */
    private String show(Tree tree) {
        return show("tree", tree)
            + format("tree.pos", Position.toString(tree.pos))
            + format("tree.symbol", tree.symbol())
            + format("tree.type", tree.type());
    }

    /** Returns the current position and given pushed value. */
    private String showPush(Object value) {
        return show("pushing", value);
    }

    /** Returns a string with the given header and value. */
    private String format(String header, Object value) {
        while (header.length() < 12) header = header + ' ';
        return "\n" + header + ": " + toString(value);
    }

    /** Returns a string representation of the given value. */
    private String toString(Object value) {
        if (value instanceof Symbol) return Debug.show(value);
        if (value instanceof Object[]) return Debug.show(value);
        return String.valueOf(value);
    }

    //########################################################################
}