A C++ name lookup mystery

Alternate title: yet another reason to loathe C++.

The offending code

// foo.hpp

namespace root::foo {
    struct Foo {};
    namespace operators {
        bool operator==(const Foo&, const Foo&);
    } // namespace operators
} // namespace root::foo

// bar.hpp

namespace root::bar {
    struct Waiter {};
    bool operator==(const Waiter&, const Waiter&);
    struct Waitress {};
    bool operator==(const Waitress&, const Waitress&);
} // namespace root::bar

// baz.cpp

using namespace ::root::foo;
using namespace ::root::foo::operators;

namespace root::bar {
    bool f(const Foo& l, const Foo& r) {
        return l == r;
    }
} // namespace root::bar

The error

<source>:26:18: error: no match for 'operator==' (operand types are 'const root::foo::Foo' and 'const root::foo::Foo')
   26 |         return l == r;
      |                ~ ^~ ~
      |                |    |
      |                |    const root::foo::Foo
      |                const root::foo::Foo
<source>:14:10: note: candidate: 'bool root::bar::operator==(const root::bar::Waiter&, const root::bar::Waiter&)'
   14 |     bool operator==(const Waiter&, const Waiter&);
      |          ^~~~~~~~
<source>:14:21: note:   no known conversion for argument 1 from 'const root::foo::Foo' to 'const root::bar::Waiter&'
   14 |     bool operator==(const Waiter&, const Waiter&);
      |                     ^~~~~~~~~~~~~
<source>:16:10: note: candidate: 'bool root::bar::operator==(const root::bar::Waitress&, const root::bar::Waitress&)'
   16 |     bool operator==(const Waitress&, const Waitress&);
      |          ^~~~~~~~
<source>:16:21: note:   no known conversion for argument 1 from 'const root::foo::Foo' to 'const root::bar::Waitress&'
   16 |     bool operator==(const Waitress&, const Waitress&);
      |                     ^~~~~~~~~~~~~~~
ASM generation compiler returned: 1
<source>: In function 'bool root::bar::f(const root::foo::Foo&, const root::foo::Foo&)':
<source>:26:18: error: no match for 'operator==' (operand types are 'const root::foo::Foo' and 'const root::foo::Foo')
   26 |         return l == r;
      |                ~ ^~ ~
      |                |    |
      |                |    const root::foo::Foo
      |                const root::foo::Foo
<source>:14:10: note: candidate: 'bool root::bar::operator==(const root::bar::Waiter&, const root::bar::Waiter&)'
   14 |     bool operator==(const Waiter&, const Waiter&);
      |          ^~~~~~~~
<source>:14:21: note:   no known conversion for argument 1 from 'const root::foo::Foo' to 'const root::bar::Waiter&'
   14 |     bool operator==(const Waiter&, const Waiter&);
      |                     ^~~~~~~~~~~~~
<source>:16:10: note: candidate: 'bool root::bar::operator==(const root::bar::Waitress&, const root::bar::Waitress&)'
   16 |     bool operator==(const Waitress&, const Waitress&);
      |          ^~~~~~~~
<source>:16:21: note:   no known conversion for argument 1 from 'const root::foo::Foo' to 'const root::bar::Waitress&'
   16 |     bool operator==(const Waitress&, const Waitress&);
      |                     ^~~~~~~~~~~~~~~

Name lookup vs overload resolution

To map a function call to the function declaration the compiler performs two sequential steps:

Name lookup
- Produces a set of candidate functions.
- Takes into account names only, not parameters.
- Two conceptually parallel lookups:
  - Lexical lookup (aka "ordinary lookup" in standard)
  - Argument Dependent Lookup (aka ADL aka Koenig's lookup)
Overload resolution
- Reduces the set of candidate to a single function (success)
- Or errors out:
  - No viable candidate => not found
  - Several candidates that fit equally well => ambiguity

Analysis

Name lookup produces following set:
- operator==(const Waiter&, const Waiter&)
- operator==(const Waitress&, const Waitress&).
Overload resolution fails because parameters of candidate functiona do not match call arguments.

Lexical lookup

The rules:

Goes from innermost scope to outermost one:
- Function scopes
- If member function:
  - Class
  - Enclosing classes
  - Base classes
- Namespaces
- Global namespace
Stops on first name match

In our case:

f() => no match
root::bar => match

An unsuccessful lexical lookup fix

// baz.cpp

namespace root::bar {
    using namespace ::root::foo;
    bool f(const Foo& l, const Foo& r) {
        using namespace ::root::foo::operators;
        return l == r;
    }
} // namespace root::bar

Same error :-(

Fallacy (but common sense):

using namespace ::root::foo does not inject names from ::root::foo into current scope.
Instead it injects them in the common ancestor of ::root::foo and the current scope, i.e. ::root :-(.

So this injects operator==(const Foo&, const Foo&) in ::root and ::root::bar::operator==() overloads still win the lexical lookup race.

An successful lexical lookup fix

A using declaration brings a specific overload set into the current scope (rather than the common ancestor):

// baz.cpp

namespace root::bar {
    using namespace ::root::foo;
    bool f(const Foo& l, const Foo& r) {
        using ::root::foo::operators::operator==;
        return l == r;
    }
} // namespace root::bar

This is not required here but we could bring the other overload too and to let overload resolution choose the best match:

// baz.cpp

namespace root::bar {
    using namespace ::root::foo;
    bool f(const Foo& l, const Foo& r) {
        using ::root::foo::operators::operator==;
        using ::root::bar::operator==;
        return l == r;
    }
} // namespace root::bar

What about ADL?

ADL looks for function declarations in the namespaces of the arguments of the function calls (and associated namespaces).

Here the arguments are const ::root::foo::Foo& so it looks in ::root::foo but the operator is defined in a different namespace and so ADL comes back empty handed.

Lessons

Follow C++ code guideline C.5 which recommends to keep types and associated non-member functions in the same namespace.
- (Or even better use the hidden friend idiom.)
Be wary of using directives (using namespace).
Be wary of deeply nested namespaces.

nthery/name_lookup_mystery.md