Expression Trees and Linq

I love this new technology called "Linq", not only does it make some things much simpler, it also allows new possibilities. While upon writing traditionnal code you get a hold on the end result function, with Expression Tree you can get a hold on the abstract composition which your function is made of. The actual operation performed by your instruction, or sequence of, is just an aspect of it. One can in principle, manipulate, enrich the sequence before transforming it to an actual function... You can think of it as an extension of delegates. While delegates enables you to defer the actual execution of a command, Expression Trees enables you to also defer the actual body content. Practically, those operations are not natively possible with Linq alone. You need :

• A way to travel in the tree structure of the Expression tree : you can start with the code below. feel free to post back some if you improve it.
• A way to convert from the Expression tree to actual code : the espresso sample provides a first start too. May be I'll post some more complete code here.

So here is a wrapper to the Linq Expression type I wrote to explicit the tree structure.I allows you to traverse the tree for transformation.

Possible improvements would be to

• support grouping of children node
• Adding event support (like adding, removing element..) to make it bindable

[+/-] read/hide the code

ExpressionTree.cs

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

namespace DataStructure
{

   [Flags]
   public enum ExpressionTypeTree : long
   {
       Add = 0,
       And = 2,
       As = 4,
       BitwiseAnd = 8,
       BitwiseNot = 16,
       BitwiseOr = 32,
       BitwiseXor = 64,
       Cast = 128,
       Coalesce = 256,
       Concat = 512,
       Constant = 1024,
       Convert = 2048,
       Divide = 4096,
       EQ = 8192,
       Funclet = 16384,
       GT = 32768,
       GE = 65536,
       Index = 131072,
       Invoke = 262144,
       Is = 524488,
       Lambda = 1048576,
       LE = 2097152,
       Len = 4194304,
       LShift = 8388608,
       LT = 16777216,
       MemberAccess = 33554432,
       MethodCall = 67108864,
       Modulo = 134217728,
       Multiply = 268435456,
       Negate = 536870912,
       NE = 1073741824,
       New = 2147483648,
       NewArrayInit = 4294967296,
       NewArrayBounds = 8589934592,
       Not = 17179869184,
       Or = 34359738368,
       Parameter = 68719476736,
       RShift = 137438953472,
       Source = 274877906944,
       Subtract = 549755813888,
       All = 1099511627775,
   }

   public class ExpressionTreeVisitor
   {
       public delegate object VisitorDelegate(Expression e, object param, object[] sonreturn);

       public VisitorDelegate VisitorNew;
       public VisitorDelegate VisitorBitwiseNot;
       public VisitorDelegate VisitorNegate;
       public VisitorDelegate VisitorNot;
       public VisitorDelegate VisitorAdd;
       public VisitorDelegate VisitorSubtract;
       public VisitorDelegate VisitorMultiply;
       public VisitorDelegate VisitorDivide;
       public VisitorDelegate VisitorModulo;
       public VisitorDelegate VisitorAnd;
       public VisitorDelegate VisitorOr;
       public VisitorDelegate VisitorLT;
       public VisitorDelegate VisitorLE;
       public VisitorDelegate VisitorGT;
       public VisitorDelegate VisitorGE;
       public VisitorDelegate VisitorEQ;
       public VisitorDelegate VisitorNE;
       public VisitorDelegate VisitorBitwiseAnd;
       public VisitorDelegate VisitorBitwiseOr;
       public VisitorDelegate VisitorBitwiseXor;
       public VisitorDelegate VisitorCoalesce;
       public VisitorDelegate VisitorConstant;
       public VisitorDelegate VisitorMemberAccess;
       public VisitorDelegate VisitorLambda;
       public VisitorDelegate VisitorParameter;
       public VisitorDelegate VisitorMethodCall;
       public VisitorDelegate VisitorCast;
       public VisitorDelegate VisitorConcat;
       public VisitorDelegate VisitorFunclet;
       public VisitorDelegate VisitorNewArrayInit;
       public VisitorDelegate VisitorDefault;


       public virtual void AssignVisitorTo(VisitorDelegate v, ExpressionTypeTree e)
       {
           if ((e & ExpressionTypeTree.New) != 0)
               VisitorNew = v;
           if ((e & ExpressionTypeTree.BitwiseNot) != 0)
               VisitorBitwiseNot = v;
           if ((e & ExpressionTypeTree.Negate) != 0)
               VisitorNegate = v;
           if ((e & ExpressionTypeTree.Not) != 0)
               VisitorNot = v;
           if ((e & ExpressionTypeTree.Add) != 0)
               VisitorAdd = v;
           if ((e & ExpressionTypeTree.Subtract) != 0)
               VisitorSubtract = v;
           if ((e & ExpressionTypeTree.Multiply) != 0)
               VisitorMultiply = v;
           if ((e & ExpressionTypeTree.Divide) != 0)
               VisitorDivide = v;
           if ((e & ExpressionTypeTree.Modulo) != 0)
               VisitorModulo = v;
           if ((e & ExpressionTypeTree.And) != 0)
               VisitorAnd = v;
           if ((e & ExpressionTypeTree.Or) != 0)
               VisitorOr = v;
           if ((e & ExpressionTypeTree.LT) != 0)
               VisitorLT = v;
           if ((e & ExpressionTypeTree.LE) != 0)
               VisitorLE = v;
           if ((e & ExpressionTypeTree.GT) != 0)
               VisitorGT = v;
           if ((e & ExpressionTypeTree.GE) != 0)
               VisitorGE = v;
           if ((e & ExpressionTypeTree.EQ) != 0)
               VisitorEQ = v;
           if ((e & ExpressionTypeTree.NE) != 0)
               VisitorNE = v;
           if ((e & ExpressionTypeTree.BitwiseAnd) != 0)
               VisitorBitwiseAnd = v;
           if ((e & ExpressionTypeTree.BitwiseOr) != 0)
               VisitorBitwiseOr = v;
           if ((e & ExpressionTypeTree.BitwiseXor) != 0)
               VisitorBitwiseXor = v;
           if ((e & ExpressionTypeTree.Coalesce) != 0)
               VisitorCoalesce = v;
           if ((e & ExpressionTypeTree.Constant) != 0)
               VisitorConstant = v;
           if ((e & ExpressionTypeTree.MemberAccess) != 0)
               VisitorMemberAccess = v;
           if ((e & ExpressionTypeTree.Lambda) != 0)
               VisitorLambda = v;
           if ((e & ExpressionTypeTree.Parameter) != 0)
               VisitorParameter = v;
           if ((e & ExpressionTypeTree.MethodCall) != 0)
               VisitorMethodCall = v;
           if ((e & ExpressionTypeTree.Cast) != 0)
               VisitorCast = v;
           if ((e & ExpressionTypeTree.Concat) != 0)
               VisitorConcat = v;
           if ((e & ExpressionTypeTree.Funclet) != 0)
               VisitorFunclet = v;
           if ((e & ExpressionTypeTree.NewArrayInit) != 0)
               VisitorNewArrayInit = v;
       }

       public object Visit(Expression e, object param)
       {
           switch (e.NodeType)
           {
               case ExpressionType.New:
               {
                   NewExpression ne = e as NewExpression;
                   object[] res1 = ne.Args.VisitList(this, param);
                   object[] res2 = ne.Bindings.VisitList(this, param);
                   return this.VisitorNew(e, param, new object[][] { res1, res2 });
               }
               case ExpressionType.BitwiseNot:
                   UnaryExpression ne1 = e as UnaryExpression;
                   return this.VisitorBitwiseNot(e, param, new object[] { ne1.Operand.Visit(this, param) });
               case ExpressionType.Negate:
                   UnaryExpression ne2 = e as UnaryExpression;
                   return this.VisitorNegate(e, param, new object[] { ne2.Operand.Visit(this, param) });
               case ExpressionType.Not:
                   UnaryExpression ne3 = e as UnaryExpression;
                   return this.VisitorNot(e, param, new object[] { ne3.Operand.Visit(this, param) });
               case ExpressionType.Add:
               case ExpressionType.Subtract:
               case ExpressionType.Multiply:
               case ExpressionType.Divide:
               case ExpressionType.Modulo:
               case ExpressionType.And:
               case ExpressionType.Or:
               case ExpressionType.LT:
               case ExpressionType.LE:
               case ExpressionType.GT:
               case ExpressionType.GE:
               case ExpressionType.EQ:
               case ExpressionType.NE:
               case ExpressionType.BitwiseAnd:
               case ExpressionType.BitwiseOr:
               case ExpressionType.BitwiseXor:
               case ExpressionType.Coalesce:
                   return this.VisitBinary((e as BinaryExpression), param);
               case ExpressionType.Constant:
                   return this.VisitorConstant(e, param, new object[] { });
               case ExpressionType.MemberAccess:
                   return this.VisitorMemberAccess(e, param, new object[] { (e as MemberExpression).Expression.Visit(this, param) });
               case ExpressionType.Lambda:
               {
                   LambdaExpression le = e as LambdaExpression;
                   object[] res1 = le.Parameters.VisitList(this, param);
                   object res2 = le.Body.Visit(this, param);
                   return this.VisitorLambda(e, param, new object[] { res1, res2 });
               }
               case ExpressionType.Parameter:
                   return this.VisitorParameter(e, param, new object[] { });
               case ExpressionType.MethodCall:
               {
                   MethodCallExpression me = e as MethodCallExpression;
                   object[] res1 = me.Parameters.VisitList(this, param);

                   return this.VisitorMethodCall(e, param, res1);
               }
               case ExpressionType.Cast:
                   return this.VisitorCast(e, param, new object[] { (e as UnaryExpression).Operand.Visit(this, param) });
               case ExpressionType.Concat:
               {
                   NAryExpression ne = e as NAryExpression;
                   object[] res1 = ne.Expressions.VisitList(this, param);
                   return this.VisitorConcat(e, param, res1);
               }
               case ExpressionType.Funclet:
                   return this.VisitorFunclet(e, param, null);
               case ExpressionType.NewArrayInit :
               {
                   NewArrayExpression ne = e as NewArrayExpression;
                   object[] res1 = ne.Expressions.VisitList(this, param);
                   return this.VisitorNewArrayInit(e, param, res1);
               }
               default:
                   return this.VisitorDefault(e, param, new object[] { });
           }
       }
       private object VisitBinary(BinaryExpression e, object param)
       {
           object[] ret = new object[2];
           ret[0] = e.Left.Visit(this, param);
           ret[1] = e.Right.Visit(this, param);
           switch (e.NodeType)
           {
               case ExpressionType.Add:
                   return this.VisitorAdd(e, param, ret);
               case ExpressionType.Subtract:
                   return this.VisitorSubtract(e, param, ret);
               case ExpressionType.Multiply:
                   return this.VisitorMultiply(e, param, ret);
               case ExpressionType.Divide:
                   return this.VisitorDivide(e, param, ret);
               case ExpressionType.Modulo:
                   return this.VisitorModulo(e, param, ret);
               case ExpressionType.And:
                   return this.VisitorAnd(e, param, ret);
               case ExpressionType.Or:
                   return this.VisitorOr(e, param, ret);
               case ExpressionType.LT:
                   return this.VisitorLT(e, param, ret);
               case ExpressionType.LE:
                   return this.VisitorLE(e, param, ret);
               case ExpressionType.GT:
                   return this.VisitorGT(e, param, ret);
               case ExpressionType.GE:
                   return this.VisitorGE(e, param, ret);
               case ExpressionType.EQ:
                   return this.VisitorEQ(e, param, ret);
               case ExpressionType.NE:
                   return this.VisitorNE(e, param, ret);
               case ExpressionType.BitwiseAnd:
                   return this.VisitorBitwiseAnd(e, param, ret);
               case ExpressionType.BitwiseOr:
                   return this.VisitorBitwiseOr(e, param, ret);
               case ExpressionType.BitwiseXor:
                   return this.VisitorBitwiseXor(e, param, ret);
               case ExpressionType.Coalesce:
                   return this.VisitorCoalesce(e, param, ret);
           }
           return null;
       }
   }


   public static partial class Utils
   {
       public static object[] VisitList(this StaticList<Expression> el, ExpressionTreeVisitor etvisitor, object param)
       {
           object[] ret = new object[el.Count];
           for (int i = 0, n = el.Count; i < n; i++)
               ret[i] = el[i].Visit(etvisitor, param);

           return ret;
       }
       public static object[] VisitList(this StaticList<Binding> el, ExpressionTreeVisitor etvisitor, object param)
       {
           object[] ret = new object[el.Count];
           for (int i = 0, n = el.Count; i < n; i++)
           {
               ret[i] = el[i].Visit(etvisitor, param);
           }
           return ret;
       }
       public static object[] VisitList(this StaticList<ParameterExpression> el, ExpressionTreeVisitor etvisitor, object param)
       {
           object[] ret = new object[el.Count];
           for (int i = 0, n = el.Count; i < n; i++)
           {
               ret[i] = (el[i] as Expression).Visit(etvisitor, param);
           }
           return ret;
       }
       public static object Visit(this Binding e, ExpressionTreeVisitor etvisitor, object param)
       {
           return null;
       }
       public static object Visit(this Expression e, ExpressionTreeVisitor etvisitor, object param)
       {
           return etvisitor.Visit(e, param);
       }
       public static object Visit(this Expression e, ExpressionTreeVisitor.VisitorDelegate etvisitordelegate, object param)
       {
           ExpressionTreeVisitor visitor = new ExpressionTreeVisitor();
           visitor.AssignVisitorTo(etvisitordelegate, ExpressionTypeTree.All);
           return e.Visit(visitor, param);
       }
   }


   public class ExpressionTree : Expression, INode<Expression>
   {
       ExpressionTreeList _Children = new ExpressionTreeList();
       Expression _expression;
       bool _isdirty = false;
       bool _isbuilding = false;

       public static object TreeBuilder(Expression expr, object param, object[] sons)
       {
           ExpressionTree exprtree = param as ExpressionTree;
           if (exprtree.Value == expr)
           {
               for (int i = 0, n = sons.Length; i < n; i++)
               {
                   object[] group = sons[i] as object[];
                   if (group != null)
                   {
                       foreach (object obj in group)
                           exprtree.Children.Add(new ExpressionTree(obj as Expression));
                   }
                   else
                       exprtree.Children.Add(new ExpressionTree(sons[i] as Expression));
               }
           }
           return expr;
       }


       public ExpressionTree(Expression expr)
           : base(expr.NodeType, expr.Type)
       {
           Value = expr;
       }

       private void BuildTree()
       {
           _isbuilding = true;
           ExpressionTreeVisitor visitor = new ExpressionTreeVisitor();
           visitor.AssignVisitorTo(new ExpressionTreeVisitor.VisitorDelegate(TreeBuilder), ExpressionTypeTree.All);
           _expression.Visit(visitor, this);
           _isbuilding = false;
           _isdirty = false;
       }


       public Expression Value
       {
           get
           {
               return _expression;
           }
           set
           {
               _expression = value;
               _isdirty = true;
           }
       }
       public INodeList<Expression> Children
       {
           get
           {
               if (_isdirty && !_isbuilding) BuildTree();
               return _Children as INodeList<Expression>;
           }
           set
           {
               _Children = value as ExpressionTreeList;
           }
       }
   }


   public class ExpressionTreeList : List<INode<Expression>>, INodeList<Expression>
   {

   }

}

and the tree structure:

Tree.cs

using System;
using System.Collections.Generic;
using System.Collections;
using System.Windows.Forms;

namespace DataStructure
{
   public interface INode
   {
       object Value { get; set;}
       ICollection Children { get;}
   }
   public interface INodeList : IList<INode> { }
   public interface INode<T>
   {
       T Value { get;            set;        }
       INodeList<T> Children
       {
           get;
           set;
       }
   }
   public interface INodeList<T> : IList<INode<T>>
   {
   }

   public class Node<T> : INode
   {
       private T data;
       private NodeList<T> _children = null;

       public Node() { }
       public Node(T data) : this(data, null) { }
       public Node(T data, NodeList<T> children)
       {
           this.data = data;
           this._children = children;
       }

       public T Value
       {
           get
           {
               return data;
           }
           set
           {
               data = value;
           }
       }

       public NodeList<T> Children
       {
           get
           {
               return _children;
           }
           set
           {
               _children = value;
           }
       }

       #region INode Members

       object INode.Value
       {
           get
           {
               return this.Value;
           }
           set
           {
               this.Value = (T)value;
           }
       }

       ICollection INode.Children
       {
           get { return this.Children; }
       }

       #endregion
   }
   public class NodeList<T> : List<Node<T>>
   {
       public NodeList() : base() { }

       public NodeList(int initialSize)
       {
           for (int i = 0; i < initialSize; i++)
               base.Add(default(Node<T>));
       }

       public Node<T> FindByValue(T value)
       {
           foreach (Node<T> node in this)
               if (node.Value.Equals(value))
                   return node;
           return null;
       }
   }

   public delegate object TreeVisitor<T>(INode<T> arg, object param, object[] sonreturn);
   public delegate INode<T> TreeTransformer<T>(INode<T> arg, object param, INode<T>[] sonreturn);



   public static partial class Utils
   {
       public static object Visit<T>(this INode<T> arg, TreeVisitor<T> treevisitor, object param)
       {
           return treevisitor(arg, param, arg.Children.VisitList<T>(treevisitor, param));
       }
       public static object[] VisitList<T>(this INodeList<T> arg, TreeVisitor<T> treevisitor, object param)
       {
           object[] ret = new object[arg.Count];
           for (int i = 0, n = arg.Count; i < n; i++)
           {
               ret[i] = arg[i].Visit(treevisitor, param);
           }
           return ret;
       }
       public static INode<T> Transform<T>(this INode<T> arg, TreeTransformer<T> treetransformer, object param)
       {
           return treetransformer(arg, param, arg.Children.TransformList<T>(treetransformer, param));
       }
       public static INode<T>[] TransformList<T>(this INodeList<T> arg, TreeTransformer<T> treetransformer, object param)
       {
           INode<T>[] ret = new INode<T>[arg.Count];
           for (int i = 0, n = arg.Count; i < n; i++)
           {
               ret[i] = arg[i].Transform(treetransformer, param);
           }
           return ret;
       }

       public static INode<T> Copy<T>(INode<T> arg, object param, INode<T>[] sonreturn)
       {
           Node<T> ret = new Node<T>();
           foreach (Node<T> son in sonreturn)
               ret.Children.Add(son);
           return ret as INode<T>;
       }
       public static object ToTreeNodes<T>(INode<T> arg, object param, object[] sonreturn)
       {
           TreeNode ret = new TreeNode(arg.ToString() + ":" + arg.Value.ToString());
           foreach (object son in sonreturn)
               ret.Nodes.Add(son as TreeNode);
           return ret;
       }
   }
}