libs/variant/doc/design.xml

   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>&quot;Never-Empty&quot; 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>&lt;T1,T2,...,TN&gt;</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         &quot;never-empty&quot; 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 &quot;obvious,&quot; 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 &quot;never-empty&quot; 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 &quot;Ideal&quot; 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 &quot;backup&quot; 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 &quot;temporary&quot;
  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 &quot;old&quot; 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>&quot;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>&quot;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>&quot;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.&quot;</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 &quot;double storage&quot; 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         &quot;<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 &quot;temporary heap backup&quot; 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 &quot;fallback&quot; 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">Caveat</emphasis>: On most platforms, the
 280         <libraryname>Type Traits</libraryname> templates
 281         <code>has_nothrow_copy</code> and <code>has_nothrow_constructor</code>
 282         by default return <code>false</code> for all <code>class</code> and
 283         <code>struct</code> types. It is necessary therefore to provide
 284         specializations of these templates as appropriate for user-defined
 285         types, as demonstrated in the following:
 286
 287 <programlisting>// ...in your code (at file scope)...
 288
 289 namespace boost {
 290
 291   template &lt;&gt;
 292   struct <classname>has_nothrow_copy</classname>&lt; myUDT &gt;
 293     : <classname>mpl::true_</classname>
 294   {
 295   };
 296
 297 }
 298 </programlisting>
 299
 300       </para>
 301
 302       <para><emphasis role="bold">Implementation Note</emphasis>: So as to make
 303         the behavior of <code>variant</code> more predictable in the aftermath
 304         of an exception, the current implementation prefers to default-construct
 305         <code><classname>boost::blank</classname></code> if specified as a
 306         bounded type instead of other nothrow default-constructible bounded
 307         types. (If this is deemed to be a useful feature, it will become part
 308         of the specification for <code>variant</code>; otherwise, it may be
 309         obsoleted. Please provide feedback to the Boost mailing list.)</para>
 310     </section>
 311
 312     <section id="variant.design.never-empty.roadmap">
 313       <title>Future Direction: Policy-based Implementation</title>
 314
 315       <para>As the previous sections have demonstrated, much effort has been
 316         expended in an attempt to provide a balance between performance, data
 317         size, and heap usage. Further, significant optimizations may be
 318         enabled in <code>variant</code> on the basis of certain traits of its
 319         bounded types.</para>
 320
 321       <para>However, there will be some users for whom the chosen compromise
 322         is unsatisfactory (e.g.: heap allocation must be avoided at all costs;
 323         if heap allocation is used, custom allocators must be used; etc.). For
 324         this reason, a future version of the library will support a
 325         policy-based implementation of <code>variant</code>. While this will
 326         not eliminate the problems described in the previous sections, it will
 327         allow the decisions regarding tradeoffs to be decided by the user
 328         rather than the library designers.</para>
 329     </section>
 330
 331   </section>
 332
 333 </section>