[Из песочницы] Реализация Undo/Redo модели для сложного документа26.10.2016 15:04

Привет Хабр! В данной статье я хочу показать, как можно организовать модель редактирование документа со сложной структурой с возможностью отмены/возврата действий.


Предыстория и проблематика


Все началось с того, что я писал узкоспециализированный 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;
    std::vector 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
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;

    std::vector data;
    std::map 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
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(event->primitive->baseEntity.get());
        pScene->create_image(p_collision);
        break;
    }
    ...
}

Правда стоит отметить, что если иерархия типов модифицирующего примитива для какой-то сущности разрастается, то внутри придется делать новые ветвления.


И это действительно работает


Описанный метод не ограничен моей моделью документа, и может быть использован в различных моделях документах. Если кому-то интересно посмотреть это в действии, то само скомпиленное приложение можно скачать на странице ultra_outliner.


Заключение


В рамках предложенного метода остался непроработанным один немаловажный вопрос. Большинство действий пользователя над документами действительно являются атомарными, однако часть из них производят сразу несколько примитивов. Например, если пользователь двигает карточку — это один примитив. А если он удаляет карточку, которая находится в 3х путях — то это 3 примитива по исключению карточки из цепи, исключение карточки с поля, и потом удаление самой карточки. Если такую цепь откатить, то за одно действие отката будет откачен только один примитив, в то время как логичным было бы откатить сразу все. Это требует определенной доработки метода, однако рассмотрим данную проблему в следующей статье.

Комментарии (2)

  • 26 октября 2016 в 14:25

    0

    ↑

    ↓

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

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

  • 26 октября 2016 в 14:49 (комментарий был изменён)

    0

    ↑

    ↓

    Однако, как оказалось, кроме общих принципов и слов найти что-то типа библиотеки сложно.

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

© Habrahabr.ru