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