ADL

ADL是compiler的一种行为，可以将compiler的name lookup分为两种：

1、ADL

2、ordinary lookup

ADL在C++中的广泛应用

今天阅读cppreference Argument-dependent lookup方知，我们的std::cout << "Test\n";竟然蕴藏着如此之多的玄机：

1、std::cout是一个object，它没有成员函数operator<<

2、在<iostram>中，定义了std::operator<<(std::ostream&, const char*)

3、当我们编写std::cout << "Test\n";的时候，compiler会使用ADL来进行查找：

There is no operator<< in global namespace, but ADL examines std namespace because the left argument is in std and finds std::operator<<(std::ostream&, const char*)

这让我想到了之前在阅读代码的时候，有很多类似的写法：

spdlog:logger-inc.h

SPDLOG_INLINE void swap(logger &a, logger &b)
{
    a.swap(b);
}

std::swap和类成员函数swap

using std::swap;
swap(a, b);

std::begin 和 类成员函数begin：

下面的initializer_list就是一个例子：

// initializer_list standard header (core)

// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

// CLASS TEMPLATE initializer_list
template <class _Elem>
class initializer_list {
public:

    _NODISCARD constexpr const _Elem* begin() const noexcept {
        return _First;
    }

    _NODISCARD constexpr const _Elem* end() const noexcept {
        return _Last;
    }


};

// FUNCTION TEMPLATE begin
template <class _Elem>
_NODISCARD constexpr const _Elem* begin(initializer_list<_Elem> _Ilist) noexcept {
    return _Ilist.begin();
}

// FUNCTION TEMPLATE end
template <class _Elem>
_NODISCARD constexpr const _Elem* end(initializer_list<_Elem> _Ilist) noexcept {
    return _Ilist.end();
}

ADL的重要意义

在C++\Language-reference\Classes\The-interface-principle中对ADL and the Interface Principle进行了分析。

ADL make C++ generic and extensible

从Interface Principle的角度来看，C++ ADL是为了更好、更灵活地支持OOP、generic programming。

扩展性

wikipedia Argument-dependent name lookup#Interfaces：

Functions found by ADL are considered part of a class's interface. In the C++ Standard Library, several algorithms use unqualified calls to swap from within the std namespace. As a result, the generic std::swap function is used if nothing else is found, but if these algorithms are used with a third-party class, Foo, found in another namespace that also contains swap(Foo&, Foo&), that overload of swap will be used.

典型的例子：

1、Range-based for loop

2、Swap values

cppreference ADL

Argument-dependent lookup, also known as ADL, or Koenig lookup, is the set of rules for looking up the unqualified function names in function-call expressions, including implicit function calls to overloaded operators. These function names are looked up in the namespaces of their arguments in addition to the scopes and namespaces considered by the usual unqualified name lookup.

NOTE:

一、使用ADL的场景:

"unqualified function names in function-call expressions, including implicit function calls to overloaded operators"

二、简而言之：在lookup function name的时候，考虑如下namespace：

1、ADL: namespace of their argument

2、ordinary lookup: scope and namespace considered by the usual unqualified name lookup（可能包含当前scope）

三、次序

1、思考：上述两者，谁先谁后？

通过swap的例子来看，应该是首先进行ADL，然后进行ordinary lookup。在cpppatterns Range-based algorithms中对此进行了说明：

On lines 12–13, we call begin and end on the range to get the respective iterators to the beginning and end of the range. We use using-declarations on lines 7–8 to allow these calls to be found via argument-dependent lookup before using the standard std::begin and std::end functions. With these iterators, we can now implement the algorithm over the elements between them.

2、ADL优秀在parameter的name space中进行lookup，然后是current name space，这和Python的lookup顺序是有些类似的

Argument-dependent lookup makes it possible to use operators defined in a different namespace. Example:

Example

#include <iostream>
int main()
{
    std::cout << "Test\n"; // There is no operator<< in global namespace, but ADL
                           // examines std namespace because the left argument is in
                           // std and finds std::operator<<(std::ostream&, const char*)
    operator<<(std::cout, "Test\n"); // same, using function call notation

    // however,
    std::cout << endl; // Error: 'endl' is not declared in this namespace.
                       // This is not a function call to endl(), so ADL does not apply

    endl(std::cout); // OK: this is a function call: ADL examines std namespace
                     // because the argument of endl is in std, and finds std::endl

    (endl)(std::cout); // Error: 'endl' is not declared in this namespace.
                       // The sub-expression (endl) is not a function call expression

NOTE: 上述例子能够极好的帮助我们理解ADL：

std::cout << endl无法编译通过的原因是：ADL是用于lookup function的，unqualified的endl，没有在当前scope中声明，所以它无法被找到。

Details

NOTE: 原文的一段，冗长且没有例子，难以阅读；

Otherwise, for every argument in a function call expression its type is examined to determine the associated set of namespaces and classes that it will add to the lookup.

NOTE: 即考虑argument的namespace

Notes

Because of argument-dependent lookup, non-member functions and non-member operators defined in the same namespace as a class are considered part of the public interface of that class (if they are found through ADL) [2].

NOTE:

1、这非常重要，从interface的角度来理解。

2、上述观点是和Herb Sutter的文章What's In a Class? - The Interface Principle中的观点一致的

ADL is the reason behind the established idiom for swapping two objects in generic code:

using std::swap;
swap(obj1, obj2);

because calling std::swap(obj1, obj2) directly would not consider the user-defined swap() functions that could be defined in the same namespace as the types of obj1 or obj2, and just calling the unqualified swap(obj1, obj2) would call nothing if no user-defined overload was provided. In particular, std::iter_swap and all other standard library algorithms use this approach when dealing with Swappable types.

Name lookup rules make it impractical(不切实际的) to declare operators in global or user-defined namespace that operate on types from the std namespace, e.g. a custom operator>> or operator+ for std::vector or for std::pair (unless the element types of the vector/pair are user-defined types, which would add their namespace to ADL). Such operators would not be looked up from template instantiations, such as the standard library algorithms. See dependent names for further details.

NOTE: 上面这一段话，没有搞懂

ADL can find a friend function (typically, an overloaded operator) that is defined entirely within a class or class template, even if it was never declared at namespace level.

template<typename T>
struct number
{
    number(int) { }
    friend number gcd(number x, number y) { return 0; }; // definition within
                                                         // a class template
};
// unless a matching declaration is provided gcd is an invisible (except through ADL)
// member of this namespace
void g() {
    number<double> a(3), b(4);
    a = gcd(a,b); // finds gcd because number<double> is an associated class,
                  // making gcd visible in its namespace (global scope)
//  b = gcd(3,4); // Error; gcd is not visible
}

int main()
{
    g();
}

NOTE: g++ test.cpp

(until C++20)

Although a function call can be resolved through ADL even if ordinary lookup finds nothing, a function call to a function template with explicitly-specified template arguments requires that there is a declaration of the template found by ordinary lookup (otherwise, it is a syntax error to encounter an unknown name followed by a less-than character)

NOTE: lookup template和lookup function call

namespace N1 {
  struct S {};
  template<int X> void f(S) {}
}
namespace N2 {
  template<class T> void f(T t) {}
}
void g(N1::S s) {
  f<3>(s);      // Syntax error until C++20 (unqualified lookup finds no f)
  N1::f<3>(s);  // OK, qualified lookup finds the template 'f'
  N2::f<3>(s);  // Error: N2::f does not take a non-type parameter
                //        N1::f is not looked up because ADL only works
                //              with unqualified names
  using N2::f;
  f<3>(s); // OK: Unqualified lookup now finds N2::f
           //     then ADL kicks in because this name is unqualified
           //     and finds N1::f
}
int main()
{
g(N1::S());
}

In the following contexts ADL-only lookup (that is, lookup in associated namespaces only) takes place:

• the lookup of non-member functions begin and end performed by the range-for loop if member lookup fails
• the dependent name lookup from the point of template instantiation.
• the lookup of non-member function get performed by structured binding declaration for tuple-like types (since C++17)

ADL and multiple dispatch

ADL和OOP multiple dispatch是有着相似之处的:

1) 都将多个argument纳入了考虑

stackoverflow What is “Argument-Dependent Lookup” (aka ADL, or “Koenig Lookup”)?

NOTE: 这篇文章介绍的更多一些

Practice

Idiom based on ADL

• Swappable idiom
• Range-based algorithms
• Range-based for loop

get_rtti

我已经使用了c++ ADL了，get_rtti就是一个例子。下面是简化的代码：

#include <string>
#include <iostream>

/**
 *  * 结构体1
 *   */
struct MyStruct1
{
};

/**
 *  * 结构体
 *   */
struct MyStruct2
{
};

/**
 *  * 结构体类型信息
 *   */
typedef std::string CStructRtti;

/**
 *  * 获得结构体MyStruct的类型信息，这是按照对象来获取结构体类型信息
 *   * @param f
 *    * @return
 *     */
CStructRtti GetRtti(MyStruct1* f)
{
    return "MyStruct1";
}

/**
 *  * 获得结构体MyStruct的类型信息，这是按照对象来获取结构体类型信息
 *   * @param f
 *    * @return
 *     */
CStructRtti GetRtti(MyStruct2* f)
{
    return "MyStruct2";
}

/**
 *  * 模板函数，根据结构体类型来获取结构体类型信息，它的实现是派发到上述的根据结构体对象来获取结构体类型休息
 *   * @return
 *    */
template<typename StructT>
CStructRtti GetRttiByType()
{
    StructT Tmp = StructT();
    return GetRtti(&Tmp);
}

class Utility
{
public:
    template<typename StrucT>
    static CStructRtti GetRtti()
    {
        return GetRttiByType<StrucT>();
    }

};
/**
 *  * 该namespace内部和外部的结构基本一致
 *   * @param f
 *    * @return
 *     */
namespace NS
{
/**
 *  * 结构体1
 *   */
struct MyStruct1
{
};

/**
 *  * 结构体
 *   */
struct MyStruct2
{
};

/**
 *  * 获得结构体MyStruct的类型信息，这是按照对象来获取结构体类型信息
 *   * @param f
 *    * @return
 *     */
CStructRtti GetRtti(MyStruct1* f)
{
    return "NS::MyStruct1";
}

/**
 *  * 获得结构体MyStruct的类型信息，这是按照对象来获取结构体类型信息
 *   * @param f
 *    * @return
 *     */
CStructRtti GetRtti(MyStruct2* f)
{
    return "NS::MyStruct2";
}


class Utility
{
public:
    template<typename StrucT>
    static CStructRtti GetRtti()
    {
        return GetRttiByType<StrucT>();
    }

};
}

int main()
{
    std::cout<<Utility::GetRtti<MyStruct1>()<<std::endl;
    std::cout<<NS::Utility::GetRtti<NS::MyStruct1>()<<std::endl;
}

观察ADL

在C++\Idiom\OOP\Non-throwing-swap中给出的例子，就展示了ADL：

使用Swappable idiom

#include <utility>
#include <cstring>
#include <algorithm>
#include <iostream>

namespace Orange
{
class String
{
    char * str;
    public:
    void swap(String &s) // noexcept
    {
        std::cout << __PRETTY_FUNCTION__ << std::endl;
        std::swap(this->str, s.str);
    }
    String(const char* p)
    {
        size_t size = strlen(p) + 1;
        str = new char[size];
        memcpy(str, p, size);
    }
    friend std::ostream& operator<<(std::ostream& Stream, String& S)
    {
        Stream << S.str;
        return Stream;
    }
};
void swap(String & s1, String & s2) // noexcept
{
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    s1.swap(s2);
}

}

namespace std
{
template<>
void swap(Orange::String & s1, Orange::String & s2) // noexcept
{
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    s1.swap(s2);
}
}

int main()
{
    using std::swap;
    Orange::String s1("hello");
    Orange::String s2("world");
    std::cout << "Before swap:" << std::endl;
    std::cout << s1 << " " << s2 << std::endl;
    swap(s1, s2);
    std::cout << "After swap:" << std::endl;
    std::cout << s1 << " " << s2 << std::endl;
}
// g++ --std=c++11 test.cpp

输出如下:

Before swap:
hello world
void Orange::swap(Orange::String&, Orange::String&)
void Orange::String::swap(Orange::String&)
After swap:
world hello

使用std::swap

#include <utility>
#include <cstring>
#include <algorithm>
#include <iostream>

namespace Orange
{
class String
{
    char * str;
    public:
    void swap(String &s) // noexcept
    {
        std::cout << __PRETTY_FUNCTION__ << std::endl;
        std::swap(this->str, s.str);
    }
    String(const char* p)
    {
        size_t size = strlen(p) + 1;
        str = new char[size];
        memcpy(str, p, size);
    }
    friend std::ostream& operator<<(std::ostream& Stream, String& S)
    {
        Stream << S.str;
        return Stream;
    }
};
void swap(String & s1, String & s2) // noexcept
{
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    s1.swap(s2);
}

}

namespace std
{
template<>
void swap(Orange::String & s1, Orange::String & s2) // noexcept
{
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    s1.swap(s2);
}
}

int main()
{
    // using std::swap;
    Orange::String s1("hello");
    Orange::String s2("world");
    std::cout << "Before swap:" << std::endl;
    std::cout << s1 << " " << s2 << std::endl;
    std::swap(s1, s2);
    std::cout << "After swap:" << std::endl;
    std::cout << s1 << " " << s2 << std::endl;
}
// g++ --std=c++11 test.cpp

输出如下:

Before swap:
hello world
void std::swap(_Tp&, _Tp&) [with _Tp = Orange::String]
void Orange::String::swap(Orange::String&)
After swap:
world hello

TODO

http://www.gotw.ca/gotw/030.htm

https://quuxplusone.github.io/blog/2019/04/26/what-is-adl/

https://stackoverflow.com/questions/18086292/is-bjarne-wrong-about-this-example-of-adl-or-do-i-have-a-compiler-bug