utree/detail/utree_detail2.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2011 Joel de Guzman
0003     Copyright (c) 2001-2011 Hartmut Kaiser
0004     Copyright (c)      2011 Bryce Lelbach
0005
0006     Distributed under the Boost Software License, Version 1.0. (See accompanying
0007     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0008 =============================================================================*/
0009 #if !defined(BOOST_SPIRIT_UTREE_DETAIL2)
0010 #define BOOST_SPIRIT_UTREE_DETAIL2
0011
0012 #include <boost/type_traits/remove_pointer.hpp>
0013 #include <boost/type_traits/is_pointer.hpp>
0014 #include <boost/utility/enable_if.hpp>
0015 #include <boost/throw_exception.hpp>
0016 #include <boost/iterator/iterator_traits.hpp>
0017 #include <cstring> // for std::memcpy
0018
0019 #ifdef _MSC_VER
0020 # pragma warning(push)
0021 # pragma warning(disable: 4800) // forcing value to bool 'true' or 'false'
0022 # if _MSC_VER < 1800
0023 #  pragma warning(disable: 4702) // unreachable code
0024 # endif
0025 #endif
0026
0027 namespace boost { namespace spirit { namespace detail
0028 {
0029     inline char& fast_string::info()
0030     {
0031         return buff[small_string_size];
0032     }
0033
0034     inline char fast_string::info() const
0035     {
0036         return buff[small_string_size];
0037     }
0038
0039     inline int fast_string::get_type() const
0040     {
0041         return info() >> 1;
0042     }
0043
0044     inline void fast_string::set_type(int t)
0045     {
0046         info() = (t << 1) | (info() & 1);
0047     }
0048
0049     inline short fast_string::tag() const
0050     {
0051         boost::int16_t tmp;
0052         std::memcpy(&tmp, &buff[small_string_size-2], sizeof(tmp));
0053         return tmp;
0054     }
0055
0056     inline void fast_string::tag(short tag)
0057     {
0058         boost::int16_t tmp = tag;
0059         std::memcpy(&buff[small_string_size-2], &tmp, sizeof(tmp));
0060     }
0061
0062     inline bool fast_string::is_heap_allocated() const
0063     {
0064         return info() & 1;
0065     }
0066
0067     inline std::size_t fast_string::size() const
0068     {
0069         if (is_heap_allocated())
0070             return heap.size;
0071         else
0072             return max_string_len - buff[max_string_len];
0073     }
0074
0075     inline char const* fast_string::str() const
0076     {
0077         if (is_heap_allocated())
0078             return heap.str;
0079         else
0080             return buff;
0081     }
0082
0083     template <typename Iterator>
0084     inline void fast_string::construct(Iterator f, Iterator l)
0085     {
0086         std::size_t const size = static_cast<std::size_t>(l-f);
0087         char* str;
0088         if (size < max_string_len)
0089         {
0090             // if it fits, store it in-situ; small_string_size minus the length
0091             // of the string is placed in buff[small_string_size - 1]
0092             str = buff;
0093             buff[max_string_len] = static_cast<char>(max_string_len - size);
0094             info() &= ~0x1;
0095         }
0096         else
0097         {
0098             // else, store it in the heap
0099             str = new char[size + 1]; // add one for the null char
0100             heap.str = str;
0101             heap.size = size;
0102             info() |= 0x1;
0103         }
0104         for (std::size_t i = 0; i != size; ++i)
0105         {
0106             *str++ = *f++;
0107         }
0108         *str = '\0'; // add the null char
0109     }
0110
0111     inline void fast_string::swap(fast_string& other)
0112     {
0113         std::swap(*this, other);
0114     }
0115
0116     inline void fast_string::free()
0117     {
0118         if (is_heap_allocated())
0119         {
0120             delete [] heap.str;
0121         }
0122     }
0123
0124     inline void fast_string::copy(fast_string const& other)
0125     {
0126         construct(other.str(), other.str() + other.size());
0127     }
0128
0129     inline void fast_string::initialize()
0130     {
0131         for (std::size_t i = 0; i != buff_size / (sizeof(long)/sizeof(char)); ++i)
0132             lbuff[i] = 0;
0133     }
0134
0135     struct list::node : boost::noncopyable
0136     {
0137         template <typename T>
0138         node(T const& val, node* next, node* prev)
0139           : val(val), next(next), prev(prev) {}
0140
0141         void unlink()
0142         {
0143             prev->next = next;
0144             next->prev = prev;
0145         }
0146
0147         utree val;
0148         node* next;
0149         node* prev;
0150     };
0151
0152     template <typename Value>
0153     class list::node_iterator
0154       : public boost::iterator_facade<
0155             node_iterator<Value>
0156           , Value
0157           , boost::bidirectional_traversal_tag>
0158     {
0159     public:
0160
0161         node_iterator()
0162           : node(0), prev(0) {}
0163
0164         node_iterator(list::node* node, list::node* prev)
0165           : node(node), prev(prev) {}
0166
0167     private:
0168
0169         friend class boost::iterator_core_access;
0170         friend class boost::spirit::utree;
0171         friend struct boost::spirit::detail::list;
0172
0173         void increment()
0174         {
0175             if (node != 0) // not at end
0176             {
0177                 prev = node;
0178                 node = node->next;
0179             }
0180         }
0181
0182         void decrement()
0183         {
0184             if (prev != 0) // not at begin
0185             {
0186                 node = prev;
0187                 prev = prev->prev;
0188             }
0189         }
0190
0191         bool equal(node_iterator const& other) const
0192         {
0193             return node == other.node;
0194         }
0195
0196         typename node_iterator::reference dereference() const
0197         {
0198             return node->val;
0199         }
0200
0201         list::node* node;
0202         list::node* prev;
0203     };
0204
0205     template <typename Value>
0206     class list::node_iterator<boost::reference_wrapper<Value> >
0207       : public boost::iterator_facade<
0208             node_iterator<boost::reference_wrapper<Value> >
0209           , boost::reference_wrapper<Value>
0210           , boost::bidirectional_traversal_tag>
0211     {
0212     public:
0213
0214         node_iterator()
0215           : node(0), prev(0), curr(nil_node) {}
0216
0217         node_iterator(list::node* node, list::node* prev)
0218           : node(node), prev(prev), curr(node ? node->val : nil_node) {}
0219
0220     private:
0221
0222         friend class boost::iterator_core_access;
0223         friend class boost::spirit::utree;
0224         friend struct boost::spirit::detail::list;
0225
0226         void increment()
0227         {
0228             if (node != 0) // not at end
0229             {
0230                 prev = node;
0231                 node = node->next;
0232                 curr = boost::ref(node ? node->val : nil_node);
0233             }
0234         }
0235
0236         void decrement()
0237         {
0238             if (prev != 0) // not at begin
0239             {
0240                 node = prev;
0241                 prev = prev->prev;
0242                 curr = boost::ref(node ? node->val : nil_node);
0243             }
0244         }
0245
0246         bool equal(node_iterator const& other) const
0247         {
0248             return node == other.node;
0249         }
0250
0251         typename node_iterator::reference dereference() const
0252         {
0253             return curr;
0254         }
0255
0256         list::node* node;
0257         list::node* prev;
0258
0259         static Value nil_node;
0260         mutable boost::reference_wrapper<Value> curr;
0261     };
0262
0263     template <typename Value>
0264     Value list::node_iterator<boost::reference_wrapper<Value> >::nil_node = Value();
0265
0266     inline void list::free()
0267     {
0268         node* p = first;
0269         while (p != 0)
0270         {
0271             node* next = p->next;
0272             delete p;
0273             p = next;
0274         }
0275     }
0276
0277     inline void list::copy(list const& other)
0278     {
0279         node* p = other.first;
0280         while (p != 0)
0281         {
0282             push_back(p->val);
0283             p = p->next;
0284         }
0285     }
0286
0287     inline void list::default_construct()
0288     {
0289         first = last = 0;
0290         size = 0;
0291     }
0292
0293     template <typename T, typename Iterator>
0294     inline void list::insert(T const& val, Iterator pos)
0295     {
0296         if (!pos.node)
0297         {
0298             push_back(val);
0299             return;
0300         }
0301
0302         detail::list::node* new_node =
0303             new detail::list::node(val, pos.node, pos.node->prev);
0304
0305         if (pos.node->prev)
0306             pos.node->prev->next = new_node;
0307         else
0308             first = new_node;
0309
0310         pos.node->prev = new_node;
0311         ++size;
0312     }
0313
0314     template <typename T>
0315     inline void list::push_front(T const& val)
0316     {
0317         detail::list::node* new_node;
0318         if (first == 0)
0319         {
0320             new_node = new detail::list::node(val, 0, 0);
0321             first = last = new_node;
0322             ++size;
0323         }
0324         else
0325         {
0326             new_node = new detail::list::node(val, first, first->prev);
0327             first->prev = new_node;
0328             first = new_node;
0329             ++size;
0330         }
0331     }
0332
0333     template <typename T>
0334     inline void list::push_back(T const& val)
0335     {
0336         if (last == 0)
0337             push_front(val);
0338         else {
0339             detail::list::node* new_node =
0340                 new detail::list::node(val, last->next, last);
0341             last->next = new_node;
0342             last = new_node;
0343             ++size;
0344         }
0345     }
0346
0347     inline void list::pop_front()
0348     {
0349         BOOST_ASSERT(size != 0);
0350         if (first == last) // there's only one item
0351         {
0352             delete first;
0353             size = 0;
0354             first = last = 0;
0355         }
0356         else
0357         {
0358             node* np = first;
0359             first = first->next;
0360             first->prev = 0;
0361             delete np;
0362             --size;
0363         }
0364     }
0365
0366     inline void list::pop_back()
0367     {
0368         BOOST_ASSERT(size != 0);
0369         if (first == last) // there's only one item
0370         {
0371             delete first;
0372             size = 0;
0373             first = last = 0;
0374         }
0375         else
0376         {
0377             node* np = last;
0378             last = last->prev;
0379             last->next = 0;
0380             delete np;
0381             --size;
0382         }
0383     }
0384
0385     inline list::node* list::erase(node* pos)
0386     {
0387         BOOST_ASSERT(pos != 0);
0388         if (pos == first)
0389         {
0390             pop_front();
0391             return first;
0392         }
0393         else if (pos == last)
0394         {
0395             pop_back();
0396             return 0;
0397         }
0398         else
0399         {
0400             node* next(pos->next);
0401             pos->unlink();
0402             delete pos;
0403             --size;
0404             return next;
0405         }
0406     }
0407
0408     ///////////////////////////////////////////////////////////////////////////
0409     // simple binder for binary visitation (we don't want to bring in the big guns)
0410     template <typename F, typename X>
0411     struct bind_impl
0412     {
0413         typedef typename F::result_type result_type;
0414         X& x; // always by reference
0415         F f;
0416         bind_impl(F f, X& x) : x(x), f(f) {}
0417
0418         template <typename Y>
0419         typename F::result_type operator()(Y& y) const
0420         {
0421             return f(x, y);
0422         }
0423
0424         template <typename Y>
0425         typename F::result_type operator()(Y const& y) const
0426         {
0427             return f(x, y);
0428         }
0429     };
0430
0431     template <typename F, typename X>
0432     bind_impl<F, X const> bind(F f, X const& x)
0433     {
0434         return bind_impl<F, X const>(f, x);
0435     }
0436
0437     template <typename F, typename X>
0438     bind_impl<F, X> bind(F f, X& x)
0439     {
0440         return bind_impl<F, X>(f, x);
0441     }
0442
0443     template <typename UTreeX, typename UTreeY = UTreeX>
0444     struct visit_impl
0445     {
0446         template <typename F>
0447         typename F::result_type
0448         static apply(UTreeX& x, F f) // single dispatch
0449         {
0450             typedef typename
0451                 boost::mpl::if_<boost::is_const<UTreeX>,
0452                 typename UTreeX::const_iterator,
0453                 typename UTreeX::iterator>::type
0454             iterator;
0455
0456             typedef boost::iterator_range<iterator> list_range;
0457             typedef utree_type type;
0458
0459             switch (x.get_type())
0460             {
0461                 default:
0462                     BOOST_THROW_EXCEPTION(
0463                         bad_type_exception("corrupt utree type", x.get_type()));
0464                     break;
0465
0466                 case type::invalid_type:
0467                     return f(invalid);
0468
0469                 case type::nil_type:
0470                     return f(nil);
0471
0472                 case type::bool_type:
0473                     return f(x.b);
0474
0475                 case type::int_type:
0476                     return f(x.i);
0477
0478                 case type::double_type:
0479                     return f(x.d);
0480
0481                 case type::list_type:
0482                     return f(list_range(iterator(x.l.first, 0), iterator(0, x.l.last)));
0483
0484                 case type::range_type:
0485                     return f(list_range(iterator(x.r.first, 0), iterator(0, x.r.last)));
0486
0487                 case type::string_type:
0488                     return f(utf8_string_range_type(x.s.str(), x.s.size()));
0489
0490                 case type::string_range_type:
0491                     return f(utf8_string_range_type(x.sr.first, x.sr.last));
0492
0493                 case type::symbol_type:
0494                     return f(utf8_symbol_range_type(x.s.str(), x.s.size()));
0495
0496                 case type::binary_type:
0497                     return f(binary_range_type(x.s.str(), x.s.size()));
0498
0499                 case type::reference_type:
0500                     return apply(*x.p, f);
0501
0502                 case type::any_type:
0503                     return f(any_ptr(x.v.p, x.v.i));
0504
0505                 case type::function_type:
0506                     return f(*x.pf);
0507             }
0508         }
0509
0510         template <typename F>
0511         typename F::result_type
0512         static apply(UTreeX& x, UTreeY& y, F f) // double dispatch
0513         {
0514             typedef typename
0515                 boost::mpl::if_<boost::is_const<UTreeX>,
0516                 typename UTreeX::const_iterator,
0517                 typename UTreeX::iterator>::type
0518             iterator;
0519
0520             typedef boost::iterator_range<iterator> list_range;
0521             typedef utree_type type;
0522
0523             switch (x.get_type())
0524             {
0525                 default:
0526                     BOOST_THROW_EXCEPTION(
0527                         bad_type_exception("corrupt utree type", x.get_type()));
0528                     break;
0529
0530                 case type::invalid_type:
0531                     return visit_impl::apply(y, detail::bind(f, invalid));
0532
0533                 case type::nil_type:
0534                     return visit_impl::apply(y, detail::bind(f, nil));
0535
0536                 case type::bool_type:
0537                     return visit_impl::apply(y, detail::bind(f, x.b));
0538
0539                 case type::int_type:
0540                     return visit_impl::apply(y, detail::bind(f, x.i));
0541
0542                 case type::double_type:
0543                     return visit_impl::apply(y, detail::bind(f, x.d));
0544
0545                 case type::list_type:
0546                     return visit_impl::apply(
0547                         y, detail::bind<F, list_range>(f,
0548                         list_range(iterator(x.l.first, 0), iterator(0, x.l.last))));
0549
0550                 case type::range_type:
0551                     return visit_impl::apply(
0552                         y, detail::bind<F, list_range>(f,
0553                         list_range(iterator(x.r.first, 0), iterator(0, x.r.last))));
0554
0555                 case type::string_type:
0556                     return visit_impl::apply(y, detail::bind(
0557                         f, utf8_string_range_type(x.s.str(), x.s.size())));
0558
0559                 case type::string_range_type:
0560                     return visit_impl::apply(y, detail::bind(
0561                         f, utf8_string_range_type(x.sr.first, x.sr.last)));
0562
0563                 case type::symbol_type:
0564                     return visit_impl::apply(y, detail::bind(
0565                         f, utf8_symbol_range_type(x.s.str(), x.s.size())));
0566
0567                 case type::binary_type:
0568                     return visit_impl::apply(y, detail::bind(
0569                         f, binary_range_type(x.s.str(), x.s.size())));
0570
0571                 case type::reference_type:
0572                     return apply(*x.p, y, f);
0573
0574                 case type::any_type:
0575                     return visit_impl::apply(
0576                         y, detail::bind(f, any_ptr(x.v.p, x.v.i)));
0577
0578                 case type::function_type:
0579                     return visit_impl::apply(y, detail::bind(f, *x.pf));
0580             }
0581         }
0582     };
0583
0584     struct index_impl
0585     {
0586         static utree& apply(utree& ut, std::size_t i)
0587         {
0588             switch (ut.get_type())
0589             {
0590                 case utree_type::reference_type:
0591                     return apply(ut.deref(), i);
0592                 case utree_type::range_type:
0593                     return apply(ut.r.first, i);
0594                 case utree_type::list_type:
0595                     return apply(ut.l.first, i);
0596                 default:
0597                     BOOST_THROW_EXCEPTION(
0598                         bad_type_exception
0599                             ("index operation performed on non-list utree type",
0600                              ut.get_type()));
0601             }
0602         }
0603
0604         static utree const& apply(utree const& ut, std::size_t i)
0605         {
0606             switch (ut.get_type())
0607             {
0608                 case utree_type::reference_type:
0609                     return apply(ut.deref(), i);
0610                 case utree_type::range_type:
0611                     return apply(ut.r.first, i);
0612                 case utree_type::list_type:
0613                     return apply(ut.l.first, i);
0614                 default:
0615                     BOOST_THROW_EXCEPTION(
0616                         bad_type_exception
0617                             ("index operation performed on non-list utree type",
0618                              ut.get_type()));
0619             }
0620         }
0621
0622         static utree& apply(list::node* node, std::size_t i)
0623         {
0624             for (; i > 0; --i)
0625                 node = node->next;
0626             return node->val;
0627         }
0628
0629         static utree const& apply(list::node const* node, std::size_t i)
0630         {
0631             for (; i > 0; --i)
0632                 node = node->next;
0633             return node->val;
0634         }
0635     };
0636 }}}
0637
0638 namespace boost { namespace spirit
0639 {
0640     template <typename F>
0641     stored_function<F>::stored_function(F f)
0642       : f(f)
0643     {
0644     }
0645
0646     template <typename F>
0647     stored_function<F>::~stored_function()
0648     {
0649     }
0650
0651     template <typename F>
0652     utree stored_function<F>::operator()(utree const& env) const
0653     {
0654         return f(env);
0655     }
0656
0657     template <typename F>
0658     utree stored_function<F>::operator()(utree& env) const
0659     {
0660         return f(env);
0661     }
0662
0663     template <typename F>
0664     function_base*
0665     stored_function<F>::clone() const
0666     {
0667         return new stored_function<F>(f);
0668     }
0669
0670     template <typename F>
0671     referenced_function<F>::referenced_function(F& f)
0672       : f(f)
0673     {
0674     }
0675
0676     template <typename F>
0677     referenced_function<F>::~referenced_function()
0678     {
0679     }
0680
0681     template <typename F>
0682     utree referenced_function<F>::operator()(utree const& env) const
0683     {
0684         return f(env);
0685     }
0686
0687     template <typename F>
0688     utree referenced_function<F>::operator()(utree& env) const
0689     {
0690         return f(env);
0691     }
0692
0693     template <typename F>
0694     function_base*
0695     referenced_function<F>::clone() const
0696     {
0697         return new referenced_function<F>(f);
0698     }
0699
0700     inline utree::utree(utree::invalid_type)
0701     {
0702         s.initialize();
0703         set_type(type::invalid_type);
0704     }
0705
0706     inline utree::utree(utree::nil_type)
0707     {
0708         s.initialize();
0709         set_type(type::nil_type);
0710     }
0711
0712     inline utree::utree(bool b_)
0713     {
0714         s.initialize();
0715         b = b_;
0716         set_type(type::bool_type);
0717     }
0718
0719     inline utree::utree(char c)
0720     {
0721         s.initialize();
0722         // char constructs a single element string
0723         s.construct(&c, &c+1);
0724         set_type(type::string_type);
0725     }
0726
0727     inline utree::utree(unsigned int i_)
0728     {
0729         s.initialize();
0730         i = i_;
0731         set_type(type::int_type);
0732     }
0733
0734     inline utree::utree(int i_)
0735     {
0736         s.initialize();
0737         i = i_;
0738         set_type(type::int_type);
0739     }
0740
0741     inline utree::utree(double d_)
0742     {
0743         s.initialize();
0744         d = d_;
0745         set_type(type::double_type);
0746     }
0747
0748     inline utree::utree(char const* str)
0749     {
0750         s.initialize();
0751         s.construct(str, str + strlen(str));
0752         set_type(type::string_type);
0753     }
0754
0755     inline utree::utree(char const* str, std::size_t len)
0756     {
0757         s.initialize();
0758         s.construct(str, str + len);
0759         set_type(type::string_type);
0760     }
0761
0762     inline utree::utree(std::string const& str)
0763     {
0764         s.initialize();
0765         s.construct(str.begin(), str.end());
0766         set_type(type::string_type);
0767     }
0768
0769     template <typename Base, utree_type::info type_>
0770     inline utree::utree(basic_string<Base, type_> const& bin)
0771     {
0772         s.initialize();
0773         s.construct(bin.begin(), bin.end());
0774         set_type(type_);
0775     }
0776
0777     inline utree::utree(boost::reference_wrapper<utree> ref)
0778     {
0779         s.initialize();
0780         p = ref.get_pointer();
0781         set_type(type::reference_type);
0782     }
0783
0784     inline utree::utree(any_ptr const& p)
0785     {
0786         s.initialize();
0787         v.p = p.p;
0788         v.i = p.i;
0789         set_type(type::any_type);
0790     }
0791
0792     inline utree::utree(function_base const& pf_)
0793     {
0794         s.initialize();
0795         pf = pf_.clone();
0796         set_type(type::function_type);
0797     }
0798
0799     inline utree::utree(function_base* pf_)
0800     {
0801         s.initialize();
0802         pf = pf_;
0803         set_type(type::function_type);
0804     }
0805
0806     template <typename Iter>
0807     inline utree::utree(boost::iterator_range<Iter> r)
0808     {
0809         s.initialize();
0810
0811         assign(r.begin(), r.end());
0812     }
0813
0814     inline utree::utree(range r, shallow_tag)
0815     {
0816         s.initialize();
0817         this->r.first = r.begin().node;
0818         this->r.last = r.end().prev;
0819         set_type(type::range_type);
0820     }
0821
0822     inline utree::utree(const_range r, shallow_tag)
0823     {
0824         s.initialize();
0825         this->r.first = r.begin().node;
0826         this->r.last = r.end().prev;
0827         set_type(type::range_type);
0828     }
0829
0830     inline utree::utree(utf8_string_range_type const& str, shallow_tag)
0831     {
0832         s.initialize();
0833         this->sr.first = str.begin();
0834         this->sr.last = str.end();
0835         set_type(type::string_range_type);
0836     }
0837
0838     inline utree::utree(utree const& other)
0839     {
0840         s.initialize();
0841         copy(other);
0842     }
0843
0844     inline utree::~utree()
0845     {
0846         free();
0847     }
0848
0849     inline utree& utree::operator=(utree const& other)
0850     {
0851         if (this != &other)
0852         {
0853             free();
0854             copy(other);
0855         }
0856         return *this;
0857     }
0858
0859     inline utree& utree::operator=(nil_type)
0860     {
0861         free();
0862         set_type(type::nil_type);
0863         return *this;
0864     }
0865
0866     inline utree& utree::operator=(bool b_)
0867     {
0868         free();
0869         b = b_;
0870         set_type(type::bool_type);
0871         return *this;
0872     }
0873
0874     inline utree& utree::operator=(char c)
0875     {
0876         // char constructs a single element string
0877         free();
0878         s.construct(&c, &c+1);
0879         set_type(type::string_type);
0880         return *this;
0881     }
0882
0883     inline utree& utree::operator=(unsigned int i_)
0884     {
0885         free();
0886         i = i_;
0887         set_type(type::int_type);
0888         return *this;
0889     }
0890
0891     inline utree& utree::operator=(int i_)
0892     {
0893         free();
0894         i = i_;
0895         set_type(type::int_type);
0896         return *this;
0897     }
0898
0899     inline utree& utree::operator=(double d_)
0900     {
0901         free();
0902         d = d_;
0903         set_type(type::double_type);
0904         return *this;
0905     }
0906
0907     inline utree& utree::operator=(char const* s_)
0908     {
0909         free();
0910         s.construct(s_, s_ + strlen(s_));
0911         set_type(type::string_type);
0912         return *this;
0913     }
0914
0915     inline utree& utree::operator=(std::string const& s_)
0916     {
0917         free();
0918         s.construct(s_.begin(), s_.end());
0919         set_type(type::string_type);
0920         return *this;
0921     }
0922
0923     template <typename Base, utree_type::info type_>
0924     inline utree& utree::operator=(basic_string<Base, type_> const& bin)
0925     {
0926         free();
0927         s.construct(bin.begin(), bin.end());
0928         set_type(type_);
0929         return *this;
0930     }
0931
0932     inline utree& utree::operator=(boost::reference_wrapper<utree> ref)
0933     {
0934         free();
0935         p = ref.get_pointer();
0936         set_type(type::reference_type);
0937         return *this;
0938     }
0939
0940     inline utree& utree::operator=(any_ptr const& p_)
0941     {
0942         free();
0943         v.p = p_.p;
0944         v.i = p_.i;
0945         set_type(type::any_type);
0946         return *this;
0947     }
0948
0949     inline utree& utree::operator=(function_base const& pf_)
0950     {
0951         free();
0952         pf = pf_.clone();
0953         set_type(type::function_type);
0954         return *this;
0955     }
0956
0957     inline utree& utree::operator=(function_base* pf_)
0958     {
0959         free();
0960         pf = pf_;
0961         set_type(type::function_type);
0962         return *this;
0963     }
0964
0965     template <typename Iter>
0966     inline utree& utree::operator=(boost::iterator_range<Iter> r)
0967     {
0968         free();
0969         assign(r.begin(), r.end());
0970         return *this;
0971     }
0972
0973     template <typename F>
0974     typename boost::result_of<F(utree const&)>::type
0975     inline utree::visit(utree const& x, F f)
0976     {
0977         return detail::visit_impl<utree const>::apply(x, f);
0978     }
0979
0980     template <typename F>
0981     typename boost::result_of<F(utree&)>::type
0982     inline utree::visit(utree& x, F f)
0983     {
0984         return detail::visit_impl<utree>::apply(x, f);
0985     }
0986
0987     template <typename F>
0988     typename boost::result_of<F(utree const&, utree const&)>::type
0989     inline utree::visit(utree const& x, utree const& y, F f)
0990     {
0991         return detail::visit_impl<utree const, utree const>::apply(x, y, f);
0992     }
0993
0994     template <typename F>
0995     typename boost::result_of<F(utree const&, utree&)>::type
0996     inline utree::visit(utree const& x, utree& y, F f)
0997     {
0998         return detail::visit_impl<utree const, utree>::apply(x, y, f);
0999     }
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