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