Add tree/graph visualisation for divergent/circular implicit expansion

[tribbloid]

Implicit expansion in all versions of scala uses a complex graph search to find a path to convert one type to another, using all implicit functions in the scope as building blocks of bridges.

When such path cannot be found it will throw an error (e.g. if 2 bridges are both viable options and are equally preferrable, it will throw an ambiguous implicit error). Of all these errors, the "circular / divergent implicit expansion" is the most complex of them all.

• Circular implicit expansion is encountered when a path leads to a type that has been visited before (a.k.a not making progress):

in both scala 2 and 3, the search algorithm will silently abandon the path and backtrack to the entry point of the circle

• Divergent implicit expansion is encountered when a path leads to a different type, yet from the same type constructor, and has become more complex or inductive, in which case it poses a certain risk of visiting infinitely inductive type(s):

Scala 2 will fail immediately, scala 3 will fail silently and backtrack. Both shapeless Lazy and implicit-by-name feature was invented to suppress such behaviour of risk aversion, as a successful implicit conversion between inductive types may still happen afterwards

Unfortunately, such complexity is aggravated by the extremely brief default error message, usually only contains:

diverging implicit expansion for type xxx.XXX
starting with method yyy in trait ZZZ

The current splain 0.5.x did very little to improve it.

Since the error is caused by an anomaly in graph search, the error message should also contains a graph or at least its tree variant, indicating the incomplete path between the visited type when the error was encountered.

I have done some work in tree and graph visualisation for the type heyting algebra in scala, so after a compatibility patch for scala 2.13.6 I can start applying my work immediately

[tribbloid]

There is one problem:

The definition of all supported implicit errors were pushed into scala compiler:

  object ImplicitErrorSpecifics {
    case class NotFound(param: Symbol) extends ImplicitErrorSpecifics

    case class NonconformantBounds(
        targs: List[Type], tparams: List[Symbol], originalError: Option[AbsTypeError],
    ) extends ImplicitErrorSpecifics
  }

And subsequently got deleted in the analyzer branch.

Now I can only see a disabled test case called "divergent". Do you know what's the last version when it was supported?

[tek]

not sure this ever had an implementation!

[tribbloid]

Well, you built it from ground up, so if you can't remember then it never existed.

For comparison, The dotty compiler seems to be able to handle it with reasonable clarity:

When compiling the following 3 toy cases:

package com.tribbloids.spike.dotty

object DivergingImplicits {

  class ***[A, B]
  class >:<[A, B]
  class C
  trait D

  object Endo {
    implicit def f(implicit c: C): C = ???

    implicitly[C]
  }

  object Circular {
    implicit def f(implicit c: C): D = ???
    implicit def g(implicit d: D): C = ???

    implicitly[C]
  }

  object Diverging {
    trait ::[A, B]
    implicit def f[A, B](implicit ii: Int :: A :: B): A :: B = ???

    implicitly[C :: D]
  }
}

Dotty pointed out the failed case when circular/diverging is encountered:

 -- Error: /home/peng/git/dottyspike/src/main/scala/com/tribbloids/spike/dotty/DivergingImplicits.scala:13:17 
 13 |    implicitly[C]
    |                 ^
    |no implicit argument of type com.tribbloids.spike.dotty.DivergingImplicits.C was found for parameter e of method implicitly in object Predef.
    |I found:
    |
    |    com.tribbloids.spike.dotty.DivergingImplicits.Endo.f(
    |      /* missing */summon[com.tribbloids.spike.dotty.DivergingImplicits.C]
    |    )
    |
    |But method f in object Endo produces a diverging implicit search when trying to match type com.tribbloids.spike.dotty.DivergingImplicits.C.
    |
    |The following import might make progress towards fixing the problem:
    |
    |  import com.tribbloids.spike.dotty.DivergingImplicits.Circular.g
    |
 -- Error: /home/peng/git/dottyspike/src/main/scala/com/tribbloids/spike/dotty/DivergingImplicits.scala:20:17 
 20 |    implicitly[C]
    |                 ^
    |no implicit argument of type com.tribbloids.spike.dotty.DivergingImplicits.C was found for parameter e of method implicitly in object Predef.
    |I found:
    |
    |    com.tribbloids.spike.dotty.DivergingImplicits.Circular.g(
    |      com.tribbloids.spike.dotty.DivergingImplicits.Circular.f(
    |        /* missing */summon[com.tribbloids.spike.dotty.DivergingImplicits.C]
    |      )
    |    )
    |
    |But method g in object Circular produces a diverging implicit search when trying to match type com.tribbloids.spike.dotty.DivergingImplicits.C.
    |
    |The following import might make progress towards fixing the problem:
    |
    |  import com.tribbloids.spike.dotty.DivergingImplicits.Endo.f
    |
 -- Error: /home/peng/git/dottyspike/src/main/scala/com/tribbloids/spike/dotty/DivergingImplicits.scala:27:22 
 27 |    implicitly[C :: D]
    |                      ^
    |no implicit argument of type com.tribbloids.spike.dotty.DivergingImplicits.C :: 
    |  com.tribbloids.spike.dotty.DivergingImplicits.D was found for parameter e of method implicitly in object Predef.
    |I found:
    |
    |    com.tribbloids.spike.dotty.DivergingImplicits.Diverging.f[A, B](
    |      com.tribbloids.spike.dotty.DivergingImplicits.Diverging.f[A, B](
    |        /* missing */summon[Int :: A :: B]
    |      )
    |    )
    |
    |But method f in object Diverging produces a diverging implicit search when trying to match type Int :: A :: B.
 three errors found

It is still not very informative for complex projects, it should have shown the complete search tree.

But it is already vastly better than scala 2 compiler

[tribbloid]

I'll ask the question again. What's your preferred IDE for this project? it should be either vim, VSCode or IntelliJ IDEA.

In IntelliJ IDEA it frequently run in problems like incompatible specs2 or sbt classpath contamination:

https://stackoverflow.com/questions/27886370/how-to-have-sbt-plugin-exclude-its-dependency

I may have to swap them all out, or wait for them to be fixed

[tribbloid]

Good news, it appears that the new AnalyzerPlugin has an extendable method which can be customised, If I implement it, an entry point may be provided:

    override def pluginsNotifyImplicitSearch(search: global.analyzer.ImplicitSearch): Unit = {

      error("dummy!")
      super.pluginsNotifyImplicitSearch(search)
    }

[tek]

I use only neovim, so can't really make any judgements about other IDEs.

regarding that plugin hook, I think you cannot stop the default machinery from running by overriding it

[tribbloid]

@tek Ahhh, that explain it.

You are right, I cannot, the entire thing is in the object DivergentImplicitRecovery. But at least it gives the input which I can run a shadow DivergentImplicitRecovery that memorise the search tree.

[tribbloid]

For further experiments on this feature, I'll rollback the SplainPluginCompat layer for the following 2 reasons:

1. I didn't get a reply for:

https://contributors.scala-lang.org/t/need-to-backport-all-the-missing-splain-configurations-for-vimplicits-vtype-diffs-options/5274

Yet I think removing feature without deprecation notice is a very bad idea. (Sometimes bad but necessary)

2. It can cover the error processing that wasn't brokered by the AnalyzerPlugin, we can gradually move them later to scalac, the SplainPluginCompat could be our test bench

[tek]

Still unsure why you want those back. The maintainers wanted the options to be less detailed, so we agreed to default to some things, like always using color, and the rest is still in here: https://github.com/scala/scala/blob/7e0e50ebd2c02067d7f007ca0eb1de194bd91fd9/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala#L504

[tribbloid]

Good, reason 1 should be gone. Reason 2 is still there: in previous versions we can override any part of typechecker.Analyzer, but now we can only override the part exposed by AnalyzerPlugin which is just a fraction of typechecker.Analyzer.

For instance, I'm able to override handling of diverging implicit error in typechecker.Analyzer, but I can't do it in the plugin

[tribbloid]

Sorry, I mean, I'll rollback the initialiser to attach the compiler Plugin, namely the following part:

  val analyzerField = classOf[Global].getDeclaredField("analyzer")
  analyzerField.setAccessible(true)
  analyzerField.set(global, analyzer)

  val phasesSetMapGetter = classOf[Global]
    .getDeclaredMethod("phasesSet")

  val phasesSet = phasesSetMapGetter
    .invoke(global)
    .asInstanceOf[scala.collection.mutable.Set[SubComponent]]

  if (phasesSet.exists(_.phaseName == "typer")) {
    def subcomponentNamed(name: String) =
      phasesSet
        .find(_.phaseName == name)
        .head
    val oldScs @ List(oldNamer @ _, oldPackageobjects @ _, oldTyper @ _) = List(
      subcomponentNamed("namer"),
      subcomponentNamed("packageobjects"),
      subcomponentNamed("typer"),
    )
    val newScs = List(analyzer.namerFactory, analyzer.packageObjects, analyzer.typerFactory)
    phasesSet --= oldScs
    phasesSet ++= newScs
  }

[tek]

maybe it would be reasonable to PR scala to add a better hook

[tribbloid]

Eventually we'll have to do this (just like your last PR for 2.13.6), and remove the reflective initializer after the AnalyzerPlugin interface stablize.

But this will take time, and patching it up in the plugin (and let other start using it immediately) could be a convincing first step, and may accelerate the process

[tribbloid]

OK I've figure out how to do this. Just pushed the latest change to divergingImplicit/dev1. This is the output for all 3 cases:

newSource1.scala:12: error: implicit error;
!I e: C

f invalid because
!I c: C
[Diverging implicit] trying to match an equal or similar (but more complex) type in the same search tree
――f invalid because
  !I c: C
  [Diverging implicit] trying to match an equal or similar (but more complex) type in the same search tree
    implicitly[C]
              ^

newSource1.scala:17: error: implicit error;
!I e: C

g invalid because
!I d: D
[Diverging implicit] trying to match an equal or similar (but more complex) type in the same search tree
――f invalid because
  !I c: C
――――g invalid because
    !I d: D
    [Diverging implicit] trying to match an equal or similar (but more complex) type in the same search tree
    implicitly[C]
              ^

newSource1.scala:16: error: implicit error;
!I e: C :: D

Diverging.f invalid because
!I ii: Int :: C :: D
――Diverging.f invalid because
  !I ii: Int :: Int :: C :: D
  Diverging implicit: trying to match an equal or similar (but more complex) type in the same search tree
    implicitly[C :: D]
              ^

I'll try to sort out other issue of 1.0.0 refactoring first, need to get all tests working on CI

[tek]

awesome, impressive work!

[tribbloid]

Integrated (with shaking hands tho, some problem will definitely pop up later).

Closing