Detecting the Existence of Operators at Compile-Time

From Wiki

Contents 1 Problem Statement and Introduction 2 The Solution 3 The Solution Explained 4 Outlook

[edit] Problem Statement and Introduction

I recently had the need to figure out if a given type T supports a particular expression at compile-time. In my particular case, I needed to know whether T supports operator ==, i.e. given two objects of Type T, t1 and t2, I wanted to know at compile-time if t1 == t2 is a valid expression that would compile for type T.

After playing around with various SFINAE tricks I found a solution in the depths of the detail namespace of Boost (where else ;). The technique is attributed to David Abrahams and I was thankfully made aware of it by Roman Perepelitsa who pointed me in the right direction on the Boost.Users mailing list and even provided an implementation for my problem above. The main idea is to use a template metaprogramming trick that is often applied, especially in type-traits or type-trait-like template metafunctions.

That trick is using sizeof(f(...)) where f is a function call. If used like this, sizeof returns the size of the return value of f. Assuming f has two overloads and both of them return a type of different size we can use that to determine at compile-time which function was chosen. So with these basics out of the way, let me present to you the compile-time predicate is_equality_comparable. See if you can figure out for yourself how this works. If you need help, I will gladly provide some detailed explanations below.

[edit] The Solution

#include <boost/type_traits/remove_reference.hpp>
#include <boost/type_traits/remove_cv.hpp>
#include <boost/static_assert.hpp>
 
namespace detail
{
    // A tag type returned by operator == for the any struct in this namespace
    // when T does not support ==.
    struct tag {};
 
    // This type soaks up any implicit conversions and makes the following operator ==
    // less preferred than any other such operator found via ADL.
    struct any
    {
        // Conversion constructor for any type.
        template <class T>
        any(T const&);
    };
 
    // Fallback operator == for types T that don't support ==.
    tag operator == (any const&, any const&);
 
    // Two overloads to distinguish whether T supports a certain operator expression.
    // The first overload returns a reference to a two-element character array and is chosen if
    // T does not support the expression, such as ==, whereas the second overload returns a char 
    // directly and is chosen if T supports the expression. So using sizeof(check(<expression>))
    // returns 2 for the first overload and 1 for the second overload.
    typedef char yes;
    typedef char (&no)[2];
 
    no check(tag);
 
    template <class T>
    yes check(T const&);
 
    // Implementation for our is_equality_comparable template metafunction.
    template <class T>
    struct is_equality_comparable_impl
    {
        static typename boost::remove_cv<typename boost::remove_reference<T>::type>::type const& x;
 
        static const bool value = sizeof(check(x == x)) == sizeof(yes);
    };
}
 
template <class T>
struct is_equality_comparable : detail::is_equality_comparable_impl<T> {};
 
// Let's test our compile-time predicate.
struct A {};
 
struct B
{
    bool operator == (B const&) const { return true; }
};
 
struct C {};
bool operator == (C const&, C const&) { return true; }
 
int main(int argc, _TCHAR* argv[])
{
    BOOST_STATIC_ASSERT(is_equality_comparable<int>::value);
    BOOST_STATIC_ASSERT(!is_equality_comparable<A>::value);
    BOOST_STATIC_ASSERT(is_equality_comparable<B>::value);
    BOOST_STATIC_ASSERT(is_equality_comparable<C>::value);
 
    return 0;
}

[edit] The Solution Explained

Let's go through this piece of code step-by-step starting with the most important lines:

static typename boost::remove_cv<typename boost::remove_reference<T>::type>::type const& x;
 
static const bool value = sizeof(check(x == x)) == sizeof(yes);

value, the result of our template metafunction, is going to be true if T supports operator == and false otherwise. We determine this by taking the size of the return value of a function called check. If the size of the return type of that function equals sizeof(yes) = 1 then T supports operator ==. If the size is sizeof(no) = 2 then T does not support operator ==. To ensure that sizeof(yes) != sizeof(no) we use the knowledge that according to the C++ standard it must be that sizeof(char) == 1. Therefore, the size of a char array with two elements must have size 2. This explains the typedefs for the types yes and no:

typedef char yes;
typedef char (&no)[2];

Since we want to use these types as return types from a function, but arrays cannot be directly returned, we simply define no as a reference to a two-element char array of which the size will still be 2.

Now, let's look at the function check. The key point here is that it has two overloads, one of them being a template function.

no check(tag);
 
template <class T>
yes check(T const&);

The template function overload is chosen by the compiler if T supports operator ==. In this case, the argument x == x that is passed to check will be whatever type operator == has as return type (most likely bool). It will definitely not return the tag type defined in the detail namespace. Therefore sizeof(check(x == x)) will be sizeof(yes) because the template function's return type is yes.

The regular free function is chosen by the compiler if T doesn't support operator == as a member function or in its namespace. In order to make our program compile, we need to provide an alternative operator == that the compiler can use as a fall back:

struct any
{
    // Conversion constructor for any type.
    template <class T>
    any(T const&);
};
 
tag operator == (any const&, any const&);

In order to make it the least preferable operator == to the compiler it accepts instances of a type any as parameters. any has a conversion constructor from arbitrary types T. The fall back operator == conveniently has the return type tag, which is just what our check free function accepts as argument. Thus, for the expression x == x the compiler will choose our fall back operator == because T doesn't support it and therefore sizeof(check(x == x)) will be sizeof(no) because the free function's return type is no.

[edit] Outlook

The nice thing about this technique is that it easily extends to other user-overridable operators as well. For example, we can extend it to determine whether a given type T supports operator << (ostream&, T const&), i.e. the output stream operator.

namespace detail
{
    template <class T>
    struct is_output_streamable_impl
    {
        static typename boost::remove_cv<typename boost::remove_reference<T>::type>::type const& x;
 
        static const bool value = sizeof(check(std::cout << x)) == sizeof(yes);
    };
}
 
template <class T>
struct is_output_streamable : detail::is_output_streamable_impl<T> {};
 
std::ostream& operator << (std::ostream& stream, C const&) { return stream; }
 
BOOST_STATIC_ASSERT(is_output_streamable<int>::value);
BOOST_STATIC_ASSERT(!is_output_streamable<A>::value);
BOOST_STATIC_ASSERT(!is_output_streamable<B>::value);
BOOST_STATIC_ASSERT(is_output_streamable<C>::value);

Tricky but awesome, if you ask me :)

There is, however, one situation where this technique falls short, and that is when a class declares its operator == private. Since name lookup and overload resolution happen before access checking, you will get a compilation error when trying to use our compile-time predicates with such a class.

For more template metafunctions that detect whether T supports the prefix or postfix increment operator, see the header file boost/detail/is_incrementable.hpp. That file was the original inspiration for this article.