1 | /* |
---|
2 | * |
---|
3 | * Copyright (c) 2002 |
---|
4 | * John Maddock |
---|
5 | * |
---|
6 | * Use, modification and distribution are subject to the |
---|
7 | * Boost Software License, Version 1.0. (See accompanying file |
---|
8 | * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
---|
9 | * |
---|
10 | */ |
---|
11 | |
---|
12 | /* |
---|
13 | * LOCATION: see http://www.boost.org for most recent version. |
---|
14 | * FILE perl_matcher_common.cpp |
---|
15 | * VERSION see <boost/version.hpp> |
---|
16 | * DESCRIPTION: Definitions of perl_matcher member functions that are |
---|
17 | * specific to the recursive implementation. |
---|
18 | */ |
---|
19 | |
---|
20 | #ifndef BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP |
---|
21 | #define BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP |
---|
22 | |
---|
23 | #ifdef BOOST_HAS_ABI_HEADERS |
---|
24 | # include BOOST_ABI_PREFIX |
---|
25 | #endif |
---|
26 | |
---|
27 | namespace boost{ |
---|
28 | namespace re_detail{ |
---|
29 | |
---|
30 | template <class BidiIterator> |
---|
31 | class backup_subex |
---|
32 | { |
---|
33 | int index; |
---|
34 | sub_match<BidiIterator> sub; |
---|
35 | public: |
---|
36 | template <class A> |
---|
37 | backup_subex(const match_results<BidiIterator, A>& w, int i) |
---|
38 | : index(i), sub(w[i], false) {} |
---|
39 | template <class A> |
---|
40 | void restore(match_results<BidiIterator, A>& w) |
---|
41 | { |
---|
42 | w.set_first(sub.first, index); |
---|
43 | w.set_second(sub.second, index, sub.matched); |
---|
44 | } |
---|
45 | const sub_match<BidiIterator>& get() { return sub; } |
---|
46 | }; |
---|
47 | |
---|
48 | template <class BidiIterator, class Allocator, class traits> |
---|
49 | bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states() |
---|
50 | { |
---|
51 | static matcher_proc_type const s_match_vtable[29] = |
---|
52 | { |
---|
53 | (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark), |
---|
54 | &perl_matcher<BidiIterator, Allocator, traits>::match_endmark, |
---|
55 | &perl_matcher<BidiIterator, Allocator, traits>::match_literal, |
---|
56 | &perl_matcher<BidiIterator, Allocator, traits>::match_start_line, |
---|
57 | &perl_matcher<BidiIterator, Allocator, traits>::match_end_line, |
---|
58 | &perl_matcher<BidiIterator, Allocator, traits>::match_wild, |
---|
59 | &perl_matcher<BidiIterator, Allocator, traits>::match_match, |
---|
60 | &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary, |
---|
61 | &perl_matcher<BidiIterator, Allocator, traits>::match_within_word, |
---|
62 | &perl_matcher<BidiIterator, Allocator, traits>::match_word_start, |
---|
63 | &perl_matcher<BidiIterator, Allocator, traits>::match_word_end, |
---|
64 | &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start, |
---|
65 | &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end, |
---|
66 | &perl_matcher<BidiIterator, Allocator, traits>::match_backref, |
---|
67 | &perl_matcher<BidiIterator, Allocator, traits>::match_long_set, |
---|
68 | &perl_matcher<BidiIterator, Allocator, traits>::match_set, |
---|
69 | &perl_matcher<BidiIterator, Allocator, traits>::match_jump, |
---|
70 | &perl_matcher<BidiIterator, Allocator, traits>::match_alt, |
---|
71 | &perl_matcher<BidiIterator, Allocator, traits>::match_rep, |
---|
72 | &perl_matcher<BidiIterator, Allocator, traits>::match_combining, |
---|
73 | &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end, |
---|
74 | &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue, |
---|
75 | (::boost::is_random_access_iterator<BidiIterator>::value ? &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast : &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow), |
---|
76 | &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat, |
---|
77 | &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat, |
---|
78 | &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat, |
---|
79 | &perl_matcher<BidiIterator, Allocator, traits>::match_backstep, |
---|
80 | &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref, |
---|
81 | &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case, |
---|
82 | }; |
---|
83 | |
---|
84 | if(state_count > max_state_count) |
---|
85 | raise_error(traits_inst, regex_constants::error_space); |
---|
86 | while(pstate) |
---|
87 | { |
---|
88 | matcher_proc_type proc = s_match_vtable[pstate->type]; |
---|
89 | ++state_count; |
---|
90 | if(!(this->*proc)()) |
---|
91 | { |
---|
92 | if((m_match_flags & match_partial) && (position == last) && (position != search_base)) |
---|
93 | m_has_partial_match = true; |
---|
94 | return 0; |
---|
95 | } |
---|
96 | } |
---|
97 | return true; |
---|
98 | } |
---|
99 | |
---|
100 | template <class BidiIterator, class Allocator, class traits> |
---|
101 | bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark() |
---|
102 | { |
---|
103 | int index = static_cast<const re_brace*>(pstate)->index; |
---|
104 | bool r = true; |
---|
105 | switch(index) |
---|
106 | { |
---|
107 | case 0: |
---|
108 | pstate = pstate->next.p; |
---|
109 | break; |
---|
110 | case -1: |
---|
111 | case -2: |
---|
112 | { |
---|
113 | // forward lookahead assert: |
---|
114 | BidiIterator old_position(position); |
---|
115 | const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p; |
---|
116 | pstate = pstate->next.p->next.p; |
---|
117 | r = match_all_states(); |
---|
118 | pstate = next_pstate; |
---|
119 | position = old_position; |
---|
120 | if((r && (index != -1)) || (!r && (index != -2))) |
---|
121 | r = false; |
---|
122 | else |
---|
123 | r = true; |
---|
124 | break; |
---|
125 | } |
---|
126 | case -3: |
---|
127 | { |
---|
128 | // independent sub-expression: |
---|
129 | bool old_independent = m_independent; |
---|
130 | m_independent = true; |
---|
131 | const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p; |
---|
132 | pstate = pstate->next.p->next.p; |
---|
133 | r = match_all_states(); |
---|
134 | pstate = next_pstate; |
---|
135 | m_independent = old_independent; |
---|
136 | #ifdef BOOST_REGEX_MATCH_EXTRA |
---|
137 | if(r && (m_match_flags & match_extra)) |
---|
138 | { |
---|
139 | // |
---|
140 | // our captures have been stored in *m_presult |
---|
141 | // we need to unpack them, and insert them |
---|
142 | // back in the right order when we unwind the stack: |
---|
143 | // |
---|
144 | unsigned i; |
---|
145 | match_results<BidiIterator, Allocator> tm(*m_presult); |
---|
146 | for(i = 0; i < tm.size(); ++i) |
---|
147 | (*m_presult)[i].get_captures().clear(); |
---|
148 | // match everything else: |
---|
149 | r = match_all_states(); |
---|
150 | // now place the stored captures back: |
---|
151 | for(i = 0; i < tm.size(); ++i) |
---|
152 | { |
---|
153 | typedef typename sub_match<BidiIterator>::capture_sequence_type seq; |
---|
154 | seq& s1 = (*m_presult)[i].get_captures(); |
---|
155 | const seq& s2 = tm[i].captures(); |
---|
156 | s1.insert( |
---|
157 | s1.end(), |
---|
158 | s2.begin(), |
---|
159 | s2.end()); |
---|
160 | } |
---|
161 | } |
---|
162 | #endif |
---|
163 | break; |
---|
164 | } |
---|
165 | case -4: |
---|
166 | { |
---|
167 | // conditional expression: |
---|
168 | const re_alt* alt = static_cast<const re_alt*>(pstate->next.p); |
---|
169 | BOOST_ASSERT(alt->type == syntax_element_alt); |
---|
170 | pstate = alt->next.p; |
---|
171 | if(pstate->type == syntax_element_assert_backref) |
---|
172 | { |
---|
173 | if(!match_assert_backref()) |
---|
174 | pstate = alt->alt.p; |
---|
175 | break; |
---|
176 | } |
---|
177 | else |
---|
178 | { |
---|
179 | // zero width assertion, have to match this recursively: |
---|
180 | BOOST_ASSERT(pstate->type == syntax_element_startmark); |
---|
181 | bool negated = static_cast<const re_brace*>(pstate)->index == -2; |
---|
182 | BidiIterator saved_position = position; |
---|
183 | const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p; |
---|
184 | pstate = pstate->next.p->next.p; |
---|
185 | bool r = match_all_states(); |
---|
186 | position = saved_position; |
---|
187 | if(negated) |
---|
188 | r = !r; |
---|
189 | if(r) |
---|
190 | pstate = next_pstate; |
---|
191 | else |
---|
192 | pstate = alt->alt.p; |
---|
193 | break; |
---|
194 | } |
---|
195 | } |
---|
196 | default: |
---|
197 | { |
---|
198 | BOOST_ASSERT(index > 0); |
---|
199 | if((m_match_flags & match_nosubs) == 0) |
---|
200 | { |
---|
201 | backup_subex<BidiIterator> sub(*m_presult, index); |
---|
202 | m_presult->set_first(position, index); |
---|
203 | pstate = pstate->next.p; |
---|
204 | r = match_all_states(); |
---|
205 | if(r == false) |
---|
206 | sub.restore(*m_presult); |
---|
207 | #ifdef BOOST_REGEX_MATCH_EXTRA |
---|
208 | // |
---|
209 | // we have a match, push the capture information onto the stack: |
---|
210 | // |
---|
211 | else if(sub.get().matched && (match_extra & m_match_flags)) |
---|
212 | ((*m_presult)[index]).get_captures().push_back(sub.get()); |
---|
213 | #endif |
---|
214 | } |
---|
215 | else |
---|
216 | { |
---|
217 | pstate = pstate->next.p; |
---|
218 | } |
---|
219 | break; |
---|
220 | } |
---|
221 | } |
---|
222 | return r; |
---|
223 | } |
---|
224 | |
---|
225 | template <class BidiIterator, class Allocator, class traits> |
---|
226 | bool perl_matcher<BidiIterator, Allocator, traits>::match_alt() |
---|
227 | { |
---|
228 | bool take_first, take_second; |
---|
229 | const re_alt* jmp = static_cast<const re_alt*>(pstate); |
---|
230 | |
---|
231 | // find out which of these two alternatives we need to take: |
---|
232 | if(position == last) |
---|
233 | { |
---|
234 | take_first = jmp->can_be_null & mask_take; |
---|
235 | take_second = jmp->can_be_null & mask_skip; |
---|
236 | } |
---|
237 | else |
---|
238 | { |
---|
239 | take_first = can_start(*position, jmp->_map, (unsigned char)mask_take); |
---|
240 | take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip); |
---|
241 | } |
---|
242 | |
---|
243 | if(take_first) |
---|
244 | { |
---|
245 | // we can take the first alternative, |
---|
246 | // see if we need to push next alternative: |
---|
247 | if(take_second) |
---|
248 | { |
---|
249 | BidiIterator oldposition(position); |
---|
250 | const re_syntax_base* old_pstate = jmp->alt.p; |
---|
251 | pstate = pstate->next.p; |
---|
252 | if(!match_all_states()) |
---|
253 | { |
---|
254 | pstate = old_pstate; |
---|
255 | position = oldposition; |
---|
256 | } |
---|
257 | return true; |
---|
258 | } |
---|
259 | pstate = pstate->next.p; |
---|
260 | return true; |
---|
261 | } |
---|
262 | if(take_second) |
---|
263 | { |
---|
264 | pstate = jmp->alt.p; |
---|
265 | return true; |
---|
266 | } |
---|
267 | return false; // neither option is possible |
---|
268 | } |
---|
269 | |
---|
270 | template <class BidiIterator, class Allocator, class traits> |
---|
271 | bool perl_matcher<BidiIterator, Allocator, traits>::match_rep() |
---|
272 | { |
---|
273 | #ifdef BOOST_MSVC |
---|
274 | #pragma warning(push) |
---|
275 | #pragma warning(disable:4127 4244) |
---|
276 | #endif |
---|
277 | const re_repeat* rep = static_cast<const re_repeat*>(pstate); |
---|
278 | // |
---|
279 | // Always copy the repeat count, so that the state is restored |
---|
280 | // when we exit this scope: |
---|
281 | // |
---|
282 | repeater_count<BidiIterator> r(rep->id, &next_count, position); |
---|
283 | // |
---|
284 | // If we've had at least one repeat already, and the last one |
---|
285 | // matched the NULL string then set the repeat count to |
---|
286 | // maximum: |
---|
287 | // |
---|
288 | next_count->check_null_repeat(position, rep->max); |
---|
289 | |
---|
290 | // find out which of these two alternatives we need to take: |
---|
291 | bool take_first, take_second; |
---|
292 | if(position == last) |
---|
293 | { |
---|
294 | take_first = rep->can_be_null & mask_take; |
---|
295 | take_second = rep->can_be_null & mask_skip; |
---|
296 | } |
---|
297 | else |
---|
298 | { |
---|
299 | take_first = can_start(*position, rep->_map, (unsigned char)mask_take); |
---|
300 | take_second = can_start(*position, rep->_map, (unsigned char)mask_skip); |
---|
301 | } |
---|
302 | |
---|
303 | if(next_count->get_count() < rep->min) |
---|
304 | { |
---|
305 | // we must take the repeat: |
---|
306 | if(take_first) |
---|
307 | { |
---|
308 | // increase the counter: |
---|
309 | ++(*next_count); |
---|
310 | pstate = rep->next.p; |
---|
311 | return match_all_states(); |
---|
312 | } |
---|
313 | return false; |
---|
314 | } |
---|
315 | bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent); |
---|
316 | if(greedy) |
---|
317 | { |
---|
318 | // try and take the repeat if we can: |
---|
319 | if((next_count->get_count() < rep->max) && take_first) |
---|
320 | { |
---|
321 | // store position in case we fail: |
---|
322 | BidiIterator pos = position; |
---|
323 | // increase the counter: |
---|
324 | ++(*next_count); |
---|
325 | pstate = rep->next.p; |
---|
326 | if(match_all_states()) |
---|
327 | return true; |
---|
328 | // failed repeat, reset posistion and fall through for alternative: |
---|
329 | position = pos; |
---|
330 | } |
---|
331 | if(take_second) |
---|
332 | { |
---|
333 | pstate = rep->alt.p; |
---|
334 | return true; |
---|
335 | } |
---|
336 | return false; // can't take anything, fail... |
---|
337 | } |
---|
338 | else // non-greedy |
---|
339 | { |
---|
340 | // try and skip the repeat if we can: |
---|
341 | if(take_second) |
---|
342 | { |
---|
343 | // store position in case we fail: |
---|
344 | BidiIterator pos = position; |
---|
345 | pstate = rep->alt.p; |
---|
346 | if(match_all_states()) |
---|
347 | return true; |
---|
348 | // failed alternative, reset posistion and fall through for repeat: |
---|
349 | position = pos; |
---|
350 | } |
---|
351 | if((next_count->get_count() < rep->max) && take_first) |
---|
352 | { |
---|
353 | // increase the counter: |
---|
354 | ++(*next_count); |
---|
355 | pstate = rep->next.p; |
---|
356 | return match_all_states(); |
---|
357 | } |
---|
358 | } |
---|
359 | return false; |
---|
360 | #ifdef BOOST_MSVC |
---|
361 | #pragma warning(pop) |
---|
362 | #endif |
---|
363 | } |
---|
364 | |
---|
365 | template <class BidiIterator, class Allocator, class traits> |
---|
366 | bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow() |
---|
367 | { |
---|
368 | #ifdef BOOST_MSVC |
---|
369 | #pragma warning(push) |
---|
370 | #pragma warning(disable:4127) |
---|
371 | #endif |
---|
372 | unsigned count = 0; |
---|
373 | const re_repeat* rep = static_cast<const re_repeat*>(pstate); |
---|
374 | re_syntax_base* psingle = rep->next.p; |
---|
375 | // match compulsary repeats first: |
---|
376 | while(count < rep->min) |
---|
377 | { |
---|
378 | pstate = psingle; |
---|
379 | if(!match_wild()) |
---|
380 | return false; |
---|
381 | ++count; |
---|
382 | } |
---|
383 | bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent); |
---|
384 | if(greedy) |
---|
385 | { |
---|
386 | // normal repeat: |
---|
387 | while(count < rep->max) |
---|
388 | { |
---|
389 | pstate = psingle; |
---|
390 | if(!match_wild()) |
---|
391 | break; |
---|
392 | ++count; |
---|
393 | } |
---|
394 | if((rep->leading) && (count < rep->max)) |
---|
395 | restart = position; |
---|
396 | pstate = rep; |
---|
397 | return backtrack_till_match(count - rep->min); |
---|
398 | } |
---|
399 | else |
---|
400 | { |
---|
401 | // non-greedy, keep trying till we get a match: |
---|
402 | BidiIterator save_pos; |
---|
403 | do |
---|
404 | { |
---|
405 | if((rep->leading) && (rep->max == UINT_MAX)) |
---|
406 | restart = position; |
---|
407 | pstate = rep->alt.p; |
---|
408 | save_pos = position; |
---|
409 | ++state_count; |
---|
410 | if(match_all_states()) |
---|
411 | return true; |
---|
412 | if(count >= rep->max) |
---|
413 | return false; |
---|
414 | ++count; |
---|
415 | pstate = psingle; |
---|
416 | position = save_pos; |
---|
417 | if(!match_wild()) |
---|
418 | return false; |
---|
419 | }while(true); |
---|
420 | } |
---|
421 | #ifdef BOOST_MSVC |
---|
422 | #pragma warning(pop) |
---|
423 | #endif |
---|
424 | } |
---|
425 | |
---|
426 | template <class BidiIterator, class Allocator, class traits> |
---|
427 | bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast() |
---|
428 | { |
---|
429 | #ifdef BOOST_MSVC |
---|
430 | #pragma warning(push) |
---|
431 | #pragma warning(disable:4127) |
---|
432 | #endif |
---|
433 | if(m_match_flags & match_not_dot_null) |
---|
434 | return match_dot_repeat_slow(); |
---|
435 | if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0) |
---|
436 | return match_dot_repeat_slow(); |
---|
437 | // |
---|
438 | // start by working out how much we can skip: |
---|
439 | // |
---|
440 | const re_repeat* rep = static_cast<const re_repeat*>(pstate); |
---|
441 | #ifdef BOOST_MSVC |
---|
442 | #pragma warning(push) |
---|
443 | #pragma warning(disable:4267) |
---|
444 | #endif |
---|
445 | bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent); |
---|
446 | std::size_t count = (std::min)(static_cast<std::size_t>(::boost::re_detail::distance(position, last)), static_cast<std::size_t>(greedy ? rep->max : rep->min)); |
---|
447 | if(rep->min > count) |
---|
448 | { |
---|
449 | position = last; |
---|
450 | return false; // not enough text left to match |
---|
451 | } |
---|
452 | std::advance(position, count); |
---|
453 | #ifdef BOOST_MSVC |
---|
454 | #pragma warning(pop) |
---|
455 | #endif |
---|
456 | if((rep->leading) && (count < rep->max) && greedy) |
---|
457 | restart = position; |
---|
458 | if(greedy) |
---|
459 | return backtrack_till_match(count - rep->min); |
---|
460 | |
---|
461 | // non-greedy, keep trying till we get a match: |
---|
462 | BidiIterator save_pos; |
---|
463 | do |
---|
464 | { |
---|
465 | while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip)) |
---|
466 | { |
---|
467 | ++position; |
---|
468 | ++count; |
---|
469 | } |
---|
470 | if((rep->leading) && (rep->max == UINT_MAX)) |
---|
471 | restart = position; |
---|
472 | pstate = rep->alt.p; |
---|
473 | save_pos = position; |
---|
474 | ++state_count; |
---|
475 | if(match_all_states()) |
---|
476 | return true; |
---|
477 | if(count >= rep->max) |
---|
478 | return false; |
---|
479 | if(save_pos == last) |
---|
480 | return false; |
---|
481 | position = ++save_pos; |
---|
482 | ++count; |
---|
483 | }while(true); |
---|
484 | #ifdef BOOST_MSVC |
---|
485 | #pragma warning(pop) |
---|
486 | #endif |
---|
487 | } |
---|
488 | |
---|
489 | template <class BidiIterator, class Allocator, class traits> |
---|
490 | bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat() |
---|
491 | { |
---|
492 | #ifdef BOOST_MSVC |
---|
493 | #pragma warning(push) |
---|
494 | #pragma warning(disable:4127) |
---|
495 | #pragma warning(disable:4267) |
---|
496 | #endif |
---|
497 | #ifdef __BORLANDC__ |
---|
498 | #pragma option push -w-8008 -w-8066 -w-8004 |
---|
499 | #endif |
---|
500 | const re_repeat* rep = static_cast<const re_repeat*>(pstate); |
---|
501 | BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length); |
---|
502 | const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1); |
---|
503 | // |
---|
504 | // start by working out how much we can skip: |
---|
505 | // |
---|
506 | bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent); |
---|
507 | std::size_t count, desired; |
---|
508 | if(::boost::is_random_access_iterator<BidiIterator>::value) |
---|
509 | { |
---|
510 | desired = |
---|
511 | (std::min)( |
---|
512 | (std::size_t)(greedy ? rep->max : rep->min), |
---|
513 | (std::size_t)::boost::re_detail::distance(position, last)); |
---|
514 | count = desired; |
---|
515 | ++desired; |
---|
516 | if(icase) |
---|
517 | { |
---|
518 | while(--desired && (traits_inst.translate_nocase(*position) == what)) |
---|
519 | { |
---|
520 | ++position; |
---|
521 | } |
---|
522 | } |
---|
523 | else |
---|
524 | { |
---|
525 | while(--desired && (traits_inst.translate(*position) == what)) |
---|
526 | { |
---|
527 | ++position; |
---|
528 | } |
---|
529 | } |
---|
530 | count = count - desired; |
---|
531 | } |
---|
532 | else |
---|
533 | { |
---|
534 | count = 0; |
---|
535 | desired = greedy ? rep->max : rep->min; |
---|
536 | while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what)) |
---|
537 | { |
---|
538 | ++position; |
---|
539 | ++count; |
---|
540 | } |
---|
541 | } |
---|
542 | if((rep->leading) && (count < rep->max) && greedy) |
---|
543 | restart = position; |
---|
544 | if(count < rep->min) |
---|
545 | return false; |
---|
546 | |
---|
547 | if(greedy) |
---|
548 | return backtrack_till_match(count - rep->min); |
---|
549 | |
---|
550 | // non-greedy, keep trying till we get a match: |
---|
551 | BidiIterator save_pos; |
---|
552 | do |
---|
553 | { |
---|
554 | while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip)) |
---|
555 | { |
---|
556 | if((traits_inst.translate(*position, icase) == what)) |
---|
557 | { |
---|
558 | ++position; |
---|
559 | ++count; |
---|
560 | } |
---|
561 | else |
---|
562 | return false; // counldn't repeat even though it was the only option |
---|
563 | } |
---|
564 | if((rep->leading) && (rep->max == UINT_MAX)) |
---|
565 | restart = position; |
---|
566 | pstate = rep->alt.p; |
---|
567 | save_pos = position; |
---|
568 | ++state_count; |
---|
569 | if(match_all_states()) |
---|
570 | return true; |
---|
571 | if(count >= rep->max) |
---|
572 | return false; |
---|
573 | position = save_pos; |
---|
574 | if(position == last) |
---|
575 | return false; |
---|
576 | if(traits_inst.translate(*position, icase) == what) |
---|
577 | { |
---|
578 | ++position; |
---|
579 | ++count; |
---|
580 | } |
---|
581 | else |
---|
582 | { |
---|
583 | return false; |
---|
584 | } |
---|
585 | }while(true); |
---|
586 | #ifdef __BORLANDC__ |
---|
587 | #pragma option pop |
---|
588 | #endif |
---|
589 | #ifdef BOOST_MSVC |
---|
590 | #pragma warning(pop) |
---|
591 | #endif |
---|
592 | } |
---|
593 | |
---|
594 | template <class BidiIterator, class Allocator, class traits> |
---|
595 | bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat() |
---|
596 | { |
---|
597 | #ifdef BOOST_MSVC |
---|
598 | #pragma warning(push) |
---|
599 | #pragma warning(disable:4127) |
---|
600 | #endif |
---|
601 | #ifdef __BORLANDC__ |
---|
602 | #pragma option push -w-8008 -w-8066 -w-8004 |
---|
603 | #endif |
---|
604 | const re_repeat* rep = static_cast<const re_repeat*>(pstate); |
---|
605 | const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map; |
---|
606 | unsigned count = 0; |
---|
607 | // |
---|
608 | // start by working out how much we can skip: |
---|
609 | // |
---|
610 | bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent); |
---|
611 | std::size_t desired = greedy ? rep->max : rep->min; |
---|
612 | if(::boost::is_random_access_iterator<BidiIterator>::value) |
---|
613 | { |
---|
614 | BidiIterator end = position; |
---|
615 | std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired)); |
---|
616 | BidiIterator origin(position); |
---|
617 | while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))]) |
---|
618 | { |
---|
619 | ++position; |
---|
620 | } |
---|
621 | count = (unsigned)::boost::re_detail::distance(origin, position); |
---|
622 | } |
---|
623 | else |
---|
624 | { |
---|
625 | while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))]) |
---|
626 | { |
---|
627 | ++position; |
---|
628 | ++count; |
---|
629 | } |
---|
630 | } |
---|
631 | if((rep->leading) && (count < rep->max) && greedy) |
---|
632 | restart = position; |
---|
633 | if(count < rep->min) |
---|
634 | return false; |
---|
635 | |
---|
636 | if(greedy) |
---|
637 | return backtrack_till_match(count - rep->min); |
---|
638 | |
---|
639 | // non-greedy, keep trying till we get a match: |
---|
640 | BidiIterator save_pos; |
---|
641 | do |
---|
642 | { |
---|
643 | while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip)) |
---|
644 | { |
---|
645 | if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))]) |
---|
646 | { |
---|
647 | ++position; |
---|
648 | ++count; |
---|
649 | } |
---|
650 | else |
---|
651 | return false; // counldn't repeat even though it was the only option |
---|
652 | } |
---|
653 | if((rep->leading) && (rep->max == UINT_MAX)) |
---|
654 | restart = position; |
---|
655 | pstate = rep->alt.p; |
---|
656 | save_pos = position; |
---|
657 | ++state_count; |
---|
658 | if(match_all_states()) |
---|
659 | return true; |
---|
660 | if(count >= rep->max) |
---|
661 | return false; |
---|
662 | position = save_pos; |
---|
663 | if(position == last) |
---|
664 | return false; |
---|
665 | if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))]) |
---|
666 | { |
---|
667 | ++position; |
---|
668 | ++count; |
---|
669 | } |
---|
670 | else |
---|
671 | { |
---|
672 | return false; |
---|
673 | } |
---|
674 | }while(true); |
---|
675 | #ifdef __BORLANDC__ |
---|
676 | #pragma option pop |
---|
677 | #endif |
---|
678 | #ifdef BOOST_MSVC |
---|
679 | #pragma warning(pop) |
---|
680 | #endif |
---|
681 | } |
---|
682 | |
---|
683 | template <class BidiIterator, class Allocator, class traits> |
---|
684 | bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat() |
---|
685 | { |
---|
686 | #ifdef BOOST_MSVC |
---|
687 | #pragma warning(push) |
---|
688 | #pragma warning(disable:4127) |
---|
689 | #endif |
---|
690 | #ifdef __BORLANDC__ |
---|
691 | #pragma option push -w-8008 -w-8066 -w-8004 |
---|
692 | #endif |
---|
693 | typedef typename traits::char_class_type char_class_type; |
---|
694 | const re_repeat* rep = static_cast<const re_repeat*>(pstate); |
---|
695 | const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p); |
---|
696 | unsigned count = 0; |
---|
697 | // |
---|
698 | // start by working out how much we can skip: |
---|
699 | // |
---|
700 | bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent); |
---|
701 | std::size_t desired = greedy ? rep->max : rep->min; |
---|
702 | if(::boost::is_random_access_iterator<BidiIterator>::value) |
---|
703 | { |
---|
704 | BidiIterator end = position; |
---|
705 | std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired)); |
---|
706 | BidiIterator origin(position); |
---|
707 | while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase))) |
---|
708 | { |
---|
709 | ++position; |
---|
710 | } |
---|
711 | count = (unsigned)::boost::re_detail::distance(origin, position); |
---|
712 | } |
---|
713 | else |
---|
714 | { |
---|
715 | while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase))) |
---|
716 | { |
---|
717 | ++position; |
---|
718 | ++count; |
---|
719 | } |
---|
720 | } |
---|
721 | if((rep->leading) && (count < rep->max) && greedy) |
---|
722 | restart = position; |
---|
723 | if(count < rep->min) |
---|
724 | return false; |
---|
725 | |
---|
726 | if(greedy) |
---|
727 | return backtrack_till_match(count - rep->min); |
---|
728 | |
---|
729 | // non-greedy, keep trying till we get a match: |
---|
730 | BidiIterator save_pos; |
---|
731 | do |
---|
732 | { |
---|
733 | while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip)) |
---|
734 | { |
---|
735 | if(position != re_is_set_member(position, last, set, re.get_data(), icase)) |
---|
736 | { |
---|
737 | ++position; |
---|
738 | ++count; |
---|
739 | } |
---|
740 | else |
---|
741 | return false; // counldn't repeat even though it was the only option |
---|
742 | } |
---|
743 | if((rep->leading) && (rep->max == UINT_MAX)) |
---|
744 | restart = position; |
---|
745 | pstate = rep->alt.p; |
---|
746 | save_pos = position; |
---|
747 | ++state_count; |
---|
748 | if(match_all_states()) |
---|
749 | return true; |
---|
750 | if(count >= rep->max) |
---|
751 | return false; |
---|
752 | position = save_pos; |
---|
753 | if(position == last) |
---|
754 | return false; |
---|
755 | if(position != re_is_set_member(position, last, set, re.get_data(), icase)) |
---|
756 | { |
---|
757 | ++position; |
---|
758 | ++count; |
---|
759 | } |
---|
760 | else |
---|
761 | { |
---|
762 | return false; |
---|
763 | } |
---|
764 | }while(true); |
---|
765 | #ifdef __BORLANDC__ |
---|
766 | #pragma option pop |
---|
767 | #endif |
---|
768 | #ifdef BOOST_MSVC |
---|
769 | #pragma warning(pop) |
---|
770 | #endif |
---|
771 | } |
---|
772 | |
---|
773 | template <class BidiIterator, class Allocator, class traits> |
---|
774 | bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count) |
---|
775 | { |
---|
776 | #ifdef BOOST_MSVC |
---|
777 | #pragma warning(push) |
---|
778 | #pragma warning(disable:4127) |
---|
779 | #endif |
---|
780 | if((m_match_flags & match_partial) && (position == last)) |
---|
781 | m_has_partial_match = true; |
---|
782 | |
---|
783 | const re_repeat* rep = static_cast<const re_repeat*>(pstate); |
---|
784 | BidiIterator backtrack = position; |
---|
785 | if(position == last) |
---|
786 | { |
---|
787 | if(rep->can_be_null & mask_skip) |
---|
788 | { |
---|
789 | pstate = rep->alt.p; |
---|
790 | if(match_all_states()) |
---|
791 | return true; |
---|
792 | } |
---|
793 | if(count) |
---|
794 | { |
---|
795 | position = --backtrack; |
---|
796 | --count; |
---|
797 | } |
---|
798 | else |
---|
799 | return false; |
---|
800 | } |
---|
801 | do |
---|
802 | { |
---|
803 | while(count && !can_start(*position, rep->_map, mask_skip)) |
---|
804 | { |
---|
805 | --position; |
---|
806 | --count; |
---|
807 | ++state_count; |
---|
808 | } |
---|
809 | pstate = rep->alt.p; |
---|
810 | backtrack = position; |
---|
811 | if(match_all_states()) |
---|
812 | return true; |
---|
813 | if(count == 0) |
---|
814 | return false; |
---|
815 | position = --backtrack; |
---|
816 | ++state_count; |
---|
817 | --count; |
---|
818 | }while(true); |
---|
819 | #ifdef BOOST_MSVC |
---|
820 | #pragma warning(pop) |
---|
821 | #endif |
---|
822 | } |
---|
823 | |
---|
824 | } // namespace re_detail |
---|
825 | } // namespace boost |
---|
826 | |
---|
827 | #ifdef BOOST_HAS_ABI_HEADERS |
---|
828 | # include BOOST_ABI_SUFFIX |
---|
829 | #endif |
---|
830 | |
---|
831 | #endif |
---|
832 | |
---|