Niebloids

Niebloids as a concept and pattern existed for a long time, they were first introduced by Eric Niebler in his C++14 range-v3 library.

The name was suggested by the author himself in a poll on twitter in 2018.

Before getting to niebloids, we first have to have some basic understanding in the following topics:

• Unqualified / Qualified lookup
• ADL (Argument Dependent Lookup)
• Customization Points
• Customization Point Objects

We will briefly go over them. You can skip to the last section if you are already familiar with them.

Qualified vs Unqualified Lookup

When we use any kind of an identifier in our code, lookup happens - the compiler tries to determine where the identifier is from and what it means in our code - is it a class/an object/a function? What type does it have? What namespace is it in? Etc.

We won't delve deeply into the details, because both are pretty complicated, but all we want to know is that the latter - unqualified lookup - is what we want.

Syntatically, qualified lookup implies the use of scope resolution operator - ::, that is:

{
  // auto value = my_ns::x; // Qualified lookup
  // The above fails, because `x` is not present in my_ns namespace

  // krabby_patty::patty_krabby(mr_krabs::secret_recipe); // Qualified lookup
  // The above fails, because namespaces `krabby_patty` and `mr_krabs` are not present

  std::print("Hello {}!", "World"); // Qualified lookup

  auto value = my_ns::MyEnum::One; // Qualified lookup

  ::printf("Hello %s!", "World"); // Qualified lookup
  // If there's nothing to the left of the scope resolution operator, it's refering to the global namespace
}

Hello hello; // Unqualified lookup to Hello, which is found in global scope

{
  // auto value = x; // Unqualified lookup, no scope resolution operator
  // The above fails, because `x` is nowhere to be found

  // foo(1, 2, 3); // Unqualified lookup, no scope resolution operator
  // The above fails, because `foo` is nowhere to be found

  std::print("{}", hello.world()); // Qualified lookup to `std::print`, unqualified lookup to `hello`, which is found in upper scope
  // Unqualified searches starting from the current scope up

  print_me(my_ns::MyEnum::One);
  // Unqualified lookup to `print_me`, qualified lookup to my_ns::MyEnum::One
  // This works.
  // But wait... print_me is not present in this scope, upper scope, nor global scope,
  // unqualified lookup didn't pick it up, so how does that work??
  // Is it a bug, magic, or maybe... ADL? :P
}

#include <cstdio>
#include <print>

namespace my_ns
{
  enum class MyEnum
  {
    One = 1,
    Two = 2
  };

  auto print_me(MyEnum my_enum) -> void
  {
    switch(my_enum) {
      case MyEnum::One: std::print("One :D\n"); break;
      case MyEnum::Two: std::print("One :D\n"); break;
      default: std::print("Boooo D:\n");
    }
  }
}

struct Hello
{
  auto world() const -> std::string
  {
    return "Helo, world!";
  }
};

auto main() -> int
{
  {
    // auto value = my_ns::x; // Qualified lookup
    // The above fails, because `x` is not present in my_ns namespace

    // krabby_patty::patty_krabby(mr_krabs::secret_recipe); // Qualified lookup
    // The above fails, because namespaces `krabby_patty` and `mr_krabs` are not present

    std::print("Hello {}!", "World"); // Qualified lookup

    auto value = my_ns::MyEnum::One; // Qualified lookup

    ::printf("Hello %s!", "World"); // Qualified lookup
    // If there's nothing to the left of the scope resolution operator, it's refering to the global namespace
  }

  Hello hello; // Unqualified lookup to Hello, which is found in global scope

  {
    // auto value = x; // Unqualified lookup, no scope resolution operator
    // The above fails, because `x` is nowhere to be found

    // foo(1, 2, 3); // Unqualified lookup, no scope resolution operator
    // The above fails, because `foo` is nowhere to be found

    std::print("{}", hello.world()); // Qualified lookup to `std::print`, unqualified lookup to `hello`, which is found in upper scope
    // Unqualified searches starting from the current scope up

    print_me(my_ns::MyEnum::One);
    // Unqualified lookup to `print_me`, qualified lookup to my_ns::MyEnum::One
    // But wait... print_me is not present in this scope, upper scope, nor global scope, how does that work??
    // Is it a bug, magic, or maybe... ADL? :P
  }
}

Both of these do a little bit different things, but unqualified lookup has one special property, Argument Dependent Lookup follows after it.

Argument Dependent Lookup

Argument Dependent Lookup (also sometimes reffered to as Koenig lookup) or ADL for short is a very advanced topic in itself, but in short, what it allows is calling functions from the argument's respective namespaces without qualifying them explicitly.

That sounds pretty complicated, but here's a simple example you've already seen and written a thousand times probably:

std::cout << "Hello, world!";

Yep. What we see above would not work if it wasn't for ADL. Here's how the code above looks to the compiler:

operator<<(std::cout, "Hello, world!");

You could even write this code yourself and see that it would compile (though, of course, no one would write code like this for real, it's not very practical and eliminates the convenience of overloading operators).

Here's the example from the previous section about lookup:

print_me(my_ns::MyEnum::One);

#include <cstdio>
#include <print>

namespace my_ns
{
  enum class MyEnum
  {
    One = 1,
    Two = 2
  };

  auto print_me(MyEnum my_enum) -> void
  {
    switch(my_enum) {
      case MyEnum::One: std::print("One :D\n"); break;
      case MyEnum::Two: std::print("One :D\n"); break;
      default: std::print("Boooo D:\n");
    }
  }
}

auto main() -> int
{
    print_me(my_ns::MyEnum::One);
}

You may be surprised it works - intuiton tells us that it shouldn't, because even though we have a fully qualified my_ns::MyEnum::One which is resolved via qualified lookup correctly, print_me is not qualified and should not be present in this scope, unqualified lookup shouldn't find it and this code should not compile.

And your intuition would be right.. At least if it wasn't for ADL.

What ADL does is actually very simple* - when you perform an unqualified call to a function, ADL follows and looks at the types of the arguments of the functions and adds all the functions from each namespace the types of the arguments participate in to the resolution set.

That is, when performing Argument Dependent Lookup on this function call:

print_me(my_ns::MyEnum::One);

We look at the type of the arguments, in this case my_ns::MyEnum, and add it's namespace (my_ns) to the resolution set.

my_ns does indeed contain print_me which accepts MyEnum::One as an argument, so it's found and later called.

* - well, it's actually a more complicated than that and it does a little bit more things, but that's the gist and that's what's actually important here

Unqualified lookup and ADL together

Unqualified Lookup and Argument Dependent Lookup work together, one after another. The important rule to keep in mind about ADL - it is not performed after unqualified lookup in several different cases.

One of these cases that is of interest to us is when unqualified lookup finds a declaration that is

• neither a function
• nor a function template

auto x = 2137;
auto y = x + 1; // unqualified lookup for x, no ADL because x is an object

And if you think about it - it makes sense, ADL should only apply to function calls, it doesn't make sense to apply ADL to an object that was being looked up. An object doesn't accept any parameters that we can examine.

Why am I talking about it? Because it's crucial for understanding niebloids.

So once again, keep in mind - ADL doesn't happen if unqualified lookup found something that is neither a function nor a function template

Customization Points

One of the ways we can utilize ADL in is making so called customization points.

You may not know about it, but you've probably used them yourself several times.

std::swap, std::data, std::begin, std::end - these are all customization points.

If you have a custom type which has a special, more performant or otherwise better implementation of any of these functions above, you can "hook" your own implementations by creating a free function with a matching interface in your type's namespace.

namespace my_ns {

struct MyAwesomeType { };

auto swap(MyAwesomeType& first, MyAwesomeType& second) -> void {
  // awesome implementation
}

}

This is great, but it has consequences. This design forces the programmer to remember about these customization points and handle them properly. What it means, is that everytime you write generic code, you have to remember to bring the default implementation to the current scope and call it unqualified, e.g.:

template <typename T, typename U>
auto awesome_function(T t, U u)
{
  using std::swap;
  swap(t, u);
}

Calling swap unqualified: swap(t, u); ensures that if the type has "hooked" into the customization point, it will be called.

If, however, there is no user provided implementation, this will produce an error, that's why we bring std::swap to the scope with using std::swap;, so that when there is no custom behaviour defined, the default one from the standard library will be chosen.

So, remember, everytime you see code like this:

std::swap(a, b);

where a and b are some generic parameters - it's probably a bug.

Customization Points are flawed, Customization Point Objects to the rescue

The two problems with customization points are that:

1. The programmer has to remember to correctly use them in generic code (doing more to achieve the correct thing)
2. If the standard decides to add some requirements to the types of these customization points (for example, Range, for begin, which is pretty sensible), it would not be possible to apply them to the "hooked", custom implementations.

These problems are solved by Customization Point Objects, or CPOs in short.

They came to C++ together with the C++20 standard.

CPOs have two main goals:

1. Define a central point to apply requirements to (which is easy to do, just apply the requirements to the CPO and tell programmers to use the CPO instead of classic customization points)
2. Define a central point to call, which will dispatch to either the "hooked" implementation or the default standard implementation

The second goal is done by inhibiting (disallowing) ADL. How do we do that? Well, there are currently only two ways to achieve that.

One of them is to to make them function objects, as specified in the Unqualified lookup and ADL together section, ADL doesn't happen if unqualified lookup happens to find something that is neither a function, nor a function template - a function object is none of those, so ADL is disabled.

The other way to implement such behaviour is to use internal compiler extensions, but no known implementation does that currently.

The CPOs are implemented under the std::ranges namespace in the standard library - std::ranges::swap, std::ranges::begin, etc.

Niebloids

Finally, we come to the pinnacle of this article - niebloids.

Cppreference* tells us that the key characteristics of a niebloid are:

• Niebloids inhibit ADL
• Explicit template arguments cannot be specified**

You may also stumble upon people mentioning, that even though they are templated, they can be passed to higher order functions without any problem.***

* Look at the end of the description of the algorithm, each and every rangified algorithm contains the same definition.

Implementation

You may notice, that niebloids have similar goals to CPOs. And, yeah, they are pretty much the same, except that niebloids don't allow for any customization points, that is, std::ranges::find is pretty much the same thing as std::ranges::swap, except that creating a free function called find doesn't really do anything, because these identifiers are not used as customization points.

Similarily to CPOs, they are also typically implemented using function objects, although that's not required.

** One of the characteristics specified is not being able to specify explicit template arguments, it is true with how niebloids are currently implemented by all the major vendors, but keep in mind that it's not a planned feature of niebloids and just a side effect of niebloids being implemented as function objects. This behaviour may change in the future, if vendors decide to conjure a special extension for ease of implementation/maintainability.

*** People also sometimes mention, that one of the advantages of niebloids over ordinary functions is that you can pass them to higher order functions (functions taking other functions as arguments, in this context) with no problem.

#include <algorithm>
#include <vector>

template <typename Fun>
auto do_thing(std::vector<int>& ints1, std::vector<int>& ints2, Fun fun)
{
  fun(ints1, ints2);
}

auto main() -> int
{
  auto ints1 = std::vector { 5, 4, 3, 2, 1 };
  auto ints2 = std::vector { 1, 2, 3, 4, 5 };
  do_thing(ints1, ints2, std::ranges::swap); // Would not compile with std::swap
}

And while it is true for range-v3, because the key design is to use function objects and have these advantages, it's not true for std:: niebloids, the standard doesn't specify they have to be implemented to allow such behaviour.

This means you should not rely on this behaviour, because your code may break in the future.

Ways to pass such a function to HOF

If you have a need to pass such a function to some HOF, you can use a lambda that mimics the intended interface:

#include <iostream>
#include <algorithm>
#include <vector>

template <typename Fun>
auto do_thing(std::vector<int>& ints1, std::vector<int>& ints2, Fun fun)
{
  fun(ints1, ints2);
}

auto main() -> int
{
  auto ints1 = std::vector { 5, 4, 3, 2, 1 };
  auto ints2 = std::vector { 1, 2, 3, 4, 5 };
  do_thing(ints1, ints2, [](auto& a, auto &b) { std::swap(a, b); }); // Compiles, tho requires thinking and typing

  std::cout << ints1[0] << ' ' << ints2[0];
}

Or write a very scary looking generic macro which abstracts that away:

#include <algorithm>
#include <vector>

#include <algorithm>
#include <vector>

#define LIFT_FWD_(...) (static_cast<decltype(__VA_ARGS__)&&>(__VA_ARGS__))
#define LIFT(...) \
  [](auto&&... args) \
    noexcept(noexcept(__VA_ARGS__(LIFT_FWD_(args)...))) \
    -> decltype(__VA_ARGS__(LIFT_FWD_(args)...)) \
    { return __VA_ARGS__(LIFT_FWD_(args)...); }

template <typename Fun>
auto do_thing(std::vector<int>& ints1, std::vector<int>& ints2, Fun fun)
{
  fun(ints1, ints2);
}

auto main() -> int
{
  auto ints1 = std::vector { 5, 4, 3, 2, 1 };
  auto ints2 = std::vector { 1, 2, 3, 4, 5 };
  do_thing(ints1, ints2, LIFT(std::swap)); // Compiles, black boxed magic that just works^tm
}

Explanation of the above macro

The above macro is a lot of magic, yes, but it basically handles everything properly and correctly for us.

First we define LIFT_FWD_ which basically does what std::forward does. If you don't know how it works, follow the above link and read the explanation there.

We define it as a macro, instead of using the function from stdlib directly, because it makes no sense to include the <utility> header for our macro.

The lift macro itself can be broken into four parts:

[](auto&&... args) // just the starting declaration of a lambda, nothing fancy, we are talking a parameter pack of whatever arguments
noexcept(noexcept(__VA_ARGS__(LIFT_FWD_(args)...))) // we are correctly handling the noexcept case - if our function call is noexcept, our lambda is noexcept as well
-> decltype(__VA_ARGS__(LIFT_FWD_(args)...)) // we are taking the return type of our function call and setting it as our lambda return type
{ return __VA_ARGS__(LIFT_FWD_(args)...); } // the body, actual function call

The only confusing part may be __VA_ARGS__, why not just #define LIFT(X) [...] X(LIFT_FWD_(args)...)?

The answer is - this would work, probably even 99% of the cases, but woud disallow passing in a type with explicit template parameters and a space in it, consider:

LIFT(something<int, std::string>)

The space in there would make X only be something<int, so that's just a way to protect against that.

Reasoning

The whole point of niebloids is to make doing the correct thing easy and convenient, without the programmer having to care or remember any rules.

By inhibiting (disallowing) ADL, the behaviour of calling an algorithm is consistent with both qualified and unqualified lookup:

auto const numbers = std::vector{ 1 ,2, 3, 4, 5 };
{
  auto const min = std::ranges::min(numbers); // Calls std::ranges::min
}

{
  using namespace std::ranges;
  auto const min = min(numbers); // Calls std::ranges::min
}

Then, niebloids correctly take care of everything inside. They call Customization Point Objects if neccessary, which take care of correct handling of customization points and all type requirements are correctly applied.