Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/more/generic_exception_safety.html @ 56

Last change on this file since 56 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 36.3 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
2<!-- saved from url=(0052)http://people.ne.mediaone.net/abrahams/abrahams.html -->
3
4    <meta name="generator" content="Microsoft FrontPage 5.0">
5    <title>Exception-Safety in Generic Components</title>
6    <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
7    <meta content="MSHTML 5.50.4522.1800" name="GENERATOR">
8
9    <h1 align="center">Exception-Safety in Generic Components</h1>
10
11    <p align="center"><i><b>Lessons Learned from Specifying Exception-Safety
12    for the C++ Standard Library</b></i>
13
14    <h3 align="center">David Abrahams</h3>
15
16    <h3 align="center"><a href="mailto:david.abrahams@rcn.com">
17    david.abrahams@rcn.com</a></h3>
18
19    <p><b>Abstract.</b> This paper represents the knowledge accumulated in
20    response to a real-world need: that the C++ Standard Template Library
21    exhibit useful and well-defined interactions with exceptions, the
22    error-handling mechanism built-in to the core C++ language. It explores the
23    meaning of exception-safety, reveals surprising myths about exceptions and
24    genericity, describes valuable tools for reasoning about program
25    correctness, and outlines an automated testing procedure for verifying
26    exception-safety.
27
28    <p><b>Keywords:</b> exception-safety, exceptions, STL, C++
29
30    <h2>1 What is exception-safety?</h2>
31
32    <p>Informally, exception-safety in a component means that it exhibits
33    reasonable behavior when an exception is thrown during its execution. For
34    most people, the term ``reasonable'' includes all the usual
35    expectations for error-handling: that resources should not be leaked, and
36    that the program should remain in a well-defined state so that execution
37    can continue. For most components, it also includes the expectation that
38    when an error is encountered, it is reported to the caller.
39
40    <p>More formally, we can describe a component as minimally exception-safe
41    if, when exceptions are thrown from within that component, its invariants
42    are intact. Later on we'll see that at least three different levels of
43    exception-safety can be usefully distinguished. These distinctions can help
44    us to describe and reason about the behavior of large systems.
45
46    <p>In a generic component, we usually have an additional expectation of
47    <i>exception-neutrality</i>, which means that exceptions thrown by a
48    component's type parameters should be propagated, unchanged, to the
49    component's caller.
50
51    <h2>2 Myths and Superstitions</h2>
52
53    <p>Exception-safety seems straightforward so far: it doesn't constitute
54    anything more than we'd expect from code using more traditional
55    error-handling techniques. It might be worthwhile, however, to examine the
56    term from a psychological viewpoint. Nobody ever spoke of
57    ``error-safety'' before C++ had exceptions.
58
59    <p>It's almost as though exceptions are viewed as a <i>mysterious
60    attack</i> on otherwise correct code, from which we must protect ourselves.
61    Needless to say, this doesn't lead to a healthy relationship with error
62    handling! During standardization, a democratic process which requires broad
63    support for changes, I encountered many widely-held superstitions. In order
64    to even begin the discussion of exception-safety in generic components, it
65    may be worthwhile confronting a few of them.
66
67    <p><i>``Interactions between templates and exceptions are not
68    well-understood.''</i> This myth, often heard from those who consider
69    these both new language features, is easily disposed of: there simply are
70    no interactions. A template, once instantiated, works in all respects like
71    an ordinary class or function. A simple way to reason about the behavior of
72    a template with exceptions is to think of how a specific instantiation of
73    that template works. Finally, the genericity of templates should not cause
74    special concern. Although the component's client supplies part of the
75    operation (which may, unless otherwise specified, throw arbitrary
76    exceptions), the same is true of operations using familiar virtual
77    functions or simple function pointers.
78
79    <p><i>``It is well known to be impossible to write an exception-safe
80    generic container.''</i> This claim is often heard with reference to
81    an article by Tom Cargill <a title=
82    "Tom Cargill, ``Exception Handling: A False Sense of Security'', C++ Report, Nov-Dec 1994"
83     href=
84    "#reference4"><sup>[4]</sup></a>
85    in which he explores the problem of exception-safety for a generic stack
86    template. In his article, Cargill raises many useful questions, but
87    unfortunately fails to present a solution to his problem.<a title=
88    "Probably the greatest impediment to a solution in Cargill's case was an unfortunate combination of choices on his part: the interface he chose for his container was incompatible with his particular demands for safety. By changing either one he might have solved the problem."
89     href=
90    "#footnote1"><sup>1</sup></a>
91    He concludes by suggesting that a solution may not be possible.
92    Unfortunately, his article was read by many as ``proof'' of that
93    speculation. Since it was published there have been many examples of
94    exception-safe generic components, among them the C++ standard library
95    containers.
96
97    <p><i>``Dealing with exceptions will slow code down, and templates are
98    used specifically to get the best possible performance.''</i> A good
99    implementation of C++ will not devote a single instruction cycle to dealing
100    with exceptions until one is thrown, and then it can be handled at a speed
101    comparable with that of calling a function <a title=
102    "D. R. Musser, ``Introspective Sorting and Selection Algorithms'', Software-Practice and Experience 27(8):983-993, 1997."
103     href=
104    "#reference7"><sup>[7]</sup></a>.
105    That alone gives programs using exceptions performance equivalent to that
106    of a program which ignores the possibility of errors. Using exceptions can
107    actually result in faster programs than ``traditional'' error
108    handling methods for other reasons. First, a catch block clearly indicates
109    to the compiler which code is devoted to error-handling; it can then be
110    separated from the usual execution path, improving locality of reference.
111    Second, code using ``traditional'' error handling must typically
112    test a return value for errors after every single function call; using
113    exceptions completely eliminates that overhead.
114
115    <p><i>``Exceptions make it more difficult to reason about a program's
116    behavior.''</i> Usually cited in support of this myth is the way
117    ``hidden'' execution paths are followed during stack-unwinding.
118    Hidden execution paths are nothing new to any C++ programmer who expects
119    local variables to be destroyed upon returning from a function:
120
121    <blockquote>
122<pre>ErrorCode f( int&amp; result )         // 1
123{                                  // 2
124    X x;                           // 3
125    ErrorCode err = x.g( result ); // 4
126    if ( err != kNoError )         // 5
127        return err;                // 6
128    // ...More code here...
129    return kNoError;               // 7
130}
131</pre>
132    </blockquote>
133
134    <p>In the example above, there is a ``hidden'' call to
135    <code>X::~X()</code> in lines 6 and 7. Granted, using exceptions, there is
136    no code devoted to error handling visible:
137
138    <blockquote>
139<pre>int f()                 // 1
140{                       // 2
141    X x;                // 3
142    int result = x.g(); // 4
143    // ...More code here...
144    return result;      // 5
145}
146</pre>
147    </blockquote>
148
149    <p>For many programmers more familiar with exceptions, the second example
150    is actually more readable and understandable than the first. The
151    ``hidden'' code paths include the same calls to destructors of
152    local variables. In addition, they follow a simple pattern which acts
153    <i>exactly</i> as though there were a potential return statement after each
154    function call in case of an exception. Readability is enhanced because the
155    normal path of execution is unobscured by error-handling, and return values
156    are freed up to be used in a natural way.
157
158    <p>There is an even more important way in which exceptions can enhance
159    correctness: by allowing simple class invariants. In the first example, if
160    <code>x</code>'s constructor should need to allocate resources, it has no
161    way to report a failure: in C++, constructors have no return values. The
162    usual result when exceptions are avoided is that classes requiring
163    resources must include a separate initializer function which finishes the
164    job of construction. The programmer can therefore never be sure, when an
165    object of class <code>X</code> is used, whether he is handling a
166    full-fledged <code>X</code> or some abortive attempt to construct one (or
167    worse: someone simply forgot to call the initializer!)
168
169    <h2>3 A contractual basis for exception-safety</h2>
170
171    <p>A non-generic component can be described as exception-safe in isolation,
172    but because of its configurability by client code, exception-safety in a
173    generic component usually depends on a contract between the component and
174    its clients. For example, the designer of a generic component might require
175    that an operation which is used in the component's destructor not throw any
176    exceptions.<a title=
177    " It is usually inadvisable to throw an exception from a destructor in C++, since the destructor may itself be called during the stack-unwinding caused by another exception. If the second exception is allowed to propagate beyond the destructor, the program is immediately terminated."
178     href=
179    "#footnote2"><sup>2</sup></a>
180    The generic component might, in return, provide one of the following
181    guarantees:
182
183    <ul>
184      <li>The <i>basic</i> guarantee: that the invariants of the component are
185      preserved, and no resources are leaked.
186
187      <li>The <i>strong</i> guarantee: that the operation has either completed
188      successfully or thrown an exception, leaving the program state exactly as
189      it was before the operation started.
190
191      <li>The <i>no-throw</i> guarantee: that the operation will not throw an
192      exception.
193    </ul>
194
195    <p>The basic guarantee is a simple minimum standard for exception-safety to
196    which we can hold all components. It says simply that after an exception,
197    the component can still be used as before. Importantly, the preservation of
198    invariants allows the component to be destroyed, potentially as part of
199    stack-unwinding. This guarantee is actually less useful than it might at
200    first appear. If a component has many valid states, after an exception we
201    have no idea what state the component is in|only that the state is valid.
202    The options for recovery in this case are limited: either destruction or
203    resetting the component to some known state before further use. Consider
204    the following example:
205
206    <blockquote>
207<pre>template &lt;class X&gt; 
208void print_random_sequence()
209{
210    std::vector&lt;X&gt; v(10); // A vector of 10 items
211    try {
212        // Provides only the <i>basic</i> guarantee
213        v.insert( v.begin(), X() );
214    }
215    catch(...) {} // ignore any exceptions above
216    // print the vector's contents
217    std::cout "(" &lt;&lt; v.size() &lt;&lt; ") ";
218    std::copy( v.begin(), v.end(),
219    std::ostream_iterator&lt;X&gt;( std::cout, " " ) );
220}
221</pre>
222    </blockquote>
223
224    <p>Since all we know about v after an exception is that it is valid, the
225    function is allowed to print any random sequence of <code>X</code>s.<a
226    title=
227    "In practice of course, this function would make an extremely poor random sequence generator!"
228     href=
229    "#footnote3"><sup>3</sup></a>
230    It is ``safe'' in the sense that it is not allowed to crash, but
231    its output may be unpredictable.
232
233    <p>The <i>strong</i> guarantee provides full
234    ``commit-or-rollback'' semantics. In the case of C++ standard
235    containers, this means, for example, that if an exception is thrown all
236    iterators remain valid. We also know that the container has exactly the
237    same elements as before the exception was thrown. A transaction that has no
238    effects if it fails has obvious benefits: the program state is simple and
239    predictable in case of an exception. In the C++ standard library, nearly
240    all of the operations on the node-based containers list, set, multiset,
241    map, and multimap provide the <i>strong</i> guarantee.<a title=
242    "It is worth noting that mutating algorithms usually cannot provide the strong guarantee: to roll back a modified element of a range, it must be set back to its previous value using operator=, which itself might throw. In the C++ standard library, there are a few exceptions to this rule, whose rollback behavior consists only of destruction: uninitialized_copy, uninitialized_fill, and uninitialized_fill_n."
243     href=
244    "#footnote4"><sup>4</sup></a>).
245
246    <p>The <i>no-throw</i> guarantee is the strongest of all, and it says that
247    an operation is guaranteed not to throw an exception: it always completes
248    successfully. This guarantee is necessary for most destructors, and indeed
249    the destructors of C++ standard library components are all guaranteed not
250    to throw exceptions. The <i>no-throw</i> guarantee turns out to be
251    important for other reasons, as we shall see.<a title=
252    "All type parameters supplied by clients of the C++ standard library are required not to throw from their destructors. In return, all components of the C++ standard library provide at least the basic guarantee."
253     href=
254    "#footnote5"><sup>5</sup></a>
255
256    <h2>4 Legal Wrangling</h2>
257
258    <p>Inevitably, the contract can get more complicated: a quid pro quo
259    arrangement is possible. Some components in the C++ Standard Library give
260    one guarantee for arbitrary type parameters, but give a stronger guarantee
261    in exchange for additional promises from the client type that no exceptions
262    will be thrown. For example, the standard container operation
263    <code>vector&lt;T&gt;::erase</code> gives the <i>basic</i> guarantee for
264    any <code>T</code>, but for types whose copy constructor and copy
265    assignment operator do not throw, it gives the <i>no-throw</i> guarantee.<a
266    title=
267    "Similar arrangements might have been made in the C++ standard for many of the mutating algorithms, but were never considered due to time constraints on the standardization process."
268     href=
269    "#footnote6"><sup>6</sup></a>
270
271    <h2>5 What level of exception-safety should a component specify?</h2>
272
273    <p>From a client's point-of-view, the strongest possible level of safety
274    would be ideal. Of course, the <i>no-throw</i> guarantee is simply
275    impossible for many operations, but what about the <i>strong</i> guarantee?
276    For example, suppose we wanted atomic behavior for
277    <code>vector&lt;T&gt;::insert</code>. Insertion into the middle of a vector
278    requires copying elements after the insertion point into later positions,
279    to make room for the new element. If copying an element can fail, rolling
280    back the operation would require ``undoing'' the previous
281    copies...which depends on copying again. If copying back should fail (as it
282    likely would), we have failed to meet our guarantee.
283
284    <p>One possible alternative would be to redefine <code>insert</code> to
285    build the new array contents in a fresh piece of memory each time, and only
286    destroy the old contents when that has succeeded. Unfortunately, there is a
287    non-trivial cost if this approach is followed: insertions near the end of a
288    vector which might have previously caused only a few copies would now cause
289    every element to be copied. The <i>basic</i> guarantee is a
290    ``natural'' level of safety for this operation, which it can
291    provide without violating its performance guarantees. In fact all of the
292    operations in the library appear to have such a ``natural'' level
293    of safety.
294
295    <p>Because performance requirements were already a well-established part of
296    the draft standard and because performance is a primary goal of the STL,
297    there was no attempt to specify more safety than could be provided within
298    those requirements. Although not all of the library gives the <i>strong</i>
299    guarantee, almost any operation on a standard container which gives the
300    <i>basic</i> guarantee can be made <i>strong</i> using the ``make a
301    new copy'' strategy described above:
302
303    <blockquote>
304<pre>template &lt;class Container, class BasicOp&gt; 
305void MakeOperationStrong( Container&amp; c, const BasicOp&amp; op )
306{
307    Container tmp(c); // Copy c
308    op(tmp); // Work on the copy
309    c.swap(tmp); // Cannot fail<a title=
310"Associative containers whose Compare object might throw an exception when copied cannot use this technique, since the swap function might fail."
311 href=
312"#footnote7"><sup>7</sup></a>
313}
314</pre>
315    </blockquote>
316
317    <p>This technique can be folded into a wrapper class to make a similar
318    container which provides stronger guarantees (and different performance
319    characteristics).<a title=
320    "This suggests another potential use for the oft-wished-for but as yet unseen container traits&lt;&gt; template: automated container selection to meet exceptionsafety constraints."
321     href=
322    "#footnote8"><sup>8</sup></a>
323
324    <h2>6 Should we take everything we can get?</h2>
325
326    <p>By considering a particular implementation, we can hope to discern a
327    natural level of safety. The danger in using this to establish requirements
328    for a component is that the implementation might be restricted. If someone
329    should come up with a more-efficient implementation which we'd like to use,
330    we may find that it's incompatible with our exception-safety requirements.
331    One might expect this to be of no concern in the well-explored domains of
332    data structures and algorithms covered by the STL, but even there, advances
333    are being made. A good example is the recent <i>introsort</i> algorithm <a
334    title=
335    "D. R. Musser, ``Introspective Sorting and Selection Algorithms'', Software-Practice and Experience 27(8):983-993, 1997."
336     href=
337    "#reference6"><sup>[6]</sup></a>,
338    which represents a substantial improvement in worst-case complexity over
339    the well-established <i>quicksort</i>.
340
341    <p>To determine exactly how much to demand of the standard components, I
342    looked at a typical real-world scenario. The chosen test case was a
343    ``composite container.'' Such a container, built of two or more
344    standard container components, is not only commonly needed, but serves as a
345    simple representative case for maintaining invariants in larger systems:
346
347    <blockquote>
348<pre>// SearchableStack - A stack which can be efficiently searched
349// for any value.
350template &lt;class T&gt; 
351class SearchableStack
352{
353 public:
354    void push(const T&amp; t); // O(log n)
355    void pop(); // O(log n)
356    bool contains(const T&amp; t) const; // O(log n)
357    const T&amp; top() const; // O(1)
358 private:
359    std::set&lt;T&gt; set_impl;
360    std::list&lt;std::set&lt;T&gt;::iterator&gt; list_impl;
361};
362</pre>
363    </blockquote>
364
365    <p>The idea is that the list acts as a stack of set iterators: every
366    element goes into the set first, and the resulting position is pushed onto
367    the list. The invariant is straightforward: the set and the list should
368    always have the same number of elements, and every element of the set
369    should be referenced by an element of the list. The following
370    implementation of the push function is designed to give the <i>strong</i>
371    guarantee within the natural levels of safety provided by set and list:
372
373    <blockquote>
374<pre>template &lt;class T&gt;                                // 1
375void SearchableStack&lt;T&gt;::push(const T&amp; t)         // 2
376{                                                       // 3
377    set&lt;T&gt;::iterator i = set_impl.insert(t);      // 4
378    try                                                 // 5
379    {                                                   // 6
380        list_impl.push_back(i);                         // 7
381    }                                                   // 8
382    catch(...)                                          // 9
383    {                                                   // 10
384        set_impl.erase(i);                              // 11
385        throw;                                          // 12
386    }                                                   // 13
387}                                                       // 14
388</pre>
389    </blockquote>
390
391    <p>What does our code actually require of the library? We need to examine
392    the lines where non-const operations occur:
393
394    <ul>
395      <li>Line 4: if the insertion fails but <code>set_impl</code> is modified
396      in the process, our invariant is violated. We need to be able to rely on
397      the <i>strong</i> guarantee from <code>set&lt;T&gt;::insert</code>.
398
399      <li>Line 7: likewise, if <code>push_back</code> fails, but
400      <code>list_impl</code> is modified in the process, our invariant is
401      violated, so we need to be able to rely on the <i>strong</i> guarantee
402      from list&lt;T&gt;::insert.
403
404      <li>Line 11: here we are ``rolling back'' the insertion on line
405      4. If this operation should fail, we will be unable to restore our
406      invariant. We absolutely depend on the <i>no-throw</i> guarantee from
407      <code>set&lt;T&gt;::erase</code>.<a title=
408      "One might be tempted to surround the erase operation with a try/catch block to reduce the requirements on set&lt;T&gt; and the problems that arise in case of an exception, but in the end that just begs the question. First, erase just failed and in this case there are no viable alternative ways to produce the necessary result. Second and more generally, because of the variability of its type parameters a generic component can seldom be assured that any alternatives will succeed."
409       href=
410      "#footnote9"><sup>9</sup></a>
411
412      <li>Line 11: for the same reasons, we also depend on being able to pass
413      the <code>i</code> to the <code>erase</code> function: we need the
414      <i>no-throw</i> guarantee from the copy constructor of
415      <code>set&lt;T&gt;::iterator</code>.
416    </ul>
417
418    <p>I learned a great deal by approaching the question this way during
419    standardization. First, the guarantee specified for the composite container
420    actually depends on stronger guarantees from its components (the
421    <i>no-throw</i> guarantees in line 11). Also, I took advantage of all of
422    the natural level of safety to implement this simple example. Finally, the
423    analysis revealed a requirement on iterators which I had previously
424    overlooked when operations were considered on their own. The conclusion was
425    that we should provide as much of the natural level of safety as possible.
426    Faster but less-safe implementations could always be provided as extensions
427    to the standard components. <sup><a title=
428    "The prevalent philosophy in the design of STL was that functionality that wasn't essential to all uses should be left out in favor of efficiency, as long as that functionality could be obtained when needed by adapting the base components. This departs from that philosophy, but it would be difficult or impossible to obtain even the basic guarantee by adapting a base component that doesn't already have it."
429     name="#footnote10">10</a></sup>
430
431    <h2>7 Automated testing for exception-safety</h2>
432
433    <p>As part of the standardization process, I produced an exception-safe
434    reference implementation of the STL. Error-handling code is seldom
435    rigorously tested in real life, in part because it is difficult to cause
436    error conditions to occur. It is very common to see error-handling code
437    which crashes the first time it is executed ...in a shipping product! To
438    bolster confidence that the implementation actually worked as advertised, I
439    designed an automated test suite, based on an exhaustive technique due to
440    my colleague Matt Arnold.
441
442    <p>The test program started with the basics: reinforcement and
443    instrumentation, especially of the global operators <code>new</code> and
444    <code>delete</code>.<sup><a title=
445    "An excellent discussion on how to fortify memory subsystems can be found in: Steve Maguire, Writing Solid Code, Microsoft Press, Redmond, WA, 1993, ISBN 1-55615- 551-4."
446     name="#footnote11">11</a></sup>Instances of the components (containers and
447    algorithms) were created, with type parameters chosen to reveal as many
448    potential problems as possible. For example, all type parameters were given
449    a pointer to heap-allocated memory, so that leaking a contained object
450    would be detected as a memory leak.
451
452    <p>Finally, a scheme was designed that could cause an operation to throw an
453    exception at each possible point of failure. At the beginning of every
454    client-supplied operation which is allowed to throw an exception, a call to
455    <code>ThisCanThrow</code> was added. A call to <code>ThisCanThrow</code>
456    also had to be added everywhere that the generic operation being tested
457    might throw an exception, for example in the global operator
458    <code>new</code>, for which an instrumented replacement was supplied.
459
460    <blockquote>
461<pre>// Use this as a type parameter, e.g. vector&lt;TestClass&gt; 
462struct TestClass
463{
464    TestClass( int v = 0 )
465        : p( ThisCanThrow(), new int( v ) ) {}
466    TestClass( const TestClass&amp; rhs )
467        : p( ThisCanThrow(), new int( *rhs.p ) ) {}
468    const TestClass&amp; operator=( const TestClass&amp; rhs )
469        { ThisCanThrow(); *p = *rhs.p; }
470    bool operator==( const TestClass&amp; rhs ) const
471        { ThisCanThrow(); return *p == *rhs.p; }
472    ...etc...
473    ~TestClass() { delete p; }
474};
475</pre>
476    </blockquote>
477
478    <p><code>ThisCanThrow</code> simply decrements a ``throw
479    counter'' and, if it has reached zero, throws an exception. Each test
480    takes a form which begins the counter at successively higher values in an
481    outer loop and repeatedly attempts to complete the operation being tested.
482    The result is that the operation throws an exception at each successive
483    step along its execution path that can possibly fail. For example, here is
484    a simplified version of the function used to test the <i>strong</i>
485    guarantee: <a title=
486    "Note that this technique requires that the operation being tested be exception-neutral. If the operation ever tries to recover from an exception and proceed, the throw counter will be negative, and subsequent operations that might fail will not be tested for exception-safety."
487     href=
488    "#footnote12"><sup>12</sup></a>
489
490    <blockquote>
491<pre>extern int gThrowCounter; // The throw counter
492void ThisCanThrow()
493{
494    if (gThrowCounter-- == 0)
495        throw 0;
496}
497 
498template &lt;class Value, class Operation&gt; 
499void StrongCheck(const Value&amp; v, const Operation&amp; op)
500{
501    bool succeeded = false;
502    for (long nextThrowCount = 0; !succeeded; ++nextThrowCount)
503    {
504        Value duplicate = v;
505        try
506        {
507            gThrowCounter = nextThrowCount;
508            op( duplicate ); // Try the operation
509            succeeded = true;
510        }
511        catch(...) // Catch all exceptions
512        {
513            bool unchanged = duplicate == v; // Test <i>strong</i> guarantee
514            assert( unchanged );
515        }
516        // Specialize as desired for each container type, to check
517        // integrity. For example, size() == distance(begin(),end())
518        CheckInvariant(v); // Check any invariant
519    }
520}
521</pre>
522    </blockquote>
523
524    <p>Notably, this kind of testing is much easier and less intrusive with a
525    generic component than with non-generics, because testing-specific type
526    parameters can be used without modifying the source code of the component
527    being tested. Also, generic functions like <code>StrongCheck</code> above
528    were instrumental in performing the tests on a wide range of values and
529    operations.
530
531    <h2>8 Further Reading</h2>
532    To my knowledge, there are currently only two descriptions of STL
533    exception-safety available. The original specification <a title=
534    "D. Abrahams, Exception Safety in STLport" href=
535    "#reference2"><sup>[2]</sup></a>
536    for the reference exception-safe implementation of the STL is an informal
537    specification, simple and self-explanatory (also verbose), and uses the
538    <i>basic-</i> and <i>strong-</i>guarantee distinctions outlined in this
539    article. It explicitly forbids leaks, and differs substantively from the
540    final C++ standard in the guarantees it makes, though they are largely
541    identical. I hope to produce an updated version of this document soon.
542
543    <p>The description of exception-safety in the C++ Standard <a title=
544    "International Standard ISO/IEC 14882, Information Technology-Programming Languages-C++, Document Number ISO/IEC 14882-1998"
545     href=
546    "#reference1"><sup>[1]</sup></a>
547    is only slightly more formal, but relies on hard-to-read
548    ``standardese'' and an occasionally subtle web of implication.<a
549    title=
550    "The changes to the draft standard which introduced exception-safety were made late in the process, when amendments were likely to be rejected solely on the basis of the number of altered words. Unfortunately, the result compromises clarity somewhat in favor of brevity. Greg Colvin was responsible for the clever language-lawyering needed to minimize the extent of these changes."
551     href=
552    "#footnote13"><sup>13</sup></a>
553    In particular, leaks are not treated directly at all. It does have the
554    advantage that it <i>is</i> the standard.
555
556    <p>The original reference implementation <a title=
557    "B. Fomitchev, Adapted SGI STL Version 1.0, with exception handling code by D. Abrahams"
558     href=
559    "#reference5"><sup>[5]</sup></a>
560    of the exception-safe STL is an adaptation of an old version of the SGI
561    STL, designed for C++ compilers with limited features. Although it is not a
562    complete STL implementation, the code may be easier to read, and it
563    illustrates a useful base-class technique for eliminating
564    exception-handling code in constructors. The full test suite <a title=
565    "D. Abrahams and B. Fomitchev, Exception Handling Test Suite" href=
566    "#reference3"><sup>[3]</sup></a>
567    used to validate the reference implementation has been used successfully to
568    validate all recent versions of the SGI STL, and has been adapted to test
569    one other vendor's implementation (which failed). As noted on the
570    documentation page, it also seems to have the power to reveal hidden
571    compiler bugs, particularly where optimizers interact with
572    exception-handling code.
573
574    <h2>References</h2>
575
576    <ol>
577      <li><a name="reference1">International</a> Standard ISO/IEC 14882,
578      <i>Information Technology-Programming Languages-C++</i>, Document Number
579      ISO/IEC 14882-1998, available from <a href=
580      "http://webstore.ansi.org/ansidocstore/default.asp">http://webstore.ansi.org/ansidocstore/default.asp</a>.
581
582      <li><a name="reference2">D.</a> Abrahams, <i>Exception Safety in
583      STLport</i>, available at <a href=
584      "http://www.stlport.org/doc/exception_safety.html">http://www.stlport.org/doc/exception_safety.html</a>.
585
586      <li><a name="reference3">D.</a> Abrahams and B. Fomitchev, <i>Exception
587      Handling Test Suite</i>, available at <a href=
588      "http://www.stlport.org/doc/eh_testsuite.html">http://www.stlport.org/doc/eh_testsuite.html</a>.
589
590      <li><a name="reference4">Tom</a> Cargill, ``Exception Handling:
591      A False Sense of Security,'' C++ Report, Nov-Dec 1994, also
592      available at <a href=
593      "http://www.awprofessional.com/content/images/020163371x/supplements/Exception_Handling_Article.html">http://www.awprofessional.com/content/images/020163371x/supplements/Exception_Handling_Article.html</a>.
594
595      <li><a name="reference5">B.</a> Fomitchev, <i>Adapted SGI STL Version
596      1.0</i>, with exception handling code by D. Abrahams, available at <a
597      href="http://www.stlport.org">http://www.stlport.org</a>.
598
599      <li><a name="reference6">D.</a> R. Musser, ``Introspective Sorting
600      and Selection Algorithms,'' <i>Software-Practice and Experience</i>
601      27(8):983-993, 1997.
602
603      <li><a name="reference7">Bjarne</a> Stroustrup, <i>The Design And
604      Evolution of C++</i>. Addison Wesley, Reading, MA, 1995, ISBN
605      0-201-54330-3, Section 16.9.1.
606    </ol>
607
608    <h2>Footnotes</h2>
609
610    <p><a name="footnote1">1</a> Probably the greatest impediment to a solution
611    in Cargill's case was an unfortunate combination of choices on his part:
612    the interface he chose for his container was incompatible with his
613    particular demands for safety. By changing either one he might have solved
614    the problem.
615
616    <p><a name="footnote2">2</a> It is usually inadvisable to throw an
617    exception from a destructor in C++, since the destructor may itself be
618    called during the stack-unwinding caused by another exception. If the
619    second exception is allowed to propagate beyond the destructor, the program
620    is immediately terminated.
621
622    <p><a name="footnote3">3</a> In practice of course, this function would
623    make an extremely poor random sequence generator!
624
625    <p><a name="footnote4">4</a> It is worth noting that mutating algorithms
626    usually cannot provide the <i>strong</i> guarantee: to roll back a modified
627    element of a range, it must be set back to its previous value using
628    <code>operator=</code>, which itself might throw. In the C++ standard
629    library, there are a few exceptions to this rule, whose rollback behavior
630    consists only of destruction: <code>uninitialized_copy</code>,
631    <code>uninitialized_fill</code>, and <code>uninitialized_fill_n</code>.
632
633    <p><a name="footnote5">5</a> All type parameters supplied by clients of the
634    C++ standard library are required not to throw from their destructors. In
635    return, all components of the C++ standard library provide at least the
636    <i>basic</i> guarantee.
637
638    <p><a name="footnote6">6</a> Similar arrangements might have been made in
639    the C++ standard for many of the mutating algorithms, but were never
640    considered due to time constraints on the standardization process.
641
642    <p><a name="footnote7">7</a> Associative containers whose
643    <code>Compare</code> object might throw an exception when copied cannot use
644    this technique, since the swap function might fail.
645
646    <p><a name="footnote8">8</a> This suggests another potential use for the
647    oft-wished-for but as yet unseen <code>container_traits&lt;&gt;</code>
648    template: automated container selection to meet exception-safety
649    constraints.
650
651    <p><a name="footnote9">9</a> One might be tempted to surround the erase
652    operation with a <code>try</code>/<code>catch</code> block to reduce the
653    requirements on <code>set&lt;T&gt;</code> and the problems that arise in
654    case of an exception, but in the end that just begs the question. First,
655    erase just failed and in this case there are no viable alternative ways to
656    produce the necessary result. Second and more generally, because of the
657    variability of its type parameters a generic component can seldom be
658    assured that any alternatives will succeed.
659
660    <p><a name="footnote10">10</a> The prevalent philosophy in the design of
661    STL was that functionality that wasn't essential to all uses should be left
662    out in favor of efficiency, as long as that functionality could be obtained
663    when needed by adapting the base components. This departs from that
664    philosophy, but it would be difficult or impossible to obtain even the
665    <i>basic</i> guarantee by adapting a base component that doesn't already
666    have it.
667
668    <p><a name="footnote11">11</a> An excellent discussion on how to fortify
669    memory subsystems can be found in: Steve Maguire, Writing Solid Code,
670    Microsoft Press, Redmond, WA, 1993, ISBN 1-55615- 551-4.
671
672    <p><a name="footnote12">12</a> Note that this technique requires that the
673    operation being tested be exception-neutral. If the operation ever tries to
674    recover from an exception and proceed, the throw counter will be negative,
675    and subsequent operations that might fail will not be tested for
676    exception-safety.
677
678    <p><a name="footnote13">13</a> The changes to the draft standard which
679    introduced exception-safety were made late in the process, when amendments
680    were likely to be rejected solely on the basis of the number of altered
681    words. Unfortunately, the result compromises clarity somewhat in favor of
682    brevity. Greg Colvin was responsible for the clever language-lawyering
683    needed to minimize the extent of these changes.
Note: See TracBrowser for help on using the repository browser.