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