Abstract syntax tree

Вступление

Сlang и AST

if (a > b) {print(a);} else { print(b);}

class FindBinaryOperatorVisitor : public clang::RecursiveASTVisitor<FindBinaryOperatorVisitor> { public:bool VisitBinaryOperator(clang::BinaryOperator* BinOp) { std::cout << BinOp->getBeginLoc() << \n;return true;}};

CodeInjector

• лениво применяет предоставленные ему замены исходного кода: сохраняет все пришедшие ему запросы, а затем разом их выполняет в конце обработки файла;
• никак не связан с clang-ом: сам открывает файл на чтение, сам ищет нужные строки и так далее.

arr[1] + arr[2];

ASSERT_SUM(arr[1], arr[2]);

ASSERT_SUM(ASSERT_IOB(arr, 1), ASSERT_IOB(arr, 2));

• arr[1+2] заменяется на ASSERT_IOB(arr, 1 + 2)
• ASSERT_IOB(arr, 1 + 2) заменяется на ASSERT_IOB(arr, ASSERT_SUM(1, 2))
  arr[1 + 2] ~~~~~> ASSERT_IOB(arr, 1 + 2) ~~~~~~> ASSERT_IOB(arr, ASSERT_SUM(1, 2)
  

Функционал

• выход за границы С-шного массива;
• UB в целочисленной арифметике;
• обращение к неинициализированной переменной.

Целочисленная арифметика

int a = INT_MIN, b = -1, z = 0;int test1 = a + b; // overflowint test2 = a * b; // overflowint test3 = a << 5; // lhs is negative => UBint test5 = 5 % z; // % by 0 => UBint test6 = --a; // overflow

template <typename T>ArithmCheckRes checkSum(T Lhs, T Rhs) {  FLT_POINT_NOT_SUPPORTED(T);  if (Rhs > 0 && Lhs > std::numeric_limits<T>::max() - Rhs)    return ArithmCheckRes::OVERFLOW_MAX;  if (Rhs < 0 && Lhs < std::numeric_limits<T>::lowest() - Rhs)    return ArithmCheckRes::OVERFLOW_MIN;  return ArithmCheckRes::SAFE_OPERATION;}

int a = INT_MIN, b = -1;int test = a % b; // -INT_MIN > INT_MAX => UBint test1 = a << 5; // lhs is negative => UBint test2 = 5 << b; // rhs is negative => UBint32_t c = 1, d = 33;int32_t test3 = c << d; // rhs is >= size of c in bits => UBint test4 = 2e9 << c; // test = -294967296, not UBint test5 = 2e9 << (c + 1); // (2e9 << 2) > UINT_MAX => UB

char c = 127;++c;

Однако мы здесь собрались не просто так

Читатель ловит нас за руку, в то время как AST делает нашу работу

Вопреки названию нашего проекта, ub-tester находит не только UB. Мотивацией арифметических проверок были не только ошибки, влекущие за собой обессмысливание всей программы, но и неприметные на первый взгляд источники неожиданных результатов (при этом корректных с точки зрения С++). Поэтому информации о возможности/невозможности UB в операторах инкремента/декремента мало, проверка должна уметь детектировать еще и сужающее неявное преобразование и уметь рассказывать про это пользователю. По этой причине в случае ++ и пришлось дополнительно поработать, чтобы добиться желаемого функционала.


Вывод ub-tester-а на примере с char c = 127; ++c;

Неинициализированные переменные

template <typename T>class UBSafeType final {public:  UBSafeType() : Value_{}, IsInit_{false} {}  UBSafeType(T t) : Value_{t}, IsInit_{true} {}  T assertGetValue_() const;  T& assertGetRef();  T& setValue_(T Val);  private:  T Value_;  bool IsInit_;};

int main() {  int a = 5;  int& b{a};  int c = b++ + (int&)a;  (b = c) = (b);}

Результаты

#include "../../include/UBTester.h"#include <iostream>int main() {  int a, b;  std::cin >> a;    char c = 89;  c = 2 * c; // unsafe conversion    int arr[10];  arr[a] = a; // possible index out of bounds    a = b; // uninit variable}

#include "../../include/UBTester.h"#include <iostream>int main() {  UBSafeType<int> a, b;  std::cin >> ASSERT_GET_REF_IGNORE(a);    UBSafeType<char> c(IMPLICIT_CAST(89, int, char));  ASSERT_SET_VALUE(c, IMPLICIT_CAST(ASSERT_BINOP(Mul, 2, IMPLICIT_CAST(c, char, int), int, int), int, char)); // unsafe conversion    UBSafeCArray<int, 10> arr(ASSERT_INVALID_SIZE(std::vector<int>({10})));  ASSERT_IOB(arr, ASSERT_GET_VALUE(a)) = ASSERT_GET_VALUE(a); // possible index out of bounds    ASSERT_SET_VALUE(a, ASSERT_GET_VALUE(b)); // uninit variable}

Декораторы одна из самых необычных особенностей Python. Это инструмент, который полноценно может существовать только в динамически типизированном, интерпретируемом языке. В первой части статьи мой товарищ Witcher136 показал, как в С++ реализовать наиболее приближенную к эталонной (питоновской) версию декораторов.

Я же расскажу про то, как решил попытаться реализовать декораторы в компилируемом языке программирования, для чего в итоге написал написал собственный небольшой компилятор на Haskell на основе LLVM.

Оглавление

1. Как работают декораторы в Python
2. Haskell и LLVM собственный компилятор
3. Так как же скомпилировать декоратор?

Как работают декораторы в Python

Перед погружением в алгоритм компиляции декораторов, поговорим про реализацию декораторов в питоне, и почему она не может быть в таком же виде воспроизведена в компилируемом языке. Сразу отмечу в данной статье под питоном понимается CPython. Все подкапотные детали относятся только к нему.

Декораторы могут изменять сигнатуры функций, к которым применяются, менять собственный результат в зависимости от параметров, известных только во время исполнения, и так далее все это слабо соотносится с представлениями о поведении функций в компилируемых, статически типизированных языках.

Как работают декораторы в Python, в общем-то интуитивно понятно любому человеку, знакомому с этим языком:

Функции decorator, принимающей другую функцию как свой аргумент func, в момент применения декоратора в качестве данного аргумента передается декорируемая функция old. Результатом является новая функция new и с этого момента она привязывается к имени old

def decorator(func):    def new(*args, **kwargs):        print('Hey!')        return func(*args, **kwargs)    return new@decoratordef old():    pass# old() выведет "Hey!" - к имени old теперь приязан вызов new

Это вполне логичное и простое объяснение и, в общем-то, верное оно правильно описывает общую концепцию, но есть несколько важных деталей.

Проблема 1. Декораторы это просто функции

Декораторы применяются в рантайме. В примере выше значение decorator может меняться вплоть до самого его использования, например вот так:

name = input('Введите имя декоратора')def first(func):    ...  # тело декоратораdef second (func):    ...  # тело декоратораif name == 'first':    decorator = firstelif name == 'second':    decorator = secondelse:    decorator = lambda f: f   # оставляем функцию в покое@decorator def old():    pass

С точки зрения нашего умозрительного компилятора, значение функции old может поменяться на что угодно в процессе выполнения программы. В некоторых языках (например, C++) замыкания реализованы так, что даже при одинаковой сигнатуре они будут разного типа (из-за разницы в захваченном ими окружении), что не позволит провернуть такой трюк. В Python же каждое замыкание носит всё свое окружение с собой в питоне всё, включая функции, это объекты, так что замыкания "могут себе это позволить", тем более потребление памяти и быстродействие не являются приоритетом для этого языка.

Теоретически, это можно обойти, сделав old указателем на void-функцию, значение которого равно результату применения декоратора, и тогда нам не будет важен его реальный тип однако это низкоуровневый хак, который убивает любые гарантии, даваемые системой типов, и заставляющий программиста самого следить за типами.

С похожей проблемой связана и следующая особенность декораторов, очевидная в контексте Python, но создающая огромные проблемы для статически типизированного языка: сигнатура получившейся после применения декоратора функции может не совпадать с сигнатурой декорируемой функции.

Проблема 2. Python мало интересуют типы

def decorator(func):    def two_args(x, y):        ...    return two_args@decoratordef one_arg(x):    ...

Допустим, наш компилятор научился применять декораторы. Тогда он может просто считать функцию one_arg функцией с таким же возвращаемым значением и аргументами, как и у замыкания внутри декоратора (на которое она заменяется) однако любому, кто будет читать такой код, будет непонятно, почему эта функция имеет такой тип (например, если декоратор "библиотечный" и его исходников нет в коде самого приложения). Кроме того, что если декораторов применено несколько? Тогда понять сигнатуру функции "на глаз" будет очень сложно. Кроме того, для этого декораторы должны применятся на этапе компиляции и от варианта с их применением во время исполнения, где decorator может быть изменяемым указателем на функцию-декоратор, придется отказаться.

Альтернативным решением является проверять на этапе компиляции, что тип замыкания, возвращаемого декоратором, наоборот полностью совпадает с типом декорируемой функции. Но для этого такой язык должен обладать довольно продвинутой системой типов, различающей функции по типу аргументов и возвращаемых значений.

Это также подводит нас к обратной проблеме какой тип должен быть у аргумента декоратора в наших примерах это аргумент с названием func? Чаще всего этот аргумент, представляющий декорируемую функцию, вызвается внутри замыкания значит нам хотелось бы знать хотя бы тип возвращаемого значения, не говоря уже об аргументах. Если мы его строго зафиксируем с помощью объявления func как функции типа A, мы ограничили область применения декоратора функциями типа A. Если же мы и это объявляем как void* func, и предлагаем программисту самому везде приводить нужные типы, то проще писать на питоне.

Один из вариантов выводить тип func автоматически, например с помощью шаблонов так и сделал Witcher136 в предыдущей статье. Однако это не решает проблему с разными сигнатурыми возвращаемых замыканий, а так же делает определения декораторов совершенно нечитаемыми для простых смертных (см. примеры на C++ в предыдущей статье).

Подведем итоги. Реализация декораторов в компилируемом языке создает следующие сложности:

• Тип декорируемой функции какие аргументы принимает декоратор?
• Тип итоговой функции какая сигнатура должна быть у результата работы декоратора?
• Применение на этапе компиляции создает дополнительные ограничения, применение в рантайме уменьшает гарантии, которые компилятор может дать относительно результата (либо требует продвинутой системы типов)

Как видно, все описанные выше проблемы полностью совпадают с основными особенностями Python он интерпретируемый и динамически типизирован. Все рассмотренные теоретические подходы сложны в реализации и имеют множество ограничений, а также обладают одной общей чертой пытаются следовать по пути Python и реализовать декораторы через замыкания из этого же проистекает и большинство проблем с типами.

Пришло время признаться в этом году я защищал дипломную работу по теме "Использование и реализация инструментов метапрограммирования в компилируемых языках", в которой и рассматривал декораторы, как пример инструмента удобного, но в оригинальном виде невозможного в компилируемом языке. В этой работе я предложил собственный вариант их реализации, написав небольшой исследовательский компилятор для демонстрации способа компиляции простых декораторов без использования замыканий.

Про этот компилятор я и расскажу далее.

Haskell и LLVM собственный компилятор

Для создания компилятора я выбрал Haskell, как язык для написания фронтенда, и LLVM в качестве компиляторного бэкенда. Для Haskell есть замечательная библиотека llvm-hs, предоставляющая все необходимые биндинги к LLVM. В поставку самого языка также входит библиотека Parsec, предназначенная для создания парсеров, путем комбинации различных парсер-функций этой библиотеки (я думаю, что на этом моменте читатель догадался, что Parsec сокращение от parser combinators).

Я опущу описание синтаксиса получившегося языка, который я окрестил Grit, и всех его тривиальных деталей (язык достаточн похож на Си, чтоб не требовать лишних пояснений, по крайней мере по части синтаксиса) остановимся подробно только на интересных его особенностях. Исходный код компилятора можно найти здесь.

Grit expression-oriented (фразированный) язык

Любое выражение в Grit, будь то сложение, блок кода или if-else, возвращает результат, который можно использовать внутри любого другого выражения например, присвоить переменной или передать функции как аргумент.

int main() = {    int i = 0;    i = i + if(someFunction() > 0) {        1;    }    else {        0;    };};

В данном примере, i будет равен 1, если функция someFunction вернет положительное значение, и нулю, если вернется 0 или меньше.

Нет ключевого слова return

Функции в данном языке возвращают либо результат последнего выражения в своем теле, либо значение (на момент выхода из функции) специально указанной переменной.

Это обсуловлено тем, что язык фразированный тело функции это блок кода, который является валидным выражением Grit, а значит он уже должен возвращать значение я решил, что разумнее всего сделать этим значением результат последнего выражения в блоке. А ключевое слово returns, описанное в примерах ниже просто синтаксический сахар, эквивалентный выражению переменная; в конце блока.

Обратите внимание, что поскольку блок кода является выражением, то тело функции как бы "присваивается" ей же после объявления сигнатуры функции идет знак "равно", затем блок кода и в конце точка с запятой такой же синтаксис, как у обычной операции присваивания.

int simple(int x) = {    /*       Данная фукция вернет результат сложения      своего аргумента x и переменной y    */    int y = someOtherFunction();    x + y;};/*  Для функций, состоящих из одного выражения, фигурные скобки можно опустить.  Эта функция вернет свой аргумент, увеличенный на единицу*/int incr(int x) = x + 1;int main() returns statusCode {    /*      В объявлении функции с помощью ключевого слова returns      можно указать название переменной, значение которой      будет возвращено после окончания работы функции.      Это переменная будет "объявлена" автоматически      с таким же типом, как у возвращаемого значения функции    */    int statusCode = 0;    int result = someFunction();    if (someFunction < 0) {        statusCode = 1;    };};

Auto компилятор Grit обладает базовой возможностью выведения типов

В языке Grit есть ключевое слово auto, означающее, что тип переменной (или функции) должен быть выведен автоматически.

Механизм вывода самый банальный для переменных это тип значения выражения, которе им присваивается. Если присваивается результат арифметической операции компилятор попытается вывести тип в зависимости от этой операции для деления это будет число с плавающей точкой, для сложения тип будет зависить от операндов и т.д.
Тип функции будет выведен такой же, как у последнего выражения в ее теле или переменной, указанной в returns.

auto half (int x) = x / 2;   // для функции incr будет выведен тип float

Фразированность (expression-oriented), отсутствие return из произвольного места (тело функции тоже выражение) и базовое выведение типов это самые интересные для нас особенности Grit. Я выделил их потому, что они напрямую используются в реализации декораторов в этом языке.

Если вам интересно внутреннее устройство языка, то сообщите об этом в комментариях, и я постараюсь написать отдельную статью про это.

А для нас теперь пришло время наконец ответить на главный вопрос этой серии статей как скомпилировать декоратор?

Так как же скомпилировать декоратор?

Как было указано ранее, при разработке декораторов для компилируемого языка программирования, нужно определиться с двумя вещами будут они применяться в runtime или compile-time, и как определять типы аргументов и результата итоговой функции.

В своем компиляторе, я разработал механизм применения декораторов, решающий эти проблемы, хоть и создающий некоторые другие ограничения результат получился достаточно интересным, чтобы поделиться им с аудиторией Хабра.

Во-первых, декораторы в Grit применяются на этапе компиляции это позволяет, после перестройки синтаксического дерева (оно же AST, abstract syntax tree), вывести тип возвращаемого значения и скопировать объявления аргументов. Во-вторых, декораторы не являются функциями, а лишь похожими на них конструкциями.

Посмотрим на конкретный пример и разберемся, как данный способ объявления декораторов решает указнные в первой части статьи проблемы:

@auto flatten = {    auto result = @target;    if (result < 0) {        0;    }    else {         result;    };};

Это декоратор, который вызовет исходную функцию, и вернет 0, если ее результат меньше 0, иначе он вернет результат без изменений.

@auto flatten объявление декоратора с именем flatten и типом @auto то есть тип будет выведен в зависимости от функции, к которой он применен (@ указатель но то, что это объявление декоратора, а не функции).

Аргументов у декоратора нет. Это не функция, и толку в аргументах в объявлении декоратора было бы немного у них могут быть разные имена и типы, в зависимости от функций, к которым он применяется, так что нет никаких очевидных способов использовать их.

Вы наверняка уже обратили внимание на необычную метку в теле декоратора @target. Это указание компилятору на то, что в это место надо вставить целиком тело декорируемой функции. Аргументы функции будут скопированы как аргументы для данного инстанса декоратора (что на уровне синтаксического дерева превращает его в новую функцию), а блок кода, являющийся телом исходной функции, вернет свой результат в место вызова, поскольку язык фразированный (этот механизм был описан ранее).
Таким образом, подобное изменение AST эквивалентно вызову исходной функции на месте @target, с правильными аргументами. После этого, исходную функцию можно просто заменить получившейся новой функцией, и все декоратор применен. Если же декораторов у функции несколько, то этот процесс можно повторять несколько раз.

@auto lockFunction = {    mutex.lock();    @target};

@auto optional = if (checkCondition()) {    @target;}else {    someDefaultValue;};

Рассмотрим этот механизм на примере сгенерированного компилятором Grit синтаксического дерева для простой программы с декораторами:

@auto flatten = {    auto result = @target;    if (result < 0) {        0;    }    else {         result;    };};@flattenint incr(int x) = x+1;

Здесь уже рассмотренный нами декоратор flatten применяется к функции, увеличивающей свой аргумент на единицу.

Так выглядит "сырое" внутреннее представление, до какой-либо обработки вообще:

Decorator "flatten" auto {  BinaryOp = (Def auto "result") (DecoratorTarget)  If (BinaryOp < (Var "result") (Int 0)) {    Int 0  }  else {    Var "result"  }}Function "incr" int ; args [Def int "x"] ; modifiers [Decorator "flatten"] ; returns Nothing {  BinaryOp + (Var "x") (Int 1)}

Не вдаваясь в конкретные обозначения, сразу видно две вещи определение декоратора это самостоятельная конструкция с типом Decorator, и функция incr на данном этапе существует в своем исходном виде, и хранит информацию о том что к ней применен модификатор Decorator "flatten". В теле декоратора же мы видим метку DecoratorTarget сюда будет вставленно тело функции incr.

Структура программы проходит внутри компилятора несколько этапов обработки, перед тем как происходит кодогенерация первый из них это применение декораторов. Таким образом, после того как синтаксическое дерево функции будет модифицированно с учетом декораторов, реализация большей части их функционала произойдет автоматически, с помощью "встроенных" средств языка вывода типов, получения результата выполнения блока кода как обычного выражения и так далее.

Посмотрим на аннотированное, полностью обработанное и готовое к кодогенерации предсавление той же программы:

Function (int -> int) incr ["x"] {  BinaryOp i= (Def int "result") (    Block int {      BinaryOp i+ (Var int "x") (int 1)    }  )  If int (BinaryOp b< (Var int "result") (int 0)) {    int 0  }  else {    Var int "result"  }}

Здесь мы можем заметить несколько важных вещей:

• Определение декоратора было удалено после его применения на этапе обработки AST, он больше не нужен.
• Тело функции incr изменилось теперь оно такое же, каким было тело декоратора flatten, но на месте DecoratorTarget теперь Block {...} выражение вида "блок кода", совпадающее с исходным телом функции. Внутри этого выражения есть обращения к аргументам функции, и оно возвращает то же значение, которое вернула бы исходная функция это значение присваивается новой переменной int "result", с которой декоратор и работает дальше. BinaryOp i= это операция присваивания int-а, но в исходном коде тип result был указан как auto значит тип возвращаемого значения и переменных в теле функции, работающих с ним, был выведен правильно.

Таким образом, в процессе разработки этого компилятора, удалось вывести общий алгоритм применения декораторов для компилируемого, статически типизированного языка. Он не обладает всеми возможностями декораторов в Python, но приближается к ним настолько, насколько это возможно в таком языке, как Grit.

Разумеется, это не окончательная и не идеальная версия например, таким декораторам можно было бы добавить собственные, декораторные аргументы:

@auto lockF(mutex M) {    M.lock();    @target;};@lockF(мьютексКоторыйФункцияДолжнаЗахватить)int someFunction(...)

Это вполне сработало бы при текущем подходе самый простой вариант это при применении декоратора убрать аргумент mutex M, и в теле конкретного инстанса декоратора заменить обращения к этому аргументу обращениями к "мьютексКоторыйФункцияДолжнаЗахватить", который должен существовать в области видимости декорируемой функции исходя из объявления (кстати, такой способ создавать декораторы с аргументами выглядит гораздо привлекательнее того, как они реализованы в Python замыкание внутри замыкания внутри функции).

Кроме того, я экспереминтировал с меткой @args, дающей внутри декоратора доступ к аргументам целевой функции, и так же разварачивающейся в "обычный код" на этапе обработки синтаксического дерева. Например, @args.length количество аргументов, @args.1 ссылка на первый аргумент и так далее. Что-то из этого работает, что-то пока не совсем но принципиально сделать это возможно.

Основным итогом этой работы мне хочется считать то, что я наконец изучил Haskell исследование подохода к компиляции сложных структур, путем предоставления разработчику синтаксических меток, которые, смешиваясь с валидным кодом на данном языке программирования, создают интересные и мощные инструменты. От макросов это отличается большей строгостью, стандартизированностью (что упрощает не только написание кода, но и понимание и отладку), и гибкостью из-за поддержки специальной логики со стороны компилятора.

Код получившегося компилятора можно найти здесь, собирается он с помощью stack

P.S. Это был очень интересный и необычный для меня опыт надеюсь, что и вы смогли вынести для себя что-нибудь полезное из этого рассказа. Если нужна отдельная статья про написание компилятора на Haskell на основе LLVM пишите в комментарии.
На любые вопросы постараюсь ответить в комментариях, или в телеграмме @nu11_pointer_exception

В этой статье, на примере простых логических выражений, будет показано, что такое абстрактное синтаксическое дерево и что с ним можно делать. Так же будет рассмотрена альтернатива выражениям LINQ для выполнения запросов к SQL базам данных.

История из жизни разработчика

Это был какой-то легаси проект, и меня попросили улучшить его расширенные возможности фильтрации.

Раньше у них было что-то вроде этого:

А хотели они что-то такое:

Процедура, которая выполняла расширенный поиск выглядела примерно так:

CREATE PROCEDURE dbo.SomeContextUserFind    (@ContextId int, @Filter nvarchar(max)) ASBEGINDECLARE @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=@ContextIdEND

и код, генерировавший строку фильтра, выглядел примерно так:

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 проект, который частично включает код из этой статьи.