How to implement the undo functionality in a text-based environment
21 Aug 2021The undo functionality is a standard today in almost all text-based environments such as text or code editors, word processors, notepads, etc. It enables the end-user to revert the action they took and bring back the environment (text or code) to the previous state. What exactly is the previous state depends on the implementation of the functionality and that can be done in several ways.
The undoing process is tightly coupled with the capabilities of the environment. The nature of the environment dictates the nature of the undo action - in plain text undo means reverting/deleting the last inserted text; in a code editor, this can mean comment or uncomment code. The complexity of the environment dictates the granularity of the undo action - one letter or a group, uncomment the line or the whole block (more on this later).
There are multiple undo models that describe how an undo command should behave. Most known are linear - where changes are strictly saved in order and retrieved in the reverse order and non-linear - where changes are saved in order but can be retrieved in arbitrary order. In this post will we implement the liner model, but the ideas can be used when implementing other models.
Looking at the bigger picture, undo implementations can be divided into two major categories: save-whole-state (a.k.a. Memento pattern implementation) and save-deltas (a.k.a. Command pattern implementation). Save-whole-state means that with each environment event, the whole (current) state is saved. If only the performed changes are saved on each event then we are talking about save-deltas.
I will explain both types by implementing an undo engine - a unit of code with the sole purpose of managing the undo functionalities regardless of the caller environment. All examples will be in Java (16) with JUnit (and AssertJ) to test the implementation.
Let's define our actors. First, the undo engine:
public interface UndoEngine<T> {
void registerNewChange(Environment environment, T change);
T performUndo();
T lastEntry();
}We defined three methods:
1. 'registerNewChange' - This method is called when an event happens in the environment. It accepts the whole environment and the performed change.
2. 'performUndo' - This method should return the previous state of the environment. It is called when the undo action is desired - for example the 'Undo' button is pressed.
3. 'lastEntry' - This is a helper method that returns the last change registered by the undo engine.
'Environment' class represents the calling environment - a text editor. For now, we will implement it like this:
public class Environment {
private String text;
public Environment(String text) {
this.text = text;
}
public String appendToExisting(String textToAppend) {
text += textToAppend;
return text;
}
public String getText() {
return text;
}
public void setText(String text) {
this.text = text;
}
}It has a text field representing the current text in the editor and I've added a helper method that appends new text to the end of the existing and returns the new state. This method should simulate typing in the editor. With this, we can implement the undo engine.
Simple undo engine
Let's start with a save-whole-state implementation. This engine will be called on each change in the environment and it will save the state of the environment at the moment of calling, every time regardless of the change type. This means that each entry has the complete picture of the environment and that previous state(s) can be easily reproduced - just swap the current state with the one saved in the engine.
Since the expected behavior of the undo is to revert the last action taken, it means that our supporting data structure should be LIFO - stack comes out as a natural choice.
Of course, we should pay attention to the capacity of the engine - how many past actions we should save.
public class SimpleUndoEngine implements UndoEngine<String> {
private final int capacity;
private final Stack<String> undoStack = new Stack<>();
public SimpleUndoEngine(int capacity) {
this.capacity = capacity;
}
@Override
public void registerNewChange(Environment environment, String change) {
if (undoStack.size() + 1 > capacity)
undoStack.remove(0);
undoStack.push(environment.getText());
}
@Override
public String performUndo() {
if (undoStack.size() > 0)
return undoStack.pop();
else
return null;
}
@Override
public String lastEntry() {
if (undoStack.size() > 0)
return undoStack.peek();
else
return null;
}
}From the implementation, we see that to maintain the given capacity size we must remove some elements occasionally - in this case, while registering a new change if the capacity is reached we remove the oldest entry (the first element in the stack).
An important thing to note with this implementation is that the 'change' argument in the 'registerNewChange' is never used. Instead, on each call, the current text from the environment is retrieved and stored. This is the characteristic of the save-whole-state undo type.
Let's write a test to prove that our implementation is working.
import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;
class SimpleUndoEngineTest {
@Test
void undoEngineWillSaveAndReturnSimpleTextChangesInOrderTheyHappened() {
Environment environment = new Environment("Test"); // initial text
SimpleUndoEngine undoEngine = new SimpleUndoEngine(3);
String firstChange = environment.appendToExisting("1");
undoEngine.registerNewChange(environment, "ignored"); // change argument is ignored, but should in effect be '1'
String secondChange = environment.appendToExisting("2");
undoEngine.registerNewChange(environment, "ignored");
String thirdChange = environment.appendToExisting("3");
undoEngine.registerNewChange(environment, "ignored");
String firstUndo = undoEngine.performUndo();
assertThat(firstUndo).isEqualTo(thirdChange);
String secondUndo = undoEngine.performUndo();
assertThat(secondUndo).isEqualTo(secondChange);
String thirdUndo = undoEngine.performUndo();
assertThat(thirdUndo).isEqualTo(firstChange);
}
}When we run this test it passes, so our implementation is correct. One remaining thing to test is the capacity overflow logic, so we add a test for it:
@Test
void undoEngineWillHonorTheCapacityLimit() {
Environment environment = new Environment("Test");
SimpleUndoEngine undoEngine = new SimpleUndoEngine(2);
environment.appendToExisting("1");
undoEngine.registerNewChange(environment, "ignored");
String secondChange = environment.appendToExisting("2");
undoEngine.registerNewChange(environment, "ignored");
String thirdChange = environment.appendToExisting("3");
undoEngine.registerNewChange(environment, "ignored");
String firstUndo = undoEngine.performUndo();
assertThat(firstUndo).isEqualTo(thirdChange);
String secondUndo = undoEngine.performUndo();
assertThat(secondUndo).isEqualTo(secondChange);
String thirdUndo = undoEngine.performUndo();
assertThat(thirdUndo).isNull();
}As we can see the last, third undo returns 'null' since that element of the stack was removed when the last event was registered and an initial capacity of 2 is preserved.
If we concentrate on the line: 'assertThat(firstUndo).isEqualTo(thirdChange);' we see that the first undo the engine returns is the same as the third change made to the environment. This means that when the saved state from the first undo is applied to the environment, it will not make a change since they are equal. Looking from the end-user perspective initiating the first undo will appear as nothing had happened. This is of course considered a bad user experience. This can be avoided by introducing guards like if the saved state is equal to the current state drop it and take the next one from the undo engine or some similar solution, but we will not do that here for the sake of simplicity.
This simple method applies to almost all text-based environments, but it has a huge memory footprint. As it was established the engine saves the whole text from the environment on each change meaning that the underlying stack will grow very big, very fast. On the other hand, if it is known that the text-base will be small, or near some acceptable size, this method can be used.
Let's try to (slightly) optimize the 'SimpleUndoEngine' implementation. Often the environment events happen in bursts (typing can be a sequence of 'on key up' events) and depending on the environment itself two or more of these events can represent the same change (in the case of rapid typing for example). To avoid storing multiple same events we can introduce this simple check to our implementation:
public class SlightlyOptimizedSimpleUndoEngine implements UndoEngine<String> {
// fields and constructor remain the same
@Override
public void registerNewChange(Environment environment, String change) {
if (!environment.getText().equals(lastEntry())) {
if (undoStack.size() + 1 > capacity)
undoStack.remove(0);
undoStack.push(environment.getText());
}
}
// other methods remain the same
}We only changed the 'registerNewChange' implementation, everything else is untouched. Then we can verify this with a new test:
class SlightlyOptimizedSimpleUndoEngineTest {
@Test
void undoEngineWillNotStoreTwoSameEntries() {
Environment environment = new Environment("Test");
SlightlyOptimizedSimpleUndoEngine undoEngine = new SlightlyOptimizedSimpleUndoEngine(2);
String change = environment.appendToExisting("1");
undoEngine.registerNewChange(environment, "ignored");
String newChange = environment.appendToExisting(""); // empty so that environment is unchanged
undoEngine.registerNewChange(environment, "ignored");
assertThat(change).isEqualTo(newChange);
String firstUndo = undoEngine.performUndo();
assertThat(firstUndo).isEqualTo(change);
assertThat(firstUndo).isEqualTo(newChange);
String secondUndo = undoEngine.performUndo();
assertThat(secondUndo).isNull();
}
}Buffered undo engine
To further evolve our implementation, we can still concentrate on optimization. We mentioned that events can happen in bursts and we introduced some kind of (simple) control of event input. Let's now expand that control by introducing an event buffer.
The idea is to save incoming events to some staged area and only after some condition is satisfied, we push the changes to the undo stack. Pushed changes will be merged into one change and will be one element of the stack. The memory benefit here is obvious - we save memory by avoiding saving every change made.
If we decide that our buffer saves a certain number of events, it wouldn't make much sense - why not save the events directly on the stack? To manage the buffering in this case, we would need to introduce much overhead with no benefit. Instead, we can opt-in for a simple solution - turn our buffer into a simple counter. On each change the counter is incremented and when the threshold is passed we push the entire environment state to the stack.
Let's implement a 'BufferedSimpleUndoEngine'. To represent our environment events let's implement an 'Event' interface that is more representative than a String instance we used in the previous implementation.
public interface Event {}And a concrete class (in this case a record) representing any text change.
public record GenericEvent(String text) implements Event {}The 'text' field represents the text change. But as before its role will be negligible for now.
The undo engine:
public class BufferedSimpleUndoEngine implements UndoEngine<GenericEvent> {
private final int capacity;
private final int bufferSize;
private final Stack<GenericEvent> undoStack = new Stack<>();
private int buffer;
public BufferedSimpleUndoEngine(int capacity, int bufferSize) {
this.capacity = capacity;
this.bufferSize = bufferSize;
}
@Override
public void registerNewChange(Environment environment, GenericEvent change) {
GenericEvent lastEntry = lastEntry();
if (lastEntry == null || !environment.getText().equals(lastEntry.text())) {
if (buffer + 1 == bufferSize) {
pushToStack(new GenericEvent(environment.getText())); // 'collect' all changes
flushBuffer();
} else
buffer++;
}
}
private void pushToStack(GenericEvent event) {
if (undoStack.size() + 1 > capacity) {
undoStack.remove(0);
}
undoStack.push(event);
}
private void flushBuffer() {
buffer = 0;
}
@Override
public GenericEvent performUndo() {
flushBuffer(); // flush the buffer on undo to refresh the counter
if (undoStack.size() > 0)
return undoStack.pop();
else
return null;
}
@Override
public GenericEvent lastEntry() {
if (undoStack.size() > 0)
return undoStack.peek();
else
return null;
}
}From the code, we see that buffer is incremented on each change that is different from the last pushed, and only when the buffer threshold is reached do we push all changes to the stack. 'All changes' here are the latest state of the environment.
Let's write a couple of tests to see if our implementation works.
class BufferedSimpleUndoEngineTest {
@Test
void undoEngineWillFlushBufferWhenFull() {
Environment environment = new Environment("Test");
BufferedSimpleUndoEngine undoEngine = new BufferedSimpleUndoEngine(1, 3);
String firstChange = environment.appendToExisting("1");
undoEngine.registerNewChange(environment, new GenericEvent(firstChange)); // buffer = 1
String secondChange = environment.appendToExisting("2");
undoEngine.registerNewChange(environment, new GenericEvent(secondChange)); // buffer = 2
String thirdChange = environment.appendToExisting("3");
undoEngine.registerNewChange(environment, new GenericEvent(thirdChange)); // buffer = 3
GenericEvent undoEvent = undoEngine.performUndo();
assertThat(undoEvent.text()).isEqualTo(thirdChange);
assertThat(undoEngine.performUndo()).isNull();
}
@Test
void undoEngineWillSaveAndReturnChangesInOrderTheyAppeared() {
Environment environment = new Environment("Test");
BufferedSimpleUndoEngine undoEngine = new BufferedSimpleUndoEngine(2, 2);
String firstChange = environment.appendToExisting("1");
undoEngine.registerNewChange(environment, new GenericEvent(firstChange)); // buffer = 1, capacity = 0
String secondChange = environment.appendToExisting("2");
undoEngine.registerNewChange(environment, new GenericEvent(secondChange)); // buffer = 2, capacity = 0
String thirdChange = environment.appendToExisting("3");
undoEngine.registerNewChange(environment, new GenericEvent(thirdChange)); // buffer = 1, capacity = 1
String fourthChange = environment.appendToExisting("4");
undoEngine.registerNewChange(environment, new GenericEvent(fourthChange)); // buffer = 2, capacity = 1
GenericEvent firstUndo = undoEngine.performUndo();
assertThat(firstUndo.text()).isEqualTo(fourthChange);
assertThat(firstUndo.text()).contains(firstChange);
GenericEvent secondUndo = undoEngine.performUndo();
assertThat(secondUndo.text()).isEqualTo(secondChange);
assertThat(secondUndo.text()).contains(firstChange);
}
}If we run these tests they will pass, so our buffered undo engine version works.
We introduced some overhead by adding a counter that we need to manage (maintain the counter, reset on undo, etc.) however it is not too complicated a structure. Primarily, the 'problem' is that undo actions are inconsistent. Since we group the changes made in the environment in groups of up to the size of the buffer, when we perform the undo action retrieved state could be just one change in the past, or more, depending on the counter number at the moment. From the end-user perspective this will appear as undo reverts only one character in one case, and a whole word in another. However, if the environment allows it, it should not pose a problem. For example, in a simple text editor, the end-user would want sometimes to undo only one character in the case of a typo, or the whole word if they want to rephrase. In a code editor refactoring one or two actions can make a huge difference.
This leaves the question of buffer size, too big will undo too much, too small and it will be the other way around. This is the problem of finding the golden middle and it depends on the type of the environment.
On the buffer management topic, 'BufferedSimpleUndoEngine' resets the counter when the threshold is reached and on performing undo action. Looking at any text editor, we can identify a couple of more scenarios where this counter should be reset. For example, what if the end-user closes the window, removes focus, or presses the 'Save' button. In all these scenarios the continuity of environment changes is broken and it would be good that all unsaved changes are stored on the stack. This means that our implementation must become aware of more events than just a generic one.
Let's first create one more event type:
public class FocusLostEvent implements Event {}This is a simple event that has no additional information.
Now to extend our implementation to handle this event alongside `GenericEvent`.
public class BufferedEventAwareSimpleUndoEngine implements UndoEngine<Event> {
// fields and constructor structure remains the same
@Override
public void registerNewChange(Environment environment, Event change) {
if (change instanceof GenericEvent) {
GenericEvent lastEntry = lastEntry();
if (lastEntry == null || !environment.getText().equals(lastEntry.text())) {
if (buffer + 1 == bufferSize) {
pushToStack(new GenericEvent(environment.getText())); // 'collect' all changes
flushBuffer();
} else
buffer++;
}
} else if (change instanceof FocusLostEvent) {
if (buffer > 0) {
pushToStack(new GenericEvent(environment.getText())); // 'collect' all changes
flushBuffer();
}
} else
throw new IllegalStateException();
}
// other methods remain the same
}Now our implementation is aware of the new 'FocusLostEvent' and handles it by saving the current state of the environment and flushes the buffer. From the end-user perspective, this covers the scenario when editor focus is lost or something similar. Most editors will not do anything when the focus is lost rather on 'window close' or 'save button pressed' events, but we will use focus lost to represent similar scenarios.
As usual, let's test our implementation.
class BufferedEventAwareSimpleUndoEngineTest {
@Test
void undoEngineWillFlushBufferOnFocusLostEvent() {
Environment environment = new Environment("Test");
BufferedEventAwareSimpleUndoEngine undoEngine = new BufferedEventAwareSimpleUndoEngine(2, 2);
String firstChange = environment.appendToExisting("1");
undoEngine.registerNewChange(environment, new GenericEvent(firstChange));
String secondChange = environment.appendToExisting("2");
undoEngine.registerNewChange(environment, new GenericEvent(secondChange));
String thirdChange = environment.appendToExisting("3");
undoEngine.registerNewChange(environment, new GenericEvent(thirdChange));
undoEngine.registerNewChange(environment, new FocusLostEvent());
GenericEvent firstUndo = undoEngine.performUndo();
assertThat(firstUndo.text()).isEqualTo(thirdChange);
GenericEvent secondUndo = undoEngine.performUndo();
assertThat(secondUndo.text()).isEqualTo(secondChange);
}
}This test passes, so our buffer is flushed on 'FocusLostEvent'.
Observing the behavior in the test we see that when we perform the second undo we revert the environment to the state like it was when we performed the first change (text: "Test1"). However, what if the user wants to revert to the initial state (text: "Test"). Looking at the implementation this is not possible and to make it possible the best way is to save the initial state before the changes take place. In other words, we need to save the initial state. We can do that by creating another event, for example, 'WindowOpenEvent':
public record WindowOpenEvent(String initialText) implements Event {}Let's expand our implementation:
public class BufferedEventAwareSimpleUndoEngine implements UndoEngine<Event> {
// fields and constructor structure remains the same
@Override
public void registerNewChange(Environment environment, Event change) {
if (change instanceof GenericEvent) {
Event lastEntry = lastEntry();
if (lastEntry == null || !environment.getText().equals(extractText(lastEntry))) { // a helper method to get the saved text
if (buffer + 1 == bufferSize) {
pushToStack(new GenericEvent(environment.getText())); // 'collect' all changes
flushBuffer();
} else
buffer++;
}
} else if (change instanceof WindowOpenEvent) {
// Store initial changes without checking the buffer since
// the initial state must be saved.
// This is expected to be called only once so there will be
// no interference with other (generic) events.
pushToStack(change);
} else if (change instanceof FocusLostEvent) {
if (buffer > 0) {
pushToStack(new GenericEvent(environment.getText())); // 'collect' all changes
flushBuffer();
}
} else
throw new IllegalStateException();
}
// other methods remain the same
}And let's add one more test to cover the new event:
@Test
void undoEngineWillSaveInitialStateOnWindowOpenAndAllSubsequentChanges() {
BufferedEventAwareSimpleUndoEngine undoEngine = new BufferedEventAwareSimpleUndoEngine(3, 2);
String initialText = "Test";
Environment environment = new Environment(initialText);
undoEngine.registerNewChange(environment, new WindowOpenEvent(initialText));
String firstChange = environment.appendToExisting("1");
undoEngine.registerNewChange(environment, new GenericEvent(firstChange));
String secondChange = environment.appendToExisting("2");
undoEngine.registerNewChange(environment, new GenericEvent(secondChange));
String thirdChange = environment.appendToExisting("3");
undoEngine.registerNewChange(environment, new GenericEvent(thirdChange));
String fourthChange = environment.appendToExisting("4");
undoEngine.registerNewChange(environment, new GenericEvent(fourthChange));
Event firstUndo = undoEngine.performUndo();
assertThat(firstUndo).isInstanceOf(GenericEvent.class);
assertThat(((GenericEvent) firstUndo).text()).isEqualTo(fourthChange);
Event secondUndo = undoEngine.performUndo();
assertThat(secondUndo).isInstanceOf(GenericEvent.class);
assertThat(((GenericEvent) secondUndo).text()).isEqualTo(secondChange);
Event thirdUndo = undoEngine.performUndo();
assertThat(thirdUndo).isInstanceOf(WindowOpenEvent.class);
assertThat(((WindowOpenEvent) thirdUndo).initialText()).isEqualTo(initialText);
}With the initial state saved, we can now revert to the initial state.
By adding a buffer, we made our engine more optimal (performance-wise), but more can be done. If we look at the way our environment states are saved we can easily deduce that most of the entries are 95% the same. When a letter or a word is inserted we save two states that differ only in the performed change. This is called full checkpoint save in the Memento pattern. With that, we can look at more optimal ways of storing this data. For example, we can save the initial state and only save deltas after (current state - initial state = delta). In this case, the undo process will have to recreate the past state by applying all changes to the initial state up to the undo point. This saves memory but provokes a need for state management. There are other examples, but here we will focus on further evolving our implementation in a different direction starting with the question of what if our environment and by the extent our undo engine can recognize more event types.
Event-based undo engine
Since the events are so granular and we've seen the possibility for them to carry their data ('text' field in 'GenericEvent'), we can make our undo engine use them to track changes. The engine will need to simply track the order of events as they appear.
This is the characteristic of save-deltas implementation - instead of saving the whole state every time, it saves individual units of data that represent the change itself. Comparing with the save-whole-state implementation for any two changes in the environment, this implementation saves two events with deltas only (just added the text added or the text removed) instead of the whole state two times. A low memory footprint is inherent in this implementation.
The bulk of the information will now be transferred to the events themselves so this will simplify our undo engine implementation, but first, we need to adjust the event implementation for the new role.
public interface Event {
void apply(Environment environment);
void unapply(Environment environment);
}The events will carry the information in the two defined methods. 'apply' will apply the changes to the passed environment, while 'unapply' will apply the inverse of the change defined with the 'apply' method. As hinted these two methods are inverse - by running 'unapply' after 'apply' the environment will be unaffected (in the same state as before any calls were made). A chain of undo commands will be represented by a chain of 'unapply' calls for all saved events. A chain of 'apply' calls can be used for the redo operation, but that is a different topic for now.
Let's now define some basic events we can work with. First, an event that appends text to the end of the existing:
public record AddTextEvent(String textToAdd) implements Event {
@Override
public void apply(Environment environment) {
environment.appendToExisting(textToAdd);
}
@Override
public void unapply(Environment environment) {
String currentText = environment.getText();
int lastChangeStartIndex = currentText.lastIndexOf(textToAdd);
if (lastChangeStartIndex != -1) {
String newText = currentText.substring(0, lastChangeStartIndex);
environment.setText(newText);
}
}
}And a little bit more complicated one, for removing/deleting text:
public class RemoveTextEvent implements Event {
private final int beginIndex;
private final int length;
private String removedText;
public RemoveTextEvent(int beginIndex, int length) {
this.beginIndex = beginIndex;
this.length = length;
}
@Override
public void apply(Environment environment) {
String currentText = environment.getText();
this.removedText = environment.getText().substring(beginIndex, beginIndex + length);
String beforeChange = currentText.substring(0, beginIndex);
String afterChange = currentText.substring(beginIndex + length);
environment.setText(beforeChange + afterChange);
}
@Override
public void unapply(Environment environment) {
if (removedText != null) {
String currentText = environment.getText();
String before = currentText.substring(0, beginIndex);
String after = currentText.substring(beginIndex);
environment.setText(before + removedText + after);
}
}
public int getBeginIndex() {
return beginIndex;
}
public int getLength() {
return length;
}
public String getRemovedText() {
return removedText;
}
}Finally, we will extend the 'WindowOpenEvent':
public record WindowOpenEvent(String initialText) implements Event {
@Override
public void apply(Environment environment) {
environment.setText(initialText);
}
@Override
public void unapply(Environment environment) {
environment.setText("");
}
}Now we can implement a completely event-based undo engine:
public class EventBasedUndoEngine implements UndoEngine<Event> {
private final int capacity;
private final Stack<Event> undoStack = new Stack<>();
public EventBasedUndoEngine(int capacity) {
this.capacity = capacity;
}
@Override
public void registerNewChange(Environment environment, Event change) {
if (change instanceof AddTextEvent ate) {
pushToStack(ate);
} else if (change instanceof RemoveTextEvent rte) {
pushToStack(rte);
} else if (change instanceof WindowOpenEvent woe) {
// The initial text will be pushed to stack,
// but it can be recreated even without saving it.
// With it we can undo all the way back to the empty screen if needed.
pushToStack(woe);
} else if (change instanceof FocusLostEvent) {
// ignored in this implementation, since all changes are saved always (no buffer)
}
}
private void pushToStack(Event event) {
Event lastEntry = lastEntry();
if (!event.equals(lastEntry)) {
if (undoStack.size() + 1 > capacity)
undoStack.remove(0);
undoStack.push(event);
}
}
// other methods remain the same
}Comparing to the previous implementations, this one is the simplest. As the events have all the information in them, the engine simply needs to keep track of the event order and the rest is done by the events and the environment.
Buffer counter feature is not necessary here because we push all events directly to the stack. Any kind of buffering will be redundant in this implementation since there is no memory benefit we tried to achieve with the buffered implementation - the events are 'small' enough to work with directly. The granularity of the action provided by the counter (one word, or whole sentence depending on the buffer size at the time of the undoing) is now determined by the events. If the environment is smart enough it can produce individual events for all kinds of changes: 'a word is added', 'a sentence is removed', etc.
The convoluted 'if/else' array can of course be simpler since all we do is call the 'pushToStack' method, but it is written like this to show that any special action for any event type can be done with ease (and with 'instanceof' pattern matching it is easier than ever).
As always let's test the engine:
class EventBasedUndoEngineTest {
@Test
void undoEngineWillSaveAndRetrieveEventInOrderTheyAppear() {
String initialText = "Test";
Environment environment = new Environment(initialText);
EventBasedUndoEngine undoEngine = new EventBasedUndoEngine(3);
undoEngine.registerNewChange(environment, new WindowOpenEvent(initialText));
AddTextEvent addTextEvent = environment.addText("1");
undoEngine.registerNewChange(environment, addTextEvent);
RemoveTextEvent removeTextEvent = environment.removeText(0, 3);
undoEngine.registerNewChange(environment, removeTextEvent);
Event firstUndo = undoEngine.performUndo();
assertThat(firstUndo).isInstanceOf(RemoveTextEvent.class);
RemoveTextEvent rte = (RemoveTextEvent) firstUndo;
assertThat(rte.getBeginIndex()).isEqualTo(0);
assertThat(rte.getLength()).isEqualTo(3);
assertThat(rte.getRemovedText()).isEqualTo("Tes");
Event secondUndo = undoEngine.performUndo();
assertThat(secondUndo).isInstanceOf(AddTextEvent.class);
AddTextEvent ate = (AddTextEvent) secondUndo;
assertThat(ate.textToAdd()).isEqualTo("1");
Event thirdUndo = undoEngine.performUndo();
assertThat(thirdUndo).isInstanceOf(WindowOpenEvent.class);
WindowOpenEvent woe = (WindowOpenEvent) thirdUndo;
assertThat(woe.initialText()).isEqualTo(initialText);
}
}When run this test it will pass and our implementation is true.
To fully understand how save-deltas implementation works we need to look from the 'Environment''s viewpoint.
An environment with event-based undo engine
As already mentioned the bulk of the work is now done by the events. Let's illustrate one of the ways to implement this. We will do it in the same way as for the engines: with unit tests. This has nothing to do with the undo engine, it should behave in the same way for any environment implementation, but to have a complete picture of the undo mechanic with an event-based undo engine we need to show what happens on the caller's side.
First, let's make our environment implementation event-oriented by adding the following two methods:
public class Environment {
// this part stays the same
public AddTextEvent addText(String text) {
AddTextEvent event = new AddTextEvent(text);
event.apply(this);
return event;
}
public RemoveTextEvent removeText(int beginIndex, int length) {
RemoveTextEvent event = new RemoveTextEvent(beginIndex, length);
event.apply(this);
return event;
}
// this part also stays the same
}Because we moved all change logic to the event implementations, the environment uses the 'apply' methods to perform changes. The following unit test simulates an orchestrator between the environment and the undo engine. It depicts how an event-based engine is used (indirectly) by our new environment implementation for undoing:
class EnvironmentWithEventBasedUndoEngineTest {
@Test
void environmentWillAddTextAndPerformUndo() {
String initialText = "Test";
Environment environment = new Environment(initialText);
EventBasedUndoEngine undoEngine = new EventBasedUndoEngine(50);
undoEngine.registerNewChange(environment, new WindowOpenEvent(initialText));
AddTextEvent addTextEvent = environment.addText("New");
undoEngine.registerNewChange(environment, addTextEvent);
assertThat(environment.getText()).isEqualTo("TestNew");
Event event = undoEngine.performUndo();
event.unapply(environment);
assertThat(environment.getText()).isEqualTo(initialText);
}
}On creation, the environment has its initial text set to "Test". This produces the first event for the undo engine the 'WindowOpenEvent' which records the initial state. After, the string "New" is added and triggers the 'AddTextEvent' which saves the new state into the undo engine. When the engine performs the undo the last saved event is returned and we see that 'unapply' method is called to revert the environment to the previous state.
As we can see, the environment is passed around as a parameter, and undo engine is used to store and retrieve the events so all work is done by the events.
Let's see an example with multiple different events.
@Test
void environmentWillApplyAndUnApplyChangesAsTheyAppear() {
String initialText = "Test";
Environment environment = new Environment(initialText);
EventBasedUndoEngine undoEngine = new EventBasedUndoEngine(50);
undoEngine.registerNewChange(environment, new WindowOpenEvent(initialText));
AddTextEvent addTextEvent = environment.addText("Test");
undoEngine.registerNewChange(environment, addTextEvent);
assertThat(environment.getText()).isEqualTo("TestTest");
assertThat(addTextEvent.textToAdd()).isEqualTo("Test");
undoEngine.registerNewChange(environment, new FocusLostEvent()); // ignored by the engine
RemoveTextEvent removeTextEvent = environment.removeText(3, 4);
undoEngine.registerNewChange(environment, removeTextEvent);
assertThat(environment.getText()).isEqualTo("Test");
assertThat(removeTextEvent.getRemovedText()).isEqualTo("tTes");
Event firstUndo = undoEngine.performUndo();
firstUndo.unapply(environment);
assertThat(environment.getText()).isEqualTo("TestTest");
Event secondUndo = undoEngine.performUndo();
secondUndo.unapply(environment);
assertThat(environment.getText()).isEqualTo(initialText);
Event thirdUndo = undoEngine.performUndo();
thirdUndo.unapply(environment);
assertThat(environment.getText()).isEmpty();
}By chaining 'unapply' calls we revert the environment to the initial state. The extensibility of the save-deltas implementation is visible. When the environment starts producing new event types, the undo engine can use them immediately regardless of how the 'apply' and 'unapply' methods are implemented.
Conclusion
In this post, we introduced two categories of undo engines: save-whole-state and save-deltas with their respective implementations. We depicted a code evolution path from the simplest implementation to more complicated ones, however, this doesn't mean that one implementation is necessarily better than the other, because each implementation can be successfully used in the right environment.
We covered only the linear undo model and made one example of implementation. This example is by far not optimal and there are many more models and many more ways to implement this functionality, but the overall logic is similar. The decision about what model and how to implement it comes down to the complexity of the environment and the end-user needs.
Full code used in this post can be found in the project repository.
This blog post is inspired by my efforts to implement the undo mechanism in Noteworthy II World of Warcraft add-on.
For any questions and suggestions feel free to e-mail me.