Overload resolution

This post is an introduction to another one that I intend to write in the future. The goal of this one is to go over the concepts of function template specialization, function (template) overloading, argument dependent lookup (ADL) and overload resolution. By no means do I intend to make it a complete reference. My only goal is to briefly show what these things are, what they can do, and what they cannot do, so that you can use them to solve practical problems. I tried to make this post as easy to understand as possible and to avoid the technical nomenclature where possible.

Setting up the stage

In the examples we will be using class template boost::optional as an example of a third party library. If you don’t know it, or cannot use it just imagine the following definition:

// header <boost/optional.hpp>

namespace boost
{
  template <typename T>
  struct optional {};
}

Simple function overloading

Now imagine another library with the following three function definitions:

namespace framework
{
  template <typename T>
  void f(T) { puts("master"); }
    
  template <typename T>
  void f(boost::optional<T>) { puts("optional<T>"); }
  
  inline  
  void f(boost::optional<bool>) { puts("optional<bool>"); }
}

Pardon me the usage of C-like function puts. I only use it in order to make the examples shorter. What it does is to print the string in the argument, followed by a new-line, into the standard output stream.

For similar reasons I am passing arguments to functions by value. In real programs, you would probably pass them by an lvalue reference to const.

I have provided three definitions associated with name f. Name f is overloaded. It refers to one function and two function templates.

This is a good place to outline the difference between phrases ‘template function’ and ‘function template’. The former suggests one function (e.g., with a single address) with some special power of being able to bind to any type. The latter says that there is no function, but a generator that is capable of generating functions on demand. The latter phrase more correctly reflects what is really going on and in fact only this phrase is used in the C++ Standard.

Thus, we have one function definition and two definitions of ‘generators’ capable of generating function definitions: The first one can generate (or formally: instantiate) a function with name f taking any type (including type boost::optional<bool>). The second can generate a function with name f taking any instantiation of class template boost::optional (also including type boost::optional<bool>).

If we now write the following test program,

int main()
{
  int i = 0;
  boost::optional<int>  oi;
  boost::optional<bool> ob;

  framework::f(i);
  framework::f(oi);
  framework::f(ob);
}  

We observe, unsurprisingly, that the output is:

master
optional<T>
optional<bool>

In the first function call (f(i)) out of three overloads, only the first one is applicable (other only work for optionals).

In the second call, we have two viable candidates, the most generic function: the first overload, and the second overload, which binds to ‘optional’. But because the second overload is ‘more specialized’ than the first, it gets selected. I will skip over what it formally means to be ‘more specialized’, but intuitively, in the case of one-argument functions, you can think of it as pattern matching rules.

In the third call, all the three overloads would work, but obviously, the third one is the most specialized for the type of ob.

Simple function template specialization

Now let’s try a similar trick, but instead of having a number of overloads, we will have only one, but with explicit specializations.

namespace framework
{
  template <typename T>
  void f(T) { puts("master"); }
    
  template <>
  void f<boost::optional<bool>>(boost::optional<bool>)
  { puts("optional<bool>"); }  
}

int main()
{
  int i = 0;
  boost::optional<bool> ob;

  framework::f(i);
  framework::f(ob);
} 

Now, we only have one function template. The specialization we provide for boost::optional<bool> only means that for this type, the body instantiated from the template will be different than usual.

If we run it, we get the similar result as before:

master
optional<bool>

In both calls to f the same function template gets chosen, but in the next stage, the compiler checks if the template has not been explicitly specialized for the argument. In the second call it does find a specialization, and uses it.

So, is there any difference between adding function template overloads or specializing a template?

To show you one, let’s try to mix overloading with explicit specialization.

namespace framework
{
  // primary template
  template <typename T>
  void f(T) { puts("master"); }

  // specialization
  template <>
  void f<boost::optional<bool>>(boost::optional<bool>)
  { puts("optional<bool> specialize"); }
    
  // overload
  void f(boost::optional<bool>)
  { puts("optional<bool> overload"); }
}

int main()
{
  int i = 0;
  boost::optional<bool> ob;

  framework::f(i);
  framework::f(ob);
} 

the question is, which will get chosen: the more specialized overload or an explicit specialization?

master
optional<bool> overload

As I told you, the first thing the compiler does is to select the best overload. And this is what it did. It does not care that there was an explicit specialization of a function template that was not selected.

Now, in the example with function template specialization we have seen the ‘full’ specialization for type boost::optional<bool>, but no ‘partial’ specialization for any boost::optional<T>. So let’s try it:

namespace framework
{
  // primary template
  template <typename T>
  void f(T) { puts("master"); }

  // partial specialization
  template <typename T>
  void f<boost::optional<T>>(boost::optional<T>)
  { puts("optional<T>"); } 
    
  // full specialization
  template <>
  void f<boost::optional<bool>>(boost::optional<bool>)
  { puts("optional<bool>"); }  
}

I do not even have to test it because the above set of declarations does not compile. The compiler understands our intention, and recognizes the declaration as partial specialization of function template, but following the Standard, gives us a message: “function template partial specialization is not allowed”.

But haven’t we already seen partial template specialization used, also in the Standard Library? Well, it does work for class templates: it only does not work for function templates. I remember once seeing the rationale for this: since function templates can already be overloaded, there is no need to offer also partial function template specializations to the language (and further complicate the overload resolution process). This rationale sounds fine at first, but let’s dig further.

Name lookup in templates

Now let’s consider a slightly more complicated example (the explanation follows):

#include <cstdio>

namespace framework  // library 1
{
  template <typename T>
  void f(T) { puts("master"); }

  template <typename T>
  void process(T v) { f(v); } 
}

namespace boost      // library 2
{
  template <typename T>
  struct optional {};
}

namespace framework  // some glue between 1 and 2
{     
  template <typename T>
  void f(boost::optional<T>) { puts("optional<T>"); }
   
  inline 
  void f(boost::optional<bool>) { puts("optional<bool>"); }
}

int main()           // our program logic
{
  int i = 0;
  boost::optional<int>  oi;
  boost::optional<bool> ob;
 
  framework::process(i);
  framework::process(oi);
  framework::process(ob);
}

This reflects a real-life use case, where we want to integrate two libraries in our program. The pattern can be conceptually described as follows:

#include <library_1>
#include <library_2>
#include "some_glue_between_1_and_2"
our_program_logic();

That is, library_1 is provided (possibly by a third-party vendor) without any knowledge or reference to library_2. And vice versa. Ideally any two libraries would just immediately inter-operate with one another — and sometimes this is the case — but in other cases we have to teach the two libraries how to talk to one another.

Thus, the first opening of namespace framework corresponds to including the interface header of the first library. Function template process is the real interface to be used by end-user programmers. Function template f is a customization point: its intention is to provide a way to teach the library how to inter-operate with other types, that are not known in advance. Such ‘teaching’ is typically achieved by specializing or overloading the template function.

The opening of namespace boost corresponds to including another library. The second opening of namespace framework, with two overloads, corresponds to the gluing code that is intended to teach the first library how to work with the second library. Finally, in function main we try to use both libraries in harmony.

So let’s run the program:

master
master
master

The result is not what we intended!

The reason should be quite obvious: when the body of function template process is parsed only the ‘master’ function template f is seen, and it is selected. The two overloads that are declared later — even though they are defined in the same namespace as the master — do not affect what is visible inside the body of process. We could fix our small example by moving the definition of boost::optional to the top and putting the two overloads before the definition of process:

namespace boost
{
  template <typename T>
  struct optional {};
}

namespace framework
{
  template <typename T>
  void f(T) { puts("master"); }

  template <typename T>
  void f(boost::optional<T>) { puts("optional<T>"); }
   
  inline 
  void f(boost::optional<bool>) { puts("optional<bool>"); }

  template <typename T>
  void process(T v) { f(v); } 
}

But that would not work in real programs where we need to preserve the model:

#include <library_1>
#include <library_2>
#include "some_glue_between_1_and_2"
our_program_logic();

One could say that we just need to force on the users a more complicated model of composing two libraries, where you need to declare more headers:

#include <library_1/declarations>
#include <library_2/declarations>
#include "some_glue_between_1_and_2"
#include <library_1/algorithms>
#include <library_2/algorithms>
our_program_logic();

But that would make the life of programmers more difficult, and the usage of libraries bug prone: if the user includes the headers in the wrong order, the program may still compile but do something else than before. If changing the order of the headers changes the semantics of the program, this is really dangerous.

If we tried to use function template specializations rather than function (template) overloads:

#include <cstdio>

namespace framework  // library 1
{
  template <typename T>
  void f(T) { puts("master"); }

  template <typename T>
  void process(T v) { f(v); } 
}

namespace boost      // library 2
{
  template <typename T>
  struct optional {};
}

namespace framework  // some glue between 1 and 2
{     
  template <>
  void f<boost::optional<bool>>(boost::optional<bool>)
  { puts("optional<bool>"); }
}

int main()           // our program logic
{
  int i = 0;
  boost::optional<bool> ob;
 
  framework::process(i);
  framework::process(ob);
}

It works:

master
optional<bool>

That is, process sees only one function template, but the process of looking up specializations of f takes place not upon parsing the body of process but later: upon instantiating process (when generating a real function from a template).

But as we already know, there are no partial function template specializations, so this also does not solve our problem.

Argument dependent lookup

Interestingly, there is a way to make out 2-library example work. And if you are not familiar with argument dependent lookup (or ADL), you might be surprised at why and how it works. Let me first give you a solution first, and then try to explain:

#include <cstdio>

namespace framework  // library 1
{
  template <typename T>
  void f(T) { puts("master"); }

  template <typename T>
  void process(T v) { f(v); } 
}

namespace boost      // library 2
{
  template <typename T>
  struct optional {};
}

namespace boost      // some glue between 1 and 2
{     
  template <typename T>
  void f(optional<T>) { puts("optional<T>"); }
   
  inline 
  void f(optional<bool>) { puts("optional<bool>"); }
}

int main()           // our program logic
{
  int i = 0;
  boost::optional<int>  oi;
  boost::optional<bool> ob;
 
  framework::process(i);
  framework::process(oi);
  framework::process(ob);
}

The only difference is in the ‘glue’ part: I still provide two overloads, but I changed the namespace from framework to boost. And all of a sudden the program works as intended:

master
optional<T>
optional<bool>

So, function template process cannot see overloads (defined subsequently) from namespace framework, but can see similar overloads from namespace boost?

Yes. The way function overloads are resolved inside templates is (as you can see) quite funny. I will not be able to tell you how it works in every detail, but hopefully the explanation will be sufficient to enable you to do some useful things with it.

First, note that inside function process we call function f without any namespace- or class-scope qualification:

template <typename T>
void process(T v) { f(v); } 

If we called it like this:

template <typename T>
void process(T v) { ::framework::f(v); } 

It would break the solution, an none of what I am about to describe would apply.

So, in the case when you call a function without any scope qualification, overloads are resolved in two stages. The first stage happens at the point of parsing the template function (process) body. In this stage, we consider the overloads from our namespace, enclosing namespaces, and namespaces imported with using-directive. This is why we see the ‘master’ template function.

The second stage takes place at the point when the template function (process) is instantiated (when a real function is produced from the template). In this stage, we add to the overload set functions from the namespaces that enclose arguments in the function (f) call, provided that these arguments’ types are template (process) parameters or are dependent on the template parameters. In our case, when process is instantiated with type boost::optional<int>, class template boost::optional is defined in namespace boost, because an object of this type (more precisely: of the type instantiated from the class template) is one of the arguments (in fact, the only argument) to the call of function f, namespace boost is searched for matching function overloads f. We find some, so they are added to the overload set, and are no worse than the candidates found in the first phase.

In our example, the instantiation of process happens inside function main, so by that time the other two overloads have been defined.

Bizarre as it may seem, the ADL is essential to allow us to define the operators in the same namespace as the types they operate on:

namespace my_lib
{
  class tool { /*...*/ };
  std::ostream& operator<<(std::ostream&, const tool& t);
}

int main()
{
  my_lib::tool t;
  std::cout << t; // works due to ADL
}

The ADL is also used by the swap functionality in the Standard Library. The typical advice for correctly swapping objects is to employ the following pattern:

template <typename T>
void test(T& a, T& b)
{
  using std::swap; // consider overloads from std
  swap(a, b);      // consider overloads via ADL
}

If we wrote it like this:

template <typename T>
void test(T& a, T& b)
{
  std::swap(a, b); // disable ADL
}

The call to swap is scope-qualified, so ADL is disabled, and if the swap overload is provided in the namespace of T (and T happens to be my_lib::tool) it is ignored.

If we wrote it like this:

template <typename T>
void test(T& a, T& b)
{                  // no namespace std (unless via ADL)
  swap(a, b);      // consider overloads via ADL
}

This would not pick the std::swap for types without custom swap as well as for built-in types.

This is why the STL advice for swap is the way it is.

So, that’s it for today. In the next post we will try to make use of this knowledge.

Acknowledgements

I would like to thank Piotr Bartosik and Tomasz Kamiński for inspiring this post and their useful feedback.