1 // Boost.TypeErasure library
3 // Copyright 2011 Steven Watanabe
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)
11 #ifndef BOOST_TYPE_ERASURE_DETAIL_NORMALIZE_HPP_INCLUDED
12 #define BOOST_TYPE_ERASURE_DETAIL_NORMALIZE_HPP_INCLUDED
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>
37 namespace type_erasure {
42 template<class T, class U>
47 struct substitution_map_tag {};
49 // a wrapper around an mpl::map that
50 // defaults to the identity map.
52 struct substitution_map
54 typedef substitution_map_tag tag;
64 struct at_impl< ::boost::type_erasure::detail::substitution_map_tag>
66 template<class Seq, class Key>
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>
78 struct has_key_impl< ::boost::type_erasure::detail::substitution_map_tag>
80 template<class Seq, class Key>
81 struct apply : boost::mpl::true_
87 namespace type_erasure {
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
95 typedef typename ::boost::mpl::eval_if< ::boost::mpl::has_key<M, T>,
96 ::boost::type_erasure::detail::resolve_same_type<
98 typename ::boost::mpl::at<M, T>::type
100 ::boost::mpl::identity<T>
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>
110 BOOST_MPL_ASSERT((::boost::is_same<T, U>));
114 template<class T, class U>
115 struct select_pair<T, ::boost::type_erasure::deduced<U> >
117 typedef ::boost::mpl::pair< ::boost::type_erasure::deduced<U>, T> type;
120 template<class T, class U>
121 struct select_pair< ::boost::type_erasure::deduced<T>, U>
123 typedef ::boost::mpl::pair< ::boost::type_erasure::deduced<T>, U> type;
126 template<class T, class U>
128 ::boost::type_erasure::deduced<T>,
129 ::boost::type_erasure::deduced<U>
132 typedef ::boost::mpl::pair<
133 ::boost::type_erasure::deduced<T>,
134 ::boost::type_erasure::deduced<U>
138 // M is a map of placeholder substitutions
139 template<class M, class T>
140 struct normalize_placeholder
142 typedef typename ::boost::mpl::eval_if< ::boost::mpl::has_key<M, T>,
143 ::boost::type_erasure::detail::normalize_placeholder<
145 typename ::boost::mpl::at<M, T>::type
147 ::boost::mpl::identity<T>
151 template<class M, class T>
152 struct normalize_placeholder<M, ::boost::type_erasure::deduced<T> >
154 typedef typename ::boost::mpl::eval_if< ::boost::mpl::has_key<M, T>,
155 ::boost::type_erasure::detail::normalize_placeholder<
157 typename ::boost::mpl::at<M, T>::type
159 ::boost::type_erasure::detail::normalize_deduced<
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.
171 struct create_placeholder_map
173 typedef typename ::boost::mpl::fold<
175 ::boost::mpl::map0<>,
176 ::boost::mpl::insert<
179 ::boost::mpl::first< ::boost::mpl::_2>,
180 ::boost::type_erasure::detail::normalize_placeholder<M, ::boost::mpl::second< ::boost::mpl::_2> >
186 template<class Bindings, class P, class Out, class Sub>
187 struct convert_deduced
189 typedef typename ::boost::type_erasure::detail::rebind_placeholders_in_argument<
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> >
199 BOOST_MPL_ASSERT((boost::is_same<typename ::boost::mpl::at<type, typename P::second>::type, result>));
202 template<class Bindings, class M, class Sub>
203 struct convert_deductions
205 typedef typename ::boost::mpl::fold<
208 ::boost::type_erasure::detail::convert_deduced<
209 Bindings, ::boost::mpl::_2, ::boost::mpl::_1, Sub
214 template<class Bindings, class P, class Out>
217 typedef typename ::boost::type_erasure::detail::rebind_placeholders_in_argument<
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> >
226 BOOST_MPL_ASSERT((boost::is_same<typename ::boost::mpl::at<type, typename P::second>::type, result>));
229 template<class Bindings, class M>
230 struct add_deductions
232 typedef typename ::boost::mpl::fold<
235 ::boost::type_erasure::detail::add_deduced<
236 Bindings, ::boost::mpl::_2, ::boost::mpl::_1
241 // Fold Op for normalize_concept_impl
242 template<class Out, class T>
243 struct insert_concept
245 typedef ::boost::mpl::pair<
246 typename ::boost::mpl::insert<typename Out::first, T>::type,
251 template<class Out, class T, class U>
252 struct insert_concept<Out, ::boost::type_erasure::same_type<T, U> >
254 typedef typename ::boost::type_erasure::detail::resolve_same_type<
255 typename Out::second,
258 typedef typename ::boost::type_erasure::detail::resolve_same_type<
259 typename Out::second,
262 typedef ::boost::mpl::pair<
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<
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
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>
291 struct append_typeinfo
293 template<class Set, class T>
296 typedef typename ::boost::mpl::insert<
298 ::boost::type_erasure::typeid_<T>
303 // Seq should be a flattened MPL sequence of leaf concepts.
304 // adds typeid_<P> for every placeholder used.
308 typedef typename ::boost::mpl::fold<
310 ::boost::mpl::set0<>,
311 ::boost::type_erasure::detail::get_placeholders<
315 >::type placeholders;
316 typedef typename ::boost::mpl::fold<
319 ::boost::type_erasure::detail::append_typeinfo
323 template<class Concept>
324 struct get_placeholder_normalization_map
326 typedef typename ::boost::type_erasure::detail::create_placeholder_map<
327 typename normalize_concept_impl<Concept>::type::second
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
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<
345 ::boost::type_erasure::detail::rebind_placeholders<
347 ::boost::type_erasure::detail::substitution_map<substitutions>
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>
356 typedef typename ::boost::mpl::copy<
358 ::boost::mpl::back_inserter< ::boost::mpl::vector0<> >
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.
367 class Map = typename ::boost::type_erasure::detail::create_placeholder_map<
368 typename ::boost::type_erasure::detail::normalize_concept_impl<
372 class Out = ::boost::mpl::set0<>
374 struct collect_concepts
376 typedef typename ::boost::type_erasure::detail::rebind_placeholders<
378 ::boost::type_erasure::detail::substitution_map<Map>
380 typedef typename ::boost::mpl::eval_if<
381 ::boost::is_same<transformed, void>,
382 ::boost::mpl::identity<Out>,
383 ::boost::mpl::insert<
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>