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