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.

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_"])

def test_delete_when_impossible():
    try:
        make_fixture(["DELETE"], (1, 1), [""])
    except AssertionError:
        pass

Going Backward

In order to undo things we have to:

1. keep track of actions and reverse them, or

2. 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

1. Implement a command to repeat the most recent operation.

2. 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.