]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | /////////////////////////////////////////////////////////////////////////////// | |
17 | namespace boost { namespace spirit { | |
18 | ||
19 | BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN | |
20 | ||
21 | /////////////////////////////////////////////////////////////////////////////// | |
22 | namespace 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 | ||
36 | template <int Level, int Node, int Index, int LastLeft> | |
37 | struct 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 | ||
55 | template <typename MetaT, typename ParserT, typename EnvT> | |
56 | struct 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 | ||
74 | template <typename MetaT, typename ParserT, typename EnvT> | |
75 | struct parser_traversal_plain_result { | |
76 | ||
77 | typedef typename MetaT::template plain_result<ParserT, EnvT>::type type; | |
78 | }; | |
79 | ||
80 | /////////////////////////////////////////////////////////////////////////////// | |
81 | template <typename MetaT, typename UnaryT, typename SubjectT, typename EnvT> | |
82 | struct parser_traversal_unary_result { | |
83 | ||
84 | typedef typename MetaT | |
85 | ::template unary_result<UnaryT, SubjectT, EnvT>::type type; | |
86 | }; | |
87 | ||
88 | /////////////////////////////////////////////////////////////////////////////// | |
89 | template <typename MetaT, typename ActionT, typename SubjectT, typename EnvT> | |
90 | struct parser_traversal_action_result { | |
91 | ||
92 | typedef typename MetaT | |
93 | ::template action_result<ActionT, SubjectT, EnvT>::type type; | |
94 | }; | |
95 | ||
96 | /////////////////////////////////////////////////////////////////////////////// | |
97 | template < | |
98 | typename MetaT, typename BinaryT, typename LeftT, | |
99 | typename RightT, typename EnvT | |
100 | > | |
101 | struct 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 | /////////////////////////////////////////////////////////////////////////////// | |
137 | namespace 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 | /////////////////////////////////////////////////////////////////////////////// | |
389 | BOOST_SPIRIT_CLASSIC_NAMESPACE_END | |
390 | ||
391 | }} // namespace boost::spirit | |
392 | ||
393 | #endif // !defined(BOOST_SPIRIT_TRAVERSE_IPP) |