source: NonGTP/Boost/boost/spirit/meta/impl/traverse.ipp @ 857

Revision 857, 13.5 KB checked in by igarcia, 18 years ago (diff)
Line 
1/*=============================================================================
2    Copyright (c) 2002-2003 Joel de Guzman
3    Copyright (c) 2002-2003 Hartmut Kaiser
4    http://spirit.sourceforge.net/
5
6    Use, modification and distribution is subject to the Boost Software
7    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8    http://www.boost.org/LICENSE_1_0.txt)
9=============================================================================*/
10#if !defined(BOOST_SPIRIT_TRAVERSE_IPP)
11#define BOOST_SPIRIT_TRAVERSE_IPP
12
13///////////////////////////////////////////////////////////////////////////////
14#include <boost/spirit/meta/fundamental.hpp>
15
16///////////////////////////////////////////////////////////////////////////////
17namespace boost { namespace spirit {
18
19///////////////////////////////////////////////////////////////////////////////
20namespace impl
21{
22
23    template <typename CategoryT>
24    struct traverse_post_order_return_category;
25
26}   // namespace impl
27
28///////////////////////////////////////////////////////////////////////////////
29//
30//  Environment class for post_order_traversal
31//
32///////////////////////////////////////////////////////////////////////////////
33
34template <int Level, int Node, int Index, int LastLeft>
35struct traverse_post_order_env {
36
37    BOOST_STATIC_CONSTANT(int, level = Level);
38    BOOST_STATIC_CONSTANT(int, node = Node);
39    BOOST_STATIC_CONSTANT(int, index = Index);
40    BOOST_STATIC_CONSTANT(int, lastleft = LastLeft);
41};
42
43///////////////////////////////////////////////////////////////////////////////
44//
45//  traverse_post_order_return template
46//
47//      This template is a helper for dispatching the calculation of a parser
48//      type result for a traversal level to the corresponding parser_category
49//      based specialization.
50//
51///////////////////////////////////////////////////////////////////////////////
52
53template <typename MetaT, typename ParserT, typename EnvT>
54struct traverse_post_order_return {
55
56    typedef typename ParserT::parser_category_t parser_category_t;
57    typedef typename impl::traverse_post_order_return_category<parser_category_t>
58        ::template result<MetaT, ParserT, EnvT>::type type;
59};
60
61///////////////////////////////////////////////////////////////////////////////
62//
63//  parser_traversal_..._result templates
64//
65//      These are metafunctions, which calculate the resulting parser type
66//      for all subparsers and feed these types to the user supplied
67//      metafunctions to get back the resulting parser type of this traversal
68//      level.
69//
70///////////////////////////////////////////////////////////////////////////////
71
72template <typename MetaT, typename ParserT, typename EnvT>
73struct parser_traversal_plain_result {
74
75    typedef typename MetaT::template plain_result<ParserT, EnvT>::type type;
76};
77
78///////////////////////////////////////////////////////////////////////////////
79template <typename MetaT, typename UnaryT, typename SubjectT, typename EnvT>
80struct parser_traversal_unary_result {
81
82    typedef typename MetaT
83        ::template unary_result<UnaryT, SubjectT, EnvT>::type type;
84};
85
86///////////////////////////////////////////////////////////////////////////////
87template <typename MetaT, typename ActionT, typename SubjectT, typename EnvT>
88struct parser_traversal_action_result {
89
90    typedef typename MetaT
91        ::template action_result<ActionT, SubjectT, EnvT>::type type;
92};
93
94///////////////////////////////////////////////////////////////////////////////
95template <
96    typename MetaT, typename BinaryT, typename LeftT,
97    typename RightT, typename EnvT
98>
99struct parser_traversal_binary_result {
100
101    BOOST_STATIC_CONSTANT(int,
102        thisnum = (node_count<BinaryT>::value + EnvT::lastleft-1));
103    BOOST_STATIC_CONSTANT(int,
104        leftnum = (node_count<LeftT>::value + EnvT::lastleft-1));
105    BOOST_STATIC_CONSTANT(int,
106        leafnum = (leaf_count<LeftT>::value + EnvT::index));
107
108    typedef parser_traversal_binary_result self_t;
109
110    // left traversal environment and resulting parser type
111    typedef traverse_post_order_env<
112                (EnvT::level+1), (self_t::leftnum), (EnvT::index), (EnvT::lastleft)
113            > left_sub_env_t;
114    typedef typename traverse_post_order_return<
115                MetaT, LeftT, left_sub_env_t
116            >::type
117        left_t;
118
119    // right traversal environment and resulting parser type
120    typedef traverse_post_order_env<
121                (EnvT::level+1), (self_t::thisnum-1), (self_t::leafnum), (self_t::leftnum+1)
122            > right_sub_env_t;
123    typedef typename traverse_post_order_return<
124                MetaT, RightT, right_sub_env_t
125            >::type
126        right_t;
127
128    typedef typename MetaT::template binary_result<
129                BinaryT, left_t, right_t, EnvT
130            >::type
131        type;
132};
133
134///////////////////////////////////////////////////////////////////////////////
135namespace impl
136{
137    ///////////////////////////////////////////////////////////////////////////
138    //
139    //  Meta functions, which dispatch the calculation of the return type of
140    //  of the post_order traverse function to the result template of the
141    //  corresponding parser_category based metafunction template.
142    //
143    ///////////////////////////////////////////////////////////////////////////
144
145    template <typename CategoryT>
146    struct traverse_post_order_return_category;
147
148    template <>
149    struct traverse_post_order_return_category<plain_parser_category> {
150
151        template <typename MetaT, typename ParserT, typename EnvT>
152        struct result {
153
154            typedef typename parser_traversal_plain_result<
155                        MetaT, ParserT, EnvT
156                    >::type
157                type;
158        };
159    };
160
161    template <>
162    struct traverse_post_order_return_category<unary_parser_category> {
163
164        template <typename MetaT, typename ParserT, typename EnvT>
165        struct result {
166
167            typedef typename parser_traversal_unary_result<
168                        MetaT, ParserT, typename ParserT::subject_t, EnvT
169                    >::type
170                type;
171        };
172    };
173
174    template <>
175    struct traverse_post_order_return_category<action_parser_category> {
176
177        template <typename MetaT, typename ParserT, typename EnvT>
178        struct result {
179
180            typedef typename parser_traversal_action_result<
181                        MetaT, ParserT, typename ParserT::subject_t, EnvT
182                    >::type
183                type;
184        };
185    };
186
187    template <>
188    struct traverse_post_order_return_category<binary_parser_category> {
189
190        template <typename MetaT, typename ParserT, typename EnvT>
191        struct result {
192
193            typedef typename parser_traversal_binary_result<
194                        MetaT, ParserT, typename ParserT::left_t,
195                        typename ParserT::right_t, EnvT
196                    >::type
197                type;
198        };
199    };
200
201    ///////////////////////////////////////////////////////////////////////////
202    //
203    //  Post-order parser traversal
204    //
205    //      The following templates contain the parser_category based code for
206    //
207    //        - calculating the type of the resulting parser, which is to be
208    //          returned from a level of traversal
209    //        - traversing down the composite parser structure, this traversal
210    //          returnes a new parser object
211    //
212    //      Both tasks are delegated to the MetaT metafunction supplied by the
213    //      user.
214    //
215    ///////////////////////////////////////////////////////////////////////////
216
217    template <typename CategoryT>
218    struct traverse_post_order;
219
220    template <>
221    struct traverse_post_order<plain_parser_category> {
222
223        template <typename MetaT, typename ParserT, typename EnvT>
224        struct result {
225
226            typedef
227                typename parser_traversal_plain_result<MetaT, ParserT, EnvT>::type
228                type;
229        };
230
231        template <typename MetaT, typename ParserT, typename EnvT>
232        static
233        typename parser_traversal_plain_result<MetaT, ParserT, EnvT>::type
234        generate(MetaT const &meta_, ParserT const &parser_, EnvT const &env)
235        {
236            return meta_.generate_plain(parser_, env);
237        }
238    };
239
240    template <>
241    struct traverse_post_order<unary_parser_category> {
242
243        template <
244            typename MetaT, typename ParserT, typename SubjectT, typename EnvT
245        >
246        struct result {
247
248            typedef typename parser_traversal_unary_result<
249                        MetaT, ParserT, SubjectT, EnvT
250                    >::type
251                type;
252        };
253
254        template <typename MetaT, typename ParserT, typename EnvT>
255        static
256        typename parser_traversal_unary_result<
257            MetaT, ParserT,
258            typename traverse_post_order_return<
259                MetaT, typename ParserT::subject_t, EnvT
260            >::type,
261            EnvT
262        >::type
263        generate(MetaT const &meta_, ParserT const &unary_, EnvT const &env)
264        {
265            typedef typename ParserT::subject_t             subject_t;
266            typedef typename subject_t::parser_category_t   subject_category_t;
267
268            return meta_.generate_unary(
269                unary_,
270                traverse_post_order<subject_category_t>::generate(meta_,
271                    unary_.subject(),
272                    traverse_post_order_env<
273                        EnvT::level+1, EnvT::node-1, EnvT::index, EnvT::lastleft
274                    >()
275                ),
276                env
277            );
278        }
279    };
280
281    template <>
282    struct traverse_post_order<action_parser_category> {
283
284        template <
285            typename MetaT, typename ParserT, typename SubjectT, typename EnvT
286        >
287        struct result {
288
289            typedef typename parser_traversal_action_result<
290                        MetaT, ParserT, SubjectT, EnvT
291                    >::type
292                type;
293        };
294
295        template <typename MetaT, typename ParserT, typename EnvT>
296        static
297        typename parser_traversal_action_result<
298            MetaT, ParserT,
299            typename traverse_post_order_return<
300                MetaT, typename ParserT::subject_t, EnvT
301            >::type,
302            EnvT
303        >::type
304        generate(MetaT const &meta_, ParserT const &action_, EnvT const &env)
305        {
306            typedef typename ParserT::subject_t             subject_t;
307            typedef typename subject_t::parser_category_t   subject_category_t;
308
309            return meta_.generate_action(
310                action_,
311                traverse_post_order<subject_category_t>::generate(meta_,
312                    action_.subject(),
313                    traverse_post_order_env<
314                        EnvT::level+1, EnvT::node-1, EnvT::index, EnvT::lastleft
315                    >()
316                ),
317                env
318            );
319        }
320    };
321
322    template <>
323    struct traverse_post_order<binary_parser_category> {
324
325        template <
326            typename MetaT, typename ParserT, typename LeftT,
327            typename RightT, typename EnvT
328        >
329        struct result {
330
331            typedef typename parser_traversal_binary_result<
332                        MetaT, ParserT, LeftT, RightT, EnvT
333                    >::type
334                type;
335        };
336
337        template <typename MetaT, typename ParserT, typename EnvT>
338        static
339        typename parser_traversal_binary_result<
340            MetaT, ParserT,
341            typename traverse_post_order_return<
342                MetaT, typename ParserT::left_t, EnvT
343            >::type,
344            typename traverse_post_order_return<
345                MetaT, typename ParserT::right_t, EnvT
346            >::type,
347            EnvT
348        >::type
349        generate(MetaT const &meta_, ParserT const &binary_, EnvT const& /*env*/)
350        {
351            typedef typename ParserT::left_t                left_t;
352            typedef typename ParserT::right_t               right_t;
353            typedef typename left_t::parser_category_t      left_category_t;
354            typedef typename right_t::parser_category_t     right_category_t;
355
356            enum {
357                leftnum = (node_count<left_t>::value + EnvT::lastleft-1),
358                thisnum = (node_count<ParserT>::value + EnvT::lastleft-1),
359                rightnum = (thisnum-1),
360                leafnum = (leaf_count<left_t>::value + EnvT::index)
361            };
362
363            return meta_.generate_binary(
364                binary_,
365                traverse_post_order<left_category_t>::generate(
366                    meta_, binary_.left(),
367                    traverse_post_order_env<
368                        EnvT::level+1, leftnum, EnvT::index, EnvT::lastleft
369                    >()
370                ),
371                traverse_post_order<right_category_t>::generate(
372                    meta_, binary_.right(),
373                    traverse_post_order_env<
374                        EnvT::level+1, rightnum, leafnum, leftnum+1
375                    >()
376                ),
377                traverse_post_order_env<
378                    EnvT::level, thisnum, EnvT::index, EnvT::lastleft
379                >()
380            );
381        }
382    };
383
384}   //  namespace impl
385
386///////////////////////////////////////////////////////////////////////////////
387}} // namespace boost::spirit
388
389#endif // !defined(BOOST_SPIRIT_TRAVERSE_IPP)
Note: See TracBrowser for help on using the repository browser.