parser/tree/node.hpp

0001 // node.hpp
0002 // Copyright (c) 2007-2009 Ben Hanson (http://www.benhanson.net/)
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0005 // file licence_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 #ifndef BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARSER_TREE_NODE_HPP
0007 #define BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARSER_TREE_NODE_HPP
0008
0009 #include <boost/assert.hpp>
0010 #include "../../containers/ptr_vector.hpp"
0011 #include "../../runtime_error.hpp"
0012 #include "../../size_t.hpp"
0013 #include <stack>
0014 #include <vector>
0015
0016 namespace boost
0017 {
0018 namespace lexer
0019 {
0020 namespace detail
0021 {
0022 class node
0023 {
0024 public:
0025     enum type {LEAF, SEQUENCE, SELECTION, ITERATION, END};
0026
0027     typedef std::stack<bool> bool_stack;
0028     typedef std::stack<node *> node_stack;
0029     // stack and vector not owner of node pointers
0030     typedef std::stack<const node *> const_node_stack;
0031     typedef std::vector<node *> node_vector;
0032     typedef ptr_vector<node> node_ptr_vector;
0033
0034     node () :
0035         _nullable (false)
0036     {
0037     }
0038
0039     node (const bool nullable_) :
0040         _nullable (nullable_)
0041     {
0042     }
0043
0044     virtual ~node ()
0045     {
0046     }
0047
0048     bool nullable () const
0049     {
0050         return _nullable;
0051     }
0052
0053     void append_firstpos (node_vector &firstpos_) const
0054     {
0055         firstpos_.insert (firstpos_.end (),
0056             _firstpos.begin (), _firstpos.end ());
0057     }
0058
0059     void append_lastpos (node_vector &lastpos_) const
0060     {
0061         lastpos_.insert (lastpos_.end (),
0062             _lastpos.begin (), _lastpos.end ());
0063     }
0064
0065     virtual void append_followpos (const node_vector &/*followpos_*/)
0066     {
0067         throw runtime_error ("Internal error node::append_followpos()");
0068     }
0069
0070     node *copy (node_ptr_vector &node_ptr_vector_) const
0071     {
0072         node *new_root_ = 0;
0073         const_node_stack node_stack_;
0074         bool_stack perform_op_stack_;
0075         bool down_ = true;
0076         node_stack new_node_stack_;
0077
0078         node_stack_.push (this);
0079
0080         while (!node_stack_.empty ())
0081         {
0082             while (down_)
0083             {
0084                 down_ = node_stack_.top ()->traverse (node_stack_,
0085                     perform_op_stack_);
0086             }
0087
0088             while (!down_ && !node_stack_.empty ())
0089             {
0090                 const node *top_ = node_stack_.top ();
0091
0092                 top_->copy_node (node_ptr_vector_, new_node_stack_,
0093                     perform_op_stack_, down_);
0094
0095                 if (!down_) node_stack_.pop ();
0096             }
0097         }
0098
0099         BOOST_ASSERT(new_node_stack_.size () == 1);
0100         new_root_ = new_node_stack_.top ();
0101         new_node_stack_.pop ();
0102         return new_root_;
0103     }
0104
0105     virtual type what_type () const = 0;
0106
0107     virtual bool traverse (const_node_stack &node_stack_,
0108         bool_stack &perform_op_stack_) const = 0;
0109
0110     node_vector &firstpos ()
0111     {
0112         return _firstpos;
0113     }
0114
0115     const node_vector &firstpos () const
0116     {
0117         return _firstpos;
0118     }
0119
0120     // _lastpos modified externally, so not const &
0121     node_vector &lastpos ()
0122     {
0123         return _lastpos;
0124     }
0125
0126     virtual bool end_state () const
0127     {
0128         return false;
0129     }
0130
0131     virtual std::size_t id () const
0132     {
0133         throw runtime_error ("Internal error node::id()");
0134     }
0135
0136     virtual std::size_t unique_id () const
0137     {
0138         throw runtime_error ("Internal error node::unique_id()");
0139     }
0140
0141     virtual std::size_t lexer_state () const
0142     {
0143         throw runtime_error ("Internal error node::state()");
0144     }
0145
0146     virtual std::size_t token () const
0147     {
0148         throw runtime_error ("Internal error node::token()");
0149     }
0150
0151     virtual void greedy (const bool /*greedy_*/)
0152     {
0153         throw runtime_error ("Internal error node::token(bool)");
0154     }
0155
0156     virtual bool greedy () const
0157     {
0158         throw runtime_error ("Internal error node::token()");
0159     }
0160
0161     virtual const node_vector &followpos () const
0162     {
0163         throw runtime_error ("Internal error node::followpos()");
0164     }
0165
0166     virtual node_vector &followpos ()
0167     {
0168         throw runtime_error ("Internal error node::followpos()");
0169     }
0170
0171 protected:
0172     const bool _nullable;
0173     node_vector _firstpos;
0174     node_vector _lastpos;
0175
0176     virtual void copy_node (node_ptr_vector &node_ptr_vector_,
0177         node_stack &new_node_stack_, bool_stack &perform_op_stack_,
0178         bool &down_) const = 0;
0179
0180 private:
0181     node (node const &); // No copy construction.
0182     node &operator = (node const &); // No assignment.
0183 };
0184 }
0185 }
0186 }
0187
0188 #endif