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

В прошлых сериях:

• DOM-подобные структуры данных: что такое, почему они присутствуют везде, как узнать, насколько хорошо их поддерживает ваш язык программирования (бенчмарк CardDOM)

• Пример реализации CardDOM языках со сборщиком мусора на примере JavaScript

• Реализация в языках с подсчетом ссылок и смарт-поинтерами на примере C++

Сегодня мы рассмотрим реализацию Card DOM задачи на языке Rust.

Исходная задача

Краткий повтор, чтобы не ходить по ссылкам:

• Для сравнения языков программирования в задачах на обработку иерархий объектов предлагается тестовое задание — упрощенный "редактор карточек".
  

  

• Документ редактора содержит несколько карточек, каждая из которых хранит элементы: текстовые блоки со стилями, изображения, кнопки, коннекторы и группы (вложенные контейнеры).

• Редактору требуется: копирование, удаление, редактирование документов, карточек и их элементов; изменение стилей и работа с перекрестными ссылками (напирмер, кнопки ссылаются на карточки, а коннекторы — на элементы карточек). Все операции обязаны выполняться корректно и безопасно, без сбоев и падений при удалении объектов.

• Документы и элементы изменяемы, тогда как стили и битмапы — неизменяемые и общие для разных элементов и модифицируются по принципу copy-on-write.

• Удаление любого объекта должно автоматически обрывать связанные ссылки, а попытки обращения к ним — контролироваться без крашей.

• При копировании карточек и элементов необходимо сохранять структуру связей, чтобы копии ссылались на копии, а не на оригиналы.

• В иерархии не должно быть закольцовок. Группы не могут содержать сами себя или свои подгруппы, а каждый элемент карточки должен иметь одного владельца — карточку или группу.

Все остальные подробности — в оригинальной статье.

Реализация на Rust

Полный исходный код (330 строк) доступен в Rust Playground.

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

• Rc<RefCell> для композиции. Как и в случае с unique_ptr в C++ мы не можем использовать Box<T> для хранения DomNode поскольку на них могут ссылаться перекрестные ссылки. Дерево изменяемых объектов будет определяться Rc<RefCell<T>>.

• Weak<T> для перекрестных связей. Кнопки и коннекторы хранят Weak<RefCell<T>> на целевые элементы или карточки, предотвращая циклы.

• Rc<T> для разделяемых ресурсов. Стили и битмапы шарятся между элементами карточек через Rc<T>, обеспечивая общее владение и неизменяемость данных.

• Глубокое копирование. Выполняется вручную в два прохода через DeepCopyContext и HashMap, чтобы корректно восстановить перекрестные ссылки.

• Проверки во время выполнения. Несмотря на заявление о строгом учете владения в языке, оно не работает для единственного указателя, пригодного для DOM-иерархий (Rc). Так что Мультипарентинг и циклы в графе владения предотвращаются через ручные проверки, с возвратом ошибок (Error::MultiParenting, Error::Loop).

• Полиморфизм без наследования. Тема была подробно обсуждена в этой статье: Rust и приведение типов. Там же в комментариях был дан совет использовать enum, что делает архитектуру простой, хоть это и создает множество других проблем.

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

Создание иерархии объектов

let doc = Document::new();
{
    let style = Style::new("Times".to_string(), 16.5, 600);
    let card = Card::new();
    let hello = CardItem::new_text("Hello".to_string(), style.clone());
    let button = CardItem::new_button("Click me".to_string(), Rc::downgrade(&card));
    let connector = CardItem::new_connector(
           Rc::downgrade(&hello), Rc::downgrade(&button));
    assert!(card.borrow_mut().add_item(hello).is_ok());
    assert!(card.borrow_mut().add_item(button).is_ok());
    assert!(card.borrow_mut().add_item(connector).is_ok());
    assert!(doc.borrow_mut().add_card(card).is_ok());
}

Из-за того, что проверки древовидности структуры выполняются в рантайме, конструирования должны сопровождаться ассертами. Кстати добавляет динамический проверок и тот факт, что наши элементы карточек не самостоятельные типы проверяемые при компиляции, а enum tags, требующие рантайм проверки на UnsupportedOperation.

Изменение стиля через копирование

Поскольку стили и битмапы — неизменяемые ресурсы, разделяемые между множеством текстовых блоков и картинок, любое их изменение должно выполняться через copy-on-write.

{
    let hello_item = doc.borrow().cards[0].borrow().items[0].clone();
    let hello_borrow = hello_item.borrow();
    if let CardItemKind::Text { style, .. } = &hello_borrow.kind {
        let new_style = style.clone_resized(style.size + 1.0);
        drop(hello_borrow); // Release immutable borrow
        assert!(hello_item.borrow_mut().set_style(new_style).is_ok());
    }
}

Обратите внимание на ручное управление временем заимствования drop(hello_borrow) если этого не сделать, программа упадет. Альтернатива — с блоком-инициализатором локальной переменной - еще менее читаемая:

{
   let hello_item = doc.borrow().cards[0].borrow().items[0].clone();
   let new_style = {
       let hello_borrow = hello_item.borrow();
       if let CardItemKind::Text { style, .. } = &hello_borrow.kind {
           style.clone_resized(style.size + 1.0)
       } else {
           return; // don't ask me where to
       }
   };
   assert!(hello_item.borrow_mut().set_style(new_style).is_ok());
}

Защита времени жизни

RefCell паникует при нарушении правил заимствования и при удалении объекта с активным borrow. Таким образом, Rust предотвращает удаление объектов, методы которых всё ещё на стеке, не продлевая их жизнь, как в языках со сборкой мусора или как shared_ptr в C++, а в соответствии с Бусидо, через харакири. Программист должен сам организовать владение и синхронизацию вокруг этих ограничений. Таким образом, следующее требование невыполнимо: «Удаление любых объектов из иерархии не должно вызывать сбоев».

Автоматический обрыв перекрестных ссылок при удалении объекта

{
    // Remove item and check weak references
    let card = &doc.borrow().cards[0];
    {
        let hello = card.borrow().items[0].clone(); // 1
        card.borrow_mut().remove_item(&hello);      // 2
    }
    let connector = &card.borrow().items[1]; // 3
    assert!(matches!(
        &connector.borrow().kind,
        CardItemKind::Connector { from, .. } if from.upgrade().is_none()
    ));
}

При удалении объекта перекрестный ссылки на него удаляются автоматически. Но есть несколько нюансов.

Обратите внимание, что удаление элемента из карточки делается в два приема (1) (2). Этому есть причина — borrow checker.

• В строке (1) card.borrow() создаёт Ref, живущий до конца выражения.

• В строке (2) вызывается card.borrow_mut(), которому нужен изменяемый заём, но прошлый Ref еще не отпущен.

Rust не допускает пересечения таких времен жизни, поэтому нужно сначала завершить неизменяемый заём — то есть разделить код на два выражения. И так повсюду. Вместо прямолинейного решения задачи программистам приходится искать обходные пути или как минимум писать, читать и сопровождать вдвое больше кода.

Кстати, весь код от строки (3) до конца делает (в псевдокоде):
assert((card[1] as Connector).from.isEmpty)

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

let new_doc = copy(&doc);

{ // Verify topological correctness
    let new_card = &new_doc.borrow().cards[0];
    let new_conn = &new_card.borrow().items[1];
    if let CardItemKind::Connector { to, .. } = &new_conn.borrow().kind {
        assert!(ptr::eq(
            Rc::as_ptr(&new_card.borrow().items[0]),
            to.upgrade().map(|rc| Rc::as_ptr(&rc)).unwrap_or(ptr::null())
        ));
    }
    if let CardItemKind::Button { target_card, .. } = &new_card.borrow().items[0].borrow().kind {
       assert!(ptr::eq(
            Rc::as_ptr(&new_card),
            target_card.upgrade().map(|rc| Rc::as_ptr(&rc)).unwrap_or(ptr::null())
       ));
    }
}

Копирование не является встроенной операцией. Оно выполняется точно таким же способом, как в С++-версии.

Обратите внимание, что проверка корректности двух ссылок на С++ записывалась бы так:

assert(new_doc->cards[0]->items[0] ==
   std::dynamic_pointer_cast<ConnectorItem>(new_doc->cards[0]->items[1])->to.lock());

assert(new_doc->cards[0] ==
   std::dynamic_pointer_cast<ButtonItem>(new_doc->cards[0]->items[0])->target.lock());

Тоже не очень компактно и удобно, но все же раза в несколько раз проще.

Предотвращение мульти-владения (Runtime)

let result = doc.borrow_mut().add_card(
       new_doc.borrow().cards[0].clone());
assert!(matches!(result, Err(Error::MultiParenting)));

Работает, но все проверки делаются вручную и в рантайме.

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

let group = CardItem::new_group();
let subgroup = CardItem::new_group();
assert!(add_subitem(&group, subgroup.clone()).is_ok());
let result = add_subitem(&subgroup, group.clone());
assert!(matches!(result, Err(Error::Loop)));

Аналогично предыдущему, тоже работает, но тоже вручную и в рантайме.

Оценка Rust CardDOM

Вывод

Модель владения в Rust (Rc, Weak, RefCell) гарантирует безопасную работу с памятью, но ценой сложности, многословия и ручного контроля за временем жизни ссылок и структурной целостностью. Она устраняет неопределённое поведение C++, но вводит новые риски — паники при заимствовании и рост когнитивной нагрузки: порой ручное жонглирование бесконечными borrow/drop/upgrade/clone тратит больше времени и сил, чем собственно решение задачи. Не решается и проблема утечек памяти.

Из-за отсутствия классического наследования полиморфизм реализуется через enum или trait-диспетчеризацию, что дробит логику и повышает связность программы.

Кроме того, значительная часть продакшн-кода на Rust использует unsafe — напрямую или через зависимости — чтобы обойти чрезмерные ограничения и вернуть производительность, гибкость или доступ к низкоуровневым функциям. Это показывает противоречие в философии языка:

• безопасность без падений остается недостижимым идеалом,

• в то время как суровая реальность — это паники и многократно переусложненный код.

Изо всех исследованных языков в задаче поддержки объектной модели документов Раст показал себя хуже всего.

Какой язык протестировать следующим? GoLang? Python? Или отказаться от своего принципа не рекламировать Аргентум, и показать этот пример на нем?

ЗЫ. По просьбам читателей сравнительная таблица для других экспериментальных и не очень языков