Substitution failure is not an error: what is it and how to use it?

How is a function to be called determined in C++?

In C++, when we call a function the compiler finds all viable declarations of the called function by its name and arguments and picks the best one (the most fitting one) according to a set of very precise rules. They are called function overload resolution rules, because declaring more than 1 function with the same name but different argument types is called function overloading. The whole process is called function overload resolution.

On a very high level, we can view the overload resolution as a two-step process:

  1. Find all overloads of the called function that could viably be called with the given set of arguments.
  2. Pick the best one or issue an error if it’s not possible (e.g., because of an ambiguity).

Consider the following example:

#include <iostream>

void foo(double d)
{
    std::cout << "foo(double)" << std::endl;
} 

int main()
{
    foo(1);     // Calls foo(double)
    foo(1.0);   // Calls foo(double)
}

Listing 1.

This outputs

foo(double)
foo(double)

The compiler looked for all possible definitions of the function foo() and found just one. Since an int can be cast to a double without losing precision, thus foo(double) is called and 1 implicitly cast to 1.0 without even issuing a warning.

What if we created a specialized version of foo() for ints?

#include <iostream>

void foo(int i)
{
    std::cout << "foo(int)" << std::endl;
}

void foo(double d)
{
    std::cout << "foo(double)" << std::endl;
} 

int main()
{
    foo(1);     // Calls foo(int)
    foo(1.0);   // Calls foo(double)
}

Listing 2.

This outputs

foo(int)
foo(double)

As we can see, the compiler prefers a more specialized version (not requiring an argument cast) if one is available.

How is a template function to be called determined?

With function templates, the problem becomes more complicated.

Paraphrasing Bjarne Stroustrup: since a function template is a generalization of a function, the rules governing which function will be called in the presence of templates are more general as well.

A function template is not a function on its own. Only when the template argument is explicitly given (by a programmer or a compiler), then the template becomes a function. The process of creating a function out of a function template is called function specialization. Only a specialized function can then take part in the overload resolution.

In the presence of function templates, the overload resolution procedure works as follows:

  1. Find a set of function template specializations that will take part in the overload resolution. To this end, analyze each available function template with the specified name and try to specialize them for the given set of arguments.
  2. If more than one function template can be used, use the more specialized (more specific) one.
  3. Perform overload resolution with specialized function templates and regular functions. Prefer the latter.
  4. If no match is found or two equally good matches exist, issue an error.

Let’s clarify it through an example.

Let’s imagine, we want to write a C++-style function that takes an iterator range [b, e) and returns the sum of elements from b to the one before e. It is somewhat similar to std::accumulate.

#include <iostream>
#include <vector>
#include <assert.h>

template<typename Iter>
typename Iter::value_type sum(Iter b, Iter e, 
                                typename Iter::value_type out)
{
    std::cout 
        << "sum(Iter b, Iter e, typename Iter::value_type out)" 
        << std::endl;

    while (b != e)
    {
        out += *b++;
    }
    return out;
}

int main()
{
    std::vector a {1, 2, 3, 4};
    auto c0 = sum(a.begin(), a.end(), 0);
    auto c1 = sum(a.data(), a.data() + 4, 0); // Compilation error!
    assert(c0 == c1);
}

Listing 3.

Note: std::vector<T>::data() returns a pointer (T*) to the underlying memory block that allows low-level value manipulation.

On gcc 11.1 I got the following error:

<source>: In function 'int main()':
<source>:21:18: error: no matching function for call to 'sum(int*, int*)'
   21 |     auto c1 = sum(a.data(), a.data() + 4); // error!
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~
<source>:6:27: note: candidate: 'template<class Iter> typename Iter::value_type sum(Iter, Iter)'
    6 | typename Iter::value_type sum(Iter b, Iter e)
      |                           ^~~
<source>:6:27: note:   template argument deduction/substitution failed:
<source>: In substitution of 'template<class Iter> typename Iter::value_type sum(Iter, Iter) [with Iter = int*]':
<source>:21:18:   required from here
<source>:6:27: error: 'int*' is not a class, struct, or union type

It says that no matching function has been found that would correspond to the sum(a.data(), a.data() + 4) call. It additionally states that an attempt to specialize the sum(Iter, Iter, typename Iter::value_type out) template failed, because the type int* does not have a member type value_type that appears in the function declaration.

Let’s fix this quickly:

#include <iostream>
#include <vector>
#include <assert.h>

template<typename Iter>
typename Iter::value_type sum(Iter b, Iter e, 
                                typename Iter::value_type out)
{
    std::cout 
        << "sum(Iter b, Iter e, typename Iter::value_type out)" 
        << std::endl;

    while (b != e)
    {
        out += *b++;
    }
    return out;
}

template<typename T>
T sum(T* b, T* e, T out)
{
    std::cout << "sum(T* b, T* e, T out)" << std::endl;

    while (b != e)
    {
        out += *b++;
    }
    return out;
}

int main()
{
    std::vector a {1, 2, 3, 4};
    std::vector b {1.0, 2.0, 3.0, 4.0};
    auto c0 = sum(a.begin(), a.end(), 0);
    auto c1 = sum(a.data(), a.data() + 4, 0);
    assert(c0 == c1);
}

Listing 4.

This compiles, runs fine, and outputs

sum(Iter b, Iter e, typename Iter::value_type out)
sum(T* b, T* e, T out)

Here we have two function templates with the same name. The compiler tries to specialize sum(Iter b, Iter e, typename Iter::value_type out) by substituting int* for Iter. It fails because int* does not have a member type value_type (just as before in Listing 3). However, this time it does not issue an error because there is another function that satisfies the call, i.e., sum(T* b, T* e, T out). (The fact that this function is a template specialization does not matter here).

We hence discovered that substitution failure is not an error; the compiler failed to substitute int* for Iter in sum(Iter b, Iter e, typename Iter::value_type out) but didn’t report an error because the function call could be carried out using a different function.

In the initial template example in Listing 3, the error was not a substitution failure: it was the lack of a possible function to call.

To make it even more clear, let’s consider the last version of the sum() function:

#include <iostream>
#include <vector>
#include <assert.h>

template<typename Iter>
typename Iter::value_type sum(Iter b, Iter e, 
                                typename Iter::value_type out)
{
    std::cout 
        << "sum(Iter b, Iter e, typename Iter::value_type out)" 
        << std::endl;

    while (b != e)
    {
        out += *b++;
    }
    return out;
}

template<typename T>
T sum(T* b, T* e, T out)
{
    std::cout << "sum(T* b, T* e, T out)" << std::endl;

    while (b != e)
    {
        out += *b++;
    }
    return out;
}

int sum(int* b, int* e, int out)
{
    std::cout << "sum(int* b, int* e, int out)" << std::endl;

    while (b != e)
    {
        out += *b++;
    }
    return out;
}

int main()
{
    std::vector a {1, 2, 3, 4};
    std::vector b {1.0, 2.0, 3.0, 4.0};
    auto c0 = sum(a.begin(), a.end(), 0);
    auto c1 = sum(b.data(), b.data() + 4, 0.0);
    auto c2 = sum(a.data(), a.data() + 4, 0);
    assert(c0 == c1);
    assert(c1 == c2);
}

Listing 5.

This compiles and runs without an error. The output reads:

sum(Iter b, Iter e, typename Iter::value_type out)
sum(T* b, T* e, T out)
sum(int* b, int* e, int out)

Let’s quickly analyze what happened here:

  1. sum(a.begin(), a.end(), 0) fails to substitute into sum(T*, T*, T) (iterator is not a pointer) but SFINAE: no error is issued. sum(int*, int*, int) function cannot take part in the overload resolution because the argument types don’t match. However, a template specialization of sum(Iter, Iter, typename Iter::value_type) with Iter equal to typename std::vector<int>::iterator matches and is able to fulfill the call, thus, it is instantiated and called.
  2. sum(b.data(), b.data() + 4, 0.0) fails to substitute into sum(Iter, Iter, typename Iter::value_type) (double* has no member type value_type) but SFINAE: no error is issued. sum(int*, int*, int) function cannot take part in the overload resolution because double* is not implicitly convertible to int*. However, a template specialization of sum(T*, T*, T) with T equal to double matches and is able to fulfill the call, thus, it is instantiated and called. Note that we had to pass 0.0 not 0 here because during template instantiation no argument conversion can take place.
  3. sum(a.data(), a.data() + 4, 0) fails to substitute into sum(Iter, Iter, typename Iter::value_type) (int* has no member type value_type) but SFINAE: no error is issued. For this call we have two possibilities: a template specialization of sum(T*, T*, T) with T equal to int and the function sum(int*, int*, int). According to the overload resolution rules for templates, the function is preferred over the specialization. Thus, sum(int*, int*, int) is called.

How can we use SFINAE to our advantage?

SFINAE Application

We can use SFINAE to explicitly state that we don’t want a particular template specialization to take part in the overload resolution. In our initial template example in Listing 3, by putting typename Iter::value_type in the function template declaration we explicitly stated that only template parameters that have a member type value_type are allowed to be used for specialization.

If we didn’t use typename Iter::value_type in the function declaration but instantiated typename Iter::value_type in the function body, this could lead to an instantiatiation error instead of a substitution failure and possibly to a “lack of a matching function”. The former may be considered less clear than the latter in the compiler output.

We may also use SFINAE as a form of an explicit statement on the assumptions we make about the template parameters as the authors of the template. This is more closely related to concepts in C++ 20. If you want to learn more about the relation of SFINAE to concepts, I encourage you to check out this great video by Jason Turner.

Summary

“Substitution failure is not an error” means that if the compiler fails to specialize a template with a given template argument list, it does not issue an error. It does when it cannot find any suitable function/class to be called/instantiated (either due to a lack of suitably declared functions/classes or an error during instantiation).

Bibliography

[1] Bjarne Stroustrup The C++ Programming Language (4th Edition) Addison-Wesley ISBN 978-0321563842. May 2013.

[2] Jason Turner C++ Weekly - Ep 194 - From SFINAE To Concepts With C++20 watch on YouTube.

[3] SFINAE on Wikipedia https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error. Retrieved: 11.06.2021.