1 // class template regex -*- C++ -*- 2 3 // Copyright (C) 2013-2014 Free Software Foundation, Inc. 4 // 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) 9 // any later version. 10 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. 15 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. 19 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/>. 24 25 /** 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} 29 */ 30 31 // FIXME convert comments to doxygen format. 32 33 namespace std _GLIBCXX_VISIBILITY(default) 34 { 35 namespace __detail 36 { 37 _GLIBCXX_BEGIN_NAMESPACE_VERSION 38 39 /** 40 * @addtogroup regex-detail 41 * @{ 42 */ 43 44 /** 45 * @brief Takes a regex and an input string in and 46 * do the matching. 47 * 48 * The %_Executor class has two modes: DFS mode and BFS mode, controlled 49 * by the template parameter %__dfs_mode. 50 */ 51 template<typename _BiIter, typename _Alloc, typename _TraitsT, 52 bool __dfs_mode> 53 class _Executor 54 { 55 public: 56 typedef typename iterator_traits<_BiIter>::value_type _CharT; 57 typedef basic_regex<_CharT, _TraitsT> _RegexT; 58 typedef std::vector<sub_match<_BiIter>, _Alloc> _ResultsVec; 59 typedef regex_constants::match_flag_type _FlagT; 60 typedef typename _TraitsT::char_class_type _ClassT; 61 typedef _NFA<_TraitsT> _NFAT; 62 63 public: 64 _Executor(_BiIter __begin, 65 _BiIter __end, 66 _ResultsVec& __results, 67 const _RegexT& __re, 68 _FlagT __flags) 69 : _M_begin(__begin), 70 _M_end(__end), 71 _M_re(__re), 72 _M_nfa(*__re._M_automaton), 73 _M_results(__results), 74 _M_match_queue(__dfs_mode ? nullptr 75 : new vector<pair<_StateIdT, _ResultsVec>>()), 76 _M_visited(__dfs_mode ? nullptr : new vector<bool>(_M_nfa.size())), 77 _M_flags((__flags & regex_constants::match_prev_avail) 78 ? (__flags 79 & ~regex_constants::match_not_bol 80 & ~regex_constants::match_not_bow) 81 : __flags), 82 _M_start_state(_M_nfa._M_start()) 83 { } 84 85 // Set matched when string exactly match the pattern. 86 bool 87 _M_match() 88 { 89 _M_current = _M_begin; 90 return _M_main<true>(); 91 } 92 93 // Set matched when some prefix of the string matches the pattern. 94 bool 95 _M_search_from_first() 96 { 97 _M_current = _M_begin; 98 return _M_main<false>(); 99 } 100 101 bool 102 _M_search(); 103 104 private: 105 template<bool __match_mode> 106 void 107 _M_dfs(_StateIdT __start); 108 109 template<bool __match_mode> 110 bool 111 _M_main(); 112 113 bool 114 _M_is_word(_CharT __ch) const 115 { 116 static const _CharT __s[2] = { 'w' }; 117 return _M_re._M_traits.isctype 118 (__ch, _M_re._M_traits.lookup_classname(__s, __s+1)); 119 } 120 121 bool 122 _M_at_begin() const 123 { 124 return _M_current == _M_begin 125 && !(_M_flags & (regex_constants::match_not_bol 126 | regex_constants::match_prev_avail)); 127 } 128 129 bool 130 _M_at_end() const 131 { 132 return _M_current == _M_end 133 && !(_M_flags & regex_constants::match_not_eol); 134 } 135 136 bool 137 _M_word_boundary(_State<_TraitsT> __state) const; 138 139 bool 140 _M_lookahead(_State<_TraitsT> __state); 141 142 public: 143 _ResultsVec _M_cur_results; 144 _BiIter _M_current; 145 const _BiIter _M_begin; 146 const _BiIter _M_end; 147 const _RegexT& _M_re; 148 const _NFAT& _M_nfa; 149 _ResultsVec& _M_results; 150 // Used in BFS, saving states that need to be considered for the next 151 // character. 152 std::unique_ptr<vector<pair<_StateIdT, _ResultsVec>>> _M_match_queue; 153 // Used in BFS, indicating that which state is already visited. 154 std::unique_ptr<vector<bool>> _M_visited; 155 _FlagT _M_flags; 156 // To record current solution. 157 _StateIdT _M_start_state; 158 // Do we have a solution so far? 159 bool _M_has_sol; 160 }; 161 162 //@} regex-detail 163 _GLIBCXX_END_NAMESPACE_VERSION 164 } // namespace __detail 165 } // namespace std 166 167 #include <bits/regex_executor.tcc> 168