libstdc++
regex_compiler.h
Go to the documentation of this file.
1 // class template regex -*- C++ -*-
2 
3 // Copyright (C) 2010-2015 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 
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>
44 
45  /**
46  * @brief Builds an NFA from an input iterator range.
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;
58 
59  _Compiler(_IterT __b, _IterT __e,
60  const typename _TraitsT::locale_type& __traits, _FlagT __flags);
61 
63  _M_get_nfa()
64  { return 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;
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(pair<bool, _CharT>& __last_char,
123  __matcher);
124 
125  int
126  _M_cur_int_value(int __radix);
127 
128  bool
129  _M_try_char();
130 
131  _StateSeqT
132  _M_pop()
133  {
134  auto ret = _M_stack.top();
135  _M_stack.pop();
136  return ret;
137  }
138 
139  _FlagT _M_flags;
140  _ScannerT _M_scanner;
141  shared_ptr<_RegexT> _M_nfa;
142  _StringT _M_value;
143  _StackT _M_stack;
144  const _TraitsT& _M_traits;
145  const _CtypeT& _M_ctype;
146  };
147 
148  template<typename _Tp>
149  struct __has_contiguous_iter : std::false_type { };
150 
151  template<typename _Ch, typename _Tr, typename _Alloc>
152  struct __has_contiguous_iter<std::basic_string<_Ch, _Tr, _Alloc>>
153  : std::true_type
154  { };
155 
156  template<typename _Tp, typename _Alloc>
157  struct __has_contiguous_iter<std::vector<_Tp, _Alloc>>
158  : std::true_type
159  { };
160 
161  template<typename _Tp>
162  struct __is_contiguous_normal_iter : std::false_type { };
163 
164  template<typename _CharT>
165  struct __is_contiguous_normal_iter<_CharT*> : std::true_type { };
166 
167  template<typename _Tp, typename _Cont>
168  struct
169  __is_contiguous_normal_iter<__gnu_cxx::__normal_iterator<_Tp, _Cont>>
170  : __has_contiguous_iter<_Cont>::type
171  { };
172 
173  template<typename _Iter, typename _TraitsT>
174  using __enable_if_contiguous_normal_iter
175  = typename enable_if< __is_contiguous_normal_iter<_Iter>::value,
177 
178  template<typename _Iter, typename _TraitsT>
179  using __disable_if_contiguous_normal_iter
180  = typename enable_if< !__is_contiguous_normal_iter<_Iter>::value,
182 
183  template<typename _FwdIter, typename _TraitsT>
184  inline __enable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
185  __compile_nfa(_FwdIter __first, _FwdIter __last,
186  const typename _TraitsT::locale_type& __loc,
188  {
189  size_t __len = __last - __first;
190  const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
191  using _Cmplr = _Compiler<_TraitsT>;
192  return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
193  }
194 
195  template<typename _FwdIter, typename _TraitsT>
196  inline __disable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
197  __compile_nfa(_FwdIter __first, _FwdIter __last,
198  const typename _TraitsT::locale_type& __loc,
200  {
201  basic_string<typename _TraitsT::char_type> __str(__first, __last);
202  return __compile_nfa(__str.data(), __str.data() + __str.size(), __loc,
203  __flags);
204  }
205 
206  // [28.13.14]
207  template<typename _TraitsT, bool __icase, bool __collate>
208  class _RegexTranslator
209  {
210  public:
211  typedef typename _TraitsT::char_type _CharT;
212  typedef typename _TraitsT::string_type _StringT;
213  typedef typename std::conditional<__collate,
214  _StringT,
215  _CharT>::type _StrTransT;
216 
217  explicit
218  _RegexTranslator(const _TraitsT& __traits)
219  : _M_traits(__traits)
220  { }
221 
222  _CharT
223  _M_translate(_CharT __ch) const
224  {
225  if (__icase)
226  return _M_traits.translate_nocase(__ch);
227  else if (__collate)
228  return _M_traits.translate(__ch);
229  else
230  return __ch;
231  }
232 
233  _StrTransT
234  _M_transform(_CharT __ch) const
235  {
236  return _M_transform_impl(__ch, typename integral_constant<bool,
237  __collate>::type());
238  }
239 
240  private:
241  _StrTransT
242  _M_transform_impl(_CharT __ch, false_type) const
243  { return __ch; }
244 
245  _StrTransT
246  _M_transform_impl(_CharT __ch, true_type) const
247  {
248  _StrTransT __str = _StrTransT(1, _M_translate(__ch));
249  return _M_traits.transform(__str.begin(), __str.end());
250  }
251 
252  const _TraitsT& _M_traits;
253  };
254 
255  template<typename _TraitsT>
256  class _RegexTranslator<_TraitsT, false, false>
257  {
258  public:
259  typedef typename _TraitsT::char_type _CharT;
260  typedef _CharT _StrTransT;
261 
262  explicit
263  _RegexTranslator(const _TraitsT&)
264  { }
265 
266  _CharT
267  _M_translate(_CharT __ch) const
268  { return __ch; }
269 
270  _StrTransT
271  _M_transform(_CharT __ch) const
272  { return __ch; }
273  };
274 
275  template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
276  struct _AnyMatcher;
277 
278  template<typename _TraitsT, bool __icase, bool __collate>
279  struct _AnyMatcher<_TraitsT, false, __icase, __collate>
280  {
281  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
282  typedef typename _TransT::_CharT _CharT;
283 
284  explicit
285  _AnyMatcher(const _TraitsT& __traits)
286  : _M_translator(__traits)
287  { }
288 
289  bool
290  operator()(_CharT __ch) const
291  {
292  static auto __nul = _M_translator._M_translate('\0');
293  return _M_translator._M_translate(__ch) != __nul;
294  }
295 
296  _TransT _M_translator;
297  };
298 
299  template<typename _TraitsT, bool __icase, bool __collate>
300  struct _AnyMatcher<_TraitsT, true, __icase, __collate>
301  {
302  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
303  typedef typename _TransT::_CharT _CharT;
304 
305  explicit
306  _AnyMatcher(const _TraitsT& __traits)
307  : _M_translator(__traits)
308  { }
309 
310  bool
311  operator()(_CharT __ch) const
312  { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
313 
314  bool
315  _M_apply(_CharT __ch, true_type) const
316  {
317  auto __c = _M_translator._M_translate(__ch);
318  auto __n = _M_translator._M_translate('\n');
319  auto __r = _M_translator._M_translate('\r');
320  return __c != __n && __c != __r;
321  }
322 
323  bool
324  _M_apply(_CharT __ch, false_type) const
325  {
326  auto __c = _M_translator._M_translate(__ch);
327  auto __n = _M_translator._M_translate('\n');
328  auto __r = _M_translator._M_translate('\r');
329  auto __u2028 = _M_translator._M_translate(u'\u2028');
330  auto __u2029 = _M_translator._M_translate(u'\u2029');
331  return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
332  }
333 
334  _TransT _M_translator;
335  };
336 
337  template<typename _TraitsT, bool __icase, bool __collate>
338  struct _CharMatcher
339  {
340  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
341  typedef typename _TransT::_CharT _CharT;
342 
343  _CharMatcher(_CharT __ch, const _TraitsT& __traits)
344  : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
345  { }
346 
347  bool
348  operator()(_CharT __ch) const
349  { return _M_ch == _M_translator._M_translate(__ch); }
350 
351  _TransT _M_translator;
352  _CharT _M_ch;
353  };
354 
355  /// Matches a character range (bracket expression)
356  template<typename _TraitsT, bool __icase, bool __collate>
357  struct _BracketMatcher
358  {
359  public:
360  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
361  typedef typename _TransT::_CharT _CharT;
362  typedef typename _TransT::_StrTransT _StrTransT;
363  typedef typename _TraitsT::string_type _StringT;
364  typedef typename _TraitsT::char_class_type _CharClassT;
365 
366  public:
367  _BracketMatcher(bool __is_non_matching,
368  const _TraitsT& __traits)
369  : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
370  _M_is_non_matching(__is_non_matching)
371 #ifdef _GLIBCXX_DEBUG
372  , _M_is_ready(false)
373 #endif
374  { }
375 
376  bool
377  operator()(_CharT __ch) const
378  {
379  _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
380  return _M_apply(__ch, _UseCache());
381  }
382 
383  void
384  _M_add_char(_CharT __c)
385  {
386  _M_char_set.push_back(_M_translator._M_translate(__c));
387 #ifdef _GLIBCXX_DEBUG
388  _M_is_ready = false;
389 #endif
390  }
391 
392  void
393  _M_add_collating_element(const _StringT& __s)
394  {
395  auto __st = _M_traits.lookup_collatename(__s.data(),
396  __s.data() + __s.size());
397  if (__st.empty())
398  __throw_regex_error(regex_constants::error_collate);
399  _M_char_set.push_back(_M_translator._M_translate(__st[0]));
400 #ifdef _GLIBCXX_DEBUG
401  _M_is_ready = false;
402 #endif
403  }
404 
405  void
406  _M_add_equivalence_class(const _StringT& __s)
407  {
408  auto __st = _M_traits.lookup_collatename(__s.data(),
409  __s.data() + __s.size());
410  if (__st.empty())
411  __throw_regex_error(regex_constants::error_collate);
412  __st = _M_traits.transform_primary(__st.data(),
413  __st.data() + __st.size());
414  _M_equiv_set.push_back(__st);
415 #ifdef _GLIBCXX_DEBUG
416  _M_is_ready = false;
417 #endif
418  }
419 
420  // __neg should be true for \D, \S and \W only.
421  void
422  _M_add_character_class(const _StringT& __s, bool __neg)
423  {
424  auto __mask = _M_traits.lookup_classname(__s.data(),
425  __s.data() + __s.size(),
426  __icase);
427  if (__mask == 0)
428  __throw_regex_error(regex_constants::error_ctype);
429  if (!__neg)
430  _M_class_set |= __mask;
431  else
432  _M_neg_class_set.push_back(__mask);
433 #ifdef _GLIBCXX_DEBUG
434  _M_is_ready = false;
435 #endif
436  }
437 
438  void
439  _M_make_range(_CharT __l, _CharT __r)
440  {
441  if (__l > __r)
442  __throw_regex_error(regex_constants::error_range);
443  _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
444  _M_translator._M_transform(__r)));
445 #ifdef _GLIBCXX_DEBUG
446  _M_is_ready = false;
447 #endif
448  }
449 
450  void
451  _M_ready()
452  {
453  std::sort(_M_char_set.begin(), _M_char_set.end());
454  auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
455  _M_char_set.erase(__end, _M_char_set.end());
456  _M_make_cache(_UseCache());
457 #ifdef _GLIBCXX_DEBUG
458  _M_is_ready = true;
459 #endif
460  }
461 
462  private:
463  // Currently we only use the cache for char
464  typedef typename std::is_same<_CharT, char>::type _UseCache;
465 
466  static constexpr size_t
467  _S_cache_size()
468  {
469  return 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
470  }
471 
472  struct _Dummy { };
473  typedef typename std::conditional<_UseCache::value,
474  std::bitset<_S_cache_size()>,
475  _Dummy>::type _CacheT;
476  typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
477 
478  bool
479  _M_apply(_CharT __ch, false_type) const;
480 
481  bool
482  _M_apply(_CharT __ch, true_type) const
483  { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
484 
485  void
486  _M_make_cache(true_type)
487  {
488  for (unsigned __i = 0; __i < _M_cache.size(); __i++)
489  _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
490  }
491 
492  void
493  _M_make_cache(false_type)
494  { }
495 
496  private:
497  std::vector<_CharT> _M_char_set;
498  std::vector<_StringT> _M_equiv_set;
500  std::vector<_CharClassT> _M_neg_class_set;
501  _CharClassT _M_class_set;
502  _TransT _M_translator;
503  const _TraitsT& _M_traits;
504  bool _M_is_non_matching;
505  _CacheT _M_cache;
506 #ifdef _GLIBCXX_DEBUG
507  bool _M_is_ready;
508 #endif
509  };
510 
511  //@} regex-detail
512 _GLIBCXX_END_NAMESPACE_VERSION
513 } // namespace __detail
514 } // namespace std
515 
516 #include <bits/regex_compiler.tcc>
Managing sequences of characters and character-like objects.
constexpr error_type error_collate(_S_error_collate)
iterator begin() noexcept
Definition: stl_vector.h:547
void push_back(const value_type &__x)
Add data to the end of the vector.
Definition: stl_vector.h:913
Primary class template ctype facet.This template class defines classification and conversion function...
constexpr error_type error_range(_S_error_range)
Builds an NFA from an input iterator range.
reference top()
Definition: stl_stack.h:162
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison.
Definition: stl_algo.h:4718
Scans an input range for regex tokens.
Matches a character range (bracket expression)
_ForwardIterator unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred)
Remove consecutive values from a sequence using a predicate.
Definition: stl_algo.h:1022
syntax_option_type
This is a bitmask type indicating how to interpret the regex.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
iterator erase(const_iterator __position)
Remove element at given position.
Definition: stl_vector.h:1146
void pop()
Removes first element.
Definition: stl_stack.h:215
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:276
constexpr error_type error_ctype(_S_error_ctype)
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
Describes a sequence of one or more _State, its current start and end(s). This structure contains fra...
ISO C++ entities toplevel namespace is std.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
iterator end() noexcept
Definition: stl_vector.h:565
A smart pointer with reference-counted copy semantics.
Definition: shared_ptr.h:93