Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Type inference can lead to cyclic instantiation of type variables which eventually crashes the compiler #15280

Open
smarter opened this issue May 24, 2022 · 0 comments

Comments

@smarter
Copy link
Member

smarter commented May 24, 2022

According to our own comments, cycles are only allowed in the upper-bound of a type variable due to F-bounds which we explicitly handle when instantiating:
https://github.com/lampepfl/dotty/blob/9d687784c30b94d07583885251b2576c3eed1f40/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala#L426-L431
The corresponding logic in addOneBound is https://github.com/lampepfl/dotty/blob/9d687784c30b94d07583885251b2576c3eed1f40/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala#L244-L247

But all of this isn't enough to catch indirect cycles like in

class LT[-X, +Y]
object LT {
 given lt[X <: Y, Y]: LT[X, Y] = ???
}

trait C[X]
trait D[X] extends C[X]
trait A {
  def foo[S <: C[T], T <: C[S]](using LT[D[T], S], LT[D[S], T]): S = ???

  foo
}

(if we had directly written def foo[S >: D[T] <: C[T], T >: D[S] <: C[S]] the compiler would have complained via checkNonCyclic:

25 |  def foo[S >: D[T] <: C[T], T >: D[S] <: C[S]]: S = ???
   |          ^
   |illegal cyclic type reference: lower bound D[T] of type S refers back to the type itself

)
It's not clear to me if we can always detect these cycles as we add a bound, so we might have to settle for detecting them at instantiation time and failing then: this is what 74c693c attempts.
This seems to work, but because we don't have a tree position when instantiating a TypeVar, and because type variable instantiation can be delayed, the error ends up being reported at an unrelated point rather than at the actual call-site, I'm not sure how to do better.
EDIT: I don't think detecting these cycles at instantiation time is enough actually, because some operations like avoidance recurse on both the upper and lower bound of a type variable and can get into infinite loops that way: #15393 (comment)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant