/* NSC -- new Scala compiler
 * Copyright 2005-2011 LAMP/EPFL
 * @author  Martin Odersky
 */

package scala.tools.nsc
package symtab

import scala.collection.{ mutable, immutable }
import scala.ref.WeakReference
import mutable.ListBuffer
import ast.TreeGen
import util.{ Position, NoPosition }
import util.Statistics._
import Flags._
import scala.util.control.ControlThrowable
import scala.annotation.tailrec

/* A standard type pattern match:
  case ErrorType =>
    // internal: error
  case WildcardType =>
    // internal: unknown
  case NoType =>
  case NoPrefix =>
  case ThisType(sym) =>
    // sym.this.type
  case SuperType(thistpe, supertpe) =>
    // super references
  case SingleType(pre, sym) =>
    // pre.sym.type
  case ConstantType(value) =>
    // Int(2)
  case TypeRef(pre, sym, args) => 
    // pre.sym[targs]
    // Outer.this.C would be represented as TypeRef(ThisType(Outer), C, List())
  case RefinedType(parents, defs) =>
    // parent1 with ... with parentn { defs }
  case ExistentialType(tparams, result) =>
    // result forSome { tparams }
  case AnnotatedType(annots, tp, selfsym) =>
    // tp @annots

  // the following are non-value types; you cannot write them down in Scala source.

  case TypeBounds(lo, hi) =>  
    // >: lo <: hi
  case ClassInfoType(parents, defs, clazz) =>
    // same as RefinedType except as body of class
  case MethodType(paramtypes, result) =>
    // (paramtypes)result 
    // For instance def m(): T is represented as MethodType(List(), T)
  case NullaryMethodType(result) => // eliminated by uncurry
    // an eval-by-name type
    // For instance def m: T is represented as NullaryMethodType(T)
  case PolyType(tparams, result) =>
    // [tparams]result where result is a (Nullary)MethodType or ClassInfoType

  // The remaining types are not used after phase `typer'. 
  case OverloadedType(pre, tparams, alts) =>
    // all alternatives of an overloaded ident
  case AntiPolyType(pre, targs) =>
    // rarely used, disappears when combined with a PolyType
  case TypeVar(inst, constr) =>
    // a type variable
    // Replace occurrences of type parameters with type vars, where
    // inst is the instantiation and constr is a list of bounds.
  case DeBruijnIndex(level, index)
    // for dependent method types: a type referring to a method parameter.
    // Not presently used, it seems.
*/

trait Types extends reflect.generic.Types { self: SymbolTable =>
  import definitions._
  
  //statistics
  def uniqueTypeCount = if (uniques == null) 0 else uniques.size

  private var explainSwitch = false
  private final val emptySymbolSet = immutable.Set.empty[Symbol]

  private final val alternativeNarrow = false

  private final val LogPendingSubTypesThreshold = 50
  private final val LogPendingBaseTypesThreshold = 50
  private final val LogVolatileThreshold = 50

  /** A don't care value for the depth parameter in lubs/glbs and related operations */
  private final val AnyDepth = -3

  /** Decrement depth unless it is a don't care */
  private final def decr(depth: Int) = if (depth == AnyDepth) AnyDepth else depth - 1

  private final val printLubs = false
  /** In case anyone wants to turn off lub verification without reverting anything. */
  private final val verifyLubs = true

  /** The current skolemization level, needed for the algorithms
   *  in isSameType, isSubType that do constraint solving under a prefix 
   */
  var skolemizationLevel = 0

  /** A log of type variable with their original constraints. Used in order
   *  to undo constraints in the case of isSubType/isSameType failure.
   */
  object undoLog {
    private type UndoLog = List[(TypeVar, TypeConstraint)]
    private[nsc] var log: UndoLog = List()

    /** Undo all changes to constraints to type variables upto `limit'
     */
    private def undoTo(limit: UndoLog) {
      while ((log ne limit) && log.nonEmpty) {
        val (tv, constr) = log.head
        tv.constr = constr
        log = log.tail
      }
    }

    private[Types] def record(tv: TypeVar) = {
      log ::= (tv, tv.constr.cloneInternal)
    }
    private[nsc] def clear() {
      if (settings.debug.value)
        self.log("Clearing " + log.size + " entries from the undoLog.")

      log = Nil
    }

    // `block` should not affect constraints on typevars
    def undo[T](block: => T): T = {
      val before = log

      try block
      finally undoTo(before)
    }

    // if `block` evaluates to false, it should not affect constraints on typevars
    def undoUnless(block: => Boolean): Boolean = {
      val before = log
      var result = false
      
      try result = block
      finally if (!result) undoTo(before)
      
      result
    }
  }

  /** A map from lists to compound types that have the given list as parents.
   *  This is used to avoid duplication in the computation of base type sequences and baseClasses.
   *  It makes use of the fact that these two operations depend only on the parents,
   *  not on the refinement.
   */
  val intersectionWitness = new mutable.WeakHashMap[List[Type], WeakReference[Type]]

  private object gen extends {
    val global : Types.this.type = Types.this
  } with TreeGen

  import gen._

  /** A proxy for a type (identified by field `underlying') that forwards most 
   *  operations to it (for exceptions, see WrappingProxy, which forwards even more operations).
   *  every operation that is overridden for some kind of types should be forwarded.
   */
  trait SimpleTypeProxy extends Type {
    def underlying: Type

    // the following operations + those in RewrappingTypeProxy are all operations 
    // in class Type that are overridden in some subclass
    // Important to keep this up-to-date when new operations are added!
    override def isTrivial = underlying.isTrivial
    override def isHigherKinded: Boolean = underlying.isHigherKinded
    override def typeConstructor: Type = underlying.typeConstructor 
    override def isNotNull = underlying.isNotNull
    override def isError = underlying.isError
    override def isErroneous = underlying.isErroneous
    override def isStable: Boolean = underlying.isStable
    override def isVolatile = underlying.isVolatile
    override def finalResultType = underlying.finalResultType
    override def paramSectionCount = underlying.paramSectionCount
    override def paramss = underlying.paramss
    override def params = underlying.params
    override def paramTypes = underlying.paramTypes
    override def termSymbol = underlying.termSymbol
    override def termSymbolDirect = underlying.termSymbolDirect
    override def typeParams = underlying.typeParams
    override def boundSyms = underlying.boundSyms
    override def typeSymbol = underlying.typeSymbol
    override def typeSymbolDirect = underlying.typeSymbolDirect
    override def widen = underlying.widen
    override def typeOfThis = underlying.typeOfThis
    override def bounds = underlying.bounds
    override def parents = underlying.parents
    override def prefix = underlying.prefix
    override def decls = underlying.decls
    override def baseType(clazz: Symbol) = underlying.baseType(clazz)
    override def baseTypeSeq = underlying.baseTypeSeq
    override def baseTypeSeqDepth = underlying.baseTypeSeqDepth
    override def baseClasses = underlying.baseClasses
  }

  /** A proxy for a type (identified by field `underlying') that forwards most 
   *  operations to it. Every operation that is overridden for some kind of types is
   *  forwarded here. Some operations are rewrapped again.
   */
  trait RewrappingTypeProxy extends SimpleTypeProxy {
    protected def maybeRewrap(newtp: Type) = if (newtp eq underlying) this else rewrap(newtp)
    protected def rewrap(newtp: Type): Type

    // the following are all operations in class Type that are overridden in some subclass
    // Important to keep this up-to-date when new operations are added!
    override def widen = maybeRewrap(underlying.widen)
    override def narrow = underlying.narrow
    override def deconst = maybeRewrap(underlying.deconst)
    override def resultType = maybeRewrap(underlying.resultType)
    override def resultType(actuals: List[Type]) = maybeRewrap(underlying.resultType(actuals))
    override def finalResultType = maybeRewrap(underlying.finalResultType)
    override def paramSectionCount = 0
    override def paramss: List[List[Symbol]] = List()
    override def params: List[Symbol] = List()
    override def paramTypes: List[Type] = List()
    override def typeArgs = underlying.typeArgs
    override def notNull = maybeRewrap(underlying.notNull)
    override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]) = underlying.instantiateTypeParams(formals, actuals)
    override def skolemizeExistential(owner: Symbol, origin: AnyRef) = underlying.skolemizeExistential(owner, origin)
    override def normalize = maybeRewrap(underlying.normalize)
    override def dealias = maybeRewrap(underlying.dealias)
    override def cloneInfo(owner: Symbol) = maybeRewrap(underlying.cloneInfo(owner))
    override def atOwner(owner: Symbol) = maybeRewrap(underlying.atOwner(owner))
    override def prefixString = underlying.prefixString
    override def isComplete = underlying.isComplete
    override def complete(sym: Symbol) = underlying.complete(sym)
    override def load(sym: Symbol) { underlying.load(sym) }
    override def withAnnotations(annots: List[AnnotationInfo]) = maybeRewrap(underlying.withAnnotations(annots))
    override def withoutAnnotations = maybeRewrap(underlying.withoutAnnotations)
  }

  /** The base class for all types */
  abstract class Type extends AbsType {
    
    /** Types for which asSeenFrom always is the identity, no matter what
     *  prefix or owner.
     */
    def isTrivial: Boolean = false

    /** Is this type higher-kinded, i.e., is it a type constructor @M */
    def isHigherKinded: Boolean = false 
    
    /** Does this type denote a stable reference (i.e. singleton type)? */
    def isStable: Boolean = false

    /** Is this type dangerous (i.e. it might contain conflicting
     *  type information when empty, so that it can be constructed
     *  so that type unsoundness results.) A dangerous type has an underlying
     *  type of the form T_1 with T_n { decls }, where one of the
     *  T_i (i > 1) is an abstract type.
     */
    def isVolatile: Boolean = false

    /** Is this type guaranteed not to have `null' as a value? */
    def isNotNull: Boolean = false

    /** Is this type a structural refinement type (it 'refines' members that have not been inherited) */
    def isStructuralRefinement: Boolean = false

    /** Does this type depend immediately on an enclosing method parameter? 
      * i.e., is it a singleton type whose termSymbol refers to an argument of the symbol's owner (which is a method)
      */
    def isImmediatelyDependent: Boolean = false

    /** Does this depend on an enclosing method parameter? */
    def isDependent: Boolean = IsDependentCollector.collect(this)

    /** True for WildcardType or BoundedWildcardType */
    def isWildcard = false

    /** The term symbol associated with the type
      * Note that the symbol of the normalized type is returned (@see normalize)
      */
    def termSymbol: Symbol = NoSymbol

    /** The type symbol associated with the type
      * Note that the symbol of the normalized type is returned (@see normalize)
      */
    def typeSymbol: Symbol = NoSymbol

    /** The term symbol *directly* associated with the type
      */
    def termSymbolDirect: Symbol = termSymbol

    /** The type symbol *directly* associated with the type
      */
    def typeSymbolDirect: Symbol = typeSymbol

    /** The base type underlying a type proxy,
     *  identity on all other types */
    def underlying: Type = this

    /** Widen from singleton type to its underlying non-singleton
     *  base type by applying one or more `underlying' dereferences,
     *  identity for all other types.
     *  
     *  class Outer { class C ; val x: C }
     *  val o: Outer
     *  <o.x.type>.widen = o.C
     */
    def widen: Type = this

    /** Map a constant type or not-null-type to its underlying base type,
     *  identity for all other types.
     */
    def deconst: Type = this

    /** The type of `this' of a class type or reference type
     */
    def typeOfThis: Type = typeSymbol.typeOfThis

    /** Map to a singleton type which is a subtype of this type.
     *  The fallback implemented here gives
     *    T.narrow  =  (T {}).this.type
     *  Overridden where we know more about where types come from.
     *
     *  todo: change to singleton type of an existentially defined variable
     *  of the right type instead of making this a `this` of a refined type.
     */
    def narrow: Type =
      if (phase.erasedTypes) this
      else if (alternativeNarrow) { // investigate why this does not work!
        val tparam = commonOwner(this) freshExistential ".type" setInfo singletonBounds(this)
        tparam.tpe
      } else {
        val cowner = commonOwner(this)
        refinedType(List(this), cowner, EmptyScope, cowner.pos).narrow
      }

    /** For a TypeBounds type, itself;
     *  for a reference denoting an abstract type, its bounds,
     *  for all other types, a TypeBounds type all of whose bounds are this type.
     */
    def bounds: TypeBounds = TypeBounds(this, this)

    /** For a class or intersection type, its parents.
     *  For a TypeBounds type, the parents of its hi bound.
     *  inherited by typerefs, singleton types, and refinement types,
     *  The empty list for all other types */
    def parents: List[Type] = List()

    /** For a typeref or single-type, the prefix of the normalized type (@see normalize).
     *  NoType for all other types. */
    def prefix: Type = NoType

    /** A chain of all typeref or singletype prefixes of this type, longest first.
     *  (Only used from safeToString.)
     */
    def prefixChain: List[Type] = this match {
      case TypeRef(pre, _, _) => pre :: pre.prefixChain
      case SingleType(pre, _) => pre :: pre.prefixChain
      case _ => List()
    }

    /** This type, without its type arguments @M */
    def typeConstructor: Type = this

    /** For a typeref, its arguments. The empty list for all other types */
    def typeArgs: List[Type] = List()

    /** For a (nullary) method or poly type, its direct result type, 
     *  the type itself for all other types. */
    def resultType: Type = this

    def resultType(actuals: List[Type]) = this

    /** Only used for dependent method types. */
    def resultApprox: Type = if(settings.YdepMethTpes.value) ApproximateDependentMap(resultType) else resultType

    /** If this is a TypeRef `clazz`[`T`], return the argument `T`
     *  otherwise return this type
     */
    def remove(clazz: Symbol): Type = this

    /** For a curried/nullary method or poly type its non-method result type, 
     *  the type itself for all other types */
    def finalResultType: Type = this

    /** For a method type, the number of its value parameter sections,
     *  0 for all other types */
    def paramSectionCount: Int = 0

    /** For a method or poly type, a list of its value parameter sections,
     *  the empty list for all other types */
    def paramss: List[List[Symbol]] = List()

    /** For a method or poly type, its first value parameter section,
     *  the empty list for all other types */
    def params: List[Symbol] = List()

    /** For a method or poly type, the types of its first value parameter section,
     *  the empty list for all other types */
    def paramTypes: List[Type] = List()
    
    /** For a (potentially wrapped) poly type, its type parameters,
     *  the empty list for all other types */
    def typeParams: List[Symbol] = List()
  
    /** For a (potentially wrapped) poly or existential type, its bound symbols,
     *  the empty list for all other types */
    def boundSyms: immutable.Set[Symbol] = emptySymbolSet

    /** Mixin a NotNull trait unless type already has one
     *  ...if the option is given, since it is causing typing bugs.
     */
    def notNull: Type =
      if (!settings.Ynotnull.value || isNotNull || phase.erasedTypes) this
      else NotNullType(this)
    
    /** Replace formal type parameter symbols with actual type arguments. 
     *
     * Amounts to substitution except for higher-kinded types. (See overridden method in TypeRef) -- @M
     */
    def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]): Type =
      if (sameLength(formals, actuals)) this.subst(formals, actuals) else ErrorType

    /** If this type is an existential, turn all existentially bound variables to type skolems.
     *  @param  owner    The owner of the created type skolems
     *  @param  origin   The tree whose type was an existential for which the skolem was created.
     */
    def skolemizeExistential(owner: Symbol, origin: AnyRef): Type = this
    
    /** A simple version of skolemizeExistential for situations where
     *  owner or unpack location do not matter (typically used in subtype tests)
     */
    def skolemizeExistential: Type = skolemizeExistential(NoSymbol, null)
    
    /** Reduce to beta eta-long normal form.
     *  Expands type aliases and converts higher-kinded TypeRefs to PolyTypes.
     *  Functions on types are also implemented as PolyTypes.
     * 
     *  Example: (in the below, <List> is the type constructor of List)
     *    TypeRef(pre, <List>, List()) is replaced by
     *    PolyType(X, TypeRef(pre, <List>, List(X)))
     */
    def normalize = this // @MAT
    
    /** Expands type aliases. */
    def dealias = this
    
    /** Is this type produced as a repair for an error? */
    def isError: Boolean = typeSymbol.isError || termSymbol.isError

    /** Is this type produced as a repair for an error? */
    def isErroneous: Boolean = ErroneousCollector.collect(this)

    /** Does this type denote a reference type which can be null? */
    // def isNullable: Boolean = false

    /** For a classtype or refined type, its defined or declared members;
     *  inherited by subtypes and typerefs.
     *  The empty scope for all other types.
     */
    def decls: Scope = EmptyScope

    /** The defined or declared members with name `name' in this type;
     *  an OverloadedSymbol if several exist, NoSymbol if none exist.
     *  Alternatives of overloaded symbol appear in the order they are declared.
     */
    def decl(name: Name): Symbol = findDecl(name, 0)

    /** The non-private defined or declared members with name `name' in this type;
     *  an OverloadedSymbol if several exist, NoSymbol if none exist.
     *  Alternatives of overloaded symbol appear in the order they are declared.
     */
    def nonPrivateDecl(name: Name): Symbol = findDecl(name, PRIVATE)

    /** A list of all members of this type (defined or inherited)
     *  Members appear in linearization order of their owners.
     *  Members with the same owner appear in reverse order of their declarations.
     */
    def members: List[Symbol] = findMember(nme.ANYNAME, 0, 0, false).alternatives

    /** A list of all non-private members of this type (defined or inherited) */
    def nonPrivateMembers: List[Symbol] =
      findMember(nme.ANYNAME, PRIVATE | BRIDGES, 0, false).alternatives

    /** A list of all non-private members of this type  (defined or inherited),
     *  admitting members with given flags `admit`
     */
    def nonPrivateMembersAdmitting(admit: Long): List[Symbol] =
      findMember(nme.ANYNAME, (PRIVATE | BRIDGES) & ~admit, 0, false).alternatives

    /** A list of all implicit symbols of this type  (defined or inherited) */
    def implicitMembers: List[Symbol] =
      findMember(nme.ANYNAME, BRIDGES, IMPLICIT, false).alternatives

    /** A list of all deferred symbols of this type  (defined or inherited) */
    def deferredMembers: List[Symbol] =
      findMember(nme.ANYNAME, BRIDGES, DEFERRED, false).alternatives

    /** The member with given name, 
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def member(name: Name): Symbol = findMember(name, BRIDGES, 0, false)

    /** The non-private member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist.
     *  Bridges are excluded from the result
     */
    def nonPrivateMember(name: Name): Symbol =
      findMember(name, PRIVATE | BRIDGES, 0, false)
  
    /** The non-private member with given name, admitting members with given flags `admit`
     *  an OverloadedSymbol if several exist, NoSymbol if none exist
     */
    def nonPrivateMemberAdmitting(name: Name, admit: Long): Symbol =
      findMember(name, (PRIVATE | BRIDGES) & ~admit, 0, false)
  
    /** The non-local member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def nonLocalMember(name: Name): Symbol =
      findMember(name, LOCAL | BRIDGES, 0, false)

    /** The least type instance of given class which is a supertype
     *  of this type.  Example:
     *    class D[T]
     *    class C extends p.D[Int]
     *    ThisType(C).baseType(D) = p.D[Int]
     */
    def baseType(clazz: Symbol): Type = NoType

    /** 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.
     *
     *  Example:
     *    class D[T] { def m: T }
     *    class C extends p.D[Int]
     *    T.asSeenFrom(ThisType(C), D)  (where D is owner of m)
     *      = Int
     */
    def asSeenFrom(pre: Type, clazz: Symbol): Type =
      if (!isTrivial && (!phase.erasedTypes || pre.typeSymbol == ArrayClass)) {
        incCounter(asSeenFromCount)
        val start = startTimer(asSeenFromNanos)
        val m = new AsSeenFromMap(pre.normalize, clazz)
        val tp = m apply this
        val result = existentialAbstraction(m.capturedParams, tp)
        stopTimer(asSeenFromNanos, start)
        result
      } else this

    /** The info of `sym', seen as a member of this type.
     *
     *  Example:
     *    class D[T] { def m: T }
     *    class C extends p.D[Int]
     *    ThisType(C).memberType(m) = Int
     */
    def memberInfo(sym: Symbol): Type = {
      sym.info.asSeenFrom(this, sym.owner)
    }

    /** The type of `sym', seen as a member of this type. */
    def memberType(sym: Symbol): Type = sym match {
      case meth: MethodSymbol =>
        meth.typeAsMemberOf(this)
      case _ =>
        computeMemberType(sym)
    }

    def computeMemberType(sym: Symbol): Type = sym.tpeHK match { //@M don't prematurely instantiate higher-kinded types, they will be instantiated by transform, typedTypeApply, etc. when really necessary
      case OverloadedType(_, alts) =>
        OverloadedType(this, alts)
      case tp =>
        tp.asSeenFrom(this, sym.owner)
    }

    /** Substitute types `to' for occurrences of references to
     *  symbols `from' in this type.
     */
    def subst(from: List[Symbol], to: List[Type]): Type =
      if (from.isEmpty) this
      else new SubstTypeMap(from, to) apply this

    /** Substitute symbols `to' for occurrences of symbols
     *  `from' in this type.
     * !!! NOTE !!!: If you need to do a substThis and a substSym, the substThis has to come
     * first, as otherwise symbols will immediately get rebound in typeRef to the old 
     * symbol.
     */
    def substSym(from: List[Symbol], to: List[Symbol]): Type =
      if (from eq to) this
      else new SubstSymMap(from, to) apply this

    /** Substitute all occurrences of `ThisType(from)' in this type
     *  by `to'.
     * !!! NOTE !!!: If you need to do a substThis and a substSym, the substThis has to come
     * first, as otherwise symbols will immediately get rebound in typeRef to the old 
     * symbol.
     */
    def substThis(from: Symbol, to: Type): Type =
      new SubstThisMap(from, to) apply this

    def substSuper(from: Type, to: Type): Type =
      new SubstSuperMap(from, to) apply this

    /** Returns all parts of this type which satisfy predicate `p' */
    def filter(p: Type => Boolean): List[Type] = new FilterTypeCollector(p).collect(this).toList

    /** Returns optionally first type (in a preorder traversal) which satisfies predicate `p',
     *  or None if none exists. 
     */
    def find(p: Type => Boolean): Option[Type] = new FindTypeCollector(p).collect(this)

    /** Apply `f' to each part of this type */
    def foreach(f: Type => Unit) { new ForEachTypeTraverser(f).traverse(this) }

    /** Apply `f' to each part of this type; children get mapped before their parents */
    def map(f: Type => Type): Type = new TypeMap {
      def apply(x: Type) = f(mapOver(x))
    } apply this

    /** Is there part of this type which satisfies predicate `p'? */
    def exists(p: Type => Boolean): Boolean = !find(p).isEmpty

    /** Does this type contain a reference to this symbol? */
    def contains(sym: Symbol): Boolean = new ContainsCollector(sym).collect(this)

    /** Does this type contain a reference to this type */
    def containsTp(tp: Type): Boolean = new ContainsTypeCollector(tp).collect(this)

    /** Is this type a subtype of that type? */
    def <:<(that: Type): Boolean = {
      if (util.Statistics.enabled) stat_<:<(that)
      else {
        (this eq that) ||
        (if (explainSwitch) explain("<:", isSubType, this, that)
         else isSubType(this, that, AnyDepth))
      }
    }
    
    /** Can this type only be subtyped by bottom types?
     *  This is assessed to be the case if the class is final,
     *  and all type parameters (if any) are invariant.
     */
    def isFinalType = (
      typeSymbol.isFinal &&
      (typeSymbol.typeParams forall (_.variance == 0))
    )
    
    /** Is this type a subtype of that type in a pattern context?
     *  Any type arguments on the right hand side are replaced with
     *  fresh existentials, except for Arrays.
     *
     *  See bug1434.scala for an example of code which would fail
     *  if only a <:< test were applied.
     */     
    def matchesPattern(that: Type): Boolean = {
      (this <:< that) || ((this, that) match {        
        case (TypeRef(_, ArrayClass, List(arg1)), TypeRef(_, ArrayClass, List(arg2))) if arg2.typeSymbol.typeParams.nonEmpty =>
          arg1 matchesPattern arg2
        case (_, TypeRef(_, _, args)) =>
          val newtp = existentialAbstraction(args map (_.typeSymbol), that)
          !(that =:= newtp) && (this <:< newtp)
        case _ =>
          false
      })
    }
    
    def stat_<:<(that: Type): Boolean = {
      incCounter(subtypeCount)
      val start = startTimer(subtypeNanos)
      val result = 
        (this eq that) ||
        (if (explainSwitch) explain("<:", isSubType, this, that)
         else isSubType(this, that, AnyDepth))
      stopTimer(subtypeNanos, start)
      result
    }

    /** Is this type a weak subtype of that type? True also for numeric types, i.e. Int weak_<:< Long.
     */
    def weak_<:<(that: Type): Boolean = {
      incCounter(subtypeCount)
      val start = startTimer(subtypeNanos)
      val result =
        ((this eq that) ||
         (if (explainSwitch) explain("weak_<:", isWeakSubType, this, that)
          else isWeakSubType(this, that)))
      stopTimer(subtypeNanos, start)
      result
    }

    /** Is this type equivalent to that type? */
    def =:=(that: Type): Boolean = (
      (this eq that) ||
      (if (explainSwitch) explain("=", isSameType, this, that)
       else isSameType(this, that))
    );

    /** Does this type implement symbol `sym' with same or stronger type?
     */
    def specializes(sym: Symbol): Boolean =
      if (explainSwitch) explain("specializes", specializesSym, this, sym)
      else specializesSym(this, sym)

    /** Is this type close enough to that type so that members
     *  with the two type would override each other?
     *  This means: 
     *    - Either both types are polytypes with the same number of
     *      type parameters and their result types match after renaming 
     *      corresponding type parameters
     *    - Or both types are (nullary) method types with equivalent type parameter types
     *      and matching result types
     *    - Or both types are equivalent
     *    - Or phase.erasedTypes is false and both types are neither method nor
     *      poly types.
     */
    def matches(that: Type): Boolean = matchesType(this, that, !phase.erasedTypes)

    /** Same as matches, except that non-method types are always assumed to match.
     */
    def looselyMatches(that: Type): Boolean = matchesType(this, that, true)

    /** The shortest sorted upwards closed array of types that contains
     *  this type as first element.
     *
     *  A list or array of types ts is upwards closed if
     *
     *    for all t in ts:
     *      for all typerefs p.s[args] such that t <: p.s[args] 
     *      there exists a typeref p'.s[args'] in ts such that 
     *      t <: p'.s['args] <: p.s[args],
     *
     *      and
     *
     *      for all singleton types p.s such that t <: p.s 
     *      there exists a singleton type p'.s in ts such that 
     *      t <: p'.s <: p.s
     *
     *  Sorting is with respect to Symbol.isLess() on type symbols.
     */
    def baseTypeSeq: BaseTypeSeq = baseTypeSingletonSeq(this)

    /** The maximum depth (@see maxDepth)
     *  of each type in the BaseTypeSeq of this type.
     */
    def baseTypeSeqDepth: Int = 1

    /** The list of all baseclasses of this type (including its own typeSymbol)
     *  in reverse linearization order, starting with the class itself and ending
     *  in class Any.
     */
    def baseClasses: List[Symbol] = List()

    /**
     *  @param sym the class symbol
     *  @return    the index of given class symbol in the BaseTypeSeq of this type,
     *             or -1 if no base type with given class symbol exists.
     */
    def baseTypeIndex(sym: Symbol): Int = {
      val bts = baseTypeSeq
      var lo = 0
      var hi = bts.length - 1
      while (lo <= hi) {
        val mid = (lo + hi) / 2
        val btssym = bts.typeSymbol(mid)
        if (sym == btssym) return mid
        else if (sym isLess btssym) hi = mid - 1
        else if (btssym isLess sym) lo = mid + 1
        else abort()
      }
      -1
    }

    /** If this is a poly- or methodtype, a copy with cloned type / value parameters
     *  owned by `owner'. Identity for all other types.
     */
    def cloneInfo(owner: Symbol) = this

    /** Make sure this type is correct as the info of given owner; clone it if not.
     */
    def atOwner(owner: Symbol) = this

    protected def objectPrefix = "object "
    protected def packagePrefix = "package "

    def trimPrefix(str: String) = str stripPrefix objectPrefix stripPrefix packagePrefix

    /** The string representation of this type used as a prefix */
    def prefixString = trimPrefix(toString) + "#"

    /** The string representation of this type, with singletypes explained */
    def toLongString = {
      val str = toString
      if (str endsWith ".type") str + " (with underlying type " + widen + ")"
      else str
    }

    /** A test whether a type contains any unification type variables */
    def isGround: Boolean = this match {
      case TypeVar(_, constr) => 
        constr.instValid && constr.inst.isGround
      case TypeRef(pre, sym, args) =>
        sym.isPackageClass || pre.isGround && (args forall (_.isGround))
      case SingleType(pre, sym) =>
        sym.isPackageClass || pre.isGround
      case ThisType(_) | NoPrefix | WildcardType | NoType | ErrorType | ConstantType(_) =>
        true
      case _ => 
        typeVarToOriginMap(this) eq this
    }

    /** If this is a symbol loader type, load and assign a new type to
     *  `sym'.
     */
    def load(sym: Symbol) {}

    private def findDecl(name: Name, excludedFlags: Int): Symbol = {
      var alts: List[Symbol] = List()
      var sym: Symbol = NoSymbol
      var e: ScopeEntry = decls.lookupEntry(name)
      while (e ne null) {
        if (!e.sym.hasFlag(excludedFlags)) {
          if (sym == NoSymbol) sym = e.sym
          else {
            if (alts.isEmpty) alts = List(sym)
            alts = e.sym :: alts
          }
        }
        e = decls.lookupNextEntry(e)
      }
      if (alts.isEmpty) sym
      else (baseClasses.head.newOverloaded(this, alts))
    }
    
    /**
     *  Find member(s) in this type. If several members matching criteria are found, they are
     *  returned in an OverloadedSymbol
     *  
     *  @param name           The member's name, where nme.ANYNAME means `unspecified' 
     *  @param excludedFlags  Returned members do not have these flags
     *  @param requiredFlags  Returned members do have these flags
     *  @param stableOnly     If set, return only members that are types or stable values
     */
    //TODO: use narrow only for modules? (correct? efficiency gain?)
    def findMember(name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean): Symbol = {
      var suspension: mutable.HashSet[TypeVar] = null
      // if this type contains type variables, put them to sleep for a while -- don't just wipe them out by
      // replacing them by the corresponding type parameter, as that messes up (e.g.) type variables in type refinements
      // without this, the matchesType call would lead to type variables on both sides
      // of a subtyping/equality judgement, which can lead to recursive types being constructed.
      // See (t0851) for a situation where this happens.
      if (!this.isGround) {
        // PP: The foreach below was formerly expressed as:
        //   for(tv @ TypeVar(_, _) <- this) { suspension suspend tv }
        //
        // The tree checker failed this saying a TypeVar is required, but a (Type @unchecked) was found.
        // This is a consequence of using a pattern match and variable binding + ticket #1503, which
        // was addressed by weakening the type of bindings in pattern matches if they occur on the right.
        // So I'm not quite sure why this works at all, as the checker is right that it is mistyped.
        // For now I modified it as below, which achieves the same without error.
        //
        // make each type var in this type use its original type for comparisons instead of collecting constraints
        val susp = new mutable.HashSet[TypeVar] // use a local val so it remains unboxed
        this foreach {
          case tv: TypeVar  => tv.suspended = true; susp += tv
          case _            => 
        }
        suspension = susp
      }

      incCounter(findMemberCount)
      val start = startTimer(findMemberNanos)

      //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG
      var members: Scope = null
      var member: Symbol = NoSymbol
      var excluded = excludedFlags | DEFERRED
      var continue = true
      var self: Type = null
      var membertpe: Type = null
      while (continue) {
        continue = false
        val bcs0 = baseClasses
        var bcs = bcs0
        while (!bcs.isEmpty) {
          val decls = bcs.head.info.decls
          var entry =
            if (name == nme.ANYNAME) decls.elems else decls.lookupEntry(name)
          while (entry ne null) {
            val sym = entry.sym
            if (sym hasAllFlags requiredFlags) {
              val excl = sym.getFlag(excluded)
              if (excl == 0L && 
                  (// omit PRIVATE LOCALS unless selector class is contained in class owning the def.
                   (bcs eq bcs0) ||
                   !sym.isPrivateLocal ||
                   (bcs0.head.hasTransOwner(bcs.head)))) {
                if (name.isTypeName || stableOnly && sym.isStable) {
                  stopTimer(findMemberNanos, start)
                  if (suspension ne null) suspension foreach (_.suspended = false)
                  return sym
                } else if (member == NoSymbol) {
                  member = sym
                } else if (members eq null) {
                  if (member.name != sym.name || 
                      !(member == sym ||
                        member.owner != sym.owner &&
                        !sym.isPrivate && {
                          if (self eq null) self = this.narrow
                          if (membertpe eq null) membertpe = self.memberType(member)
                          (membertpe matches self.memberType(sym))
                        })) {
                    members = new Scope(List(member, sym))
                  }
                } else {
                  var prevEntry = members.lookupEntry(sym.name)
                  var symtpe: Type = null
                  while ((prevEntry ne null) &&
                         !(prevEntry.sym == sym ||
                           prevEntry.sym.owner != sym.owner &&
                           !sym.hasFlag(PRIVATE) && {
                             if (self eq null) self = this.narrow
                             if (symtpe eq null) symtpe = self.memberType(sym)
                             self.memberType(prevEntry.sym) matches symtpe
                           })) {
                    prevEntry = members lookupNextEntry prevEntry
                  }
                  if (prevEntry eq null) {
                    members enter sym
                  }
                }
              } else if (excl == DEFERRED.toLong) {
                continue = true
              }
            }
            entry = if (name == nme.ANYNAME) entry.next else decls lookupNextEntry entry
          } // while (entry ne null)
          // excluded = excluded | LOCAL
          bcs = if (name == nme.CONSTRUCTOR) Nil else bcs.tail
        } // while (!bcs.isEmpty)
        excluded = excludedFlags
      } // while (continue)
      stopTimer(findMemberNanos, start)
      if (suspension ne null) suspension foreach (_.suspended = false)
      if (members eq null) {
        if (member == NoSymbol) incCounter(noMemberCount)
        member
      } else {
        incCounter(multMemberCount)
        baseClasses.head.newOverloaded(this, members.toList)
      }
    }

    /** The existential skolems and existentially quantified variables which are free in this type */
    def existentialSkolems: List[Symbol] = {
      var boundSyms: List[Symbol] = List()
      var skolems: List[Symbol] = List()
      for (t <- this) {
        t match {
          case ExistentialType(quantified, qtpe) =>
            boundSyms = boundSyms ::: quantified
          case TypeRef(_, sym, _) =>
            if ((sym hasFlag EXISTENTIAL) && !(boundSyms contains sym) && !(skolems contains sym))
              skolems = sym :: skolems
          case _ =>
        }
      }
      skolems
    }

    /** Return the annotations on this type. */
    def annotations: List[AnnotationInfo] = Nil

    /** Test for the presence of an annotation */
    def hasAnnotation(clazz: Symbol) = annotations exists { _.atp.typeSymbol == clazz }

    /** Add an annotation to this type */
    def withAnnotation(annot: AnnotationInfo) = withAnnotations(List(annot))
    
    /** Add a number of annotations to this type */
    def withAnnotations(annots: List[AnnotationInfo]): Type =
      annots match {
        case Nil => this
        case _ => AnnotatedType(annots, this, NoSymbol)
      }
      
    /** Remove any annotations from this type */
    def withoutAnnotations = this

    /** Remove any annotations from this type and from any
     *  types embedded in this type. */
    def stripAnnotations = StripAnnotationsMap(this)

    /** Set the self symbol of an annotated type, or do nothing
     *  otherwise.  */
    def withSelfsym(sym: Symbol) = this

    /** The selfsym of an annotated type, or NoSymbol of anything else */
    def selfsym: Symbol = NoSymbol

    /** The kind of this type; used for debugging */
    def kind: String = "unknown type of class "+getClass()
  }

// Subclasses ------------------------------------------------------------

  trait UniqueType {
    override lazy val hashCode: Int = super.hashCode()
  }

 /** A base class for types that defer some operations
   *  to their immediate supertype.
   */
  abstract class SubType extends Type {
    def supertype: Type
    override def parents: List[Type] = supertype.parents
    override def decls: Scope = supertype.decls
    override def baseType(clazz: Symbol): Type = supertype.baseType(clazz)
    override def baseTypeSeq: BaseTypeSeq = supertype.baseTypeSeq
    override def baseTypeSeqDepth: Int = supertype.baseTypeSeqDepth
    override def baseClasses: List[Symbol] = supertype.baseClasses
    override def isNotNull = supertype.isNotNull
  }

  case class NotNullType(override val underlying: Type) extends SubType with RewrappingTypeProxy {
    def supertype = underlying
    protected def rewrap(newtp: Type): Type = NotNullType(newtp)
    override def isNotNull: Boolean = true
    override def notNull = this
    override def deconst: Type = underlying //todo: needed?
    override def safeToString: String = underlying.toString + " with NotNull"
    override def kind = "NotNullType"
  }

  /** A base class for types that represent a single value
   *  (single-types and this-types).
   */
  abstract class SingletonType extends SubType with SimpleTypeProxy {
    def supertype = underlying
    override def isTrivial = false
    override def isStable = true
    override def isVolatile = underlying.isVolatile
    override def widen: Type = underlying.widen
    override def baseTypeSeq: BaseTypeSeq = {
      incCounter(singletonBaseTypeSeqCount)
      underlying.baseTypeSeq prepend this
    }
    override def isHigherKinded = false // singleton type classifies objects, thus must be kind *
    override def safeToString: String = prefixString + "type"
/*
    override def typeOfThis: Type = typeSymbol.typeOfThis
    override def bounds: TypeBounds = TypeBounds(this, this)
    override def prefix: Type = NoType
    override def typeArgs: List[Type] = List()
    override def typeParams: List[Symbol] = List()
*/
  }

  /** An object representing an erroneous type */
  case object ErrorType extends Type {
    // todo see whether we can do without
    override def isError: Boolean = true
    override def decls: Scope = new ErrorScope(NoSymbol)
    override def findMember(name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean): Symbol = {
      var sym = decls lookup name
      if (sym == NoSymbol) {
        sym = NoSymbol.newErrorSymbol(name)
        decls enter sym
      }
      sym
    }
    override def baseType(clazz: Symbol): Type = this
    override def safeToString: String = "<error>"
    override def narrow: Type = this
    // override def isNullable: Boolean = true
    override def kind = "ErrorType"
  }

  /** An object representing an unknown type, used during type inference.
   *  If you see WildcardType outside of inference it is almost certainly a bug.
   */
  case object WildcardType extends Type {
    override def isWildcard = true
    override def safeToString: String = "?"
    // override def isNullable: Boolean = true
    override def kind = "WildcardType"
  }

  case class BoundedWildcardType(override val bounds: TypeBounds) extends Type {
    override def isWildcard = true
    override def safeToString: String = "?" + bounds
    override def kind = "BoundedWildcardType"
  }

  /** An object representing a non-existing type */
  case object NoType extends Type {
    override def isTrivial: Boolean = true
    override def safeToString: String = "<notype>"
    // override def isNullable: Boolean = true
    override def kind = "NoType"
  }

  /** An object representing a non-existing prefix */
  case object NoPrefix extends Type {
    override def isTrivial: Boolean = true
    override def isStable: Boolean = true
    override def prefixString = ""
    override def safeToString: String = "<noprefix>"
    // override def isNullable: Boolean = true
    override def kind = "NoPrefixType"
  }

  /** A class for this-types of the form <sym>.this.type 
   */
  abstract case class ThisType(sym: Symbol) extends SingletonType {
    //assert(sym.isClass && !sym.isModuleClass || sym.isRoot, sym)
    override def isTrivial: Boolean = sym.isPackageClass
    override def isNotNull = true
    override def typeSymbol = sym
    override def underlying: Type = sym.typeOfThis
    override def isVolatile = false
    override def isHigherKinded = sym.isRefinementClass && underlying.isHigherKinded
    override def prefixString =
      if (settings.debug.value) sym.nameString + ".this."
      else if (sym.isAnonOrRefinementClass) "this."
      else if (sym.printWithoutPrefix) ""
      else if (sym.isModuleClass) sym.fullName + "."
      else sym.nameString + ".this."
    override def safeToString: String =
      if (sym.isRoot) "<root>"
      else if (sym.isEmptyPackageClass) "<empty>"
      else super.safeToString
    override def narrow: Type = this
    override def kind = "ThisType"
  }

  final class UniqueThisType(sym: Symbol) extends ThisType(sym) with UniqueType { }
  object ThisType extends ThisTypeExtractor {
    def apply(sym: Symbol): Type = {
      if (!phase.erasedTypes) unique(new UniqueThisType(sym))
      else if (sym.isImplClass) sym.typeOfThis
      else sym.tpe
    }
  }

  /** A class for singleton types of the form <prefix>.<sym.name>.type.
   *  Cannot be created directly; one should always use
   *  `singleType' for creation.
   */
  abstract case class SingleType(pre: Type, sym: Symbol) extends SingletonType {
    override val isTrivial: Boolean = pre.isTrivial
    // override def isNullable = underlying.isNullable
    override def isNotNull = underlying.isNotNull
    private var underlyingCache: Type = NoType
    private var underlyingPeriod = NoPeriod
    override def underlying: Type = {
      val period = underlyingPeriod
      if (period != currentPeriod) {
        underlyingPeriod = currentPeriod
        if (!isValid(period)) {
          underlyingCache = pre.memberType(sym).resultType;
          assert(underlyingCache ne this, this)
        }
      }
      underlyingCache
    }

    // more precise conceptually, but causes cyclic errors:    (paramss exists (_ contains sym))
    override def isImmediatelyDependent = (sym ne NoSymbol) && (sym.owner.isMethod && sym.isValueParameter)

    override def isVolatile : Boolean = underlying.isVolatile && !sym.isStable
/*
    override def narrow: Type = {
      if (phase.erasedTypes) this
      else {
        val thissym = refinedType(List(this), sym.owner, EmptyScope).typeSymbol
        if (sym.owner != NoSymbol) {
          //Console.println("narrowing module " + sym + thissym.owner);
          thissym.typeOfThis = this
        }
        thissym.thisType
      }
    }
*/
    override def narrow: Type = this

    override def termSymbol = sym
    override def prefix: Type = pre
    override def prefixString: String = 
      if ((sym.isEmptyPackage || sym.isInterpreterWrapper || sym.isPredefModule || sym.isScalaPackage) && !settings.debug.value) ""
      else pre.prefixString + sym.nameString + "."
    override def kind = "SingleType"
  }

  final class UniqueSingleType(pre: Type, sym: Symbol) extends SingleType(pre, sym) with UniqueType { }
  object SingleType extends SingleTypeExtractor {
    def apply(pre: Type, sym: Symbol): Type = {
      unique(new UniqueSingleType(pre, sym))
    }
  }

  abstract case class SuperType(thistpe: Type, supertpe: Type) extends SingletonType {
    override val isTrivial: Boolean = thistpe.isTrivial && supertpe.isTrivial
    override def isNotNull = true;
    override def typeSymbol = thistpe.typeSymbol
    override def underlying = supertpe
    override def prefix: Type = supertpe.prefix
    override def prefixString = thistpe.prefixString.replaceAll("""this\.$""", "super.")
    override def narrow: Type = thistpe.narrow
    override def kind = "SuperType"
  }

  final class UniqueSuperType(thistp: Type, supertp: Type) extends SuperType(thistp, supertp) with UniqueType { }
  object SuperType extends SuperTypeExtractor {
    def apply(thistp: Type, supertp: Type): Type = {
      if (phase.erasedTypes) supertp
      else unique(new UniqueSuperType(thistp, supertp))
    }
  }

  /** A class for the bounds of abstract types and type parameters
   */
  abstract case class TypeBounds(lo: Type, hi: Type) extends SubType {
    def supertype = hi
    override val isTrivial: Boolean = lo.isTrivial && hi.isTrivial
    override def bounds: TypeBounds = this
    def containsType(that: Type) = that match {
      case TypeBounds(_, _) => that <:< this 
      case _                => lo <:< that && that <:< hi
    }
    // override def isNullable: Boolean = NullClass.tpe <:< lo;
    override def safeToString = ">: " + lo + " <: " + hi
    override def kind = "TypeBoundsType"
  }

  final class UniqueTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) with UniqueType { }
  object TypeBounds extends TypeBoundsExtractor {
    def empty: TypeBounds           = apply(NothingClass.tpe, AnyClass.tpe)
    def upper(hi: Type): TypeBounds = apply(NothingClass.tpe, hi)
    def lower(lo: Type): TypeBounds = apply(lo, AnyClass.tpe)
    def apply(lo: Type, hi: Type): TypeBounds = {
      unique(new UniqueTypeBounds(lo, hi)).asInstanceOf[TypeBounds]
    }
  }

  /** A common base class for intersection types and class types 
   */
  abstract class CompoundType extends Type {

    var baseTypeSeqCache: BaseTypeSeq = _
    private var baseTypeSeqPeriod = NoPeriod
    private var baseClassesCache: List[Symbol] = _
    private var baseClassesPeriod = NoPeriod

    override def baseTypeSeq: BaseTypeSeq = {
      val period = baseTypeSeqPeriod;
      if (period != currentPeriod) { // no caching in IDE
        baseTypeSeqPeriod = currentPeriod
        if (!isValidForBaseClasses(period)) {
          if (parents.exists(_.exists(_.isInstanceOf[TypeVar]))) {
            // rename type vars to fresh type params, take base type sequence of
            // resulting type, and rename back all the entries in that sequence
            var tvs = Set[TypeVar]()
            for (p <- parents)
              for (t <- p) t match {
                case tv: TypeVar => tvs += tv
                case _ =>
              }
            val varToParamMap: Map[Type, Symbol] = tvs map (tv => tv -> tv.origin.typeSymbol.cloneSymbol) toMap 
            val paramToVarMap = varToParamMap map (_.swap)
            val varToParam = new TypeMap {
              def apply(tp: Type) = varToParamMap get tp match {
                case Some(sym) => sym.tpe
                case _ => mapOver(tp)
              }
            }
            val paramToVar = new TypeMap {
              def apply(tp: Type) = tp match {
                case TypeRef(_, tsym, _) if paramToVarMap.isDefinedAt(tsym) => paramToVarMap(tsym)
                case _ => mapOver(tp)
              }
            }
            val bts = copyRefinedType(this.asInstanceOf[RefinedType], parents map varToParam, varToParam mapOver decls).baseTypeSeq
            baseTypeSeqCache = bts lateMap paramToVar
          } else {
            incCounter(compoundBaseTypeSeqCount)
            baseTypeSeqCache = undetBaseTypeSeq
            baseTypeSeqCache = if (typeSymbol.isRefinementClass)
              memo(compoundBaseTypeSeq(this))(_.baseTypeSeq updateHead typeSymbol.tpe)
            else
              compoundBaseTypeSeq(this)
            // [Martin] suppressing memo-ization solves the problem with "same type after erasure" errors
            // when compiling with 
            // scalac scala.collection.IterableViewLike.scala scala.collection.IterableLike.scala
            // I have not yet figured out precisely why this is the case.
            // My current assumption is that taking memos forces baseTypeSeqs to be computed
            // at stale types (i.e. the underlying typeSymbol has already another type).
            // I do not yet see precisely why this would cause a problem, but it looks
            // fishy in any case.
          }
        }
        //Console.println("baseTypeSeq(" + typeSymbol + ") = " + baseTypeSeqCache.toList);//DEBUG
      }
      if (baseTypeSeqCache eq undetBaseTypeSeq)
        throw new TypeError("illegal cyclic inheritance involving " + typeSymbol)
      baseTypeSeqCache
    }

    override def baseTypeSeqDepth: Int = baseTypeSeq.maxDepth

    override def baseClasses: List[Symbol] = {
      def computeBaseClasses: List[Symbol] =
        if (parents.isEmpty) List(typeSymbol)
        else {
          //Console.println("computing base classes of " + typeSymbol + " at phase " + phase);//DEBUG
          // optimized, since this seems to be performance critical
          val superclazz = parents.head
          var mixins = parents.tail
          val sbcs = superclazz.baseClasses
          var bcs = sbcs
          def isNew(clazz: Symbol): Boolean = (
            superclazz.baseTypeIndex(clazz) < 0 &&
            { var p = bcs;
              while ((p ne sbcs) && (p.head != clazz)) p = p.tail;
              p eq sbcs
            }
          );
          while (!mixins.isEmpty) {
            def addMixinBaseClasses(mbcs: List[Symbol]): List[Symbol] =
              if (mbcs.isEmpty) bcs
              else if (isNew(mbcs.head)) mbcs.head :: addMixinBaseClasses(mbcs.tail)
              else addMixinBaseClasses(mbcs.tail);
            bcs = addMixinBaseClasses(mixins.head.baseClasses)
            mixins = mixins.tail
          }
          typeSymbol :: bcs
         }
      val period = baseClassesPeriod
      if (period != currentPeriod) {
        baseClassesPeriod = currentPeriod
        if (!isValidForBaseClasses(period)) {
          baseClassesCache = null
          baseClassesCache = memo(computeBaseClasses)(typeSymbol :: _.baseClasses.tail)
        }
      }
      if (baseClassesCache eq null)
        throw new TypeError("illegal cyclic reference involving " + typeSymbol)
      baseClassesCache
    }

    /** The slightly less idiomatic use of Options is due to 
     *  performance considerations. A version using for comprehensions
     *  might be too slow (this is deemed a hotspot of the type checker).
     *  
     *  See with Martin before changing this method.
     */
    def memo[A](op1: => A)(op2: Type => A): A = {
      def updateCache(): A = {
        intersectionWitness(parents) = new WeakReference(this)
        op1
      }
      
      intersectionWitness get parents match {
        case Some(ref) =>
          ref.get match {
            case Some(w) => if (w eq this) op1 else op2(w)
            case None => updateCache()
          }
        case None => updateCache() 
      }
     
    }
 
    override def baseType(sym: Symbol): Type = {
      val index = baseTypeIndex(sym)
      if (index >= 0) baseTypeSeq(index) else NoType
    }

    override def narrow: Type = typeSymbol.thisType
    override def isNotNull: Boolean = parents exists (_.isNotNull)
    
    override def isStructuralRefinement: Boolean =
      typeSymbol.isAnonOrRefinementClass &&
        (decls.toList exists { entry => !entry.isConstructor && entry.allOverriddenSymbols.isEmpty })

    // override def isNullable: Boolean =
    // parents forall (p => p.isNullable && !p.typeSymbol.isAbstractType);

    override def safeToString: String =
      parents.mkString(" with ") +
      (if (settings.debug.value || parents.isEmpty || (decls.elems ne null))
        decls.mkString("{", "; ", "}") else "")
  }

  /** A class representing intersection types with refinements of the form
   *    `<parents_0> with ... with <parents_n> { decls }'
   *  Cannot be created directly;
   *  one should always use `refinedType' for creation.
   */
  case class RefinedType(override val parents: List[Type],
                         override val decls: Scope) extends CompoundType {

    override def isHigherKinded = (
      parents.nonEmpty && 
      (parents forall (_.isHigherKinded)) &&
      !phase.erasedTypes    // @MO to AM: please check this class!
    )

    override def typeParams = 
      if (isHigherKinded) parents.head.typeParams
      else super.typeParams

    //@M may result in an invalid type (references to higher-order args become dangling )
    override def typeConstructor = 
      copyRefinedType(this, parents map (_.typeConstructor), decls)
    
    private def dummyArgs = typeParams map (_.typeConstructor)

    /* MO to AM: This is probably not correct
     * If they are several higher-kinded parents with different bounds we need
     * to take the intersection of their bounds
     */
    override def normalize = {
      if (isHigherKinded) {
        typeFun(
          typeParams,
          RefinedType(
            parents map {
              case TypeRef(pre, sym, List()) => TypeRef(pre, sym, dummyArgs)
              case p => p
            },
            decls,
            typeSymbol))
      }
      else super.normalize
    }

    /** A refined type P1 with ... with Pn { decls } is volatile if
     *  one of the parent types Pi is an abstract type, and
     *  either i > 1, or decls or a following parent Pj, j > 1, contributes
     *  an abstract member.
     *  A type contributes an abstract member if it has an abstract member which
     *  is also a member of the whole refined type. A scope `decls' contributes
     *  an abstract member if it has an abstract definition which is also
     *  a member of the whole type.
     */
    override def isVolatile = {
      def isVisible(m: Symbol) = 
        this.nonPrivateMember(m.name).alternatives contains m
      def contributesAbstractMembers(p: Type) = 
        p.deferredMembers exists isVisible

      ((parents exists (_.isVolatile)) 
       ||
       (parents dropWhile (! _.typeSymbol.isAbstractType) match {
         case ps @ (_ :: ps1) => 
           (ps ne parents) ||
           (ps1 exists contributesAbstractMembers) ||
           (decls.iterator exists (m => m.isDeferred && isVisible(m)))
         case _ =>
           false
       }))
    }

    override def kind = "RefinedType"
  }

  final class RefinedType0(parents: List[Type], decls: Scope, clazz: Symbol) extends RefinedType(parents, decls) {
    override def typeSymbol = clazz
  }
  object RefinedType extends RefinedTypeExtractor {
    def apply(parents: List[Type], decls: Scope, clazz: Symbol): RefinedType =
      new RefinedType0(parents, decls, clazz)
  }

  /** A class representing a class info
   */
  case class ClassInfoType(
    override val parents: List[Type],
    override val decls: Scope,
    override val typeSymbol: Symbol) extends CompoundType 
  {
    
    /** refs indices */
    private final val NonExpansive = 0
    private final val Expansive = 1

    /** initialization states */
    private final val UnInitialized = 0
    private final val Initializing = 1
    private final val Initialized = 2

    private type RefMap = Map[Symbol, immutable.Set[Symbol]]

    /** All type parameters reachable from given type parameter
     *  by a path which contains at least one expansive reference.
     *  @See Kennedy, Pierce: On Decidability of Nominal Subtyping with Variance
     */
    def expansiveRefs(tparam: Symbol) = {
      if (state == UnInitialized) {
        computeRefs()
        while (state != Initialized) propagate()
      }
      getRefs(Expansive, tparam)
    }

    /* The rest of this class is auxiliary code for `expansiveRefs'
     */

    /** The type parameters which are referenced type parameters of this class.
     *  Two entries: refs(0): Non-expansive references
     *               refs(1): Expansive references
     */
    private var refs: Array[RefMap] = _

    /** The initialization state of the class: UnInialized --> Initializing --> Initialized
     */
    private var state = UnInitialized

    /** Get references for given type parameter
     *  @param  which in {NonExpansive, Expansive}
     *  @param  from  The type parameter from which references originate.
     */
    private def getRefs(which: Int, from: Symbol): Set[Symbol] = refs(which) get from match {
      case Some(set) => set
      case none => Set()
    }

    /** Augment existing refs map with reference <pre>from -> to</pre> 
     *  @param  which <- {NonExpansive, Expansive}
     */
    private def addRef(which: Int, from: Symbol, to: Symbol) {
      refs(which) = refs(which) + (from -> (getRefs(which, from) + to))
    }

    /** Augment existing refs map with references <pre>from -> sym</pre>, for
     *  all elements <pre>sym</pre> of set `to'.
     *  @param  which <- {NonExpansive, Expansive}
     */
    private def addRefs(which: Int, from: Symbol, to: Set[Symbol]) {
      refs(which) = refs(which) + (from -> (getRefs(which, from) ++ to))
    }

    /** The ClassInfoType which belongs to the class containing given type parameter 
     */
    private def classInfo(tparam: Symbol): ClassInfoType = 
      tparam.owner.info.resultType match {
        case ci: ClassInfoType => ci
        case _ => classInfo(ObjectClass) // something's wrong; fall back to safe value
                                         // (this can happen only for erroneous programs).
      }

    /** Compute initial (one-step) references and set state to `Initializing'.
     */
    private def computeRefs() {
      refs = Array(Map(), Map())
      for (tparam <- typeSymbol.typeParams) {
        val enterRefs = new TypeMap {
          def apply(tp: Type): Type = {
            tp match {
              case TypeRef(_, sym, args) =>
                for ((tparam1, arg) <- sym.info.typeParams zip args)
                  if (arg contains tparam) {
                    addRef(NonExpansive, tparam, tparam1)
                    if (arg.typeSymbol != tparam) addRef(Expansive, tparam, tparam1)
                  }
              case _ =>
            }
            mapOver(tp)
          }
        }
        for (p <- parents) enterRefs(p)
      }
      state = Initializing
    }

    /** Propagate to form transitive closure.
     *  Set state to Initialized if no change resulted from propagation.
     *  @return   true iff there as a change in last iteration
     */
    private def propagate(): Boolean = {
      if (state == UnInitialized) computeRefs()
      //Console.println("Propagate "+symbol+", initial expansive = "+refs(Expansive)+", nonexpansive = "+refs(NonExpansive))//DEBUG
      val lastRefs = Array(refs(0), refs(1))
      state = Initialized
      var change = false
      for ((from, targets) <- refs(NonExpansive).iterator)
        for (target <- targets) {
          var thatInfo = classInfo(target)
          if (thatInfo.state != Initialized) 
            change = change | thatInfo.propagate()
          addRefs(NonExpansive, from, thatInfo.getRefs(NonExpansive, target))
          addRefs(Expansive, from, thatInfo.getRefs(Expansive, target))
        }
      for ((from, targets) <- refs(Expansive).iterator)
        for (target <- targets) {
          var thatInfo = classInfo(target)
          if (thatInfo.state != Initialized) 
            change = change | thatInfo.propagate()
          addRefs(Expansive, from, thatInfo.getRefs(NonExpansive, target))
        }
      change = change || refs(0) != lastRefs(0) || refs(1) != lastRefs(1)
      if (change) state = Initializing
      //else Console.println("Propagate "+symbol+", final expansive = "+refs(Expansive)+", nonexpansive = "+refs(NonExpansive))//DEBUG
      change
    }

    // override def isNullable: Boolean =
    // symbol == AnyClass ||
    // symbol != NothingClass && (symbol isSubClass ObjectClass) && !(symbol isSubClass NonNullClass);

    // override def isNonNull: Boolean = symbol == NonNullClass || super.isNonNull;
    override def kind = "ClassInfoType"
  }

  object ClassInfoType extends ClassInfoTypeExtractor

  class PackageClassInfoType(decls: Scope, clazz: Symbol)
  extends ClassInfoType(List(), decls, clazz)

  /** A class representing a constant type.
   *
   *  @param value ...
   */
  abstract case class ConstantType(value: Constant) extends SingletonType {
    override def underlying: Type = value.tpe
    assert(underlying.typeSymbol != UnitClass)
    override def isTrivial: Boolean = true
    override def isNotNull = value.value != null
    override def deconst: Type = underlying
    override def safeToString: String =
      underlying.toString + "(" + value.escapedStringValue + ")"
    // override def isNullable: Boolean = value.value eq null
    // override def isNonNull: Boolean = value.value ne null
    override def kind = "ConstantType"
  }

  final class UniqueConstantType(value: Constant) extends ConstantType(value) with UniqueType {
    /** Save the type of 'value'. For Java enums, it depends on finding the linked class,
     *  which might not be found after 'flatten'. */
    private lazy val _tpe: Type = value.tpe
    override def underlying: Type = _tpe
  }
  object ConstantType extends ConstantTypeExtractor {
    def apply(value: Constant): ConstantType = {
      unique(new UniqueConstantType(value)).asInstanceOf[ConstantType]
    }
  }

  private var volatileRecursions: Int = 0
  private val pendingVolatiles = new mutable.HashSet[Symbol]

  /** A class for named types of the form
   *  `<prefix>.<sym.name>[args]'
   *  Cannot be created directly; one should always use `typeRef'
   *  for creation. (@M: Otherwise hashing breaks)
   *
   * @M: a higher-kinded type is represented as a TypeRef with sym.info.typeParams.nonEmpty, but args.isEmpty
   *  @param pre  ...
   *  @param sym  ...
   *  @param args ...
   */
  abstract case class TypeRef(pre: Type, sym: Symbol, args: List[Type]) extends Type {
//    assert(!sym.isAbstractType || pre.isStable || pre.isError)
//    assert(!pre.isInstanceOf[ClassInfoType], this)
//    assert(!(sym hasFlag (PARAM | EXISTENTIAL)) || pre == NoPrefix, this)
//    assert(args.isEmpty || !sym.info.typeParams.isEmpty, this)
//    assert(args.isEmpty || ((sym ne AnyClass) && (sym ne NothingClass))

    private var parentsCache: List[Type] = _
    private var parentsPeriod = NoPeriod
    
    private var baseTypeSeqCache: BaseTypeSeq = _
    private var baseTypeSeqPeriod = NoPeriod

    private var symInfoCache: Type = _
    private var memberInfoCache: Type = _
    private var thisInfoCache: Type = _
    private var relativeInfoCache: Type = _

    private var normalized: Type = null
    

    override def isStable: Boolean = {
      sym == NothingClass ||
      sym == SingletonClass ||
      sym.isAliasType && normalize.isStable ||
      sym.isAbstractType && (bounds.hi.typeSymbol isSubClass SingletonClass)
    }

    override def isVolatile: Boolean = {
      sym.isAliasType && normalize.isVolatile ||
      sym.isAbstractType && {
        // need to be careful not to fall into an infinite recursion here
        // because volatile checking is done before all cycles are detected.
        // the case to avoid is an abstract type directly or
        // indirectly upper-bounded by itself. See #2918
        try {
          volatileRecursions += 1
          if (volatileRecursions < LogVolatileThreshold)
            bounds.hi.isVolatile
          else if (pendingVolatiles(sym))
            true // we can return true here, because a cycle will be detected
                 // here afterwards and an error will result anyway.
          else 
            try {
              pendingVolatiles += sym
              bounds.hi.isVolatile
            } finally {
              pendingVolatiles -= sym
            }
        } finally {
          volatileRecursions -= 1
        }
      }
    }

    override lazy val isTrivial: Boolean =
      !sym.isTypeParameter && pre.isTrivial && args.forall(_.isTrivial)

    override def isNotNull = 
      sym.isModuleClass || sym == NothingClass || isValueClass(sym) || super.isNotNull

    // @M: propagate actual type params (args) to `tp', by replacing formal type parameters with actual ones
    // if tp is higher kinded, the "actual" type arguments are types that simply reference the corresponding type parameters  (unbound type variables) 
    def transform(tp: Type): Type = {
      val res = tp.asSeenFrom(pre, sym.owner)
      if (sym.typeParams.isEmpty || (args exists (_.isError)) || isRaw(sym, args)/*#2266/2305*/) res
      else res.instantiateTypeParams(sym.typeParams, typeArgsOrDummies)
    }

    //@M! use appliedType on the polytype that represents the bounds (or if aliastype, the rhs)
    def transformInfo(tp: Type): Type = appliedType(tp.asSeenFrom(pre, sym.owner), typeArgsOrDummies)

    def thisInfo: Type = 
      if (sym.isAliasType) normalize
      else if (!sym.isNonClassType) sym.info
      else {
        val symInfo = sym.info
        if (thisInfoCache == null || (symInfo ne symInfoCache)) {
          symInfoCache = symInfo
          thisInfoCache = transformInfo(symInfo)            
        }
        thisInfoCache
      }
    
    def relativeInfo: Type = 
      if (!sym.isNonClassType) pre.memberInfo(sym)
      else {
        val memberInfo = pre.memberInfo(sym)
        if (relativeInfoCache == null || (memberInfo ne memberInfoCache)) {
          memberInfoCache = memberInfo
          relativeInfoCache = transformInfo(memberInfo)
        }
        relativeInfoCache
      }

    override def typeSymbol = if (sym.isAliasType) normalize.typeSymbol else sym
    override def termSymbol = if (sym.isAliasType) normalize.termSymbol else super.termSymbol
    override def typeSymbolDirect = sym
    override def termSymbolDirect = super.termSymbol

/* @MAT
whenever you see `tp.typeSymbol.isXXXX' and then act on tp based on that predicate, you're on thin ice, 
as `typeSymbol' (and `prefix') automatically normalize, but the other inspectors don't. 
In other words, even if `tp.normalize.sym.isXXX' is true, `tp.sym.isXXX' may be false (if sym were a public method to access the non-normalized typeSymbol)...

In retrospect, I think `tp.typeSymbol.isXXX' or (worse) `tp.typeSymbol==XXX' should be replaced by `val tp = tp0.asXXX'.  
A type's typeSymbol should never be inspected directly.
*/

    override def bounds: TypeBounds =
      if (sym.isAbstractType) thisInfo.bounds // transform(thisInfo.bounds).asInstanceOf[TypeBounds] // ??? seems to be doing asSeenFrom twice
      else super.bounds

    override def parents: List[Type] = { 
      val period = parentsPeriod 
      if (period != currentPeriod) { 
        parentsPeriod = currentPeriod 
        if (!isValidForBaseClasses(period)) { 
          parentsCache = thisInfo.parents map transform 
        } else if (parentsCache == null) { // seems this can happen if things are currupted enough, see #2641 
          parentsCache = List(AnyClass.tpe) 
        } 
      } 
      parentsCache 
    }
    override def typeOfThis = transform(sym.typeOfThis)

/*
    override def narrow =
      if (sym.isModuleClass) transform(sym.thisType) 
      else if (sym.isAliasType) normalize.narrow      
      else super.narrow
*/
    override def narrow =
      if (sym.isModuleClass) singleType(pre, sym.sourceModule)
      else if (sym.isAliasType) normalize.narrow      
      else super.narrow

    override def prefix: Type = 
      if (sym.isAliasType) normalize.prefix
      else pre

    override def typeArgs: List[Type] = args
    private def typeArgsOrDummies = if (!isHigherKinded) args else dummyArgs
    // def hasFishyArgs = args == dummyArgs

    // @MAT was typeSymbol.unsafeTypeParams, but typeSymbol normalizes now
    private def typeParamsDirect =
      if (isDefinitionsInitialized) sym.typeParams
      else sym.unsafeTypeParams

    // placeholders derived from type params
    private def dummyArgs = {
      // @PP to @AM: this appears to me a place where
      // higher-order tparams are going off the beam.
      // if (sym.isAbstractType) { something goes wrong }

      //@M must be .typeConstructor
      typeParamsDirect map (_.typeConstructor)
    }

    // (!result.isEmpty) IFF isHigherKinded
    override def typeParams: List[Symbol] = if (isHigherKinded) typeParamsDirect else List()

    // note: does not go through typeRef. There's no need to because
    // neither `pre` nor `sym` changes.  And there's a performance
    // advantage to call TypeRef directly.
    override def typeConstructor = TypeRef(pre, sym, Nil) 

    // A reference (in a Scala program) to a type that has type
    // parameters, but where the reference does not include type
    // arguments. Note that it doesn't matter whether the symbol refers
    // to a java or scala symbol, it does matter whether it occurs in
    // java or scala code. TypeRefs w/o type params that occur in java
    // signatures/code are considered raw types, and are represented as
    // existential types.
    override def isHigherKinded = args.isEmpty && typeParamsDirect.nonEmpty

    override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]): Type =
      if (isHigherKinded) {
        val substTps = formals.intersect(typeParams)
        
        if (sameLength(substTps, typeParams))
          copyTypeRef(this, pre, sym, actuals)
        else if (sameLength(formals, actuals)) // partial application (needed in infer when bunching type arguments from classes and methods together)
          copyTypeRef(this, pre, sym, dummyArgs).subst(formals, actuals)
        else ErrorType
      }
      else
        super.instantiateTypeParams(formals, actuals)


    /** @pre: sym.info.typeParams.length == typeArgs.length */
    @inline private def betaReduce: Type = {
      // isHKSubType0 introduces synthetic type params so that
      // betaReduce can first apply sym.info to typeArgs before calling
      // asSeenFrom.  asSeenFrom then skips synthetic type params, which
      // are used to reduce HO subtyping to first-order subtyping, but
      // which can't be instantiated from the given prefix and class.
      transform(sym.info.resultType)
      //
      // this crashes pos/depmet_implicit_tpbetareduce.scala
      // appliedType(sym.info, typeArgs).asSeenFrom(pre, sym.owner)
    }

    // @M: initialize (by sym.info call) needed (see test/files/pos/ticket0137.scala)
    @inline private def etaExpand: Type = {
      val tpars = sym.info.typeParams // must go through sym.info for typeParams to initialise symbol
      typeFunAnon(tpars, copyTypeRef(this, pre, sym, tpars map (_.tpeHK))) // todo: also beta-reduce?
    }

    override def dealias: Type = 
      if (sym.isAliasType && sameLength(sym.info.typeParams, args)) {
        betaReduce.dealias
      } else this

    private def normalize0: Type =
      if (pre eq WildcardType) WildcardType // arises when argument-dependent types are approximated (see def depoly in implicits)
      else if (isHigherKinded) etaExpand   // eta-expand, subtyping relies on eta-expansion of higher-kinded types
      else if (sym.isAliasType && sameLength(sym.info.typeParams, args))
                               betaReduce.normalize // beta-reduce, but don't do partial application -- cycles have been checked in typeRef
      else if (sym.isRefinementClass) 
                               sym.info.normalize // I think this is okay, but see #1241 (r12414), #2208, and typedTypeConstructor in Typers
      else {
        if(sym.isAliasType) ErrorType //println("!!error: "+(pre, sym, sym.info, sym.info.typeParams, args))
        else super.normalize
      }

   // TODO: test case that is compiled  in a specific order and in different runs
    override def normalize: Type = {
      if (phase.erasedTypes) normalize0
      else {
        if (normalized == null)
          normalized = normalize0
        
        normalized
      }
    }

    override def decls: Scope = {
      sym.info match {
        case TypeRef(_, sym1, _) =>
          assert(sym1 != sym, this) // @MAT was != typeSymbol
        case _ =>
      }
      thisInfo.decls
    }

    override def baseType(clazz: Symbol): Type =
      if (sym == clazz) this
      else if (sym.isClass) transform(sym.info.baseType(clazz))
      else 
        try { 
          basetypeRecursions += 1
          if (basetypeRecursions < LogPendingBaseTypesThreshold)
            relativeInfo.baseType(clazz)
          else if (pendingBaseTypes contains this)
            if (clazz == AnyClass) clazz.tpe else NoType
          else
            try {
              pendingBaseTypes += this
              relativeInfo.baseType(clazz)
            } finally {
              pendingBaseTypes -= this
            }
        } finally {
          basetypeRecursions -= 1
        }

    override def baseTypeSeq: BaseTypeSeq = {
      val period = baseTypeSeqPeriod
      if (period != currentPeriod) {
        baseTypeSeqPeriod = currentPeriod
        if (!isValidForBaseClasses(period)) {
          incCounter(typerefBaseTypeSeqCount)
          baseTypeSeqCache = undetBaseTypeSeq
          baseTypeSeqCache =
            if (sym.isAbstractType) transform(bounds.hi).baseTypeSeq prepend this
            else sym.info.baseTypeSeq map transform
        }
      }
      if (baseTypeSeqCache == undetBaseTypeSeq)
        throw new TypeError("illegal cyclic inheritance involving " + sym)
      baseTypeSeqCache
    }

    override def baseTypeSeqDepth: Int = baseTypeSeq.maxDepth

    override def baseClasses: List[Symbol] = thisInfo.baseClasses

    // override def isNullable: Boolean = sym.info.isNullable

    override def safeToString: String = {
      if (!settings.debug.value) {
        this match {
          case TypeRef(_, RepeatedParamClass, arg :: _) => return arg + "*"
          case TypeRef(_, ByNameParamClass, arg :: _)   => return "=> " + arg
          case _ =>
            if (isFunctionType(this)) {
              val targs = normalize.typeArgs
              // Aesthetics: printing Function1 as T => R rather than (T) => R
              val paramlist = targs.init match {
                case Nil      => "()"
                case x :: Nil => "" + x
                case xs       => xs.mkString("(", ", ", ")")
              }
              return paramlist + " => " + targs.last
            }
            else if (isTupleTypeOrSubtype(this)) 
              return normalize.typeArgs.mkString("(", ", ", if (hasLength(normalize.typeArgs, 1)) ",)" else ")")
            else if (sym.isAliasType && prefixChain.exists(_.termSymbol.isSynthetic)) {
              val normed = normalize;
              if (normed ne this) return normed.toString
            }
        }
      }
      val monopart = 
        if (!settings.debug.value && 
            (shorthands contains sym.fullName) &&
            (sym.ownerChain forall (_.isClass))) // ensure that symbol is not a local copy with a name coincidence 
          sym.name.toString
        else 
          pre.prefixString + sym.nameString
      
      var str = monopart + (if (args.isEmpty) "" else args.mkString("[", ",", "]"))
      if (sym.isPackageClass)
        packagePrefix + str
      else if (sym.isModuleClass)
        objectPrefix + str
      else if (sym.isAnonymousClass && sym.isInitialized && !settings.debug.value && !phase.erasedTypes)
        thisInfo.parents.mkString(" with ") + {
          if (sym.isStructuralRefinement)
            ((decls.toList filter { entry =>
              !entry.isConstructor && entry.allOverriddenSymbols.isEmpty && !entry.isPrivate
            }) map { entry => entry.defString }).mkString("{", "; ", "}") 
          else
            ""
        }
      else if (sym.isRefinementClass && sym.isInitialized)
        thisInfo.toString
      else str
    }

    override def prefixString = "" + (
      if (settings.debug.value) 
        super.prefixString
      else if (sym.printWithoutPrefix) 
        ""
      else if (sym.isPackageClass) 
        sym.fullName + "."
      else if (isStable && nme.isSingletonName(sym.name))
        nme.dropSingletonName(sym.name) + "."
      else 
        super.prefixString
    )
    override def kind = "TypeRef"
  }

  final class UniqueTypeRef(pre: Type, sym: Symbol, args: List[Type]) extends TypeRef(pre, sym, args) with UniqueType { }
  object TypeRef extends TypeRefExtractor {
    def apply(pre: Type, sym: Symbol, args: List[Type]): Type = {
      unique(new UniqueTypeRef(pre, sym, args))
    }
  }

  /** A class representing a method type with parameters.
   *  Note that a parameterless method is represented by a NullaryMethodType:
   *
   *    def m(): Int        MethodType(Nil, Int)
   *    def m: Int          NullaryMethodType(Int)
   */
  case class MethodType(override val params: List[Symbol],
                        override val resultType: Type) extends Type {
    override def isTrivial: Boolean = isTrivial0
    private lazy val isTrivial0 =
      resultType.isTrivial && params.forall{p => p.tpe.isTrivial &&  (
        !settings.YdepMethTpes.value || !(params.exists(_.tpe.contains(p)) || resultType.contains(p)))
      }

    def isImplicit = params.nonEmpty && params.head.isImplicit
    def isJava = false // can we do something like for implicits? I.e. do Java methods without parameters need to be recognized?

    //assert(paramTypes forall (pt => !pt.typeSymbol.isImplClass))//DEBUG
    override def paramSectionCount: Int = resultType.paramSectionCount + 1

    override def paramss: List[List[Symbol]] = params :: resultType.paramss
    
    override def paramTypes = params map (_.tpe)

    override def boundSyms = immutable.Set[Symbol](params ++ resultType.boundSyms: _*)
    
    // AM to TR: #dropNonContraintAnnotations
    // this is needed for plugins to work correctly, only TypeConstraint annotations are supposed to be carried over
    // TODO: this should probably be handled in a more structured way in adapt -- remove this map in resultType and watch the continuations tests fail
    object dropNonContraintAnnotations extends TypeMap {
      override val dropNonConstraintAnnotations = true
      def apply(x: Type) = mapOver(x)
    }

    override def resultType(actuals: List[Type]) = 
      if (isTrivial) dropNonContraintAnnotations(resultType)
      else {
        if (sameLength(actuals, params)) {
          val idm = new InstantiateDependentMap(params, actuals)
          val res = idm(resultType)
          // println("resultTypeDep "+(params, actuals, resultType, idm.existentialsNeeded, "\n= "+ res))
          existentialAbstraction(idm.existentialsNeeded, res)
        } else {
          // Thread.dumpStack()
          // println("resultType "+(params, actuals, resultType))
          if (phase.erasedTypes) resultType
          else existentialAbstraction(params, resultType)
        }
      }

    // implicit args can only be depended on in result type: TODO this may be generalised so that the only constraint is dependencies are acyclic
    def approximate: MethodType = MethodType(params, resultApprox)

    override def finalResultType: Type = resultType.finalResultType

    override def safeToString = paramString(this) + resultType

    override def cloneInfo(owner: Symbol) = {
      val vparams = cloneSymbols(params, owner)
      copyMethodType(this, vparams, resultType.substSym(params, vparams).cloneInfo(owner))
    }

    override def atOwner(owner: Symbol) = 
      if ((params exists (_.owner != owner)) || (resultType.atOwner(owner) ne resultType))
        cloneInfo(owner) 
      else
        this

    override def kind = "MethodType"
  }

  object MethodType extends MethodTypeExtractor

  class JavaMethodType(ps: List[Symbol], rt: Type) extends MethodType(ps, rt) {
    override def isJava = true
  }
  
  case class NullaryMethodType(override val resultType: Type) extends Type {
    // AM to TR: #dropNonContraintAnnotations
    // change isTrivial to the commented version and watch continuations-run/t3225.scala fail
    // isTrivial implies asSeenFrom is bypassed, since it's supposed to be the identity map
    // it's not really the identity due to dropNonContraintAnnotations
    override def isTrivial: Boolean = false //resultType.isTrivial -- `false` to make continuations plugin work (so that asSeenFromMap drops non-constrain annotations even when type doesn't change otherwise)
    override def prefix: Type = resultType.prefix
    override def narrow: Type = resultType.narrow
    override def finalResultType: Type = resultType.finalResultType
    override def termSymbol: Symbol = resultType.termSymbol
    override def typeSymbol: Symbol = resultType.typeSymbol
    override def parents: List[Type] = resultType.parents
    override def decls: Scope = resultType.decls
    override def baseTypeSeq: BaseTypeSeq = resultType.baseTypeSeq
    override def baseTypeSeqDepth: Int = resultType.baseTypeSeqDepth
    override def baseClasses: List[Symbol] = resultType.baseClasses
    override def baseType(clazz: Symbol): Type = resultType.baseType(clazz)
    override def boundSyms = resultType.boundSyms
    override def isVolatile = resultType.isVolatile
    override def safeToString: String = "=> "+ resultType
    override def kind = "NullaryMethodType"
  }

  object NullaryMethodType extends NullaryMethodTypeExtractor 

  /** A type function or the type of a polymorphic value (and thus of kind *).
   *
   * Before the introduction of NullaryMethodType, a polymorphic nullary method (e.g, def isInstanceOf[T]: Boolean) 
   * used to be typed as PolyType(tps, restpe), and a monomorphic one as PolyType(Nil, restpe)
   * This is now: PolyType(tps, NullaryMethodType(restpe)) and NullaryMethodType(restpe)
   * by symmetry to MethodTypes: PolyType(tps, MethodType(params, restpe)) and MethodType(params, restpe)
   *
   * Thus, a PolyType(tps, TypeRef(...)) unambiguously indicates a type function (which results from eta-expanding a type constructor alias).
   * Similarly, PolyType(tps, ClassInfoType(...)) is a type constructor.
   * 
   * A polytype is of kind * iff its resultType is a (nullary) method type.
   */
  case class PolyType(override val typeParams: List[Symbol], override val resultType: Type)
       extends Type {
    //assert(!(typeParams contains NoSymbol), this)
    assert(typeParams nonEmpty, this) // used to be a marker for nullary method type, illegal now (see @NullaryMethodType)

    override def paramSectionCount: Int = resultType.paramSectionCount
    override def paramss: List[List[Symbol]] = resultType.paramss
    override def params: List[Symbol] = resultType.params
    override def paramTypes: List[Type] = resultType.paramTypes
    override def parents: List[Type] = resultType.parents
    override def decls: Scope = resultType.decls
    override def termSymbol: Symbol = resultType.termSymbol
    override def typeSymbol: Symbol = resultType.typeSymbol
    override def boundSyms = immutable.Set[Symbol](typeParams ++ resultType.boundSyms: _*)
    override def prefix: Type = resultType.prefix
    override def baseTypeSeq: BaseTypeSeq = resultType.baseTypeSeq
    override def baseTypeSeqDepth: Int = resultType.baseTypeSeqDepth
    override def baseClasses: List[Symbol] = resultType.baseClasses
    override def baseType(clazz: Symbol): Type = resultType.baseType(clazz)
    override def narrow: Type = resultType.narrow
    override def isVolatile = resultType.isVolatile
    override def finalResultType: Type = resultType.finalResultType

    /** @M: typeDefSig wraps a TypeBounds in a PolyType 
     *  to represent a higher-kinded type parameter
     *  wrap lo&hi in polytypes to bind variables
     */
    override def bounds: TypeBounds = 
      TypeBounds(typeFun(typeParams, resultType.bounds.lo), 
                 typeFun(typeParams, resultType.bounds.hi))

    override def isHigherKinded = !typeParams.isEmpty
    
    override def safeToString = typeParamsString(this) + resultType

    override def cloneInfo(owner: Symbol) = {
      val tparams = cloneSymbols(typeParams, owner)
      PolyType(tparams, resultType.substSym(typeParams, tparams).cloneInfo(owner))
    }

    override def atOwner(owner: Symbol) = 
      if ((typeParams exists (_.owner != owner)) || (resultType.atOwner(owner) ne resultType))
        cloneInfo(owner) 
      else
        this

    override def kind = "PolyType"
  }

  object PolyType extends PolyTypeExtractor 

  case class ExistentialType(quantified: List[Symbol], 
                             override val underlying: Type) extends RewrappingTypeProxy
  {
    override protected def rewrap(newtp: Type) = existentialAbstraction(quantified, newtp)

    override def isTrivial = false
    override def isStable: Boolean = false
    override def bounds = TypeBounds(maybeRewrap(underlying.bounds.lo), maybeRewrap(underlying.bounds.hi))
    override def parents = underlying.parents map maybeRewrap
    override def boundSyms = quantified.toSet
    override def prefix = maybeRewrap(underlying.prefix)
    override def typeArgs = underlying.typeArgs map maybeRewrap
    override def params = underlying.params mapConserve { param =>
      val tpe1 = rewrap(param.tpe)
      if (tpe1 eq param.tpe) param else param.cloneSymbol.setInfo(tpe1)
    }
    override def paramTypes = underlying.paramTypes map maybeRewrap
    override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]) = {
//      maybeRewrap(underlying.instantiateTypeParams(formals, actuals))

      val quantified1 = new SubstTypeMap(formals, actuals) mapOver quantified
      val underlying1 = underlying.instantiateTypeParams(formals, actuals)
      if ((quantified1 eq quantified) && (underlying1 eq underlying)) this
      else existentialAbstraction(quantified1, underlying1.substSym(quantified, quantified1))

    }
    override def baseType(clazz: Symbol) = maybeRewrap(underlying.baseType(clazz))
    override def baseTypeSeq = underlying.baseTypeSeq map maybeRewrap
    override def isHigherKinded = false

    override def skolemizeExistential(owner: Symbol, origin: AnyRef) = {
      def mkSkolem(tparam: Symbol): Symbol = {
        val skolem = new TypeSkolem(
          if (owner == NoSymbol) tparam.owner else owner,
          tparam.pos, tparam.name.toTypeName, origin)
        skolem.setInfo(tparam.info.cloneInfo(skolem))
              .setFlag(tparam.flags | EXISTENTIAL)
              .resetFlag(PARAM)
      }
      val skolems = quantified map mkSkolem
      for (skolem <- skolems) 
        skolem setInfo skolem.info.substSym(quantified, skolems)
      underlying.substSym(quantified, skolems)
    }

    private def wildcardArgsString(available: Set[Symbol], args: List[Type]): List[String] = args match {
      case TypeRef(_, sym, _) :: args1 if (available contains sym) =>
        ("_"+sym.infoString(sym.info)) :: wildcardArgsString(available - sym, args1)
      case arg :: args1 if !(quantified exists (arg contains _)) =>
        arg.toString :: wildcardArgsString(available, args1) 
      case _ =>
        List()
    }

    override def safeToString: String = {
      if (!(quantified exists (_.isSingletonExistential)) && !settings.debug.value)
        // try to represent with wildcards first
        underlying match {
          case TypeRef(pre, sym, args) if args.nonEmpty =>
            val wargs = wildcardArgsString(quantified.toSet, args)
            if (sameLength(wargs, args))
              return TypeRef(pre, sym, List()) + wargs.mkString("[", ", ", "]")
          case _ =>
        }
      var ustr = underlying.toString
      underlying match {
        case MethodType(_, _) | NullaryMethodType(_) | PolyType(_, _) => ustr = "("+ustr+")"
        case _ =>
      }
      val str = 
        ustr+(quantified map (_.existentialToString) mkString(" forSome { ", "; ", " }"))
      if (settings.explaintypes.value) "("+str+")" else str
    }

    override def cloneInfo(owner: Symbol) = {
      val tparams = cloneSymbols(quantified, owner)
      ExistentialType(tparams, underlying.substSym(quantified, tparams))
    }

    override def atOwner(owner: Symbol) = 
      if (quantified exists (_.owner != owner)) cloneInfo(owner) else this

    override def kind = "ExistentialType"

    def withTypeVars(op: Type => Boolean): Boolean = withTypeVars(op, AnyDepth)

    def withTypeVars(op: Type => Boolean, depth: Int): Boolean = {
      val quantifiedFresh = cloneSymbols(quantified)
      val tvars = quantifiedFresh map (tparam => TypeVar(tparam))
      val underlying1 = underlying.instantiateTypeParams(quantified, tvars) // fuse subst quantified -> quantifiedFresh -> tvars
      op(underlying1) && {
        solve(tvars, quantifiedFresh, quantifiedFresh map (x => 0), false, depth) &&
        isWithinBounds(NoPrefix, NoSymbol, quantifiedFresh, tvars map (_.constr.inst))
      }
    }
  }

  object ExistentialType extends ExistentialTypeExtractor 

  /** A class containing the alternatives and type prefix of an overloaded symbol.
   *  Not used after phase `typer'.
   */
  case class OverloadedType(pre: Type, alternatives: List[Symbol]) extends Type {
    override def prefix: Type = pre
    override def safeToString =
      (alternatives map pre.memberType).mkString("", " <and> ", "")
    override def kind = "OverloadedType"
  }

  /** A class remembering a type instantiation for some a set of overloaded
   *  polymorphic symbols.
   *  Not used after phase `typer'.
   */
  case class AntiPolyType(pre: Type, targs: List[Type]) extends Type {
    override def safeToString =
      pre.toString + targs.mkString("(with type arguments ", ",", ")");
    override def memberType(sym: Symbol) = appliedType(pre.memberType(sym), targs)
//     override def memberType(sym: Symbol) = pre.memberType(sym) match {
//       case PolyType(tparams, restp) => 
//         restp.subst(tparams, targs)
// /* I don't think this is needed, as existential types close only over value types
//       case ExistentialType(tparams, qtpe) => 
//         existentialAbstraction(tparams, qtpe.memberType(sym))
// */ 
//       case ErrorType => 
//         ErrorType
//     }
    override def kind = "AntiPolyType"
  }

  //private var tidCount = 0  //DEBUG

  //@M 
  // a TypeVar used to be a case class with only an origin and a constr
  // then, constr became mutable (to support UndoLog, I guess),
  // but pattern-matching returned the original constr0 (a bug)
  // now, pattern-matching returns the most recent constr
  object TypeVar {
    // encapsulate suspension so we can automatically link the suspension of cloned
    // typevars to their original if this turns out to be necessary
/*
    def Suspension = new Suspension
    class Suspension {
      private val suspended = mutable.HashSet[TypeVar]()
      def suspend(tv: TypeVar): Unit = {
        tv.suspended = true
        suspended += tv
      }
      def resumeAll(): Unit = {
        for (tv <- suspended) {
          tv.suspended = false
        }
        suspended.clear()
      }
    }
*/
    def unapply(tv: TypeVar): Some[(Type, TypeConstraint)] = Some((tv.origin, tv.constr))
    def apply(origin: Type, constr: TypeConstraint) = new TypeVar(origin, constr, List(), List())
    // TODO why not initialise TypeConstraint with bounds of tparam?
    // @PP: I tried that, didn't work out so well for me.
    def apply(tparam: Symbol) = new TypeVar(tparam.tpeHK, new TypeConstraint, List(), tparam.typeParams) 
    def apply(origin: Type, constr: TypeConstraint, args: List[Type], params: List[Symbol]) =
      new TypeVar(origin, constr, args, params)
  }
  
  /** A class representing a type variable 
   * Not used after phase `typer'.
   * A higher-kinded type variable has type arguments (a list of Type's) and type parameters (list of Symbols)
   * A TypeVar whose list of args is non-empty can only be instantiated by a higher-kinded type that can be applied to these args   
   * a typevar is much like a typeref, except it has special logic for type equality/subtyping
   */
  class TypeVar(val origin: Type, val constr0: TypeConstraint, override val typeArgs: List[Type], override val params: List[Symbol]) extends Type {
    // params are needed to keep track of variance (see mapOverArgs in SubstMap)
    assert(typeArgs.isEmpty || sameLength(typeArgs, params))
    // var tid = { tidCount += 1; tidCount } //DEBUG

    /** The constraint associated with the variable */
    var constr = constr0
    def instValid = constr.instValid
    
    /** The variable's skolemization level */
    val level = skolemizationLevel

    /**
     *  two occurrences of a higher-kinded typevar, e.g. ?CC[Int] and ?CC[String], correspond to 
     *  *two instances* of TypeVar that share the *same* TypeConstraint
     *  constr for ?CC only tracks type constructors anyway, so when ?CC[Int] <:< List[Int] and ?CC[String] <:< Iterable[String]
     *  ?CC's hibounds contains List and Iterable
     */
    def applyArgs(newArgs: List[Type]): TypeVar =
      if (newArgs.isEmpty) this // SubstMap relies on this (though this check is redundant when called from appliedType...)
      else TypeVar(origin, constr, newArgs, params) // @M TODO: interaction with undoLog??
        // newArgs.length may differ from args.length (could've been empty before)
      // example: when making new typevars, you start out with C[A], then you replace C by ?C, which should yield ?C[A], then A by ?A, ?C[?A]
      // we need to track a TypeVar's arguments, and map over them (see TypeMap::mapOver)
      // TypeVars get applied to different arguments over time (in asSeenFrom)
       // -- see pos/tcpoly_infer_implicit_tuplewrapper.scala
      // thus: make new TypeVar's for every application of a TV to args,
      // inference may generate several TypeVar's for a single type parameter that must be inferred,
      // only one of them is in the set of tvars that need to be solved, but
      // they share the same TypeConstraint instance

    // <region name="constraint mutators + undoLog">
    // invariant: before mutating constr, save old state in undoLog (undoLog is used to reset constraints to avoid piling up unrelated ones)
    def setInst(tp: Type) {
//      assert(!(tp containsTp this), this)
      undoLog record this
      constr.inst = tp
    }

    def addLoBound(tp: Type, isNumericBound: Boolean = false) {
      assert(tp != this) // implies there is a cycle somewhere (?)
      //println("addLoBound: "+(safeToString, debugString(tp))) //DEBUG
      undoLog record this
      constr.addLoBound(tp, isNumericBound)
    }

    def addHiBound(tp: Type, isNumericBound: Boolean = false) {
      // assert(tp != this)
      //println("addHiBound: "+(safeToString, debugString(tp))) //DEBUG
      undoLog record this
      constr.addHiBound(tp, isNumericBound)
    }
    // </region>

    // ignore subtyping&equality checks while true -- see findMember
    private[Types] var suspended = false

    /** Called when a TypeVar is involved in a subtyping check.  Result is whether
     *  this TypeVar could plausibly be a [super/sub]type of argument `tp` and if so,
     *  tracks tp as a [lower/upper] bound of this TypeVar.
     *
     *  if (isLowerBound)   this typevar could be a subtype, track tp as a lower bound
     *  if (!isLowerBound)  this typevar could be a supertype, track tp as an upper bound
     *
     *  If isNumericBound is true, the subtype check is performed with weak_<:< instead of <:<.
     */
    def registerBound(tp: Type, isLowerBound: Boolean, isNumericBound: Boolean = false): Boolean = {
      // println("regBound: "+(safeToString, debugString(tp), isLowerBound)) //@MDEBUG
      if (isLowerBound) assert(tp != this)

      def checkSubtypeLower(tp1: Type, tp2: Type) =
        if (isNumericBound) tp1 weak_<:< tp2
        else tp1 <:< tp2
      
      // swaps the arguments if it's an upper bound
      def checkSubtype(tp1: Type, tp2: Type) =
        if (isLowerBound) checkSubtypeLower(tp1, tp2)
        else checkSubtypeLower(tp2, tp1)

      def addBound(tp: Type) = { 
        if (isLowerBound) addLoBound(tp, isNumericBound)
        else addHiBound(tp, isNumericBound)
        // println("addedBound: "+(this, tp)) // @MDEBUG
        true
      }
      
      /** Simple case: type arguments can be ignored, because either this typevar has
       *  no type parameters, or we are comparing to Any/Nothing.
       *
       *  The latter condition is needed because HK unification is limited to constraints of the shape
       *    TC1[T1,..., TN] <: TC2[T'1,...,T'N]
       *  which would preclude the following important constraints:
       *    Nothing <: ?TC[?T]
       *    ?TC[?T] <: Any
       */
      def unifySimple = (params.isEmpty || tp.typeSymbol == NothingClass || tp.typeSymbol == AnyClass) && 
        addBound(tp)

      /** Full case: involving a check of the form
       *    TC1[T1,..., TN] <: TC2[T'1,...,T'N]
       *  Checks subtyping of higher-order type vars, and uses variances as defined in the
       *  type parameter we're trying to infer (the result will be sanity-checked later)
       */
      def unifyFull(tp: Type) = sameLength(typeArgs, tp.typeArgs) && { // this is a higher-kinded type var with same arity as tp
        // side effect: adds the type constructor itself as a bound
        addBound(tp.typeConstructor)
        if (isLowerBound) isSubArgs(tp.typeArgs, typeArgs, params)
        else isSubArgs(typeArgs, tp.typeArgs, params)
      }

      /** TODO: need positive/negative test cases demonstrating this is correct.
       */
      def unifyParents =
        if (isLowerBound) tp.parents exists unifyFull
        else tp.parents forall unifyFull        
      
      // TODO: fancier unification, maybe rewrite constraint as follows?
      // val sym = constr.hiBounds map {_.typeSymbol} find { _.typeParams.length == typeArgs.length}
      // this <: tp.baseType(sym)
      if (suspended) checkSubtype(tp, origin)
      else if (constr.instValid) checkSubtype(tp, constr.inst)  // type var is already set
      else isRelatable(tp) && { // gradually let go of some type precision in hopes of finding a type that has the same shape as the type variable
        // okay, this just screams "CLEAN ME UP" -- I think we could use tp.widen instead of tp straight from the get-go in registerBound, since we don't infer singleton types anyway (but maybe that'll change?)
        unifySimple || unifyFull(tp) || unifyFull(tp.dealias) || unifyFull(tp.widen) || unifyFull(tp.widen.dealias) || unifyParents
      }
    }

    def registerTypeEquality(tp: Type, typeVarLHS: Boolean): Boolean = {
      //println("regTypeEq: "+(safeToString, debugString(tp), typeVarLHS)) //@MDEBUG
      def checkIsSameType(tp: Type) = 
        if(typeVarLHS) constr.inst =:= tp
        else           tp          =:= constr.inst

      if (suspended) tp =:= origin
      else if (constr.instValid) checkIsSameType(tp)
      else isRelatable(tp) && {
        val newInst = wildcardToTypeVarMap(tp)
        if (constr.isWithinBounds(newInst)) {
          setInst(tp)
          true
        } else false
      }
    }

    /**
     * ?A.T =:= tp is rewritten as the constraint ?A <: {type T = tp}
     *
     * TODO: make these constraints count (incorporate them into implicit search in applyImplicitArgs)
     * (T corresponds to @param sym)
     */
    def registerTypeSelection(sym: Symbol, tp: Type): Boolean = {
      val bound = refinedType(List(WildcardType), NoSymbol)
      val bsym = bound.typeSymbol.newAliasType(NoPosition, sym.name.toTypeName)
      bsym setInfo tp
      bound.decls enter bsym
      registerBound(bound, false)
    }

    /** Can this variable be related in a constraint to type `tp'?
     *  This is not the case if `tp' contains type skolems whose
     *  skolemization level is higher than the level of this variable.
     */
    def isRelatable(tp: Type): Boolean =
      !tp.exists { t =>
        t.typeSymbol match {
          case ts: TypeSkolem => ts.level > level
          case _ => false
        }
      }

    override val isHigherKinded = typeArgs.isEmpty && params.nonEmpty

    override def normalize: Type =
      if (constr.instValid) constr.inst
      // get here when checking higher-order subtyping of the typevar by itself
      // TODO: check whether this ever happens?
      else if (isHigherKinded) typeFun(params, applyArgs(params map (_.typeConstructor)))
      else super.normalize

    override def typeSymbol = origin.typeSymbol
    override def isStable = origin.isStable
    override def isVolatile = origin.isVolatile

    private def levelString = if (settings.explaintypes.value) level else ""
    override def safeToString = constr.inst match {
      case null   => "<null " + origin + ">"
      case NoType => "?" + levelString + origin + typeArgsString(this)
      case x      => "" + x
    }
    override def kind = "TypeVar"

    def cloneInternal = {
      // cloning a suspended type variable when it's suspended will cause the clone
      // to never be resumed with the current implementation
      assert(!suspended) 
      TypeVar(origin, constr cloneInternal, typeArgs, params) // @M TODO: clone args/params?
    }
  }

  /** A type carrying some annotations. Created by the typechecker
   *  when eliminating ``Annotated'' trees (see typedAnnotated).
   *
   *  @param annotations the list of annotations on the type
   *  @param underlying the type without the annotation
   *  @param selfsym a "self" symbol with type <code>underlying</code>;
   *    only available if -Yself-in-annots is turned on. Can be NoSymbol
   *    if it is not used.
   */
  case class AnnotatedType(override val annotations: List[AnnotationInfo], 
                           override val underlying: Type,
                           override val selfsym: Symbol) 
  extends RewrappingTypeProxy {

    assert(!annotations.isEmpty)

    override protected def rewrap(tp: Type) = AnnotatedType(annotations, tp, selfsym)

    override def isTrivial: Boolean = isTrivial0
    private lazy val isTrivial0 = underlying.isTrivial && (annotations forall (_.isTrivial))

    override def safeToString: String = {
      val attString =
        if (annotations.isEmpty)
          ""
        else
          annotations.mkString(" @", " @", "")

      underlying + attString
    }
    
    /** Add a number of annotations to this type */
    override def withAnnotations(annots: List[AnnotationInfo]): Type =
      copy(annots:::this.annotations)

    /** Remove any annotations from this type */
    override def withoutAnnotations = underlying.withoutAnnotations

    /** Set the self symbol */
    override def withSelfsym(sym: Symbol) = 
      AnnotatedType(annotations, underlying, sym)

    /** Drop the annotations on the bounds, unless but the low and high
     *  bounds are exactly tp.
     */
    override def bounds: TypeBounds = underlying.bounds match {
      case TypeBounds(_: this.type, _: this.type) => TypeBounds(this, this)
      case oftp                                   => oftp
    }

    // ** Replace formal type parameter symbols with actual type arguments. * /
    override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]) = {
      val annotations1 = annotations.map(info => AnnotationInfo(info.atp.instantiateTypeParams(
          formals, actuals), info.args, info.assocs).setPos(info.pos))
      val underlying1 = underlying.instantiateTypeParams(formals, actuals)
      if ((annotations1 eq annotations) && (underlying1 eq underlying)) this
      else AnnotatedType(annotations1, underlying1, selfsym)
    }

    /** Return the base type sequence of tp, dropping the annotations, unless the base type sequence of tp
      * is precisely tp itself. */
    override def baseTypeSeq: BaseTypeSeq = {
       val oftp = underlying.baseTypeSeq
       if ((oftp.length == 1) && (oftp(0) eq underlying))
         baseTypeSingletonSeq(this)
       else
         oftp
     }

    override def kind = "AnnotatedType"
  }

  object AnnotatedType extends AnnotatedTypeExtractor

  /** A class representing types with a name. When an application uses
   *  named arguments, the named argument types for calling isApplicable
   *  are represented as NamedType.
   */
  case class NamedType(name: Name, tp: Type) extends Type {
    override def safeToString: String = name.toString +": "+ tp
  }

  /** A class representing an as-yet unevaluated type.
   */
  abstract class LazyType extends Type with AbsLazyType {
    override def kind = "LazyType"
  }

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

  /** Rebind symbol `sym' to an overriding member in type `pre'.
   */
  private def rebind(pre: Type, sym: Symbol): Symbol = {
    val owner = sym.owner
    if (owner.isClass && owner != pre.typeSymbol && !sym.isEffectivelyFinal && !sym.isClass) {
      //Console.println("rebind "+pre+" "+sym)//DEBUG
      val rebind = pre.nonPrivateMember(sym.name).suchThat(sym => sym.isType || sym.isStable)
      if (rebind == NoSymbol) sym 
      else {
        // Console.println("rebound "+pre+" "+sym+" to "+rebind)//DEBUG
        rebind
      }
    } else sym
  }

  /** Convert a `super' prefix to a this-type if `sym'
   *  is abstract or final.
   */
  private def removeSuper(tp: Type, sym: Symbol): Type = tp match {
    case SuperType(thistp, _) =>
      if (sym.isEffectivelyFinal || sym.isDeferred) thistp
      else tp
    case _ =>
      tp
  }

  /** The canonical creator for single-types */
  def singleType(pre: Type, sym: Symbol): Type = {
    if (phase.erasedTypes)
      sym.tpe.resultType
    else if (sym.isRootPackage)
      ThisType(RootClass)
    else {
      var sym1 = rebind(pre, sym)
      val pre1 = removeSuper(pre, sym1)
      if (pre1 ne pre) sym1 = rebind(pre1, sym1)
      SingleType(pre1, sym1)
    }
  }

  /** the canonical creator for a refined type with a given scope */
  def refinedType(parents: List[Type], owner: Symbol, decls: Scope, pos: Position): Type = {
    if (phase.erasedTypes)
      if (parents.isEmpty) ObjectClass.tpe else parents.head
    else { 
      val clazz = owner.newRefinementClass(NoPosition)
      val result = RefinedType(parents, decls, clazz)
      clazz.setInfo(result)
      result
    }
  }

  /** The canonical creator for a refined type with an initially empty scope.
   *
   *  @param parents ...
   *  @param owner   ...
   *  @return        ...
   */
  def refinedType(parents: List[Type], owner: Symbol): Type =
    refinedType(parents, owner, new Scope, owner.pos)

  def copyRefinedType(original: RefinedType, parents: List[Type], decls: Scope) =
    if ((parents eq original.parents) && (decls eq original.decls)) original
    else {
      val owner = if (original.typeSymbol == NoSymbol) NoSymbol else original.typeSymbol.owner
      val result = refinedType(parents, owner)
      val syms1 = decls.toList
      for (sym <- syms1)
        result.decls.enter(sym.cloneSymbol(result.typeSymbol))
      val syms2 = result.decls.toList
      val resultThis = result.typeSymbol.thisType
      for (sym <- syms2)
        sym.setInfo(sym.info.substThis(original.typeSymbol, resultThis).substSym(syms1, syms2))
      result
    }

  /** The canonical creator for typerefs 
   *  todo: see how we can clean this up a bit
   */
  def typeRef(pre: Type, sym: Symbol, args: List[Type]): Type = {
    // type alias selections are rebound in TypeMap ("coevolved", actually -- see #3731)
    // e.g., when type parameters that are referenced by the alias are instantiated in
    // the prefix.  See pos/depmet_rebind_typealias.
    def rebindTR(pre: Type, sym: Symbol) =
      if (sym.isAbstractType) rebind(pre, sym) else sym
      
    val sym1 = rebindTR(pre, sym)

    // we require that object is initialized, thus info.typeParams instead of typeParams.
    if (sym1.isAliasType && sameLength(sym1.info.typeParams, args)) {
      if (sym1.lockOK) TypeRef(pre, sym1, args) // don't expand type alias (cycles checked by lockOK)
      else throw new TypeError("illegal cyclic reference involving " + sym1)
    }
    else {
      val pre1 = removeSuper(pre, sym1)
      if (pre1 ne pre)
        typeRef(pre1, rebindTR(pre1, sym1), args)
      else pre match {
        case _: CompoundType if sym1.isClass =>
          // sharpen prefix so that it is maximal and still contains the class.
          pre.parents.reverse dropWhile (_.member(sym1.name) != sym1) match {
            case Nil         => TypeRef(pre, sym1, args)
            case parent :: _ => typeRef(parent, sym1, args)
          }
        case _ =>
          TypeRef(pre, sym1, args)
      }
    }
  }

  def copyTypeRef(tp: Type, pre: Type, sym: Symbol, args: List[Type]): Type = tp match {
    case TypeRef(pre0, sym0, args0) =>
      if ((pre == pre0) && (sym.name == sym0.name)) {

        val sym1 = sym
        // we require that object is initialized, thus info.typeParams instead of typeParams.
        if (sym1.isAliasType && sameLength(sym1.info.typeParams, args)) {
          if (sym1.lockOK) TypeRef(pre, sym1, args) // don't expand type alias (cycles checked by lockOK)
          else throw new TypeError("illegal cyclic reference involving " + sym1)
        }
        else {
          TypeRef(pre, sym1, args)
        }
        
      } else
        typeRef(pre, sym, args)
  }




  /** The canonical creator for implicit method types */
  def JavaMethodType(params: List[Symbol], resultType: Type): JavaMethodType =
    new JavaMethodType(params, resultType) // don't unique this!

  /** Create a new MethodType of the same class as tp, i.e. keep JavaMethodType */
  def copyMethodType(tp: Type, params: List[Symbol], restpe: Type): Type = tp match {
    case _: JavaMethodType => JavaMethodType(params, restpe)
    case _ => MethodType(params, restpe)
  }

  /** A creator for intersection type where intersections of a single type are
   *  replaced by the type itself, and repeated parent classes are merged.
   */
  def intersectionType(tps: List[Type], owner: Symbol): Type = tps match {
    case List(tp) =>
      tp
    case _ =>
       refinedType(tps, owner)
/*
      def merge(tps: List[Type]): List[Type] = tps match {
        case tp :: tps1 =>
          val tps1a = tps1 filter (_.typeSymbol.==(tp.typeSymbol))
          val tps1b = tps1 filter (_.typeSymbol.!=(tp.typeSymbol))
          mergePrefixAndArgs(tps1a, -1) match {
            case Some(tp1) => tp1 :: merge(tps1b)
            case None => throw new MalformedType(
              "malformed type: "+refinedType(tps, owner)+" has repeated parent class "+
              tp.typeSymbol+" with incompatible prefixes or type arguments")
          }
        case _ => tps
      } 
      refinedType(merge(tps), owner)
*/
  }

  /** A creator for intersection type where intersections of a single type are
   *  replaced by the type itself. */
  def intersectionType(tps: List[Type]): Type = tps match {
    case List(tp) => tp
    case _ => refinedType(tps, commonOwner(tps))
  }
  
  /** A creator for type applications */
  def appliedType(tycon: Type, args: List[Type]): Type =  
    if (args.isEmpty) tycon //@M! `if (args.isEmpty) tycon' is crucial (otherwise we create new types in phases after typer and then they don't get adapted (??))
    else tycon match { 
      case TypeRef(pre, sym @ (NothingClass|AnyClass), _) => copyTypeRef(tycon, pre, sym, Nil)   //@M drop type args to Any/Nothing
      case TypeRef(pre, sym, _)                           => copyTypeRef(tycon, pre, sym, args)
      case PolyType(tparams, restpe)                      => restpe.instantiateTypeParams(tparams, args)
      case ExistentialType(tparams, restpe)               => ExistentialType(tparams, appliedType(restpe, args))
      case st: SingletonType                              => appliedType(st.widen, args) // @M TODO: what to do? see bug1
      case RefinedType(parents, decls)                    => RefinedType(parents map (appliedType(_, args)), decls) // MO to AM: please check
      case TypeBounds(lo, hi)                             => TypeBounds(appliedType(lo, args), appliedType(hi, args))
      case tv@TypeVar(_, _)                               => tv.applyArgs(args)
      case AnnotatedType(annots, underlying, self)        => AnnotatedType(annots, appliedType(underlying, args), self)
      case ErrorType                                      => tycon
      case WildcardType                                   => tycon // needed for neg/t0226
      case _                                              => abort(debugString(tycon))
    }

  /** A creator for type parameterizations that strips empty type parameter lists.
   * Use this factory method to indicate the type has kind * (it's a polymorphic value) 
   * until we start tracking explicit kinds equivalent to typeFun (except that the latter requires tparams nonEmpty)
   */
  def polyType(tparams: List[Symbol], tpe: Type): Type = 
    if (tparams nonEmpty) typeFun(tparams, tpe)
    else tpe // it's okay to be forgiving here

  /** A creator for anonymous type functions, where the symbol for the type function still needs to be created 
   *
   * TODO:
   * type params of anonymous type functions, which currently can only arise from normalising type aliases, are owned by the type alias of which they are the eta-expansion
   * higher-order subtyping expects eta-expansion of type constructors that arise from a class; here, the type params are owned by that class, but is that the right thing to do?
   */
  def typeFunAnon(tps: List[Symbol], body: Type): Type = typeFun(tps, body)
  
  /** A creator for a type functions, assuming the type parameters tps already have the right owner 
   */
  def typeFun(tps: List[Symbol], body: Type): Type = PolyType(tps, body)

  /** A creator for existential types. This generates:
   *  
   *  tpe1 where { tparams }
   *
   *  where `tpe1' is the result of extrapolating `tpe' wrt to `tparams'. Extrapolating means
   *  that type variables in `tparams' occurring in covariant positions are replaced by upper bounds,
   *  (minus any SingletonClass markers),
   *  type variables in `tparams' occurring in contravariant positions are replaced by upper bounds,
   *  provided the resulting type is legal wrt to stability, and does not contain any
   *  type variable in `tparams'.
   *  The abstraction drops all type parameters that are not directly or indirectly 
   *  referenced by type `tpe1'.
   *  If there are no remaining type parameters, simply returns result type `tpe'. 
   */
  def existentialAbstraction(tparams: List[Symbol], tpe0: Type): Type = 
    if (tparams.isEmpty) tpe0
    else {
      var occurCount = emptySymCount ++ (tparams map (_ -> 0))
      val tpe = deAlias(tpe0)
      def countOccs(tp: Type) =
        for (t <- tp) {
          t match {
            case TypeRef(_, sym, _) =>
              occurCount get sym match {
                case Some(count) => occurCount += (sym -> (count + 1))
                case none =>
              }
            case _ =>
          }
        }
      countOccs(tpe)
      for (tparam <- tparams) countOccs(tparam.info)
          
      val extrapolate = new TypeMap {
        variance = 1
        def apply(tp: Type): Type = {
          val tp1 = mapOver(tp) 
          tp1 match {
            case TypeRef(pre, sym, args) if (variance != 0) && (occurCount isDefinedAt sym) =>
              val repl = if (variance == 1) dropSingletonType(tp1.bounds.hi) else tp1.bounds.lo
              //println("eliminate "+sym+"/"+repl+"/"+occurCount(sym)+"/"+(tparams exists (repl.contains)))//DEBUG
              if (repl.typeSymbol != NothingClass && repl.typeSymbol != NullClass && 
                  occurCount(sym) == 1 && !(tparams exists (repl.contains)))
                repl
              else tp1
            case _ =>
              tp1
          }
        }
        override def mapOver(tp: Type): Type = tp match {
          case SingleType(pre, sym) =>
            if (sym.isPackageClass) tp // short path
            else {
              val pre1 = this(pre)
              if ((pre1 eq pre) || !pre1.isStable) tp
              else singleType(pre1, sym)
            }
          case _ => super.mapOver(tp)
        }

        override def mapOver(tree: Tree) = 
          tree match {
            case tree:Ident if tree.tpe.isStable =>
              // Do not discard the types of existential ident's.
              // The symbol of the Ident itself cannot be listed
              // in the existential's parameters, so the
              // resulting existential type would be ill-formed.
              Some(tree)

            case _ =>
              super.mapOver(tree)
          }
      }
      val tpe1 = extrapolate(tpe)
      var tparams0 = tparams
      var tparams1 = tparams0 filter tpe1.contains

      while (tparams1 != tparams0) {
        tparams0 = tparams1
        tparams1 = tparams filter { p =>
          tparams1 exists { p1 => p1 == p || (p1.info contains p) }
        }
      }
      if (tparams1.isEmpty) tpe1 
      else tpe1 match {
        case ExistentialType(tparams2, tpe2) => ExistentialType(tparams1 ::: tparams2, tpe2)
        case _ => ExistentialType(tparams1, tpe1)
      }
    }

  /** Remove any occurrences of type aliases from this type */
  object deAlias extends TypeMap {
    def apply(tp: Type): Type = mapOver {
      tp match {
        case TypeRef(pre, sym, args) if sym.isAliasType => tp.normalize
        case _ => tp
      }
    }
  }

  /** Remove any occurrence of type <singleton> from this type and its parents */
  object dropSingletonType extends TypeMap {
    def apply(tp: Type): Type = {
      tp match {
        case TypeRef(_, SingletonClass, _) =>
          AnyClass.tpe
        case tp1 @ RefinedType(parents, decls) =>
          var parents1 = parents filter (_.typeSymbol != SingletonClass)
          if (parents1.isEmpty) parents1 = List(AnyClass.tpe)
          if (parents1.tail.isEmpty && decls.isEmpty) mapOver(parents1.head)
          else mapOver(copyRefinedType(tp1, parents1, decls))
        case tp1 => 
          mapOver(tp1)
      }
    }
  }
  
// Hash consing --------------------------------------------------------------

  private val initialUniquesCapacity = 4096
  private var uniques: util.HashSet[Type] = _
  private var uniqueRunId = NoRunId

  private def unique[T <: Type](tp: T): T = {
    incCounter(rawTypeCount)
    if (uniqueRunId != currentRunId) {
      uniques = util.HashSet[Type]("uniques", initialUniquesCapacity)
      uniqueRunId = currentRunId
    }
    (uniques findEntryOrUpdate tp).asInstanceOf[T]
  }

// Helper Classes ---------------------------------------------------------

  /** @PP: Unable to see why these apparently constant types should need vals
   *  in every TypeConstraint, I lifted them out.
   */
  private lazy val numericLoBound = IntClass.tpe
  private lazy val numericHiBound = intersectionType(List(ByteClass.tpe, CharClass.tpe), ScalaPackageClass)

  /** A class expressing upper and lower bounds constraints of type variables, 
   * as well as their instantiations.
   */
  class TypeConstraint(lo0: List[Type], hi0: List[Type], numlo0: Type, numhi0: Type) { 
    def this(lo0: List[Type], hi0: List[Type]) = this(lo0, hi0, NoType, NoType)
    def this() = this(List(), List())

    private var lobounds = lo0
    private var hibounds = hi0
    private var numlo = numlo0
    private var numhi = numhi0

    def loBounds: List[Type] = if (numlo == NoType) lobounds else numlo :: lobounds
    def hiBounds: List[Type] = if (numhi == NoType) hibounds else numhi :: hibounds

    def addLoBound(tp: Type, isNumericBound: Boolean = false) {
      if (isNumericBound && isNumericValueType(tp)) {
        if (numlo == NoType || isNumericSubType(numlo, tp))
          numlo = tp
        else if (!isNumericSubType(tp, numlo))
          numlo = numericLoBound
      }
      else lobounds ::= tp
    }

    def addHiBound(tp: Type, isNumericBound: Boolean = false) {
      if (isNumericBound && isNumericValueType(tp)) {
        if (numhi == NoType || isNumericSubType(tp, numhi))
          numhi = tp
        else if (!isNumericSubType(numhi, tp))
          numhi = numericHiBound
      }
      else hibounds ::= tp
    }

    def isWithinBounds(tp: Type): Boolean =
      lobounds.forall(_ <:< tp) && 
      hibounds.forall(tp <:< _) &&
      (numlo == NoType || (numlo weak_<:< tp)) &&
      (numhi == NoType || (tp weak_<:< numhi))

    var inst: Type = NoType // @M reduce visibility?

    def instValid = (inst ne null) && (inst ne NoType)

    def cloneInternal = {
      val tc = new TypeConstraint(lobounds, hibounds, numlo, numhi)
      tc.inst = inst
      tc
    }
    
    override def toString =
      (loBounds map (_.safeToString)).mkString("[ _>:(", ",", ") ") +
      (hiBounds map (_.safeToString)).mkString("| _<:(", ",", ") ] _= ") + 
      inst.safeToString
  }

  /** A prototype for mapping a function over all possible types
   */
  abstract class TypeMap extends Function1[Type, Type] {
    // deferred inherited: def apply(tp: Type): Type

    /** The variance relative to start. If you want variances to be significant, set
     *  variance = 1
     *  at the top of the typemap.
     */
    var variance = 0

    /** Should this map drop annotations that are not
     *  type-constraint annotations?
     */
    val dropNonConstraintAnnotations = false

    /** Check whether two lists have elements that are eq-equal */
    def allEq[T <: AnyRef](l1: List[T], l2: List[T]) =
      (l1 corresponds l2)(_ eq _)

    // #3731: return sym1 for which holds: pre bound sym.name to sym and pre1 now binds sym.name to sym1, conceptually exactly the same symbol as sym
    // the selection of sym on pre must be updated to the selection of sym1 on pre1,
    // since sym's info was probably updated by the TypeMap to yield a new symbol sym1 with transformed info
    // @returns sym1
    protected def coevolveSym(pre: Type, pre1: Type, sym: Symbol): Symbol =
      if((pre ne pre1) && sym.isAliasType) // only need to rebind type aliases here, as typeRef already handles abstract types (they are allowed to be rebound more liberally)
        (pre, pre1) match {
          case (RefinedType(_, decls), RefinedType(_, decls1)) => // don't look at parents -- it would be an error to override alias types anyway
            //val sym1 =
            decls1.lookup(sym.name)
//            assert(decls.lookupAll(sym.name).toList.length == 1)
//            assert(decls1.lookupAll(sym.name).toList.length == 1)
//            assert(sym1.isAliasType)
//            println("coevolved "+ sym +" : "+ sym.info +" to "+ sym1 +" : "+ sym1.info +" with "+ pre +" -> "+ pre1)
//            sym1
          case _ => // TODO: is there another way a typeref's symbol can refer to a symbol defined in its pre?
//            val sym1 = pre1.nonPrivateMember(sym.name).suchThat(sym => sym.isAliasType)
//            println("??coevolve "+ sym +" : "+ sym.info +" to "+ sym1 +" : "+ sym1.info +" with "+ pre +" -> "+ pre1)
            sym
        }
      else sym

    /** Map this function over given type */
    def mapOver(tp: Type): Type = tp match {
      case TypeRef(pre, sym, args) =>
        val pre1 = this(pre)
        //val args1 = args mapConserve this(_)
        val args1 = if (args.isEmpty) args
                    else {
                      val tparams = sym.typeParams
                      if (tparams.isEmpty) args
                      else mapOverArgs(args, tparams)
                    }
        if ((pre1 eq pre) && (args1 eq args)) tp
        else copyTypeRef(tp, pre1, coevolveSym(pre, pre1, sym), args1) 
      case ThisType(_) => tp
      case SingleType(pre, sym) =>
        if (sym.isPackageClass) tp // short path
        else {
          val pre1 = this(pre)
          if (pre1 eq pre) tp
          else singleType(pre1, sym)
        }
      case MethodType(params, result) =>
        variance = -variance
        val params1 = mapOver(params)
        variance = -variance
        val result1 = this(result)
        if ((params1 eq params) && (result1 eq result)) tp
        // for new dependent types: result1.substSym(params, params1)?
        else copyMethodType(tp, params1, result1.substSym(params, params1))
      case PolyType(tparams, result) =>
        variance = -variance
        val tparams1 = mapOver(tparams)
        variance = -variance
        var result1 = this(result)
        if ((tparams1 eq tparams) && (result1 eq result)) tp
        else PolyType(tparams1, result1.substSym(tparams, tparams1))
      case NullaryMethodType(result) =>
        val result1 = this(result)
        if (result1 eq result) tp
        else NullaryMethodType(result1)
      case ConstantType(_) => tp
      case SuperType(thistp, supertp) =>
        val thistp1 = this(thistp)
        val supertp1 = this(supertp)
        if ((thistp1 eq thistp) && (supertp1 eq supertp)) tp
        else SuperType(thistp1, supertp1)
      case TypeBounds(lo, hi) =>
        variance = -variance
        val lo1 = this(lo)
        variance = -variance
        val hi1 = this(hi)
        if ((lo1 eq lo) && (hi1 eq hi)) tp
        else TypeBounds(lo1, hi1)
      case BoundedWildcardType(bounds) =>
        val bounds1 = this(bounds)
        if (bounds1 eq bounds) tp
        else BoundedWildcardType(bounds1.asInstanceOf[TypeBounds])
      case rtp @ RefinedType(parents, decls) =>
        val parents1 = parents mapConserve (this)
        val decls1 = mapOver(decls)
        //if ((parents1 eq parents) && (decls1 eq decls)) tp
        //else refinementOfClass(tp.typeSymbol, parents1, decls1)
        copyRefinedType(rtp, parents1, decls1)
      case ExistentialType(tparams, result) =>
        val tparams1 = mapOver(tparams)
        var result1 = this(result)
        if ((tparams1 eq tparams) && (result1 eq result)) tp
        else ExistentialType(tparams1, result1.substSym(tparams, tparams1))
      case OverloadedType(pre, alts) =>
        val pre1 = if (pre.isInstanceOf[ClassInfoType]) pre else this(pre)
        if (pre1 eq pre) tp
        else OverloadedType(pre1, alts)
      case AntiPolyType(pre, args) =>
        val pre1 = this(pre)
        val args1 = args mapConserve (this)
        if ((pre1 eq pre) && (args1 eq args)) tp
        else AntiPolyType(pre1, args1)
      case tv@TypeVar(_, constr) =>
        if (constr.instValid) this(constr.inst)
        else tv.applyArgs(mapOverArgs(tv.typeArgs, tv.params))  //@M !args.isEmpty implies !typeParams.isEmpty 
      case NotNullType(tp) =>
        val tp1 = this(tp)
        if (tp1 eq tp) tp
        else NotNullType(tp1)
      case AnnotatedType(annots, atp, selfsym) =>
        val annots1 = mapOverAnnotations(annots)
        val atp1 = this(atp)
        if ((annots1 eq annots) && (atp1 eq atp)) tp
        else if (annots1.isEmpty) atp1
        else AnnotatedType(annots1, atp1, selfsym)
/*
      case ErrorType => tp
      case WildcardType => tp
      case NoType => tp
      case NoPrefix => tp
*/
      case _ =>
        tp
        // throw new Error("mapOver inapplicable for " + tp);
    }

    def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] = 
      map2Conserve(args, tparams) { (arg, tparam) =>
        val v = variance
        if (tparam.isContravariant) variance = -variance
        else if (!tparam.isCovariant) variance = 0
        val arg1 = this(arg)
        variance = v
        arg1
      }

    /** Map this function over given scope */
    def mapOver(scope: Scope): Scope = {
      val elems = scope.toList
      val elems1 = mapOver(elems)
      if (elems1 eq elems) scope
      else new Scope(elems1)
    }

    /** Map this function over given list of symbols */
    def mapOver(origSyms: List[Symbol]): List[Symbol] = { 
      val change = origSyms exists { sym =>
        val v = variance
        if (sym.isAliasType) variance = 0
        val result = this(sym.info)
        variance = v
        result ne sym.info
      }
      if (!change) origSyms // fast path in case nothing changes due to map
      else { // map is not the identity --> do cloning properly
        val clonedSyms = origSyms map (_.cloneSymbol)
        val clonedInfos = clonedSyms map (_.info.substSym(origSyms, clonedSyms))
        val transformedInfos = clonedInfos mapConserve (this)
        (clonedSyms, transformedInfos).zipped map (_ setInfo _)
        
        clonedSyms
      }
    }


    def mapOverAnnotations(annots: List[AnnotationInfo])
    : List[AnnotationInfo] = {
      val newAnnots = annots.flatMap(mapOver(_))
      if (allEq(newAnnots, annots))
        annots
      else
        newAnnots
    }

    def mapOver(annot: AnnotationInfo): Option[AnnotationInfo] = {
      val AnnotationInfo(atp, args, assocs) = annot

      if (dropNonConstraintAnnotations &&
          !(atp.typeSymbol isNonBottomSubClass TypeConstraintClass))
        return None

      val atp1 = mapOver(atp)
      val args1 = mapOverAnnotArgs(args)
      // there is no need to rewrite assocs, as they are constants

      if ((args eq args1) && (atp eq atp1))
        Some(annot)
      else if (sameLength(args1, args))
        Some(AnnotationInfo(atp1, args1, assocs).setPos(annot.pos))
      else
        None
    }

    /** Map over a set of annotation arguments.  If any
     *  of the arguments cannot be mapped, then return Nil.  */
    def mapOverAnnotArgs(args: List[Tree]): List[Tree] = {
      val args1 = args flatMap (x => mapOver(x))
      if (!sameLength(args1, args))
        Nil
      else if (allEq(args, args1))
        args
      else
        args1
    }

    def mapOver(tree: Tree): Option[Tree] =
      Some(mapOver(tree, ()=>return None))

    /** Map a tree that is part of an annotation argument.
     *  If the tree cannot be mapped, then invoke giveup().
     *  The default is to transform the tree with
     *  TypeMapTransformer.
     */
    def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = 
      (new TypeMapTransformer).transform(tree)

    /** This transformer leaves the tree alone except to remap
     *  its types. */
    class TypeMapTransformer extends Transformer {
      override def transform(tree: Tree) = {
        val tree1 = super.transform(tree)
        val tpe1 = TypeMap.this(tree1.tpe)
        if ((tree eq tree1) && (tree.tpe eq tpe1))
          tree
        else
          tree1.shallowDuplicate.setType(tpe1)
      }
    }
  }

  /** A type map that always returns the input type unchanged */
  object IdentityTypeMap extends TypeMap {
    def apply(tp: Type) = tp
  }

  abstract class TypeTraverser extends TypeMap {
    def traverse(tp: Type): Unit
    def apply(tp: Type): Type = { traverse(tp); tp }
  }

  abstract class TypeCollector[T](initial: T) extends TypeTraverser {
    var result: T = _
    def collect(tp: Type) = {
      result = initial
      traverse(tp)
      result
    }
  }

  private val emptySymMap   = immutable.Map[Symbol, Symbol]() 
  private val emptySymCount = immutable.Map[Symbol, Int]() 

  def typeParamsToExistentials(clazz: Symbol, tparams: List[Symbol]): List[Symbol] = {
    val eparams = for ((tparam, i) <- tparams.zipWithIndex) yield {
      clazz.newExistential(clazz.pos, newTypeName("?"+i)).setInfo(tparam.info.bounds)
    }
    for (tparam <- eparams) tparam setInfo tparam.info.substSym(tparams, eparams)
    eparams
  }
  
  //  note: it's important to write the two tests in this order,
  //  as only typeParams forces the classfile to be read. See #400
  private def isRawIfWithoutArgs(sym: Symbol) =
    sym.isClass && sym.typeParams.nonEmpty && sym.isJavaDefined

  def isRaw(sym: Symbol, args: List[Type]) = 
    !phase.erasedTypes && isRawIfWithoutArgs(sym) && args.isEmpty
  
  /** Is type tp a ``raw type''? */
  def isRawType(tp: Type) = tp match {
    case TypeRef(_, sym, args) => isRaw(sym, args)
    case _ => false
  }
      
  /** The raw to existential map converts a ``raw type'' to an existential type.
   *  It is necessary because we might have read a raw type of a 
   *  parameterized Java class from a class file. At the time we read the type
   *  the corresponding class file might still not be read, so we do not
   *  know what the type parameters of the type are. Therefore
   *  the conversion of raw types to existential types might not have taken place
   *  in ClassFileparser.sigToType (where it is usually done)
   */
  object rawToExistential extends TypeMap {
    private var expanded = immutable.Set[Symbol]()
    private var generated = immutable.Set[Type]()
    def apply(tp: Type): Type = tp match {
      case TypeRef(pre, sym, List()) if isRawIfWithoutArgs(sym) =>
        if (expanded contains sym) AnyRefClass.tpe
        else try {
          expanded += sym
          val eparams = mapOver(typeParamsToExistentials(sym, sym.typeParams))
          existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe))) 
        } finally {
          expanded -= sym
        }
      case ExistentialType(_, _) if !(generated contains tp) => // to avoid infinite expansions. todo: not sure whether this is needed
        val result = mapOver(tp)
        generated += result
        result
      case _ =>
        mapOver(tp)
    }
  }

  def singletonBounds(hi: Type) = {
    TypeBounds.upper(intersectionType(List(hi, SingletonClass.tpe)))
  }

  /** A map to compute the asSeenFrom method  */
  class AsSeenFromMap(pre: Type, clazz: Symbol) extends TypeMap {
    override val dropNonConstraintAnnotations = true

    var capturedParams: List[Symbol] = List() 

    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
      object annotationArgRewriter extends TypeMapTransformer {
        /** Rewrite `This` trees in annotation argument trees */
        def rewriteThis(tree: Tree): Tree =
          tree match {
            case This(_)
            if (tree.symbol isNonBottomSubClass clazz) &&
               (pre.widen.typeSymbol isNonBottomSubClass tree.symbol) =>
              if (pre.isStable) { // XXX why is this in this method? pull it out and guard the call `annotationArgRewriter.transform(tree)`?
                val termSym =
                  pre.typeSymbol.owner.newValue(
                    pre.typeSymbol.pos,
                    pre.typeSymbol.name.toTermName).setInfo(pre)  // what symbol should really be used?
                mkAttributedQualifier(pre, termSym)
              } else
                giveup()
            
            case tree => tree
          }

        override def transform(tree: Tree): Tree = {
          val tree1 = rewriteThis(super.transform(tree))
          tree1
        }
      }

      annotationArgRewriter.transform(tree)
    }

    var capturedPre = emptySymMap

    def stabilize(pre: Type, clazz: Symbol): Type =
      capturedPre.getOrElse(clazz, {
          val qvar = clazz freshExistential ".type" setInfo singletonBounds(pre)
          capturedPre += (clazz -> qvar)
          capturedParams = qvar :: capturedParams
          qvar
      }).tpe

    /** Return pre.baseType(clazz), or if that's NoType and clazz is a refinement, pre itself.
     *  See bug397.scala for an example where the second alternative is needed.
     *  The problem is that when forming the base type sequence of an abstract type,
     *  any refinements in the base type list might be regenerated, and thus acquire
     *  new class symbols. However, since refinements always have non-interesting prefixes
     *  it looks OK to me to just take the prefix directly. */
    def base(pre: Type, clazz: Symbol) = {
      val b = pre.baseType(clazz)
      if (b == NoType && clazz.isRefinementClass) pre
      else b
    }

    def apply(tp: Type): Type = 
      if ((pre eq NoType) || (pre eq NoPrefix) || !clazz.isClass) tp
      else tp match {
        case ThisType(sym) =>
          def toPrefix(pre: Type, clazz: Symbol): Type =
            if ((pre eq NoType) || (pre eq NoPrefix) || !clazz.isClass) tp
            else if ((sym isNonBottomSubClass clazz) && 
                     (pre.widen.typeSymbol isNonBottomSubClass sym)) {
              val pre1 = pre match {
                case SuperType(thistp, _) => thistp
                case _ => pre
              }
              if (!(pre1.isStable || 
                    pre1.typeSymbol.isPackageClass || 
                    pre1.typeSymbol.isModuleClass && pre1.typeSymbol.isStatic)) {
                stabilize(pre1, sym)
              } else {
                pre1
              }
            } else {
              toPrefix(base(pre, clazz).prefix, clazz.owner);
            }
          toPrefix(pre, clazz)
        case SingleType(pre, sym) =>
          if (sym.isPackageClass) tp // short path
          else {
            val pre1 = this(pre)
            if (pre1 eq pre) tp
            else if (pre1.isStable) singleType(pre1, sym) 
            else pre1.memberType(sym).resultType //todo: this should be rolled into existential abstraction
          }
        // AM: Martin, is this description accurate?
        // walk the owner chain of `clazz` (the original argument to asSeenFrom) until we find the type param's owner (while rewriting pre as we crawl up the owner chain)
        // once we're at the owner, extract the information that pre encodes about the type param,
        // by minimally subsuming pre to the type instance of the class that owns the type param,
        // the type we're looking for is the type instance's type argument at the position corresponding to the type parameter
        // optimisation: skip this type parameter if it's not owned by a class, as those params are not influenced by the prefix through which they are seen
        // (concretely: type params of anonymous type functions, which currently can only arise from normalising type aliases, are owned by the type alias of which they are the eta-expansion) 
        // (skolems also aren't affected: they are ruled out by the isTypeParameter check)
        case TypeRef(prefix, sym, args) if (sym.isTypeParameter && sym.owner.isClass) =>
          def toInstance(pre: Type, clazz: Symbol): Type =
            if ((pre eq NoType) || (pre eq NoPrefix) || !clazz.isClass) mapOver(tp) 
            //@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary
            else {
              def throwError = abort("" + tp + sym.locationString + " cannot be instantiated from " + pre.widen)
                                    
              def instParam(ps: List[Symbol], as: List[Type]): Type = 
                if (ps.isEmpty) throwError
                else if (sym eq ps.head)  
                  // @M! don't just replace the whole thing, might be followed by type application
                  appliedType(as.head, args mapConserve (this)) // @M: was as.head   
                else instParam(ps.tail, as.tail);
              val symclazz = sym.owner
              if (symclazz == clazz && !pre.isInstanceOf[TypeVar] && (pre.widen.typeSymbol isNonBottomSubClass symclazz)) {
                // have to deconst because it may be a Class[T].
                pre.baseType(symclazz).deconst match {
                  case TypeRef(_, basesym, baseargs) =>
                    //Console.println("instantiating " + sym + " from " + basesym + " with " + basesym.typeParams + " and " + baseargs+", pre = "+pre+", symclazz = "+symclazz);//DEBUG
                    if (sameLength(basesym.typeParams, baseargs)) {
                      instParam(basesym.typeParams, baseargs)
                    } else {
                      throw new TypeError(
                        "something is wrong (wrong class file?): "+basesym+ 
                        " with type parameters "+
                        basesym.typeParams.map(_.name).mkString("[",",","]")+
                        " gets applied to arguments "+baseargs.mkString("[",",","]")+", phase = "+phase)
                    }
                  case ExistentialType(tparams, qtpe) =>
                    capturedParams = capturedParams union tparams
                    toInstance(qtpe, clazz)
                  case _ =>
                    throwError
                }
              } else toInstance(base(pre, clazz).prefix, clazz.owner)
            }
          toInstance(pre, clazz)
        case _ =>
          mapOver(tp)
      }
  }

  /** A base class to compute all substitutions */
  abstract class SubstMap[T](from: List[Symbol], to: List[T]) extends TypeMap {
    val fromContains = (x: Symbol) => from.contains(x) //from.toSet <-- traversing short lists seems to be faster than allocating sets
    assert(sameLength(from, to), "Unsound substitution from "+ from +" to "+ to)

    /** Are `sym' and `sym1' the same.
     *  Can be tuned by subclasses.
     */
    protected def matches(sym: Symbol, sym1: Symbol): Boolean = sym eq sym1

    /** Map target to type, can be tuned by subclasses */
    protected def toType(fromtp: Type, tp: T): Type

    protected def renameBoundSyms(tp: Type): Type = tp match {
      case MethodType(ps, restp) =>
        val ps1 = cloneSymbols(ps)
        copyMethodType(tp, ps1, renameBoundSyms(restp.substSym(ps, ps1)))
      case PolyType(bs, restp) =>
        val bs1 = cloneSymbols(bs)
        PolyType(bs1, renameBoundSyms(restp.substSym(bs, bs1)))
      case ExistentialType(bs, restp) =>
        val bs1 = cloneSymbols(bs)
        ExistentialType(bs1, restp.substSym(bs, bs1))
      case _ =>
        tp
    }

    def apply(tp0: Type): Type = if (from.isEmpty) tp0 else {
      @tailrec def subst(tp: Type, sym: Symbol, from: List[Symbol], to: List[T]): Type =
        if (from.isEmpty) tp
        // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(tp, from))
        else if (matches(from.head, sym)) toType(tp, to.head)
        else subst(tp, sym, from.tail, to.tail)

      val boundSyms = tp0.boundSyms
      val tp1 = if (boundSyms exists fromContains) renameBoundSyms(tp0) else tp0
      val tp = mapOver(tp1)
      
      tp match {
        // @M 
        // 1) arguments must also be substituted (even when the "head" of the 
        // applied type has already been substituted)
        // example: (subst RBound[RT] from [type RT,type RBound] to 
        // [type RT&,type RBound&]) = RBound&[RT&]
        // 2) avoid loops (which occur because alpha-conversion is 
        // not performed properly imo)
        // e.g. if in class Iterable[a] there is a new Iterable[(a,b)], 
        // we must replace the a in Iterable[a] by (a,b)
        // (must not recurse --> loops)
        // 3) replacing m by List in m[Int] should yield List[Int], not just List
        case TypeRef(NoPrefix, sym, args) =>
          appliedType(subst(tp, sym, from, to), args) // if args.isEmpty, appliedType is the identity
        case SingleType(NoPrefix, sym) =>
          subst(tp, sym, from, to)
        case _ =>
          tp
      }
    }
  }

  /** A map to implement the `substSym' method. */
  class SubstSymMap(from: List[Symbol], to: List[Symbol]) extends SubstMap(from, to) {
    protected def toType(fromtp: Type, sym: Symbol) = fromtp match {
      case TypeRef(pre, _, args) => copyTypeRef(fromtp, pre, sym, args)
      case SingleType(pre, _) => singleType(pre, sym)
    }
    override def apply(tp: Type): Type = if (from.isEmpty) tp else {
      @tailrec def subst(sym: Symbol, from: List[Symbol], to: List[Symbol]): Symbol =
        if (from.isEmpty) sym
        // else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(sym, from))
        else if (matches(from.head, sym)) to.head
        else subst(sym, from.tail, to.tail)
      tp match {
        case TypeRef(pre, sym, args) if pre ne NoPrefix =>
          val newSym = subst(sym, from, to)
          // assert(newSym.typeParams.length == sym.typeParams.length, "typars mismatch in SubstSymMap: "+(sym, sym.typeParams, newSym, newSym.typeParams))
          mapOver(copyTypeRef(tp, pre, newSym, args)) // mapOver takes care of subst'ing in args
        case SingleType(pre, sym) if pre ne NoPrefix =>
          mapOver(singleType(pre, subst(sym, from, to)))
        case _ =>
          super.apply(tp)
      }
    }


    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
      object trans extends TypeMapTransformer {

        def termMapsTo(sym: Symbol) =
          if (fromContains(sym))
            Some(to(from.indexOf(sym)))
          else
            None

        override def transform(tree: Tree) = 
          tree match {
            case tree@Ident(_) =>
              termMapsTo(tree.symbol) match {
                case Some(tosym) =>
                  if (tosym.info.bounds.hi.typeSymbol isSubClass SingletonClass) {
                    Ident(tosym.existentialToString)
                      .setSymbol(tosym)
                      .setPos(tosym.pos)
                      .setType(dropSingletonType(tosym.info.bounds.hi))
                  } else {
                    giveup()
                  }
                case none => super.transform(tree)
              }
            case tree => super.transform(tree)
          }
      }
      trans.transform(tree)
    }
  }

  /** A map to implement the `subst' method. */
  class SubstTypeMap(from: List[Symbol], to: List[Type])
  extends SubstMap(from, to) {
    protected def toType(fromtp: Type, tp: Type) = tp 

    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
      object trans extends TypeMapTransformer {
        override def transform(tree: Tree) = 
          tree match {
            case Ident(name) if fromContains(tree.symbol) =>
              val totpe = to(from.indexOf(tree.symbol))
              if (!totpe.isStable) giveup()
              else Ident(name).setPos(tree.pos).setSymbol(tree.symbol).setType(totpe)

            case _ => super.transform(tree)
          }
      }
      trans.transform(tree)
    }

  }

  /** A map to implement the `substThis' method. */
  class SubstThisMap(from: Symbol, to: Type) extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case ThisType(sym) if (sym == from) => to
      case _ => mapOver(tp)
    }
  }

  class SubstSuperMap(from: Type, to: Type) extends TypeMap {
    def apply(tp: Type): Type = if (tp eq from) to else mapOver(tp)
  }

  class SubstWildcardMap(from: List[Symbol]) extends TypeMap { 
    def apply(tp: Type): Type = try {
      tp match {
        case TypeRef(_, sym, _) if from contains sym =>
          BoundedWildcardType(sym.info.bounds)
        case _ => 
          mapOver(tp)
      }
    } catch {
      case ex: MalformedType =>
        WildcardType
    }
  }

// dependent method types
  object IsDependentCollector extends TypeCollector(false) {
    def traverse(tp: Type) {
      if(tp isImmediatelyDependent) result = true
      else if (!result) mapOver(tp)
    }
  }

  object ApproximateDependentMap extends TypeMap {
    def apply(tp: Type): Type = 
      if(tp isImmediatelyDependent) WildcardType
      else mapOver(tp)
  }

  class InstantiateDependentMap(params: List[Symbol], actuals: List[Type]) extends TypeMap {
    private val actualsIndexed = actuals.toIndexedSeq
    override val dropNonConstraintAnnotations = true

    object ParamWithActual {
      def unapply(sym: Symbol): Option[Type] = {
        val pid = params indexOf sym
        if(pid != -1) Some(actualsIndexed(pid)) else None
      }
    }

    def apply(tp: Type): Type =
      mapOver(tp) match {
        case SingleType(NoPrefix, ParamWithActual(arg)) if arg.isStable => arg // unsound to replace args by unstable actual #3873
        // (soundly) expand type alias selections on implicit arguments, see depmet_implicit_oopsla* test cases -- typically, `param.isImplicit`
        case tp1@TypeRef(SingleType(NoPrefix, ParamWithActual(arg)), sym, targs) =>
          val res = typeRef(arg, sym, targs)
          if(res.typeSymbolDirect isAliasType) res.dealias
          else tp1
        case tp1 => tp1 // don't return the original `tp`, which may be different from `tp1`, due to `dropNonConstraintAnnotations`
      }

    def existentialsNeeded: List[Symbol] = existSyms.filter(_ ne null).toList

    private val existSyms: Array[Symbol] = new Array(actualsIndexed.size)
    private def haveExistential(i: Int) = {assert((i >= 0) && (i <= actualsIndexed.size)); existSyms(i) ne null}

    /* Return the type symbol for referencing a parameter inside the existential quantifier. 
     * (Only needed if the actual is unstable.)
     */
    def existSymFor(actualIdx: Int) =
      if (haveExistential(actualIdx)) existSyms(actualIdx)
      else {
        val oldSym = params(actualIdx)
        val symowner = oldSym.owner
        val bound = singletonBounds(actualsIndexed(actualIdx))

        val sym = symowner.newExistential(oldSym.pos, newTypeName(oldSym.name + ".type"))
        sym.setInfo(bound)
        sym.setFlag(oldSym.flags)

        existSyms(actualIdx) = sym
        sym
      }

    //AM propagate more info to annotations -- this seems a bit ad-hoc... (based on code by spoon)
    override def mapOver(arg: Tree, giveup: ()=>Nothing): Tree = {
      object treeTrans extends Transformer {
        override def transform(tree: Tree): Tree = {
          tree match {
            case RefParamAt(pid) =>
              // TODO: this should be simplified; in the stable case, one can probably
              // just use an Ident to the tree.symbol. Why an existential in the non-stable case?
              val actual = actualsIndexed(pid)
              if (actual.isStable && actual.typeSymbol != NothingClass) {
                mkAttributedQualifier(actualsIndexed(pid), tree.symbol)
              } else {
                val sym = existSymFor(pid)
                (Ident(sym.name)
                 copyAttrs tree
                 setType typeRef(NoPrefix, sym, Nil))
              }
            case _ => super.transform(tree)
          }
        }
        object RefParamAt {
          def unapply(tree: Tree): Option[Int] = tree match {
            case Ident(_) => Some(params indexOf tree.symbol) filterNot (_ == -1)
            case _        => None
          }
        }
      }

      treeTrans.transform(arg)
    }
  }


  object StripAnnotationsMap extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case AnnotatedType(_, atp, _) =>
        mapOver(atp)
      case tp =>
        mapOver(tp)
    }
  }

  /** A map to convert every occurrence of a wildcard type to a fresh
   *  type variable */
  object wildcardToTypeVarMap extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case WildcardType =>
        TypeVar(tp, new TypeConstraint)
      case BoundedWildcardType(bounds) =>
        TypeVar(tp, new TypeConstraint(List(bounds.lo), List(bounds.hi)))
      case _ =>
        mapOver(tp)
    }
  }

  /** A map to convert every occurrence of a type variable to a
      wildcard type */
  object typeVarToOriginMap extends TypeMap {
    def apply(tp: Type): Type = tp match {
      case TypeVar(origin, _) => origin
      case _ => mapOver(tp)
    }
  }

  /** A map to implement the `contains' method */
  class ContainsCollector(sym: Symbol) extends TypeCollector(false) {
    def traverse(tp: Type) {
      if (!result) {
        tp.normalize match {
          case TypeRef(_, sym1, _) if (sym == sym1) => result = true
          case SingleType(_, sym1) if (sym == sym1) => result = true
          case _ => mapOver(tp)
        }
      }
    }

    override def mapOver(arg: Tree) = {
      for (t <- arg) {
        traverse(t.tpe)
        if (t.symbol == sym)
          result = true
      }
      Some(arg)
    }
  }
  
  /** A map to implement the `contains' method */
  class ContainsTypeCollector(t: Type) extends TypeCollector(false) {
    def traverse(tp: Type) {
      if (!result) {
        if (tp eq t) result = true
        else mapOver(tp)
      }
    }
    override def mapOver(arg: Tree) = {
      for (t <- arg) {
        traverse(t.tpe)
      }
      Some(arg)
    }
  }

  /** A map to implement the `filter' method */
  class FilterTypeCollector(p: Type => Boolean) extends TypeCollector(new ListBuffer[Type]) {
    def traverse(tp: Type) {
      if (p(tp)) result += tp
      mapOver(tp)
    }
  }

  class ForEachTypeTraverser(f: Type => Unit) extends TypeTraverser {
    def traverse(tp: Type) {
      f(tp)
      mapOver(tp)
    }
  }

  /** A map to implement the `filter' method */
  class FindTypeCollector(p: Type => Boolean) extends TypeCollector[Option[Type]](None) {
    def traverse(tp: Type) {
      if (result.isEmpty) {
        if (p(tp)) result = Some(tp)
        mapOver(tp)
      }
    }
  }

  /** A map to implement the `contains' method */
  object ErroneousCollector extends TypeCollector(false) {
    def traverse(tp: Type) {
      if (!result) {
        result = tp.isError
        mapOver(tp)
      }
    }
  }

  /** A map to compute the most deeply nested owner that contains all the symbols
   *  of thistype or prefixless typerefs/singletype occurrences in given type.
   */
  object commonOwnerMap extends TypeMap {
    var result: Symbol = _
    def init() = { result = NoSymbol }
    def apply(tp: Type): Type = {
      assert(tp ne null)
      tp.normalize match {
        case ThisType(sym) =>
          register(sym)
        case TypeRef(NoPrefix, sym, args) =>
          register(sym.owner); args foreach apply
        case SingleType(NoPrefix, sym) =>
          register(sym.owner)
        case _ =>
          mapOver(tp)
      }
      tp
    }
    private def register(sym: Symbol) {
      while (result != NoSymbol && sym != result && !(sym isNestedIn result))
        result = result.owner;
    }
  }

  class MissingAliasControl extends ControlThrowable
  val missingAliasException = new MissingAliasControl
  class MissingTypeControl extends ControlThrowable

  object adaptToNewRunMap extends TypeMap {
    private def adaptToNewRun(pre: Type, sym: Symbol): Symbol = {
      if (phase.flatClasses) {
        sym
      } else if (sym.isModuleClass) {
        adaptToNewRun(pre, sym.sourceModule).moduleClass
      } else if ((pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass) {
        sym
      } else {
        var rebind0 = pre.findMember(sym.name, BRIDGE, 0, true)
        if (rebind0 == NoSymbol) {
          if (sym.isAliasType) throw missingAliasException
          if (settings.debug.value) println(pre+"."+sym+" does no longer exist, phase = "+phase)
          throw new MissingTypeControl // For build manager and presentation compiler purposes
          //assert(false, pre+"."+sym+" does no longer exist, phase = "+phase)
        }
        /** The two symbols have the same fully qualified name */
        def corresponds(sym1: Symbol, sym2: Symbol): Boolean =
          sym1.name == sym2.name && (sym1.isPackageClass || corresponds(sym1.owner, sym2.owner))
        if (!corresponds(sym.owner, rebind0.owner)) {
          if (settings.debug.value)
            log("ADAPT1 pre = "+pre+", sym = "+sym+sym.locationString+", rebind = "+rebind0+rebind0.locationString)
          val bcs = pre.baseClasses.dropWhile(bc => !corresponds(bc, sym.owner));
          if (bcs.isEmpty)
            assert(pre.typeSymbol.isRefinementClass, pre) // if pre is a refinementclass it might be a structural type => OK to leave it in.
          else 
            rebind0 = pre.baseType(bcs.head).member(sym.name)
          if (settings.debug.value) log(
            "ADAPT2 pre = " + pre +
            ", bcs.head = " + bcs.head +
            ", sym = " + sym+sym.locationString +
            ", rebind = " + rebind0 + (
              if (rebind0 == NoSymbol) ""
              else rebind0.locationString
            )
          )
        }
        val rebind = rebind0.suchThat(sym => sym.isType || sym.isStable)
        if (rebind == NoSymbol) {
          if (settings.debug.value) log("" + phase + " " +phase.flatClasses+sym.owner+sym.name+" "+sym.isType)
          throw new MalformedType(pre, sym.nameString)
        }
        rebind
      }
    }
    def apply(tp: Type): Type = tp match {
      case ThisType(sym) =>
        try {
          val sym1 = adaptToNewRun(sym.owner.thisType, sym)
          if (sym1 == sym) tp else ThisType(sym1)
        } catch {
        	case ex: MissingTypeControl =>
            tp 
        }
      case SingleType(pre, sym) =>
        if (sym.isPackage) tp
        else {
          val pre1 = this(pre)
          val sym1 = adaptToNewRun(pre1, sym)
          if ((pre1 eq pre) && (sym1 eq sym)) tp
          else singleType(pre1, sym1)
        }
      case TypeRef(pre, sym, args) =>
        if (sym.isPackageClass) tp
        else {
          val pre1 = this(pre)
          val args1 = args mapConserve (this)
          try {
            val sym1 = adaptToNewRun(pre1, sym)
            if ((pre1 eq pre) && (sym1 eq sym) && (args1 eq args)/* && sym.isExternal*/) {
              tp
            } else if (sym1 == NoSymbol) {
              if (settings.debug.value) println("adapt fail: "+pre+" "+pre1+" "+sym)
              tp
            } else {
              copyTypeRef(tp, pre1, sym1, args1)
            }
          } catch {
            case ex: MissingAliasControl =>
              apply(tp.dealias)
            case _: MissingTypeControl =>
              tp
          }
        }
      case MethodType(params, restp) =>
        val restp1 = this(restp)
        if (restp1 eq restp) tp
        else copyMethodType(tp, params, restp1)
      case NullaryMethodType(restp) =>
        val restp1 = this(restp)
        if (restp1 eq restp) tp
        else NullaryMethodType(restp1)
      case PolyType(tparams, restp) =>
        val restp1 = this(restp)
        if (restp1 eq restp) tp
        else PolyType(tparams, restp1)

      // Lukas: we need to check (together) whether we should also include parameter types
      // of PolyType and MethodType in adaptToNewRun
      
      case ClassInfoType(parents, decls, clazz) =>
        if (clazz.isPackageClass) tp
        else {
          val parents1 = parents mapConserve (this)
          if (parents1 eq parents) tp
          else ClassInfoType(parents1, decls, clazz)
        }
      case RefinedType(parents, decls) =>
        val parents1 = parents mapConserve (this)
        if (parents1 eq parents) tp
        else refinedType(parents1, tp.typeSymbol.owner, decls, tp.typeSymbol.owner.pos)
      case SuperType(_, _) => mapOver(tp)
      case TypeBounds(_, _) => mapOver(tp)
      case TypeVar(_, _) => mapOver(tp)
      case AnnotatedType(_,_,_) => mapOver(tp)
      case NotNullType(_) => mapOver(tp)
      case ExistentialType(_, _) => mapOver(tp)
      case _ => tp
    }
  }

  class SubTypePair(val tp1: Type, val tp2: Type) {
    override def hashCode = tp1.hashCode * 41 + tp2.hashCode
    override def equals(other: Any) = other match {
      case stp: SubTypePair => 
        (tp1 =:= stp.tp1) && (tp2 =:= stp.tp2)
      case _ =>
        false
    }
    override def toString = tp1+" <:<? "+tp2
  }

// Helper Methods  -------------------------------------------------------------

  final val LubGlbMargin = 0

  /** The maximum allowable depth of lubs or glbs over types `ts'
    * This is the maximum depth of all types in the base type sequences 
    * of each of the types `ts', plus LubGlbMargin
    */
  def lubDepth(ts: List[Type]) = {
    var d = 0
    for (tp <- ts) d = math.max(d, tp.baseTypeSeqDepth)
    d + LubGlbMargin
  }

  /** Is intersection of given types populated? That is,
   *  for all types tp1, tp2 in intersection
   *    for all common base classes bc of tp1 and tp2
   *      let bt1, bt2 be the base types of tp1, tp2 relative to class bc
   *      Then:
   *        bt1 and bt2 have the same prefix, and
   *        any corresponding non-variant type arguments of bt1 and bt2 are the same
   */
  def isPopulated(tp1: Type, tp2: Type): Boolean = {
    def isConsistent(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match {
      case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) =>
        assert(sym1 == sym2)
        pre1 =:= pre2 &&
        ((args1, args2, sym1.typeParams).zipped forall {
          (arg1, arg2, tparam) => 
            //if (tparam.variance == 0 && !(arg1 =:= arg2)) Console.println("inconsistent: "+arg1+"!="+arg2)//DEBUG
          if (tparam.variance == 0) arg1 =:= arg2
          else if (arg1.isInstanceOf[TypeVar]) 
            // if left-hand argument is a typevar, make it compatible with variance
            // this is for more precise pattern matching
            // todo: work this in the spec of this method
            // also: think what happens if there are embedded typevars?
            if (tparam.variance < 0) arg1 <:< arg2 else arg2 <:< arg1
          else true
        })
      case (et: ExistentialType, _) =>
        et.withTypeVars(isConsistent(_, tp2))
      case (_, et: ExistentialType) =>
        et.withTypeVars(isConsistent(tp1, _))
    }    

    def check(tp1: Type, tp2: Type) = 
      if (tp1.typeSymbol.isClass && tp1.typeSymbol.hasFlag(FINAL)) 
        tp1 <:< tp2 || isNumericValueClass(tp1.typeSymbol) && isNumericValueClass(tp2.typeSymbol)
      else tp1.baseClasses forall (bc => 
        tp2.baseTypeIndex(bc) < 0 || isConsistent(tp1.baseType(bc), tp2.baseType(bc)))

    check(tp1, tp2)/* && check(tp2, tp1)*/ // need to investgate why this can't be made symmetric -- neg/gadts1 fails, and run/existials also.
  }

  /** Does a pattern of type `patType' need an outer test when executed against
   *  selector type `selType' in context defined by `currentOwner'?
   */
  def needsOuterTest(patType: Type, selType: Type, currentOwner: Symbol) = {
    def createDummyClone(pre: Type): Type = {
      val dummy = currentOwner.enclClass.newValue(NoPosition, nme.ANYNAME).setInfo(pre.widen)
      singleType(ThisType(currentOwner.enclClass), dummy)
    }
    def maybeCreateDummyClone(pre: Type, sym: Symbol): Type = pre match {
      case SingleType(pre1, sym1) =>
        if (sym1.isModule && sym1.isStatic) {
          NoType
        } else if (sym1.isModule && sym.owner == sym1.moduleClass) {
          val pre2 = maybeCreateDummyClone(pre1, sym1)
          if (pre2 eq NoType) pre2
          else singleType(pre2, sym1)
        } else {
          createDummyClone(pre)
        }
      case ThisType(clazz) =>
        if (clazz.isModuleClass)
          maybeCreateDummyClone(clazz.typeOfThis, sym)
        else if (sym.owner == clazz && (sym.hasFlag(PRIVATE) || sym.privateWithin == clazz))
          NoType
        else 
          createDummyClone(pre)
      case _ =>
        NoType
    }
    patType match {
      case TypeRef(pre, sym, args) => 
        val pre1 = maybeCreateDummyClone(pre, sym)
        (pre1 ne NoType) && isPopulated(copyTypeRef(patType, pre1, sym, args), selType)
      case _ =>
        false
    }
  }

  private var subsametypeRecursions: Int = 0

  private def isUnifiable(pre1: Type, pre2: Type) =
    (beginsWithTypeVarOrIsRefined(pre1) || beginsWithTypeVarOrIsRefined(pre2)) && (pre1 =:= pre2)

  /** Returns true iff we are past phase specialize,
   *  sym1 and sym2 are two existential skolems with equal names and bounds,
   *  and pre1 and pre2 are equal prefixes
   */
  private def isSameSpecializedSkolem(sym1: Symbol, sym2: Symbol, pre1: Type, pre2: Type) = {
    sym1.isExistentialSkolem && sym2.isExistentialSkolem && 
    sym1.name == sym2.name && 
    phase.specialized &&
    sym1.info =:= sym2.info &&
    pre1 =:= pre2
  }

  private def equalSymsAndPrefixes(sym1: Symbol, pre1: Type, sym2: Symbol, pre2: Type): Boolean =
    if (sym1 == sym2) sym1.hasPackageFlag || phase.erasedTypes || pre1 =:= pre2
    else (sym1.name == sym2.name) && isUnifiable(pre1, pre2)

  /** Do `tp1' and `tp2' denote equivalent types?
   */
  def isSameType(tp1: Type, tp2: Type): Boolean = try {
    incCounter(sametypeCount)
    subsametypeRecursions += 1
    undoLog undoUnless {
      isSameType1(tp1, tp2) 
    }
  } finally {
    subsametypeRecursions -= 1
    // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866)
    // it doesn't help to keep separate recursion counts for the three methods that now share it
    // if (subsametypeRecursions == 0) undoLog.clear()
  }

  def isDifferentType(tp1: Type, tp2: Type): Boolean = try {
    subsametypeRecursions += 1
    undoLog undo { // undo type constraints that arise from operations in this block
      !isSameType1(tp1, tp2)
    }
  } finally {
    subsametypeRecursions -= 1
    // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866)
    // it doesn't help to keep separate recursion counts for the three methods that now share it
    // if (subsametypeRecursions == 0) undoLog.clear()
  }

  def isDifferentTypeConstructor(tp1: Type, tp2: Type): Boolean = tp1 match {
    case TypeRef(pre1, sym1, _) => 
      tp2 match {
        case TypeRef(pre2, sym2, _) => sym1 != sym2 || isDifferentType(pre1, pre2)
        case _ => true
      }
    case _ => true
  }

  def normalizePlus(tp: Type) = 
    if (isRawType(tp)) rawToExistential(tp)
    else tp.normalize

  /*
  todo: change to:
  def normalizePlus(tp: Type) = tp match {
    case TypeRef(pre, sym, List()) =>
      if (!sym.isInitialized) sym.rawInfo.load(sym)
      if (sym.isJavaDefined && !sym.typeParams.isEmpty) rawToExistential(tp)
      else tp.normalize
    case _ => tp.normalize
  }
  */
/*
  private def isSameType0(tp1: Type, tp2: Type): Boolean = {
    if (tp1 eq tp2) return true
    ((tp1, tp2) match {
      case (ErrorType, _) => true
      case (WildcardType, _) => true
      case (_, ErrorType) => true
      case (_, WildcardType) => true

      case (NoType, _) => false
      case (NoPrefix, _) => tp2.typeSymbol.isPackageClass
      case (_, NoType) => false
      case (_, NoPrefix) => tp1.typeSymbol.isPackageClass

      case (ThisType(sym1), ThisType(sym2))
      if (sym1 == sym2) =>
        true
      case (SingleType(pre1, sym1), SingleType(pre2, sym2))
      if (equalSymsAndPrefixes(sym1, pre1, sym2, pre2)) =>
        true
/*
      case (SingleType(pre1, sym1), ThisType(sym2))
      if (sym1.isModule && 
          sym1.moduleClass == sym2 &&
          pre1 =:= sym2.owner.thisType) =>
        true
      case (ThisType(sym1), SingleType(pre2, sym2))
      if (sym2.isModule && 
          sym2.moduleClass == sym1 &&
          pre2 =:= sym1.owner.thisType) =>
        true
*/
      case (ConstantType(value1), ConstantType(value2)) =>
        value1 == value2
      case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) =>
        equalSymsAndPrefixes(sym1, pre1, sym2, pre2) &&
        ((tp1.isHigherKinded && tp2.isHigherKinded && tp1.normalize =:= tp2.normalize) || 
         isSameTypes(args1, args2))
         // @M! normalize reduces higher-kinded case to PolyType's
      case (RefinedType(parents1, ref1), RefinedType(parents2, ref2)) =>
        def isSubScope(s1: Scope, s2: Scope): Boolean = s2.toList.forall {
          sym2 =>
            var e1 = s1.lookupEntry(sym2.name)
            (e1 ne null) && {
              val substSym = sym2.info.substThis(sym2.owner, e1.sym.owner.thisType)
              var isEqual = false
              while (!isEqual && (e1 ne null)) { 
                isEqual = e1.sym.info =:= substSym
                e1 = s1.lookupNextEntry(e1)
              }
              isEqual
            }
        }
        //Console.println("is same? " + tp1 + " " + tp2 + " " + tp1.typeSymbol.owner + " " + tp2.typeSymbol.owner)//DEBUG
        isSameTypes(parents1, parents2) && isSubScope(ref1, ref2) && isSubScope(ref2, ref1)
      case (MethodType(params1, res1), MethodType(params2, res2)) =>
        // new dependent types: probably fix this, use substSym as done for PolyType
        (isSameTypes(tp1.paramTypes, tp2.paramTypes) &&
         res1 =:= res2 &&
         tp1.isImplicit == tp2.isImplicit)
      case (PolyType(tparams1, res1), PolyType(tparams2, res2)) => 
        // assert((tparams1 map (_.typeParams.length)) == (tparams2 map (_.typeParams.length)))
        (tparams1.length == tparams2.length) && (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && // @M looks like it might suffer from same problem as #2210 
          res1 =:= res2.substSym(tparams2, tparams1)
      case (ExistentialType(tparams1, res1), ExistentialType(tparams2, res2)) =>
        (tparams1.length == tparams2.length) && (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && // @M looks like it might suffer from same problem as #2210
          res1 =:= res2.substSym(tparams2, tparams1)
      case (TypeBounds(lo1, hi1), TypeBounds(lo2, hi2)) =>
        lo1 =:= lo2 && hi1 =:= hi2
      case (BoundedWildcardType(bounds), _) =>
        bounds containsType tp2
      case (_, BoundedWildcardType(bounds)) =>
        bounds containsType tp1
      case (tv @ TypeVar(_,_), tp) =>
        tv.registerTypeEquality(tp, true)
      case (tp, tv @ TypeVar(_,_)) =>
        tv.registerTypeEquality(tp, false)
      case (AnnotatedType(_,_,_), _) =>
        annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
      case (_, AnnotatedType(_,_,_)) =>
        annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
      case (_: SingletonType, _: SingletonType) =>
        var origin1 = tp1
        while (origin1.underlying.isInstanceOf[SingletonType]) {
          assert(origin1 ne origin1.underlying, origin1)
          origin1 = origin1.underlying
        }
        var origin2 = tp2
        while (origin2.underlying.isInstanceOf[SingletonType]) {
          assert(origin2 ne origin2.underlying, origin2)
          origin2 = origin2.underlying
        }
        ((origin1 ne tp1) || (origin2 ne tp2)) && (origin1 =:= origin2)
      case _ =>
        false
    }) || {
      val tp1n = normalizePlus(tp1)
      val tp2n = normalizePlus(tp2)
      ((tp1n ne tp1) || (tp2n ne tp2)) && isSameType(tp1n, tp2n)
    }
  }
*/
  private def isSameType1(tp1: Type, tp2: Type): Boolean = {
    if ((tp1 eq tp2) || 
        (tp1 eq ErrorType) || (tp1 eq WildcardType) ||
        (tp2 eq ErrorType) || (tp2 eq WildcardType))
      true
    else if ((tp1 eq NoType) || (tp2 eq NoType))
      false
    else if (tp1 eq NoPrefix) 
      tp2.typeSymbol.isPackageClass
    else if (tp2 eq NoPrefix)
      tp1.typeSymbol.isPackageClass
    else {
      isSameType2(tp1, tp2) || {
        val tp1n = normalizePlus(tp1)
        val tp2n = normalizePlus(tp2)
        ((tp1n ne tp1) || (tp2n ne tp2)) && isSameType(tp1n, tp2n)
      }
    }
  }
  
  def isSameType2(tp1: Type, tp2: Type): Boolean = {
    tp1 match {
      case tr1: TypeRef =>
        tp2 match {
          case tr2: TypeRef =>
            return (equalSymsAndPrefixes(tr1.sym, tr1.pre, tr2.sym, tr2.pre) &&
              ((tp1.isHigherKinded && tp2.isHigherKinded && tp1.normalize =:= tp2.normalize) || 
               isSameTypes(tr1.args, tr2.args))) ||
               ((tr1.pre, tr2.pre) match {
                 case (tv @ TypeVar(_,_), _) => tv.registerTypeSelection(tr1.sym, tr2)
                 case (_, tv @ TypeVar(_,_)) => tv.registerTypeSelection(tr2.sym, tr1)
                 case _ => false
               })
          case _ =>
        }
      case tt1: ThisType =>
        tp2 match {
          case tt2: ThisType =>
            if (tt1.sym == tt2.sym) return true
          case _ =>
        }
      case st1: SingleType =>
        tp2 match {
          case st2: SingleType =>
            if (equalSymsAndPrefixes(st1.sym, st1.pre, st2.sym, st2.pre)) return true
          case _ =>
        }
      case ct1: ConstantType =>
        tp2 match {
          case ct2: ConstantType =>
            return (ct1.value == ct2.value)
          case _ =>
        }
      case rt1: RefinedType =>
        tp2 match {
          case rt2: RefinedType => // 
            def isSubScope(s1: Scope, s2: Scope): Boolean = s2.toList.forall {
              sym2 =>
                var e1 = s1.lookupEntry(sym2.name)
                (e1 ne null) && {
                  val substSym = sym2.info.substThis(sym2.owner, e1.sym.owner.thisType)
                  var isEqual = false
                  while (!isEqual && (e1 ne null)) { 
                    isEqual = e1.sym.info =:= substSym
                    e1 = s1.lookupNextEntry(e1)
                  }
                  isEqual
                }
            }
            //Console.println("is same? " + tp1 + " " + tp2 + " " + tp1.typeSymbol.owner + " " + tp2.typeSymbol.owner)//DEBUG
            return isSameTypes(rt1.parents, rt2.parents) && {
              val decls1 = rt1.decls
              val decls2 = rt2.decls
              isSubScope(decls1, decls2) && isSubScope(decls2, decls1)
            }
          case _ =>
        }
      case mt1: MethodType =>
        tp2 match {
          case mt2: MethodType =>
            // DEPMETTODO new dependent types: probably fix this, use substSym as done for PolyType
            return isSameTypes(mt1.paramTypes, mt2.paramTypes) &&
              mt1.resultType =:= mt2.resultType &&
              mt1.isImplicit == mt2.isImplicit
          // note: no case NullaryMethodType(restpe) => return mt1.params.isEmpty && mt1.resultType =:= restpe
          case _ =>
        }
      case NullaryMethodType(restpe1) =>
        tp2 match {
          // note: no case mt2: MethodType => return mt2.params.isEmpty && restpe  =:= mt2.resultType
          case NullaryMethodType(restpe2) =>
            return restpe1 =:= restpe2
          case _ =>
        }
      case PolyType(tparams1, res1) =>
        tp2 match {
          case PolyType(tparams2, res2) =>
//            assert((tparams1 map (_.typeParams.length)) == (tparams2 map (_.typeParams.length)))
              // @M looks like it might suffer from same problem as #2210
              return (
                (sameLength(tparams1, tparams2)) && // corresponds does not check length of two sequences before checking the predicate
                (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && 
                res1 =:= res2.substSym(tparams2, tparams1)
              )
          case _ =>
        }
      case ExistentialType(tparams1, res1) =>
        tp2 match {
          case ExistentialType(tparams2, res2) =>
            // @M looks like it might suffer from same problem as #2210
            return (
              // corresponds does not check length of two sequences before checking the predicate -- faster & needed to avoid crasher in #2956
              sameLength(tparams1, tparams2) &&
              (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) &&
              res1 =:= res2.substSym(tparams2, tparams1)
            )
          case _ =>
        }
      case TypeBounds(lo1, hi1) =>
        tp2 match {
          case TypeBounds(lo2, hi2) =>
            return lo1 =:= lo2 && hi1 =:= hi2
          case _ =>
        }
      case BoundedWildcardType(bounds) =>
        return bounds containsType tp2
      case _ =>
    }
    tp2 match {
      case BoundedWildcardType(bounds) =>
        return bounds containsType tp1
      case _ =>
    }
    tp1 match {
      case tv @ TypeVar(_,_) =>
        return tv.registerTypeEquality(tp2, true)
      case _ =>
    }
    tp2 match {
      case tv @ TypeVar(_,_) =>
        return tv.registerTypeEquality(tp1, false)
      case _ =>
    }
    tp1 match {
      case _: AnnotatedType =>
        return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
      case _ =>
    }
    tp2 match {
      case _: AnnotatedType =>
        return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
      case _ =>
    }
    tp1 match {
      case _: SingletonType =>
        tp2 match {
          case _: SingletonType =>
            @inline def chaseDealiasedUnderlying(tp: Type): Type = {
              var origin = tp
              var next = origin.underlying.dealias
              while (next.isInstanceOf[SingletonType]) {
                assert(origin ne next, origin)
                origin = next
                next = origin.underlying.dealias
              }
              origin
            }
            val origin1 = chaseDealiasedUnderlying(tp1)
            val origin2 = chaseDealiasedUnderlying(tp2)
            ((origin1 ne tp1) || (origin2 ne tp2)) && (origin1 =:= origin2)
          case _ =>
            false
        }
      case _ =>
        false
    }
  }

  /** Are `tps1' and `tps2' lists of pairwise equivalent
   *  types?
   */
  def isSameTypes(tps1: List[Type], tps2: List[Type]): Boolean = (tps1 corresponds tps2)(_ =:= _)

  /** True if two lists have the same length.  Since calling length on linear sequences
   *  is O(n), it is an inadvisable way to test length equality.
   */
  final def sameLength(xs1: List[_], xs2: List[_]) = compareLengths(xs1, xs2) == 0
  @tailrec final def compareLengths(xs1: List[_], xs2: List[_]): Int =
    if (xs1.isEmpty) { if (xs2.isEmpty) 0 else -1 }
    else if (xs2.isEmpty) 1
    else compareLengths(xs1.tail, xs2.tail)
  
  /** Again avoiding calling length, but the lengthCompare interface is clunky.
   */
  final def hasLength(xs: List[_], len: Int) = xs.lengthCompare(len) == 0
  
  private val pendingSubTypes = new mutable.HashSet[SubTypePair]
  private var basetypeRecursions: Int = 0
  private val pendingBaseTypes = new mutable.HashSet[Type]

  def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, AnyDepth)

  def isSubType(tp1: Type, tp2: Type, depth: Int): Boolean = try {
    subsametypeRecursions += 1

    undoLog undoUnless { // if subtype test fails, it should not affect constraints on typevars
      if (subsametypeRecursions >= LogPendingSubTypesThreshold) {
        val p = new SubTypePair(tp1, tp2)
        if (pendingSubTypes(p))
          false
        else 
          try {
            pendingSubTypes += p
            isSubType2(tp1, tp2, depth)
          } finally {
            pendingSubTypes -= p
          }
      } else {
        isSubType2(tp1, tp2, depth)
      }
    }
  } finally {
    subsametypeRecursions -= 1
    // XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866)
    // it doesn't help to keep separate recursion counts for the three methods that now share it
    // if (subsametypeRecursions == 0) undoLog.clear()
  }

  /** Does this type have a prefix that begins with a type variable,
   *  or is it a refinement type? For type prefixes that fulfil this condition,
   *  type selections with the same name of equal (wrt) =:= prefixes are
   *  considered equal wrt =:=
   */
  def beginsWithTypeVarOrIsRefined(tp: Type): Boolean = tp match {
    case SingleType(pre, sym) =>
      !(sym hasFlag PACKAGE) && beginsWithTypeVarOrIsRefined(pre)
    case tv@TypeVar(_, constr) =>
      !tv.instValid || beginsWithTypeVarOrIsRefined(constr.inst)
    case RefinedType(_, _) => 
      true
    case _ =>
      false
  }

  def instTypeVar(tp: Type): Type = tp match {
    case TypeRef(pre, sym, args) =>
      copyTypeRef(tp, instTypeVar(pre), sym, args)
    case SingleType(pre, sym) =>
      singleType(instTypeVar(pre), sym)
    case TypeVar(_, constr) =>
      instTypeVar(constr.inst)
    case _ =>
      tp
  }

  def isErrorOrWildcard(tp: Type) = (tp eq ErrorType) || (tp eq WildcardType)

  def isSingleType(tp: Type) = tp match {
    case ThisType(_) | SuperType(_, _) | SingleType(_, _) => true
    case _ => false
  }

  def isConstantType(tp: Type) = tp match {
    case ConstantType(_) => true
    case _ => false
  }

  // @assume tp1.isHigherKinded || tp2.isHigherKinded
  def isHKSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = (
    tp1.typeSymbol == NothingClass 
    ||
    tp2.typeSymbol == AnyClass // @M Any and Nothing are super-type resp. subtype of every well-kinded type
    || // @M! normalize reduces higher-kinded case to PolyType's
    ((tp1.normalize.withoutAnnotations , tp2.normalize.withoutAnnotations) match {
      case (PolyType(tparams1, res1), PolyType(tparams2, res2)) => // @assume tp1.isHigherKinded && tp2.isHigherKinded (as they were both normalized to PolyType)
        sameLength(tparams1, tparams2) && {
          if (tparams1.head.owner.isMethod) {  // fast-path: polymorphic method type -- type params cannot be captured
            (tparams1 corresponds tparams2)((p1, p2) => p2.info.substSym(tparams2, tparams1) <:< p1.info) &&
            res1 <:< res2.substSym(tparams2, tparams1)
          } else { // normalized higher-kinded type
            //@M for an example of why we need to generate fresh symbols, see neg/tcpoly_ticket2101.scala
            val tpsFresh = cloneSymbols(tparams1)

            (tparams1 corresponds tparams2)((p1, p2) =>
              p2.info.substSym(tparams2, tpsFresh) <:< p1.info.substSym(tparams1, tpsFresh)) &&
            res1.substSym(tparams1, tpsFresh) <:< res2.substSym(tparams2, tpsFresh)

            //@M the forall in the previous test could be optimised to the following,
            // but not worth the extra complexity since it only shaves 1s from quick.comp
            //   (List.forall2(tpsFresh/*optimisation*/, tparams2)((p1, p2) =>
            //   p2.info.substSym(tparams2, tpsFresh) <:< p1.info /*optimisation, == (p1 from tparams1).info.substSym(tparams1, tpsFresh)*/) &&
            // this optimisation holds because inlining cloneSymbols in `val tpsFresh = cloneSymbols(tparams1)` gives:
            // val tpsFresh = tparams1 map (_.cloneSymbol)
            // for (tpFresh <- tpsFresh) tpFresh.setInfo(tpFresh.info.substSym(tparams1, tpsFresh))
        }
      } && annotationsConform(tp1.normalize, tp2.normalize)
      case (_, _) => false // @assume !tp1.isHigherKinded || !tp2.isHigherKinded 
      // --> thus, cannot be subtypes (Any/Nothing has already been checked)
    }))

  /** True if all three arguments have the same number of elements and
   *  the function is true for all the triples.
   */
  @tailrec final def corresponds3[A, B, C](xs1: List[A], xs2: List[B], xs3: List[C], f: (A, B, C) => Boolean): Boolean = {
    if (xs1.isEmpty) xs2.isEmpty && xs3.isEmpty
    else !xs2.isEmpty && !xs3.isEmpty && f(xs1.head, xs2.head, xs3.head) && corresponds3(xs1.tail, xs2.tail, xs3.tail, f)
  }
  
  def isSubArg(t1: Type, t2: Type, variance: Int) =
    (variance > 0 || t2 <:< t1) && (variance < 0 || t1 <:< t2)
    
  def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[Symbol]): Boolean =
    corresponds3(tps1, tps2, tparams map (_.variance), isSubArg)

  def differentOrNone(tp1: Type, tp2: Type) = if (tp1 eq tp2) NoType else tp1

  /** Does type `tp1' conform to `tp2'?
   */
  private def isSubType2(tp1: Type, tp2: Type, depth: Int): Boolean = {
    if ((tp1 eq tp2) || isErrorOrWildcard(tp1) || isErrorOrWildcard(tp2)) return true
    if ((tp1 eq NoType) || (tp2 eq NoType)) return false
    if (tp1 eq NoPrefix) return (tp2 eq NoPrefix) || tp2.typeSymbol.isPackageClass
    if (tp2 eq NoPrefix) return tp1.typeSymbol.isPackageClass
    if (isSingleType(tp1) && isSingleType(tp2) || isConstantType(tp1) && isConstantType(tp2)) return tp1 =:= tp2
    if (tp1.isHigherKinded || tp2.isHigherKinded) return isHKSubType0(tp1, tp2, depth)

    /** First try, on the right:
     *   - unwrap Annotated types, BoundedWildcardTypes,
     *   - bind TypeVars  on the right, if lhs is not Annotated nor BoundedWildcard
     *   - handle common cases for first-kind TypeRefs on both sides as a fast path.
     */
    def firstTry = { incCounter(ctr1); tp2 match {
      // fast path: two typerefs, none of them HK
      case tr2: TypeRef =>
        tp1 match {
          case tr1: TypeRef =>
            val sym1 = tr1.sym
            val sym2 = tr2.sym
            val pre1 = tr1.pre
            val pre2 = tr2.pre
            (((if (sym1 == sym2) phase.erasedTypes || pre1 <:< pre2
               else (sym1.name == sym2.name && !sym1.isModuleClass && !sym2.isModuleClass &&
                     (isUnifiable(pre1, pre2) || isSameSpecializedSkolem(sym1, sym2, pre1, pre2)))) &&
                    isSubArgs(tr1.args, tr2.args, sym1.typeParams))
             ||
             sym2.isClass && {
               val base = tr1 baseType sym2
               (base ne tr1) && base <:< tr2
             }
             ||
             thirdTryRef(tr1, tr2))
          case _ =>
            secondTry
        }
      case AnnotatedType(_, _, _) =>
        tp1.withoutAnnotations <:< tp2.withoutAnnotations && annotationsConform(tp1, tp2)
      case BoundedWildcardType(bounds) =>
        tp1 <:< bounds.hi
      case tv2 @ TypeVar(_, constr2) =>
        tp1 match {
          case AnnotatedType(_, _, _) | BoundedWildcardType(_) =>
            secondTry
          case _ =>
            tv2.registerBound(tp1, true)
        }
      case _ =>
        secondTry
    }}

    /** Second try, on the left:
     *   - unwrap AnnotatedTypes, BoundedWildcardTypes,
     *   - bind typevars,
     *   - handle existential types by skolemization.
     */
    def secondTry = { incCounter(ctr2); tp1 match {
      case AnnotatedType(_, _, _) =>
        tp1.withoutAnnotations <:< tp2.withoutAnnotations && annotationsConform(tp1, tp2)
      case BoundedWildcardType(bounds) =>
        tp1.bounds.lo <:< tp2
      case tv @ TypeVar(_,_) =>
        tv.registerBound(tp2, false)
      case ExistentialType(_, _) =>
        try { 
          skolemizationLevel += 1
          tp1.skolemizeExistential <:< tp2
        } finally {
          skolemizationLevel -= 1
        }
      case _ =>
        thirdTry
    }}

    def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = { 
      incCounter(ctr3); 
      val sym2 = tp2.sym
      sym2 match {
        case NotNullClass => tp1.isNotNull
        case SingletonClass => tp1.isStable || fourthTry
        case _: ClassSymbol =>
          if (isRaw(sym2, tp2.args))
            isSubType(tp1, rawToExistential(tp2), depth)
          else if (sym2.name == tpnme.REFINE_CLASS_NAME)
            isSubType(tp1, sym2.info, depth)
          else
            fourthTry
        case _: TypeSymbol =>
          if (sym2 hasFlag DEFERRED) {
            val tp2a = tp2.bounds.lo
            isDifferentTypeConstructor(tp2, tp2a) && tp1 <:< tp2a || fourthTry
          } else {
            isSubType(tp1.normalize, tp2.normalize, depth)
          }
        case _ =>
          fourthTry
      }
    }
    
    /** Third try, on the right:
     *   - decompose refined types.
     *   - handle typerefs, existentials, and notnull types.
     *   - handle left+right method types, polytypes, typebounds
     */
    def thirdTry = { incCounter(ctr3); tp2 match {
      case tr2: TypeRef =>
        thirdTryRef(tp1, tr2)
      case rt2: RefinedType =>
        (rt2.parents forall (tp1 <:< _)) &&
        (rt2.decls.toList forall tp1.specializes)
      case et2: ExistentialType =>
        et2.withTypeVars(tp1 <:< _, depth) || fourthTry
      case nn2: NotNullType =>
        tp1.isNotNull && tp1 <:< nn2.underlying
      case mt2: MethodType =>
        tp1 match {
          case mt1 @ MethodType(params1, res1) =>
            val params2 = mt2.params
            val res2 = mt2.resultType
            (sameLength(params1, params2) && 
             matchingParams(params1, params2, mt1.isJava, mt2.isJava) && 
             (res1 <:< res2) &&
             mt1.isImplicit == mt2.isImplicit)
          // TODO: if mt1.params.isEmpty, consider NullaryMethodType?
          case _ =>
            false
        }
      case pt2 @ NullaryMethodType(_) =>
        tp1 match {
          // TODO: consider MethodType mt for which mt.params.isEmpty??
          case pt1 @ NullaryMethodType(_) =>
            pt1.resultType <:< pt2.resultType
          case _ =>
            false
        }
      case TypeBounds(lo2, hi2) =>
        tp1 match {
          case TypeBounds(lo1, hi1) =>
            lo2 <:< lo1 && hi1 <:< hi2
          case _ =>
            false
        }
      case _ =>
        fourthTry
    }}

    /** Fourth try, on the left:
     *   - handle typerefs, refined types, notnull and singleton types. 
     */
    def fourthTry = { incCounter(ctr4); tp1 match {
      case tr1 @ TypeRef(_, sym1, _) =>
        sym1 match {
          case NothingClass => true
          case NullClass =>
            tp2 match {
              case TypeRef(_, sym2, _) =>
                sym2.isClass && (sym2 isNonBottomSubClass ObjectClass) &&
                !(tp2.normalize.typeSymbol isNonBottomSubClass NotNullClass)
              case _ =>
                isSingleType(tp2) && tp1 <:< tp2.widen
            }
          case _: ClassSymbol =>
            if (isRaw(sym1, tr1.args)) 
              isSubType(rawToExistential(tp1), tp2, depth)
            else 
              sym1.name == tpnme.REFINE_CLASS_NAME &&
              isSubType(sym1.info, tp2, depth)
          case _: TypeSymbol =>
            if (sym1 hasFlag DEFERRED) {
              val tp1a = tp1.bounds.hi
              isDifferentTypeConstructor(tp1, tp1a) && tp1a <:< tp2
            } else {
              isSubType(tp1.normalize, tp2.normalize, depth)
            } 
          case _ =>
            false
        }
      case RefinedType(parents1, _) =>
        parents1 exists (_ <:< tp2)
      case _: SingletonType | _: NotNullType =>
        tp1.underlying <:< tp2
      case _ =>
        false
    }}

    firstTry
  }

  /** Are `tps1' and `tps2' lists of equal length such
   *  that all elements of `tps1' conform to corresponding elements
   *  of `tps2'?
   */
  def isSubTypes(tps1: List[Type], tps2: List[Type]): Boolean = (tps1 corresponds tps2)(_ <:< _)

  /** Does type `tp' implement symbol `sym' with same or
   *  stronger type? Exact only if `sym' is a member of some
   *  refinement type, otherwise we might return false negatives.
   */
  def specializesSym(tp: Type, sym: Symbol): Boolean =
    tp.typeSymbol == NothingClass ||
    tp.typeSymbol == NullClass && (sym.owner isSubClass ObjectClass) ||
    (tp.nonPrivateMember(sym.name).alternatives exists
      (alt => sym == alt || specializesSym(tp.narrow, alt, sym.owner.thisType, sym)))

  /** Does member `sym1' of `tp1' have a stronger type
   *  than member `sym2' of `tp2'?
   */
  private def specializesSym(tp1: Type, sym1: Symbol, tp2: Type, sym2: Symbol): Boolean = {
    val info1 = tp1.memberInfo(sym1)
    val info2 = tp2.memberInfo(sym2).substThis(tp2.typeSymbol, tp1)
    //System.out.println("specializes "+tp1+"."+sym1+":"+info1+sym1.locationString+" AND "+tp2+"."+sym2+":"+info2)//DEBUG
    sym2.isTerm && (info1 <:< info2) /*&& (!sym2.isStable || sym1.isStable) */ ||
    sym2.isAbstractType && {
      val memberTp1 = tp1.memberType(sym1)
      // println("kinds conform? "+(memberTp1, tp1, sym2, kindsConform(List(sym2), List(memberTp1), tp2, sym2.owner)))
      info2.bounds.containsType(memberTp1) && 
      kindsConform(List(sym2), List(memberTp1), tp1, sym1.owner) 
    } ||
    sym2.isAliasType && tp2.memberType(sym2).substThis(tp2.typeSymbol, tp1) =:= tp1.memberType(sym1) //@MAT ok
  }

  /** A function implementing `tp1' matches `tp2' */
  final def matchesType(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = {
    def matchesQuantified(tparams1: List[Symbol], tparams2: List[Symbol], res1: Type, res2: Type): Boolean = (
      sameLength(tparams1, tparams2) && 
      matchesType(res1, res2.substSym(tparams2, tparams1), alwaysMatchSimple)
    )
    def lastTry = 
      tp2 match {
        case ExistentialType(_, res2) if alwaysMatchSimple =>
          matchesType(tp1, res2, true)
        case MethodType(_, _) =>
          false
        case PolyType(tparams2, res2) =>
          tparams2.isEmpty && matchesType(tp1, res2, alwaysMatchSimple)
        case _ =>
          alwaysMatchSimple || tp1 =:= tp2
      }
    tp1 match {
      case mt1 @ MethodType(params1, res1) =>
        tp2 match {
          case mt2 @ MethodType(params2, res2) =>
            sameLength(params1, params2) && // useful pre-screening optimization
            matchingParams(params1, params2, mt1.isJava, mt2.isJava) && 
            matchesType(res1, res2, alwaysMatchSimple) &&
            mt1.isImplicit == mt2.isImplicit
          case NullaryMethodType(res2) => 
            if (params1.isEmpty) matchesType(res1, res2, alwaysMatchSimple)
            else matchesType(tp1, res2, alwaysMatchSimple)
          case ExistentialType(_, res2) =>
            alwaysMatchSimple && matchesType(tp1, res2, true)
          case _ =>
            false
        }
      case mt1 @ NullaryMethodType(res1) =>
        tp2 match {
          case mt2 @ MethodType(Nil, res2)  => // could never match if params nonEmpty, and !mt2.isImplicit is implied by empty param list
            matchesType(res1, res2, alwaysMatchSimple)
          case NullaryMethodType(res2) => 
            matchesType(res1, res2, alwaysMatchSimple)
          case ExistentialType(_, res2) =>
            alwaysMatchSimple && matchesType(tp1, res2, true)
          case _ =>
            matchesType(res1, tp2, alwaysMatchSimple)
        }
      case PolyType(tparams1, res1) =>
        tp2 match {
          case PolyType(tparams2, res2) =>
            matchesQuantified(tparams1, tparams2, res1, res2)
          case ExistentialType(_, res2) =>
            alwaysMatchSimple && matchesType(tp1, res2, true)
          case _ =>
            false // remember that tparams1.nonEmpty is now an invariant of PolyType
        }
      case ExistentialType(tparams1, res1) =>
        tp2 match {
          case ExistentialType(tparams2, res2) =>
            matchesQuantified(tparams1, tparams2, res1, res2)
          case _ =>
            if (alwaysMatchSimple) matchesType(res1, tp2, true)
            else lastTry
        }
      case _ =>
        lastTry
    }
  }

/** matchesType above is an optimized version of the following implementation:

  def matchesType2(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = {
    def matchesQuantified(tparams1: List[Symbol], tparams2: List[Symbol], res1: Type, res2: Type): Boolean = 
      tparams1.length == tparams2.length &&
      matchesType(res1, res2.substSym(tparams2, tparams1), alwaysMatchSimple)
    (tp1, tp2) match {
      case (MethodType(params1, res1), MethodType(params2, res2)) =>
        params1.length == params2.length && // useful pre-secreening optimization 
        matchingParams(params1, params2, tp1.isInstanceOf[JavaMethodType], tp2.isInstanceOf[JavaMethodType]) && 
        matchesType(res1, res2, alwaysMatchSimple) &&
        tp1.isImplicit == tp2.isImplicit
      case (PolyType(tparams1, res1), PolyType(tparams2, res2)) =>
        matchesQuantified(tparams1, tparams2, res1, res2)
      case (NullaryMethodType(rtp1), MethodType(List(), rtp2)) => 
        matchesType(rtp1, rtp2, alwaysMatchSimple)
      case (MethodType(List(), rtp1), NullaryMethodType(rtp2)) => 
        matchesType(rtp1, rtp2, alwaysMatchSimple)
      case (ExistentialType(tparams1, res1), ExistentialType(tparams2, res2)) =>
        matchesQuantified(tparams1, tparams2, res1, res2)
      case (ExistentialType(_, res1), _) if alwaysMatchSimple =>
        matchesType(res1, tp2, alwaysMatchSimple)
      case (_, ExistentialType(_, res2)) if alwaysMatchSimple =>
        matchesType(tp1, res2, alwaysMatchSimple)
      case (NullaryMethodType(rtp1), _) => 
        matchesType(rtp1, tp2, alwaysMatchSimple)
      case (_, NullaryMethodType(rtp2)) => 
        matchesType(tp1, rtp2, alwaysMatchSimple)
      case (MethodType(_, _), _) => false
      case (PolyType(_, _), _)   => false
      case (_, MethodType(_, _)) => false
      case (_, PolyType(_, _))   => false
      case _ =>
        alwaysMatchSimple || tp1 =:= tp2
    }
  }
*/

  /** Are `syms1' and `syms2' parameter lists with pairwise equivalent types? */
  private def matchingParams(syms1: List[Symbol], syms2: List[Symbol], syms1isJava: Boolean, syms2isJava: Boolean): Boolean = syms1 match {
    case Nil =>
      syms2.isEmpty
    case sym1 :: rest1 =>
      syms2 match {
        case Nil =>
          false
        case sym2 :: rest2 =>
          val tp1 = sym1.tpe
          val tp2 = sym2.tpe
          (tp1 =:= tp2 || 
           syms1isJava && tp2.typeSymbol == ObjectClass && tp1.typeSymbol == AnyClass ||
           syms2isJava && tp1.typeSymbol == ObjectClass && tp2.typeSymbol == AnyClass) &&
          matchingParams(rest1, rest2, syms1isJava, syms2isJava)
      }
  }

  /** like map2, but returns list `xs' itself - instead of a copy - if function
   *  `f' maps all elements to themselves.
   */
  def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] = 
    if (xs.isEmpty) xs
    else {
      val x1 = f(xs.head, ys.head)
      val xs1 = map2Conserve(xs.tail, ys.tail)(f)
      if ((x1 eq xs.head) && (xs1 eq xs.tail)) xs
      else x1 :: xs1
    }    

  /** Solve constraint collected in types `tvars'.
   *
   *  @param tvars      All type variables to be instantiated.
   *  @param tparams    The type parameters corresponding to `tvars'
   *  @param variances  The variances of type parameters; need to reverse
   *                    solution direction for all contravariant variables.
   *  @param upper      When `true' search for max solution else min.
   */
  def solve(tvars: List[TypeVar], tparams: List[Symbol],
            variances: List[Int], upper: Boolean): Boolean =
     solve(tvars, tparams, variances, upper, AnyDepth)

  def solve(tvars: List[TypeVar], tparams: List[Symbol],
            variances: List[Int], upper: Boolean, depth: Int): Boolean = {
    val config = tvars zip (tparams zip variances)

    def solveOne(tvar: TypeVar, tparam: Symbol, variance: Int) {
      if (tvar.constr.inst == NoType) {
        val up = if (variance != CONTRAVARIANT) upper else !upper
        tvar.constr.inst = null
        val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo
        //Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound))
        var cyclic = bound contains tparam
        for ((tvar2, (tparam2, variance2)) <- config) {
          if (tparam2 != tparam &&
              ((bound contains tparam2) ||
               up && (tparam2.info.bounds.lo =:= tparam.tpe) ||
               !up && (tparam2.info.bounds.hi =:= tparam.tpe))) {
            if (tvar2.constr.inst eq null) cyclic = true
            solveOne(tvar2, tparam2, variance2)
          }
        }
        if (!cyclic) {
          if (up) {
            if (bound.typeSymbol != AnyClass)
              tvar addHiBound bound.instantiateTypeParams(tparams, tvars)
            for (tparam2 <- tparams)
              tparam2.info.bounds.lo.dealias match {
                case TypeRef(_, `tparam`, _) =>
                  tvar addHiBound tparam2.tpe.instantiateTypeParams(tparams, tvars)
                case _ =>
              }
          } else {
            if (bound.typeSymbol != NothingClass && bound.typeSymbol != tparam) {
              tvar addLoBound bound.instantiateTypeParams(tparams, tvars)
            }
            for (tparam2 <- tparams)
              tparam2.info.bounds.hi.dealias match {
                case TypeRef(_, `tparam`, _) => 
                  tvar addLoBound tparam2.tpe.instantiateTypeParams(tparams, tvars)
                case _ =>
              }
          }
        }
        tvar.constr.inst = NoType // necessary because hibounds/lobounds may contain tvar

        //println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen)))

        tvar setInst (
          if (up) {
            if (depth != AnyDepth) glb(tvar.constr.hiBounds, depth) else glb(tvar.constr.hiBounds)
          } else {
            if (depth != AnyDepth) lub(tvar.constr.loBounds, depth) else lub(tvar.constr.loBounds)
          })

        //Console.println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))+" = "+tvar.constr.inst)//@MDEBUG
      }
    }    
    
    // println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info)))
    for ((tvar, (tparam, variance)) <- config)
      solveOne(tvar, tparam, variance)

    tvars forall (tvar => tvar.constr.isWithinBounds(tvar.constr.inst))
  }

  /** Do type arguments `targs' conform to formal parameters
   *  `tparams'?
   *
   *  @param tparams ...
   *  @param targs   ...
   *  @return        ...
   */
  def isWithinBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): Boolean = {
    var bounds = instantiatedBounds(pre, owner, tparams, targs)
    if (targs.exists(_.annotations.nonEmpty))
      bounds = adaptBoundsToAnnotations(bounds, tparams, targs)
    (bounds corresponds targs)(_ containsType _)
  }

  def instantiatedBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): List[TypeBounds] = 
    tparams map (_.info.asSeenFrom(pre, owner).instantiateTypeParams(tparams, targs).bounds)

// Lubs and Glbs ---------------------------------------------------------

  /** Given a matrix `tsBts` whose columns are basetype sequences (and the symbols `tsParams` that should be interpreted as type parameters in this matrix),
   * compute its least sorted upwards closed upper bound relative to the following ordering <= between lists of types:
   *
   *    xs <= ys   iff   forall y in ys exists x in xs such that x <: y
   *
   *
   *  @arg tsParams for each type in the original list of types `ts0`, its list of type parameters (if that type is a type constructor)
   *                (these type parameters may be referred to by type arguments in the BTS column of those types,
   *                and must be interpreted as bound variables; i.e., under a type lambda that wraps the types that refer to these type params)
   *  @arg tsBts    a matrix whose columns are basetype sequences
   *                the first row is the original list of types for which we're computing the lub 
   *                  (except that type constructors have been applied to their dummyArgs)
   *  @See baseTypeSeq  for a definition of sorted and upwards closed.
   */
  private def lubList(tsParams: List[List[Symbol]], tsBts: List[List[Type]], depth: Int): List[Type] = {
    // strip typerefs in ts from their arguments if those refer to type parameters that are meant to be bound
    // TODO: this only deals with the simplest of type constructors
    // a better fix would be to actually bind those type parameters that appear free in error, but that would require major changes to the BTS infrastructure
    // example that only kindasorta works now...
      // given: trait Container[+T]; trait Template[+CC[X] <: Container[X]]; class C1[T] extends Template[Container] with Container[T]
    // C1's BTS contains Template[Container] with Container[T], but that should really be [T] => Template[Container] with Container[T]
    // instead of wrapping it in a polytype, the current approach uses elimHOTparams to patch up this type so that 
    // it looks more like a type ctor: Template[Container] with Container, but this is ill-kinded as Template[Container] is a proper type, whereas Container is not
    def elimHOTparams(ts: List[Type]) = ts map { 
      case tp@TypeRef(pre, sym, args) if args.nonEmpty && tsParams.contains(args.map(_.typeSymbol)) => tp.typeConstructor
      case tp => tp
    }

    if (tsBts.tail.isEmpty) tsBts.head
    else if (tsBts exists (_.isEmpty)) List()
    else {
      val ts0 = tsBts map (_.head) // ts0 is the 1-dimensional frontier of symbols cutting through 2-dimensional tsBts, 
      // invariant: all symbols "under" (closer to the first row) the frontier are smaller (according to _.isLess) than the ones "on and beyond" the frontier

      // is the frontier made up of types with the same symbol? 
      // --> produce a single type for this frontier by merging the prefixes and arguments of these typerefs that share the same symbol
      // due to the invariant, that symbol is the current maximal symbol for which this holds, i.e., the one that conveys most information wrt subtyping
      // before merging, strip type arguments that refer to bound type params (when we're computing the lub of type constructors)
      // furthermore, the number of types to merge is reduced without losing information by dropping types that are a subtype of some other type
      val sym0 = ts0.head.typeSymbol
      if (ts0.tail forall (_.typeSymbol == sym0)){
        mergePrefixAndArgs(elimSub(elimHOTparams(ts0), depth), 1, depth).toList ::: lubList(tsParams, tsBts map (_.tail), depth)
      } else { 
        // frontier is not uniform yet, move it beyond the current minimal symbol; lather, rince, repeat
        val sym = minSym(ts0)
        lubList(tsParams, tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts), depth)
      }
    }
  }
  // @AM the following problem is solved by elimHOTparams in lublist
  // @PP lubLists gone bad: lubList(List(
  //   List(scala.collection.generic.GenericCompanion[scala.collection.immutable.Seq], ScalaObject, java.lang.Object, Any)
  //   List(scala.collection.generic.GenericCompanion[scala.collection.mutable.Seq], ScalaObject, java.lang.Object, Any)
  // )) == (
  //   List(scala.collection.generic.GenericCompanion[Seq**[Any]**], ScalaObject, java.lang.Object, Any)
  // )

  /** The minimal symbol (wrt Symbol.isLess) of a list of types */
  private def minSym(tps: List[Type]): Symbol =
    (tps.head.typeSymbol /: tps.tail) {
      (sym1, tp2) => if (tp2.typeSymbol isLess sym1) tp2.typeSymbol else sym1
    }

  /** A minimal type list which has a given list of types as its base type sequence */ 
  def spanningTypes(ts: List[Type]): List[Type] = ts match {
    case List() => List()
    case first :: rest =>
      first :: spanningTypes(
        rest filter (t => !first.typeSymbol.isSubClass(t.typeSymbol)))
  }

  /** Eliminate from list of types all elements which are a supertype
   *  of some other element of the list. */
  private def elimSuper(ts: List[Type]): List[Type] = ts match {
    case List() => List()
    case t :: ts1 =>
      val rest = elimSuper(ts1 filter (t1 => !(t <:< t1)))
      if (rest exists (t1 => t1 <:< t)) rest else t :: rest
  }
  def elimAnonymousClass(t: Type) = t match {
    case TypeRef(pre, clazz, Nil) if clazz.isAnonymousClass =>
      clazz.classBound.asSeenFrom(pre, clazz.owner)
    case _ =>
      t
  }

  /** A collector that tests for existential types appearing at given variance in a type */
  class ContainsVariantExistentialCollector(v: Int) extends TypeCollector(false) {
    def traverse(tp: Type) = tp match {
      case ExistentialType(_, _) if (variance == v) => result = true
      case _ => mapOver(tp)
    }
    def init() = {
      variance = 1
      this
    }
  }

  val containsCovariantExistentialCollector = new ContainsVariantExistentialCollector(1)
  val containsContravariantExistentialCollector = new ContainsVariantExistentialCollector(-1)

  /** Eliminate from list of types all elements which are a subtype
   *  of some other element of the list. */
  private def elimSub(ts: List[Type], depth: Int): List[Type] = {
    def elimSub0(ts: List[Type]): List[Type] = ts match {
      case List() => List()
      case t :: ts1 =>
        val rest = elimSub0(ts1 filter (t1 => !isSubType(t1, t, decr(depth))))
        if (rest exists (t1 => isSubType(t, t1, decr(depth)))) rest else t :: rest
    }
    val ts0 = elimSub0(ts)
    if (ts0.isEmpty || ts0.tail.isEmpty) ts0
    else {
      val ts1 = ts0 mapConserve (t => elimAnonymousClass(t.underlying))
      if (ts1 eq ts0) ts0
      else elimSub(ts1, depth)
    }
  }

  private def stripExistentialsAndTypeVars(ts: List[Type]): (List[Type], List[Symbol]) = {
    val quantified = ts flatMap {
      case ExistentialType(qs, _) => qs
      case t => List()
    }
    def stripType(tp: Type) = tp match {
      case ExistentialType(_, res) => 
        res
      case TypeVar(_, constr) => 
        if (constr.instValid) constr.inst
        else abort("trying to do lub/glb of typevar "+tp)
      case t => t
    }
    val strippedTypes = ts mapConserve stripType
    (strippedTypes, quantified)
  }

  def weakLub(ts: List[Type]) = 
    if (ts.nonEmpty && (ts forall isNumericValueType)) (numericLub(ts), true)
    else if (ts.nonEmpty && (ts exists (_.annotations.nonEmpty)))
      (annotationsLub(lub(ts map (_.withoutAnnotations)), ts), true)
    else (lub(ts), false)

  def weakGlb(ts: List[Type]) = {
    if (ts.nonEmpty && (ts forall isNumericValueType)) {
      val nglb = numericGlb(ts)
      if (nglb != NoType) (nglb, true)
      else (glb(ts), false)
    } else if (ts.nonEmpty && (ts exists (_.annotations.nonEmpty))) {
      (annotationsGlb(glb(ts map (_.withoutAnnotations)), ts), true)
    } else (glb(ts), false)
  }

  def numericLub(ts: List[Type]) =
    ts reduceLeft ((t1, t2) => 
      if (isNumericSubType(t1, t2)) t2 
      else if (isNumericSubType(t2, t1)) t1
      else IntClass.tpe)

  def numericGlb(ts: List[Type]) =
    ts reduceLeft ((t1, t2) => 
      if (isNumericSubType(t1, t2)) t1 
      else if (isNumericSubType(t2, t1)) t2
      else NoType)

  def isWeakSubType(tp1: Type, tp2: Type) = 
    tp1.deconst.normalize match {
      case TypeRef(_, sym1, _) if isNumericValueClass(sym1) =>
        tp2.deconst.normalize match {
          case TypeRef(_, sym2, _) if isNumericValueClass(sym2) =>
            isNumericSubClass(sym1, sym2)
          case tv2 @ TypeVar(_, _) =>
            tv2.registerBound(tp1, isLowerBound = true, isNumericBound = true)
          case _ =>
            isSubType(tp1, tp2)
        }
      case tv1 @ TypeVar(_, _) =>
        tp2.deconst.normalize match {
          case TypeRef(_, sym2, _) if isNumericValueClass(sym2) =>
            tv1.registerBound(tp2, isLowerBound = false, isNumericBound = true)
          case _ =>
            isSubType(tp1, tp2)
        }
      case _ =>
        isSubType(tp1, tp2)
    }

  def isNumericSubType(tp1: Type, tp2: Type) =
    isNumericValueType(tp1) && isNumericValueType(tp2) &&  
    isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol)

  private val lubResults = new mutable.HashMap[(Int, List[Type]), Type]
  private val glbResults = new mutable.HashMap[(Int, List[Type]), Type]

  def lub(ts: List[Type]): Type = try {
    lub(ts, lubDepth(ts))
  } finally {
    lubResults.clear()
    glbResults.clear()
  }
 
  /** The least upper bound wrt <:< of a list of types */
  def lub(ts: List[Type], depth: Int): Type = {
    def lub0(ts0: List[Type]): Type = elimSub(ts0, depth) match {
      case List() => NothingClass.tpe
      case List(t) => t
      case ts @ PolyType(tparams, _) :: _ =>
        val tparams1 = (tparams, matchingBounds(ts, tparams).transpose).zipped map
          ((tparam, bounds) => tparam.cloneSymbol.setInfo(glb(bounds, depth)))
        PolyType(tparams1, lub0(matchingInstTypes(ts, tparams1)))
      case ts @ MethodType(params, _) :: rest =>
        MethodType(params, lub0(matchingRestypes(ts, params map (_.tpe))))
      case ts @ NullaryMethodType(_) :: rest =>
        NullaryMethodType(lub0(matchingRestypes(ts, Nil)))
      case ts @ TypeBounds(_, _) :: rest =>
        TypeBounds(glb(ts map (_.bounds.lo), depth), lub(ts map (_.bounds.hi), depth))
      case ts =>
        lubResults get (depth, ts) match {
          case Some(lubType) => 
            lubType
          case None => 
            lubResults((depth, ts)) = AnyClass.tpe
            val res = if (depth < 0) AnyClass.tpe else lub1(ts)
            lubResults((depth, ts)) = res
            res
        }
    }
    def lub1(ts0: List[Type]): Type = {
      val (ts, tparams) = stripExistentialsAndTypeVars(ts0)
      val lubBaseTypes: List[Type] = lubList(ts map (_.typeParams), ts map (_.baseTypeSeq.toList), depth)
      val lubParents = spanningTypes(lubBaseTypes)
      val lubOwner = commonOwner(ts)
      val lubBase = intersectionType(lubParents, lubOwner)
      val lubType =
        if (phase.erasedTypes || depth == 0) lubBase
        else {
          val lubRefined = refinedType(lubParents, lubOwner)
          val lubThisType = lubRefined.typeSymbol.thisType
          val narrowts = ts map (_.narrow)
          def lubsym(proto: Symbol): Symbol = {
            val prototp = lubThisType.memberInfo(proto)
            val syms = narrowts map (t =>
              t.nonPrivateMember(proto.name).suchThat(sym =>
                sym.tpe matches prototp.substThis(lubThisType.typeSymbol, t)))
            if (syms contains NoSymbol) NoSymbol
            else {
              val symtypes =
                (narrowts, syms).zipped map ((t, sym) => t.memberInfo(sym).substThis(t.typeSymbol, lubThisType))
              if (proto.isTerm) // possible problem: owner of info is still the old one, instead of new refinement class
                proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(lub(symtypes, decr(depth)))
              else if (symtypes.tail forall (symtypes.head =:=))
                proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(symtypes.head)
              else {
                def lubBounds(bnds: List[TypeBounds]): TypeBounds =
                  TypeBounds(glb(bnds map (_.lo), decr(depth)), lub(bnds map (_.hi), decr(depth)))
                lubRefined.typeSymbol.newAbstractType(proto.pos, proto.name.toTypeName)
                  .setInfoOwnerAdjusted(lubBounds(symtypes map (_.bounds)))
              }
            }
          }
          def refines(tp: Type, sym: Symbol): Boolean = {
            val syms = tp.nonPrivateMember(sym.name).alternatives;
            !syms.isEmpty && (syms forall (alt =>
              // todo alt != sym is strictly speaking not correct, but without it we lose 
              // efficiency.
              alt != sym && !specializesSym(lubThisType, sym, tp, alt)))
          }
          for (sym <- lubBase.nonPrivateMembers) {
            // add a refinement symbol for all non-class members of lubBase
            // which are refined by every type in ts.
            if (!sym.isClass && !sym.isConstructor && (narrowts forall (t => refines(t, sym))))
              try {
                val lsym = lubsym(sym)
                if (lsym != NoSymbol) addMember(lubThisType, lubRefined, lubsym(sym))
              } catch {
                case ex: NoCommonType =>
              }
          }
          if (lubRefined.decls.isEmpty) lubBase
          else if (!verifyLubs) lubRefined
          else {
            // Verify that every given type conforms to the calculated lub.
            // In theory this should not be necessary, but higher-order type
            // parameters are not handled correctly.
            val ok = ts forall { t =>
              (t <:< lubRefined) || {
                if (settings.debug.value) {
                  Console.println(
                    "Malformed lub: " + lubRefined + "\n" +
                    "Argument " + t + " does not conform.  Falling back to " + lubBase
                  )
                }
                false
              }
            }
            // If not, fall back on the more conservative calculation.
            if (ok) lubRefined
            else lubBase
          }
        }
      existentialAbstraction(tparams, lubType)
    }
    if (printLubs) {
      println(indent + "lub of " + ts + " at depth "+depth)//debug
      indent = indent + "  "
      assert(indent.length <= 100)
    }
    val res = lub0(ts)
    if (printLubs) {
      indent = indent dropRight 2
      println(indent + "lub of " + ts + " is " + res)//debug
    }
    if (ts forall (_.isNotNull)) res.notNull else res
  }

  val GlbFailure = new Throwable

  /** A global counter for glb calls in the `specializes' query connected to the `addMembers'
   *  call in `glb'. There's a possible infinite recursion when `specializes' calls
   *  memberType, which calls baseTypeSeq, which calls mergePrefixAndArgs, which calls glb.
   *  The counter breaks this recursion after two calls.
   *  If the recursion is broken, no member is added to the glb.
   */
  private var globalGlbDepth = 0
  private final val globalGlbLimit = 2

  def glb(ts: List[Type]): Type = try {
    glb(ts, lubDepth(ts))
  } finally {
    lubResults.clear()
    glbResults.clear()
  }

  /** The greatest lower bound wrt <:< of a list of types */
  private def glb(ts: List[Type], depth: Int): Type = {
    def glb0(ts0: List[Type]): Type = elimSuper(ts0) match {
      case List() => AnyClass.tpe
      case List(t) => t
      case ts @ PolyType(tparams, _) :: _ =>
        val tparams1 = (tparams, matchingBounds(ts, tparams).transpose).zipped map
          ((tparam, bounds) => tparam.cloneSymbol.setInfo(lub(bounds, depth)))
        PolyType(tparams1, glb0(matchingInstTypes(ts, tparams1)))
      case ts @ MethodType(params, _) :: rest =>
        MethodType(params, glb0(matchingRestypes(ts, params map (_.tpe))))
      case ts @ NullaryMethodType(_) :: rest =>
        NullaryMethodType(glb0(matchingRestypes(ts, Nil)))
      case ts @ TypeBounds(_, _) :: rest =>
        TypeBounds(lub(ts map (_.bounds.lo), depth), glb(ts map (_.bounds.hi), depth))
      case ts =>
        glbResults get (depth, ts) match {
          case Some(glbType) =>
            glbType
          case _ =>
            glbResults((depth, ts)) = NothingClass.tpe
            val res = if (depth < 0) NothingClass.tpe else glb1(ts)
            glbResults((depth, ts)) = res
            res
        }
    }
    def glb1(ts0: List[Type]): Type = {
      try {
        val (ts, tparams) = stripExistentialsAndTypeVars(ts0)
        val glbOwner = commonOwner(ts)
        def refinedToParents(t: Type): List[Type] = t match {
          case RefinedType(ps, _) => ps flatMap refinedToParents
          case _ => List(t)
        }
        def refinedToDecls(t: Type): List[Scope] = t match {
          case RefinedType(ps, decls) => 
            val dss = ps flatMap refinedToDecls
            if (decls.isEmpty) dss else decls :: dss
          case _ => List()
        }
        val ts1 = ts flatMap refinedToParents 
        val glbBase = intersectionType(ts1, glbOwner)
        val glbType = 
          if (phase.erasedTypes || depth == 0) glbBase
          else {
            val glbRefined = refinedType(ts1, glbOwner)
            val glbThisType = glbRefined.typeSymbol.thisType
            def glbsym(proto: Symbol): Symbol = {
              val prototp = glbThisType.memberInfo(proto)
              val syms = for (t <- ts;
                    alt <- (t.nonPrivateMember(proto.name).alternatives);
                if glbThisType.memberInfo(alt) matches prototp
              ) yield alt
              val symtypes = syms map glbThisType.memberInfo
              assert(!symtypes.isEmpty)
              proto.cloneSymbol(glbRefined.typeSymbol).setInfoOwnerAdjusted(
                if (proto.isTerm) glb(symtypes, decr(depth))
                else {
                  def isTypeBound(tp: Type) = tp match {
                    case TypeBounds(_, _) => true
                    case _ => false 
                  }
                  def glbBounds(bnds: List[Type]): TypeBounds = {
                    val lo = lub(bnds map (_.bounds.lo), decr(depth))
                    val hi = glb(bnds map (_.bounds.hi), decr(depth))
                    if (lo <:< hi) TypeBounds(lo, hi)
                    else throw GlbFailure
                  }
                  val symbounds = symtypes filter isTypeBound
                  var result: Type =
                    if (symbounds.isEmpty)
                      TypeBounds.empty
                    else glbBounds(symbounds)
                  for (t <- symtypes if !isTypeBound(t))
                    if (result.bounds containsType t) result = t
                    else throw GlbFailure
                  result
                })
            }
            if (globalGlbDepth < globalGlbLimit)
              try {
                globalGlbDepth += 1
                val dss = ts flatMap refinedToDecls
                for (ds <- dss; val sym <- ds.iterator) 
                  if (globalGlbDepth < globalGlbLimit && !(glbThisType specializes sym))
                    try {
                      addMember(glbThisType, glbRefined, glbsym(sym))
                    } catch {
                      case ex: NoCommonType =>
                    } 
              } finally {
                globalGlbDepth -= 1
              }
            if (glbRefined.decls.isEmpty) glbBase else glbRefined
          }
        existentialAbstraction(tparams, glbType)
      } catch {
        case GlbFailure =>
          if (ts forall (t => NullClass.tpe <:< t)) NullClass.tpe
          else NothingClass.tpe
      }
    }
    // if (settings.debug.value) { println(indent + "glb of " + ts + " at depth "+depth); indent = indent + "  " } //DEBUG

    val res = glb0(ts)

    // if (settings.debug.value) { indent = indent.substring(0, indent.length() - 2); log(indent + "glb of " + ts + " is " + res) }//DEBUG

    if (ts exists (_.isNotNull)) res.notNull else res
  }

  /** The most deeply nested owner that contains all the symbols
   *  of thistype or prefixless typerefs/singletype occurrences in given type.
   */
  private def commonOwner(t: Type): Symbol = {
    commonOwnerMap.init
    commonOwnerMap.apply(t)
    commonOwnerMap.result
  }

  /** The most deeply nested owner that contains all the symbols
   *  of thistype or prefixless typerefs/singletype occurrences in given list
   *  of types.
   */
  private def commonOwner(tps: List[Type]): Symbol = {
    // if (settings.debug.value) log("computing common owner of types " + tps)//DEBUG
    commonOwnerMap.init
    tps foreach { tp => commonOwnerMap.apply(tp); () }
    commonOwnerMap.result
  }

  /** Compute lub (if variance == 1) or glb (if variance == -1) of given list
   *  of types `tps'. All types in `tps' are typerefs or singletypes
   *  with the same symbol.
   *  Return `Some(x)' if the computation succeeds with result `x'.
   *  Return `None' if the computation fails.
   */
  def mergePrefixAndArgs(tps: List[Type], variance: Int, depth: Int): Option[Type] = tps match {
    case List(tp) =>
      Some(tp)
    case TypeRef(_, sym, _) :: rest =>
      val pres = tps map (_.prefix) // prefix normalizes automatically
      val pre = if (variance == 1) lub(pres, depth) else glb(pres, depth)
      val argss = tps map (_.normalize.typeArgs) // symbol equality (of the tp in tps) was checked using typeSymbol, which normalizes, so should normalize before retrieving arguments
      val capturedParams = new ListBuffer[Symbol]
      try {
        if (sym == ArrayClass && phase.erasedTypes) {
          // special treatment for lubs of array types after erasure:
          // if argss contain one value type and some other type, the lub is Object
          // if argss contain several reference types, the lub is an array over lub of argtypes
          if (argss exists (_.isEmpty)) {
            None  // something is wrong: an array without a type arg.
          } else {
            val args = argss map (_.head)
            if (args.tail forall (_ =:= args.head)) Some(typeRef(pre, sym, List(args.head)))
            else if (args exists (arg => isValueClass(arg.typeSymbol))) Some(ObjectClass.tpe)
            else Some(typeRef(pre, sym, List(lub(args))))
          }
        } else {
          val args = (sym.typeParams, argss.transpose).zipped map { (tparam, as) =>
              if (depth == 0)
                if (tparam.variance == variance) AnyClass.tpe
                else if (tparam.variance == -variance) NothingClass.tpe
                else NoType
              else {
                if (tparam.variance == variance) lub(as, decr(depth))
                else if (tparam.variance == -variance) glb(as, decr(depth))
                else {
                  val l = lub(as, decr(depth))
                  val g = glb(as, decr(depth))
                  if (l <:< g) l
                  else { // Martin: I removed this, because incomplete. Not sure there is a good way to fix it. For the moment we
                         // just err on the conservative side, i.e. with a bound that is too high.
                         // if(!(tparam.info.bounds contains tparam)){ //@M can't deal with f-bounds, see #2251

                    val qvar = commonOwner(as) freshExistential "" setInfo TypeBounds(g, l)
                    capturedParams += qvar
                    qvar.tpe
                  }
                }
              }
            }
          if (args contains NoType) None
          else Some(existentialAbstraction(capturedParams.toList, typeRef(pre, sym, args)))
        }
      } catch {
        case ex: MalformedType => None
        case ex: IndexOutOfBoundsException =>  // transpose freaked out because of irregular argss
        // catching just in case (shouldn't happen, but also doesn't cost us)
        if (settings.debug.value) log("transposed irregular matrix!?"+ (tps, argss))
        None
      }
    case SingleType(_, sym) :: rest =>
      val pres = tps map (_.prefix)
      val pre = if (variance == 1) lub(pres, depth) else glb(pres, depth)
      try {
        Some(singleType(pre, sym))
      } catch {
        case ex: MalformedType => None
      }
    case ExistentialType(tparams, quantified) :: rest =>
      mergePrefixAndArgs(quantified :: rest, variance, depth) map (existentialAbstraction(tparams, _))
    case _ =>
      assert(false, tps); None
  }

  /** Make symbol `sym' a member of scope `tp.decls'
   *  where `thistp' is the narrowed owner type of the scope.
   */
  def addMember(thistp: Type, tp: Type, sym: Symbol) {
    assert(sym != NoSymbol)
    // if (settings.debug.value) log("add member " + sym+":"+sym.info+" to "+thistp) //DEBUG
    if (!(thistp specializes sym)) {
      if (sym.isTerm)
        for (alt <- tp.nonPrivateDecl(sym.name).alternatives)
          if (specializesSym(thistp, sym, thistp, alt))
            tp.decls unlink alt;
      tp.decls enter sym
    }
  }

  /** All types in list must be polytypes with type parameter lists of
   *  same length as tparams.
   *  Returns list of list of bounds infos, where corresponding type
   *  parameters are renamed to tparams.
   */
  private def matchingBounds(tps: List[Type], tparams: List[Symbol]): List[List[Type]] = {
    def getBounds(tp: Type): List[Type] = tp match {
      case PolyType(tparams1, _) if sameLength(tparams1, tparams) =>
        tparams1 map (tparam => tparam.info.substSym(tparams1, tparams))
      case tp =>
        if (tp ne tp.normalize) getBounds(tp.normalize)
        else throw new NoCommonType(tps)
    }
    tps map getBounds
  }

  /** All types in list must be polytypes with type parameter lists of
   *  same length as tparams.
   *  Returns list of instance types, where corresponding type
   *  parameters are renamed to tparams.
   */
  private def matchingInstTypes(tps: List[Type], tparams: List[Symbol]): List[Type] = {
    def transformResultType(tp: Type): Type = tp match {
      case PolyType(tparams1, restpe) if sameLength(tparams1, tparams) =>
        restpe.substSym(tparams1, tparams)
      case tp =>
        if (tp ne tp.normalize) transformResultType(tp.normalize)
        else throw new NoCommonType(tps)
    }
    tps map transformResultType
  }

  /** All types in list must be method types with equal parameter types.
   *  Returns list of their result types.
   */
  private def matchingRestypes(tps: List[Type], pts: List[Type]): List[Type] =
    tps map {
      case MethodType(params1, res) if (isSameTypes(params1 map (_.tpe), pts)) =>
        res
      case NullaryMethodType(res) if pts isEmpty =>
        res
      case _ =>
        throw new NoCommonType(tps)
    }


  // TODO: this desperately needs to be cleaned up
  // plan: split into kind inference and subkinding
  // every Type has a (cached) Kind
  def kindsConform(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): Boolean =
    checkKindBounds0(tparams, targs, pre, owner, false).isEmpty

  /** Check well-kindedness of type application (assumes arities are already checked) -- @M
   * 
   * This check is also performed when abstract type members become concrete (aka a "type alias") -- then tparams.length==1
   * (checked one type member at a time -- in that case, prefix is the name of the type alias)
   *
   * Type application is just like value application: it's "contravariant" in the sense that 
   * the type parameters of the supplied type arguments must conform to the type parameters of 
   * the required type parameters:
   *   - their bounds must be less strict
   *   - variances must match (here, variances are absolute, the variance of a type parameter does not influence the variance of its higher-order parameters)     
   *   - @M TODO: are these conditions correct,sufficient&necessary?
   *
   *  e.g. class Iterable[t, m[+x <: t]] --> the application Iterable[Int, List] is okay, since 
   *       List's type parameter is also covariant and its bounds are weaker than <: Int
   */
  def checkKindBounds0(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol, explainErrors: Boolean): List[(Type, Symbol, List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)])] = {
    var error = false

    def transform(tp: Type, clazz: Symbol): Type = tp.asSeenFrom(pre, clazz) // instantiate type params that come from outside the abstract type we're currently checking
    def transformedBounds(p: Symbol, o: Symbol) = transform(p.info.instantiateTypeParams(tparams, targs).bounds, o)

    /** Check whether <arg>sym1</arg>'s variance conforms to <arg>sym2</arg>'s variance
     *
     * If <arg>sym2</arg> is invariant, <arg>sym1</arg>'s variance is irrelevant. Otherwise they must be equal.
     */
    def variancesMatch(sym1: Symbol, sym2: Symbol): Boolean = (sym2.variance==0 || sym1.variance==sym2.variance)

    // check that the type parameters <arg>hkargs</arg> to a higher-kinded type conform to the expected params <arg>hkparams</arg>
    def checkKindBoundsHK(
      hkargs:        List[Symbol],
      arg:           Symbol,
      param:         Symbol,
      paramowner:    Symbol,
      underHKParams: List[Symbol],
      withHKArgs:    List[Symbol]
    ): (List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)]) = {
      
      def bindHKParams(tp: Type) = tp.substSym(underHKParams, withHKArgs)
      // @M sometimes hkargs != arg.typeParams, the symbol and the type may have very different type parameters
      val hkparams = param.typeParams

      if (settings.debug.value) {
        log("checkKindBoundsHK expected: "+ param +" with params "+ hkparams +" by definition in "+ paramowner)
        log("checkKindBoundsHK supplied: "+ arg +" with params "+ hkargs +" from "+ owner)
        log("checkKindBoundsHK under params: "+ underHKParams +" with args "+ withHKArgs)
      }

      if (!sameLength(hkargs, hkparams)) {
        if (arg == AnyClass || arg == NothingClass) (Nil, Nil, Nil) // Any and Nothing are kind-overloaded
        else {error = true; (List((arg, param)), Nil, Nil) } // shortcut: always set error, whether explainTypesOrNot
      }
      else {
        val _arityMismatches    = if (explainErrors) new ListBuffer[(Symbol, Symbol)] else null
        val _varianceMismatches = if (explainErrors) new ListBuffer[(Symbol, Symbol)] else null
        val _stricterBounds     = if (explainErrors) new ListBuffer[(Symbol, Symbol)] else null
        
        def varianceMismatch(a: Symbol, p: Symbol) { if(explainErrors) _varianceMismatches += ((a, p)) else error = true}
        def stricterBound(a: Symbol, p: Symbol) { if(explainErrors) _stricterBounds += ((a, p)) else error = true }
        def arityMismatches(as: Iterable[(Symbol, Symbol)]) { if(explainErrors) _arityMismatches ++= as }
        def varianceMismatches(as: Iterable[(Symbol, Symbol)]) { if(explainErrors) _varianceMismatches ++= as }
        def stricterBounds(as: Iterable[(Symbol, Symbol)]) { if(explainErrors) _stricterBounds ++= as }

        for ((hkarg, hkparam) <- hkargs zip hkparams) { 
          if (hkparam.typeParams.isEmpty && hkarg.typeParams.isEmpty) { // base-case: kind *
            if (!variancesMatch(hkarg, hkparam))
              varianceMismatch(hkarg, hkparam)                                         

            // instantiateTypeParams(tparams, targs) --> higher-order bounds may contain references to type arguments
            // substSym(hkparams, hkargs) --> these types are going to be compared as types of kind * 
            //    --> their arguments use different symbols, but are conceptually the same 
            //        (could also replace the types by polytypes, but can't just strip the symbols, as ordering is lost then)
            val declaredBounds     = transformedBounds(hkparam, paramowner)
            val declaredBoundsInst = bindHKParams(declaredBounds)
            val argumentBounds     = transform(hkarg.info.bounds, owner)            
            if (!(declaredBoundsInst <:< argumentBounds))
              stricterBound(hkarg, hkparam)

            if (settings.debug.value) log(
              "checkKindBoundsHK base case: " + hkparam +
              " declared bounds: " + declaredBounds +
              " after instantiating earlier hkparams: " + declaredBoundsInst + "\n" +
              "checkKindBoundsHK base case: "+ hkarg + 
              " has bounds: " + argumentBounds
            )
          }
          else {
            if (settings.debug.value)
              log("checkKindBoundsHK recursing to compare params of "+ hkparam +" with "+ hkarg)
            val (am, vm, sb) = checkKindBoundsHK(
              hkarg.typeParams,
              hkarg,
              hkparam,
              paramowner, 
              underHKParams ++ hkparam.typeParams,
              withHKArgs ++ hkarg.typeParams
            )
            arityMismatches(am)
            varianceMismatches(vm)
            stricterBounds(sb)
          }
          if (!explainErrors && error) return (Nil, Nil, Nil) // stop as soon as we encountered an error
        }
        if (!explainErrors) (Nil, Nil, Nil)
        else (_arityMismatches.toList, _varianceMismatches.toList, _stricterBounds.toList)
      }    
    }

    val errors = new ListBuffer[(Type, Symbol, List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)])]
    if (tparams.nonEmpty || targs.nonEmpty)
      log("checkKindBounds0(" + tparams + ", " + targs + ", " + pre + ", " + owner + ", " + explainErrors + ")")

    for {
      (tparam, targ) <- tparams zip targs
      // Prevent WildcardType from causing kind errors, as typevars may be higher-order
      if (targ != WildcardType) && (targ.isHigherKinded || tparam.typeParams.nonEmpty)
    } {
      // @M must use the typeParams of the *type* targ, not of the *symbol* of targ!!
      targ.typeSymbolDirect.info // force symbol load for #4205
      val tparamsHO = targ.typeParams

      val (arityMismatches, varianceMismatches, stricterBounds) = (
        // NOTE: *not* targ.typeSymbol, which normalizes
        checkKindBoundsHK(tparamsHO, targ.typeSymbolDirect, tparam, tparam.owner, tparam.typeParams, tparamsHO)
      )
      if (explainErrors) {
        if (arityMismatches.nonEmpty || varianceMismatches.nonEmpty || stricterBounds.nonEmpty) {
          errors += ((targ, tparam, arityMismatches, varianceMismatches, stricterBounds))
        }
      }
      else if (error)
        return List((NoType, NoSymbol, Nil, Nil, Nil))
    }
  
    errors.toList
  }

// Errors and Diagnostics -----------------------------------------------------

  /** A throwable signalling a type error */
  class TypeError(var pos: Position, val msg: String) extends Throwable(msg) {
    def this(msg: String) = this(NoPosition, msg)
  }

  class NoCommonType(tps: List[Type]) extends Throwable(
    "lub/glb of incompatible types: " + tps.mkString("", " and ", "")) with ControlThrowable

  /** A throwable signalling a malformed type */
  class MalformedType(msg: String) extends TypeError(msg) {
    def this(pre: Type, tp: String) = this("malformed type: " + pre + "#" + tp)
  }

  /** An exception signalling a variance annotation/usage conflict */
  class VarianceError(msg: String) extends TypeError(msg)

  /** The current indentation string for traces */
  private var indent: String = ""

  /** Perform operation `p' on arguments `tp1',
   *  `arg2' and print trace of computation.
   */
  private def explain[T](op: String, p: (Type, T) => Boolean, tp1: Type, arg2: T): Boolean = {
    Console.println(indent + tp1 + " " + op + " " + arg2 + "?" /* + "("+tp1.getClass+","+arg2.asInstanceOf[AnyRef].getClass+")"*/)
    indent = indent + "  "
    val result = p(tp1, arg2)
    indent = indent dropRight 2
    Console.println(indent + result)
    result
  }

  /** If option `explaintypes' is set, print a subtype trace for
   *  `found <:< required'.
   */
  def explainTypes(found: Type, required: Type) {
    if (settings.explaintypes.value) withTypesExplained(found <:< required)
  }

  /** If option `explaintypes' is set, print a subtype trace for
   *  `op(found, required)'.
   */
  def explainTypes(op: (Type, Type) => Any, found: Type, required: Type) {
    if (settings.explaintypes.value) withTypesExplained(op(found, required))
  }

  /** Execute `op' while printing a trace of the operations on types executed.
   */
  def withTypesExplained[A](op: => A): A = {
    val s = explainSwitch
    try { explainSwitch = true; op } finally { explainSwitch = s }
  }

  def objToAny(tp: Type): Type =
    if (!phase.erasedTypes && tp.typeSymbol == ObjectClass) AnyClass.tpe
    else tp

  val shorthands = Set(
    "scala.collection.immutable.List", 
    "scala.collection.immutable.Nil",
    "scala.collection.Seq",
    "scala.collection.Traversable",
    "scala.collection.Iterable",
    "scala.collection.mutable.StringBuilder",
    "scala.collection.IndexedSeq",
    "scala.collection.Iterator")
}