1/*=============================================================================
2 Copyright (c) 2001-2011 Joel de Guzman
3 Copyright (c) 2001-2011 Hartmut Kaiser
4 Copyright (c) 2010-2011 Bryce Lelbach
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#if !defined(BOOST_SPIRIT_UTREE)
10#define BOOST_SPIRIT_UTREE
11
12#include <cstddef>
13#include <algorithm>
14#include <string>
15#include <ios>
16#include <sstream>
17#include <typeinfo>
18
19#include <boost/io/ios_state.hpp>
20#include <boost/integer.hpp>
21#include <boost/throw_exception.hpp>
22#include <boost/assert.hpp>
23#include <boost/noncopyable.hpp>
24#include <boost/iterator/iterator_facade.hpp>
25#include <boost/range/iterator_range_core.hpp>
26#include <boost/type_traits/remove_pointer.hpp>
27#include <boost/type_traits/is_polymorphic.hpp>
28#include <boost/utility/enable_if.hpp>
29#include <boost/utility/result_of.hpp>
30#include <boost/ref.hpp>
31#include <boost/config.hpp>
32
33#include <boost/spirit/home/support/utree/detail/utree_detail1.hpp>
34
35#if defined(BOOST_MSVC)
36# pragma warning(push)
37# pragma warning(disable: 4804)
38# pragma warning(disable: 4805)
39# pragma warning(disable: 4244)
40#endif
41
42namespace boost { namespace spirit
43{
44 //[utree_exceptions
45 /*` All exceptions thrown by utree are derived from utree_exception. */
46 struct BOOST_SYMBOL_VISIBLE utree_exception : std::exception {};
47
48 /*`The `bad_type_exception` is thrown whenever somebody calls a member
49 function, which applies to certain stored utree_type's only, but this
50 precondition is violated as the `utree` instance holds some other type.
51 */
52 struct bad_type_exception /*: utree_exception*/;
53
54 /*`The `empty_exception` is thrown whenever a precondition of a list
55 or range utree method is violated due to the list or range being empty.
56 */
57 struct empty_exception /*: utree_exception*/;
58 //]
59
60 //[utree_types
61 /*`Each instance of an `utree` data structure can store exactly one of the
62 following data types at a time:
63 */
64 struct utree_type
65 {
66 enum info
67 {
68 invalid_type, // the utree has not been initialized (it's
69 // default constructed)
70 nil_type, // nil is the sentinel (empty) utree type.
71 list_type, // A doubly linked list of utrees.
72 range_type, // A range of list::iterators.
73 reference_type, // A reference to another utree.
74 any_type, // A pointer or reference to any C++ type.
75 function_type, // A utree holding a stored_function<F> object,
76 // where F is an unary function object taking a
77 // utree as it's parameter and returning a
78 // utree.
79
80 // numeric atoms
81 bool_type, // An utree holding a boolean value
82 int_type, // An utree holding a integer (int) value
83 double_type, // An utree holding a floating point (double) value
84
85 // text atoms (utf8)
86 string_type, // An UTF-8 string
87 string_range_type, // A pair of iterators into an UTF-8 string
88 symbol_type, // An UTF-8 symbol name
89
90 binary_type // Arbitrary binary data
91 };
92 typedef boost::uint_t<sizeof(info)*8>::exact exact_integral_type;
93 typedef boost::uint_t<sizeof(info)*8>::fast fast_integral_type;
94 };
95 //]
96
97 // streaming operator for utree types - essential for diagnostics
98 inline std::ostream& operator<<(std::ostream& out, utree_type::info t)
99 {
100 boost::io::ios_all_saver saver(out);
101 switch (t) {
102 case utree_type::invalid_type: { out << "invalid"; break; }
103 case utree_type::nil_type: { out << "nil"; break; }
104 case utree_type::list_type: { out << "list"; break; }
105 case utree_type::range_type: { out << "range"; break; }
106 case utree_type::reference_type: { out << "reference"; break; }
107 case utree_type::any_type: { out << "any"; break; }
108 case utree_type::function_type: { out << "function"; break; }
109 case utree_type::bool_type: { out << "bool"; break; }
110 case utree_type::int_type: { out << "int"; break; }
111 case utree_type::double_type: { out << "double"; break; }
112 case utree_type::string_type: { out << "string"; break; }
113 case utree_type::string_range_type: { out << "string_range"; break; }
114 case utree_type::symbol_type: { out << "symbol"; break; }
115 case utree_type::binary_type: { out << "binary"; break; }
116 default: { out << "unknown"; break; }
117 }
118 out << std::hex << "[0x"
119 << static_cast<utree_type::fast_integral_type>(t) << "]";
120 return out;
121 }
122
123 struct bad_type_exception : utree_exception
124 {
125 std::string msg;
126
127 bad_type_exception(char const* error, utree_type::info got)
128 : msg()
129 {
130 std::ostringstream oss;
131 oss << "utree: " << error
132 << " (got utree type '" << got << "')";
133 msg = oss.str();
134 }
135
136 bad_type_exception(char const* error, utree_type::info got1,
137 utree_type::info got2)
138 : msg()
139 {
140 std::ostringstream oss;
141 oss << "utree: " << error
142 << " (got utree types '" << got1 << "' and '" << got2 << "')";
143 msg = oss.str();
144 }
145
146 virtual ~bad_type_exception() BOOST_NOEXCEPT_OR_NOTHROW {}
147
148 virtual char const* what() const BOOST_NOEXCEPT_OR_NOTHROW
149 { return msg.c_str(); }
150 };
151
152 struct empty_exception : utree_exception
153 {
154 char const* msg;
155
156 empty_exception(char const* error) : msg(error) {}
157
158 virtual ~empty_exception() BOOST_NOEXCEPT_OR_NOTHROW {}
159
160 virtual char const* what() const BOOST_NOEXCEPT_OR_NOTHROW
161 { return msg; }
162 };
163
164 ///////////////////////////////////////////////////////////////////////////
165 // A typed string with parametric Base storage. The storage can be any
166 // range or (stl container) of chars.
167 ///////////////////////////////////////////////////////////////////////////
168 template <typename Base, utree_type::info type_>
169 struct basic_string : Base
170 {
171 static utree_type::info const type = type_;
172
173 basic_string()
174 : Base() {}
175
176 basic_string(Base const& base)
177 : Base(base) {}
178
179 template <typename Iterator>
180 basic_string(Iterator bits, std::size_t len)
181 : Base(bits, bits + len) {}
182
183 template <typename Iterator>
184 basic_string(Iterator first, Iterator last)
185 : Base(first, last) {}
186
187 basic_string& operator=(Base const& other)
188 {
189 Base::operator=(other);
190 return *this;
191 }
192 };
193
194 //[utree_strings
195 /*`The `utree` string types described below are used by the `utree` API
196 only. These are not used to store information in the `utree` itself.
197 Their purpose is to refer to different internal `utree` node types
198 only. For instance, creating a `utree` from a binary data type will
199 create a `binary_type` utree node (see above).
200 */
201 /*`The binary data type can be represented either verbatim as a sequence
202 of bytes or as a pair of iterators into some other stored binary data
203 sequence. Use this string type to access/create a `binary_type` `utree`.
204 */
205 typedef basic_string<
206 boost::iterator_range<char const*>, utree_type::binary_type
207 > binary_range_type;
208 typedef basic_string<
209 std::string, utree_type::binary_type
210 > binary_string_type;
211
212 /*`The UTF-8 string can be represented either verbatim as a sequence of
213 characters or as a pair of iterators into some other stored binary data
214 sequence. Use this string type to access/create a `string_type` `utree`.
215 */
216 typedef basic_string<
217 boost::iterator_range<char const*>, utree_type::string_type
218 > utf8_string_range_type;
219 typedef basic_string<
220 std::string, utree_type::string_type
221 > utf8_string_type;
222
223 /*`The UTF-8 symbol can be represented either verbatim as a sequence of
224 characters or as a pair of iterators into some other stored binary data
225 sequence. Use this string type to access/create a `symbol_type` `utree`.
226 */
227 typedef basic_string<
228 boost::iterator_range<char const*>, utree_type::symbol_type
229 > utf8_symbol_range_type;
230 typedef basic_string<
231 std::string, utree_type::symbol_type
232 > utf8_symbol_type;
233 //]
234
235 ///////////////////////////////////////////////////////////////////////////
236 // Our function type
237 ///////////////////////////////////////////////////////////////////////////
238 class utree;
239
240 //[utree_function_object_interface
241 struct function_base
242 {
243 virtual ~function_base() {}
244 virtual utree operator()(utree const& env) const = 0;
245 virtual utree operator()(utree& env) const = 0;
246
247 // Calling f.clone() must return a newly allocated function_base
248 // instance that is equal to f.
249 virtual function_base* clone() const = 0;
250 };
251
252 template <typename F>
253 struct stored_function : function_base
254 {
255 F f;
256 stored_function(F f = F());
257 virtual ~stored_function();
258 virtual utree operator()(utree const& env) const;
259 virtual utree operator()(utree& env) const;
260 virtual function_base* clone() const;
261 };
262
263 template <typename F>
264 struct referenced_function : function_base
265 {
266 F& f;
267 referenced_function(F& f);
268 virtual ~referenced_function();
269 virtual utree operator()(utree const& env) const;
270 virtual utree operator()(utree& env) const;
271 virtual function_base* clone() const;
272 };
273 //]
274
275 ///////////////////////////////////////////////////////////////////////////
276 // Shallow tag. Instructs utree to hold an iterator_range
277 // as-is without deep copying the range.
278 ///////////////////////////////////////////////////////////////////////////
279 struct shallow_tag {};
280 shallow_tag const shallow = {};
281
282 ///////////////////////////////////////////////////////////////////////////
283 // A void* plus type_info
284 ///////////////////////////////////////////////////////////////////////////
285 class any_ptr
286 {
287 public:
288 template <typename Ptr>
289 typename boost::disable_if<
290 boost::is_polymorphic<
291 typename boost::remove_pointer<Ptr>::type>,
292 Ptr>::type
293 get() const
294 {
295 if (*i == typeid(Ptr))
296 {
297 return static_cast<Ptr>(p);
298 }
299 boost::throw_exception(e: std::bad_cast());
300 }
301
302 template <typename T>
303 any_ptr(T* p)
304 : p(p), i(&typeid(T*))
305 {}
306
307 friend bool operator==(any_ptr const& a, any_ptr const& b)
308 {
309 return (a.p == b.p) && (*a.i == *b.i);
310 }
311
312 private:
313 // constructor is private
314 any_ptr(void* p, std::type_info const* i)
315 : p(p), i(i) {}
316
317 template <typename UTreeX, typename UTreeY>
318 friend struct detail::visit_impl;
319
320 friend class utree;
321
322 void* p;
323 std::type_info const* i;
324 };
325
326 //[utree
327 class utree {
328 public:
329 ///////////////////////////////////////////////////////////////////////
330 // The invalid type
331 struct invalid_type {};
332
333 ///////////////////////////////////////////////////////////////////////
334 // The nil type
335 struct nil_type {};
336
337 ///////////////////////////////////////////////////////////////////////
338 // The list type, this can be used to initialize an utree to hold an
339 // empty list
340 struct list_type;
341
342 //[utree_container_types
343 typedef utree value_type;
344 typedef utree& reference;
345 typedef utree const& const_reference;
346 typedef std::ptrdiff_t difference_type;
347 typedef std::size_t size_type;
348
349 typedef detail::list::node_iterator<utree> iterator;
350 typedef detail::list::node_iterator<utree const> const_iterator;
351 //]
352
353 typedef detail::list::node_iterator<boost::reference_wrapper<utree> >
354 ref_iterator;
355
356 typedef boost::iterator_range<iterator> range;
357 typedef boost::iterator_range<const_iterator> const_range;
358
359 // dtor
360 ~utree();
361
362 ////////////////////////////////////////////////////////////////////////
363 //[utree_initialization
364 /*`A `utree` can be constructed or initialized from a wide range of
365 data types, allowing to create `utree` instances for every
366 possible node type (see the description of `utree_type::info` above).
367 For this reason it exposes a constructor and an assignment operator
368 for each of the allowed node types as shown below. All constructors
369 are non-explicit on purpose, allowing to use an utree instance as
370 the attribute to almost any Qi parser.
371 */
372 // This constructs an `invalid_type` node. When used in places
373 // where a boost::optional is expected (i.e. as an attribute for the
374 // optional component), this represents the 'empty' state.
375 utree(invalid_type = invalid_type());
376
377 // This initializes a `nil_type` node, which represents a valid,
378 // 'initialized empty' utree (different from invalid_type!).
379 utree(nil_type);
380 reference operator=(nil_type);
381
382 // This initializes a `boolean_type` node, which can hold 'true' or
383 // 'false' only.
384 explicit utree(bool);
385 reference operator=(bool);
386
387 // This initializes an `integer_type` node, which can hold arbitrary
388 // integers. For convenience these functions are overloaded for signed
389 // and unsigned integer types.
390 utree(unsigned int);
391 utree(int);
392 reference operator=(unsigned int);
393 reference operator=(int);
394
395 // This initializes a `double_type` node, which can hold arbitrary
396 // floating point (double) values.
397 utree(double);
398 reference operator=(double);
399
400 // This initializes a `string_type` node, which can hold a narrow
401 // character sequence (usually an UTF-8 string).
402 utree(char);
403 utree(char const*);
404 utree(char const*, std::size_t);
405 utree(std::string const&);
406 reference operator=(char);
407 reference operator=(char const*);
408 reference operator=(std::string const&);
409
410 // This constructs a `string_range_type` node, which does not copy the
411 // data but stores the iterator range to the character sequence the
412 // range has been initialized from.
413 utree(utf8_string_range_type const&, shallow_tag);
414
415 // This initializes a `reference_type` node, which holds a reference to
416 // another utree node. All operations on such a node are automatically
417 // forwarded to the referenced utree instance.
418 utree(boost::reference_wrapper<utree>);
419 reference operator=(boost::reference_wrapper<utree>);
420
421 // This initializes an `any_type` node, which can hold a pointer to an
422 // instance of any type together with the typeid of that type. When
423 // accessing that pointer the typeid will be checked, causing a
424 // std::bad_cast to be thrown if the typeids do not match.
425 utree(any_ptr const&);
426 reference operator=(any_ptr const&);
427
428 // This initializes a `range_type` node, which holds an utree list node
429 // the elements of which are copy constructed (assigned) from the
430 // elements referenced by the given range of iterators.
431 template <class Iterator>
432 utree(boost::iterator_range<Iterator>);
433 template <class Iterator>
434 reference operator=(boost::iterator_range<Iterator>);
435
436 // This initializes a `function_type` node from a polymorphic function
437 // object pointer (takes ownership) or reference.
438 utree(function_base const&);
439 reference operator=(function_base const&);
440 utree(function_base*);
441 reference operator=(function_base*);
442
443 // This initializes either a `string_type`, a `symbol_type`, or a
444 // `binary_type` node (depending on the template parameter `type_`),
445 // which will hold the corresponding narrow character sequence (usually
446 // an UTF-8 string).
447 template <class Base, utree_type::info type_>
448 utree(basic_string<Base, type_> const&);
449 template <class Base, utree_type::info type_>
450 reference operator=(basic_string<Base, type_> const&);
451 //]
452
453 // copy
454 utree(const_reference);
455 reference operator=(const_reference);
456
457 // range
458 utree(range, shallow_tag);
459 utree(const_range, shallow_tag);
460
461 // assign dispatch
462 template <class Iterator>
463 void assign(Iterator, Iterator);
464
465 ////////////////////////////////////////////////////////////////////////
466
467 ////////////////////////////////////////////////////////////////////////
468 // function object visitation interface
469
470 // single dispatch
471 template <class F>
472 typename boost::result_of<F(utree const&)>::type
473 static visit(utree const&, F);
474
475 template <class F>
476 typename boost::result_of<F(utree&)>::type
477 static visit(utree&, F);
478
479 // double dispatch
480 template <class F>
481 typename boost::result_of<F(utree const&, utree const&)>::type
482 static visit(utree const&, utree const&, F);
483
484 template <class F>
485 typename boost::result_of<F(utree&, utree const&)>::type
486 static visit(utree&, utree const&, F);
487
488 template <class F>
489 typename boost::result_of<F(utree const&, utree&)>::type
490 static visit(utree const&, utree&, F);
491
492 template <class F>
493 typename boost::result_of<F(utree&, utree&)>::type
494 static visit(utree&, utree&, F);
495
496 ////////////////////////////////////////////////////////////////////////
497
498 ///////////////////////////////////////////////////////////////////////
499 //[utree_container_functions
500 // STL Container interface
501
502 // insertion
503 template <class T>
504 void push_back(T const&);
505 template <class T>
506 void push_front(T const&);
507 template <class T>
508 iterator insert(iterator, T const&);
509 template <class T>
510 void insert(iterator, std::size_t, T const&);
511 template <class Iterator>
512 void insert(iterator, Iterator, Iterator);
513
514 // erasure
515 void pop_front();
516 void pop_back();
517 iterator erase(iterator);
518 iterator erase(iterator, iterator);
519
520 // front access
521 reference front();
522 const_reference front() const;
523 iterator begin();
524 const_iterator begin() const;
525 ref_iterator ref_begin();
526
527 // back access
528 reference back();
529 const_reference back() const;
530 iterator end();
531 const_iterator end() const;
532 ref_iterator ref_end();
533 //]
534
535 // This clears the utree instance and resets its type to `invalid_type`
536 void clear();
537
538 void swap(utree&);
539
540 bool empty() const;
541
542 size_type size() const;
543 /*`[warning `size()` has O(n) complexity on `utree` ranges. On utree
544 lists, it has O(1) complexity.]`*/
545
546 ////////////////////////////////////////////////////////////////////////
547
548 //[utree_variant_functions
549 // return the data type (`utree_type::info`) of the currently stored
550 // data item
551 utree_type::info which() const;
552
553 // access the currently stored data in a type safe manner, this will
554 // throw a `std::bad_cast()` if the currently stored data item is not
555 // default convertible to `T`.
556 template <class T>
557 T get() const;
558 //]
559
560 reference deref();
561 const_reference deref() const;
562
563 short tag() const;
564 void tag(short);
565
566 utree eval(utree const&) const;
567 utree eval(utree&) const;
568
569 utree operator() (utree const&) const;
570 utree operator() (utree&) const;
571 //<-
572 protected:
573 void ensure_list_type(char const* failed_in = "ensure_list_type()");
574
575 private:
576 typedef utree_type type;
577
578 template <class UTreeX, class UTreeY>
579 friend struct detail::visit_impl;
580 friend struct detail::index_impl;
581
582 type::info get_type() const;
583 void set_type(type::info);
584 void free();
585 void copy(const_reference);
586
587 union {
588 detail::fast_string s;
589 detail::list l;
590 detail::range r;
591 detail::string_range sr;
592 detail::void_ptr v;
593 bool b;
594 int i;
595 double d;
596 utree* p;
597 function_base* pf;
598 };
599 //->
600 };
601 //]
602
603 //[utree_tuple_interface
604 /*<-*/inline/*->*/
605 utree::reference get(utree::reference, utree::size_type);
606 /*<-*/inline/*->*/
607 utree::const_reference get(utree::const_reference, utree::size_type);
608 /*`[warning `get()` has O(n) complexity.]`*/
609 //]
610
611 struct utree::list_type : utree
612 {
613 using utree::operator=;
614
615 list_type() : utree() { ensure_list_type(failed_in: "list_type()"); }
616
617 template <typename T0>
618 list_type(T0 t0) : utree(t0) {}
619
620 template <typename T0, typename T1>
621 list_type(T0 t0, T1 t1) : utree(t0, t1) {}
622 };
623
624 ///////////////////////////////////////////////////////////////////////////
625 // predefined instances for singular types
626 utree::invalid_type const invalid = {};
627 utree::nil_type const nil = {};
628 utree::list_type const empty_list = utree::list_type();
629}}
630
631#if defined(BOOST_MSVC)
632 #pragma warning(pop)
633#endif
634
635#endif
636
637

source code of boost/libs/spirit/include/boost/spirit/home/support/utree/utree.hpp