[boost] switch-based runtime type selection (for variant)

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