ceph/src/boost/libs/xpressive/include/boost/xpressive/detail/core/matcher/simple_repeat_matcher.hpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // simple_repeat_matcher.hpp
   3 //
   4 //  Copyright 2008 Eric Niebler. Distributed under the Boost
   5 //  Software License, Version 1.0. (See accompanying file
   6 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   7
   8 #ifndef BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005
   9 #define BOOST_XPRESSIVE_DETAIL_CORE_MATCHER_SIMPLE_REPEAT_MATCHER_HPP_EAN_10_04_2005
  10
  11 // MS compatible compilers support #pragma once
  12 #if defined(_MSC_VER)
  13 # pragma once
  14 #endif
  15
  16 #include <boost/assert.hpp>
  17 #include <boost/mpl/if.hpp>
  18 #include <boost/mpl/bool.hpp>
  19 #include <boost/next_prior.hpp>
  20 #include <boost/xpressive/detail/detail_fwd.hpp>
  21 #include <boost/xpressive/detail/core/quant_style.hpp>
  22 #include <boost/xpressive/detail/core/state.hpp>
  23 #include <boost/xpressive/detail/static/type_traits.hpp>
  24
  25 namespace boost { namespace xpressive { namespace detail
  26 {
  27
  28     ///////////////////////////////////////////////////////////////////////////////
  29     // simple_repeat_traits
  30     //
  31     struct greedy_slow_tag {};
  32     struct greedy_fast_tag {};
  33     struct non_greedy_tag {};
  34
  35     typedef static_xpression<any_matcher, true_xpression> any_sxpr;
  36     typedef matcher_wrapper<any_matcher> any_dxpr;
  37
  38     template<typename Xpr, typename Greedy, typename Random>
  39     struct simple_repeat_traits
  40     {
  41         typedef typename mpl::if_c<Greedy::value, greedy_slow_tag, non_greedy_tag>::type tag_type;
  42     };
  43
  44     template<>
  45     struct simple_repeat_traits<any_sxpr, mpl::true_, mpl::true_>
  46     {
  47         typedef greedy_fast_tag tag_type;
  48     };
  49
  50     template<>
  51     struct simple_repeat_traits<any_dxpr, mpl::true_, mpl::true_>
  52     {
  53         typedef greedy_fast_tag tag_type;
  54     };
  55
  56     ///////////////////////////////////////////////////////////////////////////////
  57     // simple_repeat_matcher
  58     //
  59     template<typename Xpr, typename Greedy>
  60     struct simple_repeat_matcher
  61       : quant_style_variable_width
  62     {
  63         typedef Xpr xpr_type;
  64         typedef Greedy greedy_type;
  65
  66         Xpr xpr_;
  67         unsigned int min_, max_;
  68         std::size_t width_;
  69         mutable bool leading_;
  70
  71         simple_repeat_matcher(Xpr const &xpr, unsigned int min, unsigned int max, std::size_t width)
  72           : xpr_(xpr)
  73           , min_(min)
  74           , max_(max)
  75           , width_(width)
  76           , leading_(false)
  77         {
  78             // it is the job of the parser to make sure this never happens
  79             BOOST_ASSERT(min <= max);
  80             BOOST_ASSERT(0 != max);
  81             BOOST_ASSERT(0 != width && unknown_width() != width);
  82             BOOST_ASSERT(Xpr::width == unknown_width() || Xpr::width == width);
  83         }
  84
  85         template<typename BidiIter, typename Next>
  86         bool match(match_state<BidiIter> &state, Next const &next) const
  87         {
  88             typedef mpl::bool_<is_random<BidiIter>::value> is_rand;
  89             typedef typename simple_repeat_traits<Xpr, greedy_type, is_rand>::tag_type tag_type;
  90             return this->match_(state, next, tag_type());
  91         }
  92
  93         // greedy, fixed-width quantifier
  94         template<typename BidiIter, typename Next>
  95         bool match_(match_state<BidiIter> &state, Next const &next, greedy_slow_tag) const
  96         {
  97             int const diff = -static_cast<int>(Xpr::width == unknown_width::value ? this->width_ : Xpr::width);
  98             unsigned int matches = 0;
  99             BidiIter const tmp = state.cur_;
 100
 101             // greedily match as much as we can
 102             while(matches < this->max_ && this->xpr_.match(state))
 103             {
 104                 ++matches;
 105             }
 106
 107             // If this repeater is at the front of the pattern, note
 108             // how much of the input we consumed so that a repeated search
 109             // doesn't have to cover the same ground again.
 110             if(this->leading_)
 111             {
 112                 state.next_search_ = (matches && matches < this->max_)
 113                                    ? state.cur_
 114                                    : (tmp == state.end_) ? tmp : boost::next(tmp);
 115             }
 116
 117             if(this->min_ > matches)
 118             {
 119                 state.cur_ = tmp;
 120                 return false;
 121             }
 122
 123             // try matching the rest of the pattern, and back off if necessary
 124             for(; ; --matches, std::advance(state.cur_, diff))
 125             {
 126                 if(next.match(state))
 127                 {
 128                     return true;
 129                 }
 130                 else if(this->min_ == matches)
 131                 {
 132                     state.cur_ = tmp;
 133                     return false;
 134                 }
 135             }
 136         }
 137
 138         // non-greedy fixed-width quantification
 139         template<typename BidiIter, typename Next>
 140         bool match_(match_state<BidiIter> &state, Next const &next, non_greedy_tag) const
 141         {
 142             BOOST_ASSERT(!this->leading_);
 143             BidiIter const tmp = state.cur_;
 144             unsigned int matches = 0;
 145
 146             for(; matches < this->min_; ++matches)
 147             {
 148                 if(!this->xpr_.match(state))
 149                 {
 150                     state.cur_ = tmp;
 151                     return false;
 152                 }
 153             }
 154
 155             do
 156             {
 157                 if(next.match(state))
 158                 {
 159                     return true;
 160                 }
 161             }
 162             while(matches++ < this->max_ && this->xpr_.match(state));
 163
 164             state.cur_ = tmp;
 165             return false;
 166         }
 167
 168         // when greedily matching any character, skip to the end instead of iterating there.
 169         template<typename BidiIter, typename Next>
 170         bool match_(match_state<BidiIter> &state, Next const &next, greedy_fast_tag) const
 171         {
 172             BidiIter const tmp = state.cur_;
 173             std::size_t const diff_to_end = static_cast<std::size_t>(state.end_ - tmp);
 174
 175             // is there enough room?
 176             if(this->min_ > diff_to_end)
 177             {
 178                 if(this->leading_)
 179                 {
 180                     state.next_search_ = (tmp == state.end_) ? tmp : boost::next(tmp);
 181                 }
 182                 return false;
 183             }
 184
 185             BidiIter const min_iter = tmp + this->min_;
 186             state.cur_ += (std::min)((std::size_t)this->max_, diff_to_end);
 187
 188             if(this->leading_)
 189             {
 190                 state.next_search_ = (diff_to_end && diff_to_end < this->max_)
 191                                    ? state.cur_
 192                                    : (tmp == state.end_) ? tmp : boost::next(tmp);
 193             }
 194
 195             for(;; --state.cur_)
 196             {
 197                 if(next.match(state))
 198                 {
 199                     return true;
 200                 }
 201                 else if(min_iter == state.cur_)
 202                 {
 203                     state.cur_ = tmp;
 204                     return false;
 205                 }
 206             }
 207         }
 208
 209         detail::width get_width() const
 210         {
 211             if(this->min_ != this->max_)
 212             {
 213                 return unknown_width::value;
 214             }
 215             return this->min_ * this->width_;
 216         }
 217
 218     private:
 219         simple_repeat_matcher &operator =(simple_repeat_matcher const &);
 220     };
 221
 222     // BUGBUG can all non-greedy quantification be done with the fixed width quantifier?
 223
 224     // BUGBUG matchers are chained together using static_xpression so that matchers to
 225     // the left can invoke matchers to the right. This is so that if the left matcher
 226     // succeeds but the right matcher fails, the left matcher is given the opportunity
 227     // to try something else. This is how backtracking works. However, if the left matcher
 228     // can succeed only one way (as with any_matcher, for example), it does not need
 229     // backtracking. In this case, leaving its stack frame active is a waste of stack
 230     // space. Can something be done?
 231
 232 }}}
 233
 234 #endif