В этой статье, на примере простых логических выражений, будет показано, что такое абстрактное синтаксическое дерево и что с ним можно делать. Так же будет рассмотрена альтернатива выражениям LINQ для выполнения запросов к SQL базам данных.
История из жизни разработчика
Это был какой-то легаси проект, и меня попросили улучшить его «расширенные» возможности фильтрации.
Раньше у них было что-то вроде этого:
А хотели они что-то такое:
Процедура, которая выполняла «расширенный» поиск выглядела примерно так:
CREATE PROCEDURE dbo.SomeContextUserFind
(@ContextId int, @Filter nvarchar(max)) AS
BEGIN
DECLARE @sql nvarchar(max) =
N'SELECT U.UserId, U.FirstName, U.LastName
FROM [User] U
INNER JOIN [SomeContext] [C]
ON ....
WHERE [C].ContextId = @p1 AND ' + @Filter;
EXEC sp_executesql
@sql,
N'@p1 int',
@p1=@ContextId
ENDи код, генерировавший строку фильтра, выглядел примерно так:
string BuildFilter(IEnumerable<FilterItem> items)
{
var builder = new StringBuilder();
foreach (var item in items)
{
builder.Append(item.Field);
bool isLike = false;
switch (item.Operation)
{
case Operation.Equals:
builder.Append(" = ");
break;
case Operation.Like:
isLike = true;
builder.Append(" LIKE ");
break;
//...
}
builder.Append('\'');
if (isLike)
builder.Append('%');
builder.Append(Escape(item.Value));
if (isLike)
builder.Append('%');
builder.Append('\'');
}
return builder.ToString();
}Конечно, это не лучший код, который вы когда-либо видели, но, к сожалению, легаси проекты (или даже еще не легаси) часто полны таких вещей. В любом случае, что есть, то есть, и это нужно как-то улучшать.
Первая мысль, которая пришла мне в голову, — это просто добавить больше полей в «FilterItem» и усложнить логику построения фильтра, но я быстро понял, что это дорога в никуда ведь поддерживать такой код будет чрезвычайно сложно, и я бы никогда не смог не достичь желаемой функциональности.
В этот момент я вспомнил про «абстрактное синтаксическое дерево», которое, очевидно, является лучшим выбором в данном случае, и далее я объясню, что это такое и как оно помогает.
Абстрактное синтаксическое дерево
Во-первых, давайте проанализируем строки фильтра, которые мы собираемся генерить, например вот эту:
[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Doe')И здесь мы можем заметить некоторую структуру:
Эта структура представляет собой дерево, и это означает, что мы можем создать несколько простых классов, которые будут ее описывать:
abstract class Expr
{ }
class ExprColumn : Expr
{
public string Name;
}
class ExprStr : Expr
{
public string Value;
}
abstract class ExprBoolean : Expr
{ }
class ExprEqPredicate : ExprBoolean
{
public ExprColumn Column;
public ExprStr Value;
}
class ExprAnd : ExprBoolean
{
public ExprBoolean Left;
public ExprBoolean Right;
}
class ExprOr : ExprBoolean
{
public ExprBoolean Left;
public ExprBoolean Right;
}Используя классы, мы можем создать объект, который будет представлять исходный фильтр:
var filterExpression = new ExprAnd
{
Left = new ExprEqPredicate
{
Column = new ExprColumn
{
Name = "FirstName"
},
Value = new ExprStr
{
Value = "John"
}
},
Right = new ExprOr
{
Left = new ExprEqPredicate
{
Column = new ExprColumn
{
Name = "LastName"
},
Value = new ExprStr
{
Value = "Smith"
}
},
Right = new ExprEqPredicate
{
Column = new ExprColumn
{
Name = "LastName"
},
Value = new ExprStr
{
Value = "Doe"
}
}
}
};На самом деле, эта структура, называемая «абстрактным синтаксическим деревом», может использоваться и для представления более сложных запросов, но все они будут иметь один «корень», ссылка на который может храниться в одном объекте.
«Абстрактное синтаксическое дерево» — это результат синтаксического анализа (или парсинга) фразы некоторого формального языка (в нашем случае языка логических выражений) с определенными синтаксическими правилами. Такие правила имеют устоявшийся формат записи. Например, правила нашего простого языка (подмножество логических выражений) могут быть записаны как:
<eqPredicate> ::= <column> = <str>
<or> ::= <eqPredicate>|or|<and> OR <eqPredicate>|or|<and>
<and> ::= <eqPredicate>|(<or>)|<and> AND <eqPredicate>|(<or>)|<and>Примечание: «Абстрактное» означает, что синтаксис не описывает все детали языка, например, группирующие скобки, лишние пробелы и т. д.
Парсинг — огромная тема сама по себе, и сейчас это не так важно, поскольку у нас уже есть готовые синтаксические деревья, поэтому давайте сосредоточимся на том, что мы можем с ними делать.
Генерация SQL кода
Очевидно, что наиболее важной задачей для нас является преобразование синтаксического дерева обратно в текст, и у нас есть несколько способов сделать это.
Первый способ — использовать сопоставление с образцом (Pattern Matching), что довольно просто:
var filterExpression = ...;
StringBuilder stringBuilder = new StringBuilder();
Match(filterExpression);
void Match(Expr expr)
{
switch (expr)
{
case ExprColumn col:
stringBuilder.Append('[' + Escape(col.Name, ']') + ']');
break;
case ExprStr str:
stringBuilder.Append('\'' + Escape(str.Value, '\'') + '\'');
break;
case ExprEqPredicate predicate:
Match(predicate.Column);
stringBuilder.Append('=');
Match(predicate.Value);
break;
case ExprOr or:
Match(or.Left);
stringBuilder.Append(" OR ");
Match(or.Right);
break;
case ExprAnd and:
ParenthesisForOr(and.Left);
stringBuilder.Append(" AND ");
ParenthesisForOr(and.Right);
break;
}
}
void ParenthesisForOr(ExprBoolean expr)
{
if (expr is ExprOr)
{
stringBuilder.Append('(');
Match(expr);
stringBuilder.Append(')');
}
else
{
Match(expr);
}
}В результате в билдере будет следующая строка:
[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Joe')Вроде это то, что нам нужно!
"Посетитель"
Хоть мне и нравится функциональное программирование, но в этом случае объектно-ориентированный подход может обеспечить более эффективное решение — я говорю о шаблоне «Посетитель (Visitor)». Идея этого шаблона заключается в том, что мы не пытаемся определить тип объекта, а даем ему список всех возможных действий (в виде интерфейса), и объект сам выбирает действие, наиболее подходящее для его типа. Давайте определим это список:
interface IExprVisitor
{
void VisitColumn(ExprColumn column);
void VisitStr(ExprStr str);
void VisitEqPredicate(ExprEqPredicate eqPredicate);
void VisitOr(ExprOr or);
void VisitAnd(ExprAnd and);
}И любой объект (нашей структуры) может сделать выбор:
abstract class Expr
{
public abstract void Accept(IExprVisitor visitor);
}
class ExprColumn : Expr
{
public string Name;
public override void Accept(IExprVisitor visitor)
=> visitor.VisitColumn(this);
}
class ExprStr : Expr
{
public string Value;
public override void Accept(IExprVisitor visitor)
=> visitor.VisitStr(this);
}
...Теперь мы можем выделить генерацию sql кода в отдельный класс:
class SqlBuilder : IExprVisitor
{
private readonly StringBuilder _stringBuilder
= new StringBuilder();
public string GetResult()
=> this._stringBuilder.ToString();
public void VisitColumn(ExprColumn column)
{
this._stringBuilder
.Append('[' + Escape(column.Name, ']') + ']');
}
public void VisitStr(ExprStr str)
{
this._stringBuilder
.Append('\'' + Escape(str.Value, '\'') + '\'');
}
public void VisitEqPredicate(ExprEqPredicate eqPredicate)
{
eqPredicate.Column.Accept(this);
this._stringBuilder.Append('=');
eqPredicate.Value.Accept(this);
}
public void VisitAnd(ExprAnd and)
{
and.Left.Accept(this);
this._stringBuilder.Append(" AND ");
and.Right.Accept(this);
}
public void VisitOr(ExprOr or)
{
ParenthesisForOr(or.Left);
this._stringBuilder.Append(" OR ");
ParenthesisForOr(or.Right);
}
void ParenthesisForOr(ExprBoolean expr)
{
if (expr is ExprOr)
{
this._stringBuilder.Append('(');
expr.Accept(this);
this._stringBuilder.Append(')');
}
else
{
expr.Accept(this);
}
}
private static string Escape(string str, char ch)
{
...
}
}И использовать его следующим образом:
var filterExpression = BuildFilter();
var sqlBuilder = new SqlBuilder();
filterExpression.Accept(sqlBuilder);
string sql = sqlBuilder.GetResult();В результате мы получаем желаемую строку:
[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Joe')Использование шаблона "Посетитель (Visitor)" имеет несколько преимуществ перед сопоставлением с шаблоном. Так, например, выбор конкретных типов всегда является исчерпывающим, поскольку добавление нового типа в структуру всегда приводит к изменению интерфейса IExprVisitor и, как следствие, необходимости расширения всех его реализаций (в противном случае будут ошибки компиляции).
Обход дерева и круглые скобки
В этом алгоритме есть несколько аспектов, на которые следует обратить внимание.
Во-первых, как это вообще работает?
Фактически, здесь мы выполняем обход синтаксического дерева в глубину, и код sql является следом этого обхода:
Таким образом, каким бы сложным ни было наше дерево, мы всегда получим синтаксически правильную строку.
Во-вторых, что происходит со скобками?
Дело в том, что логические выражения имеют определенный порядок вычисления. Операция «И» вычисляется первой, а операция «ИЛИ» — второй. Скобки необходимы для изменения этой последовательности, поскольку любое выражение в скобках имеет более высокий приоритет при вычислении. Но в синтаксическом дереве последовательность оценки задается самой структурой (от ветвей до корня), поэтому отдельный тип для круглых скобок не требуется.
Расширение синтаксиса
В реальности нам конечно понадобятся и другие предикаты, например, “NotEqual”, и чтобы иметь возможность его (предикат) использовать, нам просто нужно добавить новый класс:
class ExprNotEqPredicate : ExprBoolean
{
public ExprColumn Column;
public ExprStr Value;
public override void Accept(IExprVisitor visitor)
=> visitor.VisitNotEqPredicate(this);
}А поскольку у нас есть новый тип, то компилятор сообщает нам, что нам нужно реализовать для него генерацию кода SQL:
public void VisitNotEqPredicate(ExprNotEqPredicate exprNotEqPredicate)
{
exprNotEqPredicate.Column.Accept(this);
this._stringBuilder.Append("!=");
exprNotEqPredicate.Value.Accept(this);
}Итак, мы создали очень простой набор логических предикатов, хотя MS SQL поддерживает гораздо больше, но, как видите, вы можете легко добавить все необходимые языковые структуры.
Кстати, в документации по SQL Server есть все правила синтаксиса SQL, которые весьма полезны для подобного расширения:
Перегрузка операторов
Очевидно, что создание синтаксических деревьев путем вызова конструкторов классов это не самый удобный способ. Однако нам может помочь перегрузка оператора C#. Давайте сделаем следующее:
class ExprColumn : Expr
{
...
public static ExprBoolean operator==(ExprColumn column, string value)
=> new ExprEqPredicate
{
Column = column, Value = new ExprStr {Value = value}
};
public static ExprBoolean operator !=(ExprColumn column, string value)
=> new ExprNotEqPredicate
{
Column = column, Value = new ExprStr {Value = value}
};
}
abstract class ExprBoolean : Expr
{
public static ExprBoolean operator &(ExprBoolean left, ExprBoolean right)
=> new ExprAnd{Left = left, Right = right};
public static ExprBoolean operator |(ExprBoolean left, ExprBoolean right)
=> new ExprOr { Left = left, Right = right };
}Теперь мы можем создать дерево синтаксиса очень простым и понятным способом:
ExprColumn firstName = new ExprColumn{Name = "FirstName"};
ExprColumn lastName = new ExprColumn{Name = "LastName"};
var expr = firstName == "John" & (lastName == "Smith" | lastName == "Doe");
var builder = new SqlBuilder();
expr.Accept(builder);
var sql = builder.GetResult();И результатом будет:
[FirstName]='John' AND ([LastName]='Smith' OR [LastName]='Doe')Примечание: C# не допускает перегрузки операторов && и ||, и в этом есть смысл, поскольку эти операторы прекращают дальнейшее вычисление, если результат уже заранее известен (Например true || ....), но нам нужно вычислить все части для построения синтаксического дерева (результат будет выполняться базой данных SQL).
Что дальше
Кажется, мы решили проблему с фильтрацией, но как насчет сортировки и пейджинга? Также иногда необходимо добавить к оригинальному запросу какой-нибудь под-запрос (View или Derived Table) для фильтрации (или сортировки) по вычисляемым полям.
Не проблема! Давайте просто реализуем весь синтаксис SQL SELECT:
Конечно, вам не нужно делать это самостоятельно, так как есть несколько библиотек (например, моя), где это уже реализовано, поэтому просто рассмотрите этот подход как альтернативный способ взаимодействия с базами данных SQL.
Альтернатива LINQ
То, что мы сделали с перегрузкой операторов, до некоторой степени напоминает выражения LINQ, и на самом деле тут есть некоторые сходства. Компилятор C# генерирует синтаксические деревья, а затем библиотеки, такие как Entity Framework или «LINQ to SQL», преобразуют эти деревья в реальный код SQL.
Основная проблема этого подхода заключается в том, что компилятор генерирует синтаксическое дерево языка C#, а нам то нужен SQL! Отражение императивного C# в декларативный SQL – это не простая задача, а результаты часто непредсказуемы.
Я предпочитаю другой подход — вместо использования синтаксиса C# в качестве основы можно использовать настоящий синтаксис SQL. И вместо компилятора он может использовать перегрузку операторов, методы расширения и различные вспомогательные классы.
При таком подходе, с одной стороны, мы получаем почти такую же гибкость, как если бы мы использовали хранимые процедуры. С другой стороны, у нас строгая типизация, intellisense и бизнес-логика не перемещается в базу данных. И… не нужно каждый раз гуглить, как выполнить LEFT JOIN в LINQ)
Еще одно преимущество заключается в том, что операторы обновления данных (INSERT, UPDATE, DELETE и даже MERGE) также могут быть реализованы таким же образом, и нет необходимости загружать тысячи записей из базы данных для обновления только одного столбца.
Просто пример того, что можно сделать, используя в качестве основы реальный синтаксис SQL (взято отсюда):
await InsertInto(tCustomer, tCustomer.UserId)
.From(
Select(tUser.UserId)
.From(tUser)
.Where(!Exists(
SelectOne()
.From(tSubCustomer)
.Where(tSubCustomer.UserId == tUser.UserId))))
.Exec(database);Заключение
Синтаксическое дерево — это очень мощная структура данных, с которой вы, вероятно, рано или поздно столкнетесь. Возможно, это будут выражения LINQ, или, может быть, вам надо будет создать анализатор Roslyn, или, может быть, вы самостоятельно захотите создать свой собственный синтаксис, как это я сделал несколько лет назад, чтобы провести рефакторинг одного легаси проекта. В любом случае важно понимать эту структуру и уметь с ней работать.
Link to SqExpress — проект, который частично включает код из этой статьи.
alexs0ff
Решал подобную задачу, но я выбрал путь более легкий — вроде это все в рекурсию хорошо ложилось со StringBuilder (что-то отдаленно напоминающий первый вариант ТС).
Плюс для EF linq — очень хорошая библиотека LINQKit с его PredicateBuilder.