|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r51920 - sandbox/committee/rvalue_ref
From: dgregor_at_[hidden]
Date: 2009-03-22 21:27:45
Author: dgregor
Date: 2009-03-22 21:27:43 EDT (Sun, 22 Mar 2009)
New Revision: 51920
URL: http://svn.boost.org/trac/boost/changeset/51920
Log:
Improving the intro
Text files modified:
sandbox/committee/rvalue_ref/rvalue-ref-exception-safety.html | 283 +++++++++++++++++++++++++++------------
1 files changed, 193 insertions(+), 90 deletions(-)
Modified: sandbox/committee/rvalue_ref/rvalue-ref-exception-safety.html
==============================================================================
--- sandbox/committee/rvalue_ref/rvalue-ref-exception-safety.html (original)
+++ sandbox/committee/rvalue_ref/rvalue-ref-exception-safety.html 2009-03-22 21:27:43 EDT (Sun, 22 Mar 2009)
@@ -18,9 +18,8 @@
compromises the exception safety guarantees made by the Standard
Library. In particular, well-formed C++03 programs, when compiled with
the C++0x Standard Library, can no longer rely on the strong exception
-safety guarantee provided by standard library containers. This silent
-change in behavior makes it nearly impossible to use the Standard
-Library in applications that must recover from exceptions thrown by
+safety guarantee provided by certain standard library containers. This silent
+change in behavior makes it nearly impossible to use these containers in applications that must recover from exceptions thrown by
the library. In this paper, we characterize the problem itself and
outline a potential solution that extends the language and modifies
the library.</p>
@@ -32,20 +31,18 @@
respect to exceptions based on the guarantees that the implementation
must provide if an exception is thrown. These guarantees describe the
state of the program once a thrown exception has unwound the stack
-past the point of that function. We recognize two levels of exception
+past the point of that function. We recognize three levels of exception
safety guarantees for a given library function:
<dl>
<dt>Basic exception guarantee</dt>
- <dd>No resources are leaked and all of the arguments to the function
- are left in a consistent, destructible state.</dd>
+ <dd>The invariants of the component are preserved, and no resources are leaked.</dd>
<dt>Strong exception guarantee</dt>
- <dd>No resources are leaked and all arguments to the function are
- left in the same state they were prior to invocation of the
- function. Therefore, the state of the program after exiting the
- function (via the exception) is the same as if the function were
- never called.</dd>
+ <dd>The operation has either completed successfully or thrown an exception, leaving the program state exactly as it was before the operation started.</dd>
+
+ <dt>No-throw guarantee</dt>
+ <dd>The operation will not throw an exception.</dd>
</dl>
<p>The Standard Library provides at least the basic exception
@@ -56,14 +53,159 @@
<h2 id="problem">The Problem</h2>
-<p>The fundamental problem addressed by this paper is that, for some
-functions that are specified with the strong exception guarantee that
-have also been extended with rvalue references, it is no longer
-possible to implement the strong exception guarantee. As an example,
+<p>The problem addressed by this paper is two-fold. First, for some
+functions that are specified with the strong exception guarantee, it
+is not possible to implement the strong exception guarantee if there
+exist any move constructors that throw exceptions. Second, although the C++0x standard library prohibits the use of move constructors in certain places, the C++0x Standard Library itself may provide move constructors that can throw exceptions.
+
+<h3 id="throwing-move-constructor">The Problem With Throwing Move Constructors</h3>
+
+<p>As an example,
we consider <code>vector</code>'s <code>push_back</code> operation,
e.g.,</p>
<pre>
+vec.push_back(x);
+</pre>
+
+<p>In the call to <code>push_back</code>, if the size of the
+<code>vector</code> is the same as it's capacity, we will have to
+allocate more storage for the <code>vector</code>. In this case, we
+first allocate more storage and then "move" the contents from the old
+storage into the new storage. Finally, we copy the new element into
+the new storage and, if everything has succeeded, free the old
+storage. The reallocation routine looks something like this:</p>
+
+<pre>
+T* reallocate(T *old_ptr, size_t old_capacity) {
+ // #1: allocate new storage
+ T* new_ptr = (T*)malloc(sizeof(T) * old_capacity * 2);
+ if (new_ptr == NULL)
+ throw std::bad_alloc();
+
+ // #2: try to move the elements to the new storage
+ unsigned i = 0;
+ try {
+ // #2a: construct each element in the new storage from the corresponding
+ // element in the old storage, treating the old elements as rvalues
+ for (; i < old_capacity; ++i)
+ new (new_ptr + i) T(std::move(old_ptr[i])); // "move" operation
+ } catch (...) {
+ // #2b: destroy the copies and deallocate the new storage
+ for (unsigned v = 0; v < i; ++v)
+ new_ptr[v]->~T();
+ free(new_ptr);
+ throw;
+ }
+
+ // #3: free the old storage
+ for (i = 0; i < old_capacity; ++i)
+ old_ptr[i]->~T();
+ free(old_ptr);
+ return new_ptr;
+}
+</pre>
+
+<p>For this discussion we are interested in section #2, which handles the movement of values from the old storage to the new storage. The use of <code>std::move</code> treats the elements in the old storage as rvalues, enabling a move constructor (if available) or falling back to a copy constructor (if no move constructor is available) with the same syntax.</p>
+
+<p>Consider reallocation of the vector when the type stored in the vector provides only a copy constructor (and no move constructor), as shown below. Here, we copy elements from the old storage (top) to the new storage (bottom).</p>
+
+<table border="0">
+ <tr>
+ <td>
+ <table border="1">
+ <tr>
+ <td>a</td><td>b</td><td>c</td><td>d</td>
+ <td>e</td><td>f</td><td>g</td><td>h</td>
+ </tr>
+ </table>
+ </td>
+ </tr>
+ <tr>
+ <td>
+ <table border="0">
+ <tr>
+ <td>↓</td><td>↓</td><td>↓</td><td>↓</td>
+ <td>↓</td><td></td><td></td><td></td>
+ </tr>
+ </table>
+ </td>
+ </tr>
+ <tr>
+ <td>
+ <table border="1">
+ <tr>
+ <td>a</td><td>b</td><td>c</td><td>d</td>
+ <td> </td><td> </td><td> </td><td> </td>
+<td> </td><td> </td><td> </td><td> </td>
+<td> </td><td> </td><td> </td><td> </td>
+ </tr>
+ </table>
+ </td>
+ </tr>
+</table>
+
+<p>While copying the fifth element (<code>e</code>) the copy constructor throws an exception. At this point, we can still recover, since the old storage still contains the original (unmodified) data. Thus, the recovery code (section #2b) destroys the elements in the new storage and then frees the new storage, providing the strong exception safety guarantee.</p>
+
+<p>When the type stored in the vector provides a move constructor, each of the values is moved from the old storage into the new storage, potentially mutating the values in the old storage. The notion is shown below, half-way through the reallocation:</p>
+
+<table border="0">
+ <tr>
+ <td>
+ <table border="1">
+ <tr>
+ <td>?</td><td>?</td><td>?</td><td>?</td>
+ <td>e</td><td>f</td><td>g</td><td>h</td>
+ </tr>
+ </table>
+ </td>
+ </tr>
+ <tr>
+ <td>
+ <table border="0">
+ <tr>
+ <td>⇓</td><td>⇓</td><td>⇓</td><td>⇓</td>
+ <td>⇓</td><td></td><td></td><td></td>
+ </tr>
+ </table>
+ </td>
+ </tr>
+ <tr>
+ <td>
+ <table border="1">
+ <tr>
+ <td>a</td><td>b</td><td>c</td><td>d</td>
+ <td> </td><td> </td><td> </td><td> </td>
+<td> </td><td> </td><td> </td><td> </td>
+<td> </td><td> </td><td> </td><td> </td>
+ </tr>
+ </table>
+ </td>
+ </tr>
+</table>
+
+<p>When the element's move constructor cannot throw, the reallocation is guaranteed to succeed, since no operations after the initial memory allocation can throw.</p>
+
+<p>However, if the element's move constructor can throw an exception (say, while moving the value <code>e</code>), we are left with a problem: neither the old storage nor the new storage captures the vector's state prior to initiating the reallocation. And, since we're recovering from an exception, we don't have the ability to move elements back from the new storage to the old storage, because their move constructors could throw in the process. Hence, the best we can do is maintain the basic guarantee, where no resources are leaked but the first four values in the vector have indeterminate values. Hence, it is not possible to provide the strong exception safety guarantee for vector's <code>push_back</code> in the presence of a throwing move constructor.</p>
+
+<h3 "strong-except-model">A Model of Strong Exception Safety</h3>
+<p>Stepping back from this specific instance, we can formulate a simple model for achieving the strong exception-safety guarantee. In this model, we take the set of operations that we need to perform in our routine and partition them into two sets: those operations that perform nonreversible modifications (such as moving a value from one place to another) and those operations that can throw exceptions. Providing strong exception safety means placing any operations that can throw exceptions (memory allocation, copying, etc.) before any operations that perform nonrevisible modifications (moving a value, destroying an object, freeing memory).</p>
+
+<p>Reconsidering <code>vector</code> reallocation in terms of this model, we see that, if we ignore throwing move constructors, the implementation of <code>reallocate</code> performs all of its possibly-throwing routines up front: we allocate memory, then copy (which may throw) or move (which won't throw), then we complete the operation. Either way, at some point within the routine we have committed to only using operations that can no longer throw, such as deallocating memory or destroying already-constructed objects.</p>
+
+<p>The problem with a throwing move operation is that it fits into
+both partitions. It can throw exceptions (obviously) and it is also a
+non-reversible modification, because (1) moving is permitted to transfer resources and (2) there is no non-throwing operation to reverse the transfer of resources.</p>
+
+<p>Based on this model, prohibiting the use of types that have
+throwing move constructors appears to solve the problem, and it does
+help somewhat. One immediate problem with this approach (which is already used by vector's <code>push_back</code> specification, among other things) is that it places the burden of ensuring that all move constructors are non-throwing on the user, without providing the user with any tools to determine whether this requirement is actually met.</p>
+
+<h3 id="throwing-pair">Throwing Move Constructors in the Standard Library</h3>
+
+<p>So, how easy is it to violate the requirement that move constructors not throw exceptions? It turns out to be surprisingly easy, and in fact existing, well-formed C++03 programs will violate this requirement when compiled with the C++0x Standard Library because the standard library itself creates throwing move constructors. As an example, consider a simple <code>Matrix</code> type that stores its values on the heap:</p>
+
+<pre>
class Matrix {
double *data;
unsigned rows, cols;
@@ -74,86 +216,51 @@
// copy data...
}
};
+</pre>
+
+<p>The <code>Matrix</code> type has a copy constructor that can throw an exception, but it has no move constructors. A <code>vector</code> of <code>Matrix</code> values is certainly well-formed and its <code>push_back</code> provides the strong exception safety guarantee. This is true both in C++03 and in C++0x.</p>
+<p>Next, we compose a <code>std::string</code> with a <code>Matrix</code> using <code>std::pair</code>:</p>
+
+<pre>
typedef std::pair<std::string, Matrix> NamedMatrix;
+</pre>
-void AddMatrix(std::vector<NamedMatrix>& Named, const NamedMatrix &M) {
- Named.push_back(M);
-}
+<p>Consider <code>std::pair</code>'s move constructor, which will look something like this (simplified!):</p>
+
+<pre>
+template<typename T, typename U>
+struct pair {
+ pair(pair&∓ other)
+ : first(std::move(other.first)), second(std::move(other.second)) { }
+
+ T first;
+ U second;
+};
</pre>
-<p>In the call to <code>push_back</code>, if the size of the
-<code>vector</code> is the same as it's capacity, we will have to
-allocate more storage for the <code>vector</code>. In this case, we
-first allocate more storage and then copy the contents from the old
-storage into the new storage. Finally, we copy the new element into
-the new storage and, if everything has succeeded, free the old
-storage.</p>
+<p>Here, the <code>pair</code>'s <code>first</code> data member is an <code>std::string</code>, which has a non-throwing move constructor that modifies its source value. The <code>pair</code>'s <code>second</code> data member is a <code>Matrix</code>, which has a throwing copy constructor but no move constructor. When we compose these two types, we end up with a type---<code>std::pair<std::string, Matrix></code>---that merges their behaviors. This <code>pair</code>'s move constructor performs a non-reversible modification on the <code>first</code> member of the pair (moving the resources of the <code>std::string</code>) and then performs a potentially-throwing copy construction on the <code>second</code> member of the pair (copying the <code>Matrix</code>). Thus, we have composed two well-behaved types, one from the library and one from user code, into a type that violates the prohibition on throwing move constructors. Moreover, this problem affects valid C++03 code, which will silently invoke undefin
ed behavior when compiled with a C++0x Standard Library </p>
-<p>During this reallocation and insertion process, there are many
-opportunities to exhaust the available memory, including the
-allocation of new storage for the <code>vector</code>, the allocation
-of memory while copying the <code>NamedMatrix</code> values from the
-old storage to the new storage, and the allocation of memory while
-copying the new <code>NamedMatrix</code> into the new storage. In
-C++03, the <code>push_back</code> operation can recover from an
-exception thrown from any of these places merely by destroying the
-copies in and then freeing the new storage, since the old storage
-remains intact. Therefore, <code>vector</code>'s
-<code>push_back</code> can provide the strong exception safety
-guarantee.</p>
-
-<p>With the introduction of move semantics (via rvalue references) in
-C++0x, the situation is complicated. To eliminate the need for
-extraneous copies (thereby improving performance) and to support the
-use of move-only types (like <code>std::unique_ptr</code>), the
-elements of the <code>vector</code> are moved from the old storage to
-the new storage. For C++03 types that only have a copy constructor
-(and no move constructor), the "move" operation actually performs a
-copy, so the C++0x library provides the same semantics as in
-C++03. For a type with a non-throwing move constructor (like
-<code>std::unique_ptr</code> or <code>std::string</code>), moving data
-from the old storage to the new storage will not throw any exceptions,
-and the implementation can still easily cope with exceptions thrown
-either when allocating the new storage (the old storage is still
-valid) or when copying the final element into the new storage (the new
-storage is still valid). Therefore, neither of these classes of types
-cause a problem for the strong exception guarantee.</p>
-
-<p>The <code>NamedMatrix</code> type, however, is neither here nor
-there. It is a <code>std::pair</code>, which means that it has a move
-constructor. However, this move constructor moves from its
-<code>first</code> subobject (the <code>std::string</code>) but copies
-from its <code>second</code> subobject (the <code>Matrix</code>),
-which means that it is both destructive (it modifies the source) and
-that it may throw an exception. During reallocation, after some
-elements have been move from the old storage to the new storage, the
-<code>Matrix</code> copy constructor may throw while moving an
-element. In this case, we are left in a state from which we cannot
-recover, where some elements are stored in the old storage and other
-elements are in the new storage. We cannot move the elements from the
-new storage back into the old storage, since doing so might throw
-another exception and cause us to terminate. Nor can we continue
-moving elements into the new storage, since we've already triggered an
-exception. The implementation could still provide the basic guarantee
-by, for example, truncating the <code>vector</code>, but it cannot
-roll back to its state prior to the <code>push_back</code> call.</p>
-
<h2 id="solution">Proposed Solution</h2>
-<p>In our motivating example, we saw that the <code>push_back</code>
-function can provide the strong exception safety guarantee when one of
-two conditions holds:</p>
+<p>The problematic throwing move constructor in our example comes from the aggregation of two well-formed types, so we focus our attention on the <code>pair</code> move constructor. In particular, given the prohibition on move constructors that may throw exceptions, <code>pair</code> should only declare a move constructor when it is guaranteed that the underlying move operations for the types it aggregates are both non-throwing. Using concept syntax, one might imagine that such a constructor would be written as:</p>
-<ol>
- <li>Moving an element from the old storage to the new storage is
- guaranteed not to throw, or</li>
- <li>Copying an element from the old storage to the new storage is
- guaranteed not to change the value of the original element.</li>
-</ol>
+<pre>
+ requires NothrowMoveConstructible<T> && NothrowMoveConstructible<U>
+ pair(pair&∓ other)
+ : first(std::move(other.first)), second(std::move(other.second)) { }
+</pre>
+
+<p>In this case, <code>pair</code> will only provide a move constructor when that move constructor is guaranteed to be non-throwing. Therefore, <code>std::pair<std::string, Matrix></code> will not provide a move constructor and reallocating a <code>vector</code> of these pairs will use the copy constructor, maintaining the strong exception safety guarantee. Naturally, <code>pair</code> is not the only type whose move constructor is effected: any standard library and user type that aggregates other values, including tuples and containers, will need similarly-constrained move constructors.</p>
+
+<p>At present, there is no good way to write the <code>NothrowMoveConstructible</code> concept. FIXME: pick up here
+
+
+TODO: ban
<p>At present, we have no way to detect whether either of these
-conditions hold. We therefore propose to ban the definition of move
+conditions hold. We copy constructors do not modify the values of
+We therefore propose to ban the definition of move
constructors and move assignment operators that throw
exceptions. We can then be sure that if we are invoking a move
constructor, it does not throw; that copy constructors preserve the
@@ -347,7 +454,7 @@
<pre>
auto concept NothrowMoveConstructible<typename T, typename U = T> {
- requires RvalueOf<U> &&;
+ requires RvalueOf<U>;
noexcept T::T(RvalueOf<U>::type);
}
</pre>
@@ -362,10 +469,6 @@
that users need not write concept maps for this low-level
concept.</p>
-<h3 id="noexceptmove">Move Construction and Assignment Requires
-<code>noexcept</code></h3>
-
-
<h3 id="movedefault">Default Implementations of Move Construction and Assignment</h3>
NOTE: The move constructor generated for closure types will need to be fixed, too.
@@ -380,5 +483,5 @@
<hr>
<address></address>
-<!-- hhmts start --> Last modified: Fri Mar 20 08:02:32 PDT 2009 <!-- hhmts end -->
+<!-- hhmts start --> Last modified: Sun Mar 22 18:28:39 PDT 2009 <!-- hhmts end -->
</body> </html>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk