/////////////////////////////////////////////////////////////////////////////// | |
// 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 |