Chris@16: /*=============================================================================
Chris@16:     Copyright (c) 2001-2003 Daniel Nuffer
Chris@16:     Copyright (c) 2001-2007 Hartmut Kaiser
Chris@16:     http://spirit.sourceforge.net/
Chris@16: 
Chris@16:   Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@16:   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: =============================================================================*/
Chris@16: #ifndef BOOST_SPIRIT_TREE_AST_HPP
Chris@16: #define BOOST_SPIRIT_TREE_AST_HPP
Chris@16: 
Chris@16: #include <boost/spirit/home/classic/namespace.hpp>
Chris@16: #include <boost/spirit/home/classic/tree/common.hpp>
Chris@16: #include <boost/spirit/home/classic/core/scanner/scanner.hpp>
Chris@16: 
Chris@16: #include <boost/spirit/home/classic/tree/ast_fwd.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: //  ast_match_policy is simply an id so the correct specialization of
Chris@16: //  tree_policy can be found.
Chris@16: template <
Chris@16:     typename IteratorT,
Chris@16:     typename NodeFactoryT,
Chris@16:     typename T
Chris@16: >
Chris@16: struct ast_match_policy :
Chris@16:     public common_tree_match_policy<
Chris@16:         ast_match_policy<IteratorT, NodeFactoryT, T>,
Chris@16:         IteratorT,
Chris@16:         NodeFactoryT,
Chris@16:         ast_tree_policy<
Chris@16:             ast_match_policy<IteratorT, NodeFactoryT, T>,
Chris@16:             NodeFactoryT,
Chris@16:             T
Chris@16:         >,
Chris@16:         T
Chris@16:     >
Chris@16: {
Chris@16:     typedef
Chris@16:         common_tree_match_policy<
Chris@16:             ast_match_policy<IteratorT, NodeFactoryT, T>,
Chris@16:             IteratorT,
Chris@16:             NodeFactoryT,
Chris@16:             ast_tree_policy<
Chris@16:                 ast_match_policy<IteratorT, NodeFactoryT, T>,
Chris@16:                 NodeFactoryT,
Chris@16:                 T
Chris@16:             >,
Chris@16:             T
Chris@16:         >
Chris@16:     common_tree_match_policy_;
Chris@16:     
Chris@16:     ast_match_policy()
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     template <typename PolicyT>
Chris@16:     ast_match_policy(PolicyT const & policies)
Chris@16:         : common_tree_match_policy_(policies)
Chris@16:     {
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename MatchPolicyT, typename NodeFactoryT, typename T>
Chris@16: struct ast_tree_policy :
Chris@16:     public common_tree_tree_policy<MatchPolicyT, NodeFactoryT>
Chris@16: {
Chris@16:     typedef typename MatchPolicyT::match_t match_t;
Chris@16:     typedef typename MatchPolicyT::iterator_t iterator_t;
Chris@16: 
Chris@16:     template<typename MatchAT, typename MatchBT>
Chris@16:     static void concat(MatchAT& a, MatchBT const& b)
Chris@16:     {
Chris@16:         BOOST_SPIRIT_ASSERT(a && b);
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "\n>>>AST concat. a = " << a <<
Chris@16:             "\n\tb = " << b << "<<<\n";
Chris@16: #endif
Chris@16:         typedef typename tree_match<iterator_t, NodeFactoryT, T>::container_t
Chris@16:             container_t;
Chris@16: 
Chris@16:         // test for size() is nessecary, because no_tree_gen_node leaves a.trees
Chris@16:         // and/or b.trees empty
Chris@16:         if (0 != b.trees.size() && b.trees.begin()->value.is_root())
Chris@16:         {
Chris@16:             BOOST_SPIRIT_ASSERT(b.trees.size() == 1);
Chris@16: 
Chris@16:             container_t tmp;
Chris@16:             std::swap(a.trees, tmp); // save a into tmp
Chris@16:             std::swap(b.trees, a.trees); // make b.trees[0] be new root (a.trees[0])
Chris@16:             container_t* pnon_root_trees = &a.trees;
Chris@16:             while (pnon_root_trees->size() > 0 &&
Chris@16:                     pnon_root_trees->begin()->value.is_root())
Chris@16:             {
Chris@16:                 pnon_root_trees = & pnon_root_trees->begin()->children;
Chris@16:             }
Chris@16:             pnon_root_trees->insert(pnon_root_trees->begin(),
Chris@16:                     tmp.begin(), tmp.end());
Chris@16:         }
Chris@16:         else if (0 != a.trees.size() && a.trees.begin()->value.is_root())
Chris@16:         {
Chris@16:             BOOST_SPIRIT_ASSERT(a.trees.size() == 1);
Chris@16: 
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:             a.trees.begin()->children.reserve(a.trees.begin()->children.size() + b.trees.size());
Chris@16: #endif
Chris@16:             std::copy(b.trees.begin(),
Chris@16:                  b.trees.end(),
Chris@16:                  std::back_insert_iterator<container_t>(
Chris@16:                      a.trees.begin()->children));
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:             a.trees.reserve(a.trees.size() + b.trees.size());
Chris@16: #endif
Chris@16:             std::copy(b.trees.begin(),
Chris@16:                  b.trees.end(),
Chris@16:                  std::back_insert_iterator<container_t>(a.trees));
Chris@16:         }
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << ">>>after AST concat. a = " << a << "<<<\n\n";
Chris@16: #endif
Chris@16: 
Chris@16:         return;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MatchT, typename Iterator1T, typename Iterator2T>
Chris@16:     static void group_match(MatchT& m, parser_id const& id,
Chris@16:             Iterator1T const& first, Iterator2T const& last)
Chris@16:     {
Chris@16:         if (!m)
Chris@16:             return;
Chris@16: 
Chris@16:         typedef typename tree_match<iterator_t, NodeFactoryT, T>::container_t
Chris@16:             container_t;
Chris@16:         typedef typename container_t::iterator cont_iterator_t;
Chris@16:         typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
Chris@16: 
Chris@16:         if (m.trees.size() == 1
Chris@16: #ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
Chris@16:             && !(id.to_long() && m.trees.begin()->value.id().to_long())
Chris@16: #endif
Chris@16:             )
Chris@16:         {
Chris@16:             // set rule_id's.  There may have been multiple nodes created.
Chris@16:             // Because of root_node[] they may be left-most children of the top
Chris@16:             // node.
Chris@16:             container_t* punset_id = &m.trees;
Chris@16:             while (punset_id->size() > 0 &&
Chris@16:                     punset_id->begin()->value.id() == 0)
Chris@16:             {
Chris@16:                 punset_id->begin()->value.id(id);
Chris@16:                 punset_id = &punset_id->begin()->children;
Chris@16:             }
Chris@16: 
Chris@16:             m.trees.begin()->value.is_root(false);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             match_t newmatch(m.length(),
Chris@16:                 m.trees.empty() ? 
Chris@16:                     factory_t::empty_node() : 
Chris@16:                     factory_t::create_node(first, last, false));
Chris@16: 
Chris@16:             std::swap(newmatch.trees.begin()->children, m.trees);
Chris@16:             // set this node and all it's unset children's rule_id
Chris@16:             newmatch.trees.begin()->value.id(id);
Chris@16:             for (cont_iterator_t i = newmatch.trees.begin();
Chris@16:                  i != newmatch.trees.end();
Chris@16:                  ++i)
Chris@16:             {
Chris@16:                 if (i->value.id() == 0)
Chris@16:                     i->value.id(id);
Chris@16:             }
Chris@16:             m = newmatch;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename FunctorT, typename MatchT>
Chris@16:     static void apply_op_to_match(FunctorT const& op, MatchT& m)
Chris@16:     {
Chris@16:         op(m);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: namespace impl {
Chris@16: 
Chris@16:     template <typename IteratorT, typename NodeFactoryT, typename T>
Chris@16:     struct tree_policy_selector<ast_match_policy<IteratorT, NodeFactoryT, T> >
Chris@16:     {
Chris@16:         typedef ast_tree_policy<
Chris@16:             ast_match_policy<IteratorT, NodeFactoryT, T>, 
Chris@16:             NodeFactoryT, 
Chris@16:             T
Chris@16:         > type;
Chris@16:     };
Chris@16: 
Chris@16: } // namespace impl
Chris@16: 
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: struct gen_ast_node_parser_gen;
Chris@16: 
Chris@16: template <typename T>
Chris@16: struct gen_ast_node_parser
Chris@16: :   public unary<T, parser<gen_ast_node_parser<T> > >
Chris@16: {
Chris@16:     typedef gen_ast_node_parser<T> self_t;
Chris@16:     typedef gen_ast_node_parser_gen parser_generator_t;
Chris@16:     typedef unary_parser_category parser_category_t;
Chris@16: 
Chris@16:     gen_ast_node_parser(T const& a)
Chris@16:     : unary<T, parser<gen_ast_node_parser<T> > >(a) {}
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     typename parser_result<self_t, ScannerT>::type
Chris@16:     parse(ScannerT const& scan) const
Chris@16:     {
Chris@16:         typedef typename ScannerT::iteration_policy_t iteration_policy_t;
Chris@16:         typedef typename ScannerT::match_policy_t::iterator_t iterator_t;
Chris@16:         typedef typename ScannerT::match_policy_t::factory_t factory_t;
Chris@16:         typedef ast_match_policy<iterator_t, factory_t> match_policy_t;
Chris@16:         typedef typename ScannerT::action_policy_t action_policy_t;
Chris@16:         typedef scanner_policies<
Chris@16:             iteration_policy_t,
Chris@16:             match_policy_t,
Chris@16:             action_policy_t
Chris@16:         > policies_t;
Chris@16: 
Chris@16:         return this->subject().parse(scan.change_policies(policies_t(scan)));
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: struct gen_ast_node_parser_gen
Chris@16: {
Chris@16:     template <typename T>
Chris@16:     struct result {
Chris@16: 
Chris@16:         typedef gen_ast_node_parser<T> type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     static gen_ast_node_parser<T>
Chris@16:     generate(parser<T> const& s)
Chris@16:     {
Chris@16:         return gen_ast_node_parser<T>(s.derived());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     gen_ast_node_parser<T>
Chris@16:     operator[](parser<T> const& s) const
Chris@16:     {
Chris@16:         return gen_ast_node_parser<T>(s.derived());
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: const gen_ast_node_parser_gen gen_ast_node_d = gen_ast_node_parser_gen();
Chris@16: 
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: struct root_node_op
Chris@16: {
Chris@16:     template <typename MatchT>
Chris@16:     void operator()(MatchT& m) const
Chris@16:     {
Chris@16:         BOOST_SPIRIT_ASSERT(m.trees.size() > 0);
Chris@16:         m.trees.begin()->value.is_root(true);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const node_parser_gen<root_node_op> root_node_d =
Chris@16:     node_parser_gen<root_node_op>();
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  Parse functions for ASTs
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: template <
Chris@16:     typename AstFactoryT, typename IteratorT, typename ParserT, 
Chris@16:     typename SkipT
Chris@16: >
Chris@16: inline tree_parse_info<IteratorT, AstFactoryT>
Chris@16: ast_parse(
Chris@16:     IteratorT const&        first_,
Chris@16:     IteratorT const&        last_,
Chris@16:     parser<ParserT> const&  parser,
Chris@16:     SkipT const&            skip_,
Chris@16:     AstFactoryT const &   /*dummy_*/ = AstFactoryT())
Chris@16: {
Chris@16:     typedef skip_parser_iteration_policy<SkipT> iter_policy_t;
Chris@16:     typedef ast_match_policy<IteratorT, AstFactoryT> ast_match_policy_t;
Chris@16:     typedef
Chris@16:         scanner_policies<iter_policy_t, ast_match_policy_t>
Chris@16:         scanner_policies_t;
Chris@16:     typedef scanner<IteratorT, scanner_policies_t> scanner_t;
Chris@16: 
Chris@16:     iter_policy_t iter_policy(skip_);
Chris@16:     scanner_policies_t policies(iter_policy);
Chris@16:     IteratorT first = first_;
Chris@16:     scanner_t scan(first, last_, policies);
Chris@16:     tree_match<IteratorT, AstFactoryT> hit = parser.derived().parse(scan);
Chris@16:     return tree_parse_info<IteratorT, AstFactoryT>(
Chris@16:         first, hit, hit && (first == last_), hit.length(), hit.trees);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename IteratorT, typename ParserT, typename SkipT>
Chris@16: inline tree_parse_info<IteratorT>
Chris@16: ast_parse(
Chris@16:     IteratorT const&        first_,
Chris@16:     IteratorT const&        last_,
Chris@16:     parser<ParserT> const&  parser,
Chris@16:     SkipT const&            skip_)
Chris@16: {
Chris@16:     typedef node_val_data_factory<nil_t> default_factory_t;
Chris@16:     return ast_parse(first_, last_, parser, skip_, default_factory_t());
Chris@16: }
Chris@16:   
Chris@16: //////////////////////////////////
Chris@16: template <typename IteratorT, typename ParserT>
Chris@16: inline tree_parse_info<IteratorT>
Chris@16: ast_parse(
Chris@16:     IteratorT const&        first_,
Chris@16:     IteratorT const&        last,
Chris@16:     parser<ParserT> const&  parser)
Chris@16: {
Chris@16:     typedef ast_match_policy<IteratorT> ast_match_policy_t;
Chris@16:     IteratorT first = first_;
Chris@16:     scanner<
Chris@16:         IteratorT,
Chris@16:         scanner_policies<iteration_policy, ast_match_policy_t>
Chris@16:     > scan(first, last);
Chris@16:     tree_match<IteratorT> hit = parser.derived().parse(scan);
Chris@16:     return tree_parse_info<IteratorT>(
Chris@16:         first, hit, hit && (first == last), hit.length(), hit.trees);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename CharT, typename ParserT, typename SkipT>
Chris@16: inline tree_parse_info<CharT const*>
Chris@16: ast_parse(
Chris@16:     CharT const*            str,
Chris@16:     parser<ParserT> const&  parser,
Chris@16:     SkipT const&            skip)
Chris@16: {
Chris@16:     CharT const* last = str;
Chris@16:     while (*last)
Chris@16:         last++;
Chris@16:     return ast_parse(str, last, parser, skip);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename CharT, typename ParserT>
Chris@16: inline tree_parse_info<CharT const*>
Chris@16: ast_parse(
Chris@16:     CharT const*            str,
Chris@16:     parser<ParserT> const&  parser)
Chris@16: {
Chris@16:     CharT const* last = str;
Chris@16:     while (*last)
Chris@16:     {
Chris@16:         last++;
Chris@16:     }
Chris@16:     return ast_parse(str, last, parser);
Chris@16: }
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: BOOST_SPIRIT_CLASSIC_NAMESPACE_END
Chris@16: 
Chris@16: }} // namespace BOOST_SPIRIT_CLASSIC_NS
Chris@16: 
Chris@16: #endif
Chris@16: