Дерево выражений
Дерево выражений (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
он будет указывать на ячейку, следующую за последней ячейкой подвыражения.
Для итерирования внутри подвыражений используются методы:
```c++
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
, но не наоборот.
Получение итераторов, которые указывают на первую или следующую после последней ячейки выражения:
```c++
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);