Skip to content

Divergence checker does not detect loop with higher-kinded type, unlike Scala 2 #9504

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

Closed
smarter opened this issue Aug 5, 2020 · 1 comment

Comments

@smarter
Copy link
Member

smarter commented Aug 5, 2020

Minimized code

trait Monad[F[_]] {
  def foo[A](fa: F[A]): Unit = {}
}

class Bla[F[_], A]

object Test {
  type Id[A] = A

  val bla: Bla[Id, Unit] = ???
  implicit def blaMonad[F[_]: Monad, S]: Monad[({type L[X] = Bla[F, X]})#L] = ???

  blaMonad.foo(bla)
}

Output

With Dotty, the compiler runs for ~20 seconds before producing a giant error message:

-- Error: try/divloop.scala:19:10 ----------------------------------------------
19 |  blaMonad.foo(bla)
   |          ^
   |no implicit argument of type Monad[([_$3] =>> Any)] was found for an implicit parameter of method blaMonad in object Test.
   |I found:
   |
   |    Test.blaMonad[F, S](
   |      Test.blaMonad[F, S](
   |        Test.blaMonad[F, S](
...

Expectation

With Scala 2, the compiler pretty much instantly stops with:

try/divloop.scala:19: error: diverging implicit expansion for type Monad[F]
starting with method blaMonad in object Test
  blaMonad.foo(bla)
  ^

This is not just a problem for malformed code: if I add another implicit to have a base case:

  implicit def idMonad: Monad[Id] = ???

Then Dotty still fails in the same way whereas Scala 2 is able to correctly resolve:

blaMonad(idMonad).foo(bla)

I came across this while trying to see what happens if cats Monad used dotty's extension method syntax (#9480).

Tentatively assigning to Miles since he wrote the divergence checker.

@milessabin
Copy link
Contributor

I'm afraid I won't have time to work on this in the near future.

@milessabin milessabin removed their assignment Aug 7, 2020
smarter added a commit to dotty-staging/dotty that referenced this issue Aug 10, 2020
So far, like Scala 2, given:

  Either[Int, String] <:< ?F[String]

we were able to infer:

  ?F >: [X] =>> Either[Int, X]

However, in the inverse situation:

  ?F[String] <:< Either[Int, String]

Scala 2, but not Dotty, was able to infer:

  ?F <: [X] =>> Either[Int, X]

This commit fixes this by generalizing the partial unification logic to
be run both in `compareAppliedType2` and `compareAppliedType1`, this
broke a few tests:
- In `anykind.scala`, `kinder1` and `kinder2` became ambiguous, this is
  fixed by moving `kinder2` in a lower priority base trait.
- One of the implicit search in tests/neg/i3452.scala now goes into an
  infinite loop, this seems to be the same issue as scala#9504, so I disabled
  it for now.
- shapeless in the community build now fails to compile:

```
-- Error: /home/smarter/opt/shapeless/modules/deriving/src/test/scala/shapeless3/deriving/adts.scala:30:64
30 |  sealed trait Opt[+A] derives Eq, Show, Read, Functor, EmptyK, Pure
   |                                                                ^
   | cannot reduce inline match with
   |  scrutinee:  compiletime.erasedValue[EmptyTuple.type] : EmptyTuple.type
   |  patterns :  case _:*:[a @ _, b @ _]
   | This location contains code that was inlined from kinds.scala:152
   | This location contains code that was inlined from kinds.scala:155
   | This location contains code that was inlined from kinds.scala:155
   | This location contains code that was inlined from kinds.scala:150
   | This location contains code that was inlined from type-classes.scala:345
   | This location contains code that was inlined from type-classes.scala:350
-- Error: /home/smarter/opt/shapeless/modules/deriving/src/test/scala/shapeless3/deriving/deriving.scala:163:24
163 |    val v1 = Pure[CList]
    |                        ^
    |no implicit argument of type shapeless3.deriving.Pure[shapeless3.deriving.adts.CList] was found for parameter ef of method apply in object Pure.
    |I found:
    |
    |    shapeless3.deriving.Pure.pureGenC[shapeless3.deriving.adts.CList](
    |      shapeless3.deriving.adts.CList.$asInstanceOf$[
    |
    |          (
    |            deriving.Mirror.Sum{
    |              Kind = shapeless3.deriving.K1.type;
    |                MirroredType[X] = shapeless3.deriving.adts.CList[X]
    |              ; MirroredElemTypes[_$23]
    |            }
    |           &
    |            scala.deriving.Mirror.Sum{
    |              MirroredMonoType = shapeless3.deriving.adts.CList[?];
    |                MirroredType[X] = shapeless3.deriving.adts.CList[X]
    |              ; MirroredLabel = ("CList" : String)
    |            }
    |          ){
    |            MirroredElemTypes[X] = (shapeless3.deriving.adts.CCons[X],
    |              shapeless3.deriving.adts.CNil.type
    |            ); MirroredElemLabels = (("CCons" : String), ("CNil" : String))
    |          }
    |
    |      ]
    |    )
    |
    |But method pureGenC in object Pure does not match type shapeless3.deriving.Pure[shapeless3.deriving.adts.CList].
```

As far as I can tell, this has to do with the following definition:

```
given pureGen[A[_]](using inst: K1.ProductInstances[Alt1.Of[Pure, EmptyK], A]) as Pure[A] =
```

Where:
```
trait Alt1[F[_[_]], G[_[_]], T[_]]
object Alt1 {
  type Of[F[_[_]], G[_[_]]] = [t[_]] =>> Alt1[F, G, t]
}
```

I wasn't able to really figure out what's going on but here are some
observations:
- Alt1.Of is a curried type lambda which is fairly unusual and could be
  mishandled by the compiler somehow.
- If I manually dealias `Alt1.Of[Pure, EmptyK]` to `[X[_]] =>>
  Alt1[Pure, EmptyK, X]`, then compilation fails on Dotty master but
  succeeds with this PR! However, some tests fail (for example, in
  `DerivationTests#data`, the result of `v0.gmapQ(ISB(23, "foo", true))`
  is a empty list somehow).
@odersky odersky self-assigned this Aug 10, 2020
smarter added a commit to dotty-staging/dotty that referenced this issue Aug 11, 2020
So far, like Scala 2, given:

  Either[Int, String] <:< ?F[String]

we were able to infer:

  ?F >: [X] =>> Either[Int, X]

However, in the inverse situation:

  ?F[String] <:< Either[Int, String]

Scala 2, but not Dotty, was able to infer:

  ?F <: [X] =>> Either[Int, X]

This commit fixes this by generalizing the partial unification logic to
be run both in `compareAppliedType2` and `compareAppliedType1`, this
broke a few tests:
- In `anykind.scala`, `kinder1` and `kinder2` became ambiguous, this is
  fixed by moving `kinder2` in a lower priority base trait.
- One of the implicit search in tests/neg/i3452.scala now goes into an
  infinite loop, this seems to be the same issue as scala#9504, so I disabled
  it for now.
smarter added a commit to dotty-staging/dotty that referenced this issue Aug 11, 2020
So far, like Scala 2, given:

  Either[Int, String] <:< ?F[String]

we were able to infer:

  ?F >: [X] =>> Either[Int, X]

However, in the inverse situation:

  ?F[String] <:< Either[Int, String]

Scala 2, but not Dotty, was able to infer:

  ?F <: [X] =>> Either[Int, X]

This commit fixes this by generalizing the partial unification logic to
be run both in `compareAppliedType2` and `compareAppliedType1`, this
broke a few tests:
- In `anykind.scala`, `kinder1` and `kinder2` became ambiguous, this is
  fixed by moving `kinder2` in a lower priority base trait.
- One of the implicit search in tests/neg/i3452.scala now goes into an
  infinite loop, this seems to be the same issue as scala#9504, so I disabled
  it for now.
smarter added a commit to dotty-staging/dotty that referenced this issue Aug 13, 2020
Thanks to the previous commit, this succeeds instead of looping in
implicit search.
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

3 participants