Fixes to BetaReduce and asMemberOf; add a second betaReduce

The new one only reduces straight applications of type lambdas with
definite arguments.  It is called very early on appliedTo, and derivedRefinedType.

The old one, now renamed to normalizeHkApply also handles wildcard arguments
and can garbage collect general unneeded hk-refinements. It is called later, at various
places.

TODO: See what functionality of normalizeHkApply should go into betaReduce instead.
Maybe we can even drop normalizeHkApply? However: need to be careful to maintain aliases
for hk type inference.
Handle LazyRefs in BetaReduce

Needs to be careful to not skip LazyRefs when dealiasing.

- Fix^2 of asMemberOf: This fix ensures that

 - under the old hk scheme test succeeds for compilestdlib and tasty-new-all
 - under the new scheme test succeeds for i94-nada (i.e. REP[T] = T).

- Try to beta-reduce bounds before adding to a constraint.
- More subtle handling of LazyRefs in BetaReduce
- Another refinement to asMemberOf

  Need to assume lastSymbol in sync with lastDenotation.
- Drop isSafe test from BetaReduce

  Instead, track the higherkinded argument names that a
  type variable could potentially instantiate to.

5 files changed, 97 insertions, 67 deletions

diff --git a/src/dotty/tools/dotc/core/ConstraintHandling.scala b/src/dotty/tools/dotc/core/ConstraintHandling.scala
index f8eae186a..3b368ad5e 100644
--- a/src/dotty/tools/dotc/core/ConstraintHandling.scala
+++ b/src/dotty/tools/dotc/core/ConstraintHandling.scala
@@ -285,6 +285,8 @@ trait ConstraintHandling {
           if (!addParamBound(bound)) NoType
           else if (fromBelow) defn.NothingType
           else defn.AnyType
+        case bound: RefinedType =>
+          bound.BetaReduce
         case _ =>
           bound
       }
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index c270288b2..7b2d2c3b2 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -291,10 +291,9 @@ object TypeApplications {
     TypeLambda.applyOBS(variances, bounds, body)
   }
 
-  private class InstMap(fullType: Type, shortLived: Boolean)(implicit ctx: Context) extends TypeMap {
+  private class InstMap(fullType: Type)(implicit ctx: Context) extends TypeMap {
     var localRecs: Set[RecType] = Set.empty
     var keptRefs: Set[Name] = Set.empty
-    var isSafe: Boolean = true
     var tyconIsHK: Boolean = true
     def apply(tp: Type): Type = tp match {
       case tp @ TypeRef(RecThis(rt), sel) if sel.isHkArgName && localRecs.contains(rt) =>
@@ -302,8 +301,13 @@ object TypeApplications {
           case TypeAlias(alias) => apply(alias)
           case _ => keptRefs += sel; tp
         }
-      case tp: TypeVar if !tp.inst.exists && !shortLived =>
-        isSafe = false
+      case tp: TypeVar if !tp.inst.exists =>
+        val bounds = tp.instanceOpt.orElse(ctx.typeComparer.bounds(tp.origin))
+        bounds.foreachPart {
+          case TypeRef(RecThis(rt), sel) if sel.isHkArgName && localRecs.contains(rt) =>
+            keptRefs += sel
+          case _ =>
+        }
         tp
       case _ =>
         mapOver(tp)
@@ -561,12 +565,12 @@ class TypeApplications(val self: Type) extends AnyVal {
     assert(!isHK, self)
     self match {
       case self: TypeAlias =>
-        self.derivedTypeAlias(expand(self.alias.BetaReduce()))
+        self.derivedTypeAlias(expand(self.alias.BetaReduce))
       case self @ TypeBounds(lo, hi) =>
         if (Config.newHK)
-          self.derivedTypeBounds(lo, expand(hi.BetaReduce()))
+          self.derivedTypeBounds(lo, expand(hi.BetaReduce))
         else
-          self.derivedTypeBounds(lo, expand(TypeBounds.upper(hi.BetaReduce())))
+          self.derivedTypeBounds(lo, expand(TypeBounds.upper(hi.BetaReduce)))
       case _ => expand(self)
     }
   }
@@ -594,57 +598,68 @@ class TypeApplications(val self: Type) extends AnyVal {
    *
    *  A binding is top-level if it can be reached by
    *
-   *   - following aliases
+   *   - following aliases unless the type is a LazyRef
+   *     (need to keep cycle breakers around, see i974.scala)
    *   - dropping refinements and rec-types
    *   - going from a wildcard type to its upper bound
-   *
-   *  @param  shortLived   If `false` suppresses all rewritings where a type variable with
-   *                       an unknown or uncommitted instance is rewritten. Reason: If the
-   *                       type variable is finally instantiated to something else, the
-   *                       reduction might not be valid anymore. However, when reducing
-   *                       during `<:<` tests `shortLived` is true and the reduction
-   *                       is never suppressed, because then we are only interested
-   *                       in subtyping relative to the current context.
    */
-  def BetaReduce(shortLived: Boolean = false)(implicit ctx: Context): Type = self.dealias match {
+  def BetaReduce(implicit ctx: Context): Type = self.strictDealias match {
     case self1 @ RefinedType(_, rname, _) if Config.newHK && rname.isHkArgName && self1.typeParams.isEmpty =>
-      val inst = new InstMap(self, shortLived)
-      def instTop(tp: Type): Type =
-        if (!inst.isSafe) tp
-        else tp.dealias match {
-          case tp: RecType =>
-            inst.localRecs += tp
-            tp.rebind(instTop(tp.parent))
-          case tp @ RefinedType(parent, rname, rinfo) =>
-            rinfo match {
-              case TypeAlias(TypeRef(RecThis(rt), sel)) if sel.isHkArgName && inst.localRecs.contains(rt) =>
-                val bounds @ TypeBounds(_, _) = self.member(sel).info
-                instTop(tp.derivedRefinedType(parent, rname, bounds.withBindingKind(NoBinding)))
-              case _ =>
-                val parent1 = instTop(parent)
-                if (rname.isHkArgName &&
-                    !inst.tyconIsHK &&
-                    !inst.keptRefs.contains(rname)) parent1
-                else tp.derivedRefinedType(parent1, rname, inst(rinfo))
-            }
-          case tp @ WildcardType(bounds @ TypeBounds(lo, hi)) =>
-            tp.derivedWildcardType(bounds.derivedTypeBounds(inst(lo), instTop(hi)))
-          case tp =>
-            inst.tyconIsHK = tp.isHK
-            val res = inst(tp)
-            tp match {
-              case tp: WildcardType =>
-                println(s"inst $tp --> $res")
-              case _ =>
-            }
-            res
+      val inst = new InstMap(self)
+
+      def instTop(tp: Type): Type = tp.strictDealias match {
+        case tp: RecType =>
+          inst.localRecs += tp
+          tp.rebind(instTop(tp.parent))
+        case tp @ RefinedType(parent, rname, rinfo) =>
+          rinfo match {
+            case TypeAlias(TypeRef(RecThis(rt), sel)) if sel.isHkArgName && inst.localRecs.contains(rt) =>
+              val bounds @ TypeBounds(_, _) = self.member(sel).info
+              instTop(tp.derivedRefinedType(parent, rname, bounds.withBindingKind(NoBinding)))
+            case _ =>
+              val parent1 = instTop(parent)
+              if (rname.isHkArgName &&
+                !inst.tyconIsHK &&
+                !inst.keptRefs.contains(rname)) parent1
+              else tp.derivedRefinedType(parent1, rname, inst(rinfo))
+          }
+        case tp @ WildcardType(bounds @ TypeBounds(lo, hi)) =>
+          tp.derivedWildcardType(bounds.derivedTypeBounds(inst(lo), instTop(hi)))
+        case tp: LazyRef =>
+          instTop(tp.ref)
+        case tp =>
+          inst.tyconIsHK = tp.isHK
+          val res = inst(tp)
+          tp match {
+            case tp: WildcardType =>
+              println(s"inst $tp --> $res")
+            case _ =>
+          }
+          res
+      }
+
+      def isLazy(tp: Type): Boolean = tp.strictDealias match {
+        case tp: RefinedOrRecType => isLazy(tp.parent)
+        case tp @ WildcardType(bounds @ TypeBounds(lo, hi)) => isLazy(hi)
+        case tp: LazyRef => true
+        case _ => false
+      }
+
+      val reduced =
+        if (isLazy(self1)) {
+          // A strange dance is needed here to make 974.scala compile.
+          val res = LazyRef(() => instTop(self))
+          res.ref         // without this line, pickling 974.scala fails with an assertion error
+                          // saying that we address a RecThis outside its Rec (in the case of RecThis of pickleNewType)
+          res             // without this line, typing 974.scala gives a stackoverflow in asSeenFrom.
         }
-      val reduced = instTop(self)
-      if (inst.isSafe) reduced else self
+        else instTop(self)
+      if (reduced ne self) hk.println(i"reduce $self  -->  $reduced")
+      reduced
     case _ => self
   }
 
-    /** A type ref is eta expandable if it refers to a non-lambda class.
+  /** A type ref is eta expandable if it refers to a non-lambda class.
    *  In that case we can look for parameterized base types of the type
    *  to eta expand them.
    */
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index b0c36ca58..c82dc6a39 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -661,7 +661,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling {
       }
     }
     Config.newHK && app.isHKApply && !other.isHKApply && {
-      val reduced = app.BetaReduce(shortLived = true)
+      val reduced = app.BetaReduce
       if (reduced ne app)
         if (inOrder) isSubType(reduced, other) else isSubType(other, reduced)
       else tryInfer(app.typeConstructor.dealias)
@@ -1503,7 +1503,7 @@ class ExplainingTypeComparer(initctx: Context) extends TypeComparer(initctx) {
 
   override def compareHkApply(app: RefinedType, other: Type, inOrder: Boolean) =
     if (app.isHKApply)
-      traceIndented(i"compareHkApply $app, $other, $inOrder, ${app.BetaReduce(shortLived = true)}") {
+      traceIndented(i"compareHkApply $app, $other, $inOrder, ${app.BetaReduce}") {
         super.compareHkApply(app, other, inOrder)
       }
     else super.compareHkApply(app, other, inOrder)
diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala
index 46771a5aa..c6a18f305 100644
--- a/src/dotty/tools/dotc/core/TypeOps.scala
+++ b/src/dotty/tools/dotc/core/TypeOps.scala
@@ -158,7 +158,7 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
       tp
     case tp: RefinedType =>
       tp.derivedRefinedType(simplify(tp.parent, theMap), tp.refinedName, simplify(tp.refinedInfo, theMap))
-        .BetaReduce()
+        .BetaReduce
     case tp: TypeAlias =>
       tp.derivedTypeAlias(simplify(tp.alias, theMap))
     case AndType(l, r) =>
@@ -384,7 +384,7 @@ trait TypeOps { this: Context => // TODO: Make standalone object.
     var formals: SimpleMap[TypeName, Symbol] = SimpleMap.Empty // A map of all formal parent parameter
 
     // Strip all refinements from parent type, populating `refinements` and `formals` maps.
-    def normalizeToRef(tp: Type): TypeRef = tp.dealias.BetaReduce() match {
+    def normalizeToRef(tp: Type): TypeRef = tp.dealias.BetaReduce match {
       case tp: TypeRef =>
         tp
       case tp @ RefinedType(tp1, name: TypeName, rinfo) =>
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 4f5bec56b..dadb5b95e 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -822,7 +822,16 @@ object Types {
     /** Follow aliases and dereferences LazyRefs and instantiated TypeVars until type
      *  is no longer alias type, LazyRef, or instantiated type variable.
      */
-    final def dealias(implicit ctx: Context): Type = this match {
+    final def dealias(implicit ctx: Context): Type = strictDealias match {
+      case tp: LazyRef => tp.ref.dealias
+      case tp => tp
+    }
+
+    /** Follow aliases and instantiated TypeVars until type
+     *  is no longer alias type, or instantiated type variable.
+     *  Do not follow LazyRefs
+     */
+    final def strictDealias(implicit ctx: Context): Type = this match {
       case tp: TypeRef =>
         if (tp.symbol.isClass) tp
         else tp.info match {
@@ -832,19 +841,11 @@ object Types {
       case tp: TypeVar =>
         val tp1 = tp.instanceOpt
         if (tp1.exists) tp1.dealias else tp
-      case tp: LazyRef =>
-        tp.ref.dealias
       case tp: AnnotatedType =>
         tp.derivedAnnotatedType(tp.tpe.dealias, tp.annot)
       case tp => tp
     }
 
-    /** If this is a TypeAlias type, its alias otherwise this type itself */
-    final def followTypeAlias(implicit ctx: Context): Type = this match {
-      case TypeAlias(alias) => alias
-      case _ => this
-    }
-
     /** Perform successive widenings and dealiasings until none can be applied anymore */
     final def widenDealias(implicit ctx: Context): Type = {
       val res = this.widen.dealias
@@ -859,6 +860,12 @@ object Types {
       case _ => this
     }
 
+    /** If this is a TypeAlias type, its alias otherwise this type itself */
+    final def followTypeAlias(implicit ctx: Context): Type = this match {
+      case TypeAlias(alias) => alias
+      case _ => this
+    }
+
     /** If this is a (possibly aliased, annotated, and/or parameterized) reference to
      *  a class, the class type ref, otherwise NoType.
      *  @param  refinementOK   If `true` we also skip non-parameter refinements.
@@ -1579,14 +1586,20 @@ object Types {
       // we might now get cycles over members that are in a refinement but that lack
       // a symbol. Without the following precaution i974.scala stackoverflows when compiled
       // with new hk scheme.
-      val saved = lastDenotation
-      if (name.isTypeName && lastDenotation != null && (lastDenotation.symbol ne NoSymbol))
+      val savedDenot = lastDenotation
+      val savedSymbol = lastSymbol
+      if (prefix.isInstanceOf[RecThis] && name.isTypeName) {
         lastDenotation = ctx.anyTypeDenot
+        lastSymbol = NoSymbol
+      }
       try
         if (name.isShadowedName) prefix.nonPrivateMember(name.revertShadowed)
         else prefix.member(name)
       finally
-        if (lastDenotation eq ctx.anyTypeDenot) lastDenotation = saved
+        if (lastDenotation eq ctx.anyTypeDenot) {
+          lastDenotation = savedDenot
+          lastSymbol = savedSymbol
+        }
     }
 
     /** (1) Reduce a type-ref `W # X` or `W { ... } # U`, where `W` is a wildcard type
@@ -2753,7 +2766,7 @@ object Types {
       myRepr
     }
 
-    override def toString = s"Skolem($info)"
+    override def toString = s"Skolem($hashCode)"
   }
 
   final class CachedSkolemType(info: Type) extends SkolemType(info)