标识符(identifier)
名字查找(name lookup)
注入类名(injected-class-name)
实参依赖查找(ADL: argument dependent lookup)
为什么需要ADL
ADL的大致步骤
ADL与hidden friend

参考
C++ Templates: The Complete Guide
What is ADL? - Arthur O’Dwyer
P1601r0

标识符分类

标准中关于标识符(identifier)的分类：

identifier
标识符是一个由数字，下划线，大小写拉丁字母和大多数 Unicode 字符组成的任意长度的序列。标识符不能以数字开头。
- 关键词标识符不可用于其他目的，但可以用于attribute：[[private]]
- 作为特定运算符与标点符的代用表示不能用于其他目的：xor
- 一些标识符是被保留的：
  - 任何位置带有双下划线的标识符：__builtin_popcount
  - 以一个下划线跟着一个大写字母开头的标识符：_M_storage
  - 全局命名空间中以一个下划线开头

Each identifier that contains a double underscore __ or begins with an underscore followed by an uppercase letter is reserved to the implementation for any use.
Each identifier that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

libstdc++的实现中存在存在大量的带双下划线的uglified names。例如__stable_sort。libstdc++的实现中，成员变量一般都被写成_M_xxxx。编译器的实现也存在这样的双下划线开头的标识符，例如namespace __gnu_cxx。保留这些标识符，避免和库，编译器产生冲突。

而全局命名空间中以一个下划线开头可能会导致该函数的名称和另一个函数的mangled name重复，链接器会报错

下面的例子定义了一个和全局对象std::cout的mangled name重名的函数，导致SIGSEGV(errno: 139)

operator-function-id
关键词opreator后跟随运算符的符号，例如operator new，operator []
conversion-function-id
用于进行隐式类型转换的运算符。例如operator int&。
literal-operator-id
用于用户自定义字面量，例如operator ""_km用于100_km
template-id
模板名后随包含模板实参的角括号，例如tuple<int, int, double>。一个template-id可能是一个operator-function-id或conversion-function-id，例如operator+<pair<int, int>>。
unqualified-id
包括以上的任何一种：operator-function-id、conversion-function-id、literal-operator-id、template-id和以~开头的析构函数名称，例如~X
qualified-id
一个被作用域解析操作符::限定的标识符。例如std::swap、::hton、::std::partition

为叙述方便，我们定义：

qualified-name
- 进行有限定的名字查找的标识符：
  - qualified-id，例如S::x
  - 显式成员访问运算符后的unqualified-id和qualified-id，例如this->f、p->A::m。struct x{ int y; int f(){return y;}};函数x::f()中的y不算是qualified-name，因为要求成员访问运算符必须为显式。
unqualified-name
进行无限定的名字查找的标识符，即一个不是qualified-name的unqualified-id。

名字查找

如果名字紧跟在作用域解析运算符 ::，或可能跟在 :: 之后的消歧义关键词 template 的右侧，进行有限定的名字查找，否则进行无限定的名字查找。

有限定的名字查找根据::左边的名字进行查找：
- 如果::左边的名字是命名空间，或左边为空，那么:: 右边的名字就在这个命名空间的作用域中进行查找
- 如果::左边的名字是某个类（或struct, union），则::右边的名字在该类、结构体或联合体的作用域中进行查找（因此可能找到该类或其基类的成员的声明）。注意，此时不搜索包含该类的命名空间。

int x;

class B
{
public:
	int i;
};

class D : public B{};

void f(D* pd)
{
	pd->i = 3; // i的查找结果为B::i
	D::x = 2;  // 错误：在D和B中未找到x。x位于全局命名空间。
}

关于有限定的名字查找的其他细节，参照cppreference - 有限定的名字查找

无限定的名字查找
- 先查找当前的作用域，再查找外层作用域，以此类推。
- 在成员函数定义的作用域内，先查找该类，之后查找该类的父类，之后再查找外层命名空间。

extern int count;             // #1

int lookup_example(int count) // #2
{
	if(count < 0)
	{
		int count = 1;        // #3
		lookup_example(count);// 查找结果为#3
	}
	return count + ::count;   // 第一个无限定的名字查找结果为#2
                                  // 第二个有限定的名字查找结果为#1
}

关于无限定的名字查找的其他细节，参照cppreference - 无限定的名字查找

注入类名(injected-class-name)

一个类的名字会以unqualified-name的形式，被注入到该类的作用域内。与其他成员类似，注入类名可被继承。

因此我们在类（类模板）的作用域内可以通过unqualified-name的形式来指代该类。然而，qualified-name的形式则不可以用来指代该类，因为这种形式被用来指代构造函数。

#include <cstdint>
#include <cstddef>
#include <type_traits>

int32_t C;

class C
{
private:
	int64_t i;
public:

	static size_t f()
	{
		static_assert(sizeof(C) == sizeof(int64_t));
        return sizeof(C); // C is injeceted as an `unqualified-name`
		                  // into the class scope
	}

    static void g()
    {
    	auto p = &::C;    // '::C' refers to the global variable if it
                          // is qualified with '::'
        static_assert(std::is_same_v<decltype(p), int32_t*>);
    }

    static void k()
    {
        // auto p = &C::C;
        // error: taking address of constructor 'constexpr C::C(C&&)'
    }
};

auto f() -> size_t
{
	static_assert(sizeof(C) == sizeof(int32_t));
    return sizeof(C);     // f in not in the C class scope, thus 'C'  
	                      // refers to the global variable 'int32_t C'
}

在上面的程序中，在C的类作用域中，unqualified-nameC被注入其中。

函数C::f()返回的是类C的大小。
函数c::g()中，使用被限定的标识符::C则只能进行有限定的名字查找，对应全局变量::C。
函数C::k()中，编译错误说明表达式&C::C是取C的构造函数的地址，那么C::C表示的是C的构造函数。
函数::f()中，C进行不限定的名字查找，找到全局变量::C。

struct A {};
struct B : private A {};
struct C : public B {
    A* p; // 错误：注入类名 A 不可访问
    ::A* q; // OK：不使用注入类名
};

与其他成员类似，注入类名可被继承。在私有或受保护继承的场合，可能导致某个间接基类的注入类名在派生类中最后变得不可访问。

与其他类相似，类模板也拥有注入类名。其注入类名可被用作模板名或类型名。

下列情况下，在作用域中，注入类名被当做类模板自身的模板名：

它后面跟着 <
它被用作对应某个模板模板形参的模板实参
它是某个友元类模板声明的详述类型说明符中的最后标识符。
否则，它被当做类型名，并等价于模板名后随环绕于 <> 中的该类模板的各个模板形参。

#include <type_traits>

template <template <typename, typename> typename> 
struct A{};
 
template<class T1, class T2>
struct X {

    X *p1;         // #1
    X<T1, T2>* p2; // #2

    static_assert(std::is_same_v<X, X<T1, T2> >);

    using a = A<X>; // #3

    template<class U1, class U2>
    friend class X; // #4

};

类模板A的模板参数为接受两个类为模板参数的模板模板参数。

X被当作类型名，等价于X<T1, T2>
X后面跟随<，X被当作模板名，可以接受两个类做模板参数。
X被用作类模板A的模板模板形参的实参，X此时被当作模板名。
X是某个友元类模板声明的详述类型说明符中的最后标识符，X此时被当作模板名。

template<typename>
struct crtp_base{};

template<typename T>
// struct crtp_derived : public crtp_base<crtp_derived> // #1
struct crtp_derived : public crtp_base<crtp_derived<T>> // #2
{};

在CRTP实践中，描述继承的语句不在类的作用域内，因此我们需要在继承CRTP模板时，将本类的名字写全。如#2所示。#1不能通过编译。

关于注入类名更详细的介绍，参考cppreference - 注入类名

为什么需要ADL

假设名字查找只有有限定的名字查找和无限定的名字查找，考虑下面的例子：

template<typename T>
T max(T a, T b)
{
	return b < a ? a : b;
}

namespace BigMath
{
	class BigNumber
	{
		// ...
	};

	bool opreator < (const BigNumber&, const BigNumber&);

	// ...
}

using BigMath::BigNumber;

void g(const BigNumber& a, const BigNumber& b)
{
	// ...
	auto x = ::max(a, b); // cannot find BigNumber::operator< without ADL
	// ...
}

函数模板template<typename T> T max(T a, T b)并不知道namespace BigMath的存在，如果仅进行无限定的名字查找，并不能在其函数作用域或者外部的全局命名空间找到bool opreator < (const BigNumber&, const BigNumber&)。ADL则被用来解决这种状况。

ADL如何进行？

ADL主要适用于对unqualified-name的函数进行的名字查找。查找对象是一个在进行函数调用或者运算符调用的非成员函数。
首先，若通常的无限定名字查找所生成的集合含有下列任何内容，则不考虑ADL:

类成员的声明
块作用域的（并非 using 声明的）函数声明
任何非函数或函数模板之声明（例如函数对象或另一变量，其名字与正在查找的函数名冲突）

否则，对于每个函数调用表达式中的实参，检验其类型，以确定它将向查找所添加的命名空间与类的关联集：

对于基础类型的实参，命名空间与类的关联集为空集
对于 T 的指针或指向 T 的数组的指针类型的实参，检验类型 T 并向集合中添加其类与命名空间的关联集合。
对于任何枚举类型的实参，向集合中添加于其中定义了该枚举的命名空间。若该枚举类型是类成员，则向集合中添加该类。
对于类类型（含联合体）的实参，集合由以下组成
- 该类自身
- 其所有直接与间接基类
- 若该类是另一类的成员，则为该外围类
- 添加到集合的各个类的最内层外围命名空间
若实参是一组重载函数（或函数模板）的名字或取址表达式，则检验重载集合中的每个函数，并向集合添加其类与命名空间的关联集合。另外，若以模板标识（带模板实参的模板名），比如A<B>指名重载集，则检验其所有类型模板实参与模板模板实参（但不包括非类型模板实参），并向集合添加其类与命名空间的关联集合。
对于指向类 X 的数据成员 T 的指针类型的实参，检验该成员类型和类型 X，并向集合添加它们的类与命名空间的关联集合。

在确定命名空间与类的关联集合后，忽略此集中所有于类中找到的声明，但不包括命名空间作用域的友元函数及函数模板。之后，ADL根据下列特殊规则，将通过常规无限定查找所找到的声明的集合，与通过 ADL 所生成的关联集合的所有元素中找到的声明集合进行合并：

忽略关联命名空间中的 using 指令
声明于关联类中的命名空间作用域的友元函数（及函数模板）通过 ADL 可见，即使它们通过普通查找不可见。
忽略除函数与函数模板外的所有名字（不会与变量之间发生冲突）

例子一：

namespace X
{
	template<typename T> void f(T);
}

namespace N
{
	using namespace X; //ADL will ignore this
	enum E {e1,};
	void f(E)
	{
		std::cout<<"N::f(N::E) called\n";
	}
}

void f(int)
{
	std::cout<<"::f(int) called\n";
}

int main()
{
	::f(N::e1); // 有限定的名字查找，不进行ADL
	f(N::e1);   // 无限定的名字查找，找到 `::f(int)`
	            // 之后进行ADL，实参为枚举类型，向集合中添加声明该枚举的命名空间
	            // 之后根据规则合并时，忽略`using namespace X`指令
	            // 然后在 `namespace N` 中进行无限定查找
	            // 名字查找最终找到 `::f(int)` 和 `N::f(E)`
	            // 重载决议选择了后者`N::f(E)`
}

例子二：

namespace A {
    struct A {};
}
namespace B {
    using T = A::A;
}
namespace C {
    B::T c;
}
namespace C {
    void test() {
        f(C::c);  // HERE
    }
}

在// HERE的位置，我们以A::A类型的参数调用了函数f()。即便对C::c进行有限定名字查找的过程中涉及到了namespace C、namespace B、namespace A和struct A。但这些都和ADL无关。ADL只关心“用A::A类型调用了一个未限定的函数名f

例子三：

namespace A {
    struct A { operator int(); };
    void f(A);
    void g(A);
    void h(A);
    int i(A);
    int j(A);
}
namespace B {
    void f(int);
    auto h = [](int) {};
    using i = int;
    void test() {
        A::A a;
        f(a);           // #1
        g(a);           // #2
        h(a);           // #3
        int ia = i(a);  // #4
        int j = j(a);   // #5
    }
}

无限定名字查找 在函数作用域未找到f。在namespace B中找到void f(int)。在全局命名空间未找到f。满足进行ADL的三个条件，因此将类A::A和类所在的命名空间A加入集合。A::A中无友元函数。A中存在一个函数void f(A::A)。重载决议选择void f(A::A)
无限定名字查找在函数作用域未找到g。在namespace B中未找到g。在全局命名空间未找到g。满足ADL的三个条件，因此将类A::A和类所在的命名空间A加入集合。A::A中无友元函数。A中存在一个函数void g(A::A)。重载决议选择void g(A::A)
无限定名字查找在namespace B找到lambda声明h。不进行ADL
无限定名字查找在namespace B找到alias声明i。不进行ADL
错误：无限定名字查找在函数作用域找到变量声明int j。

ADL与友元函数

注意到ADL维护了两个实参的关联集。一个是命名空间，另一个是类。注意到：

在确定命名空间与类的关联集合后，忽略此集中所有于类中找到的声明，但不包括命名空间作用域的友元函数及函数模板。

因此类的集合主要用来处理：

声明于关联类中的命名空间作用域的友元函数（及函数模板）通过 ADL 可见，即使它们通过普通查找不可见。

P1601r0中提到：

When first declared via a friend declaration, the befriended entity’s name (if unqualified) is injected into the nearest enclosing namespace. This is reasonable, as the named entity is not a member of the class granting friendship and so must become a member of some namespace.
However, such name injection does not implicitly make that name visible to qualified or unqualified lookup; only argument-dependent lookup can find such an otherwise hidden name.

因为友元关系意味着该名字不会是该类的一个成员，该友元必然需要处于某一个命名空间中。所以当我们第一次在类中声明一个unqualified name为friend时，其名字会被注入最临近的命名空间中。但是这种名字注入并不能使得无限定的名字查找和有限定的名字查找找到该名字。只有通过ADL才可以找到。

Xuanyi Fu Blog

标识符、名字查找与实参依赖查找(ADL)