Alo Sarv
lead developer

Donate via
MoneyBookers

Latest Builds

version 0.3
tar.gz tar.bz2
Boost 1.33.1 Headers
MLDonkey Downloads Import Module Development
Payment completed
Development in progress.
Developer's Diary
irc.hydranode.com/#hydranode

Friday, December 23, 2005

When all you have is a hammer...

I'v always been fascinated about template metaprogramming - a modern C++ paradigm that allows doing things at compile time. Boost libraries rely heavily on this, and have quite a lot of support libraries for the topic as well - Boost.MPL being the most famous, but is backed up by Boost.TypeTraits, Boost.Tuple and many more.

When doing template (e.g. generic) programming, you do not know at the code writing time what types you may be manipulating. A trivial, but motivating example:
template<typename T> void process(T t) { t.foo(); }
Here, the function process() has no knowledge about the type being passed to it, but it calls the foo() member function on the type. If the type doesn't have the function, you get a compile-time error.

However, there's one limitation - the function can only take arguments by value or reference, it cannot handle pointers - it would need to do t->foo() when a pointer is passed to it. A naive approach to the problem would simply provide additional specializations for the function:
template<typename T> void process(T *t) { process(*t); }
However, this has the problem of requiring the same set of overloads for every function that needs this functionality. A more generic solution is needed, something that is capable of handling pointers, pointers-to-pointers, smart pointers and so on. What we'r looking for is syntax like this, and have everything work behind the scenes:
template<typename T> void process(T t) { unchainPtr(t).foo(); }
In order to "unchain" the pointer, we start out by providing a functor that is capable of recursivly "de-pointering" a given type. We cannot solve this with simple overloaded function templates, due to ambiguouties with const overloads, so we need actually two different functors, which guarantee const-correctness:
template<typename Class>
struct UnchainPtrImpl {
// non-const overloads
Class& operator()(Class &x) const { return x; }

template<typename ChainedPtr>
Class& operator()(ChainedPtr &x) const {
return operator()(*x);
}

Class& operator()(boost::reference_wrapper<Class> &x) const {
return operator()(x.get());
}
};

template<typename Class>
struct UnchainConstPtrImpl {
// const overloads
const Class& operator()(const Class &x) const { return x; }

template<typename ChainedPtr>
const Class& operator()(const ChainedPtr &x) const {
return operator()(*x);
}

const Class& operator()(
const boost::reference_wrapper<const Class> &x
) const {
return operator()(x.get());
}
};
However, now we have another problem - we need to make a selection between these two functors, at compile-time, and choose one of them, depending on whether we want const or non-const variant. MPL to the rescue:
template<typename Class, typename ChainedPtr>
Class unchainPtr(ChainedPtr ptr) {
return boost::mpl::if_<
boost::is_const<ChainedPtr>,
UnchainConstPtrImpl<Class>, UnchainPtrImpl<Class>
>::type()(ptr);
}
template<typename Class, typename ChainedPtr>
void process(ChainedPtr ptr) {
unchainPtr<Class>(ptr).foo();
}
process<X>(new X);
Looks good, with one problem - it's inconvenient to always specify the class type when calling the function - we should be able to do better. In fact, all we really need to do is deduce the raw class name, e.g. X, from a type name like X*, X& or similar. Bring out the heavy guns and let's go. I'm not going to walk you through the entire process, but suffice to say, it took several hours of testing and tweaking before finally arriving at a solution that is capable of doing what we need. The resulting code is:
// main template of the loop type isn't implemented. One of 
// the specializations below are chosen always.
template<
typename T,
bool Final = boost::mpl::or_<
boost::is_pointer<T>, boost::is_reference<T>
>::type::value
> struct Next;

// this is selected when Final is true, e.g. T is a pointer or reference type.
// we recurse by "calling" the getType metafunction again, but after removing
// reference and/or pointer-ness from the type.
template<typename T>
struct Next<T, true> {
typedef typename getType<
typename boost::remove_reference<
typename boost::remove_pointer<T>::type
>::type
>::type type;
};

// this ends the Next recursion - the passed type isn't a pointer or reference,
// so just typedef it as itself and don't recurse into getType anymore.
template<typename T>
struct Next<T, false> {
typedef T type;
};

// if the passed is pointer or reference, we call Next, which removes
// the offending part of the type, and calls us back, so we loop
// around until the passed type isn't a pointer/ref type anymore,
// and the resulting type is available as the 'type' typedef.
template<typename T>
struct getType {
typedef typename boost::mpl::if_c<
!boost::mpl::or_<boost::is_pointer<T>,
boost::is_reference<T> >::type::value,
T, typename Next<T>::type
>::type type;
};
// these specializations can be user-defined, but here we show how boost
// smart-pointers can be added to the mix.
template<typename T>
struct getType<boost::shared_ptr<T> > {
typedef typename Next<T>::type type;
};
template<typename T>
struct getType<boost::weak_ptr<T> > {
typedef typename Next<T>::type type;
};
template<typename T>
struct getType<boost::intrusive_ptr<T> > {
typedef typename Next<T>::type type;
};
// the final function template - added getType metafunction calls to the mix
template<typename ChainedPtr>
typename getType<ChainedPtr>::type&
unchainPtr(ChainedPtr ptr) {
return typename boost::mpl::if_<
boost::is_const<ChainedPtr>,
UnchainConstPtrImpl<typename getType<ChainedPtr>::type>,
UnchainPtrImpl<typename getType<ChainedPtr>::type>
>::type()(ptr);
}
This solution works flawlessly. It can handle even rather obscure types, such as const int **const&, shared_ptr<int*&>& etc. The only offset with this is that it crashes gcc4 (works on earlier versions of the compiler), in the third line of the sample (bool Final handling).

However, then it hit me - there's actually a LOT simpler way of doing all this. If we replace the getType mechanism with this:
template<typename T>
struct getType {
typedef T type;
};
template<typename T>
struct getType<T*> {
typedef typename getType<T>::type type;
};
template<typename T>
struct getType<T *const> {
typedef typename getType<T>::type type;
};
template<typename T>
struct getType<T&> {
typedef typename getType<T>::type type;
};// add smart_ptr specializatios as needed
Everything works even better. The getType metafunctions recurse into themselves, just as the Next template above, and the recursion is stopped when no specialization can be chosen, and thus the primary template is chosen, which ends the recursion. Flawless, clean, extendable and simple. Talk about having a hammer and everything looking like a nail - the first hit on getType was major overkill (granted, it was pretty fun 3 hours fighting with it).

The underlying reason for writing this was actually that I'm generalizing WorkThread API into a template class that can handle arbitary types of jobs, and that we can create more than one WorkThread, for different purposes. IOThread simply becomes a typedef (or a derived class), and we'll be having other worker threads for other things - for example DNS resolution will be done in such a worker thread as well. Given we'll have a simple easy-to-use and safe API for doing jobs in other threads, we bring hydranode more multi-threading, thus gaining response times and speed on dual- and multi-core systems, which are not far from becoming a standard.

Since cyberz wanted to use the final code in "other places" as well, I decided to licence this header under Boost software licence, which is more permissive. The header can be viewed in complete here, and the test-app here if anyone is interested. Frankly I'm surprised I didn't find something like this in Boost anywhere - maybe they have it stashed somewhere in the back room, but all I saw was few libraries using local hacks to do this (actually the UnchainPtrImpl template was copied from multi_index library header), so I'll take this up with Boost ppl - maybe even submit this code to them :)

Hope I didn't bore you guys to death with highly-specific code-talk. Will be more human-readable post next time :)

Madcat



Comments:
Quite interesting, this is opportunity to strenghthen my poor C++ knowledge. :-)
 
Madcat for president! ;)

Seriously, you are becoming a truely C++ guru, maybe you will be soon on the C++ comitee... ;)
 
If i want fashion and girl i wouldn't be here :)

if i want funny comment i would be on ./

i'm here to learn things like that :)

and wait for the gui process to begin ;)
 
I am waiting for the GUI too!
 
That's exactly why I dropped heavy c++ long time ago. A template metafunction that recurses into itself?!? There's like 50 years of computer science history right in that sentence. Flawless, clean, extendable, simple...voodoo magic. Let's hope this stuff remains restricted to standard libraries and such, otherwise only the c++ comitee will know how to do it (or have the patience to) . Some say LISP died because of similar things...

Congrats Madcat for your deep level of understanding and your altruism for sharing with us common folk. This is stuff that's hard to find even on books.
GC
 
Post a Comment



<< Home

This page is powered by Blogger. Isn't yours?