boost/xpressive/detail/core/matcher/simple_repeat_matcher.hpp
/////////////////////////////////////////////////////////////////////////////// // 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