Доброго времени суток, уважаемые Xабровчане!

В этой статье я хочу рассказать о том, как в С++ можно делать преобразование данных времени компиляции (типов) в данные времени выполнения (целые значения) и обратно.

Пример:

int nType = ...;

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

Весь этот топик направлен на то, чтобы понять, что же надо написать вместо «magically resolve type hidden by nType here».

Если Вам интересен только результат, переходите сразу к последнему разделу.

Немного истории

Все началось с того, что мне по долгу службы понадобилось работать со сложной фабрикой объектов, которая работала приблизительно следующим образом: для создания объекта вызвалась некая функция, которая на основании бездны динамических данных возвращала ID типа объекта, который необходимо создать. Этот ID затем попадал в switch case, который собственно и создавал необходимый объект, приблизительно так:

int nObjectType = ResolveObjectType( ... );

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

В этой системе все было хорошо до тех пор, пока не оказалось, что при определенных runtime условиях на некоторые объекты необходимо навешивать врапперы вида:

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

Такие врапперы добавляли к объектам некую новую функциональность, необходимую при определенных условиях. Естественно, изначально врапперы навешивались чуть более чем постоянно и чуть менее чем на все типы объектов (для этого надо было добавить всего несколько строк кода, очень просто). Однако, лишние врапперы, хотя и не наносили вреда логике работы, но увеличивали размер объектов, что было неприемлемо:
как сама фабрика, так и созданные с ее помощью объекты были критичны с точки зрения производительности и расхода памяти.

Таким образом, включать врапперы необходимо было все-таки опционально. Сразу же возникли проблемы:

При добавлении одного единственного враппера, количество типов создаваемых объектов выростало чуть ли не в 2 раза, т.к. враппер был применим не к одному единственному типу, а к некоторому набору типов.
При добавлении этих новых типов, приходилось искать все switch case по типам по всему коду (ведь, если раньше какой-то код реагировал на объект типа A, то теперь он еще должен реагировать на CFilter< A >, потому как тип-то по сути не изменился, просто добавились новые фичи).
По значению, возвращаемому GetObjectType(… ) было совершенно невозможно восстановить исходный тип (без вручную написанного switch), что не позволяло писать абстрактный код, который включается, если объект, скажем, наследуется от некого интерфейса. Так, например, при определенных условиях враппер CFilter должен был применяться ко всем объектам, наследуемым от ISettable.
Уже созданные объекты не могли нормальным образом определить свой реальный тип без использования dynamic_cast (оччень медленно).

Поняв все это, я сел и задумался. Оказалось, что все, что мне надо это научиться вытягивать тип который скрывается за значением, возвращаемым GetObjectType(… ), при чем так, чтобы это было понятно компилятору, т.е. чтобы можно было писать вещи в духе:

int nType = ...;

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

Моя первая мысль: «это невозможно!»

Шаблонная магия, или невозможное возможно!

Еще немного подумав, я пришел к выводу, что надо «просто» написать две следующих функции:

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

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

Тут все понятно:

Первая функция возвращает дескриптор типа объекта (число) в зависимости от типа объекта (шаблонного параметра).
Вторая функция вызывает переданный ей функтор, используя в качестве параметра указатель на тип объекта, закодированный внутри числа nTypeDescriptor. Таким образом, используя шаблонный operator() в функторе, можно полностью восстановить исходный тип.

Использовать можно так (в этом примере мы определяем, наследуется ли тип, закодированный дескриптором от какого-либо интерфейса):

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
}

Списки типов и дескрипторы.

Итак, приступим к реализации. В первую очередь нам нужна некоторая табличка времени компиляции, которая будет задавать соответствие дескрипторов типа и типов. Самым простым вариантом здесь является Loki::Typelist, это структура следующего вида:

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

Созерцание этой структуры в свое время полностью перевернуло мое представление о С++. Давайте разберемся для чего она нужна. Все очень просто: с ее помощью задаются списки типов произвольной длины:

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

Здесь задается список типов из трех элементов: int, char, void. Loki::NullType означает конец списка. Используя специальные метафункции из этого списка можно вытягивать индексы типов и типы по индексу:

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

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

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

Все эти метафункции «вызываются» на этапе компиляции и не требуют накладных расходов времени выполнения. Подробнее про Loki, можно почитать в Википедии, там же есть ссылка на исходники библиотеки. В книжке «Современное проектирование на С++» (Александреску) можно узнать как все это работает.

На практике я использовал библиотеку Boost MPL. Она сложнее, но ее возможности намного шире. Эксперименты показали, что компилятор выдерживает порядка 2000 типов объектов, после чего наблюдается следующая картина:

Реализация паттерна через списки типов.

Идея:перечислить все известные типы объектов в некотором списке типов. Тогда, индекс конкретного типа будет дескриптором типа, ну а зная дескриптор типа можно вывести сам тип, посмотрев его в списке. Единственная проблема заключается в следующем: для вывода типа по индексу, индекс должен быть представлен в виде константы (значения времени компиляции), т.е. нам необходимо научиться преобразовывать значения численных переменных в соответствующие им типы вида mpl::int_< #значение# >

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 evalutes 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 called with mpl::void_(), indicating that type descriptor is broken.
return Impl::CallWithInt< mpl::int_< 0 >, TKnownObjectTypesCount >(
Impl::CallWithObjectTypeHelperPointerBased< TFunctor >( rcFunctor ),
nObjectTypeDescriptor );
}

Я постарался подробно комментировать весь код, однако он все равно достаточно сложен, поэтому есть некоторые замечания:
1.
typename ResolveReturnType::type интерпретируется компилятором как TFunctor::R. Если TFunctor::R является неверным выражением (например, если определение типа R отсутствует в TFunctor), то typename ResolveReturnType::type интерпретируется как void. Да это возможно. Нет, я не вру. Реализацию можно посмотреть ниже, по ссылке в которой описана реализация CallWithInt.

2.
MakeDescriptorImpl активно работает с boost::mpl и выглядит устрашающе. Для пущей понятности в комментариях приведены аналогичные выражения в stl (которые, естественно, не применимы на этапе компиляции). Стиль отступов выдран из Scheme. Для тех кто, знаком с функциональными языками программирования надо просто понять, что метапрограммирование (шаблонная магия) на с++ — это функциональный язык.

3.
CallWithInt занимается преобразованием целых значений времени выполнения из определенной области допустимых значений в целые значения времени компиляции. Мы реализуем эту функцию чуть позже.
Пример: 42 преобразовывается в mpl::int_< 42 >4.
Реализация была бы более эффективна (с точки зрения скорости компиляции), если вместо mpl::list использовать бинарное дерево. К сожалению, таких структур я не нашел, а самому писать долго. Для нашего проекта это было не критично, при количестве типов менее 500 работает и так.

5.
С точки зрения производительности времени выполнения этот код очень быстр. CallWithInt, как мы увидим ниже работает на вложенных switch case, поэтому для преобразования числа в тип необходимо всего несколько безусловных прыжков со смещением. Для обратного преобразования вообще ничего не надо, т.к. MakeDescriptor инлайнится в константу.

6.
В реальном мире список известных объектов строится с помощью шаблонной магии приблизительно таким образом:

Задается базовый список объектов (тем же способом, как в примере)
Каждый враппер применяется по очереди к каждому типу из текущего списка типов, если это возможно. Враппер сам определяет, каким образом он будет связываться с конкретным типом. Результат связывания (новый тип) добавляется в текущий список типов.

Сие действие выполняется с помощью шаблонов на этапе компиляции, занимает около 200 строк кода. Для добавления нового враппера (и всех новых типов, которые привнесет враппер) надо написать всего около 10 строк, при этом новые типы автоматически будут подхвачены существующим кодом.

7.
Помимо приведенных выше функций в реальном мире реализовано еще несколько их вариантов (например, MakeDescriptorNonStrict, который возвращает -1 (а не ошибку компиляции, как обычный), если он применен к неизвестному науке типу). CallWithType, также имеет другие варианты, вызывающие функтор, например, с двумя указателями (один можно использовать для специализации по дереву наследования, а второй для определения реального типа).

Релизация CallWithInt

Нам осталось совершить последний (самый трудный) шаг: написать функцию, которая будет вызывать функтор с типом mpl::int_< N >(), где N соответствует значению, сохраненному внутри переменной времени выполнения. Это, пожалуй, самая сложная часть, т.к. именно она переводит значения времени выполнения в типы.Идея очень простая:
Мы делаем функцию со switch, скажем на сто элементов, эта функция должна вызывать любой функтор со значением mpl::int< N >, где N соответствует значению переменной, переданной в функцию. Если нас просят преобразовать другой интервал, мы просто делаем дополнительные махинации: смещение и разделение на бины. Так например если нас просят преобразовать в тип число в интервале 56...156, нужно просто каждый раз вычитать из переменной, которую нам передали 56, а затем, после преобразования в тип, прибавлять 56 (но уже к типу!). Если же нас просят преобразовать число из интервала 200..400, надо сначала разделить его на участки "по 100", затем вычислить, номер участка и смещение внутри участка.Наверное, я непонятно объясняю, поэтому вот много убойного кода.

Замечания:

0.
Многа буков :(

1.
В реальном мире switch имеет 100 case-ов (значение подбиралось экспериментально, код работоспособен при любом значении >= 2).

2.
В реальном мире switch case генерируются макросами.

3.
Работает это быстро. Очень быстро. За это приходится расплачиваться такими вот зверскими выражениями. Простую реализацию через хвостовую рекурсию компилятор не смог оптимизировать до switch :(

Применение

Теперь можно делать так:

1. Создание любых объектов, достаточно добавить тип объекта в список известных типов. Ранее при добавлении нового типа объектов было необходимо искать все switch case по типам, теперь switch case нету вообще, а это означает, что все новые типы объектов поддерживаются «из коробки». Этот пример иллюстрирует пропадание switch case.

Было:

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;
};

Стало:

//! 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 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. Изменение поведения классов, находящихся в середине дерева наследования, в зависимости от реального типа объекта, не используя dynamic_cast (подход с CallWithType приблизительно в 50 раз быстрее на нашей иерархии классов):

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 virtual func, which returns descriptor of the real object type.
// Implementation shown in previous example (you don't need to write this function by hands)
if( IsKindOf< ISettable >( this->TypeDescriptor() ) )
{
// Do something
}
else
{
// Do something else
}

3. Возможность оперировать с переменной содержащей дескриптор типа непосредственно как с типом. Это очень сильно помогает во время процедуры определения того, какой же все таки тип объекта надо создать (в случае, если тип зависит от множества внешних факторов):

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;
}