Mechanismus vyhledávání jmen v C++: ADL a dvoufázové parsování šablon

Jak kompilátor C++ rozplétá spleť jmen: ADL, šablony a dvoufázové hledání

Hledání jmen (name lookup) je jednou z nejsložitějších fází kompilace C++. Kvůli historickému vývoji jazyka se pravidla hledání stala zamotanými, což vede k neočekávaným chybám i u zkušených vývojářů. Prozkoumáme, jak je mechanismus hledání strukturován a proč se různí kompilátoři chovají odlišně.

Základní pojmy: jak kompilátor klasifikuje jména

Kompilátor pracuje se striktní terminologií pro analýzu jmen v kódu. Porozumění těmto pojmům je klíčem k odhalení „mágie“ hledání.

Nekvalifikovaný identifikátor (unqualified-id) — základní forma jména, například speed, foo nebo my_var. Zahrnuje také operátory, destruktory a uživatelské literály. Příklady:

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

Kvalifikované jméno (qualified-id) — jméno s operátorem rozlišení oboru viditelnosti ::, například std::vector nebo Foo::bar. Zde Foo funguje jako kvalifikátor a bar jako terminální jméno.

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

Template-id — jméno šablony s explicitními argumenty, například std::vector<int>.

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

Terminální jméno — poslední jméno v řetězci, které kompilátor hledá. Například v obj->f() je terminální jméno f, v ns::Foo::bar() — bar. To je klíčové v šablonách:

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

ADL: kdy argumenty rozhodují o všem

Argumentově závislé hledání (ADL, Argument-Dependent Lookup) je mechanismus, který automaticky rozšiřuje obor hledání funkcí na základě typů argumentů. Bez ADL by použití přetížených operátorů pro uživatelské typy bylo nepohodlné.

Podívejme se na příklad:

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
}

Kompilátor vidí, že n má typ sak::BigNum, a přidává prostor jmen sak do oboru hledání pro operator<<. Bez ADL by bylo třeba psát sak::operator<<(std::cout, n).

ADL navrhl Andrew Koenig v roce 1995 (dokument N0645), ačkoli myšlenka existovala v praxi AT&T Bell Labs. Standard ji ustanovil jako [basic.lookup.koenig]. ADL však má úskalí: závislost na něm může vést ke konfliktům, pokud dvě knihovny definují funkce se stejnými jmény v různých prostorech.

Algoritmus ADL:

• Provádí se standardní nekvalifikované hledání.
• Pro volání funkcí se spustí ADL: do hledání se přidají prostory jmen typů argumentů.
• Pokud je jméno kvalifikované (např. std::sort), ADL se neuplatňuje.

Dvoufázové hledání v šablonách: proč se GCC a Clang hádají

V šablonách je hledání jmen rozděleno do dvou fází:

• První fáze (definice šablony): hledají se nezávislá jména (nezávislá na parametrech šablony).
• Druhá fáze (instanciace): hledají se závislá jména (závislá na parametrech šablony), zde se zapojí ADL.

Historicky kompilátoři různě interpretovali tato pravidla. GCC do verze 7 používal „lenivé parsování“: tělo šablony se neanalyzovalo při definici a všechna jména se hledala až při instanciaci. To vedlo k nesouladům se standardem.

Příklad rozporu:

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

V Clang se foo(42) hledá v první fázi a nenajde vhodnou přetížení (globální foo(int) nevyhovuje pro MyType), proto vznikne chyba. GCC naopak odkládá hledání na instanciaci a najde foo(int).

Výbor standardu zakázal hledání v závislých základních třídách v první fázi. Podívejme se na příklad:

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
    }
};

Pokud by bylo hledání v Base<T> v první fázi povoleno, pak pro T=int by se kód zkompiloval, ale pro T=float ne. To by porušilo předvídatelnost šablon.

Co je důležité: klíčové závěry

Při práci s hledáním jmen v C++ si zapamatujte:

• Terminální jméno je ohniskem hledání kompilátoru. Určete ho, abyste pochopili, kde hledat.
• ADL rozšiřuje hledání na prostory jmen argumentů. Je užitečné pro operátory, ale může způsobit konflikty.
• V šablonách se nezávislá jména hledají při definici, závislá při instanciaci. Používejte typename pro závislé typy.
• Různí kompilátoři mohou zpracovávat sporné případy odlišně. Testujte kód v GCC, Clang a MSVC.
• Pro závislé základní třídy explicitně uveďte jména pomocí this-> nebo kvalifikace.

— Editorial Team