关于c++17:谈-C17-里的-Memento-模式

备忘录模式：介绍相干概念并实现一个较全面的 Undo Manager 类库。

Memento Pattern

动机

备忘录模式也是一种行为设计模式。它在 Ctrl-Z 或者说 Undo/Redo 场合中时最为重要，这里也是它的最佳利用场合。除此之外，有时候咱们也能够称之为存档模式，你能够将其泛化到所有备份、存档、快照的场景里，例如 macOS 的 Time Machine。

Memento 之所以能成为一种 Pattern，就在于它曾经将上述场景进行了形象和覆盖。在这里探讨备忘录模式时肯定须要留神到它作为一种设计模式所提供的最弱小的能力：不是可能 Undo/Redo，而是可能覆盖细节。

当然要以文字编辑器的 Undo/Redo 场景为例来阐明这一点：

Memento 模式会覆盖编辑器编辑命令的实现细节，例如编辑地位、键击事件、批改的文字内容等等，仅仅只是将它们打包为一条编辑记录总体地提供给内部。内部使用者无需理解所谓的实现细节，它只须要收回 Undo 指令，就能从编辑历史中抽出并回退一条编辑记录，从而实现 Undo 动作。

这就是现实中的 Memento 模式应该要达到的成果。

轻量的古典定义

下面提到的字处理器设计是较为饱满的案例。实际上少数古典的如 GoF 的 Memento 模式的定义是比拟轻量级的，它们通常波及到三个对象：

1. originator : 创始人通常是指领有状态快照的对象，状态快照由创始人负责进行创立以便于未来从备忘录中复原。
2. memento : 备忘录贮存状态快照，一般来说这是个 POJO 对象。
3. caretaker : 负责人对象负责追踪多个 memento 对象。

它的关系图是这样的：

FROM: Here

一个略有调整的 C++ 实现是这样的：

namespace dp { namespace undo { namespace basic {

  template<typename State>
  class memento_t {
    public:
    ~memento_t() = default;

    void push(State &&s) {_saved_states.emplace_back(s);
      dbg_print(". save memento state : %s", undo_cxx::to_string(s).c_str());
    }
    std::optional<State> pop() {
      std::optional<State> ret;
      if (_saved_states.empty()) {return ret;}
      ret.emplace(_saved_states.back());
      _saved_states.pop_back();
      dbg_print(". restore memento state : %s", undo_cxx::to_string(*ret).c_str());
      return ret;
    }
    auto size() const { return _saved_states.size(); }
    bool empty() const { return _saved_states.empty(); }
    bool can_pop() const { return !empty(); }

    private:
    std::list<State> _saved_states;
  };

  template<typename State, typename Memento = memento_t<State>>
  class originator_t {
    public:
    originator_t() = default;
    ~originator_t() = default;

    void set(State &&s) {_state = std::move(s);
      dbg_print("originator_t: set state (%s)", undo_cxx::to_string(_state).c_str());
    }
    void save_to_memento() {dbg_print("originator_t: save state (%s) to memento", undo_cxx::to_string(_state).c_str());
      _history.push(std::move(_state));
    }
    void restore_from_memento() {_state = *_history.pop();
      dbg_print("originator_t: restore state (%s) from memento", undo_cxx::to_string(_state).c_str());
    }

    private:
    State _state;
    Memento _history;
  };

  template<typename State>
  class caretaker {
    public:
    caretaker() = default;
    ~caretaker() = default;
    void run() {
      originator_t<State> o;
      o.set("state1");
      o.set("state2");
      o.save_to_memento();
      o.set("state3");
      o.save_to_memento();
      o.set("state4");

      o.restore_from_memento();}
  };

}}} // namespace dp::undo::basic

void test_undo_basic() {
    using namespace dp::undo::basic;
    caretaker<std::string> c;
    c.run();}

int main() {test_undo_basic();
    return 0;
}

这个实现代码中对于负责人局部的职责进行了简化，将相当多的工作交给其他人去实现，目标是在于让使用者的编码可能更简略。使用者只须要像 caretaker 那样去操作 originator_t<State> 就可能实现 memento 模式的使用。

利用场景

简略的场景能够间接复用下面的 memento_t<State> 和 originator_t<State> 模板，它们尽管繁难，但足以应酬个别场景了。

抽象地对待 memento 模式，于一开始咱们就提到了所有备份、存档、快照的场景里都能够利用 Memento 模式，所以总是未免会用简单或者说通用的场景需要。这些简单的需要就不是 memento_t 所能应酬的了。

除了那些备份存档快照场景之外，有时候有的场景或者你并为意识到它们也能够以 memory history 的形式来对待。例如博客日志的工夫线展现，实际上就是一个 memento list。

实际上，为了给你加深印象，在以类库开发为已任的生存中咱们个别会用 undo_manager 这种货色来表白和实现通用型的 Memento 模式。所以牵强附会地，上面咱们将尝试用 Memento 的实践来领导实作一个 undoable 通用型模板类。

Memento 模式通常并不能独立存在，它多半是作为 Command Pattern 的一个子系统（又或是并立而合作的模块）而存在的。

所以典型的编辑器架构设计里，总是将文字操作设计为 Command 模式，例如后退一个 word，键入几个字符，挪动插入点到某个地位，粘贴一段剪贴板内容，等等，都是由一系列的 Commands 来具体实施的。在此基础上，Memento 模式才有工作空间，它将可能利用 EditCommand 来实现编辑状态的存储和重播——通过反向播放与重播一条（组）Edit Commands 的形式。

Undo Manager

UndoRedo 模型本来是一种交互性技术，为用户提供反悔的能力，起初逐步演变为一种计算模型。通常 Undo 模型被辨别为两种类型：

1. 线性的
2. 非线性的

线性 Undo 是以 Stack 的形式实现的，一条新的命令被执行后就会被增加到栈顶。也因而 Undo 零碎可能反序回退曾经执行过的命令，且只能是顺次反序回退的，所以这种形式实现的 Undo 零碎被称作为线性的。

在线性 Undo 零碎中还有严格线性模式一说，通常这种提法是指 undo 历史是有尺寸下限的，正如 CPU 体系中的 Stack 也是有尺寸限度的一个情理。在很多矢量绘图软件中，Undo 历史被要求设定为一个初值，例如 1 到 99 之间，如果回退历史表过大，则最古老的 undo 历史条目会被摈弃。

非线性 Undo

非线性 Undo 零碎和线性模型大体上是类似的，也会在某处持有一个曾经执行的命令的历史列表。但不同之处在于，用户在应用 Undo 零碎进行反悔时，他能够筛选历史列表中的某一命令甚至是某一组命令进行 undo，彷佛他并非执行过这些命令一样。

Adobe Photoshop 在向操作员提供绘图能力的同时，就保护了一个简直靠近于非线性的历史记录操作表，并且用户可能从该列表中筛选一部分予以撤销 / 悔改。但 PS 平时在撤销某一条操作记录历史时，其后的更新的操作记录将被一并回退，从这个角度来看，它还只能算是线性的，只不过运行批处理 undo 罢了。

如果想要失去非线性撤销能力，你须要去 PS 的选项中启用“容许非线性历史记录”，这就不再提了。

事实上在交互界面上向用户提供非线性级别的 Undo/Redo 操作能力的利用，通常并没有谁能很 好地反对。一个起因在于从历史表中抽取一条条目并摘除它，非常容易。但要将这条条目在文档上的效用抽出来摘除，那就可能是齐全办不到。设想一下，如果你对 pos10..20 做了字体加粗，而后对 pos15..30 做了斜体，而后删除了 pos16..20 的文字，而后对 pos 13..17 做了字体加大，当初要摘掉对 pos15..30 做的斜体操作。请问，你可能 Undo 斜体操作这一步吗？显然这是相当有难度的：能够有很多中解释办法来做这笔摘除交易，它们或者都合乎编辑者的预期。那个“好”，是个十分主观的评估级别。

当然啰，这也未必就是不可能实现，从逻辑上来说，单纯点，不就是倒退三步，放弃一条操作，而后重播（回放）后继的两条操作么，可能执行起来略有点费内存之外，也不见得肯定会是如许难。

那么还得要有另外一个起因在于，很多交互性零碎做非线性 Undo 的成果可能是用户难于脑力预判的，就如咱们方才举例的撤销斜体操作一样，用户既然无奈预测独自撤销一条记录的结果，那么这个交互性能提供给他就事实上欠缺了意义——还不如让他逐渐回退呢，这样他将能准确地把握本人的编辑效用的回退效劳。

无论是谁最初有情理，都不重要，它们都不会影响到咱们做出具备这样性能的软件实现。所以实际上有很多类库可能提供非线性 Undo 的能力，只管它们可能并不会被用到某个实在的交互零碎上。

此外，对于非线性 Undo 零碎的论文也有一大把。充沛地证实了论文这种货色，往往都是垃圾——人从出世以来到死去不就是以制作垃圾为己业的么。人类认为如许灿烂辉煌的文化，对于自然界和宇宙来说，恐怕真的是毫无意义的——直到将来某一天，人类或者能突破壁垒穿行到更高级别的宇宙，脱离与生俱来的本宇宙的藩篱的枷锁，那时候可能过往的所有才会体现出可能的意义吧。

好，无论宇宙怎么看，我，依然认为当初我制作的新的 memento pattern 的 Non-linear Undo Subsystem 是有意义的，而且将会在上面给你做出展现来。:)

进一步的分类

作为一个附加的思考，还能够对分类进一步做出组织。在前文的根本划分之上，还能够进一步做辨别：

1. 有抉择的 Undo
2. 可分组的 Undo

大体上，可选的 Undo 是非线性 Undo 的一种加强的操作体现，它容许用户在回退历史操作记录中勾选某些记录予以撤销。而可分租的 Undo 是指命令能够被分组，于是用户可能必须在曾经被分组的操作记录上整体回退，但这会是 Command Pattern 要去负责管理的事件，只是在 Undo 零碎上被体现进去而已。

C++ 实现

Undo Manager 实现中，能够有一些典型的实现计划：

1. 将命令模式的每一条命令脚本化。这种形式会设立若干的检查点，而 Undo 时首先是退到某个检查点，而后将残余的脚本重播一遍，从而实现撤销某条命令脚本的性能
2. 精简的检查点。下面的办法，检查点可能会十分耗费资源，所以有时候须要借助粗劣的命令零碎设计来削减检查点的规模。
3. 反向播放。这种形式通常只能实现线性回退，其要害思维在于反向执行一条命令从而省去建设检查点的必要。例如最初一步是加粗了 8 个字符，那么 Undo 时就为这 8 个字符去掉粗体就行了。

然而，对于一个元编程实现的通用 Undo 子系统来说，下面提到的计划并不归属于 Undo Manager 来治理，它们是划归 Command Pattern 去治理的，并且事实上其具体实现由开发者自行实现。Undo Manager 只是负责 states 的存储、定位和回放等等事务。

次要设计

上面开始真正介绍 undo-cxx 开源库的实现思路。

undoable_cmd_system_t

首先还是说主体 undoable_cmd_system_t，它须要你提供一个次要的模板参数 State。秉承 memento 模式的根本实践，State 指的是你的 Command 所须要保留的状态包，例如对于编辑器软件来讲，Command 是 FontStyleCmd，示意对抉择文字设定字体款式，而相应的状态包可能就蕴含了对字体款式的最小形容信息（粗体、斜体等等）。

undoable_cmd_system_t 的宣告大抵如下：

template<typename State,
typename Context = context_t<State>,
typename BaseCmdT = base_cmd_t,
template<class S, class B> typename RefCmdT = cmd_t,
typename Cmd = RefCmdT<State, BaseCmdT>>
  class undoable_cmd_system_t;

template<typename State,
typename Context,
typename BaseCmdT,
template<class S, class B> typename RefCmdT,
typename Cmd>
  class undoable_cmd_system_t {
    public:
    ~undoable_cmd_system_t() = default;

    using StateT = State;
    using ContextT = Context;
    using CmdT = Cmd;
    using CmdSP = std::shared_ptr<CmdT>;
    using Memento = typename CmdT::Memento;
    using MementoPtr = typename std::unique_ptr<Memento>;
    // using Container = Stack;
    using Container = std::list<MementoPtr>;
    using Iterator = typename Container::iterator;

    using size_type = typename Container::size_type;
    
    // ...
  };

template<typename State,
typename Context = context_t<State>,
typename BaseCmdT = base_cmd_t,
template<class S, class B> typename RefCmdT = cmd_t,
typename Cmd = RefCmdT<State, BaseCmdT>>
  using MgrT = undoable_cmd_system_t<State, Context, BaseCmdT, RefCmdT, Cmd>;

能够看到，你所提供的 State 将被模板参数 Cmd 所应用：typename Cmd = RefCmdT<State, BaseCmdT>。

cmd_t

而 cmd_t 的宣告是这样的：

template<typename State, typename Base>
class cmd_t : public Base {
  public:
  virtual ~cmd_t() {}

  using Self = cmd_t<State, Base>;
  using CmdSP = std::shared_ptr<Self>;
  using CmdSPC = std::shared_ptr<Self const>;
  using CmdId = std::string_view;
  CmdId id() const { return debug::type_name<Self>(); }

  using ContextT = context_t<State>;
  void execute(CmdSP &sender, ContextT &ctx) {do_execute(sender, ctx); }

  using StateT = State;
  using StateUniPtr = std::unique_ptr<StateT>;
  using Memento = state_t<StateT>;
  using MementoPtr = typename std::unique_ptr<Memento>;
  MementoPtr save_state(CmdSP &sender, ContextT &ctx) {return save_state_impl(sender, ctx); }
  void undo(CmdSP &sender, ContextT &ctx, Memento &memento) {undo_impl(sender, ctx, memento); }
  void redo(CmdSP &sender, ContextT &ctx, Memento &memento) {redo_impl(sender, ctx, memento); }
  virtual bool can_be_memento() const { return true;}

  protected:
  virtual void do_execute(CmdSP &sender, ContextT &ctx) = 0;
  virtual MementoPtr save_state_impl(CmdSP &sender, ContextT &ctx) = 0;
  virtual void undo_impl(CmdSP &sender, ContextT &ctx, Memento &memento) = 0;
  virtual void redo_impl(CmdSP &sender, ContextT &ctx, Memento &memento) = 0;
};

也就是说，State 将被咱们包装之后在 undo 零碎外部应用。

而你应该提供的 Command 类则应该从 cmd_t 派生并实现必要的纯虚函数（do_execute, save_state_impl, undo_impl, redo_impl 等等）。

应用：提供你的命令

依照下面的宣告，咱们能够实现一个演示目标的 Command：

namespace word_processor {

  template<typename State>
  class FontStyleCmd : public undo_cxx::cmd_t<State> {
    public:
    ~FontStyleCmd() {}
    FontStyleCmd() {}
    explicit FontStyleCmd(std::string const &default_state_info)
      : _info(default_state_info) {}
    UNDO_CXX_DEFINE_DEFAULT_CMD_TYPES(FontStyleCmd, undo_cxx::cmd_t);

    protected:
    virtual void do_execute(CmdSP &sender, ContextT &) override {UNUSED(sender);
      // ... do sth to add/remove font style to/from
      // current selection in current editor ...
      std::cout << "<<" << _info << ">>" << '\n';
    }
    virtual MementoPtr save_state_impl(CmdSP &sender, ContextT &ctx) override {return std::make_unique<Memento>(sender, _info);
    }
    virtual void undo_impl(CmdSP &sender, ContextT &, Memento &memento) override {
      memento = _info;
      memento.command(sender);
    }
    virtual void redo_impl(CmdSP &sender, ContextT &, Memento &memento) override {
      memento = _info;
      memento.command(sender);
    }

    private:
    std::string _info{"make italic"};
  };
}

在实在的编辑器中，咱们置信你有一个所有编辑器窗口的容器并且能跟踪到以后具备输出焦点的编辑器。

基于此，do_execute 应该是对以后编辑器中的抉择文字做字体款式设置（如粗体），save_state_impl 应该是将抉择文字的元信息以及 Command 的元信息打包到 State 中，undo 应该是反向设置字体款式（如去掉粗体），redo 应该是根据 memento 的 State 信息再次设置字体款式（粗体）。

但在本例中，出于演示目标，这些具体细节都被一个 _info 字符串所代表了。

只管 FontStyleCmd 保留了 State 模板参数，但演示代码中 State 只会等于 std::string。

应用：提供 UndoCmd 和 RedoCmd

为了定制你的 Undo/Redo 行为，你能够实现本人的 UndoCmd/RedoCmd。它们须要不同于 cmd_t 的特地的基类：

namespace word_processor {
  template<typename State>
  class UndoCmd : public undo_cxx::base_undo_cmd_t<State> {
    public:
    ~UndoCmd() {}
    using undo_cxx::base_undo_cmd_t<State>::base_undo_cmd_t;
    explicit UndoCmd(std::string const &default_state_info)
      : _info(default_state_info) {}
    UNDO_CXX_DEFINE_DEFAULT_CMD_TYPES(UndoCmd, undo_cxx::base_undo_cmd_t);

    protected:
    void do_execute(CmdSP &sender, ContextT &ctx) override {
      std::cout << "<<" << _info << ">>" << '\n';
      Base::do_execute(sender, ctx);
    }
  };

  template<typename State>
  class RedoCmd : public undo_cxx::base_redo_cmd_t<State> {
    public:
    ~RedoCmd() {}
    using undo_cxx::base_redo_cmd_t<State>::base_redo_cmd_t;
    explicit RedoCmd(std::string const &default_state_info)
      : _info(default_state_info) {}
    UNDO_CXX_DEFINE_DEFAULT_CMD_TYPES(RedoCmd, undo_cxx::base_redo_cmd_t);

    protected:
    void do_execute(CmdSP &sender, ContextT &ctx) override {
      std::cout << "<<" << _info << ">>" << '\n';
      Base::do_execute(sender, ctx);
    }
  };
}

留神对于它们来说，相应的基类被限度为 base_(undo/redo)_cmd_t，并且你必须在 do_execute 实现中蕴含到基类办法的调用，如同这样：

    void do_execute(CmdSP &sender, ContextT &ctx) override {
      // std::cout << "<<" << _info << ">>" << '\n';
      Base::do_execute(sender, ctx);
    }

基类中有默认的实现，形如这样：

    template<typename State, typename BaseCmdT,
             template<class S, class B> typename RefCmdT>
    inline void base_redo_cmd_t<State, BaseCmdT, RefCmdT>::
            do_execute(CmdSP &sender, ContextT &ctx) {ctx.mgr.redo(sender, Base::_delta);
    }

它实际上具体地调用 ctx.mgr，也就是 undoable_cmd_system_t 的 redo() 去实现具体的内务，相似的，undo 方面也有类似的语句。

undo/redo 的非凡之处在于它们的基类有特地的重载函数：

    virtual bool can_be_memento() const override { return false;}

其目标在于不会思考该命令的 memento 存档问题。

所以同时也留神 save_state_impl/undo_impl/redo_impl 是不必要的。

actions_controller

咱们当初假设字处理器软件具备一个命令管理器，它同时也是命令动作的 controller，它将会负责在具体的编辑器窗口中执行一条编辑命令：

namespace word_processor {

  namespace fct = undo_cxx::util::factory;

  class actions_controller {
    public:
    using State = std::string;
    using M = undo_cxx::undoable_cmd_system_t<State>;

    using UndoCmdT = UndoCmd<State>;
    using RedoCmdT = RedoCmd<State>;
    using FontStyleCmdT = FontStyleCmd<State>;

    using Factory = fct::factory<M::CmdT, UndoCmdT, RedoCmdT, FontStyleCmdT>;

    actions_controller() {}
    ~actions_controller() {}

    template<typename Cmd, typename... Args>
    void invoke(Args &&...args) {auto cmd = Factory::make_shared(undo_cxx::id_name<Cmd>(), args...);
      _undoable_cmd_system.invoke(cmd);
    }

    template<typename... Args>
    void invoke(char const *const cmd_id_name, Args &&...args) {auto cmd = Factory::make_shared(cmd_id_name, args...);
      _undoable_cmd_system.invoke(cmd);
    }

    void invoke(typename M::CmdSP &cmd) {_undoable_cmd_system.invoke(cmd);
    }

    private:
    M _undoable_cmd_system;
  };

} // namespace word_processor

最初是测试函数

借助于改良过的工厂模式，controller 能够调用编辑命令，留神使用者在收回 undo/redo 时，controller 同样地通过调用 UndoCmd/RedoCmd 的形式来实现相应的业务逻辑。

void test_undo_sys() {
  using namespace word_processor;
  actions_controller controller;

  using FontStyleCmd = actions_controller::FontStyleCmdT;
  using UndoCmd = actions_controller::UndoCmdT;
  using RedoCmd = actions_controller::RedoCmdT;

  // do some stuffs

  controller.invoke<FontStyleCmd>("italic state1");
  controller.invoke<FontStyleCmd>("italic-bold state2");
  controller.invoke<FontStyleCmd>("underline state3");
  controller.invoke<FontStyleCmd>("italic state4");

  // and try to undo or redo

  controller.invoke<UndoCmd>("undo 1");
  controller.invoke<UndoCmd>("undo 2");

  controller.invoke<RedoCmd>("redo 1");

  controller.invoke<UndoCmd>("undo 3");
  controller.invoke<UndoCmd>("undo 4");

  controller.invoke("word_processor::RedoCmd", "redo 2 redo");
}

个性

在 undoable_cmd_system_t 的实现中，蕴含了根本的 Undo/Redo 能力：

• 无限度的 Undo/Redo
• 受限制的：通过 undoable_cmd_system_t::max_size(n) 限度历史记录条数

此外，它是全可定制的：

• 定制你本人的 State 状态包
• 定制你的 context_t 扩大版本以包容自定义对象援用
• 如果有必要，你能够定制 base_cmd_t 或 cmd_t 来达到你的特地目标

分组命令

通过基类 class composite_cmd_t 你能够对命令分组，它们在 Undo 历史记录中被视为单条记录，这容许你批量 Undo/Redo。

除了在结构时立刻建设组合式命令之外，能够在 composite_cmd_t 的根底上结构一个 class GroupableCmd，很容易通过这个类提供运行时就地组合数条命令的能力，这样，你能够取得更灵便的命令组。

受限制的非线性

通过批量 Undo/Redo 能够实现受限制的非线性 undo 性能。

undoable_cmd_system_t::erase(n = 1) 可能删除以后地位的历史记录。

你能够认为 undo i – erase j – redo k 是一种受限制的非线性 undo/redo 实现形式，留神这须要你进一步包装后再使用（通过为 UndoCmd/RedoCmd 减少 _erased_count 成员并执行 ctx.mgr.erase(_erased_count) 的形式）。

更全功能的非线性 undo 可能须要一个更简单的 tree 状历史记录而不是以后的 list，尚须留待未来实现。

小结

限于篇幅，不能残缺介绍 undo-cxx 的能力，所以感兴趣的小伙伴间接检阅 Github 源码好了。

后记

这一次的 Undo Manager 实现的尚未尽如人意，当前再找机会改良吧。

参考：

• Memento Pattern – Wiki

过段时间再 review，就这么定了先。