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