1 /*=============================================================================
2 Copyright (c) 2002-2003 Hartmut Kaiser
3 http://spirit.sourceforge.net/
4
5 Use, modification and distribution is subject to the Boost Software
6 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
8 =============================================================================*/
9 ///////////////////////////////////////////////////////////////////////////////
10 //
11 // Traversal tests
12 //
13 ///////////////////////////////////////////////////////////////////////////////
14
15 #include <boost/detail/lightweight_test.hpp>
16 #include <iostream>
17 #include <string>
18 #include <vector>
19
20 #include <boost/config.hpp>
21 #include <boost/static_assert.hpp>
22
23 #ifdef BOOST_NO_STRINGSTREAM
24 #include <strstream>
25 #define OSSTREAM std::ostrstream
GETSTRING(std::ostrstream & ss)26 std::string GETSTRING(std::ostrstream& ss)
27 {
28 ss << ends;
29 std::string rval = ss.str();
30 ss.freeze(false);
31 return rval;
32 }
33 #else
34 #include <sstream>
35 #define GETSTRING(ss) ss.str()
36 #define OSSTREAM std::ostringstream
37 #endif
38
39 #ifndef BOOST_SPIRIT_DEBUG
40 #define BOOST_SPIRIT_DEBUG // needed for parser_name functions
41 #endif
42
43 #include <boost/spirit/include/classic_core.hpp>
44 #include <boost/spirit/include/classic_assign_actor.hpp>
45 #include <boost/spirit/include/classic_meta.hpp>
46
47 using namespace std;
48 using namespace BOOST_SPIRIT_CLASSIC_NS;
49
50 typedef ref_value_actor<char, assign_action> assign_actor;
51
52 ///////////////////////////////////////////////////////////////////////////////
53 //
54 // Test identity transformation
55 //
56 ///////////////////////////////////////////////////////////////////////////////
57 void
traverse_identity_tests()58 traverse_identity_tests()
59 {
60 // test type equality
61 typedef sequence<chlit<char>, chlit<char> > test_sequence1_t;
62 BOOST_STATIC_ASSERT((
63 ::boost::is_same<
64 test_sequence1_t,
65 post_order::result<identity_transform, test_sequence1_t>::type
66 >::value
67 ));
68
69 // test (rough) runtime equality
70 BOOST_TEST(
71 parse(
72 "ab",
73 post_order::traverse(identity_transform(), ch_p('a') >> 'b')
74 ).full
75 );
76 BOOST_TEST(
77 !parse(
78 "ba",
79 post_order::traverse(identity_transform(), ch_p('a') >> 'b')
80 ).hit
81 );
82
83 ///////////////////////////////////////////////////////////////////////////
84 BOOST_TEST(
85 !parse(
86 "cba",
87 post_order::traverse(
88 identity_transform(),
89 ch_p('a') >> 'b' >> 'c'
90 )
91 ).hit
92 );
93
94 ///////////////////////////////////////////////////////////////////////////////
95 // Test more complex sequences
96 char c;
97
98 ///////////////////////////////////////////////////////////////////////////////
99 // test: ((a >> b) >> c) >> d
100 typedef
101 sequence<
102 sequence<
103 sequence<
104 kleene_star<chlit<> >,
105 action<chlit<>, assign_actor>
106 >,
107 chlit<>
108 >,
109 optional<chlit<> >
110 > test_sequence2_t;
111
112 BOOST_STATIC_ASSERT((
113 ::boost::is_same<
114 test_sequence2_t,
115 post_order::result<identity_transform, test_sequence2_t>::type
116 >::value
117 ));
118
119 c = 0;
120 BOOST_TEST(
121 parse(
122 "aabcd",
123 post_order::traverse(
124 identity_transform(),
125 ((*ch_p('a') >> ch_p('b')[assign_a(c)]) >> 'c') >> !ch_p('d')
126 )
127 ).full
128 );
129 BOOST_TEST(c == 'b');
130
131 ///////////////////////////////////////////////////////////////////////////////
132 // test: (a >> (b >> c)) >> d
133 typedef
134 sequence<
135 sequence<
136 kleene_star<chlit<> >,
137 sequence<
138 action<chlit<>, assign_actor>,
139 chlit<>
140 >
141 >,
142 optional<chlit<char> >
143 > test_sequence3_t;
144
145 BOOST_STATIC_ASSERT((
146 ::boost::is_same<
147 test_sequence3_t,
148 post_order::result<identity_transform, test_sequence3_t>::type
149 >::value
150 ));
151
152 c = 0;
153 BOOST_TEST(
154 parse(
155 "aabcd",
156 post_order::traverse(
157 identity_transform(),
158 (*ch_p('a') >> (ch_p('b')[assign_a(c)] >> 'c')) >> !ch_p('d')
159 )
160 ).full
161 );
162 BOOST_TEST(c == 'b');
163
164 ///////////////////////////////////////////////////////////////////////////////
165 // test: a >> (b >> (c >> d))
166 typedef
167 sequence<
168 kleene_star<chlit<> >,
169 sequence<
170 action<chlit<>, assign_actor>,
171 sequence<
172 chlit<>,
173 optional<chlit<> >
174 >
175 >
176 > test_sequence4_t;
177
178 BOOST_STATIC_ASSERT((
179 ::boost::is_same<
180 test_sequence4_t,
181 post_order::result<identity_transform, test_sequence4_t>::type
182 >::value
183 ));
184
185 c = 0;
186 BOOST_TEST(
187 parse(
188 "aabcd",
189 post_order::traverse(
190 identity_transform(),
191 *ch_p('a') >> (ch_p('b')[assign_a(c)] >> ('c' >> !ch_p('d')))
192 )
193 ).full
194 );
195 BOOST_TEST(c == 'b');
196
197 ///////////////////////////////////////////////////////////////////////////////
198 // test: a >> ((b >> c) >> d)
199 typedef
200 sequence<
201 kleene_star<chlit<> >,
202 sequence<
203 sequence<
204 action<chlit<>, assign_actor>,
205 chlit<>
206 >,
207 optional<chlit<> >
208 >
209 > test_sequence5_t;
210
211 BOOST_STATIC_ASSERT((
212 ::boost::is_same<
213 test_sequence5_t,
214 post_order::result<identity_transform, test_sequence5_t>::type
215 >::value
216 ));
217
218 c = 0;
219 BOOST_TEST(
220 parse(
221 "aabcd",
222 post_order::traverse(
223 identity_transform(),
224 *ch_p('a') >> ((ch_p('b')[assign_a(c)] >> 'c') >> !ch_p('d'))
225 )
226 ).full
227 );
228 BOOST_TEST(c == 'b');
229
230 ///////////////////////////////////////////////////////////////////////////////
231 // test: (a >> b) >> (c >> d)
232 typedef
233 sequence<
234 sequence<
235 kleene_star<chlit<> >,
236 action<chlit<>, assign_actor>
237 >,
238 sequence<
239 chlit<>,
240 optional<chlit<> >
241 >
242 > test_sequence6_t;
243
244 BOOST_STATIC_ASSERT((
245 ::boost::is_same<
246 test_sequence6_t,
247 post_order::result<identity_transform, test_sequence6_t>::type
248 >::value
249 ));
250
251 c = 0;
252 BOOST_TEST(
253 parse(
254 "aabcd",
255 post_order::traverse(
256 identity_transform(),
257 (*ch_p('a') >> ch_p('b')[assign_a(c)]) >> ('c' >> !ch_p('d'))
258 )
259 ).full
260 );
261 BOOST_TEST(c == 'b');
262 }
263
264 ///////////////////////////////////////////////////////////////////////////////
265 //
266 // The following is a tracing identity_transform traverse metafunction
267 //
268 ///////////////////////////////////////////////////////////////////////////////
269
270 class trace_identity_transform
271 : public transform_policies<trace_identity_transform> {
272
273 public:
274 typedef trace_identity_transform self_t;
275 typedef transform_policies<trace_identity_transform> base_t;
276
277 template <typename ParserT, typename EnvT>
278 typename parser_traversal_plain_result<self_t, ParserT, EnvT>::type
generate_plain(ParserT const & parser_,EnvT const & env) const279 generate_plain(ParserT const &parser_, EnvT const &env) const
280 {
281 OSSTREAM strout;
282 strout
283 << EnvT::node
284 << ": plain ("
285 << EnvT::level << ", "
286 << EnvT::index
287 << "): "
288 << parser_name(parser_);
289 traces.push_back(GETSTRING(strout));
290
291 return this->base_t::generate_plain(parser_, env);
292 }
293
294 template <typename UnaryT, typename SubjectT, typename EnvT>
295 typename parser_traversal_unary_result<self_t, UnaryT, SubjectT, EnvT>::type
generate_unary(UnaryT const & unary_,SubjectT const & subject_,EnvT const & env) const296 generate_unary(UnaryT const &unary_, SubjectT const &subject_,
297 EnvT const &env) const
298 {
299 OSSTREAM strout;
300 strout
301 << EnvT::node << ": unary ("
302 << EnvT::level
303 << "): "
304 << parser_name(unary_);
305 traces.push_back(GETSTRING(strout));
306
307 return this->base_t::generate_unary(unary_, subject_, env);
308 }
309
310 template <typename ActionT, typename SubjectT, typename EnvT>
311 typename parser_traversal_action_result<self_t, ActionT, SubjectT, EnvT>::type
generate_action(ActionT const & action_,SubjectT const & subject_,EnvT const & env) const312 generate_action(ActionT const &action_, SubjectT const &subject_,
313 EnvT const &env) const
314 {
315 OSSTREAM strout;
316 strout
317 << EnvT::node << ": action("
318 << EnvT::level
319 << "): "
320 << parser_name(action_);
321 traces.push_back(GETSTRING(strout));
322
323 return this->base_t::generate_action(action_, subject_, env);
324 }
325
326 template <typename BinaryT, typename LeftT, typename RightT, typename EnvT>
327 typename parser_traversal_binary_result<self_t, BinaryT, LeftT, RightT, EnvT>::type
generate_binary(BinaryT const & binary_,LeftT const & left_,RightT const & right_,EnvT const & env) const328 generate_binary(BinaryT const &binary_, LeftT const& left_,
329 RightT const& right_, EnvT const &env) const
330 {
331 OSSTREAM strout;
332 strout
333 << EnvT::node << ": binary("
334 << EnvT::level
335 << "): "
336 << parser_name(binary_);
337 traces.push_back(GETSTRING(strout));
338
339 return this->base_t::generate_binary(binary_, left_, right_, env);
340 }
341
get_output() const342 std::vector<string> const &get_output() const { return traces; }
343
344 private:
345 mutable std::vector<std::string> traces;
346 };
347
348 template <typename ParserT>
349 void
post_order_trace_test(ParserT const & parser_,char const * first[],size_t cnt)350 post_order_trace_test(ParserT const &parser_, char const *first[], size_t cnt)
351 {
352 // traverse
353 trace_identity_transform trace_vector;
354
355 post_order::traverse(trace_vector, parser_);
356
357 // The following two re-find loops ensure, that both string arrays contain the
358 // same entries, only their order may differ. The differences in the trace
359 // string order is based on the different parameter evaluation order as it is
360 // implemented by different compilers.
361
362 // re-find all trace strings in the array of expected strings
363 std::vector<std::string>::const_iterator it = trace_vector.get_output().begin();
364 std::vector<std::string>::const_iterator end = trace_vector.get_output().end();
365
366 BOOST_TEST(cnt == trace_vector.get_output().size());
367 for (/**/; it != end; ++it)
368 {
369 if (std::find(first, first + cnt, *it) == first + cnt)
370 cerr << "node in question: " << *it << endl;
371
372 BOOST_TEST(std::find(first, first + cnt, *it) != first + cnt);
373 }
374
375 // re-find all expected strings in the vector of trace strings
376 std::vector<std::string>::const_iterator begin = trace_vector.get_output().begin();
377 char const *expected = first[0];
378
379 for (size_t i = 0; i < cnt; expected = first[++i])
380 {
381 if (std::find(begin, end, std::string(expected)) == end)
382 cerr << "node in question: " << expected << endl;
383
384 BOOST_TEST(std::find(begin, end, std::string(expected)) != end);
385 }
386 }
387
388 #if defined(_countof)
389 #undef _countof
390 #endif
391 #define _countof(x) (sizeof(x)/sizeof(x[0]))
392
393 void
traverse_trace_tests()394 traverse_trace_tests()
395 {
396 const char *test_result1[] = {
397 "0: plain (1, 0): chlit('a')",
398 "1: plain (1, 1): chlit('b')",
399 "2: binary(0): sequence[chlit('a'), chlit('b')]",
400 };
401
402 post_order_trace_test(
403 ch_p('a') >> 'b',
404 test_result1, _countof(test_result1)
405 );
406
407 char c = 0;
408
409 // test: ((a >> b) >> c) >> d
410 const char *test_result2[] = {
411 "0: plain (4, 0): chlit('a')",
412 "1: unary (3): kleene_star[chlit('a')]",
413 "2: plain (4, 1): chlit('b')",
414 "3: action(3): action[chlit('b')]",
415 "4: binary(2): sequence[kleene_star[chlit('a')], action[chlit('b')]]",
416 "5: plain (2, 2): chlit('c')",
417 "6: binary(1): sequence[sequence[kleene_star[chlit('a')], action[chlit('b')]], chlit('c')]",
418 "7: plain (2, 3): chlit('d')",
419 "8: unary (1): optional[chlit('d')]",
420 "9: binary(0): sequence[sequence[sequence[kleene_star[chlit('a')], action[chlit('b')]], chlit('c')], optional[chlit('d')]]",
421 };
422
423 post_order_trace_test(
424 ((*ch_p('a') >> ch_p('b')[assign_a(c)]) >> 'c') >> !ch_p('d'),
425 test_result2, _countof(test_result2)
426 );
427
428 // test: (a >> (b >> c)) >> d
429 const char *test_result3[] = {
430 "0: plain (3, 0): chlit('a')",
431 "1: unary (2): kleene_star[chlit('a')]",
432 "2: plain (4, 1): chlit('b')",
433 "3: action(3): action[chlit('b')]",
434 "4: plain (3, 2): chlit('c')",
435 "5: binary(2): sequence[action[chlit('b')], chlit('c')]",
436 "6: binary(1): sequence[kleene_star[chlit('a')], sequence[action[chlit('b')], chlit('c')]]",
437 "7: plain (2, 3): chlit('d')",
438 "8: unary (1): optional[chlit('d')]",
439 "9: binary(0): sequence[sequence[kleene_star[chlit('a')], sequence[action[chlit('b')], chlit('c')]], optional[chlit('d')]]",
440 };
441
442 post_order_trace_test(
443 (*ch_p('a') >> (ch_p('b')[assign_a(c)] >> 'c')) >> !ch_p('d'),
444 test_result3, _countof(test_result3)
445 );
446
447 // test: a >> (b >> (c >> d))
448 const char *test_result4[] = {
449 "0: plain (2, 0): chlit('a')",
450 "1: unary (1): kleene_star[chlit('a')]",
451 "2: plain (3, 1): chlit('b')",
452 "3: action(2): action[chlit('b')]",
453 "4: plain (3, 2): chlit('c')",
454 "5: plain (4, 3): chlit('d')",
455 "6: unary (3): optional[chlit('d')]",
456 "7: binary(2): sequence[chlit('c'), optional[chlit('d')]]",
457 "8: binary(1): sequence[action[chlit('b')], sequence[chlit('c'), optional[chlit('d')]]]",
458 "9: binary(0): sequence[kleene_star[chlit('a')], sequence[action[chlit('b')], sequence[chlit('c'), optional[chlit('d')]]]]",
459 };
460
461 post_order_trace_test(
462 *ch_p('a') >> (ch_p('b')[assign_a(c)] >> ('c' >> !ch_p('d'))),
463 test_result4, _countof(test_result4)
464 );
465
466 // test: a >> ((b >> c) >> d)
467 const char *test_result5[] = {
468 "0: plain (2, 0): chlit('a')",
469 "1: unary (1): kleene_star[chlit('a')]",
470 "2: plain (4, 1): chlit('b')",
471 "3: action(3): action[chlit('b')]",
472 "4: plain (3, 2): chlit('c')",
473 "5: binary(2): sequence[action[chlit('b')], chlit('c')]",
474 "6: plain (3, 3): chlit('d')",
475 "7: unary (2): optional[chlit('d')]",
476 "8: binary(1): sequence[sequence[action[chlit('b')], chlit('c')], optional[chlit('d')]]",
477 "9: binary(0): sequence[kleene_star[chlit('a')], sequence[sequence[action[chlit('b')], chlit('c')], optional[chlit('d')]]]",
478 };
479
480 post_order_trace_test(
481 *ch_p('a') >> ((ch_p('b')[assign_a(c)] >> 'c') >> !ch_p('d')),
482 test_result5, _countof(test_result5)
483 );
484
485 // test: (a >> b) >> (c >> d)
486 const char *test_result6[] = {
487 "0: plain (3, 0): chlit('a')",
488 "1: unary (2): kleene_star[chlit('a')]",
489 "2: plain (3, 1): chlit('b')",
490 "3: action(2): action[chlit('b')]",
491 "4: binary(1): sequence[kleene_star[chlit('a')], action[chlit('b')]]",
492 "5: plain (2, 2): chlit('c')",
493 "6: plain (3, 3): chlit('d')",
494 "7: unary (2): optional[chlit('d')]",
495 "8: binary(1): sequence[chlit('c'), optional[chlit('d')]]",
496 "9: binary(0): sequence[sequence[kleene_star[chlit('a')], action[chlit('b')]], sequence[chlit('c'), optional[chlit('d')]]]",
497 };
498
499 post_order_trace_test(
500 (*ch_p('a') >> ch_p('b')[assign_a(c)]) >> ('c' >> !ch_p('d')),
501 test_result6, _countof(test_result6)
502 );
503 }
504
505 ///////////////////////////////////////////////////////////////////////////////
506 //
507 // Main
508 //
509 ///////////////////////////////////////////////////////////////////////////////
510 int
main()511 main()
512 {
513 traverse_identity_tests();
514 traverse_trace_tests();
515
516 return boost::report_errors();
517 }
518
519