Pattern Magic, CallWithType Pattern

Good day, dear Khabrovchane!

In this article I want to talk about how in C ++ you can do the conversion of compile-time data (types) into run-time data (integer values) and back .

Example:

int nType = ... ;
')
if ( boost :: is_base_of < ISettable, / * ... magically resolve type hidden here ... * / > :: value )
{
// Do something
}
else
{
// Do something else
}

This whole topic is aimed at understanding what to write instead of “magically resolve type hidden by nType here”.

If you are only interested in the result, go directly to the last section.

A bit of history

It all started with the fact that I had to work with a complex factory of objects, which worked approximately as follows: to create an object, a certain function was invoked, which, based on the abyss of dynamic data, returned the ID of the type of object to be created. This ID then got into switch case, which actually created the necessary object, like this:

int nObjectType = ResolveObjectType ( ... ) ;

boost :: shared_ptr < IObject > pObject = CreateObject ( nObjectType ) ;

In this system, everything was fine until it turned out that, under certain runtime conditions, some objects need to be hung with wrappers like:

template < class TObject >
class CFilter : public TObject
{
virtual bool FilterValue ( ... ) { ... } ;
} ;

Such vrappers added some new functionality to objects, which is necessary under certain conditions. Naturally, initially the wrappers were hung up a little more than constantly and a little less than on all types of objects (for this you only had to add a few lines of code, very simple). However, the extra wrappers, although they did not harm the logic of the work, but increased the size of the objects, which was unacceptable: both the factory itself and the objects created with its help were critical in terms of performance and memory consumption.

Thus, it was necessary to switch on the wrappers as an option. Immediately there were problems:

• When adding a single wrapper, the number of types of objects created grew almost 2 times, because The wrapper was applicable not to a single type, but to a certain set of types.
• When adding these new types, I had to search for all switch cases by type for the entire code.

    (after all, if before some code reacted to an object of type A, now it still has to react to CFilter <A>, because the type has not changed in fact, just added new features). 

• By the value returned by GetObjectType (...) it was absolutely impossible to restore the original type (without a manually written switch), which did not allow writing abstract code that turns on if the object is, say, inherited from a certain interface. For example, under certain conditions, CFilter's wrapper should have been applied to all objects inherited from the ISettable.
• Already created objects could not normally determine their real type without using dynamic_cast (very slowly).

Having understood all this, I sat down and thought. It turned out that all I need is to learn how to pull out the type that is hidden behind the value returned by GetObjectType (...), and this so that it is understandable to the compiler, i.e. so that you can write things in the spirit of:

int nType = ... ;

if ( boost :: is_base_of < ISettable, / * ... magically resolve type hidden here ... * / > :: value )
{
// Do something
}
else
{
// Do something else
}

My first thought: “this is impossible!”

Stencil magic, or the impossible is possible!

After some more thought, I came to the conclusion that it was necessary to “simply” write the following two functions:

//! Returns object type descriptor correspondent to TObject.
template < class TObject >
inline int MakeDescriptor ( ) ;

//! Calls rcFunctor with nTypeDescriptor.
template < class TFunctor >
inline typename Impl :: ResolveReturnType < TFunctor > :: type CallWithType ( const TFunctor & rcFunctor, int nTypeDescriptor ) ;

Everything is clear here:

• The first function returns an object type descriptor (number) depending on the type of object (template parameter).
• The second function calls the functor passed to it, using as a parameter a pointer to the type of object encoded within the number nTypeDescriptor. Thus, using the template operator () in the functor, you can completely restore the original type.

You can use it this way (in this example, we determine whether the type encoded by the descriptor from an interface is inherited):

template < class TKind >
struct IsKindOfHelper
{
typedef bool
R ;

inline bool operator ( ) ( ... ) const
{
return false ;
}

inline bool operator ( ) ( TKind * ) const
{
return true ;
}
} ;

template < class TObject >
inline bool IsKindOf ( int nTypeDescriptor )
{
Return CallWithType ( IsKindOfHelper < TObject > ( ) , nTypeDescriptor ) ;
}

...

int nType = ... ;

if ( IsKindOf < ISettable > ( nType ) )
{
// Do something
}
else
{
// Do something else
}

Type lists and descriptors.

So, we will start implementation. First of all, we need some kind of compile-time table that will determine the correspondence of type descriptors and types. The simplest option here is Loki :: Typelist, this is a structure of the following form:

template < class T, class U >
struct typelist
{
typedef T Head ;
typedef U Tail ;
} ;

The contemplation of this structure in its time completely reversed my understanding of C ++. Let's see what it is for. It's very simple: with its help lists of types of arbitrary length are defined:

typedef Loki :: Typelist < int , Loki :: Typelist < char , Loki :: Typelist < void , Loki :: NullType>>>
TMyList ;

Here is a list of types of three elements: int, char, void. Loki :: NullType means the end of the list. Using special metafunctions from this list, you can pull out type indices and types by index:

// int MyInt;
Loki :: TypeAt < TMyList, 0 > :: Result MyInt ;

// char MyChar;
Loki :: TypeAt < TMyList, 1 > :: Result MyChar ;

int nIndexOfChar = Loki :: IndexOf < TMyList, char > :: value ;

All these metafunctions are "called" at compile time and do not require the overhead of execution time. More information about Loki, you can read in Wikipedia , there is also a link to the source library. In the book "Modern design in C ++" (Alexandrescu) you can find out how it all works.

In practice, I used the Boost MPL library. It is more difficult, but its possibilities are much wider. Experiments have shown that the compiler maintains about 2000 types of objects, after which the following picture is observed:

Implementing a pattern through type lists.

Idea:

  List all known object types in a list of types.  Then, the index of a particular type will be a type descriptor, but knowing the type descriptor, you can infer the type itself by looking at it in the list.  The only problem is the following: for type inference by index, the index must be represented as a constant (compile-time values), i.e.  we need to learn how to convert the values ​​of numerical variables to the corresponding types of the type mpl :: int_ <# value #> 

using namespace boost ;

namespace impl
{
//! A list of known object types.
/ ** In real world this structure constructed by templates. * /
typedef mpl :: list < TObjectType1, TObjectType2, TObjectType3 >
TKnownObjectTypes ;

//! Count of the known object types.
typedef mpl :: size < TKnownAtomTypes > :: type
TKnownObjectTypesCount ;
}

namespace impl
{
//! This metafunction returns an index of the TObject from the TKnownObjects.
/ ** If TObject is absent in TKnownObjects, returns -1 * /
template < class TObject >
struct MakeDescriptorImpl
: / * if * / mpl :: eval_if <
/ * find (TObject) == end * /
is_same <
typename mpl :: find < TKnownObjectTypes, TObject > :: type ,
mpl :: end < TKnownObjectTypes > :: type > ,
/ * then return -1 * /
mpl :: identity < mpl :: int_ < - 1 >> ,
/ * else return distance (begin, find (TObject)) * /
mpl :: apply <
mpl :: distance <
mpl :: begin < TKnownObjectTypes > :: type ,
mpl :: find < TKnownObjectTypes, _ >> ,
TObject >> :: type
{
} ;

//! Helps to call TFunctor with TObjectType *
template < class TFunctor >
struct CallWithObjectTypeHelperPointerBased
{

public :

// typename ResolveReturnType <TFunctor> :: type evalutes to TFunctor :: R if
// TFunctor :: R typedef is present, otherwise, it is to void.
typedef typename ResolveReturnType < TFunctor > :: type
R ;

protected :

const TFunctor &
m_rcFunctor ;

public :

CallWithObjectTypeHelperPointerBased ( const TFunctor & rcFunctor )
: m_rcFunctor ( rcFunctor )
{
}

//! This function is called by CallWithInt (...).
template < class TIndex >
R operator ( ) ( TIndex ) const
{
// Find object type by index
typedef typename mpl :: at < TKnownObjectTypes, TIndex > :: type
TObject ;

// Call functor with pointer to real object type
return m_rcFunctor ( ( TObject * ) NULL ) ;
}

//! This function is called by CallWithInt (...).
R operator ( ) ( mpl :: void_ ) const
{
// The descriptor is broken, call functor with special value
return m_rcFunctor ( mpl :: void_ ( ) ) ;
}
} ;

}

//! Returns Object type descriptor correspondent to TObject.
template < class TObject >
inline int MakeDescriptor ( )
{
// Attempt to make Object type description for unknown Object type!
BOOST_STATIC_ASSERT ( Impl :: MakeDescriptorImpl < TObject > :: value ! = - 1 ) ;

// Return descriptor, this is actually compile time generated constant.
return Impl :: MakeDescriptorImpl < TObject > :: value ;
}

//! Calls rcFunctor with TObject * correspondent to nObjectTypeDescriptor.
template < class TFunctor >
inline typename Impl :: ResolveReturnType < TFunctor > :: type CallWithType ( const TFunctor & rcFunctor, int nObjectTypeDescriptor )
{
// Call with int will call
// Impl :: CallWithObjectTypeHelperPointerBased <TFunctor> (rcFunctor)
// functor with mpl :: int_ <N> () argument, where N is compile time constant
// correspondent to the value of nObjectTypeDescriptor.
// If nObjectTypeDescriptor <0 || nObjectTypeDescriptor> = TKnownObjectTypesCount
// functor will be used with mpl :: void_ (), indicating that type descriptor is broken.
return Impl :: CallWithInt < mpl :: int_ < 0 > , TKnownObjectTypesCount > (
Impl :: CallWithObjectTypeHelperPointerBased < TFunctor > ( rcFunctor ) ,
nObjectTypeDescriptor ) ;
}

I tried to comment in detail on all the code, but it is still quite complicated, so there are some comments:

one.
typename ResolveReturnType :: type is interpreted by the compiler as TFunctor :: R. If TFunctor :: R is an invalid expression (for example, if the definition of type R is not in the TFunctor), then typename ResolveReturnType :: type is interpreted as void. Yes it is possible. No, I'm not lying . The implementation can be viewed below, by reference in which the implementation of CallWithInt is described.

2
MakeDescriptorImpl is actively working with boost :: mpl and it looks awesome. For the sake of clarity, comments contain similar expressions in stl (which, of course, are not applicable at the compilation stage). The indent style is torn out from Scheme . For those who are familiar with functional programming languages, you just need to understand that metaprogramming (template magic) in c ++ is a functional language.

3
CallWithInt is engaged in converting integer runtime values ​​from a specific range of allowed values ​​to integer compile time values. We will implement this feature later.

  Example: 42 is converted to mpl :: int_ <42> 

four.
An implementation would be more efficient (in terms of compilation speed) if a binary tree is used instead of mpl :: list. Unfortunately, I have not found such structures, but I myself have been writing for a long time. For our project it was not critical, with the number of types less than 500 works and so.

five.
In terms of runtime performance, this code is very fast. CallWithInt, as we will see below, works on nested switch cases, therefore, only a few unconditional jumps with an offset are needed to convert a number to a type. For the inverse transformation, nothing is needed at all. MakeDescriptor is inlined into a constant.

6
In the real world, a list of known objects is constructed using patterned magic in the following way:

• Sets the base list of objects (in the same way as in the example)
• Each wrapper is applied in turn to each type from the current list of types, if possible. Wrapper himself determines how he will communicate with a specific type. The result of the binding (new type) is added to the current type list.

This action is performed using templates at compile time, it takes about 200 lines of code. To add a new wrapper (and all new types that a wrapper introduces) you need to write about 10 lines in total, while new types will be automatically picked up by the existing code.

7
In addition to the above functions, in the real world several more variants are implemented (for example, MakeDescriptorNonStrict, which returns -1 (and not a compilation error, as usual), if it is applied to an unknown type of science). CallWithType also has other variants that call a functor, for example, with two pointers (one can be used to specialize in the inheritance tree, and the second to determine the real type).

CallWithInt implementation

  It remains for us to perform the last (most difficult) step: write a function that will call a functor with the type mpl :: int_ <N> (), where N corresponds to the value stored inside the run-time variable.  This is perhaps the most difficult part, because  it is this that translates runtime values ​​into types. 

The idea is very simple:

  We make a function with a switch, say one hundred elements, this function should call any functor with the value mpl :: int <N>, where N corresponds to the value of the variable passed to the function.  If we are asked to transform a different interval, we simply do additional manipulations: offset and separation into bins.  So for example, if we are asked to convert a number in the range 56 ... 156 to a type, you just need to subtract 56 times from the variable that was passed to us, and then, after the conversion to type, add 56 (but to the type!).  If we are asked to convert a number from the interval 200..400, we must first divide it into sections "100 each", then calculate the number of the section and the offset inside the section. 

I guess I explain it incomprehensibly, so here’s a lot of killer code .

Remarks:

0
Many beeches :(

one.
In the real world, a switch has 100 case-s (the value was chosen experimentally, the code is operational at any value> = 2).

2
In the real world, switch cases are generated by macros.

3
It works fast. Very fast. For this one has to pay with such brutal expressions. The compiler could not optimize the simple implementation through tail recursion before the switch: (

Application

Now you can do this:

1. Creating any objects, just add the type of the object to the list of known types. Previously, when adding a new type of objects, it was necessary to search for all switch cases by type, now there is no switch case at all, which means that all new types of objects are supported out of the box. This example illustrates the loss of a switch case.

It was:

int nObjectType = ResolveObjectType ( ... ) ;

switch ( nObjectType )
{
case 1 :
return new TObject1 ( ) ;
case 2 :
return new TObject2 ( ) ;
case 3 :
return new TObject3 ( ) ;
case 4 :
return new TObject4 ( ) ;
/ * ... 100+ more cases goes here * /
default :
return NULL ;
} ;

It became:

//! This wrapper allows to determine real object type.
template < class TBase, class TObject = TBase >
struct CTypeWrapper
: public TBase
{
//! Returns type descriptor correspondent to this instance.
virtual int TypeDescriptor ( ) const
{
Return MakeDescriptor < TObject > ( ) ;
}
} ;

//! Helps to create objects. Actually this is a functor, called with Object type.
class CreateObjectHelper
{

public :

// Return type
typedef IObject *
R ;

private :

template < class TBase, class TObject >
inline TBase * MakeObject ( ) const
{
return new CObjectTypeWrapper < TBase, TObject > ( ) ;
}

public :

//! Generic case
template < class TObject >
inline TObject * operator ( ) ( TObject * , ... ) const
{
return MakeObject < TObject, TObject > ( ) ;
}

inline IObject * operator ( ) ( boost :: mpl :: void_ ) const
{
assert ( ! "Type Descriptor Is Broken! Mustn't be here!" ) ;

return NULL ;
}

public :

// Special case for objects, derived from IObjectType1
template < class TObject >
IObject * operator ( ) ( TObject * , IObjectType1 * ) const
{
// ...
}

// Special case for objects, derived from IObjectType2
template < class TObject >
IObject * operator ( ) ( TObject * , IObjectType2 * ) const
{
// ...
}
} ;

...

int nObjectType = ResolveObjectType ( ... ) ;

return ObjectTraits :: CallDoublePointerBasedFunctorWithObjectType (
CreateObjectHelper ( ) ,
nObjectType ) ;

2. Changing the behavior of classes located in the middle of the inheritance tree, depending on the actual type of object, without using dynamic_cast (the approach with CallWithType is approximately 50 times faster on our class hierarchy):

template < class TKind >
struct IsKindOfHelper
{
typedef bool
R ;

inline bool operator ( ) ( ... ) const
{
return false ;
}

inline bool operator ( ) ( TKind * ) const
{
return true ;
}
} ;

template < class TObject >
inline bool IsKindOf ( int nTypeDescriptor )
{
Return CallWithType ( IsKindOfHelper < TObject > ( ) , nTypeDescriptor ) ;
}

...

// TypeDescriptor is a virtual object type.
// Implementation shown in previous example (this function by hands)
if ( IsKindOf < ISettable > ( this - > TypeDescriptor ( ) ) )
{
// Do something
}
else
{
// Do something else
}

3. Ability to operate with a variable containing a type descriptor directly as with a type. This helps a lot during the procedure of determining what kind of object you should create (if the type depends on many external factors):

int ApplySomeWrapper ( int nType )
{
bool bShouldBeWrapperApplied = ... ;

if ( bShouldBeWrapperApplied )
{
// IsWrapperApplicable converts nType to the real type TObject using CallWithType
// and calls WrapperTraits :: CSomeWrapper :: IsApplicable <TObject> :: value metafunction
if ( IsWrapperApplicable < WrapperTraits :: CSomeWrapper > ( nType ) )
{
// IsWrapperApplicable converts nType to the real type TObject using CallWithType,
// calls WrapperTraits :: CSomeWrapper :: MakeWrappedType <TObject> :: type metafunction
// in order to resolve wrapped type, then calls MakeDescriptor for this type.
return MakeWrappedType < WrapperTraits :: CSomeWrapper > ( nType ) ;
}
}

return nType ;
}