@@ -42,8 +42,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
*/
/**
- * @brief Takes a regex and an input string in and
- * do the matching.
+ * @brief Takes a regex and an input string and does the matching.
*
* The %_Executor class has two modes: DFS mode and BFS mode, controlled
* by the template parameter %__dfs_mode.
@@ -52,6 +51,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool __dfs_mode>
class _Executor
{
+ using __search_mode = integral_constant<bool, __dfs_mode>;
+ using __dfs = true_type;
+ using __bfs = false_type;
+
public:
typedef typename iterator_traits<_BiIter>::value_type _CharT;
typedef basic_regex<_CharT, _TraitsT> _RegexT;
@@ -71,16 +74,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_re(__re),
_M_nfa(*__re._M_automaton),
_M_results(__results),
- _M_match_queue(__dfs_mode ? nullptr
- : new vector<pair<_StateIdT, _ResultsVec>>()),
_M_rep_count(_M_nfa.size()),
- _M_visited(__dfs_mode ? nullptr : new vector<bool>(_M_nfa.size())),
+ _M_states(_M_nfa._M_start(), _M_nfa.size()),
_M_flags((__flags & regex_constants::match_prev_avail)
? (__flags
& ~regex_constants::match_not_bol
& ~regex_constants::match_not_bow)
- : __flags),
- _M_start_state(_M_nfa._M_start())
+ : __flags)
{ }
// Set matched when string exactly match the pattern.
@@ -113,7 +113,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<bool __match_mode>
bool
- _M_main();
+ _M_main()
+ { return _M_main_dispatch<__match_mode>(__search_mode{}); }
+
+ template<bool __match_mode>
+ bool
+ _M_main_dispatch(__dfs);
+
+ template<bool __match_mode>
+ bool
+ _M_main_dispatch(__bfs);
bool
_M_is_word(_CharT __ch) const
@@ -144,6 +153,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool
_M_lookahead(_State<_TraitsT> __state);
+ // Holds additional information used in BFS-mode.
+ template<typename _SearchMode, typename _ResultsVec>
+ struct _State_info;
+
+ template<typename _ResultsVec>
+ struct _State_info<__bfs, _ResultsVec>
+ {
+ explicit
+ _State_info(_StateIdT __start, size_t __n)
+ : _M_start(__start), _M_visited_states(new bool[__n]())
+ { }
+
+ bool _M_visited(_StateIdT __i)
+ {
+ if (_M_visited_states[__i])
+ return true;
+ _M_visited_states[__i] = true;
+ return false;
+ }
+
+ void _M_queue(_StateIdT __i, const _ResultsVec& __res)
+ { _M_match_queue.emplace_back(__i, __res); }
+
+ // Saves states that need to be considered for the next character.
+ vector<pair<_StateIdT, _ResultsVec>> _M_match_queue;
+ // Indicates which states are already visited.
+ unique_ptr<bool[]> _M_visited_states;
+ // To record current solution.
+ _StateIdT _M_start;
+ };
+
+ template<typename _ResultsVec>
+ struct _State_info<__dfs, _ResultsVec>
+ {
+ explicit
+ _State_info(_StateIdT __start, size_t) : _M_start(__start)
+ { }
+
+ // Dummy implementations for DFS mode.
+ bool _M_visited(_StateIdT) const { return false; }
+ void _M_queue(_StateIdT, const _ResultsVec&) { }
+
+ // To record current solution.
+ _StateIdT _M_start;
+ };
+
+
public:
_ResultsVec _M_cur_results;
_BiIter _M_current;
@@ -152,15 +208,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const _RegexT& _M_re;
const _NFAT& _M_nfa;
_ResultsVec& _M_results;
- // Used in BFS, saving states that need to be considered for the next
- // character.
- unique_ptr<vector<pair<_StateIdT, _ResultsVec>>> _M_match_queue;
- // Used in BFS, indicating that which state is already visited.
vector<pair<_BiIter, int>> _M_rep_count;
- unique_ptr<vector<bool>> _M_visited;
+ _State_info<__search_mode, _ResultsVec> _M_states;
_FlagT _M_flags;
- // To record current solution.
- _StateIdT _M_start_state;
// Do we have a solution so far?
bool _M_has_sol;
};
@@ -35,7 +35,7 @@ namespace __detail
_GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_search()
{
@@ -53,8 +53,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return false;
}
- // This function operates in different modes, DFS mode or BFS mode, indicated
- // by template parameter __dfs_mode. See _M_main for details.
+ // The _M_main function operates in different modes, DFS mode or BFS mode,
+ // indicated by template parameter __dfs_mode, and dispatches to one of the
+ // _M_main_dispatch overloads.
//
// ------------------------------------------------------------
//
@@ -75,6 +76,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Time complexity: \Omega(match_length), O(2^(_M_nfa.size()))
// Space complexity: \theta(match_results.size() + match_length)
//
+ template<typename _BiIter, typename _Alloc, typename _TraitsT,
+ bool __dfs_mode>
+ template<bool __match_mode>
+ bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
+ _M_main_dispatch(__dfs)
+ {
+ _M_has_sol = false;
+ _M_cur_results = _M_results;
+ _M_dfs<__match_mode>(_M_states._M_start);
+ return _M_has_sol;
+ }
+
// ------------------------------------------------------------
//
// BFS mode:
@@ -84,11 +97,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
//
// It first computes epsilon closure (states that can be achieved without
// consuming characters) for every state that's still matching,
- // using the same DFS algorithm, but doesn't re-enter states (find a true in
- // _M_visited), nor follows _S_opcode_match.
+ // using the same DFS algorithm, but doesn't re-enter states (using
+ // _M_states._M_visited to check), nor follow _S_opcode_match.
//
- // Then apply DFS using every _S_opcode_match (in _M_match_queue) as the start
- // state.
+ // Then apply DFS using every _S_opcode_match (in _M_states._M_match_queue)
+ // as the start state.
//
// It significantly reduces potential duplicate states, so has a better
// upper bound; but it requires more overhead.
@@ -98,49 +111,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Space complexity: \Omega(_M_nfa.size() + match_results.size())
// O(_M_nfa.size() * match_results.size())
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
template<bool __match_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
- _M_main()
+ _M_main_dispatch(__bfs)
{
- if (__dfs_mode)
+ _M_states._M_queue(_M_states._M_start, _M_results);
+ bool __ret = false;
+ while (1)
{
_M_has_sol = false;
- _M_cur_results = _M_results;
- _M_dfs<__match_mode>(_M_start_state);
- return _M_has_sol;
- }
- else
- {
- _M_match_queue->push_back(make_pair(_M_start_state, _M_results));
- bool __ret = false;
- while (1)
+ if (_M_states._M_match_queue.empty())
+ break;
+ std::fill_n(_M_states._M_visited_states.get(), _M_nfa.size(), false);
+ auto __old_queue = std::move(_M_states._M_match_queue);
+ for (auto& __task : __old_queue)
{
- _M_has_sol = false;
- if (_M_match_queue->empty())
- break;
- _M_visited->assign(_M_visited->size(), false);
- auto _M_old_queue = std::move(*_M_match_queue);
- for (auto __task : _M_old_queue)
- {
- _M_cur_results = __task.second;
- _M_dfs<__match_mode>(__task.first);
- }
- if (!__match_mode)
- __ret |= _M_has_sol;
- if (_M_current == _M_end)
- break;
- ++_M_current;
+ _M_cur_results = std::move(__task.second);
+ _M_dfs<__match_mode>(__task.first);
}
- if (__match_mode)
- __ret = _M_has_sol;
- return __ret;
+ if (!__match_mode)
+ __ret |= _M_has_sol;
+ if (_M_current == _M_end)
+ break;
+ ++_M_current;
}
+ if (__match_mode)
+ __ret = _M_has_sol;
+ return __ret;
}
// Return whether now match the given sub-NFA.
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_lookahead(_State<_TraitsT> __state)
{
@@ -150,7 +153,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__what,
_M_re,
_M_flags));
- __sub->_M_start_state = __state._M_alt;
+ __sub->_M_states._M_start = __state._M_alt;
if (__sub->_M_search_from_first())
{
for (size_t __i = 0; __i < __what.size(); __i++)
@@ -195,17 +198,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
};
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
template<bool __match_mode>
void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_dfs(_StateIdT __i)
{
- if (!__dfs_mode)
- {
- if ((*_M_visited)[__i])
- return;
- (*_M_visited)[__i] = true;
- }
+ if (_M_states._M_visited(__i))
+ return;
const auto& __state = _M_nfa[__i];
// Every change on _M_cur_results and _M_current will be rolled back after
@@ -302,8 +301,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
if (__state._M_matches(*_M_current))
- _M_match_queue->push_back(make_pair(__state._M_next,
- _M_cur_results));
+ _M_states._M_queue(__state._M_next, _M_cur_results);
break;
// First fetch the matched result from _M_cur_results as __submatch;
// then compare it with
@@ -375,7 +373,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Return whether now is at some word boundary.
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_word_boundary(_State<_TraitsT> __state) const
{