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