Skip to content

Avoid compiler hang in implicit resolution #6530

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.

Sign up for GitHub

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

Jump to bottom
Merged
adriaanm merged 1 commit into from
May 18, 2018
Merged

Avoid compiler hang in implicit resolution #6530

adriaanm merged 1 commit into from
May 18, 2018

Conversation

@milessabin
Copy link
Contributor

@milessabin milessabin commented Apr 16, 2018 •
edited
Loading

The current divergence checker computes the "stripped core" of the types it's resolving implicits for before computing their relative complexity. Unfortunately a missed case in the core computation means that divergent types can be smuggled into the resolution as arguments to a TypeRef and are not counted towards the overall complexity of the type. This causes implicit resolution to loop until stack overflow.

trait Foo[F[_]]
object Foo {
  implicit def mkFoo[F[_]](implicit ff: Foo[({ type λ[t] = F[F[t]] })#λ]): Foo[F] = ???
}

trait Bar[F[_]]
object Bar {
  implicit def mkBar[F[_]](implicit bb: Bar[λ forSome { type λ[t] <: F[t] }]): Bar[F] = ???
}

implicitly[Foo[List]] // compile time hang
implicitly[Bar[List]] // compile time hang

Issue reported as scala/bug#10833.

The fix is to have the computation of the core type traverse through the arguments of TypeRefs.

Nb. this fix will also be in the byname implicits PR shortly, but I thought it would be useful to get this change reviewed independently.

See comment below ...

@scala-jenkins scala-jenkins added this to the 2.13.0-M4 milestone Apr 16, 2018
@milessabin milessabin requested a review from adriaanm April 16, 2018 14:58
@milessabin
Copy link
Contributor Author

milessabin commented Apr 16, 2018 •
edited
Loading

I realized after PR'ing this that core only eliminating top level ExistentialTypes and PolyTypes is as per the spec. However, the computation in complexity seems to be assuming that all existentials and poly types have been eliminated throughout.

It would be possible to cover the missing cases in complexity, but it's not clear to me what that buys us over making the change in core as here. I note that in Dotty the stripped core is completely absent and instead we have a typeSize which appears to compute the normalized size of a type directly without constructing the intermediate stripped core type. On balance I would prefer to follow Dotty's approach here.

Comments from @odersky and @OlivierBlanvillain would be very welcome.

@milessabin milessabin requested a review from odersky April 16, 2018 19:05
@milessabin milessabin mentioned this pull request Apr 17, 2018
Closed
@adriaanm adriaanm modified the milestones: 2.13.0-M4, 2.13.0-M5 May 9, 2018
@adriaanm
Copy link
Contributor

adriaanm commented May 9, 2018

As discussed, we'll review in Berlin and give ourselves until M5 to refine.

adriaanm
adriaanm approved these changes May 18, 2018
View reviewed changes
Copy link
Contributor

@adriaanm adriaanm left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice catch! (Sneaky)

@adriaanm
Copy link
Contributor

adriaanm commented May 18, 2018

Thanks for defending against your future self :-p

@adriaanm adriaanm merged commit af7635c into scala:2.13.x May 18, 2018
This was referenced Aug 7, 2018
Merged
Merged
@milessabin
Copy link
Contributor Author

milessabin commented Aug 7, 2018

As reported here, this PR causes a significant slowdown when performing implicit searches for large types: in the case of the "select from large hlist" benchmark it roughly doubles the compile time.

That's fixed in #7012.

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

Reviewers

@odersky odersky Awaiting requested review from odersky

1 more reviewer

@adriaanm adriaanm adriaanm approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

2.13.0-M5

Development

Successfully merging this pull request may close these issues.

3 participants

@milessabin @adriaanm @scala-jenkins