libstdc++
|
00001 // class template regex -*- C++ -*- 00002 00003 // Copyright (C) 2013-2014 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** 00026 * @file bits/regex_executor.h 00027 * This is an internal header file, included by other library headers. 00028 * Do not attempt to use it directly. @headername{regex} 00029 */ 00030 00031 // FIXME convert comments to doxygen format. 00032 00033 namespace std _GLIBCXX_VISIBILITY(default) 00034 { 00035 namespace __detail 00036 { 00037 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00038 00039 /** 00040 * @addtogroup regex-detail 00041 * @{ 00042 */ 00043 00044 /** 00045 * @brief Takes a regex and an input string in and 00046 * do the matching. 00047 * 00048 * The %_Executor class has two modes: DFS mode and BFS mode, controlled 00049 * by the template parameter %__dfs_mode. 00050 */ 00051 template<typename _BiIter, typename _Alloc, typename _TraitsT, 00052 bool __dfs_mode> 00053 class _Executor 00054 { 00055 public: 00056 typedef typename iterator_traits<_BiIter>::value_type _CharT; 00057 typedef basic_regex<_CharT, _TraitsT> _RegexT; 00058 typedef std::vector<sub_match<_BiIter>, _Alloc> _ResultsVec; 00059 typedef regex_constants::match_flag_type _FlagT; 00060 typedef typename _TraitsT::char_class_type _ClassT; 00061 typedef _NFA<_TraitsT> _NFAT; 00062 00063 public: 00064 _Executor(_BiIter __begin, 00065 _BiIter __end, 00066 _ResultsVec& __results, 00067 const _RegexT& __re, 00068 _FlagT __flags) 00069 : _M_begin(__begin), 00070 _M_end(__end), 00071 _M_re(__re), 00072 _M_nfa(*__re._M_automaton), 00073 _M_results(__results), 00074 _M_match_queue(__dfs_mode ? nullptr 00075 : new vector<pair<_StateIdT, _ResultsVec>>()), 00076 _M_visited(__dfs_mode ? nullptr : new vector<bool>(_M_nfa.size())), 00077 _M_flags((__flags & regex_constants::match_prev_avail) 00078 ? (__flags 00079 & ~regex_constants::match_not_bol 00080 & ~regex_constants::match_not_bow) 00081 : __flags), 00082 _M_start_state(_M_nfa._M_start()) 00083 { } 00084 00085 // Set matched when string exactly match the pattern. 00086 bool 00087 _M_match() 00088 { 00089 _M_current = _M_begin; 00090 return _M_main<true>(); 00091 } 00092 00093 // Set matched when some prefix of the string matches the pattern. 00094 bool 00095 _M_search_from_first() 00096 { 00097 _M_current = _M_begin; 00098 return _M_main<false>(); 00099 } 00100 00101 bool 00102 _M_search(); 00103 00104 private: 00105 template<bool __match_mode> 00106 void 00107 _M_dfs(_StateIdT __start); 00108 00109 template<bool __match_mode> 00110 bool 00111 _M_main(); 00112 00113 bool 00114 _M_is_word(_CharT __ch) const 00115 { 00116 static const _CharT __s[2] = { 'w' }; 00117 return _M_re._M_traits.isctype 00118 (__ch, _M_re._M_traits.lookup_classname(__s, __s+1)); 00119 } 00120 00121 bool 00122 _M_at_begin() const 00123 { 00124 return _M_current == _M_begin 00125 && !(_M_flags & (regex_constants::match_not_bol 00126 | regex_constants::match_prev_avail)); 00127 } 00128 00129 bool 00130 _M_at_end() const 00131 { 00132 return _M_current == _M_end 00133 && !(_M_flags & regex_constants::match_not_eol); 00134 } 00135 00136 bool 00137 _M_word_boundary(_State<_TraitsT> __state) const; 00138 00139 bool 00140 _M_lookahead(_State<_TraitsT> __state); 00141 00142 public: 00143 _ResultsVec _M_cur_results; 00144 _BiIter _M_current; 00145 const _BiIter _M_begin; 00146 const _BiIter _M_end; 00147 const _RegexT& _M_re; 00148 const _NFAT& _M_nfa; 00149 _ResultsVec& _M_results; 00150 // Used in BFS, saving states that need to be considered for the next 00151 // character. 00152 std::unique_ptr<vector<pair<_StateIdT, _ResultsVec>>> _M_match_queue; 00153 // Used in BFS, indicating that which state is already visited. 00154 std::unique_ptr<vector<bool>> _M_visited; 00155 _FlagT _M_flags; 00156 // To record current solution. 00157 _StateIdT _M_start_state; 00158 // Do we have a solution so far? 00159 bool _M_has_sol; 00160 }; 00161 00162 //@} regex-detail 00163 _GLIBCXX_END_NAMESPACE_VERSION 00164 } // namespace __detail 00165 } // namespace std 00166 00167 #include <bits/regex_executor.tcc>