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