Pizer’s Weblog

programming, DSP, math

Fun with C++ namespaces [sarcasm]

leave a comment »

Last update: 2008-10-28.

I usually tend to defend C++ but name lookup is probably one of the most complicated things in C++ to wrap your head around. Namespaces are supposed to make your life easier. They provide means to group certain things together, to avoid name clashes between two parts of your program that might have been developed independently. Since typing fully qualified names is tedious people like to use short cuts: using directives and using declarations. So far so good. How well does this work together with generic programming?

Consider for a moment that you want to write a generic function that calculates the length of a right-angled triangle’s hypotenuse given the lengths of the other two sides. A generic implementation might look like this:


template<class T>
T hypot(const T& x, const T& y) {
   return sqrt( x*x + y*y );
}

You want this to work on both, fundamental floating point types (float, double, …) as well as user-defined types (high precision float for example). Then, you have to think about how the name ‘sqrt’ will be resolved. For user-defined types this not a problem. There’s a thing called ADL (argument-dependent lookup) which will make the compiler consider all functions in ‘associated namespaces’. If you call sqrt(my_type) where ‘my_type’ is your user-defined type defined in the namespace NS, the compiler will also check the namespace NS for a function called ‘sqrt’ and include it in the so-called overload set. The overload set is a set of functions the compiler uses for overload resolution (= picking the best match for a ‘sqrt’ function in our case). Of course we’d like to have the right function in our overload set. Fundamental types, however, don’t have associated namespaces. So, there’s no ADL for fundamental types which is why we need to make sure that std::sqrt(float), std::sqrt(double) and std::sqrt(long double) are part of our overload set. Up until an hour ago I thought I was aware of how name lookup would actually work. But I was wrong. Let’s tickle the C++ compiler with the following program:


namespace A
{
   void f(int x); // like our std::sqrt(double)
}

namespace B
{
   struct S {}; // user-defined type with associated namespace B

   void f(S);

   void f(int, int);

   void test1() {
      using namespace A; // using DIRECTIVE
      f(1);       // ERROR  namespace A is not considered because
                  //        B contains two overloads for 'f'
      f(1,2);     // OK     B::f(int,int)
      f(B::S());  // OK     B::f(S)
   }   

   void test2() {
      using A::f; // using DECLARATION
      f(1);       // OK     A::f(int)
      f(1,2);     // ERROR  A::f  hides  B::f(int,int)
      f(B::S());  // OK     B::f(S) due to ADL!
   }
}

namespace C
{
   void test3() {
      using namespace A; // using DIRECTIVE
      f(1);       // OK     A::f(int)
      f(B::S());  // OK     B::f(S) due to ADL!
   }   

   void test4() {
      using A::f; // using DECLARATION
      f(1);       // OK     A::f(int)
      f(B::S());  // OK     B::f(S) due to ADL!
   }
}

Let’s check the name lookup rules that can explain the compiler’s behavior. The following rules are a short digested version of the rules mentioned in the standard:

  • A using declaration introduces a declaration in the current scope. It may appear at namespace, function and class scope. Though, at class scope it plays a special role: It can only reintroduce a member from a base class and make it visible again in case it’s overloaded in the derived class.
  • The compiler checks scopes from innermost to outermost and stops immediately once it has found declarations in the current scope of question. This is why one function can hide other functions.
  • A using directive temporarily injects the namespace’s names in the global scope (::) so they are also considered in the above search when the outermost scope is checked for names. This may lead to ambiguities. A using directive may not be used at class scope.
  • The names found so far are part of the overload set. Note: names from outer scopes the compiler didn’t visit because it already found some names are hidden and not part of this set.
  • argument-dependent lookup kicks in: Associated scopes are searched. Found names are added to the overload resolution set. There’s an exception to this rule: If the name in question is mentioned in a member function that refers to another member function of the same class, ADL isn’t applied.

Every C++ programmer should know the gist of these rules. Though, I have to admit I wasn’t aware of all the details regarding the rules’ precedences and exceptions. I’m sure it happens from time to time that the compiler behaves contrary to a programmer’s expectations.

Back to our generic function example: What’s the best way to make std::sqrt visible? Good question. For now, I’d settle with a using declaration. It may hide a ‘sqrt’ function from outer scopes but it doesn’t prevent ADL:


template<class T>
T hypot(const T& x, const T& y) {
   using std::sqrt;
   return sqrt( x*x + y*y );
}

This solution is also applied in most C++ standard library algorithms that need to swap two elements. The fully qualified name for the generic swap function (std::swap) avoids ADL. This is not desirable because it makes special swap functions for user-defined types inaccessible unless the user specifically provides a specialization for swap in the std:: namespace.

Fortunately, the new C++ standard will make another solution possible. We can get rid of the using declaration and replace it with a requirement:


template<class T>
   requires std::FloatingPointLike<T> && std::HasSqrt<T>
T hypot(const T& x, const T& y) {
   return sqrt( x*x + y*y );
}

In this version of a restricted template a concept_map for the HasSqrt<T> concept takes care of our name lookup problem. Nice!

Relevant links are:

Is something wrong? Add a comment.

– P

Advertisements

Written by pizer

October 22, 2008 at 5:21 pm

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

%d bloggers like this: