1// state_machine.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_STATE_MACHINE_HPP
7#define BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_STATE_MACHINE_HPP
8
9#include <algorithm>
10#include "conversion/char_state_machine.hpp"
11#include "consts.hpp"
12#include <deque>
13#include "internals.hpp"
14#include <map>
15#include "containers/ptr_vector.hpp"
16#include "size_t.hpp"
17#include <string>
18
19namespace boost
20{
21namespace lexer
22{
23template<typename CharT>
24class basic_state_machine
25{
26public:
27 typedef CharT char_type;
28
29 class iterator
30 {
31 public:
32 friend class basic_state_machine;
33
34 struct data
35 {
36 // Current iterator info
37 std::size_t dfa;
38 std::size_t states;
39 std::size_t state;
40 std::size_t transitions;
41 std::size_t transition;
42
43 // Current state info
44 bool end_state;
45 std::size_t id;
46 std::size_t unique_id;
47 std::size_t goto_dfa;
48 std::size_t bol_index;
49 std::size_t eol_index;
50
51 // Current transition info
52 basic_string_token<CharT> token;
53 std::size_t goto_state;
54
55 data () :
56 dfa (npos),
57 states (0),
58 state (npos),
59 transitions (0),
60 transition (npos),
61 end_state (false),
62 id (npos),
63 unique_id (npos),
64 goto_dfa (npos),
65 bol_index (npos),
66 eol_index (npos),
67 goto_state (npos)
68 {
69 }
70
71 bool operator == (const data &rhs_) const
72 {
73 return dfa == rhs_.dfa &&
74 states == rhs_.states &&
75 state == rhs_.state &&
76 transitions == rhs_.transitions &&
77 transition == rhs_.transition &&
78 end_state == rhs_.end_state &&
79 id == rhs_.id &&
80 unique_id == rhs_.unique_id &&
81 goto_dfa == rhs_.goto_dfa &&
82 bol_index == rhs_.bol_index &&
83 eol_index == rhs_.eol_index &&
84 token == rhs_.token &&
85 goto_state == rhs_.goto_state;
86 }
87 };
88
89 iterator () :
90 _sm (0),
91 _dfas (0),
92 _dfa (npos),
93 _states (0),
94 _state (npos),
95 _transitions (0),
96 _transition (npos)
97 {
98 }
99
100 bool operator == (const iterator &rhs_) const
101 {
102 return _dfas == rhs_._dfas && _dfa == rhs_._dfa &&
103 _states == rhs_._states && _state == rhs_._state &&
104 _transitions == rhs_._transitions &&
105 _transition == rhs_._transition;
106 }
107
108 bool operator != (const iterator &rhs_) const
109 {
110 return !(*this == rhs_);
111 }
112
113 data &operator * ()
114 {
115 return _data;
116 }
117
118 data *operator -> ()
119 {
120 return &_data;
121 }
122
123 // Let compiler generate operator = ().
124
125 // prefix version
126 iterator &operator ++ ()
127 {
128 next ();
129 return *this;
130 }
131
132 // postfix version
133 iterator operator ++ (int)
134 {
135 iterator iter_ = *this;
136
137 next ();
138 return iter_;
139 }
140
141 void clear ()
142 {
143 _dfas = _states = _transitions = 0;
144 _dfa = _state = _transition = npos;
145 }
146
147 private:
148 basic_state_machine *_sm;
149 data _data;
150 std::size_t _dfas;
151 std::size_t _dfa;
152 std::size_t _states;
153 std::size_t _state;
154 std::size_t _transitions;
155 std::size_t _transition;
156 typename detail::basic_char_state_machine<CharT>::state::
157 size_t_string_token_map::const_iterator _token_iter;
158 typename detail::basic_char_state_machine<CharT>::state::
159 size_t_string_token_map::const_iterator _token_end;
160
161 void next ()
162 {
163 bool reset_state_ = false;
164
165 if (_transition >= _transitions)
166 {
167 _transition = _data.transition = 0;
168 _data.state = ++_state;
169 reset_state_ = true;
170
171 if (_state >= _states)
172 {
173 ++_dfa;
174
175 if (_dfa >= _dfas)
176 {
177 clear ();
178 reset_state_ = false;
179 }
180 else
181 {
182 _states = _data.states =
183 _sm->_csm._sm_vector[_dfa].size ();
184 _state = _data.state = 0;
185 }
186 }
187 }
188 else
189 {
190 _data.transition = _transition;
191 }
192
193 if (reset_state_)
194 {
195 const typename detail::basic_char_state_machine<CharT>::
196 state *ptr_ = &_sm->_csm._sm_vector[_dfa][_state];
197
198 _transitions = _data.transitions = ptr_->_transitions.size ();
199 _data.end_state = ptr_->_end_state;
200 _data.id = ptr_->_id;
201 _data.unique_id = ptr_->_unique_id;
202 _data.goto_dfa = ptr_->_state;
203 _data.bol_index = ptr_->_bol_index;
204 _data.eol_index = ptr_->_eol_index;
205 _token_iter = ptr_->_transitions.begin ();
206 _token_end = ptr_->_transitions.end ();
207 }
208
209 if (_token_iter != _token_end)
210 {
211 _data.token = _token_iter->second;
212 _data.goto_state = _token_iter->first;
213 ++_token_iter;
214 ++_transition;
215 }
216 else
217 {
218 _data.token.clear ();
219 _data.goto_state = npos;
220 }
221 }
222 };
223
224 friend class iterator;
225
226 basic_state_machine ()
227 {
228 }
229
230 void clear ()
231 {
232 _internals.clear ();
233 _csm.clear ();
234 }
235
236 bool empty () const
237 {
238 // Don't include _csm in this test, as irrelevant to state.
239 return _internals._lookup->empty () &&
240 _internals._dfa_alphabet.empty () &&
241 _internals._dfa->empty ();
242 }
243
244 std::size_t size () const
245 {
246 return _internals._dfa->size ();
247 }
248
249 bool operator == (const basic_state_machine &rhs_) const
250 {
251 // Don't include _csm in this test, as irrelevant to state.
252 return _internals._lookup == rhs_._internals._lookup &&
253 _internals._dfa_alphabet == rhs_._internals._dfa_alphabet &&
254 _internals._dfa == rhs_._internals._dfa &&
255 _internals._seen_BOL_assertion ==
256 rhs_._internals._seen_BOL_assertion &&
257 _internals._seen_EOL_assertion ==
258 rhs_._internals._seen_EOL_assertion;
259 }
260
261 iterator begin () const
262 {
263 iterator iter_;
264
265 iter_._sm = const_cast<basic_state_machine *>(this);
266 check_for_csm ();
267
268 if (!_csm.empty ())
269 {
270 const typename detail::basic_char_state_machine<CharT>::
271 state_vector *ptr_ = &_csm._sm_vector.front ();
272
273 iter_._dfas = _csm._sm_vector.size ();
274 iter_._states = iter_._data.states = ptr_->size ();
275 iter_._transitions = iter_._data.transitions =
276 ptr_->front ()._transitions.size ();
277 iter_._dfa = iter_._data.dfa = 0;
278 iter_._state = iter_._data.state = 0;
279 iter_._transition = 0;
280 iter_._data.end_state = ptr_->front ()._end_state;
281 iter_._data.id = ptr_->front ()._id;
282 iter_._data.unique_id = ptr_->front ()._unique_id;
283 iter_._data.goto_dfa = ptr_->front ()._state;
284 iter_._data.bol_index = ptr_->front ()._bol_index;
285 iter_._data.eol_index = ptr_->front ()._eol_index;
286 iter_._token_iter = ptr_->front ()._transitions.begin ();
287 iter_._token_end = ptr_->front ()._transitions.end ();
288
289 // Deal with case where there is only a bol or eol
290 // but no other transitions.
291 if (iter_._transitions)
292 {
293 ++iter_;
294 }
295 }
296
297 return iter_;
298 }
299
300 iterator end () const
301 {
302 iterator iter_;
303
304 iter_._sm = const_cast<basic_state_machine *>(this);
305 return iter_;
306 }
307
308 void swap (basic_state_machine &sm_)
309 {
310 _internals.swap (internals_&: sm_._internals);
311 _csm.swap (sm_._csm);
312 }
313
314 const detail::internals &data () const
315 {
316 return _internals;
317 }
318
319private:
320 detail::internals _internals;
321 mutable detail::basic_char_state_machine<CharT> _csm;
322
323 void check_for_csm () const
324 {
325 if (_csm.empty ())
326 {
327 human_readable (sm_&: _csm);
328 }
329 }
330
331 void human_readable (detail::basic_char_state_machine<CharT> &sm_) const
332 {
333 const std::size_t max_ = sizeof (CharT) == 1 ?
334 num_chars : num_wchar_ts;
335 const std::size_t start_states_ = _internals._dfa->size ();
336
337 sm_.clear ();
338 sm_._sm_vector.resize (start_states_);
339
340 for (std::size_t start_state_index_ = 0;
341 start_state_index_ < start_states_; ++start_state_index_)
342 {
343 const detail::internals::size_t_vector *lu_ =
344 _internals._lookup[start_state_index_];
345 const std::size_t alphabet_ =
346 _internals._dfa_alphabet[start_state_index_] - dfa_offset;
347 std::vector<std::basic_string<CharT> > chars_ (alphabet_);
348 const std::size_t states_ = _internals._dfa[start_state_index_]->
349 size () / (alphabet_ + dfa_offset);
350 const std::size_t *read_ptr_ = &_internals.
351 _dfa[start_state_index_]->front () + alphabet_ + dfa_offset;
352
353 sm_._sm_vector[start_state_index_].resize (states_ - 1);
354
355 for (std::size_t alpha_index_ = 0; alpha_index_ < max_;
356 ++alpha_index_)
357 {
358 const std::size_t col_ = lu_->at (n: alpha_index_);
359
360 if (col_ != static_cast<std::size_t>(dead_state_index))
361 {
362 chars_[col_ - dfa_offset] += static_cast<CharT>
363 (alpha_index_);
364 }
365 }
366
367 for (std::size_t state_index_ = 1; state_index_ < states_;
368 ++state_index_)
369 {
370 typename detail::basic_char_state_machine<CharT>::state
371 *state_ = &sm_._sm_vector[start_state_index_]
372 [state_index_ - 1];
373
374 state_->_end_state = *read_ptr_ != 0;
375 state_->_id = *(read_ptr_ + id_index);
376 state_->_unique_id = *(read_ptr_ + unique_id_index);
377 state_->_state = *(read_ptr_ + state_index);
378 state_->_bol_index = *(read_ptr_ + bol_index) - 1;
379 state_->_eol_index = *(read_ptr_ + eol_index) - 1;
380 read_ptr_ += dfa_offset;
381
382 for (std::size_t col_index_ = 0; col_index_ < alphabet_;
383 ++col_index_, ++read_ptr_)
384 {
385 const std::size_t transition_ = *read_ptr_;
386
387 if (transition_ != 0)
388 {
389 const std::size_t i_ = transition_ - 1;
390 typename detail::basic_char_state_machine<CharT>::
391 state::size_t_string_token_map::iterator iter_ =
392 state_->_transitions.find (i_);
393
394 if (iter_ == state_->_transitions.end ())
395 {
396 basic_string_token<CharT> token_
397 (false, chars_[col_index_]);
398 typename detail::basic_char_state_machine<CharT>::
399 state::size_t_string_token_pair pair_
400 (i_, token_);
401
402 state_->_transitions.insert (pair_);
403 }
404 else
405 {
406 iter_->second._charset += chars_[col_index_];
407 }
408 }
409 }
410
411 for (typename detail::basic_char_state_machine<CharT>::state::
412 size_t_string_token_map::iterator iter_ =
413 state_->_transitions.begin (),
414 end_ = state_->_transitions.end ();
415 iter_ != end_; ++iter_)
416 {
417 std::sort (iter_->second._charset.begin (),
418 iter_->second._charset.end ());
419 iter_->second.normalise ();
420 }
421 }
422 }
423 }
424};
425
426typedef basic_state_machine<char> state_machine;
427typedef basic_state_machine<wchar_t> wstate_machine;
428}
429}
430
431#endif
432

source code of boost/libs/spirit/include/boost/spirit/home/support/detail/lexer/state_machine.hpp