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