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 `User`

s whose username is `like`

the entered username, or select all `User`

s 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:

LHS | RHS | LHS OR RHS |
Note |

tautology | tautology | tautology | true || true => true |

tautology | anything |
tautology | true || _ => true |

anything |
tautology | tautology | _ || true => true |

contradiction | contradiction | contradiction | false || false => false |

contradiction | x | x | false || x => x |

x | contradiction | x | x || false => x |

skip | x | x | skip || x => x |

x | skip | x | x || skip => x |

b@Binary(p, op, v) | Binary(p, op, v) | b | (id is 5) || (id is 5) => (id is 5) |

Binary(p, ‘==, v) | Binary(p, ‘!=, v) | tautology | (id is 5) || (id isNot 5) => true |

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 } } }

Cool! Thanks for sharing this.