path: root/sources/scalac/transformer/Erasure.java

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

// $OldId: Erasure.java,v 1.48 2003/01/16 14:21:19 schinz Exp $
// $Id$

package scalac.transformer;

import java.util.HashMap;

import scalac.Global;
import scalac.Unit;
import scalac.ast.Tree;
import scalac.ast.Tree.Template;
import scalac.ast.Tree.AbsTypeDef;
import scalac.ast.Tree.AliasTypeDef;
import scalac.ast.Tree.ValDef;
import scalac.ast.TreeList;
import scalac.ast.Transformer;
import scalac.symtab.Definitions;
import scalac.symtab.Kinds;
import scalac.symtab.Type;
import scalac.symtab.TypeTags;
import scalac.symtab.Modifiers;
import scalac.symtab.Scope;
import scalac.symtab.SymSet;
import scalac.symtab.Symbol;
import scalac.backend.Primitive;
import scalac.backend.Primitives;
import scalac.util.Name;
import scalac.util.Names;
import scalac.util.Debug;

/** A transformer for type erasure and bridge building
 *
 *  @author     Martin Odersky
 *  @version    1.0
 *
 *  What it does:
 *  (1) Map every type to its erasure.
 *  (2) If method A overrides a method B, and the erased type ETA of A is
 *      different from the erased type ETB of B seen as a member of A's class,
 *      add a bridge method with the same name as A,B, with signature ETB
 *      which calls A after casting parameters.
 */
public class Erasure extends Transformer implements Modifiers {

    //########################################################################
    // Private Constants

    /** The unboxed types */
    private static final Type
        UNBOXED_UNIT    = Type.unboxedType(TypeTags.UNIT),
        UNBOXED_BOOLEAN = Type.unboxedType(TypeTags.BOOLEAN),
        UNBOXED_BYTE    = Type.unboxedType(TypeTags.BYTE),
        UNBOXED_SHORT   = Type.unboxedType(TypeTags.SHORT),
        UNBOXED_CHAR    = Type.unboxedType(TypeTags.CHAR),
        UNBOXED_INT     = Type.unboxedType(TypeTags.INT),
        UNBOXED_LONG    = Type.unboxedType(TypeTags.LONG),
        UNBOXED_FLOAT   = Type.unboxedType(TypeTags.FLOAT),
        UNBOXED_DOUBLE  = Type.unboxedType(TypeTags.DOUBLE);

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

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

    /** The global primitives */
    private final Primitives primitives;

    /** The current unit */
    private Unit unit;

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

    /** Initializes this instance. */
    public Erasure(Global global) {
        super(global);
	this.definitions = global.definitions;
        this.primitives = global.primitives;
    }

    //########################################################################
    // Private Methods - Tree generation

    /** Generates given bridge method forwarding to given method. */
    private Tree genBridgeMethod(Symbol bridge, Symbol method) {
        Type type = bridge.nextType();
        Tree body = genApply(bridge.pos,
            gen.Select(gen.This(bridge.pos, bridge.owner()), method),
            gen.mkRefs(bridge.pos, type.valueParams()));
        return gen.DefDef(bridge, coerce(body, type.resultType()));
    }

    /** Generates an application with given function and arguments. */
    private Tree genApply(int pos, Tree fun, Tree[] args) {
        switch (fun.type()) {
        case MethodType(Symbol[] params, Type result):
            Tree[] args1 = args;
            for (int i = 0; i < args.length; i++) {
                Tree arg = args[i];
                Tree arg1 = coerce(arg, params[i].nextType());
                if (arg1 != arg && args1 == args) {
                    args1 = new Tree[args.length];
                    for (int j = 0; j < i; j++) args1[j] = args[j];
                }
                args1[i] = arg1;
            }
            return gen.mkApply_V(pos, fun, args1);
        default:
            throw Debug.abort("illegal type " + fun.type() + " for " + fun);
        }
    }

    /**
     * Generates a new unboxed array of given size and with elements
     * of given type.
     */
    private Tree genNewUnboxedArray(int pos, Type element, Tree size) {
        switch (element) {
        case UnboxedType(int kind): return genNewUnboxedArray(pos, kind, size);
        }
        if (global.target == global.TARGET_INT) {
            global.nextPhase();
            while (!element.symbol().isJava()) element = element.parents()[0];
            global.prevPhase();
        }
        String name = primitives.getNameForClassForName(element);
        Tree[] args = { coerce(size, UNBOXED_INT), gen.mkStringLit(pos,name) };
        Tree array = gen.mkApply_V(gen.mkRef(pos,primitives.NEW_OARRAY), args);
        return gen.mkAsInstanceOf(array, Type.UnboxedArrayType(element));
    }

    /**
     * Generates a new unboxed array of given size and with elements
     * of given unboxed type kind.
     */
    private Tree genNewUnboxedArray(int pos, int kind, Tree size) {
        Symbol symbol = primitives.getNewArraySymbol(kind);
        Tree[] args = { coerce(size, UNBOXED_INT) };
        return gen.mkApply_V(gen.mkRef(pos, symbol), args);
    }

    /** Generates an unboxed array length operation. */
    private Tree genUnboxedArrayLength(int pos, Tree array) {
        assert isUnboxedArray(array.type()): array;
        Symbol symbol = primitives.getArrayLengthSymbol(array.type());
        Tree[] args = { array };
        return gen.mkApply_V(gen.mkRef(pos, symbol), args);
    }

    /** Generates an unboxed array get operation. */
    private Tree genUnboxedArrayGet(int pos, Tree array, Tree index) {
        assert isUnboxedArray(array.type()): array;
        Symbol symbol = primitives.getArrayGetSymbol(array.type());
        index = coerce(index, UNBOXED_INT);
        Tree[] args = { array, index };
        return gen.mkApply_V(gen.mkRef(pos, symbol), args);
    }

    /** Generates an unboxed array set operation. */
    private Tree genUnboxedArraySet(int pos, Tree array,Tree index,Tree value){
        assert isUnboxedArray(array.type()): array;
        Symbol symbol = primitives.getArraySetSymbol(array.type());
        index = coerce(index, UNBOXED_INT);
        value = coerce(value, getArrayElementType(array.type()));
        Tree[] args = { array, index, value };
        return gen.mkApply_V(gen.mkRef(pos, symbol), args);
    }

    //########################################################################
    //########################################################################
    //########################################################################
    //########################################################################

    public void apply(Unit unit) {
	this.unit = unit;
	unit.body = transform(unit.body);
    }

//////////////////////////////////////////////////////////////////////////////////
// Box/Unbox and Coercions
/////////////////////////////////////////////////////////////////////////////////
    private boolean hasBoxing(Tree tree) {
        switch (tree) {
        case Apply(Tree fun, _):
            return primitives.getPrimitive(fun.symbol()) == Primitive.BOX;
        default:
            return false;
        }
    }

    /**
     * Return the unboxed version of the given tree.
     */
    private Tree removeBoxing(Tree tree) {
        switch (tree) {
        case Apply(Tree fun, Tree[] args):
            assert primitives.getPrimitive(fun.symbol())==Primitive.BOX: tree;
            assert args.length == 1: tree;
            return args[0];
        default:
            throw Debug.abort("illegal case", tree);
        }
    }

    private boolean isUnboxedType(Type type) {
	switch (type) {
	case UnboxedType(_)     : return true;
	case UnboxedArrayType(_): return true;
	default                 : return false;
	}
    }

    private boolean isUnboxedSimpleType(Type type) {
	switch (type) {
	case UnboxedType(_)     : return true;
	default                 : return false;
	}
    }

    private boolean isUnboxedArrayType(Type type) {
	switch (type) {
	case UnboxedArrayType(_): return true;
	default                 : return false;
	}
    }

    boolean isUnboxed(Type type) {
	switch (type) {
	case UnboxedType(_): case UnboxedArrayType(_): return true;
	default: return false;
	}
    }

    boolean isUnboxedArray(Type type) {
	switch (type) {
	case UnboxedArrayType(_): return true;
	default: return false;
	}
    }

    boolean isBoxed(Type type) {
	return type.unbox() != type || type.symbol().fullName() == Names.scala_Array;
    }

    Type boxedType(Type tp) {
	switch (tp) {
	case UnboxedType(int kind):
	    return definitions.getType(Type.boxedFullName(kind));
	case UnboxedArrayType(Type elemtp):
            return definitions.arrayType(boxedType(elemtp));
	default:
	    return tp;
	}
    }

    Symbol boxSym(Type unboxedtp) {
        return primitives.getBoxValueSymbol(unboxedtp);
    }

    /** Emit `scala.RunTime.box(tree)' or
     *  `{ tree ; scala.RunTime.box() }' if type of `tree' is `void'.
     */
    Tree box(Tree tree) {
	Tree boxtree = gen.mkRef(tree.pos, primitives.RUNTIME_TYPE, boxSym(tree.type));
	switch (tree.type) {
	case UnboxedType(int kind):
	    if (kind == TypeTags.UNIT)
		return gen.Block(
		    tree.pos, new Tree[]{tree, gen.Apply(boxtree, new Tree[0])});
	}
	return gen.Apply(boxtree, new Tree[]{tree});
    }

    /** The symbol of the unbox method corresponding to unboxed type`unboxedtp'
     */
    Symbol unboxSym(Type unboxedtp) {
        return primitives.getUnboxValueSymbol(unboxedtp);
    }

    /** Emit tree.asType() or tree.asTypeArray(), where pt = Type or pt = Type[].
     */
    Tree unbox(Tree tree, Type pt) {
	Tree sel = gen.Select(tree, unboxSym(pt));
	return gen.Apply(sel, new Tree[0]);
    }

    /** Generate a select from an unboxed type.
     */
    public Tree unboxedSelect(Tree qual, Symbol sym) {
	return make.Select(qual.pos, qual, sym.name)
	    .setSymbol(sym)
            .setType(Type.singleType(boxedType(qual.type).symbol().thisType(),sym).erasure());
    }

    /** Subclass relation for class types; empty for other types.
     */
    boolean isSubClass(Type tp1, Type tp2) {
	Symbol sym1 = tp1.symbol();
	Symbol sym2 = tp2.symbol();
	return sym1 != null && sym2 != null && sym1.isSubClass(sym2);
    }

    /** Subtyping relation on erased types.
     */
    boolean isSubType(Type tp1, Type tp2) {
 	if (isSameAs(tp1, tp2)) return true;
	switch (tp2) {
	case UnboxedType(_):
	    return tp1.isSubType(tp2);
	case UnboxedArrayType(Type elemtp2):
	    switch (tp1) {
	    case UnboxedArrayType(Type elemtp1):
		return !(elemtp1 instanceof Type.UnboxedType) &&
		    isSubType(elemtp1, elemtp2);
	    default:
		return tp1.isSubType(tp2);
	    }
	}
	switch (tp1) {
	case UnboxedArrayType(Type elemtp1):
            if (tp2.symbol() == definitions.ANY_CLASS) return true;
        }
	return isSubClass(tp1, tp2);
    }

    /** Equality relation on erased types.
     */
    boolean isSameAs(Type tp1, Type tp2) {
        global.nextPhase();
        boolean result = tp1.isSameAs(tp2);
        global.prevPhase();
        return result;
    }

    Tree coerce(Tree tree, Type pt) {
	return isSubType(tree.type, pt) ? tree : cast(tree, pt);
    }

    Tree cast(Tree tree, Type pt) {
	if (global.debug) global.log("cast " + tree + ":" + tree.type + " to " + pt);//debug
	if (isSameAs(tree.type, pt)) {
	    return tree;
	} else if (isSubType(tree.type, pt)) {
	    return tree;
	} else if (isUnboxed(tree.type) && !isUnboxed(pt)) {
	    return cast(box(tree), pt);
	} else if ((isUnboxedArray(tree.type)
                    || (tree.type.symbol() == definitions.ANY_CLASS))
                   && isUnboxedArray(pt)) {
	    return
		make.Apply(tree.pos,
		    make.TypeApply(tree.pos,
			unboxedSelect(tree, definitions.AS),
			new Tree[]{gen.mkType(tree.pos, pt)})
		    .setType(new Type.MethodType(Symbol.EMPTY_ARRAY, pt)),
                   new Tree[0])
		.setType(pt);
	} else if (!isUnboxed(tree.type) && isUnboxed(pt)) {
	    if (isBoxed(tree.type)) {
		return coerce(unbox(tree, pt), pt);
	    } else {
		Type bt = boxedType(pt);
		while (isBoxed(bt.parents()[0])) {
		    bt = bt.parents()[0];
		}
		return cast(coerce(tree, bt), pt);
	    }
	} else if (isUnboxed(tree.type) && isUnboxed(pt)) {
	    return gen.Apply(
		unboxedSelect(box(tree), unboxSym(pt)),
		new Tree[0]);
	} else if (!isUnboxed(tree.type) && !isUnboxed(pt) ||
		   isUnboxedArray(tree.type) && isUnboxedArray(pt)) {
	    return
		gen.Apply(
		    gen.TypeApply(
			gen.Select(tree, definitions.AS),
			new Tree[]{gen.mkType(tree.pos, pt)}),
		    new Tree[0]);
	} else {
	    throw Debug.abort("cannot cast " + tree.type + " to " + pt);
	}
    }

//////////////////////////////////////////////////////////////////////////////////
// Bridge Building
/////////////////////////////////////////////////////////////////////////////////

    private TreeList bridges;
    private HashMap bridgeSyms;

    /** Add bridge which Java-overrides `sym1' and which forwards to `sym'
     */
    public void addBridge(Symbol owner, Symbol sym, Symbol sym1) {
	Type bridgeType = sym1.type().erasure();

	// create bridge symbol and add to bridgeSyms(sym)
	// or return if bridge with required type already exists for sym.
	SymSet bridgesOfSym = (SymSet) bridgeSyms.get(sym);
	if (bridgesOfSym == null) bridgesOfSym = SymSet.EMPTY;
	Symbol[] brs = bridgesOfSym.toArray();
	for (int i = 0; i < brs.length; i++) {
	    if (isSameAs(brs[i].type(), bridgeType)) return;
	}
	Symbol bridgeSym = sym.cloneSymbol();
	bridgeSym.flags |= (SYNTHETIC | BRIDGE);
	bridgeSym.flags &= ~(JAVA | DEFERRED);
	bridgesOfSym = bridgesOfSym.incl(bridgeSym);
	bridgeSyms.put(sym, bridgesOfSym);
        bridgeSym.setOwner(owner);

	// check that there is no overloaded symbol with same erasure as bridge
	// todo: why only check for overloaded?
	Symbol overSym = owner.members().lookup(sym.name);
	switch (overSym.type()) {
	case OverloadedType(Symbol[] alts, Type[] alttypes):
	    for (int i = 0; i < alts.length; i++) {
		if (sym != alts[i] && isSameAs(bridgeType, alttypes[i].erasure())) {
		    unit.error(sym.pos, "overlapping overloaded alternatives; " +
			       "overridden " + sym1 + sym1.locationString() +
			       " has same erasure as " + alts[i] +
			       alttypes[i] + alts[i].locationString());
		}
	    }
	}

	switch (bridgeType) {
	case MethodType(Symbol[] params, Type restp):
	    // assign to bridge symbol its bridge type
	    // where owner of all parameters is bridge symbol itself.
	    Symbol[] params1 = new Symbol[params.length];
	    for (int i = 0; i < params.length; i++) {
		params1[i] = params[i].cloneSymbol(bridgeSym);
	    }
	    bridgeSym.setType(Type.MethodType(params1, restp));

            bridges.append(genBridgeMethod(bridgeSym, sym));
        }

    }

//////////////////////////////////////////////////////////////////////////////////
// Transformer
/////////////////////////////////////////////////////////////////////////////////


    private Symbol getOverriddenMethod(Symbol method) {
        Type[] parents = method.owner().parents();
        if (parents.length == 0) return Symbol.NONE;
        return method.overriddenSymbol(parents[0]);
    }

    public void addBridgeMethodsTo(Symbol method) {
        assert method.owner().isClass() && !method.owner().isInterface();
        Symbol overridden = getOverriddenMethod(method);
        if (overridden != Symbol.NONE && !isSameAs(overridden.nextType(), method.nextType()))
            addBridge(method.owner(), method, overridden);
    }

    public void addInterfaceBridges(Symbol owner, Symbol method) {
	assert owner.isClass() && !owner.isInterface(): Debug.show(owner);
        Symbol overriding = method.overridingSymbol(owner.thisType());
        if (overriding != Symbol.NONE && !isSameAs(overriding.nextType(), method.nextType()))
            addBridge(owner, overriding, method);
    }

    private void addBridges(Symbol clasz, TreeList members) {
        TreeList savedBridges = bridges;
        HashMap savedBridgeSyms = bridgeSyms;
        bridges = new TreeList();
        bridgeSyms = new HashMap();

        int length = members.length();
        if (!clasz.isInterface()) {
            for (int i = 0; i < length; i++) {
                switch (members.get(i)) {
                case DefDef(_, _, _, _, _, Tree rhs):
                    addBridgeMethodsTo(members.get(i).symbol());
                }
            }
            addInterfaceBridges(clasz);
        }

        members.append(bridges);
        if (bridges.length() > 0) {
            Type info = clasz.nextInfo();
            switch (info) {
            case CompoundType(Type[] parts, Scope members_):
                members_ = new Scope(members_);
                for (int i = 0; i < bridges.length(); i++) {
                    Tree bridge = (Tree)bridges.get(i);
                    members_.enterOrOverload(bridge.symbol());
                }
                clasz.updateInfo(Type.compoundType(parts, members_, info.symbol()));
                break;
            default:
                throw Debug.abort("class = " + Debug.show(clasz) + ", " +
                    "info = " + Debug.show(info));
            }
        }
        bridgeSyms = savedBridgeSyms;
        bridges = savedBridges;
    }

    /** Contract: every node needs to be transformed so that it's type is the
     *  erasure of the node's original type.  The only exception are functions;
     *  these are mapped to the erasure of the function symbol's type.
     */
    public Tree transform(Tree tree, boolean eraseFully) {
	assert tree.type != null : tree;
	Type owntype = eraseFully ? tree.type.fullErasure() : tree.type.erasure();
	switch (tree) {

	case ClassDef(_, _, _, _, _, Template(_, Tree[] body)):
            Symbol clasz = tree.symbol();
            TreeList members = new TreeList(transform(body));
            addBridges(clasz, members);
            return gen.ClassDef(clasz, members.toArray());

	case DefDef(_, _, _, _, _, Tree rhs):
            Symbol method = tree.symbol();
            if (rhs != Tree.Empty)
                rhs = transform(rhs, method.nextType().resultType());
	    return gen.DefDef(method, rhs);

	case ValDef(_, _, _, Tree rhs):
            Symbol field = tree.symbol();
	    if (rhs != Tree.Empty) rhs = transform(rhs, field.nextType());
	    return gen.ValDef(field, rhs);

	case AbsTypeDef(_, _, _, _):
	case AliasTypeDef(_, _, _, _):
	    // eliminate
	    return Tree.Empty;

        case Block(Tree[] stats):
            Tree[] newStats = new Tree[stats.length];
            for (int i = 0; i < stats.length; ++i)
                newStats[i] = transform(stats[i], true);
            return gen.Block(tree.pos, newStats);

	case Assign(Tree lhs, Tree rhs):
	    Tree lhs1 = transform(lhs);
	    Tree rhs1 = transform(rhs, lhs1.type);
	    return copy.Assign(tree, lhs1, rhs1).setType(owntype.fullErasure());

	case If(Tree cond, Tree thenp, Tree elsep):
	    Tree cond1 = transform(cond, Type.unboxedType(TypeTags.BOOLEAN));
	    Tree thenp1 = transform(thenp, owntype);
	    Tree elsep1 = (elsep == Tree.Empty) ? elsep : transform(elsep, owntype);
	    return copy.If(tree, cond1, thenp1, elsep1).setType(owntype);

        case Switch(Tree test, int[] tags, Tree[] bodies, Tree otherwise):
	    Tree test1 = transform(test, Type.unboxedType(TypeTags.INT));
            Tree[] bodies1 = transform(bodies, owntype);
            Tree otherwise1 = transform(otherwise, owntype);
            return copy.Switch(tree, test1, tags, bodies1, otherwise1).setType(owntype);

	case Return(Tree expr):
	    Tree expr1 = transform(expr,
                                   tree.symbol().type().resultType().fullErasure());
            Tree zero = gen.Ident(tree.pos, definitions.NULL);
	    return make.Block(tree.pos, new Tree[] {
                copy.Return(tree, expr1).setType(owntype), zero}).setType(zero.type());

        case New(Template templ):
            if (tree.type.symbol() == definitions.ARRAY_CLASS) {
                switch (templ.parents[0]) {
                case Apply(_, Tree[] args):
                    args = transform(args);
                    switch (owntype) {
                    case UnboxedArrayType(Type element):
                        return genNewUnboxedArray(tree.pos, element, args[0]);
                    default:
                        throw Debug.abort("illegal case", owntype);
                    }
                default:
                    throw Debug.abort("illegal case", templ.parents[0]);
                }
            }
	    return super.transform(tree).setType(owntype);

	case Typed(Tree expr, Tree tpe):
	    // coerce expr to tpe
	    Tree tpe1 = gen.mkType(tpe.pos, tpe.type().erasure()); // !!! was transform(tpe);
            // !!! More generally, we should never transform a tree
            // that represents a type. We should always transform
            // types and then reconstruct the corresponding tree.
	    return transform(expr, tpe1.type);

	case Apply(TypeApply(Tree fun, Tree[] targs), Tree[] vargs):
            fun = transform(fun);
            vargs = transform(vargs);
            Symbol symbol = fun.symbol();
            if (symbol == definitions.AS) {
                assert targs.length == 1 && vargs.length == 0: tree;
                return coerce(getQualifier(fun), targs[0].type().erasure());
            }
            if (symbol == definitions.IS) {
                assert targs.length == 1 && vargs.length == 0: tree;
                Type type = targs[0].type.erasure();
                if (isUnboxedSimpleType(type)) type = targs[0].type;
                return gen.mkIsInstanceOf(tree.pos, getQualifier(fun), type);
            }
            return genApply(tree.pos, fun, vargs);

	case Apply(Tree fun, Tree[] vargs):
            fun = transform(fun);
            vargs = transform(vargs);
            switch (fun) {
            case Select(Tree qualifier, _):
                if (!hasBoxing(qualifier)) break;
                switch (primitives.getPrimitive(fun.symbol())) {
                case LENGTH:
                    assert vargs.length == 0: tree;
                    Tree array = removeBoxing(qualifier);
                    return genUnboxedArrayLength(tree.pos, array);
                case APPLY:
                    assert vargs.length == 1: tree;
                    Tree array = removeBoxing(qualifier);
                    Tree index = vargs[0];
                    return genUnboxedArrayGet(tree.pos, array, index);
                case UPDATE:
                    assert vargs.length == 2: tree;
                    Tree array = removeBoxing(qualifier);
                    Tree index = vargs[0];
                    Tree value = vargs[1];
                    return genUnboxedArraySet(tree.pos, array, index, value);
                }
            }
            return genApply(tree.pos, fun, vargs);

	case Select(Tree qualifier, _):
            Symbol symbol = tree.symbol();
            qualifier = transform(qualifier);
            qualifier = coerce(qualifier, symbol.owner().type().erasure());
            if (isUnboxedType(qualifier.type())) qualifier = box(qualifier);
	    return gen.Select(tree.pos, qualifier, symbol);

	case Ident(_):
            Symbol symbol = tree.symbol();
	    if (symbol == definitions.ZERO) return gen.mkNullLit(tree.pos);
            return gen.Ident(tree.pos, symbol);

        case LabelDef(Name name, Tree.Ident[] params,Tree body):
	    Tree.Ident[] new_params = new Tree.Ident[params.length];
	    for (int i = 0; i < params.length; i++) {
		new_params[i] = (Tree.Ident)gen.Ident(params[i].pos, params[i].symbol());
	    }

	    return copy.LabelDef(tree, new_params, transform(body)).setType(owntype);



        case Empty:
        case PackageDef(_,_):
        case Template(_,_):
        case Sequence(_): // !!! ? [BE:was Tuple before]
        case Super(_, _):
        case This(_):
        case Literal(_):
        case TypeTerm():
	    return super.transform(tree).setType(owntype);

        case Bad():
        case ModuleDef(_,_,_,_):
        case PatDef(_,_,_):
        case Import(_,_):
        case CaseDef(_,_,_):
        case Visitor(_):
        case Function(_,_):
        case SingletonType(_):
        case SelectFromType(_,_):
        case FunType(_,_):
        case CompoundType(_,_):
        case AppliedType(_, _):
            throw Debug.abort("illegal case", tree);

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

    public Tree transform(Tree tree) {
        return transform(tree, false);
    }

    // !!! This is just rapid fix. Needs to be reviewed.
    private void addInterfaceBridges(Symbol owner) {
        Type[] parents = owner.info().parents();
        for (int i = 1; i < parents.length; i++)
            addInterfaceBridgesRec(owner, parents[i].symbol());
    }
    private void addInterfaceBridgesRec(Symbol owner, Symbol interfase) {
        addInterfaceBridgesAux(owner, interfase.nextInfo().members());
        Type[] parents = interfase.parents();
        for (int i = 0; i < parents.length; i++) {
            Symbol clasz = parents[i].symbol();
            if (clasz.isInterface()) addInterfaceBridgesRec(owner, clasz);
        }
    }
    private void addInterfaceBridgesAux(Symbol owner, Scope symbols) {
        for (Scope.SymbolIterator i = symbols.iterator(true); i.hasNext();) {
            Symbol member = i.next();
            if (!member.isTerm() || !member.isDeferred()) continue;
            addInterfaceBridges(owner, member);
        }
    }

    /** Transform with prototype
     */
    Tree transform(Tree expr, Type pt) {
	return coerce(transform(expr), pt);
    }
    Tree[] transform(Tree[] exprs, Type pt) {
        for (int i = 0; i < exprs.length; i++) {
            Tree tree = transform(exprs[i], pt);
            if (tree == exprs[i]) continue;
            Tree[] trees = new Tree[exprs.length];
            for (int j = 0; j < i ; j++) trees[j] = exprs[j];
            trees[i] = tree;
            while (++i < exprs.length) trees[i] = transform(exprs[i], pt);
            return trees;
        }
        return exprs;
    }

    private Tree getQualifier(Tree tree) {
        switch (tree) {
        case Select(Tree qual, _):
            return qual;
        default:
            throw Debug.abort("no qualifier for tree", tree);
        }
    }


    private Type getArrayElementType(Type type) {
        switch (type) {
        case TypeRef(_, Symbol symbol, Type[] args):
            if (symbol != definitions.ARRAY_CLASS) break;
            assert args.length == 1: type;
            return args[0];
        case UnboxedArrayType(Type element):
            return element;
        }
        throw Debug.abort("non-array type", type);
    }

}