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 12Problem 13======= 14 15The current iterator_facade specification makes it unneccessarily tedious to 16implement interoperable iterators. 17 18In the following text a simplified example of the current iterator_facade specification is used to 19illustrate the problem. 20 21In 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 48The problem with this is that operator== always forwards to Derived1::equal_to. The net effect is that the 49following "obvious" implementation of to interoperable types does 50not 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 92Beside the fact that the code is significantly more complex to understand and to teach there is 93a major design problem lurking here. Note that in both types equal_to is a function template with 94an unconstrained argument T. This is necessary so that further types can be made interoperable with 95Mutable 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 103Constant and Mutable would still be interoperable but no further interoperable could be added 104without changing Mutable. Even if this would be considered acceptable the current specification forces 105a two way dependency between interoperable types. Note in the templated equal_to case this dependency 106is implicitly created when specializing equal_to. 107 108Solution 109======== 110 111The two way dependency can be avoided by enabling type conversion in the binary operator 112implementation. Note that this is the usual way interoperability betwween types is achieved 113for binary operators and one reason why binary operators are usually implemented as non-members. 114 115A 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 149This way our original simple and "obvious" implementation would 150work 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 155The backdraw of this approach is that a possibly costly conversion of iterator objects 156is forced on the user even in cases where direct comparison could be implemented 157in a much more efficient way. This problem arises especially for iterator_adaptor 158specializations and can be significantly slow down the iteration over ranges. Given the fact 159that iteration is a very basic operation this possible performance degradation is not 160acceptable. 161 162Luckily whe can have our cake and eat it by a slightly more clever implementation of the binary 163operators. :: 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 189Given 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 194But now the user can avoid the type conversion by supplying the 195appropriate 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 212This definition of operator== introduces a possible ambiguity when both types are convertible 213to each other. I don't think this is a problem as this behaviour is the same with concrete types. 214I.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 229Effect 230====== 231 232Iterator implementations using iterator_facade look exactly as if they were 233"hand-implemented" (I am working on better wording). 234 235a) Less burden for the user 236 237b) The definition (standardese) of specialized adpters might be easier 238 (This has to be proved yet) 239