1 // Boost.TypeErasure library 2 // 3 // Copyright 2011 Steven Watanabe 4 // 5 // Distributed under the Boost Software License Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // $Id$ 10 11 #ifndef BOOST_TYPE_ERASURE_DETAIL_NORMALIZE_HPP_INCLUDED 12 #define BOOST_TYPE_ERASURE_DETAIL_NORMALIZE_HPP_INCLUDED 13 14 #include <boost/mpl/assert.hpp> 15 #include <boost/mpl/eval_if.hpp> 16 #include <boost/mpl/identity.hpp> 17 #include <boost/mpl/is_sequence.hpp> 18 #include <boost/mpl/set.hpp> 19 #include <boost/mpl/map.hpp> 20 #include <boost/mpl/has_key.hpp> 21 #include <boost/mpl/insert.hpp> 22 #include <boost/mpl/vector.hpp> 23 #include <boost/mpl/back_inserter.hpp> 24 #include <boost/mpl/inserter.hpp> 25 #include <boost/mpl/fold.hpp> 26 #include <boost/mpl/transform.hpp> 27 #include <boost/mpl/copy.hpp> 28 #include <boost/mpl/at.hpp> 29 #include <boost/type_traits/is_same.hpp> 30 #include <boost/type_erasure/detail/get_placeholders.hpp> 31 #include <boost/type_erasure/detail/rebind_placeholders.hpp> 32 #include <boost/type_erasure/detail/normalize_deduced.hpp> 33 #include <boost/type_erasure/relaxed.hpp> 34 #include <boost/type_erasure/builtin.hpp> 35 36 namespace boost { 37 namespace type_erasure { 38 39 template<class F> 40 struct deduced; 41 42 template<class T, class U> 43 struct same_type; 44 45 namespace detail { 46 47 struct substitution_map_tag {}; 48 49 // a wrapper around an mpl::map that 50 // defaults to the identity map. 51 template<class M> 52 struct substitution_map 53 { 54 typedef substitution_map_tag tag; 55 typedef M map_type; 56 }; 57 58 } 59 } 60 61 namespace mpl { 62 63 template<> 64 struct at_impl< ::boost::type_erasure::detail::substitution_map_tag> 65 { 66 template<class Seq, class Key> 67 struct apply 68 { 69 typedef typename ::boost::mpl::eval_if< 70 ::boost::mpl::has_key<typename Seq::map_type, Key>, 71 ::boost::mpl::at<typename Seq::map_type, Key>, 72 ::boost::mpl::identity<Key> 73 >::type type; 74 }; 75 }; 76 77 template<> 78 struct has_key_impl< ::boost::type_erasure::detail::substitution_map_tag> 79 { 80 template<class Seq, class Key> 81 struct apply : boost::mpl::true_ 82 {}; 83 }; 84 85 } 86 87 namespace type_erasure { 88 namespace detail { 89 90 // given a partial substitution map from same_type, 91 // resolves a placeholder as far as possible. 92 template<class M, class T> 93 struct resolve_same_type 94 { 95 typedef typename ::boost::mpl::eval_if< ::boost::mpl::has_key<M, T>, 96 ::boost::type_erasure::detail::resolve_same_type< 97 M, 98 typename ::boost::mpl::at<M, T>::type 99 >, 100 ::boost::mpl::identity<T> 101 >::type type; 102 }; 103 104 // Given the arguments to same_type, determines 105 // which should be the key and which should be 106 // the value in the substitution map. 107 template<class T, class U> 108 struct select_pair 109 { 110 BOOST_MPL_ASSERT((::boost::is_same<T, U>)); 111 typedef void type; 112 }; 113 114 template<class T, class U> 115 struct select_pair<T, ::boost::type_erasure::deduced<U> > 116 { 117 typedef ::boost::mpl::pair< ::boost::type_erasure::deduced<U>, T> type; 118 }; 119 120 template<class T, class U> 121 struct select_pair< ::boost::type_erasure::deduced<T>, U> 122 { 123 typedef ::boost::mpl::pair< ::boost::type_erasure::deduced<T>, U> type; 124 }; 125 126 template<class T, class U> 127 struct select_pair< 128 ::boost::type_erasure::deduced<T>, 129 ::boost::type_erasure::deduced<U> 130 > 131 { 132 typedef ::boost::mpl::pair< 133 ::boost::type_erasure::deduced<T>, 134 ::boost::type_erasure::deduced<U> 135 > type; 136 }; 137 138 // M is a map of placeholder substitutions 139 template<class M, class T> 140 struct normalize_placeholder 141 { 142 typedef typename ::boost::mpl::eval_if< ::boost::mpl::has_key<M, T>, 143 ::boost::type_erasure::detail::normalize_placeholder< 144 M, 145 typename ::boost::mpl::at<M, T>::type 146 >, 147 ::boost::mpl::identity<T> 148 >::type type; 149 }; 150 151 template<class M, class T> 152 struct normalize_placeholder<M, ::boost::type_erasure::deduced<T> > 153 { 154 typedef typename ::boost::mpl::eval_if< ::boost::mpl::has_key<M, T>, 155 ::boost::type_erasure::detail::normalize_placeholder< 156 M, 157 typename ::boost::mpl::at<M, T>::type 158 >, 159 ::boost::type_erasure::detail::normalize_deduced< 160 M, 161 T 162 > 163 >::type type; 164 }; 165 166 // Takes a mpl::map of placeholder substitutions and 167 // fully resolves it. i.e. a -> b, b -> c, becomes 168 // a -> c, b -> c. Also resolves deduced placeholders 169 // whose arguments are all resolved. 170 template<class M> 171 struct create_placeholder_map 172 { 173 typedef typename ::boost::mpl::fold< 174 M, 175 ::boost::mpl::map0<>, 176 ::boost::mpl::insert< 177 ::boost::mpl::_1, 178 ::boost::mpl::pair< 179 ::boost::mpl::first< ::boost::mpl::_2>, 180 ::boost::type_erasure::detail::normalize_placeholder<M, ::boost::mpl::second< ::boost::mpl::_2> > 181 > 182 > 183 >::type type; 184 }; 185 186 template<class Bindings, class P, class Out, class Sub> 187 struct convert_deduced 188 { 189 typedef typename ::boost::type_erasure::detail::rebind_placeholders_in_argument< 190 typename P::first, 191 Bindings 192 >::type result1; 193 typedef typename ::boost::mpl::at<Sub, result1>::type result; 194 typedef typename ::boost::mpl::eval_if< 195 ::boost::mpl::has_key<Out, typename P::second>, 196 ::boost::mpl::identity<Out>, 197 ::boost::mpl::insert<Out, ::boost::mpl::pair<typename P::second, result> > 198 >::type type; 199 BOOST_MPL_ASSERT((boost::is_same<typename ::boost::mpl::at<type, typename P::second>::type, result>)); 200 }; 201 202 template<class Bindings, class M, class Sub> 203 struct convert_deductions 204 { 205 typedef typename ::boost::mpl::fold< 206 M, 207 Bindings, 208 ::boost::type_erasure::detail::convert_deduced< 209 Bindings, ::boost::mpl::_2, ::boost::mpl::_1, Sub 210 > 211 >::type type; 212 }; 213 214 template<class Bindings, class P, class Out> 215 struct add_deduced 216 { 217 typedef typename ::boost::type_erasure::detail::rebind_placeholders_in_argument< 218 typename P::first, 219 Bindings 220 >::type result; 221 typedef typename ::boost::mpl::eval_if< 222 ::boost::mpl::has_key<Out, typename P::second>, 223 ::boost::mpl::identity<Out>, 224 ::boost::mpl::insert<Out, ::boost::mpl::pair<typename P::second, result> > 225 >::type type; 226 BOOST_MPL_ASSERT((boost::is_same<typename ::boost::mpl::at<type, typename P::second>::type, result>)); 227 }; 228 229 template<class Bindings, class M> 230 struct add_deductions 231 { 232 typedef typename ::boost::mpl::fold< 233 M, 234 Bindings, 235 ::boost::type_erasure::detail::add_deduced< 236 Bindings, ::boost::mpl::_2, ::boost::mpl::_1 237 > 238 >::type type; 239 }; 240 241 // Fold Op for normalize_concept_impl 242 template<class Out, class T> 243 struct insert_concept 244 { 245 typedef ::boost::mpl::pair< 246 typename ::boost::mpl::insert<typename Out::first, T>::type, 247 typename Out::second 248 > type; 249 }; 250 251 template<class Out, class T, class U> 252 struct insert_concept<Out, ::boost::type_erasure::same_type<T, U> > 253 { 254 typedef typename ::boost::type_erasure::detail::resolve_same_type< 255 typename Out::second, 256 T 257 >::type t1; 258 typedef typename ::boost::type_erasure::detail::resolve_same_type< 259 typename Out::second, 260 U 261 >::type t2; 262 typedef ::boost::mpl::pair< 263 typename Out::first, 264 typename ::boost::mpl::eval_if< 265 ::boost::is_same<t1, t2>, 266 ::boost::mpl::identity<typename Out::second>, 267 ::boost::mpl::insert< 268 typename Out::second, 269 typename ::boost::type_erasure::detail::select_pair< 270 t1, 271 t2 272 >::type 273 > 274 >::type 275 > type; 276 }; 277 278 // flattens a concept returning an mpl::pair 279 // - first is an MPL sequence containing the leaf concepts 280 // - second is an MPL map of the placeholder substitutions 281 // used to resolve same_type. 282 template<class Concept, class Out = ::boost::mpl::pair< ::boost::mpl::set0<>, ::boost::mpl::map0<> > > 283 struct normalize_concept_impl 284 { 285 typedef typename ::boost::mpl::eval_if< ::boost::mpl::is_sequence<Concept>, 286 ::boost::mpl::fold<Concept, Out, normalize_concept_impl< ::boost::mpl::_2, ::boost::mpl::_1> >, 287 ::boost::type_erasure::detail::insert_concept<Out, Concept> 288 >::type type; 289 }; 290 291 struct append_typeinfo 292 { 293 template<class Set, class T> 294 struct apply 295 { 296 typedef typename ::boost::mpl::insert< 297 Set, 298 ::boost::type_erasure::typeid_<T> 299 >::type type; 300 }; 301 }; 302 303 // Seq should be a flattened MPL sequence of leaf concepts. 304 // adds typeid_<P> for every placeholder used. 305 template<class Seq> 306 struct add_typeinfo 307 { 308 typedef typename ::boost::mpl::fold< 309 Seq, 310 ::boost::mpl::set0<>, 311 ::boost::type_erasure::detail::get_placeholders< 312 ::boost::mpl::_2, 313 ::boost::mpl::_1 314 > 315 >::type placeholders; 316 typedef typename ::boost::mpl::fold< 317 placeholders, 318 Seq, 319 ::boost::type_erasure::detail::append_typeinfo 320 >::type type; 321 }; 322 323 template<class Concept> 324 struct get_placeholder_normalization_map 325 { 326 typedef typename ::boost::type_erasure::detail::create_placeholder_map< 327 typename normalize_concept_impl<Concept>::type::second 328 >::type type; 329 }; 330 331 // Flattens a Concept to an mpl::vector of primitive 332 // concepts. Resolves same_type and deduced placeholders. 333 template<class Concept> 334 struct normalize_concept 335 { 336 typedef typename normalize_concept_impl<Concept>::type impl; 337 typedef typename ::boost::type_erasure::detail::create_placeholder_map< 338 typename impl::second 339 >::type substitutions; 340 typedef typename ::boost::mpl::fold< 341 typename impl::first, 342 ::boost::mpl::set0<>, 343 ::boost::mpl::insert< 344 ::boost::mpl::_1, 345 ::boost::type_erasure::detail::rebind_placeholders< 346 ::boost::mpl::_2, 347 ::boost::type_erasure::detail::substitution_map<substitutions> 348 > 349 > 350 >::type basic; 351 typedef typename ::boost::mpl::eval_if< 352 ::boost::type_erasure::is_relaxed<Concept>, 353 ::boost::type_erasure::detail::add_typeinfo<basic>, 354 ::boost::mpl::identity<basic> 355 >::type concept_set; 356 typedef typename ::boost::mpl::copy< 357 concept_set, 358 ::boost::mpl::back_inserter< ::boost::mpl::vector0<> > 359 >::type type; 360 }; 361 362 // Returns an MPL sequence containing all the concepts 363 // in Concept. If Concept is considered as a DAG, 364 // the result will be sorted topologically. 365 template< 366 class Concept, 367 class Map = typename ::boost::type_erasure::detail::create_placeholder_map< 368 typename ::boost::type_erasure::detail::normalize_concept_impl< 369 Concept 370 >::type::second 371 >::type, 372 class Out = ::boost::mpl::set0<> 373 > 374 struct collect_concepts 375 { 376 typedef typename ::boost::type_erasure::detail::rebind_placeholders< 377 Concept, 378 ::boost::type_erasure::detail::substitution_map<Map> 379 >::type transformed; 380 typedef typename ::boost::mpl::eval_if< 381 ::boost::is_same<transformed, void>, 382 ::boost::mpl::identity<Out>, 383 ::boost::mpl::insert< 384 Out, 385 transformed 386 > 387 >::type type1; 388 typedef typename ::boost::mpl::eval_if< ::boost::mpl::is_sequence<Concept>, 389 ::boost::mpl::fold<Concept, type1, collect_concepts< ::boost::mpl::_2, Map, ::boost::mpl::_1> >, 390 ::boost::mpl::identity<type1> 391 >::type type; 392 }; 393 394 } 395 } 396 } 397 398 #endif 399