Columns

Stepping Up To C++

Compilation Firewalls, Part 1

Dan Saks

Dan Saks is the president of Saks & Associates, which offers consulting and training in C++ and C. He is secretary of the ANSI and ISO C++ committees. Dan is coauthor of C++ Programming Guidelines, and codeveloper of the Plum Hall Validation Suite for C++ (both with Thomas Plum). You can reach him at 393 Leander Dr., Springfield OH, 45504-4606, by phone at (513)324-3601, or electronically at dsaks@wittenberg.edu.

In many ways, C++ classes provide solid support for data abstraction. A class gathers the representation of a data type (its data members) along with the operations on that type (the member and friend functions) into a single, clearly-defined program unit. Access specifiers (the keywords public, protected, and private) clearly distinguish those parts of the class that clients (users of the class) can access from those parts that only the class supplier can access. A well-written class defines an abstract type with complete and consistent behavior that you can use with little or no concern for how it works.

Many classes provide behavior that you can implement in more than one way. For example, you can implement the abstract behavior of a symbol dictionary using any number of concrete structures, like a binary tree, a B-tree or a hash table. Depending on the anticipated volume of data and the application's speed and memory requirements, you might store the entire dictionary in dynamic memory, or keep only the retrieval keys in memory and store the rest on disk.

No one implementation of a particular abstraction is right for all applications. Estimating system performance during analysis and design can guide you in selecting a good implementation. But you won't really know if you made the right choice until you measure the assembled application's performance using real-live data. The measurements may indicate that another implementation yields better performance. If the class is well written, you simply slip a different implementation behind a given class interface and rebuild the application without modifying any client source code.

C++ lets you do all this, but there's one hitch. Almost invariably when you change the class implementation, you change the declarations for one or more private members. And those declarations are in the header that defines the class. If you use a make system (or the project system that comes with many development systems), rebuilding the application will recompile every source file that directly or indirectly includes the header for the revised class. (If you don't use make or its equivalent, you may get some real surprises when you test the application.) When your application is large, the lengthy build times can really reduce your productivity.

Actually, providing alternative implementations is a special case of the more general problem, namely, that any change to the private part of a class forces you to recompile source code that appears unaffected by the change. The root of problem is that C++ syntax does not physically separate all of a class's implementation details from its client interface. Another way to look at this is that a class's compilation interface typically is wider than its public interface.

The compilation interface of a class is what a compiler needs to know about that class to compile source code that uses the class. The compilation interface consists of the entire class definition — the member declarations (private and protected as well as well as public), the friend declarations, and the inline function definitions. The public interface is what a client programmer needs to know (yea verily, is allowed to access) about a class when writing code that uses that class. The public interface consists only of public members and friends of the class.

Why was C++ designed with this apparent flaw? As with any language, C++ has its share of design trade-offs. C++ places space and time efficiency of generated code at a higher premium than the speed and convenience of the translation process. The lack of physical separation between class interface and implementation offers real benefits in both storage efficiency and run-time performance.

Morever, if you really need to physically separate a class interface from its implementation, C++ offers you a choice of programming conventions that will do this. By following these conventions, you can write any class so that its compilation interface is essentially the same as its public interface. Booch [1991] refers to this process as building "compilation firewalls," so that changes in the implementation of one class don't trigger a massive recompilation.

The two most common techniques for building compilation firewalls in C++ use the following:

This month, I'll present Cheshire Cat classes. Next month I'll explain protocol classes and consider the costs of each approach.

I'll begin by presenting a sample application that has a class with two distinct implementations for the same public interface. Like many complete C++ programming examples, it requires quite a bit of explanation, including a few side trips. So bear with me and I'll to get to the point as quickly as possible.

A Cross-Reference Program

xr is a simple cross-reference generator which I've used as an example in earlier columns. (See "Writing Your First Class," CUJ, March 1991; "Your First Class," CUJ, May 1991 and/or "Rewriting Modules as Classes," CUJ, July 1991.) xr prints an alphabetized list of words appearing in a document read from standard input. The program views its input as a sequence of words (a sequence of letters and digits starting with a letter) separated by non-words (such as spaces, punctuation, and digits). xr prints each word on a separate line followed by a list of line numbers on which that word appears in the document.

For example, if the word "object" appears in the input once on lines 3, 19, and 100, and twice on line 81, then the output entry for object is

object     3  19  81  100
The program makes the simplifying assumption that all line numbers found will fit on a single output line. That is, it doesn't include any logic to break a long output line at a nice, neat place.

The program spans several source and header files. Listing 1 shows the main module. main uses the getword function to scan the input and pick out each word that goes in the cross-reference. main delegates the work of collecting and printing cross-reference entries to a single local object x of type xrt.

xrt is the cross-reference table class. The xrt class definition appears in xrt.h (Listing 2) , and its implementation appears in xrt.cpp (Listing 3) . This particular implementation uses a binary tree to store the cross-reference entries in alphabetical order.

xrt is a handle class. That is, xrt consists merely of a pointer (a handle) to an associated data structure (the body) that does the real work. That pointer is the private data member root, which is a pointer to a treenode.

xrt.h declares, but does not define, class treenode. The declaration

class treenode;
declares treenode as an incomplete type. You cannot declare objects of an incomplete type, because the type declaration doesn't provide any object size or layout. However, you can declare pointers and references to objects of incomplete type, just like xrt::root in Listing 2.

Why did I declare treenode as an incomplete type? Why didn't I define the class at the time I declared it? xrt and treenode are mutually referential types. That is, the definition for xrt refers to treenode, and the definition for treenode refers to xrt. As in C, the only way to do this in C++ is by using pointers to incomplete types. You declare one class (in this case, treenode) as an incomplete type, then define the second class (xrt) with members that are pointers to the incomplete type. Then you complete the incomplete type by defining it.

xrt.h does not complete treenode, because it doesn't have to. Only xrt.cpp uses treenode, so only xrt.cpp completes treenode before using it. Client code, like main, which includes xrt.h, should not be aware that treenodes even exist. Therefore it shouldn't matter to that code that the type remains incomplete.

Leaving treenode incomplete in xrt.h has the added advantage of removing implementation details from the header. Changes in the structure of a treenode don't induce changes in the header. The incomplete type acts as a compilation firewall. This mechanism is a foundation of the Cheshire Cat technique. As you will see shortly, the Cheshire Cat technique is a set of uniform stylistic conventions for building compilation firewalls from handle classes and incomplete types.

You could argue that leaving treenode incomplete in xrt.h also adds a little more security to the interface. xrt.h declares treenode at file scope, so any compilation that includes xrt.h adds treenode to its global namespace. But a treenode should be invisible to client code. If you can't make it invisible, the next best thing you can do is render it unusable. Leaving treenode incomplete seems to do just that. The compiler will reject any client code that tries to create an object of incomplete type treenode.

Unfortunately, nothing prevents client code from inadvertantly completing the incomplete type. Client code that completes type treenode may be in for some real surprises if it supplies its own definition for treenode that differs from the one in xrt.cpp. If the code makes it past the linker, the program may exhibit very subtle run-time errors.

The completed class treenode in xrt.cpp specifies the layout for each node in the binary tree. It pairs a word with a sequence of line numbers on which that word occurs in the input. It also contains left and right subtrees, implemented as xrt objects.

treenode uses a pointer to a dynamically-allocated null terminated character string that holds the spelling of a word. It uses an object of class type lns (line number sequence) to hold the set of line numbers associated with that word. (Earlier versions of this program that I published use the name In_seq instead of Ins.)

Alternative Implementations for lns

lns has a simple interface with only four member functions:

a) an lns consists of a single pointer to the first element in a singly-linked list of line numbers, and

b) an lns consists of a pair of pointers: one to the first element in a singly-linked list of line numbers, and another to the last element.

The definition for class lns using a single pointer appears in lns1a.h (Listing 4) , and the corresponding member function definitions appear in lns1a.cpp (Listing 5) . Like xrt, lns is a handle class; the handle is a pointer to the first node in the linked list. Unlike xrt, which uses an incomplete global type as its body class, lns uses a private nested type node. (I first discussed nested types in "Nested Classes," CUJ, July 1993.)

A nested class is in the scope of its enclosing class. Therefore, I didn't bother adding a prefix to the name node (as in lns_node), because the fully-qualified name of the node class is lns::node. Furthermore, since lns::node is private, it's inaccessible to client code.

Rather than define lns::node in situ (at the point of its declaration inside class lns), I prefer to use the new C++ feature that allows forward declaration of nested classes. The declaration

class node;
inside class lns declares lns::node as an incomplete type. The subsequent declaration

node *first;
declares first as a pointer to the nested node type. Since that is the only use of node inside the lns class definition, I've delayed defining lns::node until after completing the lns class definition.

As of this writing, I have only one compiler that supports forward declaration of nested classes, Borland 4.0 for DOS and Windows, but I've grown fond of this feature very quickly. I think nested classes are great for namespace and access control, but nested classes defined in situ can really clutter the enclosing class definition. I think forward declarations are much more readable. Granted, there are times when you must complete the nested class inside the enclosing class, but I find they are fairly uncommon. I'll be using this feature whenever I can.

By the way, the default behavior of the Borland compiler is to warn you that you should be using the fully qualified name lns::node inside the definition of lns::node rather than using the unqualified name node. That is, the folks at Borland want you to write the class definition as

class lns::node
   {
public:
   lns::node(unsigned n);
   unsigned number;
   lns::node *next;
   };
I don't see the need for this warning, so I turned it off using the -w-nst compiler switch.

If your compiler does not yet support forward declaration of nested classes, then move the node definition back inside the lns definition. Specifically, delete the forward declaration for node that appears inside class lns. Then move the complete definition for lns::node into lns in place of the deleted declaration. Be sure to delete Ins:: from the heading of the nested class.

lns1a.h in Listing 4 contains two inline member function definitions. I prefer to place inline member function definitions outside their class definitions for the same reason I prefer forward class declarations. It's a little more verbose, but a lot more orderly.

Outside the scope of class lns, you must refer to the lns::node constructor as lns::node::node. The body of the lns constructor is in the scope of class lns, so it can refer to lns::node as just node.

lns::add always adds a new line number at the end of the list. Therefore, this implementation using a single pointer to the head of the list must scan the list every time to find the last element just to tack the new number on the end. As an alternative, lns can maintain a separate pointer to the last element in the list. This eliminates the need to scan the list each time and greatly simplifies the logic of lns::add, at the cost of one additional pointer per cross-reference entry. The header for this implementation is lns1b.h (Listing 6) . The corresponding member function definitions are in lns1b.H (Listing 7) .

Listing 8 shows a makefile that will build the entire cross-reference program. It refers to the lns header and source file as lns.h and lns.cpp, respectively. To build the program using the lns implementation with one pointer, copy lns1a. * to lns.*, and then run make.

To use the other lns implementation, copy lns1b.* to lns.*, and run make. You should see make rebuild the entire program, because all the source files depend on lns.h, which just changed. (Some systems, notably MS-DOS, don't update the time stamp on the file that's the target of a copy. When you run make after copying the lns files, nothing happens because make thinks all the files are up-to-date. If that happens, you should use a utility like touch to update the time stamps on the lns.* files. Then make will know that the files have changed.)

Both versions of the lns class are in what Coplien [1992] calls the canonical form, where the class definition contains private data members that reflect a particular implementation. When you change the implementation, you typically change the header as well as the source file. Changing the header can trigger a massive recompilation.

To avoid recompilation whenever you change the lns implementation, you must design a single lns header that works with both implementations, as well as with any others as yet unwritten. The Cheshire Cat technique helps you do just that.

Cheshire Cat Classes

Carolan [1989] coined the term "Cheshire Cat" to describe his technique for separating the implementation details for a class from its public interface using handle classes and incomplete types. You can transform a class X from its canonical form to its Cheshire Cat form by following these steps:

1. move X's private members to a separate implementation details class outside X's header file

2. declare the implementations details class as an incomplete type in X's header

3. replace X's private members with a single pointer to the implementation details class

4. rewrite X's public members as non-inline functions which operate on and manage an implementation details object.

Listing 9 shows lns2.h containing a new definition for class lns as a Cheshire Cat class. The public members are the same as before (in Listing 4 and Listing 6) , but the private data is now just a single pointer, dp, to an object of incomplete type lns::details. This one header now serves both implementations for class lns.

Listing 10 shows lns2a.cpp, the implementation of lns using a single pointer. The completed definition for nested type lns: :details looks almost identical to the lns class in canonical form that appears in Listing 4. The only difference is the class name, and hence, the names appearing in the declarations for the constructor and destructor (details instead of lns). By the same token, the nested class lns::details::node is identical to class lns::node in Listing 4, except for its name. The fully-qualified name lns: :details::node indicates that node is a nested class within a nested class.

The constructor for lns::details::node is the same as the constructor for lns::node in Listing 4. Similarly, all the member functions for lns::details are the same as the corresponding functions in Listing 4. Again, all I've done is push the functionality of lns in canonical form down into the lns::details class.

At the end of Listing 10 are the new public member function definitions of lns itself. The constructor creates the details object. The destructor destroys it. And each of the other member functions does what it always did, except now it invokes the corresponding member function of the details class to do the real work.

I wrote lns2a.cpp (Listing 10) to make it easier for you to recognize the similarities with lns1a.cpp (Listing 5) . In practise, you need not maintain such a rigorous separation between the handle object (in this case, of type lns) and the body object (of type details). After all, what's the point of hiding details' data members from lns; they're all part of the same implementation. You can safely make the data members of lns::details public because details itself is private to lns. I don't think this compromises the design at all.

For example, if the lns::details data member's are public, you can rewrite the lns constructor as

lns::lns(unsigned n)
   {
   dp = new details;
   dp->first = new node(n);
   }
and simply eliminate the lns::details constructor altogether.

Listing 11 shows lns2b.cpp, the implementation of class lns using two pointers. In this implementation, the lns::details data members are public. lns::details has no member functions, and all the work they would have done is in the lns member functions. If you compare this Cheshire Cat class with its canonical form (Listing 6 and Listing 7) , you should still recognize the common functionality.

I'll continue my look at compilation firewalls next month.

References

Booch [1991]. Grady Booch, Software Development '91 Conference Keynote Address "Object-Oriented Technology: An Engineering Perspective."

Carolan [1989]. John Carolan, "Constructing Bullet-Proof Classes," C++ at Work '89 Proceedings. SIGS Publications.

Coplien [1992]. James O. Coplien, Advanced C++ Programming Styles and Idioms. Addison-Wesley.