Введение

В статье описана ленивая реализация обхода дерева на языке 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) за его вклад в реализацию и обсуждение проекта.