Undo and Redo
- Replace user interface components with mock objects to simplify testing.
- Record actions and state to check behavior these mock objects.
- Use objects to represent actions to record history and enable undo.
- Recording state is easier but more expensive than recording changes.
Terms defined: abstract base class, Command pattern, headless application
Viewing text files is useful, but we’d like to be able to edit them as well. This chapter therefore modifies the file viewer of Chapter 23 so that we can add and delete text. And since people make mistakes, we will also implement undo, which will introduce another commonly-used design pattern.
Getting Started
Our file viewer has four classes:
-
A
Window
can draw lines and report its size. -
A
Buffer
stores lines of text, keeps track of a viewport, and transforms buffer coordinates to screen coordinates. -
A
Cursor
knows its position in the buffer and can move up, down, left, and right. -
The
App
makes a window, a buffer, and a cursor, then maps keys to actions.
To make unit testing simpler,
we start by adding one more class:
a replacement for the screen object provided by the curses
module.
This class stores the current state of the display in a rectangular grid
so that our tests can check it easily.
It also takes a list of keystrokes as input
to simulate interaction with the user:
class HeadlessScreen:
def __init__(self, size, keystrokes):
self._size = size
self._keys = keystrokes
self._i_key = 0
self.erase()
def getkey(self):
if self._i_key == len(self._keys):
key = "CONTROL_X"
else:
key = self._keys[self._i_key]
self._i_key += 1
return key
def addstr(self, row, col, text):
assert 0 <= row < self._size[ROW]
assert col == 0
assert len(text) <= self._size[COL]
self._display[row] = text + self._display[row][len(text):]
GUI applications that don’t display anything
are often called headless applications.
Giving our simulated keystrokes to the screen seems odd—it would make more sense
for App
to have a method that gets keystrokes—but
it’s the simplest way to fit everything in beside
the classes we already have.
Clean Exit
Notice that when the screen runs out of simulated keystrokes
it produces CONTROL_X
,
meaning “exit the application”.
We need this to break out of the keystroke-processing loop in the application,
and no,
we didn’t think of this up front.
To finish this change,
we also need to define a HeadlessWindow
that takes a desired screen size and passes it to the screen:
class HeadlessWindow(Window):
def __init__(self, screen, size):
assert size is not None and len(size) == 2
super().__init__(screen, size)
Finally, our new application class records keystrokes, the cursor position, and the screen contents for testing:
class HeadlessApp(App):
def __init__(self, size, lines):
super().__init__(size, lines)
self._log = []
def get_log(self):
return self._log
def _add_log(self, key):
self._log.append((key, self._cursor.pos(), self._screen.display()))
def _make_window(self):
self._window = HeadlessWindow(self._screen, self._size)
We can now write tests like this:
def test_scroll_down():
size = (2, 2)
lines = ["abc", "def", "ghi"]
keys = ["KEY_DOWN"] * 3
screen = HeadlessScreen(size, keys)
app = HeadlessApp(size, lines)
app(screen)
assert app.get_log()[-1] == ("CONTROL_X", (2, 0), ["de", "gh"])
Insertion and Deletion
We are now ready to implement insertion and deletion. The first step is to add methods to the buffer class that update a line of text:
class InsertDeleteBuffer(Buffer):
def insert(self, pos, char):
assert 0 <= pos[ROW] < self.nrow()
assert 0 <= pos[COL] <= self.ncol(pos[ROW])
line = self._lines[pos[ROW]]
line = line[:pos[COL]] + char + line[pos[COL]:]
self._lines[pos[ROW]] = line
def delete(self, pos):
assert 0 <= pos[ROW] < self.nrow()
assert 0 <= pos[COL] < self.ncol(pos[ROW])
line = self._lines[pos[ROW]]
line = line[:pos[COL]] + line[pos[COL] + 1:]
self._lines[pos[ROW]] = line
Notice that we delete the character under the cursor, not the one to the left of the cursor: this is delete-in-place rather than backspace-delete. Notice also that we have done a little defensive programming by checking that the coordinates given for the operation make sense.
The window, cursor, and screen don’t need to change to support insertion and deletion, but the application class needs several updates. The first is to define the set of characters that can be inserted, which for our example will be letters and digits, and to create a buffer of the appropriate kind:
class InsertDeleteApp(HeadlessApp):
INSERTABLE = set(string.ascii_letters + string.digits)
def _make_buffer(self):
self._buffer = InsertDeleteBuffer(self._lines)
We also need to create handlers for insertion and deletion:
def _do_DELETE(self):
self._buffer.delete(self._cursor.pos())
def _do_INSERT(self, key):
self._buffer.insert(self._cursor.pos(), key)
Finally,
since we don’t want to have to add one handler
for each insertable character,
let’s write a _get_key
method that returns a pair of values.
The first indicates the “family” of the key,
while the second is the actual key.
If the family is None
,
the key is a special key with its own handler;
otherwise,
we look up the handler for the key’s family:
def _get_key(self):
key = self._screen.getkey()
if key in self.INSERTABLE:
return "INSERT", key
else:
return None, key
def _interact(self):
family, key = self._get_key()
if family is None:
name = f"_do_{key}"
if hasattr(self, name):
getattr(self, name)()
else:
name = f"_do_{family}"
if hasattr(self, name):
getattr(self, name)(key)
self._add_log(key)
We’re going to write a lot of tests for this application, so let’s write a helper function to create a fixture, run the application, and return it:
def make_fixture(keys, size, lines):
screen = HeadlessScreen(size, keys)
app = InsertDeleteApp(size, lines)
app(screen)
return app
Our tests are now straightforward to set up and check:
def test_delete_middle():
app = make_fixture(["KEY_RIGHT", "DELETE"], (1, 3), ["abc"])
assert app.get_log()[-1] == ("CONTROL_X", (0, 1), ["ac_"])
Edge Case
One of our tests uncovers the fact that our application crashes if we try to delete a character when the buffer is empty:
def test_delete_when_impossible():
try:
make_fixture(["DELETE"], (1, 1), [""])
except AssertionError:
pass
Our focus is implementing undo, so we will leave fixing this for an exercise.
Going Backward
In order to undo things we have to:
-
keep track of actions and reverse them, or
-
keep track of state and restore it.
Recording actions can be trickier to implement but requires less space than saving the entire state of the application after each change, so that’s what most systems do. The starting point is to append a record of every action to a log:
class HistoryApp(InsertDeleteApp):
def __init__(self, size, keystrokes):
super().__init__(size, keystrokes)
self._history = []
def get_history(self):
return self._history
def _do_DELETE(self):
row, col = self._cursor.pos()
char = self._buffer.char((row, col))
self._history.append(("delete", (row, col), char))
self._buffer.delete(self._cursor.pos())
But what about undoing cursor movement? If we add a character, move to another location, and then undo, shouldn’t the cursor go back to where it was before deleting the character? And how are we going to interpret these log records? Will we need a second dispatch method with its own handlers?
The common solution to these problems is to use the Command design pattern. This pattern turns verbs into nouns, i.e., each action is represented as an object with methods to go forward and backward. Our actions all derive from an abstract base class so that they can be used interchangeably. That base class is:
class Action:
def __init__(self, app):
self._app = app
def do(self):
raise NotImplementedError(f"{self.__class__.__name__}: do")
def undo(self):
raise NotImplementedError(f"{self.__class__.__name__}: undo")
The child classes for insertion and deletion are:
class Insert(Action):
def __init__(self, app, pos, char):
super().__init__(app)
self._pos = pos
self._char = char
def do(self):
self._app._buffer.insert(self._pos, self._char)
def undo(self):
self._app._buffer.delete(self._pos)
class Delete(Action):
def __init__(self, app, pos):
super().__init__(app)
self._pos = pos
self._char = self._app._buffer.char(pos)
def do(self):
self._app._buffer.delete(self._pos)
def undo(self):
self._app._buffer.insert(self._pos, self._char)
We could implement one class for each direction of cursor movement, but instead choose to create a single class:
class Move(Action):
def __init__(self, app, direction):
super().__init__(app)
self._direction = direction
self._old = self._app._cursor.pos()
self._new = None
def do(self):
self._app._cursor.act(self._direction)
self._new = self._app._cursor.pos()
def undo(self):
self._app._cursor.move_to(self._old)
This class records the new cursor position as well as the old one
to make debugging easier.
It depends on adding two new methods to Cursor
to move in a particular direction by name
(e.g., “right” or “left”)
and to move to a particular location:
def act(self, direction):
assert hasattr(self, direction)
getattr(self, direction)()
def move_to(self, pos):
self._pos = pos
self._fix()
Our application’s _interact
method changes too.
Instead of relying on keystroke handler methods to do things,
it expects them to create action objects
(Figure 24.1).
These objects are appended to the application’s history,
and then asked to do whatever they do:
def _interact(self):
family, key = self._get_key()
name = f"_do_{family}" if family else f"_do_{key}"
if not hasattr(self, name):
return
action = getattr(self, name)(key)
self._history.append(action)
action.do()
self._add_log(key)
Note that we have modified all the handler methods to take the keystroke as an input argument so that we don’t have to distinguish between cases where it’s needed and cases where it isn’t. This simplifies the code a little at the expense of introducing unused parameters into the handlers for special keys like cursor movement.
Finally, each handler method now builds an object and returns it:
def _do_DELETE(self, key):
return Delete(self, self._cursor.pos())
def _do_INSERT(self, key):
return Insert(self, self._cursor.pos(), key)
def _do_KEY_UP(self, key):
return Move(self, "up")
With all these changes in place,
our application almost works.
We add an _do_UNDO
handler that pops the most recent action from the history
and calls its undo
method.
When we test this,
though,
we wind up in an infinite loop because
we are appending the action to the history before doing the action,
so we are essentially undoing our undo forever.
The solution is to modify the base class Action
to have a .save
method
that tells the application whether or not to save this action.
The default implementation returns True
,
but we override it in Undo
to return False
:
class Undo(Action):
def do(self):
action = self._app._history.pop()
action.undo()
def save(self):
return False
def __str__(self):
return f"Undo({self._app._history[-1]})"
Note that popping the most recent action off the history stack
only works once we modify the application’s _interact
method
so that it only saves actions that ought to be saved:
class UndoableApp(ActionApp):
def _interact(self):
family, key = self._get_key()
name = f"_do_{family}" if family else f"_do_{key}"
if not hasattr(self, name):
return
action = getattr(self, name)(key)
action.do()
if action.save():
self._history.append(action)
self._add_log(key)
We can now write tests like this to check that we can insert a character, undo the action, and get back the screen we originally had:
def test_insert_undo():
app = make_fixture(["z", "UNDO"])
assert get_screen(app) == ["ab", "cd"]
Summary
Figure 24.2 summarizes the concepts introduced in this chapter. Real text editors (even simple ones) obviously have many more features, but we have now seen most of the key ideas.
Exercises
Combining Movement
Modify the application so that successive movement operations are combined into a single undo step.
Forgetting Moves
Most editors do not save cursor movements in their undo history. Modify the code in this chapter so that undo only works on changes to the content being edited.
Limiting History
Modify the application so that only the most recent hundred operations can be undone.
Breaking Lines
Modify the code so that pressing the Enter key inserts a new line or breaks the current line in two. What information do you have to store to make this operation undoable?
Redoing Operations
Implement a “redo” command that re-executes an operation that has been undone. How does redo differ from undoing an undo? Does it make sense to redo an action that wasn’t done?
Repeating Operations
-
Implement a command to repeat the most recent operation.
-
How should repeated operations be represented in the application’s history?
Saving Operations
Use the ideas of Chapter 16 to save operations to a file and reload them so that users can resume editing sessions.