libstdc++
regex_compiler.h
Go to the documentation of this file.
00001 // class template regex -*- C++ -*-
00002 
00003 // Copyright (C) 2010-2014 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 interval.
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 _TraitsT& __traits, _FlagT __flags);
00061 
00062       std::shared_ptr<_RegexT>
00063       _M_get_nfa()
00064       { return make_shared<_RegexT>(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       const _TraitsT& _M_traits;
00143       const _CtypeT&  _M_ctype;
00144       _ScannerT       _M_scanner;
00145       _RegexT         _M_nfa;
00146       _StringT        _M_value;
00147       _StackT         _M_stack;
00148     };
00149 
00150   template<typename _TraitsT>
00151     inline std::shared_ptr<_NFA<_TraitsT>>
00152     __compile_nfa(const typename _TraitsT::char_type* __first,
00153           const typename _TraitsT::char_type* __last,
00154           const _TraitsT& __traits,
00155           regex_constants::syntax_option_type __flags)
00156     {
00157       using _Cmplr = _Compiler<_TraitsT>;
00158       return _Cmplr(__first, __last, __traits, __flags)._M_get_nfa();
00159     }
00160 
00161   // [28.13.14]
00162   template<typename _TraitsT, bool __icase, bool __collate>
00163     class _RegexTranslator
00164     {
00165     public:
00166       typedef typename _TraitsT::char_type        _CharT;
00167       typedef typename _TraitsT::string_type          _StringT;
00168       typedef typename std::conditional<__collate,
00169                     _StringT,
00170                     _CharT>::type _StrTransT;
00171 
00172       explicit
00173       _RegexTranslator(const _TraitsT& __traits)
00174       : _M_traits(__traits)
00175       { }
00176 
00177       _CharT
00178       _M_translate(_CharT __ch) const
00179       {
00180     if (__icase)
00181       return _M_traits.translate_nocase(__ch);
00182     else if (__collate)
00183       return _M_traits.translate(__ch);
00184     else
00185       return __ch;
00186       }
00187 
00188       _StrTransT
00189       _M_transform(_CharT __ch) const
00190       {
00191     return _M_transform_impl(__ch, typename integral_constant<bool,
00192                  __collate>::type());
00193       }
00194 
00195     private:
00196       _StrTransT
00197       _M_transform_impl(_CharT __ch, false_type) const
00198       { return __ch; }
00199 
00200       _StrTransT
00201       _M_transform_impl(_CharT __ch, true_type) const
00202       {
00203     _StrTransT __str = _StrTransT(1, _M_translate(__ch));
00204     return _M_traits.transform(__str.begin(), __str.end());
00205       }
00206 
00207       const _TraitsT& _M_traits;
00208     };
00209 
00210   template<typename _TraitsT>
00211     class _RegexTranslator<_TraitsT, false, false>
00212     {
00213     public:
00214       typedef typename _TraitsT::char_type _CharT;
00215       typedef _CharT                       _StrTransT;
00216 
00217       explicit
00218       _RegexTranslator(const _TraitsT& __traits)
00219       { }
00220 
00221       _CharT
00222       _M_translate(_CharT __ch) const
00223       { return __ch; }
00224 
00225       _StrTransT
00226       _M_transform(_CharT __ch) const
00227       { return __ch; }
00228     };
00229 
00230   template<typename _TraitsT, bool __is_ecma, bool __icase, bool __collate>
00231     struct _AnyMatcher;
00232 
00233   template<typename _TraitsT, bool __icase, bool __collate>
00234     struct _AnyMatcher<_TraitsT, false, __icase, __collate>
00235     {
00236       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00237       typedef typename _TransT::_CharT                       _CharT;
00238 
00239       explicit
00240       _AnyMatcher(const _TraitsT& __traits)
00241       : _M_translator(__traits)
00242       { }
00243 
00244       bool
00245       operator()(_CharT __ch) const
00246       {
00247     static auto __nul = _M_translator._M_translate('\0');
00248     return _M_translator._M_translate(__ch) != __nul;
00249       }
00250 
00251       _TransT _M_translator;
00252     };
00253 
00254   template<typename _TraitsT, bool __icase, bool __collate>
00255     struct _AnyMatcher<_TraitsT, true, __icase, __collate>
00256     {
00257       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00258       typedef typename _TransT::_CharT                       _CharT;
00259 
00260       explicit
00261       _AnyMatcher(const _TraitsT& __traits)
00262       : _M_translator(__traits)
00263       { }
00264 
00265       bool
00266       operator()(_CharT __ch) const
00267       { return _M_apply(__ch, typename is_same<_CharT, char>::type()); }
00268 
00269       bool
00270       _M_apply(_CharT __ch, true_type) const
00271       {
00272     auto __c = _M_translator._M_translate(__ch);
00273     auto __n = _M_translator._M_translate('\n');
00274     auto __r = _M_translator._M_translate('\r');
00275     return __c != __n && __c != __r;
00276       }
00277 
00278       bool
00279       _M_apply(_CharT __ch, false_type) const
00280       {
00281     auto __c = _M_translator._M_translate(__ch);
00282     auto __n = _M_translator._M_translate('\n');
00283     auto __r = _M_translator._M_translate('\r');
00284     auto __u2028 = _M_translator._M_translate(u'\u2028');
00285     auto __u2029 = _M_translator._M_translate(u'\u2029');
00286     return __c != __n && __c != __r && __c != __u2028 && __c != __u2029;
00287       }
00288 
00289       _TransT _M_translator;
00290     };
00291 
00292   template<typename _TraitsT, bool __icase, bool __collate>
00293     struct _CharMatcher
00294     {
00295       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00296       typedef typename _TransT::_CharT                       _CharT;
00297 
00298       _CharMatcher(_CharT __ch, const _TraitsT& __traits)
00299       : _M_translator(__traits), _M_ch(_M_translator._M_translate(__ch))
00300       { }
00301 
00302       bool
00303       operator()(_CharT __ch) const
00304       { return _M_ch == _M_translator._M_translate(__ch); }
00305 
00306       _TransT _M_translator;
00307       _CharT  _M_ch;
00308     };
00309 
00310   /// Matches a character range (bracket expression)
00311   template<typename _TraitsT, bool __icase, bool __collate>
00312     struct _BracketMatcher
00313     {
00314     public:
00315       typedef _RegexTranslator<_TraitsT, __icase, __collate> _TransT;
00316       typedef typename _TransT::_CharT                       _CharT;
00317       typedef typename _TransT::_StrTransT                   _StrTransT;
00318       typedef typename _TraitsT::string_type                 _StringT;
00319       typedef typename _TraitsT::char_class_type             _CharClassT;
00320 
00321     public:
00322       _BracketMatcher(bool __is_non_matching,
00323               const _TraitsT& __traits)
00324       : _M_class_set(0), _M_translator(__traits), _M_traits(__traits),
00325       _M_is_non_matching(__is_non_matching)
00326 #ifdef _GLIBCXX_DEBUG
00327       , _M_is_ready(false)
00328 #endif
00329       { }
00330 
00331       bool
00332       operator()(_CharT __ch) const
00333       {
00334     _GLIBCXX_DEBUG_ASSERT(_M_is_ready);
00335     return _M_apply(__ch, _IsChar());
00336       }
00337 
00338       void
00339       _M_add_char(_CharT __c)
00340       {
00341     _M_char_set.push_back(_M_translator._M_translate(__c));
00342 #ifdef _GLIBCXX_DEBUG
00343     _M_is_ready = false;
00344 #endif
00345       }
00346 
00347       _StringT
00348       _M_add_collate_element(const _StringT& __s)
00349       {
00350     auto __st = _M_traits.lookup_collatename(__s.data(),
00351                          __s.data() + __s.size());
00352     if (__st.empty())
00353       __throw_regex_error(regex_constants::error_collate);
00354     _M_char_set.push_back(_M_translator._M_translate(__st[0]));
00355 #ifdef _GLIBCXX_DEBUG
00356     _M_is_ready = false;
00357 #endif
00358     return __st;
00359       }
00360 
00361       void
00362       _M_add_equivalence_class(const _StringT& __s)
00363       {
00364     auto __st = _M_traits.lookup_collatename(__s.data(),
00365                          __s.data() + __s.size());
00366     if (__st.empty())
00367       __throw_regex_error(regex_constants::error_collate);
00368     __st = _M_traits.transform_primary(__st.data(),
00369                        __st.data() + __st.size());
00370     _M_equiv_set.push_back(__st);
00371 #ifdef _GLIBCXX_DEBUG
00372     _M_is_ready = false;
00373 #endif
00374       }
00375 
00376       // __neg should be true for \D, \S and \W only.
00377       void
00378       _M_add_character_class(const _StringT& __s, bool __neg)
00379       {
00380     auto __mask = _M_traits.lookup_classname(__s.data(),
00381                          __s.data() + __s.size(),
00382                          __icase);
00383     if (__mask == 0)
00384       __throw_regex_error(regex_constants::error_ctype);
00385     if (!__neg)
00386       _M_class_set |= __mask;
00387     else
00388       _M_neg_class_set.push_back(__mask);
00389 #ifdef _GLIBCXX_DEBUG
00390     _M_is_ready = false;
00391 #endif
00392       }
00393 
00394       void
00395       _M_make_range(_CharT __l, _CharT __r)
00396       {
00397     if (__l > __r)
00398       __throw_regex_error(regex_constants::error_range);
00399     _M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
00400                      _M_translator._M_transform(__r)));
00401 #ifdef _GLIBCXX_DEBUG
00402     _M_is_ready = false;
00403 #endif
00404       }
00405 
00406       void
00407       _M_ready()
00408       {
00409     _M_make_cache(_IsChar());
00410 #ifdef _GLIBCXX_DEBUG
00411     _M_is_ready = true;
00412 #endif
00413       }
00414 
00415     private:
00416       typedef typename is_same<_CharT, char>::type _IsChar;
00417       struct _Dummy { };
00418       typedef typename conditional<_IsChar::value,
00419                    std::bitset<1 << (8 * sizeof(_CharT))>,
00420                    _Dummy>::type _CacheT;
00421       typedef typename make_unsigned<_CharT>::type _UnsignedCharT;
00422 
00423     private:
00424       bool
00425       _M_apply(_CharT __ch, false_type) const;
00426 
00427       bool
00428       _M_apply(_CharT __ch, true_type) const
00429       { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
00430 
00431       void
00432       _M_make_cache(true_type)
00433       {
00434     for (int __i = 0; __i < _M_cache.size(); __i++)
00435       _M_cache[static_cast<_UnsignedCharT>(__i)] =
00436         _M_apply(__i, false_type());
00437       }
00438 
00439       void
00440       _M_make_cache(false_type)
00441       { }
00442 
00443     private:
00444       _CacheT                                   _M_cache;
00445       std::vector<_CharT>                       _M_char_set;
00446       std::vector<_StringT>                     _M_equiv_set;
00447       std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
00448       std::vector<_CharClassT>                  _M_neg_class_set;
00449       _CharClassT                               _M_class_set;
00450       _TransT                                   _M_translator;
00451       const _TraitsT&                           _M_traits;
00452       bool                                      _M_is_non_matching;
00453 #ifdef _GLIBCXX_DEBUG
00454       bool                                      _M_is_ready;
00455 #endif
00456     };
00457 
00458  //@} regex-detail
00459 _GLIBCXX_END_NAMESPACE_VERSION
00460 } // namespace __detail
00461 } // namespace std
00462 
00463 #include <bits/regex_compiler.tcc>