libstdc++
|
00001 // class template regex -*- C++ -*- 00002 00003 // Copyright (C) 2013-2015 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_automaton.tcc 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 namespace std _GLIBCXX_VISIBILITY(default) 00032 { 00033 namespace __detail 00034 { 00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00036 00037 #ifdef _GLIBCXX_DEBUG 00038 inline std::ostream& 00039 _State_base::_M_print(std::ostream& ostr) const 00040 { 00041 switch (_M_opcode) 00042 { 00043 case _S_opcode_alternative: 00044 case _S_opcode_repeat: 00045 ostr << "alt next=" << _M_next << " alt=" << _M_alt; 00046 break; 00047 case _S_opcode_subexpr_begin: 00048 ostr << "subexpr begin next=" << _M_next << " index=" << _M_subexpr; 00049 break; 00050 case _S_opcode_subexpr_end: 00051 ostr << "subexpr end next=" << _M_next << " index=" << _M_subexpr; 00052 break; 00053 case _S_opcode_backref: 00054 ostr << "backref next=" << _M_next << " index=" << _M_backref_index; 00055 break; 00056 case _S_opcode_match: 00057 ostr << "match next=" << _M_next; 00058 break; 00059 case _S_opcode_accept: 00060 ostr << "accept next=" << _M_next; 00061 break; 00062 default: 00063 ostr << "unknown next=" << _M_next; 00064 break; 00065 } 00066 return ostr; 00067 } 00068 00069 // Prints graphviz dot commands for state. 00070 inline std::ostream& 00071 _State_base::_M_dot(std::ostream& __ostr, _StateIdT __id) const 00072 { 00073 switch (_M_opcode) 00074 { 00075 case _S_opcode_alternative: 00076 case _S_opcode_repeat: 00077 __ostr << __id << " [label=\"" << __id << "\\nALT\"];\n" 00078 << __id << " -> " << _M_next 00079 << " [label=\"next\", tailport=\"s\"];\n" 00080 << __id << " -> " << _M_alt 00081 << " [label=\"alt\", tailport=\"n\"];\n"; 00082 break; 00083 case _S_opcode_backref: 00084 __ostr << __id << " [label=\"" << __id << "\\nBACKREF " 00085 << _M_subexpr << "\"];\n" 00086 << __id << " -> " << _M_next << " [label=\"<match>\"];\n"; 00087 break; 00088 case _S_opcode_line_begin_assertion: 00089 __ostr << __id << " [label=\"" << __id << "\\nLINE_BEGIN \"];\n" 00090 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; 00091 break; 00092 case _S_opcode_line_end_assertion: 00093 __ostr << __id << " [label=\"" << __id << "\\nLINE_END \"];\n" 00094 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; 00095 break; 00096 case _S_opcode_word_boundary: 00097 __ostr << __id << " [label=\"" << __id << "\\nWORD_BOUNDRY " 00098 << _M_neg << "\"];\n" 00099 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; 00100 break; 00101 case _S_opcode_subexpr_lookahead: 00102 __ostr << __id << " [label=\"" << __id << "\\nLOOK_AHEAD\"];\n" 00103 << __id << " -> " << _M_next 00104 << " [label=\"epsilon\", tailport=\"s\"];\n" 00105 << __id << " -> " << _M_alt 00106 << " [label=\"<assert>\", tailport=\"n\"];\n"; 00107 break; 00108 case _S_opcode_subexpr_begin: 00109 __ostr << __id << " [label=\"" << __id << "\\nSBEGIN " 00110 << _M_subexpr << "\"];\n" 00111 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; 00112 break; 00113 case _S_opcode_subexpr_end: 00114 __ostr << __id << " [label=\"" << __id << "\\nSEND " 00115 << _M_subexpr << "\"];\n" 00116 << __id << " -> " << _M_next << " [label=\"epsilon\"];\n"; 00117 break; 00118 case _S_opcode_dummy: 00119 break; 00120 case _S_opcode_match: 00121 __ostr << __id << " [label=\"" << __id << "\\nMATCH\"];\n" 00122 << __id << " -> " << _M_next << " [label=\"<match>\"];\n"; 00123 break; 00124 case _S_opcode_accept: 00125 __ostr << __id << " [label=\"" << __id << "\\nACC\"];\n" ; 00126 break; 00127 default: 00128 _GLIBCXX_DEBUG_ASSERT(false); 00129 break; 00130 } 00131 return __ostr; 00132 } 00133 00134 template<typename _TraitsT> 00135 std::ostream& 00136 _NFA<_TraitsT>::_M_dot(std::ostream& __ostr) const 00137 { 00138 __ostr << "digraph _Nfa {\n" 00139 " rankdir=LR;\n"; 00140 for (size_t __i = 0; __i < this->size(); ++__i) 00141 (*this)[__i]._M_dot(__ostr, __i); 00142 __ostr << "}\n"; 00143 return __ostr; 00144 } 00145 #endif 00146 00147 template<typename _TraitsT> 00148 _StateIdT 00149 _NFA<_TraitsT>::_M_insert_backref(size_t __index) 00150 { 00151 // To figure out whether a backref is valid, a stack is used to store 00152 // unfinished sub-expressions. For example, when parsing 00153 // "(a(b)(c\\1(d)))" at '\\1', _M_subexpr_count is 3, indicating that 3 00154 // sub expressions are parsed or partially parsed(in the stack), aka, 00155 // "(a..", "(b)" and "(c.."). 00156 // _M_paren_stack is {1, 3}, for incomplete "(a.." and "(c..". At this 00157 // time, "\\2" is valid, but "\\1" and "\\3" are not. 00158 if (__index >= _M_subexpr_count) 00159 __throw_regex_error(regex_constants::error_backref); 00160 for (auto __it : this->_M_paren_stack) 00161 if (__index == __it) 00162 __throw_regex_error(regex_constants::error_backref); 00163 this->_M_has_backref = true; 00164 _StateT __tmp(_S_opcode_backref); 00165 __tmp._M_backref_index = __index; 00166 return _M_insert_state(std::move(__tmp)); 00167 } 00168 00169 template<typename _TraitsT> 00170 void 00171 _NFA<_TraitsT>::_M_eliminate_dummy() 00172 { 00173 for (auto& __it : *this) 00174 { 00175 while (__it._M_next >= 0 && (*this)[__it._M_next]._M_opcode 00176 == _S_opcode_dummy) 00177 __it._M_next = (*this)[__it._M_next]._M_next; 00178 if (__it._M_opcode == _S_opcode_alternative 00179 || __it._M_opcode == _S_opcode_repeat 00180 || __it._M_opcode == _S_opcode_subexpr_lookahead) 00181 while (__it._M_alt >= 0 && (*this)[__it._M_alt]._M_opcode 00182 == _S_opcode_dummy) 00183 __it._M_alt = (*this)[__it._M_alt]._M_next; 00184 } 00185 } 00186 00187 // Just apply DFS on the sequence and re-link their links. 00188 template<typename _TraitsT> 00189 _StateSeq<_TraitsT> 00190 _StateSeq<_TraitsT>::_M_clone() 00191 { 00192 std::map<_StateIdT, _StateIdT> __m; 00193 std::stack<_StateIdT> __stack; 00194 __stack.push(_M_start); 00195 while (!__stack.empty()) 00196 { 00197 auto __u = __stack.top(); 00198 __stack.pop(); 00199 auto __dup = _M_nfa[__u]; 00200 // _M_insert_state() never return -1 00201 auto __id = _M_nfa._M_insert_state(__dup); 00202 __m[__u] = __id; 00203 if (__dup._M_opcode == _S_opcode_alternative 00204 || __dup._M_opcode == _S_opcode_repeat 00205 || __dup._M_opcode == _S_opcode_subexpr_lookahead) 00206 if (__dup._M_alt != _S_invalid_state_id 00207 && __m.count(__dup._M_alt) == 0) 00208 __stack.push(__dup._M_alt); 00209 if (__u == _M_end) 00210 continue; 00211 if (__dup._M_next != _S_invalid_state_id 00212 && __m.count(__dup._M_next) == 0) 00213 __stack.push(__dup._M_next); 00214 } 00215 for (auto __it : __m) 00216 { 00217 auto __v = __it.second; 00218 auto& __ref = _M_nfa[__v]; 00219 if (__ref._M_next != _S_invalid_state_id) 00220 { 00221 _GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_next) > 0); 00222 __ref._M_next = __m[__ref._M_next]; 00223 } 00224 if (__ref._M_opcode == _S_opcode_alternative 00225 || __ref._M_opcode == _S_opcode_repeat 00226 || __ref._M_opcode == _S_opcode_subexpr_lookahead) 00227 if (__ref._M_alt != _S_invalid_state_id) 00228 { 00229 _GLIBCXX_DEBUG_ASSERT(__m.count(__ref._M_alt) > 0); 00230 __ref._M_alt = __m[__ref._M_alt]; 00231 } 00232 } 00233 return _StateSeq(_M_nfa, __m[_M_start], __m[_M_end]); 00234 } 00235 00236 _GLIBCXX_END_NAMESPACE_VERSION 00237 } // namespace __detail 00238 } // namespace