company_banner

Близкие контакты ADL-ной степени


    Как навсегда вписать своё имя в историю? Первыми слетать на Луну? Первым встретиться с инопланетным разумом? У нас есть способ проще — можно вписать себя в стандарт языка C++.


    Хороший пример показывает Эрик Ниблер — автор C++ Ranges. «Запомните это. 19 февраля 2019 года — день, когда термин «ниблоид» впервые произнесли на встрече WG21» — написал он в Twitter.


    И действительно, если зайти на CppReference, в раздел cpp/algorithm/rangescpp/algorithm/ranges, можно найти там множество упоминаний (niebloid). Для этого даже сделан отдельный вики-шаблон dsc_niebloid.


    К сожалению, я не нашёл никакой официальной полноценной статьи на эту тему и решил написать свою. Это небольшое, но увлекательное путешествие в пучины архитектурной астронавтики, в которой мы сможем окунуться в бездну ADL безумия и познакомиться с ниблоидами.


    Важно: я не настоящий сварщик, а джавист, который иногда правит ошибки в C++ коде по мере необходимости. Если вы потратите немного времени, чтобы помочь найти ошибки в рассуждениях, это будет неплохо. «Помоги Даше-путешественнице собрать что-нибудь разумное».


    Lookup


    Вначале нужно определиться с терминами. Это всем известные вещи, но «явное лучше неявного», поэтому проговорим их отдельно. Я не использую настоящую русскоязычную терминологию, а вместо этого использую англицизмы. Это нужно потому, что даже слову «ограничение» в контексте этой статьи можно сопоставить минимум три английских варианта, разница между которыми важна для понимания.


    Например, в С++ есть понятие поиска имён или иначе — лукапа: когда в программе встречается какое-то имя, во время компиляции оно связывается со своим объявлением.


    Лукап бывает квалифицированным, (если имя находится справа от оператора разрешения скоупа ::), и неквалифицированным в других случаях. Если лукап квалифицирован, то мы обходим соответствующие члены класса, неймспейса или перечисления. Можно было бы назвать это «полным» вариантом записи (как, кажется, делают в переводе Страуструпа), но лучше оставить оригинальное написание, потому что имеется в виду очень конкретный вид полноты.


    ADL


    Если лукап не квалифицирован, то нам нужно понять, где именно искать имя. И тут включается специальная фича под названием ADL: argument-dependent lookup, или иначе — поиск Кёнига (того самого, который придумал термин «анти-паттерн», что немного символично в свете последующего текста). Nicolai Josuttis в своей книге «The C++ Standard Library: A Tutorial and Reference» описывает его так: «Смысл в том, что вам не нужно квалифицировать неймспейс функции, если хотя бы один из типов аргументов определен в неймспейсе этой функции».


    Как это должно выглядеть?


    #include <iostream>
    
    int main() {
        // Это сработает.
        // С одной стороны, operator<< нет в глобальном неймспейсе, но ADL посмотрит,
        // что находится в std и найдёт там std::operator<<(std::ostream&, const char*)                                                
        std::cout << "Test\n";
    
        // И это тоже сработает. Это всего лишь другая нотация - запись в виде вызова функции.
        operator<<(std::cout, "Test\n"); // same, using function call notation
    
        // Это упадёт с ошибкой:
        // Error: 'endl' is not declared in this namespace.
        // Тут уже не вызов функции endl(), поэтому ADL не запускается. 
        std::cout << endl; 
    
        // Это сработает.
        // Мы притащили вызов функции, и на этом сразу же отработал ADL.
        // Поскольку аргумент находится в std, то и endl будут искать и найдут в std. 
        endl(std::cout);
    
        // Это упадёт с ошибкой:
        // Error: 'endl' is not declared in this namespace.
        // Просто потому, что под-выражение (endl) - это не выражение вызова функции.
        (endl)(std::cout); 
    }

    Спускаемся в ад с ADL


    Казалось бы, просто. Или нет? Во-первых, в зависимости от типа аргумента, ADL работает девятью разными способами, убиться веником.


    Во-вторых, чисто практически, представьте, что у нас есть некая функция swap. Получается, что std::swap(obj1,obj2); и using std::swap; swap(obj1, obj2); могут вести себя совершенно по-разному. Если включается ADL, то из нескольких разных swap нужный выбирается уже исходя из неймспейсов аргументов! В зависимости от точки зрения эту идиому можно считать как положительным, так и отрицательным примером :-)


    Если вам кажется, что этого недостаточно, можно докинуть дров в печь хейта. Об этом недавно хорошо написал Arthur O'Dwyer. Надеюсь, он не покарает меня за использование своего примера.


    Представьте, что у вас есть программа такого вида:


    #include <stdio.h>
    
    namespace A {
        struct A {};
        void call(void (*f)()) {
            f();
        }
    }
    
    void f() {
        puts("Hello world");
    }
    
    int main() {
        call(f);
    }

    Она, конечно, не компилируется с ошибкой:


    error: use of undeclared identifier 'call'; did you mean 'A::call'?
        call(f);
        ^~~~
        A::call

    Но если добавить туда совершенно неиспользуемую перегрузку функции f, то всё заработает!


    #include <stdio.h>
    
    namespace A {
        struct A {};
        void call(void (*f)()) {
            f();
        }
    }
    
    void f() {
        puts("Hello world");
    }
    
    void f(A::A);  // UNUSED
    
    int main() {
        call(f);
    }

    На Visual Studio всё равно сломается, но такова уж её судьба, не работать.


    Как это получилось? Давайте покопаемся в стандарте (без перевода, потому что такой перевод был бы исключительно чудовищной мешаниной баззвордов):


    If the argument is the name or address of a set of overloaded functions and/or function templates, its associated entities and namespaces are the union of those associated with each of the members of the set, i.e., the entities and namespaces associated with its parameter types and return type. [...] Additionally, if the aforementioned set of overloaded functions is named with a template-id, its associated entities and namespaces also include those of its type template-arguments and its template template-arguments.

    Теперь возьмём кода такого вида:


    #include <stdio.h>
    
    namespace B {
        struct B {};
        void call(void (*f)()) {
            f();
        }
    }
    
    template<class T>
    void f() {
        puts("Hello world");
    }
    
    int main() {
        call(f<B::B>);
    }

    В обоих случаях получаются аргументы, у которых нет типа. f and f<B::B> — это имена наборов перегруженных функций (из определения выше), и такой набор не имеет типа. Чтобы свернуть перегрузку в одну-единственную функцию, нужно понять, какой тип указателя на функции наиболее подходит к самой лучшей перегрузке call. Значит, нужно собрать набор кандидатов для call, значит — запустить лукап имени call. И для этого запустится ADL!


    Но ведь обычно для ADL мы должны знать типы аргументов! И вот тут Clang, ICC, и MSVC ошибочно сломаются следующим образом (а GCC — нет):


    [build] ..\..\main.cpp(15,5): error: use of undeclared identifier 'call'; did you mean 'B::call'?
    [build]     call(f<B::B>);
    [build]     ^~~~
    [build]     B::call
    [build] ..\..\main.cpp(4,10): note: 'B::call' declared here
    [build]     void call(void (*f)()) {
    [build]          ^

    Даже у создателей компиляторов с ADL немного натянутые отношения.


    Ну как, ADL всё ещё кажется вам хорошей идеей? С одной стороны, нам больше не нужно по-гошному писать вот такой рабский код:


    std::cout << "Hello, World!" << std::endl;
    std::operator<<(std::operator<<(std::cout, "Hello, World!"), "\n");

    С другой стороны, мы променяли на лаконичность тот факт, что теперь существует система, работающая совершенно негуманоидным образом. Трагическая и величественная история о том, как удобство написания хэлловорлда может повлиять на весь язык в масштабе десятилетий.


    Ренжи и концепты


    Если вы откроете описание библиотеки ренжей Ниблера, то ещё до упоминания ниблоидов наткнетесь на множество других маркеров под названием (concept). Это уже довольно распиаренная штука, но на всякий случай (для олдов и джавистов) напомню, что это такое.


    Концептами называются именованные наборы ограничений, которые применяются к шаблонным аргументам для выбора самых лучших перегрузок функций и самых подходящих специализаций шаблонов.


    template <typename T>
    concept bool HasStringFunc = requires(T a) {
        { to_string(a) } -> string;   
    };
    
    void print(HasStringFunc a) {
        cout << to_string(a) << endl;
    }

    Здесь мы наложили ограничение, что у аргумента должна существовать функция to_string, возвращающая строку. Если мы попытаемся засунуть в print какую-нибудь дичь, не попадающую под ограничения, то такой код просто не скомпилируется.


    Это здорово упрощает код. Например, посмотрите, как сделал Ниблер сортировку в ranges-v3, которая работает на C++11/14/17. Там есть чудный код вроде такого:


    #define CONCEPT_PP_CAT_(X, Y) X ## Y
    #define CONCEPT_PP_CAT(X, Y)  CONCEPT_PP_CAT_(X, Y)
    /// \addtogroup group-concepts                 
    /// @{                                         
    #define CONCEPT_REQUIRES_(...)                                                      \
        int CONCEPT_PP_CAT(_concept_requires_, __LINE__) = 42,                          \
        typename std::enable_if<                                                        \
            (CONCEPT_PP_CAT(_concept_requires_, __LINE__) == 43) || (__VA_ARGS__),      \
            int                                                                         \
        >::type = 0                                                                     \
        /**/

    Чтобы потом можно было делать:


    struct Sortable_
        {
            template<typename Rng, typename C = ordered_less, typename P = ident,
                typename I = iterator_t<Rng>>
            auto requires_() -> decltype(
                concepts::valid_expr(
                    concepts::model_of<concepts::ForwardRange, Rng>(),
                    concepts::is_true(ranges::Sortable<I, C, P>())
                ));
        };
    
    using Sortable = concepts::models<Sortable_, Rng, C, P>;
    
    template<typename Rng, typename C = ordered_less, typename P = ident,
                    CONCEPT_REQUIRES_(!Sortable<Rng, C, P>())>
                void operator()(Rng &&, C && = C{}, P && = P{}) const
                { 
                    ...

    Надеюсь, вы уже захотели всё это развидеть и просто пользоваться готовенькими концептами в свежем компиляторе.


    Точки кастомизации


    Следующая интересная вещь, которую можно найти в стандарте — customization.point.object. Они активно используются в библиотеке ренжей Ниблера.


    Точка кастомизации — это функция, используемая стандартной библиотекой так, что её можно перегрузить для пользовательских типов в неймспейсе пользователя, и эти перегрузки находится с помощью ADL.


    Точки кастомпизации разработаны с учетом следующих архитектурных принципов (cust здесь — это название для какой-то воображаемой точки кастомизации):


    • Код, который зовёт cust записан или в квалифицированном виде std::cust(a), или в неквалифицированном: using std::cust; cust(a);. Обе записи должны вести себя идентично. В частности, они должны находить любые пользовательские перегрузки в неймспейсах, связанных с аргументами.
    • Код, который использует cust в форме записи std::cust; cust(a); не должен иметь возможности обходить ограничения, наложенные на std::cust.
    • Вызовы точек кастомизации должны эффективно и оптимально работать на любом достаточно современном компиляторе.
    • Решение не должно создавать никаких новых нарушений Правила одного определения (ODR).

    Чтобы понять, что это такое, можно взглянуть на N4381. На первый взгляд они выглядят как способ писать собственные версии begin, swap, data, и тому подобного, а стандартная библиотека подхватит их с помощью ADL.


    Возникает вопрос, как это отличается от старой практики, когда пользователь пишет перегрузку для какого-нибудь begin для собственного типа и неймспейса? И почему они вообще являются объектами?


    На самом деле, это экземпляры функциональных объектов в неймспейсе std. Их предназначение в том, чтобы вначале дернуть проверки типов (оформленные как концепты) на всех аргументах подряд, а потом диспетчерезировать вызов на правильную функцию в неймспейсе std или отдать это на откуп в ADL.


    По сути, это не та штука, которую вы стали бы использовать в обычной не библиотечной программе. Это фича стандартной библиотеки, которая позволит добавить проверку концептов на будущих точках расширений, что в свою очередь приведёт к отображению более красивых и понятных ошибок, если вы что-то напутали в шаблонах.


    У текущего подхода к точкам кастомизации есть пара проблем. Во-первых, очень легко всё сломать. Представьте вот такой код:


    template<class T> void f(T& t1, T& t2)
    {
        using std::swap;
        swap(t1, t2);
    }

    Если мы случайно сделаем квалифицированный вызов std::swap(t1, t2) то наш собственный вариант swap уже никогда не запустится, чего бы мы туда не пихали. Но что важней, нет никакого способа централизованно навесить проверки-концепты на такие кастомные реализации функций. В N4381 пишут:


    «Представьте, что когда-нибудь в будущем std::begin потребует, чтобы её аргумент моделировался как концепт Range. Добавление такого ограничения просто не окажет никакого эффекта на код, идиоматично использующий std::begin:


    using std::begin; 
    begin(a); 

    Ведь если вызов begin диспетчеризуется в перегруженный вариант, созданный пользователем, тогда ограничения на std::begin просто проигнорируются».


    Решение, описанное в пропозале, решает обе проблемы, для этого используется подход из вот такой умозрительной реализации std::begin (можно посмотреть на godbolt):


    #include <utility>
    
    namespace my_std {
    namespace detail {
        struct begin_fn {
            /* Вызов операторного шаблона, внутри которого
                выполнятся провеки концептов и будет запущен
                begin(arg) или arg.begin(). Это - сердце данного подхода. */
            template <class T>
            auto operator()(T&& arg) const {
                return impl(arg, 1L);
            }
    
            template <class T>
            auto impl(T&& arg, int) const
                requires requires { begin(std::declval<T>()); }
            { return begin(arg); } // ADL
    
            template <class T>
            auto impl(T&& arg, long) const
                requires requires { std::declval<T>().begin(); }
            { return arg.begin(); }
    
            // ...
        };
    }
    
    // Глобальный фукнциональный объект должен быть инлайновой переменной
    inline constexpr detail::begin_fn begin{};
    }

    Квалифицированный вызов какого-нибудь my_std::begin(someObject) всегда проходит сквозь my_std::detail::begin_fn — и это хорошо. Что происходит с неквалифицированным вызовом? Давайте снова почитаем нашу бумагу:


    «В случае, когда begin вызывается без квалификации сразу после появления my_std::begin внутри скоупа, ситуация несколько меняется. На первом этапе лукапа, имя begin разрешится в глобальный объект my_std::begin. Поскольку лукап нашел объект, а не функцию, вторая фаза лукапа не выполняется. Другими словами, если my_std::begin — объект, то использование конструкции my_std::detail::begin_fn begin; begin(a); эквивалентно просто std::begin(a); — и как уже мы видели, это запускает пользовательский ADL».


    Именно поэтому проверку концептов можно делать в функциональном объекте в неймспейсе std, до того, как ADL позовёт функцию, предоставленную пользователем. Нет никаких способов обмануть это поведение.


    Как кастомизируют точки кастомизации?


    На самом деле, «customization point object» (CPO) — это не очень хорошее название. Из названия не понятно, как они расширяют, какие механизмы лежат под капотом, каким функциям они отдают предпочтение...


    Что приводит нас к термину «ниблоид». Ниблоид — это такой CPO который вызывает функцию X если она определена в классе, иначе вызывает функцию X, если есть подходящая свободная функция, иначе пытается выполнить некий fallback функции X.


    Так например ниблоид ranges::swap при вызове ranges::swap(a, b) вначале попробует вызвать a.swap(b). Если такого метода нет — попытается вызвать swap(a, b), используя ADL. Если и это не работает — попробует выполнить auto tmp = std::move(a); a = std::move(b); b = std::move(tmp).


    Итоги


    Как пошутил Мэтт в Twitter, однажды Дэйв предложил заставить функциональные объекты "работать" с ADL так же, как это делают обычные функции, из соображений консистентности. Ирония в том, что их свойство отключать ADL и быть невидимыми для него теперь стало их основными преимуществами.


    Вся эта статья была приготовлением для вот этого.


    "Просто я все понял, вот и все. Ты будешь слушать?


    Ты когда-нибудь смотрела на что-то, и оно казалось безумным, а потом в ином свете на
    безумные вещи, видя их нормальными?



    Не бойся. Не бойся. Мне так хорошо на душе. Все будет хорошо. Я не чувствовал себя так хорошо много лет. Все будет нормально.



    Минутка рекламы. Уже на этой неделе, 19-20 апреля, пройдёт С++ Russia 2019 — конференция, наполненная хардкорными докладами как по самому языку, так и по практическим вопросам вроде многопоточности и производительности. Кстати, конференцию открывает упомянутый в статье Nicolai Josuttis, автор «The C++ Standard Library: A Tutorial and Reference». Ознакомиться с программой и приобрести билеты можно на официальном сайте. Осталось очень мало времени, это последний шанс.
    • +35
    • 3,4k
    • 2
    JUG.ru Group
    907,00
    Конференции для программистов и сочувствующих. 18+
    Поделиться публикацией

    Комментарии 2

      +5
      TL, DR:
      Ниблоид — это такой CPO который вызывает функцию X если она определена в классе, иначе вызывает функцию X, если есть подходящая свободная функция, иначе пытается выполнить некий fallback функции X.
        +6
        Ни_я не понял, но очень интересно!

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое