Trying to make typechecker faster by (1) new su...

Trying to make typechecker faster by (1) new subtyping (2) better
implicit caches. Disallowed '42 as a symbol. Added cache method to
Mutable Maps. Better complietion in interactive.

17 files changed, 455 insertions, 154 deletions

diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
index 51a8495ece..c4ce109946 100644
--- a/src/compiler/scala/tools/nsc/Global.scala
+++ b/src/compiler/scala/tools/nsc/Global.scala
@@ -103,6 +103,8 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
     val global: Global.this.type = Global.this
   } with Statistics
 
+  util.Statistics.enabled = settings.Ystatistics.value
+
   /** Computing pairs of overriding/overridden symbols */
   object overridingPairs extends {
     val global: Global.this.type = Global.this
@@ -641,6 +643,8 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
    */
   class Run {
 
+    var isDefined = false
+
     private val firstPhase = {
       // ----------- Initialization code -------------------------
       curRunId += 1
@@ -731,6 +735,8 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
     val mixinPhase = phaseNamed("mixin")
     val icodePhase = phaseNamed("icode")
 
+    isDefined = true
+
     /** A test whether compilation should stop at phase with given name */
     protected def stopPhase(name : String) = settings.stop.contains(name)
 
@@ -800,7 +806,7 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
       	    warning("It is not possible to check the result of the "+globalPhase.name+" phase")
           }
         }
-        if (settings.statistics.value) statistics.print(phase)
+        if (settings.Ystatistics.value) statistics.print(phase)
         advancePhase
       }
 
diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala
index d098989906..8ef1ee0939 100644
--- a/src/compiler/scala/tools/nsc/Settings.scala
+++ b/src/compiler/scala/tools/nsc/Settings.scala
@@ -785,7 +785,7 @@ trait ScalacSettings {
   val skip          = PhasesSetting     ("-Yskip", "Skip")
   val Xsqueeze      = ChoiceSetting     ("-Ysqueeze", "if on, creates compact code in matching", List("on","off"), "on") .
                                           withHelpSyntax("-Ysqueeze:<enabled>")
-  val statistics    = BooleanSetting    ("-Ystatistics", "Print compiler statistics")
+  val Ystatistics   = BooleanSetting    ("-Ystatistics", "Print compiler statistics")
   val stop          = PhasesSetting     ("-Ystop", "Stop after phase")
   val refinementMethodDispatch =
                       ChoiceSetting     ("-Ystruct-dispatch", "Selects dispatch method for structural refinement method calls",
diff --git a/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala b/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala
index 6c40c1f0a6..e29c055911 100755
--- a/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala
+++ b/src/compiler/scala/tools/nsc/ast/parser/Scanners.scala
@@ -3,7 +3,6 @@
  * @author  Martin Odersky
  */
 // $Id: Scanners.scala 17285 2009-03-11 13:51:56Z rytz $
-
 package scala.tools.nsc.ast.parser
 
 import scala.tools.nsc.util._
@@ -329,7 +328,7 @@ trait Scanners {
           }
         case '\'' =>
           nextChar()
-          if (isIdentifierStart(ch) || '0' <= ch && ch <= '9')
+          if (isIdentifierStart(ch))
             charLitOr(getIdentRest)
           else if (isSpecial(ch))
             charLitOr(getOperatorRest)
diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
index 47a8410ae0..114054aaeb 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
@@ -277,7 +277,7 @@ abstract class Inliners extends SubComponent {
 
 
     val tfa = new analysis.MethodTFA();
-    tfa.stat = settings.statistics.value
+    tfa.stat = settings.Ystatistics.value
 
     // how many times have we already inlined this method here?
     private val inlinedMethods: Map[Symbol, Int] = new HashMap[Symbol, Int] {
diff --git a/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala b/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala
index c1e6747f8c..d264632bd5 100644
--- a/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala
+++ b/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala
@@ -18,7 +18,10 @@ trait CompilerControl { self: Global =>
 
   /** Info given for every member found by completion
    */
-  case class Member(val sym: Symbol, val tpe: Type, val accessible: Boolean, val inherited: Boolean, val viaView: Symbol)
+  case class Member(val sym: Symbol, val tpe: Type, val accessible: Boolean, val inherited: Boolean, val viaView: Symbol) {
+    def shadows(other: Member) =
+      sym.name == other.sym.name && (sym.tpe matches other.sym.tpe)
+  }
 
   /** The scheduler by which client and compiler communicate
    *  Must be initialized before starting compilerRunner
diff --git a/src/compiler/scala/tools/nsc/interactive/Global.scala b/src/compiler/scala/tools/nsc/interactive/Global.scala
index ee8865dec5..51ba19951e 100755
--- a/src/compiler/scala/tools/nsc/interactive/Global.scala
+++ b/src/compiler/scala/tools/nsc/interactive/Global.scala
@@ -319,7 +319,9 @@ self =>
           val decls = tree.tpe.decls.toList map (member(_, false))
           val inherited = tree.tpe.members.toList diff decls map (member(_, true))
           val implicits = applicableViews(tree, context) flatMap implicitMembers
-          decls ::: inherited ::: implicits
+          def isVisible(m: Member) =
+            !(decls exists (_.shadows(m))) && !(inherited exists (_.shadows(m)))
+          decls ::: inherited ::: (implicits filter isVisible)
         case None =>
           throw new FatalError("no context found for "+pos)
       }
diff --git a/src/compiler/scala/tools/nsc/symtab/Scopes.scala b/src/compiler/scala/tools/nsc/symtab/Scopes.scala
index 3becf477b4..cbe514d775 100644
--- a/src/compiler/scala/tools/nsc/symtab/Scopes.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Scopes.scala
@@ -60,7 +60,9 @@ trait Scopes {
    *  @return          ...
    */
   def newScope(initElems: ScopeEntry): Scope = new NormalScope(initElems)
+
   final def newScope: Scope = newScope(null: ScopeEntry)
+
   trait PackageScopeDependMap {
     def createDepend(from : Symbol, name : Name) : Unit
   }
@@ -306,22 +308,38 @@ trait Scopes {
     def lookupWithContext(name : Name)(from : Symbol) : Symbol = lookup(name)
 
     /** lookup a symbol entry matching given name.
-     *
-     *  @param name ...
-     *  @return     ...
+     *  @note from Martin: I believe this is a hotspot or will be one
+     *  in future versions of the type system. I have reverted the previous
+     *  change to use iterators as too costly.
      */
     def lookupEntry(name: Name): ScopeEntry = {
-      val it =
-        if (hashtable != null) hashtableIterator(name.start & HASHMASK)
-        else entryIterator(elems)
-
-      it find (_.sym.name == name) orNull
+      var e: ScopeEntry = null
+      if (hashtable ne null) {
+        e = hashtable(name.start & HASHMASK)
+        while ((e ne null) && e.sym.name != name) {
+          e = e.tail
+        }
+      } else {
+        e = elems
+        while ((e ne null) && e.sym.name != name) {
+          e = e.next
+        }
+      }
+      e
     }
 
-    /** lookup next entry with same name as this one */
+    /** lookup next entry with same name as this one
+     *  @note from Martin: I believe this is a hotspot or will be one
+     *  in future versions of the type system. I have reverted the previous
+     *  change to use iterators as too costly.
+     */
     def lookupNextEntry(entry: ScopeEntry): ScopeEntry = {
-      val it = if (hashtable == null) entry.entryIterator else entry.bucketIterator
-      (it drop 1) find (_.sym.name == entry.sym.name) orNull
+      var e = entry
+      if (hashtable ne null)
+        do { e = e.tail } while ((e ne null) && e.sym.name != entry.sym.name)
+      else
+        do { e = e.next } while ((e ne null) && e.sym.name != entry.sym.name);
+      e
     }
 
     /** Return all symbols as a list in the order they were entered in this scope.
diff --git a/src/compiler/scala/tools/nsc/symtab/Symbols.scala b/src/compiler/scala/tools/nsc/symtab/Symbols.scala
index af6f45e095..d5608dd334 100644
--- a/src/compiler/scala/tools/nsc/symtab/Symbols.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Symbols.scala
@@ -749,7 +749,7 @@ trait Symbols {
     /** Return info without checking for initialization or completing */
     def rawInfo: Type = {
       var infos = this.infos
-      assert(infos != null, name)
+      assert(infos != null)
       val curPeriod = currentPeriod
       val curPid = phaseId(curPeriod)
 
diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala
index 1b3b93eb2c..9c5367b29d 100644
--- a/src/compiler/scala/tools/nsc/symtab/Types.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Types.scala
@@ -8,7 +8,6 @@ package scala.tools.nsc.symtab
 
 import scala.collection.immutable
 import scala.collection.mutable.{ListBuffer, HashMap, WeakHashMap}
-import scala.compat.Platform.currentTime
 import scala.tools.nsc.ast.TreeGen
 import scala.tools.nsc.util.{HashSet, Position, NoPosition}
 import Flags._
@@ -70,9 +69,10 @@ trait Types {
   var findMemberCount = 0
   var noMemberCount = 0
   var multMemberCount = 0
-  var findMemberMillis = 0l
+  var findMemberNanos = 0l
   var subtypeCount = 0
-  var subtypeMillis = 0l
+  var sametypeCount = 0
+  var subtypeNanos = 0l
 
   private var explainSwitch = false
 
@@ -511,14 +511,15 @@ trait Types {
 
     /** Is this type a subtype of that type? */
     def <:<(that: Type): Boolean = {
-      if (util.Statistics.enabled) subtypeCount += 1
-      val startTime = if (util.Statistics.enabled) currentTime else 0l
+//      val startTime = if (util.Statistics.enabled) System.nanoTime() else 0l
       val result =
         ((this eq that) ||
          (if (explainSwitch) explain("<", isSubType, this, that)
           else isSubType(this, that, AnyDepth)))
-      if (util.Statistics.enabled)
-        subtypeMillis = subtypeMillis + currentTime - startTime
+//      if (util.Statistics.enabled) {
+//        subtypeNanos += System.nanoTime() - startTime
+//        subtypeCount += 1
+//      }
       result
     }
 
@@ -686,7 +687,7 @@ trait Types {
       if (!this.isGround)
         return typeVarToOriginMap(this).findMember(name, excludedFlags, requiredFlags, stableOnly)(from)
       if (util.Statistics.enabled) findMemberCount += 1
-      val startTime = if (util.Statistics.enabled) currentTime else 0l
+//      val startTime = if (util.Statistics.enabled) System.nanoTime() else 0l
 
       //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG
       var members: Scope = null
@@ -712,8 +713,7 @@ trait Types {
                    sym.getFlag(PRIVATE | LOCAL) != (PRIVATE | LOCAL) ||
                    (bcs0.head.hasTransOwner(bcs.head)))) {
                 if (name.isTypeName || stableOnly && sym.isStable) {
-                  if (util.Statistics.enabled)
-                    findMemberMillis = findMemberMillis + currentTime - startTime
+//                  if (util.Statistics.enabled) findMemberNanos += System.nanoTime() - startTime
                   return sym
                 } else if (member == NoSymbol) {
                   member = sym
@@ -753,8 +753,7 @@ trait Types {
         } // while (!bcs.isEmpty)
         excluded = excludedFlags
       } // while (continue)
-      if (util.Statistics.enabled)
-        findMemberMillis = findMemberMillis + currentTime - startTime
+//      if (util.Statistics.enabled) findMemberNanos += System.nanoTime() - startTime
       if (members eq null) {
         if (util.Statistics.enabled) if (member == NoSymbol) noMemberCount += 1;
         member
@@ -1491,29 +1490,34 @@ A type's typeSymbol should never be inspected directly.
 
     private var normalized: Type = null
 
-    override def normalize: Type = {
-      if (normalized == null) {
-        normalized = if (sym.isAliasType) { // beta-reduce
-          if (sym.info.typeParams.length == args.length || !isHigherKinded) {
-            /* !isHigherKinded && sym.info.typeParams.length != args.length only happens when compiling e.g.,
-             `val x: Class' with -Xgenerics, while `type Class = java.lang.Class' had already been compiled without -Xgenerics */
-            val xform = transform(sym.info.resultType)
-            assert(xform ne this, this)
-            xform.normalize // cycles have been checked in typeRef
-          } else PolyType(typeParams, transform(sym.info.resultType).normalize)  // eta-expand
-            // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function*
-          } else if (isHigherKinded) {
-            // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function*
-            // @M: initialize needed (see test/files/pos/ticket0137.scala)
-            PolyType(typeParams, typeRef(pre, sym.initialize, higherKindedArgs))
-          } else if (sym.isRefinementClass) {
-            sym.info.normalize // @MO to AM: OK?
-          } else {
-            super.normalize
-          }
+    def normalize0: Type =
+      if (sym.isAliasType) { // beta-reduce
+        if (sym.info.typeParams.length == args.length || !isHigherKinded) {
+          /* !isHigherKinded && sym.info.typeParams.length != args.length only happens when compiling e.g.,
+           `val x: Class' with -Xgenerics, while `type Class = java.lang.Class' had already been compiled without -Xgenerics */
+          val xform = transform(sym.info.resultType)
+          assert(xform ne this, this)
+          xform.normalize // cycles have been checked in typeRef
+        } else {
+          PolyType(typeParams, transform(sym.info.resultType).normalize)  // eta-expand
+          // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function*
+        }
+      } else if (isHigherKinded) {
+        // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function*
+        // @M: initialize needed (see test/files/pos/ticket0137.scala)
+        PolyType(typeParams, typeRef(pre, sym.initialize, higherKindedArgs))
+      } else if (sym.isRefinementClass) {
+        sym.info.normalize // @MO to AM: OK?
+      } else {
+        super.normalize
+      }
+
+    override def normalize: Type =
+      if (phase.erasedTypes) normalize0
+      else {
+        if (normalized == null) normalized = normalize0
+        normalized
       }
-      normalized
-    }
 
     override def decls: Scope = {
       sym.info match {
@@ -2325,7 +2329,7 @@ A type's typeSymbol should never be inspected directly.
 
 // Hash consing --------------------------------------------------------------
 
-  private var uniques: HashSet[AnyRef] = _
+  var uniques: HashSet[AnyRef] = _
   private var uniqueRunId = NoRunId
 
   def uniqueTypeCount = uniques.size // for statistics
@@ -2649,6 +2653,17 @@ A type's typeSymbol should never be inspected directly.
     eparams
   }
 
+  def isRaw(sym: Symbol, args: List[Type]) =
+    !phase.erasedTypes && !sym.typeParams.isEmpty && sym.hasFlag(JAVA) && args.isEmpty
+      //  note: it's important to write the two first tests in this order,
+      //  as only typeParams forces the classfile to be read. See #400
+
+  /** Is type tp a ``raw type''? */
+  def isRawType(tp: Type) = tp match {
+    case TypeRef(_, sym, args) => isRaw(sym, args)
+    case _ => false
+  }
+
   /** The raw to existential map converts a ``raw type'' to an existential type.
    *  It is necessary because we might have read a raw type of a
    *  parameterized Java class from a class file. At the time we read the type
@@ -3446,6 +3461,7 @@ A type's typeSymbol should never be inspected directly.
     subsametypeRecursions += 1
     val lastUndoLog = undoLog
     val result = isSameType0(tp1, tp2)
+    sametypeCount += 1
     if (!result) undoTo(lastUndoLog)
     result
   } finally {
@@ -3464,11 +3480,9 @@ A type's typeSymbol should never be inspected directly.
     if (subsametypeRecursions == 0) undoLog = List()
   }
 
-  def normalizePlus(tp: Type) = tp match {
-    case TypeRef(pre, sym, List()) if (sym.isInitialized && sym.hasFlag(JAVA) && !sym.typeParams.isEmpty) =>
-      rawToExistential(tp)
-    case _ => tp.normalize
-  }
+  def normalizePlus(tp: Type) =
+    if (isRawType(tp)) rawToExistential(tp)
+    else tp.normalize
 
   /*
   todo: change to:
@@ -3623,7 +3637,6 @@ A type's typeSymbol should never be inspected directly.
     if (subsametypeRecursions == 0) undoLog = List()
   }
 
-
   /** Does this type have a prefix that begins with a type variable */
   def beginsWithTypeVar(tp: Type): Boolean = tp match {
     case SingleType(pre, sym) =>
@@ -3645,9 +3658,235 @@ A type's typeSymbol should never be inspected directly.
       tp
   }
 
+  def isErrorOrWildcard(tp: Type) = (tp eq ErrorType) || (tp eq WildcardType)
+
+  def isSingleType(tp: Type) = tp match {
+    case ThisType(_) | SuperType(_, _) | SingleType(_, _) => true
+    case _ => false
+  }
+
+  def isConstantType(tp: Type) = tp match {
+    case ConstantType(_) => true
+    case _ => false
+  }
+
+  def isHKSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = (
+    tp1.typeSymbol == NothingClass
+    ||
+    tp2.typeSymbol == AnyClass // @M Any and Nothing are super-type resp. subtype of every well-kinded type
+    || // @M! normalize reduces higher-kinded case to PolyType's
+    ((tp1.normalize, tp2.normalize) match {
+      case (PolyType(tparams1, res1), PolyType(tparams2, res2)) =>
+        tparams1.length == tparams2.length &&
+        List.forall2(tparams1, tparams2) (
+          (p1, p2) => p2.info.substSym(tparams2, tparams1) <:< p1.info) &&
+        res1 <:< res2.substSym(tparams2, tparams1)
+
+      case (tp1a, tp2a) =>
+        (isDifferentType(tp1a, tp1) || isDifferentType(tp2a, tp2)) &&
+        isSubType(tp1a, tp2a, depth)
+    }))
+
+  def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[Symbol]): Boolean = (
+    tps1.isEmpty && tps2.isEmpty
+    ||
+    !tps1.isEmpty && !tps2.isEmpty &&
+    (tparams.head.isCovariant || (tps2.head <:< tps1.head)) &&
+    (tparams.head.isContravariant || (tps1.head <:< tps2.head)) &&
+    isSubArgs(tps1.tail, tps2.tail, tparams.tail)
+  )
+
+  def isSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = {
+    isSubType1(tp1, tp2, depth)
+  }
+
+  def differentOrNone(tp1: Type, tp2: Type) = if (tp1 eq tp2) NoType else tp1
+
+  /** Does type `tp1' conform to `tp2'?
+   */
+  private def isSubType2(tp1: Type, tp2: Type, depth: Int): Boolean = {
+    if (isErrorOrWildcard(tp1)) return true
+    if (isErrorOrWildcard(tp2)) return true
+    if (tp1 eq NoType) return false
+    if (tp2 eq NoType) return false
+    if (tp1 eq NoPrefix) return (tp2 eq NoPrefix) || tp2.typeSymbol.isPackageClass
+    if (tp2 eq NoPrefix) return (tp1 eq NoPrefix) || tp1.typeSymbol.isPackageClass
+    if (isSingleType(tp1) && isSingleType(tp2) ||
+        isConstantType(tp1) && isConstantType(tp2)) return tp1 =:= tp2
+    if (tp1.isHigherKinded || tp2.isHigherKinded) return isHKSubType0(tp1, tp2, depth)
+
+    /** First try, on the right:
+     *   - unwrap Annotated types, BoundedWildcardTypes,
+     *   - bind TypeVars on the right, if lhs is not Annotated nor BoundedWildcard
+     *   - handle common cases for first-kind TypeRefs on both sides as a fast path.
+     */
+    def firstTry = tp2 match {
+      // fast path: two typerefs, none of them HK
+      case tr2: TypeRef =>
+        tp1 match {
+          case tr1: TypeRef =>
+            val sym1 = tr1.sym
+            val sym2 = tr2.sym
+            val pre1 = tr1.pre
+            val pre2 = tr2.pre
+            ((if (sym1 == sym2) phase.erasedTypes || pre1 <:< pre2
+              else (sym1.name == sym2.name && isUnifiable(pre1, pre2))) &&
+             isSubArgs(tr1.args, tr2.args, sym1.typeParams)
+             ||
+             sym2.isClass && {
+               val base = tr1 baseType sym2
+               (base ne tr1) && base <:< tr2
+             }
+             ||
+             thirdTryRef(tr1, tr2))
+          case _ =>
+            secondTry
+        }
+      case AnnotatedType(_, _, _) =>
+        tp1.withoutAnnotations <:< tp2.withoutAnnotations && annotationsConform(tp1, tp2)
+      case BoundedWildcardType(bounds) =>
+        tp1 <:< bounds.hi
+      case tv2 @ TypeVar(_, constr2) =>
+        tp1 match {
+          case AnnotatedType(_, _, _) | BoundedWildcardType(_) =>
+            secondTry
+          case _ =>
+            if (constr2.inst != NoType) tp1 <:< constr2.inst
+            else isRelatable(tv2, tp1) && { constr2.lobounds = tp1 :: constr2.lobounds; true }
+        }
+      case _ =>
+        secondTry
+    }
+
+    /** Second try, on the left:
+     *   - unwrap AnnotatedTypes, BoundedWildcardTypes,
+     *   - bind typevars,
+     *   - handle existential types by skolemization.
+     */
+    def secondTry = tp1 match {
+      case AnnotatedType(_, _, _) =>
+        tp1.withoutAnnotations <:< tp2.withoutAnnotations && annotationsConform(tp1, tp2)
+      case BoundedWildcardType(bounds) =>
+        tp1.bounds.lo <:< tp2
+      case tv1 @ TypeVar(_, constr1) =>
+        if (constr1.inst != NoType) constr1.inst <:< tp2
+        else isRelatable(tv1, tp2) && { constr1.hibounds = tp2 :: constr1.hibounds; true }
+      case ExistentialType(_, _) =>
+        try {
+          skolemizationLevel += 1
+          tp1.skolemizeExistential(NoSymbol, null) <:< tp2
+        } finally {
+          skolemizationLevel -= 1
+        }
+      case _ =>
+        thirdTry
+    }
+
+    def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = {
+      val sym2 = tp2.sym
+      if (sym2.isAliasType) {
+        isSubType(tp1.normalize, tp2.normalize, depth)
+      } else if (sym2.isAbstractType) {
+        val tp2a = tp2.bounds.lo
+        isDifferentType(tp2, tp2a) && tp1 <:< tp2a || fourthTry
+      } else if (sym2 == NotNullClass) {
+        tp1.isNotNull
+      } else if (sym2 == SingletonClass) {
+        tp1.isStable
+      } else if (isRaw(sym2, tp2.args)) {
+        isSubType(tp1, rawToExistential(tp2), depth)
+      } else if (sym2.isRefinementClass) {
+        isSubType(tp1, sym2.info, depth)
+      } else {
+        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 RefinedType(parents2, ref2) =>
+        (parents2 forall (tp1 <:< _)) &&
+        (ref2.toList forall tp1.specializes)
+      case et: ExistentialType =>
+        et.withTypeVars(tp1 <:< _, depth) || fourthTry
+      case NotNullType(ntp2) =>
+        tp1.isNotNull && tp1 <:< ntp2
+      case MethodType(params2, res2) =>
+        tp1 match {
+          case MethodType(params1, res1) =>
+            (params1.length == params2.length &&
+             matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isInstanceOf[JavaMethodType], tp2.isInstanceOf[JavaMethodType]) &&
+             (res1 <:< res2) &&
+             tp1.isInstanceOf[ImplicitMethodType] == tp2.isInstanceOf[ImplicitMethodType])
+          case _ =>
+            false
+        }
+      case PolyType(List(), res2) =>
+        tp1 match {
+          case PolyType(List(), res1) =>
+            // other polytypes were already checked in isHKSubType
+            res1 <:< res2
+          case _ =>
+            false
+        }
+      case TypeBounds(lo2, hi2) =>
+        tp1 match {
+          case TypeBounds(lo1, hi1) =>
+            lo2 <:< lo1 && hi1 <:< hi2
+          case _ =>
+            false
+        }
+      case _ =>
+        fourthTry
+    }
+
+    /** Fourth try, on the left:
+     *   - handle typerefs, refined types, notnull and singleton types.
+     */
+    def fourthTry = tp1 match {
+      case TypeRef(pre1, sym1, args1) =>
+        if (sym1.isAliasType) {
+          isSubType(tp1.normalize, tp2.normalize, depth)
+        } else if (sym1.isAbstractType) {
+          val tp1a = tp1.bounds.hi
+          isDifferentType(tp1, tp1a) && tp1a <:< tp2
+        } else if (sym1 == NothingClass) {
+          true
+        } else if (sym1 == NullClass) {
+          tp2 match {
+            case TypeRef(_, sym2, _) =>
+              (sym2 isNonBottomSubClass ObjectClass) &&
+              !(tp2.normalize.typeSymbol isNonBottomSubClass NotNullClass)
+            case _ =>
+              isSingleType(tp2) && tp1 <:< tp2.widen
+          }
+        } else if (isRaw(sym1, args1)) {
+          isSubType(rawToExistential(tp1), tp2, depth)
+        } else if (sym1.isRefinementClass) {
+          isSubType(sym1.info, tp2, depth)
+        } else {
+          false
+        }
+      case RefinedType(parents1, ref1) =>
+        parents1 exists (_ <:< tp2)
+      case _: SingletonType | _: NotNullType =>
+        tp1.underlying <:< tp2
+      case _ =>
+        false
+    }
+
+    firstTry
+  }
+
   /** Does type `tp1' conform to `tp2'?
    */
-  private def isSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = {
+  private def isSubType1(tp1: Type, tp2: Type, depth: Int): Boolean = {
     ((tp1, tp2) match {
       case (ErrorType, _)    => true
       case (WildcardType, _) => true
diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala b/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala
index dbdb4e1ad7..8122177365 100644
--- a/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala
+++ b/src/compiler/scala/tools/nsc/symtab/classfile/UnPickler.scala
@@ -35,12 +35,18 @@ abstract class UnPickler {
    */
   def unpickle(bytes: Array[Byte], offset: Int, classRoot: Symbol, moduleRoot: Symbol, filename: String) {
     try {
-      new UnPickle(bytes, offset, classRoot, moduleRoot, filename)
+      val p = if (currentRun.isDefined &&
+                  currentRun.picklerPhase != NoPhase &&
+                  phase.id > currentRun.picklerPhase.id) currentRun.picklerPhase
+              else phase
+      atPhase(p) {
+        new UnPickle(bytes, offset, classRoot, moduleRoot, filename)
+      }
     } catch {
       case ex: IOException =>
         throw ex
       case ex: Throwable =>
-        if (settings.debug.value) ex.printStackTrace()
+        /*if (settings.debug.value)*/ ex.printStackTrace()
         throw new RuntimeException("error reading Scala signature of "+filename+": "+ex.getMessage())
     }
   }
@@ -798,11 +804,13 @@ abstract class UnPickler {
 
     private class LazyTypeRef(i: Int) extends LazyType {
       private val definedAtRunId = currentRunId
+      private val p = phase
       // In IDE, captures class files dependencies so they can be reloaded when their dependencies change.
       private val ideHook = unpickleIDEHook
       override def complete(sym: Symbol) : Unit = {
         val tp = ideHook(at(i, readType))
-        sym setInfo tp
+        if (p != phase) atPhase(p) (sym setInfo tp)
+        else sym setInfo tp
         if (currentRunId != definedAtRunId) sym.setInfo(adaptToNewRunMap(tp))
       }
       override def load(sym: Symbol) { complete(sym) }
diff --git a/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala b/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala
index ccae9578b9..e95c8b69bd 100644
--- a/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala
+++ b/src/compiler/scala/tools/nsc/transform/AddInterfaces.scala
@@ -154,7 +154,7 @@ abstract class AddInterfaces extends InfoTransform {
     override def complete(sym: Symbol) {
       def implType(tp: Type): Type = tp match {
         case ClassInfoType(parents, decls, _) =>
-          assert(phase == implClassPhase, sym)
+          assert(phase == implClassPhase)
           ClassInfoType(
             ObjectClass.tpe :: (parents.tail map mixinToImplClass) ::: List(iface.tpe),
             implDecls(sym, decls),
diff --git a/src/compiler/scala/tools/nsc/transform/Erasure.scala b/src/compiler/scala/tools/nsc/transform/Erasure.scala
index 19f1c737cc..747c1fb902 100644
--- a/src/compiler/scala/tools/nsc/transform/Erasure.scala
+++ b/src/compiler/scala/tools/nsc/transform/Erasure.scala
@@ -1037,10 +1037,10 @@ abstract class Erasure extends AddInterfaces with typechecker.Analyzer with ast.
               case MyError(n,ex) =>
                 Console.println(tree1)
                 throw MyError(n + 1, ex)
-              case ex : AssertionError =>
-                Console.println(tree1)
-                throw MyError(0, ex)
-              case ex => throw ex
+//              case ex : AssertionError =>
+//                Console.println(tree1)
+//                throw MyError(0, ex)
+//              case ex => throw ex
             }
         }
       }
diff --git a/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala b/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala
index f341dd0df9..16287bfc45 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Analyzer.scala
@@ -46,34 +46,10 @@ trait Analyzer extends AnyRef
     def newPhase(_prev: Phase): StdPhase = new StdPhase(_prev) {
       resetTyper()
       override def run {
-        val start = System.nanoTime()
+        val start = if (util.Statistics.enabled) System.nanoTime() else 0L
         currentRun.units foreach applyPhase
-        /*
-        typerTime += System.nanoTime() - start
-        def show(time: Long) = "%2.1f".format(time.toDouble / typerTime * 100)+" / "+time+"ns"
-        println("time spent typechecking: "+show(typerTime))
-        println("time spent in implicits: "+show(implicitTime))
-        println("    successful in scope: "+show(inscopeSucceed))
-        println("        failed in scope: "+show(inscopeFail))
-        println("     successful of type: "+show(oftypeSucceed))
-        println("         failed of type: "+show(oftypeFail))
-        println("    successful manifest: "+show(manifSucceed))
-        println("        failed manifest: "+show(manifFail))
-        println("implicit cache hitratio: "+"%2.1f".format(hits.toDouble / (hits + misses) * 100))
-        println("time spent in failed   : "+show(failedSilent))
-        println("       failed op=      : "+show(failedOpEqs))
-        println("       failed applu    : "+show(failedApplies))
-        */
-        typerTime = 0L
-        implicitTime = 0L
-        inscopeSucceed = 0L
-        inscopeFail = 0L
-        oftypeSucceed = 0L
-        oftypeFail = 0L
-        manifSucceed = 0L
-        manifFail = 0L
-        hits = 0
-        misses = 0
+        if (util.Statistics.enabled)
+          typerTime += System.nanoTime() - start
       }
       def apply(unit: CompilationUnit) {
         try {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 29c30bb285..d24f641fb4 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -10,8 +10,7 @@
 //todo: treat :::= correctly
 package scala.tools.nsc.typechecker
 
-import scala.collection.mutable.{HashMap, ListBuffer}
-import scala.compat.Platform.currentTime
+import scala.collection.mutable.{LinkedHashMap, ListBuffer}
 import scala.tools.nsc.util.{HashSet, Position, Set, NoPosition, SourceFile}
 import symtab.Flags._
 import util.HashSet
@@ -38,6 +37,7 @@ self: Analyzer =>
   var manifFail = 0L
   var hits = 0
   var misses = 0
+  var uncached = 0
 
   /** Search for an implicit value. See the comment on `result` at the end of class `ImplicitSearch`
    *  for more info how the search is conducted.
@@ -60,8 +60,8 @@ self: Analyzer =>
     result
   }
 
-  final val sizeLimit = 100
-  val implicitsCache = new HashMap[Type, SearchResult]
+  final val sizeLimit = 50000
+  val implicitsCache = new LinkedHashMap[AnyRef, SearchResult]
 
   def resetImplicits() { implicitsCache.clear() }
 
@@ -210,7 +210,6 @@ self: Analyzer =>
     }
 
     if (util.Statistics.enabled) implcnt += 1
-    private val startTime = if (util.Statistics.enabled) currentTime else 0l
 
     /** Issues an error signalling ambiguous implicits */
     private def ambiguousImplicitError(info1: ImplicitInfo, info2: ImplicitInfo,
@@ -639,6 +638,37 @@ self: Analyzer =>
       }
     }
 
+    /** An extractor for types of the form ? { name: ? }
+     */
+    object WildcardName {
+      def unapply(pt: Type): Option[Name] = pt match {
+        case RefinedType(List(WildcardType), decls) =>
+          decls.toList match {
+            case List(sym) if (sym.tpe == WildcardType) => Some(sym.name)
+            case _ => None
+          }
+        case _ =>
+          None
+      }
+    }
+
+    /** Return cached search result if found. Otherwise update cache
+     *  but keep within sizeLimit entries
+     */
+    def cacheResult(key: AnyRef): SearchResult = implicitsCache get key match {
+      case Some(r) =>
+        hits += 1
+        r
+      case None =>
+        misses += 1
+        val r = searchImplicit(implicitsOfExpectedType, false)
+        //println("new fact: search implicit of "+key+" = "+r)
+        implicitsCache(key) = r
+        if (implicitsCache.size >= sizeLimit)
+          implicitsCache -= implicitsCache.keysIterator.next
+        r
+    }
+
     /** The result of the implicit search:
      *  First search implicits visible in current context.
      *  If that fails, search implicits in expected type `pt`.
@@ -646,40 +676,29 @@ self: Analyzer =>
      *  If all fails return SearchFailure
      */
     def bestImplicit: SearchResult = {
-      //val start = System.nanoTime()
+      val start = System.nanoTime()
       var result = searchImplicit(context.implicitss, true)
-      //val timer1 = System.nanoTime()
-      //if (result == SearchFailure) inscopeFail += timer1 - start else inscopeSucceed += timer1 - start
+      val timer1 = System.nanoTime()
+      if (result == SearchFailure) inscopeFail += timer1 - start else inscopeSucceed += timer1 - start
       if (result == SearchFailure) {
-        if (pt.isInstanceOf[UniqueType])
-          implicitsCache get pt match {
-            case Some(r) =>
-              hits += 1
-              result = r
-            case None =>
-              misses += 1
-              result = searchImplicit(implicitsOfExpectedType, false)
-            //          println("new fact: search implicit of "+pt+" = "+result)
-            //          if (implicitsCache.size >= sizeLimit)
-            //            implicitsCache -= implicitsCache.values.next
-            implicitsCache(pt) = result
-          }
-        else
-          result = searchImplicit(implicitsOfExpectedType, false)
+        result = pt match {
+          case _: UniqueType => cacheResult(pt)
+          case WildcardName(name) => cacheResult(name)
+          case _ => uncached += 1; searchImplicit(implicitsOfExpectedType, false)
+         }
       }
-      //val timer2 = System.nanoTime()
-      //if (result == SearchFailure) oftypeFail += timer2 - timer1 else oftypeSucceed += timer2 - timer1
+
+      val timer2 = System.nanoTime()
+      if (result == SearchFailure) oftypeFail += timer2 - timer1 else oftypeSucceed += timer2 - timer1
       if (result == SearchFailure) {
         val resultTree = implicitManifest(pt)
         if (resultTree != EmptyTree) result = new SearchResult(resultTree, EmptyTreeTypeSubstituter)
       }
-      //val timer3 = System.nanoTime()
-      //if (result == SearchFailure) manifFail += timer3 - timer2 else manifSucceed += timer3 - timer2
+      val timer3 = System.nanoTime()
+      if (result == SearchFailure) manifFail += timer3 - timer2 else manifSucceed += timer3 - timer2
       if (result == SearchFailure && settings.debug.value)
         println("no implicits found for "+pt+" "+pt.typeSymbol.info.baseClasses+" "+parts(pt)+implicitsOfExpectedType)
-      //implicitTime += System.nanoTime() - start
-
-      if (util.Statistics.enabled) impltime += (currentTime - startTime)
+      implicitTime += System.nanoTime() - start
       result
     }
 
diff --git a/src/compiler/scala/tools/nsc/util/Statistics.scala b/src/compiler/scala/tools/nsc/util/Statistics.scala
index 758760cd08..10a344911c 100644
--- a/src/compiler/scala/tools/nsc/util/Statistics.scala
+++ b/src/compiler/scala/tools/nsc/util/Statistics.scala
@@ -8,7 +8,7 @@
 package scala.tools.nsc.util
 
 object Statistics {
-  final val enabled = false
+  var enabled = false
 }
 
 abstract class Statistics {
@@ -16,30 +16,52 @@ abstract class Statistics {
   val global: Global
   import global._
 
+  def showRelative(base: Long)(time: Long) = "%2.1f".format(time.toDouble / base * 100)+" / "+time+"ns"
+  def showRelTyper(time: Long) = showRelative(analyzer.typerTime)(time)
+
   def print(phase: Phase) = {
-    inform("*** Cumulative statistics at phase " + phase)
-    inform("#tree nodes  : " + nodeCount)
-    inform("#identifiers : " + analyzer.idcnt)
-    inform("#selections  : " + analyzer.selcnt)
-    inform("#applications: " + analyzer.appcnt)
-    inform("#implicits   : " + analyzer.implcnt)
-    inform("ms implicits : " + analyzer.impltime)
-    inform("#uniquetypes : " + uniqueTypeCount)
-    inform("#symbols     : " + symbolCount)
-    inform("#type symbols: " + typeSymbolCount)
-    inform("#class symbols: " + classSymbolCount)
-    inform("#singleton closures: " + singletonBaseTypeSeqCount)
-    inform("#compound closures : " + compoundBaseTypeSeqCount)
-    inform("#typeref closures  : " + typerefBaseTypeSeqCount)
-    inform("#findMember     : " + findMemberCount)
-    inform("#notfound member: " + noMemberCount)
-    inform("#mulitple member: " + multMemberCount)
-    inform("time findMember: " + findMemberMillis)
-    inform("#norm meth : " + analyzer.normM)
-    inform("#norm poly : " + analyzer.normP)
-    inform("#norm other: " + analyzer.normO)
-    inform("#subtype  : " + subtypeCount)
-    inform("ms subtype: " + subtypeMillis)
-    inform("ms type-flow-analysis: " + analysis.timer.millis)
+    if (List("typer", "erasure", "cleanup") contains phase.name) {
+      inform("*** Cumulative statistics at phase " + phase)
+      inform("#tree nodes  : " + nodeCount)
+      inform("#identifiers : " + analyzer.idcnt)
+      inform("#selections  : " + analyzer.selcnt)
+      inform("#applications: " + analyzer.appcnt)
+      inform("#implicits   : " + analyzer.implcnt)
+      inform("#uniquetypes : " + uniqueTypeCount)
+      inform("#symbols     : " + symbolCount)
+      inform("#type symbols: " + typeSymbolCount)
+      inform("#class symbols: " + classSymbolCount)
+      inform("#singleton closures: " + singletonBaseTypeSeqCount)
+      inform("#compound closures : " + compoundBaseTypeSeqCount)
+      inform("#typeref closures  : " + typerefBaseTypeSeqCount)
+      inform("#findMember     : " + findMemberCount)
+      inform("#notfound member: " + noMemberCount)
+      inform("#multiple member: " + multMemberCount)
+      inform("time findMember: " + findMemberNanos)
+      inform("#norm meth   : " + analyzer.normM)
+      inform("#norm poly   : " + analyzer.normP)
+      inform("#norm other  : " + analyzer.normO)
+      inform("#subtype     : " + subtypeCount)
+      inform("ns subtype   : " + subtypeNanos)
+      inform("#sametype    : " + sametypeCount)
+      inform("#unique types: " + uniques.size)
+      inform("ms type-flow-analysis: " + analysis.timer.millis)
+      if (phase.name == "typer") {
+        inform("time spent typechecking: "+showRelTyper(analyzer.typerTime))
+        inform("time spent in implicits: "+showRelTyper(analyzer.implicitTime))
+        inform("    successful in scope: "+showRelTyper(analyzer.inscopeSucceed))
+        inform("        failed in scope: "+showRelTyper(analyzer.inscopeFail))
+        inform("     successful of type: "+showRelTyper(analyzer.oftypeSucceed))
+        inform("         failed of type: "+showRelTyper(analyzer.oftypeFail))
+        inform("    successful manifest: "+showRelTyper(analyzer.manifSucceed))
+        inform("        failed manifest: "+showRelTyper(analyzer.manifFail))
+        inform("implicit cache hitratio: "+"%2.1f".format(analyzer.hits.toDouble / (analyzer.hits + analyzer.misses) * 100))
+        inform("implicit cache coverage: "+"%2.1f".format((analyzer.hits + analyzer.misses).toDouble / (analyzer.uncached + analyzer.hits + analyzer.misses) * 100))
+        inform("time spent in failed   : "+showRelTyper(analyzer.failedSilent))
+        inform("       failed op=      : "+showRelTyper(analyzer.failedOpEqs))
+        inform("       failed apply    : "+showRelTyper(analyzer.failedApplies))
+      }
+      //for (t <- uniques.iterator) println("unique: "+t)
+    }
   }
 }
diff --git a/src/library/scala/collection/generic/MutableMapTemplate.scala b/src/library/scala/collection/generic/MutableMapTemplate.scala
index 62ae9671c7..334fa937a4 100644
--- a/src/library/scala/collection/generic/MutableMapTemplate.scala
+++ b/src/library/scala/collection/generic/MutableMapTemplate.scala
@@ -96,6 +96,15 @@ trait MutableMapTemplate[A, B, +This <: MutableMapTemplate[A, B, This] with muta
    */
   override def updated[B1 >: B](key: A, value: B1): mutable.Map[A, B1] = this + ((key, value))
 
+  /** If given key is already in this map, returns associated value
+   *  Otherwise, computes value from given expression `op`, stores with key
+   *  in map and returns that value.
+   */
+  def cached(key: A, op: => B) = get(key) match {
+    case Some(v) => v
+    case None => val v = op; update(key, v); v
+  }
+
   /** Add a new key/value mapping and return the map itself.
    *
    *  @param kv    the key/value mapping to be added
diff --git a/test/files/neg/badtok-1.check b/test/files/neg/badtok-1.check
index 3bd93c47f5..b05bc60161 100644
--- a/test/files/neg/badtok-1.check
+++ b/test/files/neg/badtok-1.check
@@ -1,7 +1,7 @@
 badtok-1.scala:2: error: unclosed character literal
 '42'
-   ^
-badtok-1.scala:2: error: expected class or object definition
-'42'
 ^
+badtok-1.scala:2: error: unclosed character literal
+'42'
+   ^
 two errors found