Dynamically Creating LINQ Expression Predicates From a String

I'm working on a WPF application that has an explorer like interface, where the left side (the TreeView) controls what is displayed on the right side (DataGrid). The small prototype used typed DataSets, but now that I'm implementing the application, I'm using ObservableCollections<TArg> of data model objects. One part of the prototype used the DataView.RowFilter property to control the display in the grid by filtering the results from the master collection, something like this:

_dataView.RowFilter = "FoobarCategory = '1'";

The RowFilter could be one of many properties of the object collection and there really wasn't a way to predict which of the properties would be used singly or in combination. To get this similar functionality form my ObservableCollection<TArg>, I was looking at having to use Linq and write some kind of giant predicate that knew what every expression would be and provide a filter that I'd need for the display.

This isn't the first time I've needed to be able to filter a collection at runtime without knowing what the filter might be. So, after playing around for a while I decided to try and get the same sort of functionality in Linq as the Filter property of DataView.

In a nutshell, here's what I want to be able to do:

foreach (var o in myCollection.Filter("FoobarCategory = 1")) {
    // Do something
}

It's worth mentioning what I need isn't type safe and code refactoring, which I do a lot of, needs to be cognizant of that these filters potentially exist; however, used sparingly this serves a useful purpose.

From here, the problem is really two parts, one needs to be able to parse a simple expression, and then using the parse tree, create some kind of dynamic Expression that one can then evaluate at runtime as a Predicate.

Part 1 - The Parser

The grammar was going to be something trivial like:

Expression        : SimpleExpression
                  | BooleanExpression
                  ;

BooleanExpression : BooleanExpression "OR" Expression
                  | BooleanExpression "AND" Expression
                  | "NOT" Expression
                  ;

SimpleExpression  : Keyword Operator Value
                  ; 

Operator          : = | != | > | >= | < | <=
                  ;

Keyword           : STRING
                  ;

Value             : STRING
                  | NUMBER
                  | QUOTE STRING QUOTE
                  ;

Given that grammar I wrote a small recursive decent parser to parse the input expression, checking along the way that the keywords were actually illegal for the type I was interested in, and create a parse tree. The trickiest part of the parser is dealing with quoted strings for values. When I started this parser, I thought about this interesting rant from Steve Yegge. I think I've probably written a dozen or so small language parsers that I've used in production applications, there's still something magic about the whole thing.

Part 2 - The Runtime Expression Generator

After parsing I have a simple parse tree that I can traverse to create an Expression. To explain this in a bit more detail, let's take a sample expression of "FoobarCategory = 1" and create a predicate by hand. Assume that TArg is some kind of type with FoobarCategory as a property.

ParameterExpression parameter = Expression.Parameter(typeof(TArg), "o");

var root = ParseExpression(expression);

var condition = Expression.Equal(Expression.Property("FoobarCategory"),
                                 Expression.Constant("1"));
var lambda = Expression.Lambda<Func<TArg, bool>>(condition, parameter);

var compiledLamdba = lambda.Compile();

Func<TArg, bool> predicate = compiledLamdba.Invoke;

There are methods attached to Expression that allow one to handle all of the necessary translations of the parse tree; that is, things like boolean operators like "and" and "or" as well as relational operators. When creating the predicate we do have to be careful of mixing class properties and fields as the method calls are different (i.e. Expression.Property vs Expression.Field) and we also have to be careful about handling C# nulls.

Conclusion

I've included the complete source for the builder as well as the test fixture (you'll need NUnit or change the attributes to the mstest versions). Included in the basic test fixture is an extension method that makes using this almost as easy as the Filter property of the DataView. I've decided to use C# relational operators instead of the more SQL like syntax in DataView.RowFilter. Lastly, the parser doesn't handle all of the operations that are supported in DataView.RowFilter (see DataColumn.Expression for more details about the supported syntax); however, adding those shouldn't be that big a deal if I ever need them.

Zipped VS2008 solution is here.