libstdc++-v3/include/bits/regex_grep_matcher.tcc

   1 // class template regex -*- C++ -*-
   2
   3 // Copyright (C) 2010 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_grep_matcher.tcc
  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 #include <regex>
  32
  33 namespace std _GLIBCXX_VISIBILITY(default)
  34 {
  35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  36
  37 namespace
  38 {
  39
  40   // A stack of states used in evaluating the NFA.
  41   typedef std::stack<std::__regex::_StateIdT,
  42                      std::vector<std::__regex::_StateIdT>
  43                      > _StateStack;
  44
  45   // Obtains the next state set given the current state set __s and the current
  46   // input character.
  47   inline std::__regex::_StateSet
  48   __move(const std::__regex::_PatternCursor& __p,
  49          const std::__regex::_Nfa& __nfa,
  50          const std::__regex::_StateSet& __s)
  51   {
  52     std::__regex::_StateSet __m;
  53     for (std::__regex::_StateSet::const_iterator __i = __s.begin();
  54          __i != __s.end(); ++__i)
  55       {
  56         if (*__i == std::__regex::_S_invalid_state_id)
  57           continue;
  58
  59         const std::__regex::_State& __state = __nfa[*__i];
  60         if (__state._M_opcode == std::__regex::_S_opcode_match
  61             && __state._M_matches(__p))
  62           __m.insert(__state._M_next);
  63       }
  64     return __m;
  65   }
  66
  67   // returns true if (__s intersect __t) is not empty
  68   inline bool
  69   __includes_some(const std::__regex::_StateSet& __s,
  70                   const std::__regex::_StateSet& __t)
  71   {
  72     if (__s.size() > 0 && __t.size() > 0)
  73       {
  74         std::__regex::_StateSet::const_iterator __first = __s.begin();
  75         std::__regex::_StateSet::const_iterator __second = __t.begin();
  76         while (__first != __s.end() && __second != __t.end())
  77           {
  78             if (*__first < *__second)
  79               ++__first;
  80             else if (*__second < *__first)
  81               ++__second;
  82             else
  83               return true;
  84           }
  85       }
  86     return false;
  87   }
  88
  89   // If an identified state __u is not already in the current state set __e,
  90   // insert it and push it on the current state stack __s.
  91   inline void
  92   __add_visited_state(const std::__regex::_StateIdT __u,
  93                       _StateStack&                  __s,
  94                       std::__regex::_StateSet&      __e)
  95   {
  96     if (__e.count(__u) == 0)
  97       {
  98         __e.insert(__u);
  99         __s.push(__u);
 100       }
 101   }
 102
 103 } // anonymous namespace
 104
 105 namespace __regex
 106 {
 107   inline _Grep_matcher::
 108   _Grep_matcher(_PatternCursor& __p, _Results& __r,
 109                 const _AutomatonPtr& __nfa,
 110                 regex_constants::match_flag_type __flags)
 111   : _M_nfa(static_pointer_cast<_Nfa>(__nfa)), _M_pattern(__p), _M_results(__r)
 112   {
 113     __regex::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start());
 114     for (; !_M_pattern._M_at_end(); _M_pattern._M_next())
 115       __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t));
 116
 117     _M_results._M_set_matched(0,
 118                               __includes_some(_M_nfa->_M_final_states(), __t));
 119   }
 120
 121   // Creates the e-closure set for the initial state __i.
 122   inline _StateSet _Grep_matcher::
 123   _M_e_closure(_StateIdT __i)
 124   {
 125     _StateSet __s;
 126     __s.insert(__i);
 127     _StateStack __stack;
 128     __stack.push(__i);
 129     return this->_M_e_closure(__stack, __s);
 130   }
 131
 132   // Creates the e-closure set for an arbitrary state set __s.
 133   inline _StateSet _Grep_matcher::
 134   _M_e_closure(const _StateSet& __s)
 135   {
 136     _StateStack __stack;
 137     for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i)
 138       __stack.push(*__i);
 139     return this->_M_e_closure(__stack, __s);
 140   }
 141
 142   inline _StateSet _Grep_matcher::
 143   _M_e_closure(_StateStack& __stack, const _StateSet& __s)
 144   {
 145     _StateSet __e = __s;
 146     while (!__stack.empty())
 147       {
 148         _StateIdT __t = __stack.top(); __stack.pop();
 149         if (__t == _S_invalid_state_id)
 150           continue;
 151         // for each __u with edge from __t to __u labeled e do ...
 152         const _State& __state = _M_nfa->operator[](__t);
 153         switch (__state._M_opcode)
 154           {
 155           case _S_opcode_alternative:
 156             __add_visited_state(__state._M_next, __stack, __e);
 157             __add_visited_state(__state._M_alt, __stack, __e);
 158             break;
 159           case _S_opcode_subexpr_begin:
 160             __add_visited_state(__state._M_next, __stack, __e);
 161             __state._M_tagger(_M_pattern, _M_results);
 162             break;
 163           case _S_opcode_subexpr_end:
 164             __add_visited_state(__state._M_next, __stack, __e);
 165             __state._M_tagger(_M_pattern, _M_results);
 166             _M_results._M_set_matched(__state._M_subexpr, true);
 167             break;
 168           case _S_opcode_accept:
 169             __add_visited_state(__state._M_next, __stack, __e);
 170             break;
 171           default:
 172             break;
 173           }
 174       }
 175     return __e;
 176   }
 177
 178 } // namespace __regex
 179
 180 _GLIBCXX_END_NAMESPACE_VERSION
 181 } // namespace