I decided to write an article about the Substitution Failure for people who are looking for a clear and step by step introduction about it.
Note: if you have found out errors or misconceptions in this article, please fix it.
The first thing we should understand before we digging into the SFINAE concept is the Name Lookup mechanism. What is that?
When we start to write a program, our final program is nothing more than lots of functions/methods/classes/structs or …, in which all of these components have not any meaning for the dynamic loader of the operating system except their addresses and also their opcodes/instructions. For example, consider the following simple function (It is just an example):
If the Operating System (Windows) would execute this function, it needs the address of the DoingRandomness function after it gets load into the memory. In different operating systems, we have a different file format for the executable files in which the dynamic loader of the operating system can use the information of that file format to specify the exact location of functions and other essentials components.
So the CPP compiler in the compilation/linking phase must specify the address of the Doing and other functions like main in the memory and fills Optional Header and other PE essential attributes with those addresses and offsets.
But how compiler/linker does address resolution from a high-level point of view? Simply, It goes through a mechanism which is called Name Lookup / Address resolution.
First, it discovers in what translation unit/namespace the function has been declared and then it goes there and calculates the address of the functions of the program and other components.
Then it starts to fill PE essential attributes and tables like ImageBase attribute with the exact loading location of the EXE file in the memory and AddressOfEntryPoint attribute value which is the offset of the main function to the ImageBase value in the memory.
For example, when the compiler fills PE attributes with those addresses and information dynamic loader of the Windows can use ImageBase + AddressOfEntryPoint to specify the exact location of the main function in the memory which is 0x00400000 + 0x0001140B = 0x0041140B.
When the compiler specifies the address of the function in the memory, we can call it in the main function (or other places) and use it. Indeed, it is a simple process for those free functions that defined in global namespaces or even other namespaces but for template functions, everything is different and takes more effort. Simply we can summarize function lookup process of a free function in the following steps:
- Name Lookup
- Address Resolution (ImageBase + Offset)
- Getting of Absolute Address.
As I said before everything is different when you come to template functions. For example when we define the following template function (as an example for representation purpose):
CPP Compiler suite must go through the following steps that can finally specify an address dedicated to a function which we can call it and use it proudly.
- Name Lookup
- Argument Type Deduction
- Type Substitution
- Generate an Overload Sample of Function
- Add Overloaded Function to Overload Sets
As a usual resolution process, when you declare a template function or even a free function, the compiler/linker must specify in what translation unit or namespace the function has been declared and defined.
When it finds out in what unit/namespace it has been defined, in second steps it must be deduced what kind of argument type passed to the template function in the order it can generate an overloaded function of Doing based on template function of Doing. For example, consider the following one:
When the compiler sees the above code, it deduced argument type passed to the function has an std::string type, so in the next step, it tries to substitute T type name of Doing template function with a const std::string& type, as the following example has shown:
After type substitutions did successfully, the compiler can generate a free function as the above one and add it to an overloaded set of Doing function template. Finally, the compiler can calculate the absolute address of the function and we can call it and use it. But what will happen, if the programmer calls the following function?
Yes, here is the nightmare. If we call the function as above one for template function instantiation, the compiler will fail in the type substitution step because there isn’t a match candidate for the above instantiation with Doing(std::string&, const char).
Simply type substitution step has been failed here. In other words, type substitution failure has happened here and the compiler will generate an error for it, however, substitution failure is an error here. right?
When we write a program, we may encounter these kinds of problems/errors in which we can handle these errors/problems of metaprogramming through different techniques.
For example, if substitution failure happens like this one, we can change the template function with the following implementation to handle the type substitution error when the instantiation of the template function.
Or we can use a template specialization, or other techniques available in metaprogramming to handle these kinds of issues but you know, there is some situation in which substitution failure is not an error for the compiler.
So when we say SFINAE, we mean this thing. In other words, This rule applies during overload resolution of function templates: When substituting the explicitly specified or deduced type for the template parameter fails, the specialization is discarded from the overload set instead of causing a compile error. As a result, our program may generate the wrong result or output for us because it has the wrong implementation.
Nevertheless, either we notice substitution has happened or not, it is just a failure in which we can handle it via a thousand ways, like template specialization, template overloading, enable_if … I hope, my notes about SFINAE have helped you to understand what is it whole about.