Pattern matching

Following from the Type-safe DSL post from last week, I am now going to show you how to use pattern matching to simplify the queries we can now construct.

Let’s review the motivation for the simplification: the DSL allows us to construct arbitrary queries and, especially when using the guards, these queries could be simplified. Take these queries:

val username = ""
val userId: Option[Long] = None

val r1 = "username" like username when username != "" || 
         id is userId
val r2 = id is 5L || id isNot 5L
val r3 = "username" like username when username != "" && 
          (id is 6L && id isNot 6L)

The restriction r1 is quite reasonable: we have some search form with the username field. If the users type in the username, then we wish to select all Users whose username is like the entered username, or select all Users if the users have left the username empty. Also, for some obscure reason, we want to filter on the identity if the userId is Some(id). Now, looking at r1‘s with the values of username and userId, it should simplify to no filter at all.
Onwards, r2 is a typical example of tautology: even though the left and right hand side of the disjunction are reasonable on their own, together, they will always be true. This query should also simplify to no filter at all.
Finally, r2 is even better (considering the work the underlying data store will have to do). The first term, "username" like username when username != "" reduces to nothing because of the guard condition; the second term, (id is 6L && id isNot 6L) reduces to contradiction; the whole query simplifies to contradiction–there is nothing to do!.

Simplifying

So, the task is to simplify these restrictions; the input is the unsimplified restriction, the output is the simplified restriction. Simple!

trait RestrictionSimplifier {
  def simplifyRestriction(r: Restriction) = r
}

All we need to do is to consider the different kinds of situations we will encounter. Let’s start with the simplest case: an In restrictions with no values, equivalent to:

val usernames = Nil

val r = "username" in usernames

Clearly, such a restriction is a contradiction; this covers the first case in our simplifier:

def simplifyRestriction(r: Restriction) = r match {
  case In(property, values) if (values.isEmpty) => Contradiction()
  case x => x
}

What other simplifications can we perform? Looking at the restrictions above, we can see that our reasoning revolves around simplifying conjunctions and disjunctions if we can determine their left and right hand sides. So, we include:

def simplifyRestriction(r: Restriction) = r match {
  case d: Disjunction => simplifyDisjunction(d)
  case c: Conjunction => simplifyConjunction(c)
  case In(property, values) if (values.isEmpty) => Contradiction()
  case x => x
}

Let’s discuss the simplifyDisjunction‘s code; simplifyConjunction is very similar–but using the conjunction rules instead!
The following table lists some of the simplifications we can make:

I’m not going to list the remaining simplification rules, in the table, the code in our trait expresses them much more clearly:

private def simplifyDisjunction(d: Disjunction): Restriction = {
  (d.lhs, d.rhs) match {
    // trivial simplifications
    case (Tautology(), Tautology()) => Tautology()
    case (Contradiction(), Contradiction()) => Contradiction()
    case (lhs, Contradiction()) => lhs
    case (Contradiction(), rhs) => rhs
    case (Tautology(), _) => Tautology()
    case (_, Tautology()) => Tautology()
    case (lhs, Skip()) => lhs
    case (Skip(), rhs) => rhs

    // equals & duplicates
    case (b@Binary(p1, op1, v1), Binary(p2, op2, v2)) 
      if p1 == p2 && v1 == v2 && op1 == op2 => b
    case (Binary(p1, '==, v1), Binary(p2, '!=, v2)) 
      if p1 == p2 && v1 == v2 => Tautology()
    case (Binary(p1, '!=, v1), Binary(p2, '==, v2)) 
      if p1 == p2 && v1 == v2 => Tautology()
    case (b@Binary(p1, '==, v1), i@In(p2, v2)) 
      if p1 == p2 && v2.contains(v1) => i
    case (i@In(p2, v2), b@Binary(p1, '==, v1)) 
      if p1 == p2 && v2.contains(v1) => i

    case (lhs, rhs) =>
      val simplerLhs = simplifyRestriction(lhs)
      val simplerRhs = simplifyRestriction(rhs)
      if (simplerLhs != lhs || simplerRhs != rhs)
        simplifyDisjunction(
          Disjunction(simplerLhs, simplerRhs))
      else
        d
  }
}

And there you have it: to simplify a restriction, we match the restriction with and decide whether it is a disjunction, conjunction, or in. If it is a disjunction or conjunction, we perform the trivial simplifications and, if no trivial simplification is possible, we suspect that the lhs or rhs is complex, so we call the simplify function recursively.

The whole gem is here:

trait RestrictionSimplifier {

  protected def simplifyRestriction(r: Restriction) = r match {
    case d: Disjunction => simplifyDisjunction(d)
    case c: Conjunction => simplifyConjunction(c)
    case In(property, values) if (values.isEmpty) => Contradiction()
    case x => x
  }
  
  private def simplifyDisjunction(d: Disjunction): Restriction = {
    (d.lhs, d.rhs) match {
      // trivial simplifications
      case (Tautology(), Tautology()) => Tautology()
      case (Contradiction(), Contradiction()) => Contradiction()
      case (lhs, Contradiction()) => lhs
      case (Contradiction(), rhs) => rhs
      case (Tautology(), _) => Tautology()
      case (_, Tautology()) => Tautology()
      case (lhs, Skip()) => lhs
      case (Skip(), rhs) => rhs

      // equals & duplicates
      case (b@Binary(p1, op1, v1), Binary(p2, op2, v2)) 
        if p1 == p2 && v1 == v2 && op1 == op2 => b
      case (Binary(p1, '==, v1), Binary(p2, '!=, v2)) 
        if p1 == p2 && v1 == v2 => Tautology()
      case (Binary(p1, '!=, v1), Binary(p2, '==, v2)) 
        if p1 == p2 && v1 == v2 => Tautology()
      case (b@Binary(p1, '==, v1), i@In(p2, v2)) 
        if p1 == p2 && v2.contains(v1) => i
      case (i@In(p2, v2), b@Binary(p1, '==, v1)) 
        if p1 == p2 && v2.contains(v1) => i

      case (lhs, rhs) =>
        val simplerLhs = simplifyRestriction(lhs)
        val simplerRhs = simplifyRestriction(rhs)
        if (simplerLhs != lhs || simplerRhs != rhs)
          simplifyDisjunction(Disjunction(simplerLhs, simplerRhs))
        else
          d
    }
  }
  
  private def simplifyConjunction(c: Conjunction): Restriction = {
    (c.lhs, c.rhs) match {
      // trivial simplifications
      case (Tautology(), Tautology()) => Tautology()
      case (Contradiction(), _) => Contradiction()
      case (_, Contradiction()) => Contradiction()
      case (Tautology(), rhs) 
        if (rhs != Conjunction) => simplifyRestriction(rhs)
      case (lhs, Tautology()) 
        if (lhs != Conjunction)=> simplifyRestriction(lhs)
      case (lhs, Skip()) => lhs
      case (Skip(), rhs) => rhs

      // equals & duplicates
      case (b@Binary(p1, op1, v1), Binary(p2, op2, v2)) 
        if p1 == p2 && v1 == v2 && op1 == op2 => b
      case (Binary(p1, '==, v1), Binary(p2, '!=, v2)) 
        if p1 == p2 && v1 == v2 => Contradiction()
      case (Binary(p1, '!=, v1), Binary(p2, '==, v2)) 
        if p1 == p2 && v1 == v2 => Contradiction()
      case (Binary(p1, '==, v1), Binary(p2, '==, v2))
        if p1 == p2 && v1 != v2 => Contradiction()
      case (Binary(p1, _, v1), IsNull(p2)) 
        if p1 == p2 => Contradiction()

      // it is a conjunction of some other restrictions
      case (lhs, rhs) =>
        val simplerLhs: Restriction = simplifyRestriction(lhs)
        val simplerRhs: Restriction = simplifyRestriction(rhs)
        if (simplerLhs != lhs || simplerRhs != rhs)
          simplifyConjunction(Conjunction(simplerLhs, simplerRhs))
        else
          c
    }
  }
  
}