Fog Creek Software
Discussion Board




Undo/Redo algorithm with large data chunks

I am finishing off an application that is largely complete and pretty solid.  The app has a pretty nice undo/redo feature. Basically the way it works is there a whole bunch of attributes (actually a simplification but illustrates the point).

When you make a change it saves the previous values into a undo manager (which stores a series of previous attributes values in memory), so they can be undone. When you start actually undoing, it has a redo manager (basically the same as undo manager) for reinstating undo changes.  As the attributes are fairly small, it just saves them all.

There is one case it doesn't cover properly.  There are huge chunks of binary data floating around. This can be (but relatively infrequently - but not so infrequent as not to worry about) edited too.  At the moment changes to these can't be undone (actually there is an unrelated bug in that you can't actually do the edit - which is why lack of undo is not a problem).  By huge chunks I mean potentially several megabytes

Just so you know, it's not like you can say, they edited byte 50 to 37.  ALL the binary data can change in one go.

So I'm curious what you might suggest to handle undo.  I'm thinking about saving the previous binary data into temporary files, but I'm worried about multiple instances, leaving temp files behind on the disk in case of bad shutdown, etc.

S. Tanna
Thursday, June 05, 2003

Disclaimer: You didn't mention any detail about the environment, so I'm going with what I know, i.e., Windows.

> So I'm curious what you might suggest to handle undo.
> I'm thinking about saving the previous binary data into
> temporary files, but I'm worried about multiple instances,

Each instance can get a unique ID from a service (also developed by you). When your app starts, it checks for the service app. If it isn't there, launch it. Then, request an ID. Use that ID to stamp that instance's temp files (e.g., use it to name a folder where all the instance's temp files will be placed).

> leaving temp files behind on the disk in case of bad
> shutdown, etc.

When your "ID server" (IDSrv) starts, it could make some sort of check to see if there are any temp files remaining from older sessions, and peform a cleanup.

You could add another verification layer, for the case where your IDS goes down, but there are 1 or more instances of the app still running. E.g., assume you store the process IDs (or main window handles) and corresponding unique IDs (generated by your IDSrv) in a file (that will be deleted when you IDSrv exits normally); if your IDSrv starts and that file is present, then you can check if those IDs still correspond to instances of your apps; if that's not the case, your IDSrv can delete the folders that are no longer being used.

It's a starting point.
--
"Suravye ninto manshima taishite (Peace favor your sword)" (Shienaran salute)
"Life is a dream from which we all must wake before we can dream again" (Amys, Aiel Wise One)

Paulo Caetano
Thursday, June 05, 2003

Having a separate id generating service is overkill - and a source for many more bugs.  If you want a unique ID why not just generate a GUID?  Use this as part of a directory name.  All temporary files for a given instance then reside in a single directory.

For cleanup do what Paulo suggests but within the main app not a separate server.  If each running instance of the server hold open a well known file within its temp directory.

When the server starts up enumerate all the temporary directories (based on some naming convention) and try to delete the well known file.  If that succeeds delete the entire directory since it is no longer in use.

If there are any errors in this process just ignore them and move on. 

.
Thursday, June 05, 2003

I add a state property to all my classes. This takes the class data and turns it into a byte array.

Now I don't use this for every command that uses undo/redo but when I do need to store everything on a class I use the state variable to get that information and to restore it.

From there I either store it in memory (if it small) or write out to disk into a temp directory based on a unique GUID for that session.

Robert Conley
Thursday, June 05, 2003

> For cleanup do what Paulo suggests but within the main
> app not a separate server.  If each running instance of
> the server hold open a well known file within its temp
> directory.

My suggestion to delete the files from the server was only when one of the instances of the main app crashed, i.e., did not exit normally. You're absolutely right in that each main app instance could do its own cleanup (but see below).

Also, I meant the "ID service" and the "server" to be the same thing, but I didn't make it very clear. Besides, according to McConnel, calling it "ID server" just goes to show I haven't quite understood what's the role of this component in the whole system. It's a server, definitely :)

It's candidate list of responsibilities could be:
1. Generate a unique ID (could be a GUID).
2. Register a client (i.e., an instance of the main app). Could be done when the server receives a request for a new ID. The client should identify itself (with its process ID and/or main window handle).
3. Unregister a client (i.e., an instance of the main app).
4. Check for "zombie folders" (on startup or periodically), by polling the registered clients (using the window handle), or the OS (using the process ID).

Actually, the server could be a good place to actually create the folders and delete all the files. It would allow you to centralize all the "temp folder" management service in the server.

The sky's the limit :)
--
"Suravye ninto manshima taishite (Peace favor your sword)" (Shienaran salute)
"Life is a dream from which we all must wake before we can dream again" (Amys, Aiel Wise One)

Paulo Caetano
Thursday, June 05, 2003

I would take the simple approach: treat your byte arrays just as you would anything else.

That is, keep them in memory. A few megabytes isn't so huge these days. If the amount of data exceeds available real memory, the OS's memory manager will write the data to the page file. This is likely to be more efficient than you writing it to data files.

Going this route, you may want to put an upper bound on the amount of data used by your undo/redo manager, and throw away old undo info that exceeds the bound. For Windows, an arbitrary value somewhere in the 100Meg - 1Gig value is probably appropriate.

If you can't afford such an upper bound, then you probably want a general means of spilling all undo/redo info to a file, not just the big arrays.

Jim Lyon
Thursday, June 05, 2003

Yes Win32, Win95 and up

I was thinking maybe do the cleanup with the app itself
- When it exits (normal shutdown)
- When it starts (to clean up garbage from a previous crash)

I need to restudy how the attribute undo works (as it's a little more complicated than my original explanation as there are two kinds of attributes) before I can confidently make more detailed comments/thoughts.

Consider the question still open.

S. Tanna
Thursday, June 05, 2003

> - When it starts (to clean up garbage from a previous
> crash)

This means you'll only have one instance, right?

Otherwise, when you start a new instance, how does it know what do delete? Or even if it should delete anything?

Paulo Caetano
Thursday, June 05, 2003

Not necessarily.  I was thinking about maybe having some shared data (memory) between the instances to avoid one copy nuking the other's files.

S. Tanna
Thursday, June 05, 2003

If you want to 'swap' the data out to a file, why don't you create a file using GetTempFileName() and then CreateFile() with dwFlagsAndAttributes set to FILE_ATTRIBUTE_TEMPORARY | FILE_FLAG_DELETE_ON_CLOSE?

Roland Kaufmann
Thursday, June 05, 2003

Close button I potentially need to keep a series of files for multiple undos (undoes? undo's?). Unless I keep them all open until the app exits, they get deleted to earlier. And I will run out of file handles in typical Win95 environment.

S. Tanna
Thursday, June 05, 2003

Urgh... can you not compress this binary data down to something small? Like, a record of which command was invoked to generate it?

(If you are using undo and redo queues, each of contains commands that are the inverse of the corresponding command in the other, and you ensure the queues are accessed in the right order, you do not need to worry about preceding or future operations because it will happen all in the right order.)

Tom
Thursday, June 05, 2003

That's actually a very intelligent question, and the anwer is: sometimes

The binary data is actually raster images.  Let's just say not all the commands are reversible without retaining the original image some place.

S. Tanna
Thursday, June 05, 2003

There's another way to handle temp files.
Use IE's cacheing functions. Set up your own cache. Name the files how you want (filename_undo_23). Clear it when you shutdown and when you launch (in case of previous bad shutdown).

IE is part of the OS after all.

mb
Thursday, June 05, 2003

*  Recent Topics

*  Fog Creek Home