core/matcher/simple_repeat_matcher.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 // simple_repeat_matcher.hpp
0003 //
0004 //  Copyright 2008 Eric Niebler. Distributed under the Boost
0005 //  Software License, Version 1.0. (See accompanying file
0006 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0007
0008 #ifndef BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005
0009 #define BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005
0010
0011 // MS compatible compilers support #pragma once
0012 #if defined(_MSC_VER)
0013 # pragma once
0014 #endif
0015
0016 #include <boost/assert.hpp>
0017 #include <boost/mpl/if.hpp>
0018 #include <boost/mpl/bool.hpp>
0019 #include <boost/next_prior.hpp>
0020 #include <boost/xpressive/detail/detail_fwd.hpp>
0021 #include <boost/xpressive/detail/core/quant_style.hpp>
0022 #include <boost/xpressive/detail/core/state.hpp>
0023 #include <boost/xpressive/detail/static/type_traits.hpp>
0024
0025 namespace boost { namespace xpressive { namespace detail
0026 {
0027
0028     ///////////////////////////////////////////////////////////////////////////////
0029     // simple_repeat_traits
0030     //
0031     struct greedy_slow_tag {};
0032     struct greedy_fast_tag {};
0033     struct non_greedy_tag {};
0034
0035     typedef static_xpression<any_matcher, true_xpression> any_sxpr;
0036     typedef matcher_wrapper<any_matcher> any_dxpr;
0037
0038     template<typename Xpr, typename Greedy, typename Random>
0039     struct simple_repeat_traits
0040     {
0041         typedef typename mpl::if_c<Greedy::value, greedy_slow_tag, non_greedy_tag>::type tag_type;
0042     };
0043
0044     template<>
0045     struct simple_repeat_traits<any_sxpr, mpl::true_, mpl::true_>
0046     {
0047         typedef greedy_fast_tag tag_type;
0048     };
0049
0050     template<>
0051     struct simple_repeat_traits<any_dxpr, mpl::true_, mpl::true_>
0052     {
0053         typedef greedy_fast_tag tag_type;
0054     };
0055
0056     ///////////////////////////////////////////////////////////////////////////////
0057     // simple_repeat_matcher
0058     //
0059     template<typename Xpr, typename Greedy>
0060     struct simple_repeat_matcher
0061       : quant_style_variable_width
0062     {
0063         typedef Xpr xpr_type;
0064         typedef Greedy greedy_type;
0065
0066         Xpr xpr_;
0067         unsigned int min_, max_;
0068         std::size_t width_;
0069         mutable bool leading_;
0070
0071         simple_repeat_matcher(Xpr const &xpr, unsigned int min, unsigned int max, std::size_t width)
0072           : xpr_(xpr)
0073           , min_(min)
0074           , max_(max)
0075           , width_(width)
0076           , leading_(false)
0077         {
0078             // it is the job of the parser to make sure this never happens
0079             BOOST_ASSERT(min <= max);
0080             BOOST_ASSERT(0 != max);
0081             BOOST_ASSERT(0 != width && unknown_width() != width);
0082             BOOST_ASSERT(Xpr::width == unknown_width() || Xpr::width == width);
0083         }
0084
0085         template<typename BidiIter, typename Next>
0086         bool match(match_state<BidiIter> &state, Next const &next) const
0087         {
0088             typedef mpl::bool_<is_random<BidiIter>::value> is_rand;
0089             typedef typename simple_repeat_traits<Xpr, greedy_type, is_rand>::tag_type tag_type;
0090             return this->match_(state, next, tag_type());
0091         }
0092
0093         // greedy, fixed-width quantifier
0094         template<typename BidiIter, typename Next>
0095         bool match_(match_state<BidiIter> &state, Next const &next, greedy_slow_tag) const
0096         {
0097             int const diff = -static_cast<int>(Xpr::width == unknown_width::value ? this->width_ : Xpr::width);
0098             unsigned int matches = 0;
0099             BidiIter const tmp = state.cur_;
0100
0101             // greedily match as much as we can
0102             while(matches < this->max_ && this->xpr_.match(state))
0103             {
0104                 ++matches;
0105             }
0106
0107             // If this repeater is at the front of the pattern, note
0108             // how much of the input we consumed so that a repeated search
0109             // doesn't have to cover the same ground again.
0110             if(this->leading_)
0111             {
0112                 state.next_search_ = (matches && matches < this->max_)
0113                                    ? state.cur_
0114                                    : (tmp == state.end_) ? tmp : boost::next(tmp);
0115             }
0116
0117             if(this->min_ > matches)
0118             {
0119                 state.cur_ = tmp;
0120                 return false;
0121             }
0122
0123             // try matching the rest of the pattern, and back off if necessary
0124             for(; ; --matches, std::advance(state.cur_, diff))
0125             {
0126                 if(next.match(state))
0127                 {
0128                     return true;
0129                 }
0130                 else if(this->min_ == matches)
0131                 {
0132                     state.cur_ = tmp;
0133                     return false;
0134                 }
0135             }
0136         }
0137
0138         // non-greedy fixed-width quantification
0139         template<typename BidiIter, typename Next>
0140         bool match_(match_state<BidiIter> &state, Next const &next, non_greedy_tag) const
0141         {
0142             BOOST_ASSERT(!this->leading_);
0143             BidiIter const tmp = state.cur_;
0144             unsigned int matches = 0;
0145
0146             for(; matches < this->min_; ++matches)
0147             {
0148                 if(!this->xpr_.match(state))
0149                 {
0150                     state.cur_ = tmp;
0151                     return false;
0152                 }
0153             }
0154
0155             do
0156             {
0157                 if(next.match(state))
0158                 {
0159                     return true;
0160                 }
0161             }
0162             while(matches++ < this->max_ && this->xpr_.match(state));
0163
0164             state.cur_ = tmp;
0165             return false;
0166         }
0167
0168         // when greedily matching any character, skip to the end instead of iterating there.
0169         template<typename BidiIter, typename Next>
0170         bool match_(match_state<BidiIter> &state, Next const &next, greedy_fast_tag) const
0171         {
0172             BidiIter const tmp = state.cur_;
0173             std::size_t const diff_to_end = static_cast<std::size_t>(state.end_ - tmp);
0174
0175             // is there enough room?
0176             if(this->min_ > diff_to_end)
0177             {
0178                 if(this->leading_)
0179                 {
0180                     state.next_search_ = (tmp == state.end_) ? tmp : boost::next(tmp);
0181                 }
0182                 return false;
0183             }
0184
0185             BidiIter const min_iter = tmp + this->min_;
0186             state.cur_ += (std::min)((std::size_t)this->max_, diff_to_end);
0187
0188             if(this->leading_)
0189             {
0190                 state.next_search_ = (diff_to_end && diff_to_end < this->max_)
0191                                    ? state.cur_
0192                                    : (tmp == state.end_) ? tmp : boost::next(tmp);
0193             }
0194
0195             for(;; --state.cur_)
0196             {
0197                 if(next.match(state))
0198                 {
0199                     return true;
0200                 }
0201                 else if(min_iter == state.cur_)
0202                 {
0203                     state.cur_ = tmp;
0204                     return false;
0205                 }
0206             }
0207         }
0208
0209         detail::width get_width() const
0210         {
0211             if(this->min_ != this->max_)
0212             {
0213                 return unknown_width::value;
0214             }
0215             return this->min_ * this->width_;
0216         }
0217
0218     private:
0219         simple_repeat_matcher &operator =(simple_repeat_matcher const &);
0220     };
0221
0222     // BUGBUG can all non-greedy quantification be done with the fixed width quantifier?
0223
0224     // BUGBUG matchers are chained together using static_xpression so that matchers to
0225     // the left can invoke matchers to the right. This is so that if the left matcher
0226     // succeeds but the right matcher fails, the left matcher is given the opportunity
0227     // to try something else. This is how backtracking works. However, if the left matcher
0228     // can succeed only one way (as with any_matcher, for example), it does not need
0229     // backtracking. In this case, leaving its stack frame active is a waste of stack
0230     // space. Can something be done?
0231
0232 }}}
0233
0234 #endif