Дерево выражений

Дерево выражений (ExpressionTree) обеспечивает эффективное хранение древовидной структуры синтаксического выражения и эффективное построение этой структуры при последовательном синтаксическом анализе. Использование ExpressionTree для представления кода позволяет динамически изменять выполняемый код и создавать динамические запросы.

Описание дерева выражений в Reindexer и порядок его построения

В Reindexer используется представление дерева с помощью вектора (одномерного массива).

template <typename OperationType, typename SubTree, int holdSize, typename... Ts>
class ExpressionTree;

Здесь:

  • OperationType — тип, представляющий операторы выражений: арифметические (OpPlus, OpMinus, OpMult, OpDiv) или логические (OpOr, OpAnd, OpNot);
  • SubTree — тип, представляющий заголовок поддерева (подвыражения);
  • holdSize — количество узлов, которые должны храниться в стеке без аллокации;
  • Ts... — типы аргументов выражения.

Здесь не используется традиционный способ построения деревьев с наследованием узлов, выделением отдельных узлов и удержанием указателей на них. ExpressionTree содержит все узлы по значению в векторе (container_) последовательно в типе Node, базирующемся на variant. Для поддержки ленивого копирования узел может содержать ссылку на содержимое другого узла, используя тип ExpressionTree::Ref<T>.

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

Поддерево хранится в container_ сразу за его заголовком (SubTree), который хранит занимаемое поддеревом пространство, включая заголовок.

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

Процесс построения дерева выражений по умолчанию заключается в добавлении элементов от начала в конец с помощью методов Append(), OpenBracket() и CloseBracket() (см. пример). activeBrackets_ — список индексов, по которым в container_ находится начало каждой из открытых скобок. Эти индексы и размеры самих ячеек (SubTree), на которые они ссылаются, могут изменяться при добавлении новых элементов.

Приоритет операторов в ExpressionTree

Дерево выражений не поддерживает приоритет операторов. Управлять приоритетом можно одним из двух способов:

  • вручную, как это сделано в QueryEntries и SelectIteratorContainer;
  • заключив операторы с более высоким приоритетом в скобки, как это сделано в SortExpression.

Примеры построения дерева выражений

Пример 1

Выражение

A + (B - C - (D + E)) - F

будет храниться в следующем виде:

0 1 2 3 4 5 6 7
+, A +, 6 +, B -, C -, 3 +, D +, E -, F

В каждой ячейке хранится оператор (в данном случае + или -) и значение.

Рассмотрим ячейки 4-6, которые соответствуют подвыражению -(D + E).

Здесь:

  • Ячейка 4 содержит заголовок поддерева. - — это оператор перед скобкой. 3 — количество ячеек, используемых для хранения поддерева (в данном случае используются ячейки с четвертой по шестую). Аналогично, ячейка 1 хранит оператор перед скобкой + и количество ячеек (6), используемых для хранения подвыражения + (B - C - (D + E)) (с первой по шестую ячейку).
  • Ячейка 5 содержит оператор + и значение D.
  • Ячейка 6 содержит оператор + и значение Е.

Такая структура позволяет обеспечить эффективную прямую итерацию по дереву без итерации в обратном направлении.

Пример 2

С помощью данного примера можно проследить изменения container_ и activeBrackets_ при построении построения дерева для выражения

(A + B) - (C + (D - E) + F) - G

Процесс выглядит следующим образом:

ШАГ 1. С помощью метода OpenBracket(+) добавляется открывающая скобка, значение в ячейке 0 container_ равно 1, выражение принимает вид (:

0
+, 1

Содержимое activeBrackets_:

0

ШАГ 2. Append(+, A) добавляет к выражению A, значение в ячейке 0 container_ увеличивается на единицу и становится равно 2, выражение принимает вид (A:

0 1
+, 2 +, A

Содержимое activeBrackets_:

0

ШАГ 3. Append(+, B) добавляет к выражению + B, значение в ячейке 0 container_ увеличивается на единицу и становится равно 3, выражение принимает вид (A + B:

0 1 2
+, 3 +, A +, B

Содержимое activeBrackets_:

0

ШАГ 4. С помощью метода CloseBracket() добавляется закрывающая скобка, выражение принимает вид (A + B)

0 1 2
+, 3 +, A +, B

activeBrackets_ пустой.

ШАГ 5. С помощью метода OpenBracket(-) добавляется - и открывающая скобка, значение в ячейке 3 container_ равно 1, выражение принимает вид (A + B) - (

0 1 2 3
+, 3 +, A +, B -, 1

Содержимое activeBrackets_:

3

ШАГ 6. С помощью метода Append(+, C) добавляется C, значение в ячейке 3 container_ увеличивается на единицу и становится равно 2, выражение принимает вид (A + B) - (C

0 1 2 3 4
+, 3 +, A +, B -, 2 +, C

Содержимое activeBrackets_:

3

ШАГ 7. С помощью метода OpenBracket(+) добавляется + и открывающая скобка, значение в ячейке 3 container_ увеличивается на единицу и становится равно 3, значение в ячейке 5 container_ равно 1, выражение принимает вид: (A + B) - (C + (

0 1 2 3 4 5
+, 3 +, A +, B -, 3 +, C +, 1

Содержимое activeBrackets_:

3 5

ШАГ 8. С помощью метода Append(+, D) добавляется D, значение в ячейке 3 container_ увеличивается на единицу и становится равно 4, значение в ячейке 5 container_ увеличивается на единицу и становится равно 2, выражение принимает вид: (A + B) - (C + (D

0 1 2 3 4 5 6
+, 3 +, A +, B -, 4 +, C +, 2 +, D

Содержимое activeBrackets_:

3 5

ШАГ 9. С помощью метода Append(-, E) к выражению добавляется - E, значение в ячейке 3 container_ увеличивается на единицу и становится равно 5, значение в ячейке 5 container_ увеличивается на единицу и становится равно 3, выражение принимает вид: (A + B) - (C + (D - E

0 1 2 3 4 5 6 7
+, 3 +, A +, B -, 5 +, C +, 3 +, D -, E

Содержимое activeBrackets_:

3 5

ШАГ 10. CloseBracket() добавляет закрывающую скобку, выражение принимает вид: (A + B) - (C + (D - E)

0 1 2 3 4 5 6 7
+, 3 +, A +, B -, 5 +, C +, 3 +, D -, E

Содержимое activeBrackets_:

3

ШАГ 11. С помощью метода Append(+, F) к выражению добавляется + F, значение в ячейке 3 container_ увеличивается на единицу и становится равно 6, выражение принимает вид: (A + B) - (C + (D - E) + F

0 1 2 3 4 5 6 7 8
+, 3 +, A +, B -, 6 +, C +, 3 +, D -, E +, F

Содержимое activeBrackets_:

3

ШАГ 12. CloseBracket() добавляет закрывающую скобку, выражение принимает вид: (A + B) - (C + (D - E) + F)

0 1 2 3 4 5 6 7 8
+, 3 +, A +, B -, 6 +, C +, 3 +, D -, E +, F

activeBrackets_ пустой

ШАГ 13. С помощью метода Append(-, G) к выражению добавляется - G, выражение принимает вид: (A + B) - (C + (D - E) + F) - G

0 1 2 3 4 5 6 7 8 9
+, 3 +, A +, B -, 6 +, C +, 3 +, D -, E +, F -, G

activeBrackets_ пустой.

Классы и методы, использующиеся при формировании дерева выражений

Класс Bracket

Тип по умолчанию для аргумента шаблона поддерева. Содержит размер поддерева, который увеличивается с помощью Append() и уменьшается с помощью Erase().

Класс ExpressionTree::Node

Node — это тип ячеек container_. В нем содержится операнд (значение типа операции) и значение одного из следующих типов:

  • SubTree (по умолчанию Bracket), если узел — заголовок поддерева.
  • Один из типов аргументов выражения Ts....
  • ExpressionTree::Ref<T>, где T - один из типов Ts .... Это означает, что Node ссылается на содержимое другого узла, в котором хранится значение типа T.

Методы класса ExpressionTree::Node

При работе с деревом выражений используются следующие методы класса ExpressionTree::Node:

  • Возвращает ссылку на значение, если оно содержит значение типа T или Ref<T>. В противном случае завершается с ошибкой.

    T& Node::Value<T>(), const T& Node::Value<T>() const

  • Возвращает 1, если узел не является заголовком поддерева. В противном случае возвращается количество ячеек, занимаемых подвыражением.

    size_t Node::Size() const

  • Проверяет, является ли узел заголовком поддерева.

    bool Node::IsSubTree() const, bool Node::IsLeaf() const

  • Возвращает значение true, если узел содержит значение типа T.

    bool Node::Holds<T>() const

  • Увеличивает размер подвыражения, если узел является заголовком поддерева. В противном случае завершается с ошибкой.

    void Append()

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

    void Erase(size_t)

  • Вызывает соответствующий функтор, если узел содержит значение одного из типов Args... или Ref<T>, где T — один из типов Args..., в противном случае ни один функтор не будет вызван.

    template <typename... Args>
void Node::ExecuteAppropriate(const std::function<void(Args&)>&... funcs);
template <typename... Args>
void Node::ExecuteAppropriate(const std::function<void(const Args&)>&... funcs) const;

  • В зависимости от типа значения, содержащегося в узле, вызывает соответствующий функтор и предоставляет возвращаемое значение.

    template <typename R>
R Node::CalculateAppropriate(const std::function<R(const SubTree&)>& f, const std::function<R(const     Ts&)>&... funcs) const;

  •  1. Возвращает копию исходного значения, если оно является заголовком подвыражения или содержит значение типа Ref<T>.
    2. Возвращает новый узел, содержащий Ref<T>, который ссылается на payload исходного узла, если он содержит T (один из типов аргументов выражения Ts...).

    Node Node::MakeLazyCopy()&

Ленивая копия не должна существовать без оригинала.

  •  1. Возвращает копию исходного значения, если оно является заголовком подвыражения или содержит один из типов аргументов выражения Ts....
    2. Возвращает новый узел, содержащий копию значения, на которое ссылается Ref<T>, если в исходном узле содержится значение типа Ref<T>.

    Node Node::MakeDeepCopy() const &

  •  1. Возвращает перемещенную копию исходного значения, если оно является заголовком подвыражения или содержит значение одного из типов Ts.....
    2. Возвращает новый узел, содержащий копию значения, на которое ссылается Ref<T>, если в исходном узле содержится значение типа Ref<T>.

    Node Node::MakeDeepCopy() &&

  • Возвращает true, если узел содержит ссылку на другой узел (т.е. является ленивой копией).

    bool Node::IsRef() const

  • Устанавливает узел для хранения нового значения типа T.

    void Node::SetValue<T>(T&&)

Класс ExpressionTree::Ref<T>

Ref<T> - это оболочка для указателя на T. Используется для ленивого копирования узла, чтобы не копировать его содержимое, а просто создать ссылку на него.

Классы ExpressionTree::iterator и ExpressionTree::const_iterator

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

Для итерирования внутри подвыражений используются методы:

iterator iterator::begin();
const_iterator iterator::cbegin();
const_iterator const_iterator::begin();
const_iterator const_iterator::cbegin();
iterator iterator::end();
const_iterator iterator::cend();
const_iterator const_iterator::end();
const_iterator const_iterator::cend();

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

Например для выражения A + B - (C - D + (E - F) - G)

0 1 2 3 4 5 6 7 8
+, A +, B -, 7 +, C -, D +, 3 +, E -, F -, G
  • Если итератор it указывает на ячейку 1, it.begin() (и аналогичные методы) завершается неудачей. После операции ++it итератор будет указывать на ячейку 2.
  • Если итератор it указывает на ячейку 2, it.begin() возвращает итератор, указывающий на ячейку 3. it.end() возвращает итератор, который указывает на ячейку, следующую за ячейкой 8 (последней ячейкой подвыражения), и операция ++it делает итератор указывающим на ячейку, следующую за ячейкой 8.
  • Если итератор it указывает на ячейку 3, it.begin() (и аналогичные методы) завершается неудачей. После операции ++it итератор будет указывать на ячейку 4.
  • Если итератор it указывает на ячейку 5, it.begin() возвращает итератор, указывающий на ячейку 6. it.end() возвращает итератор, который указывает на ячейку 8, и операция ++it делает итератор указывающим на ячейку 8.

iterator может быть преобразован в const_iterator, но не наоборот.

Получение итераторов, которые указывают на первую или следующую после последней ячейки выражения:

iterator ExpressionTree::begin();
const_iterator ExpressionTree::begin() const;
const_iterator ExpressionTree::cbegin() const;
iterator ExpressionTree::end();
const_iterator ExpressionTree::end() const;
const_iterator ExpressionTree::cend() const;

Методы класса

  • Получение итератора, который указывает на первую ячейку текущего активного подвыражения (текущим является последнее подвыражение, для которого была вызвана функция Open Bracket(), а CloseBracket() - еще нет) и возвращает begin(), если активного подвыражения нет:

    const_iterator ExpressionTree::begin_of_current_bracket() const

  • Добавление операнда в конец или начало выражения. Т должен быть одним из типов аргументов выражения Ts...:

    void ExpressionTree::Append<T>(OperationType, const T&);
void ExpressionTree::Append<T>(OperationType, T&&);
void ExpressionTree::AppendFront<T>(OperationType, T&&);

  • Получение полной или ленивой копии части другого выражения:

    void ExpressionTree::Append(const_iterator begin, const_iterator end);
void ExpressionTree::LazyAppend(iterator begin, iterator end);

Ленивая копия не должна существовать без оригинала.

  • Начало и завершение подвыражения. args.. передаются конструктору SubTree:

    void ExpressionTree::OpenBracket<Args...>(OperationType, Args... args);
void ExpressionTree::CloseBracket();

  • Получение или установка операции узла в ячейке с номером i:

    OperationType ExpressionTree::GetOperation(size_t i) const ;
void ExpressionTree::SetOperation(OperationType op, size_t i);

  • Устанавливает операцию для последнего добавленного листа, или последнего закрытого поддерева, либо последнего открытого поддерева (если оно пустое).

    void ExpressionTree::SetLastOperation(OperationType)

  • Проверяет, является ли выражение пустым.

    bool ExpressionTree::Empty() const

  • Возвращает количество ячеек, занимаемых выражением.

    size_t ExpressionTree::Size() const

  • Возвращает количество ячеек, занимаемых подвыражением, если ячейка i является заголовком подвыражения или 1 — в противном случае.

    size_t ExpressionTree::Size(size_t i) const

  • Проверяет, является ли ячейка i заголовком подвыражения.

    bool ExpressionTree::IsValue(size_t i) const

  • Удаляет узлы с индексами от from до to - 1.

    void ExpressionTree::Erase(size_t from, size_t to)

  • Возвращает индекс ячейки, расположенной после последней ячейки подвыражения, если ячейка i является заголовком подвыражения или i + 1 — в противном случае.

    size_t ExpressionTree::Next(size_t i) const

Например, выражение A + B - (C - D + (E - F) - G) будет храниться в виде:

0 1 2 3 4 5 6 7 8
+, A +, B -, 7 +, C -, D +, 3 +, E -, F -, G

Метод вернет:

  • Для Next(1) — номер ячейки 2 (т.к. ячейка 1 не является заголовком подвыражения).

  • Для Next(2) — номер ячейки 9 (т.к. ячейка 2 — заголовок подвыражения - (C - D + (E - F) - G)).

  • Для Next(3) - номер ячейки 4 (т.к. ячейка 3 не является заголовком подвыражения).

  • Для Next(5) — номер ячейки 8 (т.к. ячейка 5 — заголовок подвыражения + (E - F)).

  • Вызов соответствующего функтора в зависимости от типа содержимого для каждого узла, пропустить, если нет подходящего функтора (вызвать ExecuteAppropriate(funcs) для каждого узла):

    template <typename... Args>
void ExpressionTree::ExecuteAppropriateForEach(const std::function<void(const Args&)>&... funcs) const;
template <typename... Args>
void ExecuteAppropriateForEach(const std::function<void(Args&)>&... funcs);