[compiler crash | "Recursion limit exceeded"][regression] caused by self-types + with in generic method signature + quasi-covariant wildcards (e.g. (that: PThis with HasThisType[PThis]))

[ibaklan]

When testing HasThisType trait defined in following from (PThis parameter itself is invariant, but recursive constraint is deliberately covariant)

    trait HasThisType[PThis <: HasThisType[_ <: PThis]] {
      this: PThis =>
      type This = PThis

    }

During verification whether "Self-type" constraint is visible or not in particular contexts (especially from outside of that trait) some problems with HasThisType[_] and generic methods signatures was revealed.

Part1
In particular, snippet (complete code here)

      def testSelf[PThis <: HasThisType[_ <: PThis]](that: PThis with HasThisType[PThis]): Unit = {
        // some asserts here
      }
      val that: HasThisType[_] = ???
      // this line of code makes Dotty compiler infinite recursion (stopped only by overflow)
      testSelf(that)

makes Dotty compiler crash
assertion failure for Main.HasThisType[_ <: LazyRef(Main.HasThisType[_]#PThis)] <:< Main.HasThisType ...
After rephrasing generic method signature to some alternative equivalents

// rewrite#1
def testSelf[PThis <: HasThisType[_ <: PThis], That <: PThis with HasThisType[PThis]](that: That): Unit = ???

// rewrite#2
type SelfForHasThisType[PThis <: HasThisType[_ <: PThis]] = PThis with HasThisType[PThis]
def testSelf[PThis <: HasThisType[_ <: PThis]](that: SelfForHasThisType[PThis]): Unit = ???

compiler crash could be reduced to regular compilation error.
While for "rewrite#2" compiler provides some error message of quite reasonable size (couple of lines)
for "rewrite#1" it shows "significantly" multiline error message like this:

42 |      testSelf(that)
   |      ^
   |Recursion limit exceeded.
   |Maybe there is an illegal cyclic reference?
   |If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
   |A recurring operation is (inner to outer):
   |
   |  subtype Main.HasThisType[_ <: LazyRef(Main.HasThisType[_ <: LazyRef(PThis)]#PThis)] <:< Nothing

  ... - 20 more similar lines here

   |  subtype Main.HasThisType[_ <: LazyRef(PThis)] <:< Main.HasThisType[PThis]

Also, essentially, that problem with tricky signature reproduces only with argument of wildcard (HasThisType[_]) type.
For normal (not wildcard) types matching that signature everything works well
(complete code here)

      def testSelf[PThis <: HasThisType[_ <: PThis]](that: PThis with HasThisType[PThis]): Unit = {
        // some asserts here
      }
      // this lines works as expected
      val that: Foo = Foo()
      testSelf(that)

---

Other snippet shows that problem with aforementioned signature could also happens not only when signature doesn't match passed argument, but in potentially positive case (but when some wildcard-ed type need to be passed/inferred through 'PThis')
Considering following example (complete code here)

      def testSelf[PThis <: HasThisType[_ <: PThis]](that: PThis with HasThisType[PThis]): Unit = {
        // some asserts here
      }
      val that3: Bar = Bar()
      // this line of code makes Dotty compiler runtime crash - comment it to make it compilable again
      testSelf(that3)

// ...

    // `HasThisType` instantiation/sub-classing
    trait FooLike[PThis <: FooLike[_ <: PThis]] extends HasThisType[PThis] {
      this: PThis =>
    }
    case class Foo(payload: Any = "dummy") extends FooLike[Foo]
    case class Bar(dummy: Any = "payload") extends FooLike[FooLike[_]]

One may expect no error there, while in fact it end up with similar compile runtime crash.
However in this case one may resolve problem "manually" by explicitly hinting PThis parameter (instead of expecting it's correct inference).
So that following fixed (explicit) snippet (complete code here)

        val that3: Bar = Bar()
        // provide `PThis` generic method parameter explicitly
        testSelf[PThis=FooLike[_ <: FooLike[_]]](that3)

will become compilable under Dotty compiler

---

Eventually, in case of invariant PThis parameter definition, which may looks like

    trait HasThisType[PThis <: HasThisType[PThis]] {
      this: PThis =>
      type This = PThis

    }

Runtime crash is not reproducible, however unreasonably long compilation error messages still appears.
Demonstrating snippet

      def testSelf[PThis <: HasThisType[PThis]](that: PThis with HasThisType[PThis]): Unit = {
        // some asserts here
      }
      val that: HasThisType[_] = ???
      // this line of code makes Dotty compiler uncontrolled recursion which produces unreasonably long error message
      testSelf(that)

Also rewriting signature using intermediate aliasing type as

type SelfForHasThisType[PThis <: HasThisType[PThis]] = PThis with HasThisType[PThis]
def testSelf[PThis <: HasThisType[PThis]](that: SelfForHasThisType[PThis]): Unit = ???

allows to see error message of more reasonable size, and may look like

41 |      testSelf(that)
   |               ^^^^
   |Found:    Main.HasThisType[_](that)
   |Required: SelfForHasThisType[PThis]
   |
   |where:    PThis is a type variable with constraint <: Main.HasThisType[LazyRef(PThis)]

[ibaklan]

Part2

Other issues appears when one may wont to "expose" self-type constraint "to public"
In particular, for simple cases, like
(simplest one - no recursive generics)

    type HasThisTypeSelf[PThis] = PThis with HasThisType[PThis]
    trait HasThisType[PThis] {
      this: PThis =>

      type This = PThis

      // inline // uncommenting `inline` cause problem in scastie dotty version, but is fixed in dotty `master`
      def self(): This with this.type = this
    }

(more advanced - with recursive invariant generic)

    type HasThisTypeSelf[PThis <: HasThisType[PThis]] = PThis with HasThisType[PThis]
    trait HasThisType[PThis <: HasThisType[PThis]] {
      this: PThis =>

      type This = PThis

      // inline // uncommenting `inline` cause problem in scastie dotty version, but is fixed in dotty `master`
      def self(): This with this.type = this
    }

everything works as expected!
Complete demonstration code here
In general It tries to adapt regular HasThisType signature to some self-type exposing one, like

      // def doSmthWithSelfImpl[PThis](that: PThis with HasThisType[PThis]): Unit = ???
      def doSmthWithSelfImpl[PThis <: HasThisType[PThis]](that: HasThisTypeSelf[PThis]): Unit = ???

is adapted to

      def doSmthWithSelf1[PThis <: HasThisType[PThis]](that: HasThisType[PThis]): Unit

or to wildcard version

      def doSmthWithSelfWildcard(that: HasThisType[_]): Unit

Using explicit or implicit conversion of form

      // inline
      def exposeItSelf1[PThis <: HasThisType[PThis]](that: HasThisType[PThis]): that.type with PThis = that.self()
      // inline
      def exposeItSelf2[PThis <: HasThisType[PThis]](that: HasThisType[PThis]): HasThisType[PThis] with PThis = that.self()

As shown in aforementioned scasite snippet, all this works fine for simple self-typed generics, and for most common recursive invariant generics.

However for more complicated (recursive "quasi covariant" generics) that approach does not work ...
Consider following "quasi covariant" HasThisType definition

      type HasThisTypeSelf[PThis <: HasThisType[_ <: PThis]] = PThis with HasThisType[PThis]
      trait HasThisType[PThis <: HasThisType[_ <: PThis]] {
        this: PThis =>

        type This = PThis

        // inline // uncommenting `inline` cause problem in scastie dotty version, but is fixed in dotty `master`
        def self(): This with this.type = this
      }

Here is complete problem-demonstrating snippet, same code but with commented problematic lines here
In particular, the only working "adaptation" in current state of Dotty compiler is

      def doSmthWithSelf2[PThis <: HasThisType[_ <: PThis]](that: HasThisType[PThis]): Unit = {
        // makes error on both master and scasite version of Dotty
//        doSmthWithSelfImpl(exposeItSelf2(that))
        // this is the only version that works in both master and scasite version of Dotty
        doSmthWithSelfImpl(exposeItSelf2[PThis](that))
      }

      // def doSmthWithSelfImpl[PThis](that: PThis with HasThisType[PThis]): Unit = ???
      def doSmthWithSelfImpl[PThis <: HasThisType[_ <: PThis]](that: HasThisTypeSelf[PThis]): Unit = ???

      // inline
      def exposeItSelf1[PThis <: HasThisType[_ <: PThis]](that: HasThisType[PThis]): that.type with PThis = that.self()
      // inline
      def exposeItSelf2[PThis <: HasThisType[_ <: PThis]](that: HasThisType[PThis]): HasThisType[PThis] with PThis = that.self()

While in Dotty version used by scasite more ways are working (however still less then expected)

Basically all tried adaptations looks like this (extract from aforementioned snippets 1, 2)

      // def doSmthWithSelfImpl[PThis](that: PThis with HasThisType[PThis]): Unit = ???
      def doSmthWithSelfImpl[PThis <: HasThisType[_ <: PThis]](that: HasThisTypeSelf[PThis]): Unit = {
        println(s"doSmthWithSelfImpl: that: $that")
      }

      def doSmthWithSelf1[PThis <: HasThisType[_ <: PThis]](that: HasThisType[PThis]): Unit = {
        // makes error only on master version of Dotty ; WORKS on scasite version of Dotty
        doSmthWithSelfImpl(exposeItSelf1(that))
      }

      def doSmthWithSelf2[PThis <: HasThisType[_ <: PThis]](that: HasThisType[PThis]): Unit = {
        // makes error on both master and scasite version of Dotty
//        doSmthWithSelfImpl(exposeItSelf2(that))
        // this is the only version that works in both master and scasite version of Dotty
        doSmthWithSelfImpl(exposeItSelf2[PThis](that))
      }

      def doSmthWithSelf3[PThis <: HasThisType[_ <: PThis]](that: HasThisType[PThis]): Unit = {
        import scala.language.implicitConversions
        import exposeItSelf1Impl._
        // makes error only on master version of Dotty ; WORKS on scasite version of Dotty
        doSmthWithSelfImpl(that)
      }

      def doSmthWithSelf4[PThis <: HasThisType[_ <: PThis]](that: HasThisType[PThis]): Unit = {
        import scala.language.implicitConversions
        import exposeItSelf2Impl._
        // makes error on both master and scasite version of Dotty
//        doSmthWithSelfImpl(that)
      }

      def doSmthWithSelfWildcard(that: HasThisType[_]): Unit = {
        // makes error only on master version of Dotty ; WORKS on scasite version of Dotty
        doSmthWithSelfImpl(exposeItSelf1(that))
        // makes error on both master and scasite version of Dotty
//        doSmthWithSelfImpl(exposeItSelf2(that))
        import scala.language.implicitConversions
        {
          import exposeItSelf1Impl._
          // makes error on both master and scasite version of Dotty
//          doSmthWithSelfImpl(that)
        }
        {
          import exposeItSelf2Impl._
          // makes error on both master and scasite version of Dotty
//          doSmthWithSelfImpl(that)
        }
      }

[odersky]

I think this is crazy code that we do not want to support. Instead of trying to make it work, can I put down the opposite challenge for you: Can you think of a simple rule set that would prevent code like this? I.e. the compiler should flag this as an error rather than trying too hard and going into infinite recursions and the like. But the question is: what would a good error condition be?

[ibaklan]

Can you think of a simple rule set that would prevent code like this? I.e. the compiler should flag this as an error rather than trying too hard and going into infinite recursions and the like.

probably Dotty should have better support of use-site co-variance (it works poorly only with [_ < T])
also I could observe some regression comparing to previous release

I think this is crazy code that we do not want to support.

I guess you may forgive me code quality, since I look at it as some data for Dotty compiler testing (it was not intended for use in production so far 😄 )

[odersky]

Fair enough 😉 But it still looks to me more like an abuse of Scala's features. We have to fix it for sure, but I am not sure yet whether the fix will outlaw idioms like that instead of supporting it.