Реализация DOM-подобных структур данных на C++ / Хабр

Это третья статья в серии про DOM-подобные модели данных в различных языках программирования.
В предыдущих частях:

DOM-подобные структуры данных: что это такое, где встречаются и как оценить их поддержку в вашем языке программирования.
Как JavaScript справляется с DOM-подобными структурами данных

Сегодня мы рассмотрим как с Card DOM справился С++.

Код

Код на С++ почти вдвое компактнее JS-версии (всего ~158 строк), но это все равно слишком много для включения в статью, поэтому он доступен по ссылке: https://www.mycompiler.io/view/G4ypqaNpDml.

Детали реализации

Мы используем weak_ptr для перекрестных ссылок.
Мы можем полагаться на автоматическую очистку объектов и обрыв перекрестных ссылок с помощью деструкторов.
Хотя узлы нашего дерева имеют ровно одного владельца, мы не можем использоват�� unique_ptr поскольку на них могут ссылаться weak_ptr. поэтому все владеющие ссылки в нашем DOM будут shared_ptr.
Мы не можем использовать конструкторы копий для создания топологически-корректных копий объектных иерархий, поскольку такое копирование - двухпроходный процесс, он требует формирования и использования map(оригинал->копия). Поэтому мы реализуем глубокое копирование вручную.
Поскольку мы используем shared_ptr для представления всех владеющих указателей нам придется вручную детектировать наличие циклов и множественных владельцев в графе владения.
Мы можем использовать shared_ptr<const T> для представления разделяемых ресурсов. Это не даст стопроцентной гарантии неизменяемости, но может помочь поймать некоторые ошибки на стадии компиляции.
Когда мы удаляем объект из DOM, на него могут указывать raw-указатели из стека. Даже если мы передаем параметры в функции и храним локальные ссылки как shared_ptr<T>, мы все равно рискуем, потому что this все равно передается как T*. Требуется или предельная аккуратность при кодировании или следование правилу, когда всякий вызов метода производится по временно созданному shared_ptr<T>, который будет предотвращать случайное удаление объекта.

Примеры использования

Создание документа

auto doc = make_shared<Document>();
{
    auto style = make_shared<const Style>("Times", 16.5, 600);
    auto card = make_shared<Card>();
    auto hello = make_shared<TextItem>("Hello", style);
    auto button = make_shared<ButtonItem>("Click me", card);
    auto conn = make_shared<ConnectorItem>(hello, button);
    card->add_item(move(hello));
    card->add_item(move(button));
    card->add_item(move(conn));
    card->add_item(make_shared<GroupItem>());
    doc->add_item(move(card));
}

Начальное состояние как в JS-серсии (синее-изменяемое состояние, красное - неизменяемое, зеленое-невладеющие ссылки)

Разделяемые ресурсы: clone-on-mutation

auto hello_text = dynamic_pointer_cast<TextItem>(doc->items[0]->items[0]);

// Попытка изменить замороженный стиль
hello_text->style->size++;  // Ошибка компиляции

// Изменение через копию
auto new_style = hello_text->style->clone();
new_style->size++;
hello_text->style = new_style;

В этом коде, объект, который уже считается разделяемым, все еще доступен по не-константной ссылке new_style

Продление времени жизни с помощью стековой ссылки

{
    auto hello_text = dynamic_pointer_cast<TextItem>(doc->items[0]->items[0]);
    doc->items[0]->remove_item(hello_text);

    // hello_text всё ещё жив и доступен по перекрестной ссылке from из коннектора 
    assert(!dynamic_pointer_cast<ConnectorItem>(
        doc->items[0]->items[1])->from.expired());

} // Удаление происходит здесь

Глубокое копирование с сохранением топологии

auto new_doc = deep_copy(doc);

// Убеждаемся, что в копии перекрестные ссылки показывают так же, как в оригинале
assert(new_doc->items[0]->items[0] ==
    dynamic_pointer_cast<ConnectorItem>(
        new_doc->items[0]->items[1])->to.lock());

assert(new_doc->items[0] ==
    dynamic_pointer_cast<ButtonItem>(
        new_doc->items[0]->items[0])->target_card.lock());

Защита от мульти-владения

try {
    doc->add_item(new_doc->items[0]);
} catch (std::runtime_error&) {
    std::cout << "multiparented!\n";
}

Предотвращение циклов

try {
    auto group = make_shared<GroupItem>();
    auto subgroup = make_shared<GroupItem>();
    group->add_item(subgroup);
    subgroup->add_item(group);

} catch (std::runtime_error&) {
    std::cout << "loop\n";
}

Оценка: как C++ справился с DOM-подобными структурами

Критерий	Да	Но
Безопасность памяти	Умные указатели помогают.	С++ - не дает гарантий безопасности.
Предотвращение утечек	Умные указатели и RAII помогают бороться с утечками.	С++ не предотвращает утечки.
Ясность владения	Разделение `shared_ptr` и `weak_ptr` задаёт декларативные границы владения.	За уникальностью владения приходится следить вручную. `unique_ptr` тут неприменим.
Копирование	—	Полностью ручная реали��ация.
Слабые ссылки	Обрываются автоматически, требуют проверки перед использованием.	`lock()` возвращает `shared_ptr`, поэтому неосторожное использование может привести к закольцовкам в графе владения и утечкам.
Устойчивость	—	С++ - небезопасный язык. При работе со структурами данных, даже с использованием умных указателей требуется дисциплина и аккуратность.
Выразительность		Код многословен: `make_shared<GroupItem>()`,`dynamic_pointer_cast<ButtonItem>(t)`
Момент обнаружения ошибок	Проверки неизменяемости разделяемых ресурсов производятся при компиляции благодаря `shared_ptr<const T>`	Проверки закольцовок и множественного владения - происходят только во время исполнения. Тесты обязательны. Много тестов.

Итог: C++ дает контроль, но требует дисциплины, помогает но ничего не гарантирует

C++ предоставляет тонкий контроль над временем жизни и владением,
позволяя построить DOM-подобную структуру с относительно безопасными ссылками и минимальными утечками.

Однако отсутствие встроенной защиты памяти требует избегания сырых указателей и жесткой дисциплины при использовании умных указателей.

В приложении к DOM-подобным структурам язык когнитивно сложен и не безопасен.

Реализация DOM-подобных структур данных на C++

Код