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.

This entry was posted in programming and tagged , , , , . Bookmark the permalink.

16 Responses to Overload resolution

  1. andriuss says:

    While this is very useful technique, sometimes I find no reasonably safe way to use it in face of ODR. Depending on whether “some_glue_between_1_and_2” is included or not, f in framework::process might refer either to framework::f or f<boost::optional>. Now if glue code is included in some translation units, but not in others, ODR is violated. The scariest part is that compiler is not required to warn us. It is very easy to forget to include glue library when it doesn’t lead to compiler error. Worse yet, using framework in generic code will virally propagate this trap to unsuspecting users.

    Putting glue code in one of the libraries is out of question in this blog post. Making default implementation fail to compile when no specialization is found defeats the the whole purpose of customizations.

    Any ideas?

    • This is a very important observation, and I agree with most of what you say. One thing I think I disagree with is the last statement:
      Making default implementation fail to compile when no specialization is found defeats the the whole purpose of customizations.

      I can imagine a framework that defines an operation for built in types and for some small set of well known types. For the rest, it just does not work (compile-time error) unless you provide a customization. This is how std::hash works, I believe.

  2. Bruno says:

    Hi,
    With respect to the last part of your post (“ADL is essential to …”), ADL always struck me as a very heavy solution for the problem at hand. Why is a specialized swap function for a library type not placed in the std namespace? That way it is clear that it follows standard semantics, not some function with accidentally the name “swap”. (There may be some problems with visibility, but that seems less complex than ADL.)
    Operator overloads should always be in the root namespace, since you cannot write “my_lib::<<"
    Regards,
    Bruno

    • andriuss says:

      Because you cannot partially specialize a function. You can’t get around by overloading, because adding overloads to std namespace is forbidden.
      Regarding qualified operator call, in fact you can write “my_lib::operator<<(…)". But why would you need that?

  3. ljwo says:

    Hi Andrzej, I just stumbled over a question related to what you write about, and cannot answer it. I wrote it up on SO, so let me just paste the link: http://stackoverflow.com/questions/34481998/how-to-have-adl-prefer-a-function-template-to-another Will you be addressing that in your future posts? And thanks for the code::dive lecture and for the discussion. Regards. Łukasz

  4. Pingback: A customizable C++ framework | Daily Hackers News

  5. abigagli says:

    Hi Andrzej, great and insightful post!
    But when you say “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.” is the “provided that…” further qualification really necessary? Doesn’t ADL work that way (i.e. adding namespaces of function arguments to the search domain for overloads) regardless of function arguments being dependent on template parameters or not?
    Or am I misunderstanding your sentence?

    • @abigagli: The section you quote describes the 2-stage overload resolution in templates. In short it says: “ADL is only used in the second stage provided that …”, so I think the provision is necessary: it does not say how ADL works, but on what condition ADL is employed.

      Does this make sense?

      • abigagli says:

        OK, so a breakout of the reasoning would be:
        1) ADL works the way it works, but..
        2) When unqualified calls to functions are performed in a function template, and the arguments of such unqualified calls are “template parameters or are dependent on the template parameters”, then ADL is performed during the second stage, i.e. when the function template is instantiated, as opposed as being performed during the first stage (i.e. when the function template body is parsed, which in this case would still make the boost namespace “unavailable”).

        Given point 2) above, since at the instantiation point the boost namespace is fully visible, then the overloads defined in boost are included in the overload set thanks to ADL.

        Am I right?

        • abigagli says:

          Couldn’t reply to your last comment, so I’m backing off at the top-level, but this is really a continuation of the previous thread:

          Great!
          Now, while thinking at it, and to consolidate my understanding, I thought that then there is a way to force ADL to “look again” into the “framework” namespace if we use an additional template parameter that refers to it so that the second-stage ADL lookup will be able to see the complete “framework” namespace as well.
          Not that this would really be more convenient that adding overloads to the “boost” namespace, and it adds some syntactic noise, but actually only on the “internal” side of the framework (i.e. the client-side calls to “process” would remain unchanged).
          I don’t know, maybe someone could prefer to keep all framework related stuff into the framework namespace…
          In any case, here’s my approach if you’re interested (tested with clang 3.7)

          #include

          namespace framework // library 1
          {
          struct enable_adl_in_framework_namespace {};
          constexpr auto framework_ns_enabler = enable_adl_in_framework_namespace{};

          template
          void f(T, enable_adl_in_framework_namespace) { puts(“master”); }

          template
          void process(T v, ADL_ENABLER u=framework_ns_enabler) { f(v, u); }
          }

          namespace boost // library 2
          {
          template
          struct optional {};
          }

          namespace framework // some glue between 1 and 2
          {
          template
          void f(boost::optional, enable_adl_in_framework_namespace) { puts(“optional”); }

          inline
          void f(boost::optional, enable_adl_in_framework_namespace) { puts(“optional”); }
          }

          int main() // our program logic
          {
          int i = 0;
          boost::optional oi;
          boost::optional ob;

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

          Thanks for your awesome blog!

        • You might wish to have a look at the next post: https://akrzemi1.wordpress.com/2016/01/16/a-customizable-framework/
          It describes exactly what you propose.

        • abigagli says:

          Duh! That post was on my call-stack, as I got here following the suggestion to first read this post! I just had not reached that part…
          Now that I’ve read it, your solution is a bit cleaner as I used that ADL_ENABLER template parameter that I now see being completely unnecessary, but I’m glad I got “near enough”… 😉

  6. Igor says:

    In earlier posts you occasionally wrote that it would be nice if C++ Standard was different in some matters but it’s impossible due to backward compatibility. What about adding a feature to the Standard so that on the 2nd stage of function overloading (during instantiating of template function) functions from the “namespace of the function being overloaded” (those weren’t added during parsing – the 1st stage) were added to the overload set? Would you like to see it in the Scott Meyers’ “Break those eggs!” list, for example? ( http://scottmeyers.blogspot.ru/2015/11/breaking-all-eggs-in-c.html ) Declaration of framework’s “f()” function in “boost” namespace looks unnatural to me.

    • Actually, I would not. In this post, I show a two-phase lookup used for the purpose of implementing a customization point. From this perspective (of customization points), a two-phase lookup may seem faulty, but this is only one perspective, and in general, the two-phase lookup works just fine, and tweaking with it might (as far as I can see) make the language worse.

      Instead, I can see how the language could be changed in a backwards-compatible way to facilitate customization points directly: by adding a dedicated feature. Imagine a new keyword customization_point:

      namespace std {
        template <typename T>
        customization_point void swap(T&, T&)
        { /* default impl */ }
      
        template <typename T, int N>
        void swap(T(&)[N], T(&)[N])
          : std::swap<T(&)[N]> // customization for arrays
        { /* implementation for arrays */ }
      }
      
      namespace my_program {
        template <typename T>
        void swap(boost::optional<T>&, boost::optional<T>&) 
          : std::swap<boost::optional<T>> // customization for boost::optional in unrelated namespace 
        { /* implementation */ }
      }
      

      Now you can use it qualified with namespace std:

      boost::optional<int> o1, o2;
      std::swap(o1, o2); // picks customization
      

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s