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