Template Base Delegation Ted Law tedlaw@vnet.ibm.com IBM Software Solutions Toronto Laboratory 844 Don Mills Road North York, Ontario M3C 1V7 Canada ABSTRACT When a class derives from a template instantiation, the base class is called a template base class. Non-template base classes are more commonly used, but do not take into account the specific needs of the derived class. The base class can provide better service; it can be customized by becoming a template instantiation using the derived class and/or other classes as arguments. In this way, the template base class can tailor-make itself for the derived class, taking advantage of the knowledge of its type. For example, the template base class can type its methods appropriately for the derived class. Furthermore, inheriting publicly from a template base class makes it possible for the derived class to delegate part of its public type-specific interface to the base. This paper explores the advantages of template base delegation. Introduction In C++ object-oriented programming, objects frequently delegate responsibilities to other objects to enhance modularity, reuse, and extendability\cite{RESPONSIBILITY-DRIVEN-APPROACH}. Responsibilities can also be abstracted into the base class to increase sharing among derived classes. Usually the type of the base class is fixed. Consequently, the signature of the methods and the types of the data members of the base class must be fixed. By turning the base class into a template instantiation, it can be customized according to the type of the derived class. To illustrate, Fig.~\ref{FIG-CLASS}(a) shows two classes D1 and D2 inheriting from a common non-template base class B. Fig.~\ref{FIG-CLASS}(b) shows the technique of template base delegation, where D1 and D2 inherit from template base classes B_ and B_, respectively. This is a powerful technique that can be usefully applied to a variety of domain areas. Section~\ref{SECTION-FAN-TEMPLATE-BASES} demonstrates how template base delegation can be used to provide an alternative to the container class implementation of lists. This simple example is intended for illustrative purposes. Section~\ref{SECTION-OBJECT-MODELING} builds on this example, explaining how the technique can be usefully applied to the area of object-modeling. A Simple Example of Template Base Delegation Many introductory text books on C++ use List as an example for source code reuse. List is called a container class template. A limitation of embedding a type T object in ListItem is that the type T object can belong to at most one List. This limitation can be readily overcome by using List instead of List. See Fig.~\ref{FIG:LIST}. The number of Lists that can contain the same T object can now vary dynamically. There is no predefined limit on the number of Lists to which a T object can belong. The cost of this feature is the allocation cost of ListItem and the extra level of indirection to get to the T object. This cost is more expensive than we need because the number of lists that an object needs to be on is usually fixed at compile time. Consider the ER diagram\footnote{ Entity-Relationship Modeling is a popular semantic data modeling technique in the database area. } in Fig~\ref{ER_diagram}, which shows the relationships in a Company-Employee example. Assuming the two relationships are implemented using simple linked lists, Fig.~\ref{FIG:MULTILIST} represents one possible runtime instance of some information. In each Employee object there are two next pointers: one for chaining all the employees of the same company; the other for chaining all the employees under the supervision of the same manager, who himself is also an employee. Since this application has two almost identical linked lists, there is an opportunity for source code sharing that can be realized by wrapping each next pointer in a base class. However, to distinguish between the two different next pointers, we can turn the base into a template called FanTip\footnote{ The shape of a hand fan is used to name these templates. In the example, a FanHead is the head of a simple linked list, and a FanTip is an item on the list. }\footnote{ The naming convention used here: \begin{enumerate} \item[a.] Data members are always postfixed by an underscore. \item[b.] An underscore at the end of a class name indicates that the class is meant only to be used as a base of another class. It is not stand-alone. \item[c.] For function parameters, references are used for objects that must exist, and pointers are used if they may exist. \end{enumerate}} and parameterize it by the kind of the relationship that is being represented. Similarly, the head pointers at the beginning of the lists are wrapped into a template called FanHead. Together they are called the Fan base class templates. For readers interested in more detail, the source code for this example is given in the Appendix. Both FanHead and FanTip take three arguments: the type of the 1 side, the type of the N side, and the type of the 1-N relationship. The template class definitions are written so that the class definitions of the template arguments are not needed. In fact, the definitions of CompanyEmploysEmployees\footnote{ The convention is that the name of a relationship has the encoding, Noun1VerbNoun2, for example CompanyEmploysEmployees. The ``direction'' of the relationship is always from Noun1 to Noun2. Noun1 is always on the outgoing side, and Noun2, incoming. } and ManagerManagesEmployees do not need to exist unless they are required for other reasons (for example, to carry an attribute of the relationship). Since FanHead and FanTip know the type of the derived class, their interfaces can be typed accordingly. For example, FanHead defines an add_tip() method, which takes a parameter of type Tip& (the second template argument). The client class Company customizes its base by inheriting from FanHead. Thus, the inherited add_tip() method will expect an Employee& as a parameter. In addition to the advantages of source code sharing and strong typing discussed above, using the Fan template bases also makes the definitions of the derived classes more declarative. The template bases declare what relationships the derived class can engage in using the inheritance clause of a C++ class declaration: class Employee : protected FanTip_, protected FanTip_ { ... }; Typically, the binary code for every instantiation of a template is generated. To avoid generating an undue amount of binary code, we can make FanHead inherit from a non-template base class FanHeadBase, and FanTip from FanTipBase. There is no need for these non-template bases to realize the aforementioned advantages (source code sharing, strong typing, and declarative programming). However, factoring most of the code out of the template classes and into their non-template bases means that only one copy of the binary code needs be generated. After the bulk of the code is moved into these non-template bases, only pointer adjustment code, resulting from up/down casting, is left in the templates. When all the template code is inlined, the same efficiency can be obtained as any C equivalent. Thus storage and runtime efficiency can be added to the list of advantages of applying the technique of template base delegation to the problem of implementing linked lists. If we compare the Fan templates with the conventional List container template, we will see that List makes no assumption about its client class specified as a template argument, while FanHead and FanTip always assume they are inherited by their respective client classes. Using this assumption, FanHead and FanTip can embed data members in their client classes, without an extra level of indirection. In summary, template base delegation allows a base class to be customized according to the derived class. That customization can be on the signatures of the methods or on the types of the data members. It gives the base class a chance to know exactly who is inheriting from it. Using template bases is also more declarative, directing the reader of the source code to the actual intentions of the programmer. The example shown in this section is a simple application of the technique. The author has found this technique to be quite useful in the area of object-modeling, which is explained next. A Real Life Example in Object Modeling In many C++ database-like applications, there is a C++ class, called an entity class, used to represent each type of entities in the real world. And there is a C++ class, called a relationship class, used to represent each type of relationships in the real world. Furthermore, the application code needs to inquire into the possible relationships among these types of entities and their attributes at run time. This information is often called the (conceptual) schema of the application. To make the schema information available, we represent the schema at run time using a network of objects called descriptors. We use a unique entity descriptor object to represent each entity class, and a unique relationship descriptor object for each relationship class. A challenging problem is to ensure the consistency between the schema information as manifested in the source code and the explicit representation of that schema at run time. Manually maintaining a schema generation routine or table according to the schema used in the source code is error prone. It is easy to change one but forget to update the other. Consider the inheritance hierarchy shown in Fig.~\ref{FIG-OBJECT-MODELING-INHERITANCE} for the same conceptual schema as was used in the previous example (Fig.~\ref{ER_diagram}). The fact that Company and Employee engage in a 1-N CompanyEmploysEmployees relationship is captured by Company inheriting from the base class Has1NOutgoingRelationship, and Employee inheriting from the base class Has1NIncomingRelationship. The fact that Manager is a subtype of Employee is captured by Manager inheriting from SubtypeEntity_. The template SubtypeEntity_ is written so that it derives publicly from its second template argument. This is a new kind of customization that allows the client to specify to the template base whom to inherit from, so that the intended subtype hierarchy in the application is preserved. Every inheritance shown in Fig.~\ref{FIG-OBJECT-MODELING-INHERITANCE} is public. One way to look at it is that an entity class together with its public template bases form an ``expanded'' public interface for that semantic entity. This is shown by the dotted rectangles in the figure. In a way, the entity class has delegated part of its public interface to its template bases. Alternatively, each template base can be viewed as representing a particular role that the semantic entity can play. Note that, in the conceptual schema shown in Fig~\ref{ER_diagram}, there are three kinds of semantic entities, Company, Employee and Manager, where Manager inherits (conceptually) from Employee; and there are two kinds of relationships, CompanyEmploysEmployees and ManagerManagesEmployees. These facts are captured by the template bases. Other helper classes can be added to the hierarchy as required without affecting this schema representation. Building the Schema Representation Since template bases have been used to ``declare'' the various pieces of the schema, this information can be used to automatically construct the schema's runtime representation. There is a static ``init'' object defined for each instantiation of RootEntity_, SubtypeEntity_, and IsOneNRelationship_. Each init object uses the type information supplied to the template base to specify how a piece of the schema should be built. The construction of the schema representation begins by chaining these ``init'' objects together to form a single list. This chaining can be easily achieved at static initialization time by the constructor of a common base class, Init_, for these static init objects. The rest of the construction process is carried out when a static member function Init_::initialize() is called sometime after {\tt main()} is entered\footnote{ Because Init_::initialize() will call some virtual methods in the translation units that define the static init objects, the objects are guaranteed by the language to be properly initialized.}. Several phases may be involved. During each phase, a pass is made through the list of init objects, calling a different virtual method for each phase. After each phase is finished, the next phase begins, until all the phases are carried out. There are two important phases. The builddescriptorphase is the phase for allocating all descriptor objects. For example, when the builddescriptorphase virtual method of the init object of RootEntity_ is called, it will allocate an entity descriptor object to represent the entity class Employee. The builddescriptorphase virtual method of the init object of IsOneNRelationshipForCompanyEmployee will allocate a relationship descriptor object to represent the relationship CompanyEmploysEmployees. When this phase is finished, all descriptor objects will be created. During the linkschemaphase, the descriptor objects are connected to represent the relationships among them. For example, when the linkschemaphase virtual method of the init object of IsOneNRelationshipForCompanyEmployee is called in this phase, it will link the entity descriptor objects for Company and Employee to the relationship descriptor object for CompanyEmploysEmployees. Also, when the linkschemaphase virtual method of the init object of SubtypeEntityForManager is called, it will link the entity descriptor object for Manager and that for Employee to represent the subtype relationship between the two. Overriding Pure Virtuals Template base delegation can be used to supply similar concrete implementations for pure virtual functions declared in an abstract base class. Suppose there is a pure virtual function entity_descriptor(), declared in the abstract base class Entity, which is to be overridden by each entity class to return its own descriptor object. Using the conventional way, each entity class will have to provide an overriding virtual function. This will likely involve: \begin{enumerate} \item Declaring the virtual function entity_descriptor() in the definition of the entity class. \item Declaring the descriptor object, or a pointer to it, as a static data member. \item Defining the virtual function entity_descriptor(), which returns the static data member. \end{enumerate} Alternatively, an entity class can delegate this responsibility to a template base, either RootEntity_<...> or SubtypeEntity_<...>. For example, instead of the class Employee overriding the pure virtual, its template base, RootEntity_, can supply a concrete implementation. Similarly, SubtypeEntityForManager can do the same for Manager. The template base will ensure that an appropriate override is provided for the virtual function. Using the conventional way, the number of source lines required to override the virtual is small, but they must be repeated for each entity class. In comparison, using template base delegation, there is a constant number of lines for the base template definition, but the number of additional source lines for each addition entity class is equal to 1, that is, the one used to declare the template base. The real advantage, however, is that the implementation of the overriding virtuals is centralized at the base template definition. If we need to change the implementation, say from declaring the descriptor object as a static data member to declaring a pointer to it, there is only one place to change in the source. It may be argued that using macros can achieve the same results. However, using macros generally means losing the ability to debug into the macro expansions. In comparison, the definitions of the entity classes using template base delegation are more readable, because more code is moved into the template bases. Uniform Access Building a ``uniform-access'' interface using these template bases and descriptor objects is possible. Uniform-access means essentially a general accessor method, getrelatedentities, which takes a relationship descriptor and returns a list of related entities with the specified relationship. A uniform access interface is especially useful for writing schema-independent client code, for example, a GUI(Graphical User Interface). Template Base Delegation as a Design Tradeoff The fact of the matter is that we are making the life of the client class writer easier by making the life of the base template writer more miserable. Whether this tradeoff makes sense depends on the number of client classes and client class writers versus the number of base templates and base template writers, as well as the relative complexity of the classes. Conclusion Some of the advantages of template base delegation are as follows: \begin{enumerate} \item The definition of the derived class can become more declarative. \item The interface and data members of the base class can be customized for the derived class. \item The derived class can specify to the template base whom to inherit from, thus preserving the application's inheritance hierarchy. \item Runtime efficiency can be enhanced without compromising on code sharing or strong typing. \item The derived class can inherit from two or more instantiations of the same base class template. \end{enumerate} The technique was illustrated using the Fan templates as an alternative to the traditional List container templates. A practical application of the technique in the area of object modeling was also demonstrated. \section{Acknowledgements} Dave Penny and Sam Wong have provided many good insights and suggestions for this paper. An anonymous referee suggested the use of ((void)sizeof(T)) to ensure that class T is defined before any downcast to T*. This will catch a common programming error which occurs when an upcast or downcast requires non-zero pointer adjustment. If the definition of the derived class has not been seen by the compiler, the compiler will erroneously treat the cast as to an unrelated type without generating the required pointer adjustment code. \begin{thebibliography}{99} \bibitem{RESPONSIBILITY-DRIVEN-APPROACH} Rebecca Wirfs-Brock and Brian Wilkerson. Object-Oriented Design: A Responsibility-Driven Approach. {\em Proceedings OOPSLA}, SIGPLAN Notices, Vol 24, \#10, October 1989. \bibitem{C++BOOK} Bjarne Stroustrup. {\em The C++ Programming Language: Second Edition.} Addison-Wesley, Reading, Massachusetts, 1991. \bibitem{ENTITY-RELATION} P. Chen. ``The Entity-Relation Model - Toward a Unified View of Data'' ACM Transaction on Database Systems, March 1976. \bibitem{ARM} Margaret A. Ellis and Bjarne Stroustrup. {\em The Annotated C++ Reference Manual} Addison-Wesley, Reading, Massachusetts, 1990. \bibitem{ADVANCED IDIOMS} James Coplien. {\em Advanced C++ Programming Styles and Idioms} Addison-Wesley, Reading, Massachusetts, 1992. \end{thebibliography} Appendix Source for the Fan templates (some details omitted): // If a use of the following macro causes the compiler to // fail, the definition of class T has not been seen but is // required. Try rearrange your source code so that the // definition of class T comes before the use of this macro. // #define ASSERT_CLASS_IS_DEFINED(T) ((void)sizeof(T)) // If a use of the following macro fails to compile, then // H is not inheriting from FanHead_. #define ASSERT_HEAD_INHERITS_FROM_FANHEAD(H,T,R) \ { FanHead_* dummy = (H*)0; } .... class FanHeadBase_ { public: add_tip(FanTipBase_& tip); unsigned num_tips() const; ... protected: FanHeadBase_() : first_tip_(0) {} FanTipBase_* first_tip_; }; class FanTipBase_ { protected: FanTipBase_() : head_(0), next_tip_(0) {} FanHeadBase_* head_; FanTipBase_* next_tip_; }; template class FanTip_; // Forward declaration template class FanHead_ : protected FanHeadBase_ { friend class FanTip_; public: FanHeadBase_::num_tips; add_tip(Tip& tip); ... }; template class FanTip_ : protected FanTipBase_ { friend class FanHead_; public: Head* head() const { ASSERT_CLASS_IS_DEFINED(Head); ASSERT_HEAD_INHERITS_FROM_FANHEAD(Head,Tip,Relationship); return (Head*)(FanHead_*) head_; } ... };