123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234 |
- ///////////////////////////////////////////////////////////////////////////////
- // 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)
- # 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
|