Реализация 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 примитива по исключению карточки из цепи, исключение карточки с поля, и потом удаление самой карточки. Если такую цепь откатить, то за одно действие отката будет откачен только один примитив, в то время как логичным было бы откатить сразу все. Это требует определенной доработки метода, однако рассмотрим данную проблему в следующей статье.

  • +12
  • 8,4k
  • 8
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 8
  • 0
    В своем редакторе я тоже решал подобную задачу.
    Но сделал чуть по другому — любое действие которое приводит к редактированию было сделано через объект
    EditAction

    соответственно у него были процедуры Do и UnDo
    + процедура bool JoinWith (EditAction) которая по возможности объединялась с предыдущим действием.
    • +2
      Однако, как оказалось, кроме общих принципов и слов найти что-то типа библиотеки сложно.

      А почему не подошел Qt Undo Framework?

      • 0
        1. В нем не решена проблема зависимых объектов, то что я попытался автоматизировать в «ссылочной целостности»
        2. для меня было критично, что в дереве проектов я не мог использовать Qt на том уровне, он появлялся только на GUI-уровне

        при этом соглашусь, что утверждение «найти что-то типа библиотеки сложно» слишком субъективно
        • 0

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

          • 0
            Нет, откат линеен, проблема в другом. Например если рассмотрим цепочку Create -> Move для одного объекта, то в qt-шном варианте предлагается делать new для объекта в создании самой команды Create. У меня создание будет идти непосредственно в apply, а в undo будет сделан delete. При возврате действия, надо будет для Move-а соответственно восстановить указатель на новый созданный объект. В этом и заключается сложность.
      • 0
        Я тоже в своем редакторе тоже решал подобную задачу на javascript. Если я правильно помню основную идею, то на каждое действие создавалась команда с undo / redo.

        Написать подробнее в рамках комментария затруднительно, но если кого-то заинтересовало, что в итоге получилось, можно попробовать тут: http://30pxart.com/Edit. Минификация сломалась, исходники доступны в консоли.
        • 0
          Для сценариев в какой сфере ваш софт? В геймдеве использую articy:draft, так создалось впечатление, что это что-то похожее (хотя сценариями функционал articy:draft не ограничивается).
          • 0
            Изначально для кино-сценариев. Но как показала практика — хорошо подходит для любых художественных историй, даже для поэм.
            Из articity:draft я хочу слизать частично дизайн для новой версии (пока не релизнута). А сам софт мне очень не понравился с точки зрения отзывчивости — они похоже написали свою gui-подсистему на openGL, не решили мноого классических проблем (с тем же антиалиасингом на зуме), не обеспечили отзывчивость. Но функциональность там конечно богатая, там на мой взгляд даже сценарии вторичны.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.