Java Multi-Level Undo Technique (Reflection API)

1. Overview

The best examples of the end-user software leave absolutely no doubt that undo capability is not an option ever more. Currently every application that can alter existing data has to support undo and redo operations, which allow to cancel the changes made by user and to repeat them again as needed. As user knows that he can eliminate carelessly changes at any time, his work becomes more comfortable and the software is considered reliable and predictable.

For some reasons, still many applications support only limited undo/redo capabilities, allowing canceling and repeating only single operation. There is no need to prove that multi-level undo is much better. In this article I'm going to show that implementing multi-level undo in Java is easy, requires minimal amount of changes in your existing code and can be separated to reuse the approach in future. The top of the iceberg is already well-known to the developers who have had an experience with programming for Mac OS X using Cocoa framework which has the NSUndoManager class utilizing a similar technique.

The article is divided into sections describing the approach. In the next section, “Introduction to Java Reflection API”, a very brief description of things is given. If you are already familiar with reflection, you can skip this and move on to the next section, “Implementing basic undo/redo handling”. The last one, “Tuning the undo engine”, is devoted to improving the solution. After it, the conclusions and some tips on how to continue are given.

2. Introduction to Java Reflection API

The reflection library gives you a rich instrumentation to work with your Java code dynamically. For example, if a new class is added to the application during development, it is possible to organize a set of requests to get know the features of that class. Saying more generally, reflection is a way that a program can use to know about itself. Among the possibilities opened with it, are:

  • analyzing the features of the classes during the runtime
  • checking the object state during the runtime by getting the information about its fields and the values contained there
  • using the Method instances that work similar to the pointers to functions in languages like C++, etc.
Consider, for example, a class with rather strange name: Class (java.lang.Class, to be more precise). The instance of the class Class is an object describing the particular properties of a particular class. Here is an example:

public abstract class Shape { . . . }

public class Circle extends Shape { . . . }

public class Square extends Shape { . . . }

. . .

Shape s;

. . .

Class c = s.getClass();

System.out.println(c.getName() + " " + s.toString());

The last operator can print the line “Circle radius=10”, if s is a Circle instance, or “Square side=5”, if s is a Square instance.

Now you can do whatever you want. Imagine that you don’t know the exact class of s, but it is necessary to create another instance of the same class. The following call is the solution:

Shape s1 = s.getClass().newInstance();

Here the default constructor is used to initialize s1. If there is no default constructor for the class, an exception is thrown.

You can extend your knowledge about reflection by checking out the classes Field, Method and Constructor in the java.lang.reflect package. Summing up, the key feature of reflection is the ability to instantiate and work with some entities that are the parts of the application, be it a class, its constructor, a field or its modifier, etc. Actually, the possibility to refer to a class method as to an instance of the Method class is the core of the proposed undo technique. Now we are ready to begin implementing undo mechanism.

3. Implementing basic undo/redo handling

Primarily, undo support is heavily based on using the LIFO queue (stack), as the last performed operation has to be undone first. So, it is obvious that the class being developed, let’s call it UndoManager, will have undoStack as its member. Let’s start from the following code:

public class Pair {
public Object first;
public Object second;

public Pair(Object f, Object s) {
first = f;
second = s;
}
}

public class UndoManager {
private Stack undoStack = null;
private Object target = null;

public UndoManager(Object forWhom) {
undoStack = new Stack();
target = forWhom;
}

public void addInvocation(Method method, Object[] args) {
Pair p = new Pair(method, args);
undoStack.push(p);
}

public boolean canUndo() {
return (undoStack.size() > 0);
}

public void undo() {
if (!canUndo()) {
return;
}
Object obj = undoStack.pop();
if (obj instanceof Pair) {
Pair p = (Pair)obj;
invokeCommand(p);
}
}

protected void invokeCommand(Pair p) {
Method method = (Method)p.first;
Object[] args = (Object[])p.second;
try {
method.invoke(target, args);
return;
} catch (Exception ex) {
System.err.println("Cannot undo " + method.getName());
ex.printStackTrace();
return;
}
}
}

Here class Pair is a helper which simply allows storing two objects together. The undo is actually performed by an UndoManager instance. As it is shown, it is necessary to pass the target object to its constructor. Target object is the instance responsible for making the actions and organizing the undo workflow.

To add a method invocation to UndoManager, it is necessary to call method addInvocation(Method method, Object[] args), where method is target object’s method that will be called during undo; args is an array of arguments that will be passed to method. addInvocation simply stores the given method and its arguments into a Pair instance in the undo stack.

When the method undo() is called, the following happens. The last Pair is popped from the undo stack, and the target object’s appropriate method with its arguments is executed. Of course, an exception is thrown when something goes wrong.

Actually, this is all for undo. However, additional efforts are needed to support redo. As you can see, after the method is undone, it simply disappears and thus cannot be redone:

public void undo() {
. . .
Object obj = undoStack.pop();
. . .
}

To redo this method later, it is needed to store it somewhere. The right place to do so is another stack called redoStack. For example, after the sequence of methods A B C has been executed, the undoStack contains the C B A sequence (C will be executed first during undo). If we put each method being undone to the redoStack, then it will contain the sequence A B C again. Undo stack has reverse order, redo stack has direct order – this is what we need.

The changes to UndoManager class are the following:

. . .
private Stack redoStack = null;
. . .
public UndoManager(Object forWhom) {
. . .
redoStack = new Stack();
. . .
}
. . .
public boolean canRedo() {
return (redoStack.size() > 0);
}
. . .
public void redo() {
if (!canRedo()) {
return;
}
Object obj = redoStack.pop();
if (obj instanceof Pair) {
Pair p = (Pair)obj;
invokeCommand(p);
}
}

Attentive reader will notice that there is no way to fill redoStack. Seems it remains empty all the time. So, it is time to talk about the organization of the target object. Does it have to meet some special requirements? Let’s start with example:

public class MyClass {

private String value;

public MyClass() {
value = "";
}

public String getValue() {
return value;
}

public void setValue(String s) {
value = s;
}
}

Let’s imagine that we need to support undo/redo for the method setValue(String s). Of course, first we need to provide MyClass with its own UndoManager instance. Second, the setValue() method has to be changed to the following:

public void setValue(String s) {
try {
// Get the method as an instance
Method m = this.getClass().getDeclaredMethod(
"setValue",
new Class[]{String.class}
);
// Get the current value
Object[] args = new Object[]{getValue()};
// Add it to the undo manager
undoManager.addInvocation(m, args);
} catch (Exception e) {
// . . .
}

// Modify value
value = s;
}

In the added try-catch block we first get the reference to the method, then save the current value and add this data to the undo manager. Afterwards it is safe to modify the value: when we call undoManager.undo(), the method setValue() will be invoked with the previous value as an argument, so that it will be restored.

That’s nice, isn’t it? Let’s look at the sample sequence of events:

  1. We call setValue("A"). The invocation setValue("") is added to the undo manager.
  2. The new value is set.
  3. We call undo(), during which the undo manager makes the setValue("") invocation that restores the old (empty) value and… adds invocation setValue("A") to the undo manager!

So, there are actually two sources for the undoManager.addInvocation() execution: the method setValue() (or, saying more generally, the undo invocation method, call A) and, the undoManager.undo() method, call B. If call A is the place where a method invocation should be added to the undo stack, then call B is the place to add invocation to the redo stack. This approach can be implemented by providing the boolean variable isUndoing to the UndoManager class. It should be set in the undo() method like:

public void undo() {
isUndoing = true;
. . .
isUndoing = false;
}

As we have found out, there will be an addInvocation() call, caused by the organization of the method being undone, inside the undo() method. Now it becomes clear how the UndoManager’s addInvocation() method should look:

public void addInvocation(Method method, Object[] args) {
Pair p = new Pair(method, args);
if (isUndoing) {
redoStack.push(p);
} else {
undoStack.push(p);
}
}

Now we have both undo and redo. Also we know how to organize the undo invocation methods in the target class. The last section of the article is devoted to improving the approach.

4. Tuning the undo engine

There are still two things to be done. First: sometimes it is needed to clear the redo stack. For example, we have executed operations A, B, C and D. Afterwards we have undone D and C. Now the undo stack contains B and A, and the redo stack contains C and D. If now we execute some different operation E, then the true history of operations will be A, B, E. However, C and D are still stored in the redo stack – in this case it should be cleared. The rule is the following: redo stack should be cleared each time when a method invocation is added to the undo manager, if it is not in undoing or redoing state. Such a check must be done in the addInvocation() method.

The second thing: it is often needed to group undo/redo operations to execute multiple of them in a single undo or redo step. For example, if you type the word “peace” in your favorite text editor, then you probably expect that the whole word will disappear when you press the undo button on its toolbar, not only the last letter of it. To do so, we may add yet another stack to the UndoManager class (let’s call it groupStack) that will collect undo operations to group. Also it is needed to add the boolean variable, isUndoGroupOpened, and to create the following methods:

public void beginUndoGroup() {
if (isUndoGroupOpened == true) {
throw new IllegalStateException("beginUndoGroup() call while undo group is already opened");
}
isUndoGroupOpened = true;
}

public void endUndoGroup() {

if (isUndoGroupOpened == false) {

throw new IllegalStateException("endUndoGroup() call without matching beginUndoGroup()");
}
ArrayList actions = new ArrayList(groupStack);
if (isUndoing) {
redoStack.push(actions);
} else {
undoStack.push(actions);
}
isUndoGroupOpened = false;
groupStack.clear();
}

The undo group, when closed, will be stored in the corresponding stack as an ArrayList. Now, inside the undo()/redo() methods, it is possible to track this situation and perform all operations in the ArrayList at a time.

The complete source code of the resulting UndoManager class is the following:

import java.lang.reflect.Method;
import java.util.*;

public class UndoManager {
private Stack undoStack = null;
private Stack redoStack = null;
private Object target = null;
private boolean isUndoGroupOpened;
private Stack groupStack = null;
private boolean isUndoing;
private boolean isRedoing;

public UndoManager(Object forWhom) {
undoStack = new Stack();
redoStack = new Stack();
groupStack = new Stack();
target = forWhom;
isUndoGroupOpened = false;
isUndoing = false;
isRedoing = false;
}

public void addInvocation(Method method, Object[] args) {
if (!isUndoing && !isRedoing) {
redoStack.clear();
}

Pair p = new Pair(method, args);
if (isUndoGroupOpened) {
groupStack.push(p);
} else {
if (isUndoing) {
redoStack.push(p);
} else {
undoStack.push(p);
}
}
}

public void beginUndoGroup() {
if (isUndoGroupOpened == true) {
throw new IllegalStateException("beginUndoGroup() while " +
"undo group is already opened");
}
isUndoGroupOpened = true;
}

public void endUndoGroup() {
if (isUndoGroupOpened == false) {
throw new IllegalStateException("endUndoGroup() without " +
"matching beginUndoGroup()");
}

ArrayList actions = new ArrayList(groupStack);
if (isUndoing) {
redoStack.push(actions);
} else {
undoStack.push(actions);
}
isUndoGroupOpened = false;
groupStack.clear();
}

public boolean canUndo() {
return (undoStack.size() > 0);
}

public boolean canRedo() {
return (redoStack.size() > 0);
}

public void undo() {
if (!canUndo()) {
return;
}

if (isUndoing || isRedoing) {
throw new IllegalStateException();
}
isUndoing = true;
Object obj = undoStack.pop();
if (obj instanceof Pair) {
// Plain undo
Pair p = (Pair)obj;
invokeCommand(p);
} else if (obj instanceof ArrayList) {
// Undo group
beginUndoGroup();
ArrayList actions = (ArrayList)obj;
for (int i = actions.size() - 1; i >= 0; i--) {
Pair p = (Pair)actions.get(i);
invokeCommand(p);
}
endUndoGroup();
}
isUndoing = false;
}

protected void invokeCommand(Pair p) {
Method method = (Method)p.first;
Object[] args = (Object[])p.second;
try {
method.invoke(target, args);
return;
} catch (Exception ex) {
System.err.println("Cannot undo method " + method.getName());
ex.printStackTrace();
return;
}
}

public void redo() {
if (!canRedo()) {
return;
}
if (isUndoing || isRedoing) {
throw new IllegalStateException();
}
isRedoing = true;
Object obj = redoStack.pop();
if (obj instanceof Pair) {
// Plain redo
Pair p = (Pair)obj;
invokeCommand(p);
} else if (obj instanceof ArrayList) {
// Redo group
beginUndoGroup();
ArrayList actions = (ArrayList)obj;
for (int i = actions.size() - 1; i >= 0; i--) {
Pair p = (Pair)actions.get(i);
invokeCommand(p);
}
endUndoGroup();
}
isRedoing = false;
}
}


4. Conclusions

The described approach helps to implement undo/redo functionality in your Java application fast and easy. This solution is different from the traditional way, where the design pattern Command is often used. Using reflection for undo is better as it doesn’t require the objects to implement some special interfaces. The only requirement for the undo method is to store its invocation with the previous arguments in the undo manager.

The further improvement of the proposed technique may be an effort to make it run safely in a multithreaded environment. Also, it is still possible to simplify the changes needed for undo methods and to improve the error handling. However, such a technique remains simple, can be provided without big changes to the existing code, and thus helps to get the desired results faster.

0 коммент. | добавить комментарий :: Java Multi-Level Undo Technique (Reflection API)

Отправить комментарий