From 9b630fae0d3c772610a2c58d9dbb4b95710c8c68 Mon Sep 17 00:00:00 2001
From: Martin Odersky <odersky@gmail.com>
Date: Tue, 15 Dec 2015 14:11:42 +0100
Subject: Revise alias rules in type comparisons.

The fix solves two cases where we had a deep subtype before.
---
 src/dotty/tools/dotc/core/TypeComparer.scala | 76 +++++++++++++---------------
 1 file changed, 36 insertions(+), 40 deletions(-)

(limited to 'src')

diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index b3d926a29..d14875877 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -144,47 +144,41 @@ 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]
+                ) ||
+                compareHK(tp1, tp2, inOrder = true) ||
+                compareHK(tp2, tp1, inOrder = false) ||
+                thirdTryNamed(tp1, tp2)
             case _ =>
               compareHK(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)
       }
+      compareHK(tp1, tp2, inOrder = true) ||
+      thirdTry(tp1, tp2)
     case tp1: PolyParam =>
       def flagNothingBound = {
         if (!frozenConstraint && tp2.isRef(defn.NothingClass) && state.isGlobalCommittable) {
@@ -1106,7 +1102,7 @@ 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:
    *
-- 
cgit v1.2.3