Chris@16: /*============================================================================= Chris@16: Copyright (c) 2001-2011 Joel de Guzman Chris@16: Copyright (c) 2001-2011 Hartmut Kaiser Chris@16: Copyright (c) 2010-2011 Bryce Lelbach Chris@16: Chris@16: Distributed under the Boost Software License, Version 1.0. (See accompanying Chris@16: file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) Chris@16: =============================================================================*/ Chris@16: #if !defined(BOOST_SPIRIT_UTREE) Chris@16: #define BOOST_SPIRIT_UTREE Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: Chris@16: #if defined(BOOST_MSVC) Chris@16: # pragma warning(push) Chris@16: # pragma warning(disable: 4804) Chris@16: # pragma warning(disable: 4805) Chris@16: # pragma warning(disable: 4244) Chris@16: #endif Chris@16: Chris@16: namespace boost { namespace spirit Chris@16: { Chris@16: //[utree_exceptions Chris@16: /*` All exceptions thrown by utree are derived from utree_exception. */ Chris@16: struct utree_exception : std::exception {}; Chris@16: Chris@16: /*`The `bad_type_exception` is thrown whenever somebody calls a member Chris@16: function, which applies to certain stored utree_type's only, but this Chris@16: precondition is violated as the `utree` instance holds some other type. Chris@16: */ Chris@16: struct bad_type_exception /*: utree_exception*/; Chris@16: Chris@16: /*`The `empty_exception` is thrown whenever a precondition of a list Chris@16: or range utree method is violated due to the list or range being empty. Chris@16: */ Chris@16: struct empty_exception /*: utree_exception*/; Chris@16: //] Chris@16: Chris@16: //[utree_types Chris@16: /*`Each instance of an `utree` data structure can store exactly one of the Chris@16: following data types at a time: Chris@16: */ Chris@16: struct utree_type Chris@16: { Chris@16: enum info Chris@16: { Chris@16: invalid_type, // the utree has not been initialized (it's Chris@16: // default constructed) Chris@16: nil_type, // nil is the sentinel (empty) utree type. Chris@16: list_type, // A doubly linked list of utrees. Chris@16: range_type, // A range of list::iterators. Chris@16: reference_type, // A reference to another utree. Chris@16: any_type, // A pointer or reference to any C++ type. Chris@16: function_type, // A utree holding a stored_function object, Chris@16: // where F is an unary function object taking a Chris@16: // utree as it's parameter and returning a Chris@16: // utree. Chris@16: Chris@16: // numeric atoms Chris@16: bool_type, // An utree holding a boolean value Chris@16: int_type, // An utree holding a integer (int) value Chris@16: double_type, // An utree holding a floating point (double) value Chris@16: Chris@16: // text atoms (utf8) Chris@16: string_type, // An UTF-8 string Chris@16: string_range_type, // A pair of iterators into an UTF-8 string Chris@16: symbol_type, // An UTF-8 symbol name Chris@16: Chris@16: binary_type // Arbitrary binary data Chris@16: }; Chris@16: typedef boost::uint_t::exact exact_integral_type; Chris@16: typedef boost::uint_t::fast fast_integral_type; Chris@16: }; Chris@16: //] Chris@16: Chris@16: // streaming operator for utree types - essential for diagnostics Chris@16: inline std::ostream& operator<<(std::ostream& out, utree_type::info t) Chris@16: { Chris@16: boost::io::ios_all_saver saver(out); Chris@16: switch (t) { Chris@16: case utree_type::invalid_type: { out << "invalid"; break; } Chris@16: case utree_type::nil_type: { out << "nil"; break; } Chris@16: case utree_type::list_type: { out << "list"; break; } Chris@16: case utree_type::range_type: { out << "range"; break; } Chris@16: case utree_type::reference_type: { out << "reference"; break; } Chris@16: case utree_type::any_type: { out << "any"; break; } Chris@16: case utree_type::function_type: { out << "function"; break; } Chris@16: case utree_type::bool_type: { out << "bool"; break; } Chris@16: case utree_type::int_type: { out << "int"; break; } Chris@16: case utree_type::double_type: { out << "double"; break; } Chris@16: case utree_type::string_type: { out << "string"; break; } Chris@16: case utree_type::string_range_type: { out << "string_range"; break; } Chris@16: case utree_type::symbol_type: { out << "symbol"; break; } Chris@16: case utree_type::binary_type: { out << "binary"; break; } Chris@16: default: { out << "unknown"; break; } Chris@16: } Chris@16: out << std::hex << "[0x" Chris@16: << static_cast(t) << "]"; Chris@16: return out; Chris@16: } Chris@16: Chris@16: struct bad_type_exception : utree_exception Chris@16: { Chris@16: std::string msg; Chris@16: Chris@16: bad_type_exception(char const* error, utree_type::info got) Chris@16: : msg() Chris@16: { Chris@16: std::ostringstream oss; Chris@16: oss << "utree: " << error Chris@16: << " (got utree type '" << got << "')"; Chris@16: msg = oss.str(); Chris@16: } Chris@16: Chris@16: bad_type_exception(char const* error, utree_type::info got1, Chris@16: utree_type::info got2) Chris@16: : msg() Chris@16: { Chris@16: std::ostringstream oss; Chris@16: oss << "utree: " << error Chris@16: << " (got utree types '" << got1 << "' and '" << got2 << "')"; Chris@16: msg = oss.str(); Chris@16: } Chris@16: Chris@16: virtual ~bad_type_exception() throw() {} Chris@16: Chris@16: virtual char const* what() const throw() Chris@16: { return msg.c_str(); } Chris@16: }; Chris@16: Chris@16: struct empty_exception : utree_exception Chris@16: { Chris@16: char const* msg; Chris@16: Chris@16: empty_exception(char const* error) : msg(error) {} Chris@16: Chris@16: virtual ~empty_exception() throw() {} Chris@16: Chris@16: virtual char const* what() const throw() Chris@16: { return msg; } Chris@16: }; Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: // A typed string with parametric Base storage. The storage can be any Chris@16: // range or (stl container) of chars. Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: template Chris@16: struct basic_string : Base Chris@16: { Chris@16: static utree_type::info const type = type_; Chris@16: Chris@16: basic_string() Chris@16: : Base() {} Chris@16: Chris@16: basic_string(Base const& base) Chris@16: : Base(base) {} Chris@16: Chris@16: template Chris@16: basic_string(Iterator bits, std::size_t len) Chris@16: : Base(bits, bits + len) {} Chris@16: Chris@16: template Chris@16: basic_string(Iterator first, Iterator last) Chris@16: : Base(first, last) {} Chris@16: Chris@16: basic_string& operator=(basic_string const& other) Chris@16: { Chris@16: Base::operator=(other); Chris@16: return *this; Chris@16: } Chris@16: Chris@16: basic_string& operator=(Base const& other) Chris@16: { Chris@16: Base::operator=(other); Chris@16: return *this; Chris@16: } Chris@16: }; Chris@16: Chris@16: //[utree_strings Chris@16: /*`The `utree` string types described below are used by the `utree` API Chris@16: only. These are not used to store information in the `utree` itself. Chris@16: Their purpose is to refer to different internal `utree` node types Chris@16: only. For instance, creating a `utree` from a binary data type will Chris@16: create a `binary_type` utree node (see above). Chris@16: */ Chris@16: /*`The binary data type can be represented either verbatim as a sequence Chris@16: of bytes or as a pair of iterators into some other stored binary data Chris@16: sequence. Use this string type to access/create a `binary_type` `utree`. Chris@16: */ Chris@16: typedef basic_string< Chris@16: boost::iterator_range, utree_type::binary_type Chris@16: > binary_range_type; Chris@16: typedef basic_string< Chris@16: std::string, utree_type::binary_type Chris@16: > binary_string_type; Chris@16: Chris@16: /*`The UTF-8 string can be represented either verbatim as a sequence of Chris@16: characters or as a pair of iterators into some other stored binary data Chris@16: sequence. Use this string type to access/create a `string_type` `utree`. Chris@16: */ Chris@16: typedef basic_string< Chris@16: boost::iterator_range, utree_type::string_type Chris@16: > utf8_string_range_type; Chris@16: typedef basic_string< Chris@16: std::string, utree_type::string_type Chris@16: > utf8_string_type; Chris@16: Chris@16: /*`The UTF-8 symbol can be represented either verbatim as a sequence of Chris@16: characters or as a pair of iterators into some other stored binary data Chris@16: sequence. Use this string type to access/create a `symbol_type` `utree`. Chris@16: */ Chris@16: typedef basic_string< Chris@16: boost::iterator_range, utree_type::symbol_type Chris@16: > utf8_symbol_range_type; Chris@16: typedef basic_string< Chris@16: std::string, utree_type::symbol_type Chris@16: > utf8_symbol_type; Chris@16: //] Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: // Our function type Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: class utree; Chris@16: Chris@16: //[utree_function_object_interface Chris@16: struct function_base Chris@16: { Chris@16: virtual ~function_base() {} Chris@16: virtual utree operator()(utree const& env) const = 0; Chris@16: virtual utree operator()(utree& env) const = 0; Chris@16: Chris@16: // Calling f.clone() must return a newly allocated function_base Chris@16: // instance that is equal to f. Chris@16: virtual function_base* clone() const = 0; Chris@16: }; Chris@16: Chris@16: template Chris@16: struct stored_function : function_base Chris@16: { Chris@16: F f; Chris@16: stored_function(F f = F()); Chris@16: virtual ~stored_function(); Chris@16: virtual utree operator()(utree const& env) const; Chris@16: virtual utree operator()(utree& env) const; Chris@16: virtual function_base* clone() const; Chris@16: }; Chris@16: Chris@16: template Chris@16: struct referenced_function : function_base Chris@16: { Chris@16: F& f; Chris@16: referenced_function(F& f); Chris@16: virtual ~referenced_function(); Chris@16: virtual utree operator()(utree const& env) const; Chris@16: virtual utree operator()(utree& env) const; Chris@16: virtual function_base* clone() const; Chris@16: }; Chris@16: //] Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: // Shallow tag. Instructs utree to hold an iterator_range Chris@16: // as-is without deep copying the range. Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: struct shallow_tag {}; Chris@16: shallow_tag const shallow = {}; Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: // A void* plus type_info Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: class any_ptr Chris@16: { Chris@16: public: Chris@16: template Chris@16: typename boost::disable_if< Chris@16: boost::is_polymorphic< Chris@16: typename boost::remove_pointer::type>, Chris@16: Ptr>::type Chris@16: get() const Chris@16: { Chris@16: if (*i == typeid(Ptr)) Chris@16: { Chris@16: return static_cast(p); Chris@16: } Chris@16: boost::throw_exception(std::bad_cast()); Chris@16: } Chris@16: Chris@16: template Chris@16: any_ptr(T* p) Chris@16: : p(p), i(&typeid(T*)) Chris@16: {} Chris@16: Chris@16: friend bool operator==(any_ptr const& a, any_ptr const& b) Chris@16: { Chris@16: return (a.p == b.p) && (*a.i == *b.i); Chris@16: } Chris@16: Chris@16: private: Chris@16: // constructor is private Chris@16: any_ptr(void* p, std::type_info const* i) Chris@16: : p(p), i(i) {} Chris@16: Chris@16: template Chris@16: friend struct detail::visit_impl; Chris@16: Chris@16: friend class utree; Chris@16: Chris@16: void* p; Chris@16: std::type_info const* i; Chris@16: }; Chris@16: Chris@16: //[utree Chris@16: class utree { Chris@16: public: Chris@16: /////////////////////////////////////////////////////////////////////// Chris@16: // The invalid type Chris@16: struct invalid_type {}; Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////// Chris@16: // The nil type Chris@16: struct nil_type {}; Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////// Chris@16: // The list type, this can be used to initialize an utree to hold an Chris@16: // empty list Chris@16: struct list_type; Chris@16: Chris@16: //[utree_container_types Chris@16: typedef utree value_type; Chris@16: typedef utree& reference; Chris@16: typedef utree const& const_reference; Chris@16: typedef std::ptrdiff_t difference_type; Chris@16: typedef std::size_t size_type; Chris@16: Chris@16: typedef detail::list::node_iterator iterator; Chris@16: typedef detail::list::node_iterator const_iterator; Chris@16: //] Chris@16: Chris@16: typedef detail::list::node_iterator > Chris@16: ref_iterator; Chris@16: Chris@16: typedef boost::iterator_range range; Chris@16: typedef boost::iterator_range const_range; Chris@16: Chris@16: // dtor Chris@16: ~utree(); Chris@16: Chris@16: //////////////////////////////////////////////////////////////////////// Chris@16: //[utree_initialization Chris@16: /*`A `utree` can be constructed or initialized from a wide range of Chris@16: data types, allowing to create `utree` instances for every Chris@16: possible node type (see the description of `utree_type::info` above). Chris@16: For this reason it exposes a constructor and an assignment operator Chris@16: for each of the allowed node types as shown below. All constructors Chris@16: are non-explicit on purpose, allowing to use an utree instance as Chris@16: the attribute to almost any Qi parser. Chris@16: */ Chris@16: // This constructs an `invalid_type` node. When used in places Chris@16: // where a boost::optional is expected (i.e. as an attribute for the Chris@16: // optional component), this represents the 'empty' state. Chris@16: utree(invalid_type = invalid_type()); Chris@16: Chris@16: // This initializes a `nil_type` node, which represents a valid, Chris@16: // 'initialized empty' utree (different from invalid_type!). Chris@16: utree(nil_type); Chris@16: reference operator=(nil_type); Chris@16: Chris@16: // This initializes a `boolean_type` node, which can hold 'true' or Chris@16: // 'false' only. Chris@16: explicit utree(bool); Chris@16: reference operator=(bool); Chris@16: Chris@16: // This initializes an `integer_type` node, which can hold arbitrary Chris@16: // integers. For convenience these functions are overloaded for signed Chris@16: // and unsigned integer types. Chris@16: utree(unsigned int); Chris@16: utree(int); Chris@16: reference operator=(unsigned int); Chris@16: reference operator=(int); Chris@16: Chris@16: // This initializes a `double_type` node, which can hold arbitrary Chris@16: // floating point (double) values. Chris@16: utree(double); Chris@16: reference operator=(double); Chris@16: Chris@16: // This initializes a `string_type` node, which can hold a narrow Chris@16: // character sequence (usually an UTF-8 string). Chris@16: utree(char); Chris@16: utree(char const*); Chris@16: utree(char const*, std::size_t); Chris@16: utree(std::string const&); Chris@16: reference operator=(char); Chris@16: reference operator=(char const*); Chris@16: reference operator=(std::string const&); Chris@16: Chris@16: // This constructs a `string_range_type` node, which does not copy the Chris@16: // data but stores the iterator range to the character sequence the Chris@16: // range has been initialized from. Chris@16: utree(utf8_string_range_type const&, shallow_tag); Chris@16: Chris@16: // This initializes a `reference_type` node, which holds a reference to Chris@16: // another utree node. All operations on such a node are automatically Chris@16: // forwarded to the referenced utree instance. Chris@16: utree(boost::reference_wrapper); Chris@16: reference operator=(boost::reference_wrapper); Chris@16: Chris@16: // This initializes an `any_type` node, which can hold a pointer to an Chris@16: // instance of any type together with the typeid of that type. When Chris@16: // accessing that pointer the typeid will be checked, causing a Chris@16: // std::bad_cast to be thrown if the typeids do not match. Chris@16: utree(any_ptr const&); Chris@16: reference operator=(any_ptr const&); Chris@16: Chris@16: // This initializes a `range_type` node, which holds an utree list node Chris@16: // the elements of which are copy constructed (assigned) from the Chris@16: // elements referenced by the given range of iterators. Chris@16: template Chris@16: utree(boost::iterator_range); Chris@16: template Chris@16: reference operator=(boost::iterator_range); Chris@16: Chris@16: // This initializes a `function_type` node from a polymorphic function Chris@16: // object pointer (takes ownership) or reference. Chris@16: utree(function_base const&); Chris@16: reference operator=(function_base const&); Chris@16: utree(function_base*); Chris@16: reference operator=(function_base*); Chris@16: Chris@16: // This initializes either a `string_type`, a `symbol_type`, or a Chris@16: // `binary_type` node (depending on the template parameter `type_`), Chris@16: // which will hold the corresponding narrow character sequence (usually Chris@16: // an UTF-8 string). Chris@16: template Chris@16: utree(basic_string const&); Chris@16: template Chris@16: reference operator=(basic_string const&); Chris@16: //] Chris@16: Chris@16: // copy Chris@16: utree(const_reference); Chris@16: reference operator=(const_reference); Chris@16: Chris@16: // range Chris@16: utree(range, shallow_tag); Chris@16: utree(const_range, shallow_tag); Chris@16: Chris@16: // assign dispatch Chris@16: template Chris@16: void assign(Iterator, Iterator); Chris@16: Chris@16: //////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: //////////////////////////////////////////////////////////////////////// Chris@16: // function object visitation interface Chris@16: Chris@16: // single dispatch Chris@16: template Chris@16: typename boost::result_of::type Chris@16: static visit(utree const&, F); Chris@16: Chris@16: template Chris@16: typename boost::result_of::type Chris@16: static visit(utree&, F); Chris@16: Chris@16: // double dispatch Chris@16: template Chris@16: typename boost::result_of::type Chris@16: static visit(utree const&, utree const&, F); Chris@16: Chris@16: template Chris@16: typename boost::result_of::type Chris@16: static visit(utree&, utree const&, F); Chris@16: Chris@16: template Chris@16: typename boost::result_of::type Chris@16: static visit(utree const&, utree&, F); Chris@16: Chris@16: template Chris@16: typename boost::result_of::type Chris@16: static visit(utree&, utree&, F); Chris@16: Chris@16: //////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////// Chris@16: //[utree_container_functions Chris@16: // STL Container interface Chris@16: Chris@16: // insertion Chris@16: template Chris@16: void push_back(T const&); Chris@16: template Chris@16: void push_front(T const&); Chris@16: template Chris@16: iterator insert(iterator, T const&); Chris@16: template Chris@16: void insert(iterator, std::size_t, T const&); Chris@16: template Chris@16: void insert(iterator, Iterator, Iterator); Chris@16: Chris@16: // erasure Chris@16: void pop_front(); Chris@16: void pop_back(); Chris@16: iterator erase(iterator); Chris@16: iterator erase(iterator, iterator); Chris@16: Chris@16: // front access Chris@16: reference front(); Chris@16: const_reference front() const; Chris@16: iterator begin(); Chris@16: const_iterator begin() const; Chris@16: ref_iterator ref_begin(); Chris@16: Chris@16: // back access Chris@16: reference back(); Chris@16: const_reference back() const; Chris@16: iterator end(); Chris@16: const_iterator end() const; Chris@16: ref_iterator ref_end(); Chris@16: //] Chris@16: Chris@16: // This clears the utree instance and resets its type to `invalid_type` Chris@16: void clear(); Chris@16: Chris@16: void swap(utree&); Chris@16: Chris@16: bool empty() const; Chris@16: Chris@16: size_type size() const; Chris@16: /*`[warning `size()` has O(n) complexity on `utree` ranges. On utree Chris@16: lists, it has O(1) complexity.]`*/ Chris@16: Chris@16: //////////////////////////////////////////////////////////////////////// Chris@16: Chris@16: //[utree_variant_functions Chris@16: // return the data type (`utree_type::info`) of the currently stored Chris@16: // data item Chris@16: utree_type::info which() const; Chris@16: Chris@16: // access the currently stored data in a type safe manner, this will Chris@16: // throw a `std::bad_cast()` if the currently stored data item is not Chris@16: // default convertible to `T`. Chris@16: template Chris@16: T get() const; Chris@16: //] Chris@16: Chris@16: reference deref(); Chris@16: const_reference deref() const; Chris@16: Chris@16: short tag() const; Chris@16: void tag(short); Chris@16: Chris@16: utree eval(utree const&) const; Chris@16: utree eval(utree&) const; Chris@16: Chris@16: utree operator() (utree const&) const; Chris@16: utree operator() (utree&) const; Chris@16: //<- Chris@16: protected: Chris@16: void ensure_list_type(char const* failed_in = "ensure_list_type()"); Chris@16: Chris@16: private: Chris@16: typedef utree_type type; Chris@16: Chris@16: template Chris@16: friend struct detail::visit_impl; Chris@16: friend struct detail::index_impl; Chris@16: Chris@16: type::info get_type() const; Chris@16: void set_type(type::info); Chris@16: void free(); Chris@16: void copy(const_reference); Chris@16: Chris@16: union { Chris@16: detail::fast_string s; Chris@16: detail::list l; Chris@16: detail::range r; Chris@16: detail::string_range sr; Chris@16: detail::void_ptr v; Chris@16: bool b; Chris@16: int i; Chris@16: double d; Chris@16: utree* p; Chris@16: function_base* pf; Chris@16: }; Chris@16: //-> Chris@16: }; Chris@16: //] Chris@16: Chris@16: //[utree_tuple_interface Chris@16: /*<-*/inline/*->*/ Chris@16: utree::reference get(utree::reference, utree::size_type); Chris@16: /*<-*/inline/*->*/ Chris@16: utree::const_reference get(utree::const_reference, utree::size_type); Chris@16: /*`[warning `get()` has O(n) complexity.]`*/ Chris@16: //] Chris@16: Chris@16: struct utree::list_type : utree Chris@16: { Chris@16: using utree::operator=; Chris@16: Chris@16: list_type() : utree() { ensure_list_type("list_type()"); } Chris@16: Chris@16: template Chris@16: list_type(T0 t0) : utree(t0) {} Chris@16: Chris@16: template Chris@16: list_type(T0 t0, T1 t1) : utree(t0, t1) {} Chris@16: }; Chris@16: Chris@16: /////////////////////////////////////////////////////////////////////////// Chris@16: // predefined instances for singular types Chris@16: utree::invalid_type const invalid = {}; Chris@16: utree::nil_type const nil = {}; Chris@16: utree::list_type const empty_list = utree::list_type(); Chris@16: }} Chris@16: Chris@16: #if defined(BOOST_MSVC) Chris@16: #pragma warning(pop) Chris@16: #endif Chris@16: Chris@16: #endif Chris@16: