ceph/src/boost/boost/spirit/home/classic/tree/ast.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2003 Daniel Nuffer
   3     Copyright (c) 2001-2007 Hartmut Kaiser
   4     http://spirit.sourceforge.net/
   5
   6   Distributed under the Boost Software License, Version 1.0. (See accompanying
   7   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   8 =============================================================================*/
   9 #ifndef BOOST_SPIRIT_TREE_AST_HPP
  10 #define BOOST_SPIRIT_TREE_AST_HPP
  11
  12 #include <boost/spirit/home/classic/namespace.hpp>
  13 #include <boost/spirit/home/classic/tree/common.hpp>
  14 #include <boost/spirit/home/classic/core/scanner/scanner.hpp>
  15
  16 #include <boost/spirit/home/classic/tree/ast_fwd.hpp>
  17
  18 ///////////////////////////////////////////////////////////////////////////////
  19 namespace boost { namespace spirit {
  20
  21 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
  22
  23 //////////////////////////////////
  24 //  ast_match_policy is simply an id so the correct specialization of
  25 //  tree_policy can be found.
  26 template <
  27     typename IteratorT,
  28     typename NodeFactoryT,
  29     typename T
  30 >
  31 struct ast_match_policy :
  32     public common_tree_match_policy<
  33         ast_match_policy<IteratorT, NodeFactoryT, T>,
  34         IteratorT,
  35         NodeFactoryT,
  36         ast_tree_policy<
  37             ast_match_policy<IteratorT, NodeFactoryT, T>,
  38             NodeFactoryT,
  39             T
  40         >,
  41         T
  42     >
  43 {
  44     typedef
  45         common_tree_match_policy<
  46             ast_match_policy<IteratorT, NodeFactoryT, T>,
  47             IteratorT,
  48             NodeFactoryT,
  49             ast_tree_policy<
  50                 ast_match_policy<IteratorT, NodeFactoryT, T>,
  51                 NodeFactoryT,
  52                 T
  53             >,
  54             T
  55         >
  56     common_tree_match_policy_;
  57
  58     ast_match_policy()
  59     {
  60     }
  61
  62     template <typename PolicyT>
  63     ast_match_policy(PolicyT const & policies)
  64         : common_tree_match_policy_(policies)
  65     {
  66     }
  67 };
  68
  69 //////////////////////////////////
  70 template <typename MatchPolicyT, typename NodeFactoryT, typename T>
  71 struct ast_tree_policy :
  72     public common_tree_tree_policy<MatchPolicyT, NodeFactoryT>
  73 {
  74     typedef typename MatchPolicyT::match_t match_t;
  75     typedef typename MatchPolicyT::iterator_t iterator_t;
  76
  77     template<typename MatchAT, typename MatchBT>
  78     static void concat(MatchAT& a, MatchBT const& b)
  79     {
  80         BOOST_SPIRIT_ASSERT(a && b);
  81
  82 #if defined(BOOST_SPIRIT_DEBUG) && \
  83     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
  84         BOOST_SPIRIT_DEBUG_OUT << "\n>>>AST concat. a = " << a <<
  85             "\n\tb = " << b << "<<<\n";
  86 #endif
  87         typedef typename tree_match<iterator_t, NodeFactoryT, T>::container_t
  88             container_t;
  89
  90         // test for size() is nessecary, because no_tree_gen_node leaves a.trees
  91         // and/or b.trees empty
  92         if (0 != b.trees.size() && b.trees.begin()->value.is_root())
  93         {
  94             BOOST_SPIRIT_ASSERT(b.trees.size() == 1);
  95
  96             container_t tmp;
  97             std::swap(a.trees, tmp); // save a into tmp
  98             std::swap(b.trees, a.trees); // make b.trees[0] be new root (a.trees[0])
  99             container_t* pnon_root_trees = &a.trees;
 100             while (pnon_root_trees->size() > 0 &&
 101                     pnon_root_trees->begin()->value.is_root())
 102             {
 103                 pnon_root_trees = & pnon_root_trees->begin()->children;
 104             }
 105             pnon_root_trees->insert(pnon_root_trees->begin(),
 106                     tmp.begin(), tmp.end());
 107         }
 108         else if (0 != a.trees.size() && a.trees.begin()->value.is_root())
 109         {
 110             BOOST_SPIRIT_ASSERT(a.trees.size() == 1);
 111
 112 #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
 113             a.trees.begin()->children.reserve(a.trees.begin()->children.size() + b.trees.size());
 114 #endif
 115             std::copy(b.trees.begin(),
 116                  b.trees.end(),
 117                  std::back_insert_iterator<container_t>(
 118                      a.trees.begin()->children));
 119         }
 120         else
 121         {
 122 #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
 123             a.trees.reserve(a.trees.size() + b.trees.size());
 124 #endif
 125             std::copy(b.trees.begin(),
 126                  b.trees.end(),
 127                  std::back_insert_iterator<container_t>(a.trees));
 128         }
 129
 130 #if defined(BOOST_SPIRIT_DEBUG) && \
 131     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
 132         BOOST_SPIRIT_DEBUG_OUT << ">>>after AST concat. a = " << a << "<<<\n\n";
 133 #endif
 134
 135         return;
 136     }
 137
 138     template <typename MatchT, typename Iterator1T, typename Iterator2T>
 139     static void group_match(MatchT& m, parser_id const& id,
 140             Iterator1T const& first, Iterator2T const& last)
 141     {
 142         if (!m)
 143             return;
 144
 145         typedef typename tree_match<iterator_t, NodeFactoryT, T>::container_t
 146             container_t;
 147         typedef typename container_t::iterator cont_iterator_t;
 148         typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
 149
 150         if (m.trees.size() == 1
 151 #ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
 152             && !(id.to_long() && m.trees.begin()->value.id().to_long())
 153 #endif
 154             )
 155         {
 156             // set rule_id's.  There may have been multiple nodes created.
 157             // Because of root_node[] they may be left-most children of the top
 158             // node.
 159             container_t* punset_id = &m.trees;
 160             while (punset_id->size() > 0 &&
 161                     punset_id->begin()->value.id() == 0)
 162             {
 163                 punset_id->begin()->value.id(id);
 164                 punset_id = &punset_id->begin()->children;
 165             }
 166
 167             m.trees.begin()->value.is_root(false);
 168         }
 169         else
 170         {
 171             match_t newmatch(m.length(),
 172                 m.trees.empty() ?
 173                     factory_t::empty_node() :
 174                     factory_t::create_node(first, last, false));
 175
 176             std::swap(newmatch.trees.begin()->children, m.trees);
 177             // set this node and all it's unset children's rule_id
 178             newmatch.trees.begin()->value.id(id);
 179             for (cont_iterator_t i = newmatch.trees.begin();
 180                  i != newmatch.trees.end();
 181                  ++i)
 182             {
 183                 if (i->value.id() == 0)
 184                     i->value.id(id);
 185             }
 186             m = newmatch;
 187         }
 188     }
 189
 190     template <typename FunctorT, typename MatchT>
 191     static void apply_op_to_match(FunctorT const& op, MatchT& m)
 192     {
 193         op(m);
 194     }
 195 };
 196
 197 namespace impl {
 198
 199     template <typename IteratorT, typename NodeFactoryT, typename T>
 200     struct tree_policy_selector<ast_match_policy<IteratorT, NodeFactoryT, T> >
 201     {
 202         typedef ast_tree_policy<
 203             ast_match_policy<IteratorT, NodeFactoryT, T>,
 204             NodeFactoryT,
 205             T
 206         > type;
 207     };
 208
 209 } // namespace impl
 210
 211
 212 //////////////////////////////////
 213 struct gen_ast_node_parser_gen;
 214
 215 template <typename T>
 216 struct gen_ast_node_parser
 217 :   public unary<T, parser<gen_ast_node_parser<T> > >
 218 {
 219     typedef gen_ast_node_parser<T> self_t;
 220     typedef gen_ast_node_parser_gen parser_generator_t;
 221     typedef unary_parser_category parser_category_t;
 222
 223     gen_ast_node_parser(T const& a)
 224     : unary<T, parser<gen_ast_node_parser<T> > >(a) {}
 225
 226     template <typename ScannerT>
 227     typename parser_result<self_t, ScannerT>::type
 228     parse(ScannerT const& scan) const
 229     {
 230         typedef typename ScannerT::iteration_policy_t iteration_policy_t;
 231         typedef typename ScannerT::match_policy_t::iterator_t iterator_t;
 232         typedef typename ScannerT::match_policy_t::factory_t factory_t;
 233         typedef ast_match_policy<iterator_t, factory_t> match_policy_t;
 234         typedef typename ScannerT::action_policy_t action_policy_t;
 235         typedef scanner_policies<
 236             iteration_policy_t,
 237             match_policy_t,
 238             action_policy_t
 239         > policies_t;
 240
 241         return this->subject().parse(scan.change_policies(policies_t(scan)));
 242     }
 243 };
 244
 245 //////////////////////////////////
 246 struct gen_ast_node_parser_gen
 247 {
 248     template <typename T>
 249     struct result {
 250
 251         typedef gen_ast_node_parser<T> type;
 252     };
 253
 254     template <typename T>
 255     static gen_ast_node_parser<T>
 256     generate(parser<T> const& s)
 257     {
 258         return gen_ast_node_parser<T>(s.derived());
 259     }
 260
 261     template <typename T>
 262     gen_ast_node_parser<T>
 263     operator[](parser<T> const& s) const
 264     {
 265         return gen_ast_node_parser<T>(s.derived());
 266     }
 267 };
 268
 269 //////////////////////////////////
 270 const gen_ast_node_parser_gen gen_ast_node_d = gen_ast_node_parser_gen();
 271
 272
 273 //////////////////////////////////
 274 struct root_node_op
 275 {
 276     template <typename MatchT>
 277     void operator()(MatchT& m) const
 278     {
 279         BOOST_SPIRIT_ASSERT(m.trees.size() > 0);
 280         m.trees.begin()->value.is_root(true);
 281     }
 282 };
 283
 284 const node_parser_gen<root_node_op> root_node_d =
 285     node_parser_gen<root_node_op>();
 286
 287 ///////////////////////////////////////////////////////////////////////////////
 288 //
 289 //  Parse functions for ASTs
 290 //
 291 ///////////////////////////////////////////////////////////////////////////////
 292 template <
 293     typename AstFactoryT, typename IteratorT, typename ParserT,
 294     typename SkipT
 295 >
 296 inline tree_parse_info<IteratorT, AstFactoryT>
 297 ast_parse(
 298     IteratorT const&        first_,
 299     IteratorT const&        last_,
 300     parser<ParserT> const&  parser,
 301     SkipT const&            skip_,
 302     AstFactoryT const &   /*dummy_*/ = AstFactoryT())
 303 {
 304     typedef skip_parser_iteration_policy<SkipT> iter_policy_t;
 305     typedef ast_match_policy<IteratorT, AstFactoryT> ast_match_policy_t;
 306     typedef
 307         scanner_policies<iter_policy_t, ast_match_policy_t>
 308         scanner_policies_t;
 309     typedef scanner<IteratorT, scanner_policies_t> scanner_t;
 310
 311     iter_policy_t iter_policy(skip_);
 312     scanner_policies_t policies(iter_policy);
 313     IteratorT first = first_;
 314     scanner_t scan(first, last_, policies);
 315     tree_match<IteratorT, AstFactoryT> hit = parser.derived().parse(scan);
 316     return tree_parse_info<IteratorT, AstFactoryT>(
 317         first, hit, hit && (first == last_), hit.length(), hit.trees);
 318 }
 319
 320 //////////////////////////////////
 321 template <typename IteratorT, typename ParserT, typename SkipT>
 322 inline tree_parse_info<IteratorT>
 323 ast_parse(
 324     IteratorT const&        first_,
 325     IteratorT const&        last_,
 326     parser<ParserT> const&  parser,
 327     SkipT const&            skip_)
 328 {
 329     typedef node_val_data_factory<nil_t> default_factory_t;
 330     return ast_parse(first_, last_, parser, skip_, default_factory_t());
 331 }
 332
 333 //////////////////////////////////
 334 template <typename IteratorT, typename ParserT>
 335 inline tree_parse_info<IteratorT>
 336 ast_parse(
 337     IteratorT const&        first_,
 338     IteratorT const&        last,
 339     parser<ParserT> const&  parser)
 340 {
 341     typedef ast_match_policy<IteratorT> ast_match_policy_t;
 342     IteratorT first = first_;
 343     scanner<
 344         IteratorT,
 345         scanner_policies<iteration_policy, ast_match_policy_t>
 346     > scan(first, last);
 347     tree_match<IteratorT> hit = parser.derived().parse(scan);
 348     return tree_parse_info<IteratorT>(
 349         first, hit, hit && (first == last), hit.length(), hit.trees);
 350 }
 351
 352 //////////////////////////////////
 353 template <typename CharT, typename ParserT, typename SkipT>
 354 inline tree_parse_info<CharT const*>
 355 ast_parse(
 356     CharT const*            str,
 357     parser<ParserT> const&  parser,
 358     SkipT const&            skip)
 359 {
 360     CharT const* last = str;
 361     while (*last)
 362         last++;
 363     return ast_parse(str, last, parser, skip);
 364 }
 365
 366 //////////////////////////////////
 367 template <typename CharT, typename ParserT>
 368 inline tree_parse_info<CharT const*>
 369 ast_parse(
 370     CharT const*            str,
 371     parser<ParserT> const&  parser)
 372 {
 373     CharT const* last = str;
 374     while (*last)
 375     {
 376         last++;
 377     }
 378     return ast_parse(str, last, parser);
 379 }
 380
 381 ///////////////////////////////////////////////////////////////////////////////
 382 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
 383
 384 }} // namespace BOOST_SPIRIT_CLASSIC_NS
 385
 386 #endif
 387