shapeless - 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.

question from:https://stackoverflow.com/questions/26723337/using-the-prolog-in-scala-to-find-available-type-class-instances

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.