detail/core/finder.hpp

0001 /// Contains the definition of the basic_regex\<\> class template and its associated helper functions.
0002 //
0003 //  Copyright 2008 Eric Niebler. Distributed under the Boost
0004 //  Software License, Version 1.0. (See accompanying file
0005 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_XPRESSIVE_DETAIL_CORE_FINDER_HPP_EAN_10_04_2005
0008 #define BOOST_XPRESSIVE_DETAIL_CORE_FINDER_HPP_EAN_10_04_2005
0009
0010 // MS compatible compilers support #pragma once
0011 #if defined(_MSC_VER)
0012 # pragma once
0013 # pragma warning(push)
0014 # pragma warning(disable : 4189) // local variable is initialized but not referenced
0015 #endif
0016
0017 #include <boost/xpressive/detail/detail_fwd.hpp>
0018 #include <boost/xpressive/detail/core/regex_impl.hpp>
0019 #include <boost/xpressive/detail/utility/boyer_moore.hpp>
0020 #include <boost/xpressive/detail/utility/hash_peek_bitset.hpp>
0021
0022 namespace boost { namespace xpressive { namespace detail
0023 {
0024
0025 ///////////////////////////////////////////////////////////////////////////////
0026 // boyer_moore_finder
0027 //
0028 template<typename BidiIter, typename Traits>
0029 struct boyer_moore_finder
0030   : finder<BidiIter>
0031 {
0032     typedef typename iterator_value<BidiIter>::type char_type;
0033
0034     boyer_moore_finder(char_type const *begin, char_type const *end, Traits const &tr, bool icase)
0035       : bm_(begin, end, tr, icase)
0036     {
0037     }
0038
0039     bool ok_for_partial_matches() const
0040     {
0041         return false;
0042     }
0043
0044     bool operator ()(match_state<BidiIter> &state) const
0045     {
0046         Traits const &tr = traits_cast<Traits>(state);
0047         state.cur_ = this->bm_.find(state.cur_, state.end_, tr);
0048         return state.cur_ != state.end_;
0049     }
0050
0051 private:
0052     boyer_moore_finder(boyer_moore_finder const &);
0053     boyer_moore_finder &operator =(boyer_moore_finder const &);
0054
0055     boyer_moore<BidiIter, Traits> bm_;
0056 };
0057
0058 ///////////////////////////////////////////////////////////////////////////////
0059 // hash_peek_finder
0060 //
0061 template<typename BidiIter, typename Traits>
0062 struct hash_peek_finder
0063   : finder<BidiIter>
0064 {
0065     typedef typename iterator_value<BidiIter>::type char_type;
0066
0067     hash_peek_finder(hash_peek_bitset<char_type> const &bset)
0068       : bset_(bset)
0069     {
0070     }
0071
0072     bool operator ()(match_state<BidiIter> &state) const
0073     {
0074         Traits const &tr = traits_cast<Traits>(state);
0075         state.cur_ = (this->bset_.icase()
0076             ? this->find_(state.cur_, state.end_, tr, mpl::true_())
0077             : this->find_(state.cur_, state.end_, tr, mpl::false_()));
0078         return state.cur_ != state.end_;
0079     }
0080
0081 private:
0082     hash_peek_finder(hash_peek_finder const &);
0083     hash_peek_finder &operator =(hash_peek_finder const &);
0084
0085     template<typename ICase>
0086     BidiIter find_(BidiIter begin, BidiIter end, Traits const &tr, ICase) const
0087     {
0088         for(; begin != end && !this->bset_.test(*begin, tr, ICase()); ++begin)
0089             ;
0090         return begin;
0091     }
0092
0093     hash_peek_bitset<char_type> bset_;
0094 };
0095
0096 ///////////////////////////////////////////////////////////////////////////////
0097 // line_start_finder
0098 //
0099 template<typename BidiIter, typename Traits, std::size_t Size = sizeof(typename iterator_value<BidiIter>::type)>
0100 struct line_start_finder
0101   : finder<BidiIter>
0102 {
0103     typedef typename iterator_value<BidiIter>::type char_type;
0104     typedef typename iterator_difference<BidiIter>::type diff_type;
0105     typedef typename Traits::char_class_type char_class_type;
0106
0107     line_start_finder(Traits const &tr)
0108       : newline_(lookup_classname(tr, "newline"))
0109     {
0110     }
0111
0112     bool operator ()(match_state<BidiIter> &state) const
0113     {
0114         if(state.bos() && state.flags_.match_bol_)
0115         {
0116             return true;
0117         }
0118
0119         Traits const &tr = traits_cast<Traits>(state);
0120         BidiIter cur = state.cur_;
0121         BidiIter const end = state.end_;
0122         std::advance(cur, static_cast<diff_type>(-!state.bos()));
0123
0124         for(; cur != end; ++cur)
0125         {
0126             if(tr.isctype(*cur, this->newline_))
0127             {
0128                 state.cur_ = ++cur;
0129                 return true;
0130             }
0131         }
0132
0133         return false;
0134     }
0135
0136 private:
0137     line_start_finder(line_start_finder const &);
0138     line_start_finder &operator =(line_start_finder const &);
0139
0140     char_class_type newline_;
0141 };
0142
0143 ///////////////////////////////////////////////////////////////////////////////
0144 // line_start_finder
0145 //
0146 template<typename BidiIter, typename Traits>
0147 struct line_start_finder<BidiIter, Traits, 1u>
0148   : finder<BidiIter>
0149 {
0150     typedef typename iterator_value<BidiIter>::type char_type;
0151     typedef typename iterator_difference<BidiIter>::type diff_type;
0152     typedef typename Traits::char_class_type char_class_type;
0153
0154     line_start_finder(Traits const &tr)
0155     {
0156         char_class_type newline = lookup_classname(tr, "newline");
0157         for(int j = 0; j < 256; ++j)
0158         {
0159             this->bits_[j] = tr.isctype(static_cast<char_type>(static_cast<unsigned char>(j)), newline);
0160         }
0161     }
0162
0163     bool operator ()(match_state<BidiIter> &state) const
0164     {
0165         if(state.bos() && state.flags_.match_bol_)
0166         {
0167             return true;
0168         }
0169
0170         BidiIter cur = state.cur_;
0171         BidiIter const end = state.end_;
0172         std::advance(cur, static_cast<diff_type>(-!state.bos()));
0173
0174         for(; cur != end; ++cur)
0175         {
0176             if(this->bits_[static_cast<unsigned char>(*cur)])
0177             {
0178                 state.cur_ = ++cur;
0179                 return true;
0180             }
0181         }
0182
0183         return false;
0184     }
0185
0186 private:
0187     line_start_finder(line_start_finder const &);
0188     line_start_finder &operator =(line_start_finder const &);
0189
0190     bool bits_[256];
0191 };
0192
0193 ///////////////////////////////////////////////////////////////////////////////
0194 // leading_simple_repeat_finder
0195 //
0196 template<typename BidiIter>
0197 struct leading_simple_repeat_finder
0198   : finder<BidiIter>
0199 {
0200     leading_simple_repeat_finder()
0201       : finder<BidiIter>()
0202     {}
0203
0204     bool operator ()(match_state<BidiIter> &state) const
0205     {
0206         state.cur_ = state.next_search_;
0207         return true;
0208     }
0209
0210 private:
0211     leading_simple_repeat_finder(leading_simple_repeat_finder const &);
0212     leading_simple_repeat_finder &operator =(leading_simple_repeat_finder const &);
0213 };
0214
0215 }}}
0216
0217 #if defined(_MSC_VER)
0218 # pragma warning(pop)
0219 #endif
0220
0221 #endif