[boost] "typeof" implementation idea

From: Arkadiy Vertleyb (vertleyb_at_[hidden])
Date: 2004-04-20 21:51:43

"David Abrahams" <dave_at_[hidden]> wrote

> That's the basic idea behind all typeof() emulations that I've ever
> seen.  They all require some type registration to associate a
> compile-time integral constant with a type.  The innovation that Steve
> brought, IIUC, was that with the registration of only class types, the
> rest of the transformations possible in the type system could be
> encoded by the library automatically.  For example, if you register
> class Foo, then the library can generate encodings for Foo*, Foo[2],
> Foo**, int (Foo), Foo(*)(Foo,Foo), etc., so you don't have to register
> those types.  The problem is that those numbers can get very large...

Right.  What I am even more interested in, is the ability to generate
encodings of complicated templates.  Say I registered int, std::vector, and
mpl::vector2, and the library should be able to work with std::vector<int>,
mpl::vector2<std::vector<int>, mpl::vector2<int, int> >, etc.  It looks like
this can be solved pretty easily.  I imagine that Boost.Lambda, for example
might also benefit from the ability to encode/decode templates (and maybe
Spirit, but I am not sure).

> My guess is that manipulating array types in that way has a lower
> cost at compile-time than using a vector_c, though using mpl probably
> yields much nicer library code and vector_c is more portable.

I don't suspect my solution is very compile-time efficient.  But I don't
have enough knowledge of compilers internals to estimate this.  I believe
the real advantage is in is simplicity.  Anyway, here it is...

Let's recall that to achieve our goal we have to:

1) Pass our expression to a function template, like:

template<class T> SOMETHING foo(const T&);

2) inside foo() encode our type into a compile-time list of integers;
3) somehow manage to pass this list through the function boundaries;
4) decode the type.

The most chalanging is 3.

Let's define the following template:

template<class N> struct sizer
{
    char_[N::value];
};

The whole purpose of this is to create classes with a given sizeof (to be
completely accurate we have to then divide this by sizeof(char)).

Next template is what it is all about:

template<class IntList> struct multi_int
{
    typedef IntList int_list;

    template<class T> sizer<typename mpl::apply_if<
        typename mpl::less<T, typename mpl::size<int_list>::type>,
        mpl::at<IntList, T>,
        mpl::identity<mpl::int_<1> >
    >::type> get(const T&);
};

So, if we have an object of this class, x, then
sizeof(x.get(mpl::int_<n>())) defines the nth element of the list, and
out-of-range values produce 1.

The list can be reproduced like, say:

#define BOOST_RTL_TYPEITEM(Expr, N)\
mpl::int_<sizeof(Expr.get(mpl::int_<N>()))>

mpl::vector<\
    BOOST_RTL_TYPEITEM(x, 0)
    , BOOST_RTL_TYPEITEM(x, 1)
    ...
    , BOOST_RTL_TYPEITEM(x, N)
>

Where it can be generated by the preprocessor for a fairly large N.  The
reproduced list is larger than the original one, and is 1-padded.  The
encoding scheme I use does not require to know where the list ends, so this
doesn't matter.

This is basically it.  The return type of the function foo above (sorry for
such name) is going to be multi_int<encode<T>::type>, where T is the
original type, and encode template works accordingly to some encoding
scheme.

The encoding scheme to choose is a separate issue.  In my example I encode
templates by adding the encodings of its parameters to the code of template
itself.  So, if int is 1, std::vector is 2, and mpl::vector2 is 3, the above
example:

mpl::vector2<std::vector<int>, mpl::vector2<int, int> >

becomes

3 2 1 3 1 1

Also note that all templates with one parameter behave similarly, so only
one registration macro is required.  Another macro is required to register
templates with two parameters, etc.

> For what it's worth, I'm pretty sure I know how to solve the problem
> that most typeof() implementations strip top-level references.  See
> boost/iterator/is_lvalue_iterator.hpp for a demonstration.

Cool.  I imagine pointers are pretty easy, but references surely represent a
big problem...

I will follow up with the working sketch...

Regards,
Arkadiy