Further regression with a Recursion Limit Exceeded error

[jchyb]

Regression reproduced based on the failure in Open CB #17825. Problem found in sangria-graphql/sangria

Compiler version

3.2.2-RC1-bin-20221103-bf808b3-NIGHTLY

Minimized code

trait Tagged[U]
type WithTag[+T, U] = T & Tagged[U]

trait FromInput[Val]
implicit def coercedScalaInput[T]: FromInput[WithTag[T, Int]] = ???
implicit def optionInput[T](implicit ev: FromInput[T]): FromInput[Option[T]] = ???

trait WithoutInputTypeTags[T]
implicit def coercedOptArgTpe[T]: WithoutInputTypeTags[Option[WithTag[T, Int]]] = ???

trait InputType[+T]
class OptionInputType[T](ofType: InputType[T]) extends InputType[Option[T]]

type Argument[T]
def argument[T](argumentType: InputType[T])(implicit fromInput: FromInput[T], res: WithoutInputTypeTags[T]): Argument[Option[T]] = ???

def test = argument(OptionInputType(??? : InputType[WithTag[Boolean, Int]]))

Output

-- Error: sangria.scala:17:4 ---------------------------------------------------
17 |def test = argument(OptionInputType(??? : InputType[WithTag[Boolean, Int]]))
   |^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |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 -Yno-decode-stacktraces.
   |A recurring operation is (inner to outer):
   |
   |  check fully defined T
   |  check fully defined T & Tagged[Int]
   |  check fully defined T & Tagged[Int]
   |  check fully defined T & Tagged[Int] & Tagged[Int]
   |  check fully defined Option[T & Tagged[Int] & Tagged[Int]]
   |  check fully defined Option[Option[T & Tagged[Int] & Tagged[Int]]]
   |  check fully defined Argument[Option[Option[T & Tagged[Int] & Tagged[Int]]]]

Expectation

Should compile, as it did before in 3.2.1. This issue is ver closely related to #15365, to the point where I could basically reuse the minimization, except now the issue is unrelated to the typings introduced by the :: class . Simply trying to create an Argument object is enough to trigger the error (which also means the workarounds sangria used for the previous error will no longer work). The bisect script has shown efdfe0e to be the first problematic commit.

[odersky]

I can't reproduce this using the nightly 3.3.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-d8a6751.

[jchyb]

I checked, and it turns out this was fixed in the recently merged #15642, commit f19de96. Very cool part is that #15365 was also fixed by the same PR (thank you!). I'll ask Paweł later what to do with the 3.2.2 regression

[odersky]

One can probably construct counter examples then by defining a non-transparent superclass of some union type. But for now I don't even see which union type is the problematic one. Also, it could well be that the recursion overflow for fully defined type is correct.

In principle, if you get a "Recursion Limit Exceeded" that's not a bug. It means that the program has an illegal cyclic reference. An illegal cyclic reference happens if the compiler needs to know a fact in order to establish the same fact. So what is "needs to know"? That's where it gets interesting. Essentially, the type checker makes a best effort to not investigate facts if they are not necessary, playing various tricks with lazy evaluation and memoization. But the details can change from one version of the next. For instance, if fixing one bug requires looking somewhere that was not considered before, this can trigger a cyclic reference error. I should also mention that Scala is not alone in that; Java and I am sure many other languages are very similar in that respect.

So, lot's of unknowns. We have to realize we are at the fuzzy and bleeding edge of type inference here. But it seems to be the case that #15642 makes type inference more powerful and useful in practice, and that by itself can address some regressions,

[odersky]

Need to re-open because of #16344

[odersky]

We get a constraint system with cyclic constraints here

bounds:
     T#1251897263 >: WithTag#2810[T#1168079523, Int#76]
     T#1168079523 >: T#1251897263 & Tagged#2793[Int#76]

where WithTag[T, U] = T & Tagged[U]. So the type variables depend mutually on each other.

It would be very important to see which commit first introduced this. Can we get a bisect? (based on #16344).

[nicolasstucki]

It seems that this issue started in efdfe0e.