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.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=(basic_string const& other) 189 { 190 Base::operator=(other); 191 return *this; 192 } 193 operator =boost::spirit::basic_string194 basic_string& operator=(Base const& other) 195 { 196 Base::operator=(other); 197 return *this; 198 } 199 }; 200 201 //[utree_strings 202 /*`The `utree` string types described below are used by the `utree` API 203 only. These are not used to store information in the `utree` itself. 204 Their purpose is to refer to different internal `utree` node types 205 only. For instance, creating a `utree` from a binary data type will 206 create a `binary_type` utree node (see above). 207 */ 208 /*`The binary data type can be represented either verbatim as a sequence 209 of bytes or as a pair of iterators into some other stored binary data 210 sequence. Use this string type to access/create a `binary_type` `utree`. 211 */ 212 typedef basic_string< 213 boost::iterator_range<char const*>, utree_type::binary_type 214 > binary_range_type; 215 typedef basic_string< 216 std::string, utree_type::binary_type 217 > binary_string_type; 218 219 /*`The UTF-8 string can be represented either verbatim as a sequence of 220 characters or as a pair of iterators into some other stored binary data 221 sequence. Use this string type to access/create a `string_type` `utree`. 222 */ 223 typedef basic_string< 224 boost::iterator_range<char const*>, utree_type::string_type 225 > utf8_string_range_type; 226 typedef basic_string< 227 std::string, utree_type::string_type 228 > utf8_string_type; 229 230 /*`The UTF-8 symbol can be represented either verbatim as a sequence of 231 characters or as a pair of iterators into some other stored binary data 232 sequence. Use this string type to access/create a `symbol_type` `utree`. 233 */ 234 typedef basic_string< 235 boost::iterator_range<char const*>, utree_type::symbol_type 236 > utf8_symbol_range_type; 237 typedef basic_string< 238 std::string, utree_type::symbol_type 239 > utf8_symbol_type; 240 //] 241 242 /////////////////////////////////////////////////////////////////////////// 243 // Our function type 244 /////////////////////////////////////////////////////////////////////////// 245 class utree; 246 247 //[utree_function_object_interface 248 struct function_base 249 { ~function_baseboost::spirit::function_base250 virtual ~function_base() {} 251 virtual utree operator()(utree const& env) const = 0; 252 virtual utree operator()(utree& env) const = 0; 253 254 // Calling f.clone() must return a newly allocated function_base 255 // instance that is equal to f. 256 virtual function_base* clone() const = 0; 257 }; 258 259 template <typename F> 260 struct stored_function : function_base 261 { 262 F f; 263 stored_function(F f = F()); 264 virtual ~stored_function(); 265 virtual utree operator()(utree const& env) const; 266 virtual utree operator()(utree& env) const; 267 virtual function_base* clone() const; 268 }; 269 270 template <typename F> 271 struct referenced_function : function_base 272 { 273 F& f; 274 referenced_function(F& f); 275 virtual ~referenced_function(); 276 virtual utree operator()(utree const& env) const; 277 virtual utree operator()(utree& env) const; 278 virtual function_base* clone() const; 279 }; 280 //] 281 282 /////////////////////////////////////////////////////////////////////////// 283 // Shallow tag. Instructs utree to hold an iterator_range 284 // as-is without deep copying the range. 285 /////////////////////////////////////////////////////////////////////////// 286 struct shallow_tag {}; 287 shallow_tag const shallow = {}; 288 289 /////////////////////////////////////////////////////////////////////////// 290 // A void* plus type_info 291 /////////////////////////////////////////////////////////////////////////// 292 class any_ptr 293 { 294 public: 295 template <typename Ptr> 296 typename boost::disable_if< 297 boost::is_polymorphic< 298 typename boost::remove_pointer<Ptr>::type>, 299 Ptr>::type get() const300 get() const 301 { 302 if (*i == typeid(Ptr)) 303 { 304 return static_cast<Ptr>(p); 305 } 306 boost::throw_exception(std::bad_cast()); 307 } 308 309 template <typename T> any_ptr(T * p)310 any_ptr(T* p) 311 : p(p), i(&typeid(T*)) 312 {} 313 operator ==(any_ptr const & a,any_ptr const & b)314 friend bool operator==(any_ptr const& a, any_ptr const& b) 315 { 316 return (a.p == b.p) && (*a.i == *b.i); 317 } 318 319 private: 320 // constructor is private any_ptr(void * p,std::type_info const * i)321 any_ptr(void* p, std::type_info const* i) 322 : p(p), i(i) {} 323 324 template <typename UTreeX, typename UTreeY> 325 friend struct detail::visit_impl; 326 327 friend class utree; 328 329 void* p; 330 std::type_info const* i; 331 }; 332 333 //[utree 334 class utree { 335 public: 336 /////////////////////////////////////////////////////////////////////// 337 // The invalid type 338 struct invalid_type {}; 339 340 /////////////////////////////////////////////////////////////////////// 341 // The nil type 342 struct nil_type {}; 343 344 /////////////////////////////////////////////////////////////////////// 345 // The list type, this can be used to initialize an utree to hold an 346 // empty list 347 struct list_type; 348 349 //[utree_container_types 350 typedef utree value_type; 351 typedef utree& reference; 352 typedef utree const& const_reference; 353 typedef std::ptrdiff_t difference_type; 354 typedef std::size_t size_type; 355 356 typedef detail::list::node_iterator<utree> iterator; 357 typedef detail::list::node_iterator<utree const> const_iterator; 358 //] 359 360 typedef detail::list::node_iterator<boost::reference_wrapper<utree> > 361 ref_iterator; 362 363 typedef boost::iterator_range<iterator> range; 364 typedef boost::iterator_range<const_iterator> const_range; 365 366 // dtor 367 ~utree(); 368 369 //////////////////////////////////////////////////////////////////////// 370 //[utree_initialization 371 /*`A `utree` can be constructed or initialized from a wide range of 372 data types, allowing to create `utree` instances for every 373 possible node type (see the description of `utree_type::info` above). 374 For this reason it exposes a constructor and an assignment operator 375 for each of the allowed node types as shown below. All constructors 376 are non-explicit on purpose, allowing to use an utree instance as 377 the attribute to almost any Qi parser. 378 */ 379 // This constructs an `invalid_type` node. When used in places 380 // where a boost::optional is expected (i.e. as an attribute for the 381 // optional component), this represents the 'empty' state. 382 utree(invalid_type = invalid_type()); 383 384 // This initializes a `nil_type` node, which represents a valid, 385 // 'initialized empty' utree (different from invalid_type!). 386 utree(nil_type); 387 reference operator=(nil_type); 388 389 // This initializes a `boolean_type` node, which can hold 'true' or 390 // 'false' only. 391 explicit utree(bool); 392 reference operator=(bool); 393 394 // This initializes an `integer_type` node, which can hold arbitrary 395 // integers. For convenience these functions are overloaded for signed 396 // and unsigned integer types. 397 utree(unsigned int); 398 utree(int); 399 reference operator=(unsigned int); 400 reference operator=(int); 401 402 // This initializes a `double_type` node, which can hold arbitrary 403 // floating point (double) values. 404 utree(double); 405 reference operator=(double); 406 407 // This initializes a `string_type` node, which can hold a narrow 408 // character sequence (usually an UTF-8 string). 409 utree(char); 410 utree(char const*); 411 utree(char const*, std::size_t); 412 utree(std::string const&); 413 reference operator=(char); 414 reference operator=(char const*); 415 reference operator=(std::string const&); 416 417 // This constructs a `string_range_type` node, which does not copy the 418 // data but stores the iterator range to the character sequence the 419 // range has been initialized from. 420 utree(utf8_string_range_type const&, shallow_tag); 421 422 // This initializes a `reference_type` node, which holds a reference to 423 // another utree node. All operations on such a node are automatically 424 // forwarded to the referenced utree instance. 425 utree(boost::reference_wrapper<utree>); 426 reference operator=(boost::reference_wrapper<utree>); 427 428 // This initializes an `any_type` node, which can hold a pointer to an 429 // instance of any type together with the typeid of that type. When 430 // accessing that pointer the typeid will be checked, causing a 431 // std::bad_cast to be thrown if the typeids do not match. 432 utree(any_ptr const&); 433 reference operator=(any_ptr const&); 434 435 // This initializes a `range_type` node, which holds an utree list node 436 // the elements of which are copy constructed (assigned) from the 437 // elements referenced by the given range of iterators. 438 template <class Iterator> 439 utree(boost::iterator_range<Iterator>); 440 template <class Iterator> 441 reference operator=(boost::iterator_range<Iterator>); 442 443 // This initializes a `function_type` node from a polymorphic function 444 // object pointer (takes ownership) or reference. 445 utree(function_base const&); 446 reference operator=(function_base const&); 447 utree(function_base*); 448 reference operator=(function_base*); 449 450 // This initializes either a `string_type`, a `symbol_type`, or a 451 // `binary_type` node (depending on the template parameter `type_`), 452 // which will hold the corresponding narrow character sequence (usually 453 // an UTF-8 string). 454 template <class Base, utree_type::info type_> 455 utree(basic_string<Base, type_> const&); 456 template <class Base, utree_type::info type_> 457 reference operator=(basic_string<Base, type_> const&); 458 //] 459 460 // copy 461 utree(const_reference); 462 reference operator=(const_reference); 463 464 // range 465 utree(range, shallow_tag); 466 utree(const_range, shallow_tag); 467 468 // assign dispatch 469 template <class Iterator> 470 void assign(Iterator, Iterator); 471 472 //////////////////////////////////////////////////////////////////////// 473 474 //////////////////////////////////////////////////////////////////////// 475 // function object visitation interface 476 477 // single dispatch 478 template <class F> 479 typename boost::result_of<F(utree const&)>::type 480 static visit(utree const&, F); 481 482 template <class F> 483 typename boost::result_of<F(utree&)>::type 484 static visit(utree&, F); 485 486 // double dispatch 487 template <class F> 488 typename boost::result_of<F(utree const&, utree const&)>::type 489 static visit(utree const&, utree const&, F); 490 491 template <class F> 492 typename boost::result_of<F(utree&, utree const&)>::type 493 static visit(utree&, utree const&, F); 494 495 template <class F> 496 typename boost::result_of<F(utree const&, utree&)>::type 497 static visit(utree const&, utree&, F); 498 499 template <class F> 500 typename boost::result_of<F(utree&, utree&)>::type 501 static visit(utree&, utree&, F); 502 503 //////////////////////////////////////////////////////////////////////// 504 505 /////////////////////////////////////////////////////////////////////// 506 //[utree_container_functions 507 // STL Container interface 508 509 // insertion 510 template <class T> 511 void push_back(T const&); 512 template <class T> 513 void push_front(T const&); 514 template <class T> 515 iterator insert(iterator, T const&); 516 template <class T> 517 void insert(iterator, std::size_t, T const&); 518 template <class Iterator> 519 void insert(iterator, Iterator, Iterator); 520 521 // erasure 522 void pop_front(); 523 void pop_back(); 524 iterator erase(iterator); 525 iterator erase(iterator, iterator); 526 527 // front access 528 reference front(); 529 const_reference front() const; 530 iterator begin(); 531 const_iterator begin() const; 532 ref_iterator ref_begin(); 533 534 // back access 535 reference back(); 536 const_reference back() const; 537 iterator end(); 538 const_iterator end() const; 539 ref_iterator ref_end(); 540 //] 541 542 // This clears the utree instance and resets its type to `invalid_type` 543 void clear(); 544 545 void swap(utree&); 546 547 bool empty() const; 548 549 size_type size() const; 550 /*`[warning `size()` has O(n) complexity on `utree` ranges. On utree 551 lists, it has O(1) complexity.]`*/ 552 553 //////////////////////////////////////////////////////////////////////// 554 555 //[utree_variant_functions 556 // return the data type (`utree_type::info`) of the currently stored 557 // data item 558 utree_type::info which() const; 559 560 // access the currently stored data in a type safe manner, this will 561 // throw a `std::bad_cast()` if the currently stored data item is not 562 // default convertible to `T`. 563 template <class T> 564 T get() const; 565 //] 566 567 reference deref(); 568 const_reference deref() const; 569 570 short tag() const; 571 void tag(short); 572 573 utree eval(utree const&) const; 574 utree eval(utree&) const; 575 576 utree operator() (utree const&) const; 577 utree operator() (utree&) const; 578 //<- 579 protected: 580 void ensure_list_type(char const* failed_in = "ensure_list_type()"); 581 582 private: 583 typedef utree_type type; 584 585 template <class UTreeX, class UTreeY> 586 friend struct detail::visit_impl; 587 friend struct detail::index_impl; 588 589 type::info get_type() const; 590 void set_type(type::info); 591 void free(); 592 void copy(const_reference); 593 594 union { 595 detail::fast_string s; 596 detail::list l; 597 detail::range r; 598 detail::string_range sr; 599 detail::void_ptr v; 600 bool b; 601 int i; 602 double d; 603 utree* p; 604 function_base* pf; 605 }; 606 //-> 607 }; 608 //] 609 610 //[utree_tuple_interface 611 /*<-*/inline/*->*/ 612 utree::reference get(utree::reference, utree::size_type); 613 /*<-*/inline/*->*/ 614 utree::const_reference get(utree::const_reference, utree::size_type); 615 /*`[warning `get()` has O(n) complexity.]`*/ 616 //] 617 618 struct utree::list_type : utree 619 { 620 using utree::operator=; 621 list_typeboost::spirit::utree::list_type622 list_type() : utree() { ensure_list_type("list_type()"); } 623 624 template <typename T0> list_typeboost::spirit::utree::list_type625 list_type(T0 t0) : utree(t0) {} 626 627 template <typename T0, typename T1> list_typeboost::spirit::utree::list_type628 list_type(T0 t0, T1 t1) : utree(t0, t1) {} 629 }; 630 631 /////////////////////////////////////////////////////////////////////////// 632 // predefined instances for singular types 633 utree::invalid_type const invalid = {}; 634 utree::nil_type const nil = {}; 635 utree::list_type const empty_list = utree::list_type(); 636 }} 637 638 #if defined(BOOST_MSVC) 639 #pragma warning(pop) 640 #endif 641 642 #endif 643 644