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