support/utree/utree.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2011 Joel de Guzman
0003     Copyright (c) 2001-2011 Hartmut Kaiser
0004     Copyright (c) 2010-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)
0010 #define BOOST_SPIRIT_UTREE
0011
0012 #include <cstddef>
0013 #include <algorithm>
0014 #include <string>
0015 #include <ios>
0016 #include <sstream>
0017 #include <typeinfo>
0018
0019 #include <boost/io/ios_state.hpp>
0020 #include <boost/integer.hpp>
0021 #include <boost/throw_exception.hpp>
0022 #include <boost/assert.hpp>
0023 #include <boost/noncopyable.hpp>
0024 #include <boost/iterator/iterator_facade.hpp>
0025 #include <boost/range/iterator_range_core.hpp>
0026 #include <boost/type_traits/remove_pointer.hpp>
0027 #include <boost/type_traits/is_polymorphic.hpp>
0028 #include <boost/utility/enable_if.hpp>
0029 #include <boost/utility/result_of.hpp>
0030 #include <boost/ref.hpp>
0031 #include <boost/config.hpp>
0032
0033 #include <boost/spirit/home/support/utree/detail/utree_detail1.hpp>
0034
0035 #if defined(BOOST_MSVC)
0036 # pragma warning(push)
0037 # pragma warning(disable: 4804)
0038 # pragma warning(disable: 4805)
0039 # pragma warning(disable: 4244)
0040 #endif
0041
0042 namespace boost { namespace spirit
0043 {
0044     //[utree_exceptions
0045     /*` All exceptions thrown by utree are derived from utree_exception. */
0046     struct BOOST_SYMBOL_VISIBLE utree_exception : std::exception {};
0047
0048     /*`The `bad_type_exception` is thrown whenever somebody calls a member
0049        function, which applies to certain stored utree_type's only, but this
0050        precondition is violated as the `utree` instance holds some other type.
0051     */
0052     struct bad_type_exception /*: utree_exception*/;
0053
0054     /*`The `empty_exception` is thrown whenever a precondition of a list
0055        or range utree method is violated due to the list or range being empty.
0056     */
0057     struct empty_exception /*: utree_exception*/;
0058     //]
0059
0060     //[utree_types
0061     /*`Each instance of an `utree` data structure can store exactly one of the
0062        following data types at a time:
0063     */
0064     struct utree_type
0065     {
0066         enum info
0067         {
0068             invalid_type,       // the utree has not been initialized (it's
0069                                 // default constructed)
0070             nil_type,           // nil is the sentinel (empty) utree type.
0071             list_type,          // A doubly linked list of utrees.
0072             range_type,         // A range of list::iterators.
0073             reference_type,     // A reference to another utree.
0074             any_type,           // A pointer or reference to any C++ type.
0075             function_type,      // A utree holding a stored_function<F> object,
0076                                 // where F is an unary function object taking a
0077                                 // utree as it's parameter and returning a
0078                                 // utree.
0079
0080             // numeric atoms
0081             bool_type,          // An utree holding a boolean value
0082             int_type,           // An utree holding a integer (int) value
0083             double_type,        // An utree holding a floating point (double) value
0084
0085             // text atoms (utf8)
0086             string_type,        // An UTF-8 string
0087             string_range_type,  // A pair of iterators into an UTF-8 string
0088             symbol_type,        // An UTF-8 symbol name
0089
0090             binary_type         // Arbitrary binary data
0091         };
0092         typedef boost::uint_t<sizeof(info)*8>::exact exact_integral_type;
0093         typedef boost::uint_t<sizeof(info)*8>::fast fast_integral_type;
0094     };
0095     //]
0096
0097     // streaming operator for utree types - essential for diagnostics
0098     inline std::ostream& operator<<(std::ostream& out, utree_type::info t)
0099     {
0100         boost::io::ios_all_saver saver(out);
0101         switch (t) {
0102             case utree_type::invalid_type: { out << "invalid"; break; }
0103             case utree_type::nil_type: { out << "nil"; break; }
0104             case utree_type::list_type: { out << "list"; break; }
0105             case utree_type::range_type: { out << "range"; break; }
0106             case utree_type::reference_type: { out << "reference"; break; }
0107             case utree_type::any_type: { out << "any"; break; }
0108             case utree_type::function_type: { out << "function"; break; }
0109             case utree_type::bool_type: { out << "bool"; break; }
0110             case utree_type::int_type: { out << "int"; break; }
0111             case utree_type::double_type: { out << "double"; break; }
0112             case utree_type::string_type: { out << "string"; break; }
0113             case utree_type::string_range_type: { out << "string_range"; break; }
0114             case utree_type::symbol_type: { out << "symbol"; break; }
0115             case utree_type::binary_type: { out << "binary"; break; }
0116             default: { out << "unknown"; break; }
0117         }
0118         out << std::hex << "[0x"
0119             << static_cast<utree_type::fast_integral_type>(t) << "]";
0120         return out;
0121     }
0122
0123     struct bad_type_exception : utree_exception
0124     {
0125         std::string msg;
0126
0127         bad_type_exception(char const* error, utree_type::info got)
0128           : msg()
0129         {
0130             std::ostringstream oss;
0131             oss << "utree: " << error
0132                 << " (got utree type '" << got << "')";
0133             msg = oss.str();
0134         }
0135
0136         bad_type_exception(char const* error, utree_type::info got1,
0137                            utree_type::info got2)
0138           : msg()
0139         {
0140             std::ostringstream oss;
0141             oss << "utree: " << error
0142                 << " (got utree types '" << got1 << "' and '" << got2 << "')";
0143             msg = oss.str();
0144         }
0145
0146         virtual ~bad_type_exception() BOOST_NOEXCEPT_OR_NOTHROW {}
0147
0148         virtual char const* what() const BOOST_NOEXCEPT_OR_NOTHROW
0149         { return msg.c_str(); }
0150     };
0151
0152     struct empty_exception : utree_exception
0153     {
0154         char const* msg;
0155
0156         empty_exception(char const* error) : msg(error) {}
0157
0158         virtual ~empty_exception() BOOST_NOEXCEPT_OR_NOTHROW {}
0159
0160         virtual char const* what() const BOOST_NOEXCEPT_OR_NOTHROW
0161         { return msg; }
0162     };
0163
0164     ///////////////////////////////////////////////////////////////////////////
0165     // A typed string with parametric Base storage. The storage can be any
0166     // range or (stl container) of chars.
0167     ///////////////////////////////////////////////////////////////////////////
0168     template <typename Base, utree_type::info type_>
0169     struct basic_string : Base
0170     {
0171         static utree_type::info const type = type_;
0172
0173         basic_string()
0174           : Base() {}
0175
0176         basic_string(Base const& base)
0177           : Base(base) {}
0178
0179         template <typename Iterator>
0180         basic_string(Iterator bits, std::size_t len)
0181           : Base(bits, bits + len) {}
0182
0183         template <typename Iterator>
0184         basic_string(Iterator first, Iterator last)
0185           : Base(first, last) {}
0186
0187         basic_string& operator=(Base const& other)
0188         {
0189             Base::operator=(other);
0190             return *this;
0191         }
0192     };
0193
0194     //[utree_strings
0195     /*`The `utree` string types described below are used by the `utree` API
0196        only. These are not used to store information in the `utree` itself.
0197        Their purpose is to refer to different internal `utree` node types
0198        only. For instance, creating a `utree` from a binary data type will
0199        create a `binary_type` utree node (see above).
0200     */
0201     /*`The binary data type can be represented either verbatim as a sequence
0202        of bytes or as a pair of iterators into some other stored binary data
0203        sequence. Use this string type to access/create a `binary_type` `utree`.
0204     */
0205     typedef basic_string<
0206         boost::iterator_range<char const*>, utree_type::binary_type
0207     > binary_range_type;
0208     typedef basic_string<
0209         std::string, utree_type::binary_type
0210     > binary_string_type;
0211
0212     /*`The UTF-8 string can be represented either verbatim as a sequence of
0213        characters or as a pair of iterators into some other stored binary data
0214        sequence. Use this string type to access/create a `string_type` `utree`.
0215     */
0216     typedef basic_string<
0217         boost::iterator_range<char const*>, utree_type::string_type
0218     > utf8_string_range_type;
0219     typedef basic_string<
0220         std::string, utree_type::string_type
0221     > utf8_string_type;
0222
0223     /*`The UTF-8 symbol can be represented either verbatim as a sequence of
0224        characters or as a pair of iterators into some other stored binary data
0225        sequence. Use this string type to access/create a `symbol_type` `utree`.
0226     */
0227     typedef basic_string<
0228         boost::iterator_range<char const*>, utree_type::symbol_type
0229     > utf8_symbol_range_type;
0230     typedef basic_string<
0231         std::string, utree_type::symbol_type
0232     > utf8_symbol_type;
0233     //]
0234
0235     ///////////////////////////////////////////////////////////////////////////
0236     // Our function type
0237     ///////////////////////////////////////////////////////////////////////////
0238     class utree;
0239
0240     //[utree_function_object_interface
0241     struct function_base
0242     {
0243         virtual ~function_base() {}
0244         virtual utree operator()(utree const& env) const = 0;
0245         virtual utree operator()(utree& env) const = 0;
0246
0247         // Calling f.clone() must return a newly allocated function_base
0248         // instance that is equal to f.
0249         virtual function_base* clone() const = 0;
0250     };
0251
0252     template <typename F>
0253     struct stored_function : function_base
0254     {
0255         F f;
0256         stored_function(F f = F());
0257         virtual ~stored_function();
0258         virtual utree operator()(utree const& env) const;
0259         virtual utree operator()(utree& env) const;
0260         virtual function_base* clone() const;
0261     };
0262
0263     template <typename F>
0264     struct referenced_function : function_base
0265     {
0266         F& f;
0267         referenced_function(F& f);
0268         virtual ~referenced_function();
0269         virtual utree operator()(utree const& env) const;
0270         virtual utree operator()(utree& env) const;
0271         virtual function_base* clone() const;
0272     };
0273     //]
0274
0275     ///////////////////////////////////////////////////////////////////////////
0276     // Shallow tag. Instructs utree to hold an iterator_range
0277     // as-is without deep copying the range.
0278     ///////////////////////////////////////////////////////////////////////////
0279     struct shallow_tag {};
0280     shallow_tag const shallow = {};
0281
0282     ///////////////////////////////////////////////////////////////////////////
0283     // A void* plus type_info
0284     ///////////////////////////////////////////////////////////////////////////
0285     class any_ptr
0286     {
0287     public:
0288         template <typename Ptr>
0289         typename boost::disable_if<
0290             boost::is_polymorphic<
0291                 typename boost::remove_pointer<Ptr>::type>,
0292             Ptr>::type
0293         get() const
0294         {
0295             if (*i == typeid(Ptr))
0296             {
0297                 return static_cast<Ptr>(p);
0298             }
0299             boost::throw_exception(std::bad_cast());
0300         }
0301
0302         template <typename T>
0303         any_ptr(T* p)
0304           : p(p), i(&typeid(T*))
0305         {}
0306
0307         friend bool operator==(any_ptr const& a, any_ptr const& b)
0308         {
0309             return (a.p == b.p) && (*a.i == *b.i);
0310         }
0311
0312     private:
0313         // constructor is private
0314         any_ptr(void* p, std::type_info const* i)
0315           : p(p), i(i) {}
0316
0317         template <typename UTreeX, typename UTreeY>
0318         friend struct detail::visit_impl;
0319
0320         friend class utree;
0321
0322         void* p;
0323         std::type_info const* i;
0324     };
0325
0326     //[utree
0327     class utree {
0328     public:
0329         ///////////////////////////////////////////////////////////////////////
0330         // The invalid type
0331         struct invalid_type {};
0332
0333         ///////////////////////////////////////////////////////////////////////
0334         // The nil type
0335         struct nil_type {};
0336
0337         ///////////////////////////////////////////////////////////////////////
0338         // The list type, this can be used to initialize an utree to hold an
0339         // empty list
0340         struct list_type;
0341
0342         //[utree_container_types
0343         typedef utree value_type;
0344         typedef utree& reference;
0345         typedef utree const& const_reference;
0346         typedef std::ptrdiff_t difference_type;
0347         typedef std::size_t size_type;
0348
0349         typedef detail::list::node_iterator<utree> iterator;
0350         typedef detail::list::node_iterator<utree const> const_iterator;
0351         //]
0352
0353         typedef detail::list::node_iterator<boost::reference_wrapper<utree> >
0354           ref_iterator;
0355
0356         typedef boost::iterator_range<iterator> range;
0357         typedef boost::iterator_range<const_iterator> const_range;
0358
0359         // dtor
0360         ~utree();
0361
0362         ////////////////////////////////////////////////////////////////////////
0363         //[utree_initialization
0364         /*`A `utree` can be constructed or initialized from a wide range of
0365            data types, allowing to create `utree` instances for every
0366            possible node type (see the description of `utree_type::info` above).
0367            For this reason it exposes a constructor and an assignment operator
0368            for each of the allowed node types as shown below. All constructors
0369            are non-explicit on purpose, allowing to use an utree instance as
0370            the attribute to almost any Qi parser.
0371         */
0372         // This constructs an `invalid_type` node. When used in places
0373         // where a boost::optional is expected (i.e. as an attribute for the
0374         // optional component), this represents the 'empty' state.
0375         utree(invalid_type = invalid_type());
0376
0377         // This initializes a `nil_type` node, which represents a valid,
0378         // 'initialized empty' utree (different from invalid_type!).
0379         utree(nil_type);
0380         reference operator=(nil_type);
0381
0382         // This initializes a `boolean_type` node, which can hold 'true' or
0383         // 'false' only.
0384         explicit utree(bool);
0385         reference operator=(bool);
0386
0387         // This initializes an `integer_type` node, which can hold arbitrary
0388         // integers. For convenience these functions are overloaded for signed
0389         // and unsigned integer types.
0390         utree(unsigned int);
0391         utree(int);
0392         reference operator=(unsigned int);
0393         reference operator=(int);
0394
0395         // This initializes a `double_type` node, which can hold arbitrary
0396         // floating point (double) values.
0397         utree(double);
0398         reference operator=(double);
0399
0400         // This initializes a `string_type` node, which can hold a narrow
0401         // character sequence (usually an UTF-8 string).
0402         utree(char);
0403         utree(char const*);
0404         utree(char const*, std::size_t);
0405         utree(std::string const&);
0406         reference operator=(char);
0407         reference operator=(char const*);
0408         reference operator=(std::string const&);
0409
0410         // This constructs a `string_range_type` node, which does not copy the
0411         // data but stores the iterator range to the character sequence the
0412         // range has been initialized from.
0413         utree(utf8_string_range_type const&, shallow_tag);
0414
0415         // This initializes a `reference_type` node, which holds a reference to
0416         // another utree node. All operations on such a node are automatically
0417         // forwarded to the referenced utree instance.
0418         utree(boost::reference_wrapper<utree>);
0419         reference operator=(boost::reference_wrapper<utree>);
0420
0421         // This initializes an `any_type` node, which can hold a pointer to an
0422         // instance of any type together with the typeid of that type. When
0423         // accessing that pointer the typeid will be checked, causing a
0424         // std::bad_cast to be thrown if the typeids do not match.
0425         utree(any_ptr const&);
0426         reference operator=(any_ptr const&);
0427
0428         // This initializes a `range_type` node, which holds an utree list node
0429         // the elements of which are copy constructed (assigned) from the
0430         // elements referenced by the given range of iterators.
0431         template <class Iterator>
0432         utree(boost::iterator_range<Iterator>);
0433         template <class Iterator>
0434         reference operator=(boost::iterator_range<Iterator>);
0435
0436         // This initializes a `function_type` node from a polymorphic function
0437         // object pointer (takes ownership) or reference.
0438         utree(function_base const&);
0439         reference operator=(function_base const&);
0440         utree(function_base*);
0441         reference operator=(function_base*);
0442
0443         // This initializes either a `string_type`, a `symbol_type`, or a
0444         // `binary_type` node (depending on the template parameter `type_`),
0445         // which will hold the corresponding narrow character sequence (usually
0446         // an UTF-8 string).
0447         template <class Base, utree_type::info type_>
0448         utree(basic_string<Base, type_> const&);
0449         template <class Base, utree_type::info type_>
0450         reference operator=(basic_string<Base, type_> const&);
0451         //]
0452
0453         // copy
0454         utree(const_reference);
0455         reference operator=(const_reference);
0456
0457         // range
0458         utree(range, shallow_tag);
0459         utree(const_range, shallow_tag);
0460
0461         // assign dispatch
0462         template <class Iterator>
0463         void assign(Iterator, Iterator);
0464
0465         ////////////////////////////////////////////////////////////////////////
0466
0467         ////////////////////////////////////////////////////////////////////////
0468         // function object visitation interface
0469
0470         // single dispatch
0471         template <class F>
0472         typename boost::result_of<F(utree const&)>::type
0473         static visit(utree const&, F);
0474
0475         template <class F>
0476         typename boost::result_of<F(utree&)>::type
0477         static visit(utree&, F);
0478
0479         // double dispatch
0480         template <class F>
0481         typename boost::result_of<F(utree const&, utree const&)>::type
0482         static visit(utree const&, utree const&, F);
0483
0484         template <class F>
0485         typename boost::result_of<F(utree&, utree const&)>::type
0486         static visit(utree&, utree const&, F);
0487
0488         template <class F>
0489         typename boost::result_of<F(utree const&, utree&)>::type
0490         static visit(utree const&, utree&, F);
0491
0492         template <class F>
0493         typename boost::result_of<F(utree&, utree&)>::type
0494         static visit(utree&, utree&, F);
0495
0496         ////////////////////////////////////////////////////////////////////////
0497
0498         ///////////////////////////////////////////////////////////////////////
0499         //[utree_container_functions
0500         // STL Container interface
0501
0502         // insertion
0503         template <class T>
0504         void push_back(T const&);
0505         template <class T>
0506         void push_front(T const&);
0507         template <class T>
0508         iterator insert(iterator, T const&);
0509         template <class T>
0510         void insert(iterator, std::size_t, T const&);
0511         template <class Iterator>
0512         void insert(iterator, Iterator, Iterator);
0513
0514         // erasure
0515         void pop_front();
0516         void pop_back();
0517         iterator erase(iterator);
0518         iterator erase(iterator, iterator);
0519
0520         // front access
0521         reference front();
0522         const_reference front() const;
0523         iterator begin();
0524         const_iterator begin() const;
0525         ref_iterator ref_begin();
0526
0527         // back access
0528         reference back();
0529         const_reference back() const;
0530         iterator end();
0531         const_iterator end() const;
0532         ref_iterator ref_end();
0533         //]
0534
0535         // This clears the utree instance and resets its type to `invalid_type`
0536         void clear();
0537
0538         void swap(utree&);
0539
0540         bool empty() const;
0541
0542         size_type size() const;
0543         /*`[warning `size()` has O(n) complexity on `utree` ranges. On utree
0544             lists, it has O(1) complexity.]`*/
0545
0546         ////////////////////////////////////////////////////////////////////////
0547
0548         //[utree_variant_functions
0549         // return the data type (`utree_type::info`) of the currently stored
0550         // data item
0551         utree_type::info which() const;
0552
0553         // access the currently stored data in a type safe manner, this will
0554         // throw a `std::bad_cast()` if the currently stored data item is not
0555         // default convertible to `T`.
0556         template <class T>
0557         T get() const;
0558         //]
0559
0560         reference deref();
0561         const_reference deref() const;
0562
0563         short tag() const;
0564         void tag(short);
0565
0566         utree eval(utree const&) const;
0567         utree eval(utree&) const;
0568
0569         utree operator() (utree const&) const;
0570         utree operator() (utree&) const;
0571     //<-
0572     protected:
0573         void ensure_list_type(char const* failed_in = "ensure_list_type()");
0574
0575     private:
0576         typedef utree_type type;
0577
0578         template <class UTreeX, class UTreeY>
0579         friend struct detail::visit_impl;
0580         friend struct detail::index_impl;
0581
0582         type::info get_type() const;
0583         void set_type(type::info);
0584         void free();
0585         void copy(const_reference);
0586
0587         union {
0588             detail::fast_string s;
0589             detail::list l;
0590             detail::range r;
0591             detail::string_range sr;
0592             detail::void_ptr v;
0593             bool b;
0594             int i;
0595             double d;
0596             utree* p;
0597             function_base* pf;
0598         };
0599     //->
0600     };
0601     //]
0602
0603     //[utree_tuple_interface
0604     /*<-*/inline/*->*/
0605     utree::reference get(utree::reference, utree::size_type);
0606     /*<-*/inline/*->*/
0607     utree::const_reference get(utree::const_reference, utree::size_type);
0608     /*`[warning `get()` has O(n) complexity.]`*/
0609     //]
0610
0611     struct utree::list_type : utree
0612     {
0613         using utree::operator=;
0614
0615         list_type() : utree() { ensure_list_type("list_type()"); }
0616
0617         template <typename T0>
0618         list_type(T0 t0) : utree(t0) {}
0619
0620         template <typename T0, typename T1>
0621         list_type(T0 t0, T1 t1) : utree(t0, t1) {}
0622     };
0623
0624     ///////////////////////////////////////////////////////////////////////////
0625     // predefined instances for singular types
0626     utree::invalid_type const invalid = {};
0627     utree::nil_type const nil = {};
0628     utree::list_type const empty_list = utree::list_type();
0629 }}
0630
0631 #if defined(BOOST_MSVC)
0632   #pragma warning(pop)
0633 #endif
0634
0635 #endif
0636