Вернее, как слезть с него. Но обо всем по порядку. Эта статья немного отличается от обычного формата статей от PVS-Studio. Мы часто пишем о проверке других проектов, но почти никогда не приоткрываем завесу над нашей внутренней работой. Пришло время исправить это упущение и рассказать о том, как устроен анализатор изнутри. Точнее, о самой важной его части — синтаксическом дереве. В статье речь пойдет о той части PVS-Studio, которая относится к языкам C и C++.
Перво-наперво
Синтаксическое дерево является центральной частью любого компилятора. Так или иначе, код нужно представить в виде, удобном для работы с программой, и так уж получилось, что древовидная структура подходит для этого лучше всего. Я не буду здесь углубляться в теорию — достаточно сказать, что дерево очень хорошо отражает иерархию выражений и блоков в коде, и при этом содержит только необходимые для работы данные.
Какое отношение компилятор имеет к статическому анализатору? Дело в том, что у этих двух инструментов много общего. На начальном этапе разбора кода они выполняют одну и ту же работу. Сначала код разбивается на поток токенов, который подается парсеру. Затем в процессе синтетического и семантического анализа токены организуются в дерево, которое отправляется дальше по конвейеру. На этом этапе компиляторы могут выполнять промежуточные оптимизации перед генерацией бинарного кода, статические анализаторы начинают обходить узлы и запускать различные проверки.
В анализаторе PVS-Studio с построенным деревом происходит несколько вещей:
- Для каждого объявления определяются типы. Объявлением может быть переменная, функция, класс, определение псевдонима типа через using или typedef и т. д. Одним словом, любая декларация. Все это заносится в таблицу для текущего объема;
- Обрабатываются выражения и вычисляются значения переменных. Информация, которую анализатор использует для символьных вычислений и анализа потока данных, сохраняется;
- Выбираются перегрузки вызываемых функций, к ним применяются предустановленные аннотации, а если они отсутствуют, то по возможности выводятся автоматически;
- Поток данных анализируется. Для этого анализатор сохраняет значение каждой переменной (если оно может быть вычислено во время компиляции). Помимо значений, к переменным присоединяются известные данные об их состоянии. Например, предположим, что функция начинается с проверки указателя на nullptr с последующим выходом из функции, если указатель равен нулю. В этом случае он будет считаться действительным далее по коду. Эти данные также используются в межпроцедурном анализе;
- Правила диагностики выполняются. В зависимости от логики своей работы они могут делать дополнительный обход дерева. Для разных типов выражений запускаются свои наборы диагностик, которые иногда могут пересекаться.
Если вас интересуют подробности работы анализа, рекомендую прочитать статью Технологии, используемые в анализаторе кода PVS-Studio для поиска ошибок и потенциальных уязвимостей. Там подробно описаны некоторые пункты из списка.
Рассмотрим подробнее, что происходит с деревом внутри анализатора, и как оно вообще выглядит. На этом краткое вступление закончено, пора перейти к сути дела.
Как это работает
Исторически PVS-Studio использует для представления кода двоичное дерево. Эта классическая структура данных всем знакома — у нас есть узел, который вообще относится к двум дочерним. Узлы, у которых не должно быть потомков, я буду называть терминалами, все остальные — нетерминалами. Нетерминал может в некоторых случаях не иметь дочерних узлов, но его ключевое отличие от терминала состоит в том, что для него принципиально разрешены потомки. Конечные узлы (или листья) не имеют возможности ссылаться на что-то, кроме родителя.
Структура, используемая в PVS-Studio, немного отличается от классического бинарного дерева — это нужно для удобства. Терминальные узлы обычно соответствуют ключевым словам, именам переменных, литералам и т. д. Нетерминалы — различные типы выражений, блоки кода, списки и тому подобные составные элементы дерева.
Что касается дизайна компиляторов, то здесь все достаточно стандартно. Я призываю всех заинтересованных ознакомиться с культовой Книгой дракона.
Что касается нас, то мы идем дальше. Давайте посмотрим на простой пример кода и на то, как его воспринимает анализатор. Далее будет много картинок из нашей внутренней утилиты визуализации дерева.
Итак, вот пример:
int f(int a, int b)
{
return a + b;
}При обработке парсером эта простая функция будет выглядеть так (нетерминальные узлы выделены желтым цветом):
У такого представления есть свои плюсы и минусы. Минусов, на мой взгляд, больше, чем плюсов. Впрочем, давайте посмотрим на само дерево. Спешу сказать, что оно довольно избыточно, например, так как содержит знаки препинания и скобки. Компилятор считает это лишним мусором, но анализатору эта информация может понадобиться для некоторых диагностических правил. Другими словами, анализатор работает не с абстрактным синтаксическим деревом (АСД), а с деревом вывода (ДД).
Дерево растет слева направо и сверху вниз. Левые дочерние узлы всегда содержат что-то значимое, например деклараторы. Если мы посмотрим на его правую часть, то увидим промежуточные нетерминалы, отмеченные словом NonLeaf. Они нужны только для свободного сохранения своей структуры. Никакой информационной нагрузки для нужд анализа такие узлы не несут.
На данный момент нас интересует левая часть дерева. Вот он крупным планом:
Это объявление функции. Родительский узел PtreeDeclarator — это объект, через который вы можете получить доступ к узлам с именем функции и ее параметрами. Он также хранит закодированную подпись для системы типов. Мне кажется, что эта картинка говорит сама за себя, и сравнивать элементы дерева с кодом довольно просто.
Выглядит просто, правда?
Для большей наглядности возьмем более простой пример. Представьте, что у нас есть код, который вызывает нашу функцию f:
f(42, 23);Вызов функции в дереве будет выглядеть так:
Структура очень похожа, только здесь мы видим вызов функции вместо ее объявления. Теперь предположим, что мы хотим пройтись по всем аргументам и что-то сделать с каждым из них. Это реальная задача, которая часто встречается в коде анализатора. Излишне говорить, что все это не вращается вокруг аргументов, поэтому приходится проходить разные типы узлов. Но сейчас мы рассмотрим этот конкретный пример.
Предположим, у нас есть только указатель на родительский узел FUNCALL. Из любого нетерминала мы можем получить левый и правый дочерние узлы. Тип каждого из них известен. Мы знаем структуру дерева, поэтому можем сразу перейти к узлу со списком аргументов, который является Нелистом, из которого вырастает терминал 42 (как показано на картинке). Мы заранее не знаем количество аргументов, а в списке есть запятые, которые в данном случае нас абсолютно не интересуют.
Как мы будем это делать? Продолжай читать.
Лаборатория изобретения колеса
Казалось бы, итерация по дереву довольно проста. Вам просто нужно написать функцию, которая будет делать именно это, и использовать ее везде. Возможно, также передайте ему лямбду в качестве аргумента для обработки каждого элемента. Так и было бы на самом деле, если бы не пара нюансов.
Во-первых, каждый раз обход дерева должен быть немного другим. Логика работы с каждым узлом разная, как и логика работы со всем списком. Скажем, в одном случае мы хотим пройтись по списку аргументов и передать каждый из них определенной функции для обработки. В другом мы хотим выбрать и вернуть один аргумент, отвечающий некоторым требованиям. Или отфильтруйте список и отбросьте из него все неинтересные элементы.
Во-вторых, иногда нужно знать индекс текущего элемента. Например, мы хотим обработать только первые два аргумента и остановиться.
В-третьих, давайте отвлечемся от примера функции. Допустим, у нас есть такой фрагмент кода:
int f(int a, int b)
{
int c = a + b;
c *= 2;
if (c < 42) return c;
return 42;
}Я знаю, этот код унылый, но давайте сейчас сосредоточимся на том, как выглядит дерево. Объявление функции мы уже видели, здесь нам понадобится ее тело:
Этот случай похож на список аргументов, но вы можете заметить некоторые отличия. Взгляните еще раз на картинку из предыдущего раздела.
Вы что-то заметили?
Все верно, в этом списке нет запятых, а значит, вы можете обрабатывать его подряд и не беспокоиться о пропуске разделителей.
Всего у нас есть как минимум два случая:
- Список с разделителями.
- Однородный список.
Теперь посмотрим, как все это работает в коде анализатора. Вот пример обхода списка аргументов. Это упрощенная версия одной из функций переводчика.
void ProcessArguments(Ptree* arglist) { if (!arglist) return;Ptree* args = Second(arglist); while (args) { Ptree* p = args->Car(); if (!Eq(p, ',')) { ProcessArg(p); }args = args->Cdr(); } }
Если бы мне платили доллар каждый раз, когда я вижу такой код, я бы уже разбогател.
Давайте посмотрим, что здесь происходит. Должен предупредить, это очень старый код, написанный задолго до C++11, не говоря уже о более современных стандартах. Наверное, специально искал осколок времен древних цивилизаций.
Итак, во-первых, эта функция принимает на вход список аргументов в скобках. Что-то такое:
(42, 23)
Здесь вызывается функция Second для получения содержимого скобок. Все, что он делает, это сдвигает один раз вправо, а затем один раз влево по бинарному дереву. Далее цикл последовательно получает элементы: 42, потом запятая, потом 23, и на следующем шаге указатель args становится нулевым, потому что мы доходим до конца ветки. Цикл, разумеется, пропускает неинтересные запятые.
Подобные функции с немного измененной логикой можно найти во многих местах, особенно в старом коде.
Другой пример. Как узнать, есть ли вызов определенной функции в определенном блоке кода? Как-то так:
bool IsFunctionCalled(const Ptree* body, std::string_view name) { if (!arglist) return;const Ptree* statements = body; while (statements) { const Ptree* cur = statements->Car(); if (IsA(cur, ntExprStatement) && IsA(cur->Car(), ntFuncallExpr)) { const Ptree* funcName = First(cur->Car()); if (Eq(funcName, name)) return true; }statements = statements->Cdr(); } return false; }
Примечание. Внимательный читатель мог кое-что заметить. Так где он старый? Выступает std::string_view . Все просто и понятно, даже самый старый код постепенно рефакторится и со временем ничего подобного не останется.
Было бы неплохо использовать здесь что-то более элегантное, не так ли? Ну, например, стандартный алгоритм find_if. На самом деле, даже обычный диапазон for значительно улучшит читабельность и облегчит поддержку такого кода, не говоря уже об алгоритме.
Попробуем этого добиться.
Положите дерево в коробку
Наша цель — заставить дерево вести себя как контейнер STL. При этом мы не должны заботиться о внутренней структуре списков, мы хотим равномерно перебирать узлы, например, так:
void DoSomethingWithTree(const Ptree* tree)
{
....
for (auto cur : someTreeContainer)
{
....
}
}Как видите, здесь у нас есть некая сущность с именем someTreeContainer, о которой мы пока ничего не знаем. Такой контейнер должен иметь как минимум методы begin и end, возвращающие итераторы. Говоря об итераторах, они тоже должны вести себя как стандартные. Начнем именно с них.
В простейшем случае итератор выглядит так:
template <typename Node_t, std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>> class PtreeIterator { public: using value_type = Node_t; using dereference_type = value_type; using reference = std::add_lvalue_reference_t<value_type>; using pointer = std::add_pointer_t<value_type>; using difference_type = decltype(std::declval<pointer>() - std::declval<pointer>()); using iterator_category = std::forward_iterator_tag;public: PtreeIterator(Node_t* node) noexcept : m_node{ node } {} ....PtreeIterator& operator++() noexcept { m_node = Rest(m_node); return *this; } dereference_type operator*() const noexcept { return static_cast<dereference_type>(First(m_node)); }private: Node_t* m_node = nullptr; };
Чтобы не загромождать код, я убрал некоторые детали. Ключевыми моментами здесь являются разыменование и приращение. Шаблон нужен для того, чтобы итератор мог работать как с постоянными, так и с непостоянными данными.
Теперь напишем контейнер, в который мы поместим узел дерева. Вот самый простой вариант:
template <typename Node_t> class PtreeContainer { public: using Iterator = PtreeIterator<Node_t>; using value_type = typename Iterator::dereference_type; using size_type = size_t; using difference_type = typename Iterator::difference_type;public: PtreeContainer(Node_t* nodes) : m_nodes{ nodes } { if (IsLeaf(m_nodes)) { m_nodes = nullptr; } }....Iterator begin() const noexcept { return m_nodes; } Iterator end() const noexcept { return nullptr; } bool empty() const noexcept { return begin() == end(); }private: Node_t* m_nodes = nullptr; };
Хорошо, мы закончили, мы можем спать спокойно, спасибо за внимание.
Нет, подожди. Это не может быть так просто, верно? Вернемся к нашим двум вариантам списка — с разделителями и без них. Здесь при инкрементировании мы просто берем правый узел дерева, так что это не решает проблему. Нам по-прежнему нужно пропускать запятые, если мы хотим работать только с данными.
Не проблема, мы просто добавляем в итератор дополнительный параметр шаблона. Например, следующим образом:
enum class PtreeIteratorTag : uint8_t { Statement, List };template <typename Node_t, PtreeIteratorTag tag, std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0> class PtreeIterator { .... };
Как это может нам помочь? Проще простого. Мы проверим этот параметр в операторе приращения и будем вести себя соответственно. К счастью, в C++ 17 мы можем решить эту проблему во время компиляции с помощью конструкции if constexpr:
PtreeIterator& operator++() noexcept
{
if constexpr (tag == PtreeIteratorTag::Statement)
{
m_node = Rest(m_node);
}
else
{
m_node = RestRest(m_node);
}
return *this;
}Это лучше, теперь мы можем выбрать итератор для удовлетворения наших потребностей. Что будем делать с контейнерами? Вы можете, например, сделать что-то вроде этого:
template <typename Node_t, PtreeIteratorTag tag>
class PtreeContainer
{
public:
using Iterator = PtreeIterator<Node_t, tag>;
....
};Хорошо, мы закончили? На самом деле, не совсем.
Но это не конец
Давайте посмотрим на этот код:
void ProcessEnum(Ptree* argList, Ptree* enumPtree) { const ptrdiff_t argListLen = Length(argList); if (argListLen < 0) return;for (ptrdiff_t i = 0; i < argListLen; ++i) { std::string name; Ptree* elem;const EGetEnumElement r = GetEnumElementInfo(enumPtree, i, elem, name); .... } }
Мне очень многое не нравится в этом коде, начиная от цикла со счетчиком, и заканчивая тем, что функция GetEnumElementInfo выглядит очень подозрительно. На данный момент он остается для нас черным ящиком, но можно предположить, что он получает элемент enum по индексу и возвращает его имя и узел в дереве через out-параметры. Возвращаемое значение также немного странное. Давайте избавимся от него вообще — это идеальная работа для нашего итератора списка:
void ProcessEnum(const Ptree* argList)
{
for (auto elem : PtreeContainer<const Ptree, PtreeIteratorTag::List>(argList))
{
auto name = PtreeToString(elem);
....
}
}Неплохо. Загвоздка в том, что код не компилируется. Почему? Потому что удаленный нами индекс использовался в теле цикла после вызова GetEnumElementInfo. Я не буду здесь говорить, как именно он использовался, потому что это сейчас не принципиально. Достаточно сказать, что индекс необходим.
Что ж, давайте добавим переменную и испортим наш красивый код:
void ProcessEnum(const Ptree* argList)
{
size_t i = 0;
for (auto elem : PtreeContainer<const Ptree, PtreeIteratorTag::List>(argList))
{
auto name = PtreeToString(elem);
....
UseIndexSomehow(i++);
}
}Еще рабочий вариант, но вот как лично я реагирую на нечто подобное:
Что же, попробуем решить эту проблему. Нам нужно что-то, что может автоматически считать элементы. Добавим итератор со счетчиком. Я снова пропустил лишние детали для краткости:
template <typename Node_t, PtreeIteratorTag tag, std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>> class PtreeCountingIterator { public: using size_type = size_t; using value_type = Node_t; using dereference_type = std::pair<value_type, size_type>; using reference = std::add_lvalue_reference_t<value_type>; using pointer = std::add_pointer_t<value_type>; using difference_type = decltype(std::declval<pointer>() - std::declval<pointer>()); using iterator_category = std::forward_iterator_tag;public: PtreeCountingIterator(Node_t* node) noexcept : m_node{ node } {} ....PtreeCountingIterator& operator++() noexcept { if constexpr (tag == PtreeIteratorTag::Statement) { m_node = Rest(m_node); } else { m_node = RestRest(m_node); }++m_counter; return *this; }dereference_type operator*() const noexcept { return { static_cast<value_type>(First(m_node)), counter() }; }private: Node_t* m_node = nullptr; size_type m_counter = 0; };
Теперь мы можем написать такой код, верно?
void ProcessEnum(const Ptree* argList)
{
for (auto [elem, i] :
PtreeCountedContainer<const Ptree, PtreeIteratorTag::List>(argList))
{
auto name = PtreeToString(elem);
....
UseIndexSomehow(i);
}
}Вообще говоря, мы определенно можем, но есть еще одна проблема. Если вы посмотрите на этот код, то заметите, что мы ввели еще одну сущность — что-то с именем PtreeCountedContainer. Похоже, ситуация становится все более изощренной. Чего очень не хочется, так это жонглировать разными типами контейнеров, а учитывая, что внутри они одинаковые, то рука сама тянется к бритве Оккама.
Нам придется использовать итератор в качестве параметра шаблона для контейнера, но об этом позже.
Зоопарк видов
Давайте на минутку отвлечемся от счетчиков, типов и итераторов. В погоне за универсальным обходом узлов мы забыли о самом значимом — самом дереве.
Взгляните на этот код:
int a, b, c = 0, d;Что мы видим в дереве:
Давайте теперь пройдемся по списку деклараторов, но сначала я расскажу вам еще кое-что о дереве. Все время до этого мы имели дело с указателем на класс Ptree. Это базовый класс, от которого наследуются все остальные типы узлов. Через их интерфейсы мы можем получить дополнительную информацию. В частности, самый верхний узел на картинке может вернуть нам список деклараторов без использования служебных функций, таких как First и Second. Также нам не понадобятся низкоуровневые методы Car и Cdr (привет любителям языка Лисп). Это хорошая новость, так как при диагностике мы можем игнорировать реализацию дерева. Думаю, все согласны с тем, что утечки абстракций — это очень плохо.
Вот как выглядит обход всех деклараторов:
void ProcessDecl(const PtreeDeclarator* decl) { .... }void ProcessDeclarators(const PtreeDeclaration* declaration) { for (auto decl : declaration->GetDeclarators()) { ProcessDecl(static_cast<const PtreeDeclarator*>(decl)); } }
Метод GetDeclarators возвращает итерируемый контейнер. В данном случае его тип — PtreeContainer‹const Ptree, PtreeIteratorTag::List›.
Все прекрасно и денди, кроме актерского состава. Дело в том, что функция ProcessDecl хочет указатель на класс, производный от Ptree, но наши итераторы ничего об этом не знают. Я хотел бы избежать преобразования типов вручную.
Похоже, пришло время изменить итератор и добавить ему возможность приведения типов.
template <typename Node_t, typename Deref_t, PtreeIteratorTag tag,
std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>>
class PtreeIterator
{
public:
using value_type = Deref_t;
using dereference_type = value_type;
using reference = std::add_lvalue_reference_t<value_type>;
using pointer = std::add_pointer_t<value_type>;
using difference_type =
decltype(std::declval<pointer>() - std::declval<pointer>());
using iterator_category = std::forward_iterator_tag;
....
}Чтобы каждый раз не писать вручную все эти аргументы шаблона, добавим несколько псевдонимов на все случаи жизни:
template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeStatementIterator = PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeListIterator = PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::List>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeStatementCountingIterator = PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeListCountingIterator = PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::List>;
Так-то лучше. Теперь, если нам не нужно приведение, мы можем указать только первый аргумент шаблона. Нам также не нужно забивать себе голову значением параметра tag.
Что будем делать с контейнерами? Напомним, что нам нужен только один универсальный класс, подходящий для любого итератора. Здесь мы имеем смехотворно большое количество различных комбинаций, а нам нужна простота. Что-то вроде этого:
То есть мы хотим, чтобы один класс-контейнер мог поддерживать все типы наших итераторов и мог указать им, какой тип возвращать при разыменовании. Затем в коде мы просто создаем нужный нам контейнер и начинаем с ним работать, не задумываясь, какие итераторы нам нужны.
Мы рассмотрим этот вопрос в следующем разделе.
Магия шаблонов
Итак, вот что нам нужно:
- Один контейнер, который может универсально работать с любым итератором.
- Итератор, который в зависимости от списка узлов может работать как с каждым элементом, так и через один.
- Тот же итератор, но со счетчиком.
- Оба итератора должны иметь возможность выполнять приведение типов при разыменовании, если дополнительно указан тип.
В первую очередь нам нужно как-то привязать тип контейнера к типу итератора через параметры шаблона. Вот что мы наконец получили:
template <template <typename, typename> typename FwdIt, typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> class PtreeContainer { public: using Iterator = FwdIt<Node_t, Deref_t>; using value_type = typename Iterator::dereference_type; using size_type = size_t; using difference_type = typename Iterator::difference_type;public: PtreeContainer(Node_t* nodes) : m_nodes{ nodes } { if (IsLeaf(m_nodes)) { m_nodes = nullptr; } }.... Iterator begin() const noexcept { return m_nodes; } Iterator end() const noexcept { return nullptr; } bool empty() const noexcept { return begin() == end(); } ....private: Node_t* m_nodes = nullptr; };
Кроме того, вы можете добавить дополнительные методы в контейнер. Например, вот как мы можем узнать количество элементов:
difference_type count() const noexcept
{
return std::distance(begin(), end());
}Или вот оператор индексации:
value_type operator[](size_type index) const noexcept { size_type i = 0; for (auto it = begin(); it != end(); ++it) { if (i++ == index) { return *it; } }return value_type{}; }
Понятно, что с такими методами нужно обращаться осторожно из-за их линейной сложности, но иногда они полезны.
Для простоты использования добавим псевдонимы:
template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeStatementList = PtreeContainer<PtreeStatementIterator, Node_t, Deref_t>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeItemList = PtreeContainer<PtreeListIterator, Node_t, Deref_t>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeCountedStatementList = PtreeContainer<PtreeStatementCountingIterator, Node_t, Deref_t>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeCountedItemList = PtreeContainer<PtreeListCountingIterator, Node_t, Deref_t>;
Теперь мы можем легко создавать контейнеры. Скажем, в уже упомянутом классе PtreeDeclaration мы хотим получить из метода GetDeclarators контейнер, итератор которого пропускает разделители, при этом счетчика в нем нет, а при разыменовании он возвращает значение типа PtreeDeclarator. Вот объявление такого контейнера:
using DeclList =
Iterators::PtreeItemList<Ptree, PtreeDeclarator*>;
using ConstDeclList =
Iterators::PtreeItemList<const Ptree, const PtreeDeclarator*>;Теперь мы можем написать такой код и не думать ни о типе списка, ни о приведениях:
void ProcessDecl(const PtreeDeclarator* decl) { .... }void ProcessDeclarators(const PtreeDeclaration* declaration) { for (auto decl : declaration->GetDeclarators()) { ProcessDecl(decl); } }
И, наконец, поскольку вывод типов для псевдонимов появится только в C++ 20, для более удобного создания контейнеров в коде мы добавили такие функции:
template <typename Node_t> PtreeStatementList<Node_t> MakeStatementList(Node_t* node) { return { node }; }template <typename Node_t> PtreeItemList<Node_t> MakeItemList(Node_t* node) { return { node }; }template <typename Node_t> PtreeCountedStatementList<Node_t> MakeCountedStatementList(Node_t* node) { return { node }; }template <typename Node_t> PtreeCountedItemList<Node_t> MakeCountedItemList(Node_t* node) { return { node }; }
Вспомним функцию, которая работала с перечислениями. Теперь мы можем написать это так:
void ProcessEnum(const Ptree* argList)
{
for (auto [elem, i] : MakeCountedItemList(argList))
{
auto name = PtreeToString(elem);
....
UseIndexSomehow(i);
}
}Сравните с исходной версией. Мне кажется, стало намного лучше:
void ProcessEnum(Ptree* argList, Ptree* enumPtree) { const ptrdiff_t argListLen = Length(argList); if (argListLen < 0) return;for (ptrdiff_t i = 0; i < argListLen; ++i) { std::string name; Ptree* elem;const EGetEnumElement r = GetEnumElementInfo(enumPtree, i, elem, name); .... UseIndexSomehow(i); } }
Вот и все, люди
На этом у меня все, спасибо за внимание. Надеюсь, вы узнали что-то интересное или даже полезное.
Из содержания статьи может показаться, что я ругаю код нашего анализатора и хочу сказать, что там все плохо. Но это не так. Как и любой проект с историей, наш анализатор полон геологических отложений, оставшихся от прошлых эпох. Считайте, что мы только что раскопали, вытащили артефакты древней цивилизации из-под земли и провели реставрацию, чтобы они красиво смотрелись на полке.
P.S.
Здесь будет много кода. Я сомневался включать сюда реализацию итераторов или нет, и в итоге решил включить, чтобы ничего не оставить за кадром. Если вам не интересно читать код, то здесь я с вами попрощаюсь. Желаю остальным хорошо провести время с шаблонами.
Обычный итератор
template <typename Node_t, typename Deref_t, PtreeIteratorTag tag, std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0> class PtreeIterator { public: using value_type = Deref_t; using dereference_type = value_type; using reference = std::add_lvalue_reference_t<value_type>; using pointer = std::add_pointer_t<value_type>; using difference_type = decltype(std::declval<pointer>() - std::declval<pointer>()); using iterator_category = std::forward_iterator_tag;public: PtreeIterator(Node_t* node) noexcept : m_node{ node } {} PtreeIterator() = delete; PtreeIterator(const PtreeIterator&) = default; PtreeIterator& operator=(const PtreeIterator&) = default; PtreeIterator(PtreeIterator&&) = default; PtreeIterator& operator=(PtreeIterator&&) = default;bool operator==(const PtreeIterator & other) const noexcept { return m_node == other.m_node; } bool operator!=(const PtreeIterator & other) const noexcept { return !(*this == other); } PtreeIterator& operator++() noexcept { if constexpr (tag == PtreeIteratorTag::Statement) { m_node = Rest(m_node); } else { m_node = RestRest(m_node); } return *this; } PtreeIterator operator++(int) noexcept { auto tmp = *this; ++(*this); return tmp; } dereference_type operator*() const noexcept { return static_cast<dereference_type>(First(m_node)); } pointer operator->() const noexcept { return &(**this); }Node_t* get() const noexcept { return m_node; }private: Node_t* m_node = nullptr; };template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeStatementIterator = PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeListIterator = PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::List>;
Итератор со счетчиком
template <typename Node_t, typename Deref_t, PtreeIteratorTag tag, std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0> class PtreeCountingIterator { public: using size_type = size_t; using value_type = Deref_t; using dereference_type = std::pair<value_type, size_type>; using reference = std::add_lvalue_reference_t<value_type>; using pointer = std::add_pointer_t<value_type>; using difference_type = decltype(std::declval<pointer>() - std::declval<pointer>()); using iterator_category = std::forward_iterator_tag;public: PtreeCountingIterator(Node_t* node) noexcept : m_node{ node } {} PtreeCountingIterator() = delete; PtreeCountingIterator(const PtreeCountingIterator&) = default; PtreeCountingIterator& operator=(const PtreeCountingIterator&) = default; PtreeCountingIterator(PtreeCountingIterator&&) = default; PtreeCountingIterator& operator=(PtreeCountingIterator&&) = default;bool operator==(const PtreeCountingIterator& other) const noexcept { return m_node == other.m_node; } bool operator!=(const PtreeCountingIterator& other) const noexcept { return !(*this == other); } PtreeCountingIterator& operator++() noexcept { if constexpr (tag == PtreeIteratorTag::Statement) { m_node = Rest(m_node); } else { m_node = RestRest(m_node); }++m_counter; return *this; } PtreeCountingIterator operator++(int) noexcept { auto tmp = *this; ++(*this); return tmp; } dereference_type operator*() const noexcept { return { static_cast<value_type>(First(m_node)), counter() }; } value_type operator->() const noexcept { return (**this).first; }size_type counter() const noexcept { return m_counter; } Node_t* get() const noexcept { return m_node; }private: Node_t* m_node = nullptr; size_type m_counter = 0; };template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeStatementCountingIterator = PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeListCountingIterator = PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::List>;
Общий контейнер
template <template <typename, typename> typename FwdIt, typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> class PtreeContainer { public: using Iterator = FwdIt<Node_t, Deref_t>; using value_type = typename Iterator::dereference_type; using size_type = size_t; using difference_type = typename Iterator::difference_type;public: PtreeContainer(Node_t* nodes) : m_nodes{ nodes } { if (IsLeaf(m_nodes)) { m_nodes = nullptr; } }PtreeContainer() = default; PtreeContainer(const PtreeContainer&) = default; PtreeContainer& operator=(const PtreeContainer&) = default; PtreeContainer(PtreeContainer&&) = default; PtreeContainer& operator=(PtreeContainer&&) = default;bool operator==(std::nullptr_t) const noexcept { return empty(); } bool operator!=(std::nullptr_t) const noexcept { return !(*this == nullptr); } bool operator==(Node_t* node) const noexcept { return get() == node; } bool operator!=(Node_t* node) const noexcept { return !(*this == node); } bool operator==(PtreeContainer other) const noexcept { return get() == other.get(); } bool operator!=(PtreeContainer other) const noexcept { return !(*this == other); } value_type operator[](size_type index) const noexcept { size_type i = 0; for (auto it = begin(); it != end(); ++it) { if (i++ == index) { return *it; } }return value_type{}; }Iterator begin() const noexcept { return m_nodes; } Iterator end() const noexcept { return nullptr; } bool empty() const noexcept { return begin() == end(); }value_type front() const noexcept { return (*this)[0]; } value_type back() const noexcept { value_type last{}; for (auto cur : *this) { last = cur; }return last; } Node_t* get() const noexcept { return m_nodes; }difference_type count() const noexcept { return std::distance(begin(), end()); } bool has_at_least(size_type n) const noexcept { size_type counter = 0; for (auto it = begin(); it != end(); ++it) { if (++counter == n) { return true; } } return false; }private: Node_t* m_nodes = nullptr; };template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeStatementList = PtreeContainer<PtreeStatementIterator, Node_t, Deref_t>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeItemList = PtreeContainer<PtreeListIterator, Node_t, Deref_t>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeCountedStatementList = PtreeContainer<PtreeStatementCountingIterator, Node_t, Deref_t>;template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>> using PtreeCountedItemList = PtreeContainer<PtreeListCountingIterator, Node_t, Deref_t>;
