Scala implicits

2022-06-22

Implicit Conversions

Scala allows implicit conversions between values. While this can be done for the sake of convenience, the most common usage is to extend the functionality of other types. An example of this automatic conversion is scala.collection.immutable.StringOps, with the implicit conversion method existing in scala.Predef. This implicit conversion allows Scala's additional String methods to be used, even though Scala's strings are otherwise java.lang.Strings.

Scala will do an automatic conversion in one of two situations:

  1. An expression e is of type S, but type T is required, or
  2. There is an expression e.m where S does not have an attribute or method named m, but T does.

In these cases, if Scala can find an implicit value with a signature of S => T in the current scope, it will automatically insert an invocation of it on e.

Only one conversion will be done: even if there are implicit conversions from S => T and T => U, Scala will not implicitly convert a value of type S to U.

Example 1

case class Meters(distance: Double)
case class Feet(distance: Double)

implicit def feet2meters(feet: Feet): Meters =
    Meters(feet.distance / 3.28084)

def printHeight(height: Meters) =
    println(s"You are ${height.distance} meters tall")

// Because printHeight expects Meters instead of Feet,
// Scala will automatically convert this to
//   printHeight(feet2meters(Feet(6)))
printHeight(Feet(6))

Example 2

class StudlyCaps(val value: String) {
    def studlyCaps: String = value.grouped(2).map(_.toLowerCase.capitalize).mkString
}

implicit def autoStudlycaps(s: String): StudlyCaps = new StudlyCaps(s)
// Because String has no studlyCaps method (or property),
// but StudlyCaps does, Scala will convert this to
//   autoStudlycaps("Hello world").studlyCaps
"Hello world".studlyCaps

Implicit classes

To reduce the boilerplate of writing classes like StudlyCaps from the example above, SIP-13 introduced implicit classes. Using the implicit keyword on a class will automatically generate an implicit conversion function with the same name as the class. That is,

implicit class StudlyCaps(val value: String) {
    def studlyCaps: String = value.grouped(2).map(_.toLowerCase.capitalize).mkString
}

becomes

class StudlyCaps(val value: String) {
    def studlyCaps: String = value.grouped(2).map(_.toLowerCase.capitalize).mkString
}
implicit def StudlyCaps(value: String): StudlyCaps = new StudlyCaps(value)

Because the implicit def is generated alongside the class, and with the same name, some restrictions apply:

  1. Because defs are not allowed as top-level items in a Scala module, the implicit def must be defined inside of a trait, object or class.
  2. Because the implicit def shares the same name as the class, the class cannot be a case class: the case class's companion object's name would conflict with the generated def.

Additionally, the class's constructor is allowed only one non-implicit parameter in the first parameter list, and remaining parameter lists must be implicit.

Implicit parameters and typeclasses

Scala functions and methods can take implicit parameters. If an explicit value isn't provided, Scala will search (at compile time) for an implicit value of the appropriate type to pass automatically. Scala will search twice for implicit values: first for values that can be used without qualification (e.g. foo, but not Bar.foo), and then on various companion objects. If on either step there are multiple possible implicit values, compilation fails due to the ambiguity.

Where does Scala search for implicit values?

Immediate scope

import scala.concurrent.Future
// Provides an implicit execution context
import scala.concurrent.ExecutionContext.Implicits.global

case class Meters(distance: Double)

case class Person(name: String)

object Demonstration {
    
    implicit val height = Meters(1.9)
    // This never gets used because it's always shadowed
    // by another implicit val of type Person
    implicit val person = Person("Doug")
    
    def sayHello(implicit person: Person) = {
        println(s"Hello, ${person.name}")
        // Uses the implicit height defined in this object
        printHeight
        // Uses the implicit person from the parameter list
        sayGoodbye
    }

    def sayGoodbye(implicit person: Person) =
        println(s"Goodbye, ${person.name}")

    def printHeight(implicit height: Meters) = println(s"You are ${height.distance} meters tall")

    def main(args: Array[String]) = {
        implicit val person = Person("Mark")
        // Uses the implicit value defined above
        sayHello
        // Uses the execution context we imported at the top of the module
        Future {
            println("Runs using an implicit execution context")
        }
    }
}

Companion objects

// A vastly simplified implementation of the implicit search algorithm used by scalac
// Step 1. Get all local implicits, chained by expanding scope
// Step 2. Filter it for shadowed elements
// Step 3. Find the most specific implicit val
// Step 4. Check that there are no ambiguities

// These are real typedefs from the Scala codebase
type Infos = List[ImplicitInfo]
type Infoss = List[Infos]
type InfoMap = mutable.LinkedHashMap[Symbol, Infos]
class ImplicitSearch(context: Context, targetType: Type) {
    // Search candidates for implicit values with compatible types
    // For local searches, candidates are listed from closest definition out
    def eligible(candidates: Infoss, localContext: bool): List[ImplicitInfo] = {
        val seen = new java.util.HashSet()
        for {
            infos <- candidates
            info <- infos
            // If we're in a local context, try adding the name to our set of 'seen' names
            // The method will return false if the name already exists, indicating that we've
            // seen the name already in a narrower scope, and so this definition is shadowed
            // If we're not searching the local context, then there's no need to bother with
            // tracking which names we've seen
            if !localContext || seen.add(info.name)
            if matchesType(info.typ, targetType)
        } yield info
    }

    private def getClassParts(typ: Type, infoMap: InfoMap) = typ match {
        case TypeRef(prefix, symbol, args) =>
            // The real code is more complex, and accounts for symbols being accessible via multiple prefixes
            if !infoMap.contains(symbol) {
                // Might return placeholder value if no companion object, but will always return *something*
                val companion = getCompanionSymbol(symbol)
                // Add all implicits from companion object to the infomap
                infoMap(symbol) = companion.implicitMembers.map(_.toImplicitInfo)
                // Populate infomap with values from parent types and prefix
                typ.baseTypeSeq.forEach(superTyp => getParts(superTyp, infoMap))
                getParts(pre, infoMap)
            }
        case _ => throw new MatchError(typ)
    }
    // This is simplified to omit tracking which types we've seen to avoid accidental cycles (and wasted work),
    // as well as tracking which types we're aware of, but haven't gotten around to processing yet.
    private def getParts(typ: Type, infoMap: InfoMap) = typ match {
        case TypeRef(prefix, symbol, args) =>
            if (symbol.isClass) {
                // If our type is Foo[S, T] then this will find all the implicits on Foo...
                getClassParts(typ, infoMap)
                // and then we do the same for S and T
                args.foreach(getParts)
            } else if (sym.isTypeAlias) {
                // Expand the type alias
                getParts(tp.normalize)
            } else if (sym.isAbstractType) {
                // If we have T <: SuperType, then check SuperType for implicits
                getParts(typ.upperBound)
                // Just like when this is a concrete type, recurse into the type parameters
                args.foreach(getParts)
                // If our type is S#U, then run getParts on S
                getParts(prefix)
            }
        case _ => // Omitting a bunch of other things a type expression can be, e.g. an annotated type expression, or a singleton type
            // Most of them boil down to "find all the actual named types, and pass them into getParts
    }

    @tailrec def rankImplicits(infoss: Infoss, acc: List[(SearchResult, ImplicitInfo)]): List[(SearchResult, ImplicitInfo)] {
        infoss match {
            case Nil => acc
            case first :: rest =>
                // When we built the eligible list, we filtered based on the target type, but didn't sketch out the precise
                // set of substitutions necessary to make things match: that is, it was a generous filter.
                // This is where we try to make the actual types match. This could fail for two reasons.
                // The first reason is simple: there isn't actually a set of substitutions to make things work.
                // The second reason is that there's a cyclic definition, and that our search for a set of substitutions
                // will 'diverge'.
                val searchResult = typedImplicit(first)
                if (searchResult.isDivergent) {
                    // And log errors, etc.
                    Nil
                } else (searchResult.isFailure) {
                    // Skip this one and carry on
                    rankImplicits(rest, acc)
                } else {
                    // Remove from the set of remaining candidates any that are less specific than `first`
                    // I.e. if first is `TypeClass[SubType]` and `candidate` is `TypeClass[SuperType]`, the latter will be filtered out
                    val filteredRest = rest.filterNot(candidate => first == candidate || improves(first, candidate))
                    // Because of that step, `first` is at least as good as everything we've accumulated in `acc`, so is our new best candidate
                    rankImplicits(filteredRest, (searchResult, first) :: acc)
                }
        }
    }

    def findBest(candidates: Infoss, localContext: Bool): SearchResult = {
        rankImplicits(candidates, Nil) match {
            case Nil => SearchFailure
            case (bestResult, bestInfo) :: rest =>
                // We know by construction that bestResult/bestInfo must be no worse than any that came before, but it's possible that there was a tie
                // Check against that now, and throw an exception if one was found
                if (rest.exists { case (_, otherInfo) => !improves(bestInfo, otherInfo) }) {
                    throw new AmbiguousImplicitException()
                }
                bestResult
        }
    }

    def getCompanionImplicits: Infoss = {
        targetType match {
            case TypeRef(prefix, symbol, args) =>

        }
    }
}


// Given a concrete type (i.e. all type parameters have been filled),
// and the signature of the desired implicit value,
// returns all candidate implicit values.
def findImplicits(t: Type, sig: Signature): List[ImplicitDef] = {
    val companionImplicits = t.companionObject.toList.flatMap { companion => 
        companion.attibutes.filter(attr => attr.signature == sig)
    }
    val typeParamImplicits = t.typeParameters.flatMap { typeParam =>
        findImplicits(typeParam, sig)
    }
    val superImplicits = t.superType.toList.flatMap { superType =>
        findImplicits(superType, sig)
    }
    companionImplicits ++ typeParamImplicits ++ superImplicits
}