1???Executive Summary

This proposal:

• Eliminates unpredictable and unintended overloading due to argument-dependent lookup (ADL)
• Provides a way to be explicit about where ADL should apply
• Provides a clean way for generic libraries to supply points-of-customization (e.g. swap) for user-defined types
• Eliminates the problem of unintended "name reservation" when overloading is used for customization (see N1296)
• Allows clients to be explicit about which algorithm they mean to customize via overloading
• Reduces the "syntactic weight" of client-supplied template specializations.
• And describes how existing code (and even the standard library) can be migrated to use the new facility.

2???Background

Before the introduction of namespaces to C++, it was a common practice to apply "prefixes" to all names with external linkage, in an attempt to avoid unpredictable collisions between code in applications and the libraries they linked to. As long as the prefixes were reasonably long, this practice worked reasonably well, and is still being used effecively for preprocessor macros. The major disadvantage of prefixes is aesthetic: there is no way to avoid using the prefix within user code or even within the context of a library's own definition.

Namespaces gave users and library writers a way to partition the set of all names so that the use of qualification (the namespace mechanism's replacement for prefixing) could be avoided for names defined in local or enclosing contexts. Via using-declarations and using-directives, we also provided a mechanism for using names from other namespaces without qualification, thus combining convenience with protection.

The system described so far is intuitive, convenient, and safe: an entity in the local namespace or in any enclosing namespace can be accessed without qualification, and entities in other namespaces can either be explicitly qualified or brought into the local scope with a using declaration for convenience. Many new programmers expect namespaces to work exactly this way.

// main.cpp:
#include <vector>

namespace user
{
   typedef std::vector<Customer*> index;

   // copy an index, selecting deep or shallow copy for Customers
   void copy(index const&, index&, bool deep);

   void g(index const& x)
   {
      copy(x, x, false);
   }
}

#include <tr1/shared_ptr>
#include <tr1/tuple>

namespace communications
{
    class Channel;
}

namespace user
{
   typedef tr1::shared_ptr<communications::Channel> pipe;

   // Connect p2 to the output of p1
   tie(pipe const& p1, pipe& p2);

   void g(pipe p1, pipe p2)
   {
      tie(p1, p2);  // calls tr1::tie
   }
}

3???A Solution

The solution I'll propose here centers around a different kind of namespace with new lookup rules, on the assumption that breaking backward compatibility of existing namespaces is unacceptable. I would dearly love to find a solution that didn't involve major language changes, but I don't see any alternative that allows the compiler to help library authors prevent unintended argument-dependent lookups.

The new entity is called an "explicit namespace", and is declared by preceding the namespace keyword with explicit, as follows:

explicit namespace new_std
{
    // declarations and definitions
}

The lookup rules in an explicit namespace differ from those in an old-style namespace as follows:

I.

By default, argument-dependent lookup does not take effect for arbitrary unqualified calls made within definitions in an explicit namespace.

II.

Argument-dependent lookup can be enabled for specific names through the use of an unqualified using-declaration:

explicit namespace new_std::
{
   using swap; // enables argument-dependent lookup of 
               // "swap" from within new_std

   template <class Iterator>
   void sort(Iterator start, Iterator finish)
   {
      ...
      swap(*a, *b); // uses argument-dependent lookup
      ...
   }
}

The unqualified using-declaration can also be used within a function template definition, further limiting the scope of its effect:

explicit namespace new_std
{
   template <class Iterator>
   void sort(Iterator start, Iterator finish)
   {
      using swap; // allows argument-dependent lookup of "swap" from
                  // within new_std::sort

      ...
      swap(*a, *b); // uses argument-dependent lookup
      ...
   }
}

III.

In templates in explicit namespaces, functions calls that do not use argument-dependent lookup but whose arguments are dependent types are bound to actual overloads at instantiation time. However, such calls must match some declaration in name and arity at template definition time: ³

explicit namespace new_std
{
   template <class Iterator>
   void iter_swap(Iterator x, Iterator y)
   {
      swap(*x,*y); // error: no swap defined in new_std or ::
   }

   template <class T> void swap(T&, T&);

   template <class Iterator>
   void sort(Iterator start, Iterator finish)
   {
      ...
      swap(*a, *b); // OK: the swap above could match
      ...
   }
}

Binding at instantiation time ensures that overloading in the algorithm's namespace is a viable means of customization, with no dependency on #include order.

Overloading in the algorithm's namespace solves the library interoperability problems implied by asking users to provide overloads for each library in her own namespace.

Requiring a match at definition time allows template definitions to be syntax-checked before instantiation. Since nobody will be using argument-dependent lookup by mistake in an explicit namespace, it should be possible in practice to check syntax much more thoroughly in an explicit namespace than in an ordinary one.

IV.

To make generic library customization convenient, functions and templates previously declared in other namespaces can be overloaded and specialized "remotely", without opening the other namespace. This capability applies to both ordinary and explicit namespaces:

#include <complex>
#include <algorithm>

namespace user
{
   class fixedpoint
   {
      ...
   };

   // Specialize std::complex
   template <> class std::complex<fixedpoint>
   {
     ...
   };

   void std::swap(fixedpoint&, fixedpoint&);   // OK

   // illegal by current rules, and also under new rules:
   // vector not yet declared in std::
   template <> class std::vector<fixedpoint>;

   // illegal by new rule: iter_swap() not yet declared in std::
   void std::iter_swap(fixedpoint*, fixedpoint*);
}

For function overloads, a declaration of a function with the same number of arguments in the target namespace must already be visible: ⁴

#include <algorithm>
namespace user
{
   void std::swap(fixedpoint&, fixedpoint&, int); // illegal
}

The same technique applies to the "Barton & Nackman trick", allowing it to be used to provide customizations for explicit namespaces:

namespace user
{
   class fixedpoint
   {
      ...
      friend fixedpoint newstd::math::sin(fixedpoint)
      {
         ...
      }
   };
}

Friend functions defined in this way would not be subject to the usual restrictions that prevent them from being found other than through argument-dependent lookup (see Sections 3.4.1 paragraph 1 and 11.4 paragraph 9 of the standard).

V.

Operators within an explicit namespace should be treated the same way as any other function. Argument-dependent lookup could be explicitly enabled through the use of unqualified using-declarations:

template <class T>
T square(T x)
{
   using operator*;
   return x * x;
}

Those seeking to conveniently enable argument-dependent lookups for all operators within an explicit namespace could easily create a header file that does so:

namespace mymath::
{
   #include "using_ops.hpp"
}

VI.

Partial specialization of function templates would be allowed per N1295. It's worth discussing whether element III of this proposal is needed once we have partial specialization of function templates.

4???Implications for Namespace std and Other Libraries

N1523 describes the WP status resolution to LWG 225, 226, and 229. It allows algorithms in namespace std to call other selected algorithms, most notably swap, without qualification so they can be found via argument-dependent lookup. If we continue to follow that course, implications for std are minimal. Authors of generic libraries in other namespaces must always add a using-declaration to bring the generalized algorithm into scope at the point of use, but this is status quo:

namespace lib1
{
  template<class Iterator>
  void lib1_permutation(Iterator start, Iterator finish)
  {
     ...
     using std::swap; // so we can swap built-in types
     swap(x, y);
     ...
  }
}

It is worth noting that when a generalized version of an algorithm exists, as in the case of swap, that algorithm is effectively associated with a namespace. The using-declaration becomes a clumsy form of qualification that indicates the algorithm's home.

If we choose to follow the course of using argument-dependent lookup to allow customization in namespace std, this proposal at least allows implementors to migrate the standard library to a safer explicit namespace without breaking backward compatibility. The list of names and call contexts where argument-dependent lookup takes effect could simply be encoded in unqualified using-declarations.

If we choose not to allow further argument-dependent lookup in namespace std, it could still become an explicit namespace, and implementations could drop their qualification of calls to algorithms like copy. We could grant permission to create overloads in std:: consistent with the standard versions of the same function, allowing users to customize exactly the intended standard library algorithm. Other libraries would call standard algorithms with qualification as usual, and would not need to rely on argument-dependent lookup to resolve the calls.

5???Conclusion

The future of C++ lies in its power to make great libraries, so the issues of library interoperability, customization, and robustness must be taken seriously. If we compare the C++ standard library with the sprawling libraries of languages like Java or Python, it's easy to see that the potential to increase the number of namespaces competing for an unqualified name is enormous. This proposal puts the compiler's static checking at the service of library authors and allows users to conveniently and precisely express the notion of algorithm customization.

(copy)(x, x, false)