Coding an Undo/Redo Stack

The other night I put (what I think are) the finishing touches of an Undo/Redo stack for Photobomb. This is the second time I've written an Undo/Redo stack, the first time being for the TextEditor Quidget. Neither time was I able to find much guidance for how to approach the problem. I handled it slightly differently each time. I thought I'd write up a blog post about how I approached Undo/Redo for Photobomb, in case it helps someone else out.

Generally, the way I conceived the problem was to keep a list of actions that needed to be undone. When an action is undone, then that action needs to be added to a list of actions that can be redone. But what does it mean to store an action in code? I thought of 2 approaches:

1. Keep a list of actions as functions along arguments to pass to those functions.
2. Keep a list of "backups" for every change made to an object, and on redo swap out the backup for the actual object.

List of Actions Approach
I took the first approach back when I wrote TextEditor. It was easy to do because the only actions supported by Undo and Redo was that something could be added to the TextBuffer, or something could have been removed. So I very literally stored a list of functions and elements. So on a change, such as when text has been inserted, I store point at which the text was inserted, along with the inserted text:

     cmd = {"action":"delete","offset":iter.get_offset(),"text":text}
  self._add_undo(cmd)

The _add_undo function merely ensures that the list does not grow beyond a defined maximum, and adds it to the undo list:

   def _add_undo(self, cmd):
  if self.undo_max is not None and len(self.undos) >= self.undo_max:
    del(self.undos[0])
  self.undos.append(cmd)

The heart of the __add_undo command was to extract the command to undo, and pass it along to _do_action(), and then add the return value of undo to redo stack.

     undo = self.undos[-1]
  redo = self._do_action(undo)
  self.redos.append(redo)
  del(self.undos[-1])

do_action, in turn read the type of action, did the specified action, and returned the opposite action so it could be used for redo.

     if action["action"] == "delete":
    self.get_buffer().delete(start_iter, end_iter)
    action["action"] = "insert"
  elif action["action"] == "insert":
    self.get_buffer().insert(start_iter, action["text"])
    action["action"] = "delete"
  return action

So by keeping a mapping of actions and their opposites, and by using a dictionary to store the information needed to undo or redo the action, this system worked well for simple case of simple text editor.

List of Backup Approach
Not surprisingly, when I approach this problem in Photobomb, I followed the same basic solution path. For example, I set up a list to store undo actions in. I then started storing a code for actions like I used for delete and insert in the text editor. However, I quickly ran into some problems. Photobomb is more complex then TextEditor, and GooCanvas is more complex than TextView/TextBuffer. For example, storing all the info needed for undoing and redoing a clipping path on an object required some more complex code than seemed right for the problem. So, I switched to the second approach.

Here, I store a list of undos, but what I store in the list is objects. A "new" object, as in the object after the change, and the "old" object. Kind of like the backup.

To store an undo in this system, I make a back up of the object, change it, and then add the undo:

       saved_item = self.back_up_item()
    self.selected_item.move(delta_x,delta_y)
    self.add_undo(self.selected_item, saved_item)

Making the backup entailed duplicating the entailed not just making a copy, but removing the copy from the goocanvas, and storing the z-order. GooCanvas doesn't track z-order for you, so I had to track it myself. Every object on the GooCanvas suface derives from a subclass of the custom PhotobombItem and one of the built in GooCanvas types, such as goocanvas.Image). PhotobombItems have a duplicate function witch return a copy, and a remove function. So getting a copy was easy.

   def back_up_item(self, item=None):
  if item is None:
    item = self.selected_item
  copy = item.duplicate(True, False)
  copy.remove()
  index = self.z_order.index(item)
  self.z_order.insert(index+1,copy) 
  return copy

I quickly found that it is insufficient to simply store a pair of old and new objects for each undo. This is because an object can be modified twice in a row. And if you store the object itself, rather than a copy of the object, the undo stack will reference the object in whatever is it's current state, so undo can appear to weirdly go backward.

For example if I make an item, call it O1 bigger, I'll store a copy of O1, call the copy O1.1, and O1 as the old and new items, respectively. Then if I make it bigger again, I store another copy of O1, call it O1.2, and O1 *again*. So undoing will go O1 is replaced by O1.2, which looks right, but then undo again and O1 will be replaced by O1.1. But oops, O1 was already replaced, so O1.1 appears, but O1.2 was never replaced.

To guard against this, I looked backward through the undo stack to see where in the current undo stack the object appears last, and I take the current backup of the "old_item" and make that the "new_item" for the previous undo. So, for then making something bigger would store O1.1 and O1 again, but then making it bigger again, it would replace O1 with O1.2 as the "new_item" and then store O1.2 and O1 as the new_item at the top of the undo stack. So undo would replace O1 with O1.2, and then O1.2 with O1.1, and everything seems to work.

That was a pretty long winded explanation for not that much code. Basically, I loop back through the undo stack and update the last occurrence of the object being added with the copy before going ahead and adding the objects to the stack.

   def add_undo(self, new_item, old_item):
  #ensure proper undos for multiple edits of the same object
  if len(self.undos) > 0:
    for item in self.undos[::-1]:
      if item["new_item"] is new_item:
        item["new_item"] = old_item
        break
  self.undos.append({"new_item":new_item,
              "old_item":old_item})
  self.redos = []

Note that I also reset the redo stack whenever the undo stack is modified.

So what does undo and redo do? They function in a very similar manner to the undo/redo functions in the text editor. First, they get they item from the top of the stack and stick it on the other stack. So for undo:

     undo = self.undos[-1]
  self.redos.append(undo)
  del(self.undos[-1])

Then they remove the new item, and restore the backup (assuming they both exist). If there is no backup, that means the item was just created, so removing the item is sufficient. Conversely, if there is no new item, then it means the item was deleted, so adding it back to the canvas is sufficient. Finally, the function has to position the new item in the z-order and then select the new item.

     if undo["new_item"] is not None:
    undo["new_item"].remove()
  if undo["old_item"] is not None:
    undo["old_item"].set_property("parent",self.__root)
    next_item = self._find_item_above(undo["old_item"])
    if next_item is not None:
      #position in z-order
      undo["old_item"].lower(next_item)
  self.selected_item = undo["old_item"]
  self.__reset_selection()

Redo does essentially the same thing, only removes old_items and restores new_items. There was about 100% code duplication between the undo and redo functions. However, I decided to keep the duplicate code in place because I was worried that if I have to go back and fix bugs in a year or so, I'd need the code to be crystal clear about what it did. I can always refactor into a common function later, but for now, I felt that the duplicated code was just easier to read and understand.

Now, calling these functions is easy in cases where a menu item was used to change on object, as there was one and only one change to store in the undo stack. But sometimes it's not so easy. For example, Photobomb has what I call "Press and Hold Buttons". To make an item bigger, for example, you can use the Bigger menu item, or you can hold down the Bigger button until the selected object is the size that you want and release the button. The button emits a signal called "tick" every 100 milliseconds, which is bound to an action, in the case, the "self.bigger" function. This causes the item to get bigger many many times (about 10 times per second, in fact) but the user is going to think of it as one action to be undone.

In order to handle this case, I created two signal handlers, one for the press event and one for the released signal of a button. All the Press and Hold buttons use these handlers. The press signal handler creates an immediate copy of the item, and then connects the tick and the released signals. Occasionally, the released handler gets called twice, which causes some confusion, so I track the tick signal to make sure that the released signal is only handled once.

   def pah_button_pressed(self, button, action):
  old_item = self.back_up_item()
  tick_signal_id = button.connect("tick",action)
  button.connect("released",self.pah_button_released, (tick_signal_id, old_item))

Then in the released signal, I add the new item and the old_item to the undo stack, assuming it hasn't been already.

   def pah_button_released(self, button, args):
  tick_signal_id, old_item = args
  #work around released signals being called multiple times
  if tick_signal_id in self.__disconnected_tick_signals:
    return
  self.__disconnected_tick_signals.append(tick_signal_id)
  button.disconnect(tick_signal_id)
  if self.selected_item is not None:
    self.add_undo(self.selected_item, old_item)

Now only 1 undo is added when a Press and Hold Button is used.

Another challenge to overcome in this system was handling the user changing selection by clicking on an item versus when the user clicked and dragged an item. The latter should be added to the undo stack, but not the former.

Fortunately, this can be handled with a similar pattern. The mouse_down signal handler creates a copy of the item, and passes it to the mouse_up signal handler.

           old_item = self.back_up_item(clicked_item)
        self.__mouse_up_handler = self.__goo_canvas.connect("button_release_event",self.drag_stop, old_item)

Then the drag_stop function checks if the item was actually moved before adding to the undo stack. If the item hasn't been moved, then the selection has simply changed.

Finishing Touch
One last finishing touch is to ensure that the undo and redo menu items are only sensitive if there is anything in the undo and/or redo stacks. Photobomb handles this by connecting to the activate signal of the edit menu, and then checking if there is anything in the undo and redo lists, and setting the sensitivity accordingly.

   def edit_menu_reveal(self, widget, data=None):
  active_undos = len(self.undos) > 0
  active_redos = len(self.redos) > 0
  self.builder.get_object("menuitem_undo").set_sensitive(active_undos)
  self.builder.get_object("menuitem_redo").set_sensitive(active_redos)

There is a lot of ineractivity in photobomb, and this creates a bit of complexity in handling undo/redo. You can see all the code in context in the photobomb trunk.