NOTICE! This is a static HTML version of a legacy ImageJ Trac ticket.

The ImageJ project now uses GitHub Issues for issue tracking.

Please file all new issues there.

Ticket #13 (closed feature: moved)

Opened 2010-02-16T16:43:21-06:00

Last modified 2013-04-15T09:55:25-05:00

Improve undo/redo functionality

Reported by: curtis Owned by: curtis
Priority: major Milestone: imagej2-b10-compatibility
Component: Scripting Version:
Severity: non-issue Keywords:
Cc: Blocked By: #1463
Blocking: #1543

Description

A difficult problem common to many applications is that of the undo history. Ideally, we would like ImageJ to support multiple undo and redo as efficiently as possible. There are two major kinds of undoable operations:

  1. Some operations such as adding a ROI are simple to invert efficiently (just delete it). We can use a command recorder system to keep track of such workflows both backwards and forwards to allow undo and redo.
  2. Other operations such as dithering are more destructive, and ImageJ must somehow cache the prior state of the image in order to successfully undo the change.

As such, support for a hybrid undo history supporting both types of operations may be the way to go.

Change History

comment:1 Changed 2010-02-16T16:44:32-06:00 by curtis

This ticket is related to both scripting infrastructure and event notification.

comment:2 Changed 2010-03-01T17:07:24-06:00 by gharris

  • Status changed from new to accepted

comment:3 Changed 2011-03-13T21:21:09-05:00 by curtis

  • Milestone changed from imagej-2.0-alpha1 to imagej-2.0-beta1

comment:4 Changed 2011-06-06T11:18:35-05:00 by gharris

  • Milestone changed from imagej-2.0-beta1 to imagej-2.0-beta2

comment:5 Changed 2012-01-26T12:44:45-06:00 by curtis

  • Owner changed from gharris to curtis

comment:6 Changed 2012-02-23T11:10:24-06:00 by curtis

  • Type changed from task to story

comment:7 Changed 2012-02-23T11:18:53-06:00 by curtis

  • Blocking 6 added

comment:8 Changed 2012-03-05T14:33:36-06:00 by curtis

  • Blocking 6 removed

comment:9 Changed 2012-07-03T12:38:49-05:00 by curtis

  • Milestone changed from imagej-2.0.0-beta3 to imagej-2.0.0-beta4

comment:10 Changed 2012-08-03T13:38:16-05:00 by curtis

  • Milestone changed from imagej-2.0.0-beta4 to imagej-2.0.0-beta5

Pushing to beta5.

comment:11 Changed 2012-09-07T12:48:19-05:00 by bdezonia

  • Blocked By 1463 added

comment:12 Changed 2012-09-20T11:30:35-05:00 by bdezonia

After a little discussion with Curtis:

There are three kinds of things that need to be stored in the undo history: the entire state of an object, the change by the last plugin Command, and the change by the last tool operation. This should allow us to capture all changes (right?) and helps minimize the size of the undo history when feasible.

For the snapshot of an entire set of data we need to serialize it, and during an undo operation restore it in a timely fashion. (Note: a Snapshot is just a Command that is itself reversible and would be stored in the undo history like any other command).

For commands that are invertible we need to be able to record the Command and it's mirror partner Command (Rotate 90 Left and Rotate 90 Right). In some case rounding issues might be a problem and then we just do a snapshot instead.

For the tools there are gestures that are important. We might just record a gesture at each mouse up. We might combine gestures so that it is less granular than that. Note that tools would need to be enhanced to generate events that the undo engine can track.

An example of why gestures are needed: in IJ2 hotdraw figures are first created with default values and then edited later by user gestures. We can't just capture a roi on creation and persist that info in the undo history. We also need the edits. But we want to group them so that an undo of a drawn roi would not be tedious and its not clear when the editing mode is "done". (Note the undo history might need to be smart about autocombining gestures)

The undo facility can be event driven (like a macro command recording history would). There is a whole set of events that get generated when modules are created, preprocessed, run, completed, etc. The undo facility should tap into this so that things are automatically recorded when possible.

Perhaps Commands could implement a Reversible interface. When something is reversible the Command builds a mirror opposite Command that can be queried of the Command. When a Command is reversible the undo service records the reverse command after the original Command runs. Otherwise it records a snapshot Command after the original Command runs.

In the shortest term we could keep all the undo history in ram and have user specify the amount to devote to Undo. And then we could purge older undo states when users continue to change data.

In the longer term we could use smart disk caching data structures that control how much ram they use and from which data can be pulled out. So in Imglib we could make an UndoImg (or MemoryLimitedCachingImg etc.) that would do this work.

There are some user interaction issues as well. We might detect that a change will be larger than the undo history could absorb. So warn user that this is not undoable and ask to proceed (with "never ask me again" a choosable option).

One future enhancement: save entire workspace to disk when IJ2 exits and optionally restore it the next time IJ2 is launched.

Last edited 2012-09-20T12:04:19-05:00 by bdezonia

comment:13 follow-up: ↓ 14 Changed 2012-09-20T13:38:44-05:00 by gharris

Another strategy is to store the large undo objects off the heap using java.nio.
An example of this approach is in envisaje / ImageNIO.
They have a [Byte|Int]NIOBufferedImage class where DataBuffer, WritableRaster, SinglePixelPackedSampleModel methods are overridden to use NIO. I wonder how this sort of approach could be applied to imglib2 data objects. My sense is that there is some overlap with addressing the ability to have a virtual stack.

The NIOBufferedImage code is here:
 https://github.com/imagej/envisaje/tree/master/ImageNIO/src/main/java/imagej/envisaje/imagenio

comment:14 in reply to: ↑ 13 Changed 2012-09-21T14:34:29-05:00 by curtis

Replying to gharris:

Another strategy is to store the large undo objects off the heap using java.nio.

I've been wondering for a while what the practical advantage of doing this is. I found  a nice article that provides a pretty thorough discussion of Java I/O including NIO stuff (i.e., ByteBuffer.allocateDirect()). From the article:

You might think that a direct buffer is a great way to extend the memory that your program can use. It isn't. The JVM is very good about growing the heap to the limits of physical and virtual memory, so if you've already maxed out your heap, there won't be any place to put a direct buffer.

In fact, the only reason that I can see for using direct buffers in a pure Java program is that they won't be moved during garbage collection.

But are garbage collection issues really something that is specifically relevant to undo/redo?

What is more interesting to me is using NIO in combination with JNI:

Direct buffers are useful in a program that mixes Java and native libraries: JNI provides methods to access the physical memory behind a direct buffer.

But that's not related to this ticket, of course.

comment:15 Changed 2012-10-05T16:30:19-05:00 by curtis

  • Owner changed from curtis to bdezonia
  • Status changed from accepted to assigned

bdezonia has been developing support for this on the 'undo' branch, so I am assigning this ticket to him.

comment:16 Changed 2012-10-15T11:59:17-05:00 by bdezonia

  • Owner changed from bdezonia to curtis

Note that ctrueden has taken the 'undo' branch and begun modifying it on the 'undo-ctr' branch. Assigning this ticket to him for now.

comment:17 Changed 2012-10-15T12:17:22-05:00 by curtis

We were hoping to get undo working for beta5, but unfortunately there will not be time. After thinking things through further, and discussing with bdezonia, there are still too many changes and improvements we want to make to the undo functionality.

The undo branch provides a good start on undo/redo functionality by providing an invertible operation interface, so each command can define its inverse in a flexible way. It also provides default behavior when a command is not natively invertible: saving and restoring of display snapshots. However, we need to push this logic into the module layer, so any module can be undone/redone, not just commands. We can then simplify the UndoService to require that each module be undoable. The CommandModule class can encapsulate the undo case logic, using its linked command's inverse operation if there is one, and using the snapshot restoration otherwise.

We also need the snapshot restoration to be generalized to support any type of output. (Though as an aside, note that module items of type ItemIO.BOTH are the only ones that need to be saved and restored for the purposes of undo; ItemIO.INPUTs are assumed not to change, and ItemIO.OUTPUTs are assumed to have been created by the module rather than modified from an earlier state.) The display state logic currently on the undo branch is a good start for managing snapshots of displays (specifically image displays), but for other types of mutable outputs (ResultsTables come to mind) we will need an extensible way for managing snapshots. Our best bet may be to define a new type of ImageJ plugin responsible for managing snapshots of certain types (sort of like how each widget manages inputs of a particular type and UI). In this way, we could support managing snapshots of third party objects (as opposed to requiring that undoable objects be defined a certain way, such as being serializable or implementing a specific interface).

comment:18 Changed 2012-10-19T15:45:44-05:00 by bdezonia

  • Blocking 1543 added

comment:19 Changed 2012-11-21T09:55:53-06:00 by bdezonia

  • Milestone changed from imagej-2.0.0-beta7 to imagej-2.0.0-beta6

comment:20 Changed 2012-12-27T10:53:17-06:00 by curtis

  • Milestone changed from imagej2-b6-legacy-undo to imagej2-b7-ndim-data

comment:21 Changed 2013-03-07T13:00:25-06:00 by bdezonia

  • Milestone changed from imagej2-b7-ndim-data to imagej2-unscheduled

comment:22 Changed 2013-04-15T09:55:25-05:00 by curtis

  • Milestone changed from imagej2-unscheduled to imagej2-b10-compatibility

comment:10 Changed 2014-05-06T09:15:58-05:00 by curtis

  • Status changed from assigned to closed
  • Resolution set to moved