boost/xpressive/detail/core/finder.hpp

   1 /// Contains the definition of the basic_regex\<\> class template and its associated helper functions.
   2 //
   3 //  Copyright 2008 Eric Niebler. Distributed under the Boost
   4 //  Software License, Version 1.0. (See accompanying file
   5 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_XPRESSIVE_DETAIL_CORE_FINDER_HPP_EAN_10_04_2005
   8 #define BOOST_XPRESSIVE_DETAIL_CORE_FINDER_HPP_EAN_10_04_2005
   9
  10 // MS compatible compilers support #pragma once
  11 #if defined(_MSC_VER)
  12 # pragma once
  13 # pragma warning(push)
  14 # pragma warning(disable : 4189) // local variable is initialized but not referenced
  15 #endif
  16
  17 #include <boost/xpressive/detail/detail_fwd.hpp>
  18 #include <boost/xpressive/detail/core/regex_impl.hpp>
  19 #include <boost/xpressive/detail/utility/boyer_moore.hpp>
  20 #include <boost/xpressive/detail/utility/hash_peek_bitset.hpp>
  21
  22 namespace boost { namespace xpressive { namespace detail
  23 {
  24
  25 ///////////////////////////////////////////////////////////////////////////////
  26 // boyer_moore_finder
  27 //
  28 template<typename BidiIter, typename Traits>
  29 struct boyer_moore_finder
  30   : finder<BidiIter>
  31 {
  32     typedef typename iterator_value<BidiIter>::type char_type;
  33
  34     boyer_moore_finder(char_type const *begin, char_type const *end, Traits const &tr, bool icase)
  35       : bm_(begin, end, tr, icase)
  36     {
  37     }
  38
  39     bool ok_for_partial_matches() const
  40     {
  41         return false;
  42     }
  43
  44     bool operator ()(match_state<BidiIter> &state) const
  45     {
  46         Traits const &tr = traits_cast<Traits>(state);
  47         state.cur_ = this->bm_.find(state.cur_, state.end_, tr);
  48         return state.cur_ != state.end_;
  49     }
  50
  51 private:
  52     boyer_moore_finder(boyer_moore_finder const &);
  53     boyer_moore_finder &operator =(boyer_moore_finder const &);
  54
  55     boyer_moore<BidiIter, Traits> bm_;
  56 };
  57
  58 ///////////////////////////////////////////////////////////////////////////////
  59 // hash_peek_finder
  60 //
  61 template<typename BidiIter, typename Traits>
  62 struct hash_peek_finder
  63   : finder<BidiIter>
  64 {
  65     typedef typename iterator_value<BidiIter>::type char_type;
  66
  67     hash_peek_finder(hash_peek_bitset<char_type> const &bset)
  68       : bset_(bset)
  69     {
  70     }
  71
  72     bool operator ()(match_state<BidiIter> &state) const
  73     {
  74         Traits const &tr = traits_cast<Traits>(state);
  75         state.cur_ = (this->bset_.icase()
  76             ? this->find_(state.cur_, state.end_, tr, mpl::true_())
  77             : this->find_(state.cur_, state.end_, tr, mpl::false_()));
  78         return state.cur_ != state.end_;
  79     }
  80
  81 private:
  82     hash_peek_finder(hash_peek_finder const &);
  83     hash_peek_finder &operator =(hash_peek_finder const &);
  84
  85     template<typename ICase>
  86     BidiIter find_(BidiIter begin, BidiIter end, Traits const &tr, ICase) const
  87     {
  88         for(; begin != end && !this->bset_.test(*begin, tr, ICase()); ++begin)
  89             ;
  90         return begin;
  91     }
  92
  93     hash_peek_bitset<char_type> bset_;
  94 };
  95
  96 ///////////////////////////////////////////////////////////////////////////////
  97 // line_start_finder
  98 //
  99 template<typename BidiIter, typename Traits, std::size_t Size = sizeof(typename iterator_value<BidiIter>::type)>
 100 struct line_start_finder
 101   : finder<BidiIter>
 102 {
 103     typedef typename iterator_value<BidiIter>::type char_type;
 104     typedef typename iterator_difference<BidiIter>::type diff_type;
 105     typedef typename Traits::char_class_type char_class_type;
 106
 107     line_start_finder(Traits const &tr)
 108       : newline_(lookup_classname(tr, "newline"))
 109     {
 110     }
 111
 112     bool operator ()(match_state<BidiIter> &state) const
 113     {
 114         if(state.bos() && state.flags_.match_bol_)
 115         {
 116             return true;
 117         }
 118
 119         Traits const &tr = traits_cast<Traits>(state);
 120         BidiIter cur = state.cur_;
 121         BidiIter const end = state.end_;
 122         std::advance(cur, static_cast<diff_type>(-!state.bos()));
 123
 124         for(; cur != end; ++cur)
 125         {
 126             if(tr.isctype(*cur, this->newline_))
 127             {
 128                 state.cur_ = ++cur;
 129                 return true;
 130             }
 131         }
 132
 133         return false;
 134     }
 135
 136 private:
 137     line_start_finder(line_start_finder const &);
 138     line_start_finder &operator =(line_start_finder const &);
 139
 140     char_class_type newline_;
 141 };
 142
 143 ///////////////////////////////////////////////////////////////////////////////
 144 // line_start_finder
 145 //
 146 template<typename BidiIter, typename Traits>
 147 struct line_start_finder<BidiIter, Traits, 1u>
 148   : finder<BidiIter>
 149 {
 150     typedef typename iterator_value<BidiIter>::type char_type;
 151     typedef typename iterator_difference<BidiIter>::type diff_type;
 152     typedef typename Traits::char_class_type char_class_type;
 153
 154     line_start_finder(Traits const &tr)
 155     {
 156         char_class_type newline = lookup_classname(tr, "newline");
 157         for(int j = 0; j < 256; ++j)
 158         {
 159             this->bits_[j] = tr.isctype(static_cast<char_type>(static_cast<unsigned char>(j)), newline);
 160         }
 161     }
 162
 163     bool operator ()(match_state<BidiIter> &state) const
 164     {
 165         if(state.bos() && state.flags_.match_bol_)
 166         {
 167             return true;
 168         }
 169
 170         BidiIter cur = state.cur_;
 171         BidiIter const end = state.end_;
 172         std::advance(cur, static_cast<diff_type>(-!state.bos()));
 173
 174         for(; cur != end; ++cur)
 175         {
 176             if(this->bits_[static_cast<unsigned char>(*cur)])
 177             {
 178                 state.cur_ = ++cur;
 179                 return true;
 180             }
 181         }
 182
 183         return false;
 184     }
 185
 186 private:
 187     line_start_finder(line_start_finder const &);
 188     line_start_finder &operator =(line_start_finder const &);
 189
 190     bool bits_[256];
 191 };
 192
 193 ///////////////////////////////////////////////////////////////////////////////
 194 // leading_simple_repeat_finder
 195 //
 196 template<typename BidiIter>
 197 struct leading_simple_repeat_finder
 198   : finder<BidiIter>
 199 {
 200     leading_simple_repeat_finder()
 201       : finder<BidiIter>()
 202     {}
 203
 204     bool operator ()(match_state<BidiIter> &state) const
 205     {
 206         state.cur_ = state.next_search_;
 207         return true;
 208     }
 209
 210 private:
 211     leading_simple_repeat_finder(leading_simple_repeat_finder const &);
 212     leading_simple_repeat_finder &operator =(leading_simple_repeat_finder const &);
 213 };
 214
 215 }}}
 216
 217 #if defined(_MSC_VER)
 218 # pragma warning(pop)
 219 #endif
 220
 221 #endif