An experimental proposal to implement an undo/redo mechanism on top of existing objects.

undoManager.py

"""undoManager.py -- An experimental proposal to implement an undo/redo
mechanism on top of existing objects.

This is inspired by Raph Levien's ideas, as he wrote them down here:

- https://github.com/trufont/trufont/pull/614#issuecomment-446309637

It also draws inspiration from jsonpatch: http://jsonpatch.com/

The main idea is that if one limits oneself to objects that can be viewed as
JSON-like data structures (ie. are composed of strings, numbers, lists and
dictionaries) it is possible to record changes in a completely generic way,
and use these recordings to reconstruct objects or to roll back changes, for
example to implement undo.

A key requirement was that the model objects must be completely decoupled from
the recording mechanism, and won't need any awareness of it.

The way this is implemented here is through proxy objects: instead of modifying
the original model objects directly, one uses proxy objects that mimic the
model object, allowing the proxy to pass on change information (deltas) to an
undo manager.

The undo manager collects change deltas (and their inverses), and can apply
them to the original model object when undo or redo is requested.

A change delta is an object with three fields:

- op: the operation to be performed. One of "add", "replace" or "remove"
- path: a path identifying a child object in the model object tree
- value: the value to add or replace, or None when removing the child

The path object is a tuple containing path elements. A path element is either a
string (a key or an attribute name) or an integer (a sequence index). An empty
path represents the root object.

Examples:
- ("a",) represents the key "a" if the root object is a dictionary, or the
  attribute "a" if it is a non-container object.
- (3,) represents the item with index 3 for a sequence root element
- (3, "a") represents 123 in this object: [2, 4, 8, {"a": 123}]

The UndoManager class keeps a root object. Client code wishing to modify the
object uses a proxy object that the UndoManager provides:

    model = [1, 2, 3, {"a": 123}]
    um = UndoManager()
    proxy = um.setRootObject(model)
    # Modifications have to done within a change set context:
    with um.changeSet(title="replace list item"):
        proxy[1] = 2000
    assert model[1] == 2000
    um.undo()
    assert model[1] == 2
    um.redo()
    assert model[1] == 2000
    with um.changeSet(title="replace nested dict item"):
        proxy[3]["a"] = 456
    assert model[3]["a"] == 456
    um.undo()
    assert model[3]["a"] == 123

In this example only Python list and dict objects are used as containers, but
any type of Mapping or Sequence (in the collections.abc-sense) can be used, or
any object type that uses attribute access to modify its model data. See the
demo code at the end of this module for a more elaborate example.

The undo/redo system implemented here does not support arbitrary model objects
out of the box, but custom proxy classes can be registered via the
UndoProxy.register() function.
"""

from collections.abc import Callable, Mapping, MutableMapping, Sequence, MutableSequence
from dataclasses import dataclass, field
from functools import singledispatch
from operator import getitem, setitem, delitem, contains
import typing


class UndoManagerError(Exception): pass


class UndoManager:

    def __init__(self):
        self.undoStack = []
        self.redoStack = []
        self._currentChangeSet = None
        self._currentInverseChangeSet = None
        self._rootObject = None

    def setRootObject(self, obj):
        assert self._rootObject is None, "root object can only be set once"
        proxy = UndoProxy(obj, self)
        self._rootObject = obj
        return proxy

    def changeSet(self, **info):
        return ChangeSetContextManager(self, info)

    def _newChangeSet(self):
        if self._currentChangeSet is not None:
            raise UndoManagerError("there already is an active change set")
        self._currentChangeSet = ChangeSet()
        self._currentInverseChangeSet = InverseChangeSet()

    def _pushCurrentChangeSet(self, info):
        assert self._currentChangeSet is not None
        # TODO don't push if the change set is empty
        self.undoStack.append((info, self._currentChangeSet, self._currentInverseChangeSet))
        self.redoStack = []
        self._resetChangeSet()

    def _resetChangeSet(self):
        self._currentChangeSet = None
        self._currentInverseChangeSet = None

    def addChange(self, change, invChange):
        if self._currentChangeSet is None:
            assert self._currentInverseChangeSet is None
            raise UndoManagerError("can't add change, there is no active change set")
        self._currentChangeSet.addChange(change)
        self._currentInverseChangeSet.addChange(invChange)

    def undoInfo(self):
        if self.undoStack:
            return self.undoStack[-1][0]
        else:
            return None  # empty undo stack

    def redoInfo(self):
        if self.redoStack:
            return self.redoStack[-1][0]
        else:
            return None  # empty redo stack

    def undo(self):
        self._performUndo(self.undoStack, self.redoStack)

    def redo(self):
        self._performUndo(self.redoStack, self.undoStack)

    def _performUndo(self, popStack, pushStack):
        if not popStack:
            raise UndoManagerError("empty undo/redo stack")
        if self._currentChangeSet is not None:
            raise UndoManagerError("can't undo/redo in a change set context")
        assert self._currentInverseChangeSet is None
        info, changeSet, invChangeSet = popStack.pop()
        invChangeSet.applyChanges(self._rootObject)
        pushStack.append((info, invChangeSet, changeSet))


@dataclass
class ChangeSetContextManager:

    undoManager:  UndoManager
    info: dict

    def __enter__(self):
        self.undoManager._newChangeSet()

    def __exit__(self, type, value, traceback):
        if type is None:
            self.undoManager._pushCurrentChangeSet(self.info)
        else:
            self.undoManager._resetChangeSet()


# Change Classes

@dataclass
class Change:

    op: str
    path: tuple  # path elements are str or int
    value: typing.Any

    def applyChange(self, obj):
        if self.op == "add":
            addDeepItem(obj, self.path, self.value)
        elif self.op == "replace":
            replaceDeepItem(obj, self.path, self.value)
        elif self.op == "remove":
            removeDeepItem(obj, self.path)
        else:
            assert 0, self.op


@dataclass
class ChangeSet:

    changes: list = field(default_factory=list)

    def addChange(self, change):
        self.changes.append(change)

    def applyChanges(self, obj):
        for change in self.changes:
            change.applyChange(obj)


class InverseChangeSet(ChangeSet):

    def applyChanges(self, obj):
        for change in reversed(self.changes):
            change.applyChange(obj)


# Proxy classes

class UndoBaseProxy:

    def __init__(self, obj, undoManager, path=()):
        self._obj = obj
        self._undoManager = undoManager
        self._path = path

    def __repr__(self):
        return f"{self.__class__.__name__}({self._obj}, path={self._path})"


class UndoBaseContainerProxy(UndoBaseProxy):

    def _genericGetItem(self, key, getItem):
        path = self._path + (key,)
        item = getItem(self._obj, key)
        return UndoProxy(item, self._undoManager, path)
        
    def _genericSetItem(self, key, value, hasItem, getItem, setItem):
        path = self._path + (key,)
        if hasItem(self._obj, key):
            oldValue = getItem(self._obj, key)
            change = Change("replace", path, value)
            invChange = Change("replace", path, oldValue)
        else:
            assert not isinstance(key, int), "bad call for seq __setitem__"
            change = Change("add", path, value)
            invChange = Change("remove", path, None)
        self._undoManager.addChange(change, invChange)
        setItem(self._obj, key, value)

    def _genericDelItem(self, key, getItem, delItem):
        path = self._path + (key,)
        oldValue = getItem(self._obj, key)
        change = Change("remove", path, None)
        invChange = Change("add", path, oldValue)
        self._undoManager.addChange(change, invChange)
        delItem(self._obj, key)


def _containsAlwaysTrue(obj, index):
    # The generic code assumes dict-like "contains" behavior, so for sequences
    # we pretend the indices to be "keys" into the sequence. This means that
    # the standard __contains__ behavior of sequences is not useful, and we'll
    # simply return True. We only assert that the index is not out of range,
    # which shouldn't happen here.
    assert 0 <= index < len(obj)
    return True

class UndoSequenceProxy(UndoBaseContainerProxy, MutableSequence):

    def __len__(self):
        return len(self._obj)

    def _normalizeIndex(self, index, bias=0):
        numItems = len(self._obj)
        if index < 0:
            index += numItems
        if not (0 <= index < numItems + bias):
            raise IndexError("sequence index out of range")
        return index

    def __getitem__(self, index):
        index = self._normalizeIndex(index)
        return self._genericGetItem(index, getitem)

    def __setitem__(self, index, item):
        index = self._normalizeIndex(index)
        self._genericSetItem(index, item, _containsAlwaysTrue, getitem, setitem)

    def __delitem__(self, index):
        index = self._normalizeIndex(index)
        self._genericDelItem(index, getitem, delitem)

    def insert(self, index, item):
        index = self._normalizeIndex(index, bias=1)
        path = self._path + (index,)
        change = Change("add", path, item)
        invChange = Change("remove", path, None)
        self._undoManager.addChange(change, invChange)
        self._obj.insert(index, item)


class UndoMappingProxy(UndoBaseContainerProxy, MutableMapping):

    def __len__(self):
        return len(self._obj)

    def __iter__(self):
        return iter(self._obj)

    def __getitem__(self, key):
        return self._genericGetItem(key, getitem)

    def __setitem__(self, key, value):
        self._genericSetItem(key, value, contains, getitem, setitem)

    def __delitem__(self, key):
        self._genericDelItem(key, getitem, delitem)


class UndoAttributeProxy(UndoBaseContainerProxy):

    def __getattr__(self, attr):
        return self._genericGetItem(attr, getattr)

    def __setattr__(self, attr, value):
        if attr in ("_obj", "_undoManager", "_path"):
            super().__setattr__(attr, value)
            return
        self._genericSetItem(attr, value, hasattr, getattr, setattr)

    def __delattr__(self, attr):
        self._genericDelItem(attr, getattr, delattr)


class UndoCallableProxy(UndoBaseProxy, Callable):

    # This is only for convenience, so one can call methods on the
    # real object via the proxy. It doesn't (can't) do any magic to
    # record changes.

    def __call__(self, *args, **kwargs):
        return self._obj(*args, **kwargs)


@singledispatch
def UndoProxy(obj, undoManager, path=()):
    return UndoAttributeProxy(obj, undoManager, path=path)

def _UndoProxy_atomic(obj, undoManager, path=()):
    return obj

UndoProxy.register(int, _UndoProxy_atomic)
UndoProxy.register(float, _UndoProxy_atomic)
UndoProxy.register(str, _UndoProxy_atomic)
UndoProxy.register(Mapping, UndoMappingProxy)
UndoProxy.register(Sequence, UndoSequenceProxy)
UndoProxy.register(Callable, UndoCallableProxy)


# Helpers for querying and modifying nested objects

def getDeepItem(obj, path):
    for pathElement in path:
        obj = getItem(obj, pathElement)
    return obj

def addDeepItem(obj, path, value):
    obj = getDeepItem(obj, path[:-1])
    addItem(obj, path[-1], value)

def replaceDeepItem(obj, path, value):
    obj = getDeepItem(obj, path[:-1])
    replaceItem(obj, path[-1], value)

def removeDeepItem(obj, path):
    obj = getDeepItem(obj, path[:-1])
    removeItem(obj, path[-1])


# Generic subobject access and modification

#
# hasItem
#
@singledispatch
def hasItem(obj, attr):
    return hasattr(obj, attr)

@hasItem.register(Mapping)
def _hasItem_mapping(obj, key):
    return key in obj

@hasItem.register(Sequence)
def _hasItem_sequence(obj, index):
    assert False, "hasItem is undefined for sequences"

#
# getItem
#
@singledispatch
def getItem(obj, attr):
    return getattr(obj, attr)

@getItem.register(Mapping)
def _getItem_mapping(obj, key):
    return obj[key]

@getItem.register(Sequence)
def _getItem_sequence(obj, index):
    return obj[index]


#
# addItem
#
@singledispatch
def addItem(obj, attr, value):
    assert not hasattr(obj, attr)
    setattr(obj, attr, value)

@addItem.register(Mapping)
def _addItem_mapping(obj, key, value):
    assert key not in obj
    obj[key] = value

@addItem.register(Sequence)
def _addItem_sequence(obj, index, value):
    obj.insert(index, value)


#
# replaceItem
#
@singledispatch
def replaceItem(obj, attr, value):
    assert hasattr(obj, attr)
    setattr(obj, attr, value)

@replaceItem.register(Mapping)
def _replaceItem_mapping(obj, key, value):
    assert key in obj
    obj[key] = value

@replaceItem.register(Sequence)
def _replaceItem_sequence(obj, index, value):
    obj[index] = value


#
# removeItem
#
@singledispatch
def removeItem(obj, attr):
    delattr(obj, attr)

@removeItem.register(Mapping)
def _removeItem_mapping(obj, key):
    del obj[key]

@removeItem.register(Sequence)
def _removeItem_sequence(obj, index):
    del obj[index]


if __name__ == "__main__":
    #
    # Demo time!
    #

    @dataclass
    class Point:
        x: float
        y: float
        type: str = "line"
        smooth: bool = False

    @dataclass
    class Glyph:
        width: float = 0
        contours: list = field(default_factory=list)
        def drawPoints(self, pen):
            for c in self.contours:
                pen.beginPath()
                for pt in c:
                    pen.addPoint((pt.x, pt.y), pt.type, pt.smooth)
                pen.endPath()

    def drawGlyph(g):
        # needs DrawBot
        bez = BezierPath()
        g.drawPoints(bez)
        drawPath(bez)
        translate(g.width, 0)

    modelGlyph = Glyph(width=200)
    um = UndoManager()
    proxyGlyph = um.setRootObject(modelGlyph)
    with um.changeSet(title="add a contour"):
        proxyGlyph.contours.append([])
        proxyGlyph.contours[-1].append(Point(100, 100))
        proxyGlyph.contours[-1].append(Point(100, 200))
        proxyGlyph.contours[-1].append(Point(200, 200))
        proxyGlyph.contours[-1].append(Point(200, 100))

    assert len(modelGlyph.contours) == 1
    assert len(modelGlyph.contours[0]) == 4

    with um.changeSet(title="add another contour"):
        proxyGlyph.contours.append([])
        proxyGlyph.contours[-1].append(Point(100, 300))
    with um.changeSet(title="add point"):
        proxyGlyph.contours[-1].append(Point(100, 400))
    with um.changeSet(title="add point"):
        proxyGlyph.contours[-1].append(Point(200, 400))
    with um.changeSet(title="add point"):
        proxyGlyph.contours[-1].append(Point(200, 300))
    assert len(modelGlyph.contours[1]) == 4

    um.undo()
    assert len(modelGlyph.contours[1]) == 3
    um.redo()
    assert len(modelGlyph.contours[1]) == 4

    with um.changeSet(title="move point"):
        proxyGlyph.contours[1][2].x += 30
        proxyGlyph.contours[1][2].y += 30
    assert modelGlyph.contours[1][2] == Point(230, 430)

    um.undo()
    assert modelGlyph.contours[1][2] == Point(200, 400)

    with um.changeSet(title="insert point"):
        proxyGlyph.contours[1].insert(2, Point(150, 430))
    assert modelGlyph.contours[1][2] == Point(150, 430)
    assert len(modelGlyph.contours[1]) == 5

    um.undo()
    assert len(modelGlyph.contours[1]) == 4