ceph/src/boost/boost/spirit/home/support/utree/detail/utree_detail2.hpp

   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 {
  29     inline char& fast_string::info()
  30     {
  31         return buff[small_string_size];
  32     }
  33
  34     inline char fast_string::info() const
  35     {
  36         return buff[small_string_size];
  37     }
  38
  39     inline int fast_string::get_type() const
  40     {
  41         return info() >> 1;
  42     }
  43
  44     inline void fast_string::set_type(int t)
  45     {
  46         info() = (t << 1) | (info() & 1);
  47     }
  48
  49     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
  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
  62     inline bool fast_string::is_heap_allocated() const
  63     {
  64         return info() & 1;
  65     }
  66
  67     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
  75     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>
  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
 111     inline void fast_string::swap(fast_string& other)
 112     {
 113         std::swap(*this, other);
 114     }
 115
 116     inline void fast_string::free()
 117     {
 118         if (is_heap_allocated())
 119         {
 120             delete [] heap.str;
 121         }
 122     }
 123
 124     inline void fast_string::copy(fast_string const& other)
 125     {
 126         construct(other.str(), other.str() + other.size());
 127     }
 128
 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>
 138         node(T const& val, node* next, node* prev)
 139           : val(val), next(next), prev(prev) {}
 140
 141         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
 161         node_iterator()
 162           : node(0), prev(0) {}
 163
 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
 173         void increment()
 174         {
 175             if (node != 0) // not at end
 176             {
 177                 prev = node;
 178                 node = node->next;
 179             }
 180         }
 181
 182         void decrement()
 183         {
 184             if (prev != 0) // not at begin
 185             {
 186                 node = prev;
 187                 prev = prev->prev;
 188             }
 189         }
 190
 191         bool equal(node_iterator const& other) const
 192         {
 193             return node == other.node;
 194         }
 195
 196         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
 214         node_iterator()
 215           : node(0), prev(0), curr(nil_node) {}
 216
 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
 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
 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
 246         bool equal(node_iterator const& other) const
 247         {
 248             return node == other.node;
 249         }
 250
 251         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
 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
 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
 287     inline void list::default_construct()
 288     {
 289         first = last = 0;
 290         size = 0;
 291     }
 292
 293     template <typename T, typename Iterator>
 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>
 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>
 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
 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
 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
 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;
 416         bind_impl(F f, X& x) : x(x), f(f) {}
 417
 418         template <typename Y>
 419         typename F::result_type operator()(Y& y) const
 420         {
 421             return f(x, y);
 422         }
 423
 424         template <typename Y>
 425         typename F::result_type operator()(Y const& y) const
 426         {
 427             return f(x, y);
 428         }
 429     };
 430
 431     template <typename F, typename 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>
 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
 448         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
 512         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     {
 586         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
 604         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
 622         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
 629         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>
 641     stored_function<F>::stored_function(F f)
 642       : f(f)
 643     {
 644     }
 645
 646     template <typename F>
 647     stored_function<F>::~stored_function()
 648     {
 649     }
 650
 651     template <typename F>
 652     utree stored_function<F>::operator()(utree const& env) const
 653     {
 654         return f(env);
 655     }
 656
 657     template <typename F>
 658     utree stored_function<F>::operator()(utree& env) const
 659     {
 660         return f(env);
 661     }
 662
 663     template <typename F>
 664     function_base*
 665     stored_function<F>::clone() const
 666     {
 667         return new stored_function<F>(f);
 668     }
 669
 670     template <typename F>
 671     referenced_function<F>::referenced_function(F& f)
 672       : f(f)
 673     {
 674     }
 675
 676     template <typename F>
 677     referenced_function<F>::~referenced_function()
 678     {
 679     }
 680
 681     template <typename F>
 682     utree referenced_function<F>::operator()(utree const& env) const
 683     {
 684         return f(env);
 685     }
 686
 687     template <typename F>
 688     utree referenced_function<F>::operator()(utree& env) const
 689     {
 690         return f(env);
 691     }
 692
 693     template <typename F>
 694     function_base*
 695     referenced_function<F>::clone() const
 696     {
 697         return new referenced_function<F>(f);
 698     }
 699
 700     inline utree::utree(utree::invalid_type)
 701     {
 702         s.initialize();
 703         set_type(type::invalid_type);
 704     }
 705
 706     inline utree::utree(utree::nil_type)
 707     {
 708         s.initialize();
 709         set_type(type::nil_type);
 710     }
 711
 712     inline utree::utree(bool b_)
 713     {
 714         s.initialize();
 715         b = b_;
 716         set_type(type::bool_type);
 717     }
 718
 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
 727     inline utree::utree(unsigned int i_)
 728     {
 729         s.initialize();
 730         i = i_;
 731         set_type(type::int_type);
 732     }
 733
 734     inline utree::utree(int i_)
 735     {
 736         s.initialize();
 737         i = i_;
 738         set_type(type::int_type);
 739     }
 740
 741     inline utree::utree(double d_)
 742     {
 743         s.initialize();
 744         d = d_;
 745         set_type(type::double_type);
 746     }
 747
 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
 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
 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_>
 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
 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
 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
 792     inline utree::utree(function_base const& pf_)
 793     {
 794         s.initialize();
 795         pf = pf_.clone();
 796         set_type(type::function_type);
 797     }
 798
 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>
 807     inline utree::utree(boost::iterator_range<Iter> r)
 808     {
 809         s.initialize();
 810
 811         assign(r.begin(), r.end());
 812     }
 813
 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
 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
 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
 838     inline utree::utree(utree const& other)
 839     {
 840         s.initialize();
 841         copy(other);
 842     }
 843
 844     inline utree::~utree()
 845     {
 846         free();
 847     }
 848
 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
 859     inline utree& utree::operator=(nil_type)
 860     {
 861         free();
 862         set_type(type::nil_type);
 863         return *this;
 864     }
 865
 866     inline utree& utree::operator=(bool b_)
 867     {
 868         free();
 869         b = b_;
 870         set_type(type::bool_type);
 871         return *this;
 872     }
 873
 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
 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
 891     inline utree& utree::operator=(int i_)
 892     {
 893         free();
 894         i = i_;
 895         set_type(type::int_type);
 896         return *this;
 897     }
 898
 899     inline utree& utree::operator=(double d_)
 900     {
 901         free();
 902         d = d_;
 903         set_type(type::double_type);
 904         return *this;
 905     }
 906
 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
 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_>
 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
 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
 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
 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
 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>
 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
 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
 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
 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
 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
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
1010     inline utree::visit(utree& x, utree& y, F f)
1011     {
1012         return detail::visit_impl<utree, utree>::apply(x, y, f);
1013     }
1014
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
1019     get(utree::const_reference ut, utree::size_type i)
1020     { return detail::index_impl::apply(ut, i); }
1021
1022     template <typename T>
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>
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>
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>
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>
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>
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
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
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
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
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
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
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
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
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
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
1209     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
1226     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
1243     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
1257     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
1300     inline utree_type::info utree::which() const
1301     {
1302         return get_type();
1303     }
1304
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
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
1353     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
1377     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
1401     inline void utree::swap(utree& other)
1402     {
1403         s.swap(other.s);
1404     }
1405
1406     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
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
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
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
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>
1529         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>
1535         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>
1543         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>
1561         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
1568         T* operator()(any_ptr const& p) const
1569         {
1570             return p.get<T*>();
1571         }
1572     };
1573
1574     template <typename T>
1575     inline T utree::get() const
1576     {
1577         return utree::visit(*this, utree_cast<T>());
1578     }
1579
1580     inline utree& utree::deref()
1581     {
1582         return (get_type() == type::reference_type) ? *p : *this;
1583     }
1584
1585     inline utree const& utree::deref() const
1586     {
1587         return (get_type() == type::reference_type) ? *p : *this;
1588     }
1589
1590     inline short utree::tag() const
1591     {
1592         return s.tag();
1593     }
1594
1595     inline void utree::tag(short tag)
1596     {
1597         s.tag(tag);
1598     }
1599
1600     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
1612     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
1624     inline utree utree::operator() (utree const& env) const
1625     {
1626         return eval(env);
1627     }
1628
1629     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