Механизм Save/Load + Undo/Redo с минимальным шаблоном

Ответ 1

Проблема с простым способом, описанным выше, заключается в том, что для этого требуется много ошибок, связанных с работой шаблонов.

Я не уверен, что это так. Ваш подход звучит разумно, и с использованием современных возможностей С++ и абстракций вы можете реализовать для него безопасный и элегантный интерфейс.

Для начала вы можете использовать std::variant как тип суммы для "отмененных действий" - это даст вам тип- безопасный меченый союз для каждого действия. (Рассмотрите возможность использования boost::variant или других реализаций, которые можно легко найти в Google, если у вас нет доступа к С++ 17). Пример:

namespace action
{
    // User dragged the shape to a separate position.
    struct move_shape
    {
        shape_id _id;
        offset _offset;
    };

    // User changed the color of a shape.
    struct change_shape_color
    {
        shape_id _id;
        color _previous;
        color _new;
    };

    // ...more actions...
}

using undoable_action = std::variant<
    action::move_shape,
    action::change_shape_color,
    // ...
>;

Теперь, когда у вас есть тип суммы для всех возможных "отмененных действий", вы можете определить поведение отмены, используя соответствие шаблону. Я написал две статьи о variant "сопоставлении с образцом", перегружая lambdas, которые вы могли бы найти интересными:

• "варианты посещения с использованием lambdas - часть 1"

• "варианты посещения с использованием lambdas - часть 2"

Вот пример того, как может выглядеть ваша функция undo:

void undo()
{
    auto action = undo_stack.pop_and_get();
    match(action, [&shapes](const move_shape& y)
                  {
                      // Revert shape movement.
                      shapes[y._id].move(-y._offset);
                  },
                  [&shapes](const change_shape_color& y)
                  {
                      // Revert shape color change.
                      shapes[y._id].set_color(y._previous);
                  },
                  [](auto)
                  {
                      // Produce a compile-time error.
                      struct undo_not_implemented;
                      undo_not_implemented{};
                  });
}

Если каждая ветвь match становится большой, ее можно перемещать в свою функцию для удобочитаемости. Попытка создать экземпляр undo_not_implemented или использовать зависимый static_assert также является хорошей идеей: ошибка времени компиляции будет произведена, если вы забудете реализовать поведение для определенного "отмененного действия".

Это в значительной степени! Если вы хотите сохранить undo_stack, чтобы история действий сохранялась в сохраненных документах, вы можете реализовать auto serialize(const undoable_action&), который снова использует сопоставление шаблонов для сериализации различных действий. Затем вы можете реализовать функцию deserialize, которая повторно заполняет загрузку undo_stack.

Если вы обнаружите, что реализация сериализации/десериализации для каждого действия слишком утомительна, рассмотрите возможность использования BOOST_HANA_DEFINE_STRUCT или подобных решений для автоматического создания кода сериализации/десериализации.

Поскольку вы обеспокоены батареей и производительностью, я также хотел бы упомянуть, что использование std::variant или аналогичных конструкций тегов с мечеными в среднем быстрее и более легким по сравнению с полиморфными иерархиями, поскольку распределение кучи не требуется, и поскольку это не время отправки virtual.

О функции redo: вы можете иметь redo_stack и реализовать функцию auto invert(const undoable_action&), которая инвертирует поведение действия. Пример:

void undo()
{
    auto action = undo_stack.pop_and_get();
    match(action, [&](const move_shape& y)
                  {
                      // Revert shape movement.
                      shapes[y._id].move(-y._offset);
                      redo_stack.push(invert(y));  
                  },
                  // ...

auto invert(const undoable_action& x)
{
    return match(x, [&](move_shape y)
                {
                    y._offset *= -1;
                    return y;
                },
                // ...

Если вы выполните этот шаблон, вы можете реализовать redo в терминах undo! Просто вызовите undo, выбирая из redo_stack вместо undo_stack: поскольку вы "перевернули" действия, они будут выполнять требуемую операцию.

EDIT: здесь минимальный пример wandbox, который реализует функцию match, которая принимает вариант и возвращает вариант.

• В примере используется boost::hana::overload для создания посетителя.

• Посетитель обернут в lambda f, который объединяет тип возвращаемого типа с типом варианта: это необходимо, так как std::visit требует, чтобы посетитель всегда возвращал тот же тип.

  • Если желательно вернуть тип, отличный от варианта, можно использовать std::common_type_t, иначе пользователь может явно указать его как первый параметр шаблона match.

Ответ 2

Два разумных подхода к этой проблеме реализованы в рамках Flip и ODB.

Генерация кода /ODB

В ODB вам нужно добавить объявления #pragma к вашему коду и заставить инструмент генерировать методы, которые вы используете для сохранения/загрузки и для редактирования модели, например:

#pragma db object
class person
{
public:
    void setName (string);
    string getName();
    ...
private:
    friend class odb::access;
    person () {}

    #pragma db id
    string email_;

    string name_;
 };

Если объявленные в классе аксессоры, автоматически генерируемые ODB, чтобы все изменения в модели могли быть захвачены, и для них могут быть сделаны отмена транзакций.

Отражение с минимальным шаблоном /Flip

В отличие от ODB, Flip не генерирует код С++ для вас, а требует, чтобы ваша программа вызывала Model::declare для повторного объявления ваших структур следующим образом:

class Song : public flip::Object
{
public:
    static void declare ();
    flip::Float tempo;
    flip::Array <Track> tracks;
};

void Song::declare ()
{
    Model::declare <Song> ()
    .name ("acme.product.Song")
    .member <flip::Float, &Song::tempo> ("tempo");
    .member <flip::Array <Track>, &Song::tracks> ("tracks");
}

int main()
{
    Song::declare();
    ...
}

При таком структурированном объявлении конструктор flip::Object может инициализировать все поля, чтобы они могли указывать на стек отмены, и все изменения на них записываются. Он также имеет список всех членов, так что flip::Object может реализовать сериализацию для вас.

Ответ 3

Проблема с простым способом, описанным выше, заключается в том, что для этого требуется много ошибок, связанных с работой шаблонов.

Я бы сказал, что фактическая проблема заключается в том, что ваша логика отмены/повтора является частью компонента, который должен отправлять только кучу данных в виде позиции, содержимого и т.д.

Общим способом ООП отделить логику отмены/повтора от данных является шаблон проектирования команд.
Основная идея заключается в том, что все пользовательские взаимодействия преобразуются в команды, и эти команды выполняются на самой диаграмме. Они содержат всю информацию, необходимую для выполнения операции, и откат ее при условии, что вы сохраняете отсортированный список команд и отменяете/восстанавливаете их по порядку (обычно это ожидание пользователя).

Другим распространенным шаблоном ООП, который может помочь вам либо создать пользовательскую утилиту сериализации, либо использовать наиболее распространенные, является шаблон дизайна посетителей.
Здесь основная идея заключается в том, что ваша диаграмма не должна заботиться о том, какие компоненты она содержит. Всякий раз, когда вы хотите его сериализовать, вы предоставляете сериализатор, а компоненты запрашивают правильный тип при запросе (см. Двойную диспетчеризацию для получения дополнительной информации об этом методе).

При этом минимальный пример стоит более тысячи слов:

#include <memory>
#include <stack>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
#include <string>

struct Serializer;

struct Part {
    virtual void accept(Serializer &) = 0;
    virtual void draw() = 0;
};

struct Node: Part {
    void accept(Serializer &serializer) override;
    void draw() override;
    std::string label;
    unsigned int x;
    unsigned int y;
};

struct Link: Part {
    void accept(Serializer &serializer) override;
    void draw() override;
    std::weak_ptr<Node> from;
    std::weak_ptr<Node> to;
};

struct Serializer {
    void visit(Node &node) {
        std::cout << "serializing node " << node.label << " - x: " << node.x << ", y: " << node.y << std::endl;
    }

    void visit(Link &link) {
        auto pfrom = link.from.lock();
        auto pto = link.to.lock();
       std::cout << "serializing link between " << (pfrom ? pfrom->label : "-none-") << " and " << (pto ? pto->label : "-none-") << std::endl;
    }
};

void Node::accept(Serializer &serializer) {
    serializer.visit(*this);
}

void Node::draw() {
    std::cout << "drawing node " << label << " - x: " << x << ", y: " << y << std::endl;
}

void Link::accept(Serializer &serializer) {
    serializer.visit(*this);
}

void Link::draw() {
    auto pfrom = from.lock();
    auto pto = to.lock();

    std::cout << "drawing link between " << (pfrom ? pfrom->label : "-none-") << " and " << (pto ? pto->label : "-none-") << std::endl;
}

struct TreeDiagram;

struct Command {
    virtual void execute(TreeDiagram &) = 0;
    virtual void undo(TreeDiagram &) = 0;
};

struct TreeDiagram {
    std::vector<std::shared_ptr<Part>> parts;
    std::stack<std::unique_ptr<Command>> commands;

    void execute(std::unique_ptr<Command> command) {
        command->execute(*this);
        commands.push(std::move(command));
    }

    void undo() {
        if(!commands.empty()) {
            commands.top()->undo(*this);
            commands.pop();
        }
    }

    void draw() {
        std::cout << "draw..." << std::endl;
        for(auto &part: parts) {
            part->draw();
        }
    }

    void serialize(Serializer &serializer) {
        std::cout << "serialize..." << std::endl;
        for(auto &part: parts) {
            part->accept(serializer);
        }
    }
};

struct AddNode: Command {
    AddNode(std::string label, unsigned int x, unsigned int y):
        label{label}, x{x}, y{y}, node{std::make_shared<Node>()}
    {
        node->label = label;
        node->x = x;
        node->y = y;
    }

    void execute(TreeDiagram &diagram) override {
        diagram.parts.push_back(node);
    }

    void undo(TreeDiagram &diagram) override {
        auto &parts = diagram.parts;
        parts.erase(std::remove(parts.begin(), parts.end(), node), parts.end());
    }

    std::string label;
    unsigned int x;
    unsigned int y;
    std::shared_ptr<Node> node;
};

struct AddLink: Command {
    AddLink(std::shared_ptr<Node> from, std::shared_ptr<Node> to):
        link{std::make_shared<Link>()}
    {
        link->from = from;
        link->to = to;
    }

    void execute(TreeDiagram &diagram) override {
        diagram.parts.push_back(link);
    }

    void undo(TreeDiagram &diagram) override {
        auto &parts = diagram.parts;
        parts.erase(std::remove(parts.begin(), parts.end(), link), parts.end());
    }

    std::shared_ptr<Link> link;
};

struct MoveNode: Command {
    MoveNode(unsigned int x, unsigned int y, std::shared_ptr<Node> node):
        px{node->x}, py{node->y}, x{x}, y{y}, node{node}
    {}

    void execute(TreeDiagram &) override {
        node->x = x;
        node->y = y;
    }

    void undo(TreeDiagram &) override {
        node->x = px;
        node->y = py;
    }

    unsigned int px;
    unsigned int py;
    unsigned int x;
    unsigned int y;
    std::shared_ptr<Node> node;
};

int main() {
    TreeDiagram diagram;
    Serializer serializer;

    auto addNode1 = std::make_unique<AddNode>("foo", 0, 0);
    auto addNode2 = std::make_unique<AddNode>("bar", 100, 50);
    auto moveNode2 = std::make_unique<MoveNode>(10, 10, addNode2->node);
    auto addLink = std::make_unique<AddLink>(addNode1->node, addNode2->node);

    diagram.serialize(serializer);    
    diagram.execute(std::move(addNode1));
    diagram.execute(std::move(addNode2));
    diagram.execute(std::move(addLink));
    diagram.serialize(serializer);
    diagram.execute(std::move(moveNode2));
    diagram.draw();
    diagram.undo();
    diagram.undo();
    diagram.serialize(serializer);
}

Я не реализовал действие redo, и код далеко не является готовым к производству продуктом, но он действует довольно хорошо, как отправная точка, из которой можно создать нечто более сложное.

Как вы видите, цель состоит в создании древовидной диаграммы, содержащей оба узла ссылки. Компонент содержит кучу данных и знает, как рисовать себя. Более того, как и ожидалось, компонент принимает сериализатор, если вы хотите записать его на файл или что-то еще.
Вся логика содержится в так называемых командах. В примере есть три команды: добавьте node, добавьте ссылку и переместите node. Ни диаграмма, ни компоненты ничего не знают о том, что происходит под капотом. Все, что знает диаграмма, заключается в том, что выполнение набора команд и этих команд может быть выполнено за один шаг назад.

Более сложная система отмены/повтора может содержать круговой буфер команд и несколько индексов, которые указывают тот, который будет заменен следующим, тот, который действителен при выходе, и тот, который действителен при возврате.
Это довольно просто реализовать.

Этот подход поможет вам развязать логику с данными, и это довольно часто встречается при работе с пользовательскими интерфейсами.
Честно говоря, это не то, что вдруг пришло мне в голову. Я нашел что-то подобное, глядя на то, как программное обеспечение с открытым исходным кодом решило проблему, и я использовал ее несколько лет назад в моем программном обеспечении. Полученный код очень прост в обслуживании.

Ответ 4

Другой подход, который вы, возможно, захотите рассмотреть, - работать со структурами и объектами inmutable. Затем стек отмены/повтора можно реализовать как стек версий сцены/диаграммы/документа. Undo() заменяет текущую версию более старой версией из стека и т.д. Поскольку все данные не поддаются обработке, вы можете хранить ссылки вместо копий, поэтому они бывают быстрыми и (относительно) дешевыми.

Плюсы:

• простое отменить/повторить
• многопоточный дружественный
• чистое разделение "структуры" и переходного состояния (например, текущий выбор)
• может упростить сериализацию
• кэширование/память/предварительная компиляция (например, ограничивающие боксы, буферы gpu)

Минусы:

• потребляет немного больше памяти
• принудительно разделяет "структуру" и переходное состояние.
• вероятно, сложнее: например, для типичного древовидного сценария, чтобы изменить node, вам также необходимо будет изменить все узлы вдоль пути к корню; старые и новые версии могут совместно использовать остальные узлы.

Ответ 5

Предполагая, что вы вызываете save() во временном файле для каждого редактирования диаграммы (даже если пользователь явно не вызывает действие сохранить) и что вы отменяете только последнее действие, вы можете сделать следующее:

LastDiagram load(const std::string &path)
{
  /* Check for valid path (e.g. boost::filesystem here) */
  if(!found)
  {
    throw std::runtime_exception{"No diagram found"};
  } 
  //read LastDiagram
  return LastDiagram;
}
LastDiagram undoLastAction()
{
    return loadLastDiagram("/tmp/tmp_diagram_file");
}

и в вашем основном приложении вы обрабатываете исключение, если оно выбрано. Если вы хотите разрешить больше отменить, тогда вы должны подумать о таком решении, как sqlite или tmp файл с большим количеством записей.

Если производительность во времени и пространстве возникает из-за больших диаграмм, подумайте, чтобы реализовать некоторую стратегию, такую ​​как сохранение инкрементной разницы для каждого элемента диаграммы в std::vector (ограничьте ее до 3/5, если объекты большие) и вызовите рендеринга с текущими состояниями. Я не эксперт OpenGL, но я думаю, что так оно и было. На самом деле вы могли бы "украсть" эту стратегию из лучших методов разработки игр или вообще связанных с графикой.

Одна из этих стратегий может быть примерно такой:

Структура для эффективного обновления, инкрементного повторного отображения и отмены в графических редакторах