Dotty: Type Mismatch Error is very slow

[FabioPinheiro]

Minimized code

import cats.syntax.all._

trait AAA[T]

object Test {
  implicit def aaaShow[T](implicit showT: cats.Show[T]): cats.Show[AAA[T]] = ???

  ("Enforcing union type": Int | Unit) //This will give a Type Mismatch Error
}

My build.sbt:

libraryDependencies += ("org.typelevel" %% "cats-core" % "2.2.0-M1").withDottyCompat(scalaVersion.value)
scalaVersion := "0.23.0-RC1"

https://github.com/FabioPinheiro/cats-money/tree/dotty-working-hard

Output

Expect the Type Mismatch Error almost immediately.

Expectation

The compilation should not take more than a few seconds!

If we replace the implicit def (that is a valid scala2 code) with:

given aaaShow[T](using cats.Show[T]) as cats.Show[AAA[T]] = ???

The compilation takes around 45 seconds (also very slow)

Also, there is not any to stop compilation
After a SIGINT the sbt prints: [warn] Canceling execution... but it never ends.
I don't know where to report this. I have to send a SIGKILL to sbt and to bloop/metals

[FabioPinheiro]

@smarter as we discussed I open a ticket
This seems similar to #2030

[odersky]

Can you try to minimize this further?

The problem is that implicit search can produce arbitrarily large search
trees, and this might take arbitrarily long. That's not necessarily a fault
of the compiler; it could also be that the query produces too large a
result or that search goes into too many dead-ends.

It's unlikely don't think it has to do with Dotty vs Scala-2 syntax. The
two map to exactly the same internal representation.

On Tue, Apr 21, 2020 at 8:11 PM Fabio Pinheiro [e-mail]
wrote:

@smarter https://github.com/smarter as we discussed I open a ticket
This seems similar to #2030
https://github.com/lampepfl/dotty/issues/2030

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/lampepfl/dotty/issues/8763#issuecomment-617327274,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/AAGCKVS2LSU4PX7L3RYLUFDRNXOVXANCNFSM4MNP73EA
.

--
Prof. Martin Odersky
LAMP/IC, EPFL

[smarter]

@odersky FWIW, if you're interested in trying to reproduce this without having to locally publish dotty to use an external dependency, it's easy enough to do using coursier:

./bin/dotc -classpath "$(cs fetch -p org.typelevel:cats-core_2.13:2.2.0-M1)" file.scala

I can confirm that replacing the implicit def by a given as mentioned drastically reduces the compilation time somehow.

[smarter]

Turning on the implicits printer, I see a lot of references to types defined in cats, so it's likely to be very hard to minimize any further since this probably requires a ton of implicits available to reproduce.

[smarter]

If I remove the call to importSuggestionAddendum from https://github.com/lampepfl/dotty/blob/5ec51f2dfc5186ed22f5d6f693a68bdade1dc8ef/compiler/src/dotty/tools/dotc/reporting/messages.scala#L280 then compilation ends after 2 seconds. If I don't, then it takes forever to generate the following message:

-- [E007] Type Mismatch Error: try/i8763.scala:9:3 -----------------------------
9 |  ("Enforcing union type": Int | Unit) //This will give a Type Mismatch Error
  |   ^^^^^^^^^^^^^^^^^^^^^^
  |Found:    ("Enforcing union type" : String)
  |Required: Int | Unit
  |
  |One of the following imports might make progress towards fixing the problem:
  |
  |  import collection.immutable.WrappedString.UnwrapOp
  |  import cats.syntax.all.catsSyntaxTabulate
  |  import cats.syntax.all.catsSyntaxFunction1
  |  import cats.syntax.all.catsSyntaxParallelApply
  |  import cats.syntax.parallel.catsSyntaxParallelApply
  |  import cats.syntax.all.catsSyntaxAlternativeSeparate
  |  import cats.syntax.all.catsSyntaxBitraverse
  |  import cats.syntax.all.catsSyntaxBitraverseBinCompat0
  |  import cats.syntax.all.catsSyntaxParallelBitraverse
  |  import cats.syntax.all.catsSyntaxParallelFlatSequence
  |  import cats.syntax.all.catsSyntaxParallelLeftTraverse
  |  import cats.syntax.all.catsSyntaxParallelUnorderedFlatSequence
  |  import cats.syntax.all.toArrowChoiceOps
  |  import cats.syntax.all.toArrowOps
  |  import cats.syntax.all.toBifoldableOps
  |  import cats.syntax.all.toBifunctorOps
  |  import cats.syntax.all.toChoiceOps
  |  import cats.syntax.all.toComposeOps
  |  import cats.syntax.all.toProfunctorOps
  |  import cats.syntax.all.toStrongOps
  |  import cats.syntax.alternative.catsSyntaxAlternativeSeparate
  |  import cats.syntax.arrow.toArrowOps
  |  import cats.syntax.arrowChoice.toArrowChoiceOps
  |  import cats.syntax.bifoldable.toBifoldableOps
  |  import cats.syntax.bifunctor.toBifunctorOps
  |  import cats.syntax.bitraverse.catsSyntaxBitraverse
  |  import cats.syntax.bitraverse.catsSyntaxBitraverseBinCompat0
  |  import cats.syntax.choice.toChoiceOps
  |  import cats.syntax.compose.toComposeOps
  |  import cats.syntax.parallel.catsSyntaxParallelBitraverse
  |  import cats.syntax.parallel.catsSyntaxParallelFlatSequence
  |  import cats.syntax.parallel.catsSyntaxParallelLeftTraverse
  |  import cats.syntax.parallel.catsSyntaxParallelUnorderedFlatSequence
  |  import collection.JavaConverters.seqAsJavaListConverter
  |  import cats.syntax.representable.catsSyntaxTabulate
  |  import cats.syntax.profunctor.toProfunctorOps
  |  import cats.syntax.strong.toStrongOps
  |  import collection.JavaConverters.asJavaCollectionConverter
  |  import collection.JavaConverters.asJavaIterableConverter
  |  import collection.IterableOnce.iterableOnceExtensionMethods
  |  import cats.syntax.align.toAlignOps
  |  import cats.syntax.all.catsSyntaxApplicative
  |  import cats.syntax.all.catsSyntaxApplicativeError
  |  import cats.syntax.all.catsSyntaxApply
  |  import cats.syntax.all.catsSyntaxDistributiveOps
  |  import cats.syntax.all.catsSyntaxFlatten
  |  import cats.syntax.all.catsSyntaxNestedReducible
  |  import cats.syntax.all.catsSyntaxParallelSequence
  |  import cats.syntax.all.catsSyntaxApplicativeErrorId
  |  import cats.syntax.all.catsSyntaxApplyOps
  |  import cats.syntax.all.catsSyntaxContravariantMonoidal
  |  import cats.syntax.all.catsSyntaxContravariantSemigroupal
  |  import cats.syntax.all.catsSyntaxEitherId
  |  import cats.syntax.all.catsSyntaxEitherK
  |  import cats.syntax.all.catsSyntaxFoldOps
  |  import cats.syntax.all.catsSyntaxFoldableOps0
  |  import cats.syntax.all.catsSyntaxParallelUnorderedSequence
  |  import cats.syntax.all.catsSyntaxGroup
  |  import cats.syntax.all.catsSyntaxHash
  |  import cats.syntax.all.catsSyntaxIndex
  |  import cats.syntax.all.catsSyntaxMonad
  |  import cats.syntax.all.catsSyntaxMonadError
  |  import cats.syntax.all.catsSyntaxNestedFoldable
  |  import cats.syntax.all.catsSyntaxNestedId
  |  import cats.syntax.all.catsSyntaxParallelSequence_
  |  import cats.syntax.all.catsSyntaxUnite
  |  import cats.syntax.all.catsSyntaxApplicativeId
  |  import cats.syntax.all.catsSyntaxEitherIdBinCompat0
  |  import cats.syntax.all.catsSyntaxMonadIdOps
  |  import cats.syntax.all.catsSyntaxMonoid
  |  import cats.syntax.all.catsSyntaxOptionId
  |  import cats.syntax.all.catsSyntaxOrder
  |  import cats.syntax.all.catsSyntaxParallelTraverse
  |  import cats.syntax.all.catsSyntaxPartialOrder
  |  import cats.syntax.all.catsSyntaxEq
  |  import cats.syntax.all.catsSyntaxFlatMapIdOps
  |  import cats.syntax.all.catsSyntaxFlatMapOps
  |  import cats.syntax.all.catsSyntaxIorId
  |  import cats.syntax.all.catsSyntaxParallelAp
  |  import cats.syntax.all.catsSyntaxParallelFlatTraverse
  |  import cats.syntax.all.catsSyntaxParallelFoldMapA
  |  import cats.syntax.all.catsSyntaxParallelTraverse_
  |  import cats.syntax.all.catsSyntaxParallelUnorderedTraverse
  |  import cats.syntax.all.catsSyntaxReducibleOps0
  |  import cats.syntax.all.catsSyntaxSemigroup
  |  import cats.syntax.all.catsSyntaxSemigroupal
  |  import cats.syntax.all.catsSyntaxUnorderedFoldableOps
  |  import cats.syntax.alternative.catsSyntaxUnite
  |  import cats.syntax.all.catsSyntaxValidatedId
  |  import cats.syntax.all.catsSyntaxValidatedIdBinCompat0
  |  import cats.syntax.all.catsSyntaxWriterId
  |  import cats.syntax.all.toAlignOps
  |  import cats.syntax.all.toCoflatMapOps
  |  import cats.syntax.all.toComonadOps
  |  import cats.syntax.all.toContravariantOps
  |  import cats.syntax.all.toDistributiveOps
  |  import cats.syntax.all.toFlatMapOps
  |  import cats.syntax.all.toFoldableOps
  |  import cats.syntax.all.toFunctorFilterOps
  |  import cats.syntax.all.toFunctorOps
  |  import cats.syntax.all.toInvariantOps
  |  import cats.syntax.all.toNonEmptyTraverseOps
  |  import cats.syntax.all.toReducibleOps
  |  import cats.syntax.all.toSemigroupKOps
  |  import cats.syntax.all.toShow
  |  import cats.syntax.all.toTraverseFilterOps
  |  import cats.syntax.all.toTraverseOps
  |  import cats.syntax.all.toUnorderedFoldableOps
  |  import cats.syntax.all.toUnorderedTraverseOps
  |  import cats.syntax.applicative.catsSyntaxApplicative
  |  import cats.syntax.applicative.catsSyntaxApplicativeId
  |  import cats.syntax.applicativeError.catsSyntaxApplicativeError
  |  import cats.syntax.applicativeError.catsSyntaxApplicativeErrorId
  |  import cats.syntax.apply.catsSyntaxApply
  |  import cats.syntax.apply.catsSyntaxApplyOps
  |  import cats.syntax.cartesian.catsSyntaxSemigroupal
  |  import cats.syntax.coflatMap.toCoflatMapOps
  |  import cats.syntax.comonad.toComonadOps
  |  import cats.syntax.contravariant.toContravariantOps
  |  import cats.syntax.contravariantMonoidal.catsSyntaxContravariantMonoidal
  |  import cats.syntax.contravariantSemigroupal.catsSyntaxContravariantSemigroupal
  |  import cats.syntax.distributive.catsSyntaxDistributiveOps
  |  import cats.syntax.distributive.toDistributiveOps
  |  import cats.syntax.either.catsSyntaxEitherId
  |  import cats.syntax.either.catsSyntaxEitherIdBinCompat0
  |  import cats.syntax.eitherK.catsSyntaxEitherK
  |  import cats.syntax.flatMap.catsSyntaxFlatten
  |  import cats.syntax.eq.catsSyntaxEq
  |  import cats.syntax.flatMap.catsSyntaxFlatMapIdOps
  |  import cats.syntax.flatMap.catsSyntaxFlatMapOps
  |  import cats.syntax.flatMap.toFlatMapOps
  |  import cats.syntax.foldable.catsSyntaxFoldOps
  |  import cats.syntax.foldable.catsSyntaxFoldableOps0
  |  import cats.syntax.foldable.catsSyntaxNestedFoldable
  |  import cats.syntax.foldable.toFoldableOps
  |  import cats.syntax.foldable.toUnorderedFoldableOps
  |  import cats.syntax.functor.toFunctorOps
  |  import cats.syntax.functorFilter.toFunctorFilterOps
  |  import cats.syntax.nested.catsSyntaxNestedId
  |  import cats.syntax.group.catsSyntaxGroup
  |  import cats.syntax.group.catsSyntaxSemigroup
  |  import cats.syntax.hash.catsSyntaxHash
  |  import cats.syntax.invariant.toInvariantOps
  |  import cats.syntax.ior.catsSyntaxIorId
  |  import cats.syntax.monad.catsSyntaxMonad
  |  import cats.syntax.monad.catsSyntaxMonadIdOps
  |  import cats.syntax.monadError.catsSyntaxMonadError
  |  import cats.syntax.monoid.catsSyntaxMonoid
  |  import cats.syntax.monoid.catsSyntaxSemigroup
  |  import cats.syntax.nonEmptyTraverse.toNonEmptyTraverseOps
  |  import cats.syntax.option.catsSyntaxOptionId
  |  import cats.syntax.order.catsSyntaxEq
  |  import cats.syntax.parallel.catsSyntaxParallelAp
  |  import cats.syntax.parallel.catsSyntaxParallelFlatTraverse
  |  import cats.syntax.parallel.catsSyntaxParallelFoldMapA
  |  import cats.syntax.parallel.catsSyntaxParallelSequence
  |  import cats.syntax.parallel.catsSyntaxParallelSequence_
  |  import cats.syntax.parallel.catsSyntaxParallelTraverse
  |  import cats.syntax.parallel.catsSyntaxParallelUnorderedSequence
  |  import cats.syntax.order.catsSyntaxOrder
  |  import cats.syntax.order.catsSyntaxPartialOrder
  |  import cats.syntax.parallel.catsSyntaxParallelTraverse_
  |  import cats.syntax.parallel.catsSyntaxParallelUnorderedTraverse
  |  import cats.syntax.reducible.catsSyntaxNestedReducible
  |  import cats.syntax.partialOrder.catsSyntaxPartialOrder
  |  import cats.syntax.partialOrder.catsSyntaxEq
  |  import cats.syntax.reducible.catsSyntaxReducibleOps0
  |  import cats.syntax.reducible.toReducibleOps
  |  import cats.syntax.representable.catsSyntaxIndex
  |  import cats.syntax.semigroup.catsSyntaxSemigroup
  |  import cats.syntax.semigroupal.catsSyntaxSemigroupal
  |  import cats.syntax.semigroupk.toSemigroupKOps
  |  import cats.syntax.show.toShow
  |  import cats.syntax.traverse.toTraverseOps
  |  import cats.syntax.traverseFilter.toTraverseFilterOps
  |  import cats.syntax.unorderedFoldable.catsSyntaxUnorderedFoldableOps
  |  import cats.syntax.unorderedFoldable.toUnorderedFoldableOps
  |  import cats.syntax.unorderedTraverse.toUnorderedTraverseOps
  |  import cats.syntax.validated.catsSyntaxValidatedId
  |  import cats.syntax.validated.catsSyntaxValidatedIdBinCompat0
  |  import cats.syntax.writer.catsSyntaxWriterId
  |  import collection.Searching.search
  |  import reflect.Selectable.reflectiveSelectable
  |  import util.chaining.scalaUtilChainingOps

[FabioPinheiro]

@smarter does that also explain the difference in the compilation time between implicit def aaaShow... and given aaaShow.. ?

[smarter]

Sort of, I don't understand why with given we don't get a list of import suggestions but with implicit def we do.

[odersky]

That's bizarre. It should not take forever. There's a time limit built in. I have to investigate...

[odersky]

@smarter Can you find out _how many calls_ to importSuggestionAddendum were made? There should be only one for each printed message, and that call is allowed to take not more than 10 seconds.

So what you are seeing could be either

• that there are in fact many calls to importSuggestionAddendum which are not printed. That could point to a lack of laziness in error message generation somewhere.
• that somehing's wrong with the timer logic

[smarter]

There is exactly one call to importSuggestionAddendum. Also, here's a probably unrelated but concerning error which popped up today when running this code again:

java.lang.IllegalArgumentException: Comparison method violates its general contract! while compiling try/i8763.scala
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeHi(TimSort.java:899)
        at java.util.TimSort.mergeAt(TimSort.java:516)
        at java.util.TimSort.mergeCollapse(TimSort.java:441)
        at java.util.TimSort.sort(TimSort.java:245)
        at java.util.Arrays.sort(Arrays.java:1438)
        at scala.collection.SeqOps.sorted(Seq.scala:704)
        at scala.collection.SeqOps.sorted$(Seq.scala:696)
        at scala.collection.immutable.List.scala$collection$immutable$StrictOptimizedSeqOps$$super$sorted(List.scala:79)
        at scala.collection.immutable.StrictOptimizedSeqOps.sorted(StrictOptimizedSeqOps.scala:80)
        at scala.collection.immutable.StrictOptimizedSeqOps.sorted$(StrictOptimizedSeqOps.scala:80)
        at scala.collection.immutable.List.sorted(List.scala:79)
        at scala.collection.SeqOps.sortWith(Seq.scala:731)
        at scala.collection.SeqOps.sortWith$(Seq.scala:731)
        at scala.collection.AbstractSeq.sortWith(Seq.scala:1153)
        at dotty.tools.dotc.typer.ImportSuggestions.importSuggestionAddendum(ImportSuggestions.scala:260)
        at dotty.tools.dotc.typer.Typer.importSuggestionAddendum(Typer.scala:85)
        at dotty.tools.dotc.reporting.messages$TypeMismatch.msg(messages.scala:280)
        at dotty.tools.dotc.reporting.Message.message(Message.scala:80)
        at dotty.tools.dotc.reporting.Message.isNonSensical(Message.scala:92)
        at dotty.tools.dotc.reporting.HideNonSensicalMessages.isHidden(HideNonSensicalMessages.scala:16)
        at dotty.tools.dotc.reporting.AbstractReporter.isHidden(AbstractReporter.scala:8)
        at dotty.tools.dotc.reporting.Reporter.report(Reporter.scala:265)
        at dotty.tools.dotc.reporting.Reporting.error(Reporter.scala:129)
        at dotty.tools.dotc.core.Contexts$Context.error(Contexts.scala:78)
        at dotty.tools.dotc.typer.ErrorReporting$.errorType(ErrorReporting.scala:30)
        at dotty.tools.dotc.typer.ErrorReporting$.errorTree(ErrorReporting.scala:21)
        at dotty.tools.dotc.typer.ErrorReporting$.errorTree(ErrorReporting.scala:24)
        at dotty.tools.dotc.typer.ErrorReporting$Errors.typeMismatch(ErrorReporting.scala:106)
        at dotty.tools.dotc.typer.Typer.recover$1(Typer.scala:3286)
        at dotty.tools.dotc.typer.Typer.adaptToSubType$1(Typer.scala:3305)
        at dotty.tools.dotc.typer.Typer.adaptNoArgsOther$4(Typer.scala:3119)
        at dotty.tools.dotc.typer.Typer.adaptNoArgs$1(Typer.scala:3171)
        at dotty.tools.dotc.typer.Typer.adapt1(Typer.scala:3379)
        at dotty.tools.dotc.typer.Typer.op$3(Typer.scala:2767)
        at dotty.tools.dotc.typer.Typer.adapt(Typer.scala:2768)
        at dotty.tools.dotc.typer.Typer.op$1(Typer.scala:2433)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2442)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2445)
        at dotty.tools.dotc.typer.Typer.ascription$1(Typer.scala:724)
        at dotty.tools.dotc.typer.Typer.typedTyped$$anonfun$4(Typer.scala:761)
        at dotty.tools.dotc.typer.Typer.cases$1(Typer.scala:713)
        at dotty.tools.dotc.typer.Typer.typedTyped(Typer.scala:762)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2340)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2394)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2379)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2394)
        at dotty.tools.dotc.typer.Typer.op$1(Typer.scala:2433)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2442)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2445)
        at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2490)
        at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2512)
        at dotty.tools.dotc.typer.Typer.typedClassDef(Typer.scala:2003)
        at dotty.tools.dotc.typer.Typer.typedNamed$1(Typer.scala:2325)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2393)
        at dotty.tools.dotc.typer.Typer.op$1(Typer.scala:2433)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2442)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2445)
        at dotty.tools.dotc.typer.Typer.traverse$1(Typer.scala:2467)
        at dotty.tools.dotc.typer.Typer.typedStats(Typer.scala:2512)
        at dotty.tools.dotc.typer.Typer.typedPackageDef(Typer.scala:2129)
        at dotty.tools.dotc.typer.Typer.typedUnnamed$1(Typer.scala:2366)
        at dotty.tools.dotc.typer.Typer.typedUnadapted(Typer.scala:2394)
        at dotty.tools.dotc.typer.Typer.op$1(Typer.scala:2433)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2442)
        at dotty.tools.dotc.typer.Typer.typed(Typer.scala:2445)
        at dotty.tools.dotc.typer.Typer.typedExpr(Typer.scala:2556)
        at dotty.tools.dotc.typer.FrontEnd.liftedTree1$1(FrontEnd.scala:78)
        at dotty.tools.dotc.typer.FrontEnd.typeCheck$$anonfun$1(FrontEnd.scala:83)
        at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
        at dotty.tools.dotc.typer.FrontEnd.monitor(FrontEnd.scala:42)
        at dotty.tools.dotc.typer.FrontEnd.typeCheck(FrontEnd.scala:84)
        at dotty.tools.dotc.typer.FrontEnd.runOn$$anonfun$3(FrontEnd.scala:113)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at scala.collection.immutable.List.foreach(List.scala:305)
        at dotty.tools.dotc.typer.FrontEnd.runOn(FrontEnd.scala:113)
        at dotty.tools.dotc.Run.runPhases$4$$anonfun$4(Run.scala:165)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1323)
        at dotty.tools.dotc.Run.runPhases$5(Run.scala:175)
        at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:183)
        at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
        at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:64)
        at dotty.tools.dotc.Run.compileUnits(Run.scala:190)
        at dotty.tools.dotc.Run.compileSources(Run.scala:127)
        at dotty.tools.dotc.Run.compile(Run.scala:110)
        at dotty.tools.dotc.Driver.doCompile(Driver.scala:38)
        at dotty.tools.dotc.Driver.process(Driver.scala:194)
        at dotty.tools.dotc.Driver.process(Driver.scala:163)
        at dotty.tools.dotc.Driver.process(Driver.scala:175)
        at dotty.tools.dotc.Driver.main(Driver.scala:202)
        at dotty.tools.dotc.Main.main(Main.scala)

As far as I can tell this means that Applications#compare which we use to compare refs is not a valid sort function (I guess it's not transitive ?)

[odersky]

Ah, yes, compare is not a good argument for a sorting function since it's not a total order. I'll work on a fix.

[odersky]

So, the mystery is mostly solved now:

In the example we have 265 suggested implicits. We sort them using compare as the ordering criterion. But we do so in ImplicitsEnabled mode, so each of these comparisons might entail further costly implicit searches. And all this is done when we are already past the code that's controlled by the 10 second timer.

If we retract ImplicitsEnabled it completes immediately after the 10 seconds run out (or thereabouts, I did not measure whether it was over 10 seconds, or just finished close to it).

Also, with #8640 merged, it finishes immediately, since it seems the 265 suggestions were all already available anyway, so an additional import would change nothing.

That said, to have 265 implicits available for an implicit search is ... scary .... I would think that even in the best case compile times will take a big hit with such an architecture.

"Available" means: The type is close enough that we have to do a full typecheck. I believe that's because of all the F[_] effect types in cats. They are poison for any hope of reasonable compile times.

[smarter]

That said, to have 265 implicits available for an implicit search is ... scary .... I would think that even in the best case compile times will take a big hit with such an architecture.

Note that all these implicits come from cats.syntax which only provides extension methods via implicit classes (see https://github.com/typelevel/cats/tree/master/core/src/main/scala/cats/syntax). Hopefully using actually Scala 3 extension methods means the implicit scope won't be polluted with them ?

[FabioPinheiro]

Glad I could help a little bit
Thanks for the fix

[xuwei-k]

java.lang.IllegalArgumentException: Comparison method violates its general contract! while compiling

I got still same error with dotty 0.24.0-RC1 and latest( 0.25.0-bin-20200518-b5eded6-NIGHTLY ) 😢

[smarter]

@xuwei-k can you open an issue with an example that triggers the exception ?

[xuwei-k]

reproduced in community-build scalaz test 😭

https://github.com/lampepfl/dotty/runs/710039626#step:9:8410