Columns

Stepping Up To C++

Compilation Firewalls, Part 2

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-4906, by phone at (513)324-3601, or electronically at dsaks@wittenberg.edu.

C++ programmers commonly package classes as a pair of files: a header (.h) file and a source (.cpp) file. A header contains the class definition, which in turn contains the declarations for all the class members, private and protected as well as public. A header may also contain inline member function definitions. The correspending source file contains the definitions for any members not defined in the header, typically the non-inline member functions and static data members. Compiling that source file creates the class object file.

Client source files (source files that use a class) #include the class header to gain access to the public class members during compilation. The resulting client object files link with the class object file to form an executable program.

For the most part, this packaging scheme works pretty well. Its main drawback seems to be that it doesn't completely insulate users of a class from changes to the class implementation. Typically, changes in the class implementation require changes in the declarations of one or more non-public members. Since those declarations are in the class header, class users must recompile every source file that directly or indirectly includes the revised header, even if they haven't changed any of those sources.

This is the second part in a series describing programming conventions you can use to physically separate a class interface from its implementation. By following these conventions, you can build a "compilation firewall" between the class header and the corresponding class source, so that changes in the class implementation don't require recompilation of client sources.

The two most common techniques for building compilation firewalls use "Cheshire Cat" classes and protocol classes. I presented Cheshire Cat classes last month. Along the way, I introduced forward-declared nested classes, a recent extension to C++. This month I'll explain protocol classes and consider the performance costs of these techniques.

As before, I'll demonstrate the techniques by applying them to the line number sequences in xr, a cross-reference generator application program. xr writes to standard output an alphabetized list of words read from standard input. Their program prints each word on a separate line followed by the sequence of line numbers on which that word appears in the input.

The main source file for xr appears in Listing 1. It scans the input and counts input line numbers, and delegates all other work for maintaining the crossreference table to an object of type xrt (the cross-reference table class). The header for xrt appears in Listing 2, and its corresponding source file appears in Listing 3.

Class xrt maintains the cross-reference as a binary tree of treenodes. Each treenode associates the spelling of a word with a sequence of line numbers. treenode actually uses a pointer, called word, to a dynamically allocated null-terminated character string that holds the spelling. treenode also uses an object, lines, of type Ins (the line number sequence class) to hold the set of line numbers associated with that word. Class lns is the one we're really interested in.

Class lns has many possible implementations. I've been working with two: a "small" version that uses a single pointer to the head of a singly linked list of nodes, and a "fast" version that uses a pair of pointers to the head and tail of the list. The small version uses less memory for each lns object, but it's relatively slow because it searches the entire list to find the last node every time it adds a line number. The fast version avoids that search by using a second pointer pointing directly to the tail of the list.

Listing 4 is the header for the small version of lns, and Listing 5 is the corresponding source file. Listing 6 and Listing 7 are the header and source, respectively, for the fast version. (Last month I referred to the small and fast versions as versions a and b, respectively. Small and fast are a bit more descriptive.)

Both lns implementations are in uninsulated form. That is, their class definitions include private members so that changes in the implementation may force recompilation of client source files. (Last time I used the term canonical instead of uninsulated, and attributed this use of canonical to Coplien [1992]. However, I've since reread parts of Coplien's book, and I'm not sure I used the term as he intended. Uninsulated is more descriptive anyway.)

The two versions of Ins have exactly the same public interface, but different underlying implementations. Building a firewall means writing the class header so that it contains only the public interface by moving all the implementation details to the class source file. The Cheshire Cat technique approximates this ideal by reducing the private data to a single pointer to an implementation object with incomplete type. The protocol class technique uses an abstract base class instead of an incomplete type.

lns as an Abstract Base Class

Listing 8 shows a header that defines lns as an abstract base class (ABC). An ABC is a class with at least one pure virtual function. A pure virtual function is a virtual function with a pure virtual specifier ( = 0 ) at the end of its declaration. (I introduced pure virtual functions and ABCs in "Stepping Up to C++: How Virtual Functions Work," CUJ, January, 1994.)

A virtual function declared in a base class specifies an abstract operation that may have a different implementation in a class derived from that base. An ordinary ("impure") virtual function has a definition (a function body) that accompanies the declaration, so that derived classes inherit a default implementation for that function. A derived class can override that default as appropriate.

A pure virtual function specifies an abstract operation without a default implementation. You cannot create objects of an ABC. However, you can declare pointers and references to an ABC that will refer at run time to objects of types derived from the ABC. (Such pointers and references refer to objects whose static type is an ABC, but whose dynamic type is some class derived from that ABC.) Thus, an ABC specifies a common interface for a variety of derived types, rather than the exact type of any real-live objects.

A class derived from an ABC can override any inherited pure virtual function with an "impure" virtual function declaration and corresponding function definition. Derived classes inherit pure virtual functions as pure virtual functions. Thus, if a derived class does not override every inherited pure virtual function with an impure virtual function, then that derived class is also an ABC. On the other hand, a derived class that overrides all its inherited pure virtual functions becomes a "concrete" class, so that you can create objects of that type.

Class lns in Listing 8 is an ABC that consists entirely of public members that are pure virtual functions. It specifies an inheritable interface with absolutely no implementation details. That interface is the same as the public interface in both the small and fast lns classes (Listing 4 and Listing 6) , except that ABC lns doesn't have a constructor. ABC lns has no base classes nor data members, so there's nothing for the constructor to initialize. Each concrete class derived from Ins will have its own constructor.

Why didn't I declare a pure virtual constructor in Ins? Because constructors cannot be virtual, and for good reason. A virtual function lets a client ask an object known only by its static type to perform a particular abstract operation in whatever way is appropriate for that object's dynamic type. How then does a client ask an object that doesn't yet exist to initialize itself in a way that's appropriate for whatever dynamic type it will have after it initializes itself? No way.

Destructors can be pure virtual. The Ins destructor in Listing 8 is pure virtual. But, unlike other pure virtual functions, you must provide a definition for the destructor, however trivial. Why do you need this definition? Even though you can't create objects of type lns, you can derive concrete classes from lns and create objects of those types. The destructor for a derived class automatically invokes the destructors for its base classes and members, even for a base that's an ABC.

Although ABC lns has no data members, in general an ABC can have data members. These data members provide a common partial implementation for all classes derived from the ABC. The destructor for such a derived class automatically calls the ABC's destructor to destroy resources used by inherited data members. The derived class destructor insists on calling the ABC's destructor even if the ABC's destructor is completely empty. If you don't supply a definition for the lns destructor, the linker complains when it can't find a definition.

ABCs as Protocols

ABC lns defines a protocol that all derived classes must observe. The Ins header (Ins.h) contains only this class definition and no implementation details. Thus the header completely insulates client sources, such as xr.cpp and xrt.cpp in Listing 1 and Listing 3, from changes in the Ins implementation.

You can create a concrete lns object by deriving it from the Ins protocol, adding the appropriate data members, and overriding all the inherited pure virtual functions to provide the desired behavior. Placing the derived class in the source file (Ins.cpp) keeps the implementation details out of the header.

Listing 9 shows a class definition for lns_fast, a concrete "fast" lns class derived from ABC lns. Notice that this ns_fast is nearly identical to the "fast" lns class in Listing 6: both have a constructor as well as private data. But all the member functions in Listing 9 are virtual because they override inherited virtual functions. The bodies for the lns_fast member functions (omitted from Listing 9 for brevity) are identical to the corresponding function bodies in Listing 7.

This scheme for building a compilation firewall seems simple enough. It appears that all you need do is define an ABC that specifies a protocol (abstract behavior) for all implementations, and then derive one or more concrete implementation classes from the ABC. However, it's just a little too simple, and fails to insulate clients from changes to the implementation. Here's why.

Somewhere in the client source code (in this case, xrt.cpp in Listing 3) , there must be declarations or statements that create concrete lns objects. For example, class treenode in Listing 3 has a member, lines, of type lns:

class treenode
   {
   ...
   lns lines;
   ...
   };
initialized by a member initializer in the treenode constructor:

treenode::
treenode(const char *w, unsigned n)
   : lines(n)
   {
   ...
   }
Thus, creating a treenode object creates an lns as a member object.

Unfortunately, when you change lns to an ABC, xrt.cpp can no longer create concrete objects of type lns, only pointers or references to lns objects. Therefore, you must change the lines member to a pointer, as in

class treenode
   {
   ...
   lns *lines;
   ...
   };
and rewrite the constructor to dynamically allocate a concrete lns object. But even that dynamic allocation is a problem.

Rewriting the member initializer as

: lines(new lns(n))
is still an error because you can't create objects of an ABC by using a new expression either. You can create objects of concrete types derived from lns, such as lns_fast. However, if you change the initializer to

: lines(new lns_fast(n))
you must move the class definition for lns_fast into lns.h, which breaks through the insulation provided by the header.

An alternative to defining the derived class in the header is to add a static member function to the ABC called create as shown in Listing 10. The create function is a pseudo-constructor that dynamically allocates an object of a concrete type derived from the ABC. The corresponding definition for lns::create looks something like:

lns *lns::create(n)
   {
   return new lns_fast(n);
   }
If you place this definition in lns.cpp, you need not move the definition for lns_fast into lns.h. Then you can rewrite the member initializer in the treenode constructor as

: lines(lns::create(n))
This create function effectively restores the compilation firewall.

Restoring Concrete Behavior

Defining lns as an ABC has a serious drawback: clients can't manipulate lns objects as concrete objects. They must deal with lns objects only through pointers and references to dynamically-allocated lns objects.

You can restore the concrete appearance of class Ins using a handle class similar to that used in the Cheshire Cat technique. The key insight comes from recognizing that the ABC lns should be a protocol for lns implementation objects, not for lns objects themselves. Thus, Ins becomes a handle (a concrete class implemented as a single pointer) for an implementation object of a class derived from a protocol class, as shown in Listing 11. As in the Cheshire Cat technique, each member function in the handle class delegates the bulk of its work to the corresponding member function of implementation object.

You transform a class from its concrete, uninsulated form (lns as in either Listing 4 or Listing 6) to its protocol-based insulated form (Listing 11) by following these steps:

1. Add a public member protocol as a forward-declared nested class.

2. Delete the private members and replace them with a single pointer to a protocol object.

3. Define the nested protocol class as an ABC with:

If your compiler does not support forward-declared nested classes, change Listing 11 as follows:

1. Delete the nested-declaration for protocol inside class lns.

2. Change all occurrences of either lns::protocol or just protocol to Ins_protocol.

3. Move the definition for class lns_protocol above the definition for class lns.

The protocol pointer pp points to an implementation object, much like the details pointer dp in a Cheshire Cat class. In a Cheshire Cat class, the pointer points to a details object of incomplete type. In a protocol-based class, the pointer points to an object of some concrete type derived from an ABC. Thus, the member function definitions for a concrete protocol-based class are nearly identical to their Cheshire Cat counterparts, with one key difference: you can define the protocol-based class members (except the constructor) as inline functions in the header, as in Listing 11.

Listing 12 shows an implementation for the Ins class defined in Listing 11. lns_fast derives from lns::protocol and implements the "fast" line number sequence (using two pointers as in Listing 6 and Listing 7) .

The lns constructor appears at the end of Listing 12. It cannot be defined inline because it creates the implementation object of type lns_fast. In order to preserve the compilation firewall, lns_fast must not appear outside this source file.

Different Implementations Simultaneously

As we've seen, protocol-based classes bear many similarities to Cheshire Cat classes, but they have one powerful advantage. Protocol-based classes can support different implementations for the same class at the same time in a single program.

For example, you can implement both the "fast" and "small" lns classes, and expand the lns interface to let users select, at run time, either implementation. In fact, users can create both fast and small lns objects in the same program.

A simple way to let users select the implementation is to add an argument to the constructor. That is, declare the lns constructor (in the header) as

lns(unsigned n, style s = SMALL);
where style is an enumeration defined as

enum style { FAST, SMALL };
The style parameter in the constructor has a default argument value, so a user who doesn't care gets the small implementation by default. A user who wants the fast implementation simply asks for it by name, as in

treenode::
treenode(const char *w, unsigned n)
   : lines(n, FAST)
   {
   ...
   }
The corresponding definition for the constructor looks like:

lns::lns(unsigned n, style s)
   {
   if (s == SMALL)
      pp = new lns_small(n);
   else // if (s == FAST)
      pp = new lns_fast(n);
   }
You can even use protocol-based classes to build objects that monitor themselves and automatically switch to the most efficient implementation. For example, when an lns contains only a few elements, searching the list takes little time, so you might as well save memory and use the small implementation. But for longer lists, you probably prefer using the fast implementation.

Most of the work in implementing this self-adjusting lns (Listing 13) is in changes to the add function. The lns constructor always initializes lns objects as lns_small objects. The add function simply computes the length of the list each time it searches the list. If the length ever grows beyond a certain threshold, add creates a new lns_fast object that holds the list, and deletes the lns_small object.

The header for this self-adjusting lns is the same as the header in Listing 11, except that:

1. the protocol::add returns a pointer to a protocol object instead of void, as in

   virtual protocol
       *add(unsigned n) = 0;
2. the definition for lns::add is moved to the source file (it cannot be an inline).

protocol::add returns a pointer to the protocol object. lns::add applies protocol's virtual add function to its protocol object, and compares the returned pointer with the previous protocol pointer. If the values ever differ, it means the protocol object mutated. In that case, lns::add discards the old protocol objects, and saves the new one.

lns_small objects can change into lns_fast objects, but not vice versa. Therefore, the lns_small::add does all the work to monitor the length of the list and decide when to mutate. The mutation does not create an entirely new copy of the linked list. Rather, it creates a new lns_fast object that shares the same list. Then it disconnects the lns_small object (by storing null in the pointer to the first element in the linked list).

So What Does This Cost?

Both Cheshire Cat and protocol-based classes add considerable flexibility to class designs. Of course, this flexibility comes with a small price. Compared to an uninsulated implementation, a Cheshire Cat class:

A protocol-based class is even a little more expensive. In addition to the cost for a Cheshire Cat class, a protocol-based class:

Neither Cheshire Cat classes nor protocol-based classes can do much inlining.

These techniques are typically inappropriate for small classes. But for larger classes with many possible implementations, the productivity gains from greater abstraction typically outweigh the performance costs.

References

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