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