Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/doc/html/variant/design.html @ 46

Last change on this file since 46 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 21.3 KB
Line 
1<html>
2<head>
3<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
4<title>Design Overview</title>
5<link rel="stylesheet" href="../boostbook.css" type="text/css">
6<meta name="generator" content="DocBook XSL Stylesheets V1.68.1">
7<link rel="start" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
8<link rel="up" href="../variant.html" title="Chapter 20. Boost.Variant">
9<link rel="prev" href="../boost/visitor_ptr.html" title="Function template visitor_ptr">
10<link rel="next" href="misc.html" title="Miscellaneous Notes">
11</head>
12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
13<table cellpadding="2" width="100%">
14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
15<td align="center"><a href="../../../index.htm">Home</a></td>
16<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
17<td align="center"><a href="../../../people/people.htm">People</a></td>
18<td align="center"><a href="../../../more/faq.htm">FAQ</a></td>
19<td align="center"><a href="../../../more/index.htm">More</a></td>
20</table>
21<hr>
22<div class="spirit-nav">
23<a accesskey="p" href="../boost/visitor_ptr.html"><img src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../variant.html"><img src="../images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../images/home.png" alt="Home"></a><a accesskey="n" href="misc.html"><img src="../images/next.png" alt="Next"></a>
24</div>
25<div class="section" lang="en">
26<div class="titlepage"><div><div><h2 class="title" style="clear: both">
27<a name="variant.design"></a>Design Overview</h2></div></div></div>
28<div class="toc"><dl><dt><span class="section"><a href="design.html#variant.design.never-empty">"Never-Empty" Guarantee</a></span></dt></dl></div>
29<div class="section" lang="en">
30<div class="titlepage"><div><div><h3 class="title">
31<a name="variant.design.never-empty"></a>"Never-Empty" Guarantee</h3></div></div></div>
32<div class="toc"><dl>
33<dt><span class="section"><a href="design.html#variant.design.never-empty.guarantee">The Guarantee</a></span></dt>
34<dt><span class="section"><a href="design.html#variant.design.never-empty.problem">The Implementation Problem</a></span></dt>
35<dt><span class="section"><a href="design.html#variant.design.never-empty.memcpy-solution">The "Ideal" Solution: False Hopes</a></span></dt>
36<dt><span class="section"><a href="design.html#variant.design.never-empty.double-storage-solution">An Initial Solution: Double Storage</a></span></dt>
37<dt><span class="section"><a href="design.html#variant.design.never-empty.heap-backup-solution">Current Approach: Temporary Heap Backup</a></span></dt>
38<dt><span class="section"><a href="design.html#variant.design.never-empty.optimizations">Enabling Optimizations</a></span></dt>
39<dt><span class="section"><a href="design.html#variant.design.never-empty.roadmap">Future Direction: Policy-based Implementation</a></span></dt>
40</dl></div>
41<div class="section" lang="en">
42<div class="titlepage"><div><div><h4 class="title">
43<a name="variant.design.never-empty.guarantee"></a>The Guarantee</h4></div></div></div>
44<p>All instances <code class="computeroutput">v</code> of type
45        <code class="computeroutput"><a href="../boost/variant.html" title="Class template variant">variant</a>&lt;T1,T2,...,TN&gt;</code>
46        guarantee that <code class="computeroutput">v</code> has constructed content of one of the
47        types <code class="computeroutput">T<span class="emphasis"><em>i</em></span></code>, even if an operation on
48        <code class="computeroutput">v</code> has previously failed.</p>
49<p>This implies that <code class="computeroutput">variant</code> may be viewed precisely as
50        a union of <span class="emphasis"><em>exactly</em></span> its bounded types. This
51        "never-empty" property insulates the user from the
52        possibility of undefined <code class="computeroutput">variant</code> content and the
53        significant additional complexity-of-use attendant with such a
54        possibility.</p>
55</div>
56<div class="section" lang="en">
57<div class="titlepage"><div><div><h4 class="title">
58<a name="variant.design.never-empty.problem"></a>The Implementation Problem</h4></div></div></div>
59<p>While the
60        <a href="design.html#variant.design.never-empty.guarantee" title="The Guarantee">never-empty guarantee</a>
61        might at first seem "obvious," it is in fact not even
62        straightforward how to implement it in general (i.e., without
63        unreasonably restrictive additional requirements on
64        <a href="reference.html#variant.concepts.bounded-type" title="BoundedType">bounded types</a>).</p>
65<p>The central difficulty emerges in the details of
66        <code class="computeroutput">variant</code> assignment. Given two instances <code class="computeroutput">v1</code>
67        and <code class="computeroutput">v2</code> of some concrete <code class="computeroutput">variant</code> type, there
68        are two distinct, fundamental cases we must consider for the assignment
69        <code class="computeroutput">v1 = v2</code>.</p>
70<p>First consider the case that <code class="computeroutput">v1</code> and <code class="computeroutput">v2</code>
71        each contains a value of the same type. Call this type <code class="computeroutput">T</code>.
72        In this situation, assignment is perfectly straightforward: use
73        <code class="computeroutput">T::operator=</code>.</p>
74<p>However, we must also consider the case that <code class="computeroutput">v1</code> and
75        <code class="computeroutput">v2</code> contain values <span class="emphasis"><em>of distinct types</em></span>.
76        Call these types <code class="computeroutput">T</code> and <code class="computeroutput">U</code>. At this point,
77        since <code class="computeroutput">variant</code> manages its content on the stack, the
78        left-hand side of the assignment (i.e., <code class="computeroutput">v1</code>) must destroy
79        its content so as to permit in-place copy-construction of the content
80        of the right-hand side (i.e., <code class="computeroutput">v2</code>). In the end, whereas
81        <code class="computeroutput">v1</code> began with content of type <code class="computeroutput">T</code>, it ends
82        with content of type <code class="computeroutput">U</code>, namely a copy of the content of
83        <code class="computeroutput">v2</code>.</p>
84<p>The crux of the problem, then, is this: in the event that
85        copy-construction of the content of <code class="computeroutput">v2</code> fails, how can
86        <code class="computeroutput">v1</code> maintain its "never-empty" guarantee?
87        By the time copy-construction from <code class="computeroutput">v2</code> is attempted,
88        <code class="computeroutput">v1</code> has already destroyed its content!</p>
89</div>
90<div class="section" lang="en">
91<div class="titlepage"><div><div><h4 class="title">
92<a name="variant.design.never-empty.memcpy-solution"></a>The "Ideal" Solution: False Hopes</h4></div></div></div>
93<p>Upon learning of this dilemma, clever individuals may propose the
94        following scheme hoping to solve the problem:
95
96        </p>
97<div class="orderedlist"><ol type="1">
98<li>Provide some "backup" storage, appropriately
99            aligned, capable of holding values of the contained type of the
100            left-hand side.</li>
101<li>Copy the memory (e.g., using <code class="computeroutput">memcpy</code>) of the
102            storage of the left-hand side to the backup storage.</li>
103<li>Attempt a copy of the right-hand side content to the
104            (now-replicated) left-hand side storage.</li>
105<li>In the event of an exception from the copy, restore the
106            backup (i.e., copy the memory from the backup storage back into
107            the left-hand side storage).</li>
108<li>Otherwise, in the event of success, now copy the memory
109            of the left-hand side storage to another "temporary"
110            aligned storage.</li>
111<li>Now restore the backup (i.e., again copying the memory)
112            to the left-hand side storage; with the "old" content
113            now restored, invoke the destructor of the contained type on the
114            storage of the left-hand side.</li>
115<li>Finally, copy the memory of the temporary storage to the
116            (now-empty) storage of the left-hand side.</li>
117</ol></div>
118<p>
119      </p>
120<p>While complicated, it appears such a scheme could provide the
121        desired safety in a relatively efficient manner. In fact, several
122        early iterations of the library implemented this very approach.</p>
123<p>Unfortunately, as Dave Abraham's first noted, the scheme results
124        in undefined behavior:
125
126        </p>
127<div class="blockquote"><blockquote class="blockquote">
128<p>"That's a lot of code to read through, but if it's
129            doing what I think it's doing, it's undefined behavior.</p>
130<p>"Is the trick to move the bits for an existing object
131            into a buffer so we can tentatively construct a new object in
132            that memory, and later move the old bits back temporarily to
133            destroy the old object?</p>
134<p>"The standard does not give license to do that: only one
135            object may have a given address at a time. See 3.8, and
136            particularly paragraph 4."</p>
137</blockquote></div>
138<p>
139      </p>
140<p>Additionally, as close examination quickly reveals, the scheme has
141        the potential to create irreconcilable race-conditions in concurrent
142        environments.</p>
143<p>Ultimately, even if the above scheme could be made to work on
144        certain platforms with particular compilers, it is still necessary to
145        find a portable solution.</p>
146</div>
147<div class="section" lang="en">
148<div class="titlepage"><div><div><h4 class="title">
149<a name="variant.design.never-empty.double-storage-solution"></a>An Initial Solution: Double Storage</h4></div></div></div>
150<p>Upon learning of the infeasibility of the above scheme, Anthony
151        Williams proposed in
152        <a href="refs.html#variant.refs.wil02">[Wil02]</a> a scheme that served
153        as the basis for a portable solution in some pre-release
154        implementations of <code class="computeroutput">variant</code>.</p>
155<p>The essential idea to this scheme, which shall be referred to as
156        the "double storage" scheme, is to provide enough space
157        within a <code class="computeroutput">variant</code> to hold two separate values of any of
158        the bounded types.</p>
159<p>With the secondary storage, a copy the right-hand side can be
160        attempted without first destroying the content of the left-hand side;
161        accordingly, the content of the left-hand side remains available in
162        the event of an exception.</p>
163<p>Thus, with this scheme, the <code class="computeroutput">variant</code> implementation
164        needs only to keep track of which storage contains the content -- and
165        dispatch any visitation requests, queries, etc. accordingly.</p>
166<p>The most obvious flaw to this approach is the space overhead
167        incurred. Though some optimizations could be applied in special cases
168        to eliminate the need for double storage -- for certain bounded types
169        or in some cases entirely (see
170        <a href="design.html#variant.design.never-empty.optimizations" title="Enabling Optimizations">the section called &#8220;Enabling Optimizations&#8221;</a> for more
171        details) -- many users on the Boost mailing list strongly objected to
172        the use of double storage. In particular, it was noted that the
173        overhead of double storage would be at play at all times -- even if
174        assignment to <code class="computeroutput">variant</code> never occurred. For this reason
175        and others, a new approach was developed.</p>
176</div>
177<div class="section" lang="en">
178<div class="titlepage"><div><div><h4 class="title">
179<a name="variant.design.never-empty.heap-backup-solution"></a>Current Approach: Temporary Heap Backup</h4></div></div></div>
180<p>Despite the many objections to the double storage solution, it was
181        realized that no replacement would be without drawbacks. Thus, a
182        compromise was desired.</p>
183<p>To this end, Dave Abrahams suggested to include the following in
184        the behavior specification for <code class="computeroutput">variant</code> assignment:
185        "<code class="computeroutput">variant</code> assignment from one type to another may
186        incur dynamic allocation." That is, while <code class="computeroutput">variant</code> would
187        continue to store its content <span class="emphasis"><em>in situ</em></span> after
188        construction and after assignment involving identical contained types,
189        <code class="computeroutput">variant</code> would store its content on the heap after
190        assignment involving distinct contained types.</p>
191<p>The algorithm for assignment would proceed as follows:
192
193        </p>
194<div class="orderedlist"><ol type="1">
195<li>Copy-construct the content of the right-hand side to the
196            heap; call the pointer to this data <code class="computeroutput">p</code>.</li>
197<li>Destroy the content of the left-hand side.</li>
198<li>Copy <code class="computeroutput">p</code> to the left-hand side
199            storage.</li>
200</ol></div>
201<p>
202
203        Since all operations on pointers are nothrow, this scheme would allow
204        <code class="computeroutput">variant</code> to meet its never-empty guarantee.
205      </p>
206<p>The most obvious concern with this approach is that while it
207        certainly eliminates the space overhead of double storage, it
208        introduces the overhead of dynamic-allocation to <code class="computeroutput">variant</code>
209        assignment -- not just in terms of the initial allocation but also
210        as a result of the continued storage of the content on the heap. While
211        the former problem is unavoidable, the latter problem may be avoided
212        with the following "temporary heap backup" technique:
213
214        </p>
215<div class="orderedlist"><ol type="1">
216<li>Copy-construct the content of the
217            <span class="emphasis"><em>left</em></span>-hand side to the heap; call the pointer to
218            this data <code class="computeroutput">backup</code>.</li>
219<li>Destroy the content of the left-hand side.</li>
220<li>Copy-construct the content of the right-hand side in the
221            (now-empty) storage of the left-hand side.</li>
222<li>In the event of failure, copy <code class="computeroutput">backup</code> to the
223            left-hand side storage.</li>
224<li>In the event of success, deallocate the data pointed to
225            by <code class="computeroutput">backup</code>.</li>
226</ol></div>
227<p>
228      </p>
229<p>With this technique: 1) only a single storage is used;
230        2) allocation is on the heap in the long-term only if the assignment
231        fails; and 3) after any <span class="emphasis"><em>successful</em></span> assignment,
232        storage within the <code class="computeroutput">variant</code> is guaranteed. For the
233        purposes of the initial release of the library, these characteristics
234        were deemed a satisfactory compromise solution.</p>
235<p>There remain notable shortcomings, however. In particular, there
236        may be some users for which heap allocation must be avoided at all
237        costs; for other users, any allocation may need to occur via a
238        user-supplied allocator. These issues will be addressed in the future
239        (see <a href="design.html#variant.design.never-empty.roadmap" title="Future Direction: Policy-based Implementation">the section called &#8220;Future Direction: Policy-based Implementation&#8221;</a>). For now,
240        though, the library treats storage of its content as an implementation
241        detail. Nonetheless, as described in the next section, there
242        <span class="emphasis"><em>are</em></span> certain things the user can do to ensure the
243        greatest efficiency for <code class="computeroutput">variant</code> instances (see
244        <a href="design.html#variant.design.never-empty.optimizations" title="Enabling Optimizations">the section called &#8220;Enabling Optimizations&#8221;</a> for
245        details).</p>
246</div>
247<div class="section" lang="en">
248<div class="titlepage"><div><div><h4 class="title">
249<a name="variant.design.never-empty.optimizations"></a>Enabling Optimizations</h4></div></div></div>
250<p>As described in
251        <a href="design.html#variant.design.never-empty.problem" title="The Implementation Problem">the section called &#8220;The Implementation Problem&#8221;</a>, the central
252        difficulty in implementing the never-empty guarantee is the
253        possibility of failed copy-construction during <code class="computeroutput">variant</code>
254        assignment. Yet types with nothrow copy constructors clearly never
255        face this possibility. Similarly, if one of the bounded types of the
256        <code class="computeroutput">variant</code> is nothrow default-constructible, then such a
257        type could be used as a safe "fallback" type in the event of
258        failed copy construction.</p>
259<p>Accordingly, <code class="computeroutput">variant</code> is designed to enable the
260        following optimizations once the following criteria on its bounded
261        types are met:
262
263        </p>
264<div class="itemizedlist"><ul type="disc">
265<li>For each bounded type <code class="computeroutput">T</code> that is nothrow
266            copy-constructible (as indicated by
267            <code class="computeroutput">boost::has_nothrow_copy</code>), the
268            library guarantees <code class="computeroutput">variant</code> will use only single
269            storage and in-place construction for <code class="computeroutput">T</code>.</li>
270<li>If <span class="emphasis"><em>any</em></span> bounded type is nothrow
271            default-constructible (as indicated by
272            <code class="computeroutput">boost::has_nothrow_constructor</code>),
273            the library guarantees <code class="computeroutput">variant</code> will use only single
274            storage and in-place construction for <span class="emphasis"><em>every</em></span>
275            bounded type in the <code class="computeroutput">variant</code>. Note, however, that in
276            the event of assignment failure, an unspecified nothrow
277            default-constructible bounded type will be default-constructed in
278            the left-hand side operand so as to preserve the never-empty
279            guarantee.</li>
280</ul></div>
281<p>
282
283      </p>
284<p><span class="bold"><strong>Caveat</strong></span>: On most platforms, the
285        Type Traits templates
286        <code class="computeroutput">has_nothrow_copy</code> and <code class="computeroutput">has_nothrow_constructor</code>
287        by default return <code class="computeroutput">false</code> for all <code class="computeroutput">class</code> and
288        <code class="computeroutput">struct</code> types. It is necessary therefore to provide
289        specializations of these templates as appropriate for user-defined
290        types, as demonstrated in the following:
291
292</p>
293<pre class="programlisting">// ...in your code (at file scope)...
294
295namespace boost {
296
297  template &lt;&gt;
298  struct <code class="computeroutput">has_nothrow_copy</code>&lt; myUDT &gt;
299    : <code class="computeroutput">mpl::true_</code>
300  {
301  };
302
303}
304</pre>
305<p>
306
307      </p>
308<p><span class="bold"><strong>Implementation Note</strong></span>: So as to make
309        the behavior of <code class="computeroutput">variant</code> more predictable in the aftermath
310        of an exception, the current implementation prefers to default-construct
311        <code class="computeroutput">boost::blank</code> if specified as a
312        bounded type instead of other nothrow default-constructible bounded
313        types. (If this is deemed to be a useful feature, it will become part
314        of the specification for <code class="computeroutput">variant</code>; otherwise, it may be
315        obsoleted. Please provide feedback to the Boost mailing list.)</p>
316</div>
317<div class="section" lang="en">
318<div class="titlepage"><div><div><h4 class="title">
319<a name="variant.design.never-empty.roadmap"></a>Future Direction: Policy-based Implementation</h4></div></div></div>
320<p>As the previous sections have demonstrated, much effort has been
321        expended in an attempt to provide a balance between performance, data
322        size, and heap usage. Further, significant optimizations may be
323        enabled in <code class="computeroutput">variant</code> on the basis of certain traits of its
324        bounded types.</p>
325<p>However, there will be some users for whom the chosen compromise
326        is unsatisfactory (e.g.: heap allocation must be avoided at all costs;
327        if heap allocation is used, custom allocators must be used; etc.). For
328        this reason, a future version of the library will support a
329        policy-based implementation of <code class="computeroutput">variant</code>. While this will
330        not eliminate the problems described in the previous sections, it will
331        allow the decisions regarding tradeoffs to be decided by the user
332        rather than the library designers.</p>
333</div>
334</div>
335</div>
336<table width="100%"><tr>
337<td align="left"></td>
338<td align="right"><small>Copyright © 2002, 2003 Eric Friedman, Itay Maman</small></td>
339</tr></table>
340<hr>
341<div class="spirit-nav">
342<a accesskey="p" href="../boost/visitor_ptr.html"><img src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../variant.html"><img src="../images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../images/home.png" alt="Home"></a><a accesskey="n" href="misc.html"><img src="../images/next.png" alt="Next"></a>
343</div>
344</body>
345</html>
Note: See TracBrowser for help on using the repository browser.