libstdc++
regex_compiler.h
Go to the documentation of this file.
1 // class template regex -*- C++ -*-
2 
3 // Copyright (C) 2010-2018 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 _GLIBCXX_BEGIN_NAMESPACE_VERSION
34 _GLIBCXX_BEGIN_NAMESPACE_CXX11
35 
36  template<typename>
37  class regex_traits;
38 
39 _GLIBCXX_END_NAMESPACE_CXX11
40 
41 namespace __detail
42 {
43  /**
44  * @addtogroup regex-detail
45  * @{
46  */
47 
48  template<typename, bool, bool>
50 
51  /**
52  * @brief Builds an NFA from an input iterator range.
53  *
54  * The %_TraitsT type should fulfill requirements [28.3].
55  */
56  template<typename _TraitsT>
57  class _Compiler
58  {
59  public:
60  typedef typename _TraitsT::char_type _CharT;
61  typedef const _CharT* _IterT;
62  typedef _NFA<_TraitsT> _RegexT;
64 
65  _Compiler(_IterT __b, _IterT __e,
66  const typename _TraitsT::locale_type& __traits, _FlagT __flags);
67 
69  _M_get_nfa()
70  { return std::move(_M_nfa); }
71 
72  private:
73  typedef _Scanner<_CharT> _ScannerT;
74  typedef typename _TraitsT::string_type _StringT;
75  typedef typename _ScannerT::_TokenT _TokenT;
79 
80  // accepts a specific token or returns false.
81  bool
82  _M_match_token(_TokenT __token);
83 
84  void
85  _M_disjunction();
86 
87  void
88  _M_alternative();
89 
90  bool
91  _M_term();
92 
93  bool
94  _M_assertion();
95 
96  bool
97  _M_quantifier();
98 
99  bool
100  _M_atom();
101 
102  bool
103  _M_bracket_expression();
104 
105  template<bool __icase, bool __collate>
106  void
107  _M_insert_any_matcher_ecma();
108 
109  template<bool __icase, bool __collate>
110  void
111  _M_insert_any_matcher_posix();
112 
113  template<bool __icase, bool __collate>
114  void
115  _M_insert_char_matcher();
116 
117  template<bool __icase, bool __collate>
118  void
119  _M_insert_character_class_matcher();
120 
121  template<bool __icase, bool __collate>
122  void
123  _M_insert_bracket_matcher(bool __neg);
124 
125  // Cache of the last atom seen in a bracketed range expression.
126  struct _BracketState
127  {
128  enum class _Type : char { _None, _Char, _Class } _M_type = _Type::_None;
129  _CharT _M_char;
130 
131  void
132  set(_CharT __c) noexcept { _M_type = _Type::_Char; _M_char = __c; }
133 
134  _GLIBCXX_NODISCARD _CharT
135  get() const noexcept { return _M_char; }
136 
137  void
138  reset(_Type __t = _Type::_None) noexcept { _M_type = __t; }
139 
140  explicit operator bool() const noexcept
141  { return _M_type != _Type::_None; }
142 
143  // Previous token was a single character.
144  _GLIBCXX_NODISCARD bool
145  _M_is_char() const noexcept { return _M_type == _Type::_Char; }
146 
147  // Previous token was a character class, equivalent class,
148  // collating symbol etc.
149  _GLIBCXX_NODISCARD bool
150  _M_is_class() const noexcept { return _M_type == _Type::_Class; }
151  };
152 
153  template<bool __icase, bool __collate>
154  using _BracketMatcher
156 
157  // Returns true if successfully parsed one term and should continue
158  // compiling a bracket expression.
159  // Returns false if the compiler should move on.
160  template<bool __icase, bool __collate>
161  bool
162  _M_expression_term(_BracketState& __last_char,
164 
165  int
166  _M_cur_int_value(int __radix);
167 
168  bool
169  _M_try_char();
170 
171  _StateSeqT
172  _M_pop()
173  {
174  auto ret = _M_stack.top();
175  _M_stack.pop();
176  return ret;
177  }
178 
179  _FlagT _M_flags;
180  _ScannerT _M_scanner;
181  shared_ptr<_RegexT> _M_nfa;
182  _StringT _M_value;
183  _StackT _M_stack;
184  const _TraitsT& _M_traits;
185  const _CtypeT& _M_ctype;
186  };
187 
188  template<typename _Tp>
189  struct __has_contiguous_iter : std::false_type { };
190 
191  template<typename _Ch, typename _Tr, typename _Alloc>
192  struct __has_contiguous_iter<std::basic_string<_Ch, _Tr, _Alloc>>
194  { };
195 
196  template<typename _Tp, typename _Alloc>
197  struct __has_contiguous_iter<std::vector<_Tp, _Alloc>>
199  { };
200 
201  template<typename _Tp>
202  struct __is_contiguous_normal_iter : std::false_type { };
203 
204  template<typename _CharT>
205  struct __is_contiguous_normal_iter<_CharT*> : std::true_type { };
206 
207  template<typename _Tp, typename _Cont>
208  struct
209  __is_contiguous_normal_iter<__gnu_cxx::__normal_iterator<_Tp, _Cont>>
210  : __has_contiguous_iter<_Cont>::type
211  { };
212 
213  template<typename _Iter, typename _TraitsT>
214  using __enable_if_contiguous_normal_iter
215  = typename enable_if< __is_contiguous_normal_iter<_Iter>::value,
217 
218  template<typename _Iter, typename _TraitsT>
219  using __disable_if_contiguous_normal_iter
220  = typename enable_if< !__is_contiguous_normal_iter<_Iter>::value,
222 
223  template<typename _TraitsT, typename _FwdIter>
224  inline __enable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
225  __compile_nfa(_FwdIter __first, _FwdIter __last,
226  const typename _TraitsT::locale_type& __loc,
228  {
229  size_t __len = __last - __first;
230  const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
231  using _Cmplr = _Compiler<_TraitsT>;
232  return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
233  }
234 
235  template<typename _TraitsT, typename _FwdIter>
236  inline __disable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
237  __compile_nfa(_FwdIter __first, _FwdIter __last,
238  const typename _TraitsT::locale_type& __loc,
240  {
241  const basic_string<typename _TraitsT::char_type> __str(__first, __last);
242  return __compile_nfa<_TraitsT>(__str.data(), __str.data() + __str.size(),
243  __loc, __flags);
244  }
245 
246  // [28.13.14]
247  template<typename _TraitsT, bool __icase, bool __collate>
248  class _RegexTranslatorBase
249  {
250  public:
251  typedef typename _TraitsT::char_type _CharT;
252  typedef typename _TraitsT::string_type _StringT;
253  typedef _StringT _StrTransT;
254 
255  explicit
256  _RegexTranslatorBase(const _TraitsT& __traits)
257  : _M_traits(__traits)
258  { }
259 
260  _CharT
261  _M_translate(_CharT __ch) const
262  {
263  if (__icase)
264  return _M_traits.translate_nocase(__ch);
265  else if (__collate)
266  return _M_traits.translate(__ch);
267  else
268  return __ch;
269  }
270 
271  _StrTransT
272  _M_transform(_CharT __ch) const
273  {
274  _StrTransT __str(1, __ch);
275  return _M_traits.transform(__str.begin(), __str.end());
276  }
277 
278  // See LWG 523. It's not efficiently implementable when _TraitsT is not
279  // std::regex_traits<>, and __collate is true. See specializations for
280  // implementations of other cases.
281  bool
282  _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
283  const _StrTransT& __s) const
284  { return __first <= __s && __s <= __last; }
285 
286  protected:
287  bool _M_in_range_icase(_CharT __first, _CharT __last, _CharT __ch) const
288  {
289  typedef std::ctype<_CharT> __ctype_type;
290  const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc());
291  auto __lower = __fctyp.tolower(__ch);
292  auto __upper = __fctyp.toupper(__ch);
293  return (__first <= __lower && __lower <= __last)
294  || (__first <= __upper && __upper <= __last);
295  }
296 
297  const _TraitsT& _M_traits;
298  };
299 
300  template<typename _TraitsT, bool __icase, bool __collate>
301  class _RegexTranslator
302  : public _RegexTranslatorBase<_TraitsT, __icase, __collate>
303  {
304  public:
305  typedef _RegexTranslatorBase<_TraitsT, __icase, __collate> _Base;
306  using _Base::_Base;
307  };
308 
309  template<typename _TraitsT, bool __icase>
310  class _RegexTranslator<_TraitsT, __icase, false>
311  : public _RegexTranslatorBase<_TraitsT, __icase, false>
312  {
313  public:
314  typedef _RegexTranslatorBase<_TraitsT, __icase, false> _Base;
315  typedef typename _Base::_CharT _CharT;
316  typedef _CharT _StrTransT;
317 
318  using _Base::_Base;
319 
320  _StrTransT
321  _M_transform(_CharT __ch) const
322  { return __ch; }
323 
324  bool
325  _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
326  {
327  if (!__icase)
328  return __first <= __ch && __ch <= __last;
329  return this->_M_in_range_icase(__first, __last, __ch);
330  }
331  };
332 
333  template<typename _CharType>
334  class _RegexTranslator<std::regex_traits<_CharType>, true, true>
335  : public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
336  {
337  public:
338  typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
339  _Base;
340  typedef typename _Base::_CharT _CharT;
341  typedef typename _Base::_StrTransT _StrTransT;
342 
343  using _Base::_Base;
344 
345  bool
346  _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
347  const _StrTransT& __str) const
348  {
349  __glibcxx_assert(__first.size() == 1);
350  __glibcxx_assert(__last.size() == 1);
351  __glibcxx_assert(__str.size() == 1);
352  return this->_M_in_range_icase(__first[0], __last[0], __str[0]);
353  }
354  };
355 
356  template<typename _TraitsT>
357  class _RegexTranslator<_TraitsT, false, false>
358  {
359  public:
360  typedef typename _TraitsT::char_type _CharT;
361  typedef _CharT _StrTransT;
362 
363  explicit
364  _RegexTranslator(const _TraitsT&)
365  { }
366 
367  _CharT
368  _M_translate(_CharT __ch) const
369  { return __ch; }
370 
371  _StrTransT
372  _M_transform(_CharT __ch) const
373  { return __ch; }
374 
375  bool
376  _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
377  { return __first <= __ch && __ch <= __last; }
378  };
379 
380  template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
381  struct _AnyMatcher;
382 
383  template<typename _TraitsT, bool __icase, bool __collate>
384  struct _AnyMatcher<_TraitsT, false, __icase, __collate>
385  {
386  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
387  typedef typename _TransT::_CharT _CharT;
388 
389  explicit
390  _AnyMatcher(const _TraitsT& __traits)
391  : _M_translator(__traits)
392  { }
393 
394  bool
395  operator()(_CharT __ch) const
396  {
397  static auto __nul = _M_translator._M_translate('\0');
398  return _M_translator._M_translate(__ch) != __nul;
399  }
400 
401  _TransT _M_translator;
402  };
403 
404  template<typename _TraitsT, bool __icase, bool __collate>
405  struct _AnyMatcher<_TraitsT, true, __icase, __collate>
406  {
407  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
408  typedef typename _TransT::_CharT _CharT;
409 
410  explicit
411  _AnyMatcher(const _TraitsT& __traits)
412  : _M_translator(__traits)
413  { }
414 
415  bool
416  operator()(_CharT __ch) const
417  { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
418 
419  bool
420  _M_apply(_CharT __ch, true_type) const
421  {
422  auto __c = _M_translator._M_translate(__ch);
423  auto __n = _M_translator._M_translate('\n');
424  auto __r = _M_translator._M_translate('\r');
425  return __c != __n && __c != __r;
426  }
427 
428  bool
429  _M_apply(_CharT __ch, false_type) const
430  {
431  auto __c = _M_translator._M_translate(__ch);
432  auto __n = _M_translator._M_translate('\n');
433  auto __r = _M_translator._M_translate('\r');
434  auto __u2028 = _M_translator._M_translate(u'\u2028');
435  auto __u2029 = _M_translator._M_translate(u'\u2029');
436  return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
437  }
438 
439  _TransT _M_translator;
440  };
441 
442  template<typename _TraitsT, bool __icase, bool __collate>
443  struct _CharMatcher
444  {
445  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
446  typedef typename _TransT::_CharT _CharT;
447 
448  _CharMatcher(_CharT __ch, const _TraitsT& __traits)
449  : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
450  { }
451 
452  bool
453  operator()(_CharT __ch) const
454  { return _M_ch == _M_translator._M_translate(__ch); }
455 
456  _TransT _M_translator;
457  _CharT _M_ch;
458  };
459 
460  /// Matches a character range (bracket expression)
461  template<typename _TraitsT, bool __icase, bool __collate>
462  struct _BracketMatcher
463  {
464  public:
465  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
466  typedef typename _TransT::_CharT _CharT;
467  typedef typename _TransT::_StrTransT _StrTransT;
468  typedef typename _TraitsT::string_type _StringT;
469  typedef typename _TraitsT::char_class_type _CharClassT;
470 
471  public:
472  _BracketMatcher(bool __is_non_matching,
473  const _TraitsT& __traits)
474  : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
475  _M_is_non_matching(__is_non_matching)
476  { }
477 
478  bool
479  operator()(_CharT __ch) const
480  {
481  _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
482  return _M_apply(__ch, _UseCache());
483  }
484 
485  void
486  _M_add_char(_CharT __c)
487  {
488  _M_char_set.push_back(_M_translator._M_translate(__c));
489  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
490  }
491 
492  _StringT
493  _M_add_collate_element(const _StringT& __s)
494  {
495  auto __st = _M_traits.lookup_collatename(__s.data(),
496  __s.data() + __s.size());
497  if (__st.empty())
498  __throw_regex_error(regex_constants::error_collate,
499  "Invalid collate element.");
500  _M_char_set.push_back(_M_translator._M_translate(__st[0]));
501  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
502  return __st;
503  }
504 
505  void
506  _M_add_equivalence_class(const _StringT& __s)
507  {
508  auto __st = _M_traits.lookup_collatename(__s.data(),
509  __s.data() + __s.size());
510  if (__st.empty())
511  __throw_regex_error(regex_constants::error_collate,
512  "Invalid equivalence class.");
513  __st = _M_traits.transform_primary(__st.data(),
514  __st.data() + __st.size());
515  _M_equiv_set.push_back(__st);
516  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
517  }
518 
519  // __neg should be true for \D, \S and \W only.
520  void
521  _M_add_character_class(const _StringT& __s, bool __neg)
522  {
523  auto __mask = _M_traits.lookup_classname(__s.data(),
524  __s.data() + __s.size(),
525  __icase);
526  if (__mask == 0)
527  __throw_regex_error(regex_constants::error_collate,
528  "Invalid character class.");
529  if (!__neg)
530  _M_class_set |= __mask;
531  else
532  _M_neg_class_set.push_back(__mask);
533  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
534  }
535 
536  void
537  _M_make_range(_CharT __l, _CharT __r)
538  {
539  if (__l > __r)
540  __throw_regex_error(regex_constants::error_range,
541  "Invalid range in bracket expression.");
542  _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
543  _M_translator._M_transform(__r)));
544  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
545  }
546 
547  void
548  _M_ready()
549  {
550  std::sort(_M_char_set.begin(), _M_char_set.end());
551  auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
552  _M_char_set.erase(__end, _M_char_set.end());
553  _M_make_cache(_UseCache());
554  _GLIBCXX_DEBUG_ONLY(_M_is_ready = true);
555  }
556 
557  private:
558  // Currently we only use the cache for char
559  typedef typename std::is_same<_CharT, char>::type _UseCache;
560 
561  static constexpr size_t
562  _S_cache_size()
563  {
564  return 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
565  }
566 
567  struct _Dummy { };
568  typedef typename std::conditional<_UseCache::value,
570  _Dummy>::type _CacheT;
571  typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
572 
573  bool
574  _M_apply(_CharT __ch, false_type) const;
575 
576  bool
577  _M_apply(_CharT __ch, true_type) const
578  { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
579 
580  void
581  _M_make_cache(true_type)
582  {
583  for (unsigned __i = 0; __i < _M_cache.size(); __i++)
584  _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
585  }
586 
587  void
588  _M_make_cache(false_type)
589  { }
590 
591  private:
592  std::vector<_CharT> _M_char_set;
593  std::vector<_StringT> _M_equiv_set;
595  std::vector<_CharClassT> _M_neg_class_set;
596  _CharClassT _M_class_set;
597  _TransT _M_translator;
598  const _TraitsT& _M_traits;
599  bool _M_is_non_matching;
600  _CacheT _M_cache;
601 #ifdef _GLIBCXX_DEBUG
602  bool _M_is_ready = false;
603 #endif
604  };
605 
606  //@} regex-detail
607 } // namespace __detail
608 _GLIBCXX_END_NAMESPACE_VERSION
609 } // namespace std
610 
611 #include <bits/regex_compiler.tcc>
A smart pointer with reference-counted copy semantics.
Describes a sequence of one or more _State, its current start and end(s). This structure contains fra...
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:75
reference top()
Definition: stl_stack.h:198
Scans an input range for regex tokens.
Builds an NFA from an input iterator range.
_ForwardIterator unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred)
Remove consecutive values from a sequence using a predicate.
Definition: stl_algo.h:1025
syntax_option_type
This is a bitmask type indicating how to interpret the regex.
void push_back(const value_type &__x)
Add data to the end of the vector.
Definition: stl_vector.h:1074
The bitset class represents a fixed-size sequence of bits.(Note that bitset does not meet the formal ...
Definition: bitset:751
Define a member typedef type to one of two argument types.
Definition: type_traits:92
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
iterator end() noexcept
Definition: stl_vector.h:716
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:524
constexpr error_type error_collate(_S_error_collate)
integral_constant
Definition: type_traits:57
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison.
Definition: stl_algo.h:4854
void pop()
Removes first element.
Definition: stl_stack.h:258
ISO C++ entities toplevel namespace is std.
iterator erase(const_iterator __position)
Remove element at given position.
Definition: stl_vector.h:1317
Managing sequences of characters and character-like objects.
iterator begin() noexcept
Definition: stl_vector.h:698
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:78
constexpr error_type error_range(_S_error_range)
Primary class template ctype facet.This template class defines classification and conversion function...
char_type tolower(char_type __c) const
Convert to lowercase.
Matches a character range (bracket expression)