| Author: | David Abrahams, Doug Gregor |
|---|---|
| Contact: | dave@boostpro.com, doug.gregor@gmail.com |
| Organization: | BoostPro Computing, Apple |
| Date: | 2008-12-05 |
| Number: | n2812=08-0322 |
index
This paper describes a safety problem with rvalue references that can cause unintentional modification of lvalues. The underlying issue has been known for some time, but recently-discovered examples have made its seriousness much more apparent. We also propose a solution to the problem, which has been implemented in the GNU C++ compiler.
The example that made this safety problem with rvalue references critical involves both rvalue references and concepts. The simplest example is the conceptualized version of the push_back functions in, e.g., std::list:
requires CopyConstructible<value_type> void push_back(const value_type& a); // #1: copies a requires MoveConstructible<value_type> void push_back(value_type&& a); // #2: moves from a
Recall that it's okay for #2 to modify its argument (by moving its resources into the list) because changes to rvalues can't be observed by other code. The safety problem here is that, if std::list is instantiated with a movable but non-copyable type like std::unique_ptr<int>, one can silently move from lvalues. For example:
void push_back2(
std::list<std::unique_ptr<int>>& l, std::unique_ptr<int> a)
{
l.push_back(a); // oops: moves from the lvalue 'a', silently!
l.push_back(a); // oops: 'a' no longer has its original value
}
The operation “move a value from x” is always safe when x is an unnamed temporary. Rvalue references were designed so that users must explicitly write std::move(x) otherwise. However, the example above illustrates that the intended safety mechanism can disappear without an explicit std::move.
What happened? When std::list is instantiated, the compiler eliminates any declarations whose concept requirements cannot be satisfied. Since std::unique_ptr<int> does not satisfy CopyConstructible as required by #1, the only push_back function that exists in std::list<std::unique_ptr<int>> is:
void push_back(std::unique_ptr<int>&& a); // #2: moves from a
The call l.push_back(x) succeeds because rvalue references bind liberally to lvalues. Then, push_back treats the lvalue as if it were an rvalue, silently moving from it and destroying the value of x.
Note that without concept requirements, two push_back overloads are always available:
void push_back(const X& a); // #1: copies a void push_back(X&& a); // #2: moves from a
With both overloads in play, the lvalue reference in #1 is a better match for lvalue arguments than the rvalue reference in #2. Instantiation of #1 finally fails only when it attempts to copy its argument.
To understand how we ended up silently moving from lvalues, let's review the canonical implementation of move semantics. In C++03, std::list only provides a single push_back operation:
void push_back(const value_type& x); // #1
This operation copies the value x into the list. If the value provided for x is actually a temporary value that is expensive to copy (say, a large string or a container of strings), copying x is wasted effort: we're making an expensive copy of something that will be destroyed anyway.
That's where move semantics come in. The idea is to transfer ownership of x's contents into the list instead of allocating new memory and making a copy. We can do that when the argument is a temporary, e.g.,
std::list<std::string> l;
l.push_back(string("temporary"));
because the string is an unnamed temporary and thus inaccessible and invisible to the rest of the program. If we steal from an rvalue, nobody can know the difference: that's the key to move semantics.
To add move semantics, we add a push_back overload version that takes its second parameter by rvalue reference:
void push_back(value_type&& x); // #2
This idiom relies on the presence of both overloads. Overload #2 makes it move, but overload #1 makes it safe by attracting lvalues. Without overload #1, push_back will move from lvalues, silently turning a logically non-mutating operation into a mutating one.
A movable-but-noncopyable value_type follows the same binding pattern as any other value_type: rvalue arguments, which can be safely moved from, always select overload #2:
std::list<std::unique_ptr<int>> l; l.push_back(std::unique_ptr<int>(new int));
As before, lvalue arguments select overload #1:
void f(std::list<std::unique_ptr<int>> l, std::unique_ptr<int> p) {
l.push_back(p); // calls #1
}
However, since the argument type is noncopyable, the body of #1 fails compilation (as desired) when it attempts to make a copy of the unique_ptr.
The problem with the formulation of the move/copy idiom is that the lvalue/rvalue overload set doesn't degrade safely. If overload #1 is removed from consideration, overload #2 will match both rvalues and lvalues, moving silently from all mutable arguments.
There are a number of possible reasons for such a removal, but simple programmer blunders may be the most likely causes. For example, an errant finger might hit the delete key when overload #1 is selected. Some mistakes are not nearly so obvious, because overloads can be removed due to template argument deduction failure (SFINAE) [1] or because certain concept requirements are not satisfied.
For example, consider an "enqueue" function that either copies or moves the elements from a source queue into a destination queue, using the typical copy/move idiom:
template <class T, typename Cont> void enqueue(queue<T, Cont>& dest, const queue<T, Cont>& src) // #3a template <class T, typename Cont> void enqueue(queue<T, Cont>& dest, queue<T, Cont>&& src); // #4
Now, in the case where we're copying from one queue to another, it might make sense to provide an optional allocator, so we replace #3a with:
template <class T, typename Cont> void enqueue( queue<T, Cont>& dest, const queue<T, Cont>& src, typename Cont::allocator_type alloc = typename Cont::allocator_type()); // #3b
This overload set will move from rvalues and copy from lvalues in most common cases, e.g.,
queue<string, list<string>> dest; queue<string, list<string>> src; enqueue(dest, src); // okay, calls #3b to copy from src into dest enqueue(dest, queue<string, list<string>>()); // okay, calls #4 to move from src to dest
However, not all container types Cont have allocators, and we can run into trouble again:
class simple_list {
// ... no allocator_type ...
};
queue<string, simple_list<string>> dest;
queue<string, simple_list<string>> src;
enqueue(dest, src); // oops: calls #4, silently moving from the lvalue 'src'
What happened here is similar to what happened with the conceptualized verison of push_back, but this time concepts are not involved. In this case, template argument deduction for the call to #3b deduces T=string and Cont=simple_list<string>. Then, while substituting those deduced template arguments into the signature of #3b, we attempt to look up the type simple_list<string>::allocator_type, which does not exist. This is a SFINAE case, so #3b is removed from consideration and the overload set only contains #4. The rvalue reference parameter of #4 binds to the lvalue src, and we silently move from an lvalue.
Fundamentally, the problem we've described occurs because the rvalue reference binding rules violate an important principle of type safety:
Principle of Type-safe Overloading (PTO)
Every function must be type-safe in isolation, without regard to how it has been overloaded.
This violation of principle manifests itself in several ways:
From an author's point-of-view, we have been forced add a new overload to remove unwanted behavior.
From a client's point-of-view, under the current rules, a function that accepts an rvalue reference does not crisply state its contract in the type system:
void f(X&&);
From looking at f, is not clear whether it is
The contract can be expressed as documentation, but to put it in code may require the addition of a second f overload, e.g.,
void f(value_type const&) = delete;
to ban the use of lvalues. Taken to its logical extreme, a client may need to see all the code in the translation unit in order to know whether this function is capable of mutating its argument. There is no precedent in const-correct code for such a dispersal of semantic information, or for a non-mutating call to become mutating when an overload is removed from the set.
So why is this happening now? Before we had rvalue references, it was easy to adhere to the PTO without giving it any special attention. Move semantics, however, introduce a special case: we need to modify an rvalue argument as part of a logically non-mutating operation. This paradox is only possible because of a special property of rvalues: that they can be modified with assurance that the modification can't be observed.
We propose to prohibit rvalue references from binding to lvalues. Therefore, an rvalue reference will always refer to an rvalue or to an lvalue that the user has explicitly transformed into an rvalue (e.g., through the use of std::move). This makes the overload sets used in the copy/move idiom degrade safely when either of the overloads is removed for any reason. For example, with this change, given just a single function template enqueue:
template <class T, typename Cont> void enqueue(queue<T, Cont>& dest, queue<T, Cont>&& src); // #4
calling enqueue with an rvalue succeeds while calling it with an lvalue fails:
queue<string, list<string>> dest; queue<string, list<string>> src; enqueue(dest, src); // error: cannot bind rvalue reference in #4 to lvalue 'src' enqueue(dest, queue<string, list<string>>()); // okay, calls #4 to move from temporary to dest
We can then add back the previously-problematic overload that allows one to copy from the source queue while enqueing its elements, and provide an allocator:
template <class T, typename Cont>
void enqueue(queue<T, Cont>& dest, const queue<T, Cont>& src,
typename Cont::allocator_type alloc = typename Cont::allocator_type()); // #3b
Now, if we attempt to enqueue elements from an lvalue where the queue's container does not have an allocator, we receive an error message stating that no enqueue function can be called, rather than silently moving from lvalue:
queue<string, simple_list<string>> dest;
queue<string, simple_list<string>> src;
enqueue(dest, src); // error: #3b fails template argument deduction
// #4 cannot be called because src isn't an lvalue
Our proposed solution retains the behavior of the copy/move idiom while still adhering to the principle of type-safe overloading and eliminating the safety hole that allowed silently moves from lvalues.
The most important aspect of this solution is that it does not change the common idioms that employ rvalue references. For example, when we want to optimize for rvalues (e.g., by implementing move semantics), we still implement two overloads: one with an lvalue reference to const and one with an rvalue reference, e.g.,:
void push_back(const value_type& x); // copies x void push_back(value_type&& x); // moves x
With the proposed change, the introduction of concepts into these functions does not result in any surprises:
requires CopyConstructible<value_type> void push_back(const value_type& x); // copies x requires MoveConstructible<value_type> void push_back(value_type&& x); // moves x
For a move-only type X, the first push_back will be eliminated because template argument deduction fails (X does not meet the CopyConstructible requirements), and the second push_back only accepts rvalues. Hence, calling push_back with an lvalue of move-only type X will result in an error.
The proposed change also does not have any impact on the use of rvalue references for perfect forwarding, e.g.,:
template <class F, class T>
void thunk(F f, T&& x) { f(std::forward<T>(x)); }
When an lvalue of type U is passed to f, the special template argument deduction rules for T&& ensure that T is deduced as U&. Then, when substituting T=U& into T&&, reference collapsing transforms the resulting argument type to U&, an lvalue reference that is able to bind to the lvalue argument of type U. Hence, lvalues bind to lvalue references and rvalues bind to rvalue references.
The only user code that will be directly affected by the proposed change is when a function performs the same operation regardless of whether it receives an lvalue or an rvalue. For example, this approach has been used with member swap to permit swapping with rvalues, e.g.,:
struct mytype {
void swap(mytype&& other); // other can be an lvalue or rvalue
};
void f(mytype& m1, mytype& m2) {
m.swap(mytype()); // okay: rvalue reference binds to rvalues
m1.swap(m2); // okay under the existing rules, ill-formed with the proposed rules
}
With the proposed change, the definition of mytype would have to be extended to include two swap overloads, one for lvalues and one for rvalues. The rvalue-reference version would merely forward to the lvalue-reference version, e.g.,:
struct mytype {
void swap(mytype& other);
void swap(mytype&& other) { swap(other); } // 'other' is treated as an lvalue
};
Since the vast majority of uses of rvalue references fall into one of the first two idioms---paired overloads for move semantics and the use of std::forward for perfect forwarding---and the workaround for the few functions like swap that depend on the current behavior is very simple, we do not expect any significant impact on user code. On the other hand, the proposed change eliminates a particularly vexing problem with rvalue references that makes them almost unusable with concepts and somewhat dangerous even without concepts.
The change in the binding of rvalue references affects the standard library in four different areas: the definitions of std::move and std::forward, the definition of member swap, the formulation of the stream insertion/extraction operators, and the description of the Iterator concept.
Both std::move and std::forward rely on the ability of an rvalue reference to bind to an lvalue. For std::move, this binding is used to return the argument x (which is always treated as an lvalue) from the function:
template<typename T>
inline typename std::remove_reference<T>::type&& move(T&& x)
{ return x; }
With our proposed change, a new formulation of std::move is required. It explicitly casts the lvalue to an rvalue reference type (making it an rvalue), which can bind to the rvalue-reference result type:
template<typename T>
inline typename std::remove_reference<T>::type&& move(T&& x)
{ return static_cast<typename std::remove_reference<T>::type&&>(x); }
std::forward relies on the binding of lvalues to rvalue references in its argument type, since it is typically invoked with lvalues:
template<typename T>
inline T&& forward(typename std::identity<T>::type&& x)
{ return x; }
With our proposed change to the binding rules for rvalue references, we need make two changes. First, we add a second, lvalue-reference overload of std::forward (that forwards lvalues as lvalues):
template<typename T>
inline T& forward(typename std::identity<T>::type& x)
{ return x; }
Second, we need to make sure that the two definitions of std::forward never produce identical function types, by banning the original std::forward from being instantiated with lvalue references:
template<typename T>
inline typename disable_if<is_lvalue_reference<T>, T&&>::type
forward(typename std::identity<T>::type&& x)
{ return static_cast<T&&>(x); }
Note that, with these changes to both std::move and std::forward, the idiomatic uses of these functions still work, so that user code will not need to change. Only the definitions of std::move and std::forward are affected.
Each of the member swap functions in the standard library is described in terms of rvalue references, e.g.,:
void swap(vector<T,Alloc>&&);
With our proposed change, these swap functions will no longer accept lvalues, which would break a significant amount of code. Therefore, we will need to introduce overloads of the member swap functions that accept lvalues:
void swap(vector<T,Alloc>&);
In fact, due to library issue 884, it is possible that we will want to eliminate the rvalue-reference versions of member swap entirely.
With the introduction of rvalue references into the standard library, the stream insertion and extraction operators were changed to accept both lvalue and rvalue streams, e.g.,:
template<class charT, class traits, class Allocator> basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>&& os, const basic_string<charT,traits,Allocator>& str);
This change made it possible to create a temporary stream and use it within one expression, e.g.,:
std::ofstream("out.txt") << "Hello!"; // ill-formed in C++03, okay in C++0x
With our proposed change to rvalue references, each of the stream insertion and extraction operators will need to use an lvalue reference to their stream argument to bind to lvalue streams, effectively reverting streams to their C++03 behavior:
template<class charT, class traits, class Allocator> basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>& os, const basic_string<charT,traits,Allocator>& str);
If we determine that the use case above for temporary streams is important, we could extend the library with the following two function templates:
template<typename _CharT, typename _Traits, typename _Tp>
inline basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>&& __stream, const _Tp& __x)
{
__stream << __x;
return __stream;
}
// Input via an rvalue stream
template<typename _CharT, typename _Traits, typename _Tp>
inline basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>&& __stream, _Tp& __x)
{
__stream >> __x;
return __stream;
}
These templates allow stream insertion and extraction with an rvalue stream, forwarding the stream as an lvalue to use whatever stream insertion/extraction operator already exists. Thus, we still support the use of rvalue streams throughout the library, and use cases like the following will work in C++0x:
std::ofstream("out.txt") << "Hello!"; // okay: uses rvalue-stream template above
Finally, the current definition of the Iterator concept has a dereference operator that uses rvalue references to accept both lvalue and rvalue iterators:
reference operator*(Iter&&);
We will need to augment the Iterator concept with a second overload of operator*:
reference operator*(Iter&);
Note that we use a non-const lvalue reference for this overload, because it is common with output iterators to deference non-const iterator lvalues (and the dereference operators often return non-const references to the same type).
Overall, despite the fact that our proposed change to the binding of rvalue references will affect several different parts of the library, we are able to maintain the same user experience through the introduction of additional overloads and a different implementation of std::move/std::forward. Thus, our proposed change improves the safety of the library and of user code while maintaining backward compatibility with C++03 and with the new features added into C++0x.
We have produced an implementation of the proposed solution in the GNU C++ compiler, which is available as a patch against GCC 4.3.2. The actual implementation of the language change is trivial---we merely check whether the binding computed would bind an lvalue to an rvalue reference, and reject the binding in this case. The changes to the standard library are slightly more involved, because we needed to implement the changes described in the section Impact on the Standard Library. We do not anticipate that this change will have any significant impact on compilers or standard library implementations. The GCC implementation required a day's effort to update both the language and the library, although more effort would certainly be required to update the test cases associated with this feature.
Two alternatives to our proposed solution have been proposed. One alternative is actually an extension to the proposed solution, which adds a third kind of reference type; the other modifies the behavior of concepts to preserve more of the overloading behavior of unconstrained templates. Although we describe these two alternatives here, we do not propose either of them.
With the removal of the binding from rvalue references to lvalues, certain functions that work equally well on both lvalues and rvalues---such as swap or the stream insertion/extraction operators---will need to provide additional overloads, e.g.,:
void swap(mytype&&);
becomes:
void swap(mytype&);
void swap(mytype&& other) { swap(other); }
If there were multiple parameters that could be either lvalues or rvalues, the number of required overloads would grow exponentially. For example, a non-member swap that supports all combinations of lvalues and rvalues would go from:
void swap(mytype&&, mytype&&);
to:
void swap(mytype&, mytype&);
void swap(mytype& x, mytype&& y) { swap(x, y); }
void swap(mytype&& x, mytype& y) { swap(x, y); }
void swap(mytype&& x, mytype&& y) { swap(x, y); }
At this point, we know of no use cases that would involve more than two parameters that can either be lvalues or rvalues, other than those that are actually versions of perfect forwarding (and which are, therefore, not affected by the proposed change). Nonetheless, to address this issue, one could extend our proposed resolution to support a third kind of reference (spelled &&&) that binds to either lvalues or rvalues, effectively providing the current behavior of && but with a new spelling. Thus, the above swap could be written as:
void swap(mytype&&&, mytype&&&);
Interestingly, the current working paper's definition of non-member swap would not benefit from the addition of &&&. The working paper provides three overloads of each non-member swap, prohibiting rvalue-rvalue swaps:
void swap(mytype& , mytype&); void swap(mytype&&, mytype&); void swap(mytype& , mytype&&);
This overload set works the same way regardless of whether rvalue references bind to lvalues. Moreover, an LWG straw poll in San Francisco voted to revert from using three non-member swaps back to having only a single, lvalue-lvalue swap:
void swap(mytype&, mytype&);
due to library issue 884. Thus, &&& is not likely to be used in the working paper for non-member swap. For member swap, the number of extra overloads (one per existing swap) required is not sufficient to motivate the addition of another kind of reference.
With the stream insertion and extraction operators, the introduction of the operator>> and operator>> templates described in section Impact on the Standard Library eliminates the need for the use of &&&. We expect that most other uses of &&& can be addressed using this approach.
Another alternative solution that has been proposed to address the problem posed by the conceptualized version of push_back is to delete functions that fail to meet their concept requirements. That way, these functions remain in the overload set but any attempt to use them will result in an error. Recall the push_back overloads and their concept constraints:
requires CopyConstructible<value_type> void push_back(const value_type& x); // copies x requires MoveConstructible<value_type> void push_back(value_type&& x); // moves x
When instantiated with a move-only type X for value_type, the proposed solution would result in the following two functions:
void push_back(const X& x) = delete; // X isn't CopyConstructible void push_back(X&& x); // okay: X is MoveConstructible
This approach solves the problem for this example, because lvalues passed to push_back will still be attracted to the lvalue reference, and the compiler will produce a suitable error rather than silently moving from an lvalue.
The main problem with this approach is that it only solves the problem in those cases where the concept requirements of a template are not satisfied but SFINAE does not eliminate the template from consideration. For example, it does not solve the problem with the enqueue function described above (which doesn't involve concepts):
template <class T, typename Cont>
void enqueue(queue<T, Cont>& dest, queue<T, Cont>&& src); // #1
template <class T, typename Cont>
void enqueue(queue<T, Cont>& dest, const queue<T, Cont>& src,
typename Cont::allocator_type alloc = typename Cont::allocator_type()); // #2
It also does not solve the problem with a conceptualized version of the enqueue function:
template <class T, Container Cont>
void enqueue(queue<T, Cont>& dest, queue<T, Cont>&& src); // #1
template <class T, ContainerWithAllocator Cont>
void enqueue(queue<T, Cont>& dest, const queue<T, Cont>& src,
Cont::allocator_type alloc = Cont::allocator_type()); // #2
The conceptualized formulation of enqueue suffers from the same problem as the pre-concepts version: since Cont is not a ContainerWithAllocator, we cannot form the signature of the deleted enqueue function, so only function #1 will enter the overload set. Since it is the only function available, it will move from lvalues. Thus, the proposal to replace functions that fail their concept requirements with deleted functions does not solve the general problem, either with or without concepts.
The authors thank Peter Dimov, Howard Hinnant, Jaakko Jarvi, Mat Marcus, and Thomas Witt for many lively discussions on the topic of rvalue references and concepts, where many of the ideas in this paper originated.
| [1] | “Substitution Failure Is Not An Error.” See Josuttis & Vandevoorde, C++ Templates. |