Introduction
Many programs need to solve the problem of keeping track of the history of changes made to a model, and making it possible to navigate backwards and forwards through that history. Perhaps the most obvious example is an interactive program with an undo/redo facility.
Writing code to track history can be done in a variety of ways, each with different sets of constraints, advantages and disadvantages. This article describes one technique which we have been using in our most recent product, and which we have found to have a number of advantages for the particular problem we are solving.
This technique, which we have found ourselves calling "footprint on modify", involves taking a copy of an object whenever we are about to change it, and inserting it into the historical record in place of the modified object.
In this article we will describe the problem we are solving and some alternative approaches to solving it, before describing our own approach and discussing its advantages and disadvantages in comparison with other options.
We hope, when you come to tackle a similar problem, the issues we cover here will provide you with a richer set of concepts for reasoning about the right solution for your problem area.
The Problem - tracking changes in an object model
Like many programs, our program has an object model - a set of classes which together form a model of the artefact being generated by our users as they use it. Instances of these classes are linked by parent-child relationships (some objects "contain" others) and references (some objects refer to others).
The problem we must solve is being able to backtrack to the state of the model at a given point in the past. This means we must be able to construct an object model which is identical to the one that existed at that time. We must allow modifying that object model starting from a point in the past, taking a different branch in history. In addition, we are interested in keeping track of this non-linear history, not simply throwing away the previous branch as many undo/redo systems do, but keeping it available for later reference.
This is illustrated in figure 1, which shows a system moving through states 1-4 as changes are made to the model, before backtracking to state 1, and being changed in different ways, resulting in states 2a and 3a. We want to keep the entire history in this case, including states 2, 3 and 4. Users of board-game software which allows exploring different game trees will be familiar with working this way.
Figure 1. The states of a system over time. Initially, the system moved through states 1-4, before undo-ing to state 2, and making new changes resulting in states 2a and then 3a.
There are many different ways of representing object models and the changes they undergo, and we will begin by looking at some of the alternatives we considered before settling on our approach.
Alternative solutions
Saving complete models
The most brute-force method of preserving model history is to store complete models (either on disk or in memory) every time a change is made. This is often simple to implement, but can be expensive both in terms of time taken to copy or save entire object models, and in terms of storage for the saved models.
This method makes it easy to "prune" the history, only keeping the most important points when storage becomes limited, and it does not require the invention of a new language to represent model changes - simply a way to save or clone objects in the model.
It also makes navigation through long distances in the history simple and relatively cheap - we simply restore the complete model which was stored for that point in time.
Keeping a change log
The classic solution to providing undo/redo behaviour is via a reversible log of actions taken. This amounts to a language that encodes object model modifications, and is often used as an example in textbooks explaining the Command design pattern, since this pattern is well-suited to providing this functionality. Each entry in the log provides a way of changing the model back to the state it was in before a particular change, and a way of moving back again to the after-state. The log entries themselves may be objects with methods capable of modifying the model, or they may be descriptions of how to do it in some language.
This solution has been shown to work in many contexts. Because it involves storing only the differences between states, it is light-weight in terms of the number of objects held in memory, but can be expensive to move large distances in the history, since the system must pass through all intermediate states in order to reach a particular one.
In practice, many applications do not require movements of large distances in the history, but in our situation we do need to consider this case because we store a branched tree of history, providing a visualisation to the user through which they can navigate.
The change log may be seen as somewhat fragile, since if a single point in the log is lost, we are unable accurately to reconstruct states before that time. This is not only a theoretical problem with stability, but also makes "pruning" the history to keep only important points more difficult, since every entry in the log is vital. Pruning to reduce the number of log points requires combining multiple points into one, which may be non-trivial.
Using Copy on Write
Saving complete models provides a flexible but expensive approach, and one way to gain some of its advantages without so much cost in terms of time and storage is to use the copy-on-write strategy.
In this method objects are copied when they are modified, leaving the unmodified object stored, allowing us to revert to the old state by looking at the old object.
This has some of the same advantages as saving complete models. Navigating large distances in the history is cheap since it simply involves restoring the objects that were active at that moment. "Pruning" the history is possible, but more difficult than in the case of saving complete models, because we need to identify which objects are relevant for a given moment in history. We can do this by examining the whole model.
This solution may be simpler than the change log, because it does not require a language of model changes to be used - instead we only need to know how to copy or store objects, and it will be cheaper than saving complete models because only those objects which are changing need to be copied.
Depending on the implementation, there is a significant problem with this approach, which is that the user of the object model may be forced to understand what is happening as they manipulate the objects. If objects are copied when they are modified, the user may need to get hold of a reference to the newly-copied object, and stop using the reference to the historical object. This could be inconvenient and error-prone.
The problem could, of course, be solved by introducing another level of abstraction. It was while we were considering solutions to this problem that we chose to look into the "footprint on modify" approach which is discussed in the rest of this article.
There are, of course, many different alternative solutions, but the three above were the main ones we considered before deciding on our chosen approach.
The Solution - create historical copies as objects change
The approach we chose was inspired by copy on write, but attempts to resolve the problem of allowing the user to manipulate objects without being aware of the building of history, and without adding a further level of abstraction on top of the standard objects.
The key to the solution is taking copies of objects as they are modified, and inserting those copies into the historical record.
Parent-child relationships
The object model includes parent-child ownership relationships, and the model we are considering has a single root node, which is important to the process of tracking history. In an object model with no single root, we may add one object which is the parent of all the nodes with no parents, and consider that the single root.
The parent-child relationships are stored in the parent object, which holds a list of IDs of its children. It is important that the information is stored in this indirect way, because pointers or references to objects in memory may change in the future (which would effectively change history), whereas the properties of the object referred to by a given ID will always be consistent.
The Object Log
The system is built on a structure called the Object Log. This is a collection of all versions of all the objects that have existed, indexed by unique ID. The Object Log is the owner of all objects, including those currently being manipulated by the user.
Every time an object is about to be modified, it is first cloned, and the clone is inserted into the Object Log under its old ID (replacing the object itself). The object’s ID is then changed, and it is re-inserted into the Object Log under its new ID, before being modified. This is illustrated in figure 2.
Figure 2. When an object is going to be modified, it is cloned, and the clone is given its old ID, so that objects that referred to the original now refer to it. The original object is given a new ID, and modified.
Because the object’s ID has changed, its parent, which refers to its children by ID, now refers to the old object. Therefore the parent is also cloned and given a new ID, and its list of children is updated to use the new ID for the first object. This process of cloning continues up the tree to the root, meaning that every change in the object model results in a new root node, as illustrated in figure 3.
Figure 3. When an object is modified, all ancestors are cloned.
The number of clones created for every change is limited to the depth of the parent-child tree, which in our model is a maximum of about 5 levels, and in many models is of this order. This overhead is acceptable for our system. Crucially, the children and siblings of the modified objects do not need to be cloned. The number of children and siblings of a given node in our model, and many similar models, is unbounded.
The Time Point and child-parent relationships
Because each change in the model results in a new root node, it is possible to identify a moment in time simply by storing the ID of the root node at that moment. If we retrieve the object with that ID from the Object Log and examine it to find its children’s ID, retrieve and examine them and continue in this way, we can find all the objects that existed at that moment, and their states.
We provide a Time Point object, which stores the ID of a node which was the root of our model at a given time.
Because a child object may exist in multiple instants in time in different parents (because its parent may have been cloned while being changed, but the child was unchanged), it does not make sense for the information about an object’s parent to be stored in that object. Given a Time Point, we may reconstruct the parentage of all objects by walking the tree from the root. In practice we cache that information inside the Time Point object, as shown in figure 4.
Figure 4. Objects may have different parents at different instants in time. A Time Point records the ID of the root object, uniquely identifying an instant, and caches the parent of each child at this instant.
The Trackable Object
From the point of view of the implementor of a new object in the model, there are two classes which provide the required functionality: the Trackable Object, and the Trackable Collection.
Every class in the object model has the Trackable Object as a base class, and it is this which provides the change-tracking behaviour. Trackable Object keeps a reference to the Object Log which contains this object, and provides a "footprint" method, which must be called before the object is changed. The footprint method calls a method (also called footprint) on the Object Log, which implements the cloning process described above.
An object’s ID is stored in the Trackable Object, and is controlled entirely by the Object Log. In our implementation, objects may be instantiated without an Object Log, which faciliates independent testing, but in this case they have no meaningful ID. Having an ID is tied very closely to having been inserted into an Object Log - indeed it is the job of the Object Log to set and maintain the IDs of the objects, and the objects themselves have "no interest" in their ID. (For a significant amount of our implementation time, IDs were not stored on objects at all - they were added for efficiency, but could in principle be stored only on the Object Log - they are not really considered part of the public interface of an object.)
Because the Object Log will clone the object during the footprint call, the implementor of an object must provide a way of cloning it. How much effort it is to provide this facility varies widely in different programming languages and environments. In environments with automatic cloning facility, care must be taken to handle the circular reference between a Trackable Object and the Object Log.
Ownership - the Trackable Collection
In our object model all objects except the root are owned by some parent object. We represent these relationships by allowing parents to contain one or more Trackable Collection objects. These are lists of children objects (typically with one Trackable Collection for each type of object the parent may contain). The list actually stores the IDs of children, rather than references to the actual objects. This means that an object containing a Trackable Collection of children will continue to refer to the unmodified child even if one of the objects representing a child is modified and gains a new ID.
This indirection via ID is necessary to ensure that a there is only ever one version of history - a single root ID will always give us the same tree of objects (in terms of IDs), but it does mean that when a child is changed we must make new copies of its parents and grandparents up to the root.
The Trackable Collection class provides convenience methods meaning users of the object model do not have to be aware of the references by ID or the footprinting that happens when an object changes. Methods which modify the Trackable Collection, such as "add", "replace" and "remove" take care of calling "footprint" on the object which contains the collection. This is illustrated in figure 5.
Figure 5. The Trackable Collection class holds references to the children of an object. It ensures that the footprint() method is called on the parent when it is changed.
All of the parent-child relationships in our model take the form of resizeable lists of objects of the same type, and so are handled using the Trackable Collection class, but where needed a similar class could be built on the same lines to handle individual children, or fixed-size collections.
Cross-references
Where objects in our object model need to refer to other objects elsewhere in the hierarchy, we use an unique name which is entirely separate from Trackable Object IDs. This means the reference is independent of changes in the object to which we are referring - we do not want to have to footprint all objects that refer to an object we are changing. The reference is treated the same as the other simple properties of an object like a name or description - the only potential difference is the need to clean up dangling references when an object is deleted, or to correct references if the unique name is changed. These are handled separately from the Trackable Object mechanism, and not covered here.
Object model classes
Ordinary classes in the object model, which represent aspects of our problem domain, have relatively little to do to fit in with the footprint-on-modify system. They must provide a clone() method, which copies an object, preserving its properties and keeping references intact (without copying referenced objects or children). They should derive from the Trackable Object base class and hold children objects using Trackable Collections.
Object model classes must enforce that no changes may be made without first calling the footprint() method on the Trackable Object base class. This is implemented in our model by allowing changes only through setter methods, each of which begins with a call to footprint(). This is illustrated in figure 6.
With these provisions in place, the object model classes may be written in a familiar way, using any standard language types or custom classes for properties, so long as all properties are copied by the clone() method.
Figure 6. The classes of the object model are derived from TrackableObject, and call footprint() before any properties are changed.
External users
Users of the object model classes need not know what is going on underneath. Code that manipulates the model may hold references to objects, read and write properties and add or remove children, either using the add() and remove() methods of Trackable Collections, if the collections are exposed by the object model classes, or via specialised methods on the object model classes themselves, which in turn call add() or remove() on the Trackable Collections.
As these manipulations go on, the external code will always hold a reference to the latest version of each object, and underneath, each change will cause footprints to be added to the Object Log.
Code that handles undo and redo uses the Object Log directly, asking it for a unique ID to identify a moment in time, and using such an ID later to tell the log to revert back to that moment.
When the Object Log has reverted to a given moment, all existing references to object model objects must be dropped, and new references must be found by starting at the new root node, which can be provided by the Object Log. Given that the object model may have been completely transformed by the revert event, this requirement is not considered onorous.
Once a revert has been performed, the newly-provided object model may be manipulated as normal, and new footprints begin appearing in the Object Log. The old footprints, including those on a separate "branch" of history, are not overwritten, so we may keep a complex branched undo log, and jump back to any point on it at any time. The biggest challenge here is presenting this information in a useful way to the user!
Discussion
Footprint on modify offers an alternative to change-log-based systems for undo/redo functionality in an object model.
Some advantages of this system include the ability to jump to any moment in history quickly, without the need to traverse intermediate states. This means moving to distant points is fast, there is no need for a language to describe changes in objects, and thus there is no danger that small bugs or inconsistencies in such a language will be propagated through history navigation.
Other advantages include the fact that users of the object model do not have to do anything to ensure history is tracked, unneeded time points in the log may be removed without changing other points, and keeping a history with all branches is just as easy as keeping a traditional linear history.
Disadvantages include the fact that whole objects are copied, rather than just storing changes, which could be a problem if objects are large, and the extra cloning required because the ancestors of objects must be cloned when the objects are changed.
Further potential disadvantages include the need for all objects to be clonable, and to inherit from the Tracking Object base class. Changing an existing object model to use footprint on modify would require significant changes to its implementation.
To build a fully-functional undo/redo mechanism, several areas must be covered which are outside of the scope of this article. The most important area is the structure of the actual undo/redo log, which holds on to root node IDs, and allows navigating between them. In some cases a simple linear stack and marker model will suffice, and in others a tree may need to be presented to the user, along with many other potential features such as named waypoints in history.
Further topics that are of interest, but not covered here, are the mechanisms we could use to prune unneeded time points to reduce storage space, and how to "page" out and in old history to disk or other storage.
Acknowledgements
The footprint on modify idea was developed by Edmund Stephen-Smith and Andy Balaam, based on and inspired by a copy-on-write model designed by Ramon Pisters and Ton Steijvers.