From: Brian Simpson (wheber_at_[hidden])
Date: 2003-08-05 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 statement--it 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 non-standard). 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 incrementally--it is a syntactic construct. (The
currently accepted solution builds an else-if-then 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 switch-based 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 1-3.
The general case devolves into an else-if-then:
Let us assume that we have specializations up to a certain number,
'max_specialization_count'. Then we know that we can get switch-based
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 switch-based
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 switch-based 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 code--what
self-respecting 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