Skip to content

Latest commit

 

History

History
289 lines (238 loc) · 11.2 KB

3. Type-Safe Dictionaries and Matching.md

File metadata and controls

289 lines (238 loc) · 11.2 KB
Raw

Type-Safe Dictionaries and Matching

Intention

We would like to implement a form of dictionary (or map) that is immutable and remembers all the types of it's initialized values.
There is something very similar currently in Scala 3: the Selectable trait with Refinement types, but there are a couple of issues:

  1. The selectable trait lacks an implementation and it helps only with the access of values
  2. When you create a Selectable implementation, you have to cast each created object to a refinement matching it's internal map
  3. There is no type inference when creating them, you would have to declare all types each time
  4. The syntax for creating key-value Selectables involves one of two ways, none of which resemble the syntax of refinement types:
    a) A list of tuples akin to obj("key" -> value)
    b) A dynamic object with an applyDynamicNamed resulting in obj(key = value)

We could make our own Dict type whose creation resembles refinement type declarations

Example

This is how we want our client code to look like:

// mike is automatically type-inferred by the macro as Dict { val name: String, val age: Int, val likesMacros: Boolean } 
val mike = Dict {
  val name = "Mike"
  val age = 28
  val likesMacros = true
}

println(mike.name) // Works fine, type resolves to String
println(mike.wallet) // Error at compile-time, mike has no 'wallet', it is known

// Notice how this type's declaration resembles the variable mike's initialization almost perfectly
type Programmer = Dict {
  val name: String
  val age: Int
  val likesMacros: Boolean
}

val mikeProgrammer: Programmer = mike // Works

type OfficeBuilding = Dict {
  val address: String
  val stories: Int
}

val mikeOfficeBuilding: OfficeBuilding = mike // Error at compile-time, mike doesn't have the fields of an OfficeBuilding, it is known

And here is to show that the Metals extension for VS Code recognizes our macro's inferred type: Image And that accessing also knows the type Image

Pretty cool right? If you didn't know, you would have thought this is default language syntax (but it's not, let's see how to make it happen)

Implementation

Good to know beforehand:

Could be a good idea to look over the previous examples in this repo

The Selectable trait in Scala 3 and how it works, Link to documentation

Most entities in a Quotes context have unapply methods that make matching very easy

Structure of entities used in this example: The ValDef resembles ValDef(name: String, tpt: TypeTree, rhs: Option[Term], is a type of Definition where:

  • name is the name of the declared variable
  • tpt is the TypeTree of the declaration, TypeTree can be turned into a TypeRepr with tpt.tpe
  • rhs is the right-hand side term of the declaration, if it is an abstract val, this is None

The Refinement TypeRepr resembles Refinement(parent: TypeRepr, name: String, info: TypeRepr) where:

  • parent is the predecesor of this type, Refinement types act like a linked list, each refinement object represents only one val definition and it's type, to have a refinement of multiple definitions, you need to nest them using the parent field, the last refinement should point to a base TypeRepr
  • name is the name of this refinement's val definition
  • info is the type representation of this refinement's val definition

The Type type is a Quotes-agnostic type that represents type-level entities like String or List[Int] or "Hello" | "World".
You can obtain these by accessing (tpe: TypeRepr).asType and you can use them in injected expressions by doing a match on them:

val typeReprOfString = TypeRepr.of[String] // This is an example, but this could be gotten from reflection, unknown here
val myExpr = typeReprOfString.asType match {
  case '[myType] => ${
    summon[myType]
    val list = List.empty[myType]
    // ...etc, it is a type-level name in here, the match is exhaustive
  }
}

Here is how our macro and friends will look like, for explanations, scroll down:

Dict.scala:

final class Dict private(val unsafeRawMap: Map[String, ?]) extends Selectable {
  // Must be transparent and must have inline for the key parameter
  transparent inline def selectDynamic(inline key: String) =
    unsafeRawMap(key)
}

object Dict {
  def fromUnsafeMap(map: Map[String, ?]): Dict =
    new Dict(map)

  // Must be transparent and have an inline Unit block
  transparent inline def apply(inline block: => Unit) =
    DictMacross.buildFromBlock(block)
}

DictMacros.scala:

import quoted.*

object DictMacross {
  transparent inline def buildFromBlock(inline block: => Unit): Dict =
    ${ buildFromBlockImpl('block) }

  def buildFromBlockImpl(block: Expr[Unit])(using Quotes): Expr[Dict] = {
    import quotes.reflect.*

    def getTypedKeysAndValues(list: List[Statement]): List[(String, TypeTree, Term)] = {
      list match {
        case Nil =>
          Nil
        case ValDef(name, typeTree, Some(term)) :: tail =>
          (name, typeTree, term) :: getTypedKeysAndValues(tail)
        case wrongHead :: tail =>
          report.errorAndAbort(s"All statements in a Dict initializer must be initialized val definitions. Found: ${wrongHead.show}")
      }
    }

    val info = block.asTerm.underlying match {
      case Block(statements, _) =>
        getTypedKeysAndValues(statements)
      case _ => {
        report.errorAndAbort("Parameter must be a block with only val definitions and no return")
      }
    }

    val dictType = info
      .foldLeft(TypeRepr.of[Dict])
      .apply { case (acc, (name, tpt, _)) =>
        Refinement(
          parent = acc,
          name = name,
          info = tpt.tpe
        )
      }

    val exprTuples = info
      .map { case (name, _, term) =>
          '{
            (${Expr(name)}, ${term.asExpr})
          }
      }


    dictType.asType match {
      case '[fullDictType] =>
        '{ Dict.fromUnsafeMap(${Expr.ofList(exprTuples)}.toMap).asInstanceOf[Dict & fullDictType] }
    }
  }
}

Explanations:

Dict.scala:

// Our Selectable implementation class, it has a raw map of it's objects and a private constructor
final class Dict private(val unsafeRawMap: Map[String, ?]) extends Selectable {
  // Must be transparent and must have inline for the key parameter
  // This method will be called as `selectDynamic("thing")` when we use `myDict.thing`
  transparent inline def selectDynamic(inline key: String) =
    unsafeRawMap(key)
}

object Dict {
  // Our creation function must be exposed for macros to use it
  def fromUnsafeMap(map: Map[String, ?]): Dict =
    new Dict(map)

  // Must be transparent and have an inline Unit block
  // This function's parameter is a simple Unit block {...}, we will read it's statements one by one in the macro
  transparent inline def apply(inline block: => Unit) =
    DictMacross.buildFromBlock(block)
}

DictMacros.scala:

import quoted.*

object DictMacross {
  transparent inline def buildFromBlock(inline block: => Unit): Dict =
    ${ buildFromBlockImpl('block) }

  def buildFromBlockImpl(block: Expr[Unit])(using Quotes): Expr[Dict] = {
    import quotes.reflect.*

    // Utility function, given the list of Statements in our Block
    // We extract only the statements that are ValDefs, recursively
    // Yes, this could have been a tailrec function, but I like classic recursion better
    // And if you make a type of 10,000 fields, stack overflows are the least of your concerns :')
    def getTypedKeysAndValues(list: List[Statement]): List[(String, TypeTree, Term)] = {
      list match {
        case Nil =>
          // Base case, empty to empty
          Nil
        case ValDef(name, typeTree, Some(term)) :: tail =>
          // General case, ValDef builds as head yields a tuple added to the recursive list of the tail
          (name, typeTree, term) :: getTypedKeysAndValues(tail)
        case wrongHead :: tail =>
          // If at any point we find a statement that is not a ValDef, report the error and abort
          report.errorAndAbort(s"All statements in a Dict initializer must be initialized val definitions. Found: ${wrongHead.show}")
      }
    }

    // block is an Expr[Unit] right now, so to read its contents, we use asTerm to turn it into a Term
    // term.underlying lets us access the Term's core defintion, setting aside any synthetic wrappers such as Inlined or Ident
    val info = block.asTerm.underlying match {
      case Block(statements, _) =>
        getTypedKeysAndValues(statements)
      case _ => {
        report.errorAndAbort("Parameter must be a block with only val definitions and no return")
      }
    }

    // Here, we build the final result type artificially, we will cast our final result to this
    // Casting in macros is usually a good idea if you know for certain the result type will make sense
    // and issue compile-time errors otherwise
    val dictType = info
      .foldLeft(TypeRepr.of[Dict]) // The base type of our refinement
      .apply { case (acc, (name, tpt, _)) =>
        // For each of our found ValDef types, we build yet another Refinement type wrapping the old one
        Refinement(
          parent = acc,
          name = name,
          info = tpt.tpe
        )
      }

    // Here, we build the tuples that will end up in our Dict's runtime Map
    // Just a Map[String, ?] built through expressions
    // More info on Expr splices in previous examples in this repo
    val exprTuples = info
      .map { case (name, _, term) =>
          '{
            (${Expr(name)}, ${term.asExpr})
          }
      }


    // Here, we use the match case on the computed Type of our Dict so we can cast it inside the Expr
    // While the everything else is done at compile-time, the transformation from List to Map is done at runtime
    // And the casting as well is done at runtime (but considering that refinement types are erased, this is fine)
    dictType.asType match {
      case '[fullDictType] =>
        '{ Dict.fromUnsafeMap(${Expr.ofList(exprTuples)}.toMap).asInstanceOf[Dict & fullDictType] }
    }
  }
}

Conclusion

We have made a way to build Dicts that know what they contain at compile-time. This technically allows us to write Scala code like it was Typescript, with dynamically declared types and object initialization resembling type declarations, but with type safety because the compiler always keeps tracks of our "dynamic types"; is that a good idea? your call.

Extra

This is how you would do Dict merging:

extension [D1 <: Dict, D2 <: Dict](first: D1) def ++ (second: D2) =
    Dict.fromUnsafeMap(first.unsafeRawMap ++ second.unsafeRawMap).asInstanceOf[D1 & D2]

It essentially allows you to do:

val personInfo = Dict {
  val name = "Joy"
  val age = 31
}

val programmerInfo = Dict {
  val yearsOfExperience = 7
  val favoriteLanguage = "Scala"
}

val joyTheProgrammer = personInfo ++ programmerInfo

println(joyTheProgrammer.age)
println(joyTheProgrammer.yearsOfExperience)
println(joyTheProgrammer.netWorth) // ==> Compiletime Error, no such field