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