Going Rogue, Part 2: Phantom Types

In the last post, we introduced Rogue, the type-safe DSL we implemented for writing queries against MongoDB. In this post we’ll extend QueryBuilder to support query sort ordering, while making sure we can’t build any nonsense queries like this:

Venue where (_.mayor eqs 1234) limit(10) fetch(100)

Sort ordering

Here’s how we left the QueryBuilder class:

class QueryBuilder[M <: MongoRecord[M]](
    rec: M with MongoMetaRecord[M],
    clauses: List[QueryClause[_]],
    lim: Option[Long]) {
  def where[F](clause: M => QueryClause[F]): QueryBuilder[M] =
    new QueryBuilder(rec, clause(rec) :: clauses, lim)
  def and[F](clause: M => QueryClause[F]): QueryBuilder[M] =
    new QueryBuilder(rec, clause(rec) :: clauses, lim)
  def limit(n: Long) = new QueryBulder(rec, clauses, Some(n))
  def fetch(): List[M] = ...
  def fetch(n: Long) = this.limit(n).fetch()
}

To implement sort ordering, we just need to add an order field and the orderAsc() and orderDesc() methods:

class QueryBuilder[M <: MongoRecord[M]](
    rec: M with MongoMetaRecord[M],
    clauses: List[QueryClause[_]],
    order: List[(String, Boolean)],
    lim: Option[Long]) {
  // ...
  def orderAsc[F](field: M => QueryField[M, F]): QueryBuilder[M] = {
    val newOrder = (field(rec).field.name, true) :: order
    new QueryBuilder(rec, clauses, newOrder, lim)
  }

  def orderDesc[F](field: M => QueryField[M, F]): QueryBuilder[M] = {
    val newOrder = (field(rec).field.name, false) :: order
    new QueryBuilder(rec, clauses, newOrder, lim)
  }
}

We just pass along the order fields to the query executor, and that’s it! Now we can do this:

Venue where (_.venuename startsWith “Starbucks”)
  orderDesc(_.popularity) fetch(5)

The fieldToQueryField implicit conversion we defined before does most of the work. Here it is for reference:

implicit def fieldToQueryField[M <: MongoRecord[M], F](field: Field[M, F]) =
  new QueryField[M, F](field)

Canned queries

But there’s still a problem we’d like to avoid. We’ve found it pretty convenient to write methods that construct “canned” queries. The caller can take those canned queries and further refine them by adding additional where clauses or sort orderings before calling fetch(). But consider a case like this:

def findByCategory(cat: String) =
  Venue where (_.categories contains cat) orderDesc(_.popularity)

// elsewhere ...
findByCategory(“Thai”).orderAsc(_.venuename).fetch()

The caller might not be aware that findByCategory() returns a query ordered by popularity, and tries to supply a sort ordering of its own. Instead of a query sorted on venue name, the caller gets a query sorted by popularity then venue name, which is unexpected.

Similarly, consider the case where a method returns a canned query that includes a limit() modifier:

def findMostPopular(cat: String) =
  Venue where (_.categories contains cat)
    orderDesc(_.popularity) limit(10)

// elsewhere ...
findMostPopular(“Speakeasy”).fetch(20)

It’s not clear which limit modifier should take effect — maybe the canned query method has a good reason for limiting the query, or maybe the caller knows best.

The Phantom of the Sca-laaaaaaa

Using phantom types, we can get the compiler to prevent both of these situations from happening. The idea is to declare some types that cannot be instantiated and serve no other purpose but to appear in the type parameters of another class:

abstract sealed class Ordered
abstract sealed class Unordered
abstract sealed class Limited
abstract sealed class Unlimited

First we need to add type parameters Ord and Lim to the type signature of QueryBuilder.

class QueryBuilder[M <: MongoRecord[M], Ord, Lim](
    rec: M with MongoMetaRecord[M],
    clauses: List[QueryClause[_]],
    order: List[(String, Boolean)],
    lim: Option[Long]) {
  // ...
}

Keep in mind that Ord and Lim are just type parameters, named to indicate what phantom type values they will take on in an actual instance of QueryBuilder.

Next, we need to initialize the type parameters when the builder is first created. This happens in the implicit conversion from MongoRecord to QueryBuilder:

implicit def metaRecordToQueryBuilder[M <: MongoRecord[M]]
    (rec: MongoMetaRecord[M]) =
  new QueryBuilder[M, Unordered, Unlimited](rec, Nil, Nil, None)

Then, for each method that introduces a constraint on the builder, we return a new builder instance with updated type parameters:

def limit(n: Long) =
  new QueryBulder[M, Ord, Limited](rec, clauses, Some(n))

def orderAsc[F](field: M => QueryField[M, F]): QueryBuilder[M] = {
  val newOrder = (field(rec).field.name, true) :: order
  new QueryBuilder[M, Ordered, Lim](rec, clauses, newOrder, lim)
}

def orderDesc[F](field: M => QueryField[M, F]): QueryBuilder[M] = {
  val newOrder = (field(rec).field.name, false) :: order
  new QueryBuilder[M, Ordered, Lim](rec, clauses, newOrder, lim)
}

The remaining methods leave the type parameters unchanged:

def where[F](cl: M => QueryClause[F]): QueryBuilder[M] =
  new QueryBuilder[M, Ord, Lim](rec, cl(rec) :: clauses, order, lim)

def and[F](cl: M => QueryClause[F]): QueryBuilder[M] =
  new QueryBuilder[M, Ord, Lim](rec, cl(rec) :: clauses, order, lim)

Enforcing the constraints

Now that we have the constraints set up, we need to enforce them. This is done using the =:= class, defined in scala.Predef as follows:

sealed abstract class =:=[From, To] extends (From => To)
object =:= {
  implicit def tpEquals[A]: A =:= A = new (A =:= A) {
    def apply(x: A) = x
  }
}

Basically, this sets it up so that the compiler can only generate instances of =:=[A, A]. If you make a method take an implicit argument of type =:=[A, B], you are constraining types A and B to be the same in invocations of that method. Here is how we use it in QueryBuilder:

def limit(n: Long)(implicit ev: Lim =:= Unlimited) =
  new QueryBulder[M, Ord, Limited](rec, clauses, Some(n))

def fetch(n: Long)(implicit ev: Lim =:= Unlimited) =
  this.limit(n).fetch()

def orderAsc[F](field: M => QueryField[M, F])
    (implicit ev: Ord =:= Unordered): QueryBuilder[M] = {
  val newOrder = (field(rec).field.name, true) :: order
  new QueryBuilder[M, Ordered, Lim](rec, clauses, newOrder, lim)
}

def orderDesc[F](field: M => QueryField[M, F])
    (implicit ev: Ord =:= Unordered): QueryBuilder[M] = {
  val newOrder = (field(rec).field.name, false) :: order
  new QueryBuilder[M, Ordered, Lim](rec, clauses, newOrder, lim)
}

So for instance, the compiler will be able to supply the implicit ev argument to limit() only when the type parameter Lim is the type Unlimited. When the compiler cannot supply a value for the ev argument, a compiler error will occur.

We’ve solved one problem but created another — now it is impossible to specify more than one sort ordering. We can get around this pretty easily, though, by providing two additional sort methods that require the builder to already be in the Ordered state:

def andAsc[F](field: M => QueryField[M, F])
    (implicit ev: Ord =:= Ordered): QueryBuilder[M] = {
  val newOrder = (field(rec).field.name, true) :: order
  new QueryBuilder[M, Ordered, Lim](rec, clauses, newOrder, lim)
}

def andDesc[F](field: M => QueryField[M, F])
    (implicit ev: Ord =:= Ordered): QueryBuilder[M] = {
  val newOrder = (field(rec).field.name, false) :: order
  new QueryBuilder[M, Ordered, Lim](rec, clauses, newOrder, lim)
}

This way, when a method returns a canned query that is already ordered, the caller is reminded of this fact by the need to call andAsc() instead of orderAsc():

def findByCategory(cat: String) =
  Venue where (_.categories contains cat) orderDesc(_.popularity)

findByCategory(“Thai”).andAsc(_.venuename).fetch()

For serious

Some of these constraints might seem a little contrived, but let me give you a case where constraints like this can really prevent you from doing something dangerous. We added support for modify and delete queries to Rogue; they look something like this:

Venue where (_.closed eqs false)
  orderAsc(_.popularity)
  limit(100)
  modify (_.closed setTo true)
  updateMulti()

Venue where (_.closed eqs false)
  orderAsc(_.popularity)
  limit(100)
  bulkDelete_!!()

These queries purportedly close (or delete) the 100 least popular venues. The only problem is, MongoDB does not support limits on delete and modify queries! So the limit(100) will be silently ignored. Very bad! Thankfully, we can just throw an (implicit ev: Lim =:= Unlimited) on the bulkDelete_!!() and modify() methods, and the compiler will catch this for you. Whew!

There’s a lot more we’ve built into Rogue — special operations on list and map fields, pagination, support for geospatial queries, and the ability to select only certain fields from a record, to name a few. We’re thinking about adding support for using QueryBuilders in for-comprehensions, once we figure out what kind of monad a QueryBuilder is! We’ll save that for another post though.

In the meantime, you can check out the Rogue sources on github.

Jason Liszka and Jorge Ortiz, foursquare engineers