/*=============================================================================
    Copyright (c) 2001-2011 Joel de Guzman
    Copyright (c) 2001-2011 Hartmut Kaiser
    Copyright (c) 2010-2011 Bryce Lelbach

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#if !defined(BOOST_SPIRIT_UTREE)
#define BOOST_SPIRIT_UTREE

#include <cstddef>
#include <algorithm>
#include <string>
#include <iostream>
#include <ios>
#include <sstream>
#include <typeinfo>

#include <boost/io/ios_state.hpp>
#include <boost/integer.hpp>
#include <boost/throw_exception.hpp>
#include <boost/assert.hpp>
#include <boost/noncopyable.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/type_traits/remove_pointer.hpp>
#include <boost/type_traits/is_polymorphic.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/utility/result_of.hpp>
#include <boost/ref.hpp>

#include <boost/spirit/home/support/utree/detail/utree_detail1.hpp>

#if defined(BOOST_MSVC)
# pragma warning(push)
# pragma warning(disable: 4804)
# pragma warning(disable: 4805)
# pragma warning(disable: 4244)
#endif

namespace boost { namespace spirit
{
    //[utree_exceptions
    /*` All exceptions thrown by utree are derived from utree_exception. */
    struct utree_exception : std::exception {};

    /*`The `bad_type_exception` is thrown whenever somebody calls a member 
       function, which applies to certain stored utree_type's only, but this 
       precondition is violated as the `utree` instance holds some other type.
    */
    struct bad_type_exception /*: utree_exception*/;

    /*`The `empty_exception` is thrown whenever a precondition of a list
       or range utree method is violated due to the list or range being empty. 
    */
    struct empty_exception /*: utree_exception*/;
    //]

    //[utree_types
    /*`Each instance of an `utree` data structure can store exactly one of the 
       following data types at a time: 
    */
    struct utree_type
    {
        enum info
        {
            invalid_type,       // the utree has not been initialized (it's 
                                // default constructed)
            nil_type,           // nil is the sentinel (empty) utree type.
            list_type,          // A doubly linked list of utrees.
            range_type,         // A range of list::iterators. 
            reference_type,     // A reference to another utree.
            any_type,           // A pointer or reference to any C++ type. 
            function_type,      // A utree holding a stored_function<F> object,
                                // where F is an unary function object taking a 
                                // utree as it's parameter and returning a
                                // utree.

            // numeric atoms
            bool_type,          // An utree holding a boolean value
            int_type,           // An utree holding a integer (int) value
            double_type,        // An utree holding a floating point (double) value

            // text atoms (utf8)
            string_type,        // An UTF-8 string 
            string_range_type,  // A pair of iterators into an UTF-8 string
            symbol_type,        // An UTF-8 symbol name

            binary_type         // Arbitrary binary data
        };
        typedef boost::uint_t<sizeof(info)*8>::exact exact_integral_type; 
        typedef boost::uint_t<sizeof(info)*8>::fast fast_integral_type; 
    };
    //]

    // streaming operator for utree types - essential for diagnostics    
    inline std::ostream& operator<<(std::ostream& out, utree_type::info t)
    {
        boost::io::ios_all_saver saver(out);
        switch (t) {
            case utree_type::invalid_type: { out << "invalid"; break; }
            case utree_type::nil_type: { out << "nil"; break; }
            case utree_type::list_type: { out << "list"; break; }
            case utree_type::range_type: { out << "range"; break; }
            case utree_type::reference_type: { out << "reference"; break; }
            case utree_type::any_type: { out << "any"; break; }
            case utree_type::function_type: { out << "function"; break; }
            case utree_type::bool_type: { out << "bool"; break; }
            case utree_type::int_type: { out << "int"; break; }
            case utree_type::double_type: { out << "double"; break; }
            case utree_type::string_type: { out << "string"; break; }
            case utree_type::string_range_type: { out << "string_range"; break; }
            case utree_type::symbol_type: { out << "symbol"; break; }
            case utree_type::binary_type: { out << "binary"; break; }
            default: { out << "unknown"; break; }
        }
        out << std::hex << "[0x"
            << static_cast<utree_type::fast_integral_type>(t) << "]";
        return out;
    }
    
    struct bad_type_exception : utree_exception
    {
        std::string msg;

        bad_type_exception(char const* error, utree_type::info got)
          : msg()
        {
            std::ostringstream oss;
            oss << "utree: " << error
                << " (got utree type '" << got << "')";
            msg = oss.str();
        }
        
        bad_type_exception(char const* error, utree_type::info got1,
                           utree_type::info got2)
          : msg()
        {
            std::ostringstream oss;
            oss << "utree: " << error
                << " (got utree types '" << got1 << "' and '" << got2 << "')";
            msg = oss.str();
        }

        virtual ~bad_type_exception() throw() {}

        virtual char const* what() const throw()
        { return msg.c_str(); }
    };
    
    struct empty_exception : utree_exception
    {
        char const* msg;

        empty_exception(char const* error) : msg(error) {}
        
        virtual ~empty_exception() throw() {}

        virtual char const* what() const throw()
        { return msg; }
    };

    ///////////////////////////////////////////////////////////////////////////
    // A typed string with parametric Base storage. The storage can be any
    // range or (stl container) of chars.
    ///////////////////////////////////////////////////////////////////////////
    template <typename Base, utree_type::info type_>
    struct basic_string : Base
    {
        static utree_type::info const type = type_;

        basic_string()
          : Base() {}

        basic_string(Base const& base)
          : Base(base) {}

        template <typename Iterator>
        basic_string(Iterator bits, std::size_t len)
          : Base(bits, bits + len) {}

        template <typename Iterator>
        basic_string(Iterator first, Iterator last)
          : Base(first, last) {}

        basic_string& operator=(basic_string const& other)
        {
            Base::operator=(other);
            return *this;
        }

        basic_string& operator=(Base const& other)
        {
            Base::operator=(other);
            return *this;
        }
    };

    //[utree_strings
    /*`The `utree` string types described below are used by the `utree` API 
       only. These are not used to store information in the `utree` itself.
       Their purpose is to refer to different internal `utree` node types
       only. For instance, creating a `utree` from a binary data type will 
       create a `binary_type` utree node (see above).
    */
    /*`The binary data type can be represented either verbatim as a sequence 
       of bytes or as a pair of iterators into some other stored binary data 
       sequence. Use this string type to access/create a `binary_type` `utree`.
    */
    typedef basic_string<
        boost::iterator_range<char const*>, utree_type::binary_type
    > binary_range_type;
    typedef basic_string<
        std::string, utree_type::binary_type
    > binary_string_type;

    /*`The UTF-8 string can be represented either verbatim as a sequence of 
       characters or as a pair of iterators into some other stored binary data 
       sequence. Use this string type to access/create a `string_type` `utree`.
    */
    typedef basic_string<
        boost::iterator_range<char const*>, utree_type::string_type
    > utf8_string_range_type;
    typedef basic_string<
        std::string, utree_type::string_type
    > utf8_string_type;

    /*`The UTF-8 symbol can be represented either verbatim as a sequence of 
       characters or as a pair of iterators into some other stored binary data 
       sequence. Use this string type to access/create a `symbol_type` `utree`.
    */
    typedef basic_string<
        boost::iterator_range<char const*>, utree_type::symbol_type
    > utf8_symbol_range_type;
    typedef basic_string<
        std::string, utree_type::symbol_type
    > utf8_symbol_type;
    //]

    ///////////////////////////////////////////////////////////////////////////
    // Our function type
    ///////////////////////////////////////////////////////////////////////////
    class utree;

    //[utree_function_object_interface
    struct function_base
    {
        virtual ~function_base() {}
        virtual utree operator()(utree const& env) const = 0;
        virtual utree operator()(utree& env) const = 0;

        // Calling f.clone() must return a newly allocated function_base 
        // instance that is equal to f.
        virtual function_base* clone() const = 0; 
    };

    template <typename F>
    struct stored_function : function_base
    {
        F f;
        stored_function(F f = F());
        virtual ~stored_function();
        virtual utree operator()(utree const& env) const;
        virtual utree operator()(utree& env) const;
        virtual function_base* clone() const;
    };
    
    template <typename F>
    struct referenced_function : function_base
    {
        F& f;
        referenced_function(F& f);
        virtual ~referenced_function();
        virtual utree operator()(utree const& env) const;
        virtual utree operator()(utree& env) const;
        virtual function_base* clone() const;
    };
    //]

    ///////////////////////////////////////////////////////////////////////////
    // Shallow tag. Instructs utree to hold an iterator_range
    // as-is without deep copying the range.
    ///////////////////////////////////////////////////////////////////////////
    struct shallow_tag {};
    shallow_tag const shallow = {};

    ///////////////////////////////////////////////////////////////////////////
    // A void* plus type_info
    ///////////////////////////////////////////////////////////////////////////
    class any_ptr
    {
    public:
        template <typename Ptr>
        typename boost::disable_if<
            boost::is_polymorphic<
                typename boost::remove_pointer<Ptr>::type>,
            Ptr>::type
        get() const
        {
            if (*i == typeid(Ptr))
            {
                return static_cast<Ptr>(p);
            }
            boost::throw_exception(std::bad_cast());
        }

        template <typename T>
        any_ptr(T* p)
          : p(p), i(&typeid(T*))
        {}

        friend bool operator==(any_ptr const& a, any_ptr const& b)
        {
            return (a.p == b.p) && (*a.i == *b.i);
        }

    private:
        // constructor is private
        any_ptr(void* p, std::type_info const* i)
          : p(p), i(i) {}

        template <typename UTreeX, typename UTreeY>
        friend struct detail::visit_impl;

        friend class utree;

        void* p;
        std::type_info const* i;
    };

    //[utree
    class utree {
    public:
        ///////////////////////////////////////////////////////////////////////
        // The invalid type
        struct invalid_type {};

        ///////////////////////////////////////////////////////////////////////
        // The nil type
        struct nil_type {};

        ///////////////////////////////////////////////////////////////////////
        // The list type, this can be used to initialize an utree to hold an 
        // empty list
        struct list_type;

        //[utree_container_types
        typedef utree value_type;
        typedef utree& reference;
        typedef utree const& const_reference;
        typedef std::ptrdiff_t difference_type;
        typedef std::size_t size_type;

        typedef detail::list::node_iterator<utree> iterator;
        typedef detail::list::node_iterator<utree const> const_iterator;
        //]

        typedef detail::list::node_iterator<boost::reference_wrapper<utree> >
          ref_iterator;

        typedef boost::iterator_range<iterator> range;
        typedef boost::iterator_range<const_iterator> const_range;

        // dtor
        ~utree();

        ////////////////////////////////////////////////////////////////////////
        //[utree_initialization
        /*`A `utree` can be constructed or initialized from a wide range of 
           data types, allowing to create `utree` instances for every 
           possible node type (see the description of `utree_type::info` above). 
           For this reason it exposes a constructor and an assignment operator 
           for each of the allowed node types as shown below. All constructors
           are non-explicit on purpose, allowing to use an utree instance as
           the attribute to almost any Qi parser.
        */
        // This constructs an `invalid_type` node. When used in places
        // where a boost::optional is expected (i.e. as an attribute for the 
        // optional component), this represents the 'empty' state.
        utree(invalid_type = invalid_type());

        // This initializes a `nil_type` node, which represents a valid,
        // 'initialized empty' utree (different from invalid_type!).
        utree(nil_type);
        reference operator=(nil_type);

        // This initializes a `boolean_type` node, which can hold 'true' or
        // 'false' only.
        explicit utree(bool);
        reference operator=(bool);

        // This initializes an `integer_type` node, which can hold arbitrary 
        // integers. For convenience these functions are overloaded for signed
        // and unsigned integer types.
        utree(unsigned int);
        utree(int);
        reference operator=(unsigned int);
        reference operator=(int);

        // This initializes a `double_type` node, which can hold arbitrary 
        // floating point (double) values.
        utree(double);
        reference operator=(double);

        // This initializes a `string_type` node, which can hold a narrow 
        // character sequence (usually an UTF-8 string).
        utree(char);
        utree(char const*);
        utree(char const*, std::size_t);
        utree(std::string const&);
        reference operator=(char);
        reference operator=(char const*);
        reference operator=(std::string const&);

        // This constructs a `string_range_type` node, which does not copy the 
        // data but stores the iterator range to the character sequence the 
        // range has been initialized from.
        utree(utf8_string_range_type const&, shallow_tag);

        // This initializes a `reference_type` node, which holds a reference to 
        // another utree node. All operations on such a node are automatically
        // forwarded to the referenced utree instance.
        utree(boost::reference_wrapper<utree>);
        reference operator=(boost::reference_wrapper<utree>);

        // This initializes an `any_type` node, which can hold a pointer to an
        // instance of any type together with the typeid of that type. When 
        // accessing that pointer the typeid will be checked, causing a 
        // std::bad_cast to be thrown if the typeids do not match.
        utree(any_ptr const&);
        reference operator=(any_ptr const&);

        // This initializes a `range_type` node, which holds an utree list node
        // the elements of which are copy constructed (assigned) from the 
        // elements referenced by the given range of iterators.
        template <class Iterator>
        utree(boost::iterator_range<Iterator>);
        template <class Iterator>
        reference operator=(boost::iterator_range<Iterator>);
        
        // This initializes a `function_type` node from a polymorphic function
        // object pointer (takes ownership) or reference. 
        utree(function_base const&);
        reference operator=(function_base const&);
        utree(function_base*);
        reference operator=(function_base*);

        // This initializes either a `string_type`, a `symbol_type`, or a 
        // `binary_type` node (depending on the template parameter `type_`), 
        // which will hold the corresponding narrow character sequence (usually 
        // an UTF-8 string).
        template <class Base, utree_type::info type_>
        utree(basic_string<Base, type_> const&);
        template <class Base, utree_type::info type_>
        reference operator=(basic_string<Base, type_> const&);
        //]

        // copy 
        utree(const_reference);
        reference operator=(const_reference);

        // range
        utree(range, shallow_tag);
        utree(const_range, shallow_tag);

        // assign dispatch
        template <class Iterator>
        void assign(Iterator, Iterator);

        ////////////////////////////////////////////////////////////////////////

        ////////////////////////////////////////////////////////////////////////
        // function object visitation interface

        // single dispatch
        template <class F>
        typename boost::result_of<F(utree const&)>::type
        static visit(utree const&, F);

        template <class F>
        typename boost::result_of<F(utree&)>::type
        static visit(utree&, F);

        // double dispatch
        template <class F>
        typename boost::result_of<F(utree const&, utree const&)>::type
        static visit(utree const&, utree const&, F);

        template <class F>
        typename boost::result_of<F(utree&, utree const&)>::type
        static visit(utree&, utree const&, F);

        template <class F>
        typename boost::result_of<F(utree const&, utree&)>::type
        static visit(utree const&, utree&, F);

        template <class F>
        typename boost::result_of<F(utree&, utree&)>::type
        static visit(utree&, utree&, F);

        ////////////////////////////////////////////////////////////////////////

        ///////////////////////////////////////////////////////////////////////
        //[utree_container_functions
        // STL Container interface

        // insertion 
        template <class T>
        void push_back(T const&);
        template <class T>
        void push_front(T const&);
        template <class T>
        iterator insert(iterator, T const&);
        template <class T>
        void insert(iterator, std::size_t, T const&);
        template <class Iterator>
        void insert(iterator, Iterator, Iterator);

        // erasure
        void pop_front();
        void pop_back();
        iterator erase(iterator);
        iterator erase(iterator, iterator);

        // front access
        reference front();
        const_reference front() const;
        iterator begin();
        const_iterator begin() const;
        ref_iterator ref_begin();

        // back access
        reference back();
        const_reference back() const;
        iterator end();
        const_iterator end() const;
        ref_iterator ref_end();
        //]

        // This clears the utree instance and resets its type to `invalid_type`
        void clear();

        void swap(utree&);
 
        bool empty() const;

        size_type size() const;
        /*`[warning `size()` has O(n) complexity on `utree` ranges. On utree
            lists, it has O(1) complexity.]`*/

        ////////////////////////////////////////////////////////////////////////

        //[utree_variant_functions
        // return the data type (`utree_type::info`) of the currently stored 
        // data item
        utree_type::info which() const;

        // access the currently stored data in a type safe manner, this will 
        // throw a `std::bad_cast()` if the currently stored data item is not 
        // default convertible to `T`.
        template <class T>
        T get() const;
        //]

        reference deref();
        const_reference deref() const;

        short tag() const;
        void tag(short);

        utree eval(utree const&) const;
        utree eval(utree&) const;

        utree operator() (utree const&) const;
        utree operator() (utree&) const;
    //<-
    protected:
        void ensure_list_type(char const* failed_in = "ensure_list_type()");

    private:
        typedef utree_type type;

        template <class UTreeX, class UTreeY>
        friend struct detail::visit_impl;
        friend struct detail::index_impl;

        type::info get_type() const;
        void set_type(type::info);
        void free();
        void copy(const_reference);

        union {
            detail::fast_string s;
            detail::list l;
            detail::range r;
            detail::string_range sr;
            detail::void_ptr v;
            bool b;
            int i;
            double d;
            utree* p;
            function_base* pf;
        };
    //->
    };
    //]

    //[utree_tuple_interface 
    /*<-*/inline/*->*/
    utree::reference get(utree::reference, utree::size_type);
    /*<-*/inline/*->*/
    utree::const_reference get(utree::const_reference, utree::size_type);
    /*`[warning `get()` has O(n) complexity.]`*/
    //]

    struct utree::list_type : utree
    {
        using utree::operator=;

        list_type() : utree() { ensure_list_type("list_type()"); }

        template <typename T0>
        list_type(T0 t0) : utree(t0) {}
      
        template <typename T0, typename T1>
        list_type(T0 t0, T1 t1) : utree(t0, t1) {}
    };

    ///////////////////////////////////////////////////////////////////////////
    // predefined instances for singular types
    utree::invalid_type const invalid = {};
    utree::nil_type const nil = {};
    utree::list_type const empty_list = utree::list_type();
}}

#if defined(BOOST_MSVC)
  #pragma warning(pop)
#endif

#endif