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
ast_match_policyboost::spirit::ast_match_policy58 ast_match_policy()
59 {
60 }
61
62 template <typename PolicyT>
ast_match_policyboost::spirit::ast_match_policy63 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>
concatboost::spirit::ast_tree_policy78 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 necessary, 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>
group_matchboost::spirit::ast_tree_policy139 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>
apply_op_to_matchboost::spirit::ast_tree_policy191 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
gen_ast_node_parserboost::spirit::gen_ast_node_parser223 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
parseboost::spirit::gen_ast_node_parser228 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>
generateboost::spirit::gen_ast_node_parser_gen256 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>
operator []boost::spirit::gen_ast_node_parser_gen263 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>
operator ()boost::spirit::root_node_op277 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>
ast_parse(IteratorT const & first_,IteratorT const & last_,parser<ParserT> const & parser,SkipT const & skip_,AstFactoryT const &=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> it_policy_t;
305 typedef ast_match_policy<IteratorT, AstFactoryT> ast_match_policy_t;
306 typedef
307 scanner_policies<it_policy_t, ast_match_policy_t>
308 scan_policies_t;
309 typedef scanner<IteratorT, scan_policies_t> scanner_t;
310
311 it_policy_t iter_policy(skip_);
312 scan_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>
ast_parse(IteratorT const & first_,IteratorT const & last_,parser<ParserT> const & parser,SkipT const & skip_)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>
ast_parse(IteratorT const & first_,IteratorT const & last,parser<ParserT> const & parser)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*>
ast_parse(CharT const * str,parser<ParserT> const & parser,SkipT const & skip)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*>
ast_parse(CharT const * str,parser<ParserT> const & parser)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
388