Chris@16: /*=============================================================================
Chris@16:     Copyright (c) 2001-2003 Daniel Nuffer
Chris@16:     Copyright (c) 2001-2007 Hartmut Kaiser
Chris@16:     Revised 2007, Copyright (c) Tobias Schwinger
Chris@16:     http://spirit.sourceforge.net/
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: #ifndef BOOST_SPIRIT_TREE_COMMON_HPP
Chris@16: #define BOOST_SPIRIT_TREE_COMMON_HPP
Chris@16: 
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16: #include <vector>
Chris@16: #else
Chris@16: #include <list>
Chris@16: #endif
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_USE_BOOST_ALLOCATOR_FOR_TREES)
Chris@16: #include <boost/pool/pool_alloc.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: 
Chris@16: #include <boost/ref.hpp>
Chris@16: #include <boost/call_traits.hpp>
Chris@16: #include <boost/spirit/home/classic/namespace.hpp>
Chris@16: #include <boost/spirit/home/classic/core.hpp>
Chris@16: #include <boost/detail/iterator.hpp> // for boost::detail::iterator_traits
Chris@16: #include <boost/assert.hpp>
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16: #include <iostream>
Chris@16: #include <boost/spirit/home/classic/debug/debug_node.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/spirit/home/classic/tree/common_fwd.hpp>
Chris@16: 
Chris@16: namespace boost { namespace spirit {
Chris@16: 
Chris@16: BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
Chris@16: 
Chris@16: template <typename T>
Chris@16: void swap(tree_node<T>& a, tree_node<T>& b);
Chris@16: 
Chris@16: template <typename T, typename V>
Chris@16: void swap(node_iter_data<T, V>& a, node_iter_data<T, V>& b);
Chris@16: 
Chris@16: namespace impl {
Chris@16:     template <typename T>
Chris@16:     inline void cp_swap(T& t1, T& t2);
Chris@16: }
Chris@16: 
Chris@16: template <typename T>
Chris@16: struct tree_node
Chris@16: {
Chris@16:     typedef T parse_node_t;
Chris@16:     
Chris@16: #if !defined(BOOST_SPIRIT_USE_BOOST_ALLOCATOR_FOR_TREES)
Chris@16:     typedef std::allocator<tree_node<T> > allocator_type;
Chris@16: #elif !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:     typedef boost::pool_allocator<tree_node<T> > allocator_type;
Chris@16: #else
Chris@16:     typedef boost::fast_pool_allocator<tree_node<T> > allocator_type;
Chris@16: #endif
Chris@16: 
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:     typedef std::vector<tree_node<T>, allocator_type> children_t;
Chris@16: #else
Chris@16:     typedef std::list<tree_node<T>, allocator_type> children_t;
Chris@16: #endif  // BOOST_SPIRIT_USE_LIST_FOR_TREES
Chris@16: 
Chris@16:     typedef typename children_t::iterator tree_iterator;
Chris@16:     typedef typename children_t::const_iterator const_tree_iterator;
Chris@16: 
Chris@16:     T value;
Chris@16:     children_t children;
Chris@16: 
Chris@16:     tree_node()
Chris@16:         : value()
Chris@16:         , children()
Chris@16:     {}
Chris@16: 
Chris@16:     explicit tree_node(T const& v)
Chris@16:         : value(v)
Chris@16:         , children()
Chris@16:     {}
Chris@16: 
Chris@16:     tree_node(T const& v, children_t const& c)
Chris@16:         : value(v)
Chris@16:         , children(c)
Chris@16:     {}
Chris@16: 
Chris@16:     void swap(tree_node<T>& x)
Chris@16:     {
Chris@16:         impl::cp_swap(value, x.value);
Chris@16:         impl::cp_swap(children, x.children);
Chris@16:     }
Chris@16: 
Chris@16: // Intel V5.0.1 has a problem without this explicit operator=
Chris@16:     tree_node &operator= (tree_node const &rhs)
Chris@16:     {
Chris@16:         tree_node(rhs).swap(*this);
Chris@16:         return *this;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16: template <typename T>
Chris@16: inline std::ostream&
Chris@16: operator<<(std::ostream& o, tree_node<T> const& n)
Chris@16: {
Chris@16:     static int depth = 0;
Chris@16:     o << "\n";
Chris@16:     for (int i = 0; i <= depth; ++i)
Chris@16:     {
Chris@16:         o << "\t";
Chris@16:     }
Chris@16:     o << "(depth = " << depth++ << " value = " << n.value;
Chris@16:     int c = 0;
Chris@16:     for (typename tree_node<T>::children_t::const_iterator it = n.children.begin();
Chris@16:          it != n.children.end(); ++it)
Chris@16:     {
Chris@16:         o << " children[" << c++ << "] = " << *it;
Chris@16:     }
Chris@16:     o << ")";
Chris@16:     --depth;
Chris@16:     return o;
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename IteratorT, typename ValueT>
Chris@16: struct node_iter_data
Chris@16: {
Chris@16:     typedef IteratorT iterator_t;
Chris@16:     typedef IteratorT /*const*/ const_iterator_t;
Chris@16: 
Chris@16:     node_iter_data()
Chris@16:         : first(), last(), is_root_(false), parser_id_(), value_()
Chris@16:         {}
Chris@16: 
Chris@16:     node_iter_data(IteratorT const& _first, IteratorT const& _last)
Chris@16:         : first(_first), last(_last), is_root_(false), parser_id_(), value_()
Chris@16:         {}
Chris@16: 
Chris@16:     void swap(node_iter_data& x)
Chris@16:     {
Chris@16:         impl::cp_swap(first, x.first);
Chris@16:         impl::cp_swap(last, x.last);
Chris@16:         impl::cp_swap(parser_id_, x.parser_id_);
Chris@16:         impl::cp_swap(is_root_, x.is_root_);
Chris@16:         impl::cp_swap(value_, x.value_);
Chris@16:     }
Chris@16: 
Chris@16:     IteratorT begin()
Chris@16:     {
Chris@16:         return first;
Chris@16:     }
Chris@16: 
Chris@16:     IteratorT const& begin() const
Chris@16:     {
Chris@16:         return first;
Chris@16:     }
Chris@16: 
Chris@16:     IteratorT end()
Chris@16:     {
Chris@16:         return last;
Chris@16:     }
Chris@16: 
Chris@16:     IteratorT const& end() const
Chris@16:     {
Chris@16:         return last;
Chris@16:     }
Chris@16: 
Chris@16:     bool is_root() const
Chris@16:     {
Chris@16:         return is_root_;
Chris@16:     }
Chris@16: 
Chris@16:     void is_root(bool b)
Chris@16:     {
Chris@16:         is_root_ = b;
Chris@16:     }
Chris@16: 
Chris@16:     parser_id id() const
Chris@16:     {
Chris@16:         return parser_id_;
Chris@16:     }
Chris@16: 
Chris@16:     void id(parser_id r)
Chris@16:     {
Chris@16:         parser_id_ = r;
Chris@16:     }
Chris@16: 
Chris@16:     ValueT const& value() const
Chris@16:     {
Chris@16:         return value_;
Chris@16:     }
Chris@16: 
Chris@16:     void value(ValueT const& v)
Chris@16:     {
Chris@16:         value_ = v;
Chris@16:     }
Chris@16: private:
Chris@16:     IteratorT first, last;
Chris@16:     bool is_root_;
Chris@16:     parser_id parser_id_;
Chris@16:     ValueT value_;
Chris@16: 
Chris@16: public:
Chris@16: };
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16: // value is default nil_t, so provide an operator<< for nil_t
Chris@16: inline std::ostream&
Chris@16: operator<<(std::ostream& o, nil_t const&)
Chris@16: {
Chris@16:     return o;
Chris@16: }
Chris@16: 
Chris@16: template <typename IteratorT, typename ValueT>
Chris@16: inline std::ostream&
Chris@16: operator<<(std::ostream& o, node_iter_data<IteratorT, ValueT> const& n)
Chris@16: {
Chris@16:     o << "(id = " << n.id() << " text = \"";
Chris@16:     typedef typename node_iter_data<IteratorT, ValueT>::const_iterator_t
Chris@16:         iterator_t;
Chris@16:     for (iterator_t it = n.begin(); it != n.end(); ++it)
Chris@16:         impl::token_printer(o, *it);
Chris@16:     o << "\" is_root = " << n.is_root()
Chris@16:         << /*" value = " << n.value() << */")";
Chris@16:     return o;
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename IteratorT = char const*, typename ValueT = nil_t>
Chris@16: struct node_val_data
Chris@16: {
Chris@16:     typedef
Chris@16:         typename boost::detail::iterator_traits<IteratorT>::value_type
Chris@16:         value_type;
Chris@16: 
Chris@16: #if !defined(BOOST_SPIRIT_USE_BOOST_ALLOCATOR_FOR_TREES)
Chris@16:     typedef std::allocator<value_type> allocator_type;
Chris@16: #elif !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:     typedef boost::pool_allocator<value_type> allocator_type;
Chris@16: #else
Chris@16:     typedef boost::fast_pool_allocator<value_type> allocator_type;
Chris@16: #endif
Chris@16: 
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:     typedef std::vector<value_type, allocator_type> container_t;
Chris@16: #else
Chris@16:     typedef std::list<value_type, allocator_type> container_t;
Chris@16: #endif
Chris@16: 
Chris@16:     typedef typename container_t::iterator iterator_t;
Chris@16:     typedef typename container_t::const_iterator const_iterator_t;
Chris@16: 
Chris@16:     node_val_data()
Chris@16:         : text(), is_root_(false), parser_id_(), value_()
Chris@16:         {}
Chris@16: 
Chris@16: #if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
Chris@16:     node_val_data(IteratorT const& _first, IteratorT const& _last)
Chris@16:         : text(), is_root_(false), parser_id_(), value_()
Chris@16:         {
Chris@16:             std::copy(_first, _last, std::inserter(text, text.end()));
Chris@16:         }
Chris@16: 
Chris@16:     // This constructor is for building text out of iterators
Chris@16:     template <typename IteratorT2>
Chris@16:     node_val_data(IteratorT2 const& _first, IteratorT2 const& _last)
Chris@16:         : text(), is_root_(false), parser_id_(), value_()
Chris@16:         {
Chris@16:             std::copy(_first, _last, std::inserter(text, text.end()));
Chris@16:         }
Chris@16: #else
Chris@16:     node_val_data(IteratorT const& _first, IteratorT const& _last)
Chris@16:         : text(_first, _last), is_root_(false), parser_id_(), value_()
Chris@16:         {}
Chris@16: 
Chris@16:     // This constructor is for building text out of iterators
Chris@16:     template <typename IteratorT2>
Chris@16:     node_val_data(IteratorT2 const& _first, IteratorT2 const& _last)
Chris@16:         : text(_first, _last), is_root_(false), parser_id_(), value_()
Chris@16:         {}
Chris@16: #endif
Chris@16: 
Chris@16:     void swap(node_val_data& x)
Chris@16:     {
Chris@16:         impl::cp_swap(text, x.text);
Chris@16:         impl::cp_swap(is_root_, x.is_root_);
Chris@16:         impl::cp_swap(parser_id_, x.parser_id_);
Chris@16:         impl::cp_swap(value_, x.value_);
Chris@16:     }
Chris@16: 
Chris@16:     typename container_t::iterator begin()
Chris@16:     {
Chris@16:         return text.begin();
Chris@16:     }
Chris@16: 
Chris@16:     typename container_t::const_iterator begin() const
Chris@16:     {
Chris@16:         return text.begin();
Chris@16:     }
Chris@16: 
Chris@16:     typename container_t::iterator end()
Chris@16:     {
Chris@16:         return text.end();
Chris@16:     }
Chris@16: 
Chris@16:     typename container_t::const_iterator end() const
Chris@16:     {
Chris@16:         return text.end();
Chris@16:     }
Chris@16: 
Chris@16:     bool is_root() const
Chris@16:     {
Chris@16:         return is_root_;
Chris@16:     }
Chris@16: 
Chris@16:     void is_root(bool b)
Chris@16:     {
Chris@16:         is_root_ = b;
Chris@16:     }
Chris@16: 
Chris@16:     parser_id id() const
Chris@16:     {
Chris@16:         return parser_id_;
Chris@16:     }
Chris@16: 
Chris@16:     void id(parser_id r)
Chris@16:     {
Chris@16:         parser_id_ = r;
Chris@16:     }
Chris@16: 
Chris@16:     ValueT const& value() const
Chris@16:     {
Chris@16:         return value_;
Chris@16:     }
Chris@16: 
Chris@16:     void value(ValueT const& v)
Chris@16:     {
Chris@16:         value_ = v;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     container_t text;
Chris@16:     bool is_root_;
Chris@16:     parser_id parser_id_;
Chris@16:     ValueT value_;
Chris@16: };
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16: template <typename IteratorT, typename ValueT>
Chris@16: inline std::ostream&
Chris@16: operator<<(std::ostream& o, node_val_data<IteratorT, ValueT> const& n)
Chris@16: {
Chris@16:     o << "(id = " << n.id() << " text = \"";
Chris@16:     typedef typename node_val_data<IteratorT, ValueT>::const_iterator_t
Chris@16:         iterator_t;
Chris@16:     for (iterator_t it = n.begin(); it != n.end(); ++it)
Chris@16:         impl::token_printer(o, *it);
Chris@16:     o << "\" is_root = " << n.is_root()
Chris@16:         << " value = " << n.value() << ")";
Chris@16:     return o;
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: template <typename T>
Chris@16: inline void
Chris@16: swap(tree_node<T>& a, tree_node<T>& b)
Chris@16: {
Chris@16:     a.swap(b);
Chris@16: }
Chris@16: 
Chris@16: template <typename T, typename V>
Chris@16: inline void
Chris@16: swap(node_iter_data<T, V>& a, node_iter_data<T, V>& b)
Chris@16: {
Chris@16:     a.swap(b);
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ValueT>
Chris@16: class node_iter_data_factory
Chris@16: {
Chris@16: public:
Chris@16:     // This inner class is so that node_iter_data_factory can simulate
Chris@16:     // a template template parameter
Chris@16:     template <typename IteratorT>
Chris@16:     class factory
Chris@16:     {
Chris@16:     public:
Chris@16:         typedef IteratorT iterator_t;
Chris@16:         typedef node_iter_data<iterator_t, ValueT> node_t;
Chris@16: 
Chris@16:         static node_t create_node(iterator_t const& first, iterator_t const& last,
Chris@16:                 bool /*is_leaf_node*/)
Chris@16:         {
Chris@16:             return node_t(first, last);
Chris@16:         }
Chris@16: 
Chris@16:         static node_t empty_node()
Chris@16:         {
Chris@16:             return node_t();
Chris@16:         }
Chris@16: 
Chris@16:         // precondition: ContainerT contains a tree_node<node_t>.  And all
Chris@16:         // iterators in the container point to the same sequence.
Chris@16:         template <typename ContainerT>
Chris@16:         static node_t group_nodes(ContainerT const& nodes)
Chris@16:         {
Chris@16:             return node_t(nodes.begin()->value.begin(),
Chris@16:                     nodes.back().value.end());
Chris@16:         }
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ValueT>
Chris@16: class node_val_data_factory 
Chris@16: {
Chris@16: public:
Chris@16:     // This inner class is so that node_val_data_factory can simulate
Chris@16:     // a template template parameter
Chris@16:     template <typename IteratorT>
Chris@16:     class factory
Chris@16:     {
Chris@16:     public:
Chris@16:         typedef IteratorT iterator_t;
Chris@16:         typedef node_val_data<iterator_t, ValueT> node_t;
Chris@16: 
Chris@16:         static node_t create_node(iterator_t const& first, iterator_t const& last,
Chris@16:                 bool is_leaf_node)
Chris@16:         {
Chris@16:             if (is_leaf_node)
Chris@16:                 return node_t(first, last);
Chris@16:             else
Chris@16:                 return node_t();
Chris@16:         }
Chris@16: 
Chris@16:         static node_t empty_node()
Chris@16:         {
Chris@16:             return node_t();
Chris@16:         }
Chris@16: 
Chris@16:         template <typename ContainerT>
Chris@16:         static node_t group_nodes(ContainerT const& nodes)
Chris@16:         {
Chris@16:             typename node_t::container_t c;
Chris@16:             typename ContainerT::const_iterator i_end = nodes.end();
Chris@16:             // copy all the nodes text into a new one
Chris@16:             for (typename ContainerT::const_iterator i = nodes.begin();
Chris@16:                  i != i_end; ++i)
Chris@16:             {
Chris@16:                 // See docs: reduced_node_d cannot be used with a
Chris@16:                 // rule inside the [].
Chris@16:                 BOOST_ASSERT(i->children.size() == 0);
Chris@16:                 c.insert(c.end(), i->value.begin(), i->value.end());
Chris@16:             }
Chris@16:             return node_t(c.begin(), c.end());
Chris@16:         }
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ValueT>
Chris@16: class node_all_val_data_factory
Chris@16: {
Chris@16: public:
Chris@16:     // This inner class is so that node_all_val_data_factory can simulate
Chris@16:     // a template template parameter
Chris@16:     template <typename IteratorT>
Chris@16:     class factory
Chris@16:     {
Chris@16:     public:
Chris@16:         typedef IteratorT iterator_t;
Chris@16:         typedef node_val_data<iterator_t, ValueT> node_t;
Chris@16: 
Chris@16:         static node_t create_node(iterator_t const& first, iterator_t const& last,
Chris@16:                 bool /*is_leaf_node*/)
Chris@16:         {
Chris@16:             return node_t(first, last);
Chris@16:         }
Chris@16: 
Chris@16:         static node_t empty_node()
Chris@16:         {
Chris@16:             return node_t();
Chris@16:         }
Chris@16: 
Chris@16:         template <typename ContainerT>
Chris@16:         static node_t group_nodes(ContainerT const& nodes)
Chris@16:         {
Chris@16:             typename node_t::container_t c;
Chris@16:             typename ContainerT::const_iterator i_end = nodes.end();
Chris@16:             // copy all the nodes text into a new one
Chris@16:             for (typename ContainerT::const_iterator i = nodes.begin();
Chris@16:                     i != i_end; ++i)
Chris@16:             {
Chris@16:                 BOOST_ASSERT(i->children.size() == 0);
Chris@16:                 c.insert(c.end(), i->value.begin(), i->value.end());
Chris@16:             }
Chris@16:             return node_t(c.begin(), c.end());
Chris@16:         }
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: namespace impl {
Chris@16: 
Chris@16:     ///////////////////////////////////////////////////////////////////////////
Chris@16:     // can't call unqualified swap from within classname::swap
Chris@16:     // as Koenig lookup rules will find only the classname::swap
Chris@16:     // member function not the global declaration, so use cp_swap
Chris@16:     // as a forwarding function (JM):
Chris@16:     template <typename T>
Chris@16:     inline void cp_swap(T& t1, T& t2)
Chris@16:     {
Chris@16:         using std::swap;
Chris@16:         using BOOST_SPIRIT_CLASSIC_NS::swap;
Chris@16:         using boost::swap;
Chris@16:         swap(t1, t2);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename IteratorT, typename NodeFactoryT, typename T>
Chris@16: class tree_match : public match<T>
Chris@16: {
Chris@16: public:
Chris@16: 
Chris@16:     typedef typename NodeFactoryT::template factory<IteratorT> node_factory_t;
Chris@16:     typedef typename node_factory_t::node_t parse_node_t;
Chris@16:     typedef tree_node<parse_node_t> node_t;
Chris@16:     typedef typename node_t::children_t container_t;
Chris@16:     typedef typename container_t::iterator tree_iterator;
Chris@16:     typedef typename container_t::const_iterator const_tree_iterator;
Chris@16: 
Chris@16:     typedef T attr_t;
Chris@16:     typedef typename boost::call_traits<T>::param_type      param_type;
Chris@16:     typedef typename boost::call_traits<T>::reference       reference;
Chris@16:     typedef typename boost::call_traits<T>::const_reference const_reference;
Chris@16: 
Chris@16:     tree_match()
Chris@16:     : match<T>(), trees()
Chris@16:     {}
Chris@16: 
Chris@16:     explicit
Chris@16:     tree_match(std::size_t length_)
Chris@16:     : match<T>(length_), trees()
Chris@16:     {}
Chris@16: 
Chris@16:     tree_match(std::size_t length_, parse_node_t const& n)
Chris@16:     : match<T>(length_), trees()
Chris@16:     { 
Chris@16:         trees.push_back(node_t(n)); 
Chris@16:     }
Chris@16: 
Chris@16:     tree_match(std::size_t length_, param_type val, parse_node_t const& n)
Chris@16:     : match<T>(length_, val), trees()
Chris@16:     {
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:         trees.reserve(10); // this is more or less an arbitrary number...
Chris@16: #endif
Chris@16:         trees.push_back(node_t(n));
Chris@16:     }
Chris@16: 
Chris@16:     // attention, these constructors will change the second parameter!
Chris@16:     tree_match(std::size_t length_, container_t& c)
Chris@16:     : match<T>(length_), trees()
Chris@16:     { 
Chris@16:         impl::cp_swap(trees, c);
Chris@16:     }
Chris@16: 
Chris@16:     tree_match(std::size_t length_, param_type val, container_t& c)
Chris@16:     : match<T>(length_, val), trees()
Chris@16:     {
Chris@16:         impl::cp_swap(trees, c);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T2>
Chris@16:     tree_match(match<T2> const& other)
Chris@16:     : match<T>(other), trees()
Chris@16:     {}
Chris@16: 
Chris@16:     template <typename T2, typename T3, typename T4>
Chris@16:     tree_match(tree_match<T2, T3, T4> const& other)
Chris@16:     : match<T>(other), trees()
Chris@16:     { impl::cp_swap(trees, other.trees); }
Chris@16: 
Chris@16:     template <typename T2>
Chris@16:     tree_match&
Chris@16:     operator=(match<T2> const& other)
Chris@16:     {
Chris@16:         match<T>::operator=(other);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T2, typename T3, typename T4>
Chris@16:     tree_match&
Chris@16:     operator=(tree_match<T2, T3, T4> const& other)
Chris@16:     {
Chris@16:         match<T>::operator=(other);
Chris@16:         impl::cp_swap(trees, other.trees);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     tree_match(tree_match const& x)
Chris@16:     : match<T>(x), trees()
Chris@16:     {
Chris@16:         // use auto_ptr like ownership for the trees data member
Chris@16:         impl::cp_swap(trees, x.trees);
Chris@16:     }
Chris@16: 
Chris@16:     tree_match& operator=(tree_match const& x)
Chris@16:     {
Chris@16:         tree_match tmp(x);
Chris@16:         this->swap(tmp);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     void swap(tree_match& x)
Chris@16:     {
Chris@16:         match<T>::swap(x);
Chris@16:         impl::cp_swap(trees, x.trees);
Chris@16:     }
Chris@16: 
Chris@16:     mutable container_t trees;
Chris@16: };
Chris@16: 
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16: template <typename IteratorT, typename NodeFactoryT, typename T>
Chris@16: inline std::ostream&
Chris@16: operator<<(std::ostream& o, tree_match<IteratorT, NodeFactoryT, T> const& m)
Chris@16: {
Chris@16:     typedef
Chris@16:         typename tree_match<IteratorT, NodeFactoryT, T>::container_t::iterator
Chris@16:         iterator;
Chris@16: 
Chris@16:     o << "(length = " << (int)m.length();
Chris@16:     int c = 0;
Chris@16:     for (iterator i = m.trees.begin(); i != m.trees.end(); ++i)
Chris@16:     {
Chris@16:         o << " trees[" << c++ << "] = " << *i;
Chris@16:     }
Chris@16:     o << "\n)";
Chris@16:     return o;
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: struct tree_policy
Chris@16: {
Chris@16:     template <typename FunctorT, typename MatchT>
Chris@16:     static void apply_op_to_match(FunctorT const& /*op*/, MatchT& /*m*/)
Chris@16:     {}
Chris@16: 
Chris@16:     template <typename MatchT, typename Iterator1T, typename Iterator2T>
Chris@16:     static void group_match(MatchT& /*m*/, parser_id const& /*id*/,
Chris@16:             Iterator1T const& /*first*/, Iterator2T const& /*last*/)
Chris@16:     {}
Chris@16: 
Chris@16:     template <typename MatchT>
Chris@16:     static void concat(MatchT& /*a*/, MatchT const& /*b*/)
Chris@16:     {}
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <
Chris@16:     typename MatchPolicyT,
Chris@16:     typename IteratorT,
Chris@16:     typename NodeFactoryT,
Chris@16:     typename TreePolicyT, 
Chris@16:     typename T
Chris@16: >
Chris@16: struct common_tree_match_policy : public match_policy
Chris@16: {
Chris@16:     common_tree_match_policy()
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     template <typename PolicyT>
Chris@16:     common_tree_match_policy(PolicyT const & policies)
Chris@16:         : match_policy((match_policy const &)policies)
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     template <typename U>
Chris@16:     struct result { typedef tree_match<IteratorT, NodeFactoryT, U> type; };
Chris@16: 
Chris@16:     typedef tree_match<IteratorT, NodeFactoryT, T> match_t;
Chris@16:     typedef IteratorT iterator_t;
Chris@16:     typedef TreePolicyT tree_policy_t;
Chris@16:     typedef NodeFactoryT factory_t;
Chris@16: 
Chris@16:     static const match_t no_match() { return match_t(); }
Chris@16:     static const match_t empty_match()
Chris@16:     { return match_t(0, tree_policy_t::empty_node()); }
Chris@16: 
Chris@16:     template <typename AttrT, typename Iterator1T, typename Iterator2T>
Chris@16:     static tree_match<IteratorT, NodeFactoryT, AttrT> create_match(
Chris@16:         std::size_t length,
Chris@16:         AttrT const& val,
Chris@16:         Iterator1T const& first,
Chris@16:         Iterator2T const& last)
Chris@16:     {
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16: 
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "\n>>> create_node(begin) <<<\n" 
Chris@16:             "creating node text: \"";
Chris@16:         for (Iterator1T it = first; it != last; ++it)
Chris@16:             impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "\"\n";
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << ">>> create_node(end) <<<\n\n"; 
Chris@16: #endif
Chris@16:         return tree_match<IteratorT, NodeFactoryT, AttrT>(length, val,
Chris@16:             tree_policy_t::create_node(length, first, last, true));
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Match1T, typename Match2T>
Chris@16:     static void concat_match(Match1T& a, Match2T const& b)
Chris@16:     {
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
Chris@16: 
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "\n>>> concat_match(begin) <<<\n";
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "tree a:\n" << a << "\n";
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "tree b:\n" << b << "\n";
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << ">>> concat_match(end) <<<\n\n";
Chris@16: #endif
Chris@16:         BOOST_SPIRIT_ASSERT(a && b);
Chris@16:         if (a.length() == 0)
Chris@16:         {
Chris@16:             a = b;
Chris@16:             return;
Chris@16:         }
Chris@16:         else if (b.length() == 0
Chris@16: #ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
Chris@16:             && !b.trees.begin()->value.id().to_long()
Chris@16: #endif
Chris@16:             )
Chris@16:         {
Chris@16:             return;
Chris@16:         }
Chris@16:         a.concat(b);
Chris@16:         tree_policy_t::concat(a, b);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MatchT, typename IteratorT2>
Chris@16:     void
Chris@16:     group_match(
Chris@16:         MatchT&             m,
Chris@16:         parser_id const&    id,
Chris@16:         IteratorT2 const&   first,
Chris@16:         IteratorT2 const&   last) const
Chris@16:     {
Chris@16:         if (!m) return;
Chris@16:         
Chris@16: #if defined(BOOST_SPIRIT_DEBUG) && \
Chris@16:     (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_TREES)
Chris@16: 
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "\n>>> group_match(begin) <<<\n"
Chris@16:             "new node(" << id << ") \"";
Chris@16:         for (IteratorT2 it = first; it != last; ++it)
Chris@16:             impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "\"\n";
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "new child tree (before grouping):\n" << m << "\n";
Chris@16: 
Chris@16:         tree_policy_t::group_match(m, id, first, last);
Chris@16: 
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << "new child tree (after grouping):\n" << m << "\n";
Chris@16:         BOOST_SPIRIT_DEBUG_OUT << ">>> group_match(end) <<<\n\n";
Chris@16: #else
Chris@16:         tree_policy_t::group_match(m, id, first, last);
Chris@16: #endif
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename MatchPolicyT, typename NodeFactoryT>
Chris@16: struct common_tree_tree_policy
Chris@16: {
Chris@16:     typedef typename MatchPolicyT::iterator_t iterator_t;
Chris@16:     typedef typename MatchPolicyT::match_t match_t;
Chris@16:     typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
Chris@16:     typedef typename factory_t::node_t node_t;
Chris@16: 
Chris@16:     template <typename Iterator1T, typename Iterator2T>
Chris@16:         static node_t
Chris@16:         create_node(std::size_t /*length*/, Iterator1T const& first,
Chris@16:             Iterator2T const& last, bool leaf_node)
Chris@16:     {
Chris@16:         return factory_t::create_node(first, last, leaf_node);
Chris@16:     }
Chris@16: 
Chris@16:     static node_t
Chris@16:         empty_node()
Chris@16:     {
Chris@16:         return factory_t::empty_node();
Chris@16:     }
Chris@16: 
Chris@16:     template <typename FunctorT>
Chris@16:         static void apply_op_to_match(FunctorT const& op, match_t& m)
Chris@16:     {
Chris@16:         op(m);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: // directives to modify how the parse tree is generated
Chris@16: 
Chris@16: struct no_tree_gen_node_parser_gen;
Chris@16: 
Chris@16: template <typename T>
Chris@16: struct no_tree_gen_node_parser
Chris@16: :   public unary<T, parser<no_tree_gen_node_parser<T> > >
Chris@16: {
Chris@16:     typedef no_tree_gen_node_parser<T> self_t;
Chris@16:     typedef no_tree_gen_node_parser_gen parser_generator_t;
Chris@16:     typedef unary_parser_category parser_category_t;
Chris@16: 
Chris@16:     no_tree_gen_node_parser(T const& a)
Chris@16:     : unary<T, parser<no_tree_gen_node_parser<T> > >(a) {}
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     typename parser_result<self_t, ScannerT>::type
Chris@16:     parse(ScannerT const& scanner) const
Chris@16:     {
Chris@16:         typedef typename ScannerT::iteration_policy_t iteration_policy_t;
Chris@16:         typedef match_policy match_policy_t;
Chris@16:         typedef typename ScannerT::action_policy_t action_policy_t;
Chris@16:         typedef scanner_policies<
Chris@16:             iteration_policy_t,
Chris@16:             match_policy_t,
Chris@16:             action_policy_t
Chris@16:         > policies_t;
Chris@16: 
Chris@16:         return this->subject().parse(scanner.change_policies(policies_t(scanner)));
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: struct no_tree_gen_node_parser_gen
Chris@16: {
Chris@16:     template <typename T>
Chris@16:     struct result {
Chris@16: 
Chris@16:         typedef no_tree_gen_node_parser<T> type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     static no_tree_gen_node_parser<T>
Chris@16:     generate(parser<T> const& s)
Chris@16:     {
Chris@16:         return no_tree_gen_node_parser<T>(s.derived());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     no_tree_gen_node_parser<T>
Chris@16:     operator[](parser<T> const& s) const
Chris@16:     {
Chris@16:         return no_tree_gen_node_parser<T>(s.derived());
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const no_tree_gen_node_parser_gen no_node_d = no_tree_gen_node_parser_gen();
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: 
Chris@16: struct leaf_node_parser_gen;
Chris@16: 
Chris@16: template<typename T>
Chris@16: struct leaf_node_parser
Chris@16: :   public unary<T, parser<leaf_node_parser<T> > >
Chris@16: {
Chris@16:     typedef leaf_node_parser<T> self_t;
Chris@16:     typedef leaf_node_parser_gen parser_generator_t;
Chris@16:     typedef unary_parser_category parser_category_t;
Chris@16: 
Chris@16:     leaf_node_parser(T const& a)
Chris@16:     : unary<T, parser<leaf_node_parser<T> > >(a) {}
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     typename parser_result<self_t, ScannerT>::type
Chris@16:     parse(ScannerT const& scanner) const
Chris@16:     {
Chris@16:         typedef scanner_policies< typename ScannerT::iteration_policy_t,
Chris@16:             match_policy, typename ScannerT::action_policy_t > policies_t;
Chris@16: 
Chris@16:         typedef typename ScannerT::iterator_t iterator_t;
Chris@16:         typedef typename parser_result<self_t, ScannerT>::type result_t;
Chris@16:         typedef typename result_t::node_factory_t factory_t;
Chris@16: 
Chris@16:         iterator_t from = scanner.first;
Chris@16:         result_t hit = impl::contiguous_parser_parse<result_t>(this->subject(),
Chris@16:             scanner.change_policies(policies_t(scanner,match_policy(),scanner)),
Chris@16:             scanner);
Chris@16: 
Chris@16:         if (hit)
Chris@16:             return result_t(hit.length(), 
Chris@16:                 factory_t::create_node(from, scanner.first, true));
Chris@16:         else
Chris@16:             return result_t(hit.length());
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: struct leaf_node_parser_gen
Chris@16: {
Chris@16:     template <typename T>
Chris@16:     struct result {
Chris@16: 
Chris@16:         typedef leaf_node_parser<T> type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     static leaf_node_parser<T>
Chris@16:     generate(parser<T> const& s)
Chris@16:     {
Chris@16:         return leaf_node_parser<T>(s.derived());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     leaf_node_parser<T>
Chris@16:     operator[](parser<T> const& s) const
Chris@16:     {
Chris@16:         return leaf_node_parser<T>(s.derived());
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const leaf_node_parser_gen leaf_node_d = leaf_node_parser_gen();
Chris@16: const leaf_node_parser_gen token_node_d = leaf_node_parser_gen();
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: namespace impl {
Chris@16: 
Chris@16:     template <typename MatchPolicyT>
Chris@16:     struct tree_policy_selector
Chris@16:     {
Chris@16:         typedef tree_policy type;
Chris@16:     };
Chris@16: 
Chris@16: } // namespace impl
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename NodeParserT>
Chris@16: struct node_parser_gen;
Chris@16: 
Chris@16: template <typename T, typename NodeParserT>
Chris@16: struct node_parser
Chris@16: :   public unary<T, parser<node_parser<T, NodeParserT> > >
Chris@16: {
Chris@16:     typedef node_parser<T, NodeParserT> self_t;
Chris@16:     typedef node_parser_gen<NodeParserT> parser_generator_t;
Chris@16:     typedef unary_parser_category parser_category_t;
Chris@16: 
Chris@16:     node_parser(T const& a)
Chris@16:     : unary<T, parser<node_parser<T, NodeParserT> > >(a) {}
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     struct result
Chris@16:     {
Chris@16:         typedef typename parser_result<T, ScannerT>::type type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     typename parser_result<self_t, ScannerT>::type
Chris@16:     parse(ScannerT const& scanner) const
Chris@16:     {
Chris@16:         typename parser_result<self_t, ScannerT>::type hit = this->subject().parse(scanner);
Chris@16:         if (hit)
Chris@16:         {
Chris@16:             impl::tree_policy_selector<typename ScannerT::match_policy_t>::type::apply_op_to_match(NodeParserT(), hit);
Chris@16:         }
Chris@16:         return hit;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename NodeParserT>
Chris@16: struct node_parser_gen
Chris@16: {
Chris@16:     template <typename T>
Chris@16:     struct result {
Chris@16: 
Chris@16:         typedef node_parser<T, NodeParserT> type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     static node_parser<T, NodeParserT>
Chris@16:     generate(parser<T> const& s)
Chris@16:     {
Chris@16:         return node_parser<T, NodeParserT>(s.derived());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     node_parser<T, NodeParserT>
Chris@16:     operator[](parser<T> const& s) const
Chris@16:     {
Chris@16:         return node_parser<T, NodeParserT>(s.derived());
Chris@16:     }
Chris@16: };
Chris@16: //////////////////////////////////
Chris@16: struct reduced_node_op
Chris@16: {
Chris@16:     template <typename MatchT>
Chris@16:     void operator()(MatchT& m) const
Chris@16:     {
Chris@16:         if (m.trees.size() == 1)
Chris@16:         {
Chris@16:             m.trees.begin()->children.clear();
Chris@16:         }
Chris@16:         else if (m.trees.size() > 1)
Chris@16:         {
Chris@16:             typedef typename MatchT::node_factory_t node_factory_t;
Chris@16:             m = MatchT(m.length(), node_factory_t::group_nodes(m.trees));
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const node_parser_gen<reduced_node_op> reduced_node_d =
Chris@16:     node_parser_gen<reduced_node_op>();
Chris@16: 
Chris@16: 
Chris@16: struct discard_node_op
Chris@16: {
Chris@16:     template <typename MatchT>
Chris@16:     void operator()(MatchT& m) const
Chris@16:     {
Chris@16:         m.trees.clear();
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const node_parser_gen<discard_node_op> discard_node_d =
Chris@16:     node_parser_gen<discard_node_op>();
Chris@16: 
Chris@16: struct infix_node_op
Chris@16: {
Chris@16:     template <typename MatchT>
Chris@16:     void operator()(MatchT& m) const
Chris@16:     {
Chris@16:         typedef typename MatchT::container_t container_t;
Chris@16:         typedef typename MatchT::container_t::iterator iter_t;
Chris@16:         typedef typename MatchT::container_t::value_type value_t;
Chris@16: 
Chris@16:         using std::swap;
Chris@16:         using boost::swap;
Chris@16:         using BOOST_SPIRIT_CLASSIC_NS::swap;
Chris@16: 
Chris@16:         // copying the tree nodes is expensive, since it may copy a whole
Chris@16:         // tree.  swapping them is cheap, so swap the nodes we want into
Chris@16:         // a new container of children.
Chris@16:         container_t new_children;
Chris@16:         std::size_t length = 0;
Chris@16:         std::size_t tree_size = m.trees.size();
Chris@16: 
Chris@16:         // the infix_node_d[] make no sense for nodes with no subnodes
Chris@16:         BOOST_SPIRIT_ASSERT(tree_size >= 1);
Chris@16: 
Chris@16:         bool keep = true;
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:         new_children.reserve((tree_size+1)/2);
Chris@16: #endif
Chris@16:         iter_t i_end = m.trees.end();
Chris@16:         for (iter_t i = m.trees.begin(); i != i_end; ++i)
Chris@16:         {
Chris@16:             if (keep) {
Chris@16:                 // adjust the length
Chris@16:                 length += std::distance((*i).value.begin(), (*i).value.end());
Chris@16: 
Chris@16:                 // move the child node
Chris@16:                 new_children.push_back(value_t());
Chris@16:                 swap(new_children.back(), *i);
Chris@16:                 keep = false;
Chris@16:             }
Chris@16:             else {
Chris@16:                 // ignore this child node
Chris@16:                 keep = true;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         m = MatchT(length, new_children);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const node_parser_gen<infix_node_op> infix_node_d =
Chris@16:     node_parser_gen<infix_node_op>();
Chris@16: 
Chris@16: struct discard_first_node_op
Chris@16: {
Chris@16:     template <typename MatchT>
Chris@16:     void operator()(MatchT& m) const
Chris@16:     {
Chris@16:         typedef typename MatchT::container_t container_t;
Chris@16:         typedef typename MatchT::container_t::iterator iter_t;
Chris@16:         typedef typename MatchT::container_t::value_type value_t;
Chris@16: 
Chris@16:         using std::swap;
Chris@16:         using boost::swap;
Chris@16:         using BOOST_SPIRIT_CLASSIC_NS::swap;
Chris@16: 
Chris@16:         // copying the tree nodes is expensive, since it may copy a whole
Chris@16:         // tree.  swapping them is cheap, so swap the nodes we want into
Chris@16:         // a new container of children, instead of saying
Chris@16:         // m.trees.erase(m.trees.begin()) because, on a container_t that will 
Chris@16:         // cause all the nodes afterwards to be copied into the previous 
Chris@16:         // position.
Chris@16:         container_t new_children;
Chris@16:         std::size_t length = 0;
Chris@16:         std::size_t tree_size = m.trees.size();
Chris@16: 
Chris@16:         // the discard_first_node_d[] make no sense for nodes with no subnodes
Chris@16:         BOOST_SPIRIT_ASSERT(tree_size >= 1);
Chris@16: 
Chris@16:         if (tree_size > 1) {
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:             new_children.reserve(tree_size - 1);
Chris@16: #endif
Chris@16:             iter_t i = m.trees.begin(), i_end = m.trees.end();
Chris@16:             for (++i; i != i_end; ++i)
Chris@16:             {
Chris@16:                 // adjust the length
Chris@16:                 length += std::distance((*i).value.begin(), (*i).value.end());
Chris@16: 
Chris@16:                 // move the child node
Chris@16:                 new_children.push_back(value_t());
Chris@16:                 swap(new_children.back(), *i);
Chris@16:             }
Chris@16:         }
Chris@16:         else {
Chris@16:         // if there was a tree and now there isn't any, insert an empty node
Chris@16:             iter_t i = m.trees.begin(); 
Chris@16: 
Chris@16:         // This isn't entirely correct, since the empty node will reference
Chris@16:         // the end of the discarded node, but I currently don't see any way to 
Chris@16:         // get at the begin of the node following this subnode.
Chris@16:         // This should be safe anyway because the it shouldn't get dereferenced
Chris@16:         // under any circumstances.
Chris@16:             typedef typename value_t::parse_node_t::iterator_t iterator_type;
Chris@16:             iterator_type it = (*i).value.end();
Chris@16:             
Chris@16:             new_children.push_back(
Chris@16:                 value_t(typename value_t::parse_node_t(it, it)));
Chris@16:         }
Chris@16:         
Chris@16:         m = MatchT(length, new_children);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const node_parser_gen<discard_first_node_op> discard_first_node_d =
Chris@16:     node_parser_gen<discard_first_node_op>();
Chris@16: 
Chris@16: struct discard_last_node_op
Chris@16: {
Chris@16:     template <typename MatchT>
Chris@16:     void operator()(MatchT& m) const
Chris@16:     {
Chris@16:         typedef typename MatchT::container_t container_t;
Chris@16:         typedef typename MatchT::container_t::iterator iter_t;
Chris@16:         typedef typename MatchT::container_t::value_type value_t;
Chris@16: 
Chris@16:         using std::swap;
Chris@16:         using boost::swap;
Chris@16:         using BOOST_SPIRIT_CLASSIC_NS::swap;
Chris@16: 
Chris@16:         // copying the tree nodes is expensive, since it may copy a whole
Chris@16:         // tree.  swapping them is cheap, so swap the nodes we want into
Chris@16:         // a new container of children, instead of saying
Chris@16:         // m.trees.erase(m.trees.begin()) because, on a container_t that will 
Chris@16:         // cause all the nodes afterwards to be copied into the previous 
Chris@16:         // position.
Chris@16:         container_t new_children;
Chris@16:         std::size_t length = 0;
Chris@16:         std::size_t tree_size = m.trees.size();
Chris@16: 
Chris@16:         // the discard_last_node_d[] make no sense for nodes with no subnodes
Chris@16:         BOOST_SPIRIT_ASSERT(tree_size >= 1);
Chris@16: 
Chris@16:         if (tree_size > 1) {
Chris@16:             m.trees.pop_back();
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:             new_children.reserve(tree_size - 1);
Chris@16: #endif            
Chris@16:             iter_t i_end = m.trees.end();
Chris@16:             for (iter_t i = m.trees.begin(); i != i_end; ++i)
Chris@16:             {
Chris@16:                 // adjust the length
Chris@16:                 length += std::distance((*i).value.begin(), (*i).value.end());
Chris@16: 
Chris@16:                 // move the child node
Chris@16:                 new_children.push_back(value_t());
Chris@16:                 swap(new_children.back(), *i);
Chris@16:             }
Chris@16:         }
Chris@16:         else {
Chris@16:         // if there was a tree and now there isn't any, insert an empty node
Chris@16:             iter_t i = m.trees.begin(); 
Chris@16: 
Chris@16:             typedef typename value_t::parse_node_t::iterator_t iterator_type;
Chris@16:             iterator_type it = (*i).value.begin();
Chris@16:             
Chris@16:             new_children.push_back(
Chris@16:                 value_t(typename value_t::parse_node_t(it, it)));
Chris@16:         }
Chris@16:         
Chris@16:         m = MatchT(length, new_children);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const node_parser_gen<discard_last_node_op> discard_last_node_d =
Chris@16:     node_parser_gen<discard_last_node_op>();
Chris@16: 
Chris@16: struct inner_node_op
Chris@16: {
Chris@16:     template <typename MatchT>
Chris@16:     void operator()(MatchT& m) const
Chris@16:     {
Chris@16:         typedef typename MatchT::container_t container_t;
Chris@16:         typedef typename MatchT::container_t::iterator iter_t;
Chris@16:         typedef typename MatchT::container_t::value_type value_t;
Chris@16: 
Chris@16:         using std::swap;
Chris@16:         using boost::swap;
Chris@16:         using BOOST_SPIRIT_CLASSIC_NS::swap;
Chris@16: 
Chris@16:         // copying the tree nodes is expensive, since it may copy a whole
Chris@16:         // tree.  swapping them is cheap, so swap the nodes we want into
Chris@16:         // a new container of children, instead of saying
Chris@16:         // m.trees.erase(m.trees.begin()) because, on a container_t that will 
Chris@16:         // cause all the nodes afterwards to be copied into the previous 
Chris@16:         // position.
Chris@16:         container_t new_children;
Chris@16:         std::size_t length = 0;
Chris@16:         std::size_t tree_size = m.trees.size();
Chris@16:         
Chris@16:         // the inner_node_d[] make no sense for nodes with less then 2 subnodes
Chris@16:         BOOST_SPIRIT_ASSERT(tree_size >= 2);
Chris@16: 
Chris@16:         if (tree_size > 2) {
Chris@16:             m.trees.pop_back(); // erase the last element
Chris@16: #if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)
Chris@16:             new_children.reserve(tree_size - 1);
Chris@16: #endif
Chris@16:             iter_t i = m.trees.begin(); // skip over the first element
Chris@16:             iter_t i_end = m.trees.end();
Chris@16:             for (++i; i != i_end; ++i)
Chris@16:             {
Chris@16:                 // adjust the length
Chris@16:                 length += std::distance((*i).value.begin(), (*i).value.end());
Chris@16:                 
Chris@16:                 // move the child node
Chris@16:                 new_children.push_back(value_t());
Chris@16:                 swap(new_children.back(), *i);
Chris@16:             }
Chris@16:         }
Chris@16:         else {
Chris@16:         // if there was a tree and now there isn't any, insert an empty node
Chris@16:             iter_t i = m.trees.begin(); // skip over the first element
Chris@16: 
Chris@16:             typedef typename value_t::parse_node_t::iterator_t iterator_type;
Chris@16:             iterator_type it = (*++i).value.begin();
Chris@16:             
Chris@16:             new_children.push_back(
Chris@16:                 value_t(typename value_t::parse_node_t(it, it)));
Chris@16:         }
Chris@16:         
Chris@16:         m = MatchT(length, new_children);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: const node_parser_gen<inner_node_op> inner_node_d =
Chris@16:     node_parser_gen<inner_node_op>();
Chris@16: 
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: // action_directive_parser and action_directive_parser_gen
Chris@16: // are meant to be used as a template to create directives that
Chris@16: // generate action classes.  For example access_match and
Chris@16: // access_node.  The ActionParserT template parameter must be
Chris@16: // a class that has an innter class called action that is templated
Chris@16: // on the parser type and the action type.
Chris@16: template <typename ActionParserT>
Chris@16: struct action_directive_parser_gen;
Chris@16: 
Chris@16: template <typename T, typename ActionParserT>
Chris@16: struct action_directive_parser
Chris@16: :   public unary<T, parser<action_directive_parser<T, ActionParserT> > >
Chris@16: {
Chris@16:     typedef action_directive_parser<T, ActionParserT> self_t;
Chris@16:     typedef action_directive_parser_gen<ActionParserT> parser_generator_t;
Chris@16:     typedef unary_parser_category parser_category_t;
Chris@16: 
Chris@16:     action_directive_parser(T const& a)
Chris@16:         : unary<T, parser<action_directive_parser<T, ActionParserT> > >(a) {}
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     struct result
Chris@16:     {
Chris@16:         typedef typename parser_result<T, ScannerT>::type type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     typename parser_result<self_t, ScannerT>::type
Chris@16:     parse(ScannerT const& scanner) const
Chris@16:     {
Chris@16:         return this->subject().parse(scanner);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename ActionT>
Chris@16:     typename ActionParserT::template action<action_directive_parser<T, ActionParserT>, ActionT>
Chris@16:     operator[](ActionT const& actor) const
Chris@16:     {
Chris@16:         typedef typename
Chris@16:             ActionParserT::template action<action_directive_parser, ActionT>
Chris@16:             action_t;
Chris@16:         return action_t(*this, actor);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ActionParserT>
Chris@16: struct action_directive_parser_gen
Chris@16: {
Chris@16:     template <typename T>
Chris@16:     struct result {
Chris@16: 
Chris@16:         typedef action_directive_parser<T, ActionParserT> type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     static action_directive_parser<T, ActionParserT>
Chris@16:     generate(parser<T> const& s)
Chris@16:     {
Chris@16:         return action_directive_parser<T, ActionParserT>(s.derived());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     action_directive_parser<T, ActionParserT>
Chris@16:     operator[](parser<T> const& s) const
Chris@16:     {
Chris@16:         return action_directive_parser<T, ActionParserT>(s.derived());
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: // Calls the attached action passing it the match from the parser
Chris@16: // and the first and last iterators.
Chris@16: // The inner template class is used to simulate template-template parameters
Chris@16: // (declared in common_fwd.hpp).
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: struct access_match_action::action
Chris@16: :   public unary<ParserT, parser<access_match_action::action<ParserT, ActionT> > >
Chris@16: {
Chris@16:     typedef action_parser_category parser_category;
Chris@16:     typedef action<ParserT, ActionT> self_t;
Chris@16:     
Chris@16:     template <typename ScannerT>
Chris@16:     struct result
Chris@16:     {
Chris@16:         typedef typename parser_result<ParserT, ScannerT>::type type;
Chris@16:     };
Chris@16: 
Chris@16:     action( ParserT const& subject,
Chris@16:             ActionT const& actor_);
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     typename parser_result<self_t, ScannerT>::type
Chris@16:     parse(ScannerT const& scanner) const;
Chris@16: 
Chris@16:     ActionT const &predicate() const;
Chris@16: 
Chris@16:     private:
Chris@16:     ActionT actor;
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: access_match_action::action<ParserT, ActionT>::action(
Chris@16:     ParserT const& subject,
Chris@16:     ActionT const& actor_)
Chris@16: : unary<ParserT, parser<access_match_action::action<ParserT, ActionT> > >(subject)
Chris@16: , actor(actor_)
Chris@16: {}
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: template <typename ScannerT>
Chris@16: typename parser_result<access_match_action::action<ParserT, ActionT>, ScannerT>::type
Chris@16: access_match_action::action<ParserT, ActionT>::
Chris@16: parse(ScannerT const& scan) const
Chris@16: {
Chris@16:     typedef typename ScannerT::iterator_t iterator_t;
Chris@16:     typedef typename parser_result<self_t, ScannerT>::type result_t;
Chris@16:     if (!scan.at_end())
Chris@16:     {
Chris@16:         iterator_t save = scan.first;
Chris@16:         result_t hit = this->subject().parse(scan);
Chris@16:         actor(hit, save, scan.first);
Chris@16:         return hit;
Chris@16:     }
Chris@16:     return scan.no_match();
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: ActionT const &access_match_action::action<ParserT, ActionT>::predicate() const
Chris@16: {
Chris@16:     return actor;
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: const action_directive_parser_gen<access_match_action> access_match_d
Chris@16:     = action_directive_parser_gen<access_match_action>();
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: // Calls the attached action passing it the node from the parser
Chris@16: // and the first and last iterators
Chris@16: // The inner template class is used to simulate template-template parameters
Chris@16: // (declared in common_fwd.hpp).
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: struct access_node_action::action
Chris@16: :   public unary<ParserT, parser<access_node_action::action<ParserT, ActionT> > >
Chris@16: {
Chris@16:     typedef action_parser_category parser_category;
Chris@16:     typedef action<ParserT, ActionT> self_t;
Chris@16:     
Chris@16:     template <typename ScannerT>
Chris@16:     struct result
Chris@16:     {
Chris@16:         typedef typename parser_result<ParserT, ScannerT>::type type;
Chris@16:     };
Chris@16: 
Chris@16:     action( ParserT const& subject,
Chris@16:             ActionT const& actor_);
Chris@16: 
Chris@16:     template <typename ScannerT>
Chris@16:     typename parser_result<self_t, ScannerT>::type
Chris@16:     parse(ScannerT const& scanner) const;
Chris@16: 
Chris@16:     ActionT const &predicate() const;
Chris@16: 
Chris@16:     private:
Chris@16:     ActionT actor;
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: access_node_action::action<ParserT, ActionT>::action(
Chris@16:     ParserT const& subject,
Chris@16:     ActionT const& actor_)
Chris@16: : unary<ParserT, parser<access_node_action::action<ParserT, ActionT> > >(subject)
Chris@16: , actor(actor_)
Chris@16: {}
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: template <typename ScannerT>
Chris@16: typename parser_result<access_node_action::action<ParserT, ActionT>, ScannerT>::type
Chris@16: access_node_action::action<ParserT, ActionT>::
Chris@16: parse(ScannerT const& scan) const
Chris@16: {
Chris@16:     typedef typename ScannerT::iterator_t iterator_t;
Chris@16:     typedef typename parser_result<self_t, ScannerT>::type result_t;
Chris@16:     if (!scan.at_end())
Chris@16:     {
Chris@16:         iterator_t save = scan.first;
Chris@16:         result_t hit = this->subject().parse(scan);
Chris@16:         if (hit && hit.trees.size() > 0)
Chris@16:             actor(*hit.trees.begin(), save, scan.first);
Chris@16:         return hit;
Chris@16:     }
Chris@16:     return scan.no_match();
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: template <typename ParserT, typename ActionT>
Chris@16: ActionT const &access_node_action::action<ParserT, ActionT>::predicate() const
Chris@16: {
Chris@16:     return actor;
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: const action_directive_parser_gen<access_node_action> access_node_d
Chris@16:     = action_directive_parser_gen<access_node_action>();
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: //////////////////////////////////
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: //  tree_parse_info
Chris@16: //
Chris@16: //      Results returned by the tree parse functions:
Chris@16: //
Chris@16: //      stop:   points to the final parse position (i.e parsing
Chris@16: //              processed the input up to this point).
Chris@16: //
Chris@16: //      match:  true if parsing is successful. This may be full:
Chris@16: //              the parser consumed all the input, or partial:
Chris@16: //              the parser consumed only a portion of the input.
Chris@16: //
Chris@16: //      full:   true when we have a full match (i.e the parser
Chris@16: //              consumed all the input.
Chris@16: //
Chris@16: //      length: The number of characters consumed by the parser.
Chris@16: //              This is valid only if we have a successful match
Chris@16: //              (either partial or full). A negative value means
Chris@16: //              that the match is unsucessful.
Chris@16: //
Chris@16: //     trees:   Contains the root node(s) of the tree.
Chris@16: //
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: template <
Chris@16:     typename IteratorT,
Chris@16:     typename NodeFactoryT,
Chris@16:     typename T
Chris@16: >
Chris@16: struct tree_parse_info 
Chris@16: {
Chris@16:     IteratorT   stop;
Chris@16:     bool        match;
Chris@16:     bool        full;
Chris@16:     std::size_t length;
Chris@16:     typename tree_match<IteratorT, NodeFactoryT, T>::container_t trees;
Chris@16: 
Chris@16:     tree_parse_info()
Chris@16:         : stop()
Chris@16:         , match(false)
Chris@16:         , full(false)
Chris@16:         , length(0)
Chris@16:         , trees()
Chris@16:     {}
Chris@16: 
Chris@16:     template <typename IteratorT2>
Chris@16:     tree_parse_info(tree_parse_info<IteratorT2> const& pi)
Chris@16:         : stop(pi.stop)
Chris@16:         , match(pi.match)
Chris@16:         , full(pi.full)
Chris@16:         , length(pi.length)
Chris@16:         , trees()
Chris@16:     {
Chris@16:         using std::swap;
Chris@16:         using boost::swap;
Chris@16:         using BOOST_SPIRIT_CLASSIC_NS::swap;
Chris@16: 
Chris@16:         // use auto_ptr like ownership for the trees data member
Chris@16:         swap(trees, pi.trees);
Chris@16:     }
Chris@16: 
Chris@16:     tree_parse_info(
Chris@16:         IteratorT   stop_,
Chris@16:         bool        match_,
Chris@16:         bool        full_,
Chris@16:         std::size_t length_,
Chris@16:         typename tree_match<IteratorT, NodeFactoryT, T>::container_t trees_)
Chris@16:     :   stop(stop_)
Chris@16:         , match(match_)
Chris@16:         , full(full_)
Chris@16:         , length(length_)
Chris@16:         , trees()
Chris@16:     {
Chris@16:         using std::swap;
Chris@16:         using boost::swap;
Chris@16:         using BOOST_SPIRIT_CLASSIC_NS::swap;
Chris@16: 
Chris@16:         // use auto_ptr like ownership for the trees data member
Chris@16:         swap(trees, trees_);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: BOOST_SPIRIT_CLASSIC_NAMESPACE_END
Chris@16: 
Chris@16: }} // namespace BOOST_SPIRIT_CLASSIC_NS
Chris@16: 
Chris@16: #endif
Chris@16: