Loop in member type bounds breaks intersection

[howtonotwin]

Compiler version

Running Scala 3.7.0.

Minimized code

trait A[X]
trait Allowed:
  type T <: A[U]
  type U <: A[T]
trait Boring:
  type T
  type U
type Wat = Boring & Allowed // looks fine to me, scalac loops

Here's a slightly less minimized version where the traits are explicitly related and the loop is created by overriding. I would want this example to work too.

trait A[X]
trait Sup:
  type T
  type U <: A[T]
trait Sub extends Sup:
  override type T <: A[U]
type Wat = Sup & Sub // looks fine to me, scalac loops

Output

-- Error: .\minim.scala:8:5 ----------------------------------------------------
8 |type Wat = Boring & Allowed // looks fine to me, scalac loops
  |^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |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-enrich-error-messages.
  |A recurring operation is (inner to outer):
  |
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  ...
  |
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
  |  find-member Allowed#U
  |  find-member Allowed#T
1 error found

(And similar for the other sample.)

Expectation

I'm under the impression there's nothing wrong with either code sample. The cyclic member type bounds are just more complicated F-bounds, and stuff like trait Allowed { type T <: A[T] } has always been legal.

[som-snytt]

"Allowed" is nebulous. You're allowed to write code that stackoverflows, but that doesn't make it correct.

Only one of these definitions succeeds:

//class C extends Allowed
//class C:
//  this: Allowed =>
class C:
  type Um <: Allowed

Oh, I added your intersection member and look what happened.

➜  snips scala-cli compile --server=false -S 3.7.0 i23165.scala
➜  snips vi i23165.scala
➜  snips scala-cli compile --server=false -S 3.7.0 i23165.scala
➜  snips vi i23165.scala
➜  snips scala-cli compile --server=false -S 3.7.0 i23165.scala

  unhandled exception while running posttyper on /home/amarki/snips/i23165.scala

  An unhandled exception was thrown in the compiler.
  Please file a crash report here:
  https://github.com/scala/scala3/issues/new/choose
  For non-enriched exceptions, compile with -Xno-enrich-error-messages.


     while compiling: /home/amarki/snips/i23165.scala
        during phase: posttyper
                mode: Mode(ImplicitsEnabled)
     library version: version 2.13.16
    compiler version: version 3.7.0
            settings: -classpath /home/amarki/.cache/coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala3-library_3/3.7.0/scala3-library_3-3.7.0.jar:/home/amarki/.cache/coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.16/scala-library-2.13.16.jar -d /home/amarki/snips/.scala-build/snips_71ae519d80-c7a75cb561/classes/main -sourceroot /home/amarki/snips

Exception in thread "main" java.lang.BootstrapMethodError: bootstrap method initialization exception
        at dotty.tools.dotc.core.Types$Type.findMember(Types.scala:971)
        at dotty.tools.dotc.core.Types$Type.memberBasedOnFlags(Types.scala:751)
        at dotty.tools.dotc.core.Types$Type.nonPrivateMember(Types.scala:741)
        at dotty.tools.dotc.core.Types$abstractTypeNameFilter$.apply(Types.scala:6956)
        at dotty.tools.dotc.core.Types$.dotty$tools$dotc$core$Types$Type$$_$memberNames$$anonfun$1(Types.scala:989)
        at scala.collection.immutable.Set$Set2.filterImpl(Set.scala:221)
        at scala.collection.immutable.Set$Set2.filterImpl(Set.scala:192)
        at scala.collection.StrictOptimizedIterableOps.filter(StrictOptimizedIterableOps.scala:218)
        at scala.collection.StrictOptimizedIterableOps.filter$(StrictOptimizedIterableOps.scala:218)
        at scala.collection.immutable.Set$Set2.filter(Set.scala:192)
        at dotty.tools.dotc.core.Types$Type.memberNames(Types.scala:989)
        at dotty.tools.dotc.core.Types$Type.memberDenots(Types.scala:1005)
        at dotty.tools.dotc.core.Types$Type.abstractTypeMembers(Types.scala:1045)
        at dotty.tools.dotc.typer.Checking$.$anonfun$10(Checking.scala:498)
        at scala.collection.immutable.List.flatMap(List.scala:294)
        at dotty.tools.dotc.typer.Checking$.checkNonCyclicInherited(Checking.scala:498)
        at dotty.tools.dotc.transform.PostTyper$PostTyperTransformer.transform(PostTyper.scala:569)

It "worked" ("failed") immediately after.

➜  snips scala-cli compile --server=false -S 3.7.0 i23165.scala
-- Error: /home/amarki/snips/i23165.scala:15:7 ---------------------------------
15 |  type Wat = Boring & Allowed
   |  ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |Recursion limit exceeded.

I always use --server=false because I don't want to guess about state.

That was (23.0.2, Java OpenJDK 64-Bit Server VM).

So I guess in computing, what doesn't crash is allowed.

[Gedochao]

@som-snytt might want to raise the crash repro separately 😅 (couldn't reproduce it myself, but it's unclear to me, how exactly did you cause it)
While all these are good points, I'd still say that in an ideal world, the compiler should return warnings/valid errors at all times, rather than crashing.

[howtonotwin]

"Allowed" is only nebulous insofar as there is (AFAIK) no complete, up-to-date spec for Scala 3. (Though I'm not sure what the existing one says about this either.) Short of pointing to a spec, I've got a slew of reasons for Allowed to be legal:

• Otherwise, abstract type members cannot model the legal class definitions (which are expressible even in Java!):

  class T extends A[U]
  class U extends B[T]

• Otherwise, there would be an inconsistency with the case of one F-bounded type:

  trait A[X]
  trait Allowed:
    type T <: A[T]
  trait Boring:
    type T
  type Wat = Boring & Allowed // fine
  
  // re: comment about instantiating Allowed
  new { class T(val x: T) }: Allowed // fine

  Note that the B in my original minimizer is unnecessary. I'll edit the issue text in a moment.

• If I replace trait A[X] with a defined type, then everything is well-formed and expanding according to DOT (assuming I haven't made a mistake):

  type A[X] = { val x: X }
  trait Allowed:
    type T <: A[U]
    type U <: A[T]
  // { this => type T <: { val x: this.U }; type U <: { val x: this.T } } is a well-formed DOT type, abbreviate it Allowed
  // In a context z: Allowed, z.T and z.U are well-formed and expand respectively to { val x: z.U } and { val x: z.T }
  // yet scalac appears to be getting stuck computing the members of z.T and z.U...
  trait Boring:
    type T
    type U
  // Boring := { this => type T; type U } is well-formed
  type Wat = Boring & Allowed
  // so Wat should also be well-formed
  // DOT calculates that (the expansion of) Wat should be (roughly):
  //   { this => type T <: { val x: this.U }; type U <: { val x: this.T } } (i.e. same as Allowed)
  // and so, when z: Wat, z.T and z.U have the same expansions as before
  // ...but scalac loops
  
  // DOT also calculates that instance creation of Allowed is allowed (Allowed is expanding)
  new { class T(val x: U); class U(val x: T) }: Allowed // scalac, you guessed it, loops

  It's been a while, but I was under the impression the intent of Dotty/Scala3 is to follow DOT.