libstdc++
regex_compiler.h
Go to the documentation of this file.
1 // class template regex -*- C++ -*-
2 
3 // Copyright (C) 2010-2021 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>
49  struct _BracketMatcher;
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  // Returns true if successfully matched one term and should continue.
126  // Returns false if the compiler should move on.
127  template<bool __icase, bool __collate>
128  bool
129  _M_expression_term(pair<bool, _CharT>& __last_char,
131  __matcher);
132 
133  int
134  _M_cur_int_value(int __radix);
135 
136  bool
137  _M_try_char();
138 
139  _StateSeqT
140  _M_pop()
141  {
142  auto ret = _M_stack.top();
143  _M_stack.pop();
144  return ret;
145  }
146 
147  _FlagT _M_flags;
148  _ScannerT _M_scanner;
149  shared_ptr<_RegexT> _M_nfa;
150  _StringT _M_value;
151  _StackT _M_stack;
152  const _TraitsT& _M_traits;
153  const _CtypeT& _M_ctype;
154  };
155 
156  template<typename _Tp>
157  struct __is_contiguous_iter : is_pointer<_Tp>::type { };
158 
159  template<typename _Tp, typename _Cont>
160  struct
161  __is_contiguous_iter<__gnu_cxx::__normal_iterator<_Tp*, _Cont>>
162  : true_type { };
163 
164  template<typename _Iter, typename _TraitsT>
165  using __enable_if_contiguous_iter
166  = __enable_if_t< __is_contiguous_iter<_Iter>::value,
168 
169  template<typename _Iter, typename _TraitsT>
170  using __disable_if_contiguous_iter
171  = __enable_if_t< !__is_contiguous_iter<_Iter>::value,
173 
174  template<typename _TraitsT, typename _FwdIter>
175  inline __enable_if_contiguous_iter<_FwdIter, _TraitsT>
176  __compile_nfa(_FwdIter __first, _FwdIter __last,
177  const typename _TraitsT::locale_type& __loc,
179  {
180  size_t __len = __last - __first;
181  const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
182  using _Cmplr = _Compiler<_TraitsT>;
183  return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
184  }
185 
186  template<typename _TraitsT, typename _FwdIter>
187  inline __disable_if_contiguous_iter<_FwdIter, _TraitsT>
188  __compile_nfa(_FwdIter __first, _FwdIter __last,
189  const typename _TraitsT::locale_type& __loc,
191  {
192  const basic_string<typename _TraitsT::char_type> __str(__first, __last);
193  return __compile_nfa<_TraitsT>(__str.data(), __str.data() + __str.size(),
194  __loc, __flags);
195  }
196 
197  // [28.13.14]
198  template<typename _TraitsT, bool __icase, bool __collate>
199  class _RegexTranslatorBase
200  {
201  public:
202  typedef typename _TraitsT::char_type _CharT;
203  typedef typename _TraitsT::string_type _StringT;
204  typedef _StringT _StrTransT;
205 
206  explicit
207  _RegexTranslatorBase(const _TraitsT& __traits)
208  : _M_traits(__traits)
209  { }
210 
211  _CharT
212  _M_translate(_CharT __ch) const
213  {
214  if (__icase)
215  return _M_traits.translate_nocase(__ch);
216  else if (__collate)
217  return _M_traits.translate(__ch);
218  else
219  return __ch;
220  }
221 
222  _StrTransT
223  _M_transform(_CharT __ch) const
224  {
225  _StrTransT __str(1, __ch);
226  return _M_traits.transform(__str.begin(), __str.end());
227  }
228 
229  // See LWG 523. It's not efficiently implementable when _TraitsT is not
230  // std::regex_traits<>, and __collate is true. See specializations for
231  // implementations of other cases.
232  bool
233  _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
234  const _StrTransT& __s) const
235  { return __first <= __s && __s <= __last; }
236 
237  protected:
238  bool _M_in_range_icase(_CharT __first, _CharT __last, _CharT __ch) const
239  {
240  typedef std::ctype<_CharT> __ctype_type;
241  const auto& __fctyp = use_facet<__ctype_type>(this->_M_traits.getloc());
242  auto __lower = __fctyp.tolower(__ch);
243  auto __upper = __fctyp.toupper(__ch);
244  return (__first <= __lower && __lower <= __last)
245  || (__first <= __upper && __upper <= __last);
246  }
247 
248  const _TraitsT& _M_traits;
249  };
250 
251  template<typename _TraitsT, bool __icase, bool __collate>
252  class _RegexTranslator
253  : public _RegexTranslatorBase<_TraitsT, __icase, __collate>
254  {
255  public:
256  typedef _RegexTranslatorBase<_TraitsT, __icase, __collate> _Base;
257  using _Base::_Base;
258  };
259 
260  template<typename _TraitsT, bool __icase>
261  class _RegexTranslator<_TraitsT, __icase, false>
262  : public _RegexTranslatorBase<_TraitsT, __icase, false>
263  {
264  public:
265  typedef _RegexTranslatorBase<_TraitsT, __icase, false> _Base;
266  typedef typename _Base::_CharT _CharT;
267  typedef _CharT _StrTransT;
268 
269  using _Base::_Base;
270 
271  _StrTransT
272  _M_transform(_CharT __ch) const
273  { return __ch; }
274 
275  bool
276  _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
277  {
278  if (!__icase)
279  return __first <= __ch && __ch <= __last;
280  return this->_M_in_range_icase(__first, __last, __ch);
281  }
282  };
283 
284  template<typename _CharType>
285  class _RegexTranslator<std::regex_traits<_CharType>, true, true>
286  : public _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
287  {
288  public:
289  typedef _RegexTranslatorBase<std::regex_traits<_CharType>, true, true>
290  _Base;
291  typedef typename _Base::_CharT _CharT;
292  typedef typename _Base::_StrTransT _StrTransT;
293 
294  using _Base::_Base;
295 
296  bool
297  _M_match_range(const _StrTransT& __first, const _StrTransT& __last,
298  const _StrTransT& __str) const
299  {
300  __glibcxx_assert(__first.size() == 1);
301  __glibcxx_assert(__last.size() == 1);
302  __glibcxx_assert(__str.size() == 1);
303  return this->_M_in_range_icase(__first[0], __last[0], __str[0]);
304  }
305  };
306 
307  template<typename _TraitsT>
308  class _RegexTranslator<_TraitsT, false, false>
309  {
310  public:
311  typedef typename _TraitsT::char_type _CharT;
312  typedef _CharT _StrTransT;
313 
314  explicit
315  _RegexTranslator(const _TraitsT&)
316  { }
317 
318  _CharT
319  _M_translate(_CharT __ch) const
320  { return __ch; }
321 
322  _StrTransT
323  _M_transform(_CharT __ch) const
324  { return __ch; }
325 
326  bool
327  _M_match_range(_CharT __first, _CharT __last, _CharT __ch) const
328  { return __first <= __ch && __ch <= __last; }
329  };
330 
331  template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
332  struct _AnyMatcher;
333 
334  template<typename _TraitsT, bool __icase, bool __collate>
335  struct _AnyMatcher<_TraitsT, false, __icase, __collate>
336  {
337  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
338  typedef typename _TransT::_CharT _CharT;
339 
340  explicit
341  _AnyMatcher(const _TraitsT& __traits)
342  : _M_translator(__traits)
343  { }
344 
345  bool
346  operator()(_CharT __ch) const
347  {
348  static auto __nul = _M_translator._M_translate('\0');
349  return _M_translator._M_translate(__ch) != __nul;
350  }
351 
352  _TransT _M_translator;
353  };
354 
355  template<typename _TraitsT, bool __icase, bool __collate>
356  struct _AnyMatcher<_TraitsT, true, __icase, __collate>
357  {
358  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
359  typedef typename _TransT::_CharT _CharT;
360 
361  explicit
362  _AnyMatcher(const _TraitsT& __traits)
363  : _M_translator(__traits)
364  { }
365 
366  bool
367  operator()(_CharT __ch) const
368  { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
369 
370  bool
371  _M_apply(_CharT __ch, true_type) const
372  {
373  auto __c = _M_translator._M_translate(__ch);
374  auto __n = _M_translator._M_translate('\n');
375  auto __r = _M_translator._M_translate('\r');
376  return __c != __n && __c != __r;
377  }
378 
379  bool
380  _M_apply(_CharT __ch, false_type) const
381  {
382  auto __c = _M_translator._M_translate(__ch);
383  auto __n = _M_translator._M_translate('\n');
384  auto __r = _M_translator._M_translate('\r');
385  auto __u2028 = _M_translator._M_translate(u'\u2028');
386  auto __u2029 = _M_translator._M_translate(u'\u2029');
387  return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
388  }
389 
390  _TransT _M_translator;
391  };
392 
393  template<typename _TraitsT, bool __icase, bool __collate>
394  struct _CharMatcher
395  {
396  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
397  typedef typename _TransT::_CharT _CharT;
398 
399  _CharMatcher(_CharT __ch, const _TraitsT& __traits)
400  : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
401  { }
402 
403  bool
404  operator()(_CharT __ch) const
405  { return _M_ch == _M_translator._M_translate(__ch); }
406 
407  _TransT _M_translator;
408  _CharT _M_ch;
409  };
410 
411  /// Matches a character range (bracket expression)
412  template<typename _TraitsT, bool __icase, bool __collate>
414  {
415  public:
416  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
417  typedef typename _TransT::_CharT _CharT;
418  typedef typename _TransT::_StrTransT _StrTransT;
419  typedef typename _TraitsT::string_type _StringT;
420  typedef typename _TraitsT::char_class_type _CharClassT;
421 
422  public:
423  _BracketMatcher(bool __is_non_matching,
424  const _TraitsT& __traits)
425  : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
426  _M_is_non_matching(__is_non_matching)
427  { }
428 
429  bool
430  operator()(_CharT __ch) const
431  {
432  _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
433  return _M_apply(__ch, _UseCache());
434  }
435 
436  void
437  _M_add_char(_CharT __c)
438  {
439  _M_char_set.push_back(_M_translator._M_translate(__c));
440  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
441  }
442 
443  _StringT
444  _M_add_collate_element(const _StringT& __s)
445  {
446  auto __st = _M_traits.lookup_collatename(__s.data(),
447  __s.data() + __s.size());
448  if (__st.empty())
449  __throw_regex_error(regex_constants::error_collate,
450  "Invalid collate element.");
451  _M_char_set.push_back(_M_translator._M_translate(__st[0]));
452  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
453  return __st;
454  }
455 
456  void
457  _M_add_equivalence_class(const _StringT& __s)
458  {
459  auto __st = _M_traits.lookup_collatename(__s.data(),
460  __s.data() + __s.size());
461  if (__st.empty())
462  __throw_regex_error(regex_constants::error_collate,
463  "Invalid equivalence class.");
464  __st = _M_traits.transform_primary(__st.data(),
465  __st.data() + __st.size());
466  _M_equiv_set.push_back(__st);
467  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
468  }
469 
470  // __neg should be true for \D, \S and \W only.
471  void
472  _M_add_character_class(const _StringT& __s, bool __neg)
473  {
474  auto __mask = _M_traits.lookup_classname(__s.data(),
475  __s.data() + __s.size(),
476  __icase);
477  if (__mask == 0)
478  __throw_regex_error(regex_constants::error_collate,
479  "Invalid character class.");
480  if (!__neg)
481  _M_class_set |= __mask;
482  else
483  _M_neg_class_set.push_back(__mask);
484  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
485  }
486 
487  void
488  _M_make_range(_CharT __l, _CharT __r)
489  {
490  if (__l > __r)
491  __throw_regex_error(regex_constants::error_range,
492  "Invalid range in bracket expression.");
493  _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
494  _M_translator._M_transform(__r)));
495  _GLIBCXX_DEBUG_ONLY(_M_is_ready = false);
496  }
497 
498  void
499  _M_ready()
500  {
501  std::sort(_M_char_set.begin(), _M_char_set.end());
502  auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
503  _M_char_set.erase(__end, _M_char_set.end());
504  _M_make_cache(_UseCache());
505  _GLIBCXX_DEBUG_ONLY(_M_is_ready = true);
506  }
507 
508  private:
509  // Currently we only use the cache for char
511 
512  static constexpr size_t
513  _S_cache_size =
514  1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
515 
516  struct _Dummy { };
517  typedef typename std::conditional<_UseCache::value,
519  _Dummy>::type _CacheT;
520  typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
521 
522  bool
523  _M_apply(_CharT __ch, false_type) const;
524 
525  bool
526  _M_apply(_CharT __ch, true_type) const
527  { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
528 
529  void
530  _M_make_cache(true_type)
531  {
532  for (unsigned __i = 0; __i < _M_cache.size(); __i++)
533  _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
534  }
535 
536  void
537  _M_make_cache(false_type)
538  { }
539 
540  private:
541  std::vector<_CharT> _M_char_set;
542  std::vector<_StringT> _M_equiv_set;
544  std::vector<_CharClassT> _M_neg_class_set;
545  _CharClassT _M_class_set;
546  _TransT _M_translator;
547  const _TraitsT& _M_traits;
548  bool _M_is_non_matching;
549  _CacheT _M_cache;
550 #ifdef _GLIBCXX_DEBUG
551  bool _M_is_ready = false;
552 #endif
553  };
554 
555  ///@} regex-detail
556 } // namespace __detail
557 _GLIBCXX_END_NAMESPACE_VERSION
558 } // namespace std
559 
560 #include <bits/regex_compiler.tcc>
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:83
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:86
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
ISO C++ entities toplevel namespace is std.
constexpr error_type error_range(_S_error_range)
syntax_option_type
This is a bitmask type indicating how to interpret the regex.
constexpr error_type error_collate(_S_error_collate)
The bitset class represents a fixed-size sequence of bits.
Definition: bitset:753
integral_constant
Definition: type_traits:66
Define a member typedef type to one of two argument types.
Definition: type_traits:2227
is_pointer
Definition: type_traits:451
Primary class template ctype facet.
Describes a sequence of one or more _State, its current start and end(s). This structure contains fra...
Matches a character range (bracket expression)
Builds an NFA from an input iterator range.
Scans an input range for regex tokens.
A smart pointer with reference-counted copy semantics.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:202
void pop()
Removes first element.
Definition: stl_stack.h:272
reference top()
Definition: stl_stack.h:212
iterator erase(const_iterator __position)
Remove element at given position.
Definition: stl_vector.h:1430
void push_back(const value_type &__x)
Add data to the end of the vector.
Definition: stl_vector.h:1187
iterator begin() noexcept
Definition: stl_vector.h:811
iterator end() noexcept
Definition: stl_vector.h:829