SFINAE

This post will focus on the concept of SFINAE, Substitution Failure Is Not An Error. This is a core concept that is one of the reasons templates are even possible. This concept is related exclusively to the processing of templates. It is referred to as SFINAE by the community, and this entry focuses on the two important aspects of SFINAE:

1. Why it is crucial to the flexibility of C++ templates and the programming of generics
2. How you can use it to your advantage

What the hell is it?

This is a term exclusively used in C++, which specifies that an invalid template parameter substitution itself is not an error. This is a situation specifically related to overload resolution of the considered candidates. Let me restate this without the official language jargon.

If there exists a collection of potential candidates for template substitution, even if a candidate is not a valid substitution, this will not trigger an error. It is simply eliminated from the list of potential candidates. However, if there are no candidates that can successfully meet the substitution criteria, then an error will be triggered.

SFINAE < Example >

I gave a vague description that somewhat resembled a statement in set theory. I also added a the Venn-diagram to hopefully add more clarity. However, there is nothing like seeing a demonstration in action to illustrate a vague concept. This concept is valid for class templates as well.

Below I have created a few overloaded function definitions. I have also created two template types that use the same name (overloaded), but have completely different structures. This example demonstrates the reason for the original rule:

struct Field 
{
  typedef double type;
};

template < typename T >
typename T::type Triple(typename T::type value)  
{
  return value * 3;
}

template < typename T >
T Triple(T value)
{
  return value * 3;
}

The first case below, is the simpler example. It only requires, and accepts type where the value can be extracted implicitly from the type passed in; such as the intrinsic types, or types that provide a value conversion operator. More details have been annotated above each function.

int main()
{
  // The version that requires a sub-field called "type"
  // will be excluded as a possibility for this version.
  cout << "Field type: " << Triple < int >  (5) << "\n";

  // In this case, the version that contains that
  // sub-field is the only valid type.
  cout << "Field type: " << Triple < Field >(5) << "\n";
}

Curiosity

SFINAE was added to the language to make templates usable for fundamental purposes. It was envisioned that a string class may want to overload the operator+ function or something similar for an unordered collection object. However, it did not take long for the programmers to discover some hidden powers.

The power that was unlocked by SFINAE was the ability to programmatically determine the type of an object, and force a particular overload based on the type in use. This means that a template implementation is capable of querying for information about it's type and qualifiers at compile-time. This is similar to the feature that many languages have called reflection. Although, reflection occurs at run-time (and also incurs a run-time penalty).

Rumination

I am not aware of a name for this static-form of reflection. If there is could someone comment and le me know what it is called. If it hasn't been name I think it should be something similar to reflection, but it is still a separate concept.

When I think of static, I think of "fixed-in-place" or not moving. Meditation would fit quite well, it's just not that cool. Very similar to that is ponder. I thought about using introspection, but that is just a more pretentious form of reflection.

Then it hit me. Rumination! That would be perfect. It's verb form, ruminate,  means to meditate or muse; ponder. There is also a secondary meaning for ruminate: To chew the cud; much like the compiler does. Regardless, it's always fun to create new buzzwords. Remember, Rumination.

Innovative Uses

I make heavy use of SFINAE in my implementation of Network Alchemy. Mostly the features provided by the < type_traits > header. The construct std::enable_if is built upon the concept of SFINAE. I am ashamed to admit, that I have not been able to understand and successfully apply std::enable_if yet. I have crossed many situations that it seemed like it would be an elegant fit. When I figure it out, I will be sure to distill what I learn, and explain it so you can understand it too.

Useful applications of SFINAE

To read a book, an article or blog entry and find something genuinely new and useful that I have an immediate need for is fantastic. I find it extremely irritating when there is not enough effort put into the examples that usually accompany the brief explanation. This makes the information in the article nearly useless. This is even more irritating if the examples are less complicated than what I could create with my limited understanding of the topic to begin with.

A situation is extremely frustrating when I believe that I have found a good solution, yet I cannot articulate the idea to apply it. So unless you get extremely frustrated by useful examples applied to real-world problems, I hope these next few sections excite you.

Ruminate Idiom

We will create a meta-function that can make a decision based on the type of T. To start we will need to introduce the basis on which the idiom is built. A scenario is required where there are a set of choices, and only one of the choices is valid. Let's start with the sample, and continue to build until we reach a solution.

We will need two different types that are of a different size

template < typename T >
struct yes_t
{ char buffer[2]; };

typedef char no_t;

We will also need two component that are common in meta-programming:

1. the sizeof operator
2. static-member constanst

We define a meta-function template, that will setup a test between the two types using the size of operator to determine which type was selected. This will give us the ability to make a binary decision in the meta-function.

template < typename T >
struct conditional
{
private:
  template < typename U >
  static yes_t  < /* conditional on U */ > selector(U);

  static no_t selector(...);

  static T* this_t();

public:
  static const bool value =
    sizeof(selector(*this_t())) != sizeof(no_t); 
}; 

We started with static declarations of the two types that I defined earlier. However, there is no defined conditional test for the yes_t template, yet. It is also important to understand that the template parameter name must be something different than the name used in the templates outer parameter. Otherwise the template parameter for the object would be used and SFINAE would not apply.

The lowest type in the order of precedence for C++ is .... At first glance this looks odd. However, think of it as the catch all type. If the conditional statement for yes_t produces an invalid type definition, the no_t type will be used for the declaration of the selector function.

It is important to note that it is not necessary to define the function implementations for selector because they will never actually be executed. Therefore, it is not required by the linker. We also use an arbitrary function, selector, that returns T, rather than a function that invokes T(), because T may not have a default constructor.

It is also possible to declare the selector function to take a pointer to T. However, a pointer type will allow void to become valid as a void*. Also, any type of reference will trigger an error because pointers to references are illegal. This is one area where there is no single best way to declare the types. You may need to add other specializations to cover any corner cases. Keep these alternatives in mind if you receive compiler warnings with the form I presented above.

More Detail

You were just presented a few facts, a bit of code, and another random mix of facts. Let's tie all of this information together to help you understand how it works.

• SFINAE will not allow a template substitution error halt the compiling process
• Inside of the meta-function we have created to specializations that accept T
• We have selected type definitions that will help us determine if a condition is true based upon the type. (An example condition will be shown next).
• We also added a catch-all declaration for the types that do not meet the conditional criteria (...)
• The stub function this_t() has been created to be used in a sizeof expression. The sizeof expression compares the two worker types to the no_t type to determine the result of our conditional.

The next section contains a concrete example conditional that is based on the type U.

is_class

Months ago I wrote about the standard header file, Type Traits[^]. This file contains some of the most useful templates for correctly creating templates that correctly support a wide range of types.

The classification of a type can be determined, such as differentiating between a Plain-old data (POD) struct and struct with classes. Determine if a type is const or volatile, if it's an lvalue, pointer or reference. Let me demonstrate how to tell if a type is a class type or not. Class types are the compound data structures, class, struct, and union.

What we need in the conditional template parameter is something that can differentiate these types from any other type. These types are the only types that it is legal to make a pointer to a scope operator ::*. The :: operator resolves to the global namespace.

Here is the definition of this template meta-function:

template < typename T >
struct is_class
{
private:
  template < typename U >
  static yes_t  < int U::* > selector(U);

  static no_t selector(...);

  static T* this_t();

public:
  static const bool value =
    sizeof(selector(*this_t())) != sizeof(no_t); 
};

Separate classes based on member declarations

Sometimes it becomes beneficial to determine if an object supports a certain function before you attempt to use that feature. An example would be the find() member function that is part of the associative containers in the C++ Standard Library. This is because it is recommended that you should prefer to call the member function of a container over the generic algorithm in the library.

Let's first present an example, then I'll demonstrate how you can take advantage and apply this call:

template<typename bool="std::is_class<T">::value>
struct has_find                          
{              
  static const bool value = false;
};                                                              

template<typename t="">
struct has_find< T,true>
{                                                               
  typedef char true_type;
  struct false_type
  {
    true_type dummy[2];
  };

  struct base { int find; };
  struct derived
    : T, base
  { derived(); };

  template<int base::*><int> struct tester;

  template< typename U>
      static false_type has_member(tester< &U::find >*);
  template< typename U>
      static true_type has_member(...);

  static const 
    bool value = sizeof(has_member<derived><derived>(0))==sizeof(true_type); 
};
</derived></int></typename></typename>

Applying the meta-function

The call to std::find() is very generic. However, some containers provide an optimized and more convenient version of this function. Imagine we want to build a generic function ourselves that will allow any type of container to be used. We could encapsulate the std::find() call itself in a more convenient usage. Then build a single version of the generic function, as opposed to creating specializations of the implementation.

This type of approach will allow us to encapsulate the pain-point in our function that would cause the implementation of a specialization for each type our generic function is intended to support.

We will need to create one instance of our meta-function for each branch that exist in the final chain of calls. However, once this is done, the same meta-function can be combined in any number of generic ways to build bigger and more complex expressions.

template <typename T, bool HasFindT>
struct call_find
{
  bool operator()(
    T& container, 
    const typename T::value_type& value, 
    typename T::iterator &result)
  {
    result = container.find(value);
    std::cout << "T::find() called\n";
    return result != container.end();
  }
};

template <typename T>
struct call_find <T, false>
{
  bool operator()(
    T& container, 
    const typename T::value_type& value, 
    typename T::iterator &result)
  {
    result = std::find( container.begin(),
                        container.end(),
                        value);
    std::cout << "std::find() called\n";
    return result != container.end();
  }
};

This is a very simple function. In my experience, the small, generic, and cohesive functions and objects are the ones that are most likely to be reused. With this function, we can now use it in a more specific context, which should still remain generic for any type of std container:

template < typename T >
void generic_call( T& container )
{
  T::value_type target;
  // ... Code that determines the value ...

  T::iterator item;
  if (!call_find< T, has_find < T >::value>(container, target, item))
  {
    return;
  }

  // ... item is valid, continue logic ...
}

We made it possible to create a more complex generic function with the creation of the small helper function , CotD::find(). The resulting CotD::generic_call is agnostic to the type of container that is passed to it.

This allowed us to avoid the duplication of code for the larger function, CotD::generic_call, due to template specializations.

Here is a sample program of calling the different specializations and the output they will generate:

Note: You can run this sample online from my blog (codeofthedamned.com) thanks to the coliru online compiler.

int main(int argc, char* argv[])
{
  typedef std::set<int> SetInt;

  call_find<SetInt, has_find<SetInt>::value> set_call;

  SetInt::iterator set_iter;
  SetInt s;
  set_call(s, 0, set_iter);

  typedef std::vector<int> VecInt;

  call_find<VecInt, has_find<VecInt>::value> vec_call;
  VecInt::iterator vec_iter;
  VecInt v;
  vec_call(v, 0, vec_iter);
}

T::find() called
std::find() called

There is also a great chance that the helper template will be optimized by the compiler to eliminate the unreachable branch due to the types being pre-determined and fixed when the template is instantiated.

Summary

Substitution Failure Is Not An Error (SFINAE), is a subtle addition that was added to C++ make the overload resolution possible with templates. Just like the other basic functions and classes. However, this subtle compiler feature opens the doors of possibility for many applications in generic C++ programming.