Merge remote-tracking branch 'scala/master' into fix-merge-3018

Conflicts:
	src/compiler/scala/tools/nsc/typechecker/Typers.scala

14 files changed, 601 insertions, 460 deletions

diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
index 92bfe6e0fe..1cd3e0ec4b 100644
--- a/src/compiler/scala/tools/nsc/Global.scala
+++ b/src/compiler/scala/tools/nsc/Global.scala
@@ -135,6 +135,8 @@ class Global(var currentSettings: Settings, var reporter: Reporter)
     val global: Global.this.type = Global.this
   } with OverridingPairs
 
+  type SymbolPair = overridingPairs.SymbolPair
+
   // Optimizer components
 
   /** ICode analysis for optimization */
diff --git a/src/compiler/scala/tools/nsc/transform/Erasure.scala b/src/compiler/scala/tools/nsc/transform/Erasure.scala
index 2d005b26e3..e2902a74b8 100644
--- a/src/compiler/scala/tools/nsc/transform/Erasure.scala
+++ b/src/compiler/scala/tools/nsc/transform/Erasure.scala
@@ -371,17 +371,14 @@ abstract class Erasure extends AddInterfaces
     val opc = enteringExplicitOuter {
       new overridingPairs.Cursor(root) {
         override def parents              = List(root.info.firstParent)
-        override def exclude(sym: Symbol) = !sym.isMethod || sym.isPrivate || super.exclude(sym)
+        override def exclude(sym: Symbol) = !sym.isMethod || super.exclude(sym)
       }
     }
 
     def compute(): (List[Tree], immutable.Set[Symbol]) = {
       while (opc.hasNext) {
-        val member = opc.overriding
-        val other  = opc.overridden
-        //println("bridge? " + member + ":" + member.tpe + member.locationString + " to " + other + ":" + other.tpe + other.locationString)//DEBUG
-        if (enteringExplicitOuter(!member.isDeferred))
-          checkPair(member, other)
+        if (enteringExplicitOuter(!opc.low.isDeferred))
+          checkPair(opc.currentPair)
 
         opc.next()
       }
@@ -438,8 +435,15 @@ abstract class Erasure extends AddInterfaces
       noclash
     }
 
-    def checkPair(member: Symbol, other: Symbol) {
-      val otpe = specialErasure(root)(other.tpe)
+    /** TODO - work through this logic with a fine-toothed comb, incorporating
+     *  into SymbolPairs where appropriate.
+     */
+    def checkPair(pair: SymbolPair) {
+      import pair._
+      val member = low
+      val other  = high
+      val otpe   = highErased
+
       val bridgeNeeded = exitingErasure (
         !member.isMacro &&
         !(other.tpe =:= member.tpe) &&
@@ -844,88 +848,75 @@ abstract class Erasure extends AddInterfaces
 
   /** The erasure transformer */
   class ErasureTransformer(unit: CompilationUnit) extends Transformer {
-    /** Emit an error if there is a double definition. This can happen if:
-     *
-     *  - A template defines two members with the same name and erased type.
-     *  - A template defines and inherits two members `m` with different types,
-     *    but their erased types are the same.
-     *  - A template inherits two members `m` with different types,
-     *    but their erased types are the same.
-     */
-    private def checkNoDoubleDefs(root: Symbol) {
-      def doubleDefError(sym1: Symbol, sym2: Symbol) {
-        // the .toString must also be computed at the earlier phase
-        val tpe1 = exitingRefchecks(root.thisType.memberType(sym1))
-        val tpe2 = exitingRefchecks(root.thisType.memberType(sym2))
-        if (!tpe1.isErroneous && !tpe2.isErroneous)
-          unit.error(
-          if (sym1.owner == root) sym1.pos else root.pos,
-          (if (sym1.owner == sym2.owner) "double definition:\n"
-           else if (sym1.owner == root) "name clash between defined and inherited member:\n"
-           else "name clash between inherited members:\n") +
-          sym1 + ":" + exitingRefchecks(tpe1.toString) +
-            (if (sym1.owner == root) "" else sym1.locationString) + " and\n" +
-          sym2 + ":" + exitingRefchecks(tpe2.toString) +
-            (if (sym2.owner == root) " at line " + (sym2.pos).line else sym2.locationString) +
-          "\nhave same type" +
-          (if (exitingRefchecks(tpe1 =:= tpe2)) "" else " after erasure: " + exitingPostErasure(sym1.tpe)))
-        sym1.setInfo(ErrorType)
+    import overridingPairs.Cursor
+
+    private def doubleDefError(pair: SymbolPair) {
+      import pair._
+
+      if (!pair.isErroneous) {
+        val what = (
+          if (low.owner == high.owner) "double definition"
+          else if (low.owner == base) "name clash between defined and inherited member"
+          else "name clash between inherited members"
+        )
+        val when = if (exitingRefchecks(lowType matches highType)) "" else " after erasure: " + exitingPostErasure(highType)
+
+        unit.error(pos,
+          s"""|$what:
+              |${exitingRefchecks(highString)} and
+              |${exitingRefchecks(lowString)}
+              |have same type$when""".trim.stripMargin
+        )
       }
+      low setInfo ErrorType
+    }
 
-      val decls = root.info.decls
+    /** TODO - adapt SymbolPairs so it can be used here. */
+    private def checkNoDeclaredDoubleDefs(base: Symbol) {
+      val decls = base.info.decls
       var e = decls.elems
       while (e ne null) {
         if (e.sym.isTerm) {
-          var e1 = decls.lookupNextEntry(e)
+          var e1 = decls lookupNextEntry e
           while (e1 ne null) {
-            if (exitingPostErasure(e1.sym.info =:= e.sym.info)) doubleDefError(e.sym, e1.sym)
-            e1 = decls.lookupNextEntry(e1)
+            if (exitingPostErasure(e1.sym.info =:= e.sym.info))
+              doubleDefError(new SymbolPair(base, e.sym, e1.sym))
+
+            e1 = decls lookupNextEntry e1
           }
         }
         e = e.next
       }
+    }
 
-      val opc = new overridingPairs.Cursor(root) {
+    /** Emit an error if there is a double definition. This can happen if:
+     *
+     *  - A template defines two members with the same name and erased type.
+     *  - A template defines and inherits two members `m` with different types,
+     *    but their erased types are the same.
+     *  - A template inherits two members `m` with different types,
+     *    but their erased types are the same.
+     */
+    private def checkNoDoubleDefs(root: Symbol) {
+      checkNoDeclaredDoubleDefs(root)
+      object opc extends Cursor(root) {
+        // specialized members have no type history before 'specialize', causing double def errors for curried defs
         override def exclude(sym: Symbol): Boolean = (
-             !sym.isTerm || sym.isPrivate || super.exclude(sym)
-          // specialized members have no type history before 'specialize', causing double def errors for curried defs
+             sym.isType
+          || sym.isPrivate
+          || super.exclude(sym)
           || !sym.hasTypeAt(currentRun.refchecksPhase.id)
         )
-
-        override def matches(sym1: Symbol, sym2: Symbol): Boolean =
-          exitingPostErasure(sym1.tpe =:= sym2.tpe)
+        override def matches(sym1: Symbol, sym2: Symbol) = true
       }
-      while (opc.hasNext) {
-        if (!exitingRefchecks(
-              root.thisType.memberType(opc.overriding) matches
-              root.thisType.memberType(opc.overridden))) {
-          debuglog("" + opc.overriding.locationString + " " +
-                     opc.overriding.infosString +
-                     opc.overridden.locationString + " " +
-                     opc.overridden.infosString)
-          doubleDefError(opc.overriding, opc.overridden)
-        }
-        opc.next()
+      def sameTypeAfterErasure(pair: SymbolPair) = {
+        import pair._
+        log(s"Considering for erasure clash:\n$pair")
+        !exitingRefchecks(lowType matches highType) && exitingPostErasure(low.tpe =:= high.tpe)
       }
+      opc.iterator filter sameTypeAfterErasure foreach doubleDefError
     }
 
-/*
-      for (bc <- root.info.baseClasses.tail; other <- bc.info.decls.toList) {
-        if (other.isTerm && !other.isConstructor && !(other hasFlag (PRIVATE | BRIDGE))) {
-          for (member <- root.info.nonPrivateMember(other.name).alternatives) {
-            if (member != other &&
-                !(member hasFlag BRIDGE) &&
-                exitingErasure(member.tpe =:= other.tpe) &&
-                !exitingRefchecks(
-                  root.thisType.memberType(member) matches root.thisType.memberType(other))) {
-              debuglog("" + member.locationString + " " + member.infosString + other.locationString + " " + other.infosString);
-              doubleDefError(member, other)
-            }
-          }
-        }
-      }
-*/
-
     /**  Add bridge definitions to a template. This means:
      *
      *   If there is a concrete member `m` which overrides a member in a base
@@ -940,7 +931,6 @@ abstract class Erasure extends AddInterfaces
      */
     private def bridgeDefs(owner: Symbol): (List[Tree], immutable.Set[Symbol]) = {
       assert(phase == currentRun.erasurePhase, phase)
-      debuglog("computing bridges for " + owner)
       new ComputeBridges(unit, owner) compute()
     }
 
diff --git a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
index 2610679542..4222c4d8c8 100644
--- a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
+++ b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
@@ -6,221 +6,33 @@
 package scala.tools.nsc
 package transform
 
-import scala.collection.mutable
 import symtab.Flags._
-import util.HashSet
-import scala.annotation.tailrec
+import scala.reflect.internal.SymbolPairs
 
 /** A class that yields a kind of iterator (`Cursor`),
- *  which yields all pairs of overriding/overridden symbols
- *  that are visible in some baseclass, unless there's a parent class
- *  that already contains the same pairs.
- *  @author Martin Odersky
- *  @version 1.0
+ *  which yields pairs of corresponding symbols visible in some base class,
+ *  unless there's a parent class that already contains the same pairs.
+ *  Most of the logic is in SymbolPairs, which contains generic
+ *  pair-oriented traversal logic.
  */
-abstract class OverridingPairs {
-
-  val global: Global
+abstract class OverridingPairs extends SymbolPairs {
   import global._
 
-  /** The cursor class
-   *  @param base   the base class that contains the overriding pairs
-   */
-  class Cursor(base: Symbol) {
-
-    private val self = base.thisType
-
-    /** Symbols to exclude: Here these are constructors, private locals,
-     *  and hidden symbols, including bridges. But it may be refined in subclasses.
-     *
-     */
-    protected def exclude(sym: Symbol): Boolean =
-      sym.isConstructor || sym.isPrivateLocal || sym.isArtifact
-
-    /** The parents of base (may also be refined).
-     */
-    protected def parents: List[Type] = base.info.parents
-
-    /** Does `sym1` match `sym2` so that it qualifies as overriding.
-     *  Types always match. Term symbols match if their membertypes
-     *  relative to <base>.this do
-     */
-    protected def matches(sym1: Symbol, sym2: Symbol): Boolean = {
-      def tp_s(s: Symbol) = self.memberType(s) + "/" + self.memberType(s).getClass
-      val result = sym1.isType || (self.memberType(sym1) matches self.memberType(sym2))
-      debuglog("overriding-pairs? %s matches %s (%s vs. %s) == %s".format(
-        sym1.fullLocationString, sym2.fullLocationString, tp_s(sym1), tp_s(sym2), result))
-
-      result
-    }
+  class Cursor(base: Symbol) extends super.Cursor(base) {
+    lazy val relatively = new RelativeTo(base.thisType)
 
-    /** An implementation of BitSets as arrays (maybe consider collection.BitSet
-     *  for that?) The main purpose of this is to implement
-     *  intersectionContainsElement efficiently.
+    /** Symbols to exclude: Here these are constructors and private/artifact symbols,
+     *  including bridges. But it may be refined in subclasses.
      */
-    private type BitSet = Array[Int]
-
-    private def include(bs: BitSet, n: Int) {
-      val nshifted = n >> 5
-      val nmask = 1 << (n & 31)
-      bs(nshifted) = bs(nshifted) | nmask
-    }
-
-    /** Implements `bs1 * bs2 * {0..n} != 0.
-     *  Used in hasCommonParentAsSubclass */
-    private def intersectionContainsElementLeq(bs1: BitSet, bs2: BitSet, n: Int): Boolean = {
-      val nshifted = n >> 5
-      val nmask = 1 << (n & 31)
-      var i = 0
-      while (i < nshifted) {
-        if ((bs1(i) & bs2(i)) != 0) return true
-        i += 1
-      }
-      (bs1(nshifted) & bs2(nshifted) & (nmask | nmask - 1)) != 0
-    }
-
-    /** The symbols that can take part in an overriding pair */
-    private val decls = newScope
+    override protected def exclude(sym: Symbol) = (sym hasFlag PRIVATE | ARTIFACT) || sym.isConstructor
 
-    // fill `decls` with overriding shadowing overridden */
-    { def fillDecls(bcs: List[Symbol], deferredflag: Int) {
-        if (!bcs.isEmpty) {
-          fillDecls(bcs.tail, deferredflag)
-          var e = bcs.head.info.decls.elems
-          while (e ne null) {
-            if (e.sym.getFlag(DEFERRED) == deferredflag.toLong && !exclude(e.sym))
-              decls enter e.sym
-            e = e.next
-          }
-        }
-      }
-      // first, deferred (this wil need to change if we change lookup rules!
-      fillDecls(base.info.baseClasses, DEFERRED)
-      // then, concrete.
-      fillDecls(base.info.baseClasses, 0)
-    }
-
-    private val size = base.info.baseClasses.length
-
-    /** A map from baseclasses of <base> to ints, with smaller ints meaning lower in
-     *  linearization order.
-     *  symbols that are not baseclasses map to -1.
+    /** Types always match. Term symbols match if their member types
+     *  relative to `self` match.
      */
-    private val index = new mutable.HashMap[Symbol, Int] {
-      override def default(key: Symbol) = -1
-    }
-
-    // Note: overridingPairs can be called at odd instances by the Eclipse plugin
-    // Soemtimes symbols are not yet defined and we get missing keys.
-    // The implementation here is hardened so that it does not crash on a missing key.
-
-    { var i = 0
-      for (bc <- base.info.baseClasses) {
-        index(bc) = i
-        i += 1
-      }
-    }
-
-    /** A mapping from all base class indices to a bitset
-     *  which indicates whether parents are subclasses.
-     *
-     *   i \in subParents(j)   iff
-     *   exists p \in parents, b \in baseClasses:
-     *     i = index(p)
-     *     j = index(b)
-     *     p isSubClass b
-     *     p.baseType(b) == self.baseType(b)
-     */
-    private val subParents = new Array[BitSet](size)
-
-    { for (i <- List.range(0, size))
-        subParents(i) = new BitSet(size)
-      for (p <- parents) {
-        val pIndex = index(p.typeSymbol)
-        if (pIndex >= 0)
-          for (bc <- p.baseClasses)
-            if (p.baseType(bc) =:= self.baseType(bc)) {
-              val bcIndex = index(bc)
-              if (bcIndex >= 0)
-                include(subParents(bcIndex), pIndex)
-            }
-      }
-   }
-
-    /** Do `sym1` and `sym2` have a common subclass in `parents`?
-     *  In that case we do not follow their overriding pairs
-     */
-    private def hasCommonParentAsSubclass(sym1: Symbol, sym2: Symbol) = {
-      val index1 = index(sym1.owner)
-      (index1 >= 0) && {
-        val index2 = index(sym2.owner)
-        (index2 >= 0) && {
-          intersectionContainsElementLeq(
-            subParents(index1), subParents(index2), index1 min index2)
-        }
-      }
-    }
-
-    /** The scope entries that have already been visited as overridden
-     *  (maybe excluded because of hasCommonParentAsSubclass).
-     *  These will not appear as overriding
-     */
-    private val visited = HashSet[ScopeEntry]("visited", 64)
-
-    /** The current entry candidate for overriding
-     */
-    private var curEntry = decls.elems
-
-    /** The current entry candidate for overridden */
-    private var nextEntry = curEntry
-
-    /** The current candidate symbol for overriding */
-    var overriding: Symbol = _
-
-    /** If not null: The symbol overridden by overriding */
-    var overridden: Symbol = _
-
-    //@M: note that next is called once during object initialization
-    def hasNext: Boolean = curEntry ne null
-
-    @tailrec
-    final def next() {
-      if (curEntry ne null) {
-        overriding = curEntry.sym
-        if (nextEntry ne null) {
-          do {
-            do {
-              nextEntry = decls.lookupNextEntry(nextEntry)
-              /* DEBUG
-              if ((nextEntry ne null) &&
-                  !(nextEntry.sym hasFlag PRIVATE) &&
-                  !(overriding.owner == nextEntry.sym.owner) &&
-                  !matches(overriding, nextEntry.sym))
-                println("skipping "+overriding+":"+self.memberType(overriding)+overriding.locationString+" to "+nextEntry.sym+":"+self.memberType(nextEntry.sym)+nextEntry.sym.locationString)
-              */
-              } while ((nextEntry ne null) &&
-                     ((nextEntry.sym hasFlag PRIVATE) ||
-                      (overriding.owner == nextEntry.sym.owner) ||
-                      (!matches(overriding, nextEntry.sym)) ||
-                      (exclude(overriding))))
-            if (nextEntry ne null) visited addEntry nextEntry
-            // skip nextEntry if a class in `parents` is a subclass of the owners of both
-            // overriding and nextEntry.sym
-          } while ((nextEntry ne null) && (hasCommonParentAsSubclass(overriding, nextEntry.sym)))
-          if (nextEntry ne null) {
-            overridden = nextEntry.sym
-            //Console.println("yield: " + overriding + overriding.locationString + " / " + overridden + overridden.locationString);//DEBUG
-          } else {
-            do {
-              curEntry = curEntry.next
-            } while ((curEntry ne null) && (visited contains curEntry))
-            nextEntry = curEntry
-            next()
-          }
-        }
-      }
-    }
-
-    next()
+    override protected def matches(sym1: Symbol, sym2: Symbol) = sym1.isType || (
+         (sym1.owner != sym2.owner)
+      && !exclude(sym2)
+      && relatively.matches(sym1, sym2)
+    )
   }
 }
diff --git a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
index abc5363423..5e5619d034 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
@@ -329,6 +329,7 @@ trait Contexts { self: Analyzer =>
 
     /** The first error, if any, in the report buffer */
     def firstError: Option[AbsTypeError] = reportBuffer.firstError
+    def errors: Seq[AbsTypeError] = reportBuffer.errors
     /** Does the report buffer contain any errors? */
     def hasErrors = reportBuffer.hasErrors
 
diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
index 03f680525c..ccf4a5e46f 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
@@ -913,12 +913,13 @@ trait Infer extends Checkable {
       val targs  = exprTypeArgs(tvars, tparams, treeTp, pt, useWeaklyCompatible)
       def infer_s = map3(tparams, tvars, targs)((tparam, tvar, targ) => s"$tparam=$tvar/$targ") mkString ","
       printTyping(tree, s"infer expr instance from pt=$pt, $infer_s")
+      def targsStrict = if (targs eq null) null else targs mapConserve dropByName
 
       if (keepNothings || (targs eq null)) { //@M: adjustTypeArgs fails if targs==null, neg/t0226
-        substExpr(tree, tparams, targs, pt)
+        substExpr(tree, tparams, targsStrict, pt)
         List()
       } else {
-        val AdjustedTypeArgs.Undets(okParams, okArgs, leftUndet) = adjustTypeArgs(tparams, tvars, targs)
+        val AdjustedTypeArgs.Undets(okParams, okArgs, leftUndet) = adjustTypeArgs(tparams, tvars, targsStrict)
         def solved_s = map2(okParams, okArgs)((p, a) => s"$p=$a") mkString ","
         def undet_s = leftUndet match {
           case Nil => ""
diff --git a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala
index d60e61df1b..a9a7f6a954 100644
--- a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala
@@ -305,18 +305,23 @@ abstract class RefChecks extends InfoTransform with scala.reflect.internal.trans
       /* Check that all conditions for overriding `other` by `member`
        * of class `clazz` are met.
        */
-      def checkOverride(member: Symbol, other: Symbol) {
+      def checkOverride(pair: SymbolPair) {
+        import pair._
+        val member   = low
+        val other    = high
+        def memberTp = lowType
+        def otherTp  = highType
+
         debuglog("Checking validity of %s overriding %s".format(member.fullLocationString, other.fullLocationString))
 
-        def memberTp = self.memberType(member)
-        def otherTp  = self.memberType(other)
-        def noErrorType = other.tpe != ErrorType && member.tpe != ErrorType
+        def noErrorType = !pair.isErroneous
         def isRootOrNone(sym: Symbol) = sym != null && sym.isRoot || sym == NoSymbol
-        def isNeitherInClass = (member.owner != clazz) && (other.owner != clazz)
+        def isNeitherInClass = member.owner != pair.base && other.owner != pair.base
+
         def objectOverrideErrorMsg = (
-          "overriding " + other.fullLocationString + " with " + member.fullLocationString + ":\n" +
+          "overriding " + high.fullLocationString + " with " + low.fullLocationString + ":\n" +
           "an overriding object must conform to the overridden object's class bound" +
-          analyzer.foundReqMsg(classBoundAsSeen(member.tpe), classBoundAsSeen(other.tpe))
+          analyzer.foundReqMsg(pair.lowClassBound, pair.highClassBound)
         )
 
         def overrideErrorMsg(msg: String): String = {
@@ -460,79 +465,72 @@ abstract class RefChecks extends InfoTransform with scala.reflect.internal.trans
           }
         }
 
-        def checkOverrideTypes() {
-          if (other.isAliasType) {
-            //if (!member.typeParams.isEmpty) (1.5)  @MAT
-            //  overrideError("may not be parameterized");
-            //if (!other.typeParams.isEmpty)  (1.5)   @MAT
-            //  overrideError("may not override parameterized type");
-            // @M: substSym
-
-            if( !(sameLength(member.typeParams, other.typeParams) && (memberTp.substSym(member.typeParams, other.typeParams) =:= otherTp)) ) // (1.6)
-              overrideTypeError()
+        //if (!member.typeParams.isEmpty) (1.5)  @MAT
+        //  overrideError("may not be parameterized");
+        //if (!other.typeParams.isEmpty)  (1.5)   @MAT
+        //  overrideError("may not override parameterized type");
+        // @M: substSym
+        def checkOverrideAlias() {
+          if (pair.sameKind && lowType.substSym(low.typeParams, high.typeParams) =:= highType) ()
+          else overrideTypeError() // (1.6)
+        }
+        //if (!member.typeParams.isEmpty) // (1.7)  @MAT
+        //  overrideError("may not be parameterized");
+        def checkOverrideAbstract() {
+          if (!(highInfo.bounds containsType lowType)) { // (1.7.1)
+            overrideTypeError(); // todo: do an explaintypes with bounds here
+            explainTypes(_.bounds containsType _, highInfo, lowType)
           }
-          else if (other.isAbstractType) {
-            //if (!member.typeParams.isEmpty) // (1.7)  @MAT
-            //  overrideError("may not be parameterized");
-            val otherTp = self.memberInfo(other)
-
-            if (!(otherTp.bounds containsType memberTp)) { // (1.7.1)
-              overrideTypeError(); // todo: do an explaintypes with bounds here
-              explainTypes(_.bounds containsType _, otherTp, memberTp)
-            }
-
-            // check overriding (abstract type --> abstract type or abstract type --> concrete type member (a type alias))
-            // making an abstract type member concrete is like passing a type argument
-            val kindErrors = typer.infer.checkKindBounds(List(other), List(memberTp), self, member.owner) // (1.7.2)
-
-            if(!kindErrors.isEmpty)
+          // check overriding (abstract type --> abstract type or abstract type --> concrete type member (a type alias))
+          // making an abstract type member concrete is like passing a type argument
+          typer.infer.checkKindBounds(high :: Nil, lowType :: Nil, rootType, low.owner) match { // (1.7.2)
+            case Nil        =>
+            case kindErrors =>
               unit.error(member.pos,
                 "The kind of "+member.keyString+" "+member.varianceString + member.nameString+
                 " does not conform to the expected kind of " + other.defString + other.locationString + "." +
                 kindErrors.toList.mkString("\n", ", ", ""))
-
-            // check a type alias's RHS corresponds to its declaration
-            // this overlaps somewhat with validateVariance
-            if(member.isAliasType) {
-              // println("checkKindBounds" + ((List(member), List(memberTp.dealiasWiden), self, member.owner)))
-              val kindErrors = typer.infer.checkKindBounds(List(member), List(memberTp.dealiasWiden), self, member.owner)
-
-              if(!kindErrors.isEmpty)
+          }
+          // check a type alias's RHS corresponds to its declaration
+          // this overlaps somewhat with validateVariance
+          if (low.isAliasType) {
+            typer.infer.checkKindBounds(low :: Nil, lowType.normalize :: Nil, rootType, low.owner) match {
+              case Nil        =>
+              case kindErrors =>
                 unit.error(member.pos,
-                  "The kind of the right-hand side "+memberTp.dealiasWiden+" of "+member.keyString+" "+
-                  member.varianceString + member.nameString+ " does not conform to its expected kind."+
+                  "The kind of the right-hand side "+lowType.normalize+" of "+low.keyString+" "+
+                  low.varianceString + low.nameString+ " does not conform to its expected kind."+
                   kindErrors.toList.mkString("\n", ", ", ""))
-            } else if (member.isAbstractType) {
-              if (memberTp.isVolatile && !otherTp.bounds.hi.isVolatile)
-                overrideError("is a volatile type; cannot override a type with non-volatile upper bound")
             }
-          } else if (other.isTerm) {
-            other.cookJavaRawInfo() // #2454
-            val memberTp = self.memberType(member)
-            val otherTp = self.memberType(other)
-            if (!overridesTypeInPrefix(memberTp, otherTp, self)) { // 8
-              overrideTypeError()
-              explainTypes(memberTp, otherTp)
-            }
-
-            if (member.isStable && !otherTp.isVolatile) {
-              // (1.4), pt 2 -- member.isStable && memberTp.isVolatile started being possible after SI-6815
-              // (before SI-6815, !symbol.tpe.isVolatile was implied by symbol.isStable)
-              // TODO: allow overriding when @uncheckedStable?
-              if (memberTp.isVolatile)
-                overrideError("has a volatile type; cannot override a member with non-volatile type")
-              else memberTp.dealiasWiden.resultType match {
-                case rt: RefinedType if !(rt =:= otherTp) && !(checkedCombinations contains rt.parents) =>
-                  // might mask some inconsistencies -- check overrides
-                  checkedCombinations += rt.parents
-                  val tsym = rt.typeSymbol
-                  if (tsym.pos == NoPosition) tsym setPos member.pos
-                  checkAllOverrides(tsym, typesOnly = true)
-                case _ =>
-              }
+          }
+          else if (low.isAbstractType && lowType.isVolatile && !highInfo.bounds.hi.isVolatile)
+            overrideError("is a volatile type; cannot override a type with non-volatile upper bound")
+        }
+        def checkOverrideTerm() {
+          other.cookJavaRawInfo() // #2454
+          if (!overridesTypeInPrefix(lowType, highType, rootType)) { // 8
+            overrideTypeError()
+            explainTypes(lowType, highType)
+          }
+          if (low.isStable && !highType.isVolatile) {
+            if (lowType.isVolatile)
+              overrideError("has a volatile type; cannot override a member with non-volatile type")
+            else lowType.normalize.resultType match {
+              case rt: RefinedType if !(rt =:= highType) && !(checkedCombinations contains rt.parents) =>
+                // might mask some inconsistencies -- check overrides
+                checkedCombinations += rt.parents
+                val tsym = rt.typeSymbol
+                if (tsym.pos == NoPosition) tsym setPos member.pos
+                checkAllOverrides(tsym, typesOnly = true)
+              case _ =>
             }
           }
         }
+        def checkOverrideTypes() {
+          if (high.isAliasType)         checkOverrideAlias()
+          else if (high.isAbstractType) checkOverrideAbstract()
+          else if (high.isTerm)         checkOverrideTerm()
+        }
 
         def checkOverrideDeprecated() {
           if (other.hasDeprecatedOverridingAnnotation) {
@@ -545,8 +543,8 @@ abstract class RefChecks extends InfoTransform with scala.reflect.internal.trans
 
       val opc = new overridingPairs.Cursor(clazz)
       while (opc.hasNext) {
-        //Console.println(opc.overriding/* + ":" + opc.overriding.tpe*/ + " in "+opc.overriding.fullName + " overrides " + opc.overridden/* + ":" + opc.overridden.tpe*/ + " in "+opc.overridden.fullName + "/"+ opc.overridden.hasFlag(DEFERRED));//debug
-        if (!opc.overridden.isClass) checkOverride(opc.overriding, opc.overridden)
+        if (!opc.high.isClass)
+          checkOverride(opc.currentPair)
 
         opc.next()
       }
@@ -585,10 +583,10 @@ abstract class RefChecks extends InfoTransform with scala.reflect.internal.trans
 
         def ignoreDeferred(member: Symbol) = (
           (member.isAbstractType && !member.isFBounded) || (
-            member.isJavaDefined &&
             // the test requires exitingErasure so shouldn't be
             // done if the compiler has no erasure phase available
-            (currentRun.erasurePhase == NoPhase || javaErasedOverridingSym(member) != NoSymbol)
+               member.isJavaDefined
+            && (currentRun.erasurePhase == NoPhase || javaErasedOverridingSym(member) != NoSymbol)
           )
         )
 
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 58c658ee8a..de684e69ad 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -79,12 +79,25 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
       case SilentResultValue(value) if !p(value) => SilentTypeError(TypeErrorWrapper(new TypeError(NoPosition, "!p")))
       case _                                     => this
   }
-    @inline final def orElse[T1 >: T](f: AbsTypeError => T1): T1 = this match {
+    @inline final def orElse[T1 >: T](f: Seq[AbsTypeError] => T1): T1 = this match {
       case SilentResultValue(value) => value
-      case SilentTypeError(err)     => f(err)
+      case s : SilentTypeError      => f(s.reportableErrors)
     }
   }
-  case class SilentTypeError(err: AbsTypeError) extends SilentResult[Nothing] { }
+  class SilentTypeError private(val errors: List[AbsTypeError]) extends SilentResult[Nothing] {
+    def err: AbsTypeError = errors.head
+    def reportableErrors = errors match {
+      case (e1: AmbiguousImplicitTypeError) +: _ =>
+        List(e1) // DRYer error reporting for neg/t6436b.scala
+      case all =>
+        all
+    }
+  }
+  object SilentTypeError {
+    def apply(errors: AbsTypeError*): SilentTypeError = new SilentTypeError(errors.toList)
+    def unapply(error: SilentTypeError): Option[AbsTypeError] = error.errors.headOption
+  }
+
   case class SilentResultValue[+T](value: T) extends SilentResult[T] { }
 
   def newTyper(context: Context): Typer = new NormalTyper(context)
@@ -682,14 +695,13 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
           context.undetparams = context1.undetparams
           context.savedTypeBounds = context1.savedTypeBounds
           context.namedApplyBlockInfo = context1.namedApplyBlockInfo
-          context1.firstError match {
-            case Some(err) =>
-              stopStats()
-              SilentTypeError(err)
-            case None =>
-              // If we have a successful result, emit any warnings it created.
-              context1.flushAndIssueWarnings()
-              SilentResultValue(result)
+          if (context1.hasErrors) {
+            stopStats()
+            SilentTypeError(context1.errors: _*)
+          } else {
+            // If we have a successful result, emit any warnings it created.
+            context1.flushAndIssueWarnings()
+            SilentResultValue(result)
           }
         } else {
           assert(context.bufferErrors || isPastTyper, "silent mode is not available past typer")
@@ -1258,9 +1270,9 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
           reportError
       }
 
-      silent(_.adaptToMember(qual, HasMember(name), reportAmbiguous = false)) orElse (err =>
+      silent(_.adaptToMember(qual, HasMember(name), reportAmbiguous = false)) orElse (errs =>
         onError {
-          if (reportAmbiguous) context issue err
+          if (reportAmbiguous) errs foreach (context issue _)
           setError(tree)
         }
       )
@@ -2392,9 +2404,16 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
       if (pat1.tpe.paramSectionCount > 0)
         pat1 modifyType (_.finalResultType)
 
-      for (bind @ Bind(name, _) <- cdef.pat)
-        if (name.toTermName != nme.WILDCARD && bind.symbol != null && bind.symbol != NoSymbol)
-          namer.enterIfNotThere(bind.symbol)
+      for (bind @ Bind(name, _) <- cdef.pat) {
+        val sym = bind.symbol
+        if (name.toTermName != nme.WILDCARD && sym != null) {
+          if (sym == NoSymbol) {
+            if (context.scope.lookup(name) == NoSymbol)
+              namer.enterInScope(context.owner.newErrorSymbol(name))
+          } else
+            namer.enterIfNotThere(sym)
+        }
+      }
 
       val guard1: Tree = if (cdef.guard == EmptyTree) EmptyTree
                          else typed(cdef.guard, BooleanTpe)
@@ -2875,7 +2894,7 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
         } else {
           pt baseType FunctionSymbol match {
             case TypeRef(_, FunctionSymbol, args :+ res) => (args, res)
-            case _                                       => (fun.vparams map (_ => NoType), WildcardType)
+            case _                                       => (fun.vparams map (_ => if (pt == ErrorType) ErrorType else NoType), WildcardType)
           }
         }
 
@@ -3964,7 +3983,7 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
           }
         }
       }
-      def wrapErrors(tree: Tree, typeTree: Typer => Tree): Tree = silent(typeTree) orElse (err => DynamicRewriteError(tree, err))
+      def wrapErrors(tree: Tree, typeTree: Typer => Tree): Tree = silent(typeTree) orElse (err => DynamicRewriteError(tree, err.head))
     }
 
     def typed1(tree: Tree, mode: Mode, pt: Type): Tree = {
@@ -4351,7 +4370,7 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
       def tryTypedApply(fun: Tree, args: List[Tree]): Tree = {
         val start = if (Statistics.canEnable) Statistics.startTimer(failedApplyNanos) else null
 
-        def onError(typeError: AbsTypeError): Tree = {
+        def onError(typeErrors: Seq[AbsTypeError]): Tree = {
           if (Statistics.canEnable) Statistics.stopTimer(failedApplyNanos, start)
 
           // If the problem is with raw types, copnvert to existentials and try again.
@@ -4376,13 +4395,13 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
             case TypeApply(fun, args)               => treesInResult(fun) ++ args.flatMap(treesInResult)
             case _                                  => Nil
           })
-          def errorInResult(tree: Tree) = treesInResult(tree) exists (_.pos == typeError.errPos)
+          def errorInResult(tree: Tree) = treesInResult(tree) exists (err => typeErrors.exists(_.errPos == err.pos))
 
-          val retry = (typeError.errPos != null) && (fun :: tree :: args exists errorInResult)
+          val retry = (typeErrors.forall(_.errPos != null)) && (fun :: tree :: args exists errorInResult)
           typingStack.printTyping({
             val funStr = ptTree(fun) + " and " + (args map ptTree mkString ", ")
             if (retry) "second try: " + funStr
-            else "no second try: " + funStr + " because error not in result: " + typeError.errPos+"!="+tree.pos
+            else "no second try: " + funStr + " because error not in result: " + typeErrors.head.errPos+"!="+tree.pos
           })
           if (retry) {
             val Select(qual, name) = fun
@@ -4398,7 +4417,7 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
               case _ => ()
             }
           }
-          issue(typeError)
+          typeErrors foreach issue
           setError(treeCopy.Apply(tree, fun, args))
         }
 
@@ -4450,8 +4469,12 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper
               tryTypedApply(fun2, args)
             else
               doTypedApply(tree, fun2, args, mode, pt)
-          case SilentTypeError(err) =>
-            onError({ issue(err); setError(tree) })
+          case err: SilentTypeError =>
+            onError({
+              err.reportableErrors foreach issue
+              args foreach (arg => typed(arg, mode, ErrorType))
+              setError(tree)
+            })
         }
       }
 
diff --git a/src/library/scala/annotation/implicitNotFound.scala b/src/library/scala/annotation/implicitNotFound.scala
index bbde90cebb..eeedcb014e 100644
--- a/src/library/scala/annotation/implicitNotFound.scala
+++ b/src/library/scala/annotation/implicitNotFound.scala
@@ -9,8 +9,11 @@
 package scala.annotation
 
 /**
- * An annotation that specifies the error message that is emitted when the compiler
- * cannot find an implicit value of the annotated type.
+ * To customize the error message that's emitted when an implicit of type
+ * C[T1,..., TN] cannot be found, annotate the class C with @implicitNotFound.
+ * Assuming C has type parameters X1,..., XN, the error message will be the
+ * result of replacing all occurrences of ${Xi} in the string msg with the
+ * string representation of the corresponding type argument Ti. *
  *
  * @author Adriaan Moors
  * @since 2.8.1
diff --git a/src/reflect/scala/reflect/internal/Definitions.scala b/src/reflect/scala/reflect/internal/Definitions.scala
index 5970514102..99aad4f057 100644
--- a/src/reflect/scala/reflect/internal/Definitions.scala
+++ b/src/reflect/scala/reflect/internal/Definitions.scala
@@ -709,7 +709,82 @@ trait Definitions extends api.StandardDefinitions {
       case NullaryMethodType(restpe) => finalResultType(restpe)
       case _                         => tp
     }
+    /** Similarly, putting all the isStable logic in one place.
+     *  This makes it like 1000x easier to see the overall logic
+     *  of the method.
+     */
+    def isStable(tp: Type): Boolean = tp match {
+      case _: SingletonType                             => true
+      case NoPrefix                                     => true
+      case TypeRef(_, NothingClass | SingletonClass, _) => true
+      case TypeRef(_, sym, _) if sym.isAbstractType     => tp.bounds.hi.typeSymbol isSubClass SingletonClass
+      case TypeRef(pre, sym, _) if sym.isModuleClass    => isStable(pre)
+      case TypeRef(_, _, _) if tp ne tp.dealias         => isStable(tp.dealias)
+      case TypeVar(origin, _)                           => isStable(origin)
+      case AnnotatedType(_, atp, _)                     => isStable(atp)    // Really?
+      case _: SimpleTypeProxy                           => isStable(tp.underlying)
+      case _                                            => false
+    }
+    def isVolatile(tp: Type): Boolean = {
+      // need to be careful not to fall into an infinite recursion here
+      // because volatile checking is done before all cycles are detected.
+      // the case to avoid is an abstract type directly or
+      // indirectly upper-bounded by itself. See #2918
+      def isVolatileAbstractType: Boolean = {
+        def sym = tp.typeSymbol
+        def volatileUpperBound = isVolatile(tp.bounds.hi)
+        def safeIsVolatile = (
+          if (volatileRecursions < TypeConstants.LogVolatileThreshold)
+            volatileUpperBound
+          // we can return true when pendingVolatiles contains sym, because
+          // a cycle will be detected afterwards and an error will result anyway.
+          else pendingVolatiles(sym) || {
+            pendingVolatiles += sym
+            try volatileUpperBound finally pendingVolatiles -= sym
+          }
+        )
+        volatileRecursions += 1
+        try safeIsVolatile finally volatileRecursions -= 1
+      }
+      /** A refined type P1 with ... with Pn { decls } is volatile if
+       *  one of the parent types Pi is an abstract type, and
+       *  either i > 1, or decls or a following parent Pj, j > 1, contributes
+       *  an abstract member.
+       *  A type contributes an abstract member if it has an abstract member which
+       *  is also a member of the whole refined type. A scope `decls` contributes
+       *  an abstract member if it has an abstract definition which is also
+       *  a member of the whole type.
+       */
+      def isVolatileRefinedType: Boolean = {
+        val RefinedType(parents, decls)         = tp
+        def isVisibleDeferred(m: Symbol)        = m.isDeferred && ((tp nonPrivateMember m.name).alternatives contains m)
+        def contributesAbstractMembers(p: Type) = p.deferredMembers exists isVisibleDeferred
+        def dropConcreteParents                 = parents dropWhile (p => !p.typeSymbol.isAbstractType)
+
+        (parents exists isVolatile) || {
+          dropConcreteParents match {
+            case Nil => false
+            case ps  => (ps ne parents) || (ps.tail exists contributesAbstractMembers) || (decls exists isVisibleDeferred)
+          }
+        }
+      }
+
+      tp match {
+        case ThisType(_)                              => false
+        case SingleType(_, sym)                       => isVolatile(tp.underlying) && (sym.hasVolatileType || !sym.isStable)
+        case NullaryMethodType(restpe)                => isVolatile(restpe)
+        case PolyType(_, restpe)                      => isVolatile(restpe)
+        case TypeRef(_, _, _) if tp ne tp.dealias     => isVolatile(tp.dealias)
+        case TypeRef(_, sym, _) if sym.isAbstractType => isVolatileAbstractType
+        case RefinedType(_, _)                        => isVolatileRefinedType
+        case TypeVar(origin, _)                       => isVolatile(origin)
+        case _: SimpleTypeProxy                       => isVolatile(tp.underlying)
+        case _                                        => false
+      }
+    }
 
+    private[this] var volatileRecursions: Int = 0
+    private[this] val pendingVolatiles = mutable.HashSet[Symbol]()
     def abstractFunctionForFunctionType(tp: Type) = {
       assert(isFunctionType(tp), tp)
       abstractFunctionType(tp.typeArgs.init, tp.typeArgs.last)
diff --git a/src/reflect/scala/reflect/internal/Kinds.scala b/src/reflect/scala/reflect/internal/Kinds.scala
index d1c215713e..d48a6c6322 100644
--- a/src/reflect/scala/reflect/internal/Kinds.scala
+++ b/src/reflect/scala/reflect/internal/Kinds.scala
@@ -185,6 +185,7 @@ trait Kinds {
           )
         }
         else {
+          hkarg.initialize // SI-7902 otherwise hkarg.typeParams yields List(NoSymbol)!
           debuglog("checkKindBoundsHK recursing to compare params of "+ hkparam +" with "+ hkarg)
           kindErrors ++= checkKindBoundsHK(
             hkarg.typeParams,
diff --git a/src/reflect/scala/reflect/internal/SymbolPairs.scala b/src/reflect/scala/reflect/internal/SymbolPairs.scala
new file mode 100644
index 0000000000..b538648b36
--- /dev/null
+++ b/src/reflect/scala/reflect/internal/SymbolPairs.scala
@@ -0,0 +1,302 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2013 LAMP/EPFL
+ * @author Paul Phillips
+ */
+
+package scala
+package reflect
+package internal
+
+import scala.collection.mutable
+import Flags._
+import util.HashSet
+import scala.annotation.tailrec
+
+/** An abstraction for considering symbol pairs.
+ *  One of the greatest sources of compiler bugs is that symbols can
+ *  trivially lose their prefixes and turn into some completely different
+ *  type with the smallest of errors. It is the exception not the rule
+ *  that type comparisons are done correctly.
+ *
+ *  This offers a small step toward coherence with two abstractions
+ *  which come up over and over again:
+ *
+ *    RelativeTo: operations relative to a prefix
+ *    SymbolPair: two symbols being related somehow, plus the class
+ *       in which the relation is being performed
+ *
+ *  This is only a start, but it is a start.
+ */
+abstract class SymbolPairs {
+  val global: SymbolTable
+  import global._
+
+  /** Type operations relative to a prefix.  All operations work on Symbols,
+   *  and the types are the member types of those symbols in the prefix.
+   */
+  class RelativeTo(val prefix: Type) {
+    def this(clazz: Symbol) = this(clazz.thisType)
+    import scala.language.implicitConversions // geez, it even has to hassle me when it's private
+    private implicit def symbolToType(sym: Symbol): Type = prefix memberType sym
+
+    def erasureOf(sym: Symbol): Type         = erasure.erasure(sym)(sym: Type)
+    def signature(sym: Symbol): String       = sym defStringSeenAs (sym: Type)
+    def erasedSignature(sym: Symbol): String = sym defStringSeenAs erasureOf(sym)
+
+    def isSameType(sym1: Symbol, sym2: Symbol): Boolean    = sym1 =:= sym2
+    def isSubType(sym1: Symbol, sym2: Symbol): Boolean     = sym1 <:< sym2
+    def isSuperType(sym1: Symbol, sym2: Symbol): Boolean   = sym2 <:< sym1
+    def isSameErasure(sym1: Symbol, sym2: Symbol): Boolean = erasureOf(sym1) =:= erasureOf(sym2)
+    def matches(sym1: Symbol, sym2: Symbol): Boolean       = (sym1: Type) matches (sym2: Type)
+
+    override def toString = s"RelativeTo($prefix)"
+  }
+
+  /** Are types tp1 and tp2 equivalent seen from the perspective
+   *  of `baseClass`? For instance List[Int] and Seq[Int] are =:=
+   *  when viewed from IterableClass.
+   */
+  def sameInBaseClass(baseClass: Symbol)(tp1: Type, tp2: Type) =
+    (tp1 baseType baseClass) =:= (tp2 baseType baseClass)
+
+  case class SymbolPair(base: Symbol, low: Symbol, high: Symbol) {
+    def pos                 = if (low.owner == base) low.pos else if (high.owner == base) high.pos else base.pos
+    def self: Type          = base.thisType
+    def rootType: Type      = base.thisType
+
+    def lowType: Type       = self memberType low
+    def lowErased: Type     = erasure.specialErasure(base)(low.tpe)
+    def lowClassBound: Type = classBoundAsSeen(low.tpe.typeSymbol)
+
+    def highType: Type       = self memberType high
+    def highInfo: Type       = self memberInfo high
+    def highErased: Type     = erasure.specialErasure(base)(high.tpe)
+    def highClassBound: Type = classBoundAsSeen(high.tpe.typeSymbol)
+
+    def isErroneous = low.tpe.isErroneous || high.tpe.isErroneous
+    def sameKind    = sameLength(low.typeParams, high.typeParams)
+
+    private def classBoundAsSeen(tsym: Symbol) =
+      tsym.classBound.asSeenFrom(rootType, tsym.owner)
+
+    private def memberDefString(sym: Symbol, where: Boolean) = {
+      val def_s = (
+        if (sym.isConstructor) s"$sym: ${self memberType sym}"
+        else sym defStringSeenAs (self memberType sym)
+      )
+      def_s + whereString(sym)
+    }
+    /** A string like ' at line 55' if the symbol is defined in the class
+     *  under consideration, or ' in trait Foo' if defined elsewhere.
+     */
+    private def whereString(sym: Symbol) =
+      if (sym.owner == base) " at line " + sym.pos.line else sym.locationString
+
+    def lowString  = memberDefString(low, where = true)
+    def highString = memberDefString(high, where = true)
+
+    override def toString = sm"""
+      |Cursor(in $base) {
+      |   high  $highString
+      | erased  $highErased
+      |  infos  ${high.infosString}
+      |    low  $lowString
+      | erased  $lowErased
+      |  infos  ${low.infosString}
+      |}""".trim
+  }
+
+  /** The cursor class
+   *  @param base   the base class containing the participating symbols
+   */
+  abstract class Cursor(val base: Symbol) {
+    cursor =>
+
+      final val self  = base.thisType   // The type relative to which symbols are seen.
+    private val decls = newScope        // all the symbols which can take part in a pair.
+    private val size  = bases.length
+
+    /** A symbol for which exclude returns true will not appear as
+     *  either end of a pair.
+     */
+    protected def exclude(sym: Symbol): Boolean
+
+    /** Does `sym1` match `sym2` such that (sym1, sym2) should be
+     *  considered as a (lo, high) pair? Types always match. Term symbols
+     *  match if their member types relative to `self` match.
+     */
+    protected def matches(sym1: Symbol, sym2: Symbol): Boolean
+
+    /** The parents and base classes of `base`.  Can be refined in subclasses.
+     */
+    protected def parents: List[Type] = base.info.parents
+    protected def bases: List[Symbol] = base.info.baseClasses
+
+    /** An implementation of BitSets as arrays (maybe consider collection.BitSet
+     *  for that?) The main purpose of this is to implement
+     *  intersectionContainsElement efficiently.
+     */
+    private type BitSet = Array[Int]
+
+    /** A mapping from all base class indices to a bitset
+     *  which indicates whether parents are subclasses.
+     *
+     *   i \in subParents(j)   iff
+     *   exists p \in parents, b \in baseClasses:
+     *     i = index(p)
+     *     j = index(b)
+     *     p isSubClass b
+     *     p.baseType(b) == self.baseType(b)
+     */
+    private val subParents = new Array[BitSet](size)
+
+    /** A map from baseclasses of <base> to ints, with smaller ints meaning lower in
+     *  linearization order. Symbols that are not baseclasses map to -1.
+     */
+    private val index = new mutable.HashMap[Symbol, Int] { override def default(key: Symbol) = -1 }
+
+    /** The scope entries that have already been visited as highSymbol
+     *  (but may have been excluded via hasCommonParentAsSubclass.)
+     *  These will not appear as lowSymbol.
+     */
+    private val visited = HashSet[ScopeEntry]("visited", 64)
+
+    /** Initialization has to run now so decls is populated before
+     *  the declaration of curEntry.
+     */
+    init()
+
+    // The current low and high symbols; the high may be null.
+    private[this] var lowSymbol: Symbol  = _
+    private[this] var highSymbol: Symbol = _
+
+    // The current entry candidates for low and high symbol.
+    private[this] var curEntry  = decls.elems
+    private[this] var nextEntry = curEntry
+
+    // These fields are initially populated with a call to next().
+    next()
+
+    // populate the above data structures
+    private def init() {
+      // Fill `decls` with lower symbols shadowing higher ones
+      def fillDecls(bcs: List[Symbol], deferred: Boolean) {
+        if (!bcs.isEmpty) {
+          fillDecls(bcs.tail, deferred)
+          var e = bcs.head.info.decls.elems
+          while (e ne null) {
+            if (e.sym.initialize.isDeferred == deferred && !exclude(e.sym))
+              decls enter e.sym
+            e = e.next
+          }
+        }
+      }
+      var i = 0
+      for (bc <- bases) {
+        index(bc) = i
+        subParents(i) = new BitSet(size)
+        i += 1
+      }
+      for (p <- parents) {
+        val pIndex = index(p.typeSymbol)
+        if (pIndex >= 0)
+          for (bc <- p.baseClasses ; if sameInBaseClass(bc)(p, self)) {
+            val bcIndex = index(bc)
+            if (bcIndex >= 0)
+              include(subParents(bcIndex), pIndex)
+          }
+      }
+      // first, deferred (this will need to change if we change lookup rules!)
+      fillDecls(bases, deferred = true)
+      // then, concrete.
+      fillDecls(bases, deferred = false)
+    }
+
+    private def include(bs: BitSet, n: Int) {
+      val nshifted = n >> 5
+      val nmask    = 1 << (n & 31)
+      bs(nshifted) |= nmask
+    }
+
+    /** Implements `bs1 * bs2 * {0..n} != 0.
+     *  Used in hasCommonParentAsSubclass */
+    private def intersectionContainsElementLeq(bs1: BitSet, bs2: BitSet, n: Int): Boolean = {
+      val nshifted = n >> 5
+      val nmask = 1 << (n & 31)
+      var i = 0
+      while (i < nshifted) {
+        if ((bs1(i) & bs2(i)) != 0) return true
+        i += 1
+      }
+      (bs1(nshifted) & bs2(nshifted) & (nmask | nmask - 1)) != 0
+    }
+
+    /** Do `sym1` and `sym2` have a common subclass in `parents`?
+     *  In that case we do not follow their pairs.
+     */
+    private def hasCommonParentAsSubclass(sym1: Symbol, sym2: Symbol) = {
+      val index1 = index(sym1.owner)
+      (index1 >= 0) && {
+        val index2 = index(sym2.owner)
+        (index2 >= 0) && {
+          intersectionContainsElementLeq(
+            subParents(index1), subParents(index2), index1 min index2)
+        }
+      }
+    }
+
+    @tailrec private def advanceNextEntry() {
+      if (nextEntry ne null) {
+        nextEntry = decls lookupNextEntry nextEntry
+        if (nextEntry ne null) {
+          val high    = nextEntry.sym
+          val isMatch = matches(lowSymbol, high) && { visited addEntry nextEntry ; true } // side-effect visited on all matches
+
+          // skip nextEntry if a class in `parents` is a subclass of the
+          // owners of both low and high.
+          if (isMatch && !hasCommonParentAsSubclass(lowSymbol, high))
+            highSymbol = high
+          else
+            advanceNextEntry()
+        }
+      }
+    }
+    @tailrec private def advanceCurEntry() {
+      if (curEntry ne null) {
+        curEntry = curEntry.next
+        if (curEntry ne null) {
+          if (visited(curEntry) || exclude(curEntry.sym))
+            advanceCurEntry()
+          else
+            nextEntry = curEntry
+        }
+      }
+    }
+
+    /** The `low` and `high` symbol.  In the context of overriding pairs,
+     *  low == overriding and high == overridden.
+     */
+    def low  = lowSymbol
+    def high = highSymbol
+
+    def hasNext     = curEntry ne null
+    def currentPair = new SymbolPair(base, low, high)
+    def iterator    = new Iterator[SymbolPair] {
+      def hasNext = cursor.hasNext
+      def next()  = try cursor.currentPair finally cursor.next()
+    }
+
+    // Note that next is called once during object initialization to
+    // populate the fields tracking the current symbol pair.
+    def next() {
+      if (curEntry ne null) {
+        lowSymbol = curEntry.sym
+        advanceNextEntry()        // sets highSymbol
+        if (nextEntry eq null) {
+          advanceCurEntry()
+          next()
+        }
+      }
+    }
+  }
+}
diff --git a/src/reflect/scala/reflect/internal/Symbols.scala b/src/reflect/scala/reflect/internal/Symbols.scala
index 14d742fc2c..efdc8f7435 100644
--- a/src/reflect/scala/reflect/internal/Symbols.scala
+++ b/src/reflect/scala/reflect/internal/Symbols.scala
@@ -3471,8 +3471,8 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
     assert((prev eq null) || phaseId(validFrom) > phaseId(prev.validFrom), this)
     assert(validFrom != NoPeriod, this)
 
-    override def toString() =
-      "TypeHistory(" + phaseOf(validFrom)+":"+runId(validFrom) + "," + info + "," + prev + ")"
+    private def phaseString = "%s: %s".format(phaseOf(validFrom), info)
+    override def toString = toList reverseMap (_.phaseString) mkString ", "
 
     def toList: List[TypeHistory] = this :: ( if (prev eq null) Nil else prev.toList )
 
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index be7ff84c65..8f19e89dd4 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -18,6 +18,7 @@ import util.Statistics
 import util.ThreeValues._
 import Variance._
 import Depth._
+import TypeConstants._
 
 /* A standard type pattern match:
   case ErrorType =>
@@ -90,10 +91,6 @@ trait Types
   private var explainSwitch = false
   private final val emptySymbolSet = immutable.Set.empty[Symbol]
 
-  protected[internal] final val DefaultLogThreshhold = 50
-  private final val LogPendingBaseTypesThreshold = DefaultLogThreshhold
-  private final val LogVolatileThreshold = DefaultLogThreshhold
-
   private final val traceTypeVars = sys.props contains "scalac.debug.tvar"
   private final val breakCycles = settings.breakCycles.value
   /** In case anyone wants to turn off type parameter bounds being used
@@ -142,8 +139,6 @@ trait Types
     override def typeConstructor: Type = underlying.typeConstructor
     override def isError = underlying.isError
     override def isErroneous = underlying.isErroneous
-    override def isStable: Boolean = underlying.isStable
-    override def isVolatile = underlying.isVolatile
     override def paramSectionCount = underlying.paramSectionCount
     override def paramss = underlying.paramss
     override def params = underlying.params
@@ -270,7 +265,7 @@ trait Types
     def takesTypeArgs: Boolean = this.isHigherKinded
 
     /** Does this type denote a stable reference (i.e. singleton type)? */
-    def isStable: Boolean = false
+    final def isStable: Boolean = definitions isStable this
 
     /** Is this type dangerous (i.e. it might contain conflicting
      *  type information when empty, so that it can be constructed
@@ -278,7 +273,7 @@ trait Types
      *  type of the form T_1 with T_n { decls }, where one of the
      *  T_i (i > 1) is an abstract type.
      */
-    def isVolatile: Boolean = false
+    final def isVolatile: Boolean = definitions isVolatile this
 
     /** Is this type a structural refinement type (it ''refines'' members that have not been inherited) */
     def isStructuralRefinement: Boolean = false
@@ -1233,8 +1228,6 @@ trait Types
   abstract class SingletonType extends SubType with SimpleTypeProxy {
     def supertype = underlying
     override def isTrivial = false
-    override def isStable = true
-    override def isVolatile = underlying.isVolatile
     override def widen: Type = underlying.widen
     override def baseTypeSeq: BaseTypeSeq = {
       if (Statistics.canEnable) Statistics.incCounter(singletonBaseTypeSeqCount)
@@ -1312,7 +1305,6 @@ trait Types
   /** An object representing a non-existing prefix */
   case object NoPrefix extends Type {
     override def isTrivial: Boolean = true
-    override def isStable: Boolean = true
     override def prefixString = ""
     override def safeToString: String = "<noprefix>"
     override def kind = "NoPrefixType"
@@ -1330,7 +1322,6 @@ trait Types
     override def isTrivial: Boolean = sym.isPackageClass
     override def typeSymbol = sym
     override def underlying: Type = sym.typeOfThis
-    override def isVolatile = false
     override def isHigherKinded = sym.isRefinementClass && underlying.isHigherKinded
     override def prefixString =
       if (settings.debug) sym.nameString + ".this."
@@ -1379,8 +1370,6 @@ trait Types
 
     // more precise conceptually, but causes cyclic errors:    (paramss exists (_ contains sym))
     override def isImmediatelyDependent = (sym ne NoSymbol) && (sym.owner.isMethod && sym.isValueParameter)
-
-    override def isVolatile : Boolean = underlying.isVolatile && (sym.hasVolatileType || !sym.isStable)
 /*
     override def narrow: Type = {
       if (phase.erasedTypes) this
@@ -1776,33 +1765,6 @@ trait Types
             typeSymbol))
       } else super.normalize
     }
-
-    /** A refined type P1 with ... with Pn { decls } is volatile if
-     *  one of the parent types Pi is an abstract type, and
-     *  either i > 1, or decls or a following parent Pj, j > 1, contributes
-     *  an abstract member.
-     *  A type contributes an abstract member if it has an abstract member which
-     *  is also a member of the whole refined type. A scope `decls` contributes
-     *  an abstract member if it has an abstract definition which is also
-     *  a member of the whole type.
-     */
-    override def isVolatile = {
-      def isVisible(m: Symbol) =
-        this.nonPrivateMember(m.name).alternatives contains m
-      def contributesAbstractMembers(p: Type) =
-        p.deferredMembers exists isVisible
-
-      ((parents exists (_.isVolatile))
-       ||
-       (parents dropWhile (! _.typeSymbol.isAbstractType) match {
-         case ps @ (_ :: ps1) =>
-           (ps ne parents) ||
-           (ps1 exists contributesAbstractMembers) ||
-           (decls.iterator exists (m => m.isDeferred && isVisible(m)))
-         case _ =>
-           false
-       }))
-    }
     override def kind = "RefinedType"
   }
 
@@ -2038,7 +2000,6 @@ trait Types
   class ModuleTypeRef(pre0: Type, sym0: Symbol) extends NoArgsTypeRef(pre0, sym0) with ClassTypeRef {
     require(sym.isModuleClass, sym)
     private[this] var narrowedCache: Type = _
-    override def isStable = pre.isStable
     override def narrow = {
       if (narrowedCache eq null)
         narrowedCache = singleType(pre, sym.sourceModule)
@@ -2053,7 +2014,6 @@ trait Types
   }
   class PackageTypeRef(pre0: Type, sym0: Symbol) extends ModuleTypeRef(pre0, sym0) {
     require(sym.isPackageClass, sym)
-    override def isStable = true
     override protected def finishPrefix(rest: String) = packagePrefix + rest
   }
   class RefinementTypeRef(pre0: Type, sym0: Symbol) extends NoArgsTypeRef(pre0, sym0) with ClassTypeRef {
@@ -2160,8 +2120,6 @@ trait Types
     require(sym.isAliasType, sym)
 
     override def dealias    = if (typeParamsMatchArgs) betaReduce.dealias else super.dealias
-    override def isStable   = normalize.isStable
-    override def isVolatile = normalize.isVolatile
     override def narrow     = normalize.narrow
     override def thisInfo   = normalize
     override def prefix     = if (this ne normalize) normalize.prefix else pre
@@ -2216,30 +2174,6 @@ trait Types
     private var symInfoCache: Type = _
     private var thisInfoCache: Type = _
 
-    override def isVolatile = {
-      // need to be careful not to fall into an infinite recursion here
-      // because volatile checking is done before all cycles are detected.
-      // the case to avoid is an abstract type directly or
-      // indirectly upper-bounded by itself. See #2918
-      try {
-        volatileRecursions += 1
-        if (volatileRecursions < LogVolatileThreshold)
-          bounds.hi.isVolatile
-        else if (pendingVolatiles(sym))
-          true // we can return true here, because a cycle will be detected
-               // here afterwards and an error will result anyway.
-        else
-          try {
-            pendingVolatiles += sym
-            bounds.hi.isVolatile
-          } finally {
-            pendingVolatiles -= sym
-          }
-      } finally {
-        volatileRecursions -= 1
-      }
-    }
-
     override def thisInfo   = {
       val symInfo = sym.info
       if (thisInfoCache == null || (symInfo ne symInfoCache)) {
@@ -2254,7 +2188,6 @@ trait Types
       }
       thisInfoCache
     }
-    override def isStable = bounds.hi.typeSymbol isSubClass SingletonClass
     override def bounds   = thisInfo.bounds
     override protected[Types] def baseTypeSeqImpl: BaseTypeSeq = transform(bounds.hi).baseTypeSeq prepend this
     override def kind = "AbstractTypeRef"
@@ -2340,7 +2273,6 @@ trait Types
 
     override def baseClasses      = thisInfo.baseClasses
     override def baseTypeSeqDepth = baseTypeSeq.maxDepth
-    override def isStable         = (sym eq NothingClass) || (sym eq SingletonClass)
     override def prefix           = pre
     override def termSymbol       = super.termSymbol
     override def termSymbolDirect = super.termSymbol
@@ -2607,7 +2539,6 @@ trait Types
     override def baseClasses: List[Symbol] = resultType.baseClasses
     override def baseType(clazz: Symbol): Type = resultType.baseType(clazz)
     override def boundSyms = resultType.boundSyms
-    override def isVolatile = resultType.isVolatile
     override def safeToString: String = "=> "+ resultType
     override def kind = "NullaryMethodType"
   }
@@ -2646,7 +2577,6 @@ trait Types
     override def baseClasses: List[Symbol] = resultType.baseClasses
     override def baseType(clazz: Symbol): Type = resultType.baseType(clazz)
     override def narrow: Type = resultType.narrow
-    override def isVolatile = resultType.isVolatile
 
     /** @M: typeDefSig wraps a TypeBounds in a PolyType
      *  to represent a higher-kinded type parameter
@@ -2691,7 +2621,6 @@ trait Types
     override protected def rewrap(newtp: Type) = existentialAbstraction(quantified, newtp)
 
     override def isTrivial = false
-    override def isStable: Boolean = false
     override def bounds = TypeBounds(maybeRewrap(underlying.bounds.lo), maybeRewrap(underlying.bounds.hi))
     override def parents = underlying.parents map maybeRewrap
     override def boundSyms = quantified.toSet
@@ -3251,8 +3180,6 @@ trait Types
       else super.normalize
     )
     override def typeSymbol = origin.typeSymbol
-    override def isStable = origin.isStable
-    override def isVolatile = origin.isVolatile
 
     private def tparamsOfSym(sym: Symbol) = sym.info match {
       case PolyType(tparams, _) if tparams.nonEmpty =>
@@ -4663,6 +4590,12 @@ trait Types
 
 }
 
+object TypeConstants {
+  final val DefaultLogThreshhold         = 50
+  final val LogPendingBaseTypesThreshold = DefaultLogThreshhold
+  final val LogVolatileThreshold         = DefaultLogThreshhold
+}
+
 object TypesStats {
   import BaseTypeSeqsStats._
   val rawTypeCount        = Statistics.newCounter   ("#raw type creations")
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
index 152c689c56..6532bce9f0 100644
--- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
+++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala
@@ -12,7 +12,7 @@ trait TypeComparers {
   import definitions._
   import TypesStats._
 
-  private final val LogPendingSubTypesThreshold = DefaultLogThreshhold
+  private final val LogPendingSubTypesThreshold = TypeConstants.DefaultLogThreshhold
 
   private val pendingSubTypes = new mutable.HashSet[SubTypePair]