Mechanizm wyszukiwania nazw w C++: ADL i dwufazowa analiza szablonów

Jak kompilator C++ rozplątuje plątaninę nazw: ADL, szablony i dwufazowe wyszukiwanie

Wyszukiwanie nazw (name lookup) — jeden z najbardziej skomplikowanych etapów kompilacji C++. Z powodu historycznego rozwoju języka reguły wyszukiwania stały się zagmatwane, co prowadzi do nieoczekiwanych błędów nawet u doświadczonych programistów. Rozbieramy, jak działa mechanizm wyszukiwania i dlaczego różne kompilatory zachowują się różnie.

Podstawowe terminy: jak kompilator klasyfikuje nazwy

Kompilator operuje ścisłą terminologią do analizy nazw w kodzie. Zrozumienie tych terminów — klucz do rozwikłania „magii” wyszukiwania.

Niekwalifikowany identyfikator (unqualified-id) — podstawowa forma nazwy, na przykład speed, foo lub my_var. Obejmuje również operatory, destruktory i niestandardowe literały. Przykłady:

// Niekwalifikowane nazwy
vector<int> v;       // 'vector' — niekwalifikowana nazwa
sort(v.begin(), v.end()); // 'sort' — niekwalifikowana nazwa

Kwalifikowana nazwa (qualified-id) — nazwa z operatorem rozdzielności zasięgu ::, na przykład std::vector lub Foo::bar. Tutaj Foo jest kwalifikatorem, a bar — nazwą terminalną.

// Kwalifikowane nazwy
std::vector<int> v;  // 'vector' — kwalifikowana nazwa
Foo::bar();          // 'bar' — terminalna kwalifikowana nazwa

Template-id — nazwa szablonu z jawnymi argumentami, na przykład std::vector<int>.

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

Nazwa terminalna — ostatnia nazwa w łańcuchu, której kompilator szuka. Na przykład w obj->f() nazwa terminalna to f, w ns::Foo::bar() — bar. Jest to kluczowe w szablonach:

template<typename T>
void wrapper(T& obj) {
    obj.size();      // 'size' — nazwa terminalna
    T::value_type x; // 'value_type' — terminalna kwalifikowana nazwa
}

ADL: kiedy argumenty decydują o wszystkim

Argumentozależne wyszukiwanie (ADL, Argument-Dependent Lookup) — mechanizm automatycznie rozszerzający zasięg wyszukiwania funkcji na podstawie typów argumentów. Bez ADL używanie przeciążonych operatorów dla typów użytkownika byłoby niewygodne.

Rozważmy przykład:

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 znajduje operator<< w sak
}

Kompilator widzi, że n ma typ sak::BigNum, i dodaje przestrzeń nazw sak do zasięgu wyszukiwania dla operator<<. Bez ADL trzeba by pisać sak::operator<<(std::cout, n).

ADL zaproponował Andrew Koenig w 1995 roku (dokument N0645), choć pomysł istniał w praktyce AT&T Bell Labs. Standard utrwalił go jako [basic.lookup.koenig]. Jednak ADL ma pułapki: zależność od niego może prowadzić do konfliktów, jeśli dwie biblioteki definiują funkcje o tych samych nazwach w różnych przestrzeniach.

Algorytm ADL:

• Wykonywane jest zwykłe niekwalifikowane wyszukiwanie.
• Dla wywołań funkcji uruchamiane jest ADL: do wyszukiwania dodawane są przestrzenie nazw typów argumentów.
• Jeśli nazwa jest kwalifikowana (np. std::sort), ADL nie jest stosowane.

Dwufazowe wyszukiwanie w szablonach: dlaczego GCC i Clang się różnią

W szablonach wyszukiwanie nazw jest podzielone na dwie fazy:

• Pierwsza faza (definicja szablonu): wyszukiwane są nazwy niezależne (niezależne od parametrów szablonu).
• Druga faza (instancjonizacja): wyszukiwane są nazwy zależne (zależne od parametrów szablonu), tutaj włącza się ADL.

Historycznie kompilatory różnie interpretowały te reguły. GCC do wersji 7 używał „leniwego parsowania”: ciało szablonu nie było analizowane przy definicji, a wszystkie nazwy wyszukiwano przy instancjonizacji. Prowadziło to do niezgodności ze standardem.

Przykład rozbieżności:

void foo(int) {}  // globalna foo

template<typename T>
void bar(T x) {
    foo(x);   // zależna nazwa — wyszukiwana w fazie 2 (ADL), poprawnie
    foo(42);  // NIEzależna nazwa — powinna być wyszukiwana w fazie 1
}

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

bar(myns::MyType{}); // GCC: kompiluje się, Clang: błąd

W Clang foo(42) jest wyszukiwane w fazie 1 i nie znajduje odpowiedniej przeciążenia (globalna foo(int) nie pasuje do MyType), dlatego występuje błąd. GCC odkłada wyszukiwanie do instancjonizacji i znajduje foo(int).

Komitet standardu zabronił wyszukiwania w zależnych klasach bazowych w pierwszej fazie. Rozważmy przykład:

template<typename T>
struct Base {};

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

template<typename T>
struct Derived : Base<T> {
    void run() {
        process(); // Błąd: wyszukiwanie w zależnej bazie zabronione w fazie 1
    }
};

Jeśli pozwolić na wyszukiwanie w Base<T> w pierwszej fazie, kod skompiluje się dla T=int, ale nie dla T=float. Narusza to przewidywalność szablonów.

Co ważne: kluczowe wnioski

Podczas pracy z wyszukiwaniem nazw w C++ zapamiętaj:

• Nazwa terminalna — punkt skupienia wyszukiwania kompilatora. Określ ją, by zrozumieć, gdzie szukać.
• ADL rozszerza wyszukiwanie na przestrzenie nazw argumentów. Przydatne dla operatorów, ale może powodować konflikty.
• W szablonach nazwy niezależne wyszukiwane są przy definicji, zależne — przy instancjonizacji. Używaj typename dla zależnych typów.
• Różne kompilatory mogą inaczej obsługiwać kontrowersyjne przypadki. Testuj kod w GCC, Clang i MSVC.
• Dla zależnych klas bazowych jawnie podawaj nazwy przez this-> lub kwalifikację.

— Editorial Team