"Recursion limit exceeded." on bounded type definition that is totally monotonic

[tribbloid]

Compiler version

3.5.2

  object SubType1 {

    trait X {
      type B;
      type A <: B
    }

    trait Y {
      type A;
      type B >: A
    }

    object C1 extends X with Y
  }

Output

it looks like the compiler wasted a lot of recursion stacks and failed to compile something equivalent to type B;type A <: B

[Error] /home/peng/git/dottyspike/core/src/main/scala/com/tribbloids/spike/dotty/improvement/IncrementalPoset.scala:16:12: 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.
For the unprocessed stack trace, compile with -Xno-decode-stacktraces.
A recurring operation is (inner to outer):

  find-member C1.B
  find-member C1.A
  find-member C1.B
  find-member C1.A
  find-member C1.B
  find-member C1.A
  find-member C1.B
  find-member C1.A
  find-member C1.B
  find-member C1.A
  ...

  find-member C1.A
  find-member C1.B
  find-member C1.A
  find-member C1.B
  find-member C1.A
  find-member C1.B
  find-member C1.A
  find-member C1.B
  find-member C1.A
  find-member C1.B

Expectation

In worst case, the error for above code should be equivalent to its inlined form:

object C2 {
/* <--------illegal cyclic type reference: upper bound com.tribbloids.spike.dotty.improvement.IncrementalPoset.SubType1.C2.B of type A refers back to the type itself

 Run with -explain-cyclic for more details.*/
      type A <: B
      type B >: A
    } // should be equivalent to:
    object C3 { // <------- no error
      type B
      type A <: B
    }

But I don't think it's a good solution, the above declaration doesn't introduce any cycles/monotonicity violation despite having cyclic reference, it should be legit.

Preferably, the compiler should use an algorithm to incrementally build a subtype Heyting semilattice by detecting cycles upon adding each new declaration, eventually leading to a semilattice of types and e-classes with a holistic bound representation. The latest of such algorithm is able to do it in almost linear time (https://www.youtube.com/watch?v=Im2aAL2J988), integrating it into the compiler should pose little obstacle

Afterwards the following cases can benefit from the same impl:

  object SubType2 {

    object C1 {
      type A <: B
      type B <: A
    } // v3.5.2: illegal cyclic type reference error
    // expectation: cycle with <=1 trait detected, should add A and B into an e-class and keep compiling, which leads to the equivalent form:
    object C2 {
      type A
      type B = A
    }
  }

  object SubType2_traits {

    trait X {
      trait B
      trait A extends B
    }
    trait Y {
      type A;
      type B <: A
    }
    object C1 extends X with Y // v3.5.2: succeed, really shouldn't happen
    // expectation: cycle with >=2 traits detected, should throw an error immediately
  }

  object SubType3 {

    object C1 {
      type A <: B
      type B <: C
      type C <: A
    } // v3.5.2: illegal cyclic type reference error
    // should be equivalent to:
    object C2 {
      type A
      type B = A
      type C = A
    }
  }


  object TypeClass3 { // functionally equivalent to SubType3
    trait A; trait B; trait C

    given (
        using
        b: B
    ): A = ???
    given (
        using
        c: C
    ): B = ???

    given (
        using
        a: A
    ): C = ???

    { // succeed in v3.5.2, but search can be faster
      given C = ???
      summon[A]
      summon[B]
    }

    { // succeed in v3.5.2, but search can be faster
      given A = ???
      summon[C]
      summon[B]
    }
  }

  object TransitiveConversion3 { // functionally equivalent to SubType3
    trait A; trait B; trait C

    given identity[_X]: Conversion[_X, _X] = { x =>
      x
    }

    given [_B](
        using
        cc: Conversion[_B, B]
    ): Conversion[A, _B] = ???

    given [_C](
        using
        cc: Conversion[_C, C]
    ): Conversion[B, _C] = ???

    given [_A](
        using
        cc: Conversion[_A, A]
    ): Conversion[C, _A] = ???

    var a: A = ???
    var b: B = ???
    var c: C = ???
    a = c
    /* implicit not found error in v3.5.2
    Found:    (com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.c
   :
  com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.
    C
)
Required: com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.A

Explanation
===========

Tree: com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.c
I tried to show that
  (com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.c
   :
  com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.
    C
)
conforms to
  com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.A
but none of the attempts shown below succeeded:

  ==> (com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.c    :   com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.     C )  <:  com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.A CachedTermRef CachedTypeRef
    ==> com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.C  <:  com.tribbloids.spike.dotty.improvement.IncrementalPoset.TransitiveConversion3.A CachedTypeRef CachedTypeRef  = false

The tests were made under the empty constraint
     */
  }

Obviously it would be far beyond the scope of the "Recursion limit exceeded." bug, so feel free to suggest to move it elsewhere (e.g. Scala Contributor forum or another ticket)

[tribbloid]

just to clarify: only SubType1 and SubType2_traits are bugs, all others are improvements

[tribbloid]

I'm surprised to see a similar case already described at the end of the WadlerFest talk, 8 years ago (https://events.inf.ed.ac.uk/wf2016/slides/odersky.pdf)

I wonder why it wasn't carried through in Scala 3, is it because the lack of a fast enough/polynomial time algorithm?