When you have a default implementation for some function and want to let users provide their own version for custom types, you have to do something like this:
#include <cstdio>
namespace Lib {
void foo([[maybe_unused]] auto x) { std::puts("global generic version"); }
} // namespace Lib
// user namespace
namespace X {
struct Int {
int val;
};
void foo([[maybe_unused]] Int x) { std::puts("local Int version"); }
} // namespace X
// some generic function that has to use correct version of foo
void use_foo(auto x) {
using Lib::foo; // not to be forgotten
foo(x);
}
int main() {
use_foo(42);
use_foo(X::Int{32});
}
Output
global generic version
local Int version
Though very simple, it's easy to forget the using Lib::foo
required to make the default version available if no better match can be found by ADL.
Looking at Name Lookup and Overload Resolution in C++ - Mateusz Pusz (slide 45; ~51'), I saw how the std::ranges
implementation provides a way to have such customization points for many standard algorithms, using the technics of niebloids and not requiring extra using
declaration.
The proposed implementation relies partially on using function objects instead of plain functions.
Instead of the std::range
implementation here is a neutral implementation:
// provides customizable foo
namespace N {
namespace Details {
void foo(); // makes following requires well-formed and hides possible
// enclosing scope versions
// to tell if a specialization exists, using ADL
template <typename T>
inline constexpr bool has_foo = requires(T& t) { foo(t); };
// functor
struct fn {
void operator()(auto x) const {
if constexpr (has_foo<decltype(x)>) {
foo(x); // dependant name, using ADL to get foo from argument scope
} else {
Lib::foo(x); // non-ADL, gets the global scope one or any default
// implementation
}
}
};
} // namespace Details
inline constexpr Details::fn foo;
} // namespace N
Then usage can be simplified:
// some generic function that has to use correct version of foo
void use_foo(auto x) { N::foo(x); }
int main() {
use_foo(42);
use_foo(X::Int{32});
}
Which gives the same output.
What I understand from this is that calling N::foo
will detect void foo();
from simple name-lookup, at the definition point, which will hide any other foo
function in any enclosing scope, but ADL, from instantiation point will make has_foo
true if a specialization exists in the namespace of the argument. If such specialization exists, it is called, otherwise, the generic version is called through, this time, qualified name-lookup, into the global namespace.
Yet I don't see how using a functor is necessary in the analysis.
For instance, in this page about niebloids, using functor is presented as a requirement to inhibit ADL, but I don't understand where it is needed. Niebloids there (and in Pusz's presentation) are presented as the only way to get correctly customization points (without having to add a using ::foo;
statement to inject global version into the scope of the calling site).
Implementing the same functionality with a simple function seems to give the same output:
// provides customizable foo
namespace N {
void foo(); // makes following requires well-formed and hides possible
// enclosing scope versions
// to tell if a specialization exists, using ADL
template <typename T>
inline constexpr bool has_foo = requires(T& t) { foo(t); };
// simple function
void foo(auto x) {
if constexpr (has_foo<decltype(x)>) {
foo(x); // dependant name, using ADL to get foo from argument scope
} else {
Lib::foo(x); // non-ADL, gets the global scope one or any default
// implementation
}
}
} // namespace N
To trigger a difference I have to change use_foo
to:
void use_foo(auto x) {
using namespace N;
foo(x);
}
Functor version and Function version.
In the function case, I see that use_foo(X::Int{32})
triggers ADL on foo
call site, leading to direct call of X::foo
, though with the functor version, no ADL is performed at the call site and I go through the functor to have the correct dispatch. Yet in the end, the expected version is called in both cases.
In comments, https://brevzin.github.io/c++/2020/12/19/cpo-niebloid/#niebloids-solve-undesired-adl has been proposed to illustrate a situation were it can breaks, but I cannot reproduce it with my simple example.
What could be the difference between the functor and function versions and how can it be illustrated?
I eventually found at least two issues with the function solution:
namespace N
for a type declared in namespace Lib
To illustrate that, I managed to derive a mre from https://brevzin.github.io/c++/2020/12/19/cpo-niebloid/#niebloids-solve-undesired-adl:
#include <cstdio>
namespace Lib {
// some default implementation (a)
template <typename T>
void foo(T const&, T const&) {
std::puts("global generic version");
}
template <typename T>
struct Wrap {
T val;
};
} // namespace Lib
// provides customizable foo
namespace N {
struct S {};
void foo(); // makes following requires well-formed and hides possible
// enclosing scope versions (b)
// an overload in N for 2 Lib::Wrap types (c)
template <typename T, typename U>
void foo(Lib::Wrap<T> const&, Lib::Wrap<U> const&) {
std::puts("N Wrap version");
}
// to tell if a specialization exists, using ADL
template <typename T, typename U>
inline constexpr bool has_foo = requires(T& t, U& u) { foo(t, u); };
// overload catching all kind of arguments and dispatching between
// customizations or default implementation (d)
void foo(auto x, auto y) {
if constexpr (has_foo<decltype(x), decltype(y)>) {
std::puts("Functor dispatch with ADL");
// NOTE => if x or y are of a user-defined type, declared inside N, void
// foo(auto x, auto y) will be detected again, triggering infinite
// recursion in this example
// (detected by gcc -Winfinite-recursion, warning C4717 in msvc, but not
// detected by clang)
foo(x, y); // dependent name, usual
// name lookup will find void foo() then using ADL to get foo from
// argument scope dependant name: usual name lookup at definition and
// ADL at instantiation or both at both?
} else {
std::puts("Functor dispatch without ADL");
Lib::foo(x, y); // qualified name lo lookup => no ADL, gets the global
// scope one or any default implementation
}
}
} // namespace N
// user namespace
namespace X {
struct Int {
int val;
};
// user provided overload in user namespace (e)
void foo(Int const&, Int const&) { std::puts("User Int version"); }
} // namespace X
// some generic function that has to use correct version of foo
void use_foo(auto x, auto y) {
using namespace N;
foo(x, y); // dependent name
}
int main() {
use_foo(42, 24); // (d) is selected, at definition point nothing found by
// usual nl nor adl, idem at instantiation point
// (f)
// use_foo(N::S{},
// N::S{}); // triggers infinite recursive detection in (d) as
// has_foo
// // detects void foo(auto x, auto y) through ADL
use_foo(X::Int{32},
X::Int{23}); // (d) and (e) are possible, (e) better match
// (h)
// use_foo(Lib::Wrap{32}, Lib::Wrap{23}); // (d) and (a) are possible,
// equal match => ambiguous
}
The simplest issue (infinite recursion) occurs at // (f)
. Here, as in other examples, foo(x,y)
being a dependent name, lookup is deferred until instantiation where usual lookup finds void foo()
at (b)
and void foo(auto x,auto y)
at (d)
(because of the namespace injection by using namespace N
).
ADL does not find any other match.
Thus void foo(auto x,auto y)
is selected and, inside it, the bool has_foo
, being also a dependent name, is checked at instantiation point. foo(t,u)
can be matched by void foo()
(usual name lookup) and void foo(auto x,auto y)
(ADL) this time. The second overload is the unique viable one and has_foo
is set to true.
Thus void foo(auto x,auto y)
calls foo(x,y)
which resolves again to void foo(auto x,auto y)
, with the same reasoning. This is an infinite recursion.
The second issue is more tricky and occurs at // (g)
because in namespace N
we have an overload for arguments of types that are defined inside namespace Lib
.
Usual lookup finds void foo()
, void foo(Lib::Wrap<T> const&, Lib::Wrap<U> const&)
at (c)
and void foo(auto x,auto y)
.
But ADL finds also void foo(T const&, T const&)
at (a)
.
Now (a)
and (c)
are equally better matches, the call is ambiguous.
The functor version solves both issues:
// provides customizable foo
namespace N {
struct S {};
namespace Details {
void foo(); // makes following requires well-formed and hides possible
// enclosing scope versions (b)
template <typename T, typename U>
inline constexpr bool has_foo = requires(T& t, U& u) { foo(t, u); };
// functor
struct fn {
// operator() in N for 2 Lib::Wrap types (c)
template <typename T, typename U>
void operator()(Lib::Wrap<T> const&, Lib::Wrap<U> const&) const {
std::puts("N Wrap version");
}
// operator() catching all kind of arguments and dispatching between
// customizations or default implementation (d)
void operator()(auto x, auto y) const {
if constexpr (has_foo<decltype(x), decltype(y)>) {
std::puts("Functor dispatch with ADL");
foo(x,
y); // dependant name, using ADL to get foo from argument scope
} else {
std::puts("Functor dispatch without ADL");
Lib::foo(x, y); // non-ADL, gets the global scope one or any
// default implementation
}
}
};
} // namespace Details
inline constexpr Details::fn foo;
} // namespace N
This time (d)
is not an overload of foo
anymore. The different calls in use_foo
are finding only Details::fn foo
by usual lookup. This is an object, not a function, thus ADL is not triggered at this point.
Then we have to select between two overloads of operator()
.
For use_foo(N::S{}, N::S{});
the second one is the best match. has_foo
finds only void foo();
function by usual name lookup and then uses ADL which does not find anything else. has_foo
is false, thus the default implementation (a)
is called: this might not be the expected behavior but it does not trigger infinite recursion.
For use_foo(Lib::Wrap{32}, Lib::Wrap{23});
this time the first operator() is the best match and it makes no over call to any foo
thus there is no ambiguity anymore.
NB: in order to have the correct resolution for use_foo(N::S{}, N::S{});
, in both cases, is to add an explicit overload in namespace N
:
Function version
// (h)
void foo(S const&, S const&) { std::puts("S version"); }
Functor version
// (h)
void operator()(S const&, S const&) const {
std::puts("S version");
}
As a final comment: the functor/niebloid approach is factually better than the function one. Yet the problem it solves largely arises due to the namespace injection through using namespace N
. Without it and making only a qualified call N::foo
, if possible, both solutions are much closer.