1 // class template regex -*- C++ -*-
3 // Copyright (C) 2013-2014 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
26 * @file bits/regex_automaton.h
27 * This is an internal header file, included by other library headers.
28 * Do not attempt to use it directly. @headername{regex}
31 namespace std
_GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
38 * @defgroup regex-detail Base and Implementation Classes
43 typedef long _StateIdT
;
44 typedef std::set
<_StateIdT
> _StateSet
;
45 static const _StateIdT _S_invalid_state_id
= -1;
47 template<typename _CharT
>
48 using _Matcher
= std::function
<bool (_CharT
)>;
50 /// Operation codes that define the type of transitions within the base NFA
51 /// that represents the regular expression.
55 _S_opcode_alternative
,
57 _S_opcode_line_begin_assertion
,
58 _S_opcode_line_end_assertion
,
59 _S_opcode_word_boundary
,
60 _S_opcode_subexpr_lookahead
,
61 _S_opcode_subexpr_begin
,
62 _S_opcode_subexpr_end
,
70 _Opcode _M_opcode
; // type of outgoing transition
71 _StateIdT _M_next
; // outgoing transition
72 union // Since they are mutually exclusive.
74 size_t _M_subexpr
; // for _S_opcode_subexpr_*
75 size_t _M_backref_index
; // for _S_opcode_backref
78 // for _S_opcode_alternative.
79 _StateIdT _M_quant_index
;
80 // for _S_opcode_alternative or _S_opcode_subexpr_lookahead
82 // for _S_opcode_word_boundary or _S_opcode_subexpr_lookahead or
83 // quantifiers (ungreedy if set true)
88 explicit _State_base(_Opcode __opcode
)
89 : _M_opcode(__opcode
), _M_next(_S_invalid_state_id
)
93 ~_State_base() = default;
98 _M_print(std::ostream
& ostr
) const;
100 // Prints graphviz dot commands for state.
102 _M_dot(std::ostream
& __ostr
, _StateIdT __id
) const;
106 template<typename _TraitsT
>
107 struct _State
: _State_base
109 typedef _Matcher
<typename
_TraitsT::char_type
> _MatcherT
;
111 _MatcherT _M_matches
; // for _S_opcode_match
113 explicit _State(_Opcode __opcode
) : _State_base(__opcode
) { }
118 typedef size_t _SizeT
;
119 typedef regex_constants::syntax_option_type _FlagT
;
122 _NFA_base(_FlagT __f
)
123 : _M_flags(__f
), _M_start_state(0), _M_subexpr_count(0),
124 _M_quant_count(0), _M_has_backref(false)
127 _NFA_base(_NFA_base
&&) = default;
130 ~_NFA_base() = default;
139 { return _M_start_state
; }
142 _M_final_states() const
143 { return _M_accepting_states
; }
147 { return _M_subexpr_count
; }
149 std::vector
<size_t> _M_paren_stack
;
150 _StateSet _M_accepting_states
;
152 _StateIdT _M_start_state
;
153 _SizeT _M_subexpr_count
;
154 _SizeT _M_quant_count
;
158 template<typename _TraitsT
>
160 : _NFA_base
, std::vector
<_State
<_TraitsT
>>
162 typedef _State
<_TraitsT
> _StateT
;
163 typedef _Matcher
<typename
_TraitsT::char_type
> _MatcherT
;
165 using _NFA_base::_NFA_base
;
167 // for performance reasons _NFA objects should only be moved not copied
168 _NFA(const _NFA
&) = delete;
169 _NFA(_NFA
&&) = default;
174 auto __ret
= _M_insert_state(_StateT(_S_opcode_accept
));
175 this->_M_accepting_states
.insert(__ret
);
180 _M_insert_alt(_StateIdT __next
, _StateIdT __alt
, bool __neg
)
182 _StateT
__tmp(_S_opcode_alternative
);
183 // It labels every quantifier to make greedy comparison easier in BFS
185 __tmp
._M_quant_index
= this->_M_quant_count
++;
186 __tmp
._M_next
= __next
;
187 __tmp
._M_alt
= __alt
;
188 __tmp
._M_neg
= __neg
;
189 return _M_insert_state(std::move(__tmp
));
193 _M_insert_matcher(_MatcherT __m
)
195 _StateT
__tmp(_S_opcode_match
);
196 __tmp
._M_matches
= std::move(__m
);
197 return _M_insert_state(std::move(__tmp
));
201 _M_insert_subexpr_begin()
203 auto __id
= this->_M_subexpr_count
++;
204 this->_M_paren_stack
.push_back(__id
);
205 _StateT
__tmp(_S_opcode_subexpr_begin
);
206 __tmp
._M_subexpr
= __id
;
207 return _M_insert_state(std::move(__tmp
));
211 _M_insert_subexpr_end()
213 _StateT
__tmp(_S_opcode_subexpr_end
);
214 __tmp
._M_subexpr
= this->_M_paren_stack
.back();
215 this->_M_paren_stack
.pop_back();
216 return _M_insert_state(std::move(__tmp
));
220 _M_insert_backref(size_t __index
);
223 _M_insert_line_begin()
224 { return _M_insert_state(_StateT(_S_opcode_line_begin_assertion
)); }
228 { return _M_insert_state(_StateT(_S_opcode_line_end_assertion
)); }
231 _M_insert_word_bound(bool __neg
)
233 _StateT
__tmp(_S_opcode_word_boundary
);
234 __tmp
._M_neg
= __neg
;
235 return _M_insert_state(std::move(__tmp
));
239 _M_insert_lookahead(_StateIdT __alt
, bool __neg
)
241 _StateT
__tmp(_S_opcode_subexpr_lookahead
);
242 __tmp
._M_alt
= __alt
;
243 __tmp
._M_neg
= __neg
;
244 return _M_insert_state(std::move(__tmp
));
249 { return _M_insert_state(_StateT(_S_opcode_dummy
)); }
252 _M_insert_state(_StateT __s
)
254 this->push_back(std::move(__s
));
255 return this->size()-1;
258 // Eliminate dummy node in this NFA to make it compact.
260 _M_eliminate_dummy();
262 #ifdef _GLIBCXX_DEBUG
264 _M_dot(std::ostream
& __ostr
) const;
268 /// Describes a sequence of one or more %_State, its current start
269 /// and end(s). This structure contains fragments of an NFA during
271 template<typename _TraitsT
>
275 typedef _NFA
<_TraitsT
> _RegexT
;
278 _StateSeq(_RegexT
& __nfa
, _StateIdT __s
)
279 : _M_nfa(__nfa
), _M_start(__s
), _M_end(__s
)
282 _StateSeq(_RegexT
& __nfa
, _StateIdT __s
, _StateIdT __end
)
283 : _M_nfa(__nfa
), _M_start(__s
), _M_end(__end
)
286 // Append a state on *this and change *this to the new sequence.
288 _M_append(_StateIdT __id
)
290 _M_nfa
[_M_end
]._M_next
= __id
;
294 // Append a sequence on *this and change *this to the new sequence.
296 _M_append(const _StateSeq
& __s
)
298 _M_nfa
[_M_end
]._M_next
= __s
._M_start
;
302 // Clones an entire sequence.
313 _GLIBCXX_END_NAMESPACE_VERSION
314 } // namespace __detail
317 #include <bits/regex_automaton.tcc>