path: root/sources/scalac/symtab/Type.java

/*     ____ ____  ____ ____  ______                                     *\
**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2002, LAMP/EPFL              **
** /_____/\____/\___/\____/____/                                        **
**
** $Id$
\*                                                                      */
//todo: T {} == T

package scalac.symtab;

import java.util.HashMap;

import scala.tools.util.Position;
import scalac.ApplicationError;
import scalac.atree.AConstant;
import scalac.util.*;
import scalac.Global;

public class Type implements Modifiers, Kinds, TypeTags, EntryTags {

    public static boolean explainSwitch = false;
    private static int indent = 0;

    public case ErrorType;  // not used after analysis
    public case AnyType;    // not used after analysis
    public case NoType;
    public case NoPrefix;

    /** C.this.type
     */
    public case ThisType(Symbol sym) {
        assert sym.isClassType(): Debug.show(sym);
    }

    /** pre.sym.type
     *  sym represents a valueS
     */
    public case SingleType(Type pre, Symbol sym) {
        assert this instanceof ExtSingleType;
    }

    /** Type for a numeric or string constant.
     */
    public case ConstantType(Type base, AConstant value);

    /** pre.sym[args]
     *  sym represents a type
     *  for example: scala.List[java.lang.String] is coded as
     *
     *  TypeRef(
     *      SingleType(ThisType(definitions.ROOT_CLASS), definitions.SCALA),
     *      <List>,
     *      new Type[]{
     *          TypeRef(
     *              SingleType(
     *                  SingleType(ThisType(definitions.ROOT_CLASS), definitions.JAVA),
     *                  definitions.LANG),
     *              definitions.STRING,
     *              new Type[]{})}).
     *
     */
    public case TypeRef(Type pre, Symbol sym, Type[] args) {
        assert this instanceof ExtTypeRef: this;
    }

    /** parts_1 with ... with parts_n { members }
     */
    public case CompoundType(Type[] parts, Scope members) {
        assert this instanceof ExtCompoundType;
    }

    /** synthetic type of a method  def ...(vparams): result = ...
     */
    public case MethodType(Symbol[] vparams, Type result) {
        for (int i = 0; i < vparams.length; i++)
            assert vparams[i].isParameter() && vparams[i].isTerm(): this;
    }

    /** synthetic type of a method  def ...[tparams]result
     *  For instance, given  def f[a](x: a): a
     *  f has type   PolyType(new Symbol[]{<a>},
     *                 MethodType(new Symbol[]{<x>}, <a>.type()))
     *
     *  if tparams is empty, this is the type of a parameterless method
     *  def ... =
     *  For instance, given    def f = 1
     *  f has type   PolyType(new Symbol[]{}, <scala.Int>.type())
     */
    public case PolyType(Symbol[] tparams, Type result) {
        for (int i = 0; i < tparams.length; i++)
            assert tparams[i].isParameter()&&tparams[i].isAbstractType(): this;
    }

    /** synthetic type of an overloaded value whose alternatives are
     *  alts_1, ..., alts_n, with respective types alttypes_1, ..., alttypes_n
     *
     *  For instance, if there are two definitions of `f'
     *    def f: int
     *    def f: String
     *  then there are three symbols:
     *    ``f1'' corresponding to def f: int
     *    ``f2'' corresponding to def f: String
     *    ``f3'' corresponding to both
     *  f3 has type
     *    OverloadedType(
     *      new Symbol[]{<f1>, <f2>},
     *      new Type[]{PolyType(new Symbol[]{}, <int>),
     *                 PolyType(new Symbol[]{}, <String>),
     *
     */
    public case OverloadedType(Symbol[] alts, Type[] alttypes);

    /** Hidden case to implement delayed evaluation of types.
     *  No need to pattern match on this type; it will never come up.
     */
    public case LazyType();

    /** Hidden case to implement local type inference.
     *  Later phases do not need to match on this type.
     */
    public case TypeVar(Type origin, Constraint constr);

    /** Hidden cases to implement type erasure.
     *  Earlier phases do not need to match on these types.
     */
    public case UnboxedType(int tag);
    public case UnboxedArrayType(Type elemtp);

    /** Force evaluation of a lazy type. No cycle
     *  check is needed; since this is done in Symbol.
     *  @see  Symbol.info().
     */
    public void complete(Symbol p) {}

// Creators ---------------------------------------------------------------------

    /** An empty Type array */
    public static final Type[] EMPTY_ARRAY  = new Type[0];

    public static SingleType singleType(Type pre, Symbol sym) {
        assert sym.isTerm() && !sym.isNone(): pre + " -- " + Debug.show(sym);
        rebind:
        {
            Symbol owner = sym.owner();
            if (!owner.isClass()) break rebind;
            if (owner == pre.symbol()) break rebind;
            // !!! add if (owner is sealed/final) break rebind ?
            // !!! add if (owner is module class) break rebind ?
            if (sym.isFinal() || sym.isPrivate()) break rebind;
            Symbol rebind = pre.lookupNonPrivate(sym.name);
            if (rebind.isNone()) break rebind;
            if (rebind.isLocked()) throw new Type.Error(
                "illegal cyclic reference involving " + rebind);
            sym = rebind.rebindSym();
        }
        if (pre.isStable() || pre.isError()) {
            return new ExtSingleType(pre, sym);
        } else {
            throw new Type.Malformed(pre, sym.nameString() + ".type");
        }
    }

    public static Type constantType(AConstant value) {
        return Global.instance.definitions.atyper.type(value);
    }

    public static Type singleTypeMethod(Type pre, Symbol sym) {
        Global global = Global.instance;
        if (global.currentPhase.id <= global.PHASE.UNCURRY.id())
            return singleType(pre, sym);
        else if (global.currentPhase.id <= global.PHASE.ERASURE.id())
            return sym.type().singleTypeMethod0(pre, sym);
        else
            return pre.memberType(sym);
    }

    private Type singleTypeMethod0(Type pre, Symbol sym) {
        switch (this) {
        case PolyType(Symbol[] args, Type result):
            return PolyType(args, result.singleTypeMethod0(pre, sym));
        case MethodType(Symbol[] args, Type result):
            return MethodType(args, result.singleTypeMethod0(pre, sym));
        default:
            return singleType(pre, sym);
        }
    }

    public static Type appliedType(Type tycon, Type[] args) {
        switch (tycon) {
        case TypeRef(Type pre, Symbol sym, Type[] args1):
            if (args == args1) return tycon;
            else return Type.typeRef(pre, sym, args);
        default:
            throw Debug.abort("illegal case", tycon);
        }
    }

    public static Type typeRef(Type pre, Symbol sym, Type[] args) {
        if (sym.kind == TYPE && !pre.isLegalPrefix() && !pre.isError())
            throw new Type.Malformed(pre, sym.nameString());
        rebind:
        if (sym.isAbstractType()) {
            Symbol owner = sym.owner();
            if (!owner.isClass()) break rebind;
            if (owner == pre.symbol()) break rebind;
            // !!! add if (owner is sealed/final) break rebind ?
            // !!! add if (owner is module class) break rebind ?
            if (sym.isFinal() || sym.isPrivate()) break rebind;
            Symbol rebind = pre.lookupNonPrivate(sym.name);
            if (rebind.isNone()) break rebind;
            if (rebind.isLocked()) throw new Type.Error(
                "illegal cyclic reference involving " + rebind);
            sym = rebind.rebindSym();
        }
        if (sym.isTypeAlias()) {
            Symbol[] params = sym.typeParams();
            if (args.length == params.length)
                return pre.memberInfo(sym).subst(params, args);
            assert args.length == 0 || args.length == params.length:
                Debug.show(pre, sym, args, params);
        }
        assert isLegalTypeRef(pre, sym, args):
            Debug.show(pre, sym, args, sym.typeParams());
        return new ExtTypeRef(pre, sym, args);
    }
    private static boolean isLegalTypeRef(Type pre, Symbol sym, Type[] args) {
        if (sym.kind == TYPE && !pre.isLegalPrefix() && !pre.isError()) return false;
        if (!sym.isType() && !sym.isError()) return false;
        // !!! return args.length == 0 || args.length == sym.typeParams().length;
        return true;
    }

    public static Type newTypeRefUnsafe(Type pre, Symbol sym, Type[] args) {
        return new ExtTypeRef(pre, sym, args);
    }

    public static CompoundType compoundType(Type[] parts, Scope members,
                                            Symbol clazz) {
        return new ExtCompoundType(parts, members, clazz);
    }

    public static CompoundType compoundTypeWithOwner(Symbol owner, Type[] parts, Scope members) {
        return new ExtCompoundType(owner, parts, members);
    }

    static class ExtSingleType extends SingleType {
        Type tp = null;
        int definedId = -1;
        ExtSingleType(Type pre, Symbol sym) {
            super(pre, sym);
        }
        public Type singleDeref() {
            if (definedId != Global.instance.currentPhase.id) {
                definedId = Global.instance.currentPhase.id;
                tp = pre.memberType(sym).resultType();
            }
            return tp;
        }
    }

    static class ExtTypeRef extends TypeRef {
        ExtTypeRef(Type pre, Symbol sym, Type[] args) {
            super(pre, sym, args);
        }
    }

    private static final class ExtCompoundType extends CompoundType {
        private final Symbol clasz;
        public ExtCompoundType(Symbol owner, Type[] parts, Scope members) {
            super(parts, members);
            this.clasz = owner.newCompoundClass(this);
	    assert !owner.isPackageClass() : ArrayApply.toString(parts);
        }
        public ExtCompoundType(Type[] parts, Scope members, Symbol clasz) {
            super(parts, members);
            this.clasz = clasz;
        }
        public Symbol symbol() {
            return clasz;
        }
    }

// Access methods ---------------------------------------------------------------

    /** If this is a thistype, named type, applied type, singleton type, or compound type,
     *  its symbol, otherwise Symbol.NONE.
     */
    public Symbol symbol() {
        switch (this) {
        case ThisType(Symbol sym):
            return sym;
        case TypeRef(_, Symbol sym, _):
            return sym;
        case SingleType(_, Symbol sym):
            return sym;
        case ConstantType(Type base, _):
            return base.symbol();
        case TypeVar(Type origin, _):
            return origin.symbol();
        case CompoundType(_, _):
            // overridden in ExtCompoundType
            throw new ApplicationError();
        default:
            return Symbol.NONE;
        }
    }

    public static Symbol[] symbol(Type[] tps) {
        Symbol[] syms = new Symbol[tps.length];
        for (int i = 0; i < syms.length; i++)
            syms[i] = tps[i].symbol();
        return syms;
    }

    /** If this is a reference to a type constructor, add its
     *  type parameters as arguments
     */
    public Type withDefaultArgs() {
        switch (this) {
        case TypeRef(Type pre, Symbol sym, Type[] args):
            if (args.length == 0 && sym.typeParams().length != 0)
                return Type.typeRef(pre, sym, Symbol.type(sym.typeParams()));
        }
        return this;
    }

    /** The upper bound of this type. Returns always a TypeRef whose
     * symbol is a class.
     */
    public Type bound() {
        switch (unalias()) {
        case TypeRef(Type pre, Symbol sym, _):
            if (sym.kind == TYPE) return pre.memberInfo(sym).bound();
            assert sym.isClass() : Debug.show(sym) + " -- " + this;
            return this;
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().bound();
        case TypeVar(Type origin, Constraint constr):
            if (constr.inst != NoType) return constr.inst.bound();
            else return this;
        default:
            throw Debug.abort("illegal case", this);
        }
    }

    /** If this type is a thistype or singleton type, its type,
     *  otherwise the type itself.
     */
    public Type singleDeref() {
        switch (this) {
        case ThisType(Symbol sym):
            return sym.typeOfThis();
        case SingleType(Type pre, Symbol sym):
            // overridden in ExtSingleType
            throw new ApplicationError();
        case ConstantType(Type base, _):
            return base;
        case TypeVar(Type origin, Constraint constr):
            if (constr.inst != NoType) return constr.inst.singleDeref();
            else return this;
        default:
            return this;
        }
    }

    /** If this type is a thistype or singleton type, its underlying object type,
     *  otherwise the type itself.
     */
    public Type widen() {
        Type tp = singleDeref();
        switch (tp) {
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return tp.widen();
        default:
            return tp;
        }
    }

    private static Map widenMap = new Map() {
            public Type apply(Type t) {
                return t.widen();
            }
        };

    public static Type[] widen(Type[] tps) {
        return widenMap.map(tps);
    }

    /** The thistype or singleton type corresponding to values of this type.
      */
    public Type narrow() {
        switch (unalias()) {
        case TypeRef(Type pre, Symbol sym, Type[] args):
            if (sym.kind == CLASS) return sym.thisType();
            else return ThisType(sym);
        case CompoundType(_, _):
            return symbol().thisType();
        default:
            return this;
        }
    }

    /** If this type is a constant type, its underlying basetype;
     *  otherwise the type itself
     */
    public Type deconst() {
        switch (this) {
        case ConstantType(Type base, _):
            return base;
        default:
            return this;
        }
    }

    /** If this type is a parameterless method, its underlying resulttype;
     *  otherwise the type itself
     */
    public Type derefDef() {
        switch (this) {
        case PolyType(Symbol[] tparams, Type restp):
            if (tparams.length == 0) return restp;
        }
        return this;
    }

    /** The lower approximation of this type (which must be a typeref)
     */
    public Type loBound() {
        switch (unalias()) {
        case TypeRef(Type pre, Symbol sym, Type[] args):
            Type lb = Global.instance.definitions.ALL_TYPE();
            if (sym.kind == TYPE) {
                lb = pre.memberLoBound(sym);
            }
            if (lb.symbol() == Global.instance.definitions.ALL_CLASS &&
                this.symbol() != Global.instance.definitions.ALL_CLASS &&
                this.isSubType(Global.instance.definitions.ANYREF_TYPE())) {
                lb = Global.instance.definitions.ALLREF_TYPE();
            }
            return lb;
        default:
            throw new ApplicationError();
        }
    }

    /** If this is a this-type, named-type, applied type or single-type, its prefix,
     *  otherwise NoType.
     */
    public Type prefix() {
        switch (this) {
        case ThisType(Symbol sym): return sym.owner().thisType();
        case TypeRef(Type pre, _, _): return pre;
        case SingleType(Type pre, _): return pre;
        case TypeVar(Type origin, Constraint constr):
            if (constr.inst != NoType) return constr.inst.prefix();
            else return NoType;
        default: return NoType;
        }
    }

   /** Get all type arguments of this type.
    */
    public Type[] typeArgs() {
        switch (unalias()) {
        case TypeRef(_, _, Type[] args):
            return args;
        default:
            return Type.EMPTY_ARRAY;
        }
    }

    /** Get type of `this' symbol corresponding to this type, extend
     *  homomorphically to function types and poly types.
     */
    public Type instanceType() {
        switch (unalias()) {
        case TypeRef(Type pre, Symbol sym, Type[] args):
            if (sym != sym.thisSym())
                return sym.typeOfThis()
                    .asSeenFrom(pre, sym.owner())
                    .subst(sym.typeParams(), args);
            break;
        case MethodType(Symbol[] params, Type restp):
            Type restp1 = restp.instanceType();
            if (restp1 != restp)
                return MethodType(params, restp1);
            break;
        case PolyType(Symbol[] tparams, Type restp):
            Type restp1 = restp.instanceType();
            if (restp1 != restp)
                return PolyType(tparams, restp1);
            break;
        }
        return this;
    }

    /** Remove all aliases
     */
    public Type unalias() {
        Type result = unalias(0);//debug
        //if (this != result) System.out.println(this + " ==> " + result);//DEBUG
        return result;
    }

    private Type unalias(int n) {
        if (n == 100)
            throw new Type.Error("alias chain too long (recursive type alias?): " + this);
        switch (this) {
        case TypeVar(Type origin, Constraint constr):
            if (constr.inst != NoType) return constr.inst.unalias(n + 1);
            else return this;
        }
        return this;
    }

    /** The (prefix/argument-adapted) parents of this type.
     */
    public Type[] parents() {
        switch (unalias()) {
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().parents();
        case TypeRef(Type pre, Symbol sym, Type[] args):
            if (sym.kind == CLASS) {
                assert sym.typeParams().length == args.length : sym + " " + ArrayApply.toString(args) + " " + sym.primaryConstructor().info();//debug
                return subst(asSeenFrom(sym.info().parents(), pre, sym.owner()),
                             sym.typeParams(), args);
            } else {
                return new Type[]{sym.info().asSeenFrom(pre, sym.owner())};
            }
        case CompoundType(Type[] parts, _):
            return parts;
        default:
            return Type.EMPTY_ARRAY;
        }
    }

    /** Get type parameters of method type (a PolyType or MethodType)
     * or EMPTY_ARRAY if method type is not polymorphic.
     */
    public Symbol[] typeParams() {
        switch (this) {
        case PolyType(Symbol[] tparams, _):
            return tparams;
        case MethodType(Symbol[] vparams, _):
            return Symbol.EMPTY_ARRAY;
        case TypeRef(_, Symbol sym, Type[] args):
            if (args.length == 0) return sym.typeParams();
            else return Symbol.EMPTY_ARRAY;
        default:
            return Symbol.EMPTY_ARRAY;
        }
    }

    /** Get value parameters of method type (a PolyType or MethodType)
     * or EMPTY_ARRAY if method type has no value parameter section.
     */
    public Symbol[] valueParams() {
        return valueParams(false);
    }
    private Symbol[] valueParams(boolean ok) {
        switch (this) {
        case PolyType(_, Type result):
            return result.valueParams(true);
        case MethodType(Symbol[] vparams, _):
            return vparams;
        default:
            if (ok) return Symbol.EMPTY_ARRAY;
            throw Debug.abort("illegal case", this);
        }
    }

    /** If this type is a (possibly polymorphic) method type, its result type
     *  after applying all method argument sections,
     *  otherwise the type itself.
     */
    public Type resultType() {
        switch (this) {
        case PolyType(_, Type tpe):
            return tpe.resultType();
        case MethodType(_, Type tpe):
            return tpe.resultType();
        default:
            return this;
        }
    }

    /** The number of value parameter sections of this type.
     */
    public int paramSectionCount() {
        switch (this) {
        case PolyType(_, Type restpe):
            return restpe.paramSectionCount();
        case MethodType(_, Type restpe):
            return restpe.paramSectionCount() + 1;
        default: return 0;
        }
    }

    /** The first parameter section of this type.
     */
    public Symbol[] firstParams() {
        switch (this) {
        case PolyType(_, Type restpe):
            return restpe.firstParams();
        case MethodType(Symbol[] params, _):
            return params;
        default: return Symbol.EMPTY_ARRAY;
        }
    }

    /** If this type is overloaded, its alternative types,
     *  otherwise an array consisting of this type itself.
     */
    public Type[] alternativeTypes() {
        switch (this) {
        case OverloadedType(_, Type[] alttypes):
            return alttypes;
        default:
            return new Type[]{this};
        }
    }

    /** If this type is overloaded, its alternative symbols,
     *  otherwise an empty array.
     */
    public Symbol[] alternativeSymbols() {
        switch (this) {
        case OverloadedType(Symbol[] alts, _):
            return alts;
        default:
            return Symbol.EMPTY_ARRAY;
        }
    }

// Tests --------------------------------------------------------------------

    /** Is this type a an error type?
     */
    public boolean isError() {
        switch (this) {
        case ErrorType:
            return true;
        case ThisType(Symbol clasz):
            return clasz.isError();
        case SingleType(_, Symbol symbol):
            return symbol.isError();
        case TypeRef(_, Symbol symbol, _):
            return symbol.isError();
        case CompoundType(Type[] parts, Scope members):
            return symbol().isError();
        default:
            return false;
        }
    }

    /** Is this type a this type or singleton type?
     */
    public boolean isStable() {
        switch (unalias()) {
        case NoPrefix:
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return true;
        case TypeRef(_, Symbol sym, _):
            if (sym.isParameter() && sym.isSynthetic() && sym.hasStableFlag()) return true;
            return false;
        default:
            return false;
        }
    }

    /** Is this type a legal prefix?
     */
    public boolean isLegalPrefix() {
        switch (unalias()) {
        case NoPrefix:
        case ThisType(_):
        case SingleType(_, _):
            return true;
        case TypeRef(_, Symbol sym, _):
            if (sym.isParameter() && sym.isSynthetic()) return true;
	    return false;
	    /*
            return sym.kind == CLASS &&
                ((sym.flags & JAVA) != 0 ||
                 (sym.flags & (TRAIT | ABSTRACT)) == 0);
	    */
        default:
            return false;
        }
    }

    /** Is this type a reference to an object type?
     *  todo: replace by this.isSubType(global.definitions.ANY_TYPE())?
     */
    public boolean isObjectType() {
        switch (unalias()) {
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
        case CompoundType(_, _):
        case TypeRef(_, _, _):
            return true;
        default:
            return false;
        }
    }

    /** Is this type of the form scala.FunctionN[T_1, ..., T_n, +T] or
     *  scala.AnyRef with scala.FunctionN[T_1, ..., T_n, +T] or
     *  java.lang.Object with scala.FunctionN[T_1, ..., T_n, +T]?
     */
    public boolean isFunctionType() {
        switch (this) {
        case TypeRef(Type pre, Symbol sym, Type[] args):
            Definitions definitions = Global.instance.definitions;
            return args.length > 0
                && args.length <= definitions.FUNCTION_COUNT
                && sym == definitions.FUNCTION_CLASS[args.length - 1];
        case CompoundType(Type[] parents, Scope members):
            Definitions definitions = Global.instance.definitions;
            return members.isEmpty() &&
                parents.length == 2 &&
                (parents[0].symbol() == definitions.OBJECT_CLASS ||
		 parents[0].symbol() == definitions.ANYREF_CLASS) &&
                parents[1].isFunctionType();
        }
        return false;
    }

    /** Is this a polymorphic method type?
     */
    public boolean isPolymorphic() {
        return typeParams().length > 0;
    }

    /** Is this a parameterized or polymorphic method type?
     */
    public boolean isParameterized() {
        switch (this) {
        case MethodType(_, _): return true;
        default: return isPolymorphic();
        }
    }

// Members and Lookup -------------------------------------------------------

    /** Get the scope containing the local members of this type.
     *  Symbols in this scope are not prefix-adapted!
     */
    public Scope members() {
        switch (this) {
        case ErrorType:
            return new Scope();
        case TypeRef(_, Symbol sym, _):
            return sym.info().members();
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().members();
        case CompoundType(Type[] basetypes, Scope members):
            return members;
        default:
            return Scope.EMPTY;
        }
    }

    /** Lookup symbol with given name among all local and inherited members
     *  of this type; return Symbol.NONE if not found.
     */
    public Symbol lookup(Name name) {
        switch (this) {
        case ErrorType:
            return new ErrorScope(Symbol.NONE).lookup(name);
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().lookup(name);
        case TypeRef(_, Symbol sym, _):
            return sym.info().lookup(name);
        case CompoundType(Type[] parts, Scope members):
            Symbol sym = members.lookup(name);
            if (sym.kind != NONE) return sym;
            else return lookupNonPrivate(name);
        default:
            return Symbol.NONE;
        }
    }

    /** Lookup non-private symbol with given name among all local and
     *  inherited members of this type; return Symbol.NONE if not found.
     */
    public Symbol lookupNonPrivate(Name name) {
        switch (this) {
        case ErrorType:
            return new ErrorScope(Symbol.NONE).lookup(name);
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().lookupNonPrivate(name);
        case TypeRef(_, Symbol sym, _):
            return sym.info().lookupNonPrivate(name);
        case CompoundType(Type[] parts, Scope members):
            Symbol sym = members.lookup(name);
            if (sym.kind != NONE && (sym.flags & PRIVATE) == 0) return sym;
	    else return lookupNonPrivate(parts, name);
        default:
            return Symbol.NONE;
        }
    }

    public static Symbol lookupNonPrivate(Type[] parts, Name name) {
	// search base types in reverse; non-abstract members
	// take precedence over abstract ones.
	int i = parts.length;
	Symbol sym = Symbol.NONE;
	while (i > 0) {
	    i--;
	    Symbol sym1 = parts[i].lookupNonPrivate(name);
	    if (sym1.kind != NONE &&
		(sym.kind == NONE
		 ||
		 (sym.flags & DEFERRED) != 0 &&
		 (sym1.flags & DEFERRED) == 0
		 ||
		 (sym.flags & DEFERRED) == (sym1.flags & DEFERRED) &&
		 sym1.owner().isSubClass(sym.owner())))
		sym = sym1;
	}
	return sym;
    }

    /**
     * Looks up in the current type a symbol with the same name as the
     * given symbol and whose type (as seen from the given prefix) is
     * in the given relation to the type (as seen from the given
     * prefix) of the given symbol. If no such symbol is found,
     * returns NONE. Note that in some cases, the returned symbol may
     * be equal to the given one. The main purpose of this method is
     * look up overridden and overriding symbols.
     */
    public Symbol lookup(Symbol sym, Type pre, Relation relation) {
        assert !sym.isOverloaded(): Debug.show(sym);
        if (sym.isPrivate() || sym.isInitializer())
            return symbol().isSubClass(sym.owner()) ? sym : Symbol.NONE;
        Type symtype = pre.memberType(sym).derefDef();
        Symbol[] classes = classes();
        Symbol deferred = null;
        for (int i = 0; i < classes.length; i++) {
            if (deferred != null && deferred.isSubClass(classes[i])) continue;
            Symbol sym1 = classes[i].members().lookup(sym.name);
            switch (sym1.type()) {
            case NoType:
            case ErrorType:
                continue;
            case OverloadedType(Symbol[] alts, _):
                for (int j = 0; j < alts.length; j++)
                    if (areRelated(sym, symtype, relation, pre,alts[j],false)){
                        if (!alts[j].isDeferred()) return alts[j];
                        if (deferred == null) deferred = alts[j];
                    }
                continue;
            default:
                if (areRelated(sym, symtype, relation, pre, sym1, true)) {
                    if (!sym1.isDeferred()) return sym1;
                    if (deferred == null) deferred = sym1;
                }
                continue;
            }
        }
        return deferred == null ? Symbol.NONE : deferred;
    }
    //where
    private static boolean areRelated(
        Symbol sym, Type symtype, Relation relation, Type pre, Symbol sym1,
        boolean warn)
    {
        if (sym == sym1) return true;
        if (sym1.isPrivate() || sym1.isInitializer()) return false;
//         System.out.println("Is 'sym1' " + relation + " 'sym' in 'pre' ?"
//             + "\n  sym      : " + Debug.show(sym)
//             + "\n  sym1     : " + Debug.show(sym1)
//             + "\n  sym .type: " + sym.type()
//             + "\n  sym1.type: " + sym1.type()
//             + "\n  pre      : " + pre
//         );//DEBUG
        Type sym1type = pre.memberType(sym1).derefDef();
        if (sym1.isJava()) symtype = symtype.objParamToAny();
        if (sym1type.compareTo(symtype, relation)) return true;
        if (warn && Global.instance.debug) System.out.println(
            "'sym1' is not " + relation + " 'sym' in 'pre'"
            + "\n  sym      : " + Debug.show(sym)
            + "\n  sym1     : " + Debug.show(sym1)
            + "\n  sym .type: " + sym.type()
            + "\n  sym1.type: " + sym1.type()
            + "\n  pre      : " + pre
            + "\nsince 'sym1type' " + relation.toString(true) + " 'symtype'"
            + "\n  symtype  : " + symtype
            + "\n  sym1type : " + sym1type
        );//DEBUG
        return false;
    }
    private Symbol[] classes() {
        switch (this) {
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().classes();
        case TypeRef(_, Symbol sym, _):
            return sym.info().classes();
        case CompoundType(Type[] parts, Scope members):
            return symbol(symbol().closure());
        default:
            return Symbol.EMPTY_ARRAY;
        }
    }
    static private Map objToAnyMap = new Map() {
	public Type apply(Type t) {
	    if (t.symbol() == Global.instance.definitions.OBJECT_CLASS)
		return Global.instance.definitions.ANY_TYPE();
	    else return t;
	}
    };

    private Type objParamToAny() {
	switch (this) {
	case MethodType(Symbol[] params, Type restp):
	    Symbol[] params1 = objToAnyMap.map(params);
	    if (params1 == params) return this;
	    else return MethodType(params1, restp);
	default:
	    return this;
	}
    }

// Set Owner ------------------------------------------------------------------

    public Type setOwner(Symbol owner) {
        switch (this) {
        case PolyType(Symbol[] tparams, Type restpe):
            Type restpe1 = restpe.setOwner(owner);
            if (restpe1 == restpe) return this;
            else return Type.PolyType(tparams, restpe1);
        case MethodType(Symbol[] params, Type restpe):
            Symbol[] params1 = params;
            if (params.length > 0 &&
                params[0].owner() != owner && params[0].owner() != Symbol.NONE) {
                params1 = new Symbol[params.length];
                for (int i = 0; i < params.length; i++)
                    params1[i] = params[i].cloneSymbol();
            }
            for (int i = 0; i < params.length; i++)
                params1[i].setOwner(owner);
            Type restpe1 = restpe.setOwner(owner);
            if (params1 == params && restpe1 == restpe) return this;
            else return Type.MethodType(params1, restpe1);
        default:
            return this;
        }
    }

// Maps --------------------------------------------------------------------------

    /** The type of type-to-type functions.
     */
    public abstract static class Map {

        public abstract Type apply(Type t);

        /**
         * This method assumes that all symbols in MethodTypes and
         * PolyTypes have already been cloned.
         */
        public Type applyParams(Type type) {
            switch (type) {

            case MethodType(Symbol[] vparams, Type result):
                map(vparams, true);
                Type result1 = applyParams(result);
                return result == result1 ? type : MethodType(vparams, result1);

            case PolyType(Symbol[] tparams, Type result):
                map(tparams, true);
                Type result1 = applyParams(result);
                return result == result1 ? type : PolyType(tparams, result1);

            default:
                return apply(type);
            }
        }

        /** Apply map to all top-level components of this type.
         */
        public Type map(Type tp) {
            switch (tp) {
            case ErrorType:
            case AnyType:
            case NoType:
            case NoPrefix:
            case UnboxedType(_):
            case TypeVar(_, _):
            case ThisType(_):
                return tp;
            case TypeRef(Type pre, Symbol sym, Type[] args):
                Type pre1 = apply(pre);
                Type[] args1 = map(args);
                if (pre1 == pre && args1 == args) return tp;
                else return typeRef(pre1, sym, args1);
            case SingleType(Type pre, Symbol sym):
                Type pre1 = apply(pre);
                if (pre1 == pre) return tp;
                else return singleType(pre1, sym);
            case ConstantType(Type base, AConstant value):
                Type base1 = apply(base);
                if (base1 == base) return tp;
                else return new ConstantType(base1, value);
            case CompoundType(Type[] parts, Scope members):
                Type[] parts1 = map(parts);
                Scope members1 = map(members);
                if (parts1 == parts && members1 == members) {
                    return tp;
                } else if (members1 == members && !tp.symbol().isCompoundSym()) {
                    return compoundType(parts1, members, tp.symbol());
                } else {
                    Scope members2 = new Scope();
                    //Type tp1 = compoundType(parts1, members2);
                    Type tp1 = (tp.symbol().isCompoundSym()) ? compoundTypeWithOwner(tp.symbol().owner(), parts1, members2)
                        : compoundType(parts1, members2, tp.symbol());
                    Symbol[] syms1 = members1.elements();
                    Symbol[] syms2 = new Symbol[syms1.length];
                    for (int i = 0; i < syms2.length; i++) {
                        syms2[i] = syms1[i].cloneSymbol(tp1.symbol());
                    }
                    for (int i = 0; i < syms2.length; i++) {
                        syms2[i].setInfo(syms1[i].info().subst(syms1, syms2));
                        if (syms2[i].kind == TYPE) {
                            syms2[i].setLoBound(syms1[i].loBound().subst(syms1, syms2));
                            syms2[i].setVuBound(syms1[i].vuBound().subst(syms1, syms2));
			}
                    }
                    for (int i = 0; i < syms2.length; i++) {
                        members2.enter(syms2[i]);
                    }
                    return tp1;
                }

            case MethodType(Symbol[] vparams, Type result):
                Symbol[] vparams1 = map(vparams);
                Type result1 = apply(result);
                if (vparams1 == vparams && result1 == result) return tp;
                else return MethodType(vparams1, result1);
            case PolyType(Symbol[] tparams, Type result):
                Symbol[] tparams1 = map(tparams);
                Type result1 = apply(result);
                if (tparams1 != tparams) result1 = result1.subst(tparams, tparams1);
                if (tparams1 == tparams && result1 == result) return tp;
                else return PolyType(tparams1, result1);
            case OverloadedType(Symbol[] alts, Type[] alttypes):
                Type[] alttypes1 = map(alttypes);
                if (alttypes1 == alttypes) return tp;
                else return OverloadedType(alts, alttypes1);
            case UnboxedArrayType(Type elemtp):
                Type elemtp1 = apply(elemtp);
                if (elemtp1 == elemtp) return tp;
                else return UnboxedArrayType(elemtp1);
            default:
                throw new ApplicationError(tp + " " + tp.symbol());
            }
        }

        public final Symbol map(Symbol sym) {
            return map(sym, false);
        }
        public Symbol map(Symbol sym, boolean dontClone) {
            Type tp = sym.info();
            Type tp1 = apply(tp);
            if (tp != tp1) {
                if (!dontClone) sym = sym.cloneSymbol();
                sym.setInfo(tp1);
                dontClone = true;
            }
            if (sym.kind == TYPE) {
                Type lb = sym.loBound();
                Type lb1 = apply(lb);
                if (lb != lb1) {
                    if (!dontClone) sym = sym.cloneSymbol();
                    sym.setLoBound(lb1);
                }
                Type vb = sym.vuBound();
                Type vb1 = apply(vb);
                if (vb != vb1) {
                    if (!dontClone) sym = sym.cloneSymbol();
                    sym.setVuBound(vb1);
                }
            }
            return sym;
        }

        public Type[] map(Type[] tps) {
            Type[] tps1 = tps;
            for (int i = 0; i < tps.length; i++) {
                Type tp = tps[i];
                Type tp1 = apply(tp);
                if (tp1 != tp && tps1 == tps) {
                    tps1 = new Type[tps.length];
                    System.arraycopy(tps, 0, tps1, 0, i);
                }
                tps1[i] = tp1;
            }
            return tps1;
        }

        /** Apply map to all elements of this array of symbols,
         *  preserving recursive references to symbols in the array.
         */
        public final Symbol[] map(Symbol[] syms) {
            return map(syms, false);
        }
        public Symbol[] map(Symbol[] syms, boolean dontClone) {
            Symbol[] syms1 = syms;
            for (int i = 0; i < syms.length; i++) {
                Symbol sym = syms[i];
                Symbol sym1 = map(sym, dontClone);
                if (sym != sym1 && syms1 == syms) {
                    syms1 = new Symbol[syms.length];
                    System.arraycopy(syms, 0, syms1, 0, i);
                }
                syms1[i] = sym1;
            }
            if (syms1 != syms) {
                for (int i = 0; i < syms1.length; i++) {
                    if (syms1[i] == syms[i])
                        syms1[i] = syms[i].cloneSymbol();
                }
                new SubstSymMap(syms, syms1).map(syms1, true);
            }
            return syms1;
        }

        /** Apply map to all elements of this array of this scope.
         */
        public Scope map(Scope s) {
            Symbol[] members = s.elements();
            Symbol[] members1 = map(members);
            if (members == members1) return s;
            else return new Scope(members1);
        }
    }

    public abstract static class MapOnlyTypes extends Map {
        public Symbol map(Symbol sym, boolean dontClone) { return sym; }
        public Symbol[] map(Symbol[] syms, boolean dontClone) { return syms; }
        public Scope map(Scope s) { return s; }
    }

    public static final Map IdMap = new Map() {
        public Type apply(Type tp) { return tp; }
        public Type applyParams(Type tp) { return tp; }
        public Type map(Type tp) { return tp; }
        public Symbol map(Symbol sym, boolean dontClone) { return sym; }
        public Type[] map(Type[] tps) { return tps; }
        public Symbol[] map(Symbol[] syms, boolean dontClone) { return syms; }
        public Scope map(Scope scope) { return scope; }
    };

// baseType and asSeenFrom --------------------------------------------------------

    /** Return the base type of this type whose symbol is `clazz', or NoType, if
     *  such a type does not exist.
     */
    public Type baseType(Symbol clazz) {
        //System.out.println(this + ".baseType(" + clazz + ")");//DEBUG
        switch (this) {
        case ErrorType:
            return ErrorType;

        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().baseType(clazz);

        case TypeRef(Type pre, Symbol sym, Type[] args):
            if (sym == clazz)
                return this;
            else if (sym.kind == TYPE)
                return sym.info()
                    .asSeenFrom(pre, sym.owner()).baseType(clazz);
            else if (sym.kind == ALIAS)
                return Type.NoType;
            else if (clazz.isCompoundSym())
                return NoType;
            else {
                return sym.baseType(clazz)
                    .asSeenFrom(pre, sym.owner())
                    .subst(sym.typeParams(), args);
            }

        case CompoundType(Type[] parts, _):
            for (int i = parts.length - 1; i >= 0; i--) {
                Type result = parts[i].baseType(clazz);
                if (result != NoType) return result;
            }
            break;

        case UnboxedArrayType(_):
            if (clazz == Global.instance.definitions.ANY_CLASS ||
                clazz == Global.instance.definitions.ANYREF_CLASS)
                return clazz.type();
        }
        return NoType;
    }

    /** A map to implement `asSeenFrom'.
     */
    static class AsSeenFromMap extends Map {

        private final Type pre;
        private final Symbol clazz;

        AsSeenFromMap(Type pre, Symbol clazz) {
            this.pre = pre;
            this.clazz = clazz;
        }

        public Type apply(Type type) {
            //System.out.println(type + " as seen from " + pre + "," + clazz);//DEBUG
            if (pre == NoType || clazz.kind != CLASS) return type;
            switch (type) {
            case ThisType(Symbol sym):
                return type.toPrefix(sym, pre, clazz);
            case TypeRef(Type prefix, Symbol sym, Type[] args):
                if (sym.owner().isPrimaryConstructor()) {
                    assert sym.kind == TYPE;
                    return type.toInstance(sym, pre, clazz);
                }
                return map(type);

            case SingleType(Type prefix, Symbol sym):
                try {
                    return map(type);
                } catch (Type.Malformed ex) {}
                return apply(type.singleDeref());

            default:
                return map(type);
            }
        }
    }
    //where
        Type toInstance(Symbol sym, Type pre, Symbol clazz) {
            if (pre == NoType || clazz.kind != CLASS)
                return this;
            Symbol ownclass = sym.owner().constructorClass();
            if (ownclass == clazz &&
                pre.widen().symbol().isSubClass(ownclass)) {
                switch (pre.baseType(ownclass)) {
                case TypeRef(_, Symbol basesym, Type[] baseargs):
                    Symbol[] baseparams = basesym.typeParams();
                    for (int i = 0; i < baseparams.length; i++) {
                        if (sym == baseparams[i]) return baseargs[i];
                    }
                    //System.out.println(sym + " " + basesym + " " + ArrayApply.toString(baseparams));//DEBUG
                    break;
                case ErrorType:
                    return ErrorType;
                }
                throw new ApplicationError(
                    this + " in " + ownclass + " cannot be instantiated from " + pre.widen()
                    );
            } else {
                return toInstance(sym, pre.baseType(clazz).prefix(), clazz.owner());
            }
        }

        Type toPrefix(Symbol sym, Type pre, Symbol clazz) {
            //System.out.println(this + ".toPrefix(" + sym + "," + pre + "," + clazz + ")");//DEBUG
            if (pre == NoType || clazz.kind != CLASS)
                return this;
            else if (sym.isSubClass(clazz) &&
                     pre.widen().symbol().isSubClass(sym))
                return pre;
            else
                return toPrefix(sym, pre.baseType(clazz).prefix(), clazz.owner());
        }

    /** This type as seen from prefix `pre' and class `clazz'. This means:
     *  Replace all thistypes of `clazz' or one of its subclasses by `pre'
     *  and instantiate all parameters by arguments of `pre'.
     *  Proceed analogously for thistypes referring to outer classes.
     */
    public Type asSeenFrom(Type pre, Symbol clazz) {
        //System.out.println("computing asseenfrom of " + this + " with " + pre + "," + clazz);//DEBUG
        return new AsSeenFromMap(pre, clazz).apply(this);
    }

    /** Types `these' as seen from prefix `pre' and class `clazz'.
     */
    public static Type[] asSeenFrom(Type[] these, Type pre, Symbol clazz) {
        return new AsSeenFromMap(pre, clazz).map(these);
    }

    /** The info of `sym', seen as a member of this type.
     */
    public Type memberInfo(Symbol sym) {
        return sym.info().asSeenFrom(this, sym.owner());
    }

    /** The type of `sym', seen as a member of this type.
     */
    public Type memberType(Symbol sym) {
        return sym.type().asSeenFrom(this, sym.owner());
    }

    /** The stabilized type of `sym', seen as a member of this type.
     */
    public Type memberStabilizedType(Symbol sym) {
        return sym.isStable() && this.isStable()
            ? Type.singleTypeMethod(this, sym)
            : this.memberType(sym);
    }

    /** The low bound of `sym', seen as a member of this type.
     */
    public Type memberLoBound(Symbol sym) {
        return sym.loBound().asSeenFrom(this, sym.owner());
    }

    /** The view bound of `sym', seen as a member of this type.
     */
    public Type memberVuBound(Symbol sym) {
        return sym.vuBound().asSeenFrom(this, sym.owner());
    }

// Substitutions ---------------------------------------------------------------

    /** A common map superclass for symbol/symbol and type/symbol substitutions.
     */
    public static abstract class SubstMap extends Map {
        private Symbol[] from;

        SubstMap(Symbol[] from) {
            this.from = from;
        }

        public boolean matches(Symbol sym1, Symbol sym2) {
            return sym1 == sym2;
        }

        /** Produce replacement type
         *  @param i          The index in `from' of the symbol to be replaced.
         *  @param fromtp     The type referring to this symbol.
         */
        protected abstract Type replacement(int i, Type fromtp);

        /** Produce new substitution where some symbols are excluded.
         *  @param newfrom    The new array of from symbols (without excluded syms)
         *  @param excluded   The array of excluded sysmbols
         */
        protected abstract SubstMap exclude(Symbol[] newfrom, Symbol[] excluded);

        public Type apply(Type t) {
            switch (t) {
            case TypeRef(NoPrefix, Symbol sym, Type[] args):
                for (int i = 0; i < from.length; i++) {
                    if (matches(sym, from[i])) return replacement(i, t);
                }
                break;
            case SingleType(NoPrefix, Symbol sym):
                for (int i = 0; i < from.length; i++) {
                    if (matches(sym, from[i])) return replacement(i, t);
                }
                break;
            case PolyType(Symbol[] tparams, Type result):
                Symbol[] from1 = excludeSyms(from, tparams, from);
                if (from1 != from) {
                    SubstMap f = exclude(from1, tparams);
                    Symbol[] tparams1 = f.map(tparams);
                    Type result1 = f.apply(result);
                    if (tparams1 != tparams)
                        result1 = result1.subst(tparams, tparams1);
                    if (tparams1 == tparams && result1 == result) return t;
                    else return PolyType(tparams1, result1);
                }
            }
            return map(t);
        }
        //where
        private boolean contains1(Symbol[] syms, Symbol sym) {
            int i = 0;
            while (i < syms.length && syms[i] != sym) i++;
            return i < syms.length;
        }

        private int nCommon(Symbol[] from, Symbol[] tparams) {
            int cnt = 0;
            for (int i = 0; i < from.length; i++) {
                if (contains1(tparams, from[i])) cnt++;
            }
            return cnt;
        }

        private Symbol[] excludeSyms(Symbol[] from, Symbol[] tparams, Symbol[] syms) {
            int n = nCommon(from, tparams);
            if (n == 0) {
                return syms;
            } else {
                Symbol[] syms1 = new Symbol[syms.length - n];
                int j = 0;
                for (int i = 0; i < from.length; i++) {
                    if (!contains1(tparams, from[i])) syms1[j++] = syms[i];
                }
                return syms1;
            }
        }

        private Type[] excludeTypes(Symbol[] from, Symbol[] tparams, Type[] types) {
            int n = nCommon(from, tparams);
            if (n == 0) {
                return types;
            } else {
                Type[] types1 = new Type[types.length - n];
                int j = 0;
                for (int i = 0; i < from.length; i++) {
                    if (!contains1(tparams, from[i])) types1[j++] = types[i];
                }
                return types1;
            }
        }
    }

    /** A map for symbol/symbol substitutions
     */
    public static class SubstSymMap extends SubstMap {
        Symbol[] to;
        protected SubstSymMap(Symbol[] from, Symbol[] to) {
            super(from);
            this.to = to;
        }
        protected Type replacement(int i, Type fromtp) {
            switch (fromtp) {
            case TypeRef(Type pre, Symbol sym, Type[] args):
                return typeRef(pre, to[i], args);
            case SingleType(Type pre, Symbol sym):
                return singleType(pre, to[i]);
            default:
                throw new ApplicationError();
            }
        }
        protected SubstMap exclude(Symbol[] newfrom, Symbol[] excluded) {
            return new SubstSymMap(newfrom, excludeSyms(from, excluded, to));
        }
    }

    /** A map for type/symbol substitutions
     */
    public static class SubstTypeMap extends SubstMap {
        Type[] to;
        public SubstTypeMap(Symbol[] from, Type[] to) {
            super(from);
            this.to = to;
        }
        public Type replacement(int i, Type fromtp) {
            return to[i];
        }
        public SubstMap exclude(Symbol[] newfrom, Symbol[] excluded) {
            return new SubstTypeMap(newfrom, excludeTypes(from, excluded, to));
        }
    }


    /** A map for symbol/symbol substitutions which, instead of
     * cloning parameters, updates their symbol's types.
     */
    public static class UpdateSubstSymMap extends SubstSymMap {
        protected UpdateSubstSymMap(Symbol[] from, Symbol[] to) {
            super(from, to);
        }
        public Type apply(Type t) {
            switch (t) {
            case PolyType(Symbol[] params, Type result):
                // !!! Also update loBounds? How? loBound can only be set!
                for (int i = 0; i < params.length; i++) {
                    Type tp = params[i].nextType();
                    Type tp1 = apply(tp);
                    if (tp != tp1) params[i].updateInfo(tp1);
                }
                Type result1 = apply(result);
                if (result1 == result) return t;
                else return Type.PolyType(params, result1);
            case MethodType(Symbol[] params, Type result):
                for (int i = 0; i < params.length; i++) {
                    Type tp = params[i].nextType();
                    Type tp1 = apply(tp);
                    if (tp != tp1) params[i].updateInfo(tp1);
                }
                Type result1 = apply(result);
                if (result1 == result) return t;
                else return Type.MethodType(params, result1);
            default:
                return super.apply(t);
            }
        }
        public Symbol map(Symbol sym, boolean dontClone) { return sym; }
        public Symbol[] map(Symbol[] syms, boolean dontClone) { return syms; }
        public Scope map(Scope s) { return s; }
    }

    /** Returns the given non-updating symbol/symbol substitution. */
    public static Map getSubst(Symbol[] from, Symbol[] to) {
        return getSubst(from, to, false);
    }

    /** Returns the given (updating?) symbol/symbol substitution. */
    public static Map getSubst(Symbol[] from, Symbol[] to, boolean update) {
        if (from.length == 0 && to.length == 0) return IdMap;
        if (update) return new UpdateSubstSymMap(from, to);
        return new SubstSymMap(from, to);
    }

    /** Returns the given non-updating symbol/type substitution. */
    public static Map getSubst(Symbol[] from, Type[] to) {
        if (from.length == 0 && to.length == 0) return IdMap;
        return new SubstTypeMap(from, to);
    }

    /** Substitute symbols `to' for occurrences of symbols `from' in this type.
     */
    public Type subst(Symbol[] from, Symbol[] to) {
        if (to.length != 0 && from != to) {//!!!
            assert from.length == to.length
                : this + ": " + from.length + " != " + to.length;
            return new SubstSymMap(from, to).apply(this);
        } else return this;
    }

    /** Substitute symbols `to' for occurrences of symbols `from' in these types.
     */
    public static Type[] subst(Type[] these, Symbol[] from, Symbol[] to) {
        if (these.length != 0 && to.length != 0 && from != to) {
            assert from.length == to.length;
            return new SubstSymMap(from, to).map(these);
        } else return these;
    }

    /** Substitute types `to' for occurrences of symbols `from' in this type.
     */
    public Type subst(Symbol[] from, Type[] to) {
        if (to.length != 0) {
            assert from.length == to.length
                : this + ": " + Debug.show(from) + " <> " + ArrayApply.toString(to);
            return new SubstTypeMap(from, to).apply(this);
        } else return this;
    }

    /** Substitute types `to' for occurrences of symbols `from' in these types.
     */
    public static Type[] subst(Type[] these, Symbol[] from, Type[] to) {
        if (these.length != 0 && to.length != 0) {
            assert from.length == to.length;
            return new SubstTypeMap(from, to).map(these);
        } else return these;
    }

    /**
     * A map that substitutes ThisTypes of a given class by a given
     * type. All occurrences of the type parameters of the given class
     * are replaced by the type arguments extracted from the given
     * type. Furthermore, the prefixes of the given type are used to
     * substitute, in the same way, the ThisTypes of the outer classes
     * of the given class.
     *
     * object Foo {
     *   class C[D] { class I[J]; }
     *   val c: C[Int] = new C[Int];
     *   class M[N] extends c.I[N];
     * }
     *
     * In the code above, a ThisTypeMap of class "I" and type
     * "ThisType(M)", would do the following substitutions:
     *
     *   - ThisType(I)       ->  ThisType(M)
     *   - TypeRef(_, J, _)  ->  TypeRef(_, N, -)
     *   - ThisType(C)       ->  SingleType(ThisType(Foo), c)
     *   - TypeRef(_, D, _)  ->  TypeRef(_, Int, _)
     */
    private static class ThisTypeMap extends Map {

        private static Map create(Symbol clasz, Type type) {
            HashMap subst = getSubst(clasz, type, 0);
            return subst == null ? IdMap : new ThisTypeMap(subst);
        }

        private static HashMap getSubst(Symbol clasz, Type type, int capacity){
            switch (type) {
            case NoPrefix:
                return getSubst(capacity);
            case ThisType(Symbol symbol):
                if (symbol == clasz) return getSubst(capacity);
            }
            Type base = type.baseType(clasz);
            switch (base) {
            case TypeRef(Type prefix, Symbol symbol, Type[] args):
                capacity += 1 + args.length;
                HashMap subst = getSubst(clasz.owner(), prefix, capacity);
                subst.put(clasz, type);
                Symbol[] params = clasz.typeParams();
                assert symbol == clasz && args.length == params.length:
                    type + " @ " + Debug.show(clasz) + " -> " + base;
                for (int i = 0; i < params.length; i++) {
                    assert params[i].isParameter(): Debug.show(params[i]);
                    subst.put(params[i], args[i]);
                }
                return subst;
            default:
                throw Debug.abort("illegal case",
                    type + " @ " + Debug.show(clasz) + " -> " + base);
            }
        }

        private static HashMap getSubst(int capacity) {
            return capacity == 0 ? null : new HashMap(capacity);
        }

        private final HashMap/*<Symbol,Type>*/ subst;

        private ThisTypeMap(HashMap subst) {
            this.subst = subst;
        }

        public Type apply(Type type) {
            switch (type) {
            case ThisType(Symbol symbol):
                Object lookup = subst.get(symbol);
                if (lookup == null) break;
                return (Type)lookup;
            case TypeRef(NoPrefix, Symbol symbol, Type[] args):
                if (!symbol.isParameter()) break;
                assert args.length == 0: type;
                Object lookup = subst.get(symbol);
                if (lookup == null) break;
                return (Type)lookup;
            }
            return map(type);
        }

        public String toString() {
            return subst.toString();
        }

    }

    /** Returns a ThisTypeMap of given class and type. */
    public static Map getThisTypeMap(Symbol clasz, Type type) {
        return ThisTypeMap.create(clasz, type);
    }

    /** A map for substitutions of thistypes.
     */
    public static class SubstThisMap extends Map {
        Symbol from;
        Type to;
        public SubstThisMap(Symbol from, Type to) {
            this.from = from;
            this.to = to;
        }
        public SubstThisMap(Symbol oldSym, Symbol newSym) {
            this(oldSym, newSym.thisType());
        }
        public Type apply(Type type) {
            switch (type) {
            case ThisType(Symbol sym):
                return sym == from ? to : type;
            default:
                return map(type);
            }
        }
    }

    public Type substThis(Symbol from, Type to) {
        return new SubstThisMap(from, to).apply(this);
    }

    public static Type[] substThis(Type[] these, Symbol from, Type to) {
        return new SubstThisMap(from, to).map(these);
    }

    static class ContainsMap extends Map {
        boolean result = false;
        Symbol sym;
        ContainsMap(Symbol sym) {
            this.sym = sym;
        }
        public Type apply(Type t) {
            if (!result) {
                switch (t) {
                case TypeRef(Type pre, Symbol sym1, Type[] args):
                    if (sym == sym1) result = true;
                    else { map(pre); map(args); }
                    break;
                case SingleType(Type pre, Symbol sym1):
                    map(pre);
                    if (sym == sym1) result = true;
                    break;
                default:
                    map(t);
                }
            }
            return t;
        }
    }

    /** Does this type contain symbol `sym'?
     */
    public boolean contains(Symbol sym) {
        ContainsMap f = new ContainsMap(sym);
        f.apply(this);
        return f.result;
    }

    /** Does this type contain any of the symbols `syms'?
     */
    public boolean containsSome(Symbol[] syms) {
        for (int i = 0; i < syms.length; i++)
            if (contains(syms[i])) return true;
        return false;
    }

// Cloning ---------------------------------------------------------------

    /** Returns a shallow copy of the given array. */
    public static Type[] cloneArray(Type[] array) {
        return cloneArray(0, array, 0);
    }

    /**
     * Returns a shallow copy of the given array prefixed by "prefix"
     * null items.
     */
    public static Type[] cloneArray(int prefix, Type[] array) {
        return cloneArray(prefix, array, 0);
    }

    /**
     * Returns a shallow copy of the given array suffixed by "suffix"
     * null items.
     */
    public static Type[] cloneArray(Type[] array, int suffix) {
        return cloneArray(0, array, suffix);
    }

    /**
     * Returns a shallow copy of the given array prefixed by "prefix"
     * null items and suffixed by "suffix" null items.
     */
    public static Type[] cloneArray(int prefix, Type[] array, int suffix) {
        assert prefix >= 0 && suffix >= 0: prefix + " - " + suffix;
        int size = prefix + array.length + suffix;
        if (size == 0) return EMPTY_ARRAY;
        Type[] clone = new Type[size];
        for (int i = 0; i < array.length; i++) clone[prefix + i] = array[i];
        return clone;
    }

    /** Returns the concatenation of the two arrays. */
    public static Type[] concat(Type[] array1, Type[] array2) {
        if (array1.length == 0) return array2;
        if (array2.length == 0) return array1;
        Type[] clone = cloneArray(array1.length, array2);
        for (int i = 0; i < array1.length; i++) clone[i] = array1[i];
        return clone;
    }

    /**
     * Clones a type i.e. returns a new type where all symbols in
     * MethodTypes and PolyTypes and CompoundTypes have been cloned.
     */
    public Type cloneType(Symbol oldOwner, Symbol newOwner) {
        SymbolCloner cloner = new SymbolCloner();
        cloner.owners.put(oldOwner, newOwner);
        return cloner.cloneType(this);
    }

    /**
     * Clones a type i.e. returns a new type where all symbols in
     * MethodTypes and PolyTypes have been cloned. This method
     * performs no substitution on the type of the cloned symbols.
     * Typically, the type of those symbols will be fixed later by
     * applying some Map.applyParams method to the returned type.
     */
    public Type cloneTypeNoSubst(SymbolCloner cloner) {
        switch (this) {

        case MethodType(Symbol[] vparams, Type result):
            Symbol[] clones = cloner.cloneSymbols(vparams);
            return Type.MethodType(clones, result.cloneTypeNoSubst(cloner));

        case PolyType(Symbol[] tparams, Type result):
            Symbol[] clones = cloner.cloneSymbols(tparams);
            return Type.PolyType(clones, result.cloneTypeNoSubst(cloner));

        default:
            return this;
        }
    }


// Comparisons ------------------------------------------------------------------

    /** Type relations */
    public static class Relation {
        public case SubType;   // this SubType   that <=> this.isSubType(that)
        public case SameType;  // this SameType  that <=> this.isSameAs(that)
        public case SuperType; // this SuperType that <=> that.isSubType(this)

        public String toString() {
            return toString(false);
        }
        public String toString(boolean negate) {
            switch (this) {
            case SubType  : return negate ? "!<=" : "<=";
            case SameType : return negate ? "!==" : "=";
            case SuperType: return negate ? "!>=" : ">=";
            default       : throw Debug.abort("unknown relation", this);
            }
        }
    }

    /** Is this type in given relation to that type?
     */
    public boolean compareTo(Type that, Relation relation) {
        switch (relation) {
        case SubType  : return this.isSubType(that);
        case SameType : return this.isSameAs(that);
        case SuperType: return that.isSubType(this);
        default       : throw Debug.abort("unknown relation", relation);
        }
    }

    /** Is this type a subtype of that type?
     */
    public boolean isSubType(Type that) {
        if (explainSwitch) {
            for (int i = 0; i < indent; i++) System.out.print("  ");
            System.out.println(this + " < " + that + "?");
            indent++;
        }
        boolean result = isSubType0(that);
        if (explainSwitch) {
            indent--;
            for (int i = 0; i < indent; i++) System.out.print("  ");
            System.out.println(result);
        }
        return result;
    }

    public boolean isSubType0(Type that) {
        if (this == that) return true;

        switch (this) {
        case ErrorType:
        case AnyType:
            return true;
        }

        switch (that) {
        case ErrorType:
        case AnyType:
            return true;

        case NoType:
        case NoPrefix:
            return false;

        case ThisType(_):
        case SingleType(_, _):
            switch (this) {
            case ThisType(_):
            case SingleType(_, _):
                return this.isSameAs(that);
            }
            break;

        case ConstantType(_, _):
            switch (this) {
            case ConstantType(Type base, _):
                return this.isSameAs(that) || base.isSubType(that);
            }
            break;

        case TypeRef(Type pre1, Symbol sym1, Type[] args1):
            switch (this) {
            case TypeRef(Type pre, Symbol sym, Type[] args):
                if (sym == sym1 && pre.isSubType(pre1) &&
                    isSubArgs(args, args1, sym.typeParams())
                    ||
                    sym.kind == TYPE && pre.memberInfo(sym).isSubType(that))
                    return true;
                break;
            }
            if (sym1.kind == CLASS) {
                Type base = this.baseType(sym1);
                if (this != base && base.isSubType(that))
                    return true;
            }
            break;

        case CompoundType(Type[] parts1, Scope members1):
            int i = 0;
            while (i < parts1.length && isSubType(parts1[i])) i++;
            if (i == parts1.length && specializes(members1))
                return true;
            break;

        case MethodType(Symbol[] ps1, Type res1):
            switch (this) {
            case MethodType(Symbol[] ps, Type res):
                if (ps.length != ps1.length) return false;
                for (int i = 0; i < ps.length; i++) {
                    Symbol p1 = ps1[i];
                    Symbol p = ps[i];
                    if (!p1.type().isSameAs(p.type()) ||
                        (p1.flags & (DEF | REPEATED)) != (p.flags & (DEF | REPEATED)))
                        return false;
                }
                return res.isSubType(res1);
            }
            break;

        case PolyType(Symbol[] ps1, Type res1):
            switch (this) {
            case PolyType(Symbol[] ps, Type res):
                if (ps.length != ps1.length) return false;
                for (int i = 0; i < ps.length; i++)
                    if (!ps1[i].info().subst(ps1, ps).isSubType(ps[i].info()) ||
                        !ps[i].loBound().isSubType(ps1[i].loBound().subst(ps1, ps)) ||
                        !ps1[i].vuBound().subst(ps1, ps).isSubType(ps[i].vuBound()))
                        return false;
                return res.isSubType(res1.subst(ps1, ps));
            }
            break;

        case OverloadedType(Symbol[] alts1, Type[] alttypes1):
            for (int i = 0; i < alttypes1.length; i++) {
                if (!isSubType(alttypes1[i]))
                    return false;
            }
            return true;

        case UnboxedType(int tag1):
            switch (this) {
            case UnboxedType(int tag):
                return tag == tag1;
            }
            break;

        case UnboxedArrayType(Type elemtp1):
            switch (this) {
            case UnboxedArrayType(Type elemtp):
                return elemtp.isSubType(elemtp1);
            }
            break;

        case TypeVar(Type origin, Constraint constr):
            //todo: should we test for equality with origin?
            if (constr.inst != NoType) {
                return this.isSubType(constr.inst);
            } else {
                constr.lobounds = new List(this, constr.lobounds);
                return true;
            }

        default:
            throw new ApplicationError(this + " <: " + that);
        }

        switch (this) {
        case NoType:
        case NoPrefix:
            return false;
        case ThisType(_):
        case SingleType(_, _):
            if (this.singleDeref().isSubType(that)) return true;
            break;
        case ConstantType(_, _):
            if (this.singleDeref().isSubType(that)) return true;
            break;
        case TypeVar(Type origin, Constraint constr):
            if (constr.inst != NoType) {
                return constr.inst.isSubType(that);
            } else {
                constr.hibounds = new List(that, constr.hibounds);
                return true;
            }

        case TypeRef(_, Symbol sym, _):
            switch (that) {
            case TypeRef(_, Symbol sym1, _):
                if (sym1.kind == TYPE && this.isSubType(that.loBound()))
                    return true;
            }
            if (sym == Global.instance.definitions.ALL_CLASS)
                return that.isSubType(Global.instance.definitions.ANY_TYPE());
            else if (sym == Global.instance.definitions.ALLREF_CLASS)
                return
                    that.symbol() == Global.instance.definitions.ANY_CLASS ||
                    (that.symbol() != Global.instance.definitions.ALL_CLASS &&
                     that.isSubType(Global.instance.definitions.ANYREF_TYPE()));
            break;

        case OverloadedType(Symbol[] alts, Type[] alttypes):
            for (int i = 0; i < alttypes.length; i++) {
                if (alttypes[i].isSubType(that)) return true;
            }
            break;

        case CompoundType(Type[] parts, Scope members):
            int i = 0;
            while (i < parts.length) {
                if (parts[i].isSubType(that)) return true;
                i++;
            }
            break;

        case UnboxedArrayType(_):
            if (Global.instance.definitions.OBJECT_TYPE().isSubType(that))
                return true;
            // !!! we should probably also test for Clonable, Serializable, ...
        }

        return false;
    }

    /** Are types `these' subtypes of corresponding types `those'?
     */
    public static boolean isSubType(Type[] these, Type[] those) {
        if (these.length != those.length) return false;
        for (int i = 0; i < these.length; i++) {
            if (!these[i].isSubType(those[i])) return false;
        }
        return true;
    }

    /** Are types `these' arguments types conforming to corresponding types `those'?
     */
    static boolean isSubArgs(Type[] these, Type[] those, Symbol[] tparams) {
        if (these.length != those.length) return false;
        for (int i = 0; i < these.length; i++) {
            if ((tparams[i].flags & COVARIANT) != 0) {
                if (!these[i].isSubType(those[i])) return false;
            } else if ((tparams[i].flags & CONTRAVARIANT) != 0) {
                //System.out.println("contra: " + these[i] + " " + those[i] + " " + those[i].isSubType(these[i]));//DEBUG
                if (!those[i].isSubType(these[i])) return false;
            } else {
                if (!these[i].isSameAs(those[i])) return false;
            }
        }
        return true;
    }

    public static boolean isSubSet(Type[] alts, Type[] alts1) {
        for (int i = 0; i < alts.length; i++) {
            int j = 0;
            while (j < alts1.length && !alts1[j].isSameAs(alts[i])) j++;
            if (j == alts1.length) return false;
        }
        return true;
    }

    /** Does this type implement all symbols in scope `s' with same or stronger types?
     */
    public boolean specializes(Scope s) {
        for (Scope.SymbolIterator it = s.iterator();
	     it.hasNext();) {
            if (!specializes(it.next())) return false;
        }
        return true;
    }

    /** Does this type implement symbol `sym1' with same or stronger type?
     */
    public boolean specializes(Symbol sym1) {
        if (explainSwitch) {
            for (int i = 0; i < indent; i++) System.out.print("  ");
            System.out.println(this + " specializes " + sym1 + "?");
            indent++;
        }
        boolean result = specializes0(sym1);
        if (explainSwitch) {
            indent--;
            for (int i = 0; i < indent; i++) System.out.print("  ");
            System.out.println(result);
        }
        return result;
    }

    private boolean specializes0(Symbol sym1) {
        Type self = narrow();
        Symbol[] tparams = symbol().typeParams();
        Type[] targs = typeArgs();
        Symbol sym = lookup(sym1.name);
        return
            sym.kind != NONE &&
            (sym == sym1
             ||
             (sym.kind == sym1.kind || sym1.kind == TYPE) &&
             self.memberInfo(sym).subst(tparams, targs)
             .isSubType(sym1.info().substThis(sym1.owner(), self)) &&
             sym1.loBound().substThis(sym1.owner(), self)
             .isSubType(self.memberLoBound(sym).subst(tparams, targs)) &&
             self.memberVuBound(sym).subst(tparams, targs)
             .isSubType(sym1.vuBound().substThis(sym1.owner(), self))
             ||
             (sym.kind == TYPE && sym1.kind == ALIAS &&
              sym1.info().unalias().isSameAs(sym.type())));
    }

    /** Is this type the same as that type?
     */
    public boolean isSameAs(Type that) {
        if (explainSwitch) {
            for (int i = 0; i < indent; i++) System.out.print("  ");
            System.out.println(this + " = " + that + "?");
            indent++;
        }
        boolean result = isSameAs0(that);
        if (explainSwitch) {
            indent--;
            for (int i = 0; i < indent; i++) System.out.print("  ");
            System.out.println(result);
        }
        return result;
    }

    public boolean isSameAs0(Type that) {
        if (this == that) return true;

        switch (this) {
        case ErrorType:
        case AnyType:
            return true;

        case ThisType(Symbol sym):
            switch (that) {
            case ThisType(Symbol sym1):
                return sym == sym1;
            case SingleType(Type pre1, Symbol sym1):
                return sym1.isModule()
                    && sym == sym1.moduleClass()
                    && sym.owner().thisType().isSameAs(pre1)
                    ||
                    deAlias(that) != that &&
                    this.isSameAs(deAlias(that));
            }
            break;

        case SingleType(Type pre, Symbol sym):
            switch (that) {
            case SingleType(Type pre1, Symbol sym1):
                return sym == sym1 && pre.isSameAs(pre1)
                    ||
                    (deAlias(this) != this || deAlias(that) != that) &&
                    deAlias(this).isSameAs(deAlias(that));
            case ThisType(Symbol sym1):
                return sym.isModule()
                    && sym.moduleClass() == sym1
                    && pre.isSameAs(sym1.owner().thisType())
                    ||
                    deAlias(this) != this &&
                    deAlias(this).isSameAs(that);
            default:
                if (deAlias(this) != this)
                    return deAlias(this).isSameAs(that);
            }
            break;

        case ConstantType(Type base, AConstant value):
            switch (that) {
            case ConstantType(Type base1, AConstant value1):
                return base.isSameAs(base1) && value.equals(value1);
            }
            break;

        case TypeRef(Type pre, Symbol sym, Type[] args):
            switch (that) {
            case TypeRef(Type pre1, Symbol sym1, Type[] args1):
                if (sym == sym1 && pre.isSameAs(pre1) && isSameAs(args, args1))
                    return true;
            }
            break;

        case CompoundType(Type[] parts, Scope members):
            switch (that) {
            case CompoundType(Type[] parts1, Scope members1):
                if (parts.length != parts1.length) return false;
                for (int i = 0; i < parts.length; i++)
                    if (!parts[i].isSameAs(parts1[i])) return false;
                return isSameAs(members, members1);
            }
            break;

        case MethodType(Symbol[] ps, Type res):
            switch (that) {
            case MethodType(Symbol[] ps1, Type res1):
                if (ps.length != ps1.length) return false;
                for (int i = 0; i < ps.length; i++) {
                    Symbol p1 = ps1[i];
                    Symbol p = ps[i];
                    if (!p1.type().isSameAs(p.type()) ||
                        (p1.flags & (DEF | REPEATED)) != (p.flags & (DEF | REPEATED)))
                        return false;
                }
                return res.isSameAs(res1);
            }
            break;

        case PolyType(Symbol[] ps, Type res):
            switch (that) {
            case PolyType(Symbol[] ps1, Type res1):
                if (ps.length != ps1.length) return false;
                for (int i = 0; i < ps.length; i++)
                    if (!ps1[i].info().subst(ps1, ps).isSameAs(ps[i].info()) ||
                        !ps1[i].loBound().subst(ps1, ps).isSameAs(ps[i].loBound()) ||
                        !ps1[i].vuBound().subst(ps1, ps).isSameAs(ps[i].vuBound()))
                        return false;
                return res.isSameAs(res1.subst(ps1, ps));
            }
            break;

        case OverloadedType(Symbol[] alts, Type[] alttypes):
            switch (that) {
            case OverloadedType(Symbol[] alts1, Type[] alttypes1):
                return isSubSet(alttypes1, alttypes)
                    && isSubSet(alttypes, alttypes1);
            }
            break;

        case UnboxedType(int kind):
            switch (that) {
            case UnboxedType(int kind1):
                return kind == kind1;
            }
            break;

        case UnboxedArrayType(Type elemtp):
            switch (that) {
            case UnboxedArrayType(Type elemtp1):
                return elemtp.isSameAs(elemtp1);
            }
            break;
        }

        switch (that) {
        case ErrorType:
        case AnyType:
            return true;
        case NoType:
        case NoPrefix:
            return false;
        case TypeVar(Type origin, Constraint constr):
            if (constr.inst != NoType) return constr.inst.isSameAs(this);
            else return constr.instantiate(this.any2typevar());
        }

        switch (this) {
        case NoType:
        case NoPrefix:
            return false;
        case TypeVar(Type origin, Constraint constr):
            if (constr.inst != NoType) return constr.inst.isSameAs(that);
            else return constr.instantiate(that.any2typevar());
        }

        return false;
    }
    //where
        Type deAlias(Type tp) {
            switch (tp) {
            case SingleType(_, _):
                Type tp1 = tp.singleDeref();
                if (tp1.isStable()) return deAlias(tp1);
            }
            return tp;
        }

    /** Are types `these' the same as corresponding types `those'?
     */
    public static boolean isSameAs(Type[] these, Type[] those) {
        if (these.length != those.length) return false;
        for (int i = 0; i < these.length; i++) {
            if (!these[i].isSameAs(those[i])) return false;
        }
        return true;
    }

    /** Do scopes `s1' and `s2' define he same symbols with the same kinds and infos?
     */
    public boolean isSameAs(Scope s1, Scope s2) {
        return isSubScope(s1, s2) && isSubScope(s2, s1);
    }

    /** Does scope `s1' define all symbols of scope `s2' with the same kinds and infos?
     */
    private boolean isSubScope(Scope s1, Scope s2) {
        for (Scope.SymbolIterator it = s2.iterator(); it.hasNext(); ) {
            Symbol sym2 = it.next();
            // todo: handle overloaded
            Symbol sym1 = s1.lookup(sym2.name);
            if (sym1.kind != sym2.kind ||
                !sym1.info().isSameAs(
                    sym2.info().substThis(
                        sym2.owner(), sym1.owner().thisType())) ||
                !sym1.loBound().isSameAs(
                    sym2.loBound().substThis(
                        sym2.owner(), sym1.owner().thisType())) ||
                !sym1.vuBound().isSameAs(
                    sym2.vuBound().substThis(
                        sym2.owner(), sym1.owner().thisType())))
                return false;
        }
        return true;
    }

    boolean isSameAsAll(Type[] tps) {
        int i = 1;
        while (i < tps.length && isSameAs(tps[i])) i++;
        return i == tps.length;
    }

    /** Map every occurrence of AnyType to a fresh type variable.
     */
    public static Map any2typevarMap = new Map() {
        public Type apply(Type t) { return t.any2typevar(); }
    };

    public Type any2typevar() {
        switch (this) {
        case AnyType:
            return TypeVar(this, new Constraint());
        default:
            return any2typevarMap.map(this);
        }
    }

    /** Does this type match type `tp', so that corresponding symbols with
     *  the two types would be taken to override each other?
     */
    public boolean overrides(Type tp) {
	switch (this) {
	case OverloadedType(Symbol[] alts, Type[] alttypes):
	    for (int i = 0; i < alttypes.length; i++) {
		if (alttypes[i].overrides(tp)) return true;
	    }
	    return false;
	default:
	    switch (tp) {
	    case MethodType(Symbol[] ps1, Type res1):
		switch (this) {
		case MethodType(Symbol[] ps, Type res):
		    if (ps.length != ps1.length) return false;
		    for (int i = 0; i < ps.length; i++) {
			Symbol p1 = ps1[i];
			Symbol p = ps[i];
			if (!p1.type().isSameAs(p.type()) ||
			    (p1.flags & (DEF | REPEATED)) != (p.flags & (DEF | REPEATED)))
			    return false;
		    }
		    return res.overrides(res1);
		}
		return false;

	    case PolyType(Symbol[] ps1, Type res1):
		switch (this) {
		case PolyType(Symbol[] ps, Type res):
		    if (ps.length != ps1.length) return false;
		    for (int i = 0; i < ps.length; i++)
			if (!ps1[i].info().subst(ps1, ps).isSubType(ps[i].info()) ||
			    !ps[i].loBound().isSubType(ps1[i].loBound().subst(ps1, ps)) ||
			    !ps1[i].vuBound().subst(ps1, ps).isSubType(ps[i].vuBound()))
			    return false;
		    return res.overrides(res1.subst(ps1, ps));
		}
		return false;

	    case OverloadedType(_, _):
		throw new ApplicationError("overrides inapplicable for " + tp);

	    default:
		switch (this) {
		case MethodType(_, _): case PolyType(_, _): return false;
		default: return true;
		}
	    }
	}
    }

// Closures and Least Upper Bounds ---------------------------------------------------

    /** The closure of this type, i.e. the widened type itself followed by all
     *  its direct and indirect (pre-) base types, sorted by Symbol.isLess().
     */
    public Type[] closure() {
        switch (this.widen().unalias()) {
        case TypeRef(Type pre, Symbol sym, Type[] args):
            return subst(
                asSeenFrom(sym.closure(), pre, sym.owner()),
                sym.typeParams(), args);

        case CompoundType(Type[] parts, Scope members):
/*
	    if (symbol().isCompoundSym()) {
		Type[][] closures = new Type[parts.length][];
		for (int i = 0; i < parts.length; i++)
		    closures[i] = parts[i].closure();
		return union(closures);
	    } else {
*/
	    return symbol().closure();

        default:
            return new Type[]{this};
        }
    }

    /** return union of array of closures. It is assumed that
     *  for any two base types with the same class symbols the later one
     *  is a subtype of the former.
     */
    static private Type[] union(Type[][] closures) {
        if (closures.length == 1) return closures[0]; // fast special case
        int[] index = new int[closures.length];
        int totalsize = 0;
        for (int i = 0; i < index.length; i++) {
            index[i] = 0;
            totalsize = totalsize + closures[i].length;
        }
        Type[] res = new Type[totalsize];
        int j = 0;

        while (true) {
            // find minimal element
            Type min = null;
            for (int i = 0; i < index.length; i++) {
                if (index[i] < closures[i].length) {
                    Type cltype = closures[i][index[i]];
                    if (min == null ||
                        cltype.symbol().isLess(min.symbol()) ||
                        cltype.symbol() == min.symbol()) {
                        min = cltype;
                    }
                }
            }
            if (min == null) break;

            res[j] = min;
            j = j + 1;

            // bump all indices that start with minimal element
            for (int i = 0; i < index.length; i++) {
                if (index[i] < closures[i].length &&
                    closures[i][index[i]].symbol() == min.symbol())
                    index[i] = index[i] + 1;
            }
        }
        Type[] result = new Type[j];
        System.arraycopy(res, 0, result, 0, j);
        return result;
    }

    /** return intersection of non-empty array of closures
     */
    static private Type[] intersection(Type[][] closures) {
        if (closures.length == 1) return closures[0]; // fast special case
        int[] index = new int[closures.length];
        Type[] mintypes = new Type[closures.length];
        int minsize = Integer.MAX_VALUE;
        for (int i = 0; i < index.length; i++) {
            index[i] = 0;
            if (closures[i].length < minsize) minsize = closures[i].length;
        }
        Type[] res = new Type[minsize];
        int j = 0;

        L:
        while (true) {
            // find minimal element
            Symbol minsym = null;
            for (int i = 0; i < index.length; i++) {
                if (index[i] == closures[i].length) break L;
                Symbol clsym = closures[i][index[i]].symbol();
                if (minsym == null || clsym.isLess(minsym)) minsym = clsym;
            }

            boolean agree = true;
            // bump all indices that start with minimal element
            for (int i = 0; i < index.length; i++) {
                Type cltype = closures[i][index[i]];
                if (cltype.symbol() == minsym) {
                    mintypes[i] = cltype;
                    index[i] = index[i] + 1;
                } else {
                    agree = false;
                }
            }
            if (agree) {
                Type mintype = argLub(mintypes);
                if (mintype.symbol().kind == CLASS) {
                    res[j] = mintype;
                    j = j + 1;
                }
            }
        }
        Type[] result = new Type[j];
        System.arraycopy(res, 0, result, 0, j);
        return result;
    }

    /** same as lub, but all types are instances of the same class,
     *  possibly with different prefixes and arguments.
     */
    //todo: catch lubs not within bounds.
    static Type argLub(Type[] tps) {
        tps = elimRedundant(tps, true);
        if (tps.length == 1) return tps[0];

        Type pre = tps[0].prefix();
        Symbol sym = tps[0].symbol();
        Symbol[] tparams = sym.typeParams();
        Type[] args = new Type[tparams.length];
        Type[][] argss = new Type[args.length][tps.length];
        for (int i = 0; i < tps.length; i++) {
            switch (tps[i]) {
            case TypeRef(Type pre1, Symbol sym1, Type[] args1):
                assert sym == sym1;
                assert args1.length == args.length;
                if (!pre.isSameAs(pre1)) return NoType;
                for (int j = 0; j < args1.length; j++)
                    argss[j][i] = args1[j];
                break;
            case ErrorType:
                return ErrorType;
            default:
                assert false : tps[i];
            }
        }
        for (int j = 0; j < args.length; j++) {
            if ((tparams[j].flags & COVARIANT) != 0)
                args[j] = lub(argss[j]);
            else if ((tparams[j].flags & CONTRAVARIANT) != 0)
                args[j] = glb(argss[j]);
            else return NoType;
        }
        return typeRef(pre, sym, args);
    }

    /** The frontier of a closure C is the minimal set of types such that
     *  the union of the closures of these types equals C.
     */
    static private Type[] frontier(Type[] closure) {
        Type[] front = new Type[closure.length];
        int j = 0;
        for (int i = 0; i < closure.length; i++) {
            int k = 0;
            Type tp = closure[i];
            while (k < j && !front[k].symbol().isSubClass(tp.symbol()))
                 k++;
            if (k == j) {
                front[j] = tp;
                j++;
            }
        }
        Type[] result = new Type[j];
        System.arraycopy(front, 0, result, 0, j);
        return result;
    }

    /** remove types that are subtypes of some other type.
     */
    static private Type[] elimRedundant(Type[] tps, boolean elimLower) {
        Type.List tl = Type.List.EMPTY;
        int nredundant = 0;
        boolean[] redundant = new boolean[tps.length];
        for (int i = 0; i < tps.length; i++) {
            switch (tps[i]) {
            case ErrorType:
                return new Type[]{ErrorType};
            case MethodType(_, _):
            case PolyType(_, _):
            case OverloadedType(_, _):
                return new Type[]{NoType};
            default:
                assert tps[i].isObjectType(): tps[i];
                for (int j = 0; j < i && !redundant[i]; j++) {
                    if (!redundant[j]) {
                        if (tps[i].isSubType(tps[j])) {
                            redundant[elimLower ? i : j] = true;
                            nredundant++;
                        } else if (tps[j].isSubType(tps[i])) {
                            redundant[elimLower ? j : i] = true;
                            nredundant++;
                        }
                    }
                }
            }
        }

        if (nredundant != 0) {
            Type[] tps1 = new Type[tps.length - nredundant];
            int n = 0;
            for (int i = 0; i < tps.length; i++) {
                if (!redundant[i]) tps1[n++] = tps[i];
            }
            return tps1;
        } else {
            return tps;
        }
    }

    static int recCount = 0;
    static boolean giveUp = false;
    static int recLimit = 10;

    public static Type lub(Type[] tps) {
	if (recCount == recLimit) {
	    giveUp = true;
	    return Global.instance.definitions.ANY_TYPE();
	} else {
	    recCount++;
	    Type result = lub0(tps);
	    recCount--;
	    if (recCount == 0) {
		if (giveUp) {
		    giveUp = false;
		    throw new Error("failure to compute least upper bound of types " +
				    ArrayApply.toString(tps, "", " and ", ";\n") +
				    "an approximation is: " + result + ";\n" +
				    "additional type annotations are needed");
		} else {
		    giveUp = false;
		}
	    }
	    return result;
	}
    }

    /** Return the least upper bound of non-empty array of types `tps'.
     */
    public static Type lub0(Type[] tps) {
        //System.out.println("lub" + ArrayApply.toString(tps));//DEBUG

        if (tps.length == 0) return Global.instance.definitions.ALL_TYPE();

        //If all types are method types with same parameters,
        //compute lub of their result types.
        switch (tps[0]) {
        case PolyType(Symbol[] tparams, _):
            return polyLub(tps, tparams);
        case MethodType(Symbol[] vparams, _):
            return methodLub(tps, vparams);
        }

        // remove types that are subtypes of some other type.
        tps = elimRedundant(tps, true);
        if (tps.length == 1) return tps[0];

        // intersect closures and build frontier.
        Type[][] closures = new Type[tps.length][];
        for (int i = 0; i < tps.length; i++) {
            closures[i] = tps[i].closure();
        }
        Type[] allBaseTypes = intersection(closures);
        Type[] leastBaseTypes = frontier(allBaseTypes);
        assert leastBaseTypes.length > 0 : ArrayApply.toString(tps);

        // add refinements where necessary
        Scope members = new Scope();
        Type lubType = compoundTypeWithOwner(Symbol.NONE, leastBaseTypes, members); // !!! NONE
	/*
        Type lubThisType = lubType.narrow();
        //System.out.println("lubtype = " + lubType);//DEBUG

        Symbol[] rsyms = new Symbol[tps.length];
        Type[] rtps = new Type[tps.length];
        Type[] rlbs = new Type[tps.length];
        for (int i = 0; i < allBaseTypes.length; i++) {
            for (Scope.SymbolIterator it = allBaseTypes[i].members().iterator();
                 it.hasNext(); ) {
                Symbol sym = it.next();
                Name name = sym.name;
                if ((sym.flags & PRIVATE) == 0 && lubType.lookup(name) == sym) {
                    Type symType = memberTp(lubThisType, sym);
                    Type symLoBound = lubThisType.memberLoBound(sym);
                    int j = 0;
                    while (j < tps.length) {
                        rsyms[j] = tps[j].lookupNonPrivate(name);
                        if (rsyms[j] == sym) break;
                        rtps[j] = memberTp(tps[j], rsyms[j])
                            .substThis(tps[j].symbol(), lubThisType);
                        rlbs[j] = tps[j].memberLoBound(rsyms[j])
                            .substThis(tps[j].symbol(), lubThisType);
                        if (rtps[j].isSameAs(symType) &&
                            rlbs[j].isSameAs(symLoBound)) break;
                        j++;
                    }
                    if (j == tps.length) {
			if (Global.instance.debug)
			    System.out.println("refinement lub for " +
			    ArrayApply.toString(rsyms) + ":" + ArrayApply.toString(rtps));//debug
                        Symbol lubSym = lub(rsyms, rtps, rlbs, lubType.symbol());
                        if (lubSym.kind != NONE &&
                            !(lubSym.kind == sym.kind &&
                              lubSym.info().isSameAs(symType) &&
                              lubSym.loBound().isSameAs(symType)))
                            members.enter(lubSym);
                    }
                }
            }
        }
        //System.out.print("lub "); System.out.print(ArrayApply.toString(tps)); System.out.println(" = " + lubType);//DEBUG
	*/
        if (leastBaseTypes.length == 1 && members.isEmpty())
            return leastBaseTypes[0];
        else return lubType;
    }
    //where
        private static Type memberTp(Type base, Symbol sym) {
            return sym.kind == CLASS ? base.memberType(sym) : base.memberInfo(sym);
        }

    private static Type polyLub(Type[] tps, Symbol[] tparams0) {
        Type[][] hiboundss = new Type[tparams0.length][tps.length];
        Type[][] loboundss = new Type[tparams0.length][tps.length];
        Type[][] vuboundss = new Type[tparams0.length][tps.length];
        Type[] restps   = new Type[tps.length];
        for (int i = 0; i < tps.length; i++) {
            switch (tps[i]) {
            case PolyType(Symbol[] tparams, Type restp):
                if (tparams.length == tparams0.length) {
                    for (int j = 0; j < tparams0.length; j++) {
                        hiboundss[j][i] = tparams[j].info()
                            .subst(tparams, tparams0);
                        loboundss[j][i] = tparams[j].loBound()
                            .subst(tparams, tparams0);
                        vuboundss[j][i] = tparams[j].vuBound()
                            .subst(tparams, tparams0);
                    }
                    restps[i] = restp.subst(tparams, tparams0);
                } else {
                    return Type.NoType;
                }
                break;
            default:
                return Type.NoType;
            }
        }
        Type[] hibounds = new Type[tparams0.length];
        Type[] lobounds = new Type[tparams0.length];
        Type[] vubounds = new Type[tparams0.length];
        for (int j = 0; j < tparams0.length; j++) {
            hibounds[j] = glb(hiboundss[j]);
            lobounds[j] = lub(loboundss[j]);
            vubounds[j] = glb(vuboundss[j]);
        }
        Symbol[] tparams = new Symbol[tparams0.length];
        for (int j = 0; j < tparams.length; j++) {
            tparams[j] = tparams0[j].cloneSymbol(Symbol.NONE)
                .setInfo(hibounds[j].subst(tparams0, tparams))
                .setLoBound(lobounds[j].subst(tparams0, tparams))
                .setVuBound(vubounds[j].subst(tparams0, tparams));
        }
        return Type.PolyType(tparams, lub(restps).subst(tparams0, tparams));
    }

    private static Type methodLub(Type[] tps, Symbol[] vparams0) {
        Type[] restps = new Type[tps.length];
        for (int i = 0; i < tps.length; i++) {
            switch (tps[i]) {
            case MethodType(Symbol[] vparams, Type restp):
                if (vparams.length != vparams0.length)
                    return Type.NoType;
                for (int j = 0; j < vparams.length; j++)
                    if (!vparams[j].type().isSameAs(vparams0[j].type()) ||
                        (vparams[j].flags & (DEF | REPEATED)) !=
                        (vparams0[j].flags & (DEF | REPEATED)))
                        return Type.NoType;
                restps[i] = restp;
            }
        }
        Symbol[] vparams = new Symbol[vparams0.length];
        for (int j = 0; j < vparams.length; j++) {
            vparams[j] = vparams0[j].cloneSymbol(Symbol.NONE);
        }
        return Type.MethodType(vparams, lub(restps));
    }

    private static Symbol lub(Symbol[] syms, Type[] tps, Type[] lbs, Symbol owner) {
        //System.out.println("lub" + ArrayApply.toString(syms));//DEBUG
        int lubKind = syms[0].kind;
        for (int i = 1; i < syms.length; i++) {
            Symbol sym = syms[i];
            if (sym.isError()) return Symbol.NONE;
            if (sym.isType() && sym.kind != lubKind) lubKind = TYPE;
        }
        if (lubKind == syms[0].kind && tps[0].isSameAsAll(tps)) {
            return syms[0].cloneSymbol();
        }

        Type lubType = lub(tps);
        if (lubType == Type.NoType) return Symbol.NONE;
        Symbol lubSym;
        switch (lubKind) {
        case VAL:
            lubSym = owner.newTerm(syms[0].pos, 0, syms[0].name);
            break;
        case TYPE: case ALIAS: case CLASS:
            lubSym = owner.newAbstractType(syms[0].pos, 0, syms[0].name);
            lubSym.setLoBound(glb(lbs));
            break;
        default:
            throw new ApplicationError();
        }
        lubSym.setInfo(lubType.setOwner(lubSym));
        return lubSym;
    }

    public static Type glb(Type[] tps) {
	if (recCount == recLimit) {
	    giveUp = true;
	    return Global.instance.definitions.ALL_TYPE();
	} else {
	    recCount++;
	    Type result = glb0(tps);
	    recCount--;
	    if (recCount == 0) {
		if (giveUp) {
		    giveUp = false;
		    throw new Error("failure to compute greatest lower bound of types " +
				    ArrayApply.toString(tps, "", " and ", ";\n") +
				    "an approximation is: " + result + ";\n" +
				    "additional type annotations are needed");
		} else {
		    giveUp = false;
		}
	    }
	    return result;
	}
    }

    public static Type glb0(Type[] tps) {
        if (tps.length == 0) return Global.instance.definitions.ANY_TYPE();

        // step one: eliminate redunandant types; return if one one is left
        tps = elimRedundant(tps, false);
        if (tps.length == 1) return tps[0];

        // step two: build arrays of all typerefs and all refinements
        Type.List treftl = Type.List.EMPTY;
        Type.List comptl = Type.List.EMPTY;
        for (int i = 0; i < tps.length; i++) {
            switch (tps[i]) {
            case TypeRef(_, _, _):
                treftl = new Type.List(tps[i], treftl);
                break;
            case CompoundType(Type[] parents, Scope members):
                if (!members.isEmpty())
                    comptl = new Type.List(tps[i], comptl);
                for (int j = 0; j < parents.length; j++)
                    treftl = new Type.List(parents[j], treftl);
                break;
            case ThisType(_):
            case SingleType(_, _):
            case ConstantType(_, _):
                return Global.instance.definitions.ALL_TYPE();
            }
        }

        CompoundType glbType = compoundTypeWithOwner(Symbol.NONE, Type.EMPTY_ARRAY, new Scope()); // !!! NONE
        Type glbThisType = glbType.narrow();

        // step 3: compute glb of all refinements.
        Scope members = Scope.EMPTY;
        if (comptl != List.EMPTY) {
            Type[] comptypes = comptl.toArrayReverse();
            Scope[] refinements = new Scope[comptypes.length];
            for (int i = 0; i < comptypes.length; i++)
                refinements[i] = comptypes[i].members();
            if (!setGlb(glbType.members, refinements, glbThisType)) {
                // refinements don't have lower bound, so approximate
                // by AllRef
                glbType.members = Scope.EMPTY;
                treftl = new Type.List(
                    Global.instance.definitions.ALLREF_TYPE(), treftl);
            }
        }

        // eliminate redudant typerefs
        Type[] treftypes = elimRedundant(treftl.toArrayReverse(), false);
        if (treftypes.length != 1 || !glbType.members.isEmpty()) {
            // step 4: replace all abstract types by their lower bounds.
            boolean hasAbstract = false;
            for (int i = 0; i < treftypes.length; i++) {
                if (treftypes[i].unalias().symbol().kind == TYPE)
                    hasAbstract = true;
            }
            if (hasAbstract) {
                treftl = Type.List.EMPTY;
                for (int i = 0; i < treftypes.length; i++) {
                    if (treftypes[i].unalias().symbol().kind == TYPE)
                        treftl = new Type.List(treftypes[i].loBound(), treftl);
                    else
                        treftl = new Type.List(treftypes[i], treftl);
                }
                treftypes = elimRedundant(treftl.toArrayReverse(), false);
            }
        }

        if (treftypes.length != 1) {
            // step 5: if there are conflicting instantiations of same
            // class, replace them by lub/glb of arguments or lower bound.
            Type lb = NoType;
            for (int i = 0;
                 i < treftypes.length &&
                     lb.symbol() != Global.instance.definitions.ALL_CLASS;
                 i++) {
                for (int j = 0; j < i; j++) {
                    if (treftypes[j].symbol() == treftypes[i].symbol())
                        lb = argGlb(treftypes[j], treftypes[i]);
                }
            }
            if (lb != NoType) return lb;
        }

        if (treftypes.length == 1 && glbType.members.isEmpty()) {
            return treftypes[0];
        } else {
            glbType.parts = treftypes;
            return glbType;
        }
    }

    private static Type argGlb(Type tp1, Type tp2) {
        switch (tp1) {
        case TypeRef(Type pre1, Symbol sym1, Type[] args1):
            switch (tp2) {
            case TypeRef(Type pre2, Symbol sym2, Type[] args2):
                assert sym1 == sym2;
                if (pre1.isSameAs(pre2)) {
                    Symbol[] tparams = sym1.typeParams();
                    Type[] args = new Type[tparams.length];
                    for (int i = 0; i < tparams.length; i++) {
                        if (args1[i].isSameAs(args2[i]))
                            args[i] = args1[i];
                        else if ((tparams[i].flags & COVARIANT) != 0)
                            args[i]= lub(new Type[]{args1[i], args2[i]});
                        else if ((tparams[i].flags & CONTRAVARIANT) != 0)
                            args[i]= glb(new Type[]{args1[i], args2[i]});
                        else
                            return glb(new Type[]{tp1.loBound(), tp2.loBound()});
                    }
                    return typeRef(pre1, sym1, args);
                }
            }
        }
        return glb(new Type[]{tp1.loBound(), tp2.loBound()});
    }

    /** Set scope `result' to glb of scopes `ss'. Return true iff succeeded.
     */
    private static boolean setGlb(Scope result, Scope[] ss, Type glbThisType) {
        for (int i = 0; i < ss.length; i++)
            for (Scope.SymbolIterator it = ss[i].iterator(); it.hasNext(); )
                if (!addMember(result, it.next(), glbThisType)) return false;
        return true;
    }

    /** Add member `sym' to scope `s'. If`s' has already a member with same name,
     *  overwrite its info/low bound to form glb of both symbols.
     */
    private static boolean addMember(Scope s, Symbol sym, Type glbThisType) {
        Type syminfo = sym.info().substThis(sym.owner(), glbThisType);
        Type symlb = sym.loBound().substThis(sym.owner(), glbThisType);
        Type symvb = sym.vuBound().substThis(sym.owner(), glbThisType);
        Scope.Entry e = s.lookupEntry(sym.name);
        if (e == Scope.Entry.NONE) {
            Symbol sym1 = sym.cloneSymbol(glbThisType.symbol());
            sym1.setInfo(syminfo);
            if (sym1.kind == TYPE) {
		sym1.setLoBound(symlb);
		sym1.setVuBound(symvb);
	    }
            s.enter(sym1);
        } else {
            Type einfo = e.sym.info();
            if (einfo.isSameAs(syminfo)) {
            } else if (einfo.isSubType(syminfo) && sym.kind != ALIAS) {
            } else if (syminfo.isSubType(einfo) && e.sym.kind != ALIAS) {
                e.sym.setInfo(syminfo);
            } else if (sym.kind == VAL && e.sym.kind == VAL ||
                       sym.kind == TYPE && e.sym.kind == TYPE) {
                e.sym.setInfo(glb(new Type[]{einfo, syminfo}).setOwner(e.sym));
            } else {
                return false;
            }
            if (e.sym.kind == TYPE && sym.kind == TYPE) {
                Type elb = e.sym.loBound();
                if (elb.isSameAs(symlb)) {
                } else if (symlb.isSubType(elb)) {
                } else if (elb.isSubType(symlb)) {
                    e.sym.setLoBound(symlb);
                } else {
                    e.sym.setLoBound(lub(new Type[]{elb, symlb}));
                }
                Type evb = e.sym.vuBound();
                if (evb.isSameAs(symvb)) {
                } else if (evb.isSubType(symvb)) {
                } else if (symvb.isSubType(evb)) {
                    e.sym.setVuBound(symvb);
                } else {
                    e.sym.setVuBound(glb(new Type[]{evb, symvb}));
                }
            }
        }
        return true;
    }

    private static Type polyGlb(Type[] tps, Symbol[] tparams0) {
        Type[][] hiboundss = new Type[tparams0.length][tps.length];
        Type[][] loboundss = new Type[tparams0.length][tps.length];
        Type[][] vuboundss = new Type[tparams0.length][tps.length];
        Type[] restps   = new Type[tps.length];
        for (int i = 0; i < tps.length; i++) {
            switch (tps[i]) {
            case PolyType(Symbol[] tparams, Type restp):
                if (tparams.length == tparams0.length) {
                    for (int j = 0; j < tparams0.length; j++) {
                        hiboundss[j][i] = tparams[j].info()
                            .subst(tparams, tparams0);
                        loboundss[j][i] = tparams[j].loBound()
                            .subst(tparams, tparams0);
                        vuboundss[j][i] = tparams[j].vuBound()
                            .subst(tparams, tparams0);
                    }
                    restps[i] = restp.subst(tparams, tparams0);
                } else {
                    return Type.NoType;
                }
                break;
            default:
                return Type.NoType;
            }
        }
        Type[] hibounds = new Type[tparams0.length];
        Type[] lobounds = new Type[tparams0.length];
        Type[] vubounds = new Type[tparams0.length];
        for (int j = 0; j < tparams0.length; j++) {
            hibounds[j] = lub(hiboundss[j]);
            lobounds[j] = glb(loboundss[j]);
            vubounds[j] = lub(vuboundss[j]);
        }
        Symbol[] tparams = new Symbol[tparams0.length];
        for (int j = 0; j < tparams.length; j++) {
            tparams[j] = tparams0[j].cloneSymbol(Symbol.NONE)
                .setInfo(hibounds[j].subst(tparams0, tparams))
                .setLoBound(lobounds[j].subst(tparams0, tparams))
                .setVuBound(vubounds[j].subst(tparams0, tparams));
        }
        return Type.PolyType(tparams, glb(restps).subst(tparams0, tparams));
    }

    private static Type methodGlb(Type[] tps, Symbol[] vparams0) {
        Type[] restps = new Type[tps.length];
        for (int i = 0; i < tps.length; i++) {
            switch (tps[i]) {
            case MethodType(Symbol[] vparams, Type restp):
                if (vparams.length != vparams0.length)
                    return Type.NoType;
                for (int j = 0; j < vparams.length; j++)
                    if (!vparams[i].type().isSameAs(vparams0[i].type()) ||
                        (vparams[i].flags & (DEF | REPEATED)) !=
                        (vparams0[i].flags & (DEF | REPEATED)))
                        return Type.NoType;
                restps[i] = restp;
            }
        }
        Symbol[] vparams = new Symbol[vparams0.length];
        for (int j = 0; j < vparams.length; j++) {
            vparams[j] = vparams0[j].cloneSymbol(Symbol.NONE);
        }
        return Type.MethodType(vparams, glb(restps));
    }

// Erasure --------------------------------------------------------------------------

    public static Map erasureMap = new MapOnlyTypes() {
        public Type apply(Type t) { return t.erasure(); }
    };

    private static final Type[] unboxedType =
        new Type[LastUnboxedTag + 1 - FirstUnboxedTag];
    private static final Name[] unboxedName =
        new Name[LastUnboxedTag + 1 - FirstUnboxedTag];
    private static final Symbol[] boxedSymbol =
        new Symbol[LastUnboxedTag + 1 - FirstUnboxedTag];

    private static void mkStdClassType(int kind, String unboxedstr, Symbol boxedsym) {
        unboxedType[kind - FirstUnboxedTag] = UnboxedType(kind);
        unboxedName[kind - FirstUnboxedTag] = Name.fromString(unboxedstr);
        boxedSymbol[kind - FirstUnboxedTag] = boxedsym;
    }

    static void initializeUnboxedTypes(Definitions definitions) {
        mkStdClassType(BYTE, "byte", definitions.BYTE_CLASS);
        mkStdClassType(SHORT, "short", definitions.SHORT_CLASS);
        mkStdClassType(CHAR, "char", definitions.CHAR_CLASS);
        mkStdClassType(INT, "int", definitions.INT_CLASS);
        mkStdClassType(LONG, "long", definitions.LONG_CLASS);
        mkStdClassType(FLOAT, "float", definitions.FLOAT_CLASS);
        mkStdClassType(DOUBLE, "double", definitions.DOUBLE_CLASS);
        mkStdClassType(BOOLEAN, "boolean", definitions.BOOLEAN_CLASS);
        mkStdClassType(UNIT, "void", definitions.UNIT_CLASS);
    }

    /** Return unboxed type of given kind.
     */
    public static Type unboxedType(int kind) {
        return unboxedType[kind - FirstUnboxedTag];
    }

    /** Return the name of unboxed type of given kind.
    */
    public static Name unboxedName(int kind) {
        return unboxedName[kind - FirstUnboxedTag];
    }

    /** If type is boxed, return its unboxed equivalent; otherwise return the type
     *  itself.
     */
    public Type unbox() {
        switch (this) {
        case TypeRef(_, Symbol clasz, Type[] args):
            if (args.length == 0) {
                for (int i = 0; i < boxedSymbol.length; i++)
                    if (boxedSymbol[i] == clasz) return unboxedType[i];
            } else if (args.length == 1) {
                Definitions definitions = Global.instance.definitions;
                if (clasz == definitions.ARRAY_CLASS) {
                    Type item = args[0];
                    Type bound = item.upperBound();
                    // todo: check with Philippe if this is what we want.
                    if (item.symbol().isClass() ||
                        (bound.symbol() != definitions.ANY_CLASS &&
                            bound.symbol() != definitions.ANYVAL_CLASS))
                    {
                        return UnboxedArrayType(args[0].erasure());
                    }
                }
            }
        }
        return this;
    }
    //where
        private Type upperBound() {
            switch (this) {
            case TypeRef(Type pre, Symbol sym, Type[] args):
                if (sym.kind == TYPE)
                    return pre.memberInfo(sym).upperBound();
            }
            return this;
        }

    /** Return the erasure of this type.
     */
    public Type erasure() {
        switch (this) {
        case ThisType(_):
        case SingleType(_, _):
        case ConstantType(_, _):
            return singleDeref().erasure();
        case TypeRef(Type pre, Symbol sym, Type[] args):
            switch (sym.kind) {
            case ALIAS: case TYPE:
                return sym.info().asSeenFrom(pre, sym.owner()).erasure();

            case CLASS:
                Definitions definitions = Global.instance.definitions;
                if (sym == definitions.UNIT_CLASS) return this;
                if (sym == definitions.OBJECT_CLASS ||
                    sym == definitions.ALL_CLASS ||
                    sym == definitions.ALLREF_CLASS)
                    return Type.typeRef(NoPrefix, definitions.ANY_CLASS, EMPTY_ARRAY);
                else {
                    Type this1 = unbox();
                    if (this1 != this) return this1;
                    else return Type.typeRef(NoPrefix, sym, EMPTY_ARRAY);
                }

            default: throw new ApplicationError(sym + " has wrong kind: " + sym.kind);
            }
        case CompoundType(Type[] parents, _):
            if (parents.length > 0) return parents[0].erasure();
            else return this;
        case MethodType(Symbol[] params, Type tp):
            Symbol[] params1 = erasureMap.map(params);
            Type tp1 = tp.fullErasure();
            switch (tp1) {
            case MethodType(Symbol[] params2, Type tp2):
                Symbol[] newparams = new Symbol[params1.length + params2.length];
                System.arraycopy(params1, 0, newparams, 0, params1.length);
                System.arraycopy(params2, 0, newparams, params1.length, params2.length);
                return MethodType(newparams, tp2);
            default:
                if (params1 == params && tp1 == tp) return this;
                else return MethodType(params1, tp1);
            }
        case PolyType(_, Type result):
            return result.erasure();
        default:
            return erasureMap.map(this);
        }
    }

    /** Return the full erasure of the type. Full erasure is the same
     * as "normal" erasure, except that the "Unit" type is erased to
     * the "void" type.
     */
    public Type fullErasure() {
        Type erasure = erasure();
        if (Global.instance.definitions.UNIT_CLASS == erasure.symbol())
            erasure = erasure.unbox();
        return erasure;
    }

// Object Interface -----------------------------------------------------------------

    public String toString() {
        return new SymbolTablePrinter().printType(this).toString();
    }

    public String toLongString() {
        String str = toString();
        if (str.endsWith(".type")) return str + " (with underlying type " + widen() + ")";
        else return str;
    }

    public int hashCode() {
        switch (this) {
        case ErrorType:
            return ERRORtpe;
        case NoType:
            return NOtpe;
        case NoPrefix:
            return NOpre;
        case ThisType(Symbol sym):
            return THIStpe
                ^ (sym.hashCode() * 41);
        case TypeRef(Type pre, Symbol sym, Type[] args):
            return TYPEREFtpe
                ^ (pre.hashCode() * 41)
                ^ (sym.hashCode() * (41*41))
                ^ (hashCode(args) * (41*41*41));
        case SingleType(Type pre, Symbol sym):
            return SINGLEtpe
                ^ (pre.hashCode() * 41)
                ^ (sym.hashCode() * (41*41));
        case ConstantType(Type base, AConstant value):
            return CONSTANTtpe
                ^ (base.hashCode() * 41)
                ^ (value.hashCode() * (41*41));
        case CompoundType(Type[] parts, Scope members):
            return symbol().hashCode();
            //return COMPOUNDtpe
            //  ^ (hashCode(parts) * 41)
            //  ^ (members.hashCode() * (41 * 41));
        case MethodType(Symbol[] vparams, Type result):
            int h = METHODtpe;
            for (int i = 0; i < vparams.length; i++)
                h = (h << 4) ^ (vparams[i].flags & SOURCEFLAGS);
            return h
                ^ (hashCode(Symbol.type(vparams)) * 41)
                ^ (result.hashCode() * (41 * 41));
        case PolyType(Symbol[] tparams, Type result):
            return POLYtpe
                ^ (hashCode(tparams) * 41)
                ^ (result.hashCode() * (41 * 41));
        case OverloadedType(Symbol[] alts, Type[] alttypes):
            return OVERLOADEDtpe
                ^ (hashCode(alts) * 41)
                ^ (hashCode(alttypes) * (41 * 41));
        case UnboxedType(int kind):
            return UNBOXEDtpe
                ^ (kind * 41);
        case UnboxedArrayType(Type elemtp):
            return UNBOXEDARRAYtpe
                ^ (elemtp.hashCode() * 41);
        default:
            throw new ApplicationError("bad type for hashCode: " + this);
        }
    }

    public static int hashCode(Object[] elems) {
        int h = 0;
        for (int i = 0; i < elems.length; i++)
            h = h * 41 + elems[i].hashCode();
        return h;
    }

    // todo: change in relation to needs.

    public boolean equals(Object other) {
        if (this == other) {
            return true;
        } else if (other instanceof Type) {
            Type that = (Type) other;
            switch (this) {
            case ErrorType:
                return that == ErrorType;
            case NoType:
                return that == NoType;
            case NoPrefix:
                return that == NoPrefix;
            case ThisType(Symbol sym):
                switch (that) {
                case ThisType(Symbol sym1):
                    return sym == sym1;
                default: return false;
                }
            case TypeRef(Type pre, Symbol sym, Type[] args):
                switch (that) {
                case TypeRef(Type pre1, Symbol sym1, Type[] args1):
                    return pre.equals(pre1) && sym == sym1 && equals(args, args1);
                default: return false;
                }
            case SingleType(Type pre, Symbol sym):
                switch (that) {
                case SingleType(Type pre1, Symbol sym1):
                    return pre.equals(pre1) && sym == sym1;
                default: return false;
                }
            case ConstantType(Type base, AConstant value):
                switch (that) {
                case ConstantType(Type base1, AConstant value1):
                    return base.equals(base1) && value.equals(value1);
                default: return false;
                }
            case CompoundType(Type[] parts, Scope members):
                switch (that) {
                case CompoundType(Type[] parts1, Scope members1):
                    return this.symbol() == that.symbol();
                    //return parts.equals(parts1) && members.equals(members1);
                default: return false;
                }
            case MethodType(Symbol[] vparams, Type result):
                switch (that) {
                case MethodType(Symbol[] vparams1, Type result1):
                    if (vparams.length != vparams1.length)
                        return false;
                    for (int i = 0; i < vparams.length; i++)
                        if ((vparams[i].flags & SOURCEFLAGS) !=
                            (vparams1[i].flags & SOURCEFLAGS))
                            return false;
                    return
                        equals(Symbol.type(vparams), Symbol.type(vparams1)) &&
                        result.equals(result1);
                default: return false;
                }
            case PolyType(Symbol[] tparams, Type result):
                switch (that) {
                case PolyType(Symbol[] tparams1, Type result1):
                    return equals(tparams, tparams1) && result.equals(result1);
                default: return false;
                }
            case OverloadedType(Symbol[] alts, Type[] alttypes):
                switch (that) {
                case OverloadedType(Symbol[] alts1, Type[] alttypes1):
                    return equals(alts, alts1) && equals(alttypes, alttypes1);
                default: return false;
                }
            case UnboxedType(int kind):
                switch (that) {
                case UnboxedType(int kind1):
                    return kind == kind1;
                default: return false;
                }
            case UnboxedArrayType(Type elemtp):
                switch (that) {
                case UnboxedArrayType(Type elemtp1):
                    return elemtp.equals(elemtp1);
                default: return false;
                }
            default:
            }
        }
        return false;
    }

    public static boolean equals(Object[] elems1, Object[] elems2) {
        if (elems1.length != elems2.length) return false;
        for (int i = 0; i < elems1.length; i++) {
            if (!elems1[i].equals(elems2[i])) return false;
        }
        return true;
    }

// Type.List class -----------------------------------------------------------------

    /** A class for lists of types.
     */
    public static class List {
        public Type head;
        public List tail;
        public List(Type head, List tail) {
            this.head = head; this.tail = tail;
        }
        public int length() {
            return (this == EMPTY) ? 0 : 1 + tail.length();
        }
        public Type[] toArray() {
            Type[] ts = new Type[length()];
            copyToArray(ts, 0, 1);
            return ts;
        }
        public void copyToArray(Type[] ts, int start, int delta) {
            if (this != EMPTY) {
                ts[start] = head;
                tail.copyToArray(ts, start+delta, delta);
            }
        }
        public Type[] toArrayReverse() {
            Type[] ts = new Type[length()];
            copyToArray(ts, ts.length - 1, -1);
            return ts;
        }

        public String toString() {
            if (this == EMPTY) return "List()";
            else return head + "::" + tail;
        }

        public static List EMPTY = new List(null, null);

        public static List append(List l, Type tp) {
            return (l == EMPTY) ? new List(tp, EMPTY)
                : new List(l.head, append(l.tail, tp));
        }
    }

// Type.Constraint class -------------------------------------------------------

    /** A class for keeping sub/supertype constraints and instantiations
     *  of type variables.
     */
    public static class Constraint {
        public List lobounds = List.EMPTY;
        public List hibounds = List.EMPTY;
        public Type inst = NoType;

        public boolean instantiate(Type tp) {
            for (List l = lobounds; l != List.EMPTY; l = l.tail) {
                if (!l.head.isSubType(tp)) return false;
            }
            for (List l = hibounds; l != List.EMPTY; l = l.tail) {
                if (!tp.isSubType(l.head)) return false;
            }
            inst = tp;
            return true;
        }
    }

// Type.Error class --------------------------------------------------------------

    /** A class for throwing type errors
     */
    public static class Error extends java.lang.Error {
        public String msg;
        public Error(String msg) {
            super(msg);
            this.msg = msg;
        }
    }

    public static class Malformed extends Error {
        public Malformed(Type pre, String tp) {
            super("malformed type: " + pre + "#" + tp);
        }
    }

    /** A class for throwing type errors
     */
    public static class VarianceError extends Error {
        public VarianceError(String msg) {
            super(msg);
        }
    }

    public static void explainTypes(Type found, Type required) {
        if (Global.instance.explaintypes) {
            boolean s = explainSwitch;
            explainSwitch = true;
            found.isSubType(required);
            explainSwitch = s;
        }
    }
}

/* A standard pattern match:

    case ErrorType:
    case AnyType:
    case NoType:
    case ThisType(Symbol sym):
    case TypeRef(Type pre, Symbol sym, Type[] args):
    case SingleType(Type pre, Symbol sym):
    case ConstantType(Type base, Object value):
    case CompoundType(Type[] parts, Scope members):
    case MethodType(Symbol[] vparams, Type result):
    case PolyType(Symbol[] tparams, Type result):
    case OverloadedType(Symbol[] alts, Type[] alttypes):
*/