| /////////////////////////////////////////////////////////////////////////////// |
| // simple_repeat_matcher.hpp |
| // |
| // Copyright 2008 Eric Niebler. Distributed under the Boost |
| // Software License, Version 1.0. (See accompanying file |
| // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| |
| #ifndef BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005 |
| #define BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005 |
| |
| // MS compatible compilers support #pragma once |
| #if defined(_MSC_VER) && (_MSC_VER >= 1020) |
| # pragma once |
| #endif |
| |
| #include <boost/assert.hpp> |
| #include <boost/mpl/if.hpp> |
| #include <boost/mpl/bool.hpp> |
| #include <boost/next_prior.hpp> |
| #include <boost/xpressive/detail/detail_fwd.hpp> |
| #include <boost/xpressive/detail/core/quant_style.hpp> |
| #include <boost/xpressive/detail/core/state.hpp> |
| #include <boost/xpressive/detail/static/type_traits.hpp> |
| |
| namespace boost { namespace xpressive { namespace detail |
| { |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // simple_repeat_traits |
| // |
| struct greedy_slow_tag {}; |
| struct greedy_fast_tag {}; |
| struct non_greedy_tag {}; |
| |
| typedef static_xpression<any_matcher, true_xpression> any_sxpr; |
| typedef matcher_wrapper<any_matcher> any_dxpr; |
| |
| template<typename Xpr, typename Greedy, typename Random> |
| struct simple_repeat_traits |
| { |
| typedef typename mpl::if_c<Greedy::value, greedy_slow_tag, non_greedy_tag>::type tag_type; |
| }; |
| |
| template<> |
| struct simple_repeat_traits<any_sxpr, mpl::true_, mpl::true_> |
| { |
| typedef greedy_fast_tag tag_type; |
| }; |
| |
| template<> |
| struct simple_repeat_traits<any_dxpr, mpl::true_, mpl::true_> |
| { |
| typedef greedy_fast_tag tag_type; |
| }; |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // simple_repeat_matcher |
| // |
| template<typename Xpr, typename Greedy> |
| struct simple_repeat_matcher |
| : quant_style_variable_width |
| { |
| typedef Xpr xpr_type; |
| typedef Greedy greedy_type; |
| |
| Xpr xpr_; |
| unsigned int min_, max_; |
| std::size_t width_; |
| mutable bool leading_; |
| |
| simple_repeat_matcher(Xpr const &xpr, unsigned int min, unsigned int max, std::size_t width) |
| : xpr_(xpr) |
| , min_(min) |
| , max_(max) |
| , width_(width) |
| , leading_(false) |
| { |
| // it is the job of the parser to make sure this never happens |
| BOOST_ASSERT(min <= max); |
| BOOST_ASSERT(0 != max); |
| BOOST_ASSERT(0 != width && unknown_width() != width); |
| BOOST_ASSERT(Xpr::width == unknown_width() || Xpr::width == width); |
| } |
| |
| template<typename BidiIter, typename Next> |
| bool match(match_state<BidiIter> &state, Next const &next) const |
| { |
| typedef mpl::bool_<is_random<BidiIter>::value> is_rand; |
| typedef typename simple_repeat_traits<Xpr, greedy_type, is_rand>::tag_type tag_type; |
| return this->match_(state, next, tag_type()); |
| } |
| |
| // greedy, fixed-width quantifier |
| template<typename BidiIter, typename Next> |
| bool match_(match_state<BidiIter> &state, Next const &next, greedy_slow_tag) const |
| { |
| int const diff = -static_cast<int>(Xpr::width == unknown_width::value ? this->width_ : Xpr::width); |
| unsigned int matches = 0; |
| BidiIter const tmp = state.cur_; |
| |
| // greedily match as much as we can |
| while(matches < this->max_ && this->xpr_.match(state)) |
| { |
| ++matches; |
| } |
| |
| // If this repeater is at the front of the pattern, note |
| // how much of the input we consumed so that a repeated search |
| // doesn't have to cover the same ground again. |
| if(this->leading_) |
| { |
| state.next_search_ = (matches && matches < this->max_) |
| ? state.cur_ |
| : (tmp == state.end_) ? tmp : boost::next(tmp); |
| } |
| |
| if(this->min_ > matches) |
| { |
| state.cur_ = tmp; |
| return false; |
| } |
| |
| // try matching the rest of the pattern, and back off if necessary |
| for(; ; --matches, std::advance(state.cur_, diff)) |
| { |
| if(next.match(state)) |
| { |
| return true; |
| } |
| else if(this->min_ == matches) |
| { |
| state.cur_ = tmp; |
| return false; |
| } |
| } |
| } |
| |
| // non-greedy fixed-width quantification |
| template<typename BidiIter, typename Next> |
| bool match_(match_state<BidiIter> &state, Next const &next, non_greedy_tag) const |
| { |
| BOOST_ASSERT(!this->leading_); |
| BidiIter const tmp = state.cur_; |
| unsigned int matches = 0; |
| |
| for(; matches < this->min_; ++matches) |
| { |
| if(!this->xpr_.match(state)) |
| { |
| state.cur_ = tmp; |
| return false; |
| } |
| } |
| |
| do |
| { |
| if(next.match(state)) |
| { |
| return true; |
| } |
| } |
| while(matches++ < this->max_ && this->xpr_.match(state)); |
| |
| state.cur_ = tmp; |
| return false; |
| } |
| |
| // when greedily matching any character, skip to the end instead of iterating there. |
| template<typename BidiIter, typename Next> |
| bool match_(match_state<BidiIter> &state, Next const &next, greedy_fast_tag) const |
| { |
| BidiIter const tmp = state.cur_; |
| std::size_t const diff_to_end = static_cast<std::size_t>(state.end_ - tmp); |
| |
| // is there enough room? |
| if(this->min_ > diff_to_end) |
| { |
| if(this->leading_) |
| { |
| state.next_search_ = (tmp == state.end_) ? tmp : boost::next(tmp); |
| } |
| return false; |
| } |
| |
| BidiIter const min_iter = tmp + this->min_; |
| state.cur_ += (std::min)((std::size_t)this->max_, diff_to_end); |
| |
| if(this->leading_) |
| { |
| state.next_search_ = (diff_to_end && diff_to_end < this->max_) |
| ? state.cur_ |
| : (tmp == state.end_) ? tmp : boost::next(tmp); |
| } |
| |
| for(;; --state.cur_) |
| { |
| if(next.match(state)) |
| { |
| return true; |
| } |
| else if(min_iter == state.cur_) |
| { |
| state.cur_ = tmp; |
| return false; |
| } |
| } |
| } |
| |
| detail::width get_width() const |
| { |
| if(this->min_ != this->max_) |
| { |
| return unknown_width::value; |
| } |
| return this->min_ * this->width_; |
| } |
| |
| private: |
| simple_repeat_matcher &operator =(simple_repeat_matcher const &); |
| }; |
| |
| // BUGBUG can all non-greedy quantification be done with the fixed width quantifier? |
| |
| // BUGBUG matchers are chained together using static_xpression so that matchers to |
| // the left can invoke matchers to the right. This is so that if the left matcher |
| // succeeds but the right matcher fails, the left matcher is given the opportunity |
| // to try something else. This is how backtracking works. However, if the left matcher |
| // can succeed only one way (as with any_matcher, for example), it does not need |
| // backtracking. In this case, leaving its stack frame active is a waste of stack |
| // space. Can something be done? |
| |
| }}} |
| |
| #endif |