Very long compilation with one missing implicit

[tgodzik]

Compiler version

3.3.1 and 3.4.0-RC1 both.

Minimized code

//> using dep "org.typelevel::log4cats-slf4j:2.6.0"
//> using dep "org.typelevel::cats-effect:3.5.2"
//> using dep "io.github.apimorphism::telegramium-core:8.69.0"
//> using dep "io.github.apimorphism::telegramium-high:8.69.0"
//> using scala "3.4.0-RC1"

import org.typelevel.log4cats.Logger
import org.typelevel.log4cats.slf4j.Slf4jLogger
import org.http4s.blaze.client.BlazeClientBuilder
import cats.effect.{IO, IOApp}
import cats.effect.kernel.Sync
import cats.effect.ExitCode
import cats.effect.kernel.Async
import cats.Parallel
import telegramium.bots.high.Api
import telegramium.bots.high.LongPollBot
import telegramium.bots.Message
import telegramium.bots.ChatIntId
import telegramium.bots.high.BotApi
import telegramium.bots.BotCommand
import telegramium.bots.high.implicits._

class Bot[F[_]: Logger](implicit
    bot: Api[F],
    asyncF: Async[F],
    parallel: Parallel[F]
) extends LongPollBot[F](bot) {

  import cats.syntax.functor.*

  override def onMessage(msg: Message): F[Unit] = 
    import cats.implicits._
    sendMessage(
            chatId = ChatIntId(msg.chat.id),
            text =  msg.text.getOrElse("")
    ).exec.void.handleErrorWith(e => Logger[F].error(e)("failed to send message"))
}

object HelloWorld extends IOApp {
  import cats.implicits._
  
  implicit def logger[F[_]: Sync]: Logger[F] = Slf4jLogger.getLogger[F]

  override def run(args: List[String]): IO[ExitCode] = {
    BlazeClientBuilder[IO].resource.use { httpClient =>
      implicit val api: Api[IO] =
        BotApi(httpClient, baseUrl = s"https://api.telegram.org/botSometoken")
      // implicit val logger: Logger[IO] = Slf4jLogger.getLogger[IO]
      val bot = new Bot()
      bot.start().as(ExitCode.Success)
    }
  }
}

Output

Output is correct, but it takes a very long time to compile.

Expectation

File compiled and returns an error about a missing implicit.

[tgodzik]

It takes almost 3 minutes to compile and get:

Compiling project (Scala 3.4.0-RC1, JVM (17))
[error] ./Main.scala:50:26
[error] No given instance of type org.typelevel.log4cats.Logger[F] was found for a context parameter of constructor Bot in class Bot.
[error] I found:
[error] 
[error]     org.typelevel.log4cats.Logger.eitherTLogger[F², E](
[error]       HelloWorld.logger[F²](/* missing */summon[cats.effect.kernel.Sync[F²]]), ???)
[error] 
[error] But no implicit values were found that match type cats.effect.kernel.Sync[F²]
[error] 
[error] where:    F  is a type variable with constraint <: [_] =>> Any
[error]           F² is a type variable with constraint <: [_²] =>> Any
[error] .
[error]       val bot = new Bot()
[error]                          ^
Error compiling project (Scala 3.4.0-RC1, JVM (17))
Compilation failed

[valencik]

A bit more minimized:

//> using dep "org.typelevel::cats-effect:3.5.2"
//> using dep "org.typelevel::log4cats-slf4j:2.6.0"
//> using scala "3.3.1"

import cats.effect.kernel.Sync
import cats.effect.IO
import org.typelevel.log4cats.Logger
import org.typelevel.log4cats.slf4j.Slf4jLogger

class Bot[F[_]: Logger]() {}

object HelloWorld {
  
  implicit def logger[F[_]: Sync]: Logger[F] = Slf4jLogger.getLogger[F]

  //implicit val logger: Logger[IO] = Slf4jLogger.getLogger[IO]
  def main(args: Array[String]): Unit =
    new Bot()
}

The above takes a minute or more to compile before failing with the originally reported error.

Uncommenting the implicit val line below results in successful compilation in less than a second.

implicit val logger: Logger[IO] = Slf4jLogger.getLogger[IO]

And commenting out the implicit def line results in a quick failed compilation.

//implicit def logger[F[_]: Sync]: Logger[F] = Slf4jLogger.getLogger[F]

The failed compilation then produces a different error:

[error] No given instance of type org.typelevel.log4cats.Logger[F] was found for a context parameter of constructor Bot in class Bot.
[error] I found:
[error] 
[error]     org.typelevel.log4cats.Logger.eitherTLogger[F², E](
[error]       org.typelevel.log4cats.Logger.kleisliLogger[F³, A](
[error]         org.typelevel.log4cats.Logger.optionTLogger[F⁴](
[error]           org.typelevel.log4cats.Logger.eitherTLogger[F⁵, E²](
[error]             /* missing */summon[org.typelevel.log4cats.Logger[F⁵]], ???),
[error]         ???)
[error]       ),
[error]     ???)
[error] 
[error] But no implicit values were found that match type org.typelevel.log4cats.Logger[F⁵]
[error] 
[error] where:    E  is a type variable with constraint 
[error]           E² is a type variable with constraint 
[error]           F  is a type variable with constraint <: [_] =>> Any
[error]           F² is a type variable with constraint <: [_²] =>> Any
[error]           F³ is a type variable with constraint <: [_³] =>> Any
[error]           F⁴ is a type variable with constraint <: [_⁴] =>> Any
[error]           F⁵ is a type variable with constraint <: [_²] =>> Any
[error] .
[error]     new Bot()

[tgodzik]

I think another minimization would be:

//> using scala "3.3.1"
//> using dep org.http4s::http4s-ember-client:1.0.0-M40
//> using dep org.http4s::http4s-ember-server:1.0.0-M40
//> using dep org.http4s::http4s-dsl:1.0.0-M40

import cats.effect.*
import cats.implicits.*

class Test[F[_]: Concurren]:
    def hello = ???

object Test:
    def apply[F[_]: Concurrent] = new Test[F]

The big problem here is that if we want to get completions on Concurren we are unable to do it in a reasonable time, so IDE functionalities fail.

[tgodzik]

What I find weird here is that we continue looking for an implicit while the type is actually an error and doesn't exist. Could we forgo the implicit search if the type is an error?

[dwijnand]

Yes, that sounds reasonable. We do some implicit searching to give user's suggestions and advice, but we can make that more conditional. Including, perhaps, an IDE specific way to avoid it.

[odersky]

Which type is an error? The implicit it searched for was rg.typelevel.log4cats.Logger[F] which is fine. The line

HelloWorld.logger[F²](/* missing */summon[cats.effect.kernel.Sync[F²]]), ???)

just shows where the implicit search was unsuccessful, it is the result of the implicit search, not the input.

Why does it take so long? I have no idea, but generally one should find the issue with the implicits in the library one imports. Maybe we can give a configurable timeout for implicit search to avoid this situation.

[tgodzik]

I think it's easier to see it in the last example:

class Test[F[_]: Concurren]:
    def hello = ???

where Concurren is missing the t. When run via scala compile it actually reports an error, but then continues to compile.

Why does it take so long? I have no idea, but generally one should find the issue with the implicits in the library one imports.

Those imports are a bit much when I look at them, but this is a typical scenario with cats. This came up in one of the RockTheJVM courses, so I assume this might cause a lot of headaches to a larger number of users.

Maybe we can give a configurable timeout for implicit search to avoid this situation.

Would help the interactive scenario for sure, but I am not sure if this fixes the overall problem.

[odersky]

I believe the issue is that the F parameter is less constrained than expected since there is a syntax error in the context bound. Then the system tries to find an implicit for an unconstrained F and since these libraries are full of higher-kinded Fs and have lots of implicits (some of them recursive) there's a deluge of implicits to try.

One thing we could maybe do is if there is an error in a subtype bound or context bound we mark the bound type parameter as "tainted". Then we would immediately return error for every implicit search of a type containing that parameter. to generalize this, if we have an implicit parameter for type T which is ill-formed, we'd also mark all type parameters appearing in T as tainted.