
Boost : 
From: Brian Simpson (wheber_at_[hidden])
Date: 20030805 13:50:17
A fundamental problem encountered by boost::variant is that of invoking an
overloaded function for the correct type, where the type is not known until
runtime. As near as I can tell, all proposed solutions to this problem have
involved uncomfortable space or time tradeoffs. I have read several posts
which asked why we couldn't use a switch statementit would avoid the
expenses of the current solutions without incurring any of its own.
Until recently, I agreed with those (whose expertise I highly respect) who
said it was not possible.
However, while perusing the source for the current implementation of
boost::variant, a possible solution occurred to me.
I have spent some time fleshing out the proposed solution, and it seems to
be all standard C++ (no nonstandard). I think it might be referred to as
"sequence unrolling".
Here's how it works:
The component is called, "runtime_type_selected_invoker", and it is
templated on a type which is expected to be a model of mpl::Sequence. It
has one public static function:
<code>
template <typename Operator, typename StoragePtr>
static
BOOST_DEDUCED_TYPENAME Operator::result_type
invoke(Operator & op, StoragePtr storage, long index)
</code>
"index" indicates the type on which to invoke the Operator.
"StoragePtr" is either "void *" or "const void *", and refers to the
location of the object.
"Operator" is a model of "Operator" concept, which is identical to the
"Visitor" concept recognized by variant ("Operator" has evolved from its
originally conceived form, which is why the name is different).
Essentially, the function call,
"runtime_type_selected_invoker<seq_t>::invoke(my_op, storage, index);"
results in the following function call:
"my_op(*(static_cast<mpl::at_c<seq_t, index>::type *>(storage)));"
The implementation reasoning runs like this: It seems that the problem with
building a switch statement to implement type selection is that a switch
statement can't be built incrementallyit is a syntactic construct. (The
currently accepted solution builds an elseifthen statement incrementally
by means of a recursive function template instantiation.) But what if you
could give a template the number of types among which you want to select in
addition to the sequence? Could it then implement a switchbased selection
on the first 'n' types in the sequence? The answer turns out to be yes, up
to a point. The mechanism, in this case, is partial template
specialization.
Let us define a template class:
template <typename Sequence, long n>
class n_ary_rtts_invoker;
How does it produce a switch statement based on 'n'? Well, if we limit
ourselves to a specific value of 'n', we can express it. For example, here
is a specialization for 'n'==3:
<code>
template <typename Sequence>
class rtts_invoker<Sequence, 3>
{
public:
template <typename Operator, typename StoragePtr>
static
BOOST_DEDUCED_TYPENAME Operator::result_type
invoke(Operator & op, StoragePtr storage, long index)
{
switch (index)
{
case 0:
return op(*(static_cast<mpl::at_c<Sequence, 0>::type
*>(storage)));
case 1:
return op(*(static_cast<mpl::at_c<Sequence, 1>::type
*>(storage)));
case 2:
return op(*(static_cast<mpl::at_c<Sequence, 2>::type
*>(storage)));
}
}
};
</code>
Given this specialization of n_ary_rtts_invoker, we can setup runtime type
selection on the first three types in a sequence. To be more specific, if
we instantiate a type, "n_ary_rtts_invoker<my_seq, 3>", the template
machinery should match the above specialization, and the statement,
"n_ary_rtts_invoker<my_seq, 3>::invoke(my_op, storage, index)", will make a
selection among the first three types in 'my_seq' via a switch statement
(assuming 0<=index<3).
If we define a similar specialization for values 1 and 2, we can setup
selection on sequences of size 13.
The general case devolves into an elseifthen:
Let us assume that we have specializations up to a certain number,
'max_specialization_count'. Then we know that we can get switchbased
runtime type selection ("rtts") on any mpl::Sequence whose size is not
greater than 'max_specialization_count'. To provide rtts for Sequences
whose size is greater than 'max_specialization_count', we provide a more
general template definition. Its "invoke" function sets up a switchbased
selection among the first 'max_specialization_count' types, and then sets up
a (recursive) selection among the remaining types.
I am including two source files. One is the runtime_type_selected_invoker,
the other is boost\variant\variant.hpp(ver1.41), with changes made to take
advantage of switchbased rtts (see "variant::raw_apply_visitor" and
"variant::destroy_content").
The only caveats (that I can think of...) are:
1)compiled and tested on gcc3.2.2 and Borland Builder 5  therefore no
guarantees with other compilers,
2)no workarounds for BOOST_NO_VOID_RETURNS are implemented. Actually, I
tried to improve on the workarounds in variant's visitor apply codewhat
selfrespecting hacker with enough time wouldn't?but didn't come up with
anything worth publishing. As near as I can tell, the two compilers I have
access to don't suffer from the problem, so it would have been untested
anyway.
Questions or comments?
p.s. I must acknowledge Itay's and Eric's efforts in the current
implementation of boost::variant. I've learned a lot just from studying the
code. It was while I was browsing the recently added implementation of
switched type selection based on the variadic template parameters that this
idea occurred to me. Also, the implementation depends vitally on the work
of those who put together boost::mpl and boost::preprocessor.
_________________________________________________________________
Protect your PC  get McAfee.com VirusScan Online
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk