Привет Хабр! В данной статье я хочу показать, как можно организовать модель редактирование документа со сложной структурой с возможностью отмены/возврата действий.
Предыстория и проблематика
Все началось с того, что я писал узкоспециализированный outline-софт, где основная идея заключается в оперировании кучей виртуальных бумажных карточек на разных сценах в разных редакторах.
Получилось похоже на MS Visio с определенной степенью кастомизации и плагинизации. Никаких технических сложностей здесь нету, однако есть ряд особенностей.
Во-первых, сцен несколько. А значит и оконных редакторов нужно несколько, каждый из которых работает по своим правилам.
Во-вторых, т.к. набор карточек один, а одна и та же карточка может быть использована в разных местах, то это рождает определенные зависимости между разными частями документа. И, если карточка удаляется, то это влечет за собой устранение этой карточки из всех мест, где она задействована.
В-третьих, когда я сделал все, что хотел, и показал результаты другу (который даже не программист), то он потыкал и сказал, что неплохо бы сделать Ctrl+Z. Я загорелся идеей, но вот реализовать это оказалось не такой тривиальной задачей. В этой статье я опишу, к чему пришел в итоге.
Существующие решения
Конечно, прежде чем делать что-то свое, я надеялся найти что-то готовое. Достаточно подробный анализ проблематики приводится в Undo и Redo — анализ и реализации. Однако, как оказалось, кроме общих принципов и слов найти что-то типа библиотеки сложно.
Первое, и самое очевидное решение — это делать версию документа на каждое изменение. Конечно, это надежно, но занимает много места и лишних операций. Поэтому такой вариант был отброшен сразу же.
Более интересным кажется memento pattern. Здесь уже можно немного сэкономить ресурсы за счет использования состояния документа, а не самого документа. Но это опять же, зависит от конкретной ситуации. А т.к. писал я все на C++, то здесь я бы не получил никакого выигрыша. При этом, даже существует C++ template проект undoredo-cpp, реализующий данный паттерн.
Command patter в принципе то что нужно, но, к сожалению, можно найти только принципы, но не универсальные реализации. Поэтому он и был взят за основу. И, конечно же, хотелось достичь максимальной производительности, из чего вытекала минимизация хранения данных.
Таким образом, стало примерно понятно, как и что хочется получить на уровне реализации. И получилось выделить конкретные цели:
- Система содержит набор редакторов, каждый из которых может редактировать свою сцену.
- Любое изменение документа, которое отразится на открытом редакторе, должно быть донесено до него, и сам редактор должен отреагировать на него максимально эффективно (исключая полное перестроение сцены документа).
- Все изменения глобальные, т.е. независимо в каком редакторе мы сейчас, стэк изменений общий.
- Должна быть возможность как отмены последнего действия, так и возврат (Undo/Redo).
- Размер буфера изменений не должен быть ограничен ничем, кроме настроек и аппаратных ресурсов.
Также следует отметить, что все писалось на QT5/C++11.
Модель документа
Основной сущность, над которой совершаются действия — это документ. К документу могут применяться различные атомарные действия, назовем их примитивами. Атомарность предполагает, что до и после применения примитива документ находится в консистентном состоянии.
В моем документе я выделил следующие сущности (следует отметить, что мой софт предназначался для наброски плана сценария, отсюда и специфика): карточка, персонаж, сюжетная карточка (ссылается на карточку), карточка персонажа (ссылается на карточку), точка сюжетной линии (ссылается на карточку), сюжетная линия (содержит цепь сюжетных карточек) и др. Таким образом, сущности могут ссылаться друг на друга, и это может стать источником проблем в дальнейшем, если мы захотим вернуть действие по созданию сюжетной карточки, которая ссылается на карточку, создание которой мы уже откатили. Т.е. напрашивается некий механизм управления ссылками, но о нем позже.
При выделении примитивов получается примерно следующий набор: создать карточку, поменять текст карточки, удалить карточку, создать сюжетную карточку, создать сюжетную линию, поменять текст сюжетной линии, добавить карточку в сюжетную линию и др. Концептуально любой примитив явно относится по смыслу к какой-то сущности, значит есть смысл ввести типизацию примитивов по адресованной сущности (карточка, сюжетная линия, персонаж и т.д.).
class outline_primitive { public: enum class entity_t { card, plot, act_break, outline_card, ...}; ... entity_t entity; document_t * pDoc; using ref_t = referenced_entity<outline_primitive>; std::vector<ref_t*> dependencies; };
Следует обратить внимание на атрибут dependencies — это как раз зависимости, на которые примитив ссылается, но его назначение будет рассмотрено чуть позже. Также, примитивы можно классифицировать по типу: создание; модификация; удаление.
enum class operation_t { create, modify, remove }; operation_t operation;
При этом, модифицирующие примитивы могут порождать целое дерево, в зависимости от допустимых модификаций — например подвинуть карточку, добавить карточку в сюжетную линию и др.
Примитив может быть применен либо в прямом направлении, либо в обратном. Более того, для удаляющих примитивов и для assert-ов полезно хранить, в каком состоянии примитив — примененном или откатанном.
virtual void outline_primitive::apply() { perform_check(!applied); applied = true; pDoc->unsavedChanges = true; } virtual void outline_primitive::revert() { perform_check(applied); applied = false; pDoc->unsavedChanges = true; } bool applied;
Далее, рассмотрим реализацию простейшего примитива — добавления карточки.
Реализация простейшего примитива
Примерно вот так выглядит реализация примитива создания карточки. Я не буду приводить очевидные рутинные операции, такие как инициализация pDoc и др.
class OUTLINE_DOC_API card_create_primitive : public outline_primitive { index_card * pCard; index_card::data_t cardData; //Данные для создания карточки card_create_primitive::card_create_primitive(const index_card::data_t & _data); void apply() { _Base::apply(); auto p_card = new index_card; //Создаем новую карточку p_card->data = cardData; pDoc->cards.push_back(p_card); //Добавляем в документ pCard = p_card; //И запоминаем указатель } void revert() { _Base::revert(); auto it = std::find(pdoc->cards.begin(), pdoc->cards.end(), pCard); perform_check(it != pdoc->cards.end()); //assert pDoc->cards.erase(it); //Удалим карточку из документа delete pCard; //И очистим сам объект pCard = nullptr; //Теперь карточки как будто никогда не создавалось } }
В код специально добавлены несколько assert-ов, которые подтверждают консистентное состояние документа до и после применения примитива.
Ссылочная целостность
Теперь рассмотрим примитив создание сюжетной карточки. Фактически, это та же карточка, но находящаяся на сюжетном листе и имеющая координату. Т.е. она ссылается на сюжетную карточку и содержит дополнительные атрибуты (координаты).
Таким образом, предположим у нас есть последовательность примитивов — создать карточку, создать сюжетную карточку на ее основе. Тогда 2й примитив надо сослать на первый, при этом обеспечив возможность обновления ссылки, в случае если он будет отменен и восстановлен (с попутным удалением/пересозданием самой карточки).
Для этого и вводится специальная сущность referenced_entity, которую вы уже встречали раньше в списке зависимостей.
template<typename T> struct referenced_entity { using primitive_t = T; using entity_ptr = void; referenced_entity(primitive_t * prim, entity_ptr * p_ent) { ... prim->dependencies.push_back(this); //Поместим себя в список зависимостей примитива } entity_ptr * get() const { if (!parent) return entity; else { auto cur_ref = this; while (cur_ref->parent) cur_ref = &(cur_ref->parent->baseEntity); return cur_ref->entity; } } primitive_t * parent; entity_ptr * entity; };
Здесь важным моментом является помещение себя в список зависимостей примитива. Таким образом, если на содержимое referenced_entity уже кто-то ссылается, то можно восстановить связь в момент помещения примитива в буфер, и потом на основе этой связи получать указатель на текущий адрес объекта с помощью метода get().
Обработка примитивов
Для обработки примитива вводится специальная сущность — command_buffer. В ее задачи входит:
- хранение последовательности примитивов;
- обеспечение ссылочных связей;
- прямое и обратное применение примитивов;
- отброс хвоста при превышении длины;
- генерация событий.
class command_buffer { using primitive_id_sequence_t = std::vector<unsigned>; std::vector<primitive_t*> data; std::map<void*, primitive_id_sequence_t> front; };
В data хранятся примитивы в последовательности их создания пользователем. А в front — так называемый фронт ссылочных объектов. Когда новый примитив попадает в буфер, то он попадает в последний элемент цепи объекта, который хранится в baseEntity. И затем происходит проставление ссылок.
void command_buffer::submit(primitive_t * new_prim) { discard_horizon(); //На случай если висят отмененные команды //Проставить ссылки, если надо for (auto & dep : new_prim->dependencies) { auto front_it = front.find(dep->entity); if (front_it != front.end()) dep->reset_parent(data[*front_it->second.rbegin()]); } unsigned new_id = add_action(new_prim); //Кладем в data новый примититв //Создание ни на что ссылаться не может if (new_prim->operation == primitive_t::operation_t::create) { new_prim->apply(pDoc); primitive_id_sequence_t new_seq; new_seq.push_back(new_id); front.insert(make_pair(new_prim->baseEntity.get(), new_seq)); } else //А вот удаление и модификация - могут, значит надо сославться на фронт { auto front_it = front.find(new_prim->baseEntity.get()); if (front_it == front.end()) { primitive_id_sequence_t new_seq; new_seq.push_back(new_id); front.insert(make_pair(new_prim->baseEntity.get(), new_seq)); new_prim->apply(pDoc); } else { auto & seq = front_it->second; perform_check(!seq.empty()); seq.push_back(new_id); new_prim->apply(pDoc); } } }
Все остальные методы буфера достаточно тривиальны, и они также содержат undo() и redo(). Таким образом, command_buffer обеспечивает консистентное состояние документа, и остается вопрос, как же поддерживать в корректном состоянии представления, формируемые соответствующими редакторами.
Модель взаимодействия
Для этого необходимо ввести новую сущность — событие, и каждый открытый редактор должен правильно реагировать на соответствующий тип событий. Событие связано с применением примитива — до применения, после применения, до отката, после отката. Например, после применения можно делать реакцию на примитивы создания (т.к. до применения объекта еще нету), перед откатом — на те же примитивы создания, т.к. после отката ссылка будет потеряна.
template<typename T> struct primitive_event { using primitive_t = T; enum class kind_t {pre_applied, post_applied, pre_reverted, post_reverted}; kind_t kind; primitive_t * primitive; };
Вот такие события будут рассылаться после каждой из 4х операций над примитивом. Соответственно, в каждом редакторе нужно сделать обработчик, который на эти события будет реагировать, и, соответствнно, миниально перестраивать сцену.
void my_editor::event_occured(event_t * event) { switch..case }
Здесь нужно делать трехэтажный switch..case по сущности, операции и событию, и смотрится это ужасно. Для этого воспользуемся хитростью, основываясь на том, что каждый из элементов можно преобразовать к целому числу, и введем такой макрос.
#define PRIMITIVE_EVENT_ID(entity, operation, event) ((unsigned char)entity << 16) | ((unsigned char)operation << 8) | (unsigned char)event
Тогда тело данного метода примет вот такой вид, и его можно будет дописывать по мере появления новых примитивов без ущерба для удобства восприятия.
switch (PRIMITIVE_EVENT_ID(event->primitive->entity, event->primitive->operation, event->kind)) { case PRIMITIVE_EVENT_ID(outline_primitive::entity_t::collision, outline_primitive::operation_t::create, event_t::kind_t::post_applied): case PRIMITIVE_EVENT_ID(outline_primitive::entity_t::collision, outline_primitive::operation_t::remove, event_t::kind_t::post_reverted): { auto p_collision = static_cast<collision_t*>(event->primitive->baseEntity.get()); pScene->create_image(p_collision); break; } ... }
Правда стоит отметить, что если иерархия типов модифицирующего примитива для какой-то сущности разрастается, то внутри придется делать новые ветвления.
И это действительно работает
Описанный метод не ограничен моей моделью документа, и может быть использован в различных моделях документах. Если кому-то интересно посмотреть это в действии, то само скомпиленное приложение можно скачать на странице ultra_outliner.
Заключение
В рамках предложенного метода остался непроработанным один немаловажный вопрос. Большинство действий пользователя над документами действительно являются атомарными, однако часть из них производят сразу несколько примитивов. Например, если пользователь двигает карточку — это один примитив. А если он удаляет карточку, которая находится в 3х путях — то это 3 примитива по исключению карточки из цепи, исключение карточки с поля, и потом удаление самой карточки. Если такую цепь откатить, то за одно действие отката будет откачен только один примитив, в то время как логичным было бы откатить сразу все. Это требует определенной доработки метода, однако рассмотрим данную проблему в следующей статье.
ссылка на оригинал статьи https://habrahabr.ru/post/313654/
Добавить комментарий