Al is a DDJ contributing editor. He can be contacted at [email protected].
A new book by Michael Moore, the creator of Roger and Me, TV Nation, and other works of liberal satire. I saw Mike plugging his new book, Downsize This! (Crown Publishers, ISBN 0-517-70739-X) on a couple of talk shows and, on the day he said it would be released, went directly to the local Walden Bookstore. There, in a prominent display, were several copies of Downsize This! each with a big round sticker announcing "15% Off!" just under the title. Struck by the comical irony of the discount, I sent Mike a message--his e-mail address is on the last page of the book--alerting him that he was already being downsized with an automatic paycut on his first day of publication. Being an author myself, I added that publishing one's e-mail address can be a mixed blessing for an author. I get a lot of mail, not all of it constructive. Mike replied, "I'm not yet sorry I published this address. The response is fascinating." The book's been out only a few days Mike, and you're a lot more famous than me. Just wait.
Downsizing ain't all bad. I retired from consulting several years ago to concentrate on writing, but downsizing created new opportunities for some interesting work. It wasn't easy to trade jeans, T-shirt, and flex hours for appropriate attire, an ID badge, and 9-to-5, but I did it. Judy always looks on the bright side. She likes it when I work somewhere other than at home. More money and less husband, she says.
My new consulting work results from government downsizing. I teach C and C++ classes to federal employees who need to acquire new skills in the face of drastic budget cuts. I develop and maintain C++ programs for contractors who support their government clients but cannot hire programmers because of the uncertain future. Downsizing creates opportunities for people like me. We prosper on the plight of others.
Don't misunderstand. Despite the opportunities, I'm no fan of downsizing, even when it promises to cut government waste, a promise seldom if ever kept, by the way. Politicians who promise to cut government spending never address the obvious problems associated with doing that. Whether or not a government program is productive or useful, we cannot ignore the socio-economic superstructure that it has created and sustains. When they close a base or cut the budget of a big government project, they not only add a bunch of former employees to the welfare roles, but they indirectly downsize all the local businesses, too. Real people are affected. Clerks, bartenders, plumbers, sign-painters, sales people, garbage collectors, stockbrokers, teachers, preachers, mechanics, tradesmen, cops, real estate agents. Yes, and programmers, too. All with rent or mortgages, car payments, kids to feed. The next time your favorite candidate promises you less government, ask about the side effects. Who's going to pay for them?
delete this;
In September, I addressed the advisability of coding delete this; in a class member function. I said, "It's not a good practice." I got a lot of mail from programmers about that opinion. The vote seems to be split 50/50. Nothing is more interesting than a polarizing issue. Some readers sent code showing cases where they thought the idiom was acceptable, and, in some cases, necessary. Allow me now to clarify my opinion, which has been modified somewhat by the mail I received.
If you are designing a class to publish for others to use, do not allow it to delete itself. Period. Disagree if you like and code anything the language allows to your heart's content, but I stand by that conviction and will continue to code and teach according to that guideline. I'll repeat the problems: First, the only way that delete this; works is if the object is instantiated on the heap. Second, assuming that a class could assert that an object is on the heap (which it cannot), there is no way to assert that the user does not dereference the pointer to the object after the object has deleted itself--including deleting the object a second time.
Why do I persist in this position? In my consulting work I maintain programs written by programmers who have fallen to the downsizer's axe. In virtually every case where a class uses delete this;, the usage is the source of one or more bugs, usually because the program that instantiates the object tries to use the object after it has deleted itself. Furthermore, wherever I found the idiom in use, I was able to redesign the class so that it did not need delete this;.
I wondered if the heap-only problem could be solved. After several tries, I was unable to arrive at a platform-independent, fully-portable way for an object to:
- Assert that it was indeed instantiated on the heap.
- Ascertain that it had deleted itself and intercept and suppress subsequent deletes.
- Intercept dereferences of the object's pointer after it has deleted itself.
One of those rules was a shock. I thought that by overloading the delete operator, I could determine if the object had already deleted itself. The details of that attempt are not important. What is important is what I learned when Scott said to me:
The value of a pointer may be changed by the act of deleting it. Which is why this code [Example 1] yields undefined behavior. The problem is that the full action of the delete operator (not operator delete...) is not specified by the standard. We know that for single objects, it invokes a destructor sequence and then calls operator delete, but we have no assurance that that is all it does. In particular, it remains free to change the value of the pointer being deleted, and there is no way to take control over this.
To make his point, Scott referred to the following passage in the ANSI C++ Draft Working Paper, section "5.3.5 Delete."
It is unspecified whether the deletion of an object changes its value. If the expression denoting the object in a delete-expression is a modifiable lvalue, any attempt to access its value after the deletion is undefined. [emphasis added]
Maybe it's because I don't haunt the hallowed halls of language design and standardization, but it never occurred to me that the delete operator would modify the contents of the pointer variable that is its operand. It sounds so improbable, and I've never seen that behavior implemented in a compiler. I want to believe that the explicit behavior spelled out in that passage is a mistake, but, like most such anomalies in high-level languages, it must exist because somewhere a legacy compiler does it for whatever reason.
This rule raises a red flag. You often see classes that initialize pointers to zero in their constructors and delete those pointers in their destructors. They also delete those pointers and assign to them with new elsewhere. If it is possible that a class could have the equivalent of Example 1--two subsequent deletes of a thought-to-be-zero-value pointer without an intervening assignment of something valid, an insidious bug lurks waiting to bite you when you port this program elsewhere.
From Bjarne Stroustrup
I sent Bjarne Stroustrup a message asking his opinion of delete this;. He answered:
The delete this; construct is valid in a member function. Once that is done every access to a non-static member (data or function) is undefined. Caveat emptor!
The use of the construct comes with techniques for conditionally deleting objects. For example [see Example 2(a)]: I guess someone must have misused delete this; badly for it to become an issue, but I have not personally encountered it as a serious problem in real code. On the other hand, I don't recall using delete this; recently. These days, I tend to control such objects through "handles' that tend to live on the stack and in other objects... [see Example 2(b)].
Bjarne went on to demonstrate how, if the language rules prohibited delete this;, programmers would find ways around the restriction.
Readers of the Lost Art
My attitude was adjusted not only by communications with the rich and famous. Several readers wrote to express their opinions. Esa Leskinen wrote about his usage of the idiom to implement reference counting. Adam Sapek talked about how reference-counting COM objects use the idiom to destroy themselves. John B. Williston offered this comment:
[delete this; statements] are very handy for writing classes of the CListBoxPopupEdit type. This is a class that one instantiates passing a pointer to a listbox and an item index; the edit control pops up over said item, allowing editing of the text. The edit self-destructs whenever the user presses enter, escape, or changes focus. The instantiation is controlled by a static member function that returns no pointer to the object. Without this idiom, the edit control would need to send a message off to some other window to free its own CEdit object (or something like that--it would essentially make the object less reusable).
So, given the firm stand I took at the beginning of this discussion, how have I altered my opinion about delete this;? In More Effective C++ (if you program in C++, you need both of Scott's books), Scott proposes a base class that provides reference-counting behavior to its derived classes. A reference-counted class contains data members that can be shared among several objects of the class. You cannot get the same effect with static members because there might be other objects with different values. Scott uses the ubiquitous String class to make the point. When you assign one string object to another or construct a new string object from an existing one, there is no reason that they should not share the same physical string data. A reference count specifies how many objects share the data. Copy constructors and overloaded assignment operators increment the count. Destructors decrement the count. When the count goes to zero, the destructor deletes the data.
After implementing a self-contained reference-counting String class, Scott implements a generic reference-counting base class from which new reference-counted classes can be derived. When its count goes to zero, the object deletes itself. This usage would violate my guidelines if you used it as the base for a derived class that everyone uses. Instead, Scott uses the base class to derive a specialized class that contains the shared data portion of the objects. He embeds an object of that class in his published class. Objects that delete themselves are hidden from programmers who use the published class. Presumably, the author of the published class knows enough to deal appropriately with the private suicidal object. I do not object to a usage of delete this; that hides those details from users of the class. But I doubt that I will ever use the statement in my own code.
As Bjarne says, "caveat emptor."
Undoing the Undoable
The government project I've been working on includes a downscale custom word processor that works with SGML text. SGML is the architecture upon which HTML is built. One of the editor's requirements is that it support an Undo feature similar to those on high-end text editors and word processors.
The editor's Undo class hierarchy is tailored specifically to the needs of that particular editor. Users can type text with insert or overstrike mode, they can delete characters or blocks of text, and they can insert and delete SGML tags, which define the document components. During all this, tags can be exposed or hidden behind a WYSIWYG document interface, and redlining can be on or off. Any of these actions can be undone.
There are three basic variations on the Undo scenario. The simplest is what you find in small text editors such as the Windows 95 Notepad applet. Only your most recent action can be undone. The Word for Windows Undo feature includes Undo and Redo and can Undo all the way back to the document as it was before you started making changes or until you hit the limits of its Undo buffer. Each Undo action reverses a textual change to the document. The Brief programmer's editor, and its descendent, the Borland IDE editor work with Undo and Redo down to the keystroke level. Every keystroke, including cursor movements, can be undone. The Undo feature in the custom SGML editor is more like the second variation. It would be pointless, however, to publish its source code because of its tight coupling to the editor's document format.
Decomposing
In working with a music-related program, I had to develop a custom editor that lets users change a musical score. Actually, the document is more like what musicians call a "lead sheet" because it consists of measures with quarter-note beats and chord symbols. Its editor allows the insertion of chords and the usual clipboard operations on one or more adjacent measures. After using it for a while, I realized that my music editor was in sore need of an Undo feature. Sometimes I just need to decompose.
Comparing the very specific requirements of that SGML text editor with those of the music editor, I found that they have a lot in common when viewed from a higher level of abstraction. Both must remember the insertion, deletion, and replacement of arrays of objects in order to undo those actions upon demand. Both must store those undoable actions in a stack data structure so that the most recent action is the one undone.
In the case of the SGML editor, the objects can be characters, strings, and SGML tags. This organization is typical of how a word-processing document is organized. The document is one huge array of text with interspersed commands that identify a document's organization and presentation. Users change the document by adding, changing, and deleting these elements.
In the case of the music editor, the objects can be chords, tempo changes, repeats, rests, the song title, and rhythmic style changes. Ignoring the melody for this purpose, a song is an array of beats, grouped in measures, with each beat having a particular chord and, perhaps, one or more of the other events.
I concluded that a generic Undo class library is an appropriate approach to this problem, and I set out to build one by using C++ templates. The code that accompanies this column is the implementation of that library. At the moment, I have implemented only object insertions and deletions, which satisfy the requirements of the music program as far as it has gone. I need to implement object replacement later. It is my intention that this class library could be used to implement a full Undo feature in any program that needed it.
The library uses a variation of the generic programming model that STL uses. For an application to use the feature, the application must include a document class and what I will call here an object class. The document class maintains the document's buffer of data. The document buffer consists of some mixture of objects, each identifiable as a C++ intrinsic or user-defined type. The document must include two functions (three, when replace is implemented later) that permit the Undo feature to insert and delete arrays of objects. The application must then subclass two (three later) of Undo's classes to record the insertion and deletion actions to be stored for possible later undo.
The Generic Undo Class Library
Listing One is undo.h, which contains most of the implementation of the generic class library. The first class, UndoNode, is not a template. It is the base class from which all undoable actions are derived. Since the class is not a template, a later class can instantiate an array of pointers to the class without needing template argument qualifiers.
The next class is UndoItem<D,T>, which is a template base class for the undo actions. The D argument represents the application's document class, and the T argument represents the objects that can be inserted into and deleted from the document. The class contains a reference to the document class object, and two data members that all undo actions have in common: a pointer into the document buffer where the action occurred, and a count of the number of T objects involved in the action.
Two classes derive from UndoItem<D,T>: UndoInsertNode<D,T> is a base class for insertions into the document, and UndoDeleteNode<D,T> is a base class for deletions from the document. Both are constructed with the pointer into the document, the count of items, and a bool variable that specifies whether a subsequent undo action stops after undoing this action or continues with the next action. Both classes override the pure virtual Undo function from the abstract base UndoNode class. When users choose the Undo command, the program calls the Undo function for the appropriate action class.
The UndoDeleteNode<D,T> constructor stores the document reference and the pointer and count. Then the constructor allocates a buffer and makes a copy of what is being deleted so that an undo action can restore the deleted objects. This class's Undo function calls the document's Insert function passing the pointer and count. An application that uses this class library must provide a document class with an Insert function that accepts a pointer to its object class and a count of objects to insert. After calling Insert, the Undo function deletes the memory allocated for the buffer.
The UndoInsertNode<D,T> constructor also stores the document reference and the pointer and count. Undoing an insertion does not require remembering any prior data values. This class's Undo function calls the document's Delete function passing the pointer and count. An application that uses this class library must provide a document class with a Delete function that accepts a pointer to its object class and a count of objects to delete.
The third class in Listing One declares the UndoData class. An application instantiates an object of a class derived from this class to contain the undo information. An uninitialized array of pointers to UndoNode objects constitutes the circular stack of undo actions. The m_nCurrentUndo data member is the stack pointer. The m_nUndoCount data member counts the number of undo actions stored. The m_bUndoing data member is true while the class is processing an undo request and false otherwise. Users of the class can use this value (returned by the IsUndoing member function) to prevent their Insert and Delete document functions from adding undo actions during an undo. The IsUndoDataStored function tells the application when there are any actions that can be undone. An application can use this information to enable and disable the Undo command.
The application's Undo command calls UndoData::UndoLastAction, which does what its name implies.
Listing Two is undo.cpp, which contains the member functions for the UndoData class. The destructor deletes all remaining undo actions. The AddUndoNode function adds an action to the top of the stack. UndoLastAction pops the top undo action, calls its Undo function, and pops and calls lower ones until an anchored condition is found.
Listing Three is songundo.h, which represents part of an applications implementation of the undo feature with this library. The application subclasses the UndoInsertNode<D,T> and UndoDeleteNode<D,T> classes for each insertion and deletion action. The base class specifier provides the template arguments that identify the document and object classes. These subclasses need nothing more than a public constructor that passes the object pointer, count, and the anchor indicator to the base class.
The UndoSongData class is an example of the class that you derive from UndoData and instantiate into your application. It consists mostly of member functions that add undoable actions to the stack. The application calls these member functions when an undoable delete is about to occur or an undoable insertion has just occurred.
I have not tested this class library beyond the two applications I mentioned, but every indication is that, with the addition of an UndoReplace feature and perhaps an UndoCommand feature, this library would support most of the undo requirements of any application. Adding redo would be fairly simple. Redo is the inverse of undo, and the undo system could instantiate its own undo system.
Example 1: A shocker!
char *p = 0; delete p; // fine, deletion of the null pointer delete p; // undefined, p may no longer be null
Example 2: (a) Bjarne's first example; (b) Bjarne's second example.
(a)
Class Base {
int user_count;
// ...
public:
Base() : user_count(0) { connect(); }
void connect() { user_count++; }
void disconnect { if (--user_count==0) delete this; }
// ...
};
(b)
void disconnect { if (--objp->user_count==0) delete objp; }
Listing One
// --------- undo.h
#ifndef UNDO_H
#define UNDO_H
#define bool BOOL
#define false FALSE
#define true TRUE
class UndoNode {
bool m_bAnchor; // undo action stream terminator
public:
UndoNode(bool bStophere = true) : m_bAnchor(bStophere)
{ }
virtual ~UndoNode() { }
virtual void Undo() = 0;
bool Anchor() const
{ return m_bAnchor; }
};
//---------------------------------------------------------------------------
template <class D, class T>
class UndoItem : public UndoNode {
protected:
D& m_rDoc;
T* m_pPosition; // document position
int m_nCount; // item count
public:
UndoItem(D& rDoc,T* pPosition = 0,int nCount = 0,bool bStophere = true) :
UndoNode(bStophere),m_rDoc(rDoc),m_pPosition(pPosition),m_nCount(nCount)
{ }
virtual ~UndoItem() { }
};
//--------------------------------------------------------------------------
template <class D, class T>
class UndoInsertNode : public UndoItem<D, T> {
public:
UndoInsertNode(D& rDoc, T* pPosition, int nCount, bool bStophere) :
UndoItem<D,T>(rDoc, pPosition, nCount, bStophere)
{ }
virtual ~UndoInsertNode() { }
virtual void Undo()
{
m_rDoc.Delete(m_pPosition, m_nCount);
}
};
//--------------------------------------------------------------------------
template <class D, class T>
class UndoDeleteNode : public UndoItem<D, T> {
protected:
T* m_pData;
public:
UndoDeleteNode(D& rDoc, T* pPosition, int nCount, bool bStophere) :
UndoItem<D,T>(rDoc, pPosition, nCount, bStophere)
{
m_pData = new T[nCount];
for (int i = 0; i < nCount; i++)
*(m_pData + i) = *pPosition++;
}
virtual ~UndoDeleteNode()
{
delete [] m_pData;
}
virtual void Undo()
{
m_rDoc.Insert(m_pPosition, m_nCount, m_pData);
delete [] m_pData;
m_pData = 0;
}
};
//---------------------------------------------------------------------------
const int maxUndos = 300;
class UndoData {
UndoNode* m_pUndoNode[maxUndos];
int m_nCurrentUndo;
int m_nUndoCount;
bool m_bUndoing;
public:
UndoData() : m_nCurrentUndo(0), m_nUndoCount(0), m_bUndoing(false)
{ }
~UndoData();
void AddUndoNode(UndoNode* pUndoNode);
void UndoLastAction();
bool IsUndoDataStored() const
{ return m_nUndoCount != 0; }
bool IsUndoing() const
{ return m_bUndoing; }
};
#endif
