summaryrefslogtreecommitdiff
path: root/doc/html/variant/design.html
blob: 6e04aea9847e553350b2e8bc21637c78243d70b9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Design Overview</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../variant.html" title="Chapter&#160;42.&#160;Boost.Variant">
<link rel="prev" href="../boost/visitor_ptr.html" title="Function template visitor_ptr">
<link rel="next" href="misc.html" title="Miscellaneous Notes">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../boost/visitor_ptr.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../variant.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="misc.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="variant.design"></a>Design Overview</h2></div></div></div>
<div class="toc"><dl class="toc"><dt><span class="section"><a href="design.html#variant.design.never-empty">"Never-Empty" Guarantee</a></span></dt></dl></div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="variant.design.never-empty"></a>"Never-Empty" Guarantee</h3></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="design.html#variant.design.never-empty.guarantee">The Guarantee</a></span></dt>
<dt><span class="section"><a href="design.html#variant.design.never-empty.problem">The Implementation Problem</a></span></dt>
<dt><span class="section"><a href="design.html#variant.design.never-empty.memcpy-solution">The "Ideal" Solution: False Hopes</a></span></dt>
<dt><span class="section"><a href="design.html#variant.design.never-empty.double-storage-solution">An Initial Solution: Double Storage</a></span></dt>
<dt><span class="section"><a href="design.html#variant.design.never-empty.heap-backup-solution">Current Approach: Temporary Heap Backup</a></span></dt>
<dt><span class="section"><a href="design.html#variant.design.never-empty.optimizations">Enabling Optimizations</a></span></dt>
<dt><span class="section"><a href="design.html#variant.design.never-empty.roadmap">Future Direction: Policy-based Implementation</a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="variant.design.never-empty.guarantee"></a>The Guarantee</h4></div></div></div>
<p>All instances <code class="computeroutput">v</code> of type
        <code class="computeroutput"><a class="link" href="../boost/variant.html" title="Class template variant">variant</a>&lt;T1,T2,...,TN&gt;</code>
        guarantee that <code class="computeroutput">v</code> has constructed content of one of the
        types <code class="computeroutput">T<span class="emphasis"><em>i</em></span></code>, even if an operation on
        <code class="computeroutput">v</code> has previously failed.</p>
<p>This implies that <code class="computeroutput">variant</code> may be viewed precisely as
        a union of <span class="emphasis"><em>exactly</em></span> its bounded types. This
        "never-empty" property insulates the user from the
        possibility of undefined <code class="computeroutput">variant</code> content and the
        significant additional complexity-of-use attendant with such a
        possibility.</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="variant.design.never-empty.problem"></a>The Implementation Problem</h4></div></div></div>
<p>While the
        <a class="link" href="design.html#variant.design.never-empty.guarantee" title="The Guarantee">never-empty guarantee</a>
        might at first seem "obvious," it is in fact not even
        straightforward how to implement it in general (i.e., without
        unreasonably restrictive additional requirements on
        <a class="link" href="reference.html#variant.concepts.bounded-type" title="BoundedType">bounded types</a>).</p>
<p>The central difficulty emerges in the details of
        <code class="computeroutput">variant</code> assignment. Given two instances <code class="computeroutput">v1</code>
        and <code class="computeroutput">v2</code> of some concrete <code class="computeroutput">variant</code> type, there
        are two distinct, fundamental cases we must consider for the assignment
        <code class="computeroutput">v1 = v2</code>.</p>
<p>First consider the case that <code class="computeroutput">v1</code> and <code class="computeroutput">v2</code>
        each contains a value of the same type. Call this type <code class="computeroutput">T</code>.
        In this situation, assignment is perfectly straightforward: use
        <code class="computeroutput">T::operator=</code>.</p>
<p>However, we must also consider the case that <code class="computeroutput">v1</code> and
        <code class="computeroutput">v2</code> contain values <span class="emphasis"><em>of distinct types</em></span>.
        Call these types <code class="computeroutput">T</code> and <code class="computeroutput">U</code>. At this point,
        since <code class="computeroutput">variant</code> manages its content on the stack, the
        left-hand side of the assignment (i.e., <code class="computeroutput">v1</code>) must destroy
        its content so as to permit in-place copy-construction of the content
        of the right-hand side (i.e., <code class="computeroutput">v2</code>). In the end, whereas
        <code class="computeroutput">v1</code> began with content of type <code class="computeroutput">T</code>, it ends
        with content of type <code class="computeroutput">U</code>, namely a copy of the content of
        <code class="computeroutput">v2</code>.</p>
<p>The crux of the problem, then, is this: in the event that
        copy-construction of the content of <code class="computeroutput">v2</code> fails, how can
        <code class="computeroutput">v1</code> maintain its "never-empty" guarantee?
        By the time copy-construction from <code class="computeroutput">v2</code> is attempted,
        <code class="computeroutput">v1</code> has already destroyed its content!</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="variant.design.never-empty.memcpy-solution"></a>The "Ideal" Solution: False Hopes</h4></div></div></div>
<p>Upon learning of this dilemma, clever individuals may propose the
        following scheme hoping to solve the problem:

        </p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">Provide some "backup" storage, appropriately
            aligned, capable of holding values of the contained type of the
            left-hand side.</li>
<li class="listitem">Copy the memory (e.g., using <code class="computeroutput">memcpy</code>) of the
            storage of the left-hand side to the backup storage.</li>
<li class="listitem">Attempt a copy of the right-hand side content to the
            (now-replicated) left-hand side storage.</li>
<li class="listitem">In the event of an exception from the copy, restore the
            backup (i.e., copy the memory from the backup storage back into
            the left-hand side storage).</li>
<li class="listitem">Otherwise, in the event of success, now copy the memory
            of the left-hand side storage to another "temporary"
            aligned storage.</li>
<li class="listitem">Now restore the backup (i.e., again copying the memory)
            to the left-hand side storage; with the "old" content
            now restored, invoke the destructor of the contained type on the
            storage of the left-hand side.</li>
<li class="listitem">Finally, copy the memory of the temporary storage to the
            (now-empty) storage of the left-hand side.</li>
</ol></div>
<p>
      </p>
<p>While complicated, it appears such a scheme could provide the
        desired safety in a relatively efficient manner. In fact, several
        early iterations of the library implemented this very approach.</p>
<p>Unfortunately, as Dave Abraham's first noted, the scheme results
        in undefined behavior:

        </p>
<div class="blockquote"><blockquote class="blockquote">
<p>"That's a lot of code to read through, but if it's
            doing what I think it's doing, it's undefined behavior.</p>
<p>"Is the trick to move the bits for an existing object
            into a buffer so we can tentatively construct a new object in
            that memory, and later move the old bits back temporarily to
            destroy the old object?</p>
<p>"The standard does not give license to do that: only one
            object may have a given address at a time. See 3.8, and
            particularly paragraph 4."</p>
</blockquote></div>
<p>
      </p>
<p>Additionally, as close examination quickly reveals, the scheme has
        the potential to create irreconcilable race-conditions in concurrent
        environments.</p>
<p>Ultimately, even if the above scheme could be made to work on
        certain platforms with particular compilers, it is still necessary to
        find a portable solution.</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="variant.design.never-empty.double-storage-solution"></a>An Initial Solution: Double Storage</h4></div></div></div>
<p>Upon learning of the infeasibility of the above scheme, Anthony
        Williams proposed in
        <a class="link" href="refs.html#variant.refs.wil02">[Wil02]</a> a scheme that served
        as the basis for a portable solution in some pre-release
        implementations of <code class="computeroutput">variant</code>.</p>
<p>The essential idea to this scheme, which shall be referred to as
        the "double storage" scheme, is to provide enough space
        within a <code class="computeroutput">variant</code> to hold two separate values of any of
        the bounded types.</p>
<p>With the secondary storage, a copy the right-hand side can be
        attempted without first destroying the content of the left-hand side;
        accordingly, the content of the left-hand side remains available in
        the event of an exception.</p>
<p>Thus, with this scheme, the <code class="computeroutput">variant</code> implementation
        needs only to keep track of which storage contains the content -- and
        dispatch any visitation requests, queries, etc. accordingly.</p>
<p>The most obvious flaw to this approach is the space overhead
        incurred. Though some optimizations could be applied in special cases
        to eliminate the need for double storage -- for certain bounded types
        or in some cases entirely (see
        <a class="xref" href="design.html#variant.design.never-empty.optimizations" title="Enabling Optimizations">the section called &#8220;Enabling Optimizations&#8221;</a> for more
        details) -- many users on the Boost mailing list strongly objected to
        the use of double storage. In particular, it was noted that the
        overhead of double storage would be at play at all times -- even if
        assignment to <code class="computeroutput">variant</code> never occurred. For this reason
        and others, a new approach was developed.</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="variant.design.never-empty.heap-backup-solution"></a>Current Approach: Temporary Heap Backup</h4></div></div></div>
<p>Despite the many objections to the double storage solution, it was
        realized that no replacement would be without drawbacks. Thus, a
        compromise was desired.</p>
<p>To this end, Dave Abrahams suggested to include the following in
        the behavior specification for <code class="computeroutput">variant</code> assignment:
        "<code class="computeroutput">variant</code> assignment from one type to another may
        incur dynamic allocation." That is, while <code class="computeroutput">variant</code> would
        continue to store its content <span class="emphasis"><em>in situ</em></span> after
        construction and after assignment involving identical contained types,
        <code class="computeroutput">variant</code> would store its content on the heap after
        assignment involving distinct contained types.</p>
<p>The algorithm for assignment would proceed as follows:

        </p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">Copy-construct the content of the right-hand side to the
            heap; call the pointer to this data <code class="computeroutput">p</code>.</li>
<li class="listitem">Destroy the content of the left-hand side.</li>
<li class="listitem">Copy <code class="computeroutput">p</code> to the left-hand side
            storage.</li>
</ol></div>
<p>

        Since all operations on pointers are nothrow, this scheme would allow
        <code class="computeroutput">variant</code> to meet its never-empty guarantee.
      </p>
<p>The most obvious concern with this approach is that while it
        certainly eliminates the space overhead of double storage, it
        introduces the overhead of dynamic-allocation to <code class="computeroutput">variant</code>
        assignment -- not just in terms of the initial allocation but also
        as a result of the continued storage of the content on the heap. While
        the former problem is unavoidable, the latter problem may be avoided
        with the following "temporary heap backup" technique:

        </p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">Copy-construct the content of the
            <span class="emphasis"><em>left</em></span>-hand side to the heap; call the pointer to
            this data <code class="computeroutput">backup</code>.</li>
<li class="listitem">Destroy the content of the left-hand side.</li>
<li class="listitem">Copy-construct the content of the right-hand side in the
            (now-empty) storage of the left-hand side.</li>
<li class="listitem">In the event of failure, copy <code class="computeroutput">backup</code> to the
            left-hand side storage.</li>
<li class="listitem">In the event of success, deallocate the data pointed to
            by <code class="computeroutput">backup</code>.</li>
</ol></div>
<p>
      </p>
<p>With this technique: 1) only a single storage is used;
        2) allocation is on the heap in the long-term only if the assignment
        fails; and 3) after any <span class="emphasis"><em>successful</em></span> assignment,
        storage within the <code class="computeroutput">variant</code> is guaranteed. For the
        purposes of the initial release of the library, these characteristics
        were deemed a satisfactory compromise solution.</p>
<p>There remain notable shortcomings, however. In particular, there
        may be some users for which heap allocation must be avoided at all
        costs; for other users, any allocation may need to occur via a
        user-supplied allocator. These issues will be addressed in the future
        (see <a class="xref" 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,
        though, the library treats storage of its content as an implementation
        detail. Nonetheless, as described in the next section, there
        <span class="emphasis"><em>are</em></span> certain things the user can do to ensure the
        greatest efficiency for <code class="computeroutput">variant</code> instances (see
        <a class="xref" href="design.html#variant.design.never-empty.optimizations" title="Enabling Optimizations">the section called &#8220;Enabling Optimizations&#8221;</a> for
        details).</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="variant.design.never-empty.optimizations"></a>Enabling Optimizations</h4></div></div></div>
<p>As described in
        <a class="xref" href="design.html#variant.design.never-empty.problem" title="The Implementation Problem">the section called &#8220;The Implementation Problem&#8221;</a>, the central
        difficulty in implementing the never-empty guarantee is the
        possibility of failed copy-construction during <code class="computeroutput">variant</code>
        assignment. Yet types with nothrow copy constructors clearly never
        face this possibility. Similarly, if one of the bounded types of the
        <code class="computeroutput">variant</code> is nothrow default-constructible, then such a
        type could be used as a safe "fallback" type in the event of
        failed copy construction.</p>
<p>Accordingly, <code class="computeroutput">variant</code> is designed to enable the
        following optimizations once the following criteria on its bounded
        types are met:

        </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">For each bounded type <code class="computeroutput">T</code> that is nothrow
            copy-constructible (as indicated by
            <code class="computeroutput">boost::has_nothrow_copy</code>), the
            library guarantees <code class="computeroutput">variant</code> will use only single
            storage and in-place construction for <code class="computeroutput">T</code>.</li>
<li class="listitem">If <span class="emphasis"><em>any</em></span> bounded type is nothrow
            default-constructible (as indicated by
            <code class="computeroutput">boost::has_nothrow_constructor</code>),
            the library guarantees <code class="computeroutput">variant</code> will use only single
            storage and in-place construction for <span class="emphasis"><em>every</em></span>
            bounded type in the <code class="computeroutput">variant</code>. Note, however, that in
            the event of assignment failure, an unspecified nothrow
            default-constructible bounded type will be default-constructed in
            the left-hand side operand so as to preserve the never-empty
            guarantee.</li>
</ul></div>
<p>

      </p>
<p><span class="bold"><strong>Implementation Note</strong></span>: So as to make
        the behavior of <code class="computeroutput">variant</code> more predictable in the aftermath
        of an exception, the current implementation prefers to default-construct
        <code class="computeroutput">boost::blank</code> if specified as a
        bounded type instead of other nothrow default-constructible bounded
        types. (If this is deemed to be a useful feature, it will become part
        of the specification for <code class="computeroutput">variant</code>; otherwise, it may be
        obsoleted. Please provide feedback to the Boost mailing list.)</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="variant.design.never-empty.roadmap"></a>Future Direction: Policy-based Implementation</h4></div></div></div>
<p>As the previous sections have demonstrated, much effort has been
        expended in an attempt to provide a balance between performance, data
        size, and heap usage. Further, significant optimizations may be
        enabled in <code class="computeroutput">variant</code> on the basis of certain traits of its
        bounded types.</p>
<p>However, there will be some users for whom the chosen compromise
        is unsatisfactory (e.g.: heap allocation must be avoided at all costs;
        if heap allocation is used, custom allocators must be used; etc.). For
        this reason, a future version of the library will support a
        policy-based implementation of <code class="computeroutput">variant</code>. While this will
        not eliminate the problems described in the previous sections, it will
        allow the decisions regarding tradeoffs to be decided by the user
        rather than the library designers.</p>
</div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright &#169; 2002, 2003 Eric Friedman, Itay Maman<p>Distributed under the Boost Software License, Version 1.0.
    (See accompanying file <code class="filename">LICENSE_1_0.txt</code> or copy at 
    <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
    </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../boost/visitor_ptr.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../variant.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="misc.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>