3.13 Class Generation with Typelists

If, until now, you found typelists intriguing, interesting, or just ugly, you haven't seen anything yet. This section is dedicated to defining fundamental constructs for code generation with typelists. That is, we don't write code anymore; instead, we put the compiler to work generating code for us. These constructs use one of the most powerful constructs of C++, a feature unmatched by any other language—template template parameters.

So far, typelist manipulation has not yielded actual code; the processing has produced only typelists, types, or compile-time numeric constants (as was the case with Length). Let's tap into generating some real code, that is, stuff that leaves traces in the compiled code.

Typelist objects have no use as they are; they are devoid of any runtime state or functionality. An important need in programming with typelists is to generate classes from typelists. Application programmers sometimes need to fill a class with code—be it virtual function signatures, data declarations, or function implementations—in ways directed by a typelist. We will try to automate such processes with typelists.

Because C++ lacks compile-time iteration or recursive macros, the task of adding some code for each type in a typelist is difficult. You can use partial template specialization in ways resembling the algorithms described earlier, but implementing this solution in user code is clumsy and complicated. Loki should be of help with this task.

3.13.1 Generating Scattered Hierarchies

A powerful utility template provided by Loki makes it easy to build classes by applying each type in a typelist to a basic template, provided by the user. This way, the clumsy process of distributing types in the typelist to user code is encapsulated in the library; the user need only define a simple template of one parameter.

The library class template is called GenScatterHierarchy. Although it has a simple definition, GenScatterHierarchy has amazing horsepower under its hood, as you'll see soon. For now, let's look at its definition.^[3]

^[3] This is one of those situations in which presenting the idea before its potential applications (as opposed to a problem-solution sequence) is more appropriate.

template <class TList, template <class> class Unit>


class GenScatterHierarchy;





// GenScatterHierarchy specialization: Typelist to Unit


template <class T1, class T2, template <class> class Unit>


class GenScatterHierarchy<Typelist<T1, T2>, Unit>


   : public GenScatterHierarchy<T1, Unit>


   , public GenScatterHierarchy<T2, Unit>


{


public:


   typedef Typelist<T1, T2> TList;


   typedef GenScatterHierarchy<T1, Unit> LeftBase;


   typedef GenScatterHierarchy<T2, Unit> RightBase;


};





// Pass an atomic type (non-typelist) to Unit


template <class AtomicType, template <class> class Unit>


class GenScatterHierarchy : public Unit<AtomicType>


{


   typedef Unit<AtomicType> LeftBase;


};





// Do nothing for NullType


template <template <class> class Unit>


class GenScatterHierarchy<NullType, Unit>


{


};

Template template parameters work much as you would expect (see also Chapter 1). You pass a template class Unit to GenScatterHierarchy as its second argument. Internally, GenScatterHierarchy uses its template template parameter Unit just as it would have used any regular template class with one template parameter. The power comes from your ability—as the user of GenScatterHierarchy—to pass it a template written by you.

What does GenScatterHierarchy do? If its first template argument is an atomic type (as opposed to a typelist), GenScatterHierarchy passes that type to Unit, and inherits from the resulting class Unit<T>. If GenScatterHierarchy's first template argument is a type list TList, GenScatterHierarchy recurses to GenScatterHierarchy<TList::Head, Unit> and GenScatterHierarchy<TList::Tail, Unit>, and inherits both. GenScatterHierarchy<NullType, Unit> is an empty class.

Ultimately, an instantiation of GenScatterHierarchy ends up inheriting Unit instantiated with every type in the typelist. For instance, consider this code:

template <class T>


struct Holder


{


   T value_;


};





typedef GenScatterHierarchy<


      TYPELIST_3(int, string, Widget),


      Holder>


   WidgetInfo;

The inheritance hierarchy generated by WidgetInfo looks like Figure 3.2. We call the class hierarchy in Figure 3.2 scattered, because the types in the typelist are scattered in distinct root classes. This is the gist of GenScatteredHierarchy: It generates a class hierarchy for you by repeatedly instantiating a class template that you provide as a model. Then it collects all such generated classes in a single leaf class—in our case, WidgetInfo.

As an effect of inheriting Holder<int>, Holder<string>, and Holder<Widget>, WidgetInfo has one member variable value_ for each type in the typelist. Figure 3.3 shows a likely binary layout of a WidgetInfo object. The layout assumes that empty classes such as GenScatterHierarchy<NullType, Holder> are optimized away and do not occupy any storage in the compound object.

You can do interesting things with WidgetInfo objects. You can, for instance, access the string stored in a WidgetInfo object by writing

WidgetInfo obj;


string name = (static_cast<Holder<string>&>(obj)).value_;

The explicit cast is necessary to disambiguate the member variable name value_. Otherwise, the compiler is confused as to which value_ member you are referring to.

This cast is quite ugly, so let's try to make GenScatterHierarchy easier to use by providing some handy access functions. For instance, a nice member function would access a member by its type. This is quite easy.

// Refer to HierarchyGenerators.h for FieldTraits' definition


template <class T, class H>


typename Private::FieldTraits<H>::Rebind<T>::Result&


Field(H& obj)


{


   return obj;


}

Field relies on implicit derived-to-base conversion. If you call Field<Widget>(obj) (obj being of type WidgetInfo), the compiler figures out that Holder<Widget> is a base class of WidgetInfo and simply returns a reference to that part of the compound object.

Why is Field a namespace-level function and not a member function? Well, such highly generic programming must play very carefully with names. Imagine, for instance, that Unit itself defines a symbol with the name Field. Had GenScatterHierarchy itself defined a member function Field, it would have masked Unit's Field member. This would be a major source of annoyance to the user.

There is one more major source of annoyance with Field: You cannot use it when you have duplicate types in your typelists. Consider this slightly modified definition of WidgetInfo:

typedef GenScatterHierarchy<


      TYPELIST_4(int, int, string, Widget),


      Value>


WidgetInfo;

Now WidgetInfo has two value_ members of type int. If you try to call Field<int> for a WidgetInfo object, the compiler complains about an ambiguity. There is no easy way to solve the ambiguity, because the WidgetInfo ends up inheriting Holder<int> twice through different paths, as shown in Figure 3.4.

We need a means of selecting fields in an instantiation of GenScatterHierarchy by positional index, not by type name. If you could refer to each of the two fields of type int by its position in the typelist (that is, as Field<0>(obj) and Field<1>(obj)), you would get rid of the ambiguity.

Let's implement an index-based field access function. We have to dispatch at compile time between the field index zero, which accesses the head of the typelist, and nonzero, which accesses the tail of the typelist. Dispatching is easy with the help of the little Int2Type template defined in Chapter 2. Recall that Int2Type simply transforms each distinct constant integral into a distinct type. Also, we use Type2Type to transport the result type appropriately, as shown below.

template <class H, typename R>


inline R& FieldHelper(H& obj, Type2Type<R>, Int2Type<0>)


{


   typename H::LeftBase& subobj = obj;


   return subobj;


}





template <class H, typename R, int i>


inline R& FieldHelper(H& obj, Type2Type<R> tt, Int2Type<i>)


{


   typename H::RightBase& subobj = obj;


   return FieldHelper(subobj, tt, Int2Type<i- 1>());


}


//Refer to HierarchyGenerators.h for FieldTraits' definition


template <int i, class H>


typename Private::FieldTraits<H>::At<i>::Result&


Field(H& obj)


{


   typedef typename Private::FieldTraits<H>::At<i>::Result


      Result;


   return FieldHelper(obj, Type2Type<Result>(), Int2type<i>());


}

It takes a while to figure out how to write such an implementation, but fortunately explaining it is quite easy. Two overloaded functions called FieldHelper do the actual job. The first one accepts a parameter of type Int2Type<0>, and the second is a template that accepts Int2Type<any integer>. Consequently, the first overload returns the value corresponding to the Unit<T1>&, and the other returns the type at the specified index in the typelist. Field uses a helper template FieldTraits to figure out what type it must return. Field passes that type to FieldHelper through Type2Type.

The second overload of FieldHelper recurses to FieldHelper, passing it the right-hand base of GenScatterHierarchy and Int2Type<index - 1>. This is because field N in a typelist is field N - 1 in the tail of that typelist, for a non-zero N. (And indeed, the N = 0 case is handled by the first overload of FieldHelper.)

For a streamlined interface, we need two additional Field functions: the const versions of the two Field functions defined above. They are similar to their non-const counterparts, except that they accept and return references to const types.

Field makes GenScatterHierarchy very easy to use. Now we can write

WidgetInfo obj;


...


int x = Field<0>(obj).value_; // first int


int y = Field<1>(obj).value_; // second int

The GenScatterHierarchy template is very suitable for generating elaborate classes from typelists by compounding a simple template. You can use GenScatterHierarchy to generate virtual functions for each type in a typelist. Chapter 9, Abstract Factory, uses GenScatterHierarchy to generate abstract creation functions starting from a type list. Chapter 9 also shows how to implement hierarchies generated by GenScatterHierarchy.

3.13.2 Generating Tuples

Sometimes you might need to generate a small structure with unnamed fields, known in some languages (such as ML) as a tuple. A tuple facility in C++ was first introduced by Jakko Järvi (1999a) and then refined by Järvi and Powell (1999b).

What are tuples? Consider the following example.

template <class T>


struct Holder


{


   T value_;


};





typedef GenScatterHierarchy<


   TYPELIST_3(int, int, int),


   Holder>


Point3D;

Working with Point3D is a bit clumsy, because you have to write.value_ after any field access function. What you need here is to generate a structure the same way GenScatterHierarchy does, but with the Field access functions returning references to the value_ members directly. That is, Field<n> should not return a Holder<int>&, but an int& instead.

Loki defines a Tuple template class that is implemented similarly to GenScatterHierarchy but that provides direct field access. Tuple works as follows:

typedef Tuple<TYPELIST_3(int, int, int)>


   Point3D;


Point3D pt;


Field<0>(pt) = 0;


Field<1>(pt) = 100;


Field<2>(pt) = 300;

Tuples are useful for creating small anonymous structures that don't have member functions. For example, you can use tuples for returning multiple values from a function:

Tuple<TYPELIST_3(int, int, int)>


GetWindowPlacement(Window&);

The fictitious function GetWindowPlacement allows users to get the coordinates of a window and its position in the window stack using a single function call. The library implementer does not have to provide a distinct structure for tuples of three integers.

You can see other tuple-related functions offered by Loki by looking in the file Tuple.h.

3.13.3 Generating Linear Hierarchies

Consider the following simple template that defines an event handler interface. It only defines an OnEvent member function.

template <class T>


class EventHandler


{


public:


   virtual void OnEvent(const T&, int eventId) = 0;


   virtual void ~EventHandler() {}


};

To be politically correct, EventHandler also defines a virtual destructor, which is not germane to our discussion, but necessary nonetheless (see Chapter 4 on why).

We can use GenScatterHierarchy to distribute EventHandler to each type in a typelist:

typedef GenScatterHierarchy


<


   TYPELIST_3(Window, Button, ScrollBar),


   EventHandler


>


WidgetEventHandler;

The disadvantage of GenScatterHierarchy is that it uses multiple inheritance. If you care about optimizing size, GenScatterHierarchy might be inconvenient, because Widget-EventHandler contains three pointers to virtual tables,^[4] one for each EventHandler instantiation. If sizeof(EventHandler) is 4 bytes, then sizeof(WidgetEventHandler) will likely be 12 bytes, and it grows as you add types to the typelist. The most space-efficient configuration is to have all virtual functions declared right inside WidgetEventHandler, but this dismisses any code generation opportunities.

^[4] An implementation does not need to use virtual tables, but most implementations do. For a description of virtual tables, refer to Lippman (1994).

A nice configuration that decomposes WidgetEventHandler into one class per virtual function is a linear inheritance hierarchy, as shown in Figure 3.5. By using single inheritance, WidgetEventHandler would have only one vtable pointer, thus maximizing space efficiency.

How can we provide a mechanism that automatically generates a hierarchy like this? A recursive template similar to GenScatterHierarchy can be of help here. There is a difference, though. The user-provided class template must now accept two template parameters. One of them is the current type in the typelist, as in GenScatterHierarchy. The other one is the base from which the instantiation derives. The second template parameter is needed because, as shown in Figure 3.5, the user-defined code now participates in the middle of the class hierarchy, not only at its roots (as was the case with GenScatterHierarchy).

Let's write a recursive template GenLinearHierarchy. It bears a similarity to GenScatterHierarchy, the difference being the way it handles the inheritance relationship and the user-provided template unit.

template


<


   class TList,


   template <class AtomicType, class Base> class Unit,


   class Root = EmptyType // For EmptyType, consult Chapter 2


>


class GenLinearHierarchy;





template


<


   class T1,


   class T2,


   template <class, class> class Unit,


   class Root


>


class GenLinearHierarchy<Typelist<T1, T2>, Unit, Root>


   : public Unit< T1, GenLinearHierarchy<T2, Unit, Root> >


{


};





template


<


   class T,


   template <class, class> class Unit,


   class Root


>


class GenLinearHierarchy<TYPELIST_1(T), Unit, Root>


   : public Unit<T, Root>


{


};

This code is slightly more complicated than GenScatterHierarchy's, but the structure of a hierarchy generated by GenLinearHierarchy is simpler. Let's verify the adage that an image is worth 1,024 words by looking at Figure 3.6, which shows the hierarchy generated by the following code.

template <class T, class Base>


class EventHandler : public Base


{


public:


   virtual void OnEvent(T& obj, int eventId);


};


typedef GenLinearHierarchy


<


   TYPELIST_3(Window, Button, ScrollBar),


   EventHandler


>


MyEventHandler;

In conjunction with EventHandler, GenLinearHierarchy defines a linear, rope-shaped, single-inheritance class hierarchy. Each other node in the hierarchy defines one pure virtual function, as prescribed by EventHandler. Consequently, MyEventHandler defines three virtual functions, as needed. GenLinearHierarchy adds a requirement to its template template parameter: Unit (in our example, EventHandler) must accept a second template argument, and inherit from it. In compensation, GenLinearHierarchy does the laborious task of generating the class hierarchy.

GenScatterHierarchy and GenLinearHierarchy work great in tandem. In most cases, you would generate an interface with GenScatterHierarchy and implement it with GenLinearHierarchy. Chapters 9 and 10 demonstrate concrete uses of these two hierarchy generators.