]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |