Undo/Redo Manager

Executive Brief

What? The Undo Manager Library adds undo/redo facilities to the MFC Library,
with full support for text views, along with simple command handling and menu
building.

How? Provide a set of classes and recipes that, as much as possible, provide
transparent and simple to use undo/redo facilities.

Why? I am former Mac programmer who wanted to learn about the MFC Library
and improve on one of the MFC Library’s weak spots.

Introduction

The Microsoft Foundation Classes is a sophisticated application framework which
greatly simplifies Windows programming. One of its weakest areas however is
the lack of usable undo and redo facilities. While several components of the
MFC Library do provide limited support, generally their implementations suffer
from one or all of these three drawbacks:

• single-level, not multiple-level
• oriented to a single view, not a document
• private implementations, not easily extendible

The first problem did not exist several years ago as the lack of undo was not
unusual, so providing any level of undo seemed like a major feature. For today’s
users however, an application seems unfinished without this capability and a
competitor’s product including it certainly has an advantage. It is also a great
"what if" feature, allowing users to experiment without needing to
manage many saved versions of a document.

The second and third problems are apparent in both the edit and rich edit controls
supplied with Windows. With the exception of Notepad and WordPad, these controls
are usually a small piece of the overall program and as such, should not maintain
their own undo/redo stack. To realize this, consider having two views, say in
a split window, that are views of the same document. This situation clearly
suggests storing text in the document, rather than in each view, so that both
views are always in sync. Likewise, the undo/redo stack should, in some way,
be associated with the document and not each individual view, or they potentially
can become unsynchronized. And of course, an application may have many more
operations than just text editing, but the undo/redo stack of the edit controls
cannot be used for non-text operations.

Now suppose the control is the center point of the application. Unless
the application is a simple variant of a text editor, the undo/redo capabilities
of the edit controls will most likely be useless as their implementation is
internal. With no public extension mechanism, generalizing even a built in operation
is virtually impossible as you don’t know what kind of information the stack
contains, nor can you even see the stack itself.

In both cases, when the control is the center point of the application and
when it is only a small portion, we can see that the undo capabilities of the
MFC Library leave something to be desired. What we need is a public, document-oriented,
undo/redo API that integrates well with the MFC Library.

Terminology

This guide assumes familiarity with design patterns as cataloged by the book
"Design Patterns: Elements of Reusable Object-Oriented Software",
by E. Gamma, R. Helm, R. Johnson, and J.Vlissides, especially the factory method
and template method patterns. In a nutshell, a factory method provides a central,
customizable function that creates (derived) objects of a specific base type.
It is typically used to create "helpers" and the function CBetterEditView::MakeEditAction()
is an example.

A template method is usually a non-virtual member function that invokes
a number of virtual functions, or bottlenecks, in a specific order. Effectively,
a template method is recipe whose steps must be followed, but each step is open
to interpretation. It also allows the base part of an object to call "down"
into the derived part. The function CREEditAction::Do() is an example
of a template method; CREEditAction::PerformOperation() is an example
of bottleneck.

I also like to make distinctions between the redefinition and the refinement
of member functions. Redefinition means that the base version of a member function
should probably not be invoked from within a derived version. Refinement,
on the other hand, means that the base version should be invoked at some
point, though this may be conditionally so. I have tried to state in each virtual
function’s commentary which technique seems more applicable. As a guide however,
within a subclass, factory methods are usually redefined and bottlenecks are
usually refined.

An Undo/Redo Framework

For discussion purposes, define an action as an operation which can be undone,
such as typing, changing the font height, or pasting text, and define the object(s)
they affect as targets. Actions generally affect a document, dialog,
or some other container-like object, and in general, we will call these objects
action targets. Operations, conversely, directly manipulate a subpart
of the action target, usually a specific view of a document. We will call these
more specific targets operation targets to distinguish them from an action
target. Note that an operation target often provides an implementation for a
specific operation.

An action differs from an operation in that an action can be undone, while
an operation cannot be, at least not by itself. This does not mean that an existing
operation cannot be used in implementing an action, and on the contrary, just
the opposite is often true. An existing (non-undoable) operation is usually
used in defining an (undoable) action version, and we’ll see this in the implementation
examples below.

Because of the additional behavior inherent in an action, it is useful to decompose
an action into three distinct facets: doing, undoing, and redoing. Although
their roles may seem obvious, it is instructive to see pseudo-code describing
these facets, especially when comparing them with actual code.

Do

1. Save the current or “before” state of the operation target
2. Perform the operation, producing an “after” state

Undo

1. If the action has never been undone, save the current or after state
2. Restore the before state

Redo

1. Restore the after state.

Note that most actions are lazy. They assume that other actions are ordered
and that states are saved only when absolutely necessary. As evidenced above
in undo section, the after state is saved only within it and not the do phase.
The first property, strict ordering of actions, simplifies the amount of information
which must be recorded in order to undo. The second property, saving only when
necessary, is an effective optimization in both time and space. For example,
consider typing some text then cutting a portion of it. The cut action need
only save the text it removes and not all of what was typed. The typing action
can also assume that if it is ever undone, the state of the text which existed
after typing was complete, is the current state now regardless of any actions
which followed.

Because of this laziness, and the fact that not every action is immediate,
the duration of action’s do phase becomes very important. For immediate actions,
like most commands, the duration of the do phase is by definition, very, very
short. Actions like typing, however, are not immediate. Yet we must know when
they are finished or saving state becomes rather difficult. To accommodate this,
we define a behavior, finishing, which saves any necessary state information.
We must also guarantee that this behavior will be exercised and the approach
taken is simple: an action must finish whenever another action enters its do
phase.

Lastly, let’s consider how the undo and redo commands function in a typical
application. When a user performs a series of actions, say typing, cutting,
then pasting, the most recent action done is the action which can be undone.
So selecting undo at that point undoes the paste action. Selecting undo a second
time undoes the cut action. And finally, selecting undo a third time undoes
the typing. The redo command is similar, with the exception that it is the most
recently undone action which is redone first. Clearly this last-in, last-out
behavior suggests maintaining actions on a stack, and we will often refer to
an action target’s undo or redo stack when talking collectively about its actions.

Actions and their Class Hierarchy

The class hierarchy of actions is listed below, though obviously many custom
actions would be needed for an application that was not text-oriented. Note
however that many actions will be simple variants of those below so you can
use them as models.The typing actions are particularly interesting as they are
the only non-immediate actions listed below.

As a convention, those actions specific to the rich(er) edit view are prefixed
with RE while those pertaining to the (better) edit view are prefixed
with BE. Because class CEditView is in one sense a simplification of
the CRichEditView, the set of actions for CBetterEditView are a subset of those
CRicherEditView. Because neither view is actually related via inheritance, and
that there really are some major differences between the two views, neither
set of actions is actually related to the other.

CAction

CBEAction

CBETextAction

CBEEditAction

CBEReplaceAction

CBETypingAction

CREAction

CRETextAction

CREEditAction

CREReplaceAction

CRETypingAction

CREStyleAction

CREParagraphAction

CREInsertObjectAction

As a running example of how to implement and use an action, we will examine
how the cut operation has been extended into an undoable action. This action,
since it shares many traits with the other clipboard commands, is capable of
pasting and clearing as well. (Copying is not destructive, so it need not be
undoable nor does it require an action.) In fact, because it modifies text in
an edit view, as many operations for the edit view classes do, it is derived
from a base class, CBETextAction. Although this sounds like quite a
bit to digest, it is representative of most actions. We’ll first look at class
CBEEditAction and then follow with a description of class CBETextAction
.

CBEEditAction

The constructor for class CBEEditAction is typical of most action
constructors. The first argument is the operation target, which in this case,
is an instance of class CBetterEditView. The second argument is a resource
id representing a specific action type. Unlike commands, actions use a string
id to distinguish action types. This not only allows distinguishing a specific
operation within a multi-use action, it allows a string resource (a name) to
be associated with the action for use in an undo/redo menu. The last argument,
which is not used in this particular action, allows for additional user-defined
data to be passed. We won’t examine the implementation of this constructor because
its base class constructor actually performs all relevant initialization.

CBEEditAction(CBetterEditView *operationTarget, UINT actionType, void *data);

Also typical is the Do() member function, especially for multi-use
actions. First and foremost, the base version of CBEAction::Do() is
called. This is important as most actions automatically notify the undo manager
that they exist, and this is done in the function CAction::Do(). You
can control this with the autonotification feature, either as you construct
the action or later with the CAction::SetAutoNotify() member. Note
that if autonotification is off, then you must notify the undo manager yourself
with a call to CAction::NotifyUndoManager(). Eventually, this call
will tell the previous action that it must finish and hence, its importance.
It is also imperative to avoid making major changes to a target until this is
done, as the previous action may have state left to save.

Second, a helper or bottleneck function, PerformOperation() is called,
making this a example of a template method. In this case, the bottleneck does
not actually perform the operation but instead calls yet another routine in the
operation target which does. This seems complicated but its utility will become
apparent once you realize this action works with cutting, pasting, clearing, and
replacing text. With a small amount of work which is decsribed below, it will
work with any edit-like operations you define.

At the very end of the Do() routine, the Finish() member
function is called. Since clipboard operations are immediate, the action finishes
as soon as the operation completes.

void CBEEditAction::Do()

{

}

 

void CBEEditAction::PerformOperation()

{

}

In a single-use action, you would probably perform the operation or call a
PerformXXX() routine directly in your Do() routine. The role
of PerformOperation() here is to isolate code specific to an operation
from the shared behavior in a multi-use action. Subclasses, whose operations
will obviously be very similar to cut, paste or clear, need only to refine/redefine
PerformOperation(). See class CBEReplaceAction for an example.
To recap, the chain of calls is

1. CBetterEditView::OnEditCut()         (creates action)

2. CBEEditAction::Do()                  (saves state, calls bottleneck)

3. CBEEditAction::PerformOperation()    (switches on action type)

4. CBetterEditView::PerformCut()        (performs cut operation)

Again, note that the operation target does all of the work. Another possibility,
better suited for complicated single-use actions, is to place the brunt of operation’s
implementation inside the action itself. This keeps the operation target lightweight
and simpler to use, but also transfers the responsibility of subclassing onto
the action.

Note also that this particular action class does not define redo, undo, or
any state-saving routines itself. Instead, that functionality is provided by
the base class, CBETextAction.

CBETextAction

The constructor for class CBETextAction passes on its argument to
its base class too. Unlike its child class above however, it also saves the
current selection, both the selected text and the selection endpoints. This
information is stored in an instance of the utility class CTextRange,
just as it is in the rich edit version, class CRETextAction. Here however,
the endpoints are ints rather than longs and only the string portion is actually
relevant to the edit view classes. (Class CTextRange is considerably
more general than indicated here and can be used to store text styles, paragraph
styles, OLE objects and user-defined functions.)

CBETextAction::CBETextAction(CBetterEditView *aView, UINT type)

   : CBEAction(aView, type)

{

}

No Do() member function is defined in class CBETextAction,
leaving a derived class to provide it as CBEEditAction does. Because
many of these derived actions are immediate, the Finish() member function
will usually be called inside of a derived Do() routine. Class CBETextAction
does define this function, and does so somewhat surprisingly. It simply saves
the endpoint of whatever was inserted and not the text itself. As we stated
before, state (the text in this case) is only saved if the action is undone.

void CBETextAction::Finish()
{  

CBEAction::Finish();
    
int start, end;
    
// save insertion end (long vs. int)
operationTarget->GetSelection(&start, &end);
inserted->end = end; 

}  
Finally, we come to the meat of an action, the Undo() and Redo()

  member functions. In this case, it is more helpful to consider pasting text

  over text. Before the action pastes anything, it saves the current selection

  (fully) in the deleted text range. Then, it performs the paste operation

  which inserts new text and saves the endpoints, as noted above. To undo the

  paste, we must save what was pasted, then restore what was deleted. Redo is

  very similar, differing mainly in the range which is restored. Because both

  routines share so much, most of the grunt work is performed in SaveRange()

  and RestoreRange(). We won’t consider them here; they mostly copy text

  to or from the edit view.
void CBETextAction::Undo()
{  

CBEAction::Undo();
    
// save only during the first undo; after
// that, we have the information we need.
if (neverUndone)
{    

neverUndone = false;
SaveRange(inserted); 

}

// deleted any inserted text
DeleteRange(inserted);
    
// insert any deleted text, restore selection
RestoreRange(deleted); 

}
  
void CBETextAction::Redo()
{  

CBEAction::Redo();
    
// re-delete the deleted text
DeleteRange(deleted);
    
// re-insert the inserted text
RestoreRange(inserted); 

}  
Action Targets

An action target is usually a document, dialog or some kind of pseudo-container

  of the operation target. The action target is also not usually responsible (directly)

  for performing an operation. For example, consider a simple text editor which

  follows the document-view paradigm. It probably is composed of an edit view

  and a document object, or in our world, an operation target and an action target.

  When a user chooses the cut command, both the edit view and its document are

  affected, but the latter’s change is a consequence of the former’s. The document

  does not implement the cut operation but it is nevertheless aware of it. In

  general, when an operation target is modified, so is the corresponding action

  target.
Once an action target is created, it needs to inform the undo manager of its

  existence by calling CUndoManager::RegisterTarget(). This is commonly

  done in a refined version of OnNewDocument(), e.g., 
BOOL CPadDoc::OnNewDocument()
{

if (CDocument::OnNewDocument())
{

}
else

return FALSE; 

}

Likewise, the action target must also remove itself, or memory will be lost
until the application quits.

void CPadDoc::OnCloseDocument()
{

CDocument::OnCloseDocument();
gUndoManager->RemoveTarget(this);

}

Operation Targets

An operation target is usually a view of some sort that is directly responsible
for performing an operation. For example, consider the text editor example again.
Choosing Edit:Cut sends the ID_EDIT_CUT command (eventually)
to the edit view. The edit view actually performs the operation of copying the
text to the clipboard and clearing the selection. The responsibility lies with
the edit view rather than with a frame window, document or the application object
itself.

To add undo/redo capabilities to an edit view, the CBetterEditView
class overrides a number of command handlers to create an action to carry out
the operation. Consider the cut example again. When it handles the ID_EDIT_CUT
command, it creates an action that encapsulates the operation. The action will
save whatever state is necessary, then perform the operation.

void CBetterEditView::OnEditCut()
{  

  

// create the appropriate action (IDS_CUT_ACTION);
lastAction = MakeCutAction(IDS_CUT_ACTION);
    
// do the last action
lastAction->Do(); 

}   
The creation of the action resides in a factory method so that subclasses can

  easily override with a different action. For example, to support automatic word

  selection, a derived action might automatically extend the selection from a

  simple collection of characters to the word containing those characters and

  then perform the cut..
CREAction *CBetterEditView::MakeCutAction(IDS_CUT_ACTION)
{  

return new CREEditAction(this, IDS_CUT_ACTION);    





}  
When the CBEEditAction::Do() member function is invoked, it will save

  the current selection and call CBetterEditView::PerformCut() to actually

  cut the selection. We saw this in the section on actions, so here we will concentrate

  on the implementation of operation. Because it is an operation, we do not need

  to save any state information. Nor do we need to do much of anything as the

  cut operation is already defined in the base class, CEditView.
void CBetterEditView::PerformCut()
{  

// call existing operation in base class
CEditView::OnEditCut(); 





}  
Class CBetterEditView and class CRicherEditView extend the

  CEditView and CRichEditView classes respectively. In general,

  each override of a handler follows the above logic, so that calling OnEditXXX()

  should produce an action and PerformXXX() should perform the operation.

  You can also call the base version CRichEditView::OnEditXXX() directly,

  in addition to PerformXXX(), if an action is not needed..
Handling Edit:Undo and Edit:Redo
A view not only creates actions and performs operations. It is often responsible

  for handling an undo/redo command and updating their respective menus. To respond

  to an undo command (ID_EDIT_UNDO), you would add a message handler

  as you would normally do for any command. In the implementation of the handler,

  call the member function CUndoManager::Undo(), passing as an argument

  a pointer to whatever the action target is. Usually this will be the view’s

  document. The classes CBetterEditView and CRicherEditView

  already define this, and an update version, so it is largely a matter of defining

  the appropriate menu items and accelerators to activate them. You can be copy

  the implementations below to any view you define.
void CBetterEditView::OnEditUndo()
{  

// tell undo manager to undo the last action
// associate with the document (action target)
gUndoManager->Undo(GetActionTarget()); 





}  
The Undo Manager Library also supplies a basic menu handling class, class CSimpleUndoRedoMenu.

  It defines a static member function, Set(), which automatically enables,

  disables, and modifies the text of the menu item as appropriate. It requires

  the CCmdUI pointer and the action target and produces a menu item with

  the caption Undo followed by the action name.
void CBetterEditView::OnUpdateEditUndo(CCmdUI* pCmdUI)
{  

CSimpleUndoRedoMenu::Set(pCmdUI, GetActionTarget()); 





}  
Note that these member functions appear here exactly as they are implemented.

  By default, the action target is assigned the view’s document object in CXXXEditView::OnCreate().

  You can override that setting by calling CXXXEditView::SetActionTarget();

  just do so before any action is created.
CUndoManager

Rather than being a part of a document or dialog and defining message handlers

  to communicate, the set of targets and their undo/ redo stacks are connected

  via single global object, referenced through gUndoManager. While global

  objects should in general be avoided, I believe this implementation is the best

  possible one when integrating two separate libraries. This is especially true

  in the MFC Library, as an individual object can only send arbitrary messages

  to CWnd derivatives.
Construction & Destruction
Because the undo manager is global, and because there is a potential for subclassing,

  the undo manager must be dynamically created and destroyed to allow the substitution

  of a derived object. Within the MFC Library, a convenient place to do this is

  in the InitInstance() and ExitInstance() member functions

  of the application. In the application CMultiPadApp, the following

  overrides appear.
BOOL CMultiPadApp::InitInstance()
{   

gUndoManager = new CUndoManager();


  

// remainder of InitInstance()
. . .





}
  
 int CMultiPadApp::ExitInstance()
 {   

delete gUndoManager;
return CWinApp:ExitInstance();





}   
A side benefit of dynamic allocation is that it provides a fast way to reclaim

  all memory used by the undo manager and its internal STL data structures. In

  a low memory situation, deleting the global instance will delete all action

  managers, all actions, the actions’ saved data, and free the space reserved

  by the STL allocators. The user will lose the ability to undo/redo previous

  actions but in light of a catastrophy, this is a small price to pay. Don’t forget

  to recreate the undo manager and re-register all of the previous action targets,

  or it will be an irrecoverable failure!
Registration
We’ve already mentioned that an action target must register itself with the

  undo manager. The prototype for this routine is slightly more general than in

  the example shown above, and in fact you can limit the number the undo levels

  and adapt how the undo manager notifies an action target of undo/redo changes.

  You can also change the options for an existing action target, say to dynamically

  increase the size of the undo stack or even to change how notification is handled.

  (Yes, you can call the registration routine again and again.)
The constant UM_DEFAULT_STACK_CAPACITY is programmer-definable, usually

  in a precompiled header file or in the options for the compiler. If this constant

  is not defined, it is set to 25. A large value, say LONG_MAX, effectively

  creates an unbounded stack, as it is doubtful a user could perform that many

  actions in a sitting.


virtual void RegisterTarget(
                            void *actionTarget,
                            size_t capacity = UM_DEFAULT_STACK_CAPACITY,
                            NotifyFn fn = UMDefaultNotifier
                           );

Notification
The undo manager itself is independent of the MFC Library and thus, an action

  target is represented with a generic pointer. Rather than forcing the target

  to be a derived instance of CCmdTarget, or derived instance of any

  specific class for that matter, the undo manager uses a callback to communicate

  with the action target. If the undo manager is being compiled along with the

  MFC Library, the default callback tests for an instance of class CDocument

  and sets its modified flag appropriately. Note that this behavior is correct

  even if the action target is really a dialog box, as dialog boxes generally

  are not interested in such changes.
void UMCmdTargetNotifier(void *actionTarget, UMNotificationData &data)
{

CCmdTarget *cmdTarget = (CCmdTarget *)actionTarget;
if (cmdTarget->IsKindOf( RUNTIME_CLASS(CDocument) ))
{    


    

((CDocument *)cmdTarget)->SetModifiedFlag(data.isDirty);

  

  

}





}

On the other hand, if the MFC Library is not present, the default notification

  routine does nothing and probably requires replacement by the programmer.
CActionManager

This class connects a single target with its undo and redo stack. It is hidden

  from view by the undo manager and is never used directly. Most of the member

  functions in class CActionManager mirror those in class CUndoManager;

  the routines in the undo manager generally perform a lookup to find the appropriate

  action manager, then forward the member call to that action manager.
The action manager maintains a marker indicating the size of the action target’s

  undo stack when it was last clean. In the context of a document, clean means

  saved, and we will assume we are working with a document to keep things concrete.

  At first, the marker is zero, meaning that all actions must be undone before

  the document is back to its initial (clean) state. As actions are performed,

  the document accumulates little changes that become "permanent" once

  the document is saved. Permanent here does not mean that they cannot be undone.

  It means that if they are undone, they dirty the document like any other operation.

  Only if they are redone will the document be back to its last-saved state.
Because the stacks used by an action manager are finite, they may occasionally

  overflow if the user is patient enough! If this happens, the bottom-most action

  is discarded and the marker is set to -1, indicating that no amount of undo/redo

  can return a document to a clean state, unless it is saved again.
CSimpleUndoRedoMenu

This class sets and enables or disables undo and redo labels in Edit

  menu. It requires a pointer to CCmdUI to adjust and a pointer to the

  action target it should use when building the menu item. It uses the CCmdUI

  pointer to identify which stack should be used in constructing the menu item.

  Also note this class is not usually instantiated as its only member function

  is static.

void Set(CCmdUI *pCmdUI, const void *actionTarget);  


Implementation Example

To illustrate using the Undo Manager, we shall add multiple undo to the MultiPad

  sample application included with Visual C++. This application is a simple text

  editor which uses the multiple document interface. As is, it supports only one

  level of undo.
Setting Up The Project Workspace
1. Copy the source files for the MultiPad application into a local directory.

  See the InfoViewer Topic “MultiPad: Edits Files Simultaneously” for information

  about MultiPad and for information about obtaining its source code.



2. Add the path up to and including the directories, Undo Manager

  and its subdirectory, UM Header Files, to your default search path.

  You can do this by using the /I directive or selecting Tools:Options,

  then clicking on the Directories tab, and finally selecting the Include

  Files in the Show directories for: combo box. If you plan to use

  the Undo Manager Library in many projects, the latter approach is preferable

  since it is global change.
3. Normally, maintaining parity with the existing folder structure in your

  directories simplifies project management, and the example here assumes you

  will do this, so create the following folder structure in your project:

  


    
Undo Manager


    


      
UM Header Files

UM Source Files


    


  



4. Add the contents of the Undo Manager directories to their respective folders

  in your project workspace. Do NOT add the top-level resource script “UndoManager.rc”

  directly to your project.
5. Switch to the Resource View and right-click on the resource folder. Select

  the item Resource Includes... from the pop-up context menu. In the

  second edit-box, entitled Compile-time directives:, add the following

  line:

  

#include "UndoManager.rc" 
  



 With the exception of steps 1 and 2, you would follow this recipe for each

  project that requires the Undo Manager Library. You may also have to add the

  files to ClassWizard yourself, otherwise they won’t be available.
You should be able to build the entire project at this point. Since you have

  not made the necessary calls to the Undo Manager Library, the built application

  will be no different than the default MultiPad application, but it is useful

  self-check.
Modifying the MultiPad Application
1. Add the following includes to the top of file multipad.cpp, just

  after the include of <locale.h>:

  

#include "UndoManager.h"
#include "BetterEditView.h"