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 // TODO: 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,
  56     typename _CharT, typename _TraitsT>
  57     class _Executor
  58     {
  59     public:
  60       typedef match_results<_BiIter, _Alloc>          _ResultsT;
  61       typedef std::vector<sub_match<_BiIter>, _Alloc> _ResultsVec;
  62       typedef regex_constants::match_flag_type        _FlagT;
  63
  64       virtual
  65       ~_Executor()
  66       { }
  67
  68       // Set matched when string exactly match the pattern.
  69       virtual void
  70       _M_match() = 0;
  71
  72       // Set matched when some prefix of the string matches the pattern.
  73       virtual void
  74       _M_search_from_first() = 0;
  75
  76     protected:
  77       typedef typename _NFA<_CharT, _TraitsT>::_SizeT _SizeT;
  78       _Executor(_BiIter    __begin,
  79                 _BiIter    __end,
  80                 _ResultsT& __results,
  81                 _FlagT     __flags,
  82                 _SizeT     __size)
  83       : _M_current(__begin), _M_end(__end), _M_results(__results),
  84         _M_flags(__flags)
  85       {
  86         __size += 2;
  87         _M_results.resize(__size);
  88         for (auto __i = 0; __i < __size; __i++)
  89           _M_results[__i].matched = false;
  90       }
  91
  92       _BiIter       _M_current;
  93       _BiIter       _M_end;
  94       _ResultsVec&  _M_results;
  95       _FlagT        _M_flags;
  96     };
  97
  98   // A _DFSExecutor perform a DFS on given NFA and input string. At the very
  99   // beginning the executor stands in the start state, then it try every
 100   // possible state transition in current state recursively. Some state
 101   // transitions consume input string, say, a single-char-matcher or a
 102   // back-reference matcher; some not, like assertion or other anchor nodes.
 103   // When the input is exhausted and the current state is an accepting state,
 104   // the whole executor return true.
 105   //
 106   // TODO: This approach is exponentially slow for certain input.
 107   //       Try to compile the NFA to a DFA.
 108   //
 109   // Time complexity: exponential
 110   // Space complexity: O(__end - __begin)
 111   template<typename _BiIter, typename _Alloc,
 112     typename _CharT, typename _TraitsT>
 113     class _DFSExecutor
 114     : public _Executor<_BiIter, _Alloc, _CharT, _TraitsT>
 115     {
 116     public:
 117       typedef _Executor<_BiIter, _Alloc, _CharT, _TraitsT> _BaseT;
 118       typedef _NFA<_CharT, _TraitsT>                       _RegexT;
 119       typedef typename _BaseT::_ResultsT                   _ResultsT;
 120       typedef typename _BaseT::_ResultsVec                 _ResultsVec;
 121       typedef regex_constants::match_flag_type             _FlagT;
 122
 123       _DFSExecutor(_BiIter         __begin,
 124                    _BiIter         __end,
 125                    _ResultsT&      __results,
 126                    const _RegexT&  __nfa,
 127                    const _TraitsT& __traits,
 128                    _FlagT          __flags)
 129       : _BaseT(__begin, __end, __results, __flags, __nfa._M_sub_count()),
 130         _M_traits(__traits), _M_nfa(__nfa), _M_results_ret(this->_M_results)
 131       { }
 132
 133       void
 134       _M_match()
 135       { _M_dfs<true>(_M_nfa._M_start()); }
 136
 137       void
 138       _M_search_from_first()
 139       { _M_dfs<false>(_M_nfa._M_start()); }
 140
 141     private:
 142       template<bool __match_mode>
 143         bool
 144         _M_dfs(_StateIdT __i);
 145
 146       _ResultsVec     _M_results_ret;
 147       const _TraitsT& _M_traits;
 148       const _RegexT&  _M_nfa;
 149     };
 150
 151   // Like the DFS approach, it try every possible state transition; Unlike DFS,
 152   // it uses a queue instead of a stack to store matching states. It's a BFS
 153   // approach.
 154   //
 155   // Russ Cox's article(http://swtch.com/~rsc/regexp/regexp1.html) explained
 156   // this algorithm clearly.
 157   //
 158   // Every entry of _M_covered saves the solution(grouping status) for every
 159   // matching head. When states transit, solutions will be compared and
 160   // deduplicated(based on which greedy mode we have).
 161   //
 162   // Time complexity: O((__end - __begin) * _M_nfa.size())
 163   // Space complexity: O(_M_nfa.size() * _M_nfa.mark_count())
 164   template<typename _BiIter, typename _Alloc,
 165     typename _CharT, typename _TraitsT>
 166     class _BFSExecutor
 167     : public _Executor<_BiIter, _Alloc, _CharT, _TraitsT>
 168     {
 169     public:
 170       typedef _Executor<_BiIter, _Alloc, _CharT, _TraitsT> _BaseT;
 171       typedef _NFA<_CharT, _TraitsT>                       _RegexT;
 172       typedef typename _BaseT::_ResultsT                   _ResultsT;
 173       typedef typename _BaseT::_ResultsVec                 _ResultsVec;
 174       typedef std::unique_ptr<_ResultsVec>                 _ResultsPtr;
 175       typedef regex_constants::match_flag_type             _FlagT;
 176
 177       _BFSExecutor(_BiIter        __begin,
 178                    _BiIter        __end,
 179                    _ResultsT&     __results,
 180                    const _RegexT& __nfa,
 181                    _FlagT         __flags)
 182       : _BaseT(__begin, __end, __results, __flags, __nfa._M_sub_count()),
 183         _M_nfa(__nfa)
 184       {
 185         if (_M_nfa._M_start() != _S_invalid_state_id)
 186           _M_covered[_M_nfa._M_start()] =
 187             _ResultsPtr(new _ResultsVec(this->_M_results));
 188         _M_e_closure();
 189       }
 190
 191       void
 192       _M_match()
 193       { _M_main_loop<true>(); }
 194
 195       void
 196       _M_search_from_first()
 197       { _M_main_loop<false>(); }
 198
 199     private:
 200       template<bool __match_mode>
 201         void
 202         _M_main_loop();
 203
 204       void
 205       _M_e_closure();
 206
 207       void
 208       _M_move();
 209
 210       bool
 211       _M_match_less_than(const _ResultsVec& __u, const _ResultsVec& __v) const;
 212
 213       bool
 214       _M_includes_some() const;
 215
 216       std::map<_StateIdT, _ResultsPtr>     _M_covered;
 217       const _RegexT&                       _M_nfa;
 218     };
 219
 220  //@} regex-detail
 221 _GLIBCXX_END_NAMESPACE_VERSION
 222 } // namespace __detail
 223 } // namespace std
 224
 225 #include <bits/regex_executor.tcc>