A few additional (but less dramatic) optimizati...

A few additional (but less dramatic) optimizations to implicit search,
courtesy of Tiark. No review.

3 files changed, 76 insertions, 20 deletions

diff --git a/src/compiler/scala/reflect/internal/Symbols.scala b/src/compiler/scala/reflect/internal/Symbols.scala
index 937ba0e42a..4678b69f53 100644
--- a/src/compiler/scala/reflect/internal/Symbols.scala
+++ b/src/compiler/scala/reflect/internal/Symbols.scala
@@ -404,7 +404,9 @@ trait Symbols /* extends reflect.generic.Symbols*/ { self: SymbolTable =>
         var is = infos
         (is eq null) || {
           while (is.prev ne null) { is = is.prev }
-          is.info.isComplete && is.info.typeParams.isEmpty
+          is.info.isComplete && !is.info.isHigherKinded // was: is.info.typeParams.isEmpty.
+          // YourKit listed the call to PolyType.typeParams as a hot spot but it is likely an artefact.
+          // The change to isHigherKinded did not reduce the total running time.
         }
       }
 
diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala
index 7db76fbf59..1459371349 100644
--- a/src/compiler/scala/reflect/internal/Types.scala
+++ b/src/compiler/scala/reflect/internal/Types.scala
@@ -860,7 +860,7 @@ trait Types /*extends reflect.generic.Types*/ { self: SymbolTable =>
      */
     //TODO: use narrow only for modules? (correct? efficiency gain?)
     def findMember(name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean): Symbol = {
-      val suspension = TypeVar.Suspension
+      var suspension: mutable.HashSet[TypeVar] = null
       // if this type contains type variables, put them to sleep for a while -- don't just wipe them out by
       // replacing them by the corresponding type parameter, as that messes up (e.g.) type variables in type refinements
       // without this, the matchesType call would lead to type variables on both sides
@@ -877,9 +877,10 @@ trait Types /*extends reflect.generic.Types*/ { self: SymbolTable =>
         // For now I modified it as below, which achieves the same without error.
         //
         // make each type var in this type use its original type for comparisons instead of collecting constraints
+        suspension = new mutable.HashSet
         this foreach {
-          case tv: TypeVar  => suspension suspend tv
-          case _            => ()
+          case tv: TypeVar  => tv.suspended = true; suspension += tv
+          case _            =>
         }
       }
 
@@ -912,7 +913,7 @@ trait Types /*extends reflect.generic.Types*/ { self: SymbolTable =>
                    (bcs0.head.hasTransOwner(bcs.head)))) {
                 if (name.isTypeName || stableOnly && sym.isStable) {
                   stopTimer(findMemberNanos, start)
-                  suspension.resumeAll
+                  if (suspension ne null) suspension foreach (_.suspended = false)
                   return sym
                 } else if (member == NoSymbol) {
                   member = sym
@@ -954,7 +955,7 @@ trait Types /*extends reflect.generic.Types*/ { self: SymbolTable =>
         excluded = excludedFlags
       } // while (continue)
       stopTimer(findMemberNanos, start)
-      suspension.resumeAll
+      if (suspension ne null) suspension foreach (_.suspended = false)
       if (members eq null) {
         if (member == NoSymbol) incCounter(noMemberCount)
         member
@@ -2317,6 +2318,7 @@ A type's typeSymbol should never be inspected directly.
   object TypeVar {
     // encapsulate suspension so we can automatically link the suspension of cloned
     // typevars to their original if this turns out to be necessary
+/*
     def Suspension = new Suspension
     class Suspension {
       private val suspended = mutable.HashSet[TypeVar]()
@@ -2331,7 +2333,7 @@ A type's typeSymbol should never be inspected directly.
         suspended.clear()
       }
     }
-
+*/
     def unapply(tv: TypeVar): Some[(Type, TypeConstraint)] = Some((tv.origin, tv.constr))
     def apply(origin: Type, constr: TypeConstraint) = new TypeVar(origin, constr, List(), List())
     // TODO why not initialise TypeConstraint with bounds of tparam?
@@ -2402,7 +2404,7 @@ A type's typeSymbol should never be inspected directly.
     // </region>
 
     // ignore subtyping&equality checks while true -- see findMember
-    private[TypeVar] var suspended = false
+    private[Types] var suspended = false
 
     /** Called when a TypeVar is involved in a subtyping check.  Result is whether
      *  this TypeVar could plausibly be a [super/sub]type of argument `tp` and if so,
diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
index c879f06f00..8b9107d473 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
@@ -11,6 +11,7 @@ import scala.collection.mutable.ListBuffer
 import scala.util.control.ControlThrowable
 import scala.tools.util.StringOps.{ countAsString, countElementsAsString }
 import symtab.Flags._
+import scala.annotation.tailrec
 
 /** This trait ...
  *
@@ -308,6 +309,7 @@ trait Infer {
      *  they are: perhaps someone more familiar with the intentional distinctions
      *  can examine the now much smaller concrete implementations below.
      */
+/*
     abstract class CompatibilityChecker {
       def resultTypeCheck(restpe: Type, arg: Type): Boolean
       def argumentCheck(arg: Type, param: Type): Boolean
@@ -367,23 +369,73 @@ trait Infer {
         case _                         => super.apply(tp, pt)
       }
     }
+*/
+    def isPlausiblyCompatible(tp: Type, pt: Type) = checkCompatibility(true, tp, pt)
+    def normSubType(tp: Type, pt: Type) = checkCompatibility(false, tp, pt)
+
+    @tailrec private def checkCompatibility(fast: Boolean, tp: Type, pt: Type): Boolean = tp match {
+      case mt @ MethodType(params, restpe) =>
+        if (mt.isImplicit)
+          checkCompatibility(fast, restpe, pt)
+        else pt match {
+          case tr @ TypeRef(pre, sym, args) =>
+
+            if (sym.isAliasType) checkCompatibility(fast, tp, pt.normalize)
+            else if (sym.isAbstractType) checkCompatibility(fast, tp, pt.bounds.lo)
+            else {
+              val len = args.length - 1
+              hasLength(params, len) &&
+              sym == FunctionClass(len) && {
+                var ps = params
+                var as = args
+                if (fast) {
+                  while (ps.nonEmpty && as.nonEmpty) {
+                    if (!isPlausiblySubType(as.head, ps.head.tpe))
+                      return false
+                    ps = ps.tail
+                    as = as.tail
+                  }
+                } else {
+                  while (ps.nonEmpty && as.nonEmpty) {
+                    if (!(as.head <:< ps.head.tpe))
+                      return false
+                    ps = ps.tail
+                    as = as.tail
+                  }
+                }
+                ps.isEmpty && as.nonEmpty && {
+                  val lastArg = as.head
+                  as.tail.isEmpty && checkCompatibility(fast, restpe, lastArg)
+                }
+              }
+            }
+
+          case _            => if (fast) false else tp <:< pt
+        }
+      case NullaryMethodType(restpe)  => checkCompatibility(fast, restpe, pt)
+      case PolyType(_, restpe)        => checkCompatibility(fast, restpe, pt)
+      case ExistentialType(_, qtpe)   => if (fast) checkCompatibility(fast, qtpe, pt) else normalize(tp) <:< pt // is !fast case needed??
+      case _                          => if (fast) isPlausiblySubType(tp, pt) else tp <:< pt
+    }
+
 
     /** This expresses more cleanly in the negative: there's a linear path
      *  to a final true or false.
      */
     private def isPlausiblySubType(tp1: Type, tp2: Type) = !isImpossibleSubType(tp1, tp2)
-    private def isImpossibleSubType(tp1: Type, tp2: Type) = {
-      (tp1.normalize.widen, tp2.normalize.widen) match {
-        case (TypeRef(_, sym1, _), TypeRef(_, sym2, _)) =>
-           sym1.isClass &&
-           sym2.isClass &&
-          !(sym1 isSubClass sym2) &&
-          !(sym1 isNumericSubClass sym2)
-        case (tp1@TypeRef(_, sym1, _), tp2@RefinedType(_,decls)) =>
-          !decls.toList.forall(s => tp1.member(s.name) != NoSymbol)
-        case _ =>
-          false
-      }
+    private def isImpossibleSubType(tp1: Type, tp2: Type) = tp1.normalize.widen match {
+      case tr1 @ TypeRef(_, sym1, _) =>
+        tp2.normalize.widen match {
+          case TypeRef(_, sym2, _) =>
+             sym1.isClass &&
+             sym2.isClass &&
+            !(sym1 isSubClass sym2) &&
+            !(sym1 isNumericSubClass sym2)
+          case RefinedType(_, decls) =>
+            decls.nonEmpty && tp1.member(decls.head.name) == NoSymbol
+          case _ => false
+        }
+      case _ => false
     }
 
     def isCompatible(tp: Type, pt: Type): Boolean = {