Merge pull request #984 from dotty-staging/optimize-subtyping

Fix inefficieny in the presence of aliasing.

6 files changed, 43 insertions, 64 deletions

diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index be070dace..661975dab 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -286,7 +286,7 @@ class TypeApplications(val self: Type) extends AnyVal {
    */
   final def baseArgInfos(base: Symbol)(implicit ctx: Context): List[Type] =
     if (self derivesFrom base)
-      base.typeParams map (param => self.member(param.name).info.argInfo(param))
+      base.typeParams map (param => self.member(param.name).info.argInfo)
     else
       Nil
 
@@ -311,7 +311,7 @@ class TypeApplications(val self: Type) extends AnyVal {
   /** The first type argument of the base type instance wrt `base` of this type */
   final def firstBaseArgInfo(base: Symbol)(implicit ctx: Context): Type = base.typeParams match {
     case param :: _ if self derivesFrom base =>
-      self.member(param.name).info.argInfo(param)
+      self.member(param.name).info.argInfo
     case _ =>
       NoType
   }
@@ -369,9 +369,8 @@ class TypeApplications(val self: Type) extends AnyVal {
   /** If this is an encoding of a (partially) applied type, return its arguments,
    *  otherwise return Nil.
    *  Existential types in arguments are returned as TypeBounds instances.
-   *  @param interpolate   See argInfo
    */
-  final def argInfos(interpolate: Boolean)(implicit ctx: Context): List[Type] = {
+  final def argInfos(implicit ctx: Context): List[Type] = {
     var tparams: List[TypeSymbol] = null
     def recur(tp: Type, refineCount: Int): mutable.ListBuffer[Type] = tp.stripTypeVar match {
       case tp @ RefinedType(tycon, name) =>
@@ -381,7 +380,7 @@ class TypeApplications(val self: Type) extends AnyVal {
           if (tparams == null) tparams = tycon.typeParams
           if (buf.size < tparams.length) {
             val tparam = tparams(buf.size)
-            if (name == tparam.name) buf += tp.refinedInfo.argInfo(tparam, interpolate)
+            if (name == tparam.name) buf += tp.refinedInfo.argInfo
             else null
           } else null
         }
@@ -393,8 +392,6 @@ class TypeApplications(val self: Type) extends AnyVal {
     if (buf == null) Nil else buf.toList
   }
 
-  final def argInfos(implicit ctx: Context): List[Type] = argInfos(interpolate = true)
-
   /** Argument types where existential types in arguments are disallowed */
   def argTypes(implicit ctx: Context) = argInfos mapConserve noBounds
 
@@ -415,31 +412,13 @@ class TypeApplications(val self: Type) extends AnyVal {
       self
   }
 
-  /** If this is the image of a type argument to type parameter `tparam`,
-   *  recover the type argument, otherwise NoType.
-   *  @param interpolate   If true, replace type bounds as arguments corresponding to
-   *                       variant type parameters by their dominating element. I.e. an argument
-   *
-   *                           T <: U
-   *
-   *                       for a covariant type-parameter becomes U, and an argument
-   *
-   *                           T >: L
-   *
-   *                       for a contravariant type-parameter becomes L.
+  /** If this is the image of a type argument; recover the type argument,
+   *  otherwise NoType.
    */
-  final def argInfo(tparam: Symbol, interpolate: Boolean = true)(implicit ctx: Context): Type = self match {
+  final def argInfo(implicit ctx: Context): Type = self match {
     case self: TypeAlias => self.alias
-    case TypeBounds(lo, hi) =>
-      if (interpolate) {
-        val v = tparam.variance
-        if (v > 0 && (lo isRef defn.NothingClass)) hi
-        else if (v < 0 && (hi isRef defn.AnyClass)) lo
-        else self
-      }
-      else self
-    case _ =>
-      NoType
+    case self: TypeBounds => self
+    case _ => NoType
   }
 
   /** The element type of a sequence or array */
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 0d46a4b90..d0abe86a7 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -140,38 +140,38 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
 
   private def firstTry(tp1: Type, tp2: Type): Boolean = tp2 match {
     case tp2: NamedType =>
-      def compareAlias(info1: Type) = tp2.info match {
-        case info2: TypeAlias => isSubType(tp1, info2.alias)
-        case _ => info1 match {
-          case info1: TypeAlias => isSubType(info1.alias, tp2)
-          case _ => false
-        }
-      }
-      def compareNamed = {
-        implicit val ctx: Context = this.ctx // Dotty deviation: implicits need explicit type
-        tp1 match {
-          case tp1: NamedType =>
-            val sym1 = tp1.symbol
-            compareAlias(tp1.info) ||
-            (if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol))
-               ctx.erasedTypes || sym1.isStaticOwner || isSubType(tp1.prefix, tp2.prefix)
-            else
-              (tp1.name eq tp2.name) &&
-              isSubType(tp1.prefix, tp2.prefix) &&
-              (tp1.signature == tp2.signature) &&
-              !tp1.isInstanceOf[WithFixedSym] &&
-              !tp2.isInstanceOf[WithFixedSym]
-            ) ||
-            compareHK(tp1, tp2, inOrder = true) ||
-            compareHK(tp2, tp1, inOrder = false) ||
-            thirdTryNamed(tp1, tp2)
-          case _ =>
-            compareHK(tp2, tp1, inOrder = false) ||
-            compareAlias(NoType) ||
-            secondTry(tp1, tp2)
+      def compareNamed(tp1: Type, tp2: NamedType): Boolean = {
+        implicit val ctx: Context = this.ctx
+        tp2.info match {
+          case info2: TypeAlias => firstTry(tp1, info2.alias)
+          case _ => tp1 match {
+            case tp1: NamedType =>
+              tp1.info match {
+                case info1: TypeAlias => compareNamed(info1.alias, tp2)
+                case _ =>
+                  val sym1 = tp1.symbol
+                  (if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol))
+                     ctx.erasedTypes ||
+                     sym1.isStaticOwner ||
+                     isSubType(tp1.prefix, tp2.prefix) ||
+                     thirdTryNamed(tp1, tp2)
+                   else
+                     (tp1.name eq tp2.name) &&
+                     isSubType(tp1.prefix, tp2.prefix) &&
+                     (tp1.signature == tp2.signature) &&
+                     !tp1.isInstanceOf[WithFixedSym] &&
+                     !tp2.isInstanceOf[WithFixedSym] ||
+                     compareHK(tp1, tp2, inOrder = true) ||
+                     compareHK(tp2, tp1, inOrder = false) ||
+                     thirdTryNamed(tp1, tp2))
+              }
+            case _ =>
+              compareHK(tp2, tp1, inOrder = false) ||
+              secondTry(tp1, tp2)
+          }
         }
       }
-      compareNamed
+      compareNamed(tp1, tp2)
     case tp2: ProtoType =>
       isMatchedByProto(tp2, tp1)
     case tp2: BoundType =>
diff --git a/src/dotty/tools/dotc/core/tasty/TreePickler.scala b/src/dotty/tools/dotc/core/tasty/TreePickler.scala
index d98ebb4d1..c0136538b 100644
--- a/src/dotty/tools/dotc/core/tasty/TreePickler.scala
+++ b/src/dotty/tools/dotc/core/tasty/TreePickler.scala
@@ -211,7 +211,7 @@ class TreePickler(pickler: TastyPickler) {
       case tpe: SkolemType =>
         pickleType(tpe.info)
       case tpe: RefinedType =>
-        val args = tpe.argInfos(interpolate = false)
+        val args = tpe.argInfos
         if (args.isEmpty) {
           writeByte(REFINEDtype)
           withLength {
diff --git a/src/dotty/tools/dotc/printing/RefinedPrinter.scala b/src/dotty/tools/dotc/printing/RefinedPrinter.scala
index 7065976dc..06fe0c9ef 100644
--- a/src/dotty/tools/dotc/printing/RefinedPrinter.scala
+++ b/src/dotty/tools/dotc/printing/RefinedPrinter.scala
@@ -109,7 +109,7 @@ class RefinedPrinter(_ctx: Context) extends PlainPrinter(_ctx) {
       }
     homogenize(tp) match {
       case tp: RefinedType =>
-        val args = tp.argInfos(interpolate = false)
+        val args = tp.argInfos
         if (args.nonEmpty) {
           val tycon = tp.unrefine
           val cls = tycon.typeSymbol
diff --git a/src/dotty/tools/dotc/reporting/Reporter.scala b/src/dotty/tools/dotc/reporting/Reporter.scala
index 5cad0a077..f98d85ce9 100644
--- a/src/dotty/tools/dotc/reporting/Reporter.scala
+++ b/src/dotty/tools/dotc/reporting/Reporter.scala
@@ -155,7 +155,7 @@ trait Reporting { this: Context =>
     else {
       // Avoid evaluating question multiple time, since each evaluation
       // may cause some extra logging output.
-      val q: String = question
+      lazy val q: String = question
       traceIndented[T](s"==> $q?", (res: Any) => s"<== $q = ${resStr(res)}")(op)
     }
   }
diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala
index 999efff09..5eebdbad1 100644
--- a/src/dotty/tools/dotc/typer/Namer.scala
+++ b/src/dotty/tools/dotc/typer/Namer.scala
@@ -848,7 +848,7 @@ class Namer { typer: Typer =>
     def apply(tp: Type): Type = {
       tp match {
         case tp: RefinedType =>
-          val args = tp.argInfos(interpolate = false).mapconserve(this)
+          val args = tp.argInfos.mapconserve(this)
           if (args.nonEmpty) {
             val tycon = tp.withoutArgs(args)
             val tparams = tycon.typeParams