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_executor.h
27 * This is an internal header file, included by other library headers.
28 * Do not attempt to use it directly. @headername{regex}
31 // FIXME convert comments to doxygen format.
33 namespace std
_GLIBCXX_VISIBILITY(default)
37 _GLIBCXX_BEGIN_NAMESPACE_VERSION
40 * @addtogroup regex-detail
45 * @brief Takes a regex and an input string and does the matching.
47 * The %_Executor class has two modes: DFS mode and BFS mode, controlled
48 * by the template parameter %__dfs_mode.
50 template<typename _BiIter
, typename _Alloc
, typename _TraitsT
,
54 using __search_mode
= integral_constant
<bool, __dfs_mode
>;
55 using __dfs
= true_type
;
56 using __bfs
= false_type
;
58 enum class _Match_mode
: unsigned char { _Exact
, _Prefix
};
61 typedef typename iterator_traits
<_BiIter
>::value_type _CharT
;
62 typedef basic_regex
<_CharT
, _TraitsT
> _RegexT
;
63 typedef std::vector
<sub_match
<_BiIter
>, _Alloc
> _ResultsVec
;
64 typedef regex_constants::match_flag_type _FlagT
;
65 typedef typename
_TraitsT::char_class_type _ClassT
;
66 typedef _NFA
<_TraitsT
> _NFAT
;
69 _Executor(_BiIter __begin
,
71 _ResultsVec
& __results
,
77 _M_nfa(*__re
._M_automaton
),
78 _M_results(__results
),
79 _M_rep_count(_M_nfa
.size()),
80 _M_states(_M_nfa
._M_start(), _M_nfa
.size()),
81 _M_flags((__flags
& regex_constants::match_prev_avail
)
83 & ~regex_constants::match_not_bol
84 & ~regex_constants::match_not_bow
)
88 // Set matched when string exactly matches the pattern.
92 _M_current
= _M_begin
;
93 return _M_main(_Match_mode::_Exact
);
96 // Set matched when some prefix of the string matches the pattern.
98 _M_search_from_first()
100 _M_current
= _M_begin
;
101 return _M_main(_Match_mode::_Prefix
);
109 _M_rep_once_more(_Match_mode __match_mode
, _StateIdT
);
112 _M_dfs(_Match_mode __match_mode
, _StateIdT __start
);
115 _M_main(_Match_mode __match_mode
)
116 { return _M_main_dispatch(__match_mode
, __search_mode
{}); }
119 _M_main_dispatch(_Match_mode __match_mode
, __dfs
);
122 _M_main_dispatch(_Match_mode __match_mode
, __bfs
);
125 _M_is_word(_CharT __ch
) const
127 static const _CharT __s
[2] = { 'w' };
128 return _M_re
._M_automaton
->_M_traits
.isctype
129 (__ch
, _M_re
._M_automaton
->_M_traits
.lookup_classname(__s
, __s
+1));
135 return _M_current
== _M_begin
136 && !(_M_flags
& (regex_constants::match_not_bol
137 | regex_constants::match_prev_avail
));
143 return _M_current
== _M_end
144 && !(_M_flags
& regex_constants::match_not_eol
);
148 _M_word_boundary(_State
<_TraitsT
> __state
) const;
151 _M_lookahead(_State
<_TraitsT
> __state
);
153 // Holds additional information used in BFS-mode.
154 template<typename _SearchMode
, typename _ResultsVec
>
157 template<typename _ResultsVec
>
158 struct _State_info
<__bfs
, _ResultsVec
>
161 _State_info(_StateIdT __start
, size_t __n
)
162 : _M_visited_states(new bool[__n
]()), _M_start(__start
)
165 bool _M_visited(_StateIdT __i
)
167 if (_M_visited_states
[__i
])
169 _M_visited_states
[__i
] = true;
173 void _M_queue(_StateIdT __i
, const _ResultsVec
& __res
)
174 { _M_match_queue
.emplace_back(__i
, __res
); }
176 // Dummy implementations for BFS mode.
177 _BiIter
* _M_get_sol_pos() { return nullptr; }
179 // Saves states that need to be considered for the next character.
180 vector
<pair
<_StateIdT
, _ResultsVec
>> _M_match_queue
;
181 // Indicates which states are already visited.
182 unique_ptr
<bool[]> _M_visited_states
;
183 // To record current solution.
187 template<typename _ResultsVec
>
188 struct _State_info
<__dfs
, _ResultsVec
>
191 _State_info(_StateIdT __start
, size_t) : _M_start(__start
)
194 // Dummy implementations for DFS mode.
195 bool _M_visited(_StateIdT
) const { return false; }
196 void _M_queue(_StateIdT
, const _ResultsVec
&) { }
198 _BiIter
* _M_get_sol_pos() { return &_M_sol_pos
; }
200 // To record current solution.
206 _ResultsVec _M_cur_results
;
208 const _BiIter _M_begin
;
209 const _BiIter _M_end
;
210 const _RegexT
& _M_re
;
212 _ResultsVec
& _M_results
;
213 vector
<pair
<_BiIter
, int>> _M_rep_count
;
214 _State_info
<__search_mode
, _ResultsVec
> _M_states
;
216 // Do we have a solution so far?
221 _GLIBCXX_END_NAMESPACE_VERSION
222 } // namespace __detail
225 #include <bits/regex_executor.tcc>