Critical Development

Language design, framework development, UI design, robotics and more.

Dynamically Composing LINQ OrderBy Clauses in Compact Framework

Posted by Dan Vanderboom on December 19, 2008

[There is a follow-up article to this which makes search properties strongly-typed.]

I’ve received several questions recently about dynamically composing LINQ queries.  Those of us who come from a SQL background and are familiar with embedding queries in strings have had it easy when it comes to composing query logic, although it has always come with a price: those queries are not strongly checked for syntax errors, the existence of members, or type agreement, and there is always SQL injection to be cautious of.

Still, faced with a scenario such as the need to customize the sort order of a query window in an application, sometimes it’s necessary to give up a little validation, or at least push it to a different part of the application.  Imagine an administrative view where a user selects a list, selects the fields to order by, in which direction (ascending or descending), and can reorder which fields are ordered first, second, and so on.  Validation could happen during that interaction.

To keep the example simple, I’ll be using a basic Customer class:

class Customer
{
    public string FirstName, LastName;

    public Customer(string FirstName, string LastName)
    {
        this.FirstName = FirstName;
        this.LastName = LastName;
    }
}

The test method will determine the preferred shape of the API.

class Program
{
    static void Main(string[] args)
    {
        IEnumerable<Customer> Customers = new Customer[] { new Customer("Dan", "Vanderboom"), new Customer("Steve", "Vanderboom"), 
            new Customer("Tracey", "Vanderboom"), new Customer("Sarah", "Barkelew") };

        // these would be run as various iterations of a loop,
        // based on some kind of configuration data
        Customers = Customers.Order("LastName", SortDirection.Ascending);
        Customers = Customers.Order("FirstName", SortDirection.Descending);

        // you can also string them together like this, if you know what they are ahead of time
        // but you'd be better off writing a normal, compiler-checked OrderBy clause, using the standard LINQ API
        //Customers = Customers.Order("LastName", SortDirection.Ascending).Order("FirstName", SortDirection.Descending);
        
        foreach (var cust in Customers)
        {
            Console.WriteLine(cust.FirstName + " " + cust.LastName);
        }

        Console.ReadKey();
    }
}

Curiously, when Customers is defined with the var keyword instead of explicitly defining it as IEnumerable<Customer>, the extension methods don’t work; but by being explicit, the Customer array type is somehow cast or converted into exposing the appropriate interface.

As you can tell from the code, the same Order extension method is called regardless of whether the collection is already ordered or not.  It seems odd that LINQ requires us to call OrderBy followed by ThenBy on all subsequent sorting, and has even more methods for ascending and descending sorts.  By combining all four Enumerable ordering methods into a single Order method, we make it much easier to loop through some kind of data to determine the qualities of the ordering clause.

I found this article on StackOverflow that manipulates expression trees, and the Dynamic LINQ Library–which is pretty nice–does the same sort of thing with some Reflection.Emit thrown in.  The problem with this is that it assumes you have support for Expressions or Reflection.Emit, which isn’t the case in Compact Framework.  So I thought I’d roll up my sleeves and see what I could do to help the poor souls stuck working with LINQ in Compact Framework.  It works for in-memory IEnumerables, but won’t work with query providers that don’t execute the OrderBy expression, but rather read the expression’s metadata to construct a query for the storage engine it was designed for (such as LINQ-to-Objects and SQL Server).

So with that caveat, if you query some data, and find it reasonable or necessary to sort it in memory, this implementation will do the trick:

public enum SortDirection
{
    Ascending, Descending
}

public static class IEnumerableOrderExtension
{
    public static IOrderedEnumerable<T> Order<T>(this IEnumerable<T> Source, string MemberName, SortDirection SortDirection)
    {
        MemberInfo mi = typeof(T).GetField(MemberName);
        if (mi == null)
            mi = typeof(T).GetProperty(MemberName);
        if (mi == null)
            throw new InvalidOperationException("Field or property '" + MemberName + "' not found");

        // get the field or property's type, and make a delegate type that takes a T and returns this member's type
        Type MemberType = mi is FieldInfo ? (mi as FieldInfo).FieldType : (mi as PropertyInfo).PropertyType;
        Type DelegateType = typeof(Func<,>).MakeGenericType(typeof(T), MemberType);

        // we need to call ValueProxy.ReturnValue, which is a generic type
        MethodInfo GenericReturnValueMethod = typeof(ValueProxy).GetMethod("GetValue");
        // it's type parameters are MemberType and <T>, so we "make" a method to bake in those specific types
        MethodInfo GetValueMethod = GenericReturnValueMethod.MakeGenericMethod(MemberType, typeof(T));

        var proxy = new ValueProxy(mi);

        // now create a delegate using the delegate type and method we just constructed
        Delegate GetMethodDelegate = Delegate.CreateDelegate(DelegateType, proxy, GetValueMethod);

        // method name on IEnumerable/IOrderedEnumerable to call later
        string MethodName = null;

        // do we already have at least one sort on this collection?
        if (Source is IOrderedEnumerable<T>)
        {
            if (SortDirection == SortDirection.Ascending)
                MethodName = "ThenBy";
            else
                MethodName = "ThenByDescending";
        }
        else // first sort on this collection
        {
            if (SortDirection == SortDirection.Ascending)
                MethodName = "OrderBy";
            else
                MethodName = "OrderByDescending";
        }

        MethodInfo method = typeof(Enumerable).GetMethods()
            .Single(m => m.Name == MethodName && m.MakeGenericMethod(typeof(int), typeof(int)).GetParameters().Length == 2);

        return method.MakeGenericMethod(typeof(T), MemberType)
            .Invoke(Source, new object[] { Source, GetMethodDelegate }) as IOrderedEnumerable<T>;
    }
}

public class ValueProxy
{
    private MemberInfo Member;

    public T GetValue<T, TKey>(TKey obj)
    {
        if (Member is FieldInfo)
            return (T)(Member as FieldInfo).GetValue(obj);
        else if (Member is PropertyInfo)
            return (T)(Member as PropertyInfo).GetValue(obj, null);

        return default(T);
    }

    public ValueProxy(MemberInfo Member)
    {
        this.Member = Member;
    }
}

 

There are a few things worth mentioning about this approach.  In a nutshell, what we need to do is construct a delegate to a function that will get called later, when the query is actually executed.  (In other words, we’re using Reflection to get a Reflection method that gets values.)  First we need the function to point to, so that’s defined in the ValueProxy class as GetValue, whose job it is to remember which member is being selected, and to query that member’s value when requested.

It’s defined with generics because I want to use it as a generalized mechanism for sorting all types of fields or properties.  Since we’re dealing with generics, we need to know that Func<,> is different from Func<Customer,string>.  We call MakeGenericType on the former, pass in type parameters, and end up with the latter.  The same is true of the difference between GetValue<,> and GetValue<string,Customer> with MakeGenericMethod.

Type DelegateType = typeof(Func<,>).MakeGenericType(typeof(T), MemberType);
MethodInfo GetValueMethod = GenericReturnValueMethod.MakeGenericMethod(MemberType, typeof(T));

Once we have handles to these, we can create our delegate object.

Delegate GetMethodDelegate = Delegate.CreateDelegate(DelegateType, proxy, GetValueMethod);

The ValueProxy objects bind together the method to get the value and the member to get the value from, the latter not being supplied by the OrderBy family of extension methods (which will ultimate call our GetValue method).  Abstracting this away into a proxy is what gives us the necessary indirection to inject the generalization mechanism.

The end of the Order method presents a challenge for running in Compact Framework.  Consider how to select a MethodInfo object from the following options:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector);
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector, IComparer<TKey> comparer);

We have two overloads, both generic methods, one with two parameters and the other with three.  You might expect, as I did, that one of the Type.GetMethod overloads would include a way to get a MethodInfo object for a specific method, but in the case of generic methods, it’s actually not possible.  Trying to be clever by supplying open generics for the parameters, I attempted this:

MethodInfo mi = typeof(Enumerable).GetMethod("OrderBy", BindingFlags.Public | BindingFlags.Static, null,
    new Type[] { typeof(IEnumerable<>), typeof(Func<,>) }, null);

…but alas, this doesn’t work.  Instead, you have to query all methods with Type.GetMethods, and then somehow filter them out.  In the full .NET Framework, we could do this:

MethodInfo method = typeof(Enumerable).GetMethods()
    .Single(m => m.Name == MethodName && m.GetParameters().Length == 2);

However, in Compact Framework we get a NotSupportedException: "GetParameters for Open Generic methods is not supported."  This suggests that method definitions in the type system are not exactly the same between CF and FF in terms of how generics are defined.  We can get around this problem by calling MakeGenericMethod, but it’s unfortunate that we have to incur the extra overhead just to get a parameter count.  Still, this happens once per sort field instead of something horrible like for once per object in the collection, and with the && being a short-circuit operator, the only time GetParameters will be called is when the method name matches, which brings us to two matches maximum, so it’s really not so bad.  I pass in typeof(int) for both type parameters (not to be confused with the method’s value parameters).  The type parameters used here don’t actually matter; we won’t actually use the OrderBy<int,int> method for anything other than getting a count of its value parameters, which is used to select the overload we want.

MethodInfo method = typeof(Enumerable).GetMethods()
    .Single(m => m.Name == MethodName && m.MakeGenericMethod(typeof(int), typeof(int)).GetParameters().Length == 2);

return method.MakeGenericMethod(typeof(T), MemberType)
    .Invoke(Source, new object[] { Source, GetMethodDelegate }) as IOrderedEnumerable<T>;

So there it is, an unintuitive and round-about way of selecting a method to call, but it works on both Full and Compact Framework.

Happy querying!

About these ads

8 Responses to “Dynamically Composing LINQ OrderBy Clauses in Compact Framework”

  1. !mpact said

    Hi there,

    I am currently looking for a solution to a similar problem:

    The user should be able to define his search filters dynamically (selecting which fields to see, which order and the filter, etc.). I have found the following possibilities so far:

    – using System.Linq.Dynamic and provide parts of the query as a string
    – using creating my own expression trees for filtering which can be used by Linq (problem here, expression trees are not serializable)

    Now the problem I see with your solution:

    If you put this on Linq to SQL for example (if I am not mistaking) the ordering will be performed in memory and not in the sql statement… since you are using the delegate and not an expression. So this can be a performance issue if you have large collection. Normally this could be avoided by using Expression<Func>

    Have fun !

    *J*

  2. !mpact said

    Hi me again,

    I have not seen the section that this is supposed to be for Compact Framework …

    hf

    *J*

  3. !mpact said

    Hi again,

    > It is possible to serialize expression trees, send them over WCF, etc.

    This is a custom serialization library, transforming the expression into a XML document which is sent over the wire. So i could directly use Dynamic LINQ for that purpose and wrap the expression strings in some kind of search request object, which is sent over the wire!

    Expressions trees are not serializable in the sense of using BinFormatter, SoapFormatter, XmlSerializer or DataContractSerializer. I wanted to avoid the need to transform the expression tree into an intermediate format ( e.g. XML) which is then again serialized by WCF when it goes over the wire.

    So I guess Dynamic LINQ seems to be the appropriate solution to let the client to create some sorting and ordering expression.

  4. [...] original article (with source code) is here.  All I added to the library was [...]

  5. news said

    Very interesting post. I discovered your blog within the blog listing I dont know the way it came up but you made a really informative post. Good job.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: