Привет! В данной статье я хочу показать, как можно организовать модель редактирование документа со сложной структурой с возможностью отмены/возврата действий.
Предыстория и проблематика
Все началось с того, что я писал узкоспециализированный 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 примитива по исключению карточки из цепи, исключение карточки с поля, и потом удаление самой карточки. Если такую цепь откатить, то за одно действие отката будет откачен только один примитив, в то время как логичным было бы откатить сразу все. Это требует определенной доработки метода, однако рассмотрим данную проблему в следующей статье.
Автор: ultrablox
