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