Night of the Living Dead Code

If only there were a way to get the type of an expression without evaluating the expression. There is! The unique properties of the conditional operator allow us to sidestep the issue entirely. The ENCODED_TYPEOF macro defined below encodes the type of an expression without evaluating it. Read on to see how it works.

// a simple type wrapper
template< class T > struct type2type {};

// convert an expression of type T to an
// expression of type type2type<T>
template< class T >
type2type< T > encode_type( T const & t )
{
  return type2type< T >();
}

// convertible to type2type<T> for any T
struct any_type
{
  template< class T >
  operator type2type< T > () const
  {
       return type2type< T >();
  }
};

// convert an expression of type T to an
// expression of type type2type<T> without
// evaluating the expression
#define ENCODED_TYPEOF( container ) \
  ( true ? any_type() : encode_type( container ) )

For any expression expr of type Expr, ENCODED_TYPEOF(expr) evaluates to type2type<Expr> , and (here's the important part) the expression expr is not evaluated! There is some subtlety in ENCODED_TYPEOF, so it is worth a few words to describe what's going on.

At the heart of ENCODED_TYPEOF is the conditional operator. As you probably know, the conditional operator behaves like an if/else statement. It takes three operands: (1) a Boolean condition, (2) an expression to evaluate if the condition is true, and (3) an expression to evaluate if the condition is false. The most familiar use of the conditional operator is to implement the infamous min/max macros:

#define min(a,b) ( (a) < (b) ? (a) : (b) )
#define max(a,b) ( (a) > (b) ? (a) : (b) )

Looks simple, right? Don't be fooled, there's more going on here than meets the eye. A conditional expression is just that—an expression. As such, it must have a type. The type of a conditional expression depends on the types of both its second and third operands—the two branches of the condition. Figuring out what the resulting type of a conditional expression is from the types of its two branches is enough to give even the most seasoned compiler writer a splitting headache.

Glossing over some complications which become important later, it works as follows: for a conditional expression ( b ? x : y ) where x is an expression of type X and y is an expression of type Y where X and Y are different, and one is a class type, the compiler checks to see if X can be converted to Y and if Y can be converted to X. If only one, unambiguous conversion is found, that is the one that gets used. Things get more complicated still, but this is enough to understand ENCODED_TYPEOF.

If you recall, ENCODED_TYPEOF(container) expands to (true ? any_type() : encode_type(container)). So X is any_type and Y is type2type<Container>. Now we try the conversions. type2type<Container> cannot be converted to any_type, but any_type can be converted to type2type<Container> because it defines the appropriate conversion operator. We have found one, unambiguous conversion, so we're done. The type of ENCODED_TYPEOF(container) is type2type<Container>.

You may be thinking this is needlessly convoluted. After all, couldn't we just use encode_type(container) without the conditional operator and get the same result? No, because that would have caused container to be evaluated. With the conditional operator, only one branch of the condition is ever executed. In this case, since the condition is always true, the first branch will always be taken. The second branch is "dead code"—it will never execute—yet it extends a ghostly finger into the land of the living and exerts its influence on the conditional expression's type. Spooky!

By using ENCODED_TYPEOF in our FOREACH macro, we can avoid reevaluating the container expression needlessly. All we have to do is change our function templates to take type2type<Container> instead of Container const &, as follows:

template< class Container >
void next( auto_any_base const & iter, type2type<Container > )
{
   ++auto_any_cast< typename Container::const_iterator >( iter );
}

// elsewhere ...
#define FOREACH( item, container )                \
   auto_any_base const & iter = begin( container ); \
   ...                                     \
   next( iter, ENCODED_TYPEOF( container ) ); \
   ...

The call to begin() above evaluates container and returns container.begin(). It gets bound to the const reference a-la the ScopeGuard trick. And then the call to next() increments the iterator without reevaluating container. Perfect!

<< Page 2 of 4 >>


	Web Artima.com