Thursday, July 23, 2009

DevForce Predicate Builder

One in the “DevForce is the Shiznit” series of boastful posts about our product in which I describe a cool feature that may even interest those who have yet to discover the wonders of DevForce.

The time comes when you want to construct a LINQ “Where” clause programmatically. It should be easy. It turns out to be more challenging … until you use the DevForce PredicateBuilder.

The DevForce PredicateBuilder shares a common purpose and name with the Albahari brothers’ PredicateBuilder described here and here. I would be remiss if I failed to note their good work and inspiration. I’ll cover important differences in our solutions towards the end of this post.

February 2011 Update:

Much has happened since this post was written. PredicateBuilder has been joined by a number of related components such as PredicateDescription and SortDescription. Learn more at the DevForce Resource Center (DRC).

Intersoft is also introducing their UXGridView as I write. UXGridView can be bound to their QueryDescriptor component in the ViewModel that brings QBE functionality to the grid. The QueryDescriptor is backed by a DevForce "Data Provider" that uses these features. Bill Gower wrote a tutorial about it.

Imagine a product search interface. The user can enter words in a “Name Search” text box. Your program should find and display every product that contains any of the words entered by the user. You don’t know how many words the user might enter. What do you do?

The solution would be easy if you knew the user would enter exactly one word.

Let’s illustrate with the Northwind database. Assume “Manager” is some apparatus for producing an IQueryable object tied to some persistence apparatus; when we call ToList on the query object, the apparatus uses the query to fetch data from the database.

var word = "Sir";
var q = Manager.Products
.Where(p => p.ProductName.Contains(word));
var results = q.ToList();// returns 3 products

Of course you don’t know how many words the user will enter. You want to be prepared for more than one so you write this too-simple helper method that returns an array of words from the text entered in the text box:

private IEnumerable<String> GetWords(string phrase) {
return phrase.Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
}

Now all you have to do is replace the “Where” clause with a sequence of OR clauses. You’ll want to construct it by iterating over the words. Go ahead and write it. I’ll wait.

Having trouble? I’ll give you the user’s input: “Sir Cajun Louisiana”. Did that help?

You will probably come up with the following:

var q = Manager.Products
.Where(p =>
p.ProductName.Contains("Sir")
p.ProductName.Contains("Cajun")
p.ProductName.Contains("Louisiana")
);

var results = q.ToList(); // returns 6 products

This is ultimately what the lambda expression must look like.

Of course you cannot demand that the user enter exactly three words any more than you can insist she enter exactly one. You want to construct the lambda dynamically based on the actual number of words entered. Sadly there is no obvious way of constructing a lambda expression dynamically.

The DevForce PredicateBuilder can help you build predicates dynamically.

What’s a “predicate”?

A “predicate” is a function that examines some input and returns true or false.

The code fragment, “p => p.ProductName.Contains(“Sir”)” , is a predicate that examines a product and returns true if the product’s ProductName contains the “Sir” string.

The CLR type of the predicate in our example is:

Func<Product, bool>

Which we can generalize to:

Func<T, bool>

We almost have what we want. When the compiler sees an example of this kind of thing it immediately resolves it into an anonymous delegate. We don’t want the delegate. We need a representation that retains our intent and postpones the resolution into a delegate until the last possible moment. We need an expression tree that we can analyze and morph if necessary. We want a Predicate Expression

Expression<Func<Product, bool>>

This is exactly what the DevForce “Where” extension method demands.

public static IEntityQuery<T> Where<TSource>(
this IEntityQuery<T> source1, Expression<Func<T,bool>> predicate)

The methods of the static PredicateBuilder class combine two or more Predicate Expressions into a single Predicate Expression that we can pass to this “Where” method.

Let’s stick with the example and see one of those methods in action. Let’s write a little method to produce an IEnumerable of Predicate Expressions, one expression for each of given word.

private IEnumerable<Expression<Func<Product, bool>>> ProductNameTests(
IEnumerable<String> words) {
foreach (var each in words) {
var word = each;
yield return p => p.ProductName.Contains(word);
}
}

The result is an IEnumerable of Predicate Expressions about the Product entity. The body is an iterator that returns a Predicate Expression for each word. The expression is exactly the same as the first predicate we wrote when we knew only one word.

If we give it the three-word input in our example, we’ll get an IEnumerable of three Predicate Expressions, each looking for one of the words in the product’s ProductName.

We want to OR these Predicate Expressions together so we will use this static method of PredicateBuilder:

public static Expression<Func<T, bool>>Or<T>(
params Expression<Func<T, bool>>[] expressions)

You see it takes an array (a params array to be precise) of Predicate Expressions. We will convert the output of our ProductNameTests into an array before giving it to this PredicateBuilder method. The final code looks like so:

var words = GetWords("Sir Cajun Louisiana");
var tests = ProductNameTests(words).ToArray();
if (0 == tests.Length) return;
var productNamePredicate = PredicateBuilder.Or(tests);
var q = Manager.Products.Where(productNamePredicate);
var results = q.ToList(); // returns 6 products

In plain language:

  • Split the user’s search text into separate words

  • Generate an array of Predicate Expressions that look for each word in the ProductName

  • Skip the query if there are no clauses … because there are no words

  • Ask “PredicateBuilder.Or” to combine the tests into a single Predicate Expression

  • Run it to get results.

Other PredicateBuilder Methods


There are 6 interesting methods.
MethodSyntax by example
Orp1.Or(p2)
OrPredicateBuilder.Or(p1, p2, p3 .. pn)
Andp1.And(p2)
AndPredicateBuilder.And(p1, p2, p3 .. pn)
TruePredicateBuilder.True()
FalsePredicateBuilder.False()

“p” = Predicate Expression.

All expressions must be of the same type (e.g., Product).

Examples:

Expression<Func<Product, bool>> p1, p2, p3, p4, bigP;

// Sample predicate expressions

p1 = p => p.ProductName.Contains("Sir");

p2 = p => p.ProductName.Contains("Cajun");

p3 = p => p.ProductName.Contains("Louisiana");

p4 = p => p.UnitPrice > 20;

bigP = p1.Or(p2); // Name contains "Sir" or "Cajun"

// Name contains any of the 3
bigP = p1.Or(p2).Or(p3);

bigP = PredicateBuilder.Or(p1, p2, p3); // Name contains any of the 3

bigP = PredicateBuilder.Or(tests); // OR together some tests

bigP = p1.And(p4); // "Sir" and price > 20

// Name contains "Cajun" and "Lousiana" and the price > 20

bigP = PredicateBuilder.And(p2, p3, p4);

bigP = PredicateBuilder.And(tests); // AND together some tests

// Name contains either “Sir” or “Louisiana” AND price > 20
bigP = p1.Or(p3).And(p4);

bigP = PredicateBuilder.True<Product>().And(p1);// same as p1

bigP = PredicateBuilder.False<Product>().Or(p1);// same as p1

// Not useful

bigP = PredicateBuilder.True<Product>().Or(p1);// always true

bigP = PredicateBuilder.False<Product>().And(p1);// always false

Observations

Notice that one each of the OR and the AND methods are Predicate Expression extension methods; they make it easier to compose predicates at number of Predicate Expressions known at design time.

Put a breakpoint on any of the “bigP” lines and ask the debugger to show you the result as a string. Here is the Immediate Window output for “bigP = p1.Or(p3).And(p4);”

{p => ((p.ProductName.Contains("Sir")   p.ProductName.Contains("Louisiana")) &&
(p.UnitPrice > Convert(20)))}

The True and False methods return Predicate Expression constants that help you jumpstart your chaining of PredicateBuilder expressions. Two of the combinations are not useful.

Compared to Albahari Brothers’ Predicate Builder

The Albahari brothers covered similar ground with their PredicateBuilder described here. Why duplicate their work?

Actually, we are not. We would have been happy to use their PredicateBuilder (which is open source) … if it worked in Silverlight. But it doesn’t. Moreover, it relies on a peculiar trick that adds mystery with no apparent benefit.

Why doesn’t it work in Silverlight? Because their implementation depends upon private reflection … which is forbidden in Silverlight.

Why do they require private reflection? Because they postpone resolution of the modified Expression tree until the query is resolved. In order to “lazily resolve” the expression tree, they have to carry unresolved expressions around inside the modified trees. The only way to do this is if the inner, unresolved expressions are closures … and closures are private.

The DevForce Predicate Builder resolves combined expressions immediately. Write “p1.Or(p2)” and you immediately get back the new expression

 p => p.ProductName.Contains(“Sir”)  p.ProductName.Contains(“Cajun”)

With the Albahari Predicate Builder you’d get something sort of like:

 p => p1.Invoke(p)   p.ProductName.Contains(“Cajun”)

“p1” is the closure I’m talking about.

Which brings me to the other apparent strangeness here. What is “Invoke” doing in there? I don’t want to call “invoke” … ever.

Don’t worry. “Invoke” is never actually called. “Invoke” is a placeholder in the expression tree. The Albahari’s have hijacked the “Invoke” method and are using it as a marker that means “when you finally resolve this expression, replace the invoke with the mini-expression inside the closure ‘p1’.”

They have also cleverly hooked their own expression “pre-compiler” into the expression object so that, when something tries to use this LINQ expression, this “pre-compiler” gets to fix up all the “Invoke” markers before that something get its chance to evaluate the expression.

Bet you didn’t know you could do that. It’s a good example of the Chain of Responsibility pattern.

I don’t want to go any deeper than this. You can learn more by reading up on their LinqKit and you can see where they discovered how to do it from Tomas Petricek.

I am only going this far so I can explain that

  1. They are postponing Expression tree resolution until the LINQ query is actually consumed
  2. The trick to doing so is to embed a closure of the left expression in the new Expression tree and mark it with an “Invoke” method
  3. The ultimate resolution of the LINQ query requires penetrating that closure
  4. Closures are private so you can’t penetrate them in Silverlight
  5. Therefore we can’t use their PredicateBuilder to dynamically construct LINQ in SIlverlight

Thankfully, the DevForce PredicateBuilder resolves these dynamically constructed LINQ expressions immediately so there is never an embedded closure. Nor does it need to hijack the “Invoke” method as a marker.

Importantly, there is no loss of expressiveness, performance, or capability by immediate resolution. I have no idea why they introduced this complication. The closures and “Invokes” add unnecessary mystery in my opinion … without apparent benefit.

To be clear, you still can use their PredicateBuilder to dynamically construct LINQ queries in .NET code. Their PredicateBuilder works fine with DevForce LINQ queries in regular .NET … as long as you remember to use AsExpandable (as you would for a dynamically composed Entity Framework LINQ query).

I prefer to use the DevForce version in both .NET and Silverlight myself.

13 comments:

Eric De C# said...

Very nice work, but in you last example with you r PredicateBuilder you still have to know exactly how many predicate to build.

How can you combine your PredicateBuilder with an array of words?

Ward Bell said...

Thanks Eric. I'm afraid I don't understand your question nor to which example you refer.

Although I do know in some of these examples, there is no intrinsic need to know the number of predicates in advance.

Hope that is reassuring.

Shloma Baum said...

Hi Ward,

Great post, as always.

Just one question, in your post you know the property name you look to filter 'ProductName', what if we don't know the prop name at design, it is usually supplied by the client at run-time, in this case do you still have the ability to use the Predicate Builder?

TIA
Shloma

Jaideep said...

a very nice article, certainly more useful than the predicatebuilder from albahari's.
but i did not see any code download link of your predicate builder. is it available in some other location?

Ward Bell said...

@Jaideep - The PredicateBuilder I describe is part of our DevForce product and is not independently available at this time.

@Shloma - Excellent use case. The PredicateBuilder only accepts expression trees.

We could provide a component for the purpose, one that constructed a predicate expression from a string property name ("ProductName"), an operation name ("Contains"), and parameter ("Cajun") ... but I don't see us venturing there any time soon.

Better, I think, for you to learn how to construct your expression dynamically. That's surprisingly easy to learn and not nearly as difficult as figuring out how to insert it into another expression as our PredicateBuilder does.

Ward Bell said...

@Shloma - This just in! In our next release 5.2.2 we have added PredicateDescription which enables the scenario you requested.

One of the pertinent signatures takes objectType, propertyName, operation, and value ... returns a predicate ready for your Where clause.

It seems we need this for ourselves too.

Unknown said...

Awesome post! Is the DevForce Predicate Builder something we can use in the free version of DevForce for Silverlight? Any chance the source might be published under a permissive license?

Jesse Kindwall said...

Maybe I'm missing something, but I'm not seeing what's so special about this PredicateBuilder class. Can you please explain how it is superior in these examples to something like this:

Predicate<Product> productFinder = p => false;

foreach (string searchTerm in searchTerms)
{
Predicate<Product> oldFinder = productFinder;
productFinder = new Predicate<Product>(p => oldFinder(p) || p.ProductName.Contains(searchTerm));
}

var results = Manager.Products.Where(productFinder);

Ward Bell said...

@Jesse - Have you tried your proposal? When you do you will see that it does not compile.

Predicate<Product> is a delegate equivalent to Func<Product, bool>. The Where clause in a DevForce query requires Expression<Func<Product, bool>>. Not the same thing at all.

The distinction between an expression and a delegate is crucial. A delegate is compiled CLR code; an expression is a description of code. That difference shows up in the two basic LINQ definitions: one extends IEnumerable<T> with methods that take delegate parameters; the other extends IQueryable<T> with methods that take expression parameters.

LINQ to Objects concerns local CLR objects. We can apply delegates to such objects so it implements extensions to IEnumerable. We can even compile delegates within delegates as you do in your "For" loop. Your approach might work if you were querying objects in memory.

But you're not. You're querying objects stored in a database, not held locally in memory.

We can't apply delegates to remote data source objects. Our local delegates don't make sense "over there". We can't even express them "over there". Instead, we have to use a flavor of LINQ that extends IQueryable.

IQueryable implementations - such as LINQ to EF or to DevForce or most any data source) - translate the code described in expressions (ultimately) into commands (e.g., SQL) that make sense to the remote data source.

Any LINQ book will explain this more clearly and in greater detail than I can here.

Anonymous said...

I'd expect the PredicateBuilder I describe here to work with Silverlight (and the source is available for anyone to use). Please let me know if it doesn't, though.

Ward Bell said...

@Anonymous - Let's be clear ... you are referring to YOUR "PredicateBuilder", not the DevForce PredicateBuilder.

I think it's great that developers have options. That said, we should strive to avoid obvious - perhaps misleading - ambiguity in our communications.

Pete Montgomery said...

Hi Ward, what is the ambiguity..? Pete.

Ward Bell said...

@pete - the ambiguity is this.

DevForce has a class called PredicateBuilder which is the subject of this post.

Your link refers to a PredicateBuilder class that you define in your blog post.

I don't want readers to confuse the DevForce PredicateBuilder with Pete's PredicateBuilder (nor with the Albahari PredicateBuilder either).