classic/tree/ast.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2003 Daniel Nuffer
0003     Copyright (c) 2001-2007 Hartmut Kaiser
0004     http://spirit.sourceforge.net/
0005
0006   Distributed under the Boost Software License, Version 1.0. (See accompanying
0007   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0008 =============================================================================*/
0009 #ifndef BOOST_SPIRIT_TREE_AST_HPP
0010 #define BOOST_SPIRIT_TREE_AST_HPP
0011
0012 #include <boost/spirit/home/classic/namespace.hpp>
0013 #include <boost/spirit/home/classic/tree/common.hpp>
0014 #include <boost/spirit/home/classic/core/scanner/scanner.hpp>
0015
0016 #include <boost/spirit/home/classic/tree/ast_fwd.hpp>
0017
0018 ///////////////////////////////////////////////////////////////////////////////
0019 namespace boost { namespace spirit {
0020
0021 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
0022
0023 //////////////////////////////////
0024 //  ast_match_policy is simply an id so the correct specialization of
0025 //  tree_policy can be found.
0026 template <
0027     typename IteratorT,
0028     typename NodeFactoryT,
0029     typename T
0030 >
0031 struct ast_match_policy :
0032     public common_tree_match_policy<
0033         ast_match_policy<IteratorT, NodeFactoryT, T>,
0034         IteratorT,
0035         NodeFactoryT,
0036         ast_tree_policy<
0037             ast_match_policy<IteratorT, NodeFactoryT, T>,
0038             NodeFactoryT,
0039             T
0040         >,
0041         T
0042     >
0043 {
0044     typedef
0045         common_tree_match_policy<
0046             ast_match_policy<IteratorT, NodeFactoryT, T>,
0047             IteratorT,
0048             NodeFactoryT,
0049             ast_tree_policy<
0050                 ast_match_policy<IteratorT, NodeFactoryT, T>,
0051                 NodeFactoryT,
0052                 T
0053             >,
0054             T
0055         >
0056     common_tree_match_policy_;
0057
0058     ast_match_policy()
0059     {
0060     }
0061
0062     template <typename PolicyT>
0063     ast_match_policy(PolicyT const & policies)
0064         : common_tree_match_policy_(policies)
0065     {
0066     }
0067 };
0068
0069 //////////////////////////////////
0070 template <typename MatchPolicyT, typename NodeFactoryT, typename T>
0071 struct ast_tree_policy :
0072     public common_tree_tree_policy<MatchPolicyT, NodeFactoryT>
0073 {
0074     typedef typename MatchPolicyT::match_t match_t;
0075     typedef typename MatchPolicyT::iterator_t iterator_t;
0076
0077     template<typename MatchAT, typename MatchBT>
0078     static void concat(MatchAT& a, MatchBT const& b)
0079     {
0080         BOOST_SPIRIT_ASSERT(a && b);
0081
0082 #if defined(BOOST_SPIRIT_DEBUG) && \
0083     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
0084         BOOST_SPIRIT_DEBUG_OUT << "\n>>>AST concat. a = " << a <<
0085             "\n\tb = " << b << "<<<\n";
0086 #endif
0087         typedef typename tree_match<iterator_t, NodeFactoryT, T>::container_t
0088             container_t;
0089
0090         // test for size() is necessary, because no_tree_gen_node leaves a.trees
0091         // and/or b.trees empty
0092         if (0 != b.trees.size() && b.trees.begin()->value.is_root())
0093         {
0094             BOOST_SPIRIT_ASSERT(b.trees.size() == 1);
0095
0096             container_t tmp;
0097             std::swap(a.trees, tmp); // save a into tmp
0098             std::swap(b.trees, a.trees); // make b.trees[0] be new root (a.trees[0])
0099             container_t* pnon_root_trees = &a.trees;
0100             while (pnon_root_trees->size() > 0 &&
0101                     pnon_root_trees->begin()->value.is_root())
0102             {
0103                 pnon_root_trees = & pnon_root_trees->begin()->children;
0104             }
0105             pnon_root_trees->insert(pnon_root_trees->begin(),
0106                     tmp.begin(), tmp.end());
0107         }
0108         else if (0 != a.trees.size() && a.trees.begin()->value.is_root())
0109         {
0110             BOOST_SPIRIT_ASSERT(a.trees.size() == 1);
0111
0112 #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
0113             a.trees.begin()->children.reserve(a.trees.begin()->children.size() + b.trees.size());
0114 #endif
0115             std::copy(b.trees.begin(),
0116                  b.trees.end(),
0117                  std::back_insert_iterator<container_t>(
0118                      a.trees.begin()->children));
0119         }
0120         else
0121         {
0122 #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
0123             a.trees.reserve(a.trees.size() + b.trees.size());
0124 #endif
0125             std::copy(b.trees.begin(),
0126                  b.trees.end(),
0127                  std::back_insert_iterator<container_t>(a.trees));
0128         }
0129
0130 #if defined(BOOST_SPIRIT_DEBUG) && \
0131     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
0132         BOOST_SPIRIT_DEBUG_OUT << ">>>after AST concat. a = " << a << "<<<\n\n";
0133 #endif
0134
0135         return;
0136     }
0137
0138     template <typename MatchT, typename Iterator1T, typename Iterator2T>
0139     static void group_match(MatchT& m, parser_id const& id,
0140             Iterator1T const& first, Iterator2T const& last)
0141     {
0142         if (!m)
0143             return;
0144
0145         typedef typename tree_match<iterator_t, NodeFactoryT, T>::container_t
0146             container_t;
0147         typedef typename container_t::iterator cont_iterator_t;
0148         typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
0149
0150         if (m.trees.size() == 1
0151 #ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
0152             && !(id.to_long() && m.trees.begin()->value.id().to_long())
0153 #endif
0154             )
0155         {
0156             // set rule_id's.  There may have been multiple nodes created.
0157             // Because of root_node[] they may be left-most children of the top
0158             // node.
0159             container_t* punset_id = &m.trees;
0160             while (punset_id->size() > 0 &&
0161                     punset_id->begin()->value.id() == 0)
0162             {
0163                 punset_id->begin()->value.id(id);
0164                 punset_id = &punset_id->begin()->children;
0165             }
0166
0167             m.trees.begin()->value.is_root(false);
0168         }
0169         else
0170         {
0171             match_t newmatch(m.length(),
0172                 m.trees.empty() ?
0173                     factory_t::empty_node() :
0174                     factory_t::create_node(first, last, false));
0175
0176             std::swap(newmatch.trees.begin()->children, m.trees);
0177             // set this node and all it's unset children's rule_id
0178             newmatch.trees.begin()->value.id(id);
0179             for (cont_iterator_t i = newmatch.trees.begin();
0180                  i != newmatch.trees.end();
0181                  ++i)
0182             {
0183                 if (i->value.id() == 0)
0184                     i->value.id(id);
0185             }
0186             m = newmatch;
0187         }
0188     }
0189
0190     template <typename FunctorT, typename MatchT>
0191     static void apply_op_to_match(FunctorT const& op, MatchT& m)
0192     {
0193         op(m);
0194     }
0195 };
0196
0197 namespace impl {
0198
0199     template <typename IteratorT, typename NodeFactoryT, typename T>
0200     struct tree_policy_selector<ast_match_policy<IteratorT, NodeFactoryT, T> >
0201     {
0202         typedef ast_tree_policy<
0203             ast_match_policy<IteratorT, NodeFactoryT, T>,
0204             NodeFactoryT,
0205             T
0206         > type;
0207     };
0208
0209 } // namespace impl
0210
0211
0212 //////////////////////////////////
0213 struct gen_ast_node_parser_gen;
0214
0215 template <typename T>
0216 struct gen_ast_node_parser
0217 :   public unary<T, parser<gen_ast_node_parser<T> > >
0218 {
0219     typedef gen_ast_node_parser<T> self_t;
0220     typedef gen_ast_node_parser_gen parser_generator_t;
0221     typedef unary_parser_category parser_category_t;
0222
0223     gen_ast_node_parser(T const& a)
0224     : unary<T, parser<gen_ast_node_parser<T> > >(a) {}
0225
0226     template <typename ScannerT>
0227     typename parser_result<self_t, ScannerT>::type
0228     parse(ScannerT const& scan) const
0229     {
0230         typedef typename ScannerT::iteration_policy_t iteration_policy_t;
0231         typedef typename ScannerT::match_policy_t::iterator_t iterator_t;
0232         typedef typename ScannerT::match_policy_t::factory_t factory_t;
0233         typedef ast_match_policy<iterator_t, factory_t> match_policy_t;
0234         typedef typename ScannerT::action_policy_t action_policy_t;
0235         typedef scanner_policies<
0236             iteration_policy_t,
0237             match_policy_t,
0238             action_policy_t
0239         > policies_t;
0240
0241         return this->subject().parse(scan.change_policies(policies_t(scan)));
0242     }
0243 };
0244
0245 //////////////////////////////////
0246 struct gen_ast_node_parser_gen
0247 {
0248     template <typename T>
0249     struct result {
0250
0251         typedef gen_ast_node_parser<T> type;
0252     };
0253
0254     template <typename T>
0255     static gen_ast_node_parser<T>
0256     generate(parser<T> const& s)
0257     {
0258         return gen_ast_node_parser<T>(s.derived());
0259     }
0260
0261     template <typename T>
0262     gen_ast_node_parser<T>
0263     operator[](parser<T> const& s) const
0264     {
0265         return gen_ast_node_parser<T>(s.derived());
0266     }
0267 };
0268
0269 //////////////////////////////////
0270 const gen_ast_node_parser_gen gen_ast_node_d = gen_ast_node_parser_gen();
0271
0272
0273 //////////////////////////////////
0274 struct root_node_op
0275 {
0276     template <typename MatchT>
0277     void operator()(MatchT& m) const
0278     {
0279         BOOST_SPIRIT_ASSERT(m.trees.size() > 0);
0280         m.trees.begin()->value.is_root(true);
0281     }
0282 };
0283
0284 const node_parser_gen<root_node_op> root_node_d =
0285     node_parser_gen<root_node_op>();
0286
0287 ///////////////////////////////////////////////////////////////////////////////
0288 //
0289 //  Parse functions for ASTs
0290 //
0291 ///////////////////////////////////////////////////////////////////////////////
0292 template <
0293     typename AstFactoryT, typename IteratorT, typename ParserT,
0294     typename SkipT
0295 >
0296 inline tree_parse_info<IteratorT, AstFactoryT>
0297 ast_parse(
0298     IteratorT const&        first_,
0299     IteratorT const&        last_,
0300     parser<ParserT> const&  parser,
0301     SkipT const&            skip_,
0302     AstFactoryT const &   /*dummy_*/ = AstFactoryT())
0303 {
0304     typedef skip_parser_iteration_policy<SkipT> it_policy_t;
0305     typedef ast_match_policy<IteratorT, AstFactoryT> ast_match_policy_t;
0306     typedef
0307         scanner_policies<it_policy_t, ast_match_policy_t>
0308         scan_policies_t;
0309     typedef scanner<IteratorT, scan_policies_t> scanner_t;
0310
0311     it_policy_t iter_policy(skip_);
0312     scan_policies_t policies(iter_policy);
0313     IteratorT first = first_;
0314     scanner_t scan(first, last_, policies);
0315     tree_match<IteratorT, AstFactoryT> hit = parser.derived().parse(scan);
0316     return tree_parse_info<IteratorT, AstFactoryT>(
0317         first, hit, hit && (first == last_), hit.length(), hit.trees);
0318 }
0319
0320 //////////////////////////////////
0321 template <typename IteratorT, typename ParserT, typename SkipT>
0322 inline tree_parse_info<IteratorT>
0323 ast_parse(
0324     IteratorT const&        first_,
0325     IteratorT const&        last_,
0326     parser<ParserT> const&  parser,
0327     SkipT const&            skip_)
0328 {
0329     typedef node_val_data_factory<nil_t> default_factory_t;
0330     return ast_parse(first_, last_, parser, skip_, default_factory_t());
0331 }
0332
0333 //////////////////////////////////
0334 template <typename IteratorT, typename ParserT>
0335 inline tree_parse_info<IteratorT>
0336 ast_parse(
0337     IteratorT const&        first_,
0338     IteratorT const&        last,
0339     parser<ParserT> const&  parser)
0340 {
0341     typedef ast_match_policy<IteratorT> ast_match_policy_t;
0342     IteratorT first = first_;
0343     scanner<
0344         IteratorT,
0345         scanner_policies<iteration_policy, ast_match_policy_t>
0346     > scan(first, last);
0347     tree_match<IteratorT> hit = parser.derived().parse(scan);
0348     return tree_parse_info<IteratorT>(
0349         first, hit, hit && (first == last), hit.length(), hit.trees);
0350 }
0351
0352 //////////////////////////////////
0353 template <typename CharT, typename ParserT, typename SkipT>
0354 inline tree_parse_info<CharT const*>
0355 ast_parse(
0356     CharT const*            str,
0357     parser<ParserT> const&  parser,
0358     SkipT const&            skip)
0359 {
0360     CharT const* last = str;
0361     while (*last)
0362         last++;
0363     return ast_parse(str, last, parser, skip);
0364 }
0365
0366 //////////////////////////////////
0367 template <typename CharT, typename ParserT>
0368 inline tree_parse_info<CharT const*>
0369 ast_parse(
0370     CharT const*            str,
0371     parser<ParserT> const&  parser)
0372 {
0373     CharT const* last = str;
0374     while (*last)
0375     {
0376         last++;
0377     }
0378     return ast_parse(str, last, parser);
0379 }
0380
0381 ///////////////////////////////////////////////////////////////////////////////
0382 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
0383
0384 }} // namespace BOOST_SPIRIT_CLASSIC_NS
0385
0386 #endif
0387