Merge pull request #2201 from retronym/topic/types-break-down-squash

Carve up Types.scala

7 files changed, 2732 insertions, 2649 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index f4befb1470..a6c5367425 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -14,7 +14,6 @@ import Flags._
 import scala.util.control.ControlThrowable
 import scala.annotation.tailrec
 import util.Statistics
-import scala.runtime.ObjectRef
 import util.ThreeValues._
 import Variance._
 
@@ -73,28 +72,33 @@ import Variance._
     // only used during erasure of derived value classes.
 */
 
-trait Types extends api.Types { self: SymbolTable =>
+trait Types
+  extends api.Types
+  with tpe.TypeComparers
+  with tpe.TypeToStrings
+  with tpe.CommonOwners
+  with tpe.GlbLubs
+  with tpe.TypeMaps
+  with tpe.TypeConstraints { self: SymbolTable =>
+
   import definitions._
   import TypesStats._
 
   private var explainSwitch = false
   private final val emptySymbolSet = immutable.Set.empty[Symbol]
 
-  private final val LogPendingSubTypesThreshold = 50
-  private final val LogPendingBaseTypesThreshold = 50
-  private final val LogVolatileThreshold = 50
+  protected[internal] final val DefaultLogThreshhold = 50
+  private final val LogPendingBaseTypesThreshold = DefaultLogThreshhold
+  private final val LogVolatileThreshold = DefaultLogThreshhold
 
   /** A don't care value for the depth parameter in lubs/glbs and related operations. */
-  private final val AnyDepth = -3
+  protected[internal] 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
+  protected[internal] final def decr(depth: Int) = if (depth == AnyDepth) AnyDepth else depth - 1
 
-  private final val printLubs = sys.props contains "scalac.debug.lub"
   private final val traceTypeVars = sys.props contains "scalac.debug.tvar"
   private final val breakCycles = settings.breakCycles.value
-  /** In case anyone wants to turn off lub verification without reverting anything. */
-  private final val verifyLubs = true
   /** In case anyone wants to turn off type parameter bounds being used
    *  to seed type constraints.
    */
@@ -107,80 +111,6 @@ trait Types extends api.Types { self: SymbolTable =>
    */
   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.
-   */
-  lazy val undoLog = newUndoLog
-
-  protected def newUndoLog = new UndoLog
-
-  class UndoLog extends Clearable {
-    private type UndoPairs = List[(TypeVar, TypeConstraint)]
-    //OPT this method is public so we can do `manual inlining`
-    var log: UndoPairs = List()
-
-    /*
-     * These two methods provide explicit locking mechanism that is overridden in SynchronizedUndoLog.
-     *
-     * The idea behind explicit locking mechanism is that all public methods that access mutable state
-     * will have to obtain the lock for their entire execution so both reads and writes can be kept in
-     * right order. Originally, that was achieved by overriding those public methods in
-     * `SynchronizedUndoLog` which was fine but expensive. The reason is that those public methods take
-     * thunk as argument and if we keep them non-final there's no way to make them inlined so thunks
-     * can go away.
-     *
-     * By using explicit locking we can achieve inlining.
-     *
-     * NOTE: They are made public for now so we can apply 'manual inlining' (copy&pasting into hot
-     * places implementation of `undo` or `undoUnless`). This should be changed back to protected
-     * once inliner is fixed.
-     */
-    def lock(): Unit = ()
-    def unlock(): Unit = ()
-
-    // register with the auto-clearing cache manager
-    perRunCaches.recordCache(this)
-
-    /** Undo all changes to constraints to type variables upto `limit`. */
-    //OPT this method is public so we can do `manual inlining`
-    def undoTo(limit: UndoPairs) {
-      assertCorrectThread()
-      while ((log ne limit) && log.nonEmpty) {
-        val (tv, constr) = log.head
-        tv.constr = constr
-        log = log.tail
-      }
-    }
-
-    /** No sync necessary, because record should only
-     *  be called from within an undo or undoUnless block,
-     *  which is already synchronized.
-     */
-    private[reflect] def record(tv: TypeVar) = {
-      log ::= ((tv, tv.constr.cloneInternal))
-    }
-
-    def clear() {
-      lock()
-      try {
-        if (settings.debug.value)
-          self.log("Clearing " + log.size + " entries from the undoLog.")
-        log = Nil
-      } finally unlock()
-    }
-
-    // `block` should not affect constraints on typevars
-    def undo[T](block: => T): T = {
-      lock()
-      try {
-        val before = log
-
-        try block
-        finally undoTo(before)
-      } finally unlock()
-    }
-  }
-
   /** 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,
@@ -3732,72 +3662,7 @@ trait Types extends api.Types { self: SymbolTable =>
       newExistentialType(tparams1, tpe1)
     }
 
-  /** Normalize any type aliases within this type (@see Type#normalize).
-   *  Note that this depends very much on the call to "normalize", not "dealias",
-   *  so it is no longer carries the too-stealthy name "deAlias".
-   */
-  object normalizeAliases extends TypeMap {
-    def apply(tp: Type): Type = tp match {
-      case TypeRef(_, sym, _) if sym.isAliasType =>
-        def msg = if (tp.isHigherKinded) s"Normalizing type alias function $tp" else s"Dealiasing type alias $tp"
-        mapOver(logResult(msg)(tp.normalize))
-      case _                                     => mapOver(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) =>
-          parents filter (_.typeSymbol != SingletonClass) match {
-            case Nil                       => AnyClass.tpe
-            case p :: Nil if decls.isEmpty => mapOver(p)
-            case ps                        => mapOver(copyRefinedType(tp1, ps, decls))
-          }
-        case tp1 =>
-          mapOver(tp1)
-      }
-    }
-  }
 
-  /** Type with all top-level occurrences of abstract types replaced by their bounds */
-  object abstractTypesToBounds extends TypeMap {
-    def apply(tp: Type): Type = tp match {
-      case TypeRef(_, sym, _) if sym.isAliasType    => apply(tp.dealias)
-      case TypeRef(_, sym, _) if sym.isAbstractType => apply(tp.bounds.hi)
-      case rtp @ RefinedType(parents, decls)        => copyRefinedType(rtp, parents mapConserve this, decls)
-      case AnnotatedType(_, _, _)                   => mapOver(tp)
-      case _                                        => tp             // no recursion - top level only
-    }
-  }
-
-  // Set to true for A* => Seq[A]
-  //   (And it will only rewrite A* in method result types.)
-  //   This is the pre-existing behavior.
-  // Or false for Seq[A] => Seq[A]
-  //   (It will rewrite A* everywhere but method parameters.)
-  //   This is the specified behavior.
-  protected def etaExpandKeepsStar = false
-
-  /** Turn any T* types into Seq[T] except when
-   *  in method parameter position.
-   */
-  object dropIllegalStarTypes extends TypeMap {
-    def apply(tp: Type): Type = tp match {
-      case MethodType(params, restpe) =>
-        // Not mapping over params
-        val restpe1 = apply(restpe)
-        if (restpe eq restpe1) tp
-        else MethodType(params, restpe1)
-      case TypeRef(_, RepeatedParamClass, arg :: Nil) =>
-        seqType(arg)
-      case _ =>
-        if (etaExpandKeepsStar) tp else mapOver(tp)
-    }
-  }
 
 // Hash consing --------------------------------------------------------------
 
@@ -3817,121 +3682,6 @@ trait Types extends api.Types { self: SymbolTable =>
 
 // 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, avoidWidening0: Boolean = false) {
-    def this(lo0: List[Type], hi0: List[Type]) = this(lo0, hi0, NoType, NoType)
-    def this(bounds: TypeBounds) = this(List(bounds.lo), List(bounds.hi))
-    def this() = this(List(), List())
-
-    /*  Syncnote: Type constraints are assumed to be used from only one
-     *  thread. They are not exposed in api.Types and are used only locally
-     *  in operations that are exposed from types. Hence, no syncing of any
-     *  variables should be ncessesary.
-     */
-
-    /** Guard these lists against AnyClass and NothingClass appearing,
-     *  else loBounds.isEmpty will have different results for an empty
-     *  constraint and one with Nothing as a lower bound.  [Actually
-     *  guarding addLoBound/addHiBound somehow broke raw types so it
-     *  only guards against being created with them.]
-     */
-    private var lobounds = lo0 filterNot typeIsNothing
-    private var hibounds = hi0 filterNot typeIsAny
-    private var numlo = numlo0
-    private var numhi = numhi0
-    private var avoidWidening = avoidWidening0
-
-    def loBounds: List[Type] = if (numlo == NoType) lobounds else numlo :: lobounds
-    def hiBounds: List[Type] = if (numhi == NoType) hibounds else numhi :: hibounds
-    def avoidWiden: Boolean = avoidWidening
-
-    def addLoBound(tp: Type, isNumericBound: Boolean = false) {
-      // For some reason which is still a bit fuzzy, we must let Nothing through as
-      // a lower bound despite the fact that Nothing is always a lower bound.  My current
-      // supposition is that the side-effecting type constraint accumulation mechanism
-      // depends on these subtype tests being performed to make forward progress when
-      // there are mutally recursive type vars.
-      // See pos/t6367 and pos/t6499 for the competing test cases.
-      val mustConsider = tp.typeSymbol match {
-        case NothingClass => true
-        case _            => !(lobounds contains tp)
-      }
-      if (mustConsider) {
-        if (isNumericBound && isNumericValueType(tp)) {
-          if (numlo == NoType || isNumericSubType(numlo, tp))
-            numlo = tp
-          else if (!isNumericSubType(tp, numlo))
-            numlo = numericLoBound
-        }
-        else lobounds ::= tp
-      }
-    }
-
-    def checkWidening(tp: Type) {
-      if(tp.isStable) avoidWidening = true
-      else tp match {
-        case HasTypeMember(_, _) => avoidWidening = true
-        case _ =>
-      }
-    }
-
-    def addHiBound(tp: Type, isNumericBound: Boolean = false) {
-      // My current test case only demonstrates the need to let Nothing through as
-      // a lower bound, but I suspect the situation is symmetrical.
-      val mustConsider = tp.typeSymbol match {
-        case AnyClass => true
-        case _        => !(hibounds contains tp)
-      }
-      if (mustConsider) {
-        checkWidening(tp)
-        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, avoidWidening)
-      tc.inst = inst
-      tc
-    }
-
-    override def toString = {
-      val boundsStr = {
-        val lo    = loBounds filterNot typeIsNothing
-        val hi    = hiBounds filterNot typeIsAny
-        val lostr = if (lo.isEmpty) Nil else List(lo.mkString(" >: (", ", ", ")"))
-        val histr = if (hi.isEmpty) Nil else List(hi.mkString(" <: (", ", ", ")"))
-
-        lostr ++ histr mkString ("[", " | ", "]")
-      }
-      if (inst eq NoType) boundsStr
-      else boundsStr + " _= " + inst.safeToString
-    }
-  }
-
   class TypeUnwrapper(poly: Boolean, existential: Boolean, annotated: Boolean, nullary: Boolean) extends (Type => Type) {
     def apply(tp: Type): Type = tp match {
       case AnnotatedType(_, underlying, _) if annotated   => apply(underlying)
@@ -3949,246 +3699,6 @@ trait Types extends api.Types { self: SymbolTable =>
   object  unwrapToStableClass extends ClassUnwrapper(existential = false) { }
   object   unwrapWrapperTypes extends  TypeUnwrapper(true, true, true, true) { }
 
-  trait AnnotationFilter extends TypeMap {
-    def keepAnnotation(annot: AnnotationInfo): Boolean
-
-    override def mapOver(annot: AnnotationInfo) =
-      if (keepAnnotation(annot)) super.mapOver(annot)
-      else UnmappableAnnotation
-  }
-
-  trait KeepOnlyTypeConstraints extends AnnotationFilter {
-    // filter keeps only type constraint annotations
-    def keepAnnotation(annot: AnnotationInfo) = annot matches TypeConstraintClass
-  }
-
-  // todo. move these into scala.reflect.api
-
-  /** A prototype for mapping a function over all possible types
-   */
-  abstract class TypeMap(trackVariance: Boolean) extends (Type => Type) {
-    def this() = this(trackVariance = false)
-    def apply(tp: Type): Type
-
-    private[this] var _variance: Variance = if (trackVariance) Covariant else Invariant
-
-    def variance_=(x: Variance) = { assert(trackVariance, this) ; _variance = x }
-    def variance = _variance
-
-    /** Map this function over given type */
-    def mapOver(tp: Type): Type = tp match {
-      case tr @ TypeRef(pre, sym, args) =>
-        val pre1 = this(pre)
-        val args1 = (
-          if (trackVariance && args.nonEmpty && !variance.isInvariant && sym.typeParams.nonEmpty)
-            mapOverArgs(args, sym.typeParams)
-          else
-            args mapConserve this
-        )
-        if ((pre1 eq pre) && (args1 eq args)) tp
-        else copyTypeRef(tp, pre1, tr.coevolveSym(pre1), 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) =>
-        val params1 = flipped(mapOver(params))
-        val result1 = this(result)
-        if ((params1 eq params) && (result1 eq result)) tp
-        else copyMethodType(tp, params1, result1.substSym(params, params1))
-      case PolyType(tparams, result) =>
-        val tparams1 = flipped(mapOver(tparams))
-        val 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) =>
-        val lo1 = flipped(this(lo))
-        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)
-        copyRefinedType(rtp, parents1, decls1)
-      case ExistentialType(tparams, result) =>
-        val tparams1 = mapOver(tparams)
-        val result1 = this(result)
-        if ((tparams1 eq tparams) && (result1 eq result)) tp
-        else newExistentialType(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 ErasedSingleType(sym) => tp
-*/
-      case _ =>
-        tp
-        // throw new Error("mapOver inapplicable for " + tp);
-    }
-
-    def withVariance[T](v: Variance)(body: => T): T = {
-      val saved = variance
-      variance = v
-      try body finally variance = saved
-    }
-    @inline final def flipped[T](body: => T): T = {
-      if (trackVariance) variance = variance.flip
-      try body
-      finally if (trackVariance) variance = variance.flip
-    }
-    protected def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] = (
-      if (trackVariance)
-        map2Conserve(args, tparams)((arg, tparam) => withVariance(variance * tparam.variance)(this(arg)))
-      else
-        args mapConserve this
-    )
-    /** Applies this map to the symbol's info, setting variance = Invariant
-     *  if necessary when the symbol is an alias.
-     */
-    private def applyToSymbolInfo(sym: Symbol): Type = {
-      if (trackVariance && !variance.isInvariant && sym.isAliasType)
-        withVariance(Invariant)(this(sym.info))
-      else
-        this(sym.info)
-    }
-
-    /** Called by mapOver to determine whether the original symbols can
-     *  be returned, or whether they must be cloned.
-     */
-    protected def noChangeToSymbols(origSyms: List[Symbol]): Boolean = {
-      @tailrec def loop(syms: List[Symbol]): Boolean = syms match {
-        case Nil     => true
-        case x :: xs => (x.info eq applyToSymbolInfo(x)) && loop(xs)
-      }
-      loop(origSyms)
-    }
-
-    /** 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 newScopeWith(elems1: _*)
-    }
-
-    /** Map this function over given list of symbols */
-    def mapOver(origSyms: List[Symbol]): List[Symbol] = {
-      // fast path in case nothing changes due to map
-      if (noChangeToSymbols(origSyms)) origSyms
-      // map is not the identity --> do cloning properly
-      else cloneSymbolsAndModify(origSyms, TypeMap.this)
-    }
-
-    def mapOver(annot: AnnotationInfo): AnnotationInfo = {
-      val AnnotationInfo(atp, args, assocs) = annot
-      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)) annot
-      else if (args1.isEmpty && args.nonEmpty) UnmappableAnnotation  // some annotation arg was unmappable
-      else AnnotationInfo(atp1, args1, assocs) setPos annot.pos
-    }
-
-    def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = {
-      val annots1 = annots mapConserve mapOver
-      if (annots1 eq annots) annots
-      else annots1 filterNot (_ eq UnmappableAnnotation)
-    }
-
-    /** 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 mapConserve mapOver
-      if (args1 contains UnmappableTree) Nil
-      else args1
-    }
-
-    def mapOver(tree: Tree): Tree =
-      mapOver(tree, () => return UnmappableTree)
-
-    /** 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)
-      }
-    }
-  }
-
-  abstract class TypeTraverser extends TypeMap {
-    def traverse(tp: Type): Unit
-    def apply(tp: Type): Type = { traverse(tp); tp }
-  }
-
-  abstract class TypeTraverserWithResult[T] extends TypeTraverser {
-    def result: T
-    def clear(): Unit
-  }
-
-  abstract class TypeCollector[T](initial: T) extends TypeTraverser {
-    var result: T = _
-    def collect(tp: Type) = {
-      result = initial
-      traverse(tp)
-      result
-    }
-  }
-
   /** Repack existential types, otherwise they sometimes get unpacked in the
    *  wrong location (type inference comes up with an unexpected skolem)
    */
@@ -4234,707 +3744,8 @@ trait Types extends api.Types { self: SymbolTable =>
     && isRawIfWithoutArgs(sym)
   )
 
-  /** 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).
-   */
-  def rawToExistential = new TypeMap {
-    private var expanded = immutable.Set[Symbol]()
-    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))
-          existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe)))
-        } finally {
-          expanded -= sym
-        }
-      case _ =>
-        mapOver(tp)
-    }
-  }
-  /***
-   *@M: I think this is more desirable, but Martin prefers to leave raw-types as-is as much as possible
-    object rawToExistentialInJava extends TypeMap {
-      def apply(tp: Type): Type = tp match {
-        // any symbol that occurs in a java sig, not just java symbols
-        // see http://lampsvn.epfl.ch/trac/scala/ticket/2454#comment:14
-        case TypeRef(pre, sym, List()) if !sym.typeParams.isEmpty =>
-          val eparams = typeParamsToExistentials(sym, sym.typeParams)
-          existentialAbstraction(eparams, TypeRef(pre, sym, eparams map (_.tpe)))
-        case _ =>
-          mapOver(tp)
-      }
-    }
-  */
-
-  /** Used by existentialAbstraction.
-   */
-  class ExistentialExtrapolation(tparams: List[Symbol]) extends TypeMap(trackVariance = true) {
-    private val occurCount = mutable.HashMap[Symbol, Int]()
-    private def countOccs(tp: Type) = {
-      tp foreach {
-        case TypeRef(_, sym, _) =>
-          if (tparams contains sym)
-            occurCount(sym) += 1
-        case _ => ()
-      }
-    }
-    def extrapolate(tpe: Type): Type = {
-      tparams foreach (t => occurCount(t) = 0)
-      countOccs(tpe)
-      for (tparam <- tparams)
-        countOccs(tparam.info)
-
-      apply(tpe)
-    }
-
-    /** If these conditions all hold:
-     *   1) we are in covariant (or contravariant) position
-     *   2) this type occurs exactly once in the existential scope
-     *   3) the widened upper (or lower) bound of this type contains no references to tparams
-     *  Then we replace this lone occurrence of the type with the widened upper (or lower) bound.
-     *  All other types pass through unchanged.
-     */
-    def apply(tp: Type): Type = {
-      val tp1 = mapOver(tp)
-      if (variance.isInvariant) tp1
-      else tp1 match {
-        case TypeRef(pre, sym, args) if tparams contains sym =>
-          val repl = if (variance.isPositive) dropSingletonType(tp1.bounds.hi) else tp1.bounds.lo
-          val count = occurCount(sym)
-          val containsTypeParam = tparams exists (repl contains _)
-          def msg = {
-            val word = if (variance.isPositive) "upper" else "lower"
-            s"Widened lone occurrence of $tp1 inside existential to $word bound"
-          }
-          if (!repl.typeSymbol.isBottomClass && count == 1 && !containsTypeParam)
-            logResult(msg)(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)
-    }
-
-    // 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.
-    override def mapOver(tree: Tree) = tree match {
-      case Ident(_) if tree.tpe.isStable => tree
-      case _                             => super.mapOver(tree)
-    }
-  }
-
   def singletonBounds(hi: Type) = TypeBounds.upper(intersectionType(List(hi, SingletonClass.tpe)))
 
-  /** Might the given symbol be important when calculating the prefix
-   *  of a type? When tp.asSeenFrom(pre, clazz) is called on `tp`,
-   *  the result will be `tp` unchanged if `pre` is trivial and `clazz`
-   *  is a symbol such that isPossiblePrefix(clazz) == false.
-   */
-  def isPossiblePrefix(clazz: Symbol) = clazz.isClass && !clazz.isPackageClass
-
-  private def skipPrefixOf(pre: Type, clazz: Symbol) = (
-    (pre eq NoType) || (pre eq NoPrefix) || !isPossiblePrefix(clazz)
-  )
-
-  def newAsSeenFromMap(pre: Type, clazz: Symbol): AsSeenFromMap =
-    new AsSeenFromMap(pre, clazz)
-
-  /** A map to compute the asSeenFrom method.
-   */
-  class AsSeenFromMap(seenFromPrefix: Type, seenFromClass: Symbol) extends TypeMap with KeepOnlyTypeConstraints {
-    // Some example source constructs relevant in asSeenFrom:
-    //
-    // object CaptureThis {
-    //   trait X[A] { def f: this.type = this }
-    //   class Y[A] { def f: this.type = this }
-    //   // Created new existential to represent This(CaptureThis.X) seen from CaptureThis.X[B]: type _1.type <: CaptureThis.X[B] with Singleton
-    //   def f1[B] = new X[B] { }
-    //   // TODO - why is the behavior different when it's a class?
-    //   def f2[B] = new Y[B] { }
-    // }
-    // class CaptureVal[T] {
-    //   val f: java.util.List[_ <: T] = null
-    //   // Captured existential skolem for type _$1 seen from CaptureVal.this.f.type: type _$1
-    //   def g = f get 0
-    // }
-    // class ClassParam[T] {
-    //   // AsSeenFromMap(Inner.this.type, class Inner)/classParameterAsSeen(T)#loop(ClassParam.this.type, class ClassParam)
-    //   class Inner(lhs: T) { def f = lhs }
-    // }
-    def capturedParams: List[Symbol]  = _capturedParams
-    def capturedSkolems: List[Symbol] = _capturedSkolems
-
-    def apply(tp: Type): Type = tp match {
-      case tp @ ThisType(_)                                            => thisTypeAsSeen(tp)
-      case tp @ SingleType(_, sym)                                     => if (sym.isPackageClass) tp else singleTypeAsSeen(tp)
-      case tp @ TypeRef(_, sym, _) if isTypeParamOfEnclosingClass(sym) => classParameterAsSeen(tp)
-      case _                                                           => mapOver(tp)
-    }
-
-    private var _capturedSkolems: List[Symbol] = Nil
-    private var _capturedParams: List[Symbol]  = Nil
-    private val isStablePrefix = seenFromPrefix.isStable
-
-    // isBaseClassOfEnclosingClassOrInfoIsNotYetComplete would be a more accurate
-    // but less succinct name.
-    private def isBaseClassOfEnclosingClass(base: Symbol) = {
-      def loop(encl: Symbol): Boolean = (
-           isPossiblePrefix(encl)
-        && ((encl isSubClass base) || loop(encl.owner.enclClass))
-      )
-      // The hasCompleteInfo guard is necessary to avoid cycles during the typing
-      // of certain classes, notably ones defined inside package objects.
-      !base.hasCompleteInfo || loop(seenFromClass)
-    }
-
-    /** Is the symbol a class type parameter from one of the enclosing
-     *  classes, or a base class of one of them?
-     */
-    private def isTypeParamOfEnclosingClass(sym: Symbol): Boolean = (
-         sym.isTypeParameter
-      && sym.owner.isClass
-      && isBaseClassOfEnclosingClass(sym.owner)
-    )
-
-    /** Creates an existential representing a type parameter which appears
-     *  in the prefix of a ThisType.
-     */
-    protected def captureThis(pre: Type, clazz: Symbol): Type = {
-      capturedParams find (_.owner == clazz) match {
-        case Some(p) => p.tpe
-        case _       =>
-          val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre)
-          _capturedParams ::= qvar
-          debuglog(s"Captured This(${clazz.fullNameString}) seen from $seenFromPrefix: ${qvar.defString}")
-          qvar.tpe
-      }
-    }
-    protected def captureSkolems(skolems: List[Symbol]) {
-      for (p <- skolems; if !(capturedSkolems contains p)) {
-        debuglog(s"Captured $p seen from $seenFromPrefix")
-        _capturedSkolems ::= p
-      }
-    }
-
-    /** Find the type argument in an applied type which corresponds to a type parameter.
-     *  The arguments are required to be related as follows, through intermediary `clazz`.
-     *  An exception will be thrown if this is violated.
-     *
-     *  @param   lhs    its symbol is a type parameter of `clazz`
-     *  @param   rhs    a type application constructed from `clazz`
-     */
-    private def correspondingTypeArgument(lhs: Type, rhs: Type): Type = {
-      val TypeRef(_, lhsSym, lhsArgs) = lhs
-      val TypeRef(_, rhsSym, rhsArgs) = rhs
-      require(lhsSym.safeOwner == rhsSym, s"$lhsSym is not a type parameter of $rhsSym")
-
-      // Find the type parameter position; we'll use the corresponding argument
-      val argIndex = rhsSym.typeParams indexOf lhsSym
-
-      if (argIndex >= 0 && argIndex < rhsArgs.length)             // @M! don't just replace the whole thing, might be followed by type application
-        appliedType(rhsArgs(argIndex), lhsArgs mapConserve this)
-      else if (rhsSym.tpe_*.parents exists typeIsErroneous)        // don't be too zealous with the exceptions, see #2641
-        ErrorType
-      else
-        abort(s"something is wrong: cannot make sense of type application\n  $lhs\n  $rhs")
-    }
-
-    // 0) @pre: `classParam` is a class type parameter
-    // 1) Walk the owner chain of `seenFromClass` until we find the class which owns `classParam`
-    // 2) Take the base type of the prefix at that point with respect to the owning class
-    // 3) Solve for the type parameters through correspondence with the type args of the base type
-    //
-    // Only class type parameters (and not skolems) are considered, because other type parameters
-    // are not influenced by the prefix through which they are seen. Note that 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.
-    private def classParameterAsSeen(classParam: Type): Type = {
-      val TypeRef(_, tparam, _) = classParam
-
-      def loop(pre: Type, clazz: Symbol): Type = {
-        // have to deconst because it may be a Class[T]
-        def nextBase = (pre baseType clazz).deconst
-        //@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary
-        if (skipPrefixOf(pre, clazz))
-          mapOver(classParam)
-        else if (!matchesPrefixAndClass(pre, clazz)(tparam.owner))
-          loop(nextBase.prefix, clazz.owner)
-        else nextBase match {
-          case applied @ TypeRef(_, _, _)     => correspondingTypeArgument(classParam, applied)
-          case ExistentialType(eparams, qtpe) => captureSkolems(eparams) ; loop(qtpe, clazz)
-          case t                              => abort(s"$tparam in ${tparam.owner} cannot be instantiated from ${seenFromPrefix.widen}")
-        }
-      }
-      loop(seenFromPrefix, seenFromClass)
-    }
-
-    // Does the candidate symbol match the given prefix and class?
-    // Since pre may be something like ThisType(A) where trait A { self: B => },
-    // we have to test the typeSymbol of the widened type, not pre.typeSymbol, or
-    // B will not be considered.
-    private def matchesPrefixAndClass(pre: Type, clazz: Symbol)(candidate: Symbol) = pre.widen match {
-      case _: TypeVar => false
-      case wide       => (clazz == candidate) && (wide.typeSymbol isSubClass clazz)
-    }
-
-    // Whether the annotation tree currently being mapped over has had a This(_) node rewritten.
-    private[this] var wroteAnnotation = false
-    private object annotationArgRewriter extends TypeMapTransformer {
-      private def matchesThis(thiz: Symbol) = matchesPrefixAndClass(seenFromPrefix, seenFromClass)(thiz)
-
-      // what symbol should really be used?
-      private def newThis(): Tree = {
-        wroteAnnotation = true
-        val presym      = seenFromPrefix.widen.typeSymbol
-        val thisSym     = presym.owner.newValue(presym.name.toTermName, presym.pos) setInfo seenFromPrefix
-        gen.mkAttributedQualifier(seenFromPrefix, thisSym)
-      }
-
-      /** Rewrite `This` trees in annotation argument trees */
-      override def transform(tree: Tree): Tree = super.transform(tree) match {
-        case This(_) if matchesThis(tree.symbol) => newThis()
-        case tree                                => tree
-      }
-    }
-
-    // This becomes considerably cheaper if we optimize for the common cases:
-    // where the prefix is stable and where no This nodes are rewritten. If
-    // either is true, then we don't need to worry about calling giveup. So if
-    // the prefix is unstable, use a stack variable to indicate whether the tree
-    // was touched. This takes us to one allocation per AsSeenFromMap rather
-    // than an allocation on every call to mapOver, and no extra work when the
-    // tree only has its types remapped.
-    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
-      if (isStablePrefix)
-        annotationArgRewriter transform tree
-      else {
-        val saved = wroteAnnotation
-        wroteAnnotation = false
-        try annotationArgRewriter transform tree
-        finally if (wroteAnnotation) giveup() else wroteAnnotation = saved
-      }
-    }
-
-    private def thisTypeAsSeen(tp: ThisType): Type = {
-      def loop(pre: Type, clazz: Symbol): Type = {
-        val pre1 = pre match {
-          case SuperType(thistpe, _) => thistpe
-          case _                     => pre
-        }
-        if (skipPrefixOf(pre, clazz))
-          mapOver(tp) // TODO - is mapOver necessary here?
-        else if (!matchesPrefixAndClass(pre, clazz)(tp.sym))
-          loop((pre baseType clazz).prefix, clazz.owner)
-        else if (pre1.isStable)
-          pre1
-        else
-          captureThis(pre1, clazz)
-      }
-      loop(seenFromPrefix, seenFromClass)
-    }
-
-    private def singleTypeAsSeen(tp: SingleType): Type = {
-      val SingleType(pre, sym) = tp
-
-      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
-    }
-
-    override def toString = s"AsSeenFromMap($seenFromPrefix, $seenFromClass)"
-  }
-
-  /** A base class to compute all substitutions */
-  abstract class SubstMap[T](from: List[Symbol], to: List[T]) extends TypeMap {
-    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) =>
-        createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, renameBoundSyms(tp1)))
-      case PolyType(bs, restp) =>
-        createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1)))
-      case ExistentialType(bs, restp) =>
-        createFromClonedSymbols(bs, restp)(newExistentialType)
-      case _ =>
-        tp
-    }
-
-    @tailrec private 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)
-    )
-
-    def apply(tp0: Type): Type = if (from.isEmpty) tp0 else {
-      val boundSyms             = tp0.boundSyms
-      val tp1                   = if (boundSyms.nonEmpty && (boundSyms exists from.contains)) renameBoundSyms(tp0) else tp0
-      val tp                    = mapOver(tp1)
-      def substFor(sym: Symbol) = subst(tp, sym, from, to)
-
-      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) =>
-          val tcon = substFor(sym)
-          if ((tp eq tcon) || args.isEmpty) tcon
-          else appliedType(tcon.typeConstructor, args)
-        case SingleType(NoPrefix, sym) =>
-          substFor(sym)
-        case _ =>
-          tp
-      }
-    }
-  }
-
-  /** A map to implement the `substSym` method. */
-  class SubstSymMap(from: List[Symbol], to: List[Symbol]) extends SubstMap(from, to) {
-    def this(pairs: (Symbol, Symbol)*) = this(pairs.toList.map(_._1), pairs.toList.map(_._2))
-
-    protected def toType(fromtp: Type, sym: Symbol) = fromtp match {
-      case TypeRef(pre, _, args) => copyTypeRef(fromtp, pre, sym, args)
-      case SingleType(pre, _) => singleType(pre, sym)
-    }
-    @tailrec private 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)
-    )
-    private def substFor(sym: Symbol) = subst(sym, from, to)
-
-    override def apply(tp: Type): Type = (
-      if (from.isEmpty) tp
-      else tp match {
-        case TypeRef(pre, sym, args) if pre ne NoPrefix =>
-          val newSym = substFor(sym)
-          // mapOver takes care of subst'ing in args
-          mapOver ( if (sym eq newSym) tp else copyTypeRef(tp, pre, newSym, args) )
-          // assert(newSym.typeParams.length == sym.typeParams.length, "typars mismatch in SubstSymMap: "+(sym, sym.typeParams, newSym, newSym.typeParams))
-        case SingleType(pre, sym) if pre ne NoPrefix =>
-          val newSym = substFor(sym)
-          mapOver( if (sym eq newSym) tp else singleType(pre, newSym) )
-        case _ =>
-          super.apply(tp)
-      }
-    )
-
-    object mapTreeSymbols extends TypeMapTransformer {
-      val strictCopy = newStrictTreeCopier
-
-      def termMapsTo(sym: Symbol) = from indexOf sym match {
-        case -1   => None
-        case idx  => Some(to(idx))
-      }
-
-      // if tree.symbol is mapped to another symbol, passes the new symbol into the
-      // constructor `trans` and sets the symbol and the type on the resulting tree.
-      def transformIfMapped(tree: Tree)(trans: Symbol => Tree) = termMapsTo(tree.symbol) match {
-        case Some(toSym) => trans(toSym) setSymbol toSym setType tree.tpe
-        case None => tree
-      }
-
-      // changes trees which refer to one of the mapped symbols. trees are copied before attributes are modified.
-      override def transform(tree: Tree) = {
-        // super.transform maps symbol references in the types of `tree`. it also copies trees where necessary.
-        super.transform(tree) match {
-          case id @ Ident(_) =>
-            transformIfMapped(id)(toSym =>
-              strictCopy.Ident(id, toSym.name))
-
-          case sel @ Select(qual, name) =>
-            transformIfMapped(sel)(toSym =>
-              strictCopy.Select(sel, qual, toSym.name))
-
-          case tree => tree
-        }
-      }
-    }
-    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
-      mapTreeSymbols.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) =>
-            from indexOf tree.symbol match {
-              case -1   => super.transform(tree)
-              case idx  =>
-                val totpe = to(idx)
-                if (totpe.isStable) tree.duplicate setType totpe
-                else giveup()
-            }
-          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 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)
-  }
-
-  /** Note: This map is needed even for non-dependent method types, despite what the name might imply.
-   */
-  class InstantiateDependentMap(params: List[Symbol], actuals0: List[Type]) extends TypeMap with KeepOnlyTypeConstraints {
-    private val actuals      = actuals0.toIndexedSeq
-    private val existentials = new Array[Symbol](actuals.size)
-    def existentialsNeeded: List[Symbol] = existentials.filter(_ ne null).toList
-
-    private object StableArg {
-      def unapply(param: Symbol) = Arg unapply param map actuals filter (tp =>
-        tp.isStable && (tp.typeSymbol != NothingClass)
-      )
-    }
-    private object Arg {
-      def unapply(param: Symbol) = Some(params indexOf param) filter (_ >= 0)
-    }
-
-    def apply(tp: Type): Type = mapOver(tp) match {
-      // unsound to replace args by unstable actual #3873
-      case SingleType(NoPrefix, StableArg(arg)) => arg
-      // (soundly) expand type alias selections on implicit arguments,
-      // see depmet_implicit_oopsla* test cases -- typically, `param.isImplicit`
-      case tp1 @ TypeRef(SingleType(NoPrefix, Arg(pid)), sym, targs) =>
-        val arg = actuals(pid)
-        val res = typeRef(arg, sym, targs)
-        if (res.typeSymbolDirect.isAliasType) res.dealias else tp1
-      // don't return the original `tp`, which may be different from `tp1`,
-      // due to dropping annotations
-      case tp1 => tp1
-    }
-
-    /* Return the type symbol for referencing a parameter inside the existential quantifier.
-     * (Only needed if the actual is unstable.)
-     */
-    private def existentialFor(pid: Int) = {
-      if (existentials(pid) eq null) {
-        val param = params(pid)
-        existentials(pid) = (
-          param.owner.newExistential(param.name.toTypeName append nme.SINGLETON_SUFFIX, param.pos, param.flags)
-            setInfo singletonBounds(actuals(pid))
-        )
-      }
-      existentials(pid)
-    }
-
-    //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 = {
-      // TODO: this should be simplified; in the stable case, one can
-      // probably just use an Ident to the tree.symbol.
-      //
-      // @PP: That leads to failure here, where stuff no longer has type
-      // 'String @Annot("stuff")' but 'String @Annot(x)'.
-      //
-      //   def m(x: String): String @Annot(x) = x
-      //   val stuff = m("stuff")
-      //
-      // (TODO cont.) Why an existential in the non-stable case?
-      //
-      // @PP: In the following:
-      //
-      //   def m = { val x = "three" ; val y: String @Annot(x) = x; y }
-      //
-      // m is typed as 'String @Annot(x) forSome { val x: String }'.
-      //
-      // Both examples are from run/constrained-types.scala.
-      object treeTrans extends Transformer {
-        override def transform(tree: Tree): Tree = tree.symbol match {
-          case StableArg(actual) =>
-            gen.mkAttributedQualifier(actual, tree.symbol)
-          case Arg(pid) =>
-            val sym = existentialFor(pid)
-            Ident(sym) copyAttrs tree setType typeRef(NoPrefix, sym, Nil)
-          case _ =>
-            super.transform(tree)
-        }
-      }
-      treeTrans transform arg
-    }
-  }
-
-  /** 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(bounds))
-      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
-      }
-      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)
-
-      arg
-    }
-  }
-
-  /** A map to implement the `filter` method. */
-  class FilterTypeCollector(p: Type => Boolean) extends TypeCollector[List[Type]](Nil) {
-    override def collect(tp: Type) = super.collect(tp).reverse
-
-    def traverse(tp: Type) {
-      if (p(tp)) result ::= tp
-      mapOver(tp)
-    }
-  }
-
-  /** A map to implement the `collect` method. */
-  class CollectTypeCollector[T](pf: PartialFunction[Type, T]) extends TypeCollector[List[T]](Nil) {
-    override def collect(tp: Type) = super.collect(tp).reverse
-
-    def traverse(tp: Type) {
-      if (pf.isDefinedAt(tp)) result ::= pf(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 more persistent version of `Type#memberType` which does not require
    * that the symbol is a direct member of the prefix.
@@ -4980,194 +3791,10 @@ trait Types extends api.Types { self: SymbolTable =>
     result
   }
 
-  /** 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 = commonOwner(t :: Nil)
-
-  /** 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 (tps.isEmpty) NoSymbol
-    else {
-      commonOwnerMap.clear()
-      tps foreach (commonOwnerMap traverse _)
-      if (commonOwnerMap.result ne null) commonOwnerMap.result else NoSymbol
-    }
-  }
-
-  protected def commonOwnerMap: CommonOwnerMap = commonOwnerMapObj
-
-  protected class CommonOwnerMap extends TypeTraverserWithResult[Symbol] {
-    var result: Symbol = _
-
-    def clear() { result = null }
-
-    private def register(sym: Symbol) {
-      // First considered type is the trivial result.
-      if ((result eq null) || (sym eq NoSymbol))
-        result = sym
-      else
-        while ((result ne NoSymbol) && (result ne sym) && !(sym isNestedIn result))
-          result = result.owner
-    }
-    def traverse(tp: Type) = tp.normalize match {
-      case ThisType(sym)                => register(sym)
-      case TypeRef(NoPrefix, sym, args) => register(sym.owner) ; args foreach traverse
-      case SingleType(NoPrefix, sym)    => register(sym.owner)
-      case _                            => mapOver(tp)
-    }
-  }
-
-  private lazy val commonOwnerMapObj = new CommonOwnerMap
-
   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.isRootSymbol || (pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass)
-        sym
-      else if (sym.isModuleClass) {
-        val sourceModule1 = adaptToNewRun(pre, sym.sourceModule)
-
-        sourceModule1.moduleClass orElse sourceModule1.initialize.moduleClass orElse {
-          val msg = "Cannot adapt module class; sym = %s, sourceModule = %s, sourceModule.moduleClass = %s => sourceModule1 = %s, sourceModule1.moduleClass = %s"
-          debuglog(msg.format(sym, sym.sourceModule, sym.sourceModule.moduleClass, sourceModule1, sourceModule1.moduleClass))
-          sym
-        }
-      }
-      else {
-        var rebind0 = pre.findMember(sym.name, BRIDGE, 0, stableOnly = true) orElse {
-          if (sym.isAliasType) throw missingAliasException
-          devWarning(s"$pre.$sym no longer exist at phase $phase")
-          throw new MissingTypeControl // For build manager and presentation compiler purposes
-        }
-        /** 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)) {
-          debuglog("ADAPT1 pre = "+pre+", sym = "+sym.fullLocationString+", rebind = "+rebind0.fullLocationString)
-          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)
-          debuglog(
-            "ADAPT2 pre = " + pre +
-            ", bcs.head = " + bcs.head +
-            ", sym = " + sym.fullLocationString +
-            ", rebind = " + rebind0.fullLocationString
-          )
-        }
-        rebind0.suchThat(sym => sym.isType || sym.isStable) orElse {
-          debuglog("" + phase + " " +phase.flatClasses+sym.owner+sym.name+" "+sym.isType)
-          throw new MalformedType(pre, sym.nameString)
-        }
-      }
-    }
-    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)
-          try {
-            val sym1 = adaptToNewRun(pre1, sym)
-            if ((pre1 eq pre) && (sym1 eq sym)) tp
-            else singleType(pre1, sym1)
-          } catch {
-            case _: MissingTypeControl =>
-              tp
-          }
-        }
-      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) {
-              devWarning(s"adapt to new run failed: pre=$pre pre1=$pre1 sym=$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) = (this eq other.asInstanceOf[AnyRef]) || (other match {
-      // suspend TypeVars in types compared by =:=,
-      // since we don't want to mutate them simply to check whether a subtype test is pending
-      // in addition to making subtyping "more correct" for type vars,
-      // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion)
-      // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold)
-      case stp: SubTypePair =>
-        val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t))
-        suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2)
-      case _ =>
-        false
-    })
-    override def toString = tp1+" <:<? "+tp2
-  }
-
 // Helper Methods  -------------------------------------------------------------
 
   /** The maximum allowable depth of lubs or glbs over types `ts`.
@@ -5275,84 +3902,6 @@ trait Types extends api.Types { self: SymbolTable =>
     }
   }
 
-  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 isSubPre(pre1: Type, pre2: Type, sym: Symbol) =
-    if ((pre1 ne pre2) && (pre1 ne NoPrefix) && (pre2 ne NoPrefix) && pre1 <:< pre2) {
-      if (settings.debug.value) println(s"new isSubPre $sym: $pre1 <:< $pre2")
-      true
-    } else
-      false
-
-  private def equalSymsAndPrefixes(sym1: Symbol, pre1: Type, sym2: Symbol, pre2: Type): Boolean =
-    if (sym1 == sym2) sym1.hasPackageFlag || sym1.owner.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 {
-    if (Statistics.canEnable) Statistics.incCounter(sametypeCount)
-    subsametypeRecursions += 1
-    //OPT cutdown on Function0 allocation
-    //was:
-//    undoLog undoUnless {
-//      isSameType1(tp1, tp2)
-//    }
-
-    undoLog.lock()
-    try {
-      val before = undoLog.log
-      var result = false
-      try {
-        result = isSameType1(tp1, tp2)
-      }
-      finally if (!result) undoLog.undoTo(before)
-      result
-    }
-    finally undoLog.unlock()
-  }
-  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
@@ -5368,186 +3917,6 @@ trait Types extends api.Types { self: SymbolTable =>
   }
   */
 
-  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) // !! I do not see how this would be warranted by the spec
-      tp2.typeSymbol.isPackageClass
-    else if (tp2 eq NoPrefix) // !! I do not see how this would be warranted by the spec
-      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 _: SingleType =>
-            return isSameType2(tp2, tp1)  // put singleton type on the left, caught below
-          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 TypeRef(pre2, sym2, Nil) =>
-            if (sym2.isModuleClass && equalSymsAndPrefixes(st1.sym, st1.pre, sym2.sourceModule, pre2)) 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)
-                  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 =>
-            return isSameTypes(mt1.paramTypes, mt2.paramTypes) &&
-              mt1.resultType =:= mt2.resultType.substSym(mt2.params, mt1.params) &&
-              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, typeVarLHS = true)
-      case _ =>
-    }
-    tp2 match {
-      case tv @ TypeVar(_,_) =>
-        return tv.registerTypeEquality(tp1, typeVarLHS = 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 =>
-            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)(_ =:= _)
@@ -5565,64 +3934,9 @@ trait Types extends api.Types { self: SymbolTable =>
    */
   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
-
-    //OPT cutdown on Function0 allocation
-    //was:
-//    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)
-//      }
-//    }
-
-    undoLog.lock()
-    try {
-      val before = undoLog.log
-      var result = false
-
-      try result = { // 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 if (!result) undoLog.undoTo(before)
-
-      result
-    } finally undoLog.unlock()
-  } 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,
@@ -5755,42 +4069,6 @@ trait Types extends api.Types { self: SymbolTable =>
     case _                  => false
   }
 
-  private def isPolySubType(tp1: PolyType, tp2: PolyType): Boolean = {
-    val PolyType(tparams1, res1) = tp1
-    val PolyType(tparams2, res2) = tp2
-
-    sameLength(tparams1, tparams2) && {
-      // fast-path: polymorphic method type -- type params cannot be captured
-      val isMethod = tparams1.head.owner.isMethod
-      //@M for an example of why we need to generate fresh symbols otherwise, see neg/tcpoly_ticket2101.scala
-      val substitutes = if (isMethod) tparams1 else cloneSymbols(tparams1)
-      def sub1(tp: Type) = if (isMethod) tp else tp.substSym(tparams1, substitutes)
-      def sub2(tp: Type) = tp.substSym(tparams2, substitutes)
-      def cmp(p1: Symbol, p2: Symbol) = sub2(p2.info) <:< sub1(p1.info)
-
-      (tparams1 corresponds tparams2)(cmp) && (sub1(res1) <:< sub2(res2))
-    }
-  }
-
-  // @assume tp1.isHigherKinded || tp2.isHigherKinded
-  def isHKSubType(tp1: Type, tp2: Type, depth: Int): Boolean = {
-    def isSub(ntp1: Type, ntp2: Type) = (ntp1.withoutAnnotations, ntp2.withoutAnnotations) match {
-      case (TypeRef(_, AnyClass, _), _)                                     => false                    // avoid some warnings when Nothing/Any are on the other side
-      case (_, TypeRef(_, NothingClass, _))                                 => false
-      case (pt1: PolyType, pt2: PolyType)                                   => isPolySubType(pt1, pt2)  // @assume both .isHigherKinded (both normalized to PolyType)
-      case (_: PolyType, MethodType(ps, _)) if ps exists (_.tpe.isWildcard) => false                    // don't warn on HasMethodMatching on right hand side
-      case _                                                                =>                          // @assume !(both .isHigherKinded) thus cannot be subtypes
-        def tp_s(tp: Type): String = f"$tp%-20s ${util.shortClassOfInstance(tp)}%s"
-        devWarning(s"HK subtype check on $tp1 and $tp2, but both don't normalize to polytypes:\n  tp1=${tp_s(ntp1)}\n  tp2=${tp_s(ntp2)}")
-        false
-    }
-
-    (    tp1.typeSymbol == NothingClass       // @M Nothing is subtype of every well-kinded type
-      || tp2.typeSymbol == AnyClass           // @M Any is supertype of every well-kinded type (@PP: is it? What about continuations plugin?)
-      || isSub(tp1.normalize, tp2.normalize) && annotationsConform(tp1, tp2)  // @M! normalize reduces higher-kinded case to PolyType's
-    )
-  }
-
   def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[Symbol], depth: Int): Boolean = {
     def isSubArg(t1: Type, t2: Type, variance: Variance) = (
          (variance.isContravariant || isSubType(t1, t2, depth))
@@ -5800,205 +4078,7 @@ trait Types extends api.Types { self: SymbolTable =>
     corresponds3(tps1, tps2, tparams map (_.variance))(isSubArg)
   }
 
-  /** 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 // !! I do not see how the "isPackageClass" would be warranted by the spec
-    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 isHKSubType(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 = 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 || sym1.owner.hasPackageFlag || isSubType(pre1, pre2, depth)
-               else (sym1.name == sym2.name && !sym1.isModuleClass && !sym2.isModuleClass &&
-                     (isUnifiable(pre1, pre2) ||
-                      isSameSpecializedSkolem(sym1, sym2, pre1, pre2) ||
-                      sym2.isAbstractType && isSubPre(pre1, pre2, sym2)))) &&
-                    isSubArgs(tr1.args, tr2.args, sym1.typeParams, depth))
-             ||
-             sym2.isClass && {
-               val base = tr1 baseType sym2
-               (base ne tr1) && isSubType(base, tr2, depth)
-             }
-             ||
-             thirdTryRef(tr1, tr2))
-          case _ =>
-            secondTry
-        }
-      case AnnotatedType(_, _, _) =>
-        isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) &&
-        annotationsConform(tp1, tp2)
-      case BoundedWildcardType(bounds) =>
-        isSubType(tp1, bounds.hi, depth)
-      case tv2 @ TypeVar(_, constr2) =>
-        tp1 match {
-          case AnnotatedType(_, _, _) | BoundedWildcardType(_) =>
-            secondTry
-          case _ =>
-            tv2.registerBound(tp1, isLowerBound = true)
-        }
-      case _ =>
-        secondTry
-    }
-
-    /** Second try, on the left:
-     *   - unwrap AnnotatedTypes, BoundedWildcardTypes,
-     *   - bind typevars,
-     *   - handle existential types by skolemization.
-     */
-    def secondTry = tp1 match {
-      case AnnotatedType(_, _, _) =>
-        isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) &&
-        annotationsConform(tp1, tp2)
-      case BoundedWildcardType(bounds) =>
-        isSubType(tp1.bounds.lo, tp2, depth)
-      case tv @ TypeVar(_,_) =>
-        tv.registerBound(tp2, isLowerBound = false)
-      case ExistentialType(_, _) =>
-        try {
-          skolemizationLevel += 1
-          isSubType(tp1.skolemizeExistential, tp2, depth)
-        } finally {
-          skolemizationLevel -= 1
-        }
-      case _ =>
-        thirdTry
-    }
-
-    def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = {
-      val sym2 = tp2.sym
-      sym2 match {
-        case NotNullClass => tp1.isNotNull
-        case SingletonClass => tp1.isStable || fourthTry
-        case _: ClassSymbol =>
-          if (isRawType(tp2))
-            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) &&
-            isSubType(tp1, tp2a, depth) ||
-            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 = tp2 match {
-      case tr2: TypeRef =>
-        thirdTryRef(tp1, tr2)
-      case rt2: RefinedType =>
-        (rt2.parents forall (isSubType(tp1, _, depth))) &&
-        (rt2.decls forall (specializesSym(tp1, _, depth)))
-      case et2: ExistentialType =>
-        et2.withTypeVars(isSubType(tp1, _, depth), depth) || fourthTry
-      case nn2: NotNullType =>
-        tp1.isNotNull && isSubType(tp1, nn2.underlying, depth)
-      case mt2: MethodType =>
-        tp1 match {
-          case mt1 @ MethodType(params1, res1) =>
-            val params2 = mt2.params
-            val res2 = mt2.resultType
-            (sameLength(params1, params2) &&
-             mt1.isImplicit == mt2.isImplicit &&
-             matchingParams(params1, params2, mt1.isJava, mt2.isJava) &&
-             isSubType(res1.substSym(params1, params2), res2, depth))
-          // 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(_) =>
-            isSubType(pt1.resultType, pt2.resultType, depth)
-          case _ =>
-            false
-        }
-      case TypeBounds(lo2, hi2) =>
-        tp1 match {
-          case TypeBounds(lo1, hi1) =>
-            isSubType(lo2, lo1, depth) && isSubType(hi1, hi2, depth)
-          case _ =>
-            false
-        }
-      case _ =>
-        fourthTry
-    }
-
-    /** Fourth try, on the left:
-     *   - handle typerefs, refined types, notnull and singleton types.
-     */
-    def fourthTry = tp1 match {
-      case tr1 @ TypeRef(pre1, sym1, _) =>
-        sym1 match {
-          case NothingClass => true
-          case NullClass =>
-            tp2 match {
-              case TypeRef(_, sym2, _) =>
-                containsNull(sym2)
-              case _ =>
-                isSingleType(tp2) && isSubType(tp1, tp2.widen, depth)
-            }
-          case _: ClassSymbol =>
-            if (isRawType(tp1))
-              isSubType(rawToExistential(tp1), tp2, depth)
-            else if (sym1.isModuleClass) tp2 match {
-              case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1.sourceModule, pre1, sym2, pre2)
-              case _                      => false
-            }
-            else if (sym1.isRefinementClass)
-              isSubType(sym1.info, tp2, depth)
-            else false
-
-          case _: TypeSymbol =>
-            if (sym1 hasFlag DEFERRED) {
-              val tp1a = tp1.bounds.hi
-              isDifferentTypeConstructor(tp1, tp1a) && isSubType(tp1a, tp2, depth)
-            } else {
-              isSubType(tp1.normalize, tp2.normalize, depth)
-            }
-          case _ =>
-            false
-        }
-      case RefinedType(parents1, _) =>
-        parents1 exists (isSubType(_, tp2, depth))
-      case _: SingletonType | _: NotNullType =>
-        isSubType(tp1.underlying, tp2, depth)
-      case _ =>
-        false
-    }
-
-    firstTry
-  }
-
-  private def containsNull(sym: Symbol): Boolean =
+  protected[internal] def containsNull(sym: Symbol): Boolean =
     sym.isClass && sym != NothingClass &&
     !(sym isNonBottomSubClass AnyValClass) &&
     !(sym isNonBottomSubClass NotNullClass)
@@ -6020,7 +4100,7 @@ trait Types extends api.Types { self: SymbolTable =>
   /** 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, depth: Int): Boolean = {
+  protected[internal] def specializesSym(tp1: Type, sym1: Symbol, tp2: Type, sym2: Symbol, depth: Int): Boolean = {
     require((sym1 ne NoSymbol) && (sym2 ne NoSymbol), ((tp1, sym1, tp2, sym2, depth)))
     val info1 = tp1.memberInfo(sym1)
     val info2 = tp2.memberInfo(sym2).substThis(tp2.typeSymbol, tp1)
@@ -6154,7 +4234,7 @@ trait Types extends api.Types { self: SymbolTable =>
 */
 
   /** 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 {
+  protected[internal] def matchingParams(syms1: List[Symbol], syms2: List[Symbol], syms1isJava: Boolean, syms2isJava: Boolean): Boolean = syms1 match {
     case Nil =>
       syms2.isEmpty
     case sym1 :: rest1 =>
@@ -6183,87 +4263,6 @@ trait Types extends api.Types { self: SymbolTable =>
       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[Variance], upper: Boolean): Boolean =
-     solve(tvars, tparams, variances, upper, AnyDepth)
-
-  def solve(tvars: List[TypeVar], tparams: List[Symbol],
-            variances: List[Variance], upper: Boolean, depth: Int): Boolean = {
-
-    def solveOne(tvar: TypeVar, tparam: Symbol, variance: Variance) {
-      if (tvar.constr.inst == NoType) {
-        val up = if (variance.isContravariant) !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
-        foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => {
-          val ok = (tparam2 != tparam) && (
-               (bound contains tparam2)
-            ||  up && (tparam2.info.bounds.lo =:= tparam.tpeHK)
-            || !up && (tparam2.info.bounds.hi =:= tparam.tpeHK)
-          )
-          if (ok) {
-            if (tvar2.constr.inst eq null) cyclic = true
-            solveOne(tvar2, tparam2, variance2)
-          }
-        })
-        if (!cyclic) {
-          if (up) {
-            if (bound.typeSymbol != AnyClass) {
-              log(s"$tvar addHiBound $bound.instantiateTypeParams($tparams, $tvars)")
-              tvar addHiBound bound.instantiateTypeParams(tparams, tvars)
-            }
-            for (tparam2 <- tparams)
-              tparam2.info.bounds.lo.dealias match {
-                case TypeRef(_, `tparam`, _) =>
-                  log(s"$tvar addHiBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
-                  tvar addHiBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars)
-                case _ =>
-              }
-          } else {
-            if (bound.typeSymbol != NothingClass && bound.typeSymbol != tparam) {
-              log(s"$tvar addLoBound $bound.instantiateTypeParams($tparams, $tvars)")
-              tvar addLoBound bound.instantiateTypeParams(tparams, tvars)
-            }
-            for (tparam2 <- tparams)
-              tparam2.info.bounds.hi.dealias match {
-                case TypeRef(_, `tparam`, _) =>
-                  log(s"$tvar addLoBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
-                  tvar addLoBound tparam2.tpeHK.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)))
-        val newInst = (
-          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)
-          }
-        )
-        log(s"$tvar setInst $newInst")
-        tvar setInst newInst
-        //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)))
-    foreach3(tvars, tparams, variances)(solveOne)
-    tvars forall (tvar => tvar.constr.isWithinBounds(tvar.constr.inst))
-  }
-
   /** Do type arguments `targs` conform to formal parameters `tparams`?
    */
   def isWithinBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): Boolean = {
@@ -6276,168 +4275,6 @@ trait Types extends api.Types { self: SymbolTable =>
   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 ---------------------------------------------------------
-
-  private def printLubMatrix(btsMap: Map[Type, List[Type]], depth: Int) {
-    import util.TableDef
-    import TableDef.Column
-    def str(tp: Type) = {
-      if (tp == NoType) ""
-      else {
-        val s = ("" + tp).replaceAll("""[\w.]+\.(\w+)""", "$1")
-        if (s.length < 60) s
-        else (s take 57) + "..."
-      }
-    }
-
-    val sorted       = btsMap.toList.sortWith((x, y) => x._1.typeSymbol isLess y._1.typeSymbol)
-    val maxSeqLength = sorted.map(_._2.size).max
-    val padded       = sorted map (_._2.padTo(maxSeqLength, NoType))
-    val transposed   = padded.transpose
-
-    val columns: List[Column[List[Type]]] = mapWithIndex(sorted) {
-      case ((k, v), idx) =>
-        Column(str(k), (xs: List[Type]) => str(xs(idx)), left = true)
-    }
-
-    val tableDef = TableDef(columns: _*)
-    val formatted = tableDef.table(transposed)
-    println("** Depth is " + depth + "\n" + formatted)
-  }
-
-  /** From a list of types, find any which take type parameters
-   *  where the type parameter bounds contain references to other
-   *  any types in the list (including itself.)
-   *
-   *  @return List of symbol pairs holding the recursive type
-   *    parameter and the parameter which references it.
-   */
-  def findRecursiveBounds(ts: List[Type]): List[(Symbol, Symbol)] = {
-    if (ts.isEmpty) Nil
-    else {
-      val sym = ts.head.typeSymbol
-      require(ts.tail forall (_.typeSymbol == sym), ts)
-      for (p <- sym.typeParams ; in <- sym.typeParams ; if in.info.bounds contains p) yield
-        p -> in
-    }
-  }
-
-  /** 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(ts: List[Type], depth: Int): List[Type] = {
-    var lubListDepth = 0
-    // This catches some recursive situations which would otherwise
-    // befuddle us, e.g. pos/hklub0.scala
-    def isHotForTs(xs: List[Type]) = ts exists (_.typeParams == xs.map(_.typeSymbol))
-
-    def elimHigherOrderTypeParam(tp: Type) = tp match {
-      case TypeRef(_, _, args) if args.nonEmpty && isHotForTs(args) =>
-        logResult("Retracting dummies from " + tp + " in lublist")(tp.typeConstructor)
-      case _ => tp
-    }
-    // pretypes is a tail-recursion-preserving accumulator.
-    @annotation.tailrec def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = {
-      lubListDepth += 1
-
-      if (tsBts.isEmpty || (tsBts exists typeListIsEmpty)) pretypes.reverse
-      else if (tsBts.tail.isEmpty) pretypes.reverse ++ tsBts.head
-      else {
-        // 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
-        val ts0     = tsBts map (_.head)
-
-        // Is the frontier made up of types with the same symbol?
-        val isUniformFrontier = (ts0: @unchecked) match {
-          case t :: ts  => ts forall (_.typeSymbol == t.typeSymbol)
-        }
-
-        // Produce a single type for this frontier by merging the prefixes and arguments of those
-        // typerefs that share the same symbol: that symbol is the current maximal symbol for which
-        // the invariant holds, i.e., the one that conveys most information regarding subtyping. Before
-        // merging, strip targs that refer to bound tparams (when we're computing the lub of type
-        // constructors.) Also filter out all types that are a subtype of some other type.
-        if (isUniformFrontier) {
-          val fbounds     = findRecursiveBounds(ts0) map (_._2)
-          val tcLubList   = typeConstructorLubList(ts0)
-          def isRecursive(tp: Type) = tp.typeSymbol.typeParams exists fbounds.contains
-
-          val ts1 = ts0 map { t =>
-            if (isRecursive(t)) {
-              tcLubList map (t baseType _.typeSymbol) find (t => !isRecursive(t)) match {
-                case Some(tp) => logResult(s"Breaking recursion in lublist, substituting weaker type.\n  Was: $t\n  Now")(tp)
-                case _        => t
-              }
-            }
-            else t
-          }
-          val tails = tsBts map (_.tail)
-          mergePrefixAndArgs(elimSub(ts1, depth) map elimHigherOrderTypeParam, Covariant, depth) match {
-            case Some(tp) => loop(tp :: pretypes, tails)
-            case _        => loop(pretypes, tails)
-          }
-        }
-        else {
-          // frontier is not uniform yet, move it beyond the current minimal symbol;
-          // lather, rinSe, repeat
-          val sym    = minSym(ts0)
-          val newtps = tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts)
-          if (printLubs) {
-            val str = (newtps.zipWithIndex map { case (tps, idx) =>
-              tps.map("        " + _ + "\n").mkString("   (" + idx + ")\n", "", "\n")
-            }).mkString("")
-
-            println("Frontier(\n" + str + ")")
-            printLubMatrix((ts zip tsBts).toMap, lubListDepth)
-          }
-
-          loop(pretypes, newtps)
-        }
-      }
-    }
-
-    val initialBTSes = ts map (_.baseTypeSeq.toList)
-    if (printLubs)
-      printLubMatrix((ts zip initialBTSes).toMap, depth)
-
-    loop(Nil, initialBTSes)
-  }
-
-  /** The minimal symbol of a list of types (as determined by `Symbol.isLess`). */
-  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 List(t) => List(t)
-    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)
@@ -6445,406 +4282,6 @@ trait Types extends api.Types { self: SymbolTable =>
       t
   }
 
-  /** 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 List(t) => List(t)
-      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.dealiasWiden))
-      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): Type = tp match {
-      case ExistentialType(_, res) =>
-        res
-      case tv@TypeVar(_, constr) =>
-        if (tv.instValid) stripType(constr.inst)
-        else if (tv.untouchable) tv
-        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 exists typeHasAnnotations)
-      (annotationsLub(lub(ts map (_.withoutAnnotations)), ts), true)
-    else (lub(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 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)
-    }
-
-  /** The isNumericValueType tests appear redundant, but without them
-   *  test/continuations-neg/function3.scala goes into an infinite loop.
-   *  (Even if the calls are to typeSymbolDirect.)
-   */
-  def isNumericSubType(tp1: Type, tp2: Type): Boolean = (
-       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]
-
-  /** Given a list of types, finds all the base classes they have in
-   *  common, then returns a list of type constructors derived directly
-   *  from the symbols (so any more specific type information is ignored.)
-   *  The list is filtered such that every type constructor in the list
-   *  expects the same number of type arguments, which is chosen based
-   *  on the deepest class among the common baseclasses.
-   */
-  def typeConstructorLubList(ts: List[Type]): List[Type] = {
-    val bcs   = ts.flatMap(_.baseClasses).distinct sortWith (_ isLess _)
-    val tcons = bcs filter (clazz => ts forall (_.typeSymbol isSubClass clazz))
-
-    tcons map (_.typeConstructor) match {
-      case Nil      => Nil
-      case t :: ts  => t :: ts.filter(_.typeParams.size == t.typeParams.size)
-    }
-  }
-
-  def lub(ts: List[Type]): Type = ts match {
-    case List() => NothingClass.tpe
-    case List(t) => t
-    case _ =>
-      if (Statistics.canEnable) Statistics.incCounter(lubCount)
-      val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null
-      try {
-        val res = lub(ts, lubDepth(ts))
-        // If the number of unapplied type parameters in all incoming
-        // types is consistent, and the lub does not match that, return
-        // the type constructor of the calculated lub instead.  This
-        // is because lubbing type constructors tends to result in types
-        // which have been applied to dummies or Nothing.
-        ts.map(_.typeParams.size).distinct match {
-          case x :: Nil if res.typeParams.size != x =>
-            logResult(s"Stripping type args from lub because $res is not consistent with $ts")(res.typeConstructor)
-          case _                                    =>
-            res
-        }
-      }
-      finally {
-        lubResults.clear()
-        glbResults.clear()
-        if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
-      }
-  }
-
-  /** The least upper bound wrt <:< of a list of types */
-  private 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 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) =>
-          tparam.cloneSymbol.setInfo(glb(bounds, depth)))
-        PolyType(tparams1, lub0(matchingInstTypes(ts, tparams1)))
-      case ts @ (mt @ MethodType(params, _)) :: rest =>
-        MethodType(params, lub0(matchingRestypes(ts, mt.paramTypes)))
-      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 @ AnnotatedType(annots, tpe, _) :: rest =>
-        annotationsLub(lub0(ts map (_.withoutAnnotations)), ts)
-      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, 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 excludeFromLub(sym: Symbol) = (
-               sym.isClass
-            || sym.isConstructor
-            || !sym.isPublic
-            || isGetClass(sym)
-            || sym.isFinal
-            || narrowts.exists(t => !refines(t, sym))
-          )
-          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 =
-                map2(narrowts, syms)((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.name.toTypeName, proto.pos)
-                  .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, depth)))
-          }
-          // add a refinement symbol for all non-class members of lubBase
-          // which are refined by every type in ts.
-          for (sym <- lubBase.nonPrivateMembers ; if !excludeFromLub(sym)) {
-            try lubsym(sym) andAlso (addMember(lubThisType, lubRefined, _, depth))
-            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 =>
-              isSubType(t, lubRefined, depth) || {
-                if (settings.debug.value || printLubs) {
-                  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
-          }
-        }
-      // dropIllegalStarTypes is a localized fix for SI-6897. We should probably
-      // integrate that transformation at a lower level in master, but lubs are
-      // the likely and maybe only spot they escape, so fixing here for 2.10.1.
-      existentialAbstraction(tparams, dropIllegalStarTypes(lubType))
-    }
-    if (printLubs) {
-      println(indent + "lub of " + ts + " at depth "+depth)//debug
-      indent = indent + "  "
-      assert(indent.length <= 100)
-    }
-    if (Statistics.canEnable) Statistics.incCounter(nestedLubCount)
-    val res = lub0(ts)
-    if (printLubs) {
-      indent = indent stripSuffix "  "
-      println(indent + "lub of " + ts + " is " + res)//debug
-    }
-    if (ts forall typeIsNotNull) 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
-
-  /** The greatest lower bound of a list of types (as determined by `<:<`). */
-  def glb(ts: List[Type]): Type = elimSuper(ts) match {
-    case List() => AnyClass.tpe
-    case List(t) => t
-    case ts0 =>
-      if (Statistics.canEnable) Statistics.incCounter(lubCount)
-      val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null
-      try {
-        glbNorm(ts0, lubDepth(ts0))
-      } finally {
-        lubResults.clear()
-        glbResults.clear()
-        if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
-     }
-  }
-
-  private def glb(ts: List[Type], depth: Int): Type = elimSuper(ts) match {
-    case List() => AnyClass.tpe
-    case List(t) => t
-    case ts0 => glbNorm(ts0, depth)
-  }
-
-  /** The greatest lower bound of a list of types (as determined by `<:<`), which have been normalized
-   *  with regard to `elimSuper`. */
-  protected def glbNorm(ts: List[Type], depth: Int): Type = {
-    def glb0(ts0: List[Type]): Type = ts0 match {
-      case List() => AnyClass.tpe
-      case List(t) => t
-      case ts @ PolyType(tparams, _) :: _ =>
-        val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) =>
-          tparam.cloneSymbol.setInfo(lub(bounds, depth)))
-        PolyType(tparams1, glbNorm(matchingInstTypes(ts, tparams1), depth))
-      case ts @ (mt @ MethodType(params, _)) :: rest =>
-        MethodType(params, glbNorm(matchingRestypes(ts, mt.paramTypes), depth))
-      case ts @ NullaryMethodType(_) :: rest =>
-        NullaryMethodType(glbNorm(matchingRestypes(ts, Nil), depth))
-      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; sym <- ds.iterator)
-                  if (globalGlbDepth < globalGlbLimit && !specializesSym(glbThisType, sym, depth))
-                    try {
-                      addMember(glbThisType, glbRefined, glbsym(sym), depth)
-                    } 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
-
-    if (Statistics.canEnable) Statistics.incCounter(nestedLubCount)
-    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 typeIsNotNull) res.notNull else res
-  }
-
   /** A list of the typevars in a type. */
   def typeVarsInType(tp: Type): List[TypeVar] = {
     var tvs: List[TypeVar] = Nil
@@ -6979,51 +4416,6 @@ trait Types extends api.Types { self: SymbolTable =>
   def inheritsJavaVarArgsMethod(clazz: Symbol) =
     clazz.thisType.baseClasses exists isJavaVarargsAncestor
 
-  /** 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 mt @ MethodType(params1, res) if isSameTypes(mt.paramTypes, pts) =>
-        res
-      case NullaryMethodType(res) if pts.isEmpty =>
-        res
-      case _ =>
-        throw new NoCommonType(tps)
-    }
-
 // Errors and Diagnostics -----------------------------------------------------
 
   /** A throwable signalling a type error */
@@ -7048,7 +4440,7 @@ trait Types extends api.Types { self: SymbolTable =>
   }
 
   /** The current indentation string for traces */
-  private var indent: String = ""
+  protected[internal] var indent: String = ""
 
   /** Perform operation `p` on arguments `tp1`, `arg2` and print trace of computation. */
   protected def explain[T](op: String, p: (Type, T) => Boolean, tp1: Type, arg2: T): Boolean = {
@@ -7114,29 +4506,6 @@ trait Types extends api.Types { self: SymbolTable =>
     "scala.collection.IndexedSeq",
     "scala.collection.Iterator")
 
-
-  /** The maximum number of recursions allowed in toString
-   */
-  final val maxTostringRecursions = 50
-
-  private var tostringRecursions = 0
-
-  protected def typeToString(tpe: Type): String =
-    if (tostringRecursions >= maxTostringRecursions) {
-      devWarning("Exceeded recursion depth attempting to print " + util.shortClassOfInstance(tpe))
-      if (settings.debug.value)
-        (new Throwable).printStackTrace
-
-      "..."
-    }
-    else
-      try {
-        tostringRecursions += 1
-        tpe.safeToString
-      } finally {
-        tostringRecursions -= 1
-      }
-
 // ----- Hoisted closures and convenience methods, for compile time reductions -------
 
   private[scala] val typeIsNotNull = (tp: Type) => tp.isNotNull
diff --git a/src/reflect/scala/reflect/internal/tpe/CommonOwners.scala b/src/reflect/scala/reflect/internal/tpe/CommonOwners.scala
new file mode 100644
index 0000000000..e5ddd8f359
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/tpe/CommonOwners.scala
@@ -0,0 +1,50 @@
+package scala.reflect
+package internal
+package tpe
+
+private[internal] trait CommonOwners {
+  self: SymbolTable =>
+
+  /** The most deeply nested owner that contains all the symbols
+    *  of thistype or prefixless typerefs/singletype occurrences in given type.
+    */
+  protected[internal] def commonOwner(t: Type): Symbol = commonOwner(t :: Nil)
+
+  /** The most deeply nested owner that contains all the symbols
+    *  of thistype or prefixless typerefs/singletype occurrences in given list
+    *  of types.
+    */
+  protected[internal] def commonOwner(tps: List[Type]): Symbol = {
+    if (tps.isEmpty) NoSymbol
+    else {
+      commonOwnerMap.clear()
+      tps foreach (commonOwnerMap traverse _)
+      if (commonOwnerMap.result ne null) commonOwnerMap.result else NoSymbol
+    }
+  }
+
+  protected def commonOwnerMap: CommonOwnerMap = commonOwnerMapObj
+
+  protected class CommonOwnerMap extends TypeTraverserWithResult[Symbol] {
+    var result: Symbol = _
+
+    def clear() { result = null }
+
+    private def register(sym: Symbol) {
+      // First considered type is the trivial result.
+      if ((result eq null) || (sym eq NoSymbol))
+        result = sym
+      else
+        while ((result ne NoSymbol) && (result ne sym) && !(sym isNestedIn result))
+          result = result.owner
+    }
+    def traverse(tp: Type) = tp.normalize match {
+      case ThisType(sym)                => register(sym)
+      case TypeRef(NoPrefix, sym, args) => register(sym.owner) ; args foreach traverse
+      case SingleType(NoPrefix, sym)    => register(sym.owner)
+      case _                            => mapOver(tp)
+    }
+  }
+
+  private lazy val commonOwnerMapObj = new CommonOwnerMap
+}
diff --git a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
new file mode 100644
index 0000000000..bdccc75d6d
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
@@ -0,0 +1,592 @@
+package scala.reflect
+package internal
+package tpe
+
+import scala.collection.{ mutable }
+import util.Statistics
+import Variance._
+
+private[internal] trait GlbLubs {
+  self: SymbolTable =>
+  import definitions._
+  import TypesStats._
+
+  private final val printLubs = sys.props contains "scalac.debug.lub"
+
+  /** In case anyone wants to turn off lub verification without reverting anything. */
+  private final val verifyLubs = true
+
+
+  private def printLubMatrix(btsMap: Map[Type, List[Type]], depth: Int) {
+    import util.TableDef
+    import TableDef.Column
+    def str(tp: Type) = {
+      if (tp == NoType) ""
+      else {
+        val s = ("" + tp).replaceAll("""[\w.]+\.(\w+)""", "$1")
+        if (s.length < 60) s
+        else (s take 57) + "..."
+      }
+    }
+
+    val sorted       = btsMap.toList.sortWith((x, y) => x._1.typeSymbol isLess y._1.typeSymbol)
+    val maxSeqLength = sorted.map(_._2.size).max
+    val padded       = sorted map (_._2.padTo(maxSeqLength, NoType))
+    val transposed   = padded.transpose
+
+    val columns: List[Column[List[Type]]] = mapWithIndex(sorted) {
+      case ((k, v), idx) =>
+        Column(str(k), (xs: List[Type]) => str(xs(idx)), left = true)
+    }
+
+    val tableDef = TableDef(columns: _*)
+    val formatted = tableDef.table(transposed)
+    println("** Depth is " + depth + "\n" + formatted)
+  }
+
+  /** From a list of types, find any which take type parameters
+    *  where the type parameter bounds contain references to other
+    *  any types in the list (including itself.)
+    *
+    *  @return List of symbol pairs holding the recursive type
+    *    parameter and the parameter which references it.
+    */
+  def findRecursiveBounds(ts: List[Type]): List[(Symbol, Symbol)] = {
+    if (ts.isEmpty) Nil
+    else {
+      val sym = ts.head.typeSymbol
+      require(ts.tail forall (_.typeSymbol == sym), ts)
+      for (p <- sym.typeParams ; in <- sym.typeParams ; if in.info.bounds contains p) yield
+        p -> in
+    }
+  }
+
+  /** 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.
+    */
+  def lubList(ts: List[Type], depth: Int): List[Type] = {
+    var lubListDepth = 0
+    // This catches some recursive situations which would otherwise
+    // befuddle us, e.g. pos/hklub0.scala
+    def isHotForTs(xs: List[Type]) = ts exists (_.typeParams == xs.map(_.typeSymbol))
+
+    def elimHigherOrderTypeParam(tp: Type) = tp match {
+      case TypeRef(_, _, args) if args.nonEmpty && isHotForTs(args) =>
+        logResult("Retracting dummies from " + tp + " in lublist")(tp.typeConstructor)
+      case _ => tp
+    }
+    // pretypes is a tail-recursion-preserving accumulator.
+    @annotation.tailrec def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = {
+      lubListDepth += 1
+
+      if (tsBts.isEmpty || (tsBts exists typeListIsEmpty)) pretypes.reverse
+      else if (tsBts.tail.isEmpty) pretypes.reverse ++ tsBts.head
+      else {
+        // 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
+        val ts0     = tsBts map (_.head)
+
+        // Is the frontier made up of types with the same symbol?
+        val isUniformFrontier = (ts0: @unchecked) match {
+          case t :: ts  => ts forall (_.typeSymbol == t.typeSymbol)
+        }
+
+        // Produce a single type for this frontier by merging the prefixes and arguments of those
+        // typerefs that share the same symbol: that symbol is the current maximal symbol for which
+        // the invariant holds, i.e., the one that conveys most information regarding subtyping. Before
+        // merging, strip targs that refer to bound tparams (when we're computing the lub of type
+        // constructors.) Also filter out all types that are a subtype of some other type.
+        if (isUniformFrontier) {
+          val fbounds     = findRecursiveBounds(ts0) map (_._2)
+          val tcLubList   = typeConstructorLubList(ts0)
+          def isRecursive(tp: Type) = tp.typeSymbol.typeParams exists fbounds.contains
+
+          val ts1 = ts0 map { t =>
+            if (isRecursive(t)) {
+              tcLubList map (t baseType _.typeSymbol) find (t => !isRecursive(t)) match {
+                case Some(tp) => logResult(s"Breaking recursion in lublist, substituting weaker type.\n  Was: $t\n  Now")(tp)
+                case _        => t
+              }
+            }
+            else t
+          }
+          val tails = tsBts map (_.tail)
+          mergePrefixAndArgs(elimSub(ts1, depth) map elimHigherOrderTypeParam, Covariant, depth) match {
+            case Some(tp) => loop(tp :: pretypes, tails)
+            case _        => loop(pretypes, tails)
+          }
+        }
+        else {
+          // frontier is not uniform yet, move it beyond the current minimal symbol;
+          // lather, rinSe, repeat
+          val sym    = minSym(ts0)
+          val newtps = tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts)
+          if (printLubs) {
+            val str = (newtps.zipWithIndex map { case (tps, idx) =>
+              tps.map("        " + _ + "\n").mkString("   (" + idx + ")\n", "", "\n")
+            }).mkString("")
+
+            println("Frontier(\n" + str + ")")
+            printLubMatrix((ts zip tsBts).toMap, lubListDepth)
+          }
+
+          loop(pretypes, newtps)
+        }
+      }
+    }
+
+    val initialBTSes = ts map (_.baseTypeSeq.toList)
+    if (printLubs)
+      printLubMatrix((ts zip initialBTSes).toMap, depth)
+
+    loop(Nil, initialBTSes)
+  }
+
+  /** The minimal symbol of a list of types (as determined by `Symbol.isLess`). */
+  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 List(t) => List(t)
+    case t :: ts1 =>
+      val rest = elimSuper(ts1 filter (t1 => !(t <:< t1)))
+      if (rest exists (t1 => t1 <:< t)) rest else t :: rest
+  }
+
+  /** 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 List(t) => List(t)
+      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.dealiasWiden))
+      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): Type = tp match {
+      case ExistentialType(_, res) =>
+        res
+      case tv@TypeVar(_, constr) =>
+        if (tv.instValid) stripType(constr.inst)
+        else if (tv.untouchable) tv
+        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 exists typeHasAnnotations)
+      (annotationsLub(lub(ts map (_.withoutAnnotations)), ts), true)
+    else (lub(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)
+
+  private val lubResults = new mutable.HashMap[(Int, List[Type]), Type]
+  private val glbResults = new mutable.HashMap[(Int, List[Type]), Type]
+
+  /** Given a list of types, finds all the base classes they have in
+    *  common, then returns a list of type constructors derived directly
+    *  from the symbols (so any more specific type information is ignored.)
+    *  The list is filtered such that every type constructor in the list
+    *  expects the same number of type arguments, which is chosen based
+    *  on the deepest class among the common baseclasses.
+    */
+  def typeConstructorLubList(ts: List[Type]): List[Type] = {
+    val bcs   = ts.flatMap(_.baseClasses).distinct sortWith (_ isLess _)
+    val tcons = bcs filter (clazz => ts forall (_.typeSymbol isSubClass clazz))
+
+    tcons map (_.typeConstructor) match {
+      case Nil      => Nil
+      case t :: ts  => t :: ts.filter(_.typeParams.size == t.typeParams.size)
+    }
+  }
+
+  def lub(ts: List[Type]): Type = ts match {
+    case List() => NothingClass.tpe
+    case List(t) => t
+    case _ =>
+      if (Statistics.canEnable) Statistics.incCounter(lubCount)
+      val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null
+      try {
+        val res = lub(ts, lubDepth(ts))
+        // If the number of unapplied type parameters in all incoming
+        // types is consistent, and the lub does not match that, return
+        // the type constructor of the calculated lub instead.  This
+        // is because lubbing type constructors tends to result in types
+        // which have been applied to dummies or Nothing.
+        ts.map(_.typeParams.size).distinct match {
+          case x :: Nil if res.typeParams.size != x =>
+            logResult(s"Stripping type args from lub because $res is not consistent with $ts")(res.typeConstructor)
+          case _                                    =>
+            res
+        }
+      }
+      finally {
+        lubResults.clear()
+        glbResults.clear()
+        if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
+      }
+  }
+
+  /** The least upper bound wrt <:< of a list of types */
+  protected[internal] 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 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) =>
+          tparam.cloneSymbol.setInfo(glb(bounds, depth)))
+        PolyType(tparams1, lub0(matchingInstTypes(ts, tparams1)))
+      case ts @ (mt @ MethodType(params, _)) :: rest =>
+        MethodType(params, lub0(matchingRestypes(ts, mt.paramTypes)))
+      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 @ AnnotatedType(annots, tpe, _) :: rest =>
+        annotationsLub(lub0(ts map (_.withoutAnnotations)), ts)
+      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, 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 excludeFromLub(sym: Symbol) = (
+            sym.isClass
+              || sym.isConstructor
+              || !sym.isPublic
+              || isGetClass(sym)
+              || sym.isFinal
+              || narrowts.exists(t => !refines(t, sym))
+            )
+          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 =
+                map2(narrowts, syms)((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.name.toTypeName, proto.pos)
+                  .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, depth)))
+          }
+          // add a refinement symbol for all non-class members of lubBase
+          // which are refined by every type in ts.
+          for (sym <- lubBase.nonPrivateMembers ; if !excludeFromLub(sym)) {
+            try lubsym(sym) andAlso (addMember(lubThisType, lubRefined, _, depth))
+            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 =>
+              isSubType(t, lubRefined, depth) || {
+                if (settings.debug.value || printLubs) {
+                  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
+          }
+        }
+      // dropIllegalStarTypes is a localized fix for SI-6897. We should probably
+      // integrate that transformation at a lower level in master, but lubs are
+      // the likely and maybe only spot they escape, so fixing here for 2.10.1.
+      existentialAbstraction(tparams, dropIllegalStarTypes(lubType))
+    }
+    if (printLubs) {
+      println(indent + "lub of " + ts + " at depth "+depth)//debug
+      indent = indent + "  "
+      assert(indent.length <= 100)
+    }
+    if (Statistics.canEnable) Statistics.incCounter(nestedLubCount)
+    val res = lub0(ts)
+    if (printLubs) {
+      indent = indent stripSuffix "  "
+      println(indent + "lub of " + ts + " is " + res)//debug
+    }
+    if (ts forall typeIsNotNull) 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
+
+  /** The greatest lower bound of a list of types (as determined by `<:<`). */
+  def glb(ts: List[Type]): Type = elimSuper(ts) match {
+    case List() => AnyClass.tpe
+    case List(t) => t
+    case ts0 =>
+      if (Statistics.canEnable) Statistics.incCounter(lubCount)
+      val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null
+      try {
+        glbNorm(ts0, lubDepth(ts0))
+      } finally {
+        lubResults.clear()
+        glbResults.clear()
+        if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
+      }
+  }
+
+  protected[internal] def glb(ts: List[Type], depth: Int): Type = elimSuper(ts) match {
+    case List() => AnyClass.tpe
+    case List(t) => t
+    case ts0 => glbNorm(ts0, depth)
+  }
+
+  /** The greatest lower bound of a list of types (as determined by `<:<`), which have been normalized
+    *  with regard to `elimSuper`. */
+  protected def glbNorm(ts: List[Type], depth: Int): Type = {
+    def glb0(ts0: List[Type]): Type = ts0 match {
+      case List() => AnyClass.tpe
+      case List(t) => t
+      case ts @ PolyType(tparams, _) :: _ =>
+        val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) =>
+          tparam.cloneSymbol.setInfo(lub(bounds, depth)))
+        PolyType(tparams1, glbNorm(matchingInstTypes(ts, tparams1), depth))
+      case ts @ (mt @ MethodType(params, _)) :: rest =>
+        MethodType(params, glbNorm(matchingRestypes(ts, mt.paramTypes), depth))
+      case ts @ NullaryMethodType(_) :: rest =>
+        NullaryMethodType(glbNorm(matchingRestypes(ts, Nil), depth))
+      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; sym <- ds.iterator)
+                  if (globalGlbDepth < globalGlbLimit && !specializesSym(glbThisType, sym, depth))
+                    try {
+                      addMember(glbThisType, glbRefined, glbsym(sym), depth)
+                    } 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
+
+    if (Statistics.canEnable) Statistics.incCounter(nestedLubCount)
+    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 typeIsNotNull) res.notNull else res
+  }
+
+  /** 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 mt @ MethodType(params1, res) if isSameTypes(mt.paramTypes, pts) =>
+        res
+      case NullaryMethodType(res) if pts.isEmpty =>
+        res
+      case _ =>
+        throw new NoCommonType(tps)
+    }
+}
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
new file mode 100644
index 0000000000..82321f61c2
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
@@ -0,0 +1,617 @@
+package scala.reflect
+package internal
+package tpe
+
+import scala.collection.{ mutable }
+import Flags._
+import util.Statistics
+
+trait TypeComparers {
+  self: SymbolTable =>
+  import definitions._
+  import TypesStats._
+
+  private final val LogPendingSubTypesThreshold = DefaultLogThreshhold
+
+  private val pendingSubTypes = new mutable.HashSet[SubTypePair]
+
+  class SubTypePair(val tp1: Type, val tp2: Type) {
+    override def hashCode = tp1.hashCode * 41 + tp2.hashCode
+    override def equals(other: Any) = (this eq other.asInstanceOf[AnyRef]) || (other match {
+      // suspend TypeVars in types compared by =:=,
+      // since we don't want to mutate them simply to check whether a subtype test is pending
+      // in addition to making subtyping "more correct" for type vars,
+      // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion)
+      // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold)
+      case stp: SubTypePair =>
+        val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t))
+        suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2)
+      case _ =>
+        false
+    })
+    override def toString = tp1+" <:<? "+tp2
+  }
+
+  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 isSubPre(pre1: Type, pre2: Type, sym: Symbol) =
+    if ((pre1 ne pre2) && (pre1 ne NoPrefix) && (pre2 ne NoPrefix) && pre1 <:< pre2) {
+      if (settings.debug.value) println(s"new isSubPre $sym: $pre1 <:< $pre2")
+      true
+    } else
+      false
+
+  private def equalSymsAndPrefixes(sym1: Symbol, pre1: Type, sym2: Symbol, pre2: Type): Boolean =
+    if (sym1 == sym2) sym1.hasPackageFlag || sym1.owner.hasPackageFlag || phase.erasedTypes || pre1 =:= pre2
+    else (sym1.name == sym2.name) && isUnifiable(pre1, pre2)
+
+
+  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
+  }
+
+  /** Do `tp1` and `tp2` denote equivalent types? */
+  def isSameType(tp1: Type, tp2: Type): Boolean = try {
+    if (Statistics.canEnable) Statistics.incCounter(sametypeCount)
+    subsametypeRecursions += 1
+    //OPT cutdown on Function0 allocation
+    //was:
+    //    undoLog undoUnless {
+    //      isSameType1(tp1, tp2)
+    //    }
+
+    undoLog.lock()
+    try {
+      val before = undoLog.log
+      var result = false
+      try {
+        result = isSameType1(tp1, tp2)
+      }
+      finally if (!result) undoLog.undoTo(before)
+      result
+    }
+    finally undoLog.unlock()
+  }
+  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()
+  }
+
+  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) // !! I do not see how this would be warranted by the spec
+      tp2.typeSymbol.isPackageClass
+    else if (tp2 eq NoPrefix) // !! I do not see how this would be warranted by the spec
+      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 _: SingleType =>
+            return isSameType2(tp2, tp1)  // put singleton type on the left, caught below
+          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 TypeRef(pre2, sym2, Nil) =>
+            if (sym2.isModuleClass && equalSymsAndPrefixes(st1.sym, st1.pre, sym2.sourceModule, pre2)) 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)
+                  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 =>
+            return isSameTypes(mt1.paramTypes, mt2.paramTypes) &&
+              mt1.resultType =:= mt2.resultType.substSym(mt2.params, mt1.params) &&
+              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, typeVarLHS = true)
+      case _ =>
+    }
+    tp2 match {
+      case tv @ TypeVar(_,_) =>
+        return tv.registerTypeEquality(tp1, typeVarLHS = 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 =>
+            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
+    }
+  }
+
+  def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, AnyDepth)
+
+  def isSubType(tp1: Type, tp2: Type, depth: Int): Boolean = try {
+    subsametypeRecursions += 1
+
+    //OPT cutdown on Function0 allocation
+    //was:
+    //    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)
+    //      }
+    //    }
+
+    undoLog.lock()
+    try {
+      val before = undoLog.log
+      var result = false
+
+      try result = { // 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 if (!result) undoLog.undoTo(before)
+
+      result
+    } finally undoLog.unlock()
+  } 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()
+  }
+
+  private def isPolySubType(tp1: PolyType, tp2: PolyType): Boolean = {
+    val PolyType(tparams1, res1) = tp1
+    val PolyType(tparams2, res2) = tp2
+
+    sameLength(tparams1, tparams2) && {
+      // fast-path: polymorphic method type -- type params cannot be captured
+      val isMethod = tparams1.head.owner.isMethod
+      //@M for an example of why we need to generate fresh symbols otherwise, see neg/tcpoly_ticket2101.scala
+      val substitutes = if (isMethod) tparams1 else cloneSymbols(tparams1)
+      def sub1(tp: Type) = if (isMethod) tp else tp.substSym(tparams1, substitutes)
+      def sub2(tp: Type) = tp.substSym(tparams2, substitutes)
+      def cmp(p1: Symbol, p2: Symbol) = sub2(p2.info) <:< sub1(p1.info)
+
+      (tparams1 corresponds tparams2)(cmp) && (sub1(res1) <:< sub2(res2))
+    }
+  }
+
+  // @assume tp1.isHigherKinded || tp2.isHigherKinded
+  def isHKSubType(tp1: Type, tp2: Type, depth: Int): Boolean = {
+    def isSub(ntp1: Type, ntp2: Type) = (ntp1.withoutAnnotations, ntp2.withoutAnnotations) match {
+      case (TypeRef(_, AnyClass, _), _)                                     => false                    // avoid some warnings when Nothing/Any are on the other side
+      case (_, TypeRef(_, NothingClass, _))                                 => false
+      case (pt1: PolyType, pt2: PolyType)                                   => isPolySubType(pt1, pt2)  // @assume both .isHigherKinded (both normalized to PolyType)
+      case (_: PolyType, MethodType(ps, _)) if ps exists (_.tpe.isWildcard) => false                    // don't warn on HasMethodMatching on right hand side
+      case _                                                                =>                          // @assume !(both .isHigherKinded) thus cannot be subtypes
+        def tp_s(tp: Type): String = f"$tp%-20s ${util.shortClassOfInstance(tp)}%s"
+        devWarning(s"HK subtype check on $tp1 and $tp2, but both don't normalize to polytypes:\n  tp1=${tp_s(ntp1)}\n  tp2=${tp_s(ntp2)}")
+        false
+    }
+
+    (    tp1.typeSymbol == NothingClass       // @M Nothing is subtype of every well-kinded type
+      || tp2.typeSymbol == AnyClass           // @M Any is supertype of every well-kinded type (@PP: is it? What about continuations plugin?)
+      || isSub(tp1.normalize, tp2.normalize) && annotationsConform(tp1, tp2)  // @M! normalize reduces higher-kinded case to PolyType's
+    )
+  }
+
+  /** 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 // !! I do not see how the "isPackageClass" would be warranted by the spec
+    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 isHKSubType(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 = 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 || sym1.owner.hasPackageFlag || isSubType(pre1, pre2, depth)
+            else (sym1.name == sym2.name && !sym1.isModuleClass && !sym2.isModuleClass &&
+              (isUnifiable(pre1, pre2) ||
+                isSameSpecializedSkolem(sym1, sym2, pre1, pre2) ||
+                sym2.isAbstractType && isSubPre(pre1, pre2, sym2)))) &&
+              isSubArgs(tr1.args, tr2.args, sym1.typeParams, depth))
+              ||
+              sym2.isClass && {
+                val base = tr1 baseType sym2
+                (base ne tr1) && isSubType(base, tr2, depth)
+              }
+              ||
+              thirdTryRef(tr1, tr2))
+          case _ =>
+            secondTry
+        }
+      case AnnotatedType(_, _, _) =>
+        isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) &&
+          annotationsConform(tp1, tp2)
+      case BoundedWildcardType(bounds) =>
+        isSubType(tp1, bounds.hi, depth)
+      case tv2 @ TypeVar(_, constr2) =>
+        tp1 match {
+          case AnnotatedType(_, _, _) | BoundedWildcardType(_) =>
+            secondTry
+          case _ =>
+            tv2.registerBound(tp1, isLowerBound = true)
+        }
+      case _ =>
+        secondTry
+    }
+
+    /** Second try, on the left:
+      *   - unwrap AnnotatedTypes, BoundedWildcardTypes,
+      *   - bind typevars,
+      *   - handle existential types by skolemization.
+      */
+    def secondTry = tp1 match {
+      case AnnotatedType(_, _, _) =>
+        isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) &&
+          annotationsConform(tp1, tp2)
+      case BoundedWildcardType(bounds) =>
+        isSubType(tp1.bounds.lo, tp2, depth)
+      case tv @ TypeVar(_,_) =>
+        tv.registerBound(tp2, isLowerBound = false)
+      case ExistentialType(_, _) =>
+        try {
+          skolemizationLevel += 1
+          isSubType(tp1.skolemizeExistential, tp2, depth)
+        } finally {
+          skolemizationLevel -= 1
+        }
+      case _ =>
+        thirdTry
+    }
+
+    def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = {
+      val sym2 = tp2.sym
+      sym2 match {
+        case NotNullClass => tp1.isNotNull
+        case SingletonClass => tp1.isStable || fourthTry
+        case _: ClassSymbol =>
+          if (isRawType(tp2))
+            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) &&
+              isSubType(tp1, tp2a, depth) ||
+              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 = tp2 match {
+      case tr2: TypeRef =>
+        thirdTryRef(tp1, tr2)
+      case rt2: RefinedType =>
+        (rt2.parents forall (isSubType(tp1, _, depth))) &&
+          (rt2.decls forall (specializesSym(tp1, _, depth)))
+      case et2: ExistentialType =>
+        et2.withTypeVars(isSubType(tp1, _, depth), depth) || fourthTry
+      case nn2: NotNullType =>
+        tp1.isNotNull && isSubType(tp1, nn2.underlying, depth)
+      case mt2: MethodType =>
+        tp1 match {
+          case mt1 @ MethodType(params1, res1) =>
+            val params2 = mt2.params
+            val res2 = mt2.resultType
+            (sameLength(params1, params2) &&
+              mt1.isImplicit == mt2.isImplicit &&
+              matchingParams(params1, params2, mt1.isJava, mt2.isJava) &&
+              isSubType(res1.substSym(params1, params2), res2, depth))
+          // 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(_) =>
+            isSubType(pt1.resultType, pt2.resultType, depth)
+          case _ =>
+            false
+        }
+      case TypeBounds(lo2, hi2) =>
+        tp1 match {
+          case TypeBounds(lo1, hi1) =>
+            isSubType(lo2, lo1, depth) && isSubType(hi1, hi2, depth)
+          case _ =>
+            false
+        }
+      case _ =>
+        fourthTry
+    }
+
+    /** Fourth try, on the left:
+      *   - handle typerefs, refined types, notnull and singleton types.
+      */
+    def fourthTry = tp1 match {
+      case tr1 @ TypeRef(pre1, sym1, _) =>
+        sym1 match {
+          case NothingClass => true
+          case NullClass =>
+            tp2 match {
+              case TypeRef(_, sym2, _) =>
+                containsNull(sym2)
+              case _ =>
+                isSingleType(tp2) && isSubType(tp1, tp2.widen, depth)
+            }
+          case _: ClassSymbol =>
+            if (isRawType(tp1))
+              isSubType(rawToExistential(tp1), tp2, depth)
+            else if (sym1.isModuleClass) tp2 match {
+              case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1.sourceModule, pre1, sym2, pre2)
+              case _                      => false
+            }
+            else if (sym1.isRefinementClass)
+              isSubType(sym1.info, tp2, depth)
+            else false
+
+          case _: TypeSymbol =>
+            if (sym1 hasFlag DEFERRED) {
+              val tp1a = tp1.bounds.hi
+              isDifferentTypeConstructor(tp1, tp1a) && isSubType(tp1a, tp2, depth)
+            } else {
+              isSubType(tp1.normalize, tp2.normalize, depth)
+            }
+          case _ =>
+            false
+        }
+      case RefinedType(parents1, _) =>
+        parents1 exists (isSubType(_, tp2, depth))
+      case _: SingletonType | _: NotNullType =>
+        isSubType(tp1.underlying, tp2, depth)
+      case _ =>
+        false
+    }
+
+    firstTry
+  }
+
+
+  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)
+    }
+
+  /** The isNumericValueType tests appear redundant, but without them
+    *  test/continuations-neg/function3.scala goes into an infinite loop.
+    *  (Even if the calls are to typeSymbolDirect.)
+    */
+  def isNumericSubType(tp1: Type, tp2: Type): Boolean = (
+    isNumericValueType(tp1)
+      && isNumericValueType(tp2)
+      && isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol)
+    )
+
+}
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
new file mode 100644
index 0000000000..a002b01f70
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/tpe/TypeConstraints.scala
@@ -0,0 +1,282 @@
+package scala.reflect
+package internal
+package tpe
+
+import scala.collection.{ generic }
+import generic.Clearable
+
+
+private[internal] trait TypeConstraints {
+  self: SymbolTable =>
+  import definitions._
+
+  /** A log of type variable with their original constraints. Used in order
+    *  to undo constraints in the case of isSubType/isSameType failure.
+    */
+  lazy val undoLog = newUndoLog
+
+  protected def newUndoLog = new UndoLog
+
+  class UndoLog extends Clearable {
+    private type UndoPairs = List[(TypeVar, TypeConstraint)]
+    //OPT this method is public so we can do `manual inlining`
+    var log: UndoPairs = List()
+
+    /*
+     * These two methods provide explicit locking mechanism that is overridden in SynchronizedUndoLog.
+     *
+     * The idea behind explicit locking mechanism is that all public methods that access mutable state
+     * will have to obtain the lock for their entire execution so both reads and writes can be kept in
+     * right order. Originally, that was achieved by overriding those public methods in
+     * `SynchronizedUndoLog` which was fine but expensive. The reason is that those public methods take
+     * thunk as argument and if we keep them non-final there's no way to make them inlined so thunks
+     * can go away.
+     *
+     * By using explicit locking we can achieve inlining.
+     *
+     * NOTE: They are made public for now so we can apply 'manual inlining' (copy&pasting into hot
+     * places implementation of `undo` or `undoUnless`). This should be changed back to protected
+     * once inliner is fixed.
+     */
+    def lock(): Unit = ()
+    def unlock(): Unit = ()
+
+    // register with the auto-clearing cache manager
+    perRunCaches.recordCache(this)
+
+    /** Undo all changes to constraints to type variables upto `limit`. */
+    //OPT this method is public so we can do `manual inlining`
+    def undoTo(limit: UndoPairs) {
+      assertCorrectThread()
+      while ((log ne limit) && log.nonEmpty) {
+        val (tv, constr) = log.head
+        tv.constr = constr
+        log = log.tail
+      }
+    }
+
+    /** No sync necessary, because record should only
+      *  be called from within an undo or undoUnless block,
+      *  which is already synchronized.
+      */
+    private[reflect] def record(tv: TypeVar) = {
+      log ::= ((tv, tv.constr.cloneInternal))
+    }
+
+    def clear() {
+      lock()
+      try {
+        if (settings.debug.value)
+          self.log("Clearing " + log.size + " entries from the undoLog.")
+        log = Nil
+      } finally unlock()
+    }
+
+    // `block` should not affect constraints on typevars
+    def undo[T](block: => T): T = {
+      lock()
+      try {
+        val before = log
+
+        try block
+        finally undoTo(before)
+      } finally unlock()
+    }
+  }
+
+  /** @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, avoidWidening0: Boolean = false) {
+    def this(lo0: List[Type], hi0: List[Type]) = this(lo0, hi0, NoType, NoType)
+    def this(bounds: TypeBounds) = this(List(bounds.lo), List(bounds.hi))
+    def this() = this(List(), List())
+
+    /*  Syncnote: Type constraints are assumed to be used from only one
+     *  thread. They are not exposed in api.Types and are used only locally
+     *  in operations that are exposed from types. Hence, no syncing of any
+     *  variables should be ncessesary.
+     */
+
+    /** Guard these lists against AnyClass and NothingClass appearing,
+      *  else loBounds.isEmpty will have different results for an empty
+      *  constraint and one with Nothing as a lower bound.  [Actually
+      *  guarding addLoBound/addHiBound somehow broke raw types so it
+      *  only guards against being created with them.]
+      */
+    private var lobounds = lo0 filterNot typeIsNothing
+    private var hibounds = hi0 filterNot typeIsAny
+    private var numlo = numlo0
+    private var numhi = numhi0
+    private var avoidWidening = avoidWidening0
+
+    def loBounds: List[Type] = if (numlo == NoType) lobounds else numlo :: lobounds
+    def hiBounds: List[Type] = if (numhi == NoType) hibounds else numhi :: hibounds
+    def avoidWiden: Boolean = avoidWidening
+
+    def addLoBound(tp: Type, isNumericBound: Boolean = false) {
+      // For some reason which is still a bit fuzzy, we must let Nothing through as
+      // a lower bound despite the fact that Nothing is always a lower bound.  My current
+      // supposition is that the side-effecting type constraint accumulation mechanism
+      // depends on these subtype tests being performed to make forward progress when
+      // there are mutally recursive type vars.
+      // See pos/t6367 and pos/t6499 for the competing test cases.
+      val mustConsider = tp.typeSymbol match {
+        case NothingClass => true
+        case _            => !(lobounds contains tp)
+      }
+      if (mustConsider) {
+        if (isNumericBound && isNumericValueType(tp)) {
+          if (numlo == NoType || isNumericSubType(numlo, tp))
+            numlo = tp
+          else if (!isNumericSubType(tp, numlo))
+            numlo = numericLoBound
+        }
+        else lobounds ::= tp
+      }
+    }
+
+    def checkWidening(tp: Type) {
+      if(tp.isStable) avoidWidening = true
+      else tp match {
+        case HasTypeMember(_, _) => avoidWidening = true
+        case _ =>
+      }
+    }
+
+    def addHiBound(tp: Type, isNumericBound: Boolean = false) {
+      // My current test case only demonstrates the need to let Nothing through as
+      // a lower bound, but I suspect the situation is symmetrical.
+      val mustConsider = tp.typeSymbol match {
+        case AnyClass => true
+        case _        => !(hibounds contains tp)
+      }
+      if (mustConsider) {
+        checkWidening(tp)
+        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, avoidWidening)
+      tc.inst = inst
+      tc
+    }
+
+    override def toString = {
+      val boundsStr = {
+        val lo    = loBounds filterNot typeIsNothing
+        val hi    = hiBounds filterNot typeIsAny
+        val lostr = if (lo.isEmpty) Nil else List(lo.mkString(" >: (", ", ", ")"))
+        val histr = if (hi.isEmpty) Nil else List(hi.mkString(" <: (", ", ", ")"))
+
+        lostr ++ histr mkString ("[", " | ", "]")
+      }
+      if (inst eq NoType) boundsStr
+      else boundsStr + " _= " + inst.safeToString
+    }
+  }
+
+  /** 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[Variance], upper: Boolean): Boolean =
+    solve(tvars, tparams, variances, upper, AnyDepth)
+
+  def solve(tvars: List[TypeVar], tparams: List[Symbol],
+            variances: List[Variance], upper: Boolean, depth: Int): Boolean = {
+
+    def solveOne(tvar: TypeVar, tparam: Symbol, variance: Variance) {
+      if (tvar.constr.inst == NoType) {
+        val up = if (variance.isContravariant) !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
+        foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => {
+          val ok = (tparam2 != tparam) && (
+            (bound contains tparam2)
+              ||  up && (tparam2.info.bounds.lo =:= tparam.tpeHK)
+              || !up && (tparam2.info.bounds.hi =:= tparam.tpeHK)
+            )
+          if (ok) {
+            if (tvar2.constr.inst eq null) cyclic = true
+            solveOne(tvar2, tparam2, variance2)
+          }
+        })
+        if (!cyclic) {
+          if (up) {
+            if (bound.typeSymbol != AnyClass) {
+              log(s"$tvar addHiBound $bound.instantiateTypeParams($tparams, $tvars)")
+              tvar addHiBound bound.instantiateTypeParams(tparams, tvars)
+            }
+            for (tparam2 <- tparams)
+              tparam2.info.bounds.lo.dealias match {
+                case TypeRef(_, `tparam`, _) =>
+                  log(s"$tvar addHiBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
+                  tvar addHiBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars)
+                case _ =>
+              }
+          } else {
+            if (bound.typeSymbol != NothingClass && bound.typeSymbol != tparam) {
+              log(s"$tvar addLoBound $bound.instantiateTypeParams($tparams, $tvars)")
+              tvar addLoBound bound.instantiateTypeParams(tparams, tvars)
+            }
+            for (tparam2 <- tparams)
+              tparam2.info.bounds.hi.dealias match {
+                case TypeRef(_, `tparam`, _) =>
+                  log(s"$tvar addLoBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
+                  tvar addLoBound tparam2.tpeHK.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)))
+        val newInst = (
+          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)
+          }
+          )
+        log(s"$tvar setInst $newInst")
+        tvar setInst newInst
+        //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)))
+    foreach3(tvars, tparams, variances)(solveOne)
+    tvars forall (tvar => tvar.constr.isWithinBounds(tvar.constr.inst))
+  }
+}
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
new file mode 100644
index 0000000000..51363c0f82
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala
@@ -0,0 +1,1144 @@
+package scala.reflect
+package internal
+package tpe
+
+import scala.collection.{ mutable, immutable }
+import Flags._
+import scala.annotation.tailrec
+import Variance._
+
+private[internal] trait TypeMaps {
+  self: SymbolTable =>
+  import definitions._
+
+  /** Normalize any type aliases within this type (@see Type#normalize).
+    *  Note that this depends very much on the call to "normalize", not "dealias",
+    *  so it is no longer carries the too-stealthy name "deAlias".
+    */
+  object normalizeAliases extends TypeMap {
+    def apply(tp: Type): Type = tp match {
+      case TypeRef(_, sym, _) if sym.isAliasType =>
+        def msg = if (tp.isHigherKinded) s"Normalizing type alias function $tp" else s"Dealiasing type alias $tp"
+        mapOver(logResult(msg)(tp.normalize))
+      case _                                     => mapOver(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) =>
+          parents filter (_.typeSymbol != SingletonClass) match {
+            case Nil                       => AnyClass.tpe
+            case p :: Nil if decls.isEmpty => mapOver(p)
+            case ps                        => mapOver(copyRefinedType(tp1, ps, decls))
+          }
+        case tp1 =>
+          mapOver(tp1)
+      }
+    }
+  }
+
+  /** Type with all top-level occurrences of abstract types replaced by their bounds */
+  object abstractTypesToBounds extends TypeMap {
+    def apply(tp: Type): Type = tp match {
+      case TypeRef(_, sym, _) if sym.isAliasType    => apply(tp.dealias)
+      case TypeRef(_, sym, _) if sym.isAbstractType => apply(tp.bounds.hi)
+      case rtp @ RefinedType(parents, decls)        => copyRefinedType(rtp, parents mapConserve this, decls)
+      case AnnotatedType(_, _, _)                   => mapOver(tp)
+      case _                                        => tp             // no recursion - top level only
+    }
+  }
+
+  // Set to true for A* => Seq[A]
+  //   (And it will only rewrite A* in method result types.)
+  //   This is the pre-existing behavior.
+  // Or false for Seq[A] => Seq[A]
+  //   (It will rewrite A* everywhere but method parameters.)
+  //   This is the specified behavior.
+  protected def etaExpandKeepsStar = false
+
+  /** Turn any T* types into Seq[T] except when
+    *  in method parameter position.
+    */
+  object dropIllegalStarTypes extends TypeMap {
+    def apply(tp: Type): Type = tp match {
+      case MethodType(params, restpe) =>
+        // Not mapping over params
+        val restpe1 = apply(restpe)
+        if (restpe eq restpe1) tp
+        else MethodType(params, restpe1)
+      case TypeRef(_, RepeatedParamClass, arg :: Nil) =>
+        seqType(arg)
+      case _ =>
+        if (etaExpandKeepsStar) tp else mapOver(tp)
+    }
+  }
+
+  trait AnnotationFilter extends TypeMap {
+    def keepAnnotation(annot: AnnotationInfo): Boolean
+
+    override def mapOver(annot: AnnotationInfo) =
+      if (keepAnnotation(annot)) super.mapOver(annot)
+      else UnmappableAnnotation
+  }
+
+  trait KeepOnlyTypeConstraints extends AnnotationFilter {
+    // filter keeps only type constraint annotations
+    def keepAnnotation(annot: AnnotationInfo) = annot matches TypeConstraintClass
+  }
+
+  // todo. move these into scala.reflect.api
+
+  /** A prototype for mapping a function over all possible types
+    */
+  abstract class TypeMap(trackVariance: Boolean) extends (Type => Type) {
+    def this() = this(trackVariance = false)
+    def apply(tp: Type): Type
+
+    private[this] var _variance: Variance = if (trackVariance) Covariant else Invariant
+
+    def variance_=(x: Variance) = { assert(trackVariance, this) ; _variance = x }
+    def variance = _variance
+
+    /** Map this function over given type */
+    def mapOver(tp: Type): Type = tp match {
+      case tr @ TypeRef(pre, sym, args) =>
+        val pre1 = this(pre)
+        val args1 = (
+          if (trackVariance && args.nonEmpty && !variance.isInvariant && sym.typeParams.nonEmpty)
+            mapOverArgs(args, sym.typeParams)
+          else
+            args mapConserve this
+          )
+        if ((pre1 eq pre) && (args1 eq args)) tp
+        else copyTypeRef(tp, pre1, tr.coevolveSym(pre1), 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) =>
+        val params1 = flipped(mapOver(params))
+        val result1 = this(result)
+        if ((params1 eq params) && (result1 eq result)) tp
+        else copyMethodType(tp, params1, result1.substSym(params, params1))
+      case PolyType(tparams, result) =>
+        val tparams1 = flipped(mapOver(tparams))
+        val 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) =>
+        val lo1 = flipped(this(lo))
+        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)
+        copyRefinedType(rtp, parents1, decls1)
+      case ExistentialType(tparams, result) =>
+        val tparams1 = mapOver(tparams)
+        val result1 = this(result)
+        if ((tparams1 eq tparams) && (result1 eq result)) tp
+        else newExistentialType(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 ErasedSingleType(sym) => tp
+      */
+      case _ =>
+        tp
+      // throw new Error("mapOver inapplicable for " + tp);
+    }
+
+    def withVariance[T](v: Variance)(body: => T): T = {
+      val saved = variance
+      variance = v
+      try body finally variance = saved
+    }
+    @inline final def flipped[T](body: => T): T = {
+      if (trackVariance) variance = variance.flip
+      try body
+      finally if (trackVariance) variance = variance.flip
+    }
+    protected def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] = (
+      if (trackVariance)
+        map2Conserve(args, tparams)((arg, tparam) => withVariance(variance * tparam.variance)(this(arg)))
+      else
+        args mapConserve this
+      )
+    /** Applies this map to the symbol's info, setting variance = Invariant
+      *  if necessary when the symbol is an alias.
+      */
+    private def applyToSymbolInfo(sym: Symbol): Type = {
+      if (trackVariance && !variance.isInvariant && sym.isAliasType)
+        withVariance(Invariant)(this(sym.info))
+      else
+        this(sym.info)
+    }
+
+    /** Called by mapOver to determine whether the original symbols can
+      *  be returned, or whether they must be cloned.
+      */
+    protected def noChangeToSymbols(origSyms: List[Symbol]): Boolean = {
+      @tailrec def loop(syms: List[Symbol]): Boolean = syms match {
+        case Nil     => true
+        case x :: xs => (x.info eq applyToSymbolInfo(x)) && loop(xs)
+      }
+      loop(origSyms)
+    }
+
+    /** 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 newScopeWith(elems1: _*)
+    }
+
+    /** Map this function over given list of symbols */
+    def mapOver(origSyms: List[Symbol]): List[Symbol] = {
+      // fast path in case nothing changes due to map
+      if (noChangeToSymbols(origSyms)) origSyms
+      // map is not the identity --> do cloning properly
+      else cloneSymbolsAndModify(origSyms, TypeMap.this)
+    }
+
+    def mapOver(annot: AnnotationInfo): AnnotationInfo = {
+      val AnnotationInfo(atp, args, assocs) = annot
+      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)) annot
+      else if (args1.isEmpty && args.nonEmpty) UnmappableAnnotation  // some annotation arg was unmappable
+      else AnnotationInfo(atp1, args1, assocs) setPos annot.pos
+    }
+
+    def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = {
+      val annots1 = annots mapConserve mapOver
+      if (annots1 eq annots) annots
+      else annots1 filterNot (_ eq UnmappableAnnotation)
+    }
+
+    /** 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 mapConserve mapOver
+      if (args1 contains UnmappableTree) Nil
+      else args1
+    }
+
+    def mapOver(tree: Tree): Tree =
+      mapOver(tree, () => return UnmappableTree)
+
+    /** 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)
+      }
+    }
+  }
+
+  abstract class TypeTraverser extends TypeMap {
+    def traverse(tp: Type): Unit
+    def apply(tp: Type): Type = { traverse(tp); tp }
+  }
+
+  abstract class TypeTraverserWithResult[T] extends TypeTraverser {
+    def result: T
+    def clear(): Unit
+  }
+
+  abstract class TypeCollector[T](initial: T) extends TypeTraverser {
+    var result: T = _
+    def collect(tp: Type) = {
+      result = initial
+      traverse(tp)
+      result
+    }
+  }
+
+  /** 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).
+    */
+  def rawToExistential = new TypeMap {
+    private var expanded = immutable.Set[Symbol]()
+    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))
+          existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe)))
+        } finally {
+          expanded -= sym
+        }
+      case _ =>
+        mapOver(tp)
+    }
+  }
+  /***
+    *@M: I think this is more desirable, but Martin prefers to leave raw-types as-is as much as possible
+    object rawToExistentialInJava extends TypeMap {
+      def apply(tp: Type): Type = tp match {
+        // any symbol that occurs in a java sig, not just java symbols
+        // see http://lampsvn.epfl.ch/trac/scala/ticket/2454#comment:14
+        case TypeRef(pre, sym, List()) if !sym.typeParams.isEmpty =>
+          val eparams = typeParamsToExistentials(sym, sym.typeParams)
+          existentialAbstraction(eparams, TypeRef(pre, sym, eparams map (_.tpe)))
+        case _ =>
+          mapOver(tp)
+      }
+    }
+    */
+
+  /** Used by existentialAbstraction.
+    */
+  class ExistentialExtrapolation(tparams: List[Symbol]) extends TypeMap(trackVariance = true) {
+    private val occurCount = mutable.HashMap[Symbol, Int]()
+    private def countOccs(tp: Type) = {
+      tp foreach {
+        case TypeRef(_, sym, _) =>
+          if (tparams contains sym)
+            occurCount(sym) += 1
+        case _ => ()
+      }
+    }
+    def extrapolate(tpe: Type): Type = {
+      tparams foreach (t => occurCount(t) = 0)
+      countOccs(tpe)
+      for (tparam <- tparams)
+        countOccs(tparam.info)
+
+      apply(tpe)
+    }
+
+    /** If these conditions all hold:
+      *   1) we are in covariant (or contravariant) position
+      *   2) this type occurs exactly once in the existential scope
+      *   3) the widened upper (or lower) bound of this type contains no references to tparams
+      *  Then we replace this lone occurrence of the type with the widened upper (or lower) bound.
+      *  All other types pass through unchanged.
+      */
+    def apply(tp: Type): Type = {
+      val tp1 = mapOver(tp)
+      if (variance.isInvariant) tp1
+      else tp1 match {
+        case TypeRef(pre, sym, args) if tparams contains sym =>
+          val repl = if (variance.isPositive) dropSingletonType(tp1.bounds.hi) else tp1.bounds.lo
+          val count = occurCount(sym)
+          val containsTypeParam = tparams exists (repl contains _)
+          def msg = {
+            val word = if (variance.isPositive) "upper" else "lower"
+            s"Widened lone occurrence of $tp1 inside existential to $word bound"
+          }
+          if (!repl.typeSymbol.isBottomClass && count == 1 && !containsTypeParam)
+            logResult(msg)(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)
+    }
+
+    // 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.
+    override def mapOver(tree: Tree) = tree match {
+      case Ident(_) if tree.tpe.isStable => tree
+      case _                             => super.mapOver(tree)
+    }
+  }
+
+  /** Might the given symbol be important when calculating the prefix
+    *  of a type? When tp.asSeenFrom(pre, clazz) is called on `tp`,
+    *  the result will be `tp` unchanged if `pre` is trivial and `clazz`
+    *  is a symbol such that isPossiblePrefix(clazz) == false.
+    */
+  def isPossiblePrefix(clazz: Symbol) = clazz.isClass && !clazz.isPackageClass
+
+  protected[internal] def skipPrefixOf(pre: Type, clazz: Symbol) = (
+    (pre eq NoType) || (pre eq NoPrefix) || !isPossiblePrefix(clazz)
+    )
+
+  def newAsSeenFromMap(pre: Type, clazz: Symbol): AsSeenFromMap =
+    new AsSeenFromMap(pre, clazz)
+
+  /** A map to compute the asSeenFrom method.
+    */
+  class AsSeenFromMap(seenFromPrefix: Type, seenFromClass: Symbol) extends TypeMap with KeepOnlyTypeConstraints {
+    // Some example source constructs relevant in asSeenFrom:
+    //
+    // object CaptureThis {
+    //   trait X[A] { def f: this.type = this }
+    //   class Y[A] { def f: this.type = this }
+    //   // Created new existential to represent This(CaptureThis.X) seen from CaptureThis.X[B]: type _1.type <: CaptureThis.X[B] with Singleton
+    //   def f1[B] = new X[B] { }
+    //   // TODO - why is the behavior different when it's a class?
+    //   def f2[B] = new Y[B] { }
+    // }
+    // class CaptureVal[T] {
+    //   val f: java.util.List[_ <: T] = null
+    //   // Captured existential skolem for type _$1 seen from CaptureVal.this.f.type: type _$1
+    //   def g = f get 0
+    // }
+    // class ClassParam[T] {
+    //   // AsSeenFromMap(Inner.this.type, class Inner)/classParameterAsSeen(T)#loop(ClassParam.this.type, class ClassParam)
+    //   class Inner(lhs: T) { def f = lhs }
+    // }
+    def capturedParams: List[Symbol]  = _capturedParams
+    def capturedSkolems: List[Symbol] = _capturedSkolems
+
+    def apply(tp: Type): Type = tp match {
+      case tp @ ThisType(_)                                            => thisTypeAsSeen(tp)
+      case tp @ SingleType(_, sym)                                     => if (sym.isPackageClass) tp else singleTypeAsSeen(tp)
+      case tp @ TypeRef(_, sym, _) if isTypeParamOfEnclosingClass(sym) => classParameterAsSeen(tp)
+      case _                                                           => mapOver(tp)
+    }
+
+    private var _capturedSkolems: List[Symbol] = Nil
+    private var _capturedParams: List[Symbol]  = Nil
+    private val isStablePrefix = seenFromPrefix.isStable
+
+    // isBaseClassOfEnclosingClassOrInfoIsNotYetComplete would be a more accurate
+    // but less succinct name.
+    private def isBaseClassOfEnclosingClass(base: Symbol) = {
+      def loop(encl: Symbol): Boolean = (
+        isPossiblePrefix(encl)
+          && ((encl isSubClass base) || loop(encl.owner.enclClass))
+        )
+      // The hasCompleteInfo guard is necessary to avoid cycles during the typing
+      // of certain classes, notably ones defined inside package objects.
+      !base.hasCompleteInfo || loop(seenFromClass)
+    }
+
+    /** Is the symbol a class type parameter from one of the enclosing
+      *  classes, or a base class of one of them?
+      */
+    private def isTypeParamOfEnclosingClass(sym: Symbol): Boolean = (
+      sym.isTypeParameter
+        && sym.owner.isClass
+        && isBaseClassOfEnclosingClass(sym.owner)
+      )
+
+    /** Creates an existential representing a type parameter which appears
+      *  in the prefix of a ThisType.
+      */
+    protected def captureThis(pre: Type, clazz: Symbol): Type = {
+      capturedParams find (_.owner == clazz) match {
+        case Some(p) => p.tpe
+        case _       =>
+          val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre)
+          _capturedParams ::= qvar
+          debuglog(s"Captured This(${clazz.fullNameString}) seen from $seenFromPrefix: ${qvar.defString}")
+          qvar.tpe
+      }
+    }
+    protected def captureSkolems(skolems: List[Symbol]) {
+      for (p <- skolems; if !(capturedSkolems contains p)) {
+        debuglog(s"Captured $p seen from $seenFromPrefix")
+        _capturedSkolems ::= p
+      }
+    }
+
+    /** Find the type argument in an applied type which corresponds to a type parameter.
+      *  The arguments are required to be related as follows, through intermediary `clazz`.
+      *  An exception will be thrown if this is violated.
+      *
+      *  @param   lhs    its symbol is a type parameter of `clazz`
+      *  @param   rhs    a type application constructed from `clazz`
+      */
+    private def correspondingTypeArgument(lhs: Type, rhs: Type): Type = {
+      val TypeRef(_, lhsSym, lhsArgs) = lhs
+      val TypeRef(_, rhsSym, rhsArgs) = rhs
+      require(lhsSym.safeOwner == rhsSym, s"$lhsSym is not a type parameter of $rhsSym")
+
+      // Find the type parameter position; we'll use the corresponding argument
+      val argIndex = rhsSym.typeParams indexOf lhsSym
+
+      if (argIndex >= 0 && argIndex < rhsArgs.length)             // @M! don't just replace the whole thing, might be followed by type application
+        appliedType(rhsArgs(argIndex), lhsArgs mapConserve this)
+      else if (rhsSym.tpe_*.parents exists typeIsErroneous)        // don't be too zealous with the exceptions, see #2641
+        ErrorType
+      else
+        abort(s"something is wrong: cannot make sense of type application\n  $lhs\n  $rhs")
+    }
+
+    // 0) @pre: `classParam` is a class type parameter
+    // 1) Walk the owner chain of `seenFromClass` until we find the class which owns `classParam`
+    // 2) Take the base type of the prefix at that point with respect to the owning class
+    // 3) Solve for the type parameters through correspondence with the type args of the base type
+    //
+    // Only class type parameters (and not skolems) are considered, because other type parameters
+    // are not influenced by the prefix through which they are seen. Note that 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.
+    private def classParameterAsSeen(classParam: Type): Type = {
+      val TypeRef(_, tparam, _) = classParam
+
+      def loop(pre: Type, clazz: Symbol): Type = {
+        // have to deconst because it may be a Class[T]
+        def nextBase = (pre baseType clazz).deconst
+        //@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary
+        if (skipPrefixOf(pre, clazz))
+          mapOver(classParam)
+        else if (!matchesPrefixAndClass(pre, clazz)(tparam.owner))
+          loop(nextBase.prefix, clazz.owner)
+        else nextBase match {
+          case applied @ TypeRef(_, _, _)     => correspondingTypeArgument(classParam, applied)
+          case ExistentialType(eparams, qtpe) => captureSkolems(eparams) ; loop(qtpe, clazz)
+          case t                              => abort(s"$tparam in ${tparam.owner} cannot be instantiated from ${seenFromPrefix.widen}")
+        }
+      }
+      loop(seenFromPrefix, seenFromClass)
+    }
+
+    // Does the candidate symbol match the given prefix and class?
+    // Since pre may be something like ThisType(A) where trait A { self: B => },
+    // we have to test the typeSymbol of the widened type, not pre.typeSymbol, or
+    // B will not be considered.
+    private def matchesPrefixAndClass(pre: Type, clazz: Symbol)(candidate: Symbol) = pre.widen match {
+      case _: TypeVar => false
+      case wide       => (clazz == candidate) && (wide.typeSymbol isSubClass clazz)
+    }
+
+    // Whether the annotation tree currently being mapped over has had a This(_) node rewritten.
+    private[this] var wroteAnnotation = false
+    private object annotationArgRewriter extends TypeMapTransformer {
+      private def matchesThis(thiz: Symbol) = matchesPrefixAndClass(seenFromPrefix, seenFromClass)(thiz)
+
+      // what symbol should really be used?
+      private def newThis(): Tree = {
+        wroteAnnotation = true
+        val presym      = seenFromPrefix.widen.typeSymbol
+        val thisSym     = presym.owner.newValue(presym.name.toTermName, presym.pos) setInfo seenFromPrefix
+        gen.mkAttributedQualifier(seenFromPrefix, thisSym)
+      }
+
+      /** Rewrite `This` trees in annotation argument trees */
+      override def transform(tree: Tree): Tree = super.transform(tree) match {
+        case This(_) if matchesThis(tree.symbol) => newThis()
+        case tree                                => tree
+      }
+    }
+
+    // This becomes considerably cheaper if we optimize for the common cases:
+    // where the prefix is stable and where no This nodes are rewritten. If
+    // either is true, then we don't need to worry about calling giveup. So if
+    // the prefix is unstable, use a stack variable to indicate whether the tree
+    // was touched. This takes us to one allocation per AsSeenFromMap rather
+    // than an allocation on every call to mapOver, and no extra work when the
+    // tree only has its types remapped.
+    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
+      if (isStablePrefix)
+        annotationArgRewriter transform tree
+      else {
+        val saved = wroteAnnotation
+        wroteAnnotation = false
+        try annotationArgRewriter transform tree
+        finally if (wroteAnnotation) giveup() else wroteAnnotation = saved
+      }
+    }
+
+    private def thisTypeAsSeen(tp: ThisType): Type = {
+      def loop(pre: Type, clazz: Symbol): Type = {
+        val pre1 = pre match {
+          case SuperType(thistpe, _) => thistpe
+          case _                     => pre
+        }
+        if (skipPrefixOf(pre, clazz))
+          mapOver(tp) // TODO - is mapOver necessary here?
+        else if (!matchesPrefixAndClass(pre, clazz)(tp.sym))
+          loop((pre baseType clazz).prefix, clazz.owner)
+        else if (pre1.isStable)
+          pre1
+        else
+          captureThis(pre1, clazz)
+      }
+      loop(seenFromPrefix, seenFromClass)
+    }
+
+    private def singleTypeAsSeen(tp: SingleType): Type = {
+      val SingleType(pre, sym) = tp
+
+      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
+    }
+
+    override def toString = s"AsSeenFromMap($seenFromPrefix, $seenFromClass)"
+  }
+
+  /** A base class to compute all substitutions */
+  abstract class SubstMap[T](from: List[Symbol], to: List[T]) extends TypeMap {
+    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) =>
+        createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, renameBoundSyms(tp1)))
+      case PolyType(bs, restp) =>
+        createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1)))
+      case ExistentialType(bs, restp) =>
+        createFromClonedSymbols(bs, restp)(newExistentialType)
+      case _ =>
+        tp
+    }
+
+    @tailrec private 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)
+      )
+
+    def apply(tp0: Type): Type = if (from.isEmpty) tp0 else {
+      val boundSyms             = tp0.boundSyms
+      val tp1                   = if (boundSyms.nonEmpty && (boundSyms exists from.contains)) renameBoundSyms(tp0) else tp0
+      val tp                    = mapOver(tp1)
+      def substFor(sym: Symbol) = subst(tp, sym, from, to)
+
+      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) =>
+          val tcon = substFor(sym)
+          if ((tp eq tcon) || args.isEmpty) tcon
+          else appliedType(tcon.typeConstructor, args)
+        case SingleType(NoPrefix, sym) =>
+          substFor(sym)
+        case _ =>
+          tp
+      }
+    }
+  }
+
+  /** A map to implement the `substSym` method. */
+  class SubstSymMap(from: List[Symbol], to: List[Symbol]) extends SubstMap(from, to) {
+    def this(pairs: (Symbol, Symbol)*) = this(pairs.toList.map(_._1), pairs.toList.map(_._2))
+
+    protected def toType(fromtp: Type, sym: Symbol) = fromtp match {
+      case TypeRef(pre, _, args) => copyTypeRef(fromtp, pre, sym, args)
+      case SingleType(pre, _) => singleType(pre, sym)
+    }
+    @tailrec private 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)
+      )
+    private def substFor(sym: Symbol) = subst(sym, from, to)
+
+    override def apply(tp: Type): Type = (
+      if (from.isEmpty) tp
+      else tp match {
+        case TypeRef(pre, sym, args) if pre ne NoPrefix =>
+          val newSym = substFor(sym)
+          // mapOver takes care of subst'ing in args
+          mapOver ( if (sym eq newSym) tp else copyTypeRef(tp, pre, newSym, args) )
+        // assert(newSym.typeParams.length == sym.typeParams.length, "typars mismatch in SubstSymMap: "+(sym, sym.typeParams, newSym, newSym.typeParams))
+        case SingleType(pre, sym) if pre ne NoPrefix =>
+          val newSym = substFor(sym)
+          mapOver( if (sym eq newSym) tp else singleType(pre, newSym) )
+        case _ =>
+          super.apply(tp)
+      }
+      )
+
+    object mapTreeSymbols extends TypeMapTransformer {
+      val strictCopy = newStrictTreeCopier
+
+      def termMapsTo(sym: Symbol) = from indexOf sym match {
+        case -1   => None
+        case idx  => Some(to(idx))
+      }
+
+      // if tree.symbol is mapped to another symbol, passes the new symbol into the
+      // constructor `trans` and sets the symbol and the type on the resulting tree.
+      def transformIfMapped(tree: Tree)(trans: Symbol => Tree) = termMapsTo(tree.symbol) match {
+        case Some(toSym) => trans(toSym) setSymbol toSym setType tree.tpe
+        case None => tree
+      }
+
+      // changes trees which refer to one of the mapped symbols. trees are copied before attributes are modified.
+      override def transform(tree: Tree) = {
+        // super.transform maps symbol references in the types of `tree`. it also copies trees where necessary.
+        super.transform(tree) match {
+          case id @ Ident(_) =>
+            transformIfMapped(id)(toSym =>
+              strictCopy.Ident(id, toSym.name))
+
+          case sel @ Select(qual, name) =>
+            transformIfMapped(sel)(toSym =>
+              strictCopy.Select(sel, qual, toSym.name))
+
+          case tree => tree
+        }
+      }
+    }
+    override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
+      mapTreeSymbols.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) =>
+            from indexOf tree.symbol match {
+              case -1   => super.transform(tree)
+              case idx  =>
+                val totpe = to(idx)
+                if (totpe.isStable) tree.duplicate setType totpe
+                else giveup()
+            }
+          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 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)
+  }
+
+  /** Note: This map is needed even for non-dependent method types, despite what the name might imply.
+    */
+  class InstantiateDependentMap(params: List[Symbol], actuals0: List[Type]) extends TypeMap with KeepOnlyTypeConstraints {
+    private val actuals      = actuals0.toIndexedSeq
+    private val existentials = new Array[Symbol](actuals.size)
+    def existentialsNeeded: List[Symbol] = existentials.filter(_ ne null).toList
+
+    private object StableArg {
+      def unapply(param: Symbol) = Arg unapply param map actuals filter (tp =>
+        tp.isStable && (tp.typeSymbol != NothingClass)
+        )
+    }
+    private object Arg {
+      def unapply(param: Symbol) = Some(params indexOf param) filter (_ >= 0)
+    }
+
+    def apply(tp: Type): Type = mapOver(tp) match {
+      // unsound to replace args by unstable actual #3873
+      case SingleType(NoPrefix, StableArg(arg)) => arg
+      // (soundly) expand type alias selections on implicit arguments,
+      // see depmet_implicit_oopsla* test cases -- typically, `param.isImplicit`
+      case tp1 @ TypeRef(SingleType(NoPrefix, Arg(pid)), sym, targs) =>
+        val arg = actuals(pid)
+        val res = typeRef(arg, sym, targs)
+        if (res.typeSymbolDirect.isAliasType) res.dealias else tp1
+      // don't return the original `tp`, which may be different from `tp1`,
+      // due to dropping annotations
+      case tp1 => tp1
+    }
+
+    /* Return the type symbol for referencing a parameter inside the existential quantifier.
+     * (Only needed if the actual is unstable.)
+     */
+    private def existentialFor(pid: Int) = {
+      if (existentials(pid) eq null) {
+        val param = params(pid)
+        existentials(pid) = (
+          param.owner.newExistential(param.name.toTypeName append nme.SINGLETON_SUFFIX, param.pos, param.flags)
+            setInfo singletonBounds(actuals(pid))
+          )
+      }
+      existentials(pid)
+    }
+
+    //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 = {
+      // TODO: this should be simplified; in the stable case, one can
+      // probably just use an Ident to the tree.symbol.
+      //
+      // @PP: That leads to failure here, where stuff no longer has type
+      // 'String @Annot("stuff")' but 'String @Annot(x)'.
+      //
+      //   def m(x: String): String @Annot(x) = x
+      //   val stuff = m("stuff")
+      //
+      // (TODO cont.) Why an existential in the non-stable case?
+      //
+      // @PP: In the following:
+      //
+      //   def m = { val x = "three" ; val y: String @Annot(x) = x; y }
+      //
+      // m is typed as 'String @Annot(x) forSome { val x: String }'.
+      //
+      // Both examples are from run/constrained-types.scala.
+      object treeTrans extends Transformer {
+        override def transform(tree: Tree): Tree = tree.symbol match {
+          case StableArg(actual) =>
+            gen.mkAttributedQualifier(actual, tree.symbol)
+          case Arg(pid) =>
+            val sym = existentialFor(pid)
+            Ident(sym) copyAttrs tree setType typeRef(NoPrefix, sym, Nil)
+          case _ =>
+            super.transform(tree)
+        }
+      }
+      treeTrans transform arg
+    }
+  }
+
+  /** 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(bounds))
+      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
+      }
+      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)
+
+      arg
+    }
+  }
+
+  /** A map to implement the `filter` method. */
+  class FilterTypeCollector(p: Type => Boolean) extends TypeCollector[List[Type]](Nil) {
+    override def collect(tp: Type) = super.collect(tp).reverse
+
+    def traverse(tp: Type) {
+      if (p(tp)) result ::= tp
+      mapOver(tp)
+    }
+  }
+
+  /** A map to implement the `collect` method. */
+  class CollectTypeCollector[T](pf: PartialFunction[Type, T]) extends TypeCollector[List[T]](Nil) {
+    override def collect(tp: Type) = super.collect(tp).reverse
+
+    def traverse(tp: Type) {
+      if (pf.isDefinedAt(tp)) result ::= pf(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)
+      }
+    }
+  }
+
+  object adaptToNewRunMap extends TypeMap {
+
+    private def adaptToNewRun(pre: Type, sym: Symbol): Symbol = {
+      if (phase.flatClasses || sym.isRootSymbol || (pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass)
+        sym
+      else if (sym.isModuleClass) {
+        val sourceModule1 = adaptToNewRun(pre, sym.sourceModule)
+
+        sourceModule1.moduleClass orElse sourceModule1.initialize.moduleClass orElse {
+          val msg = "Cannot adapt module class; sym = %s, sourceModule = %s, sourceModule.moduleClass = %s => sourceModule1 = %s, sourceModule1.moduleClass = %s"
+          debuglog(msg.format(sym, sym.sourceModule, sym.sourceModule.moduleClass, sourceModule1, sourceModule1.moduleClass))
+          sym
+        }
+      }
+      else {
+        var rebind0 = pre.findMember(sym.name, BRIDGE, 0, stableOnly = true) orElse {
+          if (sym.isAliasType) throw missingAliasException
+          devWarning(s"$pre.$sym no longer exist at phase $phase")
+          throw new MissingTypeControl // For build manager and presentation compiler purposes
+        }
+        /** 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)) {
+          debuglog("ADAPT1 pre = "+pre+", sym = "+sym.fullLocationString+", rebind = "+rebind0.fullLocationString)
+          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)
+          debuglog(
+            "ADAPT2 pre = " + pre +
+              ", bcs.head = " + bcs.head +
+              ", sym = " + sym.fullLocationString +
+              ", rebind = " + rebind0.fullLocationString
+          )
+        }
+        rebind0.suchThat(sym => sym.isType || sym.isStable) orElse {
+          debuglog("" + phase + " " +phase.flatClasses+sym.owner+sym.name+" "+sym.isType)
+          throw new MalformedType(pre, sym.nameString)
+        }
+      }
+    }
+    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)
+          try {
+            val sym1 = adaptToNewRun(pre1, sym)
+            if ((pre1 eq pre) && (sym1 eq sym)) tp
+            else singleType(pre1, sym1)
+          } catch {
+            case _: MissingTypeControl =>
+              tp
+          }
+        }
+      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) {
+              devWarning(s"adapt to new run failed: pre=$pre pre1=$pre1 sym=$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
+    }
+  }
+
+}
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala b/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala
new file mode 100644
index 0000000000..263b0f5a3e
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/tpe/TypeToStrings.scala
@@ -0,0 +1,29 @@
+package scala.reflect
+package internal
+package tpe
+
+private[internal] trait TypeToStrings {
+  self: SymbolTable =>
+
+  /** The maximum number of recursions allowed in toString
+    */
+  final val maxTostringRecursions = 50
+
+  private var tostringRecursions = 0
+
+  protected def typeToString(tpe: Type): String =
+    if (tostringRecursions >= maxTostringRecursions) {
+      devWarning("Exceeded recursion depth attempting to print " + util.shortClassOfInstance(tpe))
+      if (settings.debug.value)
+        (new Throwable).printStackTrace
+
+      "..."
+    }
+    else
+      try {
+        tostringRecursions += 1
+        tpe.safeToString
+      } finally {
+        tostringRecursions -= 1
+      }
+}