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