Type-Level Computations with Functional Dependencies

It has been a long time since my last blog post about ScalaQuery, and in the meantime I have announced new features in my Twitter stream and in the release notes but now I need some more space to explain a refactoring I have been working on which should eventually lead to ScalaQuery 0.10.

Recap

In ScalaQuery 0.9, there is a simple relationship between the types of queries and the types of values they return: A Query[ColumnBase[T]] selects values of type T, so e.g. calling .list on such a query gives you a List[T]. You can create Query objects of types other than ColumnBase[T] forSome { type T } but the implicit conversion to a StatementInvoker (which allows you to call methods such as .list) is not available for them.

Let’s look at the different subtypes of ColumnBase that we can use in queries. First of all, all tables extend ColumnBase, so that Table[T] <: ColumnBase[T].

  object MyTable extends Table[(Int, String, String)]("MY_TABLE") {
    def a = column[Int]("A")
    def b = column[String]("B")
    def c = column[String]("C")
    def * = a ~ b ~ c
  }

  val q1 = Query(MyTable)
  // q1: Query[MyTable]
  val res1 = q1.list
  // res1: List[(Int, String, String)]

And, as implied by the name ColumnBase, Column[T] <: ColumnBase[T], so we can query for individual columns:

  val q2 = for {
    t <- MyTable // automatically lifted to a Query
  } yield t.a
  // q2: Query[Column[Int]]
  val res2 = q2.list
  // res2: List[Int]

So what about selecting multiple columns? The most natural notation would be the same as when you’re querying a Scala collection instead of a database:

  val q3 = for {
    t <- MyTable
  } yield (t.a, t.b)
  // q3: Query[(Column[Int], Column[String])]

But this won’t work. We get a Query[(ColumnBase[A], ColumnBase[B])] but what we need is a Query[ColumnBase[(A, B)]] — wrapped in the opposite order! This ColumnBase[Tuple2[A,B]] is called a Projection2[A,B] in ScalaQuery (actually, a Projection2[A,B] is both a ColumnBase[(A,B)] and a (Column[A], Column[B])). You construct it with the ~ operator:

  val q3b = for {
    t <- MyTable
  } yield t.a ~ t.b
  // q3b: Query[Projection2[Int, String]]
  val res3 = q3b.list
  // res3: List[(Int, String)]

Type-Level Transformation

For the sake of simplicity, instead of the implicit conversions and Invokers we will assume a method list() which takes a Query and returns a list of the results. At the moment, it would look like this:

  def list[T](q: Query[ColumnBase[T]]): List[T]

We need to generalize it to:

  def list[T, U](q: Query[T]): List[U]

where U is a transformed version of T, which we will write as T =>> U. So what kinds of transformations do we need? The existing functionality is covered by:

  ColumnBase[T] =>> T

For tuples, as used in q3, we need another rule:

  (T1, T2) =>> (U1, U2) where T1 =>> U1 and T2 =>> U2

Actually, we need one of those for all arities from 2 to 22:

  (T1, T2, T3) =>> (U1, U2, U3) where T1 =>> U1 and T2 =>> U2 and T3 =>> U3
  ...and so on

Note that these rules are recursive. They enable the transformation of arbitrarily nested tuples.

Just one more rule before we’re done: ScalaQuery’s Projection classes can only wrap Columns, so any primitive value is lifted implicitly:

  t.a ~ t.b ~ 42
  // : Projection3[Int, String, Int]
  //   == (Column[Int], Column[String], Column[Int])

If we allow the use of Tuples instead of Projections, we do not get this implicit lifting anymore, so we need to allow primitive values, too:

  T =>> T where a TypeMapper[T] is available

We can use functional dependencies to have the Scala compiler do the required transformation by turning =>> into a trait, every “where” condition into an implicit parameter, and every rule into an implicit method:

  trait =>> [-T, U]

  implicit def unpackColumnBase[T]: ColumnBase[T] =>> T = null
  implicit def unpackTuple2[T1, T2, U2, U2](implicit u1: T1 =>> U1, u2: T2 =>> U2): (T1, T2) =>> (U1, U2) = null
  ...
  implicit def unpack[T : TypeMapper]: T =>> T = null

In order to avoid ambiguities, we need to prioritize the implicits. We also add a nice error message in case a bad query type is used:

  @implicitNotFound(msg = "Don't know how to unpack ${T} (to ${U})")
  trait =>> [-T, U]

  object =>> extends LowPriority_=>> {
    implicit def unpackColumnBase[T]: ColumnBase[T] =>> T = null
  }

  trait LowPriority_=>> {
    implicit def unpackTuple2[T1, T2, U2, U2](implicit u1: T1 =>> U1, u2: T2 =>> U2): (T1, T2) =>> (U1, U2) = null
    ...
    implicit def unpack[T : TypeMapper]: T =>> T = null
  }

And finally, the list() method gets an implicit parameter to compute the U type.

  def list[T, U](q: Query[T])(implicit u: T =>> U): List[U]

That’s it, basically. We can now call list() with a Query of any nesting of tuples and columns and it will remove all ColumnBase type constructors for the result type. We still need to extract a value of the right type from the query result at run-time. That can be done with a method in an implementation of =>> in a straight-forward way. For the purpose of computing the type at compile-time, the implementation does not matter, so we just used null above.

Another Transformation

There’s still a catch though. Take a look at the following queries:

  val q4a = for {
    a ~ b ~ c <- MyTable.where(_.a === 1).map(t => t.a ~ t.b ~ 4) unionAll
                 MyTable.where(_.a === 2).map(t => t.a ~ t.b ~ 5)
  } yield a ~ b ~ (c*2)

  val q4b = for {
    (a, b, c) <- MyTable.where(_.a === 1).map(t => (t.a, t.b, 4)) unionAll
                 MyTable.where(_.a === 2).map(t => (t.a, t.b, 5))
  } yield a ~ b ~ (c*2)

A unionAll operation takes multiple Queries of the same type and produces another Query of that type which represents their union. The values that come out of this operation need to encode the union as a ScalaQuery AST node. In q4a (old style), this value has the type Projection3[Int, String, Int] which is (Column[Int], Column[String], Column[Int]). The literal values 4 and 5 have been lifted to ConstColumns and the union operation can be properly encoded into the three resulting Columns.

In q4b (new style), the unionAll produces a (Column[String], Column[Int], Int) tuple and we have no way of encoding the union operation into the Int value! To solve this problem, union operations need to return a different type than that of their operands: One where all primitive values have been lifted to Columns, i.e. the opposite of the =>> transformation:

  @implicitNotFound(msg = "Don't know how to reify ${Packed} (to ${Reified})")
  sealed trait Reify[-Packed, Reified]

  object Reify extends ReifyLowPriority {
    implicit final def reifyColumnBase[T <: ColumnBase[_]]: Reify[T, T] = null
  }

  trait ReifyLowPriority {
    implicit final def reifyPrimitive[T](implicit tm: TypeMapper[T]): Reify[T, ConstColumn[T]] = null
    implicit final def reifyTuple2[T1,T2, U1,U2, R1,R2](implicit u1: Reify[T1, R1], u2: Reify[T2, R2]): Reify[(T1,T2), (R1,R2)] = null
    ...
  }

Limitations

The actual reification at run-time is done in =>>, so it is essential that the =>> and Reify implementation match. It would be nicer to encode the reification directly in =>> but this fails due to a limitation in Scala’s type inferencer. Compare the unpacking and reification for ColumnBase:

  implicit def unpackColumnBase[T]: ColumnBase[T] =>> T
  implicit final def reifyColumnBase[T <: ColumnBase[_]]: Reify[T, T]

In both cases, we get a type like A <: ColumnBase[B] but one operation has to capture the A and the other one the B (we need the actual sub-type of ColumnBase for the reification to preserve table types). There is no way (that I know of) of doing both together. Exposing the type parameter through a type alias in ColumnBase does not help. It allows us to write the unpacking in the desired style but T#Alias is always inferred as Any:

  implicit def unpackColumnBase[T <: ColumnBase[_]]: T =>> T#Alias

A second problem is caused by Scala issue SI-3346: Fundep implicits do not work on implicit conversions. I have been able to work around this in some cases but in others the situation looks hopeless. As long is this issue is not resolved, some extra methods calls for explicit unpacking might be needed.

You can find the work in progress in ScalaQuery’s nested-tuples-query2 branch.