adrientetar/history.md Secret

## history.md

      
    Raw
  

              history.md
            
          
    Tracking (and undoing) changes

In a complex application like TruFont, many different changes can be done or undone. So we want an undo model that's made out of simple primitives and scales easily without requiring a ton of custom code – that starts with a mean of recording changes.
Atoms

Now the exact undo APIs can be formulated in a few varying ways, but some properties hold regardless:

Any action can be represented as a list of 3 elementary changes (or deltas): set(object, key, value), insert(items, index, item), and delete(items, index)
Now, for the sake of undo, we want these actions to be invertible. We can classify these 3 actions into two buckets: set is an object action (object as in JSON's {}), we can invert it by trading the value it stores with that previously held by the object. insert and delete are array actions and the inverse of eachother. When insert is applied, its value is set to null, which makes it into a delete. And vice-versa: delete stores the item it deletes which makes it become an insert. We now have: ∀ action f, ∀ target α, f²(α) = α
The implication here is that all classes in the model are either arrays or objects (or bear the interface thereof – the setter interface can be made private or internal to the data module). In C# adding an object interface to a class can be achieved with reflection, but where RTTI isn't available said interface can be handcoded rather.
Finally, we can add a compound delta to the model. It bears the same interface as the elementary deltas but stores and applies a list of deltas.

We now have something like this:
interface IChange
{
    void Apply();
}

internal interface IArray<T>
{
    void Insert(int index, T item);
    // Returns the removed value
    T Remove(int index);
}

internal interface IObject<T>
{
    // Returns the old value
    T Set<T>(string key, T value);
}

struct ArrayChange<T> : IChange
{
    private IArray<T> _items;
    private int _index;
    private T _item;

    bool Insert => _item != null;

    public ArrayChange(IArray<T> items, int index, T item)
    {
        _items = items;
        _index = index;
        _item = item;
    }

    public void Apply()
    {
        if (Insert)
        {
            _items.Insert(_index, _item);
            _item = null;
        }
        else
        {
            _item = _items.Remove(_index);
        }
    }
}

struct ObjectChange<T> : IChange
{
    private IObject<T> _obj;
    private string _key;
    private T _value;

    public ObjectChange(IObject<T> obj, string key, T value)
    {
        _obj = obj;
        _key = key;
        _value = value;
    }

    public void Apply()
    {
        _value = _obj.Set(_key, _value);
    }
}

public class Changes : IChange
{
    private List<IChange> _changes;

    public void Delete<T>(IArray<T> items, int index)
    {
        _changes.Add(new ListChange(items, index, null));
    }

    public void Insert<T>(IArray<T> items, int index, T value)
    {
        _changes.Add(new ListChange(items, index, value));
    }

    public void Set<T>(IObject<T> obj, string key, T value)
    {
        _changes.Add(new ObjectChange(obj, key, value));
    }

    public void Apply()
    {
        foreach (var change in _changes)
        {
            change.Apply();
        }
    }
}
Now, we can give all our objects read-only properties, an internal setter interface, and a public ApplyChange() method that calls into the setter interface.
Serialization

Now suppose we want to throw serialization into the mix. Reasons are adding quicksave functionality through a log of delta, or send changes over the wire when collaborative editing comes about (which would require a merging logic for conflicting changes, see CRDT litterature).
Scoping

Given that our model is of a complex tree of objects, the question of hierarchy comes up i.e. who stores the changes.
Looking at the model, the first idea that comes up is to store changes in each Glyph (which doubles as an undo stack), and the remaining, top-level changes in the Font. This lets us undo Glyph-level changes indeed, though it's worth noting some disparities that stem from the class hierarchy in the model:

Guidelines: given that global guidelines are stored in the Master, once you convert a guideline to global there's no undoing it in the considered model. This is problematic as the "removing local guideline" change is a Glyph change, while the "adding global guideline" is not. But both these changes are really part of the same changelist.
Kerning: whereas stored in the Master, it is set in the context of a glyph (actually two, or more), and can therefore be viewed as a "Glyph-level change" of sorts. It wouldn't be undoable either in the proposed model.

These examples hint at a view-centered model – not for change history globally, but for undo specifically. (We really care about two properties here: the notion of temporality [the order of changes], and also of view owner i.e. did I set this in my Glyph view? When I leave the Glyph view, for instance now looking at a font-level kerning window, I prolly don't want these changes to come up. [Or do I?]).
We can attain such a model by storing all history at the Font level (switching from Glyph is easy, as it suffices to add the Glyph name to the change path – idem for Layer) and have views store the change history they were a part of – said change history would be a subset of the Font's changelist, and may be cleared [or not?] when user switches to a different view.
We can possibly even remove the storage of changes in the Font, that's only useful for collaborative editing (rebasing changes).
Unresolved questions


should be prune no-op changes?
read A Temporal Model for Multi-Level Undo and Redo
stack should probably be bounded. linked-list?

Terminology


Action: any change that the user performs on the document
Delta: an elementary change, any action can be represented as a list of deltas
History: the list of all changes that are stored in the Font

Thanks

Raph Levien