Using the "Prolog in Scala" to find available type class instances

Question

Considering https://speakerdeck.com/folone/theres-a-prolog-in-your-scala, I would like to "abuse" the Scala type system to find all instances of e.g. CanBuildFrom that match a given criteria. Prolog style, I would evaluate something in the lines of the following pseudocode:

can_build_from(Src, int, list[int])
Src = somecollectiontype1[int]
Src = somecollectiontype2[int]
... etc

i.e. the runtime would look up all the values for Src that satisfy the statement can_build_from(Src, int, list[int]).

Now, I'm aware that the primitive constraint/logic programming environment, which the Scala implicit lookup system is, isn't meant to be used for such tricks and is not able to "return" more than one found value for Src out of the box, so my question is: is there a "magic trick" to make it work so that somehow I'd get all the possible values for X in CanBuildFrom[X, Int, List[Int]]?

Additional example:

trait CanFoo[T, U]

implicit val canFooIntString  = new CanFoo[Int,     String] {}
implicit val canFooDblString  = new CanFoo[Double,  String] {}
implicit val canFooBoolString = new CanFoo[Boolean, String] {}
implicit val canFooIntSym     = new CanFoo[Int,     Symbol] {}
implicit val canFooDblSym     = new CanFoo[Double,  Symbol] {}
implicit val canFooBoolSym    = new CanFoo[Boolean, Symbol] {}

now I'd like to query CanFoo[X, String] and get back X ∈ [Int, Double, Boolean], or CanFoo[Int, X] and get back X ∈ [String, Symbol].

Alternatively, CanFoo[X, String] would return List(canFooIntString, canFooDblString, canFooBoolString), i.e. all instances of CanFoo that match.

Answer 1

This can be done (at least in some cases) with compiler internals

import scala.language.experimental.macros
import scala.reflect.internal.util
import scala.reflect.macros.{blackbox, contexts}

object Macros {

  def allImplicits[A]: List[String] = macro impl[A]

  def impl[A: c.WeakTypeTag](c: blackbox.Context): c.Tree = {
    import c.universe._

    val context = c.asInstanceOf[contexts.Context]
    val global: context.universe.type = context.universe
    val analyzer: global.analyzer.type = global.analyzer
    val callsiteContext = context.callsiteTyper.context

    val tpA = weakTypeOf[A]

    val search = new analyzer.ImplicitSearch(
      tree = EmptyTree.asInstanceOf[global.Tree],
      pt = tpA.asInstanceOf[global.Type],
      isView = false,
      context0 = callsiteContext.makeImplicit(reportAmbiguousErrors = false),
      pos0 = c.enclosingPosition.asInstanceOf[util.Position]
    )

    q"${search.allImplicits.map(_.tree.symbol.toString).distinct}"
  }
}

allImplicits[CanFoo[_, String]]
// List(value canFooBoolString, value canFooDblString, value canFooIntString)

Tested in 2.13.0.

---

Still working in 2.13.10.

Scala 3 implementation is similar

import dotty.tools.dotc.typer.{Implicits => dottyImplicits}
import scala.quoted.{Expr, Quotes, Type, quotes}

inline def allImplicits[A]: List[String] = ${impl[A]}

def impl[A: Type](using Quotes): Expr[List[String]] = {
  import quotes.reflect.*
  given c: dotty.tools.dotc.core.Contexts.Context =
    quotes.asInstanceOf[scala.quoted.runtime.impl.QuotesImpl].ctx

  val typer = c.typer

  val search = new typer.ImplicitSearch(
    TypeRepr.of[A].asInstanceOf[dotty.tools.dotc.core.Types.Type],
    dotty.tools.dotc.ast.tpd.EmptyTree,
    Position.ofMacroExpansion.asInstanceOf[dotty.tools.dotc.util.SourcePosition].span
  )

  def eligible(contextual: Boolean): List[dottyImplicits.Candidate] =
    if contextual then
      if c.gadt.isNarrowing then
        dotty.tools.dotc.core.Contexts.withoutMode(dotty.tools.dotc.core.Mode.ImplicitsEnabled) {
          c.implicits.uncachedEligible(search.wildProto)
        }
      else c.implicits.eligible(search.wildProto)
    else search.implicitScope(search.wildProto).eligible


  def implicits(contextual: Boolean): List[dottyImplicits.SearchResult] =
    eligible(contextual).map(search.tryImplicit(_, contextual))

  val contextualImplicits = implicits(true)
  val nonContextualImplicits = implicits(false)
  val contextualSymbols = contextualImplicits.map(_.tree.symbol)
  val filteredNonContextual = nonContextualImplicits.filterNot(sr => contextualSymbols.contains(sr.tree.symbol))

  val implicitStrs = (contextualImplicits ++ filteredNonContextual).collect {
    case success: dottyImplicits.SearchSuccess => success.tree.asInstanceOf[ImplicitSearchSuccess].tree.show
  }

  Expr(implicitStrs)
}

trait CanFoo[T, U]

object CanFoo {
  given canFooIntString: CanFoo[Int, String] with {}
  given canFooDblString: CanFoo[Double, String] with {}
  given canFooBoolString: CanFoo[Boolean, String] with {}
  given canFooIntSym: CanFoo[Int, Symbol] with {}
  given canFooDblSym: CanFoo[Double, Symbol] with {}
  given canFooBoolSym: CanFoo[Boolean, Symbol] with {}
}

allImplicits[CanFoo[_, String]] 
//"CanFoo.canFooIntString", "CanFoo.canFooBoolString", "CanFoo.canFooDblString"

Scala 3.2.0.