1 // node.hpp
2 // Copyright (c) 2007-2009 Ben Hanson (http://www.benhanson.net/)
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file licence_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 #ifndef BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARSER_TREE_NODE_HPP
7 #define BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARSER_TREE_NODE_HPP
8 
9 #include <boost/assert.hpp>
10 #include "../../containers/ptr_vector.hpp"
11 #include "../../runtime_error.hpp"
12 #include "../../size_t.hpp"
13 #include <stack>
14 #include <vector>
15 
16 namespace boost
17 {
18 namespace lexer
19 {
20 namespace detail
21 {
22 class node
23 {
24 public:
25     enum type {LEAF, SEQUENCE, SELECTION, ITERATION, END};
26 
27     typedef std::stack<bool> bool_stack;
28     typedef std::stack<node *> node_stack;
29     // stack and vector not owner of node pointers
30     typedef std::stack<const node *> const_node_stack;
31     typedef std::vector<node *> node_vector;
32     typedef ptr_vector<node> node_ptr_vector;
33 
node()34     node () :
35         _nullable (false)
36     {
37     }
38 
node(const bool nullable_)39     node (const bool nullable_) :
40         _nullable (nullable_)
41     {
42     }
43 
~node()44     virtual ~node ()
45     {
46     }
47 
nullable() const48     bool nullable () const
49     {
50         return _nullable;
51     }
52 
append_firstpos(node_vector & firstpos_) const53     void append_firstpos (node_vector &firstpos_) const
54     {
55         firstpos_.insert (firstpos_.end (),
56             _firstpos.begin (), _firstpos.end ());
57     }
58 
append_lastpos(node_vector & lastpos_) const59     void append_lastpos (node_vector &lastpos_) const
60     {
61         lastpos_.insert (lastpos_.end (),
62             _lastpos.begin (), _lastpos.end ());
63     }
64 
append_followpos(const node_vector &)65     virtual void append_followpos (const node_vector &/*followpos_*/)
66     {
67         throw runtime_error ("Internal error node::append_followpos()");
68     }
69 
copy(node_ptr_vector & node_ptr_vector_) const70     node *copy (node_ptr_vector &node_ptr_vector_) const
71     {
72         node *new_root_ = 0;
73         const_node_stack node_stack_;
74         bool_stack perform_op_stack_;
75         bool down_ = true;
76         node_stack new_node_stack_;
77 
78         node_stack_.push (this);
79 
80         while (!node_stack_.empty ())
81         {
82             while (down_)
83             {
84                 down_ = node_stack_.top ()->traverse (node_stack_,
85                     perform_op_stack_);
86             }
87 
88             while (!down_ && !node_stack_.empty ())
89             {
90                 const node *top_ = node_stack_.top ();
91 
92                 top_->copy_node (node_ptr_vector_, new_node_stack_,
93                     perform_op_stack_, down_);
94 
95                 if (!down_) node_stack_.pop ();
96             }
97         }
98 
99         BOOST_ASSERT(new_node_stack_.size () == 1);
100         new_root_ = new_node_stack_.top ();
101         new_node_stack_.pop ();
102         return new_root_;
103     }
104 
105     virtual type what_type () const = 0;
106 
107     virtual bool traverse (const_node_stack &node_stack_,
108         bool_stack &perform_op_stack_) const = 0;
109 
firstpos()110     node_vector &firstpos ()
111     {
112         return _firstpos;
113     }
114 
firstpos() const115     const node_vector &firstpos () const
116     {
117         return _firstpos;
118     }
119 
120     // _lastpos modified externally, so not const &
lastpos()121     node_vector &lastpos ()
122     {
123         return _lastpos;
124     }
125 
end_state() const126     virtual bool end_state () const
127     {
128         return false;
129     }
130 
id() const131     virtual std::size_t id () const
132     {
133         throw runtime_error ("Internal error node::id()");
134     }
135 
unique_id() const136     virtual std::size_t unique_id () const
137     {
138         throw runtime_error ("Internal error node::unique_id()");
139     }
140 
lexer_state() const141     virtual std::size_t lexer_state () const
142     {
143         throw runtime_error ("Internal error node::state()");
144     }
145 
token() const146     virtual std::size_t token () const
147     {
148         throw runtime_error ("Internal error node::token()");
149     }
150 
greedy(const bool)151     virtual void greedy (const bool /*greedy_*/)
152     {
153         throw runtime_error ("Internal error node::token(bool)");
154     }
155 
greedy() const156     virtual bool greedy () const
157     {
158         throw runtime_error ("Internal error node::token()");
159     }
160 
followpos() const161     virtual const node_vector &followpos () const
162     {
163         throw runtime_error ("Internal error node::followpos()");
164     }
165 
followpos()166     virtual node_vector &followpos ()
167     {
168         throw runtime_error ("Internal error node::followpos()");
169     }
170 
171 protected:
172     const bool _nullable;
173     node_vector _firstpos;
174     node_vector _lastpos;
175 
176     virtual void copy_node (node_ptr_vector &node_ptr_vector_,
177         node_stack &new_node_stack_, bool_stack &perform_op_stack_,
178         bool &down_) const = 0;
179 
180 private:
181     node (node const &); // No copy construction.
182     node &operator = (node const &); // No assignment.
183 };
184 }
185 }
186 }
187 
188 #endif
189