2.7 Detecting Convertibility and Inheritance at Compile Time

When you're implementing template functions and classes, a question arises every so often: Given two arbitrary types T and U that you know nothing about, how can you detect whether or not U inherits from T? Discovering such relationships at compile time is key to implementing advanced optimizations in generic libraries. In a generic function, you can rely on an optimized algorithm if a class implements a certain interface. Discovering this at compile time means not having to use dynamic_cast, which is costly at runtime.

Detecting inheritance relies on a more general mechanism, that of detecting convertibility. The more general problem is, How can you detect whether an arbitrary type T supports automatic conversion to an arbitrary type U?

There is a solution to this problem, and it relies on sizeof. There is a surprising amount of power in sizeof: You can apply sizeof to any expression, no matter how complex, and sizeof returns its size without actually evaluating that expression at runtime. This means that sizeof is aware of overloading, template instantiation, conversion rules—everything that can take part in a C++ expression. In fact, sizeof conceals a complete facility for deducing the type of an expression; eventually, sizeof throws away the expression and returns only the size of its result.^[2]

^[2] There is a proposal for adding a typeof operator to C++, that is, an operator returning the type of an expression. Having typeof would make much template code easier to write and understand. Gnu C++ already implements typeof as an extension. Obviously, typeof and sizeof share the same back end, because sizeof has to figure out the type anyway.

The idea of conversion detection relies on using sizeof in conjunction with overloaded functions. We provide two overloads of a function: One accepts the type to convert to (U), and the other accepts just about anything else. We call the overloaded function with a temporary of type T, the type whose convertibility to U we want to determine. If the function that accepts a U gets called, we know that T is convertible to U; if the fallback function gets called, then T is not convertible to U. To detect which function gets called, we arrange the two overloads to return types of different sizes, and then we discriminate with sizeof. The types themselves do not matter, as long as they have different sizes.

Let's first create two types of different sizes. (Apparently, char and long double do have different sizes, but that's not guaranteed by the standard.) A foolproof scheme would be the following:

typedef char Small;


class Big { char dummy[2]; };

By definition, sizeof(Small) is 1. The size of Big is unknown, but it's certainly greater than 1, which is the only guarantee we need.

Next, we need the two overloads. One accepts a U and returns, say, a Small:

Small Test(U);

How can we write a function that accepts "anything else"? A template is not a solution because the template would always qualify as the best match, thus hiding the conversion. We need a match that's "worse" than an automatic conversion—that is, a conversion that kicks in if and only if there's no automatic conversion. A quick look through the conversion rules applied for a function call yields the ellipsis match, which is the worst of all—the bottom of the list. That's exactly what the doctor prescribed.

Big Test(...);

(Passing a C++ object to a function with ellipses has undefined results, but this doesn't matter. Nothing actually calls the function. It's not even implemented. Recall that sizeof does not evaluate its argument.)

Now we need to apply sizeof to the call of Test, passing it a T:

const bool convExists = sizeof(Test(T())) == sizeof(Small);

That's it! The call of Test gets a default-constructed object—T()—and then sizeof extracts the size of the result of that expression. It can be either sizeof(Small) or sizeof(Big), depending on whether or not the compiler found a conversion.

There is one little problem. If T makes its default constructor private, the expression T() fails to compile and so does all of our scaffolding. Fortunately, there is a simple solu-tion—just use a strawman function returning a T. (Remember, we're in the sizeof wonderland where no expression is actually evaluated.) In this case, the compiler is happy and so are we.

T MakeT(); // not implemented


const bool convExists = sizeof(Test(MakeT())) == sizeof(Small);

(By the way, isn't it nifty just how much you can do with functions, like MakeT and Test, that not only don't do anything but don't even really exist at all?)

Now that we have it working, let's package everything in a class template that hides all the details of type deduction and exposes only the result.

template <class T, class U>


class Conversion


{


   typedef char Small;


   class Big { char dummy[2]; };


   static Small Test(U);


   static Big Test(...);


   static T MakeT();


public:


   enum { exists =


      sizeof(Test(MakeT())) == sizeof(Small) };


};

Now you can test the Conversion class template by writing

int main()


{


   using namespace std;


   cout


      << Conversion<double, int>::exists << ' '


      << Conversion<char, char*>::exists << ' '


      << Conversion<size_t, vector<int> >::exists << ' ';


}

This little program prints "1 0 0." Note that although std::vector does implement a constructor taking a size_t, the conversion test returns 0 because that constructor is explicit.

We can implement one more constant inside Conversion: sameType, which is true if T and U represent the same type:

template <class T, class U>


class Conversion


{


   ... as above ...


   enum { sameType = false };


};

We implement sameType through a partial specialization of Conversion:

template <class T>


class Conversion<T, T>


{


public:


   enum { exists = 1, sameType = 1 };


};

Finally, we're back home. With the help of Conversion, it is now very easy to determine inheritance:

#define SUPERSUBCLASS(T, U) \


   (Conversion<const U*, const T*>::exists && \


   !Conversion<const T*, const void*>::sameType)

SUPERSUBCLASS(T, U) evaluates to true if U inherits from T publicly, or if T and U are actually the same type. SUPERSUBCLASS does its job by evaluating the convertibility from a const U* to a const T*. There are only three cases in which const U* converts implicitly to const T*:

The last case is eliminated by the second test. In practice it's useful to accept the first case (T is the same as U) as a degenerated case of "is-a" because for practical purposes you can often consider a class to be its own superclass. If you need a stricter test, you can write it this way:

#define SUPERSUBCLASS_STRICT(T, U) \


   (SUPERSUBCLASS(T, U) && \


   !Conversion<const T, const U>::sameType)

Why does the code add all those const modifiers? The reason is that we don't want the conversion test to fail due to const issues. If template code applies const twice (to a type that's already const), the second const is ignored. In a nutshell, by using const in SUPERSUBCLASS, we're always on the safe side.

Why use SUPERSUBCLASS and not the cuter BASE_OF or INHERITS? For a very practical reason. Initially Loki used INHERITS. But with INHERITS(T, U) it was a constant struggle to say which way the test worked—did it tell whether T inherited U or vice versa? Arguably, SUPERSUBCLASS(T, U) makes it clearer which one is first and which one is second.