Thursday, February 12, 2009 3:50 AM bart

Help! Drowning in Expression Trees, What Now?

Introduction

Once more I found myself in LINQ providers land recently for a project yet unannounced. Given the relative poverty of the query language we’re targeting in that particular provider, a very common question came up: what about complex expressions in predicates? Let me give you an example:

from p in products where p.Price > 100 select p

is a pretty innocent query, right? But what about:

from p in products where EnterUnknownTerritory(p.Price * Math.PI / 4) == 26 select p

That’s the totally opposite side of the spectrum, where we can’t translate the query anymore because the “EnterUnknownTerritory” method is definitely not known in the target language. So, take a look at something “in the center”, not quite trivial but by no means impossible:

from p in products where p.Price > minPrice select p

where minPrice is a variable. You might say this is as innocent as the original query, but in fact quite some stuff is going on here. Remember that LINQ queries are composed of chains of method calls each of which represent a query operator. In the sample above that boils down to:

products.Where(p => p.Price > minPrice)

The argument to the Where method is a lambda expression that captures an outer variable, so you end up with a closure and minPrice becomes a field access on the closure class. Here’s an illustration of this behavior:

image

So, MemberExpressions are lurking around every corner, sometime a little unexpectedly. Another sample of user-induced complication of expression trees (most likely well-intentioned anyway) is the following:

from p in products where p.Price > 100 && someThingLocal.Equals(alsoLocal) select p

where whole parts of the expression tree can be evaluated locally, meaning the above query can be simplified by applying the rules of Boolean logic after partial evaluation of the local portions.

 

Approach #1 – Foreign nodes

So, how to tackle this “issue”? As part of any expression tree translator (whether it’s LINQ or something else) you’ll turn the source tree into some target tree, resembling the abstract syntax of the target domain. Typically this is carried out by some kind of expression tree visitor that recursively “visits” the tree, translating nodes and putting them together. For example, you might recognize a BinaryExpression with NodeType set to ExpressionType.AndAlso and turn it into an AndPredicate:

public BinaryPredicate VisitAndAlso(BinaryExpression andAlso)
{
    return Predicate.AndAlso(Visit(andAlso.Left), Visit(andAlso.Right));
}

Here Visit is the top-level method that can take in an arbitrary (System.Linq-based) expression, and we’re turning everything into Predicate objects, our destination universe. The top-level method will look much like:

public Predicate Visit(Expression ex)
{
    switch (ex.NodeType)
    {
        case ExpressionType.AndAlso:
            return VisitAndAlso((BinaryExpression)ex);
        …
    }
}

Obviously you’ll add much more cases to the Visit method, and likely you’ll merge implementations for various binary operations that share a common implementation (recurse, construct, return). That said, at some point you’ll end up with things you don’t know about. Let’s use method calls as a sample. Maybe a method call itself is still of interest (in a sense it can be turned into a target-side equivalent), like:

  • p.Name.Equals(“Chai”)
  • String.Equals(p.Name, “Chai”)
  • p.Price.CompareTo(100)

but at some level, inevitably, you’ll end up with lots of unknowns, like (assuming the methods invoked below don’t have a target-side equivalent):

  • EnterUnknownTerritory(p.Price * Math.PI / 4)
  • p.Name.Normalize()

Outside the domain of method calls, similar unknowns can exist. Maybe the target language can’t cope with a Boolean Not, or with a simple numerical addition. Either way, you’re drowning in expression trees at that point, and the subtree you’re stuck at becomes an “unknown” to you.

Now two things can happen: either the unknown expression tree node has a dependency on a target-side thing (brought in scope through abstraction, i.e. lambda parameters), or it’s completely defined source-side (in the C#/VB local execution domain). The samples above fall under the former category because of the occurrence of “p” in the expression subtree.

During the first visit over the tree, you could (and maybe should) decide not to investigate the unknown territory yet, and invent some pseudo-node in the target domain AST that represents something “Foreign”:

return Predicate.Foreign(ex);

On a subsequent phase in the compiler, you’d decide whether or not you can evaluate the expression (some kind of partial evaluation of the entire expression) locally. If so, it gets substituted by a constant node (containing the result of source-side evaluation); if not, an exception occurs (like NotSupportedException). How to figure out whether you can do local evaluation or not? Detect whether or not foreign expression contains (again recursively by some visitor) references to the lambda parameter representing the input to the predicate clause (i.e. representing the target-side entity, e.g. a database row or entity).

The evaluation itself can be done in two ways:

  • A complete expression tree interpreter: quite a bit of work.
  • Some trick, like wrapping the remaining expression in a lambda expression, using the Compile method on it and invoke the resulting delegate, like this:

    object result = Expression.Lambda(foreignEx).Compile().DynamicInvoke();

    Note this could actually be used to figure out the foreign expression is lambda parameter free, because an InvalidOperationException will result from the Compile method if this is not the case. (Question for the reader: is the premise of requiring a foreign expression to be completely lambda-parameter-free valid?)

 

Approach #2 – Avoid the problem altogether

How’s that for a solution? If the target domain is sufficiently poor with a relatively little number of operators and such, you could try to avoid general expression trees altogether. But how? Let’s stick with query predicates (the where clause body) for our discussion to simplify matters a bit. Remember my post titled Who ever said LINQ predicates need to be Boolean-valued? from last year? That’s precisely the thing we’re going to leverage here. Instead of assigning the predicate lambda to an Expression<Func<T, bool>>, let’s “assign it” to a Func<T, Predicate>. Sounds awkward? Not really, if the way to build up the Predicate instance (which is already in a pretty good shape to be turned into the final destination language, as it reflects the AST of the target language quite accurately already) is user-friendly enough.

What do I mean with that? Well, you most certainly don’t want the user to write the following:

from p in products where Predicate.AndAlso(Predicate.LessThan(p.Price, 100), …) select p

but it would just work fine (for reasons outlined in my Who ever said LINQ predicates need to be Boolean-valued? post). However, let’s look at the problem step-by-step, inside-out. What’s up with that p.Price thing? How can we still know all the metadata about that guy? Remember, what we’re defining above in a hidden way is a simple lambda expression of type Func<Product, Predicate>:

p => Predicate.AndAlso(Predicate.LessThan(p.Price, 100), …)

That is, give it a Product instance and it will give you back a Predicate instance. But we won’t have Product instances till we’ve executed the query, and to execute the query we need to have the predicate first. Err, something’s not quite right yet as we’re turning in circles. The crux is in the use of p.Price somewhere deep inside the lambda expression (in fact, every reference to p is where the snake bites its own tail). We clearly want to have IntelliSense on every p. (“p dot”) showing all the properties on the entity we can use in our predicate. But on the other hand, executing the lambda with some Product instance, we don’t want to traverse the “dot” into the Price property above, as we need to capture the fact we’re putting a condition on the price of the product.

 

Columns and values

So, that’s where things get a little tricky. What about making the Price property something that behaves just like a decimal (assuming that’s the type we want) – well, possibly in a restricted way, see further – but still knows its own identity (i.e. it’s a representation of an underlying field/column/attribute/… with the name “Price”). Actually, here we already have an opportunity to control what the user can do with the field. Maybe the target-side doesn’t support, say, addition. So, we want to disallow that (statically). It should be clear by now that p.Price should have a type different from a “raw” decimal. It represents a column, that carries an identity, and can be instantiated at some time to become a value. Let’s ignore the latter part for now and just focus on the “column has a name” part (enough to formulate a query expression). Here’s a proposal:

class Column
{
    internal Column(string name)
    {
        Name = name;
    }

    public string Name { get; private set; }

    public NullCheck HasValue
    {
        get
        {
            return new NullCheck(this, false);
        }
    }

    public override string ToString()
    {
        return "[" + Name + "]";
    }
}

The class above acts as the base class for any column. As our target domain is “nullable” regardless of the data type (i.e. not discrepancies in nullability based on reference or value type taxonomies), we also provide a HasValue property here, which returns something that acts like a Boolean but captures semantics for use in query translation. Let’s come back to that in a few moments, but dive into the Column subclass for decimal columns first:

sealed class Number : Column
{
    internal Number(string name)
        : base(name)
    {
    }

    public Comparison Equals(NumberValue value)
    {
        return Comparison.Equal(this, value);
    }

    public static Comparison operator <(Number a, NumberValue b)
    {
        return Comparison.LessThan(a, b);
    }

    public static Comparison operator <(NumberValue a, Number b)
    {
        return Comparison.GreaterThan(b, a);
    }
    …
}

Again, here we have an opportunity to be different. In the above, I’m mimicking the target domain already in that I’m stepping away from the CLR types into target types. For example, here we talk about Number instead of Decimal (maybe because the target domain only has one numerical format). But notice how the operator overloads (I’ve omitted the opposite ones, which are identical in nature) don’t return Booleans but Comparison objects. Again, wait a moment for a peek at the Comparison type. First we need to talk about the difference between Number and NumberValue. NumberValue is the source-side representation of a constant number, e.g. in our sample query the “100” we’re comparing to would be a NumberValue. That’s where the two worlds meet: in writing a query, you simply use literals in your source language of choice, but NumberValue allows us to transition to the target domain smoothly:

sealed class NumberValue : Value
{
    private NumberValue(decimal value)
    {
        Value = value;
    }

    internal decimal Value { get; private set; }

    public override string ToString()
    {
        return Value.ToString();
    }

    public static implicit operator NumberValue(decimal x)
    {
        return new NumberValue(x);
    }
    …
}

Value is a trivial empty base class (just to have a base class in places where we need it to make our code as generic as possible). The only way to construct a NumberValue is by an implicit operator that (and that’s where things are seamless) “lifts” the CLR value into our domain-specific representation. Notice you could perfectly have additional such conversions that allow you to take in other numerical types, causing them to be normalized to the common type the target language knows about.

 

Comparisons

Now we know about the leaf nodes of the predicate trees, namely columns and values, we can turn to their parents. Predicates are based on conditions, that can be of various kind. Relational operators, null checks, string matching, etc are a few samples of such possibilities. What about the LessThan comparison?

class Comparison : Predicate
{
    internal Comparison(PredicateType type, Column column, Value value)
        : base(type)
    {
        Column = column;
        Value = value;
    }

    internal Column Column { get; private set; }
    internal Value Value { get; private set; }

    public override string ToString()
    {
        string op = null;

        switch (Type)
        {
            case PredicateType.LessThan:
                op = "<";
                break;
… } return Column.ToString() + " " + op + " " + (Value == null ? "null" : Value.ToString()); } public static Comparison LessThan(Column column, Value value) { if (column == null) throw new ArgumentNullException("column"); if (value == null) throw new NotSupportedException("Cannot apply comparison operator with a null value argument."); return new Comparison(PredicateType.LessThan, column, value); } …
}

Obviously, you can envision much more such factory methods. The key here is that all of those comparisons represent (part of) a predicate (see further) but are purely a representation instead of something executable locally. I.e. writing p.Price > 100 will result in a Comparison object with Column set to the Number(Column) pointing a the “Price” column, and Value set to a NumberValue carrying the decimal value of 100. We’ve just created a domain-specific representation of the essential building blocks of predicates.

Our NullCheck we met earlier is built in a very similar way, although it only refers to a column (it’s a unary operator so to speak):

class NullCheck : Comparison
{
    internal NullCheck(Column column, bool isNull)
        : base(isNull ? PredicateType.IsNull : PredicateType.IsNotNull, column, null)
    {
        IsNull = isNull;
    }

    internal bool IsNull { get; private set; }

    public static NullCheck operator !(NullCheck check)
    {
        return new NullCheck(check.Column, !check.IsNull);
    }

    public override string ToString()
    {
        return base.ToString();
    }
}

Notice we just play the rules of Booleans, and you can negate a null-check to get a not-null—check. Dead easy.

Actually there’s a special type of column that needs special treatment: Boolean columns (like p.IsInStock) can be used as a condition straight away (i.e. leaving off the == true comparison). That means a Boolean column should be implicitly convertible into a Condition:

sealed class Boolean : Column
{
    internal Boolean(string name)
        : base(name)
    {
    }

    public static Comparison operator !(Boolean a)
    {
        return Comparison.Equal(a, new BooleanValue(false));
    }

    public static implicit operator Comparison(Boolean a)
    {
        return Comparison.Equal(a, new BooleanValue(true));
    }
    …
}

Again I’ve omitted a bunch of operator overloads (like ==, !=) that are quite predictable.

 

Predicates

Finally the predicates themselves. Comparisons already are predicates, hence their base class being Predicate. However, predicates need to be combinable using Boolean operators, so we need a bit of plumbing there as well:

class Predicate
{
    internal Predicate(PredicateType type)
    {
        Type = type;
    }

    public PredicateType Type { get; private set; }

    public static Predicate operator &(Predicate a, Predicate b)
    {
        return new BinaryPredicate(PredicateType.And, a, b);
    }

    public static Predicate operator |(Predicate a, Predicate b)
    {
        return new BinaryPredicate(PredicateType.Or, a, b);
    }

    public static Predicate operator !(Predicate a)
    {
        return new UnaryPredicate(PredicateType.Not, a);
    }

    public static bool operator false(Predicate a)
    {
        // Used by operator && (7.11.2)
        // x && y --> T.false(x) ? x : T.&(x,y)
        return false;
    }

    public static bool operator true(Predicate a)
    {
        // Used by operator || (7.11.2)
        // x || y --> T.true(x) ? x : T.|(x,y)
        return false;
    }
}

The interesting thing here is that the operators && and || are not overloadable by themselves. The C# specification, section 7.11, details how short-circuiting operators && and || are defined in terms of more basic building blocks: &, |, true and false. So, we play a trick above: by defining operator overloads for true and false (you can think of those as “has value true” and “has value false” checks), we can force the overloads for & and | to be called at all times, eliminating short-circuiting behavior. Here’s a sample:

p.Name == “Chai” && p.Price < 100

Both sides of the && are Comparison objects, which have an overload for the & operator, in addition to the false operator (the || case is defined symmetrically in terms of | and true), so the expression above turns into:

Comparison left = p.Name == “Chai”;
Predicate.false(left) ? left : left & (p.Price < 100);

By returns “false” from the “false” call (I know, it gets abstract), we always end up in the bold part of the conditional expression above, forcing the & operator overload to be called (so, we’re in control again). And actually, it’s not much of a trick after all: by returning “false” from both the “false” and “true” operators, we actually say: “we don’t know yet whether this thing is true or false, please be pessimistic and don’t try to short-circuit this evaluation” (in a sneaky way mumbling to ourselves: “and we’ll do the rest, as you’ll blindly call us on either & or |”).

Now it should be clear that Boolean operators “just work” based on the operator overloads above. The UnaryPredicate returned from ! is straightforward, and so is the BinaryPredicate on & and |, so let’s show just one of the two:

class BinaryPredicate : Predicate
{
    public BinaryPredicate(PredicateType type, Predicate left, Predicate right)
        : base(type)
    {
        Left = left;
        Right = right;
    }

    internal Predicate Left { get; private set; }
    internal Predicate Right { get; private set; }

    public override string ToString()
    {
        string op = null;

        switch (Type)
        {
            case PredicateType.And:
                op = "and";
                break;
            case PredicateType.Or:
                op = "or";
                break;
        }

        return "(" + Left.ToString() + " " + op + " " + Right.ToString() + ")";
    }
}

No surprises here. So ultimately, the expression p.Name == “Chai” && p.Price < 100 results in a Predicate instance that carries all the semantics of the predicate and that can be translated (by means of a visitor over our AST representation) into the target domain. Here’s the PredicateType enum that illustrates the breadth of the predicate expressiveness:

enum PredicateType
{
    LessThan,
    LessThanOrEqual,
    GreaterThan,
    GreaterThanOrEqual,
    Equal,
    NotEqual,
    IsNull,
    IsNotNull,
    StartsWith,
    EndsWith,
    Contains,
    Matches,
    And,
    Or,
    Not,
}

 

Entities

We have all the materials to be successful in building up a Predicate given an entity object, like Person. Remaining question is how to write such an entity type in a straightforward way, given that the properties need to be subtypes of the Column class (like Number, (our own) Boolean, etc). Here’s a naive attempt:

class Product
{
    public String Name { get { return new String("productName"); } }
    public Number Price { get { return new Number("unitPrice"); } }
}

Brr, that’s by no means a nice representation. We’re stating the obvious a number of times: Name is a String (again, one of our subclasses of Column, maybe it should be called StringColumn after all, oh well), referring to a column with name “productName”. Same deal for Price. Lots of boilerplate here just to be able to write queries against a container of such objects. Ideally, we’d be able to write something like:

class Product
{
    [Column("productName")]
    public String Name { get; private set; } }

    [Column("unitPrice")]
    public Number Price { get; private set; } }
}

Question is how we can magically populate those properties. There are lots of tricks to do this; I’ll illustrate one below. But first, the model above doesn’t allow us to use the same type for the results of the query (we have no place to stick values). In the typical LINQ providers world, that’s a problem. In more exotic scenarios, we might just want to use LINQ to formulate a query, send it to a server and get some kind of visualization of the results back other than raw data. If the latter is the case (as it turned out to be for the problem this blog post is inspired by), this restriction is not a problem. However, even if we’d have to write a “classic” LINQ provider that allows users to return data, you could hack up a solution that looks like this. Maybe I’ll cover that another time as it’s quite an elegant approach to the problem.

Back to reality: being able to formulate the query requires us to populate the entity object instance with “good” values for its column properties. How did we get here? Well, we don’t have a mechanism anymore that can capture things like p.Name (without causing client-side evaluation). I say “anymore” because we’ve given up expression trees which exactly have that power. In order to populate the properties on the entity type, we could sacrifice the inheritance hierarchy and require the user to derive from some base class called Entity. Again, if we’re just interested in formulating a query, the entity object doesn’t have to do much more than act as a client-side metadata-container in the local type system, so this restriction shouldn’t be a stumble block:

class Product : Entity
{
    [Column("productName")]
    public String Name { get { return new String("Name"); } }

    [Column("unitPrice")]
    public Number Price { get { return new Number("Price"); } }
}

Now, what does the ColumnAttribute (used for mapping purposes) look like?

[AttributeUsage(AttributeTargets.Property, Inherited = false, AllowMultiple = false)]
sealed class ColumnAttribute : Attribute
{
    readonly string name;

    public ColumnAttribute(string name)
    {
        this.name = name;
    }

    public string Name
    {
        get { return name; }
    }
}

Given this, the role of the Entity base class will be to reflect upon the entity object itself, resolve the mapping attributes, new up column objects (like Number, String, etc), carrying the column they refer to:

sealed class Number : Column
{
    internal Number(string name)
        : base(name)
    {
    }

Here’s a possible simple implementation of the Entity constructor:

class Entity
{
    public Entity()
    {
        foreach (var prop in this.GetType().GetProperties())
        {
            var mapping = prop.GetCustomAttributes(typeof(ColumnAttribute), false).Cast<ColumnAttribute>().SingleOrDefault();
            if (mapping != null)
            {
                var column = prop.PropertyType.GetConstructor(BindingFlags.Instance | BindingFlags.NonPublic, null, new Type[] { typeof(string) }, null).Invoke(new object[] { mapping.Name });
                prop.SetValue(this, column, null);
            }
        }
    }
}

Nothing more than some reflection voodoo to find all the properties, corresponding mappings, private property setters and invoke the constructor for the column type required, passing in the column mapping value. “Cooperative instantiation” if you really want to hear a fancy word that summarizes it all :-).

 

The result

Let’s write a query and see how all of this works in concert. To be able to write such a query I’m going to provide a dummy implementation of a Source<T>, in order to allow the query expression pattern to work:

class Source<T> where T : new()
{
    private Predicate _predicate;

    public Source<T> Where(Func<T, Predicate> where)
    {
        _predicate = where(new T());
        return this;
    }
}

Now we can target this source with a LINQ query as follows:

var res = from p in new Source<Product>() where p.Price > 100 && p.Name == "Chai" select p;

Notice how all the operator overloads do their thing:

image 

The user can’t tell the difference with a regular query (i.e. against CLR types) but can’t fall off the ship either now: no exotic methods will be allowed in the expression if they don’t participate in the typing for the Predicate, Comparison, etc. Obviously, you can still substitute parts of the expression by local values (that can be retrieved by doing whatever you wish) but the other way around – trying to use the entity column references like p.Price and p.Name – won’t work:

image 

From an operation point of view, how did we manage to get the Predicate instance that represents the whole where clause? Take a look at the Where method definition:

public Source<T> Where(Func<T, Predicate> where)
{
    _predicate = where(new T());
    return this;
}

The only thing to realize here is that T, which is substituted for Product in the sample, is not a concrete instance of the entity type, but merely a metadata container as discussed before. In a bottom-up fashion, our query above translates into a Predicate as follows:

  • new T() gives us a new Product object, where the base constructor takes care of resolving the column mappings
  • calling the “where” delegate (which refers to the lambda expression from the query expression) will evaluate like this:
    • p.Price becomes a Number, as instantiated by the constructor trick above and pointing at the unitPrice column;
    • p.Price > 100 causes the 100 to become a NumberValue (through the implicit conversion), and the comparison becomes a Comparison through the > operator overload;
    • similar things happen for p.Name == “Chai”;
    • the two Comparison objects are combined through the & operator overload (together with the “false” operator trick), this produces a Predicate instance;
    • we’re done…

Under the debugger, the result looks like this (thanks to the ToString implementation):

image

Ah, I like it!

 

Download

You can find the code of this blog post here. All usual warnings apply: no quality assurance was carried out, use at your own risk, and blahblah.

 

Cheers!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# Dew Drop - February 12, 2009 | Alvin Ashcraft's Morning Dew

Thursday, February 12, 2009 6:42 AM by Dew Drop - February 12, 2009 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - February 12, 2009 | Alvin Ashcraft's Morning Dew

# Reflective Perspective - Chris Alcock &raquo; The Morning Brew #286

Pingback from  Reflective Perspective - Chris Alcock  &raquo; The Morning Brew #286

# My Linq2Oracle (1) : Where | Dogs &amp; Mice

Tuesday, July 09, 2013 7:17 AM by My Linq2Oracle (1) : Where | Dogs & Mice

Pingback from  My Linq2Oracle (1) : Where | Dogs &amp; Mice

# My Linq2Oracle (1) : Where | Dogs &amp; Mice

Tuesday, July 09, 2013 7:17 AM by My Linq2Oracle (1) : Where | Dogs & Mice

Pingback from  My Linq2Oracle (1) : Where | Dogs &amp; Mice