ceph/src/boost/libs/type_erasure/include/boost/type_erasure/detail/normalize.hpp

   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