1 /////////////////////////////////////////////////////////////////////////////// 2 // simple_repeat_matcher.hpp 3 // 4 // Copyright 2008 Eric Niebler. Distributed under the Boost 5 // Software License, Version 1.0. (See accompanying file 6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 7 8 #ifndef BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005 9 #define BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005 10 11 // MS compatible compilers support #pragma once 12 #if defined(_MSC_VER) 13 # pragma once 14 #endif 15 16 #include <boost/assert.hpp> 17 #include <boost/mpl/if.hpp> 18 #include <boost/mpl/bool.hpp> 19 #include <boost/next_prior.hpp> 20 #include <boost/xpressive/detail/detail_fwd.hpp> 21 #include <boost/xpressive/detail/core/quant_style.hpp> 22 #include <boost/xpressive/detail/core/state.hpp> 23 #include <boost/xpressive/detail/static/type_traits.hpp> 24 25 namespace boost { namespace xpressive { namespace detail 26 { 27 28 /////////////////////////////////////////////////////////////////////////////// 29 // simple_repeat_traits 30 // 31 struct greedy_slow_tag {}; 32 struct greedy_fast_tag {}; 33 struct non_greedy_tag {}; 34 35 typedef static_xpression<any_matcher, true_xpression> any_sxpr; 36 typedef matcher_wrapper<any_matcher> any_dxpr; 37 38 template<typename Xpr, typename Greedy, typename Random> 39 struct simple_repeat_traits 40 { 41 typedef typename mpl::if_c<Greedy::value, greedy_slow_tag, non_greedy_tag>::type tag_type; 42 }; 43 44 template<> 45 struct simple_repeat_traits<any_sxpr, mpl::true_, mpl::true_> 46 { 47 typedef greedy_fast_tag tag_type; 48 }; 49 50 template<> 51 struct simple_repeat_traits<any_dxpr, mpl::true_, mpl::true_> 52 { 53 typedef greedy_fast_tag tag_type; 54 }; 55 56 /////////////////////////////////////////////////////////////////////////////// 57 // simple_repeat_matcher 58 // 59 template<typename Xpr, typename Greedy> 60 struct simple_repeat_matcher 61 : quant_style_variable_width 62 { 63 typedef Xpr xpr_type; 64 typedef Greedy greedy_type; 65 66 Xpr xpr_; 67 unsigned int min_, max_; 68 std::size_t width_; 69 mutable bool leading_; 70 simple_repeat_matcherboost::xpressive::detail::simple_repeat_matcher71 simple_repeat_matcher(Xpr const &xpr, unsigned int min, unsigned int max, std::size_t width) 72 : xpr_(xpr) 73 , min_(min) 74 , max_(max) 75 , width_(width) 76 , leading_(false) 77 { 78 // it is the job of the parser to make sure this never happens 79 BOOST_ASSERT(min <= max); 80 BOOST_ASSERT(0 != max); 81 BOOST_ASSERT(0 != width && unknown_width() != width); 82 BOOST_ASSERT(Xpr::width == unknown_width() || Xpr::width == width); 83 } 84 85 template<typename BidiIter, typename Next> matchboost::xpressive::detail::simple_repeat_matcher86 bool match(match_state<BidiIter> &state, Next const &next) const 87 { 88 typedef mpl::bool_<is_random<BidiIter>::value> is_rand; 89 typedef typename simple_repeat_traits<Xpr, greedy_type, is_rand>::tag_type tag_type; 90 return this->match_(state, next, tag_type()); 91 } 92 93 // greedy, fixed-width quantifier 94 template<typename BidiIter, typename Next> match_boost::xpressive::detail::simple_repeat_matcher95 bool match_(match_state<BidiIter> &state, Next const &next, greedy_slow_tag) const 96 { 97 int const diff = -static_cast<int>(Xpr::width == unknown_width::value ? this->width_ : Xpr::width); 98 unsigned int matches = 0; 99 BidiIter const tmp = state.cur_; 100 101 // greedily match as much as we can 102 while(matches < this->max_ && this->xpr_.match(state)) 103 { 104 ++matches; 105 } 106 107 // If this repeater is at the front of the pattern, note 108 // how much of the input we consumed so that a repeated search 109 // doesn't have to cover the same ground again. 110 if(this->leading_) 111 { 112 state.next_search_ = (matches && matches < this->max_) 113 ? state.cur_ 114 : (tmp == state.end_) ? tmp : boost::next(tmp); 115 } 116 117 if(this->min_ > matches) 118 { 119 state.cur_ = tmp; 120 return false; 121 } 122 123 // try matching the rest of the pattern, and back off if necessary 124 for(; ; --matches, std::advance(state.cur_, diff)) 125 { 126 if(next.match(state)) 127 { 128 return true; 129 } 130 else if(this->min_ == matches) 131 { 132 state.cur_ = tmp; 133 return false; 134 } 135 } 136 } 137 138 // non-greedy fixed-width quantification 139 template<typename BidiIter, typename Next> match_boost::xpressive::detail::simple_repeat_matcher140 bool match_(match_state<BidiIter> &state, Next const &next, non_greedy_tag) const 141 { 142 BOOST_ASSERT(!this->leading_); 143 BidiIter const tmp = state.cur_; 144 unsigned int matches = 0; 145 146 for(; matches < this->min_; ++matches) 147 { 148 if(!this->xpr_.match(state)) 149 { 150 state.cur_ = tmp; 151 return false; 152 } 153 } 154 155 do 156 { 157 if(next.match(state)) 158 { 159 return true; 160 } 161 } 162 while(matches++ < this->max_ && this->xpr_.match(state)); 163 164 state.cur_ = tmp; 165 return false; 166 } 167 168 // when greedily matching any character, skip to the end instead of iterating there. 169 template<typename BidiIter, typename Next> match_boost::xpressive::detail::simple_repeat_matcher170 bool match_(match_state<BidiIter> &state, Next const &next, greedy_fast_tag) const 171 { 172 BidiIter const tmp = state.cur_; 173 std::size_t const diff_to_end = static_cast<std::size_t>(state.end_ - tmp); 174 175 // is there enough room? 176 if(this->min_ > diff_to_end) 177 { 178 if(this->leading_) 179 { 180 state.next_search_ = (tmp == state.end_) ? tmp : boost::next(tmp); 181 } 182 return false; 183 } 184 185 BidiIter const min_iter = tmp + this->min_; 186 state.cur_ += (std::min)((std::size_t)this->max_, diff_to_end); 187 188 if(this->leading_) 189 { 190 state.next_search_ = (diff_to_end && diff_to_end < this->max_) 191 ? state.cur_ 192 : (tmp == state.end_) ? tmp : boost::next(tmp); 193 } 194 195 for(;; --state.cur_) 196 { 197 if(next.match(state)) 198 { 199 return true; 200 } 201 else if(min_iter == state.cur_) 202 { 203 state.cur_ = tmp; 204 return false; 205 } 206 } 207 } 208 get_widthboost::xpressive::detail::simple_repeat_matcher209 detail::width get_width() const 210 { 211 if(this->min_ != this->max_) 212 { 213 return unknown_width::value; 214 } 215 return this->min_ * this->width_; 216 } 217 218 private: 219 simple_repeat_matcher &operator =(simple_repeat_matcher const &); 220 }; 221 222 // BUGBUG can all non-greedy quantification be done with the fixed width quantifier? 223 224 // BUGBUG matchers are chained together using static_xpression so that matchers to 225 // the left can invoke matchers to the right. This is so that if the left matcher 226 // succeeds but the right matcher fails, the left matcher is given the opportunity 227 // to try something else. This is how backtracking works. However, if the left matcher 228 // can succeed only one way (as with any_matcher, for example), it does not need 229 // backtracking. In this case, leaving its stack frame active is a waste of stack 230 // space. Can something be done? 231 232 }}} 233 234 #endif 235