libstdc++

regex_grep_matcher.tcc

Go to the documentation of this file.
00001 // class template regex -*- C++ -*-
00002 
00003 // Copyright (C) 2010 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_grep_matcher.tcc
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 #include <regex>
00032 
00033 namespace std _GLIBCXX_VISIBILITY(default)
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00036 
00037 namespace
00038 {
00039 
00040   // A stack of states used in evaluating the NFA.
00041   typedef std::stack<std::__regex::_StateIdT,
00042                      std::vector<std::__regex::_StateIdT>
00043              > _StateStack;
00044 
00045   // Obtains the next state set given the current state set __s and the current
00046   // input character.
00047   inline std::__regex::_StateSet
00048   __move(const std::__regex::_PatternCursor& __p,
00049          const std::__regex::_Nfa& __nfa,
00050          const std::__regex::_StateSet& __s)
00051   {
00052     std::__regex::_StateSet __m;
00053     for (std::__regex::_StateSet::const_iterator __i = __s.begin();
00054      __i != __s.end(); ++__i)
00055       {
00056     if (*__i == std::__regex::_S_invalid_state_id)
00057       continue;
00058 
00059     const std::__regex::_State& __state = __nfa[*__i];
00060     if (__state._M_opcode == std::__regex::_S_opcode_match
00061         && __state._M_matches(__p))
00062       __m.insert(__state._M_next);
00063       }
00064     return __m;
00065   }
00066 
00067   // returns true if (__s intersect __t) is not empty
00068   inline bool
00069   __includes_some(const std::__regex::_StateSet& __s,
00070                   const std::__regex::_StateSet& __t)
00071   {
00072     if (__s.size() > 0 && __t.size() > 0)
00073       {
00074     std::__regex::_StateSet::const_iterator __first = __s.begin();
00075     std::__regex::_StateSet::const_iterator __second = __t.begin();
00076     while (__first != __s.end() && __second != __t.end())
00077       {
00078         if (*__first < *__second)
00079           ++__first;
00080         else if (*__second < *__first)
00081           ++__second;
00082         else
00083           return true;
00084       }
00085       }
00086     return false;
00087   }
00088 
00089   // If an identified state __u is not already in the current state set __e,
00090   // insert it and push it on the current state stack __s.
00091   inline void
00092   __add_visited_state(const std::__regex::_StateIdT __u,
00093                       _StateStack&                  __s,
00094                       std::__regex::_StateSet&      __e)
00095   {
00096     if (__e.count(__u) == 0)
00097       {
00098     __e.insert(__u);
00099     __s.push(__u);
00100       }
00101   }
00102 
00103 } // anonymous namespace
00104 
00105 namespace __regex
00106 {
00107   inline _Grep_matcher::
00108   _Grep_matcher(_PatternCursor& __p, _Results& __r,
00109         const _AutomatonPtr& __nfa,
00110         regex_constants::match_flag_type __flags)
00111   : _M_nfa(static_pointer_cast<_Nfa>(__nfa)), _M_pattern(__p), _M_results(__r)
00112   {
00113     __regex::_StateSet __t = this->_M_e_closure(_M_nfa->_M_start());
00114     for (; !_M_pattern._M_at_end(); _M_pattern._M_next())
00115       __t = this->_M_e_closure(__move(_M_pattern, *_M_nfa, __t));
00116 
00117     _M_results._M_set_matched(0,
00118                               __includes_some(_M_nfa->_M_final_states(), __t));
00119   }
00120 
00121   // Creates the e-closure set for the initial state __i.
00122   inline _StateSet _Grep_matcher::
00123   _M_e_closure(_StateIdT __i)
00124   {
00125     _StateSet __s;
00126     __s.insert(__i);
00127     _StateStack __stack;
00128     __stack.push(__i);
00129     return this->_M_e_closure(__stack, __s);
00130   }
00131 
00132   // Creates the e-closure set for an arbitrary state set __s.
00133   inline _StateSet _Grep_matcher::
00134   _M_e_closure(const _StateSet& __s)
00135   {
00136     _StateStack __stack;
00137     for (_StateSet::const_iterator __i = __s.begin(); __i != __s.end(); ++__i)
00138       __stack.push(*__i);
00139     return this->_M_e_closure(__stack, __s);
00140   }
00141 
00142   inline _StateSet _Grep_matcher::
00143   _M_e_closure(_StateStack& __stack, const _StateSet& __s)
00144   {
00145     _StateSet __e = __s;
00146     while (!__stack.empty())
00147       {
00148     _StateIdT __t = __stack.top(); __stack.pop();
00149     if (__t == _S_invalid_state_id)
00150       continue;
00151     // for each __u with edge from __t to __u labeled e do ...
00152     const _State& __state = _M_nfa->operator[](__t);
00153     switch (__state._M_opcode)
00154       {
00155       case _S_opcode_alternative:
00156         __add_visited_state(__state._M_next, __stack, __e);
00157         __add_visited_state(__state._M_alt, __stack, __e);
00158         break;
00159       case _S_opcode_subexpr_begin:
00160         __add_visited_state(__state._M_next, __stack, __e);
00161         __state._M_tagger(_M_pattern, _M_results);
00162         break;
00163       case _S_opcode_subexpr_end:
00164         __add_visited_state(__state._M_next, __stack, __e);
00165         __state._M_tagger(_M_pattern, _M_results);
00166         _M_results._M_set_matched(__state._M_subexpr, true);
00167         break;
00168       case _S_opcode_accept:
00169         __add_visited_state(__state._M_next, __stack, __e);
00170         break;
00171       default:
00172         break;
00173       }
00174       }
00175     return __e;
00176   }
00177 
00178 } // namespace __regex
00179 
00180 _GLIBCXX_END_NAMESPACE_VERSION
00181 } // namespace