libstdc++-v3/include/bits/regex_executor.h

   1 // class template regex -*- C++ -*-
   2
   3 // Copyright (C) 2013 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_executor.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 // FIXME convert comments to doxygen format.
  32
  33 namespace std _GLIBCXX_VISIBILITY(default)
  34 {
  35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  36   template<typename, typename>
  37     class basic_regex;
  38
  39   template<typename>
  40     class sub_match;
  41
  42   template<typename, typename>
  43     class match_results;
  44 _GLIBCXX_END_NAMESPACE_VERSION
  45
  46 namespace __detail
  47 {
  48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  49
  50   /**
  51    * @addtogroup regex-detail
  52    * @{
  53    */
  54
  55   template<typename _BiIter, typename _Alloc, typename _TraitsT,
  56            bool __dfs_mode>
  57     class _Executor
  58     {
  59     public:
  60       typedef typename iterator_traits<_BiIter>::value_type _CharT;
  61       typedef basic_regex<_CharT, _TraitsT>                 _RegexT;
  62       typedef std::vector<sub_match<_BiIter>, _Alloc>       _ResultsVec;
  63       typedef regex_constants::match_flag_type              _FlagT;
  64       typedef typename _TraitsT::char_class_type            _ClassT;
  65       typedef _NFA<_TraitsT>                                _NFAT;
  66
  67     public:
  68       _Executor(_BiIter         __begin,
  69                 _BiIter         __end,
  70                 _ResultsVec&    __results,
  71                 const _RegexT&  __re,
  72                 _FlagT          __flags)
  73       : _M_begin(__begin),
  74       _M_end(__end),
  75       _M_re(__re),
  76       _M_nfa(*__re._M_automaton),
  77       _M_results(__results),
  78       _M_match_queue(__dfs_mode ? nullptr
  79                      : new queue<pair<_StateIdT, _ResultsVec>>()),
  80       _M_visited(__dfs_mode ? nullptr : new vector<bool>(_M_nfa.size())),
  81       _M_flags((__flags & regex_constants::match_prev_avail)
  82                ? (__flags
  83                   & ~regex_constants::match_not_bol
  84                   & ~regex_constants::match_not_bow)
  85                : __flags),
  86       _M_start_state(_M_nfa._M_start())
  87       { }
  88
  89       // Set matched when string exactly match the pattern.
  90       bool
  91       _M_match()
  92       {
  93         _M_current = _M_begin;
  94         return _M_main<true>();
  95       }
  96
  97       // Set matched when some prefix of the string matches the pattern.
  98       bool
  99       _M_search_from_first()
 100       {
 101         _M_current = _M_begin;
 102         return _M_main<false>();
 103       }
 104
 105       bool
 106       _M_search();
 107
 108     private:
 109       template<bool __match_mode>
 110         void
 111         _M_dfs(_StateIdT __start);
 112
 113       template<bool __match_mode>
 114         bool
 115         _M_main();
 116
 117       bool
 118       _M_is_word(_CharT __ch) const
 119       {
 120         static const _CharT __s[2] = { 'w' };
 121         return _M_re._M_traits.isctype
 122           (__ch, _M_re._M_traits.lookup_classname(__s, __s+1));
 123       }
 124
 125       bool
 126       _M_at_begin() const
 127       {
 128         return _M_current == _M_begin
 129           && !(_M_flags & (regex_constants::match_not_bol
 130                            | regex_constants::match_prev_avail));
 131       }
 132
 133       bool
 134       _M_at_end() const
 135       {
 136         return _M_current == _M_end
 137           && !(_M_flags & regex_constants::match_not_eol);
 138       }
 139
 140       bool
 141       _M_word_boundary(_State<_TraitsT> __state) const;
 142
 143       bool
 144       _M_lookahead(_State<_TraitsT> __state);
 145
 146     public:
 147       _ResultsVec                                          _M_cur_results;
 148       _BiIter                                              _M_current;
 149       const _BiIter                                        _M_begin;
 150       const _BiIter                                        _M_end;
 151       const _RegexT&                                       _M_re;
 152       const _NFAT&                                         _M_nfa;
 153       _ResultsVec&                                         _M_results;
 154       // Used in BFS, saving states that need to be considered for the next
 155       // character.
 156       std::unique_ptr<queue<pair<_StateIdT, _ResultsVec>>> _M_match_queue;
 157       // Used in BFS, indicating that which state is already visited.
 158       std::unique_ptr<vector<bool>>                        _M_visited;
 159       _FlagT                                               _M_flags;
 160       // To record current solution.
 161       _StateIdT                                            _M_start_state;
 162       // Do we have a solution so far?
 163       bool                                                 _M_has_sol;
 164     };
 165
 166  //@} regex-detail
 167 _GLIBCXX_END_NAMESPACE_VERSION
 168 } // namespace __detail
 169 } // namespace std
 170
 171 #include <bits/regex_executor.tcc>