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

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

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

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

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

• CardDOM на Rust плюс краткий анализ Zig, Odin, Jai, GoLang, Python, The V, Nim, Cone, Pony, плюс в комментах - реализация D-lang by Siemargl

Сегодня мы рассмотрим реализацию задачи CardDOM на языке Аргентум.

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

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

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

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

  

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

• Документы и элементы — изменяемые, а стили и битмапы — общие и неизменяемые, меняются только по схеме copy-on-write (не важно — автоматической или ручной).

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

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

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

Остальные детали — в исходной статье.

Полная реализация CardDOM

В Argentum DOM-подобные структуры данных реализуются декларативно, поскольку все типы DOM-ссылок встроены в язык:

• Дерево изменяемых объектов удерживается композитными ссылками (они гарантируют единственность владельца)

• Сеть перекрестных ссылок задается ассоциативными ссылками (слабыми ссылками, с автоматическим разрывом при удалении таргета)

• Ациклический граф неизменяемых ресурсов обеспечивается агрегатными ссылками (шареными ссылками на неизменяемые объекты).

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

Не требуется никакого дополнительного кода для операций копирования, удаления слабых ссылок, отслеживания не изменяемого состояния и т.д. Неизменяемость объектов-ресурсов, мультипарентинг и циклы в дереве владения проверяются на этапе компиляции.

Пример кода можно найти в Argentum Playground. Он занимает всего 30 строк, поэтому статья содержит его полностью с объяснением синтаксиса:

Argentum не имеет встроенных в язык массивов — Array это класс который импортируется из модуля sys:

using sys { Array }

Объявление классов Style и Bitmap c полями string, double и int64.

Поля обязаны быть инициализированы, при этом выражение инициализации задает и начальное значение и тип:

class Style {
    font = "";
    size = 0.0;
    weight = 0;
}
class Bitmap {
    src = "";
}

Родительский класс для всех элементов карточек (может быть интерфейсом при необходимости):

class CardItem {}

Классы для документа и карточки.

class Document {
    cards = Array(Card);
}
class Card {
    items = Array(CardItem);
}

• Поля cards и items — композитные указатели на массивы.

• Array — массив композитных указателей.

• Array(CardItem) и Array(Card) — дженерики.

Классы элементов карточек:

class Text {
    +CardItem;      // Базовый класс
    text = "";
    style = *Style; // Неизменяемый шареный объект-ресурс
}
class Image {
    +CardItem;
    bitmap = *Bitmap; // Неизменяемый шареный объект-ресурс
}
class Button {
    +CardItem;
    caption = "";
    targetCard = &Card; // Слабая ссылка
}
class Connector {
    +CardItem;
    from = &CardItem;  // Еще две
    to = &CardItem;    // слабых ссылки
}
class Group {
    +CardItem;
    items = Array(CardItem);
}

На этом все. Реализация Card DOM закончена. Далее идет пример использования

Создание начальных объектов

// Создаем экземпляр класса Document и сохраняем в локальную переменную doc
// типа "Уникально-владеющий (композитный) указатель на Document"
doc = Document;

// Создаем карточку и добавляем её в массив cards документа.
// Метод append возвращает временно-стековый указатель на вставленную карту.
card = doc.cards.append(Card);

// Style создает экземпляр, а конструкция .{} инициализирует его вложенными в {}
// выражениями.
// Внутри {}-скобок имя `_` ссылается на объект, который мы инициализируем.
// Затем оператор `*` замораживает его, превращая в неизменяемый объект.
normal = *Style.{
    _.font := "Times";
    _.size := 16.5;
    _.weight := 600
};
// Переменная `normal` — "Шареный указатель на неизменяемый экземпляр Style"

Создание переменной vs модификация:

• normal = выражение декларирует новую локальную переменную или поле объекта

• size := 16 присваивает новое значение существующей переменной или полю

// Создаем элемент Text, заполняем его, добавляем в карточку
// и сохраняем ссылку на него в переменную helloText
// (тип переменной - "временно-стековый указатель на CardItem")
helloText = card.items.append(Text.{
   _.text := "Hello";
   _.style := normal;  // шареный указатель на замороженный объект
});
buttonOk = card.items.append(Button.{
    _.caption := "Click me";
    _.targetCard := &card;  // слабая ссылка
});
card.items.append(Connector.{
    _.from := &helloText;
    _.to := &buttonOk;
});

Использование встроенного имени "_" не обязательно. На самом деле в языке нет конструкции Class.{ _.field := value }, тут скомбинированы две конструкции:

1. <выражение>.<лямбда с одним параметром>

2. и { выражения через ";" использующие имя "_" } которое задает такую лямбду.

Конструкция <выражение>.<лямбда> работает так:

1. вычисляется выражение слева

2. вызывается лямбда с результатом этого выражения в качестве параметра

3. результат лямбды (void) игнорируется.

4. результат выражения становится результатом операции "."

Есть другие способы задавать лямбды, например, `parameterName { lambda body }. Используя такой синтаксис, последнее выражение можно переписать так:

card.items.append(Connector.`conn{
    conn.from := &helloText;
    conn.to := &buttonOk;
});

Все вместе:

doc = Document.{
    normal = *Style.{
        _.font := "Times";
        _.size := 16.5;
        _.weight := 600;
    };
    _.cards.append(Card.`c{
        helloText = c.items.append(Text.{
            _.text := "Hello";
            _.style := normal;
        });
        buttonOk = c.items.append(Button.{
            _.caption := "Click me";
            _.targetCard := &c;
        });
        c.items.append(Connector.{
            _.from := &helloText;
            _.to := &buttonOk;
        });
    });
};

Альтернативное создание объектов

Код конструирования объектной иерархии можно упростить, если добавить несколько методов в наши классы:

class Document {
    with(c()@Card) this {
        cards.append(c)
    }
}
class Style {
    call(f str, s double, w int) this {
        font := f;
        size := s;
        weight := w
    }
}
class Card{
    add(c()@CardItem) CardItem {
        items.append(c)
    }
}
class Text {
    call(t str, s *Style) this {
        text := t;
        style := s
    }
}
class Connector {
    call(f CardItem, t CardItem) this {
        from := &f;
        to := &t
    }
}
class Button {
    call(c str, t Card) this {
        caption := c;
        targetCard := &t;
    }
}

Теперь код конструирования может быть таким:

doc = Document.with(Card.`c {
    helloText = c.add(Text("Hello", *Style("Times", 16.5, 600)));
    buttonOk = c.add(Button("Click me", c));
    c.add(Connector(helloText, buttonOk))
});

Оба варианта конструируют такой DOM:

Копирование с сохранением топологии

Оператор @ создаёт копию с учётом топологии:

newDoc = @doc;

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

Вставим в документ его собственную карточку.

doc.cards.append(doc.cards[0])

Этот код не скомпилируется, но не из-за мульти-парентинга, а потому что нет проверки на выход индекса за пределы массива, так как cards[0] может не существовать.

Выражение doc.cards[0] вернет optional. Его надо проверить с помощью операторов

doc.cards[0]               // Если cards[0] есть -
   ? doc.cards.append(_)   // вставить его в doc.cards
   : log("все плохо?");  // иначе поругаться в лог

Теперь optional побежден, но код все равно не скомпилируется, на это раз по причине мульти-парентинга. Объект, который мы хотим вставить в документ, уже имеет владельца и Аргентум поймает это на стадии компиляции.

К счастью, мы уже умеем копировать, поэтому вставляем копию:

doc.cards[0] ?            // если карточка[0] есть, 
    doc.cards.append(@_)  // скопировать ее и вставить копию

Теперь все скомпилировалось и заработало.
Кстати, это пример показывает сокращенное условие.

Давайте однако красиво обработаем и случай, когда карточки нет и копировать нечего:

doc.cards.append(    // Вставить в doc.cards...
   doc.cards[0]      // Если cards[0] есть
      ? @_           // ...то его копию
      : Card);       // иначе - новый экземпляр Card

Защита от закольцовок

Чтобы создать закольцовку, нужно:

• иметь поле объекта или элемент массива типа "уникально-владеющий указатель" (композит)

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

В Аргентуме это сделать невозможно из-за следующих правил:

• Переменной (полю, элементу массива) типа "композитная ссылка" можно присвоить только значение типа "композитная ссылка"

• Любое чтение переменной типа "композитная ссылка" возвращает значение типа "временная стековая ссылка", которую нельзя присвоить другим композитным ссылкам.

• Значение типа "композитная ссылка" может быть создано только тремя путями:

  • Созданием нового объекта, например выражение Card

  • Копированием объекта по ссылке любого типа, например @myOtherField.

  • Возвращением именованной переменной типа "композитная ссылка" из блока, лямбды, функции. Такой возврат, в отличие от простого чтения переменной имеет move-семантику и сохраняет композитность.

Давайте попробуем создать закольцовку.

// Вначале мы создаем группу элементов карточек с вложенной группой:
superGroup = Group.{ _.add(Group) };

// А потом попробуем записать ссылку на эту группу в массив вложенной группы
superGroup.items[0] && _~Group // Если superGroup[0] есть, и у него тип Group...
  ? _.add(superGroup); // <- ошибка компиляции нельзя в add передать временную ссылку

Таким образом все закольцовки и прочие нарушения дерева композиции всегда ловятся на стадии компиляции. С помощью вышеперечисленных правил Аргентум гарантирует отсутствие повреждений DOMа и утечек памяти в любых иерархиях мутабельных объектов.

Локальная ссылка продлевает время жизни целевого объекта

doc.cards[1] ? `myCard { // Локальная переменная myCard` удерживает карточку.
   doc.cards.delete(1,1);   // Удаляем эту карточку из дерева.
   // Мы всё ещё можем обращаться к карточке, несмотря на ее удаление из документа.
   log("в моей карточке {myCard.items.size()} элементов");
} // Экземпляр карточки фактически удаляется здесь.

Операторы ? && : || подобно инфиксному оператору "." принимают в качестве правого операнда не просто выражение с "_", а полноценную лямбду, что позволяет делать сложные вложенные {}-блоки и использовать вместо "_" удобное имя, фактически вводя временные переменные, локальные для одного выражения или его части. В вышеприведенном примере мы таким способом ввели переменную myCard и блок, в котором она определена.

Безопасная работа с Weak-ссылками

В Аргентуме слабая ссылка может ссылаться на любой объект без ограничений.

w = &doc;   // w — слабый указатель на наш документ

Но ее нельзя использовать для доступа к объектам. Вначале ее нужно заблокировать - проверить на не-оторванность (на наличие таргет-объекта) и получить временную ссылку, которая будет защищать объект от удаления.

n = w.cards.size();
//   ^
//>>> Ошибка: ожидается временный указатель, а не weak-ссылка на Card

В Аргентуме нет никакого специального синтаксиса для такого блокирования. Вместо этого, в любом контексте где ожидается optional-временная ссылка можно использовать слабую ссылку, и блокировка произойдет автоматически:

log(w                                        // 1
   ? "В документе {_.cards.size()} карточек" // 2
   : "Документа нет");                       // 3

1. Временная ссылка блокируется и получается optional

2. Оператор ? распаковывает optional и мы обращаемся по временной-ссылке _-которая прошла проверку на None

3. Орабатываем случай если ссылка потеряна

Сброс слабого указателя при уничтожении целевого объекта

doc.cards[0]              // Если card[0] существует,
  ? _.items.delete(0, 1); // удалить её helloText по индексу 0 (1 элемент)

assert(doc.cards[0] &&          // Если card[0] существует,
  _.items[1] && _~Connector &&  // и её item[1] существует и имеет тип Connector,
  !_.from);                     // проверить, что его поле from сброшено.

Обратите внимание как в условиях внутри assert каждый оператор && переопределяет имя _ внутри своего правого операнда, превращая его в результат предыдущих проверок - спускаясь по иерархии объектов и уточняя тип:

• вначале это Card

• затем элемент карточки

• и наконец элемент карточки типа Connector

Неизменяемость shared-состояния

// Проверить, что card[1] существует и содержит TextItem по индексу [0]
// и при успехе привязать к нему локальную переменную helloText
// и выполнить следующий блок
doc.cards[1] && _.items[0] && _~Text ? `helloText {

    helloText.style.size := 42.0; // ошибка компиляции: style является неизменяемым

    newStyle = @helloText.style;  // создать глубокую изменяемую копию объекта Style
    newStyle.size := 42.0;        // OK, newStyle — изменяемый

    helloText.style := newStyle;  // ошибка: поле не может ссылаться на изменяемый объект

    helloText.style := *newStyle; // OK, заморозить newStyle и сохранить в helloText.style

    // или все выше написанное одной строкой:
    helloText.style := *(@helloText.style).{ _.size := 42.0 };
}

Пример демонстрирует:

• тип "указатель на неизменяемый объект" (helloText.style)

• гарантию, что неизменяемый объект нигде не будет случайно доступен как изменяемый

• использование автоматических операторов заморозки * и глубокого копирования @ для передачи объектов (копий) между mutable-immutable мирами

• паттерн builder, без использования двух отдельных класссов (изменяемого и неизменяемого).

Аргентум гарантирует отсутствие утечек памяти в иерархиях immutable-объектов, т.к. чтобы создать закольцовку в графе нужно создать дополнительную шареную ссылку между двумя неизменяемыми объектами, но это невозможно сделать т.к. они - не изменяемые. А при отсутствии закольцовок достаточно простого подсчета ссылок, причем в Аргентуме они не atomics.

Проверка правильности операции копирования

В предыдущих выпусках (про С++ и Rust) мы проверяли топологическую корректность операции копирования с помощью серией ассертов, вот таких:

C++:

auto new_doc = deep_copy(doc);
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());

Rust:

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())
       ));
    }
}

В Аргентуме это тоже стоит сделать:

newDoc = @doc;

assert(newDoc.cards[0] &&`card
  card.items[0] && _~Button &&`btn
  btn.targetCard == &card &&
  card.items[1] && _~Connector && _.to == &btn);

Этот код не только компактнее, он имеет несколько дополнительных преимуществ:

• Выполняет больше проверок по сравнению с C++ и Rust (полный список):

  • существует ли card[0] в newDoc в С++ это было UB, в Rust - panic

  • существуют ли items[0] и [1] в карточке,

  • является ли items[0] Button

  • является  ли items[1] Connector

  • указывает ли поле to у коннектора на кнопку

  • указывает ли поле target кнопки на карточку

• Он вводит читаемые, типизированные и проверенные на null имена для удобства понимания условий.

• Все введенные имена живут только в пределах выражения.

• Индексация cards и items, проверки на null и приведения типов выполняются ровно один раз.

Оценка Argentum CardDOM

Вывод

Большинство современных языков программирования пытаются решить проблему управления абстрактными структурами данных в общем виде. И эти решения получаются весьма посредственными: утечки памяти, нарушения композиции, бесконтрольное шарение мутабельного состояния, повреждения данных, тонны рукописного кода, многочисленные проверки и падения в рантайме.

Аргентум идет противоположным путем - изо всех универсальных структур данных были выбраны и поддержаны только те, что реально используются высокоуровневыми приложениями - те, что укладываются в систему UML-ссылок - композиция-ассоциация-агрегация, только те, что составляют Объектную Модель Документов. Это избранное подмножество было реализовано непосредственно в языке, что позволило автоматизировать все операции и обеспечить отсутствие утечек памяти, безопасность и эффективность.

Является ли Аргентум серебрянной пулей?

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

• Для всего низкоуровневого - нет. Для этого есть другие языки, которые можно вызывать из Аргентума через FFI - тот же C/C++.