common.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 1,588 行 · 第 1/3 页

/*=============================================================================
    Copyright (c) 2001-2003 Daniel Nuffer
    Copyright (c) 2001-2007 Hartmut Kaiser
    Revised 2007, Copyright (c) Tobias Schwinger
    http://spirit.sourceforge.net/

  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)
=============================================================================*/
#ifndef BOOST_SPIRIT_TREE_COMMON_HPP
#define BOOST_SPIRIT_TREE_COMMON_HPP

#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
#include <vector>
#else
#include <list>
#endif

#if defined(BOOST_SPIRIT_USE_BOOST_ALLOCATOR_FOR_TREES)
#include <boost/pool/pool_alloc.hpp>
#endif

#include <algorithm>

#include <boost/ref.hpp>
#include <boost/call_traits.hpp>
#include <boost/spirit/home/classic/namespace.hpp>
#include <boost/spirit/home/classic/core.hpp>
#include <boost/detail/iterator.hpp> // for boost::detail::iterator_traits

#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
#include <iostream>
#include <boost/spirit/home/classic/debug/debug_node.hpp>
#endif

#include <boost/spirit/home/classic/tree/common_fwd.hpp>

namespace boost { namespace spirit {

BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN

template <typename T>
void swap(tree_node<T>& a, tree_node<T>& b);

template <typename T, typename V>
void swap(node_iter_data<T, V>& a, node_iter_data<T, V>& b);

namespace impl {
    template <typename T>
    inline void cp_swap(T& t1, T& t2);
}

template <typename T>
struct tree_node
{
    typedef T parse_node_t;
    
#if !defined(BOOST_SPIRIT_USE_BOOST_ALLOCATOR_FOR_TREES)
    typedef std::allocator<tree_node<T> > allocator_type;
#elif !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
    typedef boost::pool_allocator<tree_node<T> > allocator_type;
#else
    typedef boost::fast_pool_allocator<tree_node<T> > allocator_type;
#endif

#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
    typedef std::vector<tree_node<T>, allocator_type> children_t;
#else
    typedef std::list<tree_node<T>, allocator_type> children_t;
#endif  // BOOST_SPIRIT_USE_LIST_FOR_TREES

    typedef typename children_t::iterator tree_iterator;
    typedef typename children_t::const_iterator const_tree_iterator;

    T value;
    children_t children;

    tree_node()
        : value()
        , children()
    {}

    explicit tree_node(T const& v)
        : value(v)
        , children()
    {}

    tree_node(T const& v, children_t const& c)
        : value(v)
        , children(c)
    {}

    void swap(tree_node<T>& x)
    {
        impl::cp_swap(value, x.value);
        impl::cp_swap(children, x.children);
    }

// Intel V5.0.1 has a problem without this explicit operator=
    tree_node &operator= (tree_node const &rhs)
    {
        tree_node(rhs).swap(*this);
        return *this;
    }
};

#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
template <typename T>
inline std::ostream&
operator<<(std::ostream& o, tree_node<T> const& n)
{
    static int depth = 0;
    o << "\n";
    for (int i = 0; i <= depth; ++i)
    {
        o << "\t";
    }
    o << "(depth = " << depth++ << " value = " << n.value;
    int c = 0;
    for (typename tree_node<T>::children_t::const_iterator it = n.children.begin();
         it != n.children.end(); ++it)
    {
        o << " children[" << c++ << "] = " << *it;
    }
    o << ")";
    --depth;
    return o;
}
#endif

//////////////////////////////////
template <typename IteratorT, typename ValueT>
struct node_iter_data
{
    typedef IteratorT iterator_t;
    typedef IteratorT /*const*/ const_iterator_t;

    node_iter_data()
        : first(), last(), is_root_(false), parser_id_(), value_()
        {}

    node_iter_data(IteratorT const& _first, IteratorT const& _last)
        : first(_first), last(_last), is_root_(false), parser_id_(), value_()
        {}

    void swap(node_iter_data& x)
    {
        impl::cp_swap(first, x.first);
        impl::cp_swap(last, x.last);
        impl::cp_swap(parser_id_, x.parser_id_);
        impl::cp_swap(is_root_, x.is_root_);
        impl::cp_swap(value_, x.value_);
    }

    IteratorT begin()
    {
        return first;
    }

    IteratorT const& begin() const
    {
        return first;
    }

    IteratorT end()
    {
        return last;
    }

    IteratorT const& end() const
    {
        return last;
    }

    bool is_root() const
    {
        return is_root_;
    }

    void is_root(bool b)
    {
        is_root_ = b;
    }

    parser_id id() const
    {
        return parser_id_;
    }

    void id(parser_id r)
    {
        parser_id_ = r;
    }

    ValueT const& value() const
    {
        return value_;
    }

    void value(ValueT const& v)
    {
        value_ = v;
    }
private:
    IteratorT first, last;
    bool is_root_;
    parser_id parser_id_;
    ValueT value_;

public:
};

#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
// value is default nil_t, so provide an operator<< for nil_t
inline std::ostream&
operator<<(std::ostream& o, nil_t const&)
{
    return o;
}

template <typename IteratorT, typename ValueT>
inline std::ostream&
operator<<(std::ostream& o, node_iter_data<IteratorT, ValueT> const& n)
{
    o << "(id = " << n.id() << " text = \"";
    typedef typename node_iter_data<IteratorT, ValueT>::const_iterator_t
        iterator_t;
    for (iterator_t it = n.begin(); it != n.end(); ++it)
        impl::token_printer(o, *it);
    o << "\" is_root = " << n.is_root()
        << /*" value = " << n.value() << */")";
    return o;
}
#endif

//////////////////////////////////
template <typename IteratorT = char const*, typename ValueT = nil_t>
struct node_val_data
{
    typedef
        typename boost::detail::iterator_traits<IteratorT>::value_type
        value_type;

#if !defined(BOOST_SPIRIT_USE_BOOST_ALLOCATOR_FOR_TREES)
    typedef std::allocator<value_type> allocator_type;
#elif !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
    typedef boost::pool_allocator<value_type> allocator_type;
#else
    typedef boost::fast_pool_allocator<value_type> allocator_type;
#endif

#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
    typedef std::vector<value_type, allocator_type> container_t;
#else
    typedef std::list<value_type, allocator_type> container_t;
#endif

    typedef typename container_t::iterator iterator_t;
    typedef typename container_t::const_iterator const_iterator_t;

    node_val_data()
        : text(), is_root_(false), parser_id_(), value_()
        {}

#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
    node_val_data(IteratorT const& _first, IteratorT const& _last)
        : text(), is_root_(false), parser_id_(), value_()
        {
            std::copy(_first, _last, std::inserter(text, text.end()));
        }

    // This constructor is for building text out of iterators
    template <typename IteratorT2>
    node_val_data(IteratorT2 const& _first, IteratorT2 const& _last)
        : text(), is_root_(false), parser_id_(), value_()
        {
            std::copy(_first, _last, std::inserter(text, text.end()));
        }
#else
    node_val_data(IteratorT const& _first, IteratorT const& _last)
        : text(_first, _last), is_root_(false), parser_id_(), value_()
        {}

    // This constructor is for building text out of iterators
    template <typename IteratorT2>
    node_val_data(IteratorT2 const& _first, IteratorT2 const& _last)
        : text(_first, _last), is_root_(false), parser_id_(), value_()
        {}
#endif

    void swap(node_val_data& x)
    {
        impl::cp_swap(text, x.text);
        impl::cp_swap(is_root_, x.is_root_);
        impl::cp_swap(parser_id_, x.parser_id_);
        impl::cp_swap(value_, x.value_);
    }

    typename container_t::iterator begin()
    {
        return text.begin();
    }

    typename container_t::const_iterator begin() const
    {
        return text.begin();
    }

    typename container_t::iterator end()
    {
        return text.end();
    }

    typename container_t::const_iterator end() const
    {
        return text.end();
    }

    bool is_root() const
    {
        return is_root_;
    }

    void is_root(bool b)
    {
        is_root_ = b;
    }

    parser_id id() const
    {
        return parser_id_;
    }

    void id(parser_id r)
    {
        parser_id_ = r;
    }

    ValueT const& value() const
    {
        return value_;
    }

    void value(ValueT const& v)
    {
        value_ = v;
    }

private:
    container_t text;
    bool is_root_;
    parser_id parser_id_;
    ValueT value_;
};

#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
template <typename IteratorT, typename ValueT>
inline std::ostream&
operator<<(std::ostream& o, node_val_data<IteratorT, ValueT> const& n)
{
    o << "(id = " << n.id() << " text = \"";
    typedef typename node_val_data<IteratorT, ValueT>::const_iterator_t
        iterator_t;
    for (iterator_t it = n.begin(); it != n.end(); ++it)
        impl::token_printer(o, *it);
    o << "\" is_root = " << n.is_root()
        << " value = " << n.value() << ")";
    return o;
}
#endif

template <typename T>
inline void
swap(tree_node<T>& a, tree_node<T>& b)
{
    a.swap(b);
}

template <typename T, typename V>
inline void
swap(node_iter_data<T, V>& a, node_iter_data<T, V>& b)
{
    a.swap(b);
}

//////////////////////////////////
template <typename ValueT>
class node_iter_data_factory
{
public:
    // This inner class is so that node_iter_data_factory can simulate
    // a template template parameter
    template <typename IteratorT>
    class factory
    {
    public:
        typedef IteratorT iterator_t;
        typedef node_iter_data<iterator_t, ValueT> node_t;

        static node_t create_node(iterator_t const& first, iterator_t const& last,
                bool /*is_leaf_node*/)
        {
            return node_t(first, last);
        }

        static node_t empty_node()
        {
            return node_t();
        }

        // precondition: ContainerT contains a tree_node<node_t>.  And all
        // iterators in the container point to the same sequence.
        template <typename ContainerT>
        static node_t group_nodes(ContainerT const& nodes)
        {
            return node_t(nodes.begin()->value.begin(),
                    nodes.back().value.end());
        }
    };
};

//////////////////////////////////
template <typename ValueT>
class node_val_data_factory 
{
public:
    // This inner class is so that node_val_data_factory can simulate
    // a template template parameter
    template <typename IteratorT>
    class factory
    {
    public:
        typedef IteratorT iterator_t;
        typedef node_val_data<iterator_t, ValueT> node_t;

        static node_t create_node(iterator_t const& first, iterator_t const& last,
                bool is_leaf_node)
        {
            if (is_leaf_node)
                return node_t(first, last);
            else
                return node_t();
        }

        static node_t empty_node()
        {
            return node_t();
        }

        template <typename ContainerT>
        static node_t group_nodes(ContainerT const& nodes)
        {
            typename node_t::container_t c;
            typename ContainerT::const_iterator i_end = nodes.end();
            // copy all the nodes text into a new one
            for (typename ContainerT::const_iterator i = nodes.begin();
                 i != i_end; ++i)
            {
                // See docs: reduced_node_d cannot be used with a
                // rule inside the [].
                assert(i->children.size() == 0);
                c.insert(c.end(), i->value.begin(), i->value.end());
            }
            return node_t(c.begin(), c.end());
        }
    };
};

//////////////////////////////////
template <typename ValueT>
class node_all_val_data_factory
{
public:
    // This inner class is so that node_all_val_data_factory can simulate
    // a template template parameter
    template <typename IteratorT>
    class factory
    {
    public:
        typedef IteratorT iterator_t;
        typedef node_val_data<iterator_t, ValueT> node_t;

        static node_t create_node(iterator_t const& first, iterator_t const& last,
                bool /*is_leaf_node*/)
        {
            return node_t(first, last);
        }

        static node_t empty_node()
        {
            return node_t();
        }

        template <typename ContainerT>
        static node_t group_nodes(ContainerT const& nodes)
        {
            typename node_t::container_t c;
            typename ContainerT::const_iterator i_end = nodes.end();
            // copy all the nodes text into a new one
            for (typename ContainerT::const_iterator i = nodes.begin();
                    i != i_end; ++i)
            {
                assert(i->children.size() == 0);
                c.insert(c.end(), i->value.begin(), i->value.end());
            }
            return node_t(c.begin(), c.end());
        }
    };
};

namespace impl {

    ///////////////////////////////////////////////////////////////////////////
    // can't call unqualified swap from within classname::swap
    // as Koenig lookup rules will find only the classname::swap
    // member function not the global declaration, so use cp_swap
    // as a forwarding function (JM):
#if __GNUC__ == 2
    using ::std::swap;
#endif
    template <typename T>
    inline void cp_swap(T& t1, T& t2)
    {
        using std::swap;
        using BOOST_SPIRIT_CLASSIC_NS::swap;
        using boost::swap;