Comments 42
Т.е к аллокации(выделение и распределение памяти) и сортировке(найти/вставить) вернулись с этим "домом"
Очередная нейростатья, где афтор поленился даже глупые llm-паттерны убрать, все эти сравнения, метафоры — по-любому это писал живой человек)
Технически это выражается в подсчёте ссылок или составления обычного линейного массива указателей на объекты с детектированием не высвобожденных сущностей, путём введения туда флажков (ценой увеличения памяти). Включая флажки синхронизации и детектирования гонки данных. Другое дело что это поддерживается самим языком из коробки. Но таких языков где явно можно управлять виртуальными функциями, скрытыми атрибутами классов, исключения по доступу вне границ специально выделенной кучи, вроде как нет. Железобетонно и в явном виде это может делать только подобный С.
Поскольку, требований к сложности нет, а упор в основном на скорость и безопасность, то Rust лидер.
GC языки будут тормозить, особенно в 95 перцентиле. С++ требует высокой дисциплины, не страхует от ошибок
Особо приглашаются любители Раста - это ваш шанс показать насколько Rust заточен для реальных задач.
Привет
Ваш хваленый Rust не решает проблему циклический зависимостей и множественного владения.
Пока.
Множественное владение это не проблема а ошибка дизайна.
Циклические зависимости не появляются, если использовать слабые ссылки, которые не мешают удалить элемент
Классический пример: дерево. Родитель владеет детьми (Rc<Node>), а дети лишь ссылаются на родителя (Weak<Node>).
Живите теперь с этим
Множественное владение может быть требованием задачи (как в текущем случае), и если язык не может это реализовать, то это проблема дизайна языка программирования.
Живите теперь с этим :--)
Реализация не может быть требованием. Я даже удивлен, что это надо писать буквами в комментарий.
Вам выше написали, как язык это реализует - Rc, Weak и т.д.
Я даже знаю такие языки где на уровне языка это решается. Целых джва. Go, PHP.
Появились дедлоки или утечка памяти - прихлопнуть процесс. Делов то. Бггг
PHP: max_execution_time истёк — убили скрипт, пользователь пусть обновит страницу.
Go: дедлок детектор в рантайме паникует и роняет всю программу / микросервис а супервайзер рестартит. "Лучше упасть, чем зависнуть".
Это как "решение" проблемы с памятью через перезагрузку сервера каждую ночь. Работает? Да. Решение? Ну такое.
Rust лидер
Вполне может быть. Однако, чтобы доказать это,все равно придется показать реализацию этого бенчмарка на Rust и проанализировать его на соответствие критериям.
Минимальный набор тестов (описания)
1. Удаление карточки обрывает перекрёстные ссылки
Сценарий: Создать документ с двумя карточками. В первой карточке разместить кнопку, ссылающуюся на вторую карточку. Удалить вторую карточку.
Ожидание: Обращение к цели кнопки возвращает «ссылка недоступна» (например,
nullилиNone). Программа не падает.
2. Глубокое копирование сохраняет внутренние связи
Сценарий: Создать карточку, содержащую текстовый блок и коннектор, ссылающийся на этот блок. Сделать глубокую копию карточки.
Ожидание: В копии коннектор указывает на копию текстового блока (а не на оригинал). Изменение текста в оригинале не влияет на копию.
3. Copy-on-write для стилей
Сценарий: Создать два текстовых блока с одним и тем же стилем. Изменить стиль одного из них (например, размер шрифта).
Ожидание: Стиль второго блока остаётся неизменным. Это подтверждает, что ресурсы разделяются до момента изменения.
4. Запрет циклической вложенности
Сценарий: Создать группу элементов. Попытаться вставить эту группу в саму себя (напрямую или через промежуточную подгруппу).
Ожидание: Операция отклоняется (ошибка, исключение или возврат
false). Структура остаётся целостной.
5. Безопасное удаление изнутри элемента
Сценарий: Создать карточку с элементом, у которого есть метод (например, «обработчик клика»), вызывающий удаление своей собственной карточки из документа. Вызвать этот метод.
Ожидание: Карточка успешно удаляется. Программа не падает, нет use-after-free или dangling pointers.
6. Единственность владельца
Сценарий: Создать карточку и попытаться добавить её в два разных документа (или дважды в один).
Ожидание: Вторая попытка добавления отклоняется. Аналогично для элементов: нельзя вставить один и тот же элемент в две разные карточки или группы.
Почему этого достаточно?
Эти 6 тестов покрывают все три слоя модели из ТЗ:
Дерево владения тесты 4, 6
Сеть перекрёстных ссылок тесты 1, 2, 5
DAG (ориентированный ациклический граф) неизменяемых ресурсов тест 3
Так? Это соответствует табличке
use std::rc::{Rc, Weak};
use std::cell::RefCell;
// === Ошибки ===
#[derive(Debug, PartialEq)]
pub enum DomError {
AlreadyHasOwner,
WouldCreateCycle,
InvalidOperation, // для прочих недопустимых действий
}
// === Style и Bitmap неизменяемы и безопасны) ===
#[derive(Clone, Debug, PartialEq)]
pub struct Style { /* ... */ }
impl Style {
pub fn new(font_size: i32, color: String) -> Self;
pub fn with_font_size(&self, new_size: i32) -> Self;
pub fn with_color(&self, new_color: String) -> Self;
}
#[derive(Clone, Debug)]
pub struct Bitmap { /* ... */ }
impl Bitmap {
pub fn new(width: u32, height: u32, data_hash: u64) -> Self;
}
// === Element ===
pub type ElementRef = Rc<RefCell<Element>>;
#[derive(Debug)]
pub enum Element {
Text { content: String, style: Rc<Style> },
Image { bitmap: Rc<Bitmap> },
Connector { target: Weak<RefCell<Element>> },
Button { target_card: Weak<RefCell<Card>> },
Group { children: Vec<ElementRef> },
}
impl Element {
pub fn text(content: String, style: Rc<Style>) -> Self;
pub fn image(bitmap: Rc<Bitmap>) -> Self;
pub fn connector() -> Self;
pub fn button() -> Self;
pub fn group() -> Self;
pub fn deep_clone(&self) -> ElementRef;
// Работа со ссылками — всегда безопасна, ошибок нет
pub fn set_target(&mut self, target: &ElementRef);
pub fn get_target(&self) -> Option<ElementRef>;
pub fn set_target_card(&mut self, card: &Rc<RefCell<Card>>);
pub fn get_target_card(&self) -> Option<Rc<RefCell<Card>>>;
// Добавление в группу — может завершиться ошибкой
pub fn add_child(&mut self, child: ElementRef) -> Result<(), DomError>;
}
// === Card ===
#[derive(Debug)]
pub struct Card {
pub elements: Vec<ElementRef>,
has_owner: bool,
}
impl Card {
pub fn new() -> Self;
pub fn add_element(&mut self, element: ElementRef) -> Result<(), DomError>;
pub fn deep_clone(&self) -> Rc<RefCell<Card>>;
}
// === Document ===
#[derive(Debug)]
pub struct Document {
pub cards: Vec<Rc<RefCell<Card>>>,
}
impl Document {
pub fn new() -> Self;
pub fn add_card(&mut self) -> Rc<RefCell<Card>>; // всегда успешно
pub fn remove_card(&mut self, card: &Rc<RefCell<Card>>); // всегда успешно
}Тесты
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_button_target_becomes_none_after_card_deletion() {
let mut doc = Document::new();
let card1 = doc.add_card();
let card2 = doc.add_card();
let button = Rc::new(RefCell::new(Element::button()));
card1.borrow_mut().add_element(button.clone()).unwrap();
// Устанавливаем ссылку на card2
button.borrow_mut().set_target_card(&card2);
// Удаляем card2
doc.remove_card(&card2);
// Проверяем, что ссылка стала недоступна
assert!(button.borrow().get_target_card().is_none());
}
#[test]
fn test_deep_clone_preserves_internal_references() {
let mut doc = Document::new();
let card = doc.add_card();
let text = Rc::new(RefCell::new(Element::text(
"Hello".to_string(),
Rc::new(Style::new(12, "#000000".to_string())),
)));
let connector = Rc::new(RefCell::new(Element::connector()));
card.borrow_mut().add_element(text.clone()).unwrap();
card.borrow_mut().add_element(connector.clone()).unwrap();
connector.borrow_mut().set_target(&text);
// Копируем карточку
let cloned_card = card.borrow().deep_clone();
// Извлекаем копии
let cloned_elements = &cloned_card.borrow().elements;
let cloned_text = cloned_elements[0].clone();
let cloned_connector = cloned_elements[1].clone();
// Проверяем: коннектор ссылается на копию текста
let target = cloned_connector.borrow().get_target().unwrap();
assert_eq!(
target.borrow().as_text().unwrap().content,
"Hello"
);
// Проверяем, что это разные объекты
assert_ne!(
Rc::as_ptr(&text),
Rc::as_ptr(&cloned_text)
);
}
#[test]
fn test_style_copy_on_write() {
let base_style = Rc::new(Style::new(12, "#000000".to_string()));
let text1 = Rc::new(RefCell::new(Element::text("A".to_string(), base_style.clone())));
let text2 = Rc::new(RefCell::new(Element::text("B".to_string(), base_style.clone())));
// Меняем стиль у text1
let new_style = base_style.with_font_size(16);
text1.borrow_mut().as_text_mut().unwrap().style = Rc::new(new_style);
// text2 должен остаться с оригинальным стилем
assert_eq!(text1.borrow().as_text().unwrap().style.font_size, 16);
assert_eq!(text2.borrow().as_text().unwrap().style.font_size, 12);
}
#[test]
fn test_group_cannot_be_inserted_into_itself() {
let group = Rc::new(RefCell::new(Element::group()));
let result = group.borrow_mut().add_child(group.clone());
assert_eq!(result, Err(DomError::WouldCreateCycle));
}
#[test]
fn test_safe_deletion_from_within_element_callback() {
let mut doc = Document::new();
let card = doc.add_card();
// Имитируем "обработчик", который удаляет карточку
let doc_ref = Rc::new(RefCell::new(doc));
let card_ref = card.clone();
let doc_weak = Rc::downgrade(&doc_ref);
// Создаём элемент с замыканием (в реальности — через поле, здесь упрощённо)
let _element = Rc::new(RefCell::new(Element::text(
"Click me".to_string(),
Rc::new(Style::new(12, "#000000".to_string())),
)));
// Выполняем удаление "изнутри"
{
let mut doc_strong = doc_weak.upgrade().unwrap();
doc_strong.borrow_mut().remove_card(&card_ref);
}
// После удаления карточка больше не в документе
// (проверка через подсчёт — в реальной реализации можно добавить is_removed флаг)
// Главное: не упало
}
#[test]
fn test_element_cannot_be_added_to_multiple_groups() {
let elem = Rc::new(RefCell::new(Element::text(
"Shared".to_string(),
Rc::new(Style::new(12, "#000000".to_string())),
)));
let group1 = Rc::new(RefCell::new(Element::group()));
let group2 = Rc::new(RefCell::new(Element::group()));
// Первое добавление — успешно
assert!(group1.borrow_mut().add_child(elem.clone()).is_ok());
// Второе — ошибка
assert_eq!(
group2.borrow_mut().add_child(elem.clone()),
Err(DomError::AlreadyHasOwner)
);
}
}Ну, а реализация как нибудь на неделе )
Спасибо. Пекрасное переложение текста в тесты и прекрасный Раст-код (декларации). Очень профессионально и четко.
Не то, чтобы я не согласен вот с этим решением, но у меня есть несколько вопросов:
pub enum Element {
Text { content: String, style: Rc<Style> },
Image { bitmap: Rc<Bitmap> },
Connector { target: Weak<RefCell<Element>> },
Button { target_card: Weak<RefCell<Card>> },
Group { children: Vec<ElementRef> },
}Мне кажется, что этот подход:
Усложнит в будущем архитектеру, потоу что
В будущем мы планируем добавлять новые типы элементов карточек. А при использованииenum-а, нам придется вписывать куски кода для их поддержки в десятки мест, вместо добавления нового типа данных в отдельном модуле, если использовать полиморфные типы данных.Может ударить по памяти, если один из элементов
enum-а будет иметь слишком много прожорливых по памяти атрибутов.Не позволяет адекватно моделировать ограничения предметной области с помощью системы типов, например
Element::set_target_cardприменим только к кнопкам, но может быть вызван у любогоElement-а, нарушение этого правила не поймается на этапе компиляции.
Может быть стоит сделать полиморфизм через dyn CardItem?
В любом случае, каким бы ни было ваше решение,
спасибо за очень профессональный код и подход.
PS. Это не должно потеряться в виде 100-500-го комментария. Сделайте это отдельной статьёй.
Операции тут сложны, должны учитывать несколько правил и потому enum для облегчения проверок этих правил
Да, enum нарушает принцип «открытость/закрытость» (OCP): чтобы добавить новый элемент нужно менять enum и все match-выражения.
Но в DOM-подобных структурах это оправдано:
Типы элементов известны на этапе проектирования (текст, картинка, кнопка, группа, их не сотни),
А глубокое копирование, обход, сериализация, проверка циклов требуют полного знания всех вариантов и
enumдаёт это безопасно и явно.
Полиморфизм только маскирует проблему, придётся делать проверки типов вручную с возможностью ошибиться.
Проблема выражения не даёт одновременно легко расширять типы и функции. Но здесь лучше enum: стабильный набор типов и расширяемое множество операций. Типы согласно ТЗ будет добавляться, но заранее известно, что их немного.
А... Вот ещё:
Инварианты/правила глобальные, для нескольких типов сразу. Поэтому, нельзя размазать одно правило на несколько кусочков в каждом типе отдельно (будет не читаемо).
Зачем статьёй? Мы же сравним с вашим решением в вашей новой статье? Могу и я статью написать, конечно...
P.S.
Тяжёлые элементы если они появятся я вынесу в Box<>
Video { url: String, metadata: Box<HugeStruct> }set_target_card вынесу в конкретный тип
Написал Card DOM на JavaScript: https://habr.com/en/articles/956542/
Общий итог - JS безопасен по памяти. И на этом его сильные стороны заканчиваются.
Написал аналогичный Card DOM на С++ https://habr.com/en/articles/957906/
Итог - С++ немного помогает, но ничего не гарантирует.
GC пауз нет, но и нет и безопасности.
Контроль единственности владельца. Карточка не может быть вставлена в несколько документов одновременно и не может быть вставлена в один и тот же документ несколько раз. Аналогично с элементами карточек — они должны иметь строго одного владельца — или карточку или группу.
Почему накладывается такое ограничение? Почему не может быть двух владельцев у одного объекта?
Это логическое ограничение уровня бизнес логики. Если карточка вставлена в несколько документов, то все операции с ней будут происходить во всех документах одновременно. Представьте себе редактор PowerPoint, где вставив карточку в два открытых документа и исправив ее в одном мы автоматически получим изменение в другом документе, который сейчас вообще не на экране - это был бы явный баг. Или нажимая одну кнопку на карточке мы увидим ее анимацию нажатия в десяти местах только потому что она была вставлена в десяток разных групп.
Правло единственного владельца это общее правило всех DOM-структур, например в Qt виджет имеет строго одного владельца, или в HTML DOM каждый атрибут и каждый элемент присутствует в дереве сторого в одном месте.
Это логическое ограничение уровня бизнес логики.
Это возможное ограничение одной конкретной бизнес логики, но оно не логичное и не обязательно для всех возможных сценариев использования.
Например, с помощью DOM можно описываться иерархия форм ввода и меню пользователя согласно его роли, в котором поле ввода для авторизации может иметь несколько владельцев, т.к. находится в разных пункта дерева меню.
Эти поля ввода - это независимые объекты, лежащие в своих формах (и даже возможно создаваемые динамически) но связанные с одним и тем же полем модели данных.
Qt и HTML DOM не случайно не позволяют шарить виджеты между формами.
Я пишу про иерархию форм меню пользователя, которая так же очень хорошо описывается DOM структурой. Считайте, что это не виджет отдельной формы, а форма целиком (т.е. тот-же DOM, но на уровень выше одного документа).
Qt и HTML DOM не случайно не позволяют шарить виджеты между формами.
Кстати, в Qt я могу очень легко расшарить виджет между формами, создавая его динамически.
Стили и битмапы — неизменяемые ресурсы, разделяемые между текстовыми блоками и картинками. Любое их изменение должно выполняться через copy-on-write.
Так не изменяемые или изменяемые через copy-on-write? Это принципиально различные требования, которые требуют совершенно разной реализации в коде (особенно при работе в нескольких потоках).
Copy-on-write может быть
автоматическим, когда система неявно копирует объект при изменениях,
полуавтоматическим, когда система позволяет сделать копию явно перед изменениями, но если этого не следано явно, делает это незаметно при первом изменении, например QSharedDataPointer::detach(),
ручным, когда система запрещает изменения объекта, пока он не будет скопирован и переведен в статус изменяемого.
Вы можете использовать любой вариант, до тех пор пока предотвращается модификация расшаренных объектов.
Я понимаю, что можно сделать по разному, но вы пишите требования, которые я и стараюсь понять. Вам нужна оптимизация для редко изменяемых объектов (Copy-on-write) или вам нужны именно НЕ изменяемые объекты.
Если первое, то в реализации потребуется контроль чтения записи и синхронизация доступа в рантайме при многопоточной работе, тогда как для второго варианта (только чтение) ненужно вообще ничего, что упрощает реализацию в разы, а все проверки делаются во время компиляции.
Любой вариант по вашему выбору, до тех пор пока предотвращается модификация расшаренных объектов
Любой вариант по вашему выбору, до тех пор пока предотвращается модификация расшаренных объектов
Мы наверно говорим про разные вещи или друг друга просто не понимаем, так как требования определяет заказчик (задача), а не по выбору исполнителя.
Но в этом конкретном случае, я подозреваю, что требования нужно разделить на два разных пункта, отдельно - константные не изменяемые объекты (проверка во время компиляции), и расшаренные - изменяемые, но с захватом блокировки, а как - на усмотрение разработчика в конкретной реализации.
Расшаренные объекты всегда неизменяемые. (Указатель допускающий мульти-парентинг -всегда указатель на immutable). Но с них можно снять изменяемые копии, которые после изменения можно сделать неизменяемыми снова присвоить в этот указатель.
Вы повторяете уже написанное, но не объясняете почему, тогда как меня интересует ответ именно на этот вопрос.
Не изменяемые объекты, это понятно - проверка во время компиляции и не нужно никаких дополнительных проверок.
Изменяемые данные - тоже понятно, захватили блокировку, изменили, сняли блокировку.
Изменяемые данные с Copy-on-write - тоже самое, что и изменяемые данные, но экономим память при множестве копий одного и того же объекта. При изменении данных - создаем новый объект.
Откуда берется утверждение, что расшаренные данные всегда должны быть не изменяемыми? Данные могут быть не изменяемыми, но это не связано с множественностью владельцев.
Или вы пытаетесь натянуть систему типов Аргентума на классические алгоритмы?
Откуда берется утверждение, что расшаренные данные всегда должны быть не изменяемыми
Сушествует два вида шаренья:
изменяемые данные хранятся на каком-то уровне дома или на них ссылаются все, кто угодно (как, например, таблица именованных стилей текста, которая может жить в странице, секции, документе, группе документов)
данные, которые хранятся вне уровней, шарятся без ограничений в глобальном смысле, но тогда они просто обязаны быть неизменяемыми (как строки в Java).
Когда страница скопируется в пределах документа, стили относящаяся к странице должы скопироваться и редактироваться независимо от оригинальной страницы, а стили относящиеся к документу останутся общими. Разница между скопированными и расшаренными объектами проявляется только для изменяемых объектов. Поэтому только для них нужно фиксировать уровень DOM-а которому они принадлежат.
Первый метод шаренья реализуется композитными ссылками, которые тестируются в Card DOM через document->card->cardItems и перекрестными ссылками, которые тестируются через button->card и connector->cardItems.
Второй (limitless) метод шаренья тестируется через text->style и image->bitmap. И в нем действительно не должно быть мутабельных объектов.
Мы с вами вошли в какой-то деструктивный цикл.
Я вам уже привел примеры как минимум трех вариантов расшаренных объектов, а вы почему вы упорствуете, что могут быть только всего два варианта "шаренья".
Та же самая картинка в документе (документах) может принадлежать:
одной странице (иллюстрация на одной странице документе)
всем страницам одного документа (колонтитулы)
одной для группы документов (шапка раздела)
одной для всех документов сразу (штамп или заголовок бланка организации)
Поэтому у данных могут быть один или несколько владельца, данные могут быть константные во время компиляции или изменяемые/не изменяемые во время выполнения, изменяемые данные могут редактироваться в рамках только одного или сразу нескольких потоков или даже асинхронно.
Это все разные и не связанные между собой свойства данных, и не важно, в DOM они находятся или нет.
Я вам уже привел примеры как минимум трех вариантов расшаренных объектов, а вы почему вы упорствуете, что могут быть только всего два варианта "шаренья".
Вы приводите три варианта изменяемых-неизменяемых-cow объектов. Это вообще не про шаринг.
Я привел два варианта шаринга - один с мутабельностью, но баундед на уровень DOM-a, другой - без баундинга но и без мутабельности. Вы не находите, что мы говорим про разные вещи?
картинка в документе (документах) может принадлежать
Нужно различать "картинку", которая определяет координаты, место в иерархии, ноду в рендер-сцене, флаг сфокуссированности и пр. атрибуты, индивидуальные для каждого инстанса картинки в документе и неизменяемый "битмап"-ресурс, который шарится между всеми этими картинками.
Почему Qt / Win32 / MFC / WPF / WinForms / GTK / JavaFX / Swing / HTML DOM / OpenXML-Microsoft Word / LibreOffice-ODF / PDF object model / Google Docs и все остальные GUI и документные фреймворки в мире запрещают мультипарентинг всего, кроме неизменяемых ресурсов? Вам стоит написать свой фреймворк, лишенный такого ограничения. И если он заработает как надо, я на него перейду первым.
Да, мы говорим про разные вещи, ведь ДОМ не ограничивается только "документными фреймворками". Но вижу, что как и в прошлый раз, я так и не получу ответа, на свой вопрос :-(
Принцип shared xor mutable появился не вчера и не в Расте. И шаринг - он не про многопоточнось а про логическую непротиворечивость данных. Только выделив домен для каждого изменяемого состояния можно построить структуру которая не сломает твое приложение в будущем, в то время как неизменяемое состояние не привязано ни к каким доменам и поэтому может шариться без ограничений. Ты получил ответ на свой вопрос. Просто он, похоже, непонятный.
Это не ответ на мой вопрос, но теперь хотя бы стало немного понятно, откуда растут ноги в ваших требованиях. Ваше мнение имеет право быть именно такими, просто я пытаюсь в который раз вам показать, что ваши требования к ДОМ не покрывают всех возможных сценариев и структур данных.
Из-за этого вы можете отказаться в положении разработчиков Rust, когда красивая идея "единственного владельца" не может реализовать схему с множественным владением, из-за чего приходится идти на разные ухищрения и переделки архитектуры, либо писать unsafe код, фактически обнуляя исходную идею безопасного языка.
Кажется формулировка задачи слишком сильно привязана к классовой модели. Есть также и другие подходы к моделированию. Это сильно сужает полезность данного теста.
Например, взять ту же Julia. Опыт показывает что на ней прекрасно пишется моделирование и довольно нетривиальные взаимодействия. Но при этом, кажется, конкретно Ваш тест она завалит.
Базы данных: записи и документы, вложенные в таблицы и коллекции и связанные ключами.
Не буду говорить об остальных пунктах, но конкретно в реализации баз данных никакого dom нет. Там сильно по-другому строиться архитектура.
На Julia можно написать редактор карточек? Если да, у этой программы будет модель документа, пусть не из таких классов а из чего-то другого. И у этой модели обязательно будет копирование и прочие перечисленные действия (просто потому что они нужны редактору). Тест не требует решить задачу определенным образом. Сдейлайте по-своему - и посмотрим сколько пунктов и как это решение закроет.
Особо приглашаются любители Раста - это ваш шанс показать насколько Rust заточен для реальных задач.
Да, пожалуйста, смотрите https://github.com/servo/servo The Servo Parallel Browser Engine Project. Концепция DOM там реализована.
Настоящий тест для языков программирования — как они справляются с DOM-подобными структурами данных