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