Friday, January 13, 2006

C++: Strange name lookup

This is something I never knew and read about it recently in "Exceptional C++". Let me start with a code example...

namespace A {
  class S { };
  void foo(S& parm) { }
}

namespace B {
  void foo(A::S& parm) { }
  void bar(A::S& parm) {
    foo(parm); // Which "foo" does this call?
  }
}

Try this out and to your surprise you'll find that this gives a "call to foo is ambiguous" error. But why?? The only foo visible at the place of call is in namespace B. Why should this result in an error? Okay, now try this out - comment out the "foo" definition in namespace B.

namespace A {
  class S { };
  void foo(S& parm) { }
}

namespace B {
  // void foo(A::S& parm) { }
  void bar(A::S& parm) {
    foo(parm); // Which "foo" does this call?
  }
}

This compiles without errors! Surprised again? When you run the program, it'd have called A::foo. What happened here? Does this not appear to be a namespace violation. Apparently not! This strange behavior is explained by "Koenig lookup" also known as "Argument dependent lookup".

If you supply a function argument of class type (here parm, of type A::S), then to find the function name the compiler considers matching names in the namespace (here A) containing the argument's type.

But still, is'nt this a namespace violation?? NO. Just consider this piece of code...

std::string str("Hello");
std::cout << str;

This works fine right? How? This works because of Koenig lookup. The function in question here is "operator <<" which is found in "namespace std". But we have'nt used any "using" declaration to bring that function into the current scope. Since std::string is going as an argument into that function, the compiler will automatically look into the std namespace and will find that function. Without this kind of lookup, the same function call would have to be written as...

std::operator <<( std::cout, str) ; // ugly! ain't it??

This is the great value that Koenig lookup gets us and we tend to use it every now and then without realising it. Interesting - is'nt it??

3 comments:

Shantanu said...

Gem of an article Srinivas..
Indeed Look up mechanism in C++ is interesting (if I am allowed to put it that way)

In Reference to "http://h21007.www2.hp.com/dspp/tech/tech_TechDocumentDetailPage_IDX/1,1701,990,00.html"--
here it is mentioned that "Koenig Lookup"(ADL) applies to unqualified funtions.

As in , on the failure of "Ordinary Name Lookup"(OL) to find a better foo()--- ADL, finds a better foo() by rolling up in the class/namespace ladder. ADL in effect is acting as a more intelligent algorithm than OL.

Continuing on your example

Case 1:
================
namespace A{
class S{};
//Line edited
}
namespace B{
void foo(A::S& parm) { }
void bar(A::S& parm) {
foo(parm); //B's version of foo called as its the only one (No ambiguity)
}
}

Both namespaces are in perfect sync with each other. As you can rightly sense at this instanst the above code is vulnerable.

If in course of time(as any OOL must handle such future changes) -- namespace A had modifications as follows

Case 2:
==================
namespace A{
class S{};
void foo(S& parm) { }
}

namespace B{
void foo(A::S& parm) { }
void bar(A::S& parm) {
foo(parm); //Ambiguity arises even though B's code is untouched
}
}


One intutive solution is to make B parsed by the OL itself ,by something like B::foo(parm).
Ideally B's code should be untouched, as changes should be localized( here only to A).

ADL tremendously eases life (cout example very apt).

My question is "Does ADL in the process of making the coder's life simple , work against the very concept of OO?"

Srinivas said...

No, it does not go against OO. Look up "the interface principle" in google to know more. The question in OO is, "What forms the interface to a class?" - turns out that its not just the public member functions, but also the functions in the same namespace. This has to be so, because there's the concept of "friends". "friends" are not a part of the class per se - but they do form a part of the class's interface.

And whether ADL makes life easy or difficult:
1) If one is the only maintainer and he's adept about the effects of ADL, he'll design the classes well and will be in no trouble.

2) If one is maintaining somebody else's code, and that guy has done a poor design of classes, then better be prepared for sleepless nights!

Shantanu said...

"http://www.gotw.ca/publications/mill08.htm"

Conclusion is worth a look.

Extracts:
=========================
"Use namespaces wisely. Either put all of a class inside the same namespace -- including things that to innocent eyes don't look like they're part of the class, such as free functions that mention the class -- or don't put the class in a namespace at all. Your users will thank you."