How does Eric Niebler's implementation of std::is_function work?

Question

Last week Eric Niebler tweeted a very compact implementation for the std::is_function traits class:

#include <type_traits>  template<int I> struct priority_tag : priority_tag<I - 1> {}; template<> struct priority_tag<0> {};  // Function types here: template<typename T> char(&is_function_impl_(priority_tag<0>))[1];  // Array types here: template<typename T, typename = decltype((*(T*)0)[0])> char(&is_function_impl_(priority_tag<1>))[2];  // Anything that can be returned from a function here (including // void and reference types): template<typename T, typename = T(*)()> char(&is_function_impl_(priority_tag<2>))[3];  // Classes and unions (including abstract types) here: template<typename T, typename = int T::*> char(&is_function_impl_(priority_tag<3>))[4];  template <typename T> struct is_function     : std::integral_constant<bool, sizeof(is_function_impl_<T>(priority_tag<3>{})) == 1> {}; 

But how does it work?

Answer 1

The general idea

Instead of listing all the valid function types, like the sample implementation over on cpprefereence.com, this implementation lists all of the types that are not functions, and then only resolves to true if none of those is matched.

The list of non-function types consists of (from bottom to top):

• Classes and unions (including abstract types)
• Anything that can be returned from a function (including void and reference types)
• Array types

A type that does not match any of those non-function types is a function type. Note that std::is_function explicitly considers callable types like lambdas or classes with a function call operator as not being functions.

is_function_impl_

We provide one overload of the is_function_impl function for each of the possible non-function types. The function declarations can be a bit hard to parse, so let's break it down for the example of the classes and unions case:

template<typename T, typename = int T::*> char(&is_function_impl_(priority_tag<3>))[4]; 

This line declares a function template is_function_impl_ that takes a single argument of type priority_tag<3> and returns a reference to an array of 4 chars. As is customary since the ancient days of C, the declaration syntax gets horribly convoluted by the presence of array types.

This function template takes two template arguments. The first is just an unconstrained T, but the second is a pointer to a member of T of type int. The int part here does not really matter, ie. this will even work for Ts that do not have any members of type int. What it does though is that it will result in a syntax error for Ts that are not of class or union type. For those other types, attempting to instantiate the function template will result in a substitution failure.

Similar tricks are used for the priority_tag<2> and priority_tag<1> overloads, which use their second template arguments to form expressions that only compile for Ts being valid function return types or array types respectively. Only the priority_tag<0> overload does not have such a constraining second template parameter and thus can be instantiated with any T.

All in all we declare four different overloads for is_function_impl_, which differ by their input argument and return type. Each of them takes a different priority_tag type as argument and returns a reference to a char array of different unique size.

Tag dispatching in is_function

Now, when instantiating is_function, it instantiates is_function_impl with T. Note that since we provided four different overloads for this function, overload resolution has to take place here. And since all of these overloads are function templates, that means SFINAE has a chance to kick in.

So for functions (and only functions) all of the overloads will fail except the most general one with priority_tag<0>. So why doesn't instantiation always resolve to that overload, if it's the most general one? Because of the input arguments of our overloaded functions.

Note that priority_tag is constructed in such a way that priority_tag<N+1> publicly inherits from priority_tag<N>. Now, since is_function_impl is invoked here with priority_tag<3>, that overload is a better match than the others for overload resolution, so it will be tried first. Only if that fails due to a substitution error the next-best match is tried, which is the priority_tag<2> overload. We continue in this way until we either find an overload that can be instantiated or we reach priority_tag<0>, which is not constrained and will always work. Since all of the non-function types are covered by the higher prio overloads, this can only happen for function types.

Evaluating the result

We now inspect the size of the type returned by the call to is_function_impl_ to evaluate the result. Remember that each overload returns a reference to a char array of different size. We can therefore use sizeof to check which overload was selected and only set the result to true if we reached the priority_tag<0> overload.

Known Bugs

Johannes Schaub found a bug in the implementation. An array of incomplete class type will be incorrectly classified as a function. This is because the current detection mechanism for array types does not work with incomplete types.