Chris@16
|
1 ///////////////////////////////////////////////////////////////////////////////
|
Chris@16
|
2 // dynamic.hpp
|
Chris@16
|
3 //
|
Chris@16
|
4 // Copyright 2008 Eric Niebler. Distributed under the Boost
|
Chris@16
|
5 // Software License, Version 1.0. (See accompanying file
|
Chris@16
|
6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
|
Chris@16
|
7
|
Chris@16
|
8 #ifndef BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
|
Chris@16
|
9 #define BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
|
Chris@16
|
10
|
Chris@16
|
11 // MS compatible compilers support #pragma once
|
Chris@101
|
12 #if defined(_MSC_VER)
|
Chris@16
|
13 # pragma once
|
Chris@16
|
14 #endif
|
Chris@16
|
15
|
Chris@16
|
16 #include <vector>
|
Chris@16
|
17 #include <utility>
|
Chris@16
|
18 #include <algorithm>
|
Chris@16
|
19 #include <boost/assert.hpp>
|
Chris@16
|
20 #include <boost/mpl/int.hpp>
|
Chris@16
|
21 #include <boost/mpl/assert.hpp>
|
Chris@16
|
22 #include <boost/throw_exception.hpp>
|
Chris@16
|
23 #include <boost/type_traits/is_same.hpp>
|
Chris@16
|
24 #include <boost/xpressive/detail/detail_fwd.hpp>
|
Chris@16
|
25 #include <boost/xpressive/detail/core/quant_style.hpp>
|
Chris@16
|
26 #include <boost/xpressive/detail/dynamic/matchable.hpp>
|
Chris@16
|
27 #include <boost/xpressive/detail/dynamic/sequence.hpp>
|
Chris@16
|
28 #include <boost/xpressive/detail/core/icase.hpp>
|
Chris@16
|
29
|
Chris@16
|
30 namespace boost { namespace xpressive { namespace detail
|
Chris@16
|
31 {
|
Chris@16
|
32
|
Chris@16
|
33 ///////////////////////////////////////////////////////////////////////////////
|
Chris@16
|
34 // invalid_xpression
|
Chris@16
|
35 template<typename BidiIter>
|
Chris@16
|
36 struct invalid_xpression
|
Chris@16
|
37 : matchable_ex<BidiIter>
|
Chris@16
|
38 {
|
Chris@16
|
39 invalid_xpression()
|
Chris@16
|
40 : matchable_ex<BidiIter>()
|
Chris@16
|
41 {
|
Chris@16
|
42 intrusive_ptr_add_ref(this); // keep alive forever
|
Chris@16
|
43 }
|
Chris@16
|
44
|
Chris@16
|
45 bool match(match_state<BidiIter> &) const
|
Chris@16
|
46 {
|
Chris@16
|
47 BOOST_ASSERT(false);
|
Chris@16
|
48 return false;
|
Chris@16
|
49 }
|
Chris@16
|
50 };
|
Chris@16
|
51
|
Chris@16
|
52 ///////////////////////////////////////////////////////////////////////////////
|
Chris@16
|
53 // get_invalid_xpression
|
Chris@16
|
54 template<typename BidiIter>
|
Chris@16
|
55 inline shared_matchable<BidiIter> const &get_invalid_xpression()
|
Chris@16
|
56 {
|
Chris@16
|
57 static invalid_xpression<BidiIter> const invalid_xpr;
|
Chris@16
|
58 static intrusive_ptr<matchable_ex<BidiIter> const> const invalid_ptr(&invalid_xpr);
|
Chris@16
|
59 static shared_matchable<BidiIter> const invalid_matchable(invalid_ptr);
|
Chris@16
|
60 return invalid_matchable;
|
Chris@16
|
61 }
|
Chris@16
|
62
|
Chris@16
|
63 ///////////////////////////////////////////////////////////////////////////////
|
Chris@16
|
64 // dynamic_xpression
|
Chris@16
|
65 template<typename Matcher, typename BidiIter>
|
Chris@16
|
66 struct dynamic_xpression
|
Chris@16
|
67 : Matcher
|
Chris@16
|
68 , matchable_ex<BidiIter>
|
Chris@16
|
69 {
|
Chris@16
|
70 typedef typename iterator_value<BidiIter>::type char_type;
|
Chris@16
|
71
|
Chris@16
|
72 dynamic_xpression(Matcher const &matcher = Matcher())
|
Chris@16
|
73 : Matcher(matcher)
|
Chris@16
|
74 , next_(get_invalid_xpression<BidiIter>())
|
Chris@16
|
75 {
|
Chris@16
|
76 }
|
Chris@16
|
77
|
Chris@16
|
78 virtual bool match(match_state<BidiIter> &state) const
|
Chris@16
|
79 {
|
Chris@16
|
80 return this->Matcher::match(state, *this->next_.matchable());
|
Chris@16
|
81 }
|
Chris@16
|
82
|
Chris@16
|
83 virtual void link(xpression_linker<char_type> &linker) const
|
Chris@16
|
84 {
|
Chris@16
|
85 linker.accept(*static_cast<Matcher const *>(this), this->next_.matchable().get());
|
Chris@16
|
86 this->next_.link(linker);
|
Chris@16
|
87 }
|
Chris@16
|
88
|
Chris@16
|
89 virtual void peek(xpression_peeker<char_type> &peeker) const
|
Chris@16
|
90 {
|
Chris@16
|
91 this->peek_next_(peeker.accept(*static_cast<Matcher const *>(this)), peeker);
|
Chris@16
|
92 }
|
Chris@16
|
93
|
Chris@16
|
94 virtual void repeat(quant_spec const &spec, sequence<BidiIter> &seq) const
|
Chris@16
|
95 {
|
Chris@16
|
96 this->repeat_(spec, seq, quant_type<Matcher>(), is_same<Matcher, mark_begin_matcher>());
|
Chris@16
|
97 }
|
Chris@16
|
98
|
Chris@16
|
99 private:
|
Chris@16
|
100 friend struct sequence<BidiIter>;
|
Chris@16
|
101
|
Chris@16
|
102 void peek_next_(mpl::true_, xpression_peeker<char_type> &peeker) const
|
Chris@16
|
103 {
|
Chris@16
|
104 this->next_.peek(peeker);
|
Chris@16
|
105 }
|
Chris@16
|
106
|
Chris@16
|
107 void peek_next_(mpl::false_, xpression_peeker<char_type> &) const
|
Chris@16
|
108 {
|
Chris@16
|
109 // no-op
|
Chris@16
|
110 }
|
Chris@16
|
111
|
Chris@16
|
112 void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_none>, mpl::false_) const
|
Chris@16
|
113 {
|
Chris@16
|
114 if(quant_none == seq.quant())
|
Chris@16
|
115 {
|
Chris@16
|
116 BOOST_THROW_EXCEPTION(
|
Chris@16
|
117 regex_error(regex_constants::error_badrepeat, "expression cannot be quantified")
|
Chris@16
|
118 );
|
Chris@16
|
119 }
|
Chris@16
|
120 else
|
Chris@16
|
121 {
|
Chris@16
|
122 this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
|
Chris@16
|
123 }
|
Chris@16
|
124 }
|
Chris@16
|
125
|
Chris@16
|
126 void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::false_) const
|
Chris@16
|
127 {
|
Chris@16
|
128 if(this->next_ == get_invalid_xpression<BidiIter>())
|
Chris@16
|
129 {
|
Chris@16
|
130 make_simple_repeat(spec, seq, matcher_wrapper<Matcher>(*this));
|
Chris@16
|
131 }
|
Chris@16
|
132 else
|
Chris@16
|
133 {
|
Chris@16
|
134 this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
|
Chris@16
|
135 }
|
Chris@16
|
136 }
|
Chris@16
|
137
|
Chris@16
|
138 void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_variable_width>, mpl::false_) const
|
Chris@16
|
139 {
|
Chris@16
|
140 if(!is_unknown(seq.width()) && seq.pure())
|
Chris@16
|
141 {
|
Chris@16
|
142 make_simple_repeat(spec, seq);
|
Chris@16
|
143 }
|
Chris@16
|
144 else
|
Chris@16
|
145 {
|
Chris@16
|
146 make_repeat(spec, seq);
|
Chris@16
|
147 }
|
Chris@16
|
148 }
|
Chris@16
|
149
|
Chris@16
|
150 void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::true_) const
|
Chris@16
|
151 {
|
Chris@16
|
152 make_repeat(spec, seq, this->mark_number_);
|
Chris@16
|
153 }
|
Chris@16
|
154
|
Chris@16
|
155 shared_matchable<BidiIter> next_;
|
Chris@16
|
156 };
|
Chris@16
|
157
|
Chris@16
|
158 ///////////////////////////////////////////////////////////////////////////////
|
Chris@16
|
159 // make_dynamic
|
Chris@16
|
160 template<typename BidiIter, typename Matcher>
|
Chris@16
|
161 inline sequence<BidiIter> make_dynamic(Matcher const &matcher)
|
Chris@16
|
162 {
|
Chris@16
|
163 typedef dynamic_xpression<Matcher, BidiIter> xpression_type;
|
Chris@16
|
164 intrusive_ptr<xpression_type> xpr(new xpression_type(matcher));
|
Chris@16
|
165 return sequence<BidiIter>(xpr);
|
Chris@16
|
166 }
|
Chris@16
|
167
|
Chris@16
|
168 ///////////////////////////////////////////////////////////////////////////////
|
Chris@16
|
169 // alternates_vector
|
Chris@16
|
170 template<typename BidiIter>
|
Chris@16
|
171 struct alternates_vector
|
Chris@16
|
172 : std::vector<shared_matchable<BidiIter> >
|
Chris@16
|
173 {
|
Chris@16
|
174 BOOST_STATIC_CONSTANT(std::size_t, width = unknown_width::value);
|
Chris@16
|
175 BOOST_STATIC_CONSTANT(bool, pure = false);
|
Chris@16
|
176 };
|
Chris@16
|
177
|
Chris@16
|
178 ///////////////////////////////////////////////////////////////////////////////
|
Chris@16
|
179 // matcher_wrapper
|
Chris@16
|
180 template<typename Matcher>
|
Chris@16
|
181 struct matcher_wrapper
|
Chris@16
|
182 : Matcher
|
Chris@16
|
183 {
|
Chris@16
|
184 matcher_wrapper(Matcher const &matcher = Matcher())
|
Chris@16
|
185 : Matcher(matcher)
|
Chris@16
|
186 {
|
Chris@16
|
187 }
|
Chris@16
|
188
|
Chris@16
|
189 template<typename BidiIter>
|
Chris@16
|
190 bool match(match_state<BidiIter> &state) const
|
Chris@16
|
191 {
|
Chris@16
|
192 return this->Matcher::match(state, matcher_wrapper<true_matcher>());
|
Chris@16
|
193 }
|
Chris@16
|
194
|
Chris@16
|
195 template<typename Char>
|
Chris@16
|
196 void link(xpression_linker<Char> &linker) const
|
Chris@16
|
197 {
|
Chris@16
|
198 linker.accept(*static_cast<Matcher const *>(this), 0);
|
Chris@16
|
199 }
|
Chris@16
|
200
|
Chris@16
|
201 template<typename Char>
|
Chris@16
|
202 void peek(xpression_peeker<Char> &peeker) const
|
Chris@16
|
203 {
|
Chris@16
|
204 peeker.accept(*static_cast<Matcher const *>(this));
|
Chris@16
|
205 }
|
Chris@16
|
206 };
|
Chris@16
|
207
|
Chris@16
|
208 //////////////////////////////////////////////////////////////////////////
|
Chris@16
|
209 // make_simple_repeat
|
Chris@16
|
210 template<typename BidiIter, typename Xpr>
|
Chris@16
|
211 inline void
|
Chris@16
|
212 make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq, Xpr const &xpr)
|
Chris@16
|
213 {
|
Chris@16
|
214 if(spec.greedy_)
|
Chris@16
|
215 {
|
Chris@16
|
216 simple_repeat_matcher<Xpr, mpl::true_> quant(xpr, spec.min_, spec.max_, seq.width().value());
|
Chris@16
|
217 seq = make_dynamic<BidiIter>(quant);
|
Chris@16
|
218 }
|
Chris@16
|
219 else
|
Chris@16
|
220 {
|
Chris@16
|
221 simple_repeat_matcher<Xpr, mpl::false_> quant(xpr, spec.min_, spec.max_, seq.width().value());
|
Chris@16
|
222 seq = make_dynamic<BidiIter>(quant);
|
Chris@16
|
223 }
|
Chris@16
|
224 }
|
Chris@16
|
225
|
Chris@16
|
226 //////////////////////////////////////////////////////////////////////////
|
Chris@16
|
227 // make_simple_repeat
|
Chris@16
|
228 template<typename BidiIter>
|
Chris@16
|
229 inline void
|
Chris@16
|
230 make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
|
Chris@16
|
231 {
|
Chris@16
|
232 seq += make_dynamic<BidiIter>(true_matcher());
|
Chris@16
|
233 make_simple_repeat(spec, seq, seq.xpr());
|
Chris@16
|
234 }
|
Chris@16
|
235
|
Chris@16
|
236 //////////////////////////////////////////////////////////////////////////
|
Chris@16
|
237 // make_optional
|
Chris@16
|
238 template<typename BidiIter>
|
Chris@16
|
239 inline void
|
Chris@16
|
240 make_optional(quant_spec const &spec, sequence<BidiIter> &seq)
|
Chris@16
|
241 {
|
Chris@16
|
242 typedef shared_matchable<BidiIter> xpr_type;
|
Chris@16
|
243 seq += make_dynamic<BidiIter>(alternate_end_matcher());
|
Chris@16
|
244 if(spec.greedy_)
|
Chris@16
|
245 {
|
Chris@16
|
246 optional_matcher<xpr_type, mpl::true_> opt(seq.xpr());
|
Chris@16
|
247 seq = make_dynamic<BidiIter>(opt);
|
Chris@16
|
248 }
|
Chris@16
|
249 else
|
Chris@16
|
250 {
|
Chris@16
|
251 optional_matcher<xpr_type, mpl::false_> opt(seq.xpr());
|
Chris@16
|
252 seq = make_dynamic<BidiIter>(opt);
|
Chris@16
|
253 }
|
Chris@16
|
254 }
|
Chris@16
|
255
|
Chris@16
|
256 //////////////////////////////////////////////////////////////////////////
|
Chris@16
|
257 // make_optional
|
Chris@16
|
258 template<typename BidiIter>
|
Chris@16
|
259 inline void
|
Chris@16
|
260 make_optional(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
|
Chris@16
|
261 {
|
Chris@16
|
262 typedef shared_matchable<BidiIter> xpr_type;
|
Chris@16
|
263 seq += make_dynamic<BidiIter>(alternate_end_matcher());
|
Chris@16
|
264 if(spec.greedy_)
|
Chris@16
|
265 {
|
Chris@16
|
266 optional_mark_matcher<xpr_type, mpl::true_> opt(seq.xpr(), mark_nbr);
|
Chris@16
|
267 seq = make_dynamic<BidiIter>(opt);
|
Chris@16
|
268 }
|
Chris@16
|
269 else
|
Chris@16
|
270 {
|
Chris@16
|
271 optional_mark_matcher<xpr_type, mpl::false_> opt(seq.xpr(), mark_nbr);
|
Chris@16
|
272 seq = make_dynamic<BidiIter>(opt);
|
Chris@16
|
273 }
|
Chris@16
|
274 }
|
Chris@16
|
275
|
Chris@16
|
276 //////////////////////////////////////////////////////////////////////////
|
Chris@16
|
277 // make_repeat
|
Chris@16
|
278 template<typename BidiIter>
|
Chris@16
|
279 inline void
|
Chris@16
|
280 make_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
|
Chris@16
|
281 {
|
Chris@16
|
282 // only bother creating a repeater if max is greater than one
|
Chris@16
|
283 if(1 < spec.max_)
|
Chris@16
|
284 {
|
Chris@16
|
285 // create a hidden mark so this expression can be quantified
|
Chris@16
|
286 int mark_nbr = -static_cast<int>(++*spec.hidden_mark_count_);
|
Chris@16
|
287 seq = make_dynamic<BidiIter>(mark_begin_matcher(mark_nbr)) + seq
|
Chris@16
|
288 + make_dynamic<BidiIter>(mark_end_matcher(mark_nbr));
|
Chris@16
|
289 make_repeat(spec, seq, mark_nbr);
|
Chris@16
|
290 return;
|
Chris@16
|
291 }
|
Chris@16
|
292
|
Chris@16
|
293 // if min is 0, the repeat must be made optional
|
Chris@16
|
294 if(0 == spec.min_)
|
Chris@16
|
295 {
|
Chris@16
|
296 make_optional(spec, seq);
|
Chris@16
|
297 }
|
Chris@16
|
298 }
|
Chris@16
|
299
|
Chris@16
|
300 //////////////////////////////////////////////////////////////////////////
|
Chris@16
|
301 // make_repeat
|
Chris@16
|
302 template<typename BidiIter>
|
Chris@16
|
303 inline void
|
Chris@16
|
304 make_repeat(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
|
Chris@16
|
305 {
|
Chris@16
|
306 BOOST_ASSERT(spec.max_); // we should never get here if max is 0
|
Chris@16
|
307
|
Chris@16
|
308 // only bother creating a repeater if max is greater than one
|
Chris@16
|
309 if(1 < spec.max_)
|
Chris@16
|
310 {
|
Chris@16
|
311 // TODO: statically bind the repeat matchers to the mark matchers for better perf
|
Chris@16
|
312 unsigned int min = spec.min_ ? spec.min_ : 1U;
|
Chris@16
|
313 repeat_begin_matcher repeat_begin(mark_nbr);
|
Chris@16
|
314 if(spec.greedy_)
|
Chris@16
|
315 {
|
Chris@16
|
316 repeat_end_matcher<mpl::true_> repeat_end(mark_nbr, min, spec.max_);
|
Chris@16
|
317 seq = make_dynamic<BidiIter>(repeat_begin) + seq
|
Chris@16
|
318 + make_dynamic<BidiIter>(repeat_end);
|
Chris@16
|
319 }
|
Chris@16
|
320 else
|
Chris@16
|
321 {
|
Chris@16
|
322 repeat_end_matcher<mpl::false_> repeat_end(mark_nbr, min, spec.max_);
|
Chris@16
|
323 seq = make_dynamic<BidiIter>(repeat_begin) + seq
|
Chris@16
|
324 + make_dynamic<BidiIter>(repeat_end);
|
Chris@16
|
325 }
|
Chris@16
|
326 }
|
Chris@16
|
327
|
Chris@16
|
328 // if min is 0, the repeat must be made optional
|
Chris@16
|
329 if(0 == spec.min_)
|
Chris@16
|
330 {
|
Chris@16
|
331 make_optional(spec, seq, mark_nbr);
|
Chris@16
|
332 }
|
Chris@16
|
333 }
|
Chris@16
|
334
|
Chris@16
|
335 }}} // namespace boost::xpressive::detail
|
Chris@16
|
336
|
Chris@16
|
337 #endif
|