Введение
В статье описана ленивая реализация обхода дерева на языке C++ с использованием сопрограмм и диапазонов на примере улучшения интерфейса работы с дочерними элементами класса QObject из фреймворка Qt. Подробно рассмотрено создание пользовательского представления для работы с дочерними элементами и приведены ленивая и классическая его реализации. В конце статьи есть ссылка на репозиторий с полным исходным кодом.
Об авторе
Работаю старшим разработчиком в норвежском офисе The Qt Company. Разрабатываю виджеты и QtQuick элементы, с недавних пор и Qt Core. Использую C++ и немного интересуюсь функциональным программированием. Иногда делаю доклады и пишу статьи.
Что такое Qt
Qt — это кроссплатформенный фреймворк для создания графических интерфейсов пользователя (GUI). Помимо модулей для создания GUI, Qt содержит множество модулей для разработки прикладного программного обеспечения. Фреймворк разработан преимущественно на языке программирования C++, некоторые компоненты используют QML и JavaScript.
Класс QObject
QObject — это класс, вокруг которого построена объектная модель Qt. Классы, унаследованные от QObject, можно использовать в слот-сигнальной модели и цикле обработки событий. Кроме того, QObject позволяет получить доступ к мета-объектной информации класса и организовывать объекты в древовидные структуры.
Древовидная структура QObject
Использование древовидной структуры означает, что каждый объект типа QObject может иметь одного родителя и ноль или несколько детей. Родительский объект управляет временем жизни дочерних объектов. В следующем примере два дочерних объекта будут удалены автоматически:
auto parent = std::make_unique<QObject>(); auto onDestroyed = [](auto obj){ qDebug("Object %p destroyed.", obj); }; QObject::connect(new QObject(parent.get()), &QObject::destroyed, onDestroyed); QObject::connect(new QObject(parent.get()), &QObject::destroyed, onDestroyed); // Дважды выводит сообщение об удалении объекта
К сожалению, пока что большая часть API Qt работает только с сырыми указателями. Мы работаем над этим, и возможно скоро ситуация изменится к лучшему хотя бы частично.
Интерфейс класс QObject позволяет получить список всех дочерних объектов и осуществлять поиск по некоторым критериям. Рассмотрим пример получения списка всех дочерних объектов:
auto parent = std::make_unique<QObject>(); // Создадим 10 дочерних объектов for (std::size_t i = 0; i < 10; ++i) { auto obj = new QObject(parent.get()); obj->setObjectName(QStringLiteral("Object %1").arg(i)); } const auto& children = parent->children(); qDebug() << children; // => (QObject(0x1f7ffa0, name = "Object 0"), ...) qDebug() << children.count(); // => 10
Метод QObject::children возвращает список всех дочерних для данного объекта элементов. Однако часто требуется поиск среди всего поддерева объектов по некоторому критерию:
auto children = parent->findChildren<QObject>(QRegularExpression("0$")); qDebug() << children.count();
Пример выше демонстрирует, как можно получить список всех дочерних элементов типа QObject, имя которых заканчивается на 0. В отличие от метода children, метод findChildren осуществляет рекурсивный обход дерева, то есть ищет по всей иерархии объектов. Это поведение можно изменить, передав флаг Qt::FindDirectChildrenOnly.
Недостатки интерфейса работы с дочерними элементами
На первый взгляд может показаться, что интерфейс работы с дочерними элементами достаточно продуман и гибок. Однако и он не лишён недостатков. Рассмотрим некоторые из них:
- Избыточный интерфейс
Есть два различных методаfindChildren(не так давно их было три): методfindChildдля поиска одного элемента и метод children. Все они частично дублируют друг друга. - Интерфейс сложно изменить
Qt гарантируют бинарную совместимость и совместимость на уровне исходного кода в рамках одного мажорного релиза. Следовательно, нельзя так просто менять сигнатуру метода или добавлять новые методы. - Интерфейс сложно расширить
Помимо нарушения совместимости, невозможно, например, получить список дочерних элементов по заданному критерию. Чтобы добавить такую функциональность, необходимо ждать следующего релиза или создавать ещё один метод. - Избыточное копирование всех элементов
Зачастую необходимо просто пройтись по списку всех дочерних элементов, отфильтрованных по заданному критерию. Для этого совсем не обязательно возвращать контейнер указателей на все эти элементы. - Возможное нарушение SRP
Это довольно спорный вопрос, однако же необходимость изменять интерфейс класса для изменения, скажем, метода обхода дочерних элементов выглядит странно.
Использование range-v3 для устранения некоторых недостатков
range-v3 — это библиотека, которая предоставляет компоненты для работы с диапазонами элементов. По сути, это дополнительный слой абстракции над классическими итераторами, который позволяет компоновать операции и пользоваться преимуществами ленивых вычислений.
Сторонняя библиотека используется потому, что на момент написания статьи не существует известных автору компиляторов со встроенной поддержкой этой функциональности. Возможно, ситуация изменится в скором времени.
Для QObject использование данного подхода позволит отделить операции обхода дерева дочерних элементов от класса и создать гибкий интерфейс поиска объектов по заданному критерию, который можно будет легко модифицировать.
Пример использования ranges-v3
Для начала рассмотрим простой пример использования библиотеки. Прежде чем перейти к примеру, введём сокращённые обозначения для пространств имён:
namespace r = ranges; namespace v = r::views; namespace a = r::actions;
Теперь рассмотрим пример программы, которая напечатает кубы всех нечётных чисел в интервале [1, 10) в обратном порядке:
auto is_odd = [](int n) { return n % 2 != 0; }; auto pow3 = [](int n) { return std::pow(n, 3); }; // Выведет [729,343,125,27,1] std::cout << (v::ints(1, 10) | v::filter(is_odd) | v::transform(pow3) | v::reverse);
Следует обратить внимание на то, что все вычисления происходят лениво, т.е. временные массивы данных не создаются и не копируются. Программа выше эквивалентна такой, за исключением форматирования выходных данных:
// Выведет 729 343 125 27 1 for (int i = 9; i > 0; --i) { if (i % 2 != 0) { std::cout << std::pow(i, 3) << " "; } }
Как видно из примера выше, библиотека позволяет изящно компоновать различные операции. Больше примеров использования можно найти в директориях tests и examples репозитория range-v3.
Класс для представления последовательности дочерних элементов
Библиотека range-v3 предоставляет вспомогательные классы для создания различных пользовательских классов-обёрток; среди них и классы из категории view. Эти классы предназначены для представления последовательности элементов определённым образом без преобразования и копирования самой последовательности. В предыдущем примере был использован класс filter, чтобы рассматривать только те элементы последовательности, которые соответствуют заданному критерию.
Чтобы создать такой класс для работы с дочерними элементами QObject, его необходимо унаследовать от вспомогательного класса ranges::view_facade:
namespace qt::detail { template <class T = QObject> class children_view : public r::view_facade<children_view<T>> { // Вспомогательная функциональность friend r::range_access; // Указатель на объект, с дочерними элементами которого планируется работать T *obj; // Параметры поиска элементов (рекурсивно или нет) Qt::FindChildOptions opts; // Курсор -- это аналог итератора cursor begin_cursor() { return cursor(obj, opts); } public: // Конструкторы }; } // namespace qt::detail
Стоит отметить, что класс автоматически определяет метод end_cursor, который возвращает признак конца последовательности. В случае необходимости этот метод можно переопределить.
Далее определим сам класс курсора. Это можно сделать как внутри класса children_view, так и за его пределами:
struct cursor { // Контейнер, который содержит все дочерние элементы std::shared_ptr<ObjectVector> children; // Индекс текущего элемента std::size_t current_index = 0; // Метод получения доступа к текущему элементу decltype(auto) read() const { return (*children)[current_index]; } // Переход к следующему элементу void next() { ++current_index; } // Проверка признака конца последовательности auto equal(ranges::default_sentinel_t) const { return current_index == children->size(); } // Конструкторы };
Курсор, определённый выше, однопроходный (single-pass). Это означает, что по последовательности разрешается двигаться только в одном направлении и только один раз. Для данной реализации это не обязательно, т.к. мы храним последовательность всех дочерних объектов и можем проходить по ним в любом направлении сколько угодно раз. Чтобы указать, что по последовательности можно проходить несколько раз, необходимо реализовать следующий метод в класс cursor:
auto equal(const cursor &that) const { return current_index == that.current_index; }
Теперь необходимо добавить сделать так, чтобы созданное представление можно было включать в композицию. Для этого используем вспомогательную функцию ranges::make_pipeable:
namespace qt { constexpr auto children = r::make_pipeable([](auto &&o) { return detail::children_view(o); }); constexpr auto find_children(Qt::FindChildOptions opts = Qt::FindChildrenRecursively) { return r::make_pipeable([opts](auto &&o) { return detail::children_view(o, opts); }); } } // namespace qt
Теперь можно писать такой код:
for (auto &&c : root | qt::children) { // Обработка все дочерних объектов (рекурсивно) } for (auto &&c : root | qt::find_children(Qt::FindDirectChildrenOnly)) { // Обработка только прямых наследников }
Реализация существующей функциональности класса QObject
После реализации класса представления можно легко реализовать всю функциональность по работе с дочерними элементами. Для этого нужно реализовать три функции:
namespace qt { template <class T> const auto with_type = v::filter([](auto &&o) { using ObjType = std::remove_cv_t<std::remove_pointer_t<T>>; return ObjType::staticMetaObject.cast(o); }) | v::transform([](auto &&o){ return static_cast<T>(o); }); auto by_name(const QString &name) { return v::filter([name](auto &&obj) { return obj->objectName() == name; }); } auto by_re(const QRegularExpression &re) { return v::filter([re](auto &&obj) { return re.match(obj->objectName()).hasMatch(); }); } } // namespace qt
В качестве примера использования рассмотрим следующий код:
for (auto &&c : root | qt::children | qt::with_type<Foo*>) { // Обработка всех дочерних элементов с типом Foo }
Промежуточные выводы
Как можно судить по коду, теперь довольно просто расширять функциональность без изменения интерфейса класса. Помимо этого, все операции представлены отдельными функциями и могут быть скомпонованы в нужную последовательность. Это, в числе прочего, улучшает читабельность кода и позволяет уйти от использования функций с несколькими параметрами в интерфейсе класса. Также стоит отметить разгрузку интерфейса класса и уменьшение количества причин его изменять.
По сути, данная реализация уже устраняет практически все перечисленные недостатки интерфейса, за исключением того, что нам всё ещё приходится копировать все дочерние элементы в контейнер. Один из вариантов решения этой проблемы — использование сопрограмм.
Ленивая реализация обхода дерева объектов с использованием сопрограмм
Сопрограммы (coroutines) позволяют приостановить выполнение функции и возобновить его позднее. Можно рассматривать эту технологию как некоторый конечный автомат.
На момент написания статьи в стандартной библиотеке отсутствуют множество важных элементов, необходимых для комфортного использования сопрограмм. Поэтому предлагается использовать стороннюю библиотеку cppcoro, которая, вероятно, войдёт в стандарт в том или ином виде.
Для начала напишем функции, которые будут возвращать следующий дочерний элемент по требованию:
namespace qt::detail { cppcoro::recursive_generator<QObject*> takeChildRecursivelyImpl( const QObjectList &children, Qt::FindChildOptions opts) { for (QObject *c : children) { if (opts == Qt::FindChildrenRecursively) { co_yield takeChildRecursivelyImpl(c->children(), opts); } co_yield c; } } cppcoro::recursive_generator<QObject*> takeChildRecursively( QObject *root, Qt::FindChildOptions opts = Qt::FindChildrenRecursively) { if (root) { co_yield takeChildRecursivelyImpl(root->children(), opts); } } } // namespace qt::detail
Инструкция co_yield возвращает значение вызывающему коду и приостанавливает выполнение сопрограммы.
Теперь интегрируем этот код в класс children_view. В следующем коде приведены только изменившиеся элементы:
// В классе children_view // Инициализируется как Data{obj, takeChildRecursively(obj, opts)} struct Data { T *obj; cppcoro::recursive_generator<QObject*> gen; }; std::shared_ptr<Data> m_data; // ... cursor begin_cursor() { return cursor(m_data->gen.begin()); }
Курсор тоже необходимо модифицировать:
template <class T> struct children_view<T>::cursor { cppcoro::recursive_generator<QObject*>::iterator it; decltype(auto) read() const { return *it; } void next() { ++it; } auto equal(ranges::default_sentinel_t) const { return it == cppcoro::recursive_generator<QObject*>::iterator(nullptr); } explicit cursor(cppcoro::recursive_generator<QObject*>::iterator it): it(it) {} cursor() = default; };
Курсор здесь выступает просто в роли обёртки вокруг обычного итератора. Остальной код можно использовать как есть, без дополнительных изменений.
Опасности ленивого обхода дерева
Стоит отметить, что ленивый обход дерева дочерних элементов не всегда безопасен. В первую очередь это касается обхода сложных иерархий графических элементов, например, виджетов. Дело в том, что в процессе обхода иерархия может быть перестроена, а некоторые элементы и вовсе удалены. Если использовать ленивый обход в этом случае, то можно получить очень интересные и непредсказуемые результаты работы программы.
Это означает, что в некоторых случаях полезно скопировать все элементы в контейнер. Для этого можно использовать следующую вспомогательную функцию:
auto children = ranges::to<std::vector>(root | qt::children);
Строго говоря, в этом случае в использовании сопрограмм нет необходимости и можно использовать представление из первой итерации.
Будет ли это в Qt
Возможно, но не в следующем релизе. Этому есть несколько причин:
- Следующий мажорный релиз — Qt 6 — будет официально требовать и поддерживать C++17, но не выше.
- Нет возможности реализовать без сторонних библиотек.
- Относительно сложно будет адаптировать существующую кодовую базу.
Скорее всего, к этому вопросу вернутся в рамках релиза Qt 7.
Заключение
Предлагаемая реализация обхода дерева дочерних элементов позволяет легко добавить новую функциональность. За счёт разделения операций достигается написание более чистого кода и удаление лишних элементов из интерфейса класса.
Стоит отметить, что обе использованные библиотеки (range-v3 и cpp-coro) поставляются в виде заголовочных файлов, что упрощает процесс сборки. В будущем возможно будет обойтись вообще без сторонних библиотек.
Однако у описанного подхода есть некоторые недостатки. Среди них можно отметить непривычный для многих разработчиков синтаксис, относительную сложность внедрения и ленивость, которая может быть опасна в некоторых случаях.
Дополнительно
Отдельное спасибо Мише Светкину (Trilla) за его вклад в реализацию и обсуждение проекта.
ссылка на оригинал статьи https://habr.com/ru/post/481402/
Добавить комментарий