1 // class template regex -*- C++ -*-
2
3 // Copyright (C) 2010-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_compiler.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
_GLIBCXX_VISIBILITY(default)31 namespace std _GLIBCXX_VISIBILITY(default)
32 {
33 namespace __detail
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36
37 /**
38 * @addtogroup regex-detail
39 * @{
40 */
41
42 template<typename, bool, bool>
43 struct _BracketMatcher;
44
45 /**
46 * @brief Builds an NFA from an input iterator interval.
47 *
48 * The %_TraitsT type should fulfill requirements [28.3].
49 */
50 template<typename _TraitsT>
51 class _Compiler
52 {
53 public:
54 typedef typename _TraitsT::char_type _CharT;
55 typedef const _CharT* _IterT;
56 typedef _NFA<_TraitsT> _RegexT;
57 typedef regex_constants::syntax_option_type _FlagT;
58
59 _Compiler(_IterT __b, _IterT __e,
60 const _TraitsT& __traits, _FlagT __flags);
61
62 std::shared_ptr<_RegexT>
63 _M_get_nfa()
64 { return make_shared<_RegexT>(std::move(_M_nfa)); }
65
66 private:
67 typedef _Scanner<_CharT> _ScannerT;
68 typedef typename _TraitsT::string_type _StringT;
69 typedef typename _ScannerT::_TokenT _TokenT;
70 typedef _StateSeq<_TraitsT> _StateSeqT;
71 typedef std::stack<_StateSeqT> _StackT;
72 typedef std::ctype<_CharT> _CtypeT;
73
74 // accepts a specific token or returns false.
75 bool
76 _M_match_token(_TokenT __token);
77
78 void
79 _M_disjunction();
80
81 void
82 _M_alternative();
83
84 bool
85 _M_term();
86
87 bool
88 _M_assertion();
89
90 bool
91 _M_quantifier();
92
93 bool
94 _M_atom();
95
96 bool
97 _M_bracket_expression();
98
99 template<bool __icase, bool __collate>
100 void
101 _M_insert_any_matcher_ecma();
102
103 template<bool __icase, bool __collate>
104 void
105 _M_insert_any_matcher_posix();
106
107 template<bool __icase, bool __collate>
108 void
109 _M_insert_char_matcher();
110
111 template<bool __icase, bool __collate>
112 void
113 _M_insert_character_class_matcher();
114
115 template<bool __icase, bool __collate>
116 void
117 _M_insert_bracket_matcher(bool __neg);
118
119 template<bool __icase, bool __collate>
120 void
121 _M_expression_term(_BracketMatcher<_TraitsT, __icase, __collate>&
122 __matcher);
123
124 int
125 _M_cur_int_value(int __radix);
126
127 bool
128 _M_try_char();
129
130 _StateSeqT
131 _M_pop()
132 {
133 auto ret = _M_stack.top();
134 _M_stack.pop();
135 return ret;
136 }
137
138 _FlagT _M_flags;
139 const _TraitsT& _M_traits;
140 const _CtypeT& _M_ctype;
141 _ScannerT _M_scanner;
142 _RegexT _M_nfa;
143 _StringT _M_value;
144 _StackT _M_stack;
145 };
146
147 template<typename _TraitsT>
148 inline std::shared_ptr<_NFA<_TraitsT>>
149 __compile_nfa(const typename _TraitsT::char_type* __first,
150 const typename _TraitsT::char_type* __last,
151 const _TraitsT& __traits,
152 regex_constants::syntax_option_type __flags)
153 {
154 using _Cmplr = _Compiler<_TraitsT>;
155 return _Cmplr(__first, __last, __traits, __flags)._M_get_nfa();
156 }
157
158 // [28.13.14]
159 template<typename _TraitsT, bool __icase, bool __collate>
160 class _RegexTranslator
161 {
162 public:
163 typedef typename _TraitsT::char_type _CharT;
164 typedef typename _TraitsT::string_type _StringT;
165 typedef typename std::conditional<__collate,
166 _StringT,
167 _CharT>::type _StrTransT;
168
169 explicit
170 _RegexTranslator(const _TraitsT& __traits)
171 : _M_traits(__traits)
172 { }
173
174 _CharT
175 _M_translate(_CharT __ch) const
176 {
177 if (__icase)
178 return _M_traits.translate_nocase(__ch);
179 else if (__collate)
180 return _M_traits.translate(__ch);
181 else
182 return __ch;
183 }
184
185 _StrTransT
186 _M_transform(_CharT __ch) const
187 {
188 return _M_transform_impl(__ch, typename integral_constant<bool,
189 __collate>::type());
190 }
191
192 private:
193 _StrTransT
194 _M_transform_impl(_CharT __ch, false_type) const
195 { return __ch; }
196
197 _StrTransT
198 _M_transform_impl(_CharT __ch, true_type) const
199 {
200 _StrTransT __str = _StrTransT(1, _M_translate(__ch));
201 return _M_traits.transform(__str.begin(), __str.end());
202 }
203
204 const _TraitsT& _M_traits;
205 };
206
207 template<typename _TraitsT>
208 class _RegexTranslator<_TraitsT, false, false>
209 {
210 public:
211 typedef typename _TraitsT::char_type _CharT;
212 typedef _CharT _StrTransT;
213
214 explicit
215 _RegexTranslator(const _TraitsT& __traits)
216 { }
217
218 _CharT
219 _M_translate(_CharT __ch) const
220 { return __ch; }
221
222 _StrTransT
223 _M_transform(_CharT __ch) const
224 { return __ch; }
225 };
226
227 template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
228 struct _AnyMatcher;
229
230 template<typename _TraitsT, bool __icase, bool __collate>
231 struct _AnyMatcher<_TraitsT, false, __icase, __collate>
232 {
233 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
234 typedef typename _TransT::_CharT _CharT;
235
236 explicit
237 _AnyMatcher(const _TraitsT& __traits)
238 : _M_translator(__traits)
239 { }
240
241 bool
242 operator()(_CharT __ch) const
243 {
244 static auto __nul = _M_translator._M_translate('\0');
245 return _M_translator._M_translate(__ch) != __nul;
246 }
247
248 _TransT _M_translator;
249 };
250
251 template<typename _TraitsT, bool __icase, bool __collate>
252 struct _AnyMatcher<_TraitsT, true, __icase, __collate>
253 {
254 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
255 typedef typename _TransT::_CharT _CharT;
256
257 explicit
258 _AnyMatcher(const _TraitsT& __traits)
259 : _M_translator(__traits)
260 { }
261
262 bool
263 operator()(_CharT __ch) const
264 { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
265
266 bool
267 _M_apply(_CharT __ch, true_type) const
268 {
269 auto __c = _M_translator._M_translate(__ch);
270 auto __n = _M_translator._M_translate('\n');
271 auto __r = _M_translator._M_translate('\r');
272 return __c != __n && __c != __r;
273 }
274
275 bool
276 _M_apply(_CharT __ch, false_type) const
277 {
278 auto __c = _M_translator._M_translate(__ch);
279 auto __n = _M_translator._M_translate('\n');
280 auto __r = _M_translator._M_translate('\r');
281 auto __u2028 = _M_translator._M_translate(u'\u2028');
282 auto __u2029 = _M_translator._M_translate(u'\u2029');
283 return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
284 }
285
286 _TransT _M_translator;
287 };
288
289 template<typename _TraitsT, bool __icase, bool __collate>
290 struct _CharMatcher
291 {
292 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
293 typedef typename _TransT::_CharT _CharT;
294
295 _CharMatcher(_CharT __ch, const _TraitsT& __traits)
296 : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
297 { }
298
299 bool
300 operator()(_CharT __ch) const
301 { return _M_ch == _M_translator._M_translate(__ch); }
302
303 _TransT _M_translator;
304 _CharT _M_ch;
305 };
306
307 /// Matches a character range (bracket expression)
308 template<typename _TraitsT, bool __icase, bool __collate>
309 struct _BracketMatcher
310 {
311 public:
312 typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
313 typedef typename _TransT::_CharT _CharT;
314 typedef typename _TransT::_StrTransT _StrTransT;
315 typedef typename _TraitsT::string_type _StringT;
316 typedef typename _TraitsT::char_class_type _CharClassT;
317
318 public:
319 _BracketMatcher(bool __is_non_matching,
320 const _TraitsT& __traits)
321 : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
322 _M_is_non_matching(__is_non_matching)
323 #ifdef _GLIBCXX_DEBUG
324 , _M_is_ready(false)
325 #endif
326 { }
327
328 bool
329 operator()(_CharT __ch) const
330 {
331 _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
332 return _M_apply(__ch, _IsChar());
333 }
334
335 void
336 _M_add_char(_CharT __c)
337 {
338 _M_char_set.push_back(_M_translator._M_translate(__c));
339 #ifdef _GLIBCXX_DEBUG
340 _M_is_ready = false;
341 #endif
342 }
343
344 void
345 _M_add_collating_element(const _StringT& __s)
346 {
347 auto __st = _M_traits.lookup_collatename(__s.data(),
348 __s.data() + __s.size());
349 if (__st.empty())
350 __throw_regex_error(regex_constants::error_collate);
351 _M_char_set.push_back(_M_translator._M_translate(__st[0]));
352 #ifdef _GLIBCXX_DEBUG
353 _M_is_ready = false;
354 #endif
355 }
356
357 void
358 _M_add_equivalence_class(const _StringT& __s)
359 {
360 auto __st = _M_traits.lookup_collatename(__s.data(),
361 __s.data() + __s.size());
362 if (__st.empty())
363 __throw_regex_error(regex_constants::error_collate);
364 __st = _M_traits.transform_primary(__st.data(),
365 __st.data() + __st.size());
366 _M_equiv_set.push_back(__st);
367 #ifdef _GLIBCXX_DEBUG
368 _M_is_ready = false;
369 #endif
370 }
371
372 // __neg should be true for \D, \S and \W only.
373 void
374 _M_add_character_class(const _StringT& __s, bool __neg)
375 {
376 auto __mask = _M_traits.lookup_classname(__s.data(),
377 __s.data() + __s.size(),
378 __icase);
379 if (__mask == 0)
380 __throw_regex_error(regex_constants::error_ctype);
381 if (!__neg)
382 _M_class_set |= __mask;
383 else
384 _M_neg_class_set.push_back(__mask);
385 #ifdef _GLIBCXX_DEBUG
386 _M_is_ready = false;
387 #endif
388 }
389
390 void
391 _M_make_range(_CharT __l, _CharT __r)
392 {
393 _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
394 _M_translator._M_transform(__r)));
395 #ifdef _GLIBCXX_DEBUG
396 _M_is_ready = false;
397 #endif
398 }
399
400 void
401 _M_ready()
402 {
403 _M_make_cache(_IsChar());
404 #ifdef _GLIBCXX_DEBUG
405 _M_is_ready = true;
406 #endif
407 }
408
409 private:
410 typedef typename is_same<_CharT, char>::type _IsChar;
411 struct _Dummy { };
412 typedef typename conditional<_IsChar::value,
413 std::bitset<1 << (8 * sizeof(_CharT))>,
414 _Dummy>::type _CacheT;
415 typedef typename make_unsigned<_CharT>::type _UnsignedCharT;
416
417 private:
418 bool
419 _M_apply(_CharT __ch, false_type) const;
420
421 bool
422 _M_apply(_CharT __ch, true_type) const
423 { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
424
425 void
426 _M_make_cache(true_type)
427 {
428 for (int __i = 0; __i < _M_cache.size(); __i++)
429 _M_cache[static_cast<_UnsignedCharT>(__i)] =
430 _M_apply(__i, false_type());
431 }
432
433 void
434 _M_make_cache(false_type)
435 { }
436
437 private:
438 _CacheT _M_cache;
439 std::vector<_CharT> _M_char_set;
440 std::vector<_StringT> _M_equiv_set;
441 std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
442 std::vector<_CharClassT> _M_neg_class_set;
443 _CharClassT _M_class_set;
444 _TransT _M_translator;
445 const _TraitsT& _M_traits;
446 bool _M_is_non_matching;
447 #ifdef _GLIBCXX_DEBUG
448 bool _M_is_ready;
449 #endif
450 };
451
452 //@} regex-detail
453 _GLIBCXX_END_NAMESPACE_VERSION
454 } // namespace __detail
455 } // namespace std
456
457 #include <bits/regex_compiler.tcc>
458