1 /*============================================================================= 2 Copyright (c) 2001-2011 Joel de Guzman 3 Copyright (c) 2001-2011 Hartmut Kaiser 4 Copyright (c) 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_DETAIL2) 10 #define BOOST_SPIRIT_UTREE_DETAIL2 11 12 #if defined(BOOST_MSVC) 13 # pragma warning(push) 14 # pragma warning(disable: 4800) 15 #endif 16 17 #include <boost/type_traits/remove_pointer.hpp> 18 #include <boost/type_traits/is_pointer.hpp> 19 #include <boost/utility/enable_if.hpp> 20 #include <boost/throw_exception.hpp> 21 #include <boost/iterator/iterator_traits.hpp> 22 23 namespace boost { namespace spirit { namespace detail 24 { info()25 inline char& fast_string::info() 26 { 27 return buff[small_string_size]; 28 } 29 info() const30 inline char fast_string::info() const 31 { 32 return buff[small_string_size]; 33 } 34 get_type() const35 inline int fast_string::get_type() const 36 { 37 return info() >> 1; 38 } 39 set_type(int t)40 inline void fast_string::set_type(int t) 41 { 42 info() = (t << 1) | (info() & 1); 43 } 44 tag() const45 inline short fast_string::tag() const 46 { 47 return (int(buff[small_string_size-2]) << 8) + (unsigned char)buff[small_string_size-1]; 48 } 49 tag(short tag)50 inline void fast_string::tag(short tag) 51 { 52 buff[small_string_size-2] = tag >> 8; 53 buff[small_string_size-1] = tag & 0xff; 54 } 55 is_heap_allocated() const56 inline bool fast_string::is_heap_allocated() const 57 { 58 return info() & 1; 59 } 60 size() const61 inline std::size_t fast_string::size() const 62 { 63 if (is_heap_allocated()) 64 return heap.size; 65 else 66 return max_string_len - buff[max_string_len]; 67 } 68 str() const69 inline char const* fast_string::str() const 70 { 71 if (is_heap_allocated()) 72 return heap.str; 73 else 74 return buff; 75 } 76 77 template <typename Iterator> construct(Iterator f,Iterator l)78 inline void fast_string::construct(Iterator f, Iterator l) 79 { 80 unsigned const size = l-f; 81 char* str; 82 if (size < max_string_len) 83 { 84 // if it fits, store it in-situ; small_string_size minus the length 85 // of the string is placed in buff[small_string_size - 1] 86 str = buff; 87 buff[max_string_len] = static_cast<char>(max_string_len - size); 88 info() &= ~0x1; 89 } 90 else 91 { 92 // else, store it in the heap 93 str = new char[size + 1]; // add one for the null char 94 heap.str = str; 95 heap.size = size; 96 info() |= 0x1; 97 } 98 for (std::size_t i = 0; i != size; ++i) 99 { 100 *str++ = *f++; 101 } 102 *str = '\0'; // add the null char 103 } 104 swap(fast_string & other)105 inline void fast_string::swap(fast_string& other) 106 { 107 std::swap(*this, other); 108 } 109 free()110 inline void fast_string::free() 111 { 112 if (is_heap_allocated()) 113 { 114 delete [] heap.str; 115 } 116 } 117 copy(fast_string const & other)118 inline void fast_string::copy(fast_string const& other) 119 { 120 construct(other.str(), other.str() + other.size()); 121 } 122 initialize()123 inline void fast_string::initialize() 124 { 125 for (std::size_t i = 0; i != buff_size / (sizeof(long)/sizeof(char)); ++i) 126 lbuff[i] = 0; 127 } 128 129 struct list::node : boost::noncopyable 130 { 131 template <typename T> nodeboost::spirit::detail::list::node132 node(T const& val, node* next, node* prev) 133 : val(val), next(next), prev(prev) {} 134 unlinkboost::spirit::detail::list::node135 void unlink() 136 { 137 prev->next = next; 138 next->prev = prev; 139 } 140 141 utree val; 142 node* next; 143 node* prev; 144 }; 145 146 template <typename Value> 147 class list::node_iterator 148 : public boost::iterator_facade< 149 node_iterator<Value> 150 , Value 151 , boost::bidirectional_traversal_tag> 152 { 153 public: 154 node_iterator()155 node_iterator() 156 : node(0), prev(0) {} 157 node_iterator(list::node * node,list::node * prev)158 node_iterator(list::node* node, list::node* prev) 159 : node(node), prev(prev) {} 160 161 private: 162 163 friend class boost::iterator_core_access; 164 friend class boost::spirit::utree; 165 friend struct boost::spirit::detail::list; 166 increment()167 void increment() 168 { 169 if (node != 0) // not at end 170 { 171 prev = node; 172 node = node->next; 173 } 174 } 175 decrement()176 void decrement() 177 { 178 if (prev != 0) // not at begin 179 { 180 node = prev; 181 prev = prev->prev; 182 } 183 } 184 equal(node_iterator const & other) const185 bool equal(node_iterator const& other) const 186 { 187 return node == other.node; 188 } 189 dereference() const190 typename node_iterator::reference dereference() const 191 { 192 return node->val; 193 } 194 195 list::node* node; 196 list::node* prev; 197 }; 198 199 template <typename Value> 200 class list::node_iterator<boost::reference_wrapper<Value> > 201 : public boost::iterator_facade< 202 node_iterator<boost::reference_wrapper<Value> > 203 , boost::reference_wrapper<Value> 204 , boost::bidirectional_traversal_tag> 205 { 206 public: 207 node_iterator()208 node_iterator() 209 : node(0), prev(0), curr(nil_node) {} 210 node_iterator(list::node * node,list::node * prev)211 node_iterator(list::node* node, list::node* prev) 212 : node(node), prev(prev), curr(node ? node->val : nil_node) {} 213 214 private: 215 216 friend class boost::iterator_core_access; 217 friend class boost::spirit::utree; 218 friend struct boost::spirit::detail::list; 219 increment()220 void increment() 221 { 222 if (node != 0) // not at end 223 { 224 prev = node; 225 node = node->next; 226 curr = boost::ref(node ? node->val : nil_node); 227 } 228 } 229 decrement()230 void decrement() 231 { 232 if (prev != 0) // not at begin 233 { 234 node = prev; 235 prev = prev->prev; 236 curr = boost::ref(node ? node->val : nil_node); 237 } 238 } 239 equal(node_iterator const & other) const240 bool equal(node_iterator const& other) const 241 { 242 return node == other.node; 243 } 244 dereference() const245 typename node_iterator::reference dereference() const 246 { 247 return curr; 248 } 249 250 list::node* node; 251 list::node* prev; 252 253 static Value nil_node; 254 mutable boost::reference_wrapper<Value> curr; 255 }; 256 257 template <typename Value> 258 Value list::node_iterator<boost::reference_wrapper<Value> >::nil_node = Value(); 259 free()260 inline void list::free() 261 { 262 node* p = first; 263 while (p != 0) 264 { 265 node* next = p->next; 266 delete p; 267 p = next; 268 } 269 } 270 copy(list const & other)271 inline void list::copy(list const& other) 272 { 273 node* p = other.first; 274 while (p != 0) 275 { 276 push_back(p->val); 277 p = p->next; 278 } 279 } 280 default_construct()281 inline void list::default_construct() 282 { 283 first = last = 0; 284 size = 0; 285 } 286 287 template <typename T, typename Iterator> insert(T const & val,Iterator pos)288 inline void list::insert(T const& val, Iterator pos) 289 { 290 if (!pos.node) 291 { 292 push_back(val); 293 return; 294 } 295 296 detail::list::node* new_node = 297 new detail::list::node(val, pos.node, pos.node->prev); 298 299 if (pos.node->prev) 300 pos.node->prev->next = new_node; 301 else 302 first = new_node; 303 304 pos.node->prev = new_node; 305 ++size; 306 } 307 308 template <typename T> push_front(T const & val)309 inline void list::push_front(T const& val) 310 { 311 detail::list::node* new_node; 312 if (first == 0) 313 { 314 new_node = new detail::list::node(val, 0, 0); 315 first = last = new_node; 316 ++size; 317 } 318 else 319 { 320 new_node = new detail::list::node(val, first, first->prev); 321 first->prev = new_node; 322 first = new_node; 323 ++size; 324 } 325 } 326 327 template <typename T> push_back(T const & val)328 inline void list::push_back(T const& val) 329 { 330 if (last == 0) 331 push_front(val); 332 else { 333 detail::list::node* new_node = 334 new detail::list::node(val, last->next, last); 335 last->next = new_node; 336 last = new_node; 337 ++size; 338 } 339 } 340 pop_front()341 inline void list::pop_front() 342 { 343 BOOST_ASSERT(size != 0); 344 if (first == last) // there's only one item 345 { 346 delete first; 347 size = 0; 348 first = last = 0; 349 } 350 else 351 { 352 node* np = first; 353 first = first->next; 354 first->prev = 0; 355 delete np; 356 --size; 357 } 358 } 359 pop_back()360 inline void list::pop_back() 361 { 362 BOOST_ASSERT(size != 0); 363 if (first == last) // there's only one item 364 { 365 delete first; 366 size = 0; 367 first = last = 0; 368 } 369 else 370 { 371 node* np = last; 372 last = last->prev; 373 last->next = 0; 374 delete np; 375 --size; 376 } 377 } 378 erase(node * pos)379 inline list::node* list::erase(node* pos) 380 { 381 BOOST_ASSERT(pos != 0); 382 if (pos == first) 383 { 384 pop_front(); 385 return first; 386 } 387 else if (pos == last) 388 { 389 pop_back(); 390 return 0; 391 } 392 else 393 { 394 node* next(pos->next); 395 pos->unlink(); 396 delete pos; 397 --size; 398 return next; 399 } 400 } 401 402 /////////////////////////////////////////////////////////////////////////// 403 // simple binder for binary visitation (we don't want to bring in the big guns) 404 template <typename F, typename X> 405 struct bind_impl 406 { 407 typedef typename F::result_type result_type; 408 X& x; // always by reference 409 F f; bind_implboost::spirit::detail::bind_impl410 bind_impl(F f, X& x) : x(x), f(f) {} 411 412 template <typename Y> operator ()boost::spirit::detail::bind_impl413 typename F::result_type operator()(Y& y) const 414 { 415 return f(x, y); 416 } 417 418 template <typename Y> operator ()boost::spirit::detail::bind_impl419 typename F::result_type operator()(Y const& y) const 420 { 421 return f(x, y); 422 } 423 }; 424 425 template <typename F, typename X> bind(F f,X const & x)426 bind_impl<F, X const> bind(F f, X const& x) 427 { 428 return bind_impl<F, X const>(f, x); 429 } 430 431 template <typename F, typename X> bind(F f,X & x)432 bind_impl<F, X> bind(F f, X& x) 433 { 434 return bind_impl<F, X>(f, x); 435 } 436 437 template <typename UTreeX, typename UTreeY = UTreeX> 438 struct visit_impl 439 { 440 template <typename F> 441 typename F::result_type applyboost::spirit::detail::visit_impl442 static apply(UTreeX& x, F f) // single dispatch 443 { 444 typedef typename 445 boost::mpl::if_<boost::is_const<UTreeX>, 446 typename UTreeX::const_iterator, 447 typename UTreeX::iterator>::type 448 iterator; 449 450 typedef boost::iterator_range<iterator> list_range; 451 typedef utree_type type; 452 453 switch (x.get_type()) 454 { 455 default: 456 BOOST_THROW_EXCEPTION( 457 bad_type_exception("corrupt utree type", x.get_type())); 458 break; 459 460 case type::invalid_type: 461 return f(invalid); 462 463 case type::nil_type: 464 return f(nil); 465 466 case type::bool_type: 467 return f(x.b); 468 469 case type::int_type: 470 return f(x.i); 471 472 case type::double_type: 473 return f(x.d); 474 475 case type::list_type: 476 return f(list_range(iterator(x.l.first, 0), iterator(0, x.l.last))); 477 478 case type::range_type: 479 return f(list_range(iterator(x.r.first, 0), iterator(0, x.r.last))); 480 481 case type::string_type: 482 return f(utf8_string_range_type(x.s.str(), x.s.size())); 483 484 case type::string_range_type: 485 return f(utf8_string_range_type(x.sr.first, x.sr.last)); 486 487 case type::symbol_type: 488 return f(utf8_symbol_range_type(x.s.str(), x.s.size())); 489 490 case type::binary_type: 491 return f(binary_range_type(x.s.str(), x.s.size())); 492 493 case type::reference_type: 494 return apply(*x.p, f); 495 496 case type::any_type: 497 return f(any_ptr(x.v.p, x.v.i)); 498 499 case type::function_type: 500 return f(*x.pf); 501 } 502 } 503 504 template <typename F> 505 typename F::result_type applyboost::spirit::detail::visit_impl506 static apply(UTreeX& x, UTreeY& y, F f) // double dispatch 507 { 508 typedef typename 509 boost::mpl::if_<boost::is_const<UTreeX>, 510 typename UTreeX::const_iterator, 511 typename UTreeX::iterator>::type 512 iterator; 513 514 typedef boost::iterator_range<iterator> list_range; 515 typedef utree_type type; 516 517 switch (x.get_type()) 518 { 519 default: 520 BOOST_THROW_EXCEPTION( 521 bad_type_exception("corrupt utree type", x.get_type())); 522 break; 523 524 case type::invalid_type: 525 return visit_impl::apply(y, detail::bind(f, invalid)); 526 527 case type::nil_type: 528 return visit_impl::apply(y, detail::bind(f, nil)); 529 530 case type::bool_type: 531 return visit_impl::apply(y, detail::bind(f, x.b)); 532 533 case type::int_type: 534 return visit_impl::apply(y, detail::bind(f, x.i)); 535 536 case type::double_type: 537 return visit_impl::apply(y, detail::bind(f, x.d)); 538 539 case type::list_type: 540 return visit_impl::apply( 541 y, detail::bind<F, list_range>(f, 542 list_range(iterator(x.l.first, 0), iterator(0, x.l.last)))); 543 544 case type::range_type: 545 return visit_impl::apply( 546 y, detail::bind<F, list_range>(f, 547 list_range(iterator(x.r.first, 0), iterator(0, x.r.last)))); 548 549 case type::string_type: 550 return visit_impl::apply(y, detail::bind( 551 f, utf8_string_range_type(x.s.str(), x.s.size()))); 552 553 case type::string_range_type: 554 return visit_impl::apply(y, detail::bind( 555 f, utf8_string_range_type(x.sr.first, x.sr.last))); 556 557 case type::symbol_type: 558 return visit_impl::apply(y, detail::bind( 559 f, utf8_symbol_range_type(x.s.str(), x.s.size()))); 560 561 case type::binary_type: 562 return visit_impl::apply(y, detail::bind( 563 f, binary_range_type(x.s.str(), x.s.size()))); 564 565 case type::reference_type: 566 return apply(*x.p, y, f); 567 568 case type::any_type: 569 return visit_impl::apply( 570 y, detail::bind(f, any_ptr(x.v.p, x.v.i))); 571 572 case type::function_type: 573 return visit_impl::apply(y, detail::bind(f, *x.pf)); 574 } 575 } 576 }; 577 578 struct index_impl 579 { applyboost::spirit::detail::index_impl580 static utree& apply(utree& ut, std::size_t i) 581 { 582 switch (ut.get_type()) 583 { 584 case utree_type::reference_type: 585 return apply(ut.deref(), i); 586 case utree_type::range_type: 587 return apply(ut.r.first, i); 588 case utree_type::list_type: 589 return apply(ut.l.first, i); 590 default: 591 BOOST_THROW_EXCEPTION( 592 bad_type_exception 593 ("index operation performed on non-list utree type", 594 ut.get_type())); 595 } 596 } 597 applyboost::spirit::detail::index_impl598 static utree const& apply(utree const& ut, std::size_t i) 599 { 600 switch (ut.get_type()) 601 { 602 case utree_type::reference_type: 603 return apply(ut.deref(), i); 604 case utree_type::range_type: 605 return apply(ut.r.first, i); 606 case utree_type::list_type: 607 return apply(ut.l.first, i); 608 default: 609 BOOST_THROW_EXCEPTION( 610 bad_type_exception 611 ("index operation performed on non-list utree type", 612 ut.get_type())); 613 } 614 } 615 applyboost::spirit::detail::index_impl616 static utree& apply(list::node* node, std::size_t i) 617 { 618 for (; i > 0; --i) 619 node = node->next; 620 return node->val; 621 } 622 applyboost::spirit::detail::index_impl623 static utree const& apply(list::node const* node, std::size_t i) 624 { 625 for (; i > 0; --i) 626 node = node->next; 627 return node->val; 628 } 629 }; 630 }}} 631 632 namespace boost { namespace spirit 633 { 634 template <typename F> stored_function(F f)635 stored_function<F>::stored_function(F f) 636 : f(f) 637 { 638 } 639 640 template <typename F> ~stored_function()641 stored_function<F>::~stored_function() 642 { 643 } 644 645 template <typename F> operator ()(utree const & env) const646 utree stored_function<F>::operator()(utree const& env) const 647 { 648 return f(env); 649 } 650 651 template <typename F> operator ()(utree & env) const652 utree stored_function<F>::operator()(utree& env) const 653 { 654 return f(env); 655 } 656 657 template <typename F> 658 function_base* clone() const659 stored_function<F>::clone() const 660 { 661 return new stored_function<F>(f); 662 } 663 664 template <typename F> referenced_function(F & f)665 referenced_function<F>::referenced_function(F& f) 666 : f(f) 667 { 668 } 669 670 template <typename F> ~referenced_function()671 referenced_function<F>::~referenced_function() 672 { 673 } 674 675 template <typename F> operator ()(utree const & env) const676 utree referenced_function<F>::operator()(utree const& env) const 677 { 678 return f(env); 679 } 680 681 template <typename F> operator ()(utree & env) const682 utree referenced_function<F>::operator()(utree& env) const 683 { 684 return f(env); 685 } 686 687 template <typename F> 688 function_base* clone() const689 referenced_function<F>::clone() const 690 { 691 return new referenced_function<F>(f); 692 } 693 utree(utree::invalid_type)694 inline utree::utree(utree::invalid_type) 695 { 696 s.initialize(); 697 set_type(type::invalid_type); 698 } 699 utree(utree::nil_type)700 inline utree::utree(utree::nil_type) 701 { 702 s.initialize(); 703 set_type(type::nil_type); 704 } 705 utree(bool b_)706 inline utree::utree(bool b_) 707 { 708 s.initialize(); 709 b = b_; 710 set_type(type::bool_type); 711 } 712 utree(char c)713 inline utree::utree(char c) 714 { 715 s.initialize(); 716 // char constructs a single element string 717 s.construct(&c, &c+1); 718 set_type(type::string_type); 719 } 720 utree(unsigned int i_)721 inline utree::utree(unsigned int i_) 722 { 723 s.initialize(); 724 i = i_; 725 set_type(type::int_type); 726 } 727 utree(int i_)728 inline utree::utree(int i_) 729 { 730 s.initialize(); 731 i = i_; 732 set_type(type::int_type); 733 } 734 utree(double d_)735 inline utree::utree(double d_) 736 { 737 s.initialize(); 738 d = d_; 739 set_type(type::double_type); 740 } 741 utree(char const * str)742 inline utree::utree(char const* str) 743 { 744 s.initialize(); 745 s.construct(str, str + strlen(str)); 746 set_type(type::string_type); 747 } 748 utree(char const * str,std::size_t len)749 inline utree::utree(char const* str, std::size_t len) 750 { 751 s.initialize(); 752 s.construct(str, str + len); 753 set_type(type::string_type); 754 } 755 utree(std::string const & str)756 inline utree::utree(std::string const& str) 757 { 758 s.initialize(); 759 s.construct(str.begin(), str.end()); 760 set_type(type::string_type); 761 } 762 763 template <typename Base, utree_type::info type_> utree(basic_string<Base,type_> const & bin)764 inline utree::utree(basic_string<Base, type_> const& bin) 765 { 766 s.initialize(); 767 s.construct(bin.begin(), bin.end()); 768 set_type(type_); 769 } 770 utree(boost::reference_wrapper<utree> ref)771 inline utree::utree(boost::reference_wrapper<utree> ref) 772 { 773 s.initialize(); 774 p = ref.get_pointer(); 775 set_type(type::reference_type); 776 } 777 utree(any_ptr const & p)778 inline utree::utree(any_ptr const& p) 779 { 780 s.initialize(); 781 v.p = p.p; 782 v.i = p.i; 783 set_type(type::any_type); 784 } 785 utree(function_base const & pf_)786 inline utree::utree(function_base const& pf_) 787 { 788 s.initialize(); 789 pf = pf_.clone(); 790 set_type(type::function_type); 791 } 792 utree(function_base * pf_)793 inline utree::utree(function_base* pf_) 794 { 795 s.initialize(); 796 pf = pf_; 797 set_type(type::function_type); 798 } 799 800 template <typename Iter> utree(boost::iterator_range<Iter> r)801 inline utree::utree(boost::iterator_range<Iter> r) 802 { 803 s.initialize(); 804 805 assign(r.begin(), r.end()); 806 } 807 utree(range r,shallow_tag)808 inline utree::utree(range r, shallow_tag) 809 { 810 s.initialize(); 811 this->r.first = r.begin().node; 812 this->r.last = r.end().prev; 813 set_type(type::range_type); 814 } 815 utree(const_range r,shallow_tag)816 inline utree::utree(const_range r, shallow_tag) 817 { 818 s.initialize(); 819 this->r.first = r.begin().node; 820 this->r.last = r.end().prev; 821 set_type(type::range_type); 822 } 823 utree(utf8_string_range_type const & str,shallow_tag)824 inline utree::utree(utf8_string_range_type const& str, shallow_tag) 825 { 826 s.initialize(); 827 this->sr.first = str.begin(); 828 this->sr.last = str.end(); 829 set_type(type::string_range_type); 830 } 831 utree(utree const & other)832 inline utree::utree(utree const& other) 833 { 834 s.initialize(); 835 copy(other); 836 } 837 ~utree()838 inline utree::~utree() 839 { 840 free(); 841 } 842 operator =(utree const & other)843 inline utree& utree::operator=(utree const& other) 844 { 845 if (this != &other) 846 { 847 free(); 848 copy(other); 849 } 850 return *this; 851 } 852 operator =(nil_type)853 inline utree& utree::operator=(nil_type) 854 { 855 free(); 856 set_type(type::nil_type); 857 return *this; 858 } 859 operator =(bool b_)860 inline utree& utree::operator=(bool b_) 861 { 862 free(); 863 b = b_; 864 set_type(type::bool_type); 865 return *this; 866 } 867 operator =(char c)868 inline utree& utree::operator=(char c) 869 { 870 // char constructs a single element string 871 free(); 872 s.construct(&c, &c+1); 873 set_type(type::string_type); 874 return *this; 875 } 876 operator =(unsigned int i_)877 inline utree& utree::operator=(unsigned int i_) 878 { 879 free(); 880 i = i_; 881 set_type(type::int_type); 882 return *this; 883 } 884 operator =(int i_)885 inline utree& utree::operator=(int i_) 886 { 887 free(); 888 i = i_; 889 set_type(type::int_type); 890 return *this; 891 } 892 operator =(double d_)893 inline utree& utree::operator=(double d_) 894 { 895 free(); 896 d = d_; 897 set_type(type::double_type); 898 return *this; 899 } 900 operator =(char const * s_)901 inline utree& utree::operator=(char const* s_) 902 { 903 free(); 904 s.construct(s_, s_ + strlen(s_)); 905 set_type(type::string_type); 906 return *this; 907 } 908 operator =(std::string const & s_)909 inline utree& utree::operator=(std::string const& s_) 910 { 911 free(); 912 s.construct(s_.begin(), s_.end()); 913 set_type(type::string_type); 914 return *this; 915 } 916 917 template <typename Base, utree_type::info type_> operator =(basic_string<Base,type_> const & bin)918 inline utree& utree::operator=(basic_string<Base, type_> const& bin) 919 { 920 free(); 921 s.construct(bin.begin(), bin.end()); 922 set_type(type_); 923 return *this; 924 } 925 operator =(boost::reference_wrapper<utree> ref)926 inline utree& utree::operator=(boost::reference_wrapper<utree> ref) 927 { 928 free(); 929 p = ref.get_pointer(); 930 set_type(type::reference_type); 931 return *this; 932 } 933 operator =(any_ptr const & p)934 inline utree& utree::operator=(any_ptr const& p) 935 { 936 free(); 937 v.p = p.p; 938 v.i = p.i; 939 set_type(type::any_type); 940 return *this; 941 } 942 operator =(function_base const & pf_)943 inline utree& utree::operator=(function_base const& pf_) 944 { 945 free(); 946 pf = pf_.clone(); 947 set_type(type::function_type); 948 return *this; 949 } 950 operator =(function_base * pf_)951 inline utree& utree::operator=(function_base* pf_) 952 { 953 free(); 954 pf = pf_; 955 set_type(type::function_type); 956 return *this; 957 } 958 959 template <typename Iter> operator =(boost::iterator_range<Iter> r)960 inline utree& utree::operator=(boost::iterator_range<Iter> r) 961 { 962 free(); 963 assign(r.begin(), r.end()); 964 return *this; 965 } 966 967 template <typename F> 968 typename boost::result_of<F(utree const&)>::type visit(utree const & x,F f)969 inline utree::visit(utree const& x, F f) 970 { 971 return detail::visit_impl<utree const>::apply(x, f); 972 } 973 974 template <typename F> 975 typename boost::result_of<F(utree&)>::type visit(utree & x,F f)976 inline utree::visit(utree& x, F f) 977 { 978 return detail::visit_impl<utree>::apply(x, f); 979 } 980 981 template <typename F> 982 typename boost::result_of<F(utree const&, utree const&)>::type visit(utree const & x,utree const & y,F f)983 inline utree::visit(utree const& x, utree const& y, F f) 984 { 985 return detail::visit_impl<utree const, utree const>::apply(x, y, f); 986 } 987 988 template <typename F> 989 typename boost::result_of<F(utree const&, utree&)>::type visit(utree const & x,utree & y,F f)990 inline utree::visit(utree const& x, utree& y, F f) 991 { 992 return detail::visit_impl<utree const, utree>::apply(x, y, f); 993 } 994 995 template <typename F> 996 typename boost::result_of<F(utree&, utree const&)>::type visit(utree & x,utree const & y,F f)997 inline utree::visit(utree& x, utree const& y, F f) 998 { 999 return detail::visit_impl<utree, utree const>::apply(x, y, f); 1000 } 1001 1002 template <typename F> 1003 typename boost::result_of<F(utree&, utree&)>::type visit(utree & x,utree & y,F f)1004 inline utree::visit(utree& x, utree& y, F f) 1005 { 1006 return detail::visit_impl<utree, utree>::apply(x, y, f); 1007 } 1008 get(utree::reference ut,utree::size_type i)1009 inline utree::reference get(utree::reference ut, utree::size_type i) 1010 { return detail::index_impl::apply(ut, i); } 1011 1012 inline utree::const_reference get(utree::const_reference ut,utree::size_type i)1013 get(utree::const_reference ut, utree::size_type i) 1014 { return detail::index_impl::apply(ut, i); } 1015 1016 template <typename T> push_front(T const & val)1017 inline void utree::push_front(T const& val) 1018 { 1019 if (get_type() == type::reference_type) 1020 return p->push_front(val); 1021 1022 ensure_list_type("push_front()"); 1023 l.push_front(val); 1024 } 1025 1026 template <typename T> push_back(T const & val)1027 inline void utree::push_back(T const& val) 1028 { 1029 if (get_type() == type::reference_type) 1030 return p->push_back(val); 1031 1032 ensure_list_type("push_back()"); 1033 l.push_back(val); 1034 } 1035 1036 template <typename T> insert(iterator pos,T const & val)1037 inline utree::iterator utree::insert(iterator pos, T const& val) 1038 { 1039 if (get_type() == type::reference_type) 1040 return p->insert(pos, val); 1041 1042 ensure_list_type("insert()"); 1043 if (!pos.node) 1044 { 1045 l.push_back(val); 1046 return utree::iterator(l.last, l.last->prev); 1047 } 1048 l.insert(val, pos); 1049 return utree::iterator(pos.node->prev, pos.node->prev->prev); 1050 } 1051 1052 template <typename T> insert(iterator pos,std::size_t n,T const & val)1053 inline void utree::insert(iterator pos, std::size_t n, T const& val) 1054 { 1055 if (get_type() == type::reference_type) 1056 return p->insert(pos, n, val); 1057 1058 ensure_list_type("insert()"); 1059 for (std::size_t i = 0; i != n; ++i) 1060 insert(pos, val); 1061 } 1062 1063 template <typename Iterator> insert(iterator pos,Iterator first,Iterator last)1064 inline void utree::insert(iterator pos, Iterator first, Iterator last) 1065 { 1066 if (get_type() == type::reference_type) 1067 return p->insert(pos, first, last); 1068 1069 ensure_list_type("insert()"); 1070 while (first != last) 1071 insert(pos, *first++); 1072 } 1073 1074 template <typename Iterator> assign(Iterator first,Iterator last)1075 inline void utree::assign(Iterator first, Iterator last) 1076 { 1077 if (get_type() == type::reference_type) 1078 return p->assign(first, last); 1079 1080 clear(); 1081 set_type(type::list_type); 1082 1083 while (first != last) 1084 { 1085 push_back(*first); 1086 ++first; 1087 } 1088 } 1089 clear()1090 inline void utree::clear() 1091 { 1092 if (get_type() == type::reference_type) 1093 return p->clear(); 1094 1095 // clear will always make this an invalid type 1096 free(); 1097 set_type(type::invalid_type); 1098 } 1099 pop_front()1100 inline void utree::pop_front() 1101 { 1102 if (get_type() == type::reference_type) 1103 return p->pop_front(); 1104 if (get_type() != type::list_type) 1105 BOOST_THROW_EXCEPTION( 1106 bad_type_exception 1107 ("pop_front() called on non-list utree type", 1108 get_type())); 1109 1110 l.pop_front(); 1111 } 1112 pop_back()1113 inline void utree::pop_back() 1114 { 1115 if (get_type() == type::reference_type) 1116 return p->pop_back(); 1117 if (get_type() != type::list_type) 1118 BOOST_THROW_EXCEPTION( 1119 bad_type_exception 1120 ("pop_back() called on non-list utree type", 1121 get_type())); 1122 1123 l.pop_back(); 1124 } 1125 erase(iterator pos)1126 inline utree::iterator utree::erase(iterator pos) 1127 { 1128 if (get_type() == type::reference_type) 1129 return p->erase(pos); 1130 if (get_type() != type::list_type) 1131 BOOST_THROW_EXCEPTION( 1132 bad_type_exception 1133 ("erase() called on non-list utree type", 1134 get_type())); 1135 1136 detail::list::node* np = l.erase(pos.node); 1137 return iterator(np, np?np->prev:l.last); 1138 } 1139 erase(iterator first,iterator last)1140 inline utree::iterator utree::erase(iterator first, iterator last) 1141 { 1142 if (get_type() == type::reference_type) 1143 return p->erase(first, last); 1144 1145 if (get_type() != type::list_type) 1146 BOOST_THROW_EXCEPTION( 1147 bad_type_exception 1148 ("erase() called on non-list utree type", 1149 get_type())); 1150 while (first != last) 1151 erase(first++); 1152 return last; 1153 } 1154 begin()1155 inline utree::iterator utree::begin() 1156 { 1157 if (get_type() == type::reference_type) 1158 return p->begin(); 1159 else if (get_type() == type::range_type) 1160 return iterator(r.first, 0); 1161 1162 // otherwise... 1163 ensure_list_type("begin()"); 1164 return iterator(l.first, 0); 1165 } 1166 end()1167 inline utree::iterator utree::end() 1168 { 1169 if (get_type() == type::reference_type) 1170 return p->end(); 1171 else if (get_type() == type::range_type) 1172 return iterator(0, r.first); 1173 1174 // otherwise... 1175 ensure_list_type("end()"); 1176 return iterator(0, l.last); 1177 } 1178 ref_begin()1179 inline utree::ref_iterator utree::ref_begin() 1180 { 1181 if (get_type() == type::reference_type) 1182 return p->ref_begin(); 1183 else if (get_type() == type::range_type) 1184 return ref_iterator(r.first, 0); 1185 1186 // otherwise... 1187 ensure_list_type("ref_begin()"); 1188 return ref_iterator(l.first, 0); 1189 } 1190 ref_end()1191 inline utree::ref_iterator utree::ref_end() 1192 { 1193 if (get_type() == type::reference_type) 1194 return p->ref_end(); 1195 else if (get_type() == type::range_type) 1196 return ref_iterator(0, r.first); 1197 1198 // otherwise... 1199 ensure_list_type("ref_end()"); 1200 return ref_iterator(0, l.last); 1201 } 1202 begin() const1203 inline utree::const_iterator utree::begin() const 1204 { 1205 if (get_type() == type::reference_type) 1206 return ((utree const*)p)->begin(); 1207 if (get_type() == type::range_type) 1208 return const_iterator(r.first, 0); 1209 1210 // otherwise... 1211 if (get_type() != type::list_type) 1212 BOOST_THROW_EXCEPTION( 1213 bad_type_exception 1214 ("begin() called on non-list utree type", 1215 get_type())); 1216 1217 return const_iterator(l.first, 0); 1218 } 1219 end() const1220 inline utree::const_iterator utree::end() const 1221 { 1222 if (get_type() == type::reference_type) 1223 return ((utree const*)p)->end(); 1224 if (get_type() == type::range_type) 1225 return const_iterator(0, r.first); 1226 1227 // otherwise... 1228 if (get_type() != type::list_type) 1229 BOOST_THROW_EXCEPTION( 1230 bad_type_exception 1231 ("end() called on non-list utree type", 1232 get_type())); 1233 1234 return const_iterator(0, l.last); 1235 } 1236 empty() const1237 inline bool utree::empty() const 1238 { 1239 type::info t = get_type(); 1240 if (t == type::reference_type) 1241 return ((utree const*)p)->empty(); 1242 1243 if (t == type::range_type) 1244 return r.first == 0; 1245 if (t == type::list_type) 1246 return l.size == 0; 1247 1248 return t == type::nil_type || t == type::invalid_type; 1249 } 1250 size() const1251 inline std::size_t utree::size() const 1252 { 1253 type::info t = get_type(); 1254 if (t == type::reference_type) 1255 return ((utree const*)p)->size(); 1256 1257 if (t == type::range_type) 1258 { 1259 // FIXME: O(n), and we have the room to store the size of a range 1260 // in the union if we compute it when assigned/constructed. 1261 std::size_t size = 0; 1262 detail::list::node* n = r.first; 1263 while (n) 1264 { 1265 n = n->next; 1266 ++size; 1267 } 1268 return size; 1269 } 1270 if (t == type::list_type) 1271 return l.size; 1272 1273 if (t == type::string_type) 1274 return s.size(); 1275 1276 if (t == type::symbol_type) 1277 return s.size(); 1278 1279 if (t == type::binary_type) 1280 return s.size(); 1281 1282 if (t == type::string_range_type) 1283 return sr.last - sr.first; 1284 1285 if (t != type::nil_type) 1286 BOOST_THROW_EXCEPTION( 1287 bad_type_exception 1288 ("size() called on non-list and non-string utree type", 1289 get_type())); 1290 1291 return 0; 1292 } 1293 which() const1294 inline utree_type::info utree::which() const 1295 { 1296 return get_type(); 1297 } 1298 front()1299 inline utree& utree::front() 1300 { 1301 if (get_type() == type::reference_type) 1302 return p->front(); 1303 if (get_type() == type::range_type) 1304 { 1305 if (!r.first) 1306 BOOST_THROW_EXCEPTION( 1307 empty_exception("front() called on empty utree range")); 1308 return r.first->val; 1309 } 1310 1311 // otherwise... 1312 if (get_type() != type::list_type) 1313 BOOST_THROW_EXCEPTION( 1314 bad_type_exception 1315 ("front() called on non-list utree type", get_type())); 1316 else if (!l.first) 1317 BOOST_THROW_EXCEPTION( 1318 empty_exception("front() called on empty utree list")); 1319 1320 return l.first->val; 1321 } 1322 back()1323 inline utree& utree::back() 1324 { 1325 if (get_type() == type::reference_type) 1326 return p->back(); 1327 if (get_type() == type::range_type) 1328 { 1329 if (!r.last) 1330 BOOST_THROW_EXCEPTION( 1331 empty_exception("back() called on empty utree range")); 1332 return r.last->val; 1333 } 1334 1335 // otherwise... 1336 if (get_type() != type::list_type) 1337 BOOST_THROW_EXCEPTION( 1338 bad_type_exception 1339 ("back() called on non-list utree type", get_type())); 1340 else if (!l.last) 1341 BOOST_THROW_EXCEPTION( 1342 empty_exception("back() called on empty utree list")); 1343 1344 return l.last->val; 1345 } 1346 front() const1347 inline utree const& utree::front() const 1348 { 1349 if (get_type() == type::reference_type) 1350 return ((utree const*)p)->front(); 1351 if (get_type() == type::range_type) 1352 { 1353 if (!r.first) 1354 BOOST_THROW_EXCEPTION( 1355 empty_exception("front() called on empty utree range")); 1356 return r.first->val; 1357 } 1358 1359 // otherwise... 1360 if (get_type() != type::list_type) 1361 BOOST_THROW_EXCEPTION( 1362 bad_type_exception 1363 ("front() called on non-list utree type", get_type())); 1364 else if (!l.first) 1365 BOOST_THROW_EXCEPTION( 1366 empty_exception("front() called on empty utree list")); 1367 1368 return l.first->val; 1369 } 1370 back() const1371 inline utree const& utree::back() const 1372 { 1373 if (get_type() == type::reference_type) 1374 return ((utree const*)p)->back(); 1375 if (get_type() == type::range_type) 1376 { 1377 if (!r.last) 1378 BOOST_THROW_EXCEPTION( 1379 empty_exception("back() called on empty utree range")); 1380 return r.last->val; 1381 } 1382 1383 // otherwise... 1384 if (get_type() != type::list_type) 1385 BOOST_THROW_EXCEPTION( 1386 bad_type_exception 1387 ("back() called on non-list utree type", get_type())); 1388 else if (!l.last) 1389 BOOST_THROW_EXCEPTION( 1390 empty_exception("back() called on empty utree list")); 1391 1392 return l.last->val; 1393 } 1394 swap(utree & other)1395 inline void utree::swap(utree& other) 1396 { 1397 s.swap(other.s); 1398 } 1399 get_type() const1400 inline utree::type::info utree::get_type() const 1401 { 1402 // the fast string holds the type info 1403 return static_cast<utree::type::info>(s.get_type()); 1404 } 1405 set_type(type::info t)1406 inline void utree::set_type(type::info t) 1407 { 1408 // the fast string holds the type info 1409 s.set_type(t); 1410 } 1411 ensure_list_type(char const * failed_in)1412 inline void utree::ensure_list_type(char const* failed_in) 1413 { 1414 type::info t = get_type(); 1415 if (t == type::invalid_type) 1416 { 1417 set_type(type::list_type); 1418 l.default_construct(); 1419 } 1420 else if (get_type() != type::list_type) 1421 { 1422 std::string msg = failed_in; 1423 msg += "called on non-list and non-invalid utree type"; 1424 BOOST_THROW_EXCEPTION(bad_type_exception(msg.c_str(), get_type())); 1425 } 1426 } 1427 free()1428 inline void utree::free() 1429 { 1430 switch (get_type()) 1431 { 1432 case type::binary_type: 1433 case type::symbol_type: 1434 case type::string_type: 1435 s.free(); 1436 break; 1437 case type::list_type: 1438 l.free(); 1439 break; 1440 case type::function_type: 1441 delete pf; 1442 break; 1443 default: 1444 break; 1445 }; 1446 s.initialize(); 1447 } 1448 copy(utree const & other)1449 inline void utree::copy(utree const& other) 1450 { 1451 set_type(other.get_type()); 1452 switch (other.get_type()) 1453 { 1454 default: 1455 BOOST_THROW_EXCEPTION( 1456 bad_type_exception("corrupt utree type", other.get_type())); 1457 break; 1458 case type::invalid_type: 1459 case type::nil_type: 1460 s.tag(other.s.tag()); 1461 break; 1462 case type::bool_type: 1463 b = other.b; 1464 s.tag(other.s.tag()); 1465 break; 1466 case type::int_type: 1467 i = other.i; 1468 s.tag(other.s.tag()); 1469 break; 1470 case type::double_type: 1471 d = other.d; 1472 s.tag(other.s.tag()); 1473 break; 1474 case type::reference_type: 1475 p = other.p; 1476 s.tag(other.s.tag()); 1477 break; 1478 case type::any_type: 1479 v = other.v; 1480 s.tag(other.s.tag()); 1481 break; 1482 case type::range_type: 1483 r = other.r; 1484 s.tag(other.s.tag()); 1485 break; 1486 case type::string_range_type: 1487 sr = other.sr; 1488 s.tag(other.s.tag()); 1489 break; 1490 case type::function_type: 1491 pf = other.pf->clone(); 1492 s.tag(other.s.tag()); 1493 break; 1494 case type::string_type: 1495 case type::symbol_type: 1496 case type::binary_type: 1497 s.copy(other.s); 1498 s.tag(other.s.tag()); 1499 break; 1500 case type::list_type: 1501 l.copy(other.l); 1502 s.tag(other.s.tag()); 1503 break; 1504 } 1505 } 1506 1507 template <typename T> 1508 struct is_iterator_range 1509 : boost::mpl::false_ 1510 {}; 1511 1512 template <typename Iterator> 1513 struct is_iterator_range<boost::iterator_range<Iterator> > 1514 : boost::mpl::true_ 1515 {}; 1516 1517 template <typename To> 1518 struct utree_cast 1519 { 1520 typedef To result_type; 1521 1522 template <typename From> dispatchboost::spirit::utree_cast1523 To dispatch(From const& val, boost::mpl::true_) const 1524 { 1525 return To(val); // From is convertible to To 1526 } 1527 1528 template <typename From> dispatchboost::spirit::utree_cast1529 To dispatch(From const&, boost::mpl::false_) const 1530 { 1531 // From is NOT convertible to To !!! 1532 throw std::bad_cast(); 1533 return To(); 1534 } 1535 1536 template <typename From> operator ()boost::spirit::utree_cast1537 To operator()(From const& val) const 1538 { 1539 // boost::iterator_range has a templated constructor, accepting 1540 // any argument and hence any type is 'convertible' to it. 1541 typedef typename boost::mpl::eval_if< 1542 is_iterator_range<To> 1543 , boost::is_same<From, To>, boost::is_convertible<From, To> 1544 >::type is_convertible; 1545 return dispatch(val, is_convertible()); 1546 } 1547 }; 1548 1549 template <typename T> 1550 struct utree_cast<T*> 1551 { 1552 typedef T* result_type; 1553 1554 template <typename From> operator ()boost::spirit::utree_cast1555 T* operator()(From const&) const 1556 { 1557 // From is NOT convertible to T !!! 1558 throw std::bad_cast(); 1559 return 0; 1560 } 1561 operator ()boost::spirit::utree_cast1562 T* operator()(any_ptr const& p) const 1563 { 1564 return p.get<T*>(); 1565 } 1566 }; 1567 1568 template <typename T> get() const1569 inline T utree::get() const 1570 { 1571 return utree::visit(*this, utree_cast<T>()); 1572 } 1573 deref()1574 inline utree& utree::deref() 1575 { 1576 return (get_type() == type::reference_type) ? *p : *this; 1577 } 1578 deref() const1579 inline utree const& utree::deref() const 1580 { 1581 return (get_type() == type::reference_type) ? *p : *this; 1582 } 1583 tag() const1584 inline short utree::tag() const 1585 { 1586 return s.tag(); 1587 } 1588 tag(short tag)1589 inline void utree::tag(short tag) 1590 { 1591 s.tag(tag); 1592 } 1593 eval(utree const & env) const1594 inline utree utree::eval(utree const& env) const 1595 { 1596 if (get_type() == type::reference_type) 1597 return deref().eval(env); 1598 1599 if (get_type() != type::function_type) 1600 BOOST_THROW_EXCEPTION( 1601 bad_type_exception( 1602 "eval() called on non-function utree type", get_type())); 1603 return (*pf)(env); 1604 } 1605 eval(utree & env) const1606 inline utree utree::eval(utree& env) const 1607 { 1608 if (get_type() == type::reference_type) 1609 return deref().eval(env); 1610 1611 if (get_type() != type::function_type) 1612 BOOST_THROW_EXCEPTION( 1613 bad_type_exception( 1614 "eval() called on non-function utree type", get_type())); 1615 return (*pf)(env); 1616 } 1617 operator ()(utree const & env) const1618 inline utree utree::operator() (utree const& env) const 1619 { 1620 return eval(env); 1621 } 1622 operator ()(utree & env) const1623 inline utree utree::operator() (utree& env) const 1624 { 1625 return eval(env); 1626 } 1627 }} 1628 1629 #if defined(BOOST_MSVC) 1630 # pragma warning(pop) 1631 #endif 1632 #endif 1633