comparison DEPENDENCIES/generic/include/boost/spirit/home/classic/tree/common.hpp @ 16:2665513ce2d3

Add boost headers

+/*=============================================================================
+    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
+#include <boost/assert.hpp>
+
+#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 [].
+                BOOST_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)
+            {
+                BOOST_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;
+        swap(t1, t2);
+    }
+}
+
+//////////////////////////////////
+template <typename IteratorT, typename NodeFactoryT, typename T>
+class tree_match : public match<T>
+{
+public:
+
+    typedef typename NodeFactoryT::template factory<IteratorT> node_factory_t;
+    typedef typename node_factory_t::node_t parse_node_t;
+    typedef tree_node<parse_node_t> node_t;
+    typedef typename node_t::children_t container_t;
+    typedef typename container_t::iterator tree_iterator;
+    typedef typename container_t::const_iterator const_tree_iterator;
+
+    typedef T attr_t;
+    typedef typename boost::call_traits<T>::param_type      param_type;
+    typedef typename boost::call_traits<T>::reference       reference;
+    typedef typename boost::call_traits<T>::const_reference const_reference;
+
+    tree_match()
+    : match<T>(), trees()
+    {}
+
+    explicit
+    tree_match(std::size_t length_)
+    : match<T>(length_), trees()
+    {}
+
+    tree_match(std::size_t length_, parse_node_t const& n)
+    : match<T>(length_), trees()
+    { 
+        trees.push_back(node_t(n)); 
+    }
+
+    tree_match(std::size_t length_, param_type val, parse_node_t const& n)
+    : match<T>(length_, val), trees()
+    {
+#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
+        trees.reserve(10); // this is more or less an arbitrary number...
+#endif
+        trees.push_back(node_t(n));
+    }
+
+    // attention, these constructors will change the second parameter!
+    tree_match(std::size_t length_, container_t& c)
+    : match<T>(length_), trees()
+    { 
+        impl::cp_swap(trees, c);
+    }
+
+    tree_match(std::size_t length_, param_type val, container_t& c)
+    : match<T>(length_, val), trees()
+    {
+        impl::cp_swap(trees, c);
+    }
+
+    template <typename T2>
+    tree_match(match<T2> const& other)
+    : match<T>(other), trees()
+    {}
+
+    template <typename T2, typename T3, typename T4>
+    tree_match(tree_match<T2, T3, T4> const& other)
+    : match<T>(other), trees()
+    { impl::cp_swap(trees, other.trees); }
+
+    template <typename T2>
+    tree_match&
+    operator=(match<T2> const& other)
+    {
+        match<T>::operator=(other);
+        return *this;
+    }
+
+    template <typename T2, typename T3, typename T4>
+    tree_match&
+    operator=(tree_match<T2, T3, T4> const& other)
+    {
+        match<T>::operator=(other);
+        impl::cp_swap(trees, other.trees);
+        return *this;
+    }
+
+    tree_match(tree_match const& x)
+    : match<T>(x), trees()
+    {
+        // use auto_ptr like ownership for the trees data member
+        impl::cp_swap(trees, x.trees);
+    }
+
+    tree_match& operator=(tree_match const& x)
+    {
+        tree_match tmp(x);
+        this->swap(tmp);
+        return *this;
+    }
+
+    void swap(tree_match& x)
+    {
+        match<T>::swap(x);
+        impl::cp_swap(trees, x.trees);
+    }
+
+    mutable container_t trees;
+};
+
+#if defined(BOOST_SPIRIT_DEBUG) && \
+    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
+template <typename IteratorT, typename NodeFactoryT, typename T>
+inline std::ostream&
+operator<<(std::ostream& o, tree_match<IteratorT, NodeFactoryT, T> const& m)
+{
+    typedef
+        typename tree_match<IteratorT, NodeFactoryT, T>::container_t::iterator
+        iterator;
+
+    o << "(length = " << (int)m.length();
+    int c = 0;
+    for (iterator i = m.trees.begin(); i != m.trees.end(); ++i)
+    {
+        o << " trees[" << c++ << "] = " << *i;
+    }
+    o << "\n)";
+    return o;
+}
+#endif
+
+//////////////////////////////////
+struct tree_policy
+{
+    template <typename FunctorT, typename MatchT>
+    static void apply_op_to_match(FunctorT const& /*op*/, MatchT& /*m*/)
+    {}
+
+    template <typename MatchT, typename Iterator1T, typename Iterator2T>
+    static void group_match(MatchT& /*m*/, parser_id const& /*id*/,
+            Iterator1T const& /*first*/, Iterator2T const& /*last*/)
+    {}
+
+    template <typename MatchT>
+    static void concat(MatchT& /*a*/, MatchT const& /*b*/)
+    {}
+};
+
+//////////////////////////////////
+template <
+    typename MatchPolicyT,
+    typename IteratorT,
+    typename NodeFactoryT,
+    typename TreePolicyT, 
+    typename T
+>
+struct common_tree_match_policy : public match_policy
+{
+    common_tree_match_policy()
+    {
+    }
+
+    template <typename PolicyT>
+    common_tree_match_policy(PolicyT const & policies)
+        : match_policy((match_policy const &)policies)
+    {
+    }
+
+    template <typename U>
+    struct result { typedef tree_match<IteratorT, NodeFactoryT, U> type; };
+
+    typedef tree_match<IteratorT, NodeFactoryT, T> match_t;
+    typedef IteratorT iterator_t;
+    typedef TreePolicyT tree_policy_t;
+    typedef NodeFactoryT factory_t;
+
+    static const match_t no_match() { return match_t(); }
+    static const match_t empty_match()
+    { return match_t(0, tree_policy_t::empty_node()); }
+
+    template <typename AttrT, typename Iterator1T, typename Iterator2T>
+    static tree_match<IteratorT, NodeFactoryT, AttrT> create_match(
+        std::size_t length,
+        AttrT const& val,
+        Iterator1T const& first,
+        Iterator2T const& last)
+    {
+#if defined(BOOST_SPIRIT_DEBUG) && \
+    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
+
+        BOOST_SPIRIT_DEBUG_OUT << "\n>>> create_node(begin) <<<\n" 
+            "creating node text: \"";
+        for (Iterator1T it = first; it != last; ++it)
+            impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
+        BOOST_SPIRIT_DEBUG_OUT << "\"\n";
+        BOOST_SPIRIT_DEBUG_OUT << ">>> create_node(end) <<<\n\n"; 
+#endif
+        return tree_match<IteratorT, NodeFactoryT, AttrT>(length, val,
+            tree_policy_t::create_node(length, first, last, true));
+    }
+
+    template <typename Match1T, typename Match2T>
+    static void concat_match(Match1T& a, Match2T const& b)
+    {
+#if defined(BOOST_SPIRIT_DEBUG) && \
+    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
+
+        BOOST_SPIRIT_DEBUG_OUT << "\n>>> concat_match(begin) <<<\n";
+        BOOST_SPIRIT_DEBUG_OUT << "tree a:\n" << a << "\n";
+        BOOST_SPIRIT_DEBUG_OUT << "tree b:\n" << b << "\n";
+        BOOST_SPIRIT_DEBUG_OUT << ">>> concat_match(end) <<<\n\n";
+#endif
+        BOOST_SPIRIT_ASSERT(a && b);
+        if (a.length() == 0)
+        {
+            a = b;
+            return;
+        }
+        else if (b.length() == 0
+#ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
+            && !b.trees.begin()->value.id().to_long()
+#endif
+            )
+        {
+            return;
+        }
+        a.concat(b);
+        tree_policy_t::concat(a, b);
+    }
+
+    template <typename MatchT, typename IteratorT2>
+    void
+    group_match(
+        MatchT&             m,
+        parser_id const&    id,
+        IteratorT2 const&   first,
+        IteratorT2 const&   last) const
+    {
+        if (!m) return;
+        
+#if defined(BOOST_SPIRIT_DEBUG) && \
+    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_TREES)
+
+        BOOST_SPIRIT_DEBUG_OUT << "\n>>> group_match(begin) <<<\n"
+            "new node(" << id << ") \"";
+        for (IteratorT2 it = first; it != last; ++it)
+            impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
+        BOOST_SPIRIT_DEBUG_OUT << "\"\n";
+        BOOST_SPIRIT_DEBUG_OUT << "new child tree (before grouping):\n" << m << "\n";
+
+        tree_policy_t::group_match(m, id, first, last);
+
+        BOOST_SPIRIT_DEBUG_OUT << "new child tree (after grouping):\n" << m << "\n";
+        BOOST_SPIRIT_DEBUG_OUT << ">>> group_match(end) <<<\n\n";
+#else
+        tree_policy_t::group_match(m, id, first, last);
+#endif
+    }
+};
+
+//////////////////////////////////
+template <typename MatchPolicyT, typename NodeFactoryT>
+struct common_tree_tree_policy
+{
+    typedef typename MatchPolicyT::iterator_t iterator_t;
+    typedef typename MatchPolicyT::match_t match_t;
+    typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
+    typedef typename factory_t::node_t node_t;
+
+    template <typename Iterator1T, typename Iterator2T>
+        static node_t
+        create_node(std::size_t /*length*/, Iterator1T const& first,
+            Iterator2T const& last, bool leaf_node)
+    {
+        return factory_t::create_node(first, last, leaf_node);
+    }
+
+    static node_t
+        empty_node()
+    {
+        return factory_t::empty_node();
+    }
+
+    template <typename FunctorT>
+        static void apply_op_to_match(FunctorT const& op, match_t& m)
+    {
+        op(m);
+    }
+};
+
+//////////////////////////////////
+// directives to modify how the parse tree is generated
+
+struct no_tree_gen_node_parser_gen;
+
+template <typename T>
+struct no_tree_gen_node_parser
+:   public unary<T, parser<no_tree_gen_node_parser<T> > >
+{
+    typedef no_tree_gen_node_parser<T> self_t;
+    typedef no_tree_gen_node_parser_gen parser_generator_t;
+    typedef unary_parser_category parser_category_t;
+
+    no_tree_gen_node_parser(T const& a)
+    : unary<T, parser<no_tree_gen_node_parser<T> > >(a) {}
+
+    template <typename ScannerT>
+    typename parser_result<self_t, ScannerT>::type
+    parse(ScannerT const& scanner) const
+    {
+        typedef typename ScannerT::iteration_policy_t iteration_policy_t;
+        typedef match_policy match_policy_t;
+        typedef typename ScannerT::action_policy_t action_policy_t;
+        typedef scanner_policies<
+            iteration_policy_t,
+            match_policy_t,
+            action_policy_t
+        > policies_t;
+
+        return this->subject().parse(scanner.change_policies(policies_t(scanner)));
+    }
+};
+
+struct no_tree_gen_node_parser_gen
+{
+    template <typename T>
+    struct result {
+
+        typedef no_tree_gen_node_parser<T> type;
+    };
+
+    template <typename T>
+    static no_tree_gen_node_parser<T>
+    generate(parser<T> const& s)
+    {
+        return no_tree_gen_node_parser<T>(s.derived());
+    }
+
+    template <typename T>
+    no_tree_gen_node_parser<T>
+    operator[](parser<T> const& s) const
+    {
+        return no_tree_gen_node_parser<T>(s.derived());
+    }
+};
+
+const no_tree_gen_node_parser_gen no_node_d = no_tree_gen_node_parser_gen();
+
+//////////////////////////////////
+
+struct leaf_node_parser_gen;
+
+template<typename T>
+struct leaf_node_parser
+:   public unary<T, parser<leaf_node_parser<T> > >
+{
+    typedef leaf_node_parser<T> self_t;
+    typedef leaf_node_parser_gen parser_generator_t;
+    typedef unary_parser_category parser_category_t;
+
+    leaf_node_parser(T const& a)
+    : unary<T, parser<leaf_node_parser<T> > >(a) {}
+
+    template <typename ScannerT>
+    typename parser_result<self_t, ScannerT>::type
+    parse(ScannerT const& scanner) const
+    {
+        typedef scanner_policies< typename ScannerT::iteration_policy_t,
+            match_policy, typename ScannerT::action_policy_t > policies_t;
+
+        typedef typename ScannerT::iterator_t iterator_t;
+        typedef typename parser_result<self_t, ScannerT>::type result_t;
+        typedef typename result_t::node_factory_t factory_t;
+
+        iterator_t from = scanner.first;
+        result_t hit = impl::contiguous_parser_parse<result_t>(this->subject(),
+            scanner.change_policies(policies_t(scanner,match_policy(),scanner)),
+            scanner);
+
+        if (hit)
+            return result_t(hit.length(), 
+                factory_t::create_node(from, scanner.first, true));
+        else
+            return result_t(hit.length());
+    }
+};
+
+struct leaf_node_parser_gen
+{
+    template <typename T>
+    struct result {
+
+        typedef leaf_node_parser<T> type;
+    };
+
+    template <typename T>
+    static leaf_node_parser<T>
+    generate(parser<T> const& s)
+    {
+        return leaf_node_parser<T>(s.derived());
+    }
+
+    template <typename T>
+    leaf_node_parser<T>
+    operator[](parser<T> const& s) const
+    {
+        return leaf_node_parser<T>(s.derived());
+    }
+};
+
+const leaf_node_parser_gen leaf_node_d = leaf_node_parser_gen();
+const leaf_node_parser_gen token_node_d = leaf_node_parser_gen();
+
+//////////////////////////////////
+namespace impl {
+
+    template <typename MatchPolicyT>
+    struct tree_policy_selector
+    {
+        typedef tree_policy type;
+    };
+
+} // namespace impl
+
+//////////////////////////////////
+template <typename NodeParserT>
+struct node_parser_gen;
+
+template <typename T, typename NodeParserT>
+struct node_parser
+:   public unary<T, parser<node_parser<T, NodeParserT> > >
+{
+    typedef node_parser<T, NodeParserT> self_t;
+    typedef node_parser_gen<NodeParserT> parser_generator_t;
+    typedef unary_parser_category parser_category_t;
+
+    node_parser(T const& a)
+    : unary<T, parser<node_parser<T, NodeParserT> > >(a) {}
+
+    template <typename ScannerT>
+    struct result
+    {
+        typedef typename parser_result<T, ScannerT>::type type;
+    };
+
+    template <typename ScannerT>
+    typename parser_result<self_t, ScannerT>::type
+    parse(ScannerT const& scanner) const
+    {
+        typename parser_result<self_t, ScannerT>::type hit = this->subject().parse(scanner);
+        if (hit)
+        {
+            impl::tree_policy_selector<typename ScannerT::match_policy_t>::type::apply_op_to_match(NodeParserT(), hit);
+        }
+        return hit;
+    }
+};
+
+template <typename NodeParserT>
+struct node_parser_gen
+{
+    template <typename T>
+    struct result {
+
+        typedef node_parser<T, NodeParserT> type;
+    };
+
+    template <typename T>
+    static node_parser<T, NodeParserT>
+    generate(parser<T> const& s)
+    {
+        return node_parser<T, NodeParserT>(s.derived());
+    }
+
+    template <typename T>
+    node_parser<T, NodeParserT>
+    operator[](parser<T> const& s) const
+    {
+        return node_parser<T, NodeParserT>(s.derived());
+    }
+};
+//////////////////////////////////
+struct reduced_node_op
+{
+    template <typename MatchT>
+    void operator()(MatchT& m) const
+    {
+        if (m.trees.size() == 1)
+        {
+            m.trees.begin()->children.clear();
+        }
+        else if (m.trees.size() > 1)
+        {
+            typedef typename MatchT::node_factory_t node_factory_t;
+            m = MatchT(m.length(), node_factory_t::group_nodes(m.trees));
+        }
+    }
+};
+
+const node_parser_gen<reduced_node_op> reduced_node_d =
+    node_parser_gen<reduced_node_op>();
+
+
+struct discard_node_op
+{
+    template <typename MatchT>
+    void operator()(MatchT& m) const
+    {
+        m.trees.clear();
+    }
+};
+
+const node_parser_gen<discard_node_op> discard_node_d =
+    node_parser_gen<discard_node_op>();
+
+struct infix_node_op
+{
+    template <typename MatchT>
+    void operator()(MatchT& m) const
+    {
+        typedef typename MatchT::container_t container_t;
+        typedef typename MatchT::container_t::iterator iter_t;
+        typedef typename MatchT::container_t::value_type value_t;
+
+        using std::swap;
+        using boost::swap;
+        using BOOST_SPIRIT_CLASSIC_NS::swap;
+
+        // copying the tree nodes is expensive, since it may copy a whole
+        // tree.  swapping them is cheap, so swap the nodes we want into
+        // a new container of children.
+        container_t new_children;
+        std::size_t length = 0;
+        std::size_t tree_size = m.trees.size();
+
+        // the infix_node_d[] make no sense for nodes with no subnodes
+        BOOST_SPIRIT_ASSERT(tree_size >= 1);
+
+        bool keep = true;
+#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
+        new_children.reserve((tree_size+1)/2);
+#endif
+        iter_t i_end = m.trees.end();
+        for (iter_t i = m.trees.begin(); i != i_end; ++i)
+        {
+            if (keep) {
+                // adjust the length
+                length += std::distance((*i).value.begin(), (*i).value.end());
+
+                // move the child node
+                new_children.push_back(value_t());
+                swap(new_children.back(), *i);
+                keep = false;
+            }
+            else {
+                // ignore this child node
+                keep = true;
+            }
+        }
+
+        m = MatchT(length, new_children);
+    }
+};
+
+const node_parser_gen<infix_node_op> infix_node_d =
+    node_parser_gen<infix_node_op>();
+
+struct discard_first_node_op
+{
+    template <typename MatchT>
+    void operator()(MatchT& m) const
+    {
+        typedef typename MatchT::container_t container_t;
+        typedef typename MatchT::container_t::iterator iter_t;
+        typedef typename MatchT::container_t::value_type value_t;
+
+        using std::swap;
+        using boost::swap;
+        using BOOST_SPIRIT_CLASSIC_NS::swap;
+
+        // copying the tree nodes is expensive, since it may copy a whole
+        // tree.  swapping them is cheap, so swap the nodes we want into
+        // a new container of children, instead of saying
+        // m.trees.erase(m.trees.begin()) because, on a container_t that will 
+        // cause all the nodes afterwards to be copied into the previous 
+        // position.
+        container_t new_children;
+        std::size_t length = 0;
+        std::size_t tree_size = m.trees.size();
+
+        // the discard_first_node_d[] make no sense for nodes with no subnodes
+        BOOST_SPIRIT_ASSERT(tree_size >= 1);
+
+        if (tree_size > 1) {
+#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
+            new_children.reserve(tree_size - 1);
+#endif
+            iter_t i = m.trees.begin(), i_end = m.trees.end();
+            for (++i; i != i_end; ++i)
+            {
+                // adjust the length
+                length += std::distance((*i).value.begin(), (*i).value.end());
+
+                // move the child node
+                new_children.push_back(value_t());
+                swap(new_children.back(), *i);
+            }
+        }
+        else {
+        // if there was a tree and now there isn't any, insert an empty node
+            iter_t i = m.trees.begin(); 
+
+        // This isn't entirely correct, since the empty node will reference
+        // the end of the discarded node, but I currently don't see any way to 
+        // get at the begin of the node following this subnode.
+        // This should be safe anyway because the it shouldn't get dereferenced
+        // under any circumstances.
+            typedef typename value_t::parse_node_t::iterator_t iterator_type;
+            iterator_type it = (*i).value.end();
+            
+            new_children.push_back(
+                value_t(typename value_t::parse_node_t(it, it)));
+        }
+        
+        m = MatchT(length, new_children);
+    }
+};
+
+const node_parser_gen<discard_first_node_op> discard_first_node_d =
+    node_parser_gen<discard_first_node_op>();
+
+struct discard_last_node_op
+{
+    template <typename MatchT>
+    void operator()(MatchT& m) const
+    {
+        typedef typename MatchT::container_t container_t;
+        typedef typename MatchT::container_t::iterator iter_t;
+        typedef typename MatchT::container_t::value_type value_t;
+
+        using std::swap;
+        using boost::swap;
+        using BOOST_SPIRIT_CLASSIC_NS::swap;
+
+        // copying the tree nodes is expensive, since it may copy a whole
+        // tree.  swapping them is cheap, so swap the nodes we want into
+        // a new container of children, instead of saying
+        // m.trees.erase(m.trees.begin()) because, on a container_t that will 
+        // cause all the nodes afterwards to be copied into the previous 
+        // position.
+        container_t new_children;
+        std::size_t length = 0;
+        std::size_t tree_size = m.trees.size();
+
+        // the discard_last_node_d[] make no sense for nodes with no subnodes
+        BOOST_SPIRIT_ASSERT(tree_size >= 1);
+
+        if (tree_size > 1) {
+            m.trees.pop_back();
+#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
+            new_children.reserve(tree_size - 1);
+#endif            
+            iter_t i_end = m.trees.end();
+            for (iter_t i = m.trees.begin(); i != i_end; ++i)
+            {
+                // adjust the length
+                length += std::distance((*i).value.begin(), (*i).value.end());
+
+                // move the child node
+                new_children.push_back(value_t());
+                swap(new_children.back(), *i);
+            }
+        }
+        else {
+        // if there was a tree and now there isn't any, insert an empty node
+            iter_t i = m.trees.begin(); 
+
+            typedef typename value_t::parse_node_t::iterator_t iterator_type;
+            iterator_type it = (*i).value.begin();
+            
+            new_children.push_back(
+                value_t(typename value_t::parse_node_t(it, it)));
+        }
+        
+        m = MatchT(length, new_children);
+    }
+};
+
+const node_parser_gen<discard_last_node_op> discard_last_node_d =
+    node_parser_gen<discard_last_node_op>();
+
+struct inner_node_op
+{
+    template <typename MatchT>
+    void operator()(MatchT& m) const
+    {
+        typedef typename MatchT::container_t container_t;
+        typedef typename MatchT::container_t::iterator iter_t;
+        typedef typename MatchT::container_t::value_type value_t;
+
+        using std::swap;
+        using boost::swap;
+        using BOOST_SPIRIT_CLASSIC_NS::swap;
+
+        // copying the tree nodes is expensive, since it may copy a whole
+        // tree.  swapping them is cheap, so swap the nodes we want into
+        // a new container of children, instead of saying
+        // m.trees.erase(m.trees.begin()) because, on a container_t that will 
+        // cause all the nodes afterwards to be copied into the previous 
+        // position.
+        container_t new_children;
+        std::size_t length = 0;
+        std::size_t tree_size = m.trees.size();
+        
+        // the inner_node_d[] make no sense for nodes with less then 2 subnodes
+        BOOST_SPIRIT_ASSERT(tree_size >= 2);
+
+        if (tree_size > 2) {
+            m.trees.pop_back(); // erase the last element
+#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
+            new_children.reserve(tree_size - 1);
+#endif
+            iter_t i = m.trees.begin(); // skip over the first element
+            iter_t i_end = m.trees.end();
+            for (++i; i != i_end; ++i)
+            {
+                // adjust the length
+                length += std::distance((*i).value.begin(), (*i).value.end());
+                
+                // move the child node
+                new_children.push_back(value_t());
+                swap(new_children.back(), *i);
+            }
+        }
+        else {
+        // if there was a tree and now there isn't any, insert an empty node
+            iter_t i = m.trees.begin(); // skip over the first element
+
+            typedef typename value_t::parse_node_t::iterator_t iterator_type;
+            iterator_type it = (*++i).value.begin();
+            
+            new_children.push_back(
+                value_t(typename value_t::parse_node_t(it, it)));
+        }
+        
+        m = MatchT(length, new_children);
+    }
+};
+
+const node_parser_gen<inner_node_op> inner_node_d =
+    node_parser_gen<inner_node_op>();
+
+
+//////////////////////////////////
+// action_directive_parser and action_directive_parser_gen
+// are meant to be used as a template to create directives that
+// generate action classes.  For example access_match and
+// access_node.  The ActionParserT template parameter must be
+// a class that has an innter class called action that is templated
+// on the parser type and the action type.
+template <typename ActionParserT>
+struct action_directive_parser_gen;
+
+template <typename T, typename ActionParserT>
+struct action_directive_parser
+:   public unary<T, parser<action_directive_parser<T, ActionParserT> > >
+{
+    typedef action_directive_parser<T, ActionParserT> self_t;
+    typedef action_directive_parser_gen<ActionParserT> parser_generator_t;
+    typedef unary_parser_category parser_category_t;
+
+    action_directive_parser(T const& a)
+        : unary<T, parser<action_directive_parser<T, ActionParserT> > >(a) {}
+
+    template <typename ScannerT>
+    struct result
+    {
+        typedef typename parser_result<T, ScannerT>::type type;
+    };
+
+    template <typename ScannerT>
+    typename parser_result<self_t, ScannerT>::type
+    parse(ScannerT const& scanner) const
+    {
+        return this->subject().parse(scanner);
+    }
+
+    template <typename ActionT>
+    typename ActionParserT::template action<action_directive_parser<T, ActionParserT>, ActionT>
+    operator[](ActionT const& actor) const
+    {
+        typedef typename
+            ActionParserT::template action<action_directive_parser, ActionT>
+            action_t;
+        return action_t(*this, actor);
+    }
+};
+
+//////////////////////////////////
+template <typename ActionParserT>
+struct action_directive_parser_gen
+{
+    template <typename T>
+    struct result {
+
+        typedef action_directive_parser<T, ActionParserT> type;
+    };
+
+    template <typename T>
+    static action_directive_parser<T, ActionParserT>
+    generate(parser<T> const& s)
+    {
+        return action_directive_parser<T, ActionParserT>(s.derived());
+    }
+
+    template <typename T>
+    action_directive_parser<T, ActionParserT>
+    operator[](parser<T> const& s) const
+    {
+        return action_directive_parser<T, ActionParserT>(s.derived());
+    }
+};
+
+//////////////////////////////////
+// Calls the attached action passing it the match from the parser
+// and the first and last iterators.
+// The inner template class is used to simulate template-template parameters
+// (declared in common_fwd.hpp).
+template <typename ParserT, typename ActionT>
+struct access_match_action::action
+:   public unary<ParserT, parser<access_match_action::action<ParserT, ActionT> > >
+{
+    typedef action_parser_category parser_category;
+    typedef action<ParserT, ActionT> self_t;
+    
+    template <typename ScannerT>
+    struct result
+    {
+        typedef typename parser_result<ParserT, ScannerT>::type type;
+    };
+
+    action( ParserT const& subject,
+            ActionT const& actor_);
+
+    template <typename ScannerT>
+    typename parser_result<self_t, ScannerT>::type
+    parse(ScannerT const& scanner) const;
+
+    ActionT const &predicate() const;
+
+    private:
+    ActionT actor;
+};
+
+//////////////////////////////////
+template <typename ParserT, typename ActionT>
+access_match_action::action<ParserT, ActionT>::action(
+    ParserT const& subject,
+    ActionT const& actor_)
+: unary<ParserT, parser<access_match_action::action<ParserT, ActionT> > >(subject)
+, actor(actor_)
+{}
+
+//////////////////////////////////
+template <typename ParserT, typename ActionT>
+template <typename ScannerT>
+typename parser_result<access_match_action::action<ParserT, ActionT>, ScannerT>::type
+access_match_action::action<ParserT, ActionT>::
+parse(ScannerT const& scan) const
+{
+    typedef typename ScannerT::iterator_t iterator_t;
+    typedef typename parser_result<self_t, ScannerT>::type result_t;
+    if (!scan.at_end())
+    {
+        iterator_t save = scan.first;
+        result_t hit = this->subject().parse(scan);
+        actor(hit, save, scan.first);
+        return hit;
+    }
+    return scan.no_match();
+}
+
+//////////////////////////////////
+template <typename ParserT, typename ActionT>
+ActionT const &access_match_action::action<ParserT, ActionT>::predicate() const
+{
+    return actor;
+}
+
+//////////////////////////////////
+const action_directive_parser_gen<access_match_action> access_match_d
+    = action_directive_parser_gen<access_match_action>();
+
+
+
+//////////////////////////////////
+// Calls the attached action passing it the node from the parser
+// and the first and last iterators
+// The inner template class is used to simulate template-template parameters
+// (declared in common_fwd.hpp).
+template <typename ParserT, typename ActionT>
+struct access_node_action::action
+:   public unary<ParserT, parser<access_node_action::action<ParserT, ActionT> > >
+{
+    typedef action_parser_category parser_category;
+    typedef action<ParserT, ActionT> self_t;
+    
+    template <typename ScannerT>
+    struct result
+    {
+        typedef typename parser_result<ParserT, ScannerT>::type type;
+    };
+
+    action( ParserT const& subject,
+            ActionT const& actor_);
+
+    template <typename ScannerT>
+    typename parser_result<self_t, ScannerT>::type
+    parse(ScannerT const& scanner) const;
+
+    ActionT const &predicate() const;
+
+    private:
+    ActionT actor;
+};
+
+//////////////////////////////////
+template <typename ParserT, typename ActionT>
+access_node_action::action<ParserT, ActionT>::action(
+    ParserT const& subject,
+    ActionT const& actor_)
+: unary<ParserT, parser<access_node_action::action<ParserT, ActionT> > >(subject)
+, actor(actor_)
+{}
+
+//////////////////////////////////
+template <typename ParserT, typename ActionT>
+template <typename ScannerT>
+typename parser_result<access_node_action::action<ParserT, ActionT>, ScannerT>::type
+access_node_action::action<ParserT, ActionT>::
+parse(ScannerT const& scan) const
+{
+    typedef typename ScannerT::iterator_t iterator_t;
+    typedef typename parser_result<self_t, ScannerT>::type result_t;
+    if (!scan.at_end())
+    {
+        iterator_t save = scan.first;
+        result_t hit = this->subject().parse(scan);
+        if (hit && hit.trees.size() > 0)
+            actor(*hit.trees.begin(), save, scan.first);
+        return hit;
+    }
+    return scan.no_match();
+}
+
+//////////////////////////////////
+template <typename ParserT, typename ActionT>
+ActionT const &access_node_action::action<ParserT, ActionT>::predicate() const
+{
+    return actor;
+}
+
+//////////////////////////////////
+const action_directive_parser_gen<access_node_action> access_node_d
+    = action_directive_parser_gen<access_node_action>();
+
+
+
+//////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////
+//
+//  tree_parse_info
+//
+//      Results returned by the tree parse functions:
+//
+//      stop:   points to the final parse position (i.e parsing
+//              processed the input up to this point).
+//
+//      match:  true if parsing is successful. This may be full:
+//              the parser consumed all the input, or partial:
+//              the parser consumed only a portion of the input.
+//
+//      full:   true when we have a full match (i.e the parser
+//              consumed all the input.
+//
+//      length: The number of characters consumed by the parser.
+//              This is valid only if we have a successful match
+//              (either partial or full). A negative value means
+//              that the match is unsucessful.
+//
+//     trees:   Contains the root node(s) of the tree.
+//
+///////////////////////////////////////////////////////////////////////////////
+template <
+    typename IteratorT,
+    typename NodeFactoryT,
+    typename T
+>
+struct tree_parse_info 
+{
+    IteratorT   stop;
+    bool        match;
+    bool        full;
+    std::size_t length;
+    typename tree_match<IteratorT, NodeFactoryT, T>::container_t trees;
+
+    tree_parse_info()
+        : stop()
+        , match(false)
+        , full(false)
+        , length(0)
+        , trees()
+    {}
+
+    template <typename IteratorT2>
+    tree_parse_info(tree_parse_info<IteratorT2> const& pi)
+        : stop(pi.stop)
+        , match(pi.match)
+        , full(pi.full)
+        , length(pi.length)
+        , trees()
+    {
+        using std::swap;
+        using boost::swap;
+        using BOOST_SPIRIT_CLASSIC_NS::swap;
+
+        // use auto_ptr like ownership for the trees data member
+        swap(trees, pi.trees);
+    }
+
+    tree_parse_info(
+        IteratorT   stop_,
+        bool        match_,
+        bool        full_,
+        std::size_t length_,
+        typename tree_match<IteratorT, NodeFactoryT, T>::container_t trees_)
+    :   stop(stop_)
+        , match(match_)
+        , full(full_)
+        , length(length_)
+        , trees()
+    {
+        using std::swap;
+        using boost::swap;
+        using BOOST_SPIRIT_CLASSIC_NS::swap;
+
+        // use auto_ptr like ownership for the trees data member
+        swap(trees, trees_);
+    }
+};
+
+BOOST_SPIRIT_CLASSIC_NAMESPACE_END
+
+}} // namespace BOOST_SPIRIT_CLASSIC_NS
+
+#endif
+