libstdc++
regex_compiler.h
Go to the documentation of this file.
00001 // class template regex -*- C++ -*-
00002 
00003 // Copyright (C) 2010-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /**
00026  *  @file bits/regex_compiler.h
00027  *  This is an internal header file, included by other library headers.
00028  *  Do not attempt to use it directly. @headername{regex}
00029  */
00030 
00031 namespace std _GLIBCXX_VISIBILITY(default)
00032 {
00033 namespace __detail
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00036 
00037   /**
00038    * @addtogroup regex-detail
00039    * @{
00040    */
00041 
00042   template<typename, bool, bool>
00043     struct _BracketMatcher;
00044 
00045   /**
00046    * @brief Builds an NFA from an input iterator range.
00047    *
00048    * The %_TraitsT type should fulfill requirements [28.3].
00049    */
00050   template<typename _TraitsT>
00051     class _Compiler
00052     {
00053     public:
00054       typedef typename _TraitsT::char_type        _CharT;
00055       typedef const _CharT*                       _IterT;
00056       typedef _NFA<_TraitsT>                      _RegexT;
00057       typedef regex_constants::syntax_option_type _FlagT;
00058 
00059       _Compiler(_IterT __b, _IterT __e,
00060                 const typename _TraitsT::locale_type& __traits, _FlagT __flags);
00061 
00062       shared_ptr<const _RegexT>
00063       _M_get_nfa()
00064       { return std::move(_M_nfa); }
00065 
00066     private:
00067       typedef _Scanner<_CharT>               _ScannerT;
00068       typedef typename _TraitsT::string_type _StringT;
00069       typedef typename _ScannerT::_TokenT    _TokenT;
00070       typedef _StateSeq<_TraitsT>            _StateSeqT;
00071       typedef std::stack<_StateSeqT>         _StackT;
00072       typedef std::ctype<_CharT>             _CtypeT;
00073 
00074       // accepts a specific token or returns false.
00075       bool
00076       _M_match_token(_TokenT __token);
00077 
00078       void
00079       _M_disjunction();
00080 
00081       void
00082       _M_alternative();
00083 
00084       bool
00085       _M_term();
00086 
00087       bool
00088       _M_assertion();
00089 
00090       bool
00091       _M_quantifier();
00092 
00093       bool
00094       _M_atom();
00095 
00096       bool
00097       _M_bracket_expression();
00098 
00099       template<bool __icase, bool __collate>
00100         void
00101         _M_insert_any_matcher_ecma();
00102 
00103       template<bool __icase, bool __collate>
00104         void
00105         _M_insert_any_matcher_posix();
00106 
00107       template<bool __icase, bool __collate>
00108         void
00109         _M_insert_char_matcher();
00110 
00111       template<bool __icase, bool __collate>
00112         void
00113         _M_insert_character_class_matcher();
00114 
00115       template<bool __icase, bool __collate>
00116         void
00117         _M_insert_bracket_matcher(bool __neg);
00118 
00119       // Returns true if successfully matched one term and should continue.
00120       // Returns false if the compiler should move on.
00121       template<bool __icase, bool __collate>
00122         bool
00123         _M_expression_term(pair<bool, _CharT>& __last_char,
00124                            _BracketMatcher<_TraitsT, __icase, __collate>&
00125                            __matcher);
00126 
00127       int
00128       _M_cur_int_value(int __radix);
00129 
00130       bool
00131       _M_try_char();
00132 
00133       _StateSeqT
00134       _M_pop()
00135       {
00136         auto ret = _M_stack.top();
00137         _M_stack.pop();
00138         return ret;
00139       }
00140 
00141       _FlagT              _M_flags;
00142       _ScannerT           _M_scanner;
00143       shared_ptr<_RegexT> _M_nfa;
00144       _StringT            _M_value;
00145       _StackT             _M_stack;
00146       const _TraitsT&     _M_traits;
00147       const _CtypeT&      _M_ctype;
00148     };
00149 
00150   template<typename _Tp>
00151     struct __has_contiguous_iter : std::false_type { };
00152 
00153   template<typename _Ch, typename _Tr, typename _Alloc>
00154     struct __has_contiguous_iter<std::basic_string<_Ch, _Tr, _Alloc>>
00155     : std::true_type
00156     { };
00157 
00158   template<typename _Tp, typename _Alloc>
00159     struct __has_contiguous_iter<std::vector<_Tp, _Alloc>>
00160     : std::true_type
00161     { };
00162 
00163   template<typename _Tp>
00164     struct __is_contiguous_normal_iter : std::false_type { };
00165 
00166   template<typename _CharT>
00167     struct __is_contiguous_normal_iter<_CharT*> : std::true_type { };
00168 
00169   template<typename _Tp, typename _Cont>
00170     struct
00171     __is_contiguous_normal_iter<__gnu_cxx::__normal_iterator<_Tp, _Cont>>
00172     : __has_contiguous_iter<_Cont>::type
00173     { };
00174 
00175   template<typename _Iter, typename _TraitsT>
00176     using __enable_if_contiguous_normal_iter
00177       = typename enable_if< __is_contiguous_normal_iter<_Iter>::value,
00178                            std::shared_ptr<const _NFA<_TraitsT>> >::type;
00179 
00180   template<typename _Iter, typename _TraitsT>
00181     using __disable_if_contiguous_normal_iter
00182       = typename enable_if< !__is_contiguous_normal_iter<_Iter>::value,
00183                            std::shared_ptr<const _NFA<_TraitsT>> >::type;
00184 
00185   template<typename _FwdIter, typename _TraitsT>
00186     inline __enable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
00187     __compile_nfa(_FwdIter __first, _FwdIter __last,
00188                   const typename _TraitsT::locale_type& __loc,
00189                   regex_constants::syntax_option_type __flags)
00190     {
00191       size_t __len = __last - __first;
00192       const auto* __cfirst = __len ? std::__addressof(*__first) : nullptr;
00193       using _Cmplr = _Compiler<_TraitsT>;
00194       return _Cmplr(__cfirst, __cfirst + __len, __loc, __flags)._M_get_nfa();
00195     }
00196 
00197   template<typename _FwdIter, typename _TraitsT>
00198     inline __disable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
00199     __compile_nfa(_FwdIter __first, _FwdIter __last,
00200                   const typename _TraitsT::locale_type& __loc,
00201                   regex_constants::syntax_option_type __flags)
00202     {
00203       basic_string<typename _TraitsT::char_type> __str(__first, __last);
00204       return __compile_nfa(__str.data(), __str.data() + __str.size(), __loc,
00205           __flags);
00206     }
00207 
00208   // [28.13.14]
00209   template<typename _TraitsT, bool __icase, bool __collate>
00210     class _RegexTranslator
00211     {
00212     public:
00213       typedef typename _TraitsT::char_type            _CharT;
00214       typedef typename _TraitsT::string_type          _StringT;
00215       typedef typename std::conditional<__collate,
00216                                         _StringT,
00217                                         _CharT>::type _StrTransT;
00218 
00219       explicit
00220       _RegexTranslator(const _TraitsT& __traits)
00221       : _M_traits(__traits)
00222       { }
00223 
00224       _CharT
00225       _M_translate(_CharT __ch) const
00226       {
00227         if (__icase)
00228           return _M_traits.translate_nocase(__ch);
00229         else if (__collate)
00230           return _M_traits.translate(__ch);
00231         else
00232           return __ch;
00233       }
00234 
00235       _StrTransT
00236       _M_transform(_CharT __ch) const
00237       {
00238         return _M_transform_impl(__ch, typename integral_constant<bool,
00239                                  __collate>::type());
00240       }
00241 
00242     private:
00243       _StrTransT
00244       _M_transform_impl(_CharT __ch, false_type) const
00245       { return __ch; }
00246 
00247       _StrTransT
00248       _M_transform_impl(_CharT __ch, true_type) const
00249       {
00250         _StrTransT __str = _StrTransT(1, _M_translate(__ch));
00251         return _M_traits.transform(__str.begin(), __str.end());
00252       }
00253 
00254       const _TraitsT& _M_traits;
00255     };
00256 
00257   template<typename _TraitsT>
00258     class _RegexTranslator<_TraitsT, false, false>
00259     {
00260     public:
00261       typedef typename _TraitsT::char_type _CharT;
00262       typedef _CharT                       _StrTransT;
00263 
00264       explicit
00265       _RegexTranslator(const _TraitsT&)
00266       { }
00267 
00268       _CharT
00269       _M_translate(_CharT __ch) const
00270       { return __ch; }
00271 
00272       _StrTransT
00273       _M_transform(_CharT __ch) const
00274       { return __ch; }
00275     };
00276 
00277   template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
00278     struct _AnyMatcher;
00279 
00280   template<typename _TraitsT, bool __icase, bool __collate>
00281     struct _AnyMatcher<_TraitsT, false, __icase, __collate>
00282     {
00283       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00284       typedef typename _TransT::_CharT                       _CharT;
00285 
00286       explicit
00287       _AnyMatcher(const _TraitsT& __traits)
00288       : _M_translator(__traits)
00289       { }
00290 
00291       bool
00292       operator()(_CharT __ch) const
00293       {
00294         static auto __nul = _M_translator._M_translate('\0');
00295         return _M_translator._M_translate(__ch) != __nul;
00296       }
00297 
00298       _TransT _M_translator;
00299     };
00300 
00301   template<typename _TraitsT, bool __icase, bool __collate>
00302     struct _AnyMatcher<_TraitsT, true, __icase, __collate>
00303     {
00304       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00305       typedef typename _TransT::_CharT                       _CharT;
00306 
00307       explicit
00308       _AnyMatcher(const _TraitsT& __traits)
00309       : _M_translator(__traits)
00310       { }
00311 
00312       bool
00313       operator()(_CharT __ch) const
00314       { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
00315 
00316       bool
00317       _M_apply(_CharT __ch, true_type) const
00318       {
00319         auto __c = _M_translator._M_translate(__ch);
00320         auto __n = _M_translator._M_translate('\n');
00321         auto __r = _M_translator._M_translate('\r');
00322         return __c != __n && __c != __r;
00323       }
00324 
00325       bool
00326       _M_apply(_CharT __ch, false_type) const
00327       {
00328         auto __c = _M_translator._M_translate(__ch);
00329         auto __n = _M_translator._M_translate('\n');
00330         auto __r = _M_translator._M_translate('\r');
00331         auto __u2028 = _M_translator._M_translate(u'\u2028');
00332         auto __u2029 = _M_translator._M_translate(u'\u2029');
00333         return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
00334       }
00335 
00336       _TransT _M_translator;
00337     };
00338 
00339   template<typename _TraitsT, bool __icase, bool __collate>
00340     struct _CharMatcher
00341     {
00342       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00343       typedef typename _TransT::_CharT                       _CharT;
00344 
00345       _CharMatcher(_CharT __ch, const _TraitsT& __traits)
00346       : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
00347       { }
00348 
00349       bool
00350       operator()(_CharT __ch) const
00351       { return _M_ch == _M_translator._M_translate(__ch); }
00352 
00353       _TransT _M_translator;
00354       _CharT  _M_ch;
00355     };
00356 
00357   /// Matches a character range (bracket expression)
00358   template<typename _TraitsT, bool __icase, bool __collate>
00359     struct _BracketMatcher
00360     {
00361     public:
00362       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00363       typedef typename _TransT::_CharT                       _CharT;
00364       typedef typename _TransT::_StrTransT                   _StrTransT;
00365       typedef typename _TraitsT::string_type                 _StringT;
00366       typedef typename _TraitsT::char_class_type             _CharClassT;
00367 
00368     public:
00369       _BracketMatcher(bool __is_non_matching,
00370                       const _TraitsT& __traits)
00371       : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
00372       _M_is_non_matching(__is_non_matching)
00373 #ifdef _GLIBCXX_DEBUG
00374       , _M_is_ready(false)
00375 #endif
00376       { }
00377 
00378       bool
00379       operator()(_CharT __ch) const
00380       {
00381         _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
00382         return _M_apply(__ch, _UseCache());
00383       }
00384 
00385       void
00386       _M_add_char(_CharT __c)
00387       {
00388         _M_char_set.push_back(_M_translator._M_translate(__c));
00389 #ifdef _GLIBCXX_DEBUG
00390         _M_is_ready = false;
00391 #endif
00392       }
00393 
00394       _StringT
00395       _M_add_collate_element(const _StringT& __s)
00396       {
00397         auto __st = _M_traits.lookup_collatename(__s.data(),
00398                                                  __s.data() + __s.size());
00399         if (__st.empty())
00400           __throw_regex_error(regex_constants::error_collate);
00401         _M_char_set.push_back(_M_translator._M_translate(__st[0]));
00402 #ifdef _GLIBCXX_DEBUG
00403         _M_is_ready = false;
00404 #endif
00405         return __st;
00406       }
00407 
00408       void
00409       _M_add_equivalence_class(const _StringT& __s)
00410       {
00411         auto __st = _M_traits.lookup_collatename(__s.data(),
00412                                                  __s.data() + __s.size());
00413         if (__st.empty())
00414           __throw_regex_error(regex_constants::error_collate);
00415         __st = _M_traits.transform_primary(__st.data(),
00416                                            __st.data() + __st.size());
00417         _M_equiv_set.push_back(__st);
00418 #ifdef _GLIBCXX_DEBUG
00419         _M_is_ready = false;
00420 #endif
00421       }
00422 
00423       // __neg should be true for \D, \S and \W only.
00424       void
00425       _M_add_character_class(const _StringT& __s, bool __neg)
00426       {
00427         auto __mask = _M_traits.lookup_classname(__s.data(),
00428                                                  __s.data() + __s.size(),
00429                                                  __icase);
00430         if (__mask == 0)
00431           __throw_regex_error(regex_constants::error_ctype);
00432         if (!__neg)
00433           _M_class_set |= __mask;
00434         else
00435           _M_neg_class_set.push_back(__mask);
00436 #ifdef _GLIBCXX_DEBUG
00437         _M_is_ready = false;
00438 #endif
00439       }
00440 
00441       void
00442       _M_make_range(_CharT __l, _CharT __r)
00443       {
00444         if (__l > __r)
00445           __throw_regex_error(regex_constants::error_range);
00446         _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
00447                                          _M_translator._M_transform(__r)));
00448 #ifdef _GLIBCXX_DEBUG
00449         _M_is_ready = false;
00450 #endif
00451       }
00452 
00453       void
00454       _M_ready()
00455       {
00456         std::sort(_M_char_set.begin(), _M_char_set.end());
00457         auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
00458         _M_char_set.erase(__end, _M_char_set.end());
00459         _M_make_cache(_UseCache());
00460 #ifdef _GLIBCXX_DEBUG
00461         _M_is_ready = true;
00462 #endif
00463       }
00464 
00465     private:
00466       // Currently we only use the cache for char
00467       typedef typename std::is_same<_CharT, char>::type _UseCache;
00468 
00469       static constexpr size_t
00470       _S_cache_size()
00471       {
00472         return 1ul << (sizeof(_CharT) * __CHAR_BIT__ * int(_UseCache::value));
00473       }
00474 
00475       struct _Dummy { };
00476       typedef typename std::conditional<_UseCache::value,
00477                                         std::bitset<_S_cache_size()>,
00478                                         _Dummy>::type _CacheT;
00479       typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
00480 
00481       bool
00482       _M_apply(_CharT __ch, false_type) const;
00483 
00484       bool
00485       _M_apply(_CharT __ch, true_type) const
00486       { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
00487 
00488       void
00489       _M_make_cache(true_type)
00490       {
00491         for (unsigned __i = 0; __i < _M_cache.size(); __i++)
00492           _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
00493       }
00494 
00495       void
00496       _M_make_cache(false_type)
00497       { }
00498 
00499     private:
00500       std::vector<_CharT>                       _M_char_set;
00501       std::vector<_StringT>                     _M_equiv_set;
00502       std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
00503       std::vector<_CharClassT>                  _M_neg_class_set;
00504       _CharClassT                               _M_class_set;
00505       _TransT                                   _M_translator;
00506       const _TraitsT&                           _M_traits;
00507       bool                                      _M_is_non_matching;
00508       _CacheT                                   _M_cache;
00509 #ifdef _GLIBCXX_DEBUG
00510       bool                                      _M_is_ready;
00511 #endif
00512     };
00513 
00514  //@} regex-detail
00515 _GLIBCXX_END_NAMESPACE_VERSION
00516 } // namespace __detail
00517 } // namespace std
00518 
00519 #include <bits/regex_compiler.tcc>