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