How to implement BOOST_TYPEOF?

Question

Here I would like to understand the general idea of implementing BOOST_TYPEOF. I mean the code may be OK, but I guess the code will not be simple, as it is in real Boost implementation. Therefore, I would like to understand the idea of BOOST_TYPEOF implementation. Does it use compiler functions (some API) to understand the type of an expression in compile time?

Answer 1

At core, Boost::Typeof uses a sizeof non-evaluated context to convert the type of an expression into an integer, and then converts it back to a type.

Consider:

template<int N> struct sizer { char value[N]; };

sizer<1> encode(char);
sizer<2> encode(unsigned char);
sizer<3> encode(signed char);
sizer<4> encode(bool);
...

template<int N> struct decode {};
template<> struct decode<1> { typedef char type; };
template<> struct decode<2> { typedef unsigned char type; };
template<> struct decode<3> { typedef signed char type; };
template<> struct decode<4> { typedef bool type; };

#define TYPEOF(expr) decode<sizeof(encode(expr))>::type

Now, given an expression that evaluates to any char type or to bool, we can write:

TYPEOF(expr) var = expr;

Boost::Typeof is essentially an expansion of this idea, which was originally invented by Brian Parker in 1997; see A Portable "typeof" Operator for a discussion and history of the idea.

---

Templates are a bit of a problem for this scheme; something as simple as std::pair gives the square of the type space, even before recursion. Boost::Typeof solves this by encoding the template type and its parameter types into successive slots of a compile time linked list:

template<typename List> struct sizer {
    char item0[List::at<0>];
    char item1[List::at<1>];
    char item2[List::at<2>];
    ...
};

template<typename List> struct encode_type<List, char>: append<List, 1> {};
template<typename List> struct encode_type<List, unsigned char>: append<List, 2> {};
template<typename List, typename S, typename T>
struct encode_type<List, std::pair<S, T> >:
    encode_type<encode_type<append<List, 99>, S>, T> {};

template<typename Iter> struct decode_type<1, Iter> {
    typedef char type;
    typedef Iter iter;
};
template<typename Iter> struct decode_type<2, Iter> {
    typedef unsigned char type;
    typedef Iter iter;
};
template<typename Iter> struct decode_type<99, Iter> {
    typedef typename decode_type<Iter::next::value, Iter::next>::type S;
    typedef typename decode_type<Iter::next::value, Iter::next>::iter S_iter;
    typedef typename decode_type<S_Iter::next::value, S_Iter::next>::type T;
    typedef typename decode_type<S_Iter::next::value, S_Iter::next>::iter T_iter;
    typedef std::pair<S, T> type;
    typedef T_iter iter;
};

template<typename List, typename T>
sizer<typename encode_type<List, T>::type> encode(const T&);

template<typename List> struct decode {
    typedef typename decode_type<List::begin::value, List::begin>::type type; };

#define TYPEOF(expr) decode<list<
    sizeof(encode(expr).item0),
    sizeof(encode(expr).item1),
    sizeof(encode(expr).item2),
    ...
    > >::type

This assumes an existing compile-time linked list implementation. You'll notice that the decoder for std::pair consumes as many items from the list iterator as required for its parameter types; this is essentially a straight translation of equivalent functional code in a language with non-mutable types.

On the two lines marked as ellipsis ... we are limited to a fixed level of complexity in types (i.e. the number of templates and types making up a type we want to deduce). Boost::Typeof has a default of 50 for this limit, but will let you reduce it for efficiency or increase it for crazily complex programs.

Answer 2

It is based on the idea that sizeof is a compile time operator and can be used as template argument. This way we can assign an integer to each type and that integer can be used to get back to the type. The drawback is that each type has to be registered manually.

E.g.:

#include <boost/preprocessor/stringize.hpp>
#include <cstddef>
#include <iostream>

template<size_t> struct TypeId;

#define REGISTER_TYPE(T, id)                                    \
template<> struct TypeId<id> {                                  \
    char value[id];                                             \
    typedef T type;                                             \
    static char const* const name;                              \
};                                                              \
char const* const TypeId<id>::name = BOOST_PP_STRINGIZE(T);     \
TypeId<id> type_to_id(T);

#define TYPEID_(value) TypeId<sizeof(type_to_id(value))>
#define TYPEOF(value) typename TYPEID_(value)::type
#define TYPENAME(value) TYPEID_(value)::name

REGISTER_TYPE(int, 1)
REGISTER_TYPE(unsigned int, 2)
// and so on for all built-in types

int main() {
    int x;
    TYPEOF(x) y;
    std::cout << TYPENAME(y) << '\n';
}

Output:

./test
int