ceph/src/boost/libs/proto/doc/implementation.qbk

   1 [/
   2  / Copyright (c) 2008 Eric Niebler
   3  /
   4  / Distributed under the Boost Software License, Version 1.0. (See accompanying
   5  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6  /]
   7
   8 [section:implementation Appendix D: Implementation Notes]
   9
  10 [section:sfinae Quick-n-Dirty Type Categorization]
  11
  12 Much has already been written about dispatching on type traits using
  13 SFINAE (Substitution Failure Is Not An Error) techniques in C++. There
  14 is a Boost library, Boost.Enable_if, to make the technique idiomatic.
  15 Proto dispatches on type traits extensively, but it doesn't use
  16 `enable_if<>` very often. Rather, it dispatches based on the presence
  17 or absence of nested types, often typedefs for void.
  18
  19 Consider the implementation of `is_expr<>`. It could have been written
  20 as something like this:
  21
  22     template<typename T>
  23     struct is_expr
  24       : is_base_and_derived<proto::some_expr_base, T>
  25     {};
  26
  27 Rather, it is implemented as this:
  28
  29     template<typename T, typename Void = void>
  30     struct is_expr
  31       : mpl::false_
  32     {};
  33
  34     template<typename T>
  35     struct is_expr<T, typename T::proto_is_expr_>
  36       : mpl::true_
  37     {};
  38
  39 This relies on the fact that the specialization will be preferred
  40 if `T` has a nested `proto_is_expr_` that is a typedef for `void`.
  41 All Proto expression types have such a nested typedef.
  42
  43 Why does Proto do it this way? The reason is because, after running
  44 extensive benchmarks while trying to improve compile times, I have
  45 found that this approach compiles faster. It requires exactly one
  46 template instantiation. The other approach requires at least 2:
  47 `is_expr<>` and `is_base_and_derived<>`, plus whatever templates
  48 `is_base_and_derived<>` may instantiate.
  49
  50 [endsect]
  51
  52 [section:function_arity Detecting the Arity of Function Objects]
  53
  54 In several places, Proto needs to know whether or not a function
  55 object `Fun` can be called with certain parameters and take a
  56 fallback action if not. This happens in _callable_context_ and
  57 in the _call_ transform. How does Proto know? It involves some
  58 tricky metaprogramming. Here's how.
  59
  60 Another way of framing the question is by trying to implement
  61 the following `can_be_called<>` Boolean metafunction, which
  62 checks to see if a function object `Fun` can be called with
  63 parameters of type `A` and `B`:
  64
  65     template<typename Fun, typename A, typename B>
  66     struct can_be_called;
  67
  68 First, we define the following `dont_care` struct, which has an
  69 implicit conversion from anything. And not just any implicit
  70 conversion; it has a ellipsis conversion, which is the worst possible
  71 conversion for the purposes of overload resolution:
  72
  73     struct dont_care
  74     {
  75         dont_care(...);
  76     };
  77
  78 We also need some private type known only to us with an overloaded
  79 comma operator (!), and some functions that detect the presence of
  80 this type and return types with different sizes, as follows:
  81
  82     struct private_type
  83     {
  84         private_type const &operator,(int) const;
  85     };
  86
  87     typedef char yes_type;      // sizeof(yes_type) == 1
  88     typedef char (&no_type)[2]; // sizeof(no_type)  == 2
  89
  90     template<typename T>
  91     no_type is_private_type(T const &);
  92
  93     yes_type is_private_type(private_type const &);
  94
  95 Next, we implement a binary function object wrapper with a very
  96 strange conversion operator, whose meaning will become clear later.
  97
  98     template<typename Fun>
  99     struct funwrap2 : Fun
 100     {
 101         funwrap2();
 102         typedef private_type const &(*pointer_to_function)(dont_care, dont_care);
 103         operator pointer_to_function() const;
 104     };
 105
 106 With all of these bits and pieces, we can implement `can_be_called<>` as
 107 follows:
 108
 109     template<typename Fun, typename A, typename B>
 110     struct can_be_called
 111     {
 112         static funwrap2<Fun> &fun;
 113         static A &a;
 114         static B &b;
 115
 116         static bool const value = (
 117             sizeof(no_type) == sizeof(is_private_type( (fun(a,b), 0) ))
 118         );
 119
 120         typedef mpl::bool_<value> type;
 121     };
 122
 123 The idea is to make it so that `fun(a,b)` will always compile by adding
 124 our own binary function overload, but doing it in such a way that we can
 125 detect whether our overload was selected or not. And we rig it so that
 126 our overload is selected if there is really no better option. What follows
 127 is a description of how `can_be_called<>` works.
 128
 129 We wrap `Fun` in a type that has an implicit conversion to a pointer to
 130 a binary function. An object `fun` of class type can be invoked as
 131 `fun(a, b)` if it has such a conversion operator, but since it involves
 132 a user-defined conversion operator, it is less preferred than an
 133 overloaded `operator()`, which requires no such conversion.
 134
 135 The function pointer can accept any two arguments by virtue
 136 of the `dont_care` type. The conversion sequence for each argument is
 137 guaranteed to be the worst possible conversion sequence: an implicit
 138 conversion through an ellipsis, and a user-defined conversion to
 139 `dont_care`. In total, it means that `funwrap2<Fun>()(a, b)` will
 140 always compile, but it will select our overload only if there really is
 141 no better option.
 142
 143 If there is a better option --- for example if `Fun` has an overloaded
 144 function call operator such as `void operator()(A a, B b)` --- then
 145 `fun(a, b)` will resolve to that one instead. The question now is how
 146 to detect which function got picked by overload resolution.
 147
 148 Notice how `fun(a, b)` appears in `can_be_called<>`: `(fun(a, b), 0)`.
 149 Why do we use the comma operator there? The reason is because we are
 150 using this expression as the argument to a function. If the return type
 151 of `fun(a, b)` is `void`, it cannot legally be used as an argument to
 152 a function. The comma operator sidesteps the issue.
 153
 154 This should also make plain the purpose of the overloaded comma operator
 155 in `private_type`. The return type of the pointer to function is
 156 `private_type`. If overload resolution selects our overload, then the
 157 type of `(fun(a, b), 0)` is `private_type`. Otherwise, it is `int`.
 158 That fact is used to dispatch to either overload of `is_private_type()`,
 159 which encodes its answer in the size of its return type.
 160
 161 That's how it works with binary functions. Now repeat the above process
 162 for functions up to some predefined function arity, and you're done.
 163
 164 [endsect]
 165
 166 [/
 167     [section:ppmp_vs_tmp Avoiding Template Instiations With The Preprocessor]
 168
 169     TODO
 170
 171     [endsect]
 172 ]
 173
 174 [endsect]