Template programming with MPL — XOR example
The Boost extension libraries are a treasure trove of brilliant hackery. The template usage and metaprogramming throughout the libraries is particularly interesting. But it’s also confusing, especially when you first see it. The C++ template language is like a functional language with limited types and obtuse syntax. It has no loops and allows no side effects (no changes to objects or variables after construction). It uses the constructs of C++ in unexpected ways and is very different from normal C++ programming.
The best way to get an idea of how template programming works is to look at it. So here are some examples of how to implement a very simple template function, an XOR predicate that takes two boolean arguments and returns a third.
As a base we start with the templates in type_traits which are included in TR1. We will also use the Boost MPL library, which provides predicates like and_<..>, or_<..>, and not_<..>. MPL also provides the boolean template class bool_<..> and it’s two type-values true_ and false_.
# include <boost/type_traits.hpp> using boost::is_same; // is_same< A, B > is a template function // that compares types A and B. # include <boost/mpl/logical.hpp> using boost::mpl::bool_; using boost::mpl::true_; using boost::mpl::false_; using boost::mpl::and_; using boost::mpl::or_; using boost::mpl::not_; # include <boost/mpl/assert.hpp> // BOOST_MPL_ASSERT(..) and // BOOST_MPL_ASSERT_NOT(..)
In template programming, you assign variable values with typedef. true_ and false_ are variables that evaluate to bool<true> and bool<false>. You can assign them over and over again as long as the value does not change. Typedef variables never change once they are assigned, so they’re not really “variable”. They are constant variables (which sounds like an oxymoron). There is no untypedef.
// true_ is already assigned, but you can // assign it over and over again to an // identical value. typedef bool_<true> true_; typedef bool_<true> true_; typedef bool_<true> true_; // not_<false_> is the same as true_. typedef not_<false_>::type true_;
You can use is_same< A, B > to test if two types are the same. Boost MPL provides a useful ASSERT.
BOOST_MPL_ASSERT( (is_same< true_, true_ >)); BOOST_MPL_ASSERT_NOT( (is_same< true_, false_ >)); BOOST_MPL_ASSERT( (is_same< true_, bool_<true> >));
true_ and false_ are self evaluating. You evaluate an expression or a variable by appending ::type.
// true_, false_, bool_<true>, etc are self evaluating. BOOST_MPL_ASSERT( (is_same< true_, true_::type >)); BOOST_MPL_ASSERT( (is_same< true_, true_::type::type >)); // not_<false_> is an expression. // Tt only yields _true after you evaluate it. BOOST_MPL_ASSERT_NOT( (is_same< true_, not_<false_> >)); BOOST_MPL_ASSERT( (is_same< true_, not_<false_>::type >)); BOOST_MPL_ASSERT( (is_same< true_, or_<true_>::type >));
You may have noticed BOOST_MPL_ASSERT( (..)) has double parentheses around its argument. This is needed because the argument is usually an expression containing commas, and the preprocessor will mis-interpret the commas unless they are buried in parentheses.
You might be tempted by the following macros. But they only work with type expressions that contain no commas.
# define ASSERT_same_types( A, B) \
BOOST_MPL_ASSERT( (is_same< B , A >))
# define ASSERT_different_types( A, B) \
BOOST_MPL_ASSERT_NOT( (is_same< B , A >))
ASSERT_same_types( int, int);
ASSERT_different_types( char, int);
ASSERT_same_types( void(*)(int), void(*)(int) );
ASSERT_different_types( false_, true_::type::type);
// These do not work because of the commas!
// Putting parens around the args doesn't work either.
/*
ASSERT_same_types( true_, and_<true_,true_>::type >));
ASSERT_same_types( int(int,char), int(int,char) >));
ASSERT_same_types( (int(int,char)), (int(int,char)) >));
*/
Notice that and_<..> evaluates its arguments while is_same<..> does not. (This is not strictly true since and_<..> short circuits, but in these examples we can treat it like it evaluates all its args.)
// is_same<..> does not eval its args. Otherwise // you could not use it with types like int. BOOST_MPL_ASSERT( (is_same< int, int >)); // These look the same, but they're not because args // are not evaluated. BOOST_MPL_ASSERT_NOT( (is_same< true_, not_<false_> >)); // You can force evaluation. Only the second arg needs // to be eval'ed in this case. BOOST_MPL_ASSERT( (is_same< true_, not_<false_>::type >)); // Here we force eval of the outer not_<..> because it is an // arg to is_same<..>. But the args to and_<..>, or_<..>, // and not_<..> are automatically evaluated. BOOST_MPL_ASSERT( (is_same< true_, not_<or_<and_<not_<false_>>>>::type >)); // You can force evaluation of args to and_<..> etc, but // the results will just be eval'ed again. Since the // results are self evaluating (true_ or false_), you can // redundantly evaluate them several times and the // expressions will still work. BOOST_MPL_ASSERT( (is_same< true_, not_<or_<and_<not_<false_>::type>::type::type>>::type >));
Now we can finally get to our example template predicate. Here is a definition of xor_test<..> that evals its args. It can be used with MPL functions like and_<..> and or_<..>.
template< typename A, typename B >
struct xor_test
: bool_< A::type::value ^ B::type::value >
{ };
BOOST_MPL_ASSERT_NOT( (xor_test< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_test< false_, false_ >));
BOOST_MPL_ASSERT( (xor_test< true_, false_ >));
BOOST_MPL_ASSERT( (xor_test< false_, true_ >));
BOOST_MPL_ASSERT( (xor_test< false_, or_<true_> >));
I don’t like using the bitwise XOR operator ^ here with boolean args, although it works. I’d prefer to use a boolean operator like ^^ if it existed. Also, I considered replacing : bool< A::type::value ^ B::type::value > with : bool< A::value ^ B::value > because X::value also evaluates X. It works with and_<..>, or_<..> and not_<..> because these classes mimic bool_<..> and provide value as well as type.
When you define an MPL-style template function, you need a typedef XX type; in the template struct to evaluate the template expression. You get that if you inherit from bool_<..>, or you can typedef XX type; yourself.
You also need to figure out if the predicate should evaluate true_ or false_. You can specify that with logic or with template specialization.
The first XOR predicate example inherits from bool_<..> and calculates true/false with and_<..>, or_<..>, and not_<..>.
// xor_1<..> inherits from bool_<..>
template< typename A, typename B >
struct xor_1
: or_< and_< A, not_< B > >, and_< not_< A >, B > >::type
{ };
BOOST_MPL_ASSERT_NOT( (xor_1< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_1< false_, false_ >));
BOOST_MPL_ASSERT( (xor_1< true_, false_ >));
BOOST_MPL_ASSERT( (xor_1< false_, true_ >));
BOOST_MPL_ASSERT( (xor_1< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_1< or_<true_>, false_ >));
You don’t have to evaluate the supertype of xor_1<..>. You could say or_<..> instead of or_<..>::type. This stops evaluation of the top-level or_<..>, and it means we are not inheriting directly from bool_<..> but rather from or_<..>. But we still evaluate to a bool_<..> type.
The second XOR example typedefs type explicitly. It also typedefs value_type and tag and defines value and operator bool() (the same as operator value_type()). These make it look more like bool_<..> and work better with MPL.
// xor_2<..> typedefs type instead of inheriting
template< typename A, typename B >
struct xor_2
{
typedef
or_< and_< A, not_< B > >, and_< not_< A >, B > >
type;
typedef bool value_type;
static const value_type value = type::value;
operator value_type() { return value; }
typedef bool_<value> tag;
};
BOOST_MPL_ASSERT_NOT( (xor_2< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_2< false_, false_ >));
BOOST_MPL_ASSERT( (xor_2< true_, false_ >));
BOOST_MPL_ASSERT( (xor_2< false_, true_ >));
BOOST_MPL_ASSERT( (xor_2< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_2< or_<true_>, false_ >));
The third example inherits from either true_ or false_ and uses specialization to choose which. Template specialization tends to leave parameters un-evaluated. We wrap the non-evalating base class so we can evaluate explicitly.
// specialization and inheritance
template< typename A, typename B >
struct xor_3_no_eval
: false_
{ };
template< >
struct xor_3_no_eval< true_, false_ >
: true_
{ };
template< >
struct xor_3_no_eval< false_, true_ >
: true_
{ };
template< typename A, typename B >
struct xor_3
: xor_3_no_eval< typename A::type, typename B::type >::type
{ };
BOOST_MPL_ASSERT_NOT( (xor_3< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_3< false_, false_ >));
BOOST_MPL_ASSERT( (xor_3< true_, false_ >));
BOOST_MPL_ASSERT( (xor_3< false_, true_ >));
BOOST_MPL_ASSERT( (xor_3< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_3< or_<true_>, false_ >));
The last example predicate typedefs explicitly instead of inheriting from bool_<..>. It also uses a recursive type definition.
// specialization and calculation
template< typename A, typename B >
struct xor_4_no_evalB
{
// We only ever get here if B evals to something
// other than true_ or false_. Maybe we should
// flag this:
// BOOST_STATIC_ASSERT( false);
typedef false_ type;
};
template< typename A >
struct xor_4_no_evalB< A, false_ >
{
// recursive type definition uses xor_4_no_evalB<..>
typedef
typename xor_4_no_evalB< not_< A >, true_ >::type
type;
};
template< typename A >
struct xor_4_no_evalB< A, true_ >
{
typedef
typename not_< A >::type
type;
};
template< typename A, typename B >
struct xor_4
: xor_4_no_evalB< A, typename B::type >::type
{
typedef bool value_type;
static const value_type value = type::value;
operator value_type() { return value; }
typedef bool_< value > tag;
};
BOOST_MPL_ASSERT_NOT( (xor_4< true_, true_ >));
BOOST_MPL_ASSERT_NOT( (xor_4< false_, false_ >));
BOOST_MPL_ASSERT( (xor_4< true_, false_ >));
BOOST_MPL_ASSERT( (xor_4< false_, true_ >));
BOOST_MPL_ASSERT( (xor_4< false_, or_<true_> >));
BOOST_MPL_ASSERT( (xor_4< or_<true_>, false_ >));
So there you have it — five examples of a very simple template XOR predicate.
C++ — cast_away_const(..) revisited
In my last post I talked about writing a cast_away_const(..) function. With const_cast<..>(..) you have to specify the target type explicitly, but you can leave that out with cast_away_const(..). You can see the difference in this example.
const int c = 0; int& r1 = const_cast< int& >( c); int& r2 = cast_away_const( c);
cast_away_const(..) as it was written in the last post will not warn you if you are using it unnecessarily. (Neither will const_cast<..>(..).) Since I like to avoid casts of all types, and since I’d never cast unless I was sure I needed to, I’d like cast_away_const(..) to tell me if I’m using it frivolously.
Fortunately, this is easy to achieve. Just define non-const overloads.
# include <boost/static_assert.hpp>
template< typename T >
T&
cast_away_const( const T& a)
{
return const_cast< T& >( a);
}
template< typename T >
T&
cast_away_const( T& a)
{
// cast_away_const(..) called
// with non-const param
BOOST_STATIC_ASSERT( false);
return a;
}
template< typename T >
T*&
cast_away_const( const T*& a)
{
return const_cast< T*& >( a);
}
template< typename T >
T*&
cast_away_const( T*& a)
{
// unnecessary const cast
BOOST_STATIC_ASSERT( false);
return a;
}
template< typename T >
T* const &
cast_away_const( const T* const & a)
{
return const_cast< T* const & >( a);
}
template< typename T >
T* const &
cast_away_const( T* const & a)
{
// unnecessary const cast
BOOST_STATIC_ASSERT( false);
return a;
}
I prefer using a macro to make this more compact.
# include <boost/static_assert.hpp>
# define DEFINE_CAST_AWAY_CONST( TYPE_SUFFIX) \
\
template< typename T > \
T TYPE_SUFFIX \
cast_away_const( T TYPE_SUFFIX a) \
{ \
BOOST_STATIC_ASSERT( false); \
return a; \
} \
\
template< typename T > \
T TYPE_SUFFIX \
cast_away_const( const T TYPE_SUFFIX a) \
{ \
return const_cast< T TYPE_SUFFIX >( a); \
}
DEFINE_CAST_AWAY_CONST( & )
DEFINE_CAST_AWAY_CONST( * & )
DEFINE_CAST_AWAY_CONST( * const & )
# undef DEFINE_CAST_AWAY_CONST
And since I’m defining cast_away_const(..), I might as well define cast_away_volatile(..) and cast_away_cv(..) too (cv stands for const volatile). Although I’ve never found occasion to use volatile in my own code.
# define DEFINE_CAST_AWAY_FUNCTIONS_( \
FN_NAME, \
TYPE_PREFIX, \
TYPE_SUFFIX) \
\
template< typename T > \
T TYPE_SUFFIX \
FN_NAME( T TYPE_SUFFIX a) \
{ \
BOOST_STATIC_ASSERT( false); \
return a; \
} \
\
template< typename T > \
T TYPE_SUFFIX \
FN_NAME( TYPE_PREFIX T TYPE_SUFFIX a) \
{ \
return const_cast< T TYPE_SUFFIX >( a); \
}
# define DEFINE_CAST_AWAY_FUNCTIONS( \
FN_NAME, \
TYPE_PREFIX) \
DEFINE_CAST_AWAY_FUNCTIONS_( \
FN_NAME, TYPE_PREFIX, &) \
DEFINE_CAST_AWAY_FUNCTIONS_( \
FN_NAME, TYPE_PREFIX, * &) \
DEFINE_CAST_AWAY_FUNCTIONS_( \
FN_NAME, TYPE_PREFIX, * const &)
// Each line defines 6 overrides.
DEFINE_CAST_AWAY_FUNCTIONS( cast_away_const, const)
DEFINE_CAST_AWAY_FUNCTIONS( cast_away_volatile, volatile)
DEFINE_CAST_AWAY_FUNCTIONS( cast_away_cv, const volatile)
# undef DEFINE_CAST_AWAY_FUNCTIONS_
# undef DEFINE_CAST_AWAY_FUNCTIONS
And there you have it. Functions cast_away_const(..), cast_away_volatile(..), and cast_away_cv(..) that work for const T&, const T*&, const T* const &, volatile T&, volatile T*&, volatile T* const &, etc. And unlike const_cast<..>(..), these functions warn you if you use them unnecessarily.
C++ — cast_away_const(..)
The other day I was using const_cast<..>(..) (safely and appropriately, I assure you), and I wondered how difficult it would be to wrap it in a template function. I was only interested in the common simple casting cases:
- Ref-to-ref: const T& –> T&
- Ptr-to-ptr: const T* –> T*
- RefPtr-to-RefPtr: const T*& –> T*&
I did not care about deeper cases such as these.
- Buried pointer: const T*** –> T***
- Function params: void(*)( const int&) –> void(*)( int&) — illegal
const_cast<..>(..) will not cast away const buried in function types anyway.
My first thought was to try this:
// first (incorrect) try
template< typename T >
T
cast_away_const( const T a)
{
return const_cast< T >( a);
}
This does not work for a lot of reasons. Let’s look at some test cases:
// vars with const to be cast const int c = 3; const int& rc = c; const int* pc = &c; const int*& rpc = pc; // function that returns an int const int get_const_int( ); const int& get_const_ref( ); // Simple ref cast: // (const int&) --> (int&) int& r1 = cast_away_const( c); int& r2 = cast_away_const( rc); int& r3 = cast_away_const( get_const_ref( )); // Simple ptr cast: // (const int*) --> (int*) int* p1 = cast_away_const( pc); int* p2 = cast_away_const( rpc); // Simple ptr ref cast: // (const int*&) --> (int*&) int*& rp1 = cast_away_const( pc); int*& rp2 = cast_away_const( rpc); // Rvalue ptr cast: // (const int*&&) --> (int*) int* p3 = cast_away_const( &c); int* p4 = cast_away_const( &rc); // Rvalue ref cast: // (const int&&) --> (int&) // This tries to create a ref to an unnamed temp var. // This is illegal. The compiler should report an error. int& r4 = cast_away_const( get_const_int( )); /* illegal */ // Rvalue ptr ref cast: // (const int*&&) --> (int*&) // These are illegal. They will result // in a ref to an r-value (an unnamed // temporary). The compiler should // refuse these and report an error. int*& rp3 = cast_away_const( &c); /* illegal */ int*& rp4 = cast_away_const( &rc); /* illegal */
The first try above is wrong even with simple ref and ptr casts. In the simple ref case, T is interpreted as int and cast_away_const(..) returns int. The returned int is stored as a copy in an unnamed temporary variable, also known as an rvalue or r-value. Even if you could take its ref it would be a ref to the wrong variable.
In the simple ptr case, T is interpreted as const int* which is the return type. T is not int* like we hoped. The const is buried under the pointer, but the pointer value itself is not const.
My second try looked like this:
// Second try. Almost right.
template< typename T >
T*
cast_away_const( const T* a)
{
return const_cast< T* >( a);
}
template< typename T >
T&
cast_away_const( const T& a)
{
return const_cast< T& >( a);
}
This mostly works. It even correctly reports rp3 and rp4 as errors. But it does not report r4 as an error, and it incorrectly reports rp1 and rp2 as errors. With rp1 it follows this reasoning:
- pc is const int*, so T is int
- return is int*
- an unnamed temp (rvalue) int* is created
- you cannot get an int*& from an rvalue int*
With rp2 it follows the same reasoning. rpc (a const int*&) also uses the pointer version of the function and expands with T as int, so it too creates an rvalue upon return. And r4 is (wrongly) considered OK because get_const_int( ) returns const int which creates an rvalue which is passed to cast_away_const( const T&) where T is int, and which returns a non-const ref to that rvalue (which no longer looks like an rvalue to cast_away_const(..)).
Next we try three overloads, for const T&, const T* and const T*&.
// Third try. Overload conflicts.
template< typename T >
T&
cast_away_const( const T& a)
{
return const_cast< T& >( a);
}
template< typename T >
T*
cast_away_const( const T* a)
{
return const_cast< T* >( a);
}
template< typename T >
T*&
cast_away_const( const T*& a)
{
return const_cast< T*& >( a);
}
This does not work either. Many of the pointers (p1, p2, rp1 and rp2) match both const T* and const T*&, and so the compiler cannot decide which overload to call. But p3 and p4 work correctly, and rp3 and rp4 are both correctly flagged as errors because on those lines cast_away_const(..) is passed an rvalue param (&c or &rc) which only matches const T*. An rvalue will only match a reference to a constant value, and const T* is not a const pointer. It is a non-const pointer to a const T. The rvalues &c and &rc would however match const T* const & since the pointer value is const.
Another thing to try is provide just two overloads, for const T& and const T*&. This does not work for p3 and p4 however, since on those lines cast_away_const(..) is called with const T* rvalues. And rvalues cannot be passed as refs unless the immediate value (the pointer in this case) is const.
All this talk about rvalues suggests a solution however. Provide overloads for const T&, const T*&, and const T* const &.
// Final try.
template< typename T >
T&
cast_away_const( const T& a)
{
return const_cast< T& >( a);
}
template< typename T >
T*&
cast_away_const( const T*& a)
{
return const_cast< T*& >( a);
}
template< typename T >
T* const &
cast_away_const( const T* const & a)
{
return const_cast< T* const & >( a);
}
This works for all the cases except r4. It correctly rejects rp3 and rp4 and accepts everything else. In the r4 case, it sets r4 to be a ref to an unnamed temporary rvalue variable. This is probably safe (depending on context) since the unnamed temp is only destroyed upon local-scope exit, just after r4 is destroyed. I wouldn’t want this in my code, but it is probably safe.
Consider the following statements.
int& r4 = cast_away_const( get_const_int( )); /* not error */ int& r5 = const_cast< int& >( get_const_int( )); /* is error */ int& r6 = const_cast< int >( get_const_int( )); /* is error */ const int& r7 = get_const_int( ); /* not error */ int& r8 = const_cast< int& >( r7); /* not error */
Although r4 and r5 are exactly the same, only r5 generates a compiler error. But r8 is also exactly the same and generates no error. This inconsistency arises because you are allowed to bind const int& (r7) but not int& to an rvalue. And then you can cast const int& to int&, making a non-const ref to an rvalue. r4 may be bad style, but it is also just a simpler way of achieving r8.
When C++0x comes out and I get a compiler with rvalues (&&) then I’ll find out more. Will it become illegal to bind rvalues to const T& and const T* const &? It is only legal now as a kludge, because there is no rvalue ref. And how will rvalue refs affect the definition of cast_away_const(..)? I suspect I’ll end up with four overrides, for const T&, const T&&, const T*& and const T*&&. I won’t know for sure until I try it though. I look forward to finding out.