How to put your name in history forever? The first to fly to the moon? The first to meet with an alien mind? We have a simpler way - you can write yourself into the standard of the C ++ language.

A good example is Eric Nibler, author of C ++ Ranges. “Remember this. February 19, 2019 is the day when the term “nibloid” was first pronounced at the WG21 meeting, ”he wrote on Twitter.

And indeed, if you go to the CppReference, in the section cpp / algorithm / rangescpp / algorithm / ranges , you can find there many references (niebloid). To do this, even made a separate wiki template dsc_niebloid .

Unfortunately, I did not find any official full-fledged article on this topic and decided to write my own. This is a small, but fascinating journey into the abyss of architectural astronautics, in which we can plunge into the abyss of ADL madness and meet with nibloids.

Important: I am not a real welder, but a javist, who sometimes corrects errors in C ++ code as needed. If you spend a little time to help find errors in reasoning, it will be nice. "Help Dasha the traveler to collect something reasonable."

Lookup

First you need to decide on the terms. These are well-known things, but “the obvious is better than the implicit,” so let's talk them separately. I do not use real Russian terminology, but instead use Englishism. This is necessary because even the word “restriction” in the context of this article can be compared with at least three English versions, the difference between which is important for understanding.

For example, in C ++ there is the concept of searching for names or otherwise - lukapa: when a program encounters a name , it is associated with its declaration at compile time.

Lucap is qualified , (if the name is to the right of the Scop permit operator :: :), and unqualified in other cases. If the lookup is qualified, then we bypass the appropriate members of the class, namespace, or enumeration. One could call it the “full” version of the record (as it seems to be done in the Stroustrup translation), but it is better to leave the original spelling, because it means a very specific kind of completeness.

ADL

If Lukap is not qualified, then we need to understand exactly where to look for the name. And here comes a special feature called ADL: argument-dependent lookup , or else, a search for Koenig (the one who coined the term “anti-pattern”, which is a bit symbolic in the light of the following text). Nicolai Josuttis in his book “The C ++ Standard Library: A Tutorial and Reference” describes it like this: “The point is that you don’t need to qualify the namespace function if at least one of the argument types is defined in the namespace of this function.”

What should it look like?

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

Get down to hell with ADL

It would seem simple. Or not? First, depending on the type of argument, ADL works in nine different ways , get killed with a broom.

Secondly, purely practically, imagine that we have a certain function swap. It turns out that std::swap(obj1,obj2); and using std::swap; swap(obj1, obj2); using std::swap; swap(obj1, obj2); may behave completely differently. If ADL is included, then from several different swaps the necessary one is selected based on the namespaces of the arguments! Depending on the point of view, this idiom can be considered both a positive and negative example :-)

If it seems to you that this is not enough, you can throw the wood into the stove heyta. This was recently well written by Arthur O'Dwyer . I hope he does not punish me for using my example.

Imagine that you have a program of this type:

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

Of course, it does not compile with an error:

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

But if we add a completely unused overload of the function f , then everything will work!

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

At Visual Studio it will still break, but such is its fate, not to work.

How did it happen? Let's dig in the standard (without translation, because such a translation would be an extremely monstrous mix of buzzwords):

This is a list of the rules of the association. types and return type. [...] Additionally, it’s also possible to use it.

Now take a code like this:

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

In both cases, arguments are obtained that have no type. f and f<B::B> are the names of the sets of overloaded functions (from the definition above), and such a set has no type. To minimize the overload into a single function, you need to understand which type of function pointer is best suited to the best overload call . So, you need to collect a set of candidates for call , it means - to launch the call name call . And for this ADL will start!

But usually, for ADL, we need to know the types of arguments! And here Clang, ICC, and MSVC mistakenly break like this (GCC doesn't):

 [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] ^ 

Even the creators of the compilers with ADL have some strained relationships.

Well, ADL still seems like a good idea to you? On the one hand, we no longer need to write such slave code in a way that looks like this:

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

On the other hand, we traded for brevity the fact that now there is a system that works in a completely non-humanoid manner. The tragic and magnificent story of how the convenience of writing Hello World can affect the entire language across decades.

Rengi and concepts

If you open the description of the library Nibblera , then before mentioning nibloidov stumble on many other markers called (concept) . This is already a pretty raspiarennaya thing, but just in case (for the Old and Javista) I remind you what it is .

Concepts are called named sets of constraints that apply to template arguments to select the best function overloads and the most appropriate template specializations.

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

Here we have imposed the restriction that the argument must have a function to_string , which returns a string. If we try to shove any game into print that does not fall under the restrictions, then such code simply will not compile.

This is great code simplification. For example, see how Niebler did the sorting in ranges-v3 , which works on C ++ 11/14/17. There is a wonderful code like this:

 #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 \ /**/ 

So that you can do it later:

 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 { ... 

I hope you already wanted to sort it all out and just use ready-made concepts in a fresh compiler.

Customization points

The next interesting thing that can be found in the standard is customization.point.object . They are actively used in the library of Nibbler.

The customization point is a function used by the standard library so that it can be reloaded for user types in the user's namespace, and these overloads are found using ADL.

The customization points have been developed taking into account the following architectural principles ( cust here is the name for some imaginary customization point):

• The code that calls cust written either in a qualified form std::cust(a) , or unqualified: using std::cust; cust(a); using std::cust; cust(a); . Both entries must behave identically. In particular, they must find any user overloads in the namespaces associated with the arguments.
• Code that uses cust in the form of std::cust; cust(a); std::cust; cust(a); should not be able to bypass the restrictions imposed on std::cust .
• The challenges of customization points should work efficiently and optimally on any sufficiently modern compiler.
• The decision should not create any new violations of the Rules for a single definition (ODR) .

To understand what it is, you can take a look at N4381 . At first glance, they look like a way to write your own versions of begin , swap , data , and the like, and the standard library picks them up with ADL.

The question arises, how is this different from the old practice when the user writes an overload for some begin for his own type and namespace? And why are they objects at all?

In fact, these are instances of functional objects in the std . Their purpose is to first pull type checks (designed as concepts) on all arguments in a row, and then dispatch the call to the correct function in std or redeem it to ADL.

In fact, this is not the thing that you would use in a regular non-library program. This is a feature of the standard library, which will allow you to add concept checking on future extension points, which in turn will lead to displaying more beautiful and understandable errors if you have messed up something in the templates.

The current approach to customization points has a couple of problems. First, it is very easy to break everything. Imagine this code:

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

If we accidentally make a qualified call to std::swap(t1, t2) then our own version of the swap will never start, which we would not push there. But what is more important, there is no way to centrally check concept checks on such custom implementations of functions. In N4381 write:

“Imagine that sometime in the future, std::begin will require its argument to be modeled as a Range concept. Adding such a restriction simply will not have any effect on the code idiomatically using std::begin :

 using std::begin; begin(a); 

After all, if the begin call is dispatched to the overloaded version created by the user, then the restrictions on std::begin simply ignored. ”

The solution described in propozale solves both problems, for this the approach from the following speculative implementation of std::begin (you can look at 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{}; } 

A qualified call to some kind of my_std::begin(someObject) always passes through my_std::detail::begin_fn - and that's good. What happens to the unqualified call? Let's read our paper again:

“In the case when begin is called without qualification immediately after the appearance of my_std::begin inside the loop, the situation changes somewhat. In the first stage of the lukap, the name begin resolve to the global object my_std::begin . Since lukap found an object, not a function, the second phase of the lukap is not performed. In other words, if my_std::begin is an object, then use the construction my_std::detail::begin_fn begin; begin(a); my_std::detail::begin_fn begin; begin(a); equivalent to just std::begin(a); - and as we have already seen, it launches a custom ADL. ”

That is why concept checking can be done in a functional object in std , before ADL calls the function provided by the user. There is no way to fool this behavior.

How to customize customization points?

In fact, “customization point object” (CPO) is not a very good name. From the name it is not clear how they expand, what mechanisms lie under the hood, what functions they prefer ...

Which leads us to the term "nibloid". A nibloid is such a CPO that calls function X if it is defined in a class, otherwise it calls function X, if there is a suitable free function, otherwise it tries to perform some fallback of function X.

So for example, the nibloid ranges::swap when calling ranges::swap(a, b) will first try to call a.swap(b) . If there is no such method, it will try to call swap(a, b) using ADL. If that doesn't work either, it will try auto tmp = std::move(a); a = std::move(b); b = std::move(tmp) auto tmp = std::move(a); a = std::move(b); b = std::move(tmp) auto tmp = std::move(a); a = std::move(b); b = std::move(tmp) .

Results

As Matt joked on Twitter, Dave once offered to make functional objects "work" with ADL in the same way as regular functions do, for consistency reasons. The irony is that their property to disable ADL and being invisible to it has now become their main advantage.

This whole article was a preparation for this.

" I just understood everything, that's all. Will you listen ?

Have you ever looked at something, and it seemed insane, and then in a different light on
crazy things seeing them normal?

Do not be afraid. Do not be afraid. I'm so good at heart. Everything will be fine. I have not felt so good for many years. Everything will be fine.

Minute advertising. Already this week , April 19-20, C ++ Russia 2019 will be held - a conference full of hardcore presentations both on the language itself and on practical issues like multithreading and performance. By the way, the conference is opened by Nicolai Josuttis mentioned in the article, the author of "The C ++ Standard Library: A Tutorial and Reference". You can view the program and purchase tickets on the official website . There is very little time left, this is the last chance.