libstdc++
regex_compiler.h
Go to the documentation of this file.
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 
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 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;
58 
59  _Compiler(_IterT __b, _IterT __e,
60  const _TraitsT& __traits, _FlagT __flags);
61 
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;
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  const _TraitsT& _M_traits;
143  const _CtypeT& _M_ctype;
144  _ScannerT _M_scanner;
145  _RegexT _M_nfa;
146  _StringT _M_value;
147  _StackT _M_stack;
148  };
149 
150  template<typename _TraitsT>
152  __compile_nfa(const typename _TraitsT::char_type* __first,
153  const typename _TraitsT::char_type* __last,
154  const _TraitsT& __traits,
156  {
157  using _Cmplr = _Compiler<_TraitsT>;
158  return _Cmplr(__first, __last, __traits, __flags)._M_get_nfa();
159  }
160 
161  // [28.13.14]
162  template<typename _TraitsT, bool __icase, bool __collate>
163  class _RegexTranslator
164  {
165  public:
166  typedef typename _TraitsT::char_type _CharT;
167  typedef typename _TraitsT::string_type _StringT;
168  typedef typename std::conditional<__collate,
169  _StringT,
170  _CharT>::type _StrTransT;
171 
172  explicit
173  _RegexTranslator(const _TraitsT& __traits)
174  : _M_traits(__traits)
175  { }
176 
177  _CharT
178  _M_translate(_CharT __ch) const
179  {
180  if (__icase)
181  return _M_traits.translate_nocase(__ch);
182  else if (__collate)
183  return _M_traits.translate(__ch);
184  else
185  return __ch;
186  }
187 
188  _StrTransT
189  _M_transform(_CharT __ch) const
190  {
191  return _M_transform_impl(__ch, typename integral_constant<bool,
192  __collate>::type());
193  }
194 
195  private:
196  _StrTransT
197  _M_transform_impl(_CharT __ch, false_type) const
198  { return __ch; }
199 
200  _StrTransT
201  _M_transform_impl(_CharT __ch, true_type) const
202  {
203  _StrTransT __str = _StrTransT(1, _M_translate(__ch));
204  return _M_traits.transform(__str.begin(), __str.end());
205  }
206 
207  const _TraitsT& _M_traits;
208  };
209 
210  template<typename _TraitsT>
211  class _RegexTranslator<_TraitsT, false, false>
212  {
213  public:
214  typedef typename _TraitsT::char_type _CharT;
215  typedef _CharT _StrTransT;
216 
217  explicit
218  _RegexTranslator(const _TraitsT& __traits)
219  { }
220 
221  _CharT
222  _M_translate(_CharT __ch) const
223  { return __ch; }
224 
225  _StrTransT
226  _M_transform(_CharT __ch) const
227  { return __ch; }
228  };
229 
230  template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
231  struct _AnyMatcher;
232 
233  template<typename _TraitsT, bool __icase, bool __collate>
234  struct _AnyMatcher<_TraitsT, false, __icase, __collate>
235  {
236  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
237  typedef typename _TransT::_CharT _CharT;
238 
239  explicit
240  _AnyMatcher(const _TraitsT& __traits)
241  : _M_translator(__traits)
242  { }
243 
244  bool
245  operator()(_CharT __ch) const
246  {
247  static auto __nul = _M_translator._M_translate('\0');
248  return _M_translator._M_translate(__ch) != __nul;
249  }
250 
251  _TransT _M_translator;
252  };
253 
254  template<typename _TraitsT, bool __icase, bool __collate>
255  struct _AnyMatcher<_TraitsT, true, __icase, __collate>
256  {
257  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
258  typedef typename _TransT::_CharT _CharT;
259 
260  explicit
261  _AnyMatcher(const _TraitsT& __traits)
262  : _M_translator(__traits)
263  { }
264 
265  bool
266  operator()(_CharT __ch) const
267  { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
268 
269  bool
270  _M_apply(_CharT __ch, true_type) const
271  {
272  auto __c = _M_translator._M_translate(__ch);
273  auto __n = _M_translator._M_translate('\n');
274  auto __r = _M_translator._M_translate('\r');
275  return __c != __n && __c != __r;
276  }
277 
278  bool
279  _M_apply(_CharT __ch, false_type) const
280  {
281  auto __c = _M_translator._M_translate(__ch);
282  auto __n = _M_translator._M_translate('\n');
283  auto __r = _M_translator._M_translate('\r');
284  auto __u2028 = _M_translator._M_translate(u'\u2028');
285  auto __u2029 = _M_translator._M_translate(u'\u2029');
286  return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
287  }
288 
289  _TransT _M_translator;
290  };
291 
292  template<typename _TraitsT, bool __icase, bool __collate>
293  struct _CharMatcher
294  {
295  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
296  typedef typename _TransT::_CharT _CharT;
297 
298  _CharMatcher(_CharT __ch, const _TraitsT& __traits)
299  : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
300  { }
301 
302  bool
303  operator()(_CharT __ch) const
304  { return _M_ch == _M_translator._M_translate(__ch); }
305 
306  _TransT _M_translator;
307  _CharT _M_ch;
308  };
309 
310  /// Matches a character range (bracket expression)
311  template<typename _TraitsT, bool __icase, bool __collate>
312  struct _BracketMatcher
313  {
314  public:
315  typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
316  typedef typename _TransT::_CharT _CharT;
317  typedef typename _TransT::_StrTransT _StrTransT;
318  typedef typename _TraitsT::string_type _StringT;
319  typedef typename _TraitsT::char_class_type _CharClassT;
320 
321  public:
322  _BracketMatcher(bool __is_non_matching,
323  const _TraitsT& __traits)
324  : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
325  _M_is_non_matching(__is_non_matching)
326 #ifdef _GLIBCXX_DEBUG
327  , _M_is_ready(false)
328 #endif
329  { }
330 
331  bool
332  operator()(_CharT __ch) const
333  {
334  _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
335  return _M_apply(__ch, _IsChar());
336  }
337 
338  void
339  _M_add_char(_CharT __c)
340  {
341  _M_char_set.push_back(_M_translator._M_translate(__c));
342 #ifdef _GLIBCXX_DEBUG
343  _M_is_ready = false;
344 #endif
345  }
346 
347  _StringT
348  _M_add_collate_element(const _StringT& __s)
349  {
350  auto __st = _M_traits.lookup_collatename(__s.data(),
351  __s.data() + __s.size());
352  if (__st.empty())
353  __throw_regex_error(regex_constants::error_collate);
354  _M_char_set.push_back(_M_translator._M_translate(__st[0]));
355 #ifdef _GLIBCXX_DEBUG
356  _M_is_ready = false;
357 #endif
358  return __st;
359  }
360 
361  void
362  _M_add_equivalence_class(const _StringT& __s)
363  {
364  auto __st = _M_traits.lookup_collatename(__s.data(),
365  __s.data() + __s.size());
366  if (__st.empty())
367  __throw_regex_error(regex_constants::error_collate);
368  __st = _M_traits.transform_primary(__st.data(),
369  __st.data() + __st.size());
370  _M_equiv_set.push_back(__st);
371 #ifdef _GLIBCXX_DEBUG
372  _M_is_ready = false;
373 #endif
374  }
375 
376  // __neg should be true for \D, \S and \W only.
377  void
378  _M_add_character_class(const _StringT& __s, bool __neg)
379  {
380  auto __mask = _M_traits.lookup_classname(__s.data(),
381  __s.data() + __s.size(),
382  __icase);
383  if (__mask == 0)
384  __throw_regex_error(regex_constants::error_ctype);
385  if (!__neg)
386  _M_class_set |= __mask;
387  else
388  _M_neg_class_set.push_back(__mask);
389 #ifdef _GLIBCXX_DEBUG
390  _M_is_ready = false;
391 #endif
392  }
393 
394  void
395  _M_make_range(_CharT __l, _CharT __r)
396  {
397  if (__l > __r)
398  __throw_regex_error(regex_constants::error_range);
399  _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
400  _M_translator._M_transform(__r)));
401 #ifdef _GLIBCXX_DEBUG
402  _M_is_ready = false;
403 #endif
404  }
405 
406  void
407  _M_ready()
408  {
409  _M_make_cache(_IsChar());
410 #ifdef _GLIBCXX_DEBUG
411  _M_is_ready = true;
412 #endif
413  }
414 
415  private:
416  typedef typename is_same<_CharT, char>::type _IsChar;
417  struct _Dummy { };
418  typedef typename conditional<_IsChar::value,
419  std::bitset<1 << (8 * sizeof(_CharT))>,
420  _Dummy>::type _CacheT;
421  typedef typename make_unsigned<_CharT>::type _UnsignedCharT;
422 
423  private:
424  bool
425  _M_apply(_CharT __ch, false_type) const;
426 
427  bool
428  _M_apply(_CharT __ch, true_type) const
429  { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
430 
431  void
432  _M_make_cache(true_type)
433  {
434  for (int __i = 0; __i < _M_cache.size(); __i++)
435  _M_cache[static_cast<_UnsignedCharT>(__i)] =
436  _M_apply(__i, false_type());
437  }
438 
439  void
440  _M_make_cache(false_type)
441  { }
442 
443  private:
444  _CacheT _M_cache;
445  std::vector<_CharT> _M_char_set;
446  std::vector<_StringT> _M_equiv_set;
448  std::vector<_CharClassT> _M_neg_class_set;
449  _CharClassT _M_class_set;
450  _TransT _M_translator;
451  const _TraitsT& _M_traits;
452  bool _M_is_non_matching;
453 #ifdef _GLIBCXX_DEBUG
454  bool _M_is_ready;
455 #endif
456  };
457 
458  //@} regex-detail
459 _GLIBCXX_END_NAMESPACE_VERSION
460 } // namespace __detail
461 } // namespace std
462 
463 #include <bits/regex_compiler.tcc>
Primary class template ctype facet.This template class defines classification and conversion function...
constexpr error_type error_collate(_S_error_collate)
reference top()
Definition: stl_stack.h:162
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
Describes a sequence of one or more _State, its current start and end(s). This structure contains fra...
constexpr error_type error_range(_S_error_range)
ISO C++ entities toplevel namespace is std.
syntax_option_type
This is a bitmask type indicating how to interpret the regex.
Scans an input range for regex tokens.
Builds an NFA from an input iterator interval.
constexpr error_type error_ctype(_S_error_ctype)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
Matches a character range (bracket expression)
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
void pop()
Removes first element.
Definition: stl_stack.h:215
A smart pointer with reference-counted copy semantics.
Definition: shared_ptr.h:93