Chris@16: /*=============================================================================
Chris@16:     Copyright (c) 2002-2003 Joel de Guzman
Chris@16:     Copyright (c) 2002-2003 Hartmut Kaiser
Chris@16:     http://spirit.sourceforge.net/
Chris@16: 
Chris@16:     Use, modification and distribution is subject to the Boost Software
Chris@16:     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:     http://www.boost.org/LICENSE_1_0.txt)
Chris@16: =============================================================================*/
Chris@16: #if !defined(BOOST_SPIRIT_TRAVERSE_IPP)
Chris@16: #define BOOST_SPIRIT_TRAVERSE_IPP
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: #include <boost/spirit/home/classic/meta/fundamental.hpp>
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: namespace boost { namespace spirit {
Chris@16: 
Chris@16: BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: namespace impl
Chris@16: {
Chris@16: 
Chris@16:     template <typename CategoryT>
Chris@16:     struct traverse_post_order_return_category;
Chris@16: 
Chris@16: }   // namespace impl
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  Environment class for post_order_traversal
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: template <int Level, int Node, int Index, int LastLeft>
Chris@16: struct traverse_post_order_env {
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(int, level = Level);
Chris@16:     BOOST_STATIC_CONSTANT(int, node = Node);
Chris@16:     BOOST_STATIC_CONSTANT(int, index = Index);
Chris@16:     BOOST_STATIC_CONSTANT(int, lastleft = LastLeft);
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  traverse_post_order_return template
Chris@16: //
Chris@16: //      This template is a helper for dispatching the calculation of a parser
Chris@16: //      type result for a traversal level to the corresponding parser_category
Chris@16: //      based specialization.
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: template <typename MetaT, typename ParserT, typename EnvT>
Chris@16: struct traverse_post_order_return {
Chris@16: 
Chris@16:     typedef typename ParserT::parser_category_t parser_category_t;
Chris@16:     typedef typename impl::traverse_post_order_return_category<parser_category_t>
Chris@16:         ::template result<MetaT, ParserT, EnvT>::type type;
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  parser_traversal_..._result templates
Chris@16: //
Chris@16: //      These are metafunctions, which calculate the resulting parser type
Chris@16: //      for all subparsers and feed these types to the user supplied
Chris@16: //      metafunctions to get back the resulting parser type of this traversal
Chris@16: //      level.
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: template <typename MetaT, typename ParserT, typename EnvT>
Chris@16: struct parser_traversal_plain_result {
Chris@16: 
Chris@16:     typedef typename MetaT::template plain_result<ParserT, EnvT>::type type;
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: template <typename MetaT, typename UnaryT, typename SubjectT, typename EnvT>
Chris@16: struct parser_traversal_unary_result {
Chris@16: 
Chris@16:     typedef typename MetaT
Chris@16:         ::template unary_result<UnaryT, SubjectT, EnvT>::type type;
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: template <typename MetaT, typename ActionT, typename SubjectT, typename EnvT>
Chris@16: struct parser_traversal_action_result {
Chris@16: 
Chris@16:     typedef typename MetaT
Chris@16:         ::template action_result<ActionT, SubjectT, EnvT>::type type;
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: template <
Chris@16:     typename MetaT, typename BinaryT, typename LeftT,
Chris@16:     typename RightT, typename EnvT
Chris@16: >
Chris@16: struct parser_traversal_binary_result {
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(int,
Chris@16:         thisnum = (node_count<BinaryT>::value + EnvT::lastleft-1));
Chris@16:     BOOST_STATIC_CONSTANT(int,
Chris@16:         leftnum = (node_count<LeftT>::value + EnvT::lastleft-1));
Chris@16:     BOOST_STATIC_CONSTANT(int,
Chris@16:         leafnum = (leaf_count<LeftT>::value + EnvT::index));
Chris@16: 
Chris@16:     typedef parser_traversal_binary_result self_t;
Chris@16: 
Chris@16:     // left traversal environment and resulting parser type
Chris@16:     typedef traverse_post_order_env<
Chris@16:                 (EnvT::level+1), (self_t::leftnum), (EnvT::index), (EnvT::lastleft)
Chris@16:             > left_sub_env_t;
Chris@16:     typedef typename traverse_post_order_return<
Chris@16:                 MetaT, LeftT, left_sub_env_t
Chris@16:             >::type
Chris@16:         left_t;
Chris@16: 
Chris@16:     // right traversal environment and resulting parser type
Chris@16:     typedef traverse_post_order_env<
Chris@16:                 (EnvT::level+1), (self_t::thisnum-1), (self_t::leafnum), (self_t::leftnum+1)
Chris@16:             > right_sub_env_t;
Chris@16:     typedef typename traverse_post_order_return<
Chris@16:                 MetaT, RightT, right_sub_env_t
Chris@16:             >::type
Chris@16:         right_t;
Chris@16: 
Chris@16:     typedef typename MetaT::template binary_result<
Chris@16:                 BinaryT, left_t, right_t, EnvT
Chris@16:             >::type
Chris@16:         type;
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: namespace impl
Chris@16: {
Chris@16:     ///////////////////////////////////////////////////////////////////////////
Chris@16:     //
Chris@16:     //  Meta functions, which dispatch the calculation of the return type of
Chris@16:     //  of the post_order traverse function to the result template of the
Chris@16:     //  corresponding parser_category based metafunction template.
Chris@16:     //
Chris@16:     ///////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16:     template <typename CategoryT>
Chris@16:     struct traverse_post_order_return_category;
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order_return_category<plain_parser_category> {
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef typename parser_traversal_plain_result<
Chris@16:                         MetaT, ParserT, EnvT
Chris@16:                     >::type
Chris@16:                 type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order_return_category<unary_parser_category> {
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef typename parser_traversal_unary_result<
Chris@16:                         MetaT, ParserT, typename ParserT::subject_t, EnvT
Chris@16:                     >::type
Chris@16:                 type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order_return_category<action_parser_category> {
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef typename parser_traversal_action_result<
Chris@16:                         MetaT, ParserT, typename ParserT::subject_t, EnvT
Chris@16:                     >::type
Chris@16:                 type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order_return_category<binary_parser_category> {
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef typename parser_traversal_binary_result<
Chris@16:                         MetaT, ParserT, typename ParserT::left_t,
Chris@16:                         typename ParserT::right_t, EnvT
Chris@16:                     >::type
Chris@16:                 type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     ///////////////////////////////////////////////////////////////////////////
Chris@16:     //
Chris@16:     //  Post-order parser traversal
Chris@16:     //
Chris@16:     //      The following templates contain the parser_category based code for
Chris@16:     //
Chris@16:     //        - calculating the type of the resulting parser, which is to be
Chris@16:     //          returned from a level of traversal
Chris@16:     //        - traversing down the composite parser structure, this traversal
Chris@16:     //          returnes a new parser object
Chris@16:     //
Chris@16:     //      Both tasks are delegated to the MetaT metafunction supplied by the
Chris@16:     //      user.
Chris@16:     //
Chris@16:     ///////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16:     template <typename CategoryT>
Chris@16:     struct traverse_post_order;
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order<plain_parser_category> {
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef
Chris@16:                 typename parser_traversal_plain_result<MetaT, ParserT, EnvT>::type
Chris@16:                 type;
Chris@16:         };
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         static
Chris@16:         typename parser_traversal_plain_result<MetaT, ParserT, EnvT>::type
Chris@16:         generate(MetaT const &meta_, ParserT const &parser_, EnvT const &env)
Chris@16:         {
Chris@16:             return meta_.generate_plain(parser_, env);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order<unary_parser_category> {
Chris@16: 
Chris@16:         template <
Chris@16:             typename MetaT, typename ParserT, typename SubjectT, typename EnvT
Chris@16:         >
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef typename parser_traversal_unary_result<
Chris@16:                         MetaT, ParserT, SubjectT, EnvT
Chris@16:                     >::type
Chris@16:                 type;
Chris@16:         };
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         static
Chris@16:         typename parser_traversal_unary_result<
Chris@16:             MetaT, ParserT, 
Chris@16:             typename traverse_post_order_return<
Chris@16:                 MetaT, typename ParserT::subject_t, EnvT
Chris@16:             >::type,
Chris@16:             EnvT
Chris@16:         >::type
Chris@16:         generate(MetaT const &meta_, ParserT const &unary_, EnvT const &env)
Chris@16:         {
Chris@16:             typedef typename ParserT::subject_t             subject_t;
Chris@16:             typedef typename subject_t::parser_category_t   subject_category_t;
Chris@16: 
Chris@16:             return meta_.generate_unary(
Chris@16:                 unary_,
Chris@16:                 traverse_post_order<subject_category_t>::generate(meta_,
Chris@16:                     unary_.subject(),
Chris@16:                     traverse_post_order_env<
Chris@16:                         EnvT::level+1, EnvT::node-1, EnvT::index, EnvT::lastleft
Chris@16:                     >()
Chris@16:                 ),
Chris@16:                 env
Chris@16:             );
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order<action_parser_category> {
Chris@16: 
Chris@16:         template <
Chris@16:             typename MetaT, typename ParserT, typename SubjectT, typename EnvT
Chris@16:         >
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef typename parser_traversal_action_result<
Chris@16:                         MetaT, ParserT, SubjectT, EnvT
Chris@16:                     >::type
Chris@16:                 type;
Chris@16:         };
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         static
Chris@16:         typename parser_traversal_action_result<
Chris@16:             MetaT, ParserT, 
Chris@16:             typename traverse_post_order_return<
Chris@16:                 MetaT, typename ParserT::subject_t, EnvT
Chris@16:             >::type,
Chris@16:             EnvT
Chris@16:         >::type
Chris@16:         generate(MetaT const &meta_, ParserT const &action_, EnvT const &env)
Chris@16:         {
Chris@16:             typedef typename ParserT::subject_t             subject_t;
Chris@16:             typedef typename subject_t::parser_category_t   subject_category_t;
Chris@16: 
Chris@16:             return meta_.generate_action(
Chris@16:                 action_,
Chris@16:                 traverse_post_order<subject_category_t>::generate(meta_,
Chris@16:                     action_.subject(),
Chris@16:                     traverse_post_order_env<
Chris@16:                         EnvT::level+1, EnvT::node-1, EnvT::index, EnvT::lastleft
Chris@16:                     >()
Chris@16:                 ),
Chris@16:                 env
Chris@16:             );
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct traverse_post_order<binary_parser_category> {
Chris@16: 
Chris@16:         template <
Chris@16:             typename MetaT, typename ParserT, typename LeftT,
Chris@16:             typename RightT, typename EnvT
Chris@16:         >
Chris@16:         struct result {
Chris@16: 
Chris@16:             typedef typename parser_traversal_binary_result<
Chris@16:                         MetaT, ParserT, LeftT, RightT, EnvT
Chris@16:                     >::type
Chris@16:                 type;
Chris@16:         };
Chris@16: 
Chris@16:         template <typename MetaT, typename ParserT, typename EnvT>
Chris@16:         static
Chris@16:         typename parser_traversal_binary_result<
Chris@16:             MetaT, ParserT, 
Chris@16:             typename traverse_post_order_return<
Chris@16:                 MetaT, typename ParserT::left_t, EnvT
Chris@16:             >::type,
Chris@16:             typename traverse_post_order_return<
Chris@16:                 MetaT, typename ParserT::right_t, EnvT
Chris@16:             >::type,
Chris@16:             EnvT
Chris@16:         >::type
Chris@16:         generate(MetaT const &meta_, ParserT const &binary_, EnvT const& /*env*/)
Chris@16:         {
Chris@16:             typedef typename ParserT::left_t                left_t;
Chris@16:             typedef typename ParserT::right_t               right_t;
Chris@16:             typedef typename left_t::parser_category_t      left_category_t;
Chris@16:             typedef typename right_t::parser_category_t     right_category_t;
Chris@16: 
Chris@16:             enum {
Chris@16:                 leftnum = (node_count<left_t>::value + EnvT::lastleft-1),
Chris@16:                 thisnum = (node_count<ParserT>::value + EnvT::lastleft-1),
Chris@16:                 rightnum = (thisnum-1),
Chris@16:                 leafnum = (leaf_count<left_t>::value + EnvT::index)
Chris@16:             };
Chris@16: 
Chris@16:             return meta_.generate_binary(
Chris@16:                 binary_,
Chris@16:                 traverse_post_order<left_category_t>::generate(
Chris@16:                     meta_, binary_.left(),
Chris@16:                     traverse_post_order_env<
Chris@16:                         EnvT::level+1, leftnum, EnvT::index, EnvT::lastleft
Chris@16:                     >()
Chris@16:                 ),
Chris@16:                 traverse_post_order<right_category_t>::generate(
Chris@16:                     meta_, binary_.right(),
Chris@16:                     traverse_post_order_env<
Chris@16:                         EnvT::level+1, rightnum, leafnum, leftnum+1
Chris@16:                     >()
Chris@16:                 ),
Chris@16:                 traverse_post_order_env<
Chris@16:                     EnvT::level, thisnum, EnvT::index, EnvT::lastleft
Chris@16:                 >()
Chris@16:             );
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16: }   //  namespace impl
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: BOOST_SPIRIT_CLASSIC_NAMESPACE_END
Chris@16: 
Chris@16: }} // namespace boost::spirit
Chris@16: 
Chris@16: #endif // !defined(BOOST_SPIRIT_TRAVERSE_IPP)