Designing Undo Buffers

One of the inescapable features of nearly every single user-facing piece of software is the ability to undo an action. Why is this feature so common? Is it a projection of our acute desire to have this power in the physical world? We are all painfully aware that actions have consequences, actors have memories, and generally speaking, there is indeed no use crying over spilt milk. However, that hardly prevents us from entertaining an illusion of control over our environment. Feeding this illusion is of course the myriad ways in which we do succeed in performing the opposite of undesired actions: we regularly retrieve sunken ships, rehabilitate broken limbs, and restore damaged cars. We may not be able to do it perfectly, and we certainly can’t do it in every situation. But within a software program, inside the computer’s memory, every action can be perfectly and reliably undone. So no wonder they are everywhere–they ideally match our expectations in the real world. But they are also taken for granted it would seem. Have you ever wondered how they are designed? I woke up this Sunday morning intrigued by the behavior of my Emacs buffers, and look where it got me. By the end of the post I’ll show you how to implement an undo buffer in C++ that has infinite recall, is easily extensible, and implements good software abstractions.

Like all things commonplace, undo buttons come in different flavors. I have myself only come across two broad kinds, which I will describe now. That will set the stage for outlining the design of undo buffers in the context of a simple document editor. This minimal editor we speak of will have only two actions-a Write action that appends characters to the end, and a Delete action that removes characters from the end.

The Two Flavors of Undo Buffers

The first flavor of undo buttons is the simpler one. The software program exposes an inventory of actions to the user, who selects from them an arbitrary action at a time, leading to a sequence of actions A_1, \ldots, A_\ell describing the history of the state of the program. A rather fine point here is that we only care about the state of the program as perceived useful by the user. Therefore the undo actions we are interested in will not twiddle bits outside its scope (of actions) like, say, a counter measuring a user’s time spent in the program. The simplest flavor of undo in this context provides this guarantee: Following the sequence of \ell actions, performing k undo actions consecutively would leave the state of the program as if the history only constituted the first \ell-k actions. Further, if at this point a regular (that is, non-undo) action were to be performed then the new action O' is tacked on to the end so that the history now reads A_1, \ldots, A_{\ell-k}, O' .

In practice, an additional redo facility is paired with the first flavor of undo. This works as follows. If the most recent action performed by the user is an undo, the redo action undoes the undo and in effect performs the action that was previously undone. Therefore, when the most recent action is an undo/redo the user is simply moving backwards and forwards across the sequence A_1, \ldots, A_\ell , but the moment a different action is performed, actions after the current position in the sequence are clipped, and the newly performed action is tacked on to the end.

In all this, the glaring property that stands out is that the “other branches” of history are totally and completely lost. Take the WordPress editor that I’m typing this blog post in, for instance. Suppose I were to write

I have a blue_

first, the cursor being where the underscore is, delete the word “blue” and replace it by “red car”. I can undo/redo as many times as I like but the editor has no memory of “blue” ever appearing in the document at any point in time.

So can we do something to save these lost branches of history? Before reading any further, now might be a good point to contemplate this question for a minute. How might you go about it?

Now come the second flavor of undo buffers. I am not entirely sure the description I present fits any actual implementation but the behavior does. And this description is the simplest I could manage to explain it. We will treat the undo action as somewhat less privileged [1] than in the first flavor where, effectively, performing this action puts it into an “undo mode”. Now, undo actions are also actions albeit simply with a pointer to a previous action (which could itself be another undo action), namely the action that must be undone. The undo buffer in this flavor is deceptively simple–it still is a linear sequence of actions despite all the “branches” of history we want to represent. Of course, this makes sense given the simple observation that the wall time pins each action to a point on the number line. There is an additional undo pointer into the undo buffer. Say that we have the sequence A_1, \ldots, A_\ell with the pointer at position \ell to begin with. Each consecutive undo operation will

  • add to the end of the sequence an undo action pointing to the current position of the undo pointer, and
  • decrement the undo pointer.

Say the undo pointer is at position k < \ell now, which must mean that the length of the sequence is 2\ell-k . Performing a non-undo action will

  • add to the end of the sequence the corresponding action, and
  • reset the undo pointer to the end.

Our sequence keeps track of everything we did, including undos, and therefore it constitutes a perfect record of history. There is no need for a redo button either. Performing a dummy non-undo action to break a chain of consecutive actions will result in the undo pointer being reset to the new dummy action, which of course will be immediately preceded by the corresponding redo actions we want to visit. So undoing one more time than the number of redos we wanted to perform, undoing the dummy action first, does the job. This is the behavior of undo I’m accustomed to in Emacs.

There are two things we want to immediately address. First, computer memory is finite and quite valuable, so we often want to cull the size of our undo buffer when its size exceeds some predetermined limit. If one followed the above scheme literally, it becomes quite problematic to start culling actions from the head of the action sequence since there may be undo actions that follow that point to it. Second, when we undo an undo action, we may have to perform a large number of pointer hops to find the action we want to effectively undo/redo (depending on the parity of the number of hops we took). Undo actions should be instantaneous and not depend linearly on the size of the buffer. Addressing both concerns, we simply rid ourselves of the concept of an undo action altogether and instead put in its place a regular action within the sequence, namely the opposite of the action it would point to. All else remains the same, except, of course, no more pointers to actions. The history recorded this way would only lose the information of which actions arose from an undo and which ones didn’t, but I can’t see why that would matter.

As a side note, I can’t resist mentioning that this is one example of the general rule where spending time to think and critique the initial solutions helps a long way in minimizing the time it takes to reach the eventual solution.

THE DESIGN OF UNDO BUFFERS

Now that we have an idea of the what, let’s look at the how. We come back to our minimal document editor with two actions-Write and Delete-we spoke of earlier. For the rest of the post we’ll be writing C++ classes to express the abstractions we come up with. Finally we’ll end with some cool directions to take this further.

We start with a simple class to describe our document editor.

class Editor {
public:
  // Append `s` to the end of the buffer.
  Editor &Write(const std::string &s);
  // Delete the last `len` characters.
  Editor &Delete(int len);

private:
  std::string buffer_;
};

The only thing worth noting is that we make the methods return non-const references to the Editor object so we can neatly chain a series of actions.

To add undo functionality to this class, we need to store the history sequence of actions. Storing a sequence is a solved problem. We could use std::list, but std::vector is even better because it will simultaneously reduce the number of heap allocations in a growing list and also enable efficient sequential traversal, both of which are desirable in an undo buffer [2]. But how do we represent actions? An action fundamentally modifies the state of the editor. In addition, an action should encapsulate enough information to enable someone in the future to undo it. But apart from that an action could be anything. So it’s natural to frame these requirements in an abstract class.

class Action {
public:
  // Perform the action on the supplied Editor
  // object.
  virtual void Do(Editor &doc) = 0;
  // Return an action representing the opposite
  // action.
  virtual std::unique_ptr<Action> MakeUndoAction() = 0;
  virtual ~Action() {}

protected:
  // Provides pointer access to `doc.​buffer_`.
  static std::string *BufferPointer(Editor &doc);
};

There are several points to note here.

  • Every action gets access to the internals of the editor. This may seem like a leaky abstraction at first, but this coupling is unavoidable. Action and Editor classes are by nature tightly coupled. But we still minimize the dependency by allowing derivations of Action to only access the private members of Editor through static methods like BufferPointer(..). So, for instance, if we were to rename the private member buffer_ we only need to change one method outside of Editor. For this to work, we make Action a friend class of Editor through an appropriate declaration inside Editor.
  • An important point about friendship in C++ is that it not heritable. Therefore, derivations of Action will not be able to access the private members of Editor. To get around this, we make the Editor pass a reference to itself when it calls the Do(..) method. The latter can then get pointer access to the private buffer by calling the protected method BufferPointer of the base Action class (our inheritance will be public).
  • The opposite of an action should also be an action, so we simply make a MakeUndoAction that constructs the opposite action on the heap. Ownership is made clear by returning a unique pointer.
  • Finally, every polymorphic base class should have a virtual destructor so that the correct derived class’ destructor is called before the base class destructor.

Let’s write a concrete action now. To write something to the editor we need a string that represents the something. But do we also need to keep a copy of what we wrote? Let’s maybe first see what our WriteAction class might look like.

class WriteAction : public Action {
public:
  explicit WriteAction(const std::string &s) : s_(s) {}
  void Do(Editor &doc) { *BufferPointer(doc) += s_; }
  std::unique_ptr<Action> MakeUndoAction() {
    return std::make_unique<DeleteAction>(...);
  }
};

To undo any writes we will define a similar DeleteAction class later as well. A delete operation simply has to receive an integer length representing the number of characters to remove from the end of the buffer. So it seems that we can complete the definition of WriteAction::MakeUndoAction() by simply passing the size of string that the WriteAction wrote. Altogether it seems there is no save a copy the string we wrote. Think about that for a second.

Of course we have to keep a copy around! Otherwise how will we define DeleteAction::MakeUndoAction()? In other words, if I write something, undo it, and then sometime in the future, undo the delete, the editor must know what I first wrote, or it can’t reconstruct it. When our abstractions start to solve real problems we know we are on the right path. WriteAction needs a stored copy of the string, so that it can pass it on to DeleteAction when MakeUndoAction is called:.

class WriteAction : public Action {
public:
  ...
  std::unique_ptr<Action> MakeUndoAction() {
    return std::make_unique<DeleteAction>(s_);
  }

private:
  std::string s_;
};

Once we have WriteAction and DeleteAction, we can return to the definition of our Editor class and add the undo buffer as a sequence of unique pointers to Action objects. Dynamic polymorphism is sweet. The careful reader will note that we already encountered it in the previous code snippet by way of std::unique_ptr transforming to std::unique_ptr in the MakeUndoAction() method. In any case, here is our Editor class minus the bits we already saw.

class Editor {
  friend class Action;

public:
  Editor() { ResetUndoPointerToHead(); }
  void ResetUndoPointerToHead() {
    undo_ptr_ = actions_.size() - 1;
  }
  bool CanUndo() { return undo_ptr_ >= 0; }

  ...
  // Undo the action being pointed to by the
  // undo_ptr_ and decrement the undo pointer.
  Editor &Undo();

private:
  ...
  // Record the series of actions with undo
  // information. Semantically this is a list.
  std::vector<Action> actions_;
  // Index of the undo pointer referring to a
  // location in `actions_`.
  int undo_ptr_;
};

The undo pointer keeps track of the action that would be undone if we were to call the Undo() method on the editor. The visible state of the editor is simply the sequence of actions from head up to (and including) the action at the undo pointer index. Let’s look at how the editor would make use of the undo buffer when performing the delete action.

Editor &Editor::Delete(int len) {
  std::unique_ptr<Action> delete_action =
    std::make_unique<DeleteAction>
      (buffer_.substr(buffer_.size() - len));
  delete_action->Do(*this);
  actions_.push_back(std::move(delete_action));
  ResetUndoPointerToHead();
  return *this;
}

So we construct a DeleteAction object, call the Do(..) method, record the action using the undo buffer and update the undo pointer. The Write method would be similar. The only thing that remains is to implement the Undo method. But our abstractions make this trivial:

Editor &Editor::Undo() {
  assert(CanUndo());
  std::unique_ptr<Action> undo_action
    = actions_[undo_ptr_]->MakeUndoAction();
  undo_action->Do(*this);
  actions_.push_back(std::move(undo_action));
  undo_ptr_--;
  return *this;
}

The undo pointer tells us the action we want to undo. We perform the relevant undo action by calling the MakeUndoAction method to get the opposite action. We record the opposite action we perform by tacking it on to the end of the undo buffer.

Now that we meticulously keep track of the state of the editor, let’s add a method

std::vector<std::string> GetHistory() const;

that returns the complete history of the buffer maintained by the editor. Pause for a second to think about how you might write its definition.

The important point to note is that we can perform a sequence of Undo calls and retrieve the state buffer at earlier points in time, but this is a destructive operation. But there is a simple solution.

std::vector<std::string> Editor::GetHistory() const {
  ResetUndoPointerToHead();
  std::vector<std::string> history;
  Editor tmp = *this;
  while (tmp.CanUndo()) {
    history.push_back(tmp.buffer_);
    tmp.Undo();
  }
  // The initial empty state.
  history.push_back(std::string());
  std::reverse(history.begin(), history.end());
  return history;
}

However, we still haven’t defined what it means to copy an Editor object in the highlighted line from the previous snippet. This is nuanced because Editor owns a whole bunch of heap allocated objects via std::unique_ptr. So we clearly need some non-trivial copy constructor here. There are a few options. We could replace the std::unique_ptr with a std::shared_ptr. Or since in this case we are completely sure that the temporary Editor object will not outlive the calling object, we can simply make the copy constructor share the objects even through a mechanism like

aliased_unique_ptr.reset(other_unique_ptr.get());

If we were to follow this logic, it would be best to avoid putting that code in the copy constructor since a copy constructor should be generic and not assume lifetimes of the arguments. But we want to stick with the highlighted line and not replace the copy constructor. The expected and correct behavior is for it to create an independent clone of whatever Editor object it receives. What this implies is that we need to be able to clone derivations of Action as well. So let’s add that to the list of requirements.

class Action {
public:
  ...
  virtual std::unique_ptr<Action> MakeClone() = 0;
  ...
};

Then, in each of our derivations of Action, we define the appropriate Clone methods.

std::unique_ptr<Action> WriteAction::MakeClone() {
  std::unique_ptr<Action> clone;
  clone.reset(new WriteAction(*this));
  return clone;
}

The definition of DeleteAction::MakeClone() is hardly going to be different. But we cannot write a template to avoid this repetition since we cannot know at compile-time which MakeClone() methods we will end up needing at runtime. Dynamic polymorphism is a double-edged sword. Once we have the MakeClone() methods defined, the copy constructor is a breeze.

Editor::Editor(const Editor &o) {
  buffer_ = o.buffer_;
  undo_ptr_ = o.undo_ptr_;
  for (int i = 0; i < o.actions_.size(); i++) {
    actions_.push_back(o.actions_[i]->MakeClone());
  }
}

So there we have it–an editor that remembers everything. If you want to play around with the code from this post, you can find it in this repository. If you want to continue this further, here are some directions:

  • Ensure that the size of the buffer never exceeds a certain number of predetermined (compile-time constant) number of bytes.
  • The actions stored in the undo buffer will accumulate over time a ton of duplicate data. Repeatedly undo/redo-ing the same long string will cost a lot of bytes (or actions, if you have implemented the task from the previous bullet point). Create an arena maintained by the Editor that gives out const references to actions on the undo buffer, and garbage collects unreferenced data.

Footnotes

  • [1] Yet they are still somewhat so in relation to their effect on the undo pointer.
  • [2] std::deque if you eventually want to trim the sequence from the head.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.