Monthly Archives: May 2007

Announcing MetaLinq – Linq to Expressions

May 24, 2007 – 10:24 pm

It is with great pleasure that I announce yet another flavor of LINQ – MetaLinq – the ability to query over and edit expression trees using LINQ.

Why MetaLinq?  Well, Oren Novotny, who is working on yet another project, SLINQ, aka Linq to Streams, and who also has contributed to i4o, was asking me if I knew an mechanism where one could walk an expression tree and replace certain nodes.  Being the sort of person who always like a challenge, I decided to help, creating an enumerator extension method for Expressions that allows you to easily walk the expression tree, with the plan of editing the nodes in the tree as I go along (i.e. using a LINQ query over the resulting "walk the tree" enumeration).  Then it hit me.  Expression trees are immutable.  I find this by not reading stuff online, but hacking away and finding all those darn properties of expression nodes are read only.

Damn.  How to get around this one?

Well, after reading Jomo Fisher’s blog, it became evident that if you want to get a variation of a tree, you have to copy part, or all, of the tree, and carefully replace the parts you want changed as you are doing so.  Thankfully, Jomo put a reasonable approach up on his blog, which uses a visitor pattern and does a selective replacement.  And his method works.

That said, I decided to take a different approach.  ExpressionBuilder, which is part of MetaLinq for the moment, is the result.  The ExpressionBuilder namespace allows you to create an Editable Shadow of an expression tree, modify it in place, and then by calling ToExpression on the shadow tree, generate a new, normal, immutable tree.  It has a class, EditableExpression, that has a factory method (CreateEditableExpression) that takes any expression, and returns an EditableExpression that mirrors the immutable Expression.

For example, to get the editable tree, you would do this to get an editable copy:

Expression immutable = someExpression; //you can’t change immutable directly

EditableExpression mutable = EditableExpression.CreateEditableExpression(immutable);

//..then do this to convert it back

Expression newCopy = mutable.ToExpression;

//pretend there are parens after ToExpression -  shortcoming in my blog software that does not allow me to say ToExpression with parens afterwards

In other words, you can now edit expression trees.  ExpressionBuilder is to Expressions what StringBuilder is to Strings.

I will warn you that you can easily shoot yourself in the foot with this.  As of the current version, you can easily create a cyclic graph, which, of course, will create an infinite loop when you try to convert it back into an immutable expression.  While I will be adding code to check for cycles in the future, there is no getting around that having full edit capability on the expression tree can cause subtle bugs.

The project is hosted on codeplex, and as with i4o, it is open source, and other contributors are welcome to help add to it or fix bugs.  For more information, email me at aaron.c.erickson@gmail.com .

By Aaron Erickson | Posted in Uncategorized | Comments (0)

LINQ to Objects and Bi-Directional Binding

May 11, 2007 – 10:22 pm

There is a lot of great technology coming from Microsoft in this year – there is almost not enough time to take it all in.  That said, there are some areas where we can try to anticipate where some issues are going to occur, be they fast access to objects (i4o), or in this latest installment, enabling bi-directional binding to work correctly on results from LINQ to Objects operations.

You might ask, why is this an issue?  Well, as Rocky Lhotka as pointed out before, the results of a query from LINQ to Objects do not return a filtered view of the original collection, but a whole new object (something called a Sequence) that implements IEnumerable<T>, so you can iterate over it and, at least in a read-only sense, bind to it.  Now, presumably you could, in theory, add or remove to the result (though I don’t know for sure – have not tried yet)… but the problem is that even if you could, you would be adding or removing from a different collection, as well as losing anything that was implemented for you in the IEnumerable<T> you start with in the first place.  Which means that, if you are using CSLA.net, you not only will have wierd things happen on add/remove, but you will also break features that framework provides, like N-level undo.

Needless to say, this is the kind of thing that might rain on the LINQ to objects parade for certain kinds of use cases… if LINQ were not extensible that is :).  Writers of frameworks – especially the kind of frameworks that have custom collections, will want to implement IQueryable<T> on their custom collections in order to allow for bi-directional binding LINQ generated subsets.  IQueryable<T> allows you to, in its CreateQuery<TElement> method, to specify what exactly comes back from the different LINQ methods (i.e. Where, Select, GroupBy, etc.).  Of particular interest for filtering is handling your Where call such that it returns an IQueryable<T> whose concrete implementation you can control, rather than using the default that LINQ gives you.

The technique I am using to do this relies on two classes.  The first class is a simple collection class that implements ICollection<T> and IQueryable<T>, that I am calling CollectionExtendingIQueryable<T>.  The second class is designed to be a read/write view of the first one that is derived from the first one – called ViewOnCollectionExtendingIQueryable<T>.  This second class (the view) also implements IQueryable<T>.  The result of a LINQ query that projects an identity projection – that is – a projection of the whole objects of the enumerable we are enumerating – will now be typed to ViewOnCollectionExtendingIQueryable<T>, which can have all the stuff behavior the parent has, and the same data, but is assigned a different expression that IEnumerable<T>.GetEnumerator() will use when generating it’s result from the where clause.

More simply, we generate a read/write view collection that differs from the original collection only in it’s GetEnumerator implementation.  In most other respects (most importantly the underlying concrete collection) – it is the same object.  If you add or remove from the filtered version, you remove from the concrete collection, which potentially, removes it from other filtered views.

Of course, there is a lot of other work you have to do to fully implement IQueryable<T>.  I have done some of it, such as making sure non-identity projections work like normal LINQ projections – but I am sure there is other work needed to do a full implementation.  That said, the important part of this is that it proves the concept that you can have LINQ to Objects and support filter style projections, if you are willing to dive into supporting IQueryable<T>.

Source code is below, with a demo console implementation:

FilteredCollection.cs:

using System;
using System.Linq;
using System.Collections.Generic;
using System.Linq.Expressions;

namespace TestExtendingIQueryable
{
    //NOTE: This is a proof of concept – not designed to be production code

    public class RandomThing
    {
        public int SomeVal;
        public RandomThing(int x) { SomeVal = x; }
    }

   
    public class CollectionExtendingIQueryable<T> : ICollection<T>, IQueryable<T>
    {
        public CollectionExtendingIQueryable()
        { _internalList = new List<T>(); _ex = System.Linq.Expressions.Expression.Constant(this); }
       
        protected Expression _ex;
        protected List<T> _internalList;

        internal List<T> UnderlyingList { get { return _internalList; } }

        public void RemoveBottomItem()
        {
            _internalList.RemoveAt(0);
        }

        public void Add(T item)
        {
            _internalList.Add(item);
        }

        public int FilteredCount
        {
            get
            {
                int cnt = 0;
                foreach (T item in this)
                    cnt++;
                return cnt;
            }
        }

        public int UnfilteredCount
        {
            get
            {
                int cnt = 0;
                foreach (T item in _internalList)
                    cnt++;
                return cnt;
            }
        }

        #region IQueryable<T> Members

        IQueryable<TElement> IQueryable<T>.CreateQuery<TElement>(Expression expression)
        {
           
            MethodCallExpression mex = expression as MethodCallExpression;
            switch(mex.Method.Name)
            {
                case "Where":
                    return (IQueryable<TElement>) new ViewOnCollectionExtendingIQueryable<T>(expression, this);
                case "Select":
                   
                    UnaryExpression selectHolder = mex.Arguments[1] as UnaryExpression;
                    LambdaExpression theSelect = selectHolder.Operand as LambdaExpression;
                   
                    Expression<Func<T, TElement>> selectorLambda
                        = Expression.Lambda<Func<T, TElement>>(theSelect.Body,theSelect.Parameters);
                    Func<T, TElement> selector = selectorLambda.Compile();
                    return this.Select<T, TElement>(selector).AsQueryable<TElement>();
                default:
                    return null;
            }
        }

        TResult IQueryable<T>.Execute<TResult>(Expression expression)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        #endregion

        #region IEnumerable<T> Members

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            MethodCallExpression mex = _ex as MethodCallExpression;
            UnaryExpression whereHolder = mex.Arguments[1] as UnaryExpression;
            LambdaExpression theWhere = whereHolder.Operand as LambdaExpression;
            Expression<Func<T, bool>> theParmedWhere
                = Expression.Lambda<Func<T, bool>>(theWhere.Body, theWhere.Parameters);
            Func<T, bool> filter = theParmedWhere.Compile();
            //if we had indexes in this collection, they would be used here
            foreach (T item in _internalList)
                if (filter(item))
                    yield return item;
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            MethodCallExpression mex = _ex as MethodCallExpression;
            UnaryExpression whereHolder = mex.Arguments[1] as UnaryExpression;
            LambdaExpression theWhere = whereHolder.Operand as LambdaExpression;
            Expression<Func<T, bool>> theParmedWhere = Expression.Lambda<Func<T, bool>>(theWhere.Body, theWhere.Parameters);
            Func<T, bool> filter = theParmedWhere.Compile();
            foreach (T item in this)
                if (filter(item))
                    yield return item;
        }

        #endregion

        #region IQueryable Members

        IQueryable IQueryable.CreateQuery(Expression expression)
        {
            _ex = expression;
            return this;
        }

        Type IQueryable.ElementType
        {
            get { return typeof(T); }
        }

        object IQueryable.Execute(Expression expression)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        Expression IQueryable.Expression
        {
            get { return _ex; }
        }

        #endregion

        #region ICollection<T> Members

        void ICollection<T>.Add(T item)
        {
            _internalList.Add(item);
        }

        void ICollection<T>.Clear()
        {
            _internalList.Clear();
        }

        bool ICollection<T>.Contains(T item)
        {
            return _internalList.Contains(item);
        }

        void ICollection<T>.CopyTo(T[] array, int arrayIndex)
        {
            _internalList.CopyTo(array,arrayIndex);
        }

        int ICollection<T>.Count
        {
            get { return _internalList.Count; }
        }

        bool ICollection<T>.IsReadOnly
        {
            get { return false; }
        }

        bool ICollection<T>.Remove(T item)
        {
            return(_internalList.Remove(item));
        }

        #endregion
    }

    public class ViewOnCollectionExtendingIQueryable<T> : CollectionExtendingIQueryable<T>, IQueryable<T>
    {
        protected Expression _specificEx;
       
        public ViewOnCollectionExtendingIQueryable(Expression ex, CollectionExtendingIQueryable<T> baseCollection)
        {
            _internalList = baseCollection.UnderlyingList;
            _specificEx = ex;
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            MethodCallExpression mex = _specificEx as MethodCallExpression;
            UnaryExpression whereHolder = mex.Arguments[1] as UnaryExpression;
            LambdaExpression theWhere = whereHolder.Operand as LambdaExpression;
            Expression<Func<T, bool>> theParmedWhere
                = Expression.Lambda<Func<T, bool>>(theWhere.Body, theWhere.Parameters);
            Func<T, bool> filter = theParmedWhere.Compile();
            //if we had indexes in this collection, they would be used here
            foreach (T item in _internalList)
                if (filter(item))
                    yield return item;
        }

        #region IQueryable<T> Members

        IQueryable<TElement> IQueryable<T>.CreateQuery<TElement>(Expression expression)
        {

            MethodCallExpression mex = expression as MethodCallExpression;
            switch (mex.Method.Name)
            {
                case "Where":
                    _specificEx = expression;
                    return (IQueryable<TElement>) this;
                case "Select":

                    UnaryExpression selectHolder = mex.Arguments[1] as UnaryExpression;
                    LambdaExpression theSelect = selectHolder.Operand as LambdaExpression;

                    Expression<Func<T, TElement>> selectorLambda
                        = Expression.Lambda<Func<T, TElement>>(theSelect.Body, theSelect.Parameters);
                    Func<T, TElement> selector = selectorLambda.Compile();
                    return this.Select<T, TElement>(selector).AsQueryable<TElement>();
                default:
                    return null;
            }
        }

        TResult IQueryable<T>.Execute<TResult>(Expression expression)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new Exception("The method or operation is not implemented.");
        }

        #endregion

        #region IQueryable Members

        IQueryable IQueryable.CreateQuery(Expression expression)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        Type IQueryable.ElementType
        {
            get { return typeof(T); }
        }

        object IQueryable.Execute(Expression expression)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        Expression IQueryable.Expression
        {
            get { return _specificEx; }
        }

        #endregion
    }
}

Program.cs:

using System;
using System.Linq;
using System.Collections.Generic;

namespace TestExtendingIQueryable
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Demonstration of using LINQ to generate filtered results, using a");
            Console.WriteLine("collection class specifically designed to filter rather than project");
            Console.WriteLine("by default.");
            Console.WriteLine("");
            Console.WriteLine("We will generate a collection with 100 random numbers, between 1 and 300");
            Console.WriteLine("We will then generate two views on the numbers, one for those below 100,");
            Console.WriteLine("the other for those below 200.  Removing the bottom most item, which is");
            Console.WriteLine("the only item that wont be random (fixed at 42, to fit in both ranges)");
            Console.WriteLine("will affect the count of all three collections (original, filteredview,");
            Console.WriteLine("and different filtered view.");
            Console.WriteLine("");
            Console.WriteLine("Lastly, we will do a typical projection, which will demonstrate that");
            Console.WriteLine("the filtering logic gets out of the way when you select something that");
            Console.WriteLine("is not amenable to filtering.");
           
            CollectionExtendingIQueryable<RandomThing> random = new CollectionExtendingIQueryable<RandomThing>();
            Random rnd = new Random();
            random.Add(new RandomThing(42)); //first one has to be under 100 to run our removal tests correctly
            for (int i = 0; i < 99; i++)
                random.Add(new RandomThing(rnd.Next(300)));
                       
            var filteredResult = from r in random
                                where r.SomeVal < 100
                                select r;

            var differentFilteredResult = from r in random
                                          where r.SomeVal < 200
                                          select r;

            Console.WriteLine("Filtered results (random numbers under 100)");
            foreach (var x in filteredResult)
                Console.Write(x.SomeVal + ",");
            Console.WriteLine("");
            Console.WriteLine("———————————-");
            Console.WriteLine("Filtered result Count = " + ((CollectionExtendingIQueryable<RandomThing>)filteredResult).FilteredCount);
            Console.WriteLine("Different filtered result Count = " + ((CollectionExtendingIQueryable<RandomThing>)differentFilteredResult).FilteredCount);
            Console.WriteLine("Now we are going to remove the bottom item from the first filtered result, which should reduce the count of all filtered results by one");
            Console.WriteLine("Press any key to continue…");

            Console.ReadKey();

            Console.WriteLine("Count of original collection = " + random.UnfilteredCount);
            ((CollectionExtendingIQueryable<RandomThing>)filteredResult).RemoveBottomItem();
            Console.WriteLine("Count of original collection after removal from filtered list = " + random.UnfilteredCount);
            Console.WriteLine("Count in the filtered list = " + ((CollectionExtendingIQueryable<RandomThing>)filteredResult).FilteredCount);
           
            Console.WriteLine("Count in the different filtered result = " + ((CollectionExtendingIQueryable<RandomThing>)differentFilteredResult).FilteredCount);
            Console.WriteLine("Press any key to test projection…");
            Console.ReadKey();

            var projectedResult = from r in random
                                  where r.SomeVal < 100
                                  select r.SomeVal;
            foreach (var x in projectedResult)
                Console.Write(x + ",");
            Console.WriteLine("");
            Console.WriteLine("———————");
            Console.WriteLine("Press any key to exit the demo…");
            Console.ReadKey();

        }
    }
}

 

By Aaron Erickson | Posted in Uncategorized | Comments (0)
Follow

Get every new post delivered to your Inbox.