ceph/src/boost/libs/spirit/include/boost/spirit/home/classic/meta/impl/traverse.ipp

   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)