If you had to struggle a bit on your first pass through Alexandrescu’s Modern C++ Design, let this gem serve as a gentler introduction to policy-based design in C++.
Introduction
Within the overall plan of my column, “STL & Generic Programming,” I am still in the process of making a first pass through the STL. After that, I will be talking about generic programming techniques in general. In my last column, however, I digressed and talked about something that is not specific to the STL, namely, traits classes. Digressions are a dangerous thing. You can get lost in them. As a matter of fact, I have decided that there is another topic so closely related to traits classes and so important that I must talk about it now, before returning to my discussion of the STL. The topic is policy classes and policy-driven design. Before I tell you about policy classes and why I feel compelled to discuss them, let me say that the definitive source on the subject is Andrei Alexandrescu’s book Modern C++ Design [1]. I cannot recommend this book strongly enough to anybody with an interest in cutting-edge C++ programming. Reading it makes you wonder if perhaps it can cause cancer in laboratory rats. It’s that good. You will also encounter the idea of policy-driven design in some of the stuff at <http://boost.org>, a site that you should check out frequently if you use the STL.
In my last column (CUJ, December 2001), I used a prototype factory class as an example to illustrate traits classes. When I read my column again after it had gone to print, all of a sudden I felt that this was a poorly chosen example. It looked to me as if policy classes would have been a much better way to make the prototype factory customizable for different purposes. Dazed and confused, I picked up Andrei Alexandrescu’s book and re-read Chapter 1, “Policy Based Class Design.” There, I found the following enlightening sentence: “Policies have much in common with traits [...] but differ in that they put less emphasis on type and more emphasis on behavior” [2]. Looking at my example again, I now understood that traits and policies are closely related techniques, and that there is in fact an overlap of problem domains where either one of the two is applicable. My doubts about the use of traits with the prototype factory example stemmed from the fact that this example does reside in that gray zone, where both traits and policies can be used.
Therefore, in this column I will first remind you of my last column’s prototype factory example and how it used traits classes. After that, I will rework the example completely using policy classes, and voila, I have not only shown you traits and policies, but we also have a single example that illustrates the relationship and the tradeoffs between the two.
The Prototype Factory Example Revisited
Listing 1 shows the bare essence of the prototype factory class template that was the main example in my December 2001 column. The factory stores pointers to objects of type Proto, indexed by identifies of type Id. Such a prototype factory would, for example, be useful in a CAD program, where it would hold prototypes of the different parts that go into a drawing. Creating the first instance of a particular part is typically costly, involving a trip to a database or a website. Subsequent instances can be obtained much more easily as clones of the first instance. Therefore, it is a good idea to store the first instance of each part in a prototype factory and get all subsequent instances from there. The prototype factory pattern is described in more detail in Chapter 3 of the Gang-of-Four book [3].
The starting point for my discussion of traits classes was the observation that the class ProtoTypeFactory, although templatized with the type of the prototypes and the type of the index, is not very generic. For example, we might want to store prototypes of some type Widget, but the Widget method that needs to be called to create the clone happens to be called DeepCopy rather than Clone. Then the line:
return protoTypeCollection[id]->Clone();in ProtoTypeFactory’s GetClone method must be changed to:
return protoTypeCollection[id]->DeepCopy();In order to achieve this change generically, without having to change the factory’s source code, we routed the call to the prototype’s cloning operation through a traits class. To this end, we implemented the factory’s GetClone method as:
return prototype_traits<Proto>::Clone( protoTypeCollection[id]);The default implementation of the class template prototype_traits looked as follows:
template<typename Proto> class prototype_traits { public: static Proto* Clone(Proto* p) { return p->Clone(); } };So far, the whole caboodle behaved exactly like Listing 1’s prototype factory, except for an extra level of indirection when calling the prototype’s Clone method. But we could now easily solve the Widget problem. To this end, we provided an explicit template specialization of the prototype_traits class template for widgets, like this:
template<> class prototype_traits<Widget> { public: static Widget* Clone(Widget* p) { return p->DeepCopy(); } }Now if we instantiated a widget prototype factory, like this:
ProtoTypeFactory<Widget, int> widgetFactory;then the call:
Widget* clone = widgetFactory.GetClone(42);would retrieve the prototype with index 42 and then return the result of calling DeepCopy on this prototype.
Once we had this traits mechanism in place, we used it to make the prototype factory even more generic. For example, instead of hard coding the map of Ids to prototypes as:
std::map<Id, Proto*> protoTypeCollection;we wrote:
std::map<Id, prototype_traits<Proto>::stored_type> protoTypeCollection;The default implementation of the prototype_traits class template had the typedef:
typedef Proto* stored_type;which took us right back to the original:
std::map<Id, Proto*> protoTypeCollection;However, explicit specializations of prototype_traits are now free to store something other than a plain pointer to the prototype object (e.g., some sort of smart pointer). Listing 2 shows the end result of pursuing this idea. What we’ve done here can be loosely described as follows: wherever there is something in ProtoTypeFactory’s implementation that could be done in more than one way, we do not make a decision and hard-code one possibility. Instead, we say to the prototype factory, “Go ask the traits of your template argument Proto. They’ll tell you what to do.”
So why was I uncomfortable with all this when I read it again after it had gone to print? One could argue that the decision whether to store plain pointers or smart pointers or what have you is not really a property of the type Proto. One could conceivably use two different prototype factories for the same type of prototype: one that stores plain pointers, and another that stores something else. Similarly, one factory for a particular type of prototype may use the prototype’s DeepCopy method for cloning, while another factory for the same type may prefer to obtain its clones as shallow copies. From this point of view, all the decisions that we have previously deferred to the traits class must really be made by the factory class itself. It is thus not a good idea to specify a particular policy for each type of prototype. Instead, we want to set things up so that the client programmer can, upon instantiation of a prototype factory object, flip a few switches to give this particular factory object certain behavioral characteristics. This is exactly what policy classes and policy-driven design are all about.
A Prototype Factory with Policies
Let us go back to the original, non-customizable prototype factory of Listing 1 and give it a “policy template” so that the client programmer can specify, upon instantiation of a factory object, what function should be called on the prototype object to obtain the clone. Listing 3 shows how this is done. The ProtoTypeFactory class template takes an additional template argument CloningPolicy. Looking at ProtoTypeFactory’s GetClone method and the class template CloneFromPointer, which is the default value for CloningPolicy, it is easy to see how it all works. GetClone simply defers the decision of how to obtain the clone to a static member function of the cloning policy. The default policy CloneFromPointer gives us exactly what we had before in the simple factory of Listing 1. However, we can now create a prototype factory that calls DeepCopy to obtain the clone by specifying a new policy, like this:
template<typename Proto> class DeepCopyFromPointer { public: typedef Proto* cloning_result_type; static cloning_result_type Clone(Proto* p) { return p->DeepCopy(); } }; ProtoTypeFactory< Widget, int, DeepCopyFromPointer<Widget> > deep_widget_factory;If the same class Widget also has a method ShallowCopy, then we can have another widget prototype factory that hands out shallow clones:
template<typename Proto> class ShallowCopyFromPointer { public: typedef Proto* cloning_result_type; static cloning_result_type Clone(Proto* p) { return p->ShallowCopy(); } }; ProtoTypeFactory< Widget, int, ShallowCopyFromPointer<Widget> > shallow_widget_factory;Notice how the cloning policy also specifies the result type of the factory’s GetClone method. The clone can thus be returned by value, by reference, as a plain pointer, or as some smart pointer, as desired.
That’s pretty much it: policy-driven design in a nutshell. Using the same loose language as before with traits, what we’ve done here can be described as follows: wherever there is something in ProtoTypeFactory’s implementation that could be done in more than one way, we do not make a decision and hard-code one possibility. Instead, we say to the prototype factory, “Don’t worry about it now. When you’re instantiated, you’ll be given a policy (via a template argument) that will tell you what to do.”
The beauty and the power of policy-driven design become apparent when we start to combine and layer different policies. Due to the magic of combinatorics, it is then possible to obtain an enormous amount of functionality from very little source code. The prototype factory example can be used to illustrate this to some extent. But before I do this, I want to pause briefly to mention a C++ language feature that I should be using here, but can’t because it is not supported by Microsoft’s Visual C++ compiler, which many if not most of us use in our daily work.
Template Template Parameters
Let us look at a very simple example of a class template:
template<typename T> class X { // Some stuff ... private: T m_templMember; };This class template has a member of type T, the template parameter. Upon instantiation, the client programmer can specify any type for the template parameter. It can be a built-in type, as in:
X<int> someVariable;or it can be a class type, as in:
class SomeClass { ... } ; X<SomeClass> anotherVariable;It can even be an instantiation of a class template, like this:
template<typname S> class SomeClassTemplate { ... }; X<SomeClassTemplate<int> > yetAnotherVariable;By the time the template parameter S of SomeClassTemplate has been specified to int, SomeClassTemplate<int> is just another class type. The fact that it came into existence as an instantiation of a class template is now irrelevant. It can therefore be used as a value for X’s template parameter T just like any other class type. However, C++ allows us to go one step further and use, as values for template parameters, class templates whose template parameters have not yet been specified. Here’s an example:
template<template<typename S> T> class A { // Some stuff ... private: T<int> m_aTOfInt; T<double> m_aTOfDouble; }The line:
template<template<typename S> T>in the code above says that A is going to be a class template with one template argument. Furthermore, any value used for this template argument must itself be a class template with one template argument. Inside the definition of A, the class template T is used twice, once with its template argument S specified to int, and then again with S specified to double. Client code that uses A could, for example, look like this:
template<typename S> class SomeClassTemplate { ... }; A<SomeClassTemplate> someVariable;So far so good, but how is this relevant to policy-driven design? Take another look at our instantiation of a prototype factory using the shallow copy cloning policy:
ProtoTypeFactory< Widget, int, DeepCopyFromPointer<Widget> > deep_widget_factory;The first template parameter of the factory class template is specified to be Widget. The cloning policy class (DeepCopyFromPointer in this case) also has a template parameter, and that parameter must be specified to the same class Widget. This is a redundancy that is plain ugly. Furthermore, the poor client programmer who inadvertently mixes types, as in:
ProtoTypeFactory< Widget, int, DeepCopyFromPointer<Gadget> // Oohps... > deep_widget_factory;ends up in template-error-message hell, and it would certainly be nice to prevent that from ever happening. This can indeed be achieved using template template parameters, as shown in Listing 4. The template parameter CloningPolicy is now specified to be a class template that takes one template argument. Therefore, a typical instantiation now looks like this:
ProtoTypeFactory< Widget, int, DeepCopyFromPointer > deep_widget_factory;The client programmer does not have to redundantly specify Widget as the cloning policy’s template argument anymore. It suffices to just provide a class template such as DeepCopyFromPointer. Inside ProtoTypeFactory’s class definition, the value of the cloning policy’s template argument is hard-wired to always be the same as the value of Proto: no more redundancy, no more error-proneness.
Notice how in Listing 4, the template template parameter CloningPolicy is declared as:
template<typename> CloningPolicy = CloneFromPointerThis demonstrates that C++ allows you to skip naming the inner template parameters. All the compiler needs to know is how many of them there will be.
If you try to use template template parameters with Microsoft’s VC++ v6 compiler, you get two error messages: “template definitions cannot nest” and “template declarations are only permitted at global or namespace scope.” The purpose of this little excursion was to make it clear that these statements are somewhat misleading, to put it mildly. The correct error message would be, “template template parameters not supported.”
Combining Policies
As I said before, the real power and beauty of policy-driven design comes to light when a class allows the client programmer to specify policies for different aspects of its behavior. Because of the sheer combinatorial number of possibilities, a relatively small number of policy implementations for each aspect will magically produce a large number of classes with different behavior. Listing 5 shows the prototype factory of Listing 4 with many more aspects of its behavior delegated to policy classes. There are two policy template parameters, ProtoTypingPolicy and ThreadingPolicy.
ProtoTypingPolicy handles all aspects of storing, cloning, and destroying the prototype objects. It should not be necessary to discuss the code in detail; it is rather obvious how ProtoTypeFactory delegates the relevant behavior to the policy class. Listing 6 shows the default policy, which makes the factory store owned pointers to prototypes. Listing 7 shows an alternate policy, where the factory stores copies of prototypes and hands out copy-constructed clones.
One could of course, in the interest of better reusability, choose a finer granularity and have separate policy template arguments for storing, cloning, and destroying prototypes. On the other hand, having many very specialized policy arguments complicates things for the author of the class, as well as the client programmer, because it becomes harder to understand and handle the interdependencies between the different aspects of behavior. This is one of those situations where it is ultimately a matter of discretion how one weighs the tradeoffs.
The second policy argument of our ProtoTypeFactory is the threading policy. It is quite likely that such a factory will be used in a multithreaded environment, where registering a new prototype and cloning an existing one can occur concurrently. In this case, access to the collection of prototypes must be synchronized appropriately. Delegating this synchronization to a policy brings two advantages: first, it allows us to implement synchronization as a no-op when it is known that the object will be used in a single-threaded environment, thus saving us the overhead of acquiring and releasing locks. Secondly, we can write synchronization policies for different environments and operating systems, thus greatly increasing reusability.
All the synchronization stuff is in the RegisterProtoType and Clone methods of Listing 5. Looking at RegisterProtoType and comparing it to the versions of Listings 1, 2, and 3, you’ll find that for simplicity, we now strictly disallow re-registering a prototype with the same ID. To allow re-registering is of course a reasonable demand. It is an interesting exercise to make this possible via a policy and handle thread-safety correctly and efficiently. In our case, in the absence of re-registering, all we have to do is serialize access to the collection of prototypes with a lock. We do this in the standard way, by constructing a dummy object whose lifetime is the scope of the operation that is to be synchronized. For the default threading policy PFSingleThreaded as shown in Listing 6, construction and destruction of this dummy object is a no-op, which is practically guaranteed to be optimized away by the compiler. For multithreaded policies, construction of the object must acquire a lock, and destruction must release it. Listing 8 shows an example that works under Win32.
The interesting point here is that we want to synchronize on the object level (i.e., we must have one lock per factory object). On the other hand, the lock conceptually resides in the policy class; otherwise, there would be no customizability. This dilemma can be resolved by making the lock a member of the threading policy class and letting the factory class inherit from its own template argument ThreadingPolicy. That way, the lock ends up being a data member of the factory object, as desired. This little gimmick of inheriting from one’s own template argument is known among C++ buffs as the CRTP (Curiously Recurring Template Pattern), a term that was coined by James Coplien [4]. As an alternative, the factory class could aggregate an object of type ThreadingPolicy.
Conclusion
Policy-driven design is a great way to enhance reusability by delegating certain aspects of the behavior of a class to external policy classes. Since policies can often be used in different combinations, a relatively small amount of source code leads to a large number of classes with different behavior.
References
[1] Andrei Alexandrescu. Modern C++ Design (Addison-Wesley, 2001).
[3] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns (Addison-Wesley, 1994).
[4] James Coplien. “The column without a name: A curiously recurring template pattern,” C++ Report, February 1995.
Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, NV. He can be reached at thomas@styleadvisor.com.