Optimized RefinedType

3 files changed, 248 insertions, 144 deletions

diff --git a/src/dotty/tools/dotc/core/SubTypers.scala b/src/dotty/tools/dotc/core/SubTypers.scala
index 2dcceceba..304bd9938 100644
--- a/src/dotty/tools/dotc/core/SubTypers.scala
+++ b/src/dotty/tools/dotc/core/SubTypers.scala
@@ -122,6 +122,13 @@ object TypeComparers {
         val base = tp1.baseType(clazz2)
         base.exists && isSubArgs(base.typeArgs, tp2.typeArgs, clazz2.typeParams) ||
         fourthTry(tp1, tp2)
+      case tp2: RefinedType1 =>
+        isSubType(tp1, tp2.parent) &&
+        isSubType(tp1.member(tp2.name1).info, tp2.info1)
+      case tp2: RefinedType2 =>
+        isSubType(tp1, tp2.parent) &&
+        isSubType(tp1.member(tp2.name1).info, tp2.info1) &&
+        isSubType(tp1.member(tp2.name2).info, tp2.info2)
       case tp2: RefinedType =>
         isSubType(tp1, tp2.parent) &&
         ((tp2.names, tp2.infos).zipped forall ((name, info) =>
@@ -178,8 +185,8 @@ object TypeComparers {
          (tp1 eq defn.NullType) && tp2.typeSymbol.isNonValueClass
          ||
          (!tp1.symbol.isClass && isSubType(tp1.info.bounds.hi, tp2)))
-      case RefinedType(parent, _) =>
-        isSubType(parent, tp2)
+      case tp1: RefinedType =>
+        isSubType(tp1.parent, tp2)
       case AndType(tp11, tp12) =>
         isSubType(tp11, tp2) || isSubType(tp12, tp2)
       case OrType(tp11, tp12) =>
diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 8fb3d69a0..558d34f52 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -1,6 +1,6 @@
 package dotty.tools.dotc.core
 
-import Contexts._, Types._, Symbols._
+import Contexts._, Types._, Symbols._, Names._
 
 trait TypeOps { this: Context =>
 
@@ -15,7 +15,7 @@ trait TypeOps { this: Context =>
       else if ((thisclazz isNonBottomSubClass clazz) &&
         (pre.widen.typeSymbol isNonBottomSubClass thisclazz))
         pre match {
-          case SuperType(thistp, _) => thistp
+          case SuperType(thispre, _) => thispre
           case _ => pre
         }
       else
@@ -84,129 +84,134 @@ trait TypeOps { this: Context =>
   }
 
   final def isVolatile(tp: Type): Boolean = {
-      def isAbstractIntersection(tp: Type): Boolean = tp match {
-        case tp: TypeRef => tp.isAbstractType
-        case AndType(l, r) => isAbstractIntersection(l) | isAbstractIntersection(l)
-        case OrType(l, r) => isAbstractIntersection(l) & isAbstractIntersection(r)
-        case _ => false
+    def isAbstractIntersection(tp: Type): Boolean = tp match {
+      case tp: TypeRef => tp.isAbstractType
+      case AndType(l, r) => isAbstractIntersection(l) | isAbstractIntersection(l)
+      case OrType(l, r) => isAbstractIntersection(l) & isAbstractIntersection(r)
+      case _ => false
+    }
+    def containsName(names: Set[Name], tp: RefinedType): Boolean = tp match {
+      case tp: RefinedType1 => names contains tp.name1
+      case tp: RefinedType2 => (names contains tp.name1) || (names contains tp.name2)
+      case _ => tp.names exists (names contains)
+    }
+    def test = {
+      tp match {
+        case ThisType(_) =>
+          false
+        case tp: RefinedType =>
+          tp.parent.isVolatile ||
+            isAbstractIntersection(tp.parent) &&
+            containsName(tp.abstractMemberNames(tp), tp)
+        case tp: TypeProxy =>
+          tp.underlying.isVolatile
+        case AndType(l, r) =>
+          l.isVolatile || r.isVolatile ||
+            isAbstractIntersection(l) && r.abstractMemberNames(tp).nonEmpty
+        case OrType(l, r) =>
+          l.isVolatile && r.isVolatile
+        case _ =>
+          false
       }
-      def test = {
-        tp match {
-          case ThisType(_) =>
-            false
-          case RefinedType(p, names) =>
-            p.isVolatile ||
-              isAbstractIntersection(p) &&
-              (names exists (tp.abstractMemberNames(tp) contains))
-          case tp: TypeProxy =>
-            tp.underlying.isVolatile
-          case AndType(l, r) =>
-            l.isVolatile || r.isVolatile ||
-              isAbstractIntersection(l) && r.abstractMemberNames(tp).nonEmpty
-          case OrType(l, r) =>
-            l.isVolatile && r.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
+    import ctx.root.{ volatileRecursions, pendingVolatiles }
+    try {
+      volatileRecursions += 1
+      if (volatileRecursions < LogVolatileThreshold)
+        test
+      else if (pendingVolatiles(tp))
+        false // we can return false here, because a cycle will be detected
+      // here afterwards and an error will result anyway.
+      else
+        try {
+          pendingVolatiles += tp
+          test
+        } finally {
+          pendingVolatiles -= tp
+        }
+    } finally {
+      volatileRecursions -= 1
+    }
+  }
+
+  final def glb(tp1: Type, tp2: Type): Type =
+    if (tp1 eq tp2) tp1
+    else if (tp1.isWrong) tp2
+    else if (tp2.isWrong) tp1
+    else tp2 match {
+      case OrType(tp21, tp22) =>
+        tp1 & tp21 | tp1 & tp22
+      case _ =>
+        tp1 match {
+          case OrType(tp11, tp12) =>
+            tp11 & tp2 | tp12 & tp2
           case _ =>
-            false
+            val t1 = mergeIfSub(tp1, tp2)
+            if (t1.exists) t1
+            else {
+              val t2 = mergeIfSub(tp2, tp1)
+              if (t2.exists) t2
+              else AndType(tp1, tp2)
+            }
         }
-      }
-      // 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
-      import ctx.root.{volatileRecursions, pendingVolatiles}
-      try {
-        volatileRecursions += 1
-        if (volatileRecursions < LogVolatileThreshold)
-          test
-        else if (pendingVolatiles(tp))
-          false // we can return false here, because a cycle will be detected
-                // here afterwards and an error will result anyway.
-        else
-          try {
-            pendingVolatiles += tp
-            test
-          } finally {
-            pendingVolatiles -= tp
-          }
-      } finally {
-        volatileRecursions -= 1
-      }
     }
 
-    final def glb (tp1: Type, tp2: Type): Type =
-      if (tp1 eq tp2) tp1
-      else if (tp1.isWrong) tp2
-      else if (tp2.isWrong) tp1
-      else tp2 match {
-        case OrType(tp21, tp22) =>
-          tp1 & tp21 | tp1 & tp22
-        case _ =>
-          tp1 match {
-            case OrType(tp11, tp12) =>
-              tp11 & tp2 | tp12 & tp2
-            case _ =>
-              val t1 = mergeIfSub(tp1, tp2)
-              if (t1.exists) t1
-              else {
-                val t2 = mergeIfSub(tp2, tp1)
-                if (t2.exists) t2
-                else AndType(tp1, tp2)
-              }
-          }
+  def lub(tp1: Type, tp2: Type): Type =
+    if (tp1 eq tp2) tp1
+    else if (tp1.isWrong) tp1
+    else if (tp2.isWrong) tp2
+    else {
+      val t1 = mergeIfSuper(tp1, tp2)
+      if (t1.exists) t1
+      else {
+        val t2 = mergeIfSuper(tp2, tp1)
+        if (t2.exists) t2
+        else OrType(tp1, tp2)
       }
+    }
 
-    def lub (tp1: Type, tp2: Type): Type =
-      if (tp1 eq tp2) tp1
-      else if (tp1.isWrong) tp1
-      else if (tp2.isWrong) tp2
-      else {
-        val t1 = mergeIfSuper(tp1, tp2)
-        if (t1.exists) t1
+  /** Merge `t1` into `tp2` if t1 is a subtype of some part of tp2.
+   */
+  private def mergeIfSub(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
+    if (tp1 <:< tp2)
+      if (tp2 <:< tp1) tp2 else tp1
+    else tp2 match {
+      case tp2 @ AndType(tp21, tp22) =>
+        val lower1 = mergeIfSub(tp1, tp21)
+        if (lower1 eq tp21) tp2
+        else if (lower1.exists) lower1 & tp22
         else {
-          val t2 = mergeIfSuper(tp2, tp1)
-          if (t2.exists) t2
-          else OrType(tp1, tp2)
+          val lower2 = mergeIfSub(tp1, tp22)
+          if (lower2 eq tp22) tp2
+          else if (lower2.exists) tp21 & lower2
+          else NoType
         }
-      }
-
-    /** Merge `t1` into `tp2` if t1 is a subtype of some part of tp2.
-     */
-    private def mergeIfSub(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
-      if (tp1 <:< tp2)
-        if (tp2 <:< tp1) tp2 else tp1
-      else tp2 match {
-        case tp2 @ AndType(tp21, tp22) =>
-          val lower1 = mergeIfSub(tp1, tp21)
-          if (lower1 eq tp21) tp2
-          else if (lower1.exists) lower1 & tp22
-          else {
-            val lower2 = mergeIfSub(tp1, tp22)
-            if (lower2 eq tp22) tp2
-            else if (lower2.exists) tp21 & lower2
-            else NoType
-          }
-        case _ =>
-          NoType
-      }
+      case _ =>
+        NoType
+    }
 
-   /** Merge `tp1` into `tp2` if tp1 is a supertype of some part of tp2.
-    */
-    private def mergeIfSuper(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
-      if (tp2 <:< tp1)
-        if (tp1 <:< tp2) tp2 else tp1
-      else tp2 match {
-        case tp2 @ OrType(tp21, tp22) =>
-          val higher1 = mergeIfSuper(tp1, tp21)
-          if (higher1 eq tp21) tp2
-          else if (higher1.exists) higher1 | tp22
-          else {
-            val higher2 = mergeIfSuper(tp1, tp22)
-            if (higher2 eq tp22) tp2
-            else if (higher2.exists) tp21 | higher2
-            else NoType
-          }
-        case _ =>
-          NoType
-      }
+  /** Merge `tp1` into `tp2` if tp1 is a supertype of some part of tp2.
+   */
+  private def mergeIfSuper(tp1: Type, tp2: Type)(implicit ctx: Context): Type =
+    if (tp2 <:< tp1)
+      if (tp1 <:< tp2) tp2 else tp1
+    else tp2 match {
+      case tp2 @ OrType(tp21, tp22) =>
+        val higher1 = mergeIfSuper(tp1, tp21)
+        if (higher1 eq tp21) tp2
+        else if (higher1.exists) higher1 | tp22
+        else {
+          val higher2 = mergeIfSuper(tp1, tp22)
+          if (higher2 eq tp22) tp2
+          else if (higher2.exists) tp21 | higher2
+          else NoType
+        }
+      case _ =>
+        NoType
+    }
 }
 
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 624720d50..a45ea7596 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -110,7 +110,16 @@ object Types {
     final def memberNames(pre: Type, keepOnly: NameFilter)(implicit ctx: Context): Set[Name] = this match {
       case tp: ClassInfo =>
         tp.classd.memberNames(keepOnly) filter (keepOnly(pre, _))
-      case tp: RefinedType =>
+      case tp: RefinedType1 =>
+        var ns = tp.parent.memberNames(pre, keepOnly)
+        if (keepOnly(pre, tp.name1)) ns += tp.name1
+        ns
+      case tp: RefinedType2 =>
+        var ns = tp.parent.memberNames(pre, keepOnly)
+        if (keepOnly(pre, tp.name1)) ns += tp.name1
+        if (keepOnly(pre, tp.name2)) ns += tp.name2
+        ns
+      case tp: RefinedTypeN =>
         tp.parent.memberNames(pre, keepOnly) ++ (tp.names filter (keepOnly(pre, _))).toSet
       case tp: AndType =>
         tp.tp1.memberNames(pre, keepOnly) | tp.tp2.memberNames(pre, keepOnly)
@@ -470,6 +479,18 @@ object Types {
       finishHash(hashing.mix(seed, elemHash), arity + 1)
     }
 
+    private def finishHash(seed: Int, arity: Int, tp1: Type, tp2: Type): Int = {
+      val elemHash = tp1.hash
+      if (elemHash == NotCached) return NotCached
+      finishHash(hashing.mix(seed, elemHash), arity + 1, tp2)
+    }
+
+    private def finishHash(seed: Int, arity: Int, tp1: Type, tp2: Type, tp3: Type): Int = {
+      val elemHash = tp1.hash
+      if (elemHash == NotCached) return NotCached
+      finishHash(hashing.mix(seed, elemHash), arity + 1, tp2, tp3)
+    }
+
     private def finishHash(seed: Int, arity: Int, tps: List[Type]): Int = {
       var h = seed
       var xs = tps
@@ -496,20 +517,24 @@ object Types {
     protected def doHash(tp: Type): Int =
       finishHash(hashSeed, 0, tp)
 
-    protected def doHash(tp1: Type, tp2: Type): Int = {
-      val elemHash = tp1.hash
-      if (elemHash == NotCached) return NotCached
-      finishHash(hashing.mix(hashSeed, elemHash), 1, tp2)
-    }
-
     protected def doHash(x1: Any, tp2: Type): Int =
       finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2)
 
+    protected def doHash(tp1: Type, tp2: Type): Int =
+      finishHash(hashSeed, 0, tp1, tp2)
+
+    protected def doHash(x1: Any, tp2: Type, tp3: Type): Int =
+      finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tp3)
+
     protected def doHash(tp1: Type, tps2: List[Type]): Int =
       finishHash(hashSeed, 0, tp1, tps2)
 
     protected def doHash(x1: Any, tp2: Type, tps3: List[Type]): Int =
       finishHash(hashing.mix(hashSeed, x1.hashCode), 1, tp2, tps3)
+
+    protected def doHash(x1: Any, x2: Any, tp3: Type, tp4: Type, tp5: Type) =
+      finishHash(hashing.mix(hashing.mix(hashSeed, x1.hashCode), x2.hashCode), 2, tp3, tp4, tp5)
+
   } // end Type
 
   /** A marker trait for cached types */
@@ -737,33 +762,88 @@ object Types {
 
   // --- Refined Type ---------------------------------------------------------
 
-  case class RefinedType(parent: Type, names: List[Name])(infosExpr: RefinedType => List[Type]) extends CachedProxyType {
+  abstract case class RefinedType(parent: Type) extends CachedProxyType {
 
     override def underlying(implicit ctx: Context) = parent
 
-    lazy val infos = infosExpr(this)
-
-    def derivedRefinedType(parent1: Type, names1: List[Name], infos1: List[Type])(implicit ctx: Context): RefinedType =
-      if ((parent1 eq parent) && (names1 eq names) && (infos1 eq infos)) this
+    def derivedRefinedType(parent: Type, names: List[Name], infos: List[Type])(implicit ctx: Context): RefinedType =
+      if ((parent eq this.parent) && (names eq this.names) && (infos eq this.infos)) this
       else
-        RefinedType(parent1, names1) { rt =>
-          val thistp = RefinedThis(rt)
-          infos1 map (_.substThis(this, thistp))
-        }
+        RefinedType(parent, names, infos map (info => (rt: RefinedType) => info.substThis(this, RefinedThis(rt))))
+
+    def names: List[Name]
+
+    def infos: List[Type]
+
+    def info(name: Name): Type
 
     def findDecl(name: Name, pre: Type)(implicit ctx: Context): Denotation = {
+      val tpe = info(name)
+      if (tpe == NoType) NoDenotation
+      else new JointRefDenotation(NoSymbol, tpe.substThis(this, pre), Period.allInRun(ctx.runId))
+    }
+  }
+
+  object RefinedType {
+
+    def make(parent: Type, names: List[Name], infofs: List[RefinedType => Type])(implicit ctx: Context): Type =
+      if (names.isEmpty) parent
+      else apply(parent, names, infofs)
+
+    def apply(parent: Type, names: List[Name], infofs: List[RefinedType => Type])(implicit ctx: Context): RefinedType =
+      names.length match {
+        case 1 => apply(parent, names.head, infofs.head)
+        case 2 => apply(parent, names.head, infofs.head, names.tail.head, infofs.tail.head)
+        case _ => unique(new RefinedTypeN(parent, names, infofs))
+      }
+
+    def apply(parent: Type, name1: Name, infof1: RefinedType => Type)(implicit ctx: Context): RefinedType1 =
+      unique(new RefinedType1(parent, name1, infof1))
+
+    def apply(parent: Type, name1: Name, infof1: RefinedType => Type, name2: Name, infof2: RefinedType => Type)(implicit ctx: Context): RefinedType2 =
+      unique(new RefinedType2(parent, name1, infof1, name2, infof2))
+  }
+
+  class RefinedType1(parent: Type, val name1: Name, infof1: RefinedType => Type) extends RefinedType(parent) {
+    val info1 = infof1(this)
+    def names = name1 :: Nil
+    def infos = info1 :: Nil
+    def info(name: Name) =
+      if (name == name1) info1
+      else NoType
+    def derivedRefinedType1(parent: Type, name1: Name, info1: Type)(implicit ctx: Context): RefinedType1 =
+      if ((parent eq this.parent) && (name1 eq this.name1) && (info1 eq this.info1)) this
+      else RefinedType(parent, name1, rt => info1.substThis(this, RefinedThis(rt)))
+    override def computeHash = doHash(name1, info1, parent)
+  }
+
+  class RefinedType2(parent: Type, val name1: Name, infof1: RefinedType => Type, val name2: Name, infof2: RefinedType => Type) extends RefinedType(parent) {
+    val info1 = infof1(this)
+    val info2 = infof2(this)
+    def names = name1 :: name2 :: Nil
+    def infos = info1 :: info2 :: Nil
+    def info(name: Name) =
+      if (name == name1) info1
+      else if (name == name2) info2
+      else NoType
+    def derivedRefinedType2(parent: Type, name1: Name, info1: Type, name2: Name, info2: Type)(implicit ctx: Context): RefinedType2 =
+      if ((parent eq this.parent) && (name1 eq this.name1) && (info1 eq this.info1) && (name2 eq this.name2) && (info2 eq this.info2)) this
+      else RefinedType(parent, name1, rt => info1.substThis(this, RefinedThis(rt)), name2, rt => info2.substThis(this, RefinedThis(rt)))
+    override def computeHash = doHash(name1, name2, info1, info2, parent)
+  }
+
+  class RefinedTypeN(parent: Type, val names: List[Name], infofs: List[RefinedType => Type]) extends RefinedType(parent) {
+    val infos = infofs map (_(this))
+    def info(name: Name): Type = {
       var ns = names
       var is = infos
-      var denot: Denotation = NoDenotation
-      while (ns.nonEmpty && (denot eq NoDenotation)) {
-        if (ns.head == name)
-          denot = new JointRefDenotation(NoSymbol, is.head.substThis(this, pre), Period.allInRun(ctx.runId))
+      while (ns.nonEmpty) {
+        if (ns.head == name) return is.head
         ns = ns.tail
         is = is.tail
       }
-      denot
+      NoType
     }
-
     override def computeHash = doHash(names, parent, infos)
   }
 
@@ -1052,8 +1132,14 @@ object Types {
           tp.derivedTypeBounds(this(lo), this(hi))
         }
 
-      case tp @ RefinedType(parent, names) =>
-        tp.derivedRefinedType(this(parent), names, tp.infos mapConserve this)
+      case tp: RefinedType1 =>
+        tp.derivedRefinedType1(this(tp.parent), tp.name1, this(tp.info1))
+
+      case tp: RefinedType2 =>
+        tp.derivedRefinedType2(this(tp.parent), tp.name1, this(tp.info1), tp.name2, this(tp.info2))
+
+      case tp: RefinedTypeN =>
+        tp.derivedRefinedType(this(tp.parent), tp.names, tp.infos mapConserve this)
 
       case tp @ AnnotatedType(annots, underlying) =>
         tp.derivedAnnotatedType(mapOverAnnotations(annots), this(underlying))
@@ -1122,8 +1208,14 @@ object Types {
       case TypeBounds(lo, hi) =>
         this(this(x, lo), hi)
 
-      case tp @ RefinedType(parent, names) =>
-        (this(x, parent) /: tp.infos)(apply)
+      case tp: RefinedType1 =>
+        this(this(x, tp.parent), tp.info1)
+
+      case tp: RefinedType2 =>
+        this(this(this(x, tp.parent), tp.info1), tp.info2)
+
+      case tp: RefinedTypeN =>
+        (this(x, tp.parent) /: tp.infos)(apply)
 
       case AnnotatedType(annots, underlying) =>
         this((x /: annots)(apply), underlying)