C++ Name Lookup Mechanism: ADL and Two-Phase Template Lookup

How the C++ Compiler Untangles the Tangle of Names: ADL, Templates, and Two-Phase Lookup

Name lookup is one of the most complex stages of C++ compilation. Due to the language's historical evolution, the lookup rules have become convoluted, leading to unexpected errors even for experienced developers. Let's break down how the lookup mechanism works and why different compilers behave differently.

Key Terms: How the Compiler Classifies Names

The compiler uses precise terminology to analyze names in code. Understanding these terms is key to unraveling the "magic" of lookup.

Unqualified identifier (unqualified-id) — the basic form of a name, for example speed, foo, or my_var. This also includes operators, destructors, and user-defined literals. Examples:

// Nekvalifitsirovannye names
vector<int> v;       // 'vector' — unqualified name
sort(v.begin(), v.end()); // 'sort' — unqualified name

Qualified name (qualified-id) — a name with the scope resolution operator ::, for example std::vector or Foo::bar. Here Foo acts as the qualifier, and bar as the terminal name.

// Kvalifitsirovannye names
std::vector<int> v;  // 'vector' — qualified name
Foo::bar();          // 'bar' — terminal qualified name

Template-id — a template name with explicit arguments, for example std::vector<int>.

// Template-id
std::vector<int> v1;         // 'vector<int>' — template-id
std::pair<int, float> p;     // 'pair<int, float>' — template-id

Terminal name — the final name in the chain that the compiler searches for. For example, in obj->f() the terminal name is f, in ns::Foo::bar() it's bar. This is critically important in templates:

template<typename T>
void wrapper(T& obj) {
    obj.size();      // 'size' — terminal name
    T::value_type x; // 'value_type' — terminal qualified name
}

ADL: When Arguments Call the Shots

Argument-Dependent Lookup (ADL) is a mechanism that automatically extends the search scope for functions based on argument types. Without ADL, using overloaded operators for user-defined types would be cumbersome.

Consider this example:

namespace sak {
    struct BigNum { int value; };
    std::ostream& operator<<(std::ostream& os, const BigNum& n) {
        return os << "BigNum(" << n.value << ")";
    }
}

int main() {
    sak::BigNum n(42);
    std::cout << n; // ADL nakhodit operator<< in sak
}

The compiler sees that n has type sak::BigNum and adds the sak namespace to the search scope for operator<<. Without ADL, you'd have to write sak::operator<<(std::cout, n).

ADL was proposed by Andrew Koenig in 1995 (document N0645), though the idea had been in use at AT&T Bell Labs. The standard codified it in [basic.lookup.koenig]. However, ADL has pitfalls: over-reliance on it can cause conflicts if two libraries define functions with the same names in different namespaces.

ADL algorithm:

• Ordinary unqualified lookup is performed.
• For function calls, ADL kicks in: namespaces from argument types are added to the search.
• If the name is qualified (e.g., std::sort), ADL is not applied.

Two-Phase Lookup in Templates: Why GCC and Clang Disagree

In templates, name lookup is split into two phases:

• Phase 1 (template definition): Searches for non-dependent names (independent of template parameters).
• Phase 2 (instantiation): Searches for dependent names (dependent on template parameters), where ADL applies.

Historically, compilers interpreted these rules differently. GCC prior to version 7 used "lazy parsing": the template body wasn't analyzed at definition time, and all names were looked up during instantiation. This led to standard non-conformance.

Example of divergence:

void foo(int) {}  // globalnaya foo

template<typename T>
void bar(T x) {
    foo(x);   // zavisimoe name — ischetsya in phase 2 (ADL), vsyo correct
    foo(42);  // NEzavisimoe name — must iskatsya in phase 1
}

namespace myns {
    struct MyType {};
    void foo(MyType) {}
}

bar(myns::MyType{}); // GCC: kompiliruetsya, Clang: oshibka

In Clang, foo(42) is looked up in phase 1 and finds no suitable overload (the global foo(int) doesn't match for MyType), causing an error. GCC delays lookup until instantiation and finds foo(int).

The standards committee banned lookup in dependent base classes during phase 1. Consider this example:

template<typename T>
struct Base {};

template<>
struct Base<int> {
    void process() {}
};

template<typename T>
struct Derived : Base<T> {
    void run() {
        process(); // Error: poszukiwanie in zavisimoy baze zapreschyon in phase 1
    }
};

If lookup in Base<T> were allowed in phase 1, the code would compile for T=int but not for T=float. This would break template predictability.

What Matters: Key Takeaways

When working with name lookup in C++, keep these in mind:

• The terminal name is the compiler's focus. Identify it to know where to look.
• ADL extends lookup to argument namespaces. Great for operators, but can cause conflicts.
• In templates, non-dependent names are looked up at definition, dependent ones at instantiation. Use typename for dependent types.
• Different compilers may handle edge cases differently. Test in GCC, Clang, and MSVC.
• For dependent base classes, explicitly qualify names with this-> or scopes.

— Editorial Team