libs/iterator/doc/interoperability-revisited.rst

   1 ++++++++++++++++++++++++++++
   2  Interoperability Revisited
   3 ++++++++++++++++++++++++++++
   4
   5 :date: $Date$
   6 :copyright: Copyright Thomas Witt 2004.
   7
   8 .. Distributed under the Boost
   9 .. Software License, Version 1.0. (See accompanying
  10 .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  11
  12 Problem
  13 =======
  14
  15 The current iterator_facade specification makes it unneccessarily tedious to
  16 implement interoperable iterators.
  17
  18 In the following text a simplified example of the current iterator_facade specification is used to
  19 illustrate the problem.
  20
  21 In the current specification binary operators are implemented in the following way::
  22
  23   template <class Derived>
  24   struct Facade
  25   {
  26   };
  27
  28   template <class T1, T2>
  29   struct is_interoperable :
  30     or_<
  31          is_convertible<T1, T2>
  32        , is_convertible<T2, T1>
  33     >
  34   {};
  35
  36   template<
  37       class Derived1
  38     , class Derived2
  39   >
  40   enable_if<is_interoperable<Derived1, Derived2>, bool> operator==(
  41       Derived1 const& lhs
  42     , Derived2 const& rhs
  43   )
  44   {
  45     return static_cast<Derived1 const&>(lhs).equal_to(static_cast<Derived2 const&(rhs));
  46   }
  47
  48 The problem with this is that operator== always forwards to Derived1::equal_to. The net effect is that the
  49 following "obvious" implementation of to interoperable types does
  50 not quite work. ::
  51
  52   struct Mutable : Facade<Mutable>
  53   {
  54     bool equal_to(Mutable const&);
  55   };
  56
  57   struct Constant : Facade<Constant>
  58   {
  59     Constant();
  60     Constant(Constant const&);
  61     Constant(Mutable const&);
  62
  63     ...
  64
  65     bool equal_to(Constant const&);
  66   };
  67
  68   Constant c;
  69   Mutable  m;
  70
  71   c == m; // ok, dispatched to Constant::equal_to
  72   m == c; // !! error, dispatched to Mutable::equal_to
  73
  74   Instead the following "slightly" more complicated implementation is necessary
  75
  76   struct Mutable : Facade<Mutable>
  77   {
  78     template <class T>
  79     enable_if<is_convertible<Mutable, T> || is_convertible<T, Mutable>, bool>::type equal_to(T const&);
  80   };
  81
  82   struct Constant : Tag<Constant>
  83   {
  84     Constant();
  85     Constant(Constant const&);
  86     Constant(Mutable const&);
  87
  88     template <class T>
  89     enable_if<is_convertible<Constant, T> || is_convertible<T, Constant>, bool>::type equal_to(T const&);
  90   };
  91
  92 Beside the fact that the code is significantly more complex to understand and to teach there is
  93 a major design problem lurking here. Note that in both types equal_to is a function template with
  94 an unconstrained argument T. This is necessary so that further types can be made interoperable with
  95 Mutable or Constant. Would Mutable be defined as   ::
  96
  97   struct Mutable : Facade<Mutable>
  98   {
  99     bool equal_to(Mutable const&);
 100     bool equal_to(Constant const&);
 101   };
 102
 103 Constant and Mutable would still be interoperable but no further interoperable could be added
 104 without changing Mutable. Even if this would be considered acceptable the current specification forces
 105 a two way dependency between interoperable types. Note in the templated equal_to case this dependency
 106 is implicitly created when specializing equal_to.
 107
 108 Solution
 109 ========
 110
 111 The two way dependency can be avoided by enabling type conversion in the binary operator
 112 implementation. Note that this is the usual way interoperability betwween types is achieved
 113 for binary operators and one reason why binary operators are usually implemented as non-members.
 114
 115 A simple implementation of this strategy would look like this ::
 116
 117   template<
 118       class T1
 119     , class T2
 120   >
 121   struct interoperable_base :
 122       if_<
 123           is_convertible<
 124               T2
 125             , T1
 126           >
 127         , T1
 128         , T2>
 129   {};
 130
 131
 132   template<
 133       class Derived1
 134     , class Derived2
 135   >
 136   enable_if<is_interoperable<Derived1, Derived2>, bool> operator==(
 137       Derived1 const& lhs
 138     , Derived2 const& rhs
 139   )
 140   {
 141     typedef interoperable_base<
 142                 Derived1
 143               , Derived2
 144             >::type Base;
 145
 146     return static_cast<Base const&>(lhs).equal_to(static_cast<Derived2 const&(rhs));
 147   }
 148
 149 This way our original simple and "obvious" implementation would
 150 work again. ::
 151
 152   c == m; // ok, dispatched to Constant::equal_to
 153   m == c; // ok, dispatched to Constant::equal_to, m converted to Constant
 154
 155 The backdraw of this approach is that a possibly costly conversion of iterator objects
 156 is forced on the user even in cases where direct comparison could be implemented
 157 in a much more efficient way. This problem arises especially for iterator_adaptor
 158 specializations and can be significantly slow down the iteration over ranges. Given the fact
 159 that iteration is a very basic operation this possible performance degradation is not
 160 acceptable.
 161
 162 Luckily whe can have our cake and eat it by a slightly more clever implementation of the binary
 163 operators. ::
 164
 165   template<
 166       class Derived1
 167     , class Derived2
 168   >
 169   enable_if<is_convertible<Derived2, Derived1>, bool> operator==(
 170       Derived1 const& lhs
 171     , Derived2 const& rhs
 172   )
 173   {
 174     return static_cast<Derived1 const&>(lhs).equal_to(static_cast<Derived2 const&(rhs));
 175   }
 176
 177   template<
 178       class Derived1
 179     , class Derived2
 180   >
 181   enable_if<is_convertible<Derived1, Derived2>, bool> operator==(
 182       Derived1 const& lhs
 183     , Derived2 const& rhs
 184   )
 185   {
 186     return static_cast<Derived2 const&>(rhs).equal_to(static_cast<Derived1 const&(lhs));
 187   }
 188
 189 Given our simple and obvious definition of Mutable and Constant nothing has changed yet. ::
 190
 191   c == m; // ok, dispatched to Constant::equal_to, m converted to Constant
 192   m == c; // ok, dispatched to Constant::equal_to, m converted to Constant
 193
 194 But now the user can avoid the type conversion by supplying the
 195 appropriate overload in Constant ::
 196
 197   struct Constant : Facade<Constant>
 198   {
 199     Constant();
 200     Constant(Constant const&);
 201     Constant(Mutable const&);
 202
 203     ...
 204
 205     bool equal_to(Constant const&);
 206     bool equal_to(Mutable const&);
 207   };
 208
 209   c == m; // ok, dispatched to Constant::equal_to(Mutable const&), no conversion
 210   m == c; // ok, dispatched to Constant::equal_to(Mutable const&), no conversion
 211
 212 This definition of operator== introduces a possible ambiguity when both types are convertible
 213 to each other. I don't think this is a problem as this behaviour is the same with concrete types.
 214 I.e.  ::
 215
 216   struct A {};
 217
 218   bool operator==(A, A);
 219
 220   struct B { B(A); };
 221
 222   bool operator==(B, B);
 223
 224   A a;
 225   B b(a);
 226
 227   a == b; // error, ambiguous overload
 228
 229 Effect
 230 ======
 231
 232 Iterator implementations using iterator_facade look exactly as if they were
 233 "hand-implemented" (I am working on better wording).
 234
 235 a) Less burden for the user
 236
 237 b) The definition (standardese) of specialized adpters might be easier
 238    (This has to be proved yet)