Memo mode: Introduces related concepts and implements a comprehensive Undo Manager class library.
Memento Pattern
motivation
The memo pattern is also a behavior design pattern. It is most important in ctrl-Z or Undo/Redo scenarios, where it is best used. In addition to this, sometimes called archive mode, you can generalize it to all backup, archive, snapshot scenarios, such as macOS Time Machine.
What makes Memento a Pattern is that it abstracts and disguises these scenarios. When discussing the memo pattern here, it’s important to note that it offers the most powerful capability as a design pattern: not the ability to Undo/Redo, but the ability to obscure details.
Of course, take the Undo/Redo scenario of the text editor as an example:
The Memento mode masks the implementation details of the editor’s edit commands, such as the edit location, keystroke events, modified text content, and so on, and simply packages them as an edit record that is collectively available to the outside world. The external user does not need to know the so-called implementation details. It only needs to issue the Undo command to pull out and roll back an edit record from the edit history to complete the Undo action.
This is what the ideal Memento pattern should do.
The classical definition of lightweight
The word processor design mentioned above is a fuller example. In fact, most classical definitions of Memento schemas such as GoF are fairly lightweight and usually involve three objects:
- Originator: The originator is usually an object that has a snapshot of its status. The originator is responsible for creating a snapshot to recover from a memo in the future.
- Memento: Memento stores snapshots of state, which is generally a POJO object.
- Caretaker: Caretaker keeps track of multiple memento objects.
The diagram looks like this:
FROM: Here
A slightly tweaked C++ implementation looks like this:
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;
}
Copy the codeThis implementation simplifies the responsibility for the responsible part of the code, delegating a considerable amount of work to others to make coding easier for the user. The user only needs to operate originator_t
like the caretaker to complete the memento mode.
Application scenarios
Simple scenarios can reuse the memento_T
and Originator_t
templates above, which are simple but adequate for general scenarios.
Looking at the Memento pattern in the abstract, we mentioned at the beginning that the Memento pattern can be used in any backup, archive, or snapshot scenario, so there are always complex or common scenario requirements. These complex requirements are beyond memento_t’s capacity.
In addition to those backup archive snapshot scenarios, sometimes there are scenarios that you may not realize can also be viewed in terms of memory history. A timeline of blog posts, for example, is essentially a memento list.
In fact, just to impress you, we use something like undo_manager to express and implement the general-purpose Memento pattern in our library development lives. So it makes sense that we’ll try to implement an undoable generic template class using Memento’s theory.
The Memento Pattern usually does not exist on its own, but rather as a subsystem (or concurrent and collaborative module) of the Command Pattern.
Therefore, in the typical editor architecture design, text operations are always designed as Command mode, such as advancing a Word, typing a few characters, moving an insertion point to a location, pasting a clipboard content, etc., which are performed by a series of Commands. On this basis, the Memento mode will have a workspace, and it will be able to use EditCommand to store and replay Edit state — by playing back and replaying a (group) Edit Commands.
Undo Manager
The UndoRedo model was originally an interactive technique that gave users the ability to back out, but has evolved into a computational model. Generally, Undo models are divided into two types:
- linear
- The nonlinear
Linear Undo is implemented as a Stack, where a new command is added to the top of the Stack when executed. Therefore, the Undo system can roll back the executed commands in reverse order, and only in reverse order. Therefore, the Undo system implemented in this way is called linear.
In linear Undo systems, there is also a strictly linear mode, which usually refers to the fact that Undo history has a size limit, just as Stack in CPU systems has a size limit. In many vector drawing software, Undo history is required to be set to an initial value, such as between 1 and 99. If the rollback history table is too large, the oldest Undo history entries are discarded.
Nonlinear Undo
Non-linear Undo systems are similar to linear models in that they hold a history list of commands that have been executed somewhere. However, the difference is that when using Undo system, the user can select a command in the history list or even a group of commands to Undo, as if he did not execute these commands.
Adobe Photoshop, while providing the operator with the ability to draw, maintains an almost non-linear list of historical actions, from which the user can select portions to undo/repent. However, when PS undoes an operation record, subsequent updated operation records will be rolled back. From this point of view, it can only be considered linear, but it only runs batch undo.
To get the nonlinear undo capability, you need to enable “Allow nonlinear History” in the Photoshop option.
In fact, applications that provide users with non-linear Undo/Redo capabilities on the interface are not well supported. One reason is that it is very easy to extract an entry from a history table and remove it. But it may be completely impossible to extract the utility of this item from the document. Imagine if you had a problem with pos10.. 20 made the font bold, and then on pos15.. 30 is italicized and pos16 is deleted.. 20 text, then on pos 13.. 17 made font enlargement, now want to remove on pos15.. 30 does the italic operation. Can you Undo italics for this step? This is obviously quite difficult: there are a number of explanatory ways to do this removal transaction, all of which may be in line with the editors’ expectations. That “good” is a very subjective level.
Of course, this is not necessarily impossible, from a logical point of view, is not simple, three steps back, give up one operation, and then replay (replay) the next two operations, it may be a bit more expensive to perform, and not necessarily how difficult.
You will have to have another reason is that a lot of interactive system for the effect of nonlinear Undo users difficult may be mental anticipation, as we have just cancel italics operation, for example, since the user cannot predict separate Undo the consequences of a record, then the interaction capabilities offered him was in fact lacks meaning – it is better to let him back step by step? In this way he will be able to accurately determine the fallback effect of his editing utility.
It doesn’t matter who ends up having a point, and they don’t affect our ability to make software implementations that do this. So there are actually a number of libraries that provide nonlinear Undo capabilities, although they may not be used on a real interactive system.
In addition, there are a lot of papers on nonlinear Undo systems. Fully proved that papers this kind of thing, often are rubbish – people from birth to death is not to make rubbish as their business. Think how brilliant culture, for nature and the universe, I’m afraid there is no point in really – until one day in the future, humans may be able to break through barriers to a higher level of the universe, from the shackles of natural barriers of this universe and all that time could past will reflect the possible meaning.
Well, no matter what the universe thinks, I still think the new non-linear Undo Subsystem of memento pattern I made now makes sense and will show it to you below. 🙂
Further classification
As an added thought, the classification can be further organized. On the basis of the above basic division, further differentiation can be made:
- Optional Undo
- Grouping Undo
In general, optional Undo is an enhanced operational embodiment of nonlinear Undo, which allows the user to select certain records in the rollback history operation record to Undo. However, the subrentable Undo means that commands can be grouped, so users may have to roll back the whole operation record that has been grouped, but this is what the Command Pattern is responsible for managing, which is only reflected in the Undo system.
C + + implementation
In the Undo Manager implementation, there are some typical implementations:
- Scripts each command in command mode. In this mode, several checkpoints are set up. In Undo mode, a certain checkpoint is replayed and the rest scripts are replayed to complete the function of canceling a command script
- Streamlined checkpoints. In the above approach, checkpoints can be very resource-intensive, so sometimes elaborate command system design is needed to reduce the size of checkpoints.
- Play in reverse. This approach usually only achieves linear fallback, and the idea is to execute a command backwards to eliminate the need to set up checkpoints. For example, the last step is bold 8 characters, so when Undo, remove the bold for these 8 characters.
However, for a general Undo subsystem implemented by metaprogramming, the schemes mentioned above are not managed by Undo Manager, but by Command Pattern. In fact, the specific implementation is completed by the developers themselves. The Undo Manager is only responsible for states storage, location, playback, and so on.
The main design
The following is a real introduction to the implementation of the undo- CXX open source library.
undoable_cmd_system_t
First, the body undoable_cmd_system_t requires you to provide the main template argument State. Following the basic memento pattern, State refers to the State package that your Command needs to save. For example, for editor software, Command is FontStyleCmd, which means setting font styles for selected text. The corresponding state package may contain minimal description of the font style (bold, italic, and so on).
The undoable_cmd_system_t declaration looks something like this:
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>;
Copy the codeAs you can see, the State you provide will be used by the template argument Cmd: typename Cmd = RefCmdT
.
cmd_t
The declaration of cmD_T looks like this:
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;
};
Copy the codeThat is, State will be wrapped and used within the Undo system.
The Command class you should provide should derive from cmd_t and implement the necessary pure virtual functions (do_execute, save_state_impl, undo_impl, redo_impl, etc.).
Use: Provide your command
Following the above declaration, we can implement a Command for demo purposes:
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"};
};
}
Copy the codeIn a real editor, we believe that you have a container of all editor Windows and can keep track of the editor that currently has input focus.
Based on this, do_execute should set the font style (such as bold) for the selected text in the current editor, save_state_impl should pack the meta information for the selected text and the meta information for the Command into State, Undo should reverse the font style (remove bold), and redo should restyle the font based on memento State information (bold).
But in this case, for demonstration purposes, these details are represented by a _info string.
Although FontStyleCmd retains the State template argument, State in the demo code will only equal STD :: String.
Use: Provides UndoCmd and RedoCmd
To customize your Undo/Redo behavior, you can implement your own UndoCmd/RedoCmd. They require a special base class different from 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); }}; }Copy the codeNote that for them, the corresponding base class is limited to base (undo/redo) cmd_t, and you must include calls to base class methods in your do_execute implementation, as follows:
void do_execute(CmdSP &sender, ContextT &ctx) override {
// std::cout << "<<" << _info << ">>" << '\n';
Base::do_execute(sender, ctx);
}
Copy the codeThere is a default implementation in the base class that looks something like this:
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);
}
Copy the codeIt actually specifically calls ctx.mgr, undoable_cmd_system_t redo() to do specific housekeeping, and similarly, undo has a similar statement.
What makes undo/redo special is that their base classes have special overloaded functions:
virtual bool can_be_memento() const override { return false; }
Copy the codeThe purpose is not to consider the memento archive of the command.
So also note that save_state_impl/undo_impl/redo_impl is not necessary.
actions_controller
We now assume that the word processor software has a command manager, which is also a command action controller, which will be responsible for executing an edit command in a specific editor window:
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_processorCopy the codeFinally, the test function
With the improved factory mode, the controller can call edit commands. Note that when the user issues undo/redo, the controller also calls UndoCmd/RedoCmd to complete the corresponding business logic.
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");
}
Copy the codefeatures
The undoable_cmd_system_t implementation contains the basic Undo/Redo capability:
- Unrestricted Undo/Redo
- Restricted: pass
undoable_cmd_system_t::max_size(n)Limit the number of historical records
Plus, it’s all customizable:
- Customize your own State package
- Customize your context_T extension to accommodate custom object references
- If necessary, you can customize base_cmd_t or cmd_t for your specific purpose
Grouping command
With the base class Class Composite_cmd_t you can group commands that are treated as a single record in the Undo history, which allows you to batch Undo/Redo.
In addition to creating composite commands immediately at construct time, you can construct a class GroupableCmd based on the Composite_cmd_t. This class easily provides the ability to compose several commands in place at run time so that you can have a more flexible command set.
Constrained nonlinearity
Batch Undo/Redo allows limited nonlinear Undo functionality.
Undoable_cmd_system_t ::erase(n = 1) Deletes the history of the current position.
You can think of undo i-erase j-redo k as a limited nonlinear undo/redo implementation, Note that you need to wrap this up further (by adding a _erased_count member to UndoCmd/RedoCmd and executing ctx.Mgr. erase(_erased_count)).
A more full-featured nonlinear undo might require a more complex tree-like history than the current list and will have to be implemented in the future.
summary
Due to limited space, there is not a complete introduction to the capabilities of undo-cxx, so if you are interested in Github source code, please review it directly.
Afterword.
This time the implementation of Undo Manager is not perfect, look for opportunities to improve later.
Reference:
- Memento Pattern – Wiki
We will review it later. That’s settled.
🔚