Merge pull request #1001 from dotty-staging/change-distribute-or

Change distribute or

8 files changed, 174 insertions, 88 deletions

diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala
index 7e3615416..cf43d277e 100644
--- a/src/dotty/tools/dotc/config/Config.scala
+++ b/src/dotty/tools/dotc/config/Config.scala
@@ -87,6 +87,15 @@ object Config {
   /** Check that certain types cannot be created in erasedTypes phases */
   final val checkUnerased = true
 
+  /** In `derivedSelect`, rewrite
+   *
+   *      (S & T)#A  -->  S#A & T#A
+   *      (S | T)#A  -->  S#A | T#A
+   *
+   *  Not sure whether this is useful. Preliminary measurements show a slowdown of about
+   *  7% for the build when this option is enabled.
+   */
+  final val splitProjections = false
 
   /** Initial size of superId table */
   final val InitialSuperIdsSize = 4096
diff --git a/src/dotty/tools/dotc/config/ScalaSettings.scala b/src/dotty/tools/dotc/config/ScalaSettings.scala
index 62b071372..0c381c077 100644
--- a/src/dotty/tools/dotc/config/ScalaSettings.scala
+++ b/src/dotty/tools/dotc/config/ScalaSettings.scala
@@ -173,6 +173,7 @@ class ScalaSettings extends Settings.SettingGroup {
   val Ypatmatdebug = BooleanSetting("-Ypatmat-debug", "Trace pattern matching translation.")
   val Yexplainlowlevel = BooleanSetting("-Yexplain-lowlevel", "When explaining type errors, show types at a lower level.")
   val YnoDoubleBindings = BooleanSetting("-Yno-double-bindings", "Assert no namedtype is bound twice (should be enabled only if program is error-free).")
+  val YshowVarBounds = BooleanSetting("-Yshow-var-bounds", "Print type variables with their bounds")
 
   val optimise = BooleanSetting("-optimise", "Generates faster bytecode by applying optimisations to the program") withAbbreviation "-optimize"
 
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index fbab4ee39..8aea3381a 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -173,8 +173,46 @@ object TypeApplications {
     if (tparams.isEmpty) args
     else args.zipWithConserve(tparams)((arg, tparam) => arg.etaExpandIfHK(tparam.infoOrCompleter))
 
+  /** The references `<rt>.this.$hk0, ..., <rt>.this.$hk<n-1>`. */
   def argRefs(rt: RefinedType, n: Int)(implicit ctx: Context) =
     List.range(0, n).map(i => RefinedThis(rt).select(tpnme.hkArg(i)))
+
+  /** Merge `tp1` and `tp2` under a common lambda, combining them with `op`.
+   *  @param tparams1   The type parameters of `tp1`
+   *  @param tparams2   The type parameters of `tp2`
+   *  @pre tparams1.length == tparams2.length
+   *  Produces the type lambda
+   *
+   *     [v1 X1 B1, ..., vn Xn Bn] -> op(tp1[X1, ..., Xn], tp2[X1, ..., Xn])
+   *
+   *  where
+   *
+   *   - variances `vi` are the variances of corresponding type parameters for `tp1`
+   *     or `tp2`, or are 0 of the latter disagree.
+   *   - bounds `Bi` are the intersection of the corresponding type parameter bounds
+   *     of `tp1` and `tp2`.
+   */
+  def hkCombine(tp1: Type, tp2: Type,
+      tparams1: List[TypeSymbol], tparams2: List[TypeSymbol], op: (Type, Type) => Type)
+      (implicit ctx: Context): Type = {
+    val variances = (tparams1, tparams2).zipped.map { (tparam1, tparam2) =>
+      val v1 = tparam1.variance
+      val v2 = tparam2.variance
+      if (v1 == v2) v1 else 0
+    }
+    val bounds: List[RefinedType => TypeBounds] =
+      (tparams1, tparams2).zipped.map { (tparam1, tparam2) =>
+        val b1: RefinedType => TypeBounds =
+          tp1.memberInfo(tparam1).bounds.internalizeFrom(tparams1)
+        val b2: RefinedType => TypeBounds =
+          tp2.memberInfo(tparam2).bounds.internalizeFrom(tparams2)
+        (rt: RefinedType) => b1(rt) & b2(rt)
+      }
+    val app1: RefinedType => Type = rt => tp1.appliedTo(argRefs(rt, tparams1.length))
+    val app2: RefinedType => Type = rt => tp2.appliedTo(argRefs(rt, tparams2.length))
+    val body: RefinedType => Type = rt => op(app1(rt), app2(rt))
+    TypeLambda(variances, bounds, body)
+  }
 }
 
 import TypeApplications._
@@ -273,6 +311,14 @@ class TypeApplications(val self: Type) extends AnyVal {
       false
   }
 
+  /** Replace references to type parameters with references to hk arguments `this.$hk_i`
+   * Care is needed not to cause cyclic reference errors, hence `SafeSubstMap`.
+   */
+  private[TypeApplications] def internalizeFrom[T <: Type](tparams: List[Symbol])(implicit ctx: Context): RefinedType => T =
+    (rt: RefinedType) =>
+      new ctx.SafeSubstMap(tparams , argRefs(rt, tparams.length))
+        .apply(self).asInstanceOf[T]
+
   /** Lambda abstract `self` with given type parameters. Examples:
    *
    *      type T[X] = U        becomes    type T = [X] -> U
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 163fa4919..1e90bd6c8 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -144,49 +144,43 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       def compareNamed(tp1: Type, tp2: NamedType): Boolean = {
         implicit val ctx: Context = this.ctx
         tp2.info match {
-          case info2: TypeAlias if tp2.prefix.isStable =>
-            // If prefix is not stable (i.e. is not a path), then we have a true
-            // projection `T # A` which is treated as the existential type
-            // `ex(x: T)x.A`. We need to deal with the existential first before
-            // following the alias. If we did follow the alias we could be
-            // unsound as well as incomplete. An example of this was discovered in Iter2.scala.
-            // It failed to validate the subtype test
-            //
-            //   (([+X] -> Seq[X]) & C)[SA] <: C[SA]
-            //
-            // Both sides are projections of $Apply. The left $Apply does have an
-            // aliased info, namely, Seq[SA]. But that is not a subtype of C[SA].
-            // The problem is that, with the prefix not being a path, an aliased info
-            // does not necessarily give all of the information of the original projection.
-            // So we can't follow the alias without a backup strategy. If the alias
-            // would appear on the right then I believe this can be turned into a case
-            // of unsoundness.
-            isSubType(tp1, info2.alias)
+          case info2: TypeAlias => isSubType(tp1, info2.alias)
           case _ => tp1 match {
             case tp1: NamedType =>
               tp1.info match {
-                case info1: TypeAlias if tp1.prefix.isStable =>
-                  isSubType(info1.alias, tp2)
+                case info1: TypeAlias =>
+                  if (isSubType(info1.alias, tp2)) return true
+                  if (tp1.prefix.isStable) return false
+                    // If tp1.prefix is stable, the alias does contain all information about the original ref, so
+                    // there's no need to try something else. (This is important for performance).
+                    // To see why we cannot in general stop here, consider:
+                    //
+                    //     trait C { type A }
+                    //     trait D { type A = String }
+                    //     (C & D)#A <: C#A
+                    //
+                    // Following the alias leads to the judgment `String <: C#A` which is false.
+                    // However the original judgment should be true.
                 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)
               }
+              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]
+                ) ||
+                compareHkApply(tp1, tp2, inOrder = true) ||
+                compareHkApply(tp2, tp1, inOrder = false) ||
+                thirdTryNamed(tp1, tp2)
             case _ =>
-              compareHK(tp2, tp1, inOrder = false) ||
+              compareHkApply(tp2, tp1, inOrder = false) ||
               secondTry(tp1, tp2)
           }
         }
@@ -258,11 +252,13 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
   private def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match {
     case tp1: NamedType =>
       tp1.info match {
-        case info1: TypeAlias => isSubType(info1.alias, tp2)
+        case info1: TypeAlias =>
+          if (isSubType(info1.alias, tp2)) return true
+          if (tp1.prefix.isStable) return false
         case _ =>
-          compareHK(tp1, tp2, inOrder = true) ||
-          thirdTry(tp1, tp2)
       }
+      compareHkApply(tp1, tp2, inOrder = true) ||
+      thirdTry(tp1, tp2)
     case tp1: PolyParam =>
       def flagNothingBound = {
         if (!frozenConstraint && tp2.isRef(defn.NothingClass) && state.isGlobalCommittable) {
@@ -356,8 +352,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
         isSubType(tp1, tp2.parent) &&
           (name2 == nme.WILDCARD || hasMatchingMember(name2, tp1, tp2))
       }
-      def etaExpandedSubType(tp1: Type) =
-        isSubType(tp1.typeConstructor.EtaExpand(tp2.typeParams), tp2)
       def compareRefined: Boolean = {
         val tp1w = tp1.widen
         val skipped2 = skipMatching(tp1w, tp2)
@@ -371,7 +365,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
             case _ =>
               compareRefinedSlow ||
               fourthTry(tp1, tp2) ||
-              needsEtaLift(tp1, tp2) && testLifted(tp1, tp2, tp2.typeParams, etaExpandedSubType)
+              compareHkLambda(tp2, tp1, inOrder = false)
           }
         else // fast path, in particular for refinements resulting from parameterization.
           isSubType(tp1, skipped2) &&
@@ -491,10 +485,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       }
       isNewSubType(tp1.underlying.widenExpr, tp2) || comparePaths
     case tp1: RefinedType =>
-       isNewSubType(tp1.parent, tp2) ||
-         needsEtaLift(tp2, tp1) &&
-         tp2.typeParams.length == tp1.typeParams.length &&
-         isSubType(tp1, tp2.EtaExpand(tp1.typeParams))
+      isNewSubType(tp1.parent, tp2) || compareHkLambda(tp1, tp2, inOrder = true)
     case AndType(tp11, tp12) =>
       // Rewrite (T111 | T112) & T12 <: T2 to (T111 & T12) <: T2 and (T112 | T12) <: T2
       // and analogously for T11 & (T121 | T122) & T12 <: T2
@@ -525,14 +516,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       false
   }
 
-  /** Does `tp` need to be eta lifted to be comparable to `target`?
-   *  This is the case if:
-   *   - target is a type lambda, and
-   *   - `tp` is eta-expandable (i.e. is a non-lambda class ref)
-   */
-  private def needsEtaLift(tp: Type, target: RefinedType): Boolean =
-    target.refinedName == tpnme.hkApply && tp.isEtaExpandable
-
   /** Test whether `tp1` has a base type of the form `B[T1, ..., Tn]` where
    *   - `B` derives from one of the class symbols of `tp2`,
    *   - the type parameters of `B` match one-by-one the variances of `tparams`,
@@ -574,7 +557,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
    *
    *   (4) If `inOrder`, test `projection <: other` else test `other <: projection`.
    */
-  def compareHK(projection: NamedType, other: Type, inOrder: Boolean): Boolean = {
+  def compareHkApply(projection: NamedType, other: Type, inOrder: Boolean): Boolean = {
     def tryInfer(tp: Type): Boolean = ctx.traceIndented(i"compareHK($projection, $other, inOrder = $inOrder, constr = $tp)", subtyping) {
       tp match {
         case tp: TypeVar => tryInfer(tp.underlying)
@@ -609,6 +592,18 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
     tryInfer(projection.prefix.typeConstructor.dealias)
   }
 
+  /** Compare type lambda with non-lambda type. */
+  def compareHkLambda(rt: RefinedType, other: Type, inOrder: Boolean) = rt match {
+    case TypeLambda(vs, args, body) =>
+      other.isInstanceOf[TypeRef] &&
+      args.length == other.typeParams.length && {
+        val applied = other.appliedTo(argRefs(rt, args.length))
+        if (inOrder) isSubType(body, applied) else isSubType(applied, body)
+      }
+    case _ =>
+      false
+  }
+
   /** Returns true iff either `tp11 <:< tp21` or `tp12 <:< tp22`, trying at the same time
    *  to keep the constraint as wide as possible. Specifically, if
    *
@@ -1007,12 +1002,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       val t2 = distributeAnd(tp2, tp1)
       if (t2.exists) t2
       else if (erased) erasedGlb(tp1, tp2, isJava = false)
-      else {
-        //if (isHKRef(tp1)) tp2
-        //else if (isHKRef(tp2)) tp1
-        //else
-        AndType(tp1, tp2)
-      }
+      else liftIfHK(tp1, tp2, AndType(_, _))
     }
   }
 
@@ -1036,14 +1026,23 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       val t2 = distributeOr(tp2, tp1)
       if (t2.exists) t2
       else if (erased) erasedLub(tp1, tp2)
-      else
-        //if (isHKRef(tp1)) tp1
-        //else if (isHKRef(tp2)) tp2
-        //else
-        OrType(tp1, tp2)
+      else liftIfHK(tp1, tp2, OrType(_, _))
     }
   }
 
+  /** `op(tp1, tp2)` unless `tp1` and `tp2` are type-constructors.
+   *  In the latter case, combine `tp1` and `tp2` under a type lambda like this:
+   *
+   *    [X1, ..., Xn] -> op(tp1[X1, ..., Xn], tp2[X1, ..., Xn])
+   */
+  private def liftIfHK(tp1: Type, tp2: Type, op: (Type, Type) => Type) = {
+    val tparams1 = tp1.typeParams
+    val tparams2 = tp2.typeParams
+    if (tparams1.isEmpty || tparams2.isEmpty) op(tp1, tp2)
+    else if (tparams1.length != tparams2.length) mergeConflict(tp1, tp2)
+    else hkCombine(tp1, tp2, tparams1, tparams2, op)
+  }
+
   /** Try to distribute `&` inside type, detect and handle conflicts */
   private def distributeAnd(tp1: Type, tp2: Type): Type = tp1 match {
     // opportunistically merge same-named refinements
@@ -1106,18 +1105,15 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       NoType
   }
 
-  /** Try to distribute `|` inside type, detect and handle conflicts */
+  /** Try to distribute `|` inside type, detect and handle conflicts
+   *  Note that, unlike for `&`, a disjunction cannot be pushed into
+   *  a refined or applied type. Example:
+   *
+   *     List[T] | List[U] is not the same as List[T | U].
+   *
+   *  The rhs is a proper supertype of the lhs.
+   */
   private def distributeOr(tp1: Type, tp2: Type): Type = tp1 match {
-    case tp1: RefinedType =>
-      tp2 match {
-        case tp2: RefinedType if tp1.refinedName == tp2.refinedName =>
-          tp1.derivedRefinedType(
-              tp1.parent | tp2.parent,
-              tp1.refinedName,
-              tp1.refinedInfo | tp2.refinedInfo.substRefinedThis(tp2, RefinedThis(tp1)))
-        case _ =>
-          NoType
-      }
     case tp1: TypeBounds =>
       tp2 match {
         case tp2: TypeBounds => tp1 | tp2
@@ -1325,12 +1321,12 @@ class ExplainingTypeComparer(initctx: Context) extends TypeComparer(initctx) {
 
   override def copyIn(ctx: Context) = new ExplainingTypeComparer(ctx)
 
-  override def compareHK(projection: NamedType, other: Type, inOrder: Boolean) =
+  override def compareHkApply(projection: NamedType, other: Type, inOrder: Boolean) =
     if (projection.name == tpnme.hkApply)
       traceIndented(i"compareHK $projection, $other, $inOrder") {
-        super.compareHK(projection, other, inOrder)
+        super.compareHkApply(projection, other, inOrder)
       }
-    else super.compareHK(projection, other, inOrder)
+    else super.compareHkApply(projection, other, inOrder)
 
   override def toString = "Subtype trace:" + { try b.toString finally b.clear() }
 }
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 21b74e07b..624549bac 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -1533,19 +1533,49 @@ object Types {
       ctx.underlyingRecursions -= 1
     }
 
+    /** A selection of the same kind, but with potentially a differet prefix.
+     *  The following normalizations are performed for type selections T#A:
+     *
+     *     T#A --> B                if A is bound to an alias `= B` in T
+     *
+     *     (S & T)#A --> S#A        if T does not have a member namd A
+     *               --> T#A        if S does not have a member namd A
+     *               --> S#A & T#A  otherwise
+     *     (S | T)#A --> S#A | T#A
+     */
     def derivedSelect(prefix: Type)(implicit ctx: Context): Type =
       if (prefix eq this.prefix) this
-      else {
+      else if (isType) {
         val res = prefix.lookupRefined(name)
         if (res.exists) res
-        else if (name == tpnme.hkApply && prefix.classNotLambda) {
+        else if (name == tpnme.hkApply && prefix.classNotLambda)
           // After substitution we might end up with a type like
           // `C { type hk$0 = T0; ...; type hk$n = Tn } # $Apply`
           // where C is a class. In that case we eta expand `C`.
           derivedSelect(prefix.EtaExpandCore(this.prefix.typeConstructor.typeParams))
-        }
+        else if (Config.splitProjections)
+          prefix match {
+            case prefix: AndType =>
+              def isMissing(tp: Type) = tp match {
+                case tp: TypeRef => !tp.info.exists
+                case _ => false
+              }
+              val derived1 = derivedSelect(prefix.tp1)
+              val derived2 = derivedSelect(prefix.tp2)
+              return (
+                if (isMissing(derived1)) derived2
+                else if (isMissing(derived2)) derived1
+                else prefix.derivedAndType(derived1, derived2))
+            case prefix: OrType =>
+              val derived1 = derivedSelect(prefix.tp1)
+              val derived2 = derivedSelect(prefix.tp2)
+              return prefix.derivedOrType(derived1, derived2)
+            case _ =>
+              newLikeThis(prefix)
+          }
         else newLikeThis(prefix)
       }
+      else newLikeThis(prefix)
 
     /** Create a NamedType of the same kind as this type, but with a new prefix.
      */
@@ -2774,7 +2804,7 @@ object Types {
     }
 
     override def toString =
-      if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)"
+      if (lo eq hi) s"TypeAlias($lo, $variance)" else s"TypeBounds($lo, $hi)"
   }
 
   class RealTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) {
diff --git a/src/dotty/tools/dotc/printing/PlainPrinter.scala b/src/dotty/tools/dotc/printing/PlainPrinter.scala
index 9e5ab5d8c..8f9d70d4c 100644
--- a/src/dotty/tools/dotc/printing/PlainPrinter.scala
+++ b/src/dotty/tools/dotc/printing/PlainPrinter.scala
@@ -170,7 +170,8 @@ class PlainPrinter(_ctx: Context) extends Printer {
           val bounds =
             if (constr.contains(tp)) constr.fullBounds(tp.origin)(ctx.addMode(Mode.Printing))
             else TypeBounds.empty
-          "(" ~ toText(tp.origin) ~ "?" ~ toText(bounds) ~ ")"
+          if (ctx.settings.YshowVarBounds.value) "(" ~ toText(tp.origin) ~ "?" ~ toText(bounds) ~ ")"
+          else toText(tp.origin)
         }
       case tp: LazyRef =>
         "LazyRef(" ~ toTextGlobal(tp.ref) ~ ")"
diff --git a/src/dotty/tools/dotc/transform/Splitter.scala b/src/dotty/tools/dotc/transform/Splitter.scala
index 62a080f37..410b412e0 100644
--- a/src/dotty/tools/dotc/transform/Splitter.scala
+++ b/src/dotty/tools/dotc/transform/Splitter.scala
@@ -47,7 +47,10 @@ class Splitter extends MiniPhaseTransform { thisTransform =>
       if (!mbr.isOverloaded) mbr.asSingleDenotation
       else tree.tpe match {
         case tref: TermRefWithSignature => mbr.atSignature(tref.sig)
-        case _ => ctx.error(s"cannot disambiguate overloaded member $mbr"); NoDenotation
+        case _ =>
+          def alts = mbr.alternatives.map(alt => i"$alt: ${alt.info}").mkString(", ")
+          ctx.error(s"cannot disambiguate overloaded members $alts", tree.pos)
+          NoDenotation
       }
     }
 
diff --git a/src/dotty/tools/dotc/typer/TypeAssigner.scala b/src/dotty/tools/dotc/typer/TypeAssigner.scala
index 2b7eb3936..42ee513cd 100644
--- a/src/dotty/tools/dotc/typer/TypeAssigner.scala
+++ b/src/dotty/tools/dotc/typer/TypeAssigner.scala
@@ -282,7 +282,7 @@ trait TypeAssigner {
       else if (!mix.isEmpty) findMixinSuper(cls.info)
       else if (inConstrCall || ctx.erasedTypes) cls.info.firstParent
       else {
-        val ps = cls.info.parents
+        val ps = cls.classInfo.instantiatedParents
         if (ps.isEmpty) defn.AnyType else ps.reduceLeft((x: Type, y: Type) => x & y)
       }
     tree.withType(SuperType(cls.thisType, owntype))