Реалізація Undo/Redo моделі для складного документа

Привіт Хабр! У цій статті я хочу показати, як можна організувати модель редагування документа зі складною структурою з можливістю відміни/повернення дій.
Передісторія і проблематика
Все почалося з того, що я писав вузькоспеціалізований outline-софт, де основна ідея полягає в оперуванні купою віртуальних паперових карток на різних сценах у різних редакторах.
Вийшло схоже на MS Visio з певним ступенем кастомізації і плагинизации. Ніяких технічних складнощів тут немає, проте є ряд особливостей.
По-перше, кілька сцен. А значить і віконних редакторів потрібно кілька, кожен з яких працює за своїми правилами.
По-друге, т. к. набір карток один, а одна і та ж картка може бути використана в різних місцях, то це породжує певні залежності між різними частинами документа. І, якщо картка віддаляється, то це тягне за собою усунення цієї картки з усіх місць, де вона задіяна.
по-третє, коли я зробив все, що хотів, і показав результати другу (який навіть не програміст), то він потикав і сказав, що непогано б зробити Ctrl+Z. Я загорівся ідеєю, але ось реалізувати це виявилося не такою тривіальною задачею. У цій статті я опишу, до чого прийшов у підсумку.
Існуючі рішення
Звичайно, перш ніж робити що-то своє, я сподівався знайти що-то готовий. Досить докладний аналіз проблематики наводиться в Undo і Redo — аналіз та реалізації. Однак, як виявилося, крім загальних принципів і слів знайти що-то типу бібліотеки складно.
Перше і найочевидніше рішення — це робити версію документа на кожну зміну. Звичайно, це надійно, але займає багато місця і зайвих операцій. Тому такий варіант був відкинутий відразу ж.
Більш цікавим здається memento pattern. Тут вже можна трохи заощадити ресурси за рахунок використання стану документа, а не самого документа. Але це знову ж таки, залежить від конкретної ситуації. А т. к. писав я все на C++, то тут я б не отримав ніякого виграшу. При цьому, навіть існує C++ template проект undoredo-cpp, що реалізує даний патерн.
Command patter в принципі те що потрібно, але, на жаль, можна знайти тільки принципи, але не універсальні реалізації. Тому він і був узятий за основу. І, звичайно ж, хотілося досягти максимальної продуктивності, з чого випливала мінімізація зберігання даних.
Таким чином, стало приблизно зрозуміло, як і що хочеться отримати на рівні реалізації. І вийшло виділити конкретні цілі:
  1. Система містить набір редакторів, кожен з яких може редагувати свою сцену.
  2. Будь-яка зміна документа, що відіб'ється на відкритому редакторі, повинне бути донесене до нього, і сам редактор повинен відреагувати на нього максимально ефективно (виключаючи повне перестроювання сцени документа).
  3. Всі зміни глобальні, тобто незалежно в якому редакторі ми зараз, стек змін загальний.
  4. Повинна бути можливість скасування останнього дії, так і повернення (Undo/Redo).
  5. Розмір буфера змін не повинен бути обмежений нічим, крім налаштувань і апаратних ресурсів.
Також слід зазначити, що все писалося на 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 примітиву щодо виключення картки з ланцюга, виключення картки з поля, і потім видалення самої картки. Якщо таку ланцюг відкотити, то за одну дію відкату буде откачен тільки один примітив, в той час як логічним було б відкотити відразу все. Це вимагає певної доробки методу, однак розглянемо дану проблему в наступній статті.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.