DevTut

# SFINAE (Substitution Failure Is Not An Error)

# What is SFINAE

SFINAE stands for Substitution Failure Is Not An Error. Ill-formed code that results from substituting types (or values) to instantiate a function template or a class template is not a hard compile error, it is only treated as a deduction failure.

Deduction failures on instantiating function templates or class template specializations remove that candidate from the set of consideration - as if that failed candidate did not exist to begin with.

template <class T>
auto begin(T& c) -> decltype(c.begin()) { return c.begin(); }

template <class T, size_t N>
T* begin(T (&arr)[N]) { return arr; }

int vals[10];
begin(vals); // OK. The first function template substitution fails because
             // vals.begin() is ill-formed. This is not an error! That function
             // is just removed from consideration as a viable overload candidate,
             // leaving us with the array overload.

Only substitution failures in the immediate context are considered deduction failures, all others are considered hard errors.

template <class T>
void add_one(T& val) { val += 1; }

int i = 4;
add_one(i); // ok

std::string msg = "Hello";
add_one(msg); // error. msg += 1 is ill-formed for std::string, but this
              // failure is NOT in the immediate context of substituting T

# void_t

void_t is a meta-function that maps any (number of) types to type void. The primary purpose of void_t is to facilitate writing of type traits.

std::void_t (opens new window) will be part of C++17, but until then, it is extremely straightforward to implement:

template <class...> using void_t = void;

Some compilers require (opens new window) a slightly different implementation:

template <class...>
struct make_void { using type = void; };

template <typename... T>
using void_t = typename make_void<T...>::type;

The primary application of void_t is writing type traits that check validity of a statement. For example, let's check if a type has a member function foo() that takes no arguments:

template <class T, class=void>
struct has_foo : std::false_type {};

template <class T>
struct has_foo<T, void_t<decltype(std::declval<T&>().foo())>> : std::true_type {};

How does this work? When I try to instantiate has_foo<T>::value, that will cause the compiler to try to look for the best specialization for has_foo<T, void>. We have two options: the primary, and this secondary one which involves having to instantiate that underlying expression:

  • If T does have a member function foo(), then whatever type that returns gets converted to void, and the specialization is preferred to the primary based on the template partial ordering rules. So has_foo<T>::value will be true
  • If T doesn't have such a member function (or it requires more than one argument), then substitution fails for the specialization and we only have the primary template to fallback on. Hence, has_foo<T>::value is false.

A simpler case:

template<class T, class=void>
struct can_reference : std::false_type {};

template<class T>
struct can_reference<T, std::void_t<T&>> : std::true_type {};

this doesn't use std::declval or decltype.

You may notice a common pattern of a void argument. We can factor this out:

struct details {
  template<template<class...>class Z, class=void, class...Ts>
  struct can_apply:
    std::false_type
  {};
  template<template<class...>class Z, class...Ts>
  struct can_apply<Z, std::void_t<Z<Ts...>>, Ts...>:
    std::true_type
  {};
};

template<template<class...>class Z, class...Ts>
using can_apply = details::can_apply<Z, void, Ts...>;

which hides the use of std::void_t and makes can_apply act like an indicator whether the type supplied as the first template argument is well-formed after substituting the other types into it. The previous examples may now be rewritten using can_apply as:

template<class T>
using ref_t = T&;

template<class T>
using can_reference = can_apply<ref_t, T>;    // Is T& well formed for T?

and:

template<class T>
using dot_foo_r = decltype(std::declval<T&>().foo());

template<class T>
using can_dot_foo = can_apply< dot_foo_r, T >;    // Is T.foo() well formed for T?

which seems simpler than the original versions.

There are post-C++17 proposals for std traits similar to can_apply.

The utility of void_t was discovered by Walter Brown. He gave a wonderful presentation (opens new window) on it at CppCon 2016.

# enable_if

std::enable_if is a convenient utility to use boolean conditions to trigger SFINAE. It is defined as:

template <bool Cond, typename Result=void>
struct enable_if { };

template <typename Result>
struct enable_if<true, Result> {
    using type = Result;
};

That is, enable_if<true, R>::type is an alias for R, whereas enable_if<false, T>::type is ill-formed as that specialization of enable_if does not have a type member type.

std::enable_if can be used to constrain templates:

int negate(int i) { return -i; }

template <class F>
auto negate(F f) { return -f(); }

Here, a call to negate(1) would fail due to ambiguity. But the second overload is not intended to be used for integral types, so we can add:

int negate(int i) { return -i; }

template <class F, class = typename std::enable_if<!std::is_arithmetic<F>::value>::type>
auto negate(F f) { return -f(); }

Now, instantiating negate<int> would result in a substitution failure since !std::is_arithmetic<int>::value is false. Due to SFINAE, this is not a hard error, this candidate is simply removed from the overload set. As a result, negate(1) only has one single viable candidate - which is then called.

# When to use it

It's worth keeping in mind that std::enable_if is a helper on top of SFINAE, but it's not what makes SFINAE work in the first place. Let's consider these two alternatives for implementing functionality similar to std::size, i.e. an overload set size(arg) that produces the size of a container or array:

// for containers
template<typename Cont>
auto size1(Cont const& cont) -> decltype( cont.size() );

// for arrays
template<typename Elt, std::size_t Size>
std::size_t size1(Elt const(&arr)[Size]);

// implementation omitted
template<typename Cont>
struct is_sizeable;

// for containers
template<typename Cont, std::enable_if_t<std::is_sizeable<Cont>::value, int> = 0>
auto size2(Cont const& cont);

// for arrays
template<typename Elt, std::size_t Size>
std::size_t size2(Elt const(&arr)[Size]);

Assuming that is_sizeable is written appropriately, these two declarations should be exactly equivalent with respect to SFINAE. Which is the easiest to write, and which is the easiest to review and understand at a glance?

Now let's consider how we might want to implement arithmetic helpers that avoid signed integer overflow in favour of wrap around or modular behaviour. Which is to say that e.g. incr(i, 3) would be the same as i += 3 save for the fact that the result would always be defined even if i is an int with value INT_MAX. These are two possible alternatives:

// handle signed types
template<typename Int>
auto incr1(Int& target, Int amount)
-> std::void_t<int[static_cast<Int>(-1) < static_cast<Int>(0)]>;

// handle unsigned types by just doing target += amount
// since unsigned arithmetic already behaves as intended
template<typename Int>
auto incr1(Int& target, Int amount)
-> std::void_t<int[static_cast<Int>(0) < static_cast<Int>(-1)]>;
 
template<typename Int, std::enable_if_t<std::is_signed<Int>::value, int> = 0>
void incr2(Int& target, Int amount);
 
template<typename Int, std::enable_if_t<std::is_unsigned<Int>::value, int> = 0>
void incr2(Int& target, Int amount);

Once again which is the easiest to write, and which is the easiest to review and understand at a glance?

A strength of std::enable_if is how it plays with refactoring and API design. If is_sizeable<Cont>::value is meant to reflect whether cont.size() is valid then just using the expression as it appears for size1 can be more concise, although that could depend on whether is_sizeable would be used in several places or not. Contrast that with std::is_signed which reflects its intention much more clearly than when its implementation leaks into the declaration of incr1.

# is_detected

To generalize type_trait creation:based on SFINAE there are experimental traits detected_or, detected_t, is_detected.

With template parameters typename Default, template <typename...> Op and typename ... Args:

  • is_detected: alias of std::true_type or std::false_type depending of the validity of Op<Args...>
  • detected_t: alias of Op<Args...> or nonesuch depending of validity of Op<Args...>.
  • detected_or: alias of a struct with value_t which is is_detected, and type which is Op<Args...> or Default depending of validity of Op<Args...>

which can be implemented using std::void_t for SFINAE as following:

namespace detail {
    template <class Default, class AlwaysVoid,
              template<class...> class Op, class... Args>
    struct detector
    {
        using value_t = std::false_type;
        using type = Default;
    };

    template <class Default, template<class...> class Op, class... Args>
    struct detector<Default, std::void_t<Op<Args...>>, Op, Args...>
    {
        using value_t = std::true_type;
        using type = Op<Args...>;
    };

} // namespace detail

// special type to indicate detection failure
struct nonesuch {
    nonesuch() = delete;
    ~nonesuch() = delete;
    nonesuch(nonesuch const&) = delete;
    void operator=(nonesuch const&) = delete;
};

template <template<class...> class Op, class... Args>
using is_detected =
    typename detail::detector<nonesuch, void, Op, Args...>::value_t;

template <template<class...> class Op, class... Args>
using detected_t = typename detail::detector<nonesuch, void, Op, Args...>::type;

template <class Default, template<class...> class Op, class... Args>
using detected_or = detail::detector<Default, void, Op, Args...>;

Traits to detect presence of method can then be simply implemented:

typename <typename T, typename ...Ts>
using foo_type = decltype(std::declval<T>().foo(std::declval<Ts>()...));

struct C1 {};

struct C2 {
    int foo(char) const;
};

template <typename T>
using has_foo_char = is_detected<foo_type, T, char>;

static_assert(!has_foo_char<C1>::value, "Unexpected");
static_assert(has_foo_char<C2>::value, "Unexpected");

static_assert(std::is_same<int, detected_t<foo_type, C2, char>>::value,
              "Unexpected");

static_assert(std::is_same<void, // Default
                           detected_or<void, foo_type, C1, char>>::value,
              "Unexpected");
static_assert(std::is_same<int, detected_or<void, foo_type, C2, char>>::value,
              "Unexpected");

# Overload resolution with a large number of options

If you need to select between several options, enabling just one via enable_if<> can be quite cumbersome, since several conditions needs to be negated too.

The ordering between overloads can instead be selected using inheritance, i.e. tag dispatch.

Instead of testing for the thing that needs to be well-formed, and also testing the negation of all the other versions conditions, we instead test just for what we need, preferably in a decltype in a trailing return.
This might leave several option well formed, we differentiate between those using 'tags', similar to iterator-trait tags (random_access_tag et al). This works because a direct match is better that a base class, which is better that a base class of a base class, etc.

#include <algorithm>
#include <iterator>

namespace detail
{
    // this gives us infinite types, that inherit from each other
    template<std::size_t N>
    struct pick : pick<N-1> {};
    template<>
    struct pick<0> {};

    // the overload we want to be preferred have a higher N in pick<N>
    // this is the first helper template function
    template<typename T>
    auto stable_sort(T& t, pick<2>)
        -> decltype( t.stable_sort(), void() )
    {
        // if the container have a member stable_sort, use that
        t.stable_sort();
    }

    // this helper will be second best match
    template<typename T>
    auto stable_sort(T& t, pick<1>)
        -> decltype( t.sort(), void() )
    {
        // if the container have a member sort, but no member stable_sort
        // it's customary that the sort member is stable
        t.sort();
    }

    // this helper will be picked last
    template<typename T>
    auto stable_sort(T& t, pick<0>)
        -> decltype( std::stable_sort(std::begin(t), std::end(t)), void() )
    {
        // the container have neither a member sort, nor member stable_sort
        std::stable_sort(std::begin(t), std::end(t));
    }

}

// this is the function the user calls. it will dispatch the call
// to the correct implementation with the help of 'tags'.
template<typename T>
void stable_sort(T& t)
{
    // use an N that is higher that any used above.
    // this will pick the highest overload that is well formed.
    detail::stable_sort(t, detail::pick<10>{});
}

There are other methods commonly used to differentiate between overloads, such as exact match being better than conversion, being better than ellipsis.

However, tag-dispatch can extend to any number of choices, and is a bit more clear in intent.

# trailing decltype in function templates

One of constraining function is to use trailing decltype to specify the return type:

namespace details {
   using std::to_string;

   // this one is constrained on being able to call to_string(T)
   template <class T>
   auto convert_to_string(T const& val, int )
       -> decltype(to_string(val))
   {
       return to_string(val);
   }

   // this one is unconstrained, but less preferred due to the ellipsis argument
   template <class T>
   std::string convert_to_string(T const& val, ... )
   {
       std::ostringstream oss;
       oss << val;
       return oss.str();
   }
}

template <class T>
std::string convert_to_string(T const& val)
{
    return details::convert_to_string(val, 0);
}

If I call convert_to_string() with an argument with which I can invoke to_string(), then I have two viable functions for details::convert_to_string(). The first is preferred since the conversion from 0 to int is a better implicit conversion sequence than the conversion from 0 to ...

If I call convert_to_string() with an argument from which I cannot invoke to_string(), then the first function template instantiation leads to substitution failure (there is no decltype(to_string(val))). As a result, that candidate is removed from the overload set. The second function template is unconstrained, so it is selected and we instead go through operator<<(std::ostream&, T). If that one is undefined, then we have a hard compile error with a template stack on the line oss << val.

# enable_if_all / enable_if_any

Motivational example

When you have a variadic template pack in the template parameters list, like in the following code snippet:

template<typename ...Args> void func(Args &&...args) { //... };

The standard library (prior to C++17) offers no direct way to write enable_if to impose SFINAE constraints on all of the parameters in Args or any of the parameters in Args. C++17 offers std::conjunction (opens new window) and std::disjunction (opens new window) which solve this problem. For example:

/// C++17: SFINAE constraints on all of the parameters in Args.
template<typename ...Args,
         std::enable_if_t<std::conjunction_v<custom_conditions_v<Args>...>>* = nullptr>
void func(Args &&...args) { //... };

/// C++17: SFINAE constraints on any of the parameters in Args.
template<typename ...Args,
         std::enable_if_t<std::disjunction_v<custom_conditions_v<Args>...>>* = nullptr>
void func(Args &&...args) { //... };

If you do not have C++17 available, there are several solutions to achieve these. One of them is to use a base-case class and partial specializations, as demonstrated in answers of this question (opens new window).

Alternatively, one may also implement by hand the behavior of std::conjunction and std::disjunction in a rather straight-forward way. In the following example I'll demonstrate the implementations and combine them with std::enable_if to produce two alias: enable_if_all and enable_if_any, which do exactly what they are supposed to semantically. This may provide a more scalable solution.

Implementation of enable_if_all and enable_if_any

First let's emulate std::conjunction and std::disjunction using customized seq_and and seq_or respectively:

/// Helper for prior to C++14.
template<bool B, class T, class F >
using conditional_t = typename std::conditional<B,T,F>::type;

/// Emulate C++17 std::conjunction.
template<bool...> struct seq_or: std::false_type {};
template<bool...> struct seq_and: std::true_type {};

template<bool B1, bool... Bs>
struct seq_or<B1,Bs...>: 
  conditional_t<B1,std::true_type,seq_or<Bs...>> {};

template<bool B1, bool... Bs>
struct seq_and<B1,Bs...>:
  conditional_t<B1,seq_and<Bs...>,std::false_type> {};

Then the implementation is quite straight-forward:

template<bool... Bs>
using enable_if_any = std::enable_if<seq_or<Bs...>::value>;

template<bool... Bs>
using enable_if_all = std::enable_if<seq_and<Bs...>::value>;

Eventually some helpers:

template<bool... Bs>
using enable_if_any_t = typename enable_if_any<Bs...>::type;

template<bool... Bs>
using enable_if_all_t = typename enable_if_all<Bs...>::type;

Usage

The usage is also straight-forward:


   /// SFINAE constraints on all of the parameters in Args.
    template<typename ...Args,
             enable_if_all_t<custom_conditions_v<Args>...>* = nullptr>
    void func(Args &&...args) { //... };

    /// SFINAE constraints on any of the parameters in Args.
    template<typename ...Args,
             enable_if_any_t<custom_conditions_v<Args>...>* = nullptr>
    void func(Args &&...args) { //... };

← Undefined Behavior →