1 /*=============================================================================
2 Copyright (c) 2002-2003 Joel de Guzman
3 Copyright (c) 2002-2003 Hartmut Kaiser
4 http://spirit.sourceforge.net/
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
13 ///////////////////////////////////////////////////////////////////////////////
14 #include <boost/spirit/home/classic/meta/fundamental.hpp>
16 ///////////////////////////////////////////////////////////////////////////////
17 namespace boost { namespace spirit {
19 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
21 ///////////////////////////////////////////////////////////////////////////////
25 template <typename CategoryT>
26 struct traverse_post_order_return_category;
30 ///////////////////////////////////////////////////////////////////////////////
32 // Environment class for post_order_traversal
34 ///////////////////////////////////////////////////////////////////////////////
36 template <int Level, int Node, int Index, int LastLeft>
37 struct traverse_post_order_env {
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);
45 ///////////////////////////////////////////////////////////////////////////////
47 // traverse_post_order_return template
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.
53 ///////////////////////////////////////////////////////////////////////////////
55 template <typename MetaT, typename ParserT, typename EnvT>
56 struct traverse_post_order_return {
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;
63 ///////////////////////////////////////////////////////////////////////////////
65 // parser_traversal_..._result templates
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
72 ///////////////////////////////////////////////////////////////////////////////
74 template <typename MetaT, typename ParserT, typename EnvT>
75 struct parser_traversal_plain_result {
77 typedef typename MetaT::template plain_result<ParserT, EnvT>::type type;
80 ///////////////////////////////////////////////////////////////////////////////
81 template <typename MetaT, typename UnaryT, typename SubjectT, typename EnvT>
82 struct parser_traversal_unary_result {
84 typedef typename MetaT
85 ::template unary_result<UnaryT, SubjectT, EnvT>::type type;
88 ///////////////////////////////////////////////////////////////////////////////
89 template <typename MetaT, typename ActionT, typename SubjectT, typename EnvT>
90 struct parser_traversal_action_result {
92 typedef typename MetaT
93 ::template action_result<ActionT, SubjectT, EnvT>::type type;
96 ///////////////////////////////////////////////////////////////////////////////
98 typename MetaT, typename BinaryT, typename LeftT,
99 typename RightT, typename EnvT
101 struct parser_traversal_binary_result {
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));
110 typedef parser_traversal_binary_result self_t;
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)
116 typedef typename traverse_post_order_return<
117 MetaT, LeftT, left_sub_env_t
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)
125 typedef typename traverse_post_order_return<
126 MetaT, RightT, right_sub_env_t
130 typedef typename MetaT::template binary_result<
131 BinaryT, left_t, right_t, EnvT
136 ///////////////////////////////////////////////////////////////////////////////
139 ///////////////////////////////////////////////////////////////////////////
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.
145 ///////////////////////////////////////////////////////////////////////////
147 template <typename CategoryT>
148 struct traverse_post_order_return_category;
151 struct traverse_post_order_return_category<plain_parser_category> {
153 template <typename MetaT, typename ParserT, typename EnvT>
156 typedef typename parser_traversal_plain_result<
164 struct traverse_post_order_return_category<unary_parser_category> {
166 template <typename MetaT, typename ParserT, typename EnvT>
169 typedef typename parser_traversal_unary_result<
170 MetaT, ParserT, typename ParserT::subject_t, EnvT
177 struct traverse_post_order_return_category<action_parser_category> {
179 template <typename MetaT, typename ParserT, typename EnvT>
182 typedef typename parser_traversal_action_result<
183 MetaT, ParserT, typename ParserT::subject_t, EnvT
190 struct traverse_post_order_return_category<binary_parser_category> {
192 template <typename MetaT, typename ParserT, typename EnvT>
195 typedef typename parser_traversal_binary_result<
196 MetaT, ParserT, typename ParserT::left_t,
197 typename ParserT::right_t, EnvT
203 ///////////////////////////////////////////////////////////////////////////
205 // Post-order parser traversal
207 // The following templates contain the parser_category based code for
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
214 // Both tasks are delegated to the MetaT metafunction supplied by the
217 ///////////////////////////////////////////////////////////////////////////
219 template <typename CategoryT>
220 struct traverse_post_order;
223 struct traverse_post_order<plain_parser_category> {
225 template <typename MetaT, typename ParserT, typename EnvT>
229 typename parser_traversal_plain_result<MetaT, ParserT, EnvT>::type
233 template <typename MetaT, typename ParserT, typename EnvT>
235 typename parser_traversal_plain_result<MetaT, ParserT, EnvT>::type
236 generate(MetaT const &meta_, ParserT const &parser_, EnvT const &env)
238 return meta_.generate_plain(parser_, env);
243 struct traverse_post_order<unary_parser_category> {
246 typename MetaT, typename ParserT, typename SubjectT, typename EnvT
250 typedef typename parser_traversal_unary_result<
251 MetaT, ParserT, SubjectT, EnvT
256 template <typename MetaT, typename ParserT, typename EnvT>
258 typename parser_traversal_unary_result<
260 typename traverse_post_order_return<
261 MetaT, typename ParserT::subject_t, EnvT
265 generate(MetaT const &meta_, ParserT const &unary_, EnvT const &env)
267 typedef typename ParserT::subject_t subject_t;
268 typedef typename subject_t::parser_category_t subject_category_t;
270 return meta_.generate_unary(
272 traverse_post_order<subject_category_t>::generate(meta_,
274 traverse_post_order_env<
275 EnvT::level+1, EnvT::node-1, EnvT::index, EnvT::lastleft
284 struct traverse_post_order<action_parser_category> {
287 typename MetaT, typename ParserT, typename SubjectT, typename EnvT
291 typedef typename parser_traversal_action_result<
292 MetaT, ParserT, SubjectT, EnvT
297 template <typename MetaT, typename ParserT, typename EnvT>
299 typename parser_traversal_action_result<
301 typename traverse_post_order_return<
302 MetaT, typename ParserT::subject_t, EnvT
306 generate(MetaT const &meta_, ParserT const &action_, EnvT const &env)
308 typedef typename ParserT::subject_t subject_t;
309 typedef typename subject_t::parser_category_t subject_category_t;
311 return meta_.generate_action(
313 traverse_post_order<subject_category_t>::generate(meta_,
315 traverse_post_order_env<
316 EnvT::level+1, EnvT::node-1, EnvT::index, EnvT::lastleft
325 struct traverse_post_order<binary_parser_category> {
328 typename MetaT, typename ParserT, typename LeftT,
329 typename RightT, typename EnvT
333 typedef typename parser_traversal_binary_result<
334 MetaT, ParserT, LeftT, RightT, EnvT
339 template <typename MetaT, typename ParserT, typename EnvT>
341 typename parser_traversal_binary_result<
343 typename traverse_post_order_return<
344 MetaT, typename ParserT::left_t, EnvT
346 typename traverse_post_order_return<
347 MetaT, typename ParserT::right_t, EnvT
351 generate(MetaT const &meta_, ParserT const &binary_, EnvT const& /*env*/)
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;
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)
365 return meta_.generate_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
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
379 traverse_post_order_env<
380 EnvT::level, thisnum, EnvT::index, EnvT::lastleft
388 ///////////////////////////////////////////////////////////////////////////////
389 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
391 }} // namespace boost::spirit
393 #endif // !defined(BOOST_SPIRIT_TRAVERSE_IPP)