Document number: | N4381=yy-nnnn |
Date: | 2015-03-11 |
Project: | Programming Language C++, Library Working Group |
Reply-to: |
Eric Niebler <eniebler@boost.org>, |
A customization point, as will be discussed in this document, is a function used by the Standard Library that can be overloaded on user-defined types in the user’s namespace and that is found by argument-dependent lookup. The Standard Library already defines several customization points:
swap
begin
end
The first is the most well-known and widely used. It is not obvious that begin
and end
are in fact customization points until one reads the specification of the range-for statement, which mandates that functions begin
and end
are called unqualified. (iter_swap
may also be a customization point depending on how one chooses to read the specification of the reverse
algorithm.) We can expect the number of customization points to grow. For instance, N4014[2] suggests adding size
as a customization point for fetching the size of a range.
The purpose of this paper is to describe some usability problems with the current approach to defining customization points and to suggest a design pattern that can be used when defining future ones.
The correct usage of customization points like swap
is to first bring the standard swap
into scope with a using
declaration, and then to call swap
unqualified:
using std::swap;
swap(a, b);
One problem with this approach is that it is error-prone. It is all too easy to call (qualified) std::swap
in a generic context, which is potentially wrong since it will fail to find any user-defined overloads.
Another potential problem – and one that will likely become bigger with the advent of Concepts Lite – is the inability to centralize constraints-checking. Suppose that a future version of std::begin
requires that its argument model a Range
concept. Adding such a constraint would have no effect on code that uses std::begin
idiomatically:
using std::begin;
begin(a);
If the call to begin
dispatches to a user-defined overload, then the constraint on std::begin
has been bypassed.
This paper aims to rectify these problems by recommending that future customization points be global function objects that do argument dependent lookup internally on the users’ behalf.
This paper recommends no changes to the current working draft. Changing the definition of existing customization points from function templates to global polymorphic function objects is a potentially breaking change. Users are allowed to add specializations of function templates in namespace std
for user-defined types. Such code would be broken by this change.
Rather, this paper proposes merely that any customization points added in the future use the design pattern described below.
The goals of customization point design are as follows (for some hypothetical future customization point cust
):
cust
either qualified as std::cust(a);
or unqualified as using std::cust; cust(a);
should behave identically. In particular, it should find any user-defined overloads in the argument’s associated namespace(s).cust
as using std::cust; cust(a);
should not bypass any constraints defined on std::cust
.This design proposes to make customization points global function objects. Below is what std::begin
would look like if it were redesigned as a function object (something this paper does not advocate).
namespace std {
namespace __detail {
// define begin for arrays
template <class T, size_t N>
constexpr T* begin(T (&a)[N]) noexcept {
return a;
}
// Define begin for containers
// (trailing return type needed for SFINAE)
template <class _RangeLike>
constexpr auto begin(_RangeLike && rng) ->
decltype(forward<_RangeLike>(rng).begin()) {
return forward<_RangeLike>(rng).begin();
}
struct __begin_fn {
template <class R>
constexpr auto operator()(R && rng) const
noexcept(noexcept(begin(forward<R>(rng)))) ->
decltype(begin(forward<R>(rng))) {
return begin(forward<R>(rng));
}
};
}
// To avoid ODR violations:
template <class T>
constexpr T __static_const{};
// std::begin is a global function object
namespace {
constexpr auto const & begin =
__static_const<__detail::__begin_fn>;
}
}
There are some notable things about this solution. As promised, std::begin
is a function object, the type of which is std::__detail::__begin_fn
. Also in the std::__detail
namespace are the familiar begin
free functions which presently live in namespace std
. The function call operator of __begin_fn
makes an unqualified call to begin
which, since it shares the __detail
namespace with the begin
free functions, will consider those in addition to any overloads that are found by argument-dependent lookup. The strange __static_const
template will be described later.
From a behavioral perspective, there are two cases to consider: calling std::begin
qualified and calling it unqualified.
It is clear that code that calls std::begin
qualified will get the desired behavior. The call routes to __begin_fn::operator()
, which makes an unqualified call to begin
, thereby finding any user-defined overloads.
In the case that begin
is called unqualified after bringing std::begin
into scope, the situation is different. In the first phase of lookup, the name begin
will resolve to the global object std::begin
. Since lookup has found an object and not a function, the second phase of lookup is not performed. In other words, if std::begin
is an object, then using std::begin; begin(a);
is equivalent to std::begin(a);
which, as we’ve already seen, does argument-dependent lookup on the users’ behalf.
Since calls route through the global function object whether calls are made qualified or unqualified, we are sure to get the benefit of any constraints checking done there.
Given the above defintion of std::begin
the following program was compiled with GCC 4.9.2 both with and without the USE_CUSTPOINT define (after switching __static_const
from a variable template to a class template with a static constexpr data member to get it to compile).
int main() {
int rgi[] = {1,2,3,4};
#ifdef USE_CUSTPOINT
// Go through the customization point
int * p = std::begin(rgi);
#else
// Call the free functions directly
using namespace std::__detail;
int * p = begin(rgi);
#endif
std::printf("%p\n",(void*)p);
}
The resulting optimized (-O3) assembly listings were exactly identical:
Global object | Free function |
|
|
This makes sense. Although the use of a global reference to a function object would appear to introduce an indirection to every call of the customization point, the body of __begin_fn::operator()
is available in every translation unit and does not refer to the implicit this
parameter. Therefore, compilers should have no difficulty eliding the parameter, removing the indirection, and inlining the call.
The example code above uses a strange __static_const
variable template to avoid ODR violations. The need for it is illustrated by simpler code like below:
// <iterator>
namespace std {
// ... define __detail::__begin_fn as before...
constexpr __detail::_begin_fn {};
}
// header.h
#include <iterator>
template <class RangeLike>
void foo( RangeLike & rng ) {
auto * pbegin = &std::begin; // ODR violation here
auto it = (*pbegin)(rng);
}
// file1.cpp
#include "header.h"
void fun() {
int rgi[] = {1,2,3,4};
foo(rgi); // INSTANTIATION 1
}
// file2.cpp
#include "header.h"
int main() {
int rgi[] = {1,2,3,4};
foo(rgi); // INSTANTIATION 2
}
The code above demonstrates the potential for ODR violations if the global std::begin
function object is defined naïvely. Both functions fun
in file1.cpp and main
in file2.cpp cause the implicit instantiation foo<int[4]>
. Since global const
objects have internal linkage, both translation units file1.cpp and file2.cpp see separate std::begin
objects, and the two foo
instantiations will see different addresses for the std::begin
object. That is an ODR violation.
In contrast, variable templates are required to have external linkage ([temp]/4). Customization points can take advantage of that to avoid the ODR problem, as below:
namespace std {
template <class T>
constexpr T __static_const{};
namespace {
constexpr auto const& begin =
__static_const<__detail::__begin_fn>;
}
}
Because of the external linkage of variable templates, every translation unit will see the same address for __static_const<__detail::__begin_fn>
. Since std::begin
is a reference to the variable template, it too will have the same address in all translation units.
The anonymous namespace is needed to keep the std::begin
reference itself from being multiply defined. This is from a private communicaiton with James Widman:
A constexpr reference declared at namespace scope is a variable; but
IIUC it has external linkage unless it is placed inside an unnamed
namespace.For objects (not references): a constexpr object implicitly has a
const-qualified type, and the added const qualification at namespace
scope means that a constexpr object implicitly has internal linkage.For references: a constexpr reference has no implicitly-added
const-qualification on its type. Even if it did, there is nothing in
the linkage rules that would implicitly give references internal
linkage.So, it turns out that a constexpr reference at namespace scope would
have external linkage by default; so you still want the unnamed
namespace.
The author can imagine a reading of [basic.def.odr]/6 that makes the use of std::begin
from multiple translation units an ODR violation. The relevant part of [basic.def.odr]/6.2 is as follows:
[…] in each definition of D, corresponding names, looked up according to 3.4, shall refer to an entity defined within the definition of D, or shall refer to the same entity, after overload resolution (13.3) and after matching of partial template specialization (14.8.3), except that a name can refer to a non-volatile const object with internal or no linkage if the object has the same literal type in all definitions of D, and the object is initialized with a constant expression (5.19), and the object is not odr-used, and the object has the same value in all definitions of D
The question then comes down to whether the reference std::begin
is an entity (which, according to [basic]/3, it is), whether the reference is odr-used in, e.g., inline functions (this is unclear to the author), and what “refer to” means in this context. Does the name std::begin
refer to the reference with internal linkage, or to the object referenced with external linkage?
This question was put to core, and the consensus seems to be that this is a defect – or at least that this use case can be supported by a relaxation of [basic.def.odr]/6.2 to “look through” constexpr references (see Mike Miller in c++std-core-27326).
Whether this solution conforms to the letter of the standard as it’s written today, from a purely practical standpoint, it seems patently impossible that the distinction could have any significance to real-world code. It is impossible to get the “address” of a reference entity (as opposed to the address of the object it references), so any template or inline function that uses the std::begin
function object is guaranteed to generate identical code in all translation units. And the suggested fix to the ODR specification means this design is likely to conform to the letter of some future version of the standard.
If you refer back to the assembly listing for the simple program that uses the std::begin
function object, you will notice the lack of any storage for the global objects std::begin
or __static_const<__detail::__begin_fn>
. The optimizer has removed them. Unoptimized code does have these global objects, but the number of customization points in the STL is so small that their presence in unoptimized object files is not expected to amount to any significant bloat.
End users who wish to “hook” the customization point simply provide the appropriately named overload in their namespace, as they always have.
namespace My {
struct S {
};
int *begin(S &);
}
Since the global function object performs ADL internally, the overload in the My
namespace gets found.
int main() {
My::S s;
int *p = std::begin(s); // this calls My::begin
}
As shown, the customization point is hooked by defining a free function of the same name as the global function object. That works well for types in other namespaces but for types that are in std
themselves, attempting to define such a free function would lead to an error. So the recommendation for types in std
is different. Such types can hook the customization point by defining a friend function, as below:
namespace std {
template <class T>
class vector {
public:
// ...
friend T * begin(vector & v) {
// ...
}
};
}
(In this case, of course, the friend function is unnecessary since the default begin
function automatically works for vectors by calling vector’s begin
member function.) Friend functions works for class types. For enums in namespace std
that must hook customization points – if any such exist – the recommendation is somewhat less elegant. The enum and the overload must be defined in a hidden namespace, and then the enum is pulled into namespace std
with a using
declaration, as shown below.
namespace std {
namespace {
// If hash were a customization point...
constexpr auto const & hash =
__static_const<__detail::__hash_fn>;
}
namespace __hidden {
enum memory_order {
// ...
};
// If memory_order needed to hook hash...
size_t hash(memory_order) {
// ...
}
}
using __hidden::memory_order;
}
Although ugly this would work, and it would only be needed should an enum in namespace std ever need to hook a customization point, which seems unlikely.
The author is aware of a few relatively minor drawbacks to the approach described here. The first is added complexity of implementing and specifying customization points. That could be alleviated by centrally defining customization point as a term of art in the standard – describing the properties of customization points instead of the implementation details – and then saying which APIs are customization points.
Another drawback is the added complexity from the perspective of end users. Although this design doesn’t change how people hook the customization point[*] or necessitate changes in how they are called, it will require users to understand what’s going on when things break. It also may not be obvious that a qualified call to a function std::foo
will find a foo
function in another namespace. This is somewhat mitigated by the fact that users can continue doing using std::foo; foo(a);
as they have been told to do for years.
This design may also negatively impact compiler error messages when the customization point is misused. Since the call redirects though an intermediate function object, there will necessary be more noise in the compiler backtrace. This problem is likely to go away with Concepts Lite.
Unoptimized builds will get somewhat slower and larger with this change, but it’s unlikely to be enough to be noticed.
There would also necessarily be some inconsistency in the standard if we accepted this new design for future customization points but left the existing ones alone. That hardly seems a reason to the author to continue doing things in a sub-standard way if the committee decides that the new approach is better. An alternate approach that would not introduce inconsistency would be to adopt the new design for any future TS to redesign the STL as has been discussed in the context of Concepts Lite[5] and Ranges[3].
A more concerning issues comes from James Widman, who points out that defining customization points as objects can introduce ambiguity errors where none would otherwise occur. See the example below:
#include <iterator> // for std::begin function object
// begin user's code:
struct X{};
void begin(X);
using namespace std;
void g() {
begin(X()); // error: ambiguous name lookup result: '::begin'
// (function) and 'std::begin' (reference-to-object)
}
The ambiguity occurs when the user:
std
namespace with a using directive.In that case, lookup will find both the function and the object and error out. This is cause for legitimate concern. The mitigating factors are:
Whether these mitigating factors are enough is left for the committee to decide.
[*] This design does not permit users to hook customization points by specializing function templates in namespace std
. If users are accustomed to doing that, they will need to learn new behavior. But in the opinion of the author, they should anyway.
The customization point design recommended here has been used for the past year in the Range-v3[4] library, where all functions are implemented as global function object, not just the customization points. The library is popular judging from the number of people who have registered for notifications, cloned it, and submitted issues and pull requests. There have thus far been no negative comments from users about the use of global function objects or about the customization point design.
Admittedly, this experience is limited.
One alternative is to not change anything. The approach to customization point design that the current standard takes – namely, just making them free functions and requiring using
declarations to call them – has served the community with some degree of success since the beginning. The drawbacks of this approach have already been described.
Another approach is to replace the function object described here with a free function that dispatches to a differently named function. For instance, a std::begin
free function could make an unqualified call to a free function named std_begin
, as below:
namespace std {
// define begin for arrays
template <class T, size_t N>
constexpr T* std_begin(T (&a)[N]) noexcept {
return a;
}
// Define begin for containers
// (trailing return type needed for SFINAE)
template <class _RangeLike>
constexpr auto std_begin(_RangeLike && rng) ->
decltype(forward<_RangeLike>(rng).begin()) {
return forward<_RangeLike>(rng).begin();
}
template <class R>
constexpr auto begin(R && rng) ->
decltype(std_begin(forward<R>(rng))) {
return std_begin(forward<R>(rng));
}
}
Users hook customization points like this by overloaded std_begin
in their namespace. They call std::begin
qualified. This design is certainly more straightforward than the design presented here. It is used in Boost.Range[1], where boost::begin
makes an unqualified call to a range_begin
function that users can overload.
The problems with this approach are:
using
declaration wrong. With this approach, ADL shouldn’t be happening on the name “begin
” – it should happen only on the name “std_begin
”.begin
or std_begin
? Or do they specialize begin
in namespace std
? All will work to one degree or another, but only one is “correct”.Finally, a third approach would be to add a new language feature for customization points that would achieve the desired goals without the drawbacks. This solution has not yet been pursued. The author hopes that a pure library solution is good enough.
The author would like to thank James Widman for reviewing an early version of this paper, offering feedback and explaining the intricacies of lookup and the ODR as they relate to this proposal.
[1]Boost.Range Library: http://boost.org/libs/range. Accessed: 2014-10-08.
[2]Marcangelo, R. 2014. N4017: Non-member size() and more.
[3]Niebler, E. et al. 2014. N4128: Ranges for the Standard Library, Revision 1.
[4]Range v3: https://github.com/ericniebler/range-v3. Accessed: 2014-10-08.
[5]2015. N4377: Programming Languages — C++ Extensions for Concepts.