=== Expression Tree ===

Побеседуем об Expression. Есть такая штука в .NET и именно благодаря ей .NET поддерживает возможность хранить структуры дерева запросов. Самый тривиальный пример, когда мы создаем, лямбда выражение и оно может быть сохранено в Expression, в результате чего мы имеем возможность анализировать это дерево и на его основе выполнять некие собственные действия. Отличный пример этого Linq to Sql, когда на основе распарсеного Expression строится физический запрос к базе данных. Чтобы свести разговор к некому практическому руслу я предлагаю обсудить возможность добавления поддержки Linq запросов к уже существующим решениям. Возьмем абстрактный пример у нас есть ORM не поддерживающая Linq или мы работаем с библиотекой поддержка Linq в которой не предусмотрена, но писать Linq запросы ну очень хочется. Как быть? Можно попробовать реализовать разбор синтаксического дерева и функционал который Вы получите в замен зависит наверное только от ваших возможностей и надобностей Вашего приложения. Не так давно в Nhibernate появилась поддержка трансляции Linq запросов в запросы к базе данных. Авторами проэкта было принято решение транслировать Linq запросы в уже существующие к тому моменту в NHIbernate Criteria API. Конечно же Linq предоставляет несколько более богатые возможности, но и такое решение выглядит довольно цельным. Почему я заговорил об Nhibernate? Потому, что я хочу предложить Вам попробовать самостоятельно сделать несколько шагов в написании собственного кода по трансляции Expression в некое другое API для построения запросов. Я же знаю Criteria API достаточно хорошо, что бы показать на практике направление в котором можно двигаться в своем собственном проекте.
Нашей конечной целью будет достижение следующий задачи:
<code csharp>
Expression<Func<Message, bool>> lambda = m =>
                    (m.Id > 0 && m.Id < 15) ||
                    m.FirstName.StartsWith("J") ||
                    m.LastName == "Blog";
 
                    var transformer = new ExpressionTransformer<Message>();
                    DetachedCriteria criteria = transformer.Transform(lambda);
 
                    var result = criteria.GetExecutableCriteria(session).List<Message>();
</code>
В первой строчке мы создаем дерево, далее парсим его с помощью некого класса преобразователя получая на выходе DetachedCriteria, которая может быть использована для выполнения запроса к БД. Более глобально мы могли бы иметь в своем репозитории обощенный метод наподобии List<T> FindAll(Func<T, bool> clause); (или Where) Который бы без сомнения был бы полезен в приложении, более того на мой субъективный взгляд он был бы удобней чего то вроде List<T> FindAll(DetachedCriteria clause);
Начнем с того, что лямбда выражение в первой строчке может быть легко присвоено соответствующему делегату, без каких либо изменений. Соль кода выше как раз и заключается в том, что структура нашего лямбда выражения будет сохранена в объекте Expression, а соответственно будет доступна и для разбора нашим парсером. Ниже пример с использованием делегата.
<code csharp>
Func<Message, bool> lambda =  m =>
                    (m.Id > 0 && m.Id < 15) ||                    
                    m.FirstName.StartsWith("J") ||
                    m.LastName == "Blog";
</code>
Прежде чем мы приступим к написанию парсера, я хочу сказать, что за один вечер не в состоянии написать полноценный парсер на все случаи жизни, но даже предложенный мной вариант будет уметь очень много. Он будет поддерживать возможности использования всех операций сравнения с невычисляемыми выражениями, в не зависимости от того в какой части распологается константа в правой или левой. Также он будет поддерживать логические выражения Or и And и будет иметь ограниченную поддержку обработки вызовов методов. В примере мы реализуем возможность использования Contains, StartsWith и EndWith для строк. Все остальное вы сможете добавить и сами, но думаю, что большей частью для Nhibernate это уже реализовано, а в Вашей системе Вы реализуете именно то, что Вам будет нужно, главное понять принцип.
Я уже не раз писал, что Expression не более чем дерево. В добавок к этому каждый узел этого дерева имеет собственный NodeType. А посему стратегия реализации лежит в том, что нам нужно обойти это самое дерево и если оно содержит ноды которые мы можем обработать, то обработать их и предложить механизм аккумуляции результата в виде объекта DetachedCriteria.
С одной стороны задача может показаться простой нужно просто обойти дерево, но с другой по достижению некоторого конечного узла, нам нужно выполнить некоторое действие. Первой моей мыслью было сделать так, что бы каждый метод возвращал объект реализующий Icriterion, собирая которые в кучу можно построить Criteria Query. Но соль в том, что некоторые узлы дерева содержат только значение или имя свойства. Давайти рассмотрим пример:
<code csharp>
m => m.Id > 0;
</code>
Следующие дерево будет представлять из себя не замысловатую конструкцию в корне которой тип узла Lambda (мы ведь сохранили в дереве лямбда выражение) тело корня будет представлять собой тип GreateThan (>) c двумя потомками первый MemberAccess (m.Id), а второй Constant (0).
Для построения DetacheCriteria нужно было бы написать следующий код:
<code csharp>
detachedCriteria.Add(Restrictions.Gt("Id", 0));
</code>
Метод Add принимает Criterion, а следовательно нет проблем преобразовать верхний уровень иерархии, но как в него поместить парамметры "Id", 0?
Которые нам прийдется обрабатывать ниже по дереву? Соответственно идея предоставить единый интерфейсс преобразования каждому узлу терпит крах еще не начав реализовываться. Разрабатывать несколько интерфейссов для «вечернего» примера я счел накладным, а потому ограничелся тем, что каждый обрабатываемый узел имеет возможность использовать общий стек для передачи всей необходимой информации.
<code csharp>
public class NodeValue
    {
        public ICriterion Criterion { get; set; }
        public string Name { get; set; }
        public object Value { get; set; }
    }
 
private readonly Stack<NodeValue> _stack = new Stack<NodeValue>();
</code>
Прежде чем продолжить давайте рассмотрим класс NodeValueи упомянем все типы узлов, что мы будем рассматривать:
<code>
ExpressionType.AndAlso
ExpressionType.OrElse
ExpressionType.Equal
ExpressionType.NotEqual
ExpressionType.GreaterThan
ExpressionType.GreaterThanOrEqual
ExpressionType.LessThan
ExpressionType.LessThanOrEqual 
ExpressionType.MemberAccess
ExpressionType.Constant
ExpressionType.Call
ExpressionType.Lambda
</code>
Все за исключением последних четырех для сохранения результатов своей работы будут использовать свойство Criterion. MemberAccess будет сохранять полученное из узла значение в Name, а Constant в Value. Вот таким не замысловатым способом мы организуем хранение обработанных в узлах данных. Почему именно все кроме последних четырех? Да потому, что все эти операции в NHibernate Criteria API создают критерион, а вот последние либо устанавливаются явно как в примере выше, либо задаются путем IProjection, а обращение к методам может генерировать специальный критерион которому передаются все те же параметры в виде имени поля и его значения.

Что бы как то унифицировать свою работу я объявил словарь, где типу обрабатываемого узла соответствует делегат обработчика узла (метод берущий данные из стека, помещающий их туда, а также выполняющий всю необходимую работу по разбору узла Expression).
<code csharp>
private readonly Dictionary<ExpressionType, Action<Expression>> _expressionNodeHandlers =
            new Dictionary<ExpressionType, Action<Expression>>();
</code>
Конструктор ExpressionTransformer
<code csharp>
public ExpressionTransformer()
        {
            _expressionNodeHandlers.Add(ExpressionType.AndAlso, AndAlsoProccess);
            _expressionNodeHandlers.Add(ExpressionType.OrElse, OrElseProccess);
            _expressionNodeHandlers.Add(ExpressionType.Equal, EqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.NotEqual, NotEqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.GreaterThan, GreaterThanProccess);
            _expressionNodeHandlers.Add(ExpressionType.GreaterThanOrEqual, GreaterThanOrEqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.LessThan, LessThanProccess);
            _expressionNodeHandlers.Add(ExpressionType.LessThanOrEqual, LessThanOrEqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.MemberAccess, MemberAccessProccess);
            _expressionNodeHandlers.Add(ExpressionType.Constant, ConstantProccess);
            _expressionNodeHandlers.Add(ExpressionType.Call, CallProccess);
            _expressionNodeHandlers.Add(ExpressionType.Lambda, LambdaProccess);
        }
</code>
Не сложно догадаться, что нам понадобятся методы: AndAlsoProccess, OrElseProccess …
Я объясню реализацию основных методов, ниже же будет приведен полностью исходный код класса.
<code csharp>
public void AndAlsoProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
 
            AbstractCriterion and = Restrictions.And(op1.Criterion, op2.Criterion);
            var op = new NodeValue {Criterion = and};
            _stack.Push(op);
        }
</code>
И так в какой то момент наш парсер сталкивается с узлом имеющим тим AndAlso. На самом деле это ничто иное как оператор && в лямбде. Согласно структуре Expression такой узел имеет двух потомков, собственно то, что стоит справа и слева от оператора. Следовательно нам нужно разделить выражение на две части и обработать каждую из них, после чего взять со стека пару значений и достать нужные нам критерионы. Далее мы на их основе формируем единый критерион объединяющий их в единое целое по условию and и сохраняем его на вершине стека делая доступным вышележащему коду.

Проверка на равенство:
<code csharp>
public void EqualProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
 
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
            AbstractCriterion criterion = Restrictions.Eq(op1.Name ?? op2.Name, op1.Value ?? op2.Value);
            var op = new NodeValue { Criterion = criterion };
            _stack.Push(op);
        }
</code>
Все также в лямбда имеем два операнда (m.Id == 5). Обрабатываем их и снимаем со стека значение имени параметра и собственно его значение, формируем критерион размещая его на стеке. 
<code csharp>
AbstractCriterion criterion = Restrictions.Eq(op1.Name ?? op2.Name, op1.Value ?? op2.Value);
</code>
Чтобы понять, что делает этот код достаточно вспомнить, что мы можем записать лямбду как => m.Id = 5 так и 5 = m.Id. Соответственно на стеке значение и имя свойства могут находиться в разном порядке после обработки в соответствующих узлах. Стоит заметить, что код реализации все равно не является универсальным т.к. делается явное предположение, что ниже по дереву вызова всегда будут находиться узлы Constannt и MemberAccess. Более интеллектуальная реализация вероятно требует того, что кроме значений в стеке хранить еще и тип узла помещающего значение на стек. Тогда обработчик может точно знать, что содержится на стеке. Мне это кажется более оптимальным вариантом, чем анализировать свойства установленные в NodeValue.
<code csharp>
public void MemberAccessProccess(Expression expression)
        {
            var member = (MemberExpression)expression;
 
            var op = new NodeValue { Name = member.Member.Name };
            _stack.Push(op);
        }
 
        public void ConstantProccess(Expression expression)
        {
            var constant = (ConstantExpression)expression;
 
            var op = new NodeValue { Value = constant.Value };
            _stack.Push(op);
        }
</code>
Тут вроде просто мы вытаскиваем значение свойства в одном случае и его имя в другом. Для примера m => m.Id > 0 левая часть это MemberAccess - m.Id, а правая Constant - 0.
Для поддержки трансформации методов:
<code csharp>
public void CallProccess(Expression expression)
        {
            var ex = (MethodCallExpression)expression;
            var memberExpression = (MemberExpression)ex.Object;
            var constantExpression = (ConstantExpression)ex.Arguments[0];
 
            if (ex.Method.Name == "Contains")
            {
                var op = new NodeValue
                             {
                                 Criterion =
                                     Restrictions.Like(memberExpression.Member.Name,
                                                       "%" + constantExpression.Value + "%")
                             };
                _stack.Push(op);
            }
            else
            if (ex.Method.Name == "StartsWith")
            {
                var op = new NodeValue
                {
                    Criterion =
                        Restrictions.Like(memberExpression.Member.Name,
                                          constantExpression.Value + "%")
                };
                _stack.Push(op);
            }
            else
            if (ex.Method.Name == "EndsWith")
            {
                var op = new NodeValue
                {
                    Criterion =
                        Restrictions.Like(memberExpression.Member.Name,
                                          "%" + constantExpression.Value)
                };
                _stack.Push(op);
            }
            else
                throw new ArgumentException("Tree contains invalid structure");
        }
</code>
Мы поддерживаем только три метода, которые легко могут быть преобразованы в Like через Criteria API. Стоит заметить, что в данной реализации, тоже неявно предполагается, что метод содержит единственный аргумент, а также, что аргумент представляет собой константное выражение. Думаю, что те кому нужно поняв основной принцип реализуют дополнительный разбор без всяких проблем.

Полный пример:
<code csharp>
public class NodeValue
    {
        public ICriterion Criterion { get; set; }
        public string Name { get; set; }
        public object Value { get; set; }
    }
 
    public class ExpressionTransformer<T>
    {
        private readonly Stack<NodeValue> _stack = new Stack<NodeValue>();
 
        public NodeValue CurrentNodeValue
        {
            get { return _stack.Peek(); }
        } 
 
        public void AndAlsoProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
 
            AbstractCriterion and = Restrictions.And(op1.Criterion, op2.Criterion);
            var op = new NodeValue {Criterion = and};
            _stack.Push(op);
        }
 
        public void OrElseProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
 
            AbstractCriterion or = Restrictions.Or(op1.Criterion, op2.Criterion);
            var op = new NodeValue { Criterion = or };
            _stack.Push(op);
        }
 
 
        public void EqualProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
 
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
            AbstractCriterion criterion = Restrictions.Eq(op1.Name ?? op2.Name, op1.Value ?? op2.Value);
            var op = new NodeValue { Criterion = criterion };
            _stack.Push(op);
        }
 
        public void NotEqualProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
 
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
            AbstractCriterion criterion = Restrictions.Not(Restrictions.Eq(op1.Name ?? op2.Name, op1.Value ?? op2.Value));
            var op = new NodeValue { Criterion = criterion };
            _stack.Push(op);
        }
 
 
        public void GreaterThanProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
 
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
            if (op1.Name == null && op2.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Gt(op2.Name, op1.Value);
                var op = new NodeValue { Criterion = criterion };
                _stack.Push(op);
            }
            else if (op2.Name == null && op1.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Lt(op1.Name, op2.Value);
                var op = new NodeValue { Criterion = criterion };
                _stack.Push(op);
            }
        }
 
        public void GreaterThanOrEqualProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
 
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
            if (op1.Name == null && op2.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Ge(op2.Name, op1.Value);
                var op = new NodeValue { Criterion = criterion };
                _stack.Push(op);
            }
            else if (op2.Name == null && op1.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Le(op1.Name, op2.Value);
                var op = new NodeValue { Criterion = criterion };
                _stack.Push(op);
            }
        }
 
 
        public void LessThanProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
 
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
 
            if (op1.Name == null && op2.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Lt(op2.Name, op1.Value);
                var op = new NodeValue {Criterion = criterion};
                _stack.Push(op);
            }else if(op2.Name == null && op1.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Gt(op1.Name, op2.Value);
                var op = new NodeValue { Criterion = criterion };
                _stack.Push(op);
            }
        }
 
        public void LessThanOrEqualProccess(Expression expression)
        {
            var binary = (BinaryExpression)expression;
 
            Proccess(binary.Left);
            Proccess(binary.Right);
 
            var op1 = _stack.Pop();
            var op2 = _stack.Pop();
            if (op1.Name == null && op2.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Le(op2.Name, op1.Value);
                var op = new NodeValue { Criterion = criterion };
                _stack.Push(op);
            }
            else if (op2.Name == null && op1.Value == null)
            {
                AbstractCriterion criterion = Restrictions.Ge(op1.Name, op2.Value);
                var op = new NodeValue { Criterion = criterion };
                _stack.Push(op);
            }
        }
 
        public void MemberAccessProccess(Expression expression)
        {
            var member = (MemberExpression)expression;
 
            var op = new NodeValue { Name = member.Member.Name };
            _stack.Push(op);
        }
 
        public void ConstantProccess(Expression expression)
        {
            var constant = (ConstantExpression)expression;
 
            var op = new NodeValue { Value = constant.Value };
            _stack.Push(op);
        }
 
        public void CallProccess(Expression expression)
        {
            var ex = (MethodCallExpression)expression;
            var memberExpression = (MemberExpression)ex.Object;
            var constantExpression = (ConstantExpression)ex.Arguments[0];
 
            if (ex.Method.Name == "Contains")
            {
                var op = new NodeValue
                             {
                                 Criterion =
                                     Restrictions.Like(memberExpression.Member.Name,
                                                       "%" + constantExpression.Value + "%")
                             };
                _stack.Push(op);
            }
            else
            if (ex.Method.Name == "StartsWith")
            {
                var op = new NodeValue
                {
                    Criterion =
                        Restrictions.Like(memberExpression.Member.Name,
                                          constantExpression.Value + "%")
                };
                _stack.Push(op);
            }
            else
            if (ex.Method.Name == "EndsWith")
            {
                var op = new NodeValue
                {
                    Criterion =
                        Restrictions.Like(memberExpression.Member.Name,
                                          "%" + constantExpression.Value)
                };
                _stack.Push(op);
            }
            else
                throw new ArgumentException("Tree contains invalid structure");
        }
 
 
        public void LambdaProccess(Expression expression)
        {
            var lambda = (LambdaExpression)expression;
            Proccess(lambda.Body);
        }
 
 
        private readonly Dictionary<ExpressionType, Action<Expression>> _expressionNodeHandlers =
            new Dictionary<ExpressionType, Action<Expression>>();
 
        public ExpressionTransformer()
        {
            _expressionNodeHandlers.Add(ExpressionType.AndAlso, AndAlsoProccess);
            _expressionNodeHandlers.Add(ExpressionType.OrElse, OrElseProccess);
            _expressionNodeHandlers.Add(ExpressionType.Equal, EqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.NotEqual, NotEqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.GreaterThan, GreaterThanProccess);
            _expressionNodeHandlers.Add(ExpressionType.GreaterThanOrEqual, GreaterThanOrEqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.LessThan, LessThanProccess);
            _expressionNodeHandlers.Add(ExpressionType.LessThanOrEqual, LessThanOrEqualProccess);
            _expressionNodeHandlers.Add(ExpressionType.MemberAccess, MemberAccessProccess);
            _expressionNodeHandlers.Add(ExpressionType.Constant, ConstantProccess);
            _expressionNodeHandlers.Add(ExpressionType.Call, CallProccess);
            _expressionNodeHandlers.Add(ExpressionType.Lambda, LambdaProccess);
        }
 
        protected void Proccess(Expression expression)
        {
            _expressionNodeHandlers[expression.NodeType](expression);
        }
 
        public DetachedCriteria Transform(Expression<Func<T, bool>> root)
        {
            Proccess(root);
            DetachedCriteria criteria = DetachedCriteria.For(typeof(T));
            criteria.Add(CurrentNodeValue.Criterion);
            return criteria;
        }
    }
</code>
Написав не так много кода, мы имеем возможность преобразовывать наше дерево в Criteria API, конечно разобран только частный случай, но даже он показывает насколько большого результата можно добиться. Надеюсь те из Вас, кто задумывается о добавлении поддержки Linq в свое существующие API, получили отличный пример для старта, поняв работу которого можно без труда двигаться в направлении написания собственного полноценного провайдера (конечно после прочтения статей описывающих необходимые интерфейсы)или ограничится добавлением базовой функциональности по аналогии с вышеприведенным примером.

До новых встреч :-)