ceph/src/boost/libs/preprocessor/doc/topics/reentrancy.html

   1 <html>
   2         <head>
   3                 <title>reentrancy.html</title>
   4                 <link rel="stylesheet" type="text/css" href="../styles.css">
   5         </head>
   6         <body>
   7                 <h4>
   8                         Reentrancy
   9                 </h4>
  10                 <div>
  11                         Macro expansion in the preprocessor is entirely functional.&nbsp; Therefore,
  12                         there is no iteration.&nbsp; Unfortunately, the preprocessor also disallows
  13                         recursion.&nbsp; This means that the library must fake iteration or recursion
  14                         by defining sets of macros that are implemented similarly.&nbsp;
  15                 </div>
  16                 <div>
  17                         To illustrate, here is a simple concatenation macro:
  18                 </div>
  19                 <div class="code">
  20                         <pre>
  21 #define CONCAT(a, b) CONCAT_D(a, b)
  22 #define CONCAT_D(a, b) a ## b
  23
  24 CONCAT(a, CONCAT(b, c)) // abc
  25 </pre>
  26                 </div>
  27                 <div>
  28                         This is fine for a simple case like the above, but what happens in a scenario
  29                         like the following:
  30                 </div>
  31                 <div class="code">
  32                         <pre>
  33 #define AB(x, y) CONCAT(x, y)
  34
  35 CONCAT(A, B(p, q)) // CONCAT(p, q)
  36 </pre>
  37                 </div>
  38                 <div>
  39                         Because there is no recursion, the example above expands to <code>CONCAT(p, q)</code>
  40                         rather than <code>pq</code>.
  41                 </div>
  42                 <div>
  43                         There are only two ways to "fix" the above.&nbsp; First, it can be documented
  44                         that <code>AB</code> uses <code>CONCAT</code> and disallow usage similar to the
  45                         above.&nbsp; Second, multiple concatenation macros can be provided....
  46                 </div>
  47                 <div class="code">
  48                         <pre>
  49 #define CONCAT_1(a, b) CONCAT_1_D(a, b)
  50 #define CONCAT_1_D(a, b) a ## b
  51
  52 #define CONCAT_2(a, b) CONCAT_2_D(a, b)
  53 #define CONCAT_2_D(a, b) a ## b
  54
  55 #define AB(x, y) CONCAT_2(x, y)
  56
  57 CONCAT_1(A, B(p, q)) // pq
  58 </pre>
  59                 </div>
  60                 <div>
  61                         This solves the problem.&nbsp; However, it is now necessary to know that <code>AB</code>
  62                         uses, not only <i>a</i> concatenation macro, but <code>CONCAT_2</code> specifically.
  63                 </div>
  64                 <div>
  65                         A better solution is to abstract <i>which</i> concatenation macro is used....
  66                 </div>
  67                 <div class="code">
  68                         <pre>
  69 #define AB(c, x, y) CONCAT_ ## c(x, y)
  70
  71 CONCAT_1(A, B(2, p, q)) // pq
  72 </pre>
  73                 </div>
  74                 <div>
  75                         This is an example of <i>generic reentrance</i>, in this case, into a fictional
  76                         set of concatenation macros.&nbsp; The <code>c</code> parameter represents the
  77                         "state" of the concatenation construct, and as long as the user keeps track of
  78                         this state, <code>AB</code> can be used inside of a concatenation macro.
  79                 </div>
  80                 <div>
  81                         The library has the same choices.&nbsp; It either has to disallow a construct
  82                         being inside itself or provide multiple, equivalent definitions of a construct
  83                         and provide a uniform way to <i>reenter</i> that construct.&nbsp; There are
  84                         several contructs that <i>require</i> recursion (such as <b>BOOST_PP_WHILE</b>).&nbsp;
  85                         Consequently, the library chooses to provide several sets of macros with
  86                         mechanisms to reenter the set at a macro that has not already been used.
  87                 </div>
  88                 <div>
  89                         In particular, the library must provide reentrance for <b>BOOST_PP_FOR</b>, <b>BOOST_PP_REPEAT</b>,
  90                         and <b>BOOST_PP_WHILE</b>.&nbsp; There are two mechanisms that are used to
  91                         accomplish this:&nbsp; state parameters (like the above concatenation example)
  92                         and <i>automatic recursion</i>.
  93                 </div>
  94                 <h4>
  95                         State Parameters
  96                 </h4>
  97                 <div>
  98                         Each of the above constructs (<b>BOOST_PP_FOR</b>, <b>BOOST_PP_REPEAT</b>, and <b>BOOST_PP_WHILE</b>)
  99                         has an associated state.&nbsp; This state provides the means to reenter the
 100                         respective construct.
 101                 </div>
 102                 <div>
 103                         Several user-defined macros are passed to each of these constructs (for use as
 104                         predicates, operations, etc.).&nbsp; Every time a user-defined macro is
 105                         invoked, it is passed the current state of the construct that invoked it so
 106                         that the macro can reenter the respective set if necessary.
 107                 </div>
 108                 <div>
 109                         These states are used in one of two ways--either by concatenating to or passing
 110                         to another macro.
 111                 </div>
 112                 <div>
 113                         There are three types of macros that use these state parameters.&nbsp; First,
 114                         the set itself which is reentered through concatenation.&nbsp; Second,
 115                         corresponding sets that act like they are a part of the the primary set.&nbsp;
 116                         These are also reentered through concatenation.&nbsp; And third, macros that
 117                         internally use the first or second type of macro.&nbsp; These macros take the
 118                         state as an additional argument.
 119                 </div>
 120                 <div>
 121                         The state of <b>BOOST_PP_WHILE</b> is symbolized by the letter <i>D</i>.&nbsp;
 122                         Two user-defined macros are passed to <b>BOOST_PP_WHILE</b>--a predicate and an
 123                         operation.&nbsp; When <b>BOOST_PP_WHILE</b> expands these macros, it passes
 124                         along its state so that these macros can reenter the <b>BOOST_PP_WHILE</b> set.&nbsp;
 125                 </div>
 126                 <div>
 127                         Consider the following multiplication implementation that illustrates this
 128                         technique:
 129                 </div>
 130                 <div class="code">
 131                         <pre>
 132 // The addition interface macro.
 133 // The _D signifies that it reenters
 134 // BOOST_PP_WHILE with concatenation.
 135
 136 #define ADD_D(d, x, y) \
 137    BOOST_PP_TUPLE_ELEM( \
 138       2, 0, \
 139       BOOST_PP_WHILE_ ## d(ADD_P, ADD_O, (x, y)) \
 140    ) \
 141    /**/
 142
 143 // The predicate that is passed to BOOST_PP_WHILE.
 144 // It returns "true" until "y" becomes zero.
 145
 146 #define ADD_P(d, xy) BOOST_PP_TUPLE_ELEM(2, 1, xy)
 147
 148 // The operation that is passed to BOOST_PP_WHILE.
 149 // It increments "x" and decrements "y" which will
 150 // eventually cause "y" to equal zero and therefore
 151 // cause the predicate to return "false."
 152
 153 #define ADD_O(d, xy) \
 154    ( \
 155       BOOST_PP_INC( \
 156          BOOST_PP_TUPLE_ELEM(2, 0, xy) \
 157       ), \
 158       BOOST_PP_DEC( \
 159          BOOST_PP_TUPLE_ELEM(2, 1, xy) \
 160       ) \
 161    ) \
 162    /**/
 163
 164 // The multiplication interface macro.
 165
 166 #define MUL(x, y) \
 167    BOOST_PP_TUPLE_ELEM( \
 168       3, 0, \
 169       BOOST_PP_WHILE(MUL_P, MUL_O, (0, x, y)) \
 170    ) \
 171    /**/
 172
 173 // The predicate that is passed to BOOST_PP_WHILE.
 174 // It returns "true" until "y" becomes zero.
 175
 176 #define MUL_P(d, rxy) BOOST_PP_TUPLE_ELEM(3, 2, rxy)
 177
 178 // The operation that is passed to BOOST_PP_WHILE.
 179 // It adds "x" to "r" and decrements "y" which will
 180 // eventually cause "y" to equal zero and therefore
 181 // cause the predicate to return "false."
 182
 183 #define MUL_O(d, rxy) \
 184    ( \
 185       ADD_D( \
 186          d, /* pass the state on to ADD_D */ \
 187          BOOST_PP_TUPLE_ELEM(3, 0, rxy), \
 188          BOOST_PP_TUPLE_ELEM(3, 1, rxy) \
 189       ), \
 190       BOOST_PP_TUPLE_ELEM(3, 1, rxy), \
 191       BOOST_PP_DEC( \
 192          BOOST_PP_TUPLE_ELEM(3, 2, rxy) \
 193       ) \
 194    ) \
 195    /**/
 196
 197 MUL(3, 2) // expands to 6
 198 </pre>
 199                 </div>
 200                 <div>
 201                         There are a couple things to note in the above implementation.&nbsp; First,
 202                         note how <code>ADD_D</code> reenters <b>BOOST_PP_WHILE</b> using the <i>d</i> state
 203                         parameter.&nbsp; Second, note how <code>MUL</code>'s operation, which is
 204                         expanded by <b>BOOST_PP_WHILE</b>, passes the state on to <code>ADD_D</code>.&nbsp;
 205                         This illustrates state reentrance by both argument and concatenation.
 206                 </div>
 207                 <div>
 208                         For every macro in the library that uses <b>BOOST_PP_WHILE</b>, there is a
 209                         state reentrant variant.&nbsp; If that variant uses an argument rather than
 210                         concatenation, it is suffixed by <code>_D</code> to symbolize its method of
 211                         reentrance.&nbsp; Examples or this include the library's own <b>BOOST_PP_ADD_D</b>
 212                         and <b>BOOST_PP_MUL_D</b>.&nbsp; If the variant uses concatenation, it is
 213                         suffixed by an underscore.&nbsp; It is completed by concatenation of the
 214                         state.&nbsp; This includes <b>BOOST_PP_WHILE</b> itself with <b>BOOST_PP_WHILE_</b>
 215                         ## <i>d</i> and, for example, <b>BOOST_PP_LIST_FOLD_LEFT</b> with <b>BOOST_PP_LIST_FOLD_LEFT_</b>
 216                         ## <i>d</i>.
 217                 </div>
 218                 <div>
 219                         The same set of conventions are used for <b>BOOST_PP_FOR</b> and <b>BOOST_PP_REPEAT</b>,
 220                         but with the letters <i>R</i> and <i>Z</i>, respectively, to symbolize their
 221                         states.
 222                 </div>
 223                 <div>
 224                         Also note that the above <code>MUL</code> implementation, though not
 225                         immediately obvious, is using <i>all three</i> types of reentrance.&nbsp; Not
 226                         only is it using both types of <i>state</i> reentrance, it is also using <i>automatic
 227                                 recursion</i>....
 228                 </div>
 229                 <h4>
 230                         Automatic Recursion
 231                 </h4>
 232                 <div>
 233                         Automatic recursion is a technique that vastly simplifies the use of reentrant
 234                         constructs.&nbsp; It is used by simply <i>not</i> using any state parameters at
 235                         all.
 236                 </div>
 237                 <div>
 238                         The <code>MUL</code> example above uses automatic recursion when it uses <b>BOOST_PP_WHILE</b>
 239                         by itself.&nbsp; In other words, <code>MUL</code> can <i>still</i> be used
 240                         inside <b>BOOST_PP_WHILE</b> even though it doesn't reenter <b>BOOST_PP_WHILE</b>
 241                         by concatenating the state to <b>BOOST_PP_WHILE_</b>.
 242                 </div>
 243                 <div>
 244                         To accomplish this, the library uses a "trick."&nbsp; Despite what it looks
 245                         like, the macro <b>BOOST_PP_WHILE</b> does not take three arguments.&nbsp; In
 246                         fact, it takes no arguments at all.&nbsp; Instead, the <b>BOOST_PP_WHILE</b> macro
 247                         expands <i>to</i> a macro that takes three arguments.&nbsp; It simply detects
 248                         what the next available <b>BOOST_PP_WHILE_</b> ## <i>d</i> macro is and returns
 249                         it.&nbsp; This detection process is somewhat involved, so I won't go into <i>how</i>
 250                         it works here, but suffice to say it <i>does</i> work.
 251                 </div>
 252                 <div>
 253                         Using automatic recursion to reenter various sets of macros is obviously much
 254                         simpler.&nbsp; It completely hides the underlying implementation details.&nbsp;
 255                         So, if it is so much easier to use, why do the state parameters still
 256                         exist?&nbsp; The reason is simple as well.&nbsp; When state parameters are
 257                         used, the state is <i>known</i> at all times.&nbsp; This is not the case when
 258                         automatic recursion is used.&nbsp; The automatic recursion mechanism has to <i>deduce</i>
 259                         the state at each point that it is used.&nbsp; This implies a cost in macro
 260                         complexity that in some situations--notably at deep macro depths--will slow
 261                         some preprocessors to a crawl.
 262                 </div>
 263                 <h4>
 264                         Conclusion
 265                 </h4>
 266                 <div>
 267                         It is really a tradeoff whether to use state parameters or automatic recursion
 268                         for reentrancy.&nbsp; The strengths of automatic recursion are ease of use and
 269                         implementation encapsulation.&nbsp; These come at a performance cost on some
 270                         preprocessors in some situations.&nbsp; The primary strength of state
 271                         parameters, on the other hand, is efficiency.&nbsp; Use of the state parameters
 272                         is the only way to achieve <i>maximum</i> efficiency.&nbsp; This efficiency
 273                         comes at the cost of both code complexity and exposition of implementation.
 274                 </div>
 275                 <h4>
 276                         See Also
 277                 </h4>
 278                 <ul>
 279                         <li><a href="../ref/for.html">BOOST_PP_FOR</a></li>
 280                         <li><a href="../ref/repeat.html">BOOST_PP_REPEAT</a></li>
 281                         <li><a href="../ref/while.html">BOOST_PP_WHILE</a></li>
 282                 </ul>
 283                 <div class="sig">
 284                         - Paul Mensonides
 285                 </div>
 286         <hr size="1">
 287         <div style="margin-left: 0px;">
 288                 <i>© Copyright <a href="http://www.housemarque.com" target="_top">Housemarque Oy</a> 2002</i>
 289                 </br><i>© Copyright Paul Mensonides 2002</i>
 290         </div>
 291         <div style="margin-left: 0px;">
 292                 <p><small>Distributed under the Boost Software License, Version 1.0. (See
 293                 accompanying file <a href="../../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
 294                 copy at <a href=
 295                 "http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</small></p>
 296         </div>
 297         </body>
 298 </html>