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 non-recursive implementation.
18 */
19
20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP
21 #define BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP
22
23 #include <new>
24
25 #ifdef BOOST_MSVC
26 #pragma warning(push)
27 #pragma warning(disable: 4103)
28 #endif
29 #ifdef BOOST_HAS_ABI_HEADERS
30 # include BOOST_ABI_PREFIX
31 #endif
32 #ifdef BOOST_MSVC
33 #pragma warning(pop)
34 #endif
35 #ifdef BOOST_MSVC
36 # pragma warning(push)
37 # pragma warning(disable: 4800)
38 #endif
39
40 namespace boost{
41 namespace re_detail{
42
43 template <class T>
inplace_destroy(T * p)44 inline void inplace_destroy(T* p)
45 {
46 (void)p; // warning suppression
47 p->~T();
48 }
49
50 struct saved_state
51 {
52 union{
53 unsigned int state_id;
54 // this padding ensures correct alignment on 64-bit platforms:
55 std::size_t padding1;
56 std::ptrdiff_t padding2;
57 void* padding3;
58 };
saved_stateboost::re_detail::saved_state59 saved_state(unsigned i) : state_id(i) {}
60 };
61
62 template <class BidiIterator>
63 struct saved_matched_paren : public saved_state
64 {
65 int index;
66 sub_match<BidiIterator> sub;
saved_matched_parenboost::re_detail::saved_matched_paren67 saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){};
68 };
69
70 template <class BidiIterator>
71 struct saved_position : public saved_state
72 {
73 const re_syntax_base* pstate;
74 BidiIterator position;
saved_positionboost::re_detail::saved_position75 saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){};
76 };
77
78 template <class BidiIterator>
79 struct saved_assertion : public saved_position<BidiIterator>
80 {
81 bool positive;
saved_assertionboost::re_detail::saved_assertion82 saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
83 : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){};
84 };
85
86 template <class BidiIterator>
87 struct saved_repeater : public saved_state
88 {
89 repeater_count<BidiIterator> count;
saved_repeaterboost::re_detail::saved_repeater90 saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start)
91 : saved_state(saved_state_repeater_count), count(i,s,start){}
92 };
93
94 struct saved_extra_block : public saved_state
95 {
96 saved_state *base, *end;
saved_extra_blockboost::re_detail::saved_extra_block97 saved_extra_block(saved_state* b, saved_state* e)
98 : saved_state(saved_state_extra_block), base(b), end(e) {}
99 };
100
101 struct save_state_init
102 {
103 saved_state** stack;
save_state_initboost::re_detail::save_state_init104 save_state_init(saved_state** base, saved_state** end)
105 : stack(base)
106 {
107 *base = static_cast<saved_state*>(get_mem_block());
108 *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
109 --(*end);
110 (void) new (*end)saved_state(0);
111 BOOST_ASSERT(*end > *base);
112 }
~save_state_initboost::re_detail::save_state_init113 ~save_state_init()
114 {
115 put_mem_block(*stack);
116 *stack = 0;
117 }
118 };
119
120 template <class BidiIterator>
121 struct saved_single_repeat : public saved_state
122 {
123 std::size_t count;
124 const re_repeat* rep;
125 BidiIterator last_position;
saved_single_repeatboost::re_detail::saved_single_repeat126 saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
127 : saved_state(arg_id), count(c), rep(r), last_position(lp){}
128 };
129
130 template <class Results>
131 struct saved_recursion : public saved_state
132 {
saved_recursionboost::re_detail::saved_recursion133 saved_recursion(int idx, const re_syntax_base* p, Results* pr)
134 : saved_state(14), recursion_id(idx), preturn_address(p), results(*pr)
135 {}
136 int recursion_id;
137 const re_syntax_base* preturn_address;
138 Results results;
139 };
140
141 template <class BidiIterator, class Allocator, class traits>
match_all_states()142 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
143 {
144 static matcher_proc_type const s_match_vtable[30] =
145 {
146 (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
147 &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
148 &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
149 &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
150 &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
151 &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
152 &perl_matcher<BidiIterator, Allocator, traits>::match_match,
153 &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
154 &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
155 &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
156 &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
157 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
158 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
159 &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
160 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
161 &perl_matcher<BidiIterator, Allocator, traits>::match_set,
162 &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
163 &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
164 &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
165 &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
166 &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
167 &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
168 // Although this next line *should* be evaluated at compile time, in practice
169 // some compilers (VC++) emit run-time initialisation which breaks thread
170 // safety, so use a dispatch function instead:
171 //(::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),
172 &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
173 &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
174 &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
175 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
176 &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
177 &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
178 &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
179 &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
180 };
181
182 push_recursion_stopper();
183 do{
184 while(pstate)
185 {
186 matcher_proc_type proc = s_match_vtable[pstate->type];
187 ++state_count;
188 if(!(this->*proc)())
189 {
190 if(state_count > max_state_count)
191 raise_error(traits_inst, regex_constants::error_complexity);
192 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
193 m_has_partial_match = true;
194 bool successful_unwind = unwind(false);
195 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
196 m_has_partial_match = true;
197 if(false == successful_unwind)
198 return m_recursive_result;
199 }
200 }
201 }while(unwind(true));
202 return m_recursive_result;
203 }
204
205 template <class BidiIterator, class Allocator, class traits>
extend_stack()206 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
207 {
208 if(used_block_count)
209 {
210 --used_block_count;
211 saved_state* stack_base;
212 saved_state* backup_state;
213 stack_base = static_cast<saved_state*>(get_mem_block());
214 backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
215 saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
216 --block;
217 (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
218 m_stack_base = stack_base;
219 m_backup_state = block;
220 }
221 else
222 raise_error(traits_inst, regex_constants::error_stack);
223 }
224
225 template <class BidiIterator, class Allocator, class traits>
push_matched_paren(int index,const sub_match<BidiIterator> & sub)226 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
227 {
228 //BOOST_ASSERT(index);
229 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
230 --pmp;
231 if(pmp < m_stack_base)
232 {
233 extend_stack();
234 pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
235 --pmp;
236 }
237 (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
238 m_backup_state = pmp;
239 }
240
241 template <class BidiIterator, class Allocator, class traits>
push_recursion_stopper()242 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
243 {
244 saved_state* pmp = m_backup_state;
245 --pmp;
246 if(pmp < m_stack_base)
247 {
248 extend_stack();
249 pmp = m_backup_state;
250 --pmp;
251 }
252 (void) new (pmp)saved_state(saved_type_recurse);
253 m_backup_state = pmp;
254 }
255
256 template <class BidiIterator, class Allocator, class traits>
push_assertion(const re_syntax_base * ps,bool positive)257 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
258 {
259 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
260 --pmp;
261 if(pmp < m_stack_base)
262 {
263 extend_stack();
264 pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
265 --pmp;
266 }
267 (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
268 m_backup_state = pmp;
269 }
270
271 template <class BidiIterator, class Allocator, class traits>
push_alt(const re_syntax_base * ps)272 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
273 {
274 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
275 --pmp;
276 if(pmp < m_stack_base)
277 {
278 extend_stack();
279 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
280 --pmp;
281 }
282 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
283 m_backup_state = pmp;
284 }
285
286 template <class BidiIterator, class Allocator, class traits>
push_non_greedy_repeat(const re_syntax_base * ps)287 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
288 {
289 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
290 --pmp;
291 if(pmp < m_stack_base)
292 {
293 extend_stack();
294 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
295 --pmp;
296 }
297 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
298 m_backup_state = pmp;
299 }
300
301 template <class BidiIterator, class Allocator, class traits>
push_repeater_count(int i,repeater_count<BidiIterator> ** s)302 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
303 {
304 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
305 --pmp;
306 if(pmp < m_stack_base)
307 {
308 extend_stack();
309 pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
310 --pmp;
311 }
312 (void) new (pmp)saved_repeater<BidiIterator>(i, s, position);
313 m_backup_state = pmp;
314 }
315
316 template <class BidiIterator, class Allocator, class traits>
push_single_repeat(std::size_t c,const re_repeat * r,BidiIterator last_position,int state_id)317 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
318 {
319 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
320 --pmp;
321 if(pmp < m_stack_base)
322 {
323 extend_stack();
324 pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
325 --pmp;
326 }
327 (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
328 m_backup_state = pmp;
329 }
330
331 template <class BidiIterator, class Allocator, class traits>
push_recursion(int idx,const re_syntax_base * p,results_type * presults)332 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion(int idx, const re_syntax_base* p, results_type* presults)
333 {
334 saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
335 --pmp;
336 if(pmp < m_stack_base)
337 {
338 extend_stack();
339 pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
340 --pmp;
341 }
342 (void) new (pmp)saved_recursion<results_type>(idx, p, presults);
343 m_backup_state = pmp;
344 }
345
346 template <class BidiIterator, class Allocator, class traits>
match_startmark()347 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
348 {
349 int index = static_cast<const re_brace*>(pstate)->index;
350 icase = static_cast<const re_brace*>(pstate)->icase;
351 switch(index)
352 {
353 case 0:
354 pstate = pstate->next.p;
355 break;
356 case -1:
357 case -2:
358 {
359 // forward lookahead assert:
360 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
361 pstate = pstate->next.p->next.p;
362 push_assertion(next_pstate, index == -1);
363 break;
364 }
365 case -3:
366 {
367 // independent sub-expression, currently this is always recursive:
368 bool old_independent = m_independent;
369 m_independent = true;
370 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
371 pstate = pstate->next.p->next.p;
372 bool r = match_all_states();
373 pstate = next_pstate;
374 m_independent = old_independent;
375 #ifdef BOOST_REGEX_MATCH_EXTRA
376 if(r && (m_match_flags & match_extra))
377 {
378 //
379 // our captures have been stored in *m_presult
380 // we need to unpack them, and insert them
381 // back in the right order when we unwind the stack:
382 //
383 match_results<BidiIterator, Allocator> temp_match(*m_presult);
384 unsigned i;
385 for(i = 0; i < temp_match.size(); ++i)
386 (*m_presult)[i].get_captures().clear();
387 // match everything else:
388 r = match_all_states();
389 // now place the stored captures back:
390 for(i = 0; i < temp_match.size(); ++i)
391 {
392 typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
393 seq& s1 = (*m_presult)[i].get_captures();
394 const seq& s2 = temp_match[i].captures();
395 s1.insert(
396 s1.end(),
397 s2.begin(),
398 s2.end());
399 }
400 }
401 #endif
402 return r;
403 }
404 case -4:
405 {
406 // conditional expression:
407 const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
408 BOOST_ASSERT(alt->type == syntax_element_alt);
409 pstate = alt->next.p;
410 if(pstate->type == syntax_element_assert_backref)
411 {
412 if(!match_assert_backref())
413 pstate = alt->alt.p;
414 break;
415 }
416 else
417 {
418 // zero width assertion, have to match this recursively:
419 BOOST_ASSERT(pstate->type == syntax_element_startmark);
420 bool negated = static_cast<const re_brace*>(pstate)->index == -2;
421 BidiIterator saved_position = position;
422 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
423 pstate = pstate->next.p->next.p;
424 bool r = match_all_states();
425 position = saved_position;
426 if(negated)
427 r = !r;
428 if(r)
429 pstate = next_pstate;
430 else
431 pstate = alt->alt.p;
432 break;
433 }
434 }
435 case -5:
436 {
437 push_matched_paren(0, (*m_presult)[0]);
438 m_presult->set_first(position, 0, true);
439 pstate = pstate->next.p;
440 break;
441 }
442 default:
443 {
444 BOOST_ASSERT(index > 0);
445 if((m_match_flags & match_nosubs) == 0)
446 {
447 push_matched_paren(index, (*m_presult)[index]);
448 m_presult->set_first(position, index);
449 }
450 pstate = pstate->next.p;
451 break;
452 }
453 }
454 return true;
455 }
456
457 template <class BidiIterator, class Allocator, class traits>
match_alt()458 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
459 {
460 bool take_first, take_second;
461 const re_alt* jmp = static_cast<const re_alt*>(pstate);
462
463 // find out which of these two alternatives we need to take:
464 if(position == last)
465 {
466 take_first = jmp->can_be_null & mask_take;
467 take_second = jmp->can_be_null & mask_skip;
468 }
469 else
470 {
471 take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
472 take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
473 }
474
475 if(take_first)
476 {
477 // we can take the first alternative,
478 // see if we need to push next alternative:
479 if(take_second)
480 {
481 push_alt(jmp->alt.p);
482 }
483 pstate = pstate->next.p;
484 return true;
485 }
486 if(take_second)
487 {
488 pstate = jmp->alt.p;
489 return true;
490 }
491 return false; // neither option is possible
492 }
493
494 template <class BidiIterator, class Allocator, class traits>
match_rep()495 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
496 {
497 #ifdef BOOST_MSVC
498 #pragma warning(push)
499 #pragma warning(disable:4127 4244)
500 #endif
501 #ifdef __BORLANDC__
502 #pragma option push -w-8008 -w-8066 -w-8004
503 #endif
504 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
505
506 // find out which of these two alternatives we need to take:
507 bool take_first, take_second;
508 if(position == last)
509 {
510 take_first = rep->can_be_null & mask_take;
511 take_second = rep->can_be_null & mask_skip;
512 }
513 else
514 {
515 take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
516 take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
517 }
518
519 if((m_backup_state->state_id != saved_state_repeater_count)
520 || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
521 || (next_count->get_id() != rep->state_id))
522 {
523 // we're moving to a different repeat from the last
524 // one, so set up a counter object:
525 push_repeater_count(rep->state_id, &next_count);
526 }
527 //
528 // If we've had at least one repeat already, and the last one
529 // matched the NULL string then set the repeat count to
530 // maximum:
531 //
532 next_count->check_null_repeat(position, rep->max);
533
534 if(next_count->get_count() < rep->min)
535 {
536 // we must take the repeat:
537 if(take_first)
538 {
539 // increase the counter:
540 ++(*next_count);
541 pstate = rep->next.p;
542 return true;
543 }
544 return false;
545 }
546
547 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
548 if(greedy)
549 {
550 // try and take the repeat if we can:
551 if((next_count->get_count() < rep->max) && take_first)
552 {
553 if(take_second)
554 {
555 // store position in case we fail:
556 push_alt(rep->alt.p);
557 }
558 // increase the counter:
559 ++(*next_count);
560 pstate = rep->next.p;
561 return true;
562 }
563 else if(take_second)
564 {
565 pstate = rep->alt.p;
566 return true;
567 }
568 return false; // can't take anything, fail...
569 }
570 else // non-greedy
571 {
572 // try and skip the repeat if we can:
573 if(take_second)
574 {
575 if((next_count->get_count() < rep->max) && take_first)
576 {
577 // store position in case we fail:
578 push_non_greedy_repeat(rep->next.p);
579 }
580 pstate = rep->alt.p;
581 return true;
582 }
583 if((next_count->get_count() < rep->max) && take_first)
584 {
585 // increase the counter:
586 ++(*next_count);
587 pstate = rep->next.p;
588 return true;
589 }
590 }
591 return false;
592 #ifdef __BORLANDC__
593 #pragma option pop
594 #endif
595 #ifdef BOOST_MSVC
596 #pragma warning(pop)
597 #endif
598 }
599
600 template <class BidiIterator, class Allocator, class traits>
match_dot_repeat_slow()601 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
602 {
603 unsigned count = 0;
604 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
605 re_syntax_base* psingle = rep->next.p;
606 // match compulsary repeats first:
607 while(count < rep->min)
608 {
609 pstate = psingle;
610 if(!match_wild())
611 return false;
612 ++count;
613 }
614 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
615 if(greedy)
616 {
617 // repeat for as long as we can:
618 while(count < rep->max)
619 {
620 pstate = psingle;
621 if(!match_wild())
622 break;
623 ++count;
624 }
625 // remember where we got to if this is a leading repeat:
626 if((rep->leading) && (count < rep->max))
627 restart = position;
628 // push backtrack info if available:
629 if(count - rep->min)
630 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
631 // jump to next state:
632 pstate = rep->alt.p;
633 return true;
634 }
635 else
636 {
637 // non-greedy, push state and return true if we can skip:
638 if(count < rep->max)
639 push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
640 pstate = rep->alt.p;
641 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
642 }
643 }
644
645 template <class BidiIterator, class Allocator, class traits>
match_dot_repeat_fast()646 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
647 {
648 if(m_match_flags & match_not_dot_null)
649 return match_dot_repeat_slow();
650 if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
651 return match_dot_repeat_slow();
652
653 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
654 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
655 unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::re_detail::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));
656 if(rep->min > count)
657 {
658 position = last;
659 return false; // not enough text left to match
660 }
661 std::advance(position, count);
662
663 if(greedy)
664 {
665 if((rep->leading) && (count < rep->max))
666 restart = position;
667 // push backtrack info if available:
668 if(count - rep->min)
669 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
670 // jump to next state:
671 pstate = rep->alt.p;
672 return true;
673 }
674 else
675 {
676 // non-greedy, push state and return true if we can skip:
677 if(count < rep->max)
678 push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
679 pstate = rep->alt.p;
680 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
681 }
682 }
683
684 template <class BidiIterator, class Allocator, class traits>
match_char_repeat()685 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
686 {
687 #ifdef BOOST_MSVC
688 #pragma warning(push)
689 #pragma warning(disable:4127)
690 #endif
691 #ifdef __BORLANDC__
692 #pragma option push -w-8008 -w-8066 -w-8004
693 #endif
694 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
695 BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
696 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
697 std::size_t count = 0;
698 //
699 // start by working out how much we can skip:
700 //
701 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
702 std::size_t desired = greedy ? rep->max : rep->min;
703 if(::boost::is_random_access_iterator<BidiIterator>::value)
704 {
705 BidiIterator end = position;
706 // Move end forward by "desired", preferably without using distance or advance if we can
707 // as these can be slow for some iterator types.
708 std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::re_detail::distance(position, last);
709 if(desired >= len)
710 end = last;
711 else
712 std::advance(end, desired);
713 BidiIterator origin(position);
714 while((position != end) && (traits_inst.translate(*position, icase) == what))
715 {
716 ++position;
717 }
718 count = (unsigned)::boost::re_detail::distance(origin, position);
719 }
720 else
721 {
722 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
723 {
724 ++position;
725 ++count;
726 }
727 }
728
729 if(count < rep->min)
730 return false;
731
732 if(greedy)
733 {
734 if((rep->leading) && (count < rep->max))
735 restart = position;
736 // push backtrack info if available:
737 if(count - rep->min)
738 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
739 // jump to next state:
740 pstate = rep->alt.p;
741 return true;
742 }
743 else
744 {
745 // non-greedy, push state and return true if we can skip:
746 if(count < rep->max)
747 push_single_repeat(count, rep, position, saved_state_rep_char);
748 pstate = rep->alt.p;
749 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
750 }
751 #ifdef __BORLANDC__
752 #pragma option pop
753 #endif
754 #ifdef BOOST_MSVC
755 #pragma warning(pop)
756 #endif
757 }
758
759 template <class BidiIterator, class Allocator, class traits>
match_set_repeat()760 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
761 {
762 #ifdef BOOST_MSVC
763 #pragma warning(push)
764 #pragma warning(disable:4127)
765 #endif
766 #ifdef __BORLANDC__
767 #pragma option push -w-8008 -w-8066 -w-8004
768 #endif
769 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
770 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
771 std::size_t count = 0;
772 //
773 // start by working out how much we can skip:
774 //
775 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
776 std::size_t desired = greedy ? rep->max : rep->min;
777 if(::boost::is_random_access_iterator<BidiIterator>::value)
778 {
779 BidiIterator end = position;
780 // Move end forward by "desired", preferably without using distance or advance if we can
781 // as these can be slow for some iterator types.
782 std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::re_detail::distance(position, last);
783 if(desired >= len)
784 end = last;
785 else
786 std::advance(end, desired);
787 BidiIterator origin(position);
788 while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
789 {
790 ++position;
791 }
792 count = (unsigned)::boost::re_detail::distance(origin, position);
793 }
794 else
795 {
796 while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
797 {
798 ++position;
799 ++count;
800 }
801 }
802
803 if(count < rep->min)
804 return false;
805
806 if(greedy)
807 {
808 if((rep->leading) && (count < rep->max))
809 restart = position;
810 // push backtrack info if available:
811 if(count - rep->min)
812 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
813 // jump to next state:
814 pstate = rep->alt.p;
815 return true;
816 }
817 else
818 {
819 // non-greedy, push state and return true if we can skip:
820 if(count < rep->max)
821 push_single_repeat(count, rep, position, saved_state_rep_short_set);
822 pstate = rep->alt.p;
823 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
824 }
825 #ifdef __BORLANDC__
826 #pragma option pop
827 #endif
828 #ifdef BOOST_MSVC
829 #pragma warning(pop)
830 #endif
831 }
832
833 template <class BidiIterator, class Allocator, class traits>
match_long_set_repeat()834 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
835 {
836 #ifdef BOOST_MSVC
837 #pragma warning(push)
838 #pragma warning(disable:4127)
839 #endif
840 #ifdef __BORLANDC__
841 #pragma option push -w-8008 -w-8066 -w-8004
842 #endif
843 typedef typename traits::char_class_type m_type;
844 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
845 const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate->next.p);
846 std::size_t count = 0;
847 //
848 // start by working out how much we can skip:
849 //
850 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
851 std::size_t desired = greedy ? rep->max : rep->min;
852 if(::boost::is_random_access_iterator<BidiIterator>::value)
853 {
854 BidiIterator end = position;
855 // Move end forward by "desired", preferably without using distance or advance if we can
856 // as these can be slow for some iterator types.
857 std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::re_detail::distance(position, last);
858 if(desired >= len)
859 end = last;
860 else
861 std::advance(end, desired);
862 BidiIterator origin(position);
863 while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
864 {
865 ++position;
866 }
867 count = (unsigned)::boost::re_detail::distance(origin, position);
868 }
869 else
870 {
871 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
872 {
873 ++position;
874 ++count;
875 }
876 }
877
878 if(count < rep->min)
879 return false;
880
881 if(greedy)
882 {
883 if((rep->leading) && (count < rep->max))
884 restart = position;
885 // push backtrack info if available:
886 if(count - rep->min)
887 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
888 // jump to next state:
889 pstate = rep->alt.p;
890 return true;
891 }
892 else
893 {
894 // non-greedy, push state and return true if we can skip:
895 if(count < rep->max)
896 push_single_repeat(count, rep, position, saved_state_rep_long_set);
897 pstate = rep->alt.p;
898 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
899 }
900 #ifdef __BORLANDC__
901 #pragma option pop
902 #endif
903 #ifdef BOOST_MSVC
904 #pragma warning(pop)
905 #endif
906 }
907
908 template <class BidiIterator, class Allocator, class traits>
match_recursion()909 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
910 {
911 BOOST_ASSERT(pstate->type == syntax_element_recurse);
912 //
913 // Backup call stack:
914 //
915 push_recursion_pop();
916 //
917 // Set new call stack:
918 //
919 if(recursion_stack.capacity() == 0)
920 {
921 recursion_stack.reserve(50);
922 }
923 recursion_stack.push_back(recursion_info<results_type>());
924 recursion_stack.back().preturn_address = pstate->next.p;
925 recursion_stack.back().results = *m_presult;
926 if(static_cast<const re_recurse*>(pstate)->state_id > 0)
927 {
928 push_repeater_count(static_cast<const re_recurse*>(pstate)->state_id, &next_count);
929 }
930 pstate = static_cast<const re_jump*>(pstate)->alt.p;
931 recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
932
933 return true;
934 }
935
936 template <class BidiIterator, class Allocator, class traits>
match_endmark()937 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
938 {
939 int index = static_cast<const re_brace*>(pstate)->index;
940 icase = static_cast<const re_brace*>(pstate)->icase;
941 if(index > 0)
942 {
943 if((m_match_flags & match_nosubs) == 0)
944 {
945 m_presult->set_second(position, index);
946 }
947 if(!recursion_stack.empty())
948 {
949 if(index == recursion_stack.back().idx)
950 {
951 pstate = recursion_stack.back().preturn_address;
952 *m_presult = recursion_stack.back().results;
953 push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, &recursion_stack.back().results);
954 recursion_stack.pop_back();
955 }
956 }
957 }
958 else if((index < 0) && (index != -4))
959 {
960 // matched forward lookahead:
961 pstate = 0;
962 return true;
963 }
964 pstate = pstate->next.p;
965 return true;
966 }
967
968 template <class BidiIterator, class Allocator, class traits>
match_match()969 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
970 {
971 if(!recursion_stack.empty())
972 {
973 BOOST_ASSERT(0 == recursion_stack.back().idx);
974 pstate = recursion_stack.back().preturn_address;
975 *m_presult = recursion_stack.back().results;
976 push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, &recursion_stack.back().results);
977 recursion_stack.pop_back();
978 return true;
979 }
980 if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
981 return false;
982 if((m_match_flags & match_all) && (position != last))
983 return false;
984 if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
985 return false;
986 m_presult->set_second(position);
987 pstate = 0;
988 m_has_found_match = true;
989 if((m_match_flags & match_posix) == match_posix)
990 {
991 m_result.maybe_assign(*m_presult);
992 if((m_match_flags & match_any) == 0)
993 return false;
994 }
995 #ifdef BOOST_REGEX_MATCH_EXTRA
996 if(match_extra & m_match_flags)
997 {
998 for(unsigned i = 0; i < m_presult->size(); ++i)
999 if((*m_presult)[i].matched)
1000 ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
1001 }
1002 #endif
1003 return true;
1004 }
1005
1006 /****************************************************************************
1007
1008 Unwind and associated proceedures follow, these perform what normal stack
1009 unwinding does in the recursive implementation.
1010
1011 ****************************************************************************/
1012
1013 template <class BidiIterator, class Allocator, class traits>
unwind(bool have_match)1014 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
1015 {
1016 static unwind_proc_type const s_unwind_table[18] =
1017 {
1018 &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
1019 &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
1020 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
1021 &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
1022 &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
1023 &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
1024 &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
1025 &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
1026 &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
1027 &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
1028 &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
1029 &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
1030 &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
1031 &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
1032 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion,
1033 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop,
1034 };
1035
1036 m_recursive_result = have_match;
1037 unwind_proc_type unwinder;
1038 bool cont;
1039 //
1040 // keep unwinding our stack until we have something to do:
1041 //
1042 do
1043 {
1044 unwinder = s_unwind_table[m_backup_state->state_id];
1045 cont = (this->*unwinder)(m_recursive_result);
1046 }while(cont);
1047 //
1048 // return true if we have more states to try:
1049 //
1050 return pstate ? true : false;
1051 }
1052
1053 template <class BidiIterator, class Allocator, class traits>
unwind_end(bool)1054 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
1055 {
1056 pstate = 0; // nothing left to search
1057 return false; // end of stack nothing more to search
1058 }
1059
1060 template <class BidiIterator, class Allocator, class traits>
unwind_paren(bool have_match)1061 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
1062 {
1063 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
1064 // restore previous values if no match was found:
1065 if(have_match == false)
1066 {
1067 m_presult->set_first(pmp->sub.first, pmp->index, pmp->index == 0);
1068 m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched, pmp->index == 0);
1069 }
1070 #ifdef BOOST_REGEX_MATCH_EXTRA
1071 //
1072 // we have a match, push the capture information onto the stack:
1073 //
1074 else if(pmp->sub.matched && (match_extra & m_match_flags))
1075 ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
1076 #endif
1077 // unwind stack:
1078 m_backup_state = pmp+1;
1079 boost::re_detail::inplace_destroy(pmp);
1080 return true; // keep looking
1081 }
1082
1083 template <class BidiIterator, class Allocator, class traits>
unwind_recursion_stopper(bool)1084 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
1085 {
1086 boost::re_detail::inplace_destroy(m_backup_state++);
1087 pstate = 0; // nothing left to search
1088 return false; // end of stack nothing more to search
1089 }
1090
1091 template <class BidiIterator, class Allocator, class traits>
unwind_assertion(bool r)1092 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
1093 {
1094 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
1095 pstate = pmp->pstate;
1096 position = pmp->position;
1097 bool result = (r == pmp->positive);
1098 m_recursive_result = pmp->positive ? r : !r;
1099 boost::re_detail::inplace_destroy(pmp++);
1100 m_backup_state = pmp;
1101 return !result; // return false if the assertion was matched to stop search.
1102 }
1103
1104 template <class BidiIterator, class Allocator, class traits>
unwind_alt(bool r)1105 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
1106 {
1107 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1108 if(!r)
1109 {
1110 pstate = pmp->pstate;
1111 position = pmp->position;
1112 }
1113 boost::re_detail::inplace_destroy(pmp++);
1114 m_backup_state = pmp;
1115 return r;
1116 }
1117
1118 template <class BidiIterator, class Allocator, class traits>
unwind_repeater_counter(bool)1119 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
1120 {
1121 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
1122 boost::re_detail::inplace_destroy(pmp++);
1123 m_backup_state = pmp;
1124 return true; // keep looking
1125 }
1126
1127 template <class BidiIterator, class Allocator, class traits>
unwind_extra_block(bool)1128 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
1129 {
1130 saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
1131 void* condemmed = m_stack_base;
1132 m_stack_base = pmp->base;
1133 m_backup_state = pmp->end;
1134 boost::re_detail::inplace_destroy(pmp);
1135 put_mem_block(condemmed);
1136 return true; // keep looking
1137 }
1138
1139 template <class BidiIterator, class Allocator, class traits>
destroy_single_repeat()1140 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
1141 {
1142 saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1143 boost::re_detail::inplace_destroy(p++);
1144 m_backup_state = p;
1145 }
1146
1147 template <class BidiIterator, class Allocator, class traits>
unwind_greedy_single_repeat(bool r)1148 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
1149 {
1150 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1151
1152 // if we have a match, just discard this state:
1153 if(r)
1154 {
1155 destroy_single_repeat();
1156 return true;
1157 }
1158
1159 const re_repeat* rep = pmp->rep;
1160 std::size_t count = pmp->count;
1161 BOOST_ASSERT(rep->next.p != 0);
1162 BOOST_ASSERT(rep->alt.p != 0);
1163
1164 count -= rep->min;
1165
1166 if((m_match_flags & match_partial) && (position == last))
1167 m_has_partial_match = true;
1168
1169 BOOST_ASSERT(count);
1170 position = pmp->last_position;
1171
1172 // backtrack till we can skip out:
1173 do
1174 {
1175 --position;
1176 --count;
1177 ++state_count;
1178 }while(count && !can_start(*position, rep->_map, mask_skip));
1179
1180 // if we've hit base, destroy this state:
1181 if(count == 0)
1182 {
1183 destroy_single_repeat();
1184 if(!can_start(*position, rep->_map, mask_skip))
1185 return true;
1186 }
1187 else
1188 {
1189 pmp->count = count + rep->min;
1190 pmp->last_position = position;
1191 }
1192 pstate = rep->alt.p;
1193 return false;
1194 }
1195
1196 template <class BidiIterator, class Allocator, class traits>
unwind_slow_dot_repeat(bool r)1197 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1198 {
1199 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1200
1201 // if we have a match, just discard this state:
1202 if(r)
1203 {
1204 destroy_single_repeat();
1205 return true;
1206 }
1207
1208 const re_repeat* rep = pmp->rep;
1209 std::size_t count = pmp->count;
1210 BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1211 BOOST_ASSERT(rep->next.p != 0);
1212 BOOST_ASSERT(rep->alt.p != 0);
1213 BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1214
1215 BOOST_ASSERT(count < rep->max);
1216 pstate = rep->next.p;
1217 position = pmp->last_position;
1218
1219 if(position != last)
1220 {
1221 // wind forward until we can skip out of the repeat:
1222 do
1223 {
1224 if(!match_wild())
1225 {
1226 // failed repeat match, discard this state and look for another:
1227 destroy_single_repeat();
1228 return true;
1229 }
1230 ++count;
1231 ++state_count;
1232 pstate = rep->next.p;
1233 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1234 }
1235 if(position == last)
1236 {
1237 // can't repeat any more, remove the pushed state:
1238 destroy_single_repeat();
1239 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1240 m_has_partial_match = true;
1241 if(0 == (rep->can_be_null & mask_skip))
1242 return true;
1243 }
1244 else if(count == rep->max)
1245 {
1246 // can't repeat any more, remove the pushed state:
1247 destroy_single_repeat();
1248 if(!can_start(*position, rep->_map, mask_skip))
1249 return true;
1250 }
1251 else
1252 {
1253 pmp->count = count;
1254 pmp->last_position = position;
1255 }
1256 pstate = rep->alt.p;
1257 return false;
1258 }
1259
1260 template <class BidiIterator, class Allocator, class traits>
unwind_fast_dot_repeat(bool r)1261 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1262 {
1263 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1264
1265 // if we have a match, just discard this state:
1266 if(r)
1267 {
1268 destroy_single_repeat();
1269 return true;
1270 }
1271
1272 const re_repeat* rep = pmp->rep;
1273 std::size_t count = pmp->count;
1274
1275 BOOST_ASSERT(count < rep->max);
1276 position = pmp->last_position;
1277 if(position != last)
1278 {
1279
1280 // wind forward until we can skip out of the repeat:
1281 do
1282 {
1283 ++position;
1284 ++count;
1285 ++state_count;
1286 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1287 }
1288
1289 // remember where we got to if this is a leading repeat:
1290 if((rep->leading) && (count < rep->max))
1291 restart = position;
1292 if(position == last)
1293 {
1294 // can't repeat any more, remove the pushed state:
1295 destroy_single_repeat();
1296 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1297 m_has_partial_match = true;
1298 if(0 == (rep->can_be_null & mask_skip))
1299 return true;
1300 }
1301 else if(count == rep->max)
1302 {
1303 // can't repeat any more, remove the pushed state:
1304 destroy_single_repeat();
1305 if(!can_start(*position, rep->_map, mask_skip))
1306 return true;
1307 }
1308 else
1309 {
1310 pmp->count = count;
1311 pmp->last_position = position;
1312 }
1313 pstate = rep->alt.p;
1314 return false;
1315 }
1316
1317 template <class BidiIterator, class Allocator, class traits>
unwind_char_repeat(bool r)1318 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1319 {
1320 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1321
1322 // if we have a match, just discard this state:
1323 if(r)
1324 {
1325 destroy_single_repeat();
1326 return true;
1327 }
1328
1329 const re_repeat* rep = pmp->rep;
1330 std::size_t count = pmp->count;
1331 pstate = rep->next.p;
1332 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1333 position = pmp->last_position;
1334
1335 BOOST_ASSERT(rep->type == syntax_element_char_rep);
1336 BOOST_ASSERT(rep->next.p != 0);
1337 BOOST_ASSERT(rep->alt.p != 0);
1338 BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1339 BOOST_ASSERT(count < rep->max);
1340
1341 if(position != last)
1342 {
1343 // wind forward until we can skip out of the repeat:
1344 do
1345 {
1346 if(traits_inst.translate(*position, icase) != what)
1347 {
1348 // failed repeat match, discard this state and look for another:
1349 destroy_single_repeat();
1350 return true;
1351 }
1352 ++count;
1353 ++ position;
1354 ++state_count;
1355 pstate = rep->next.p;
1356 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1357 }
1358 // remember where we got to if this is a leading repeat:
1359 if((rep->leading) && (count < rep->max))
1360 restart = position;
1361 if(position == last)
1362 {
1363 // can't repeat any more, remove the pushed state:
1364 destroy_single_repeat();
1365 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1366 m_has_partial_match = true;
1367 if(0 == (rep->can_be_null & mask_skip))
1368 return true;
1369 }
1370 else if(count == rep->max)
1371 {
1372 // can't repeat any more, remove the pushed state:
1373 destroy_single_repeat();
1374 if(!can_start(*position, rep->_map, mask_skip))
1375 return true;
1376 }
1377 else
1378 {
1379 pmp->count = count;
1380 pmp->last_position = position;
1381 }
1382 pstate = rep->alt.p;
1383 return false;
1384 }
1385
1386 template <class BidiIterator, class Allocator, class traits>
unwind_short_set_repeat(bool r)1387 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1388 {
1389 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1390
1391 // if we have a match, just discard this state:
1392 if(r)
1393 {
1394 destroy_single_repeat();
1395 return true;
1396 }
1397
1398 const re_repeat* rep = pmp->rep;
1399 std::size_t count = pmp->count;
1400 pstate = rep->next.p;
1401 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1402 position = pmp->last_position;
1403
1404 BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1405 BOOST_ASSERT(rep->next.p != 0);
1406 BOOST_ASSERT(rep->alt.p != 0);
1407 BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1408 BOOST_ASSERT(count < rep->max);
1409
1410 if(position != last)
1411 {
1412 // wind forward until we can skip out of the repeat:
1413 do
1414 {
1415 if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1416 {
1417 // failed repeat match, discard this state and look for another:
1418 destroy_single_repeat();
1419 return true;
1420 }
1421 ++count;
1422 ++ position;
1423 ++state_count;
1424 pstate = rep->next.p;
1425 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1426 }
1427 // remember where we got to if this is a leading repeat:
1428 if((rep->leading) && (count < rep->max))
1429 restart = position;
1430 if(position == last)
1431 {
1432 // can't repeat any more, remove the pushed state:
1433 destroy_single_repeat();
1434 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1435 m_has_partial_match = true;
1436 if(0 == (rep->can_be_null & mask_skip))
1437 return true;
1438 }
1439 else if(count == rep->max)
1440 {
1441 // can't repeat any more, remove the pushed state:
1442 destroy_single_repeat();
1443 if(!can_start(*position, rep->_map, mask_skip))
1444 return true;
1445 }
1446 else
1447 {
1448 pmp->count = count;
1449 pmp->last_position = position;
1450 }
1451 pstate = rep->alt.p;
1452 return false;
1453 }
1454
1455 template <class BidiIterator, class Allocator, class traits>
unwind_long_set_repeat(bool r)1456 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1457 {
1458 typedef typename traits::char_class_type m_type;
1459 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1460
1461 // if we have a match, just discard this state:
1462 if(r)
1463 {
1464 destroy_single_repeat();
1465 return true;
1466 }
1467
1468 const re_repeat* rep = pmp->rep;
1469 std::size_t count = pmp->count;
1470 pstate = rep->next.p;
1471 const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate);
1472 position = pmp->last_position;
1473
1474 BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1475 BOOST_ASSERT(rep->next.p != 0);
1476 BOOST_ASSERT(rep->alt.p != 0);
1477 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1478 BOOST_ASSERT(count < rep->max);
1479
1480 if(position != last)
1481 {
1482 // wind forward until we can skip out of the repeat:
1483 do
1484 {
1485 if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1486 {
1487 // failed repeat match, discard this state and look for another:
1488 destroy_single_repeat();
1489 return true;
1490 }
1491 ++position;
1492 ++count;
1493 ++state_count;
1494 pstate = rep->next.p;
1495 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1496 }
1497 // remember where we got to if this is a leading repeat:
1498 if((rep->leading) && (count < rep->max))
1499 restart = position;
1500 if(position == last)
1501 {
1502 // can't repeat any more, remove the pushed state:
1503 destroy_single_repeat();
1504 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1505 m_has_partial_match = true;
1506 if(0 == (rep->can_be_null & mask_skip))
1507 return true;
1508 }
1509 else if(count == rep->max)
1510 {
1511 // can't repeat any more, remove the pushed state:
1512 destroy_single_repeat();
1513 if(!can_start(*position, rep->_map, mask_skip))
1514 return true;
1515 }
1516 else
1517 {
1518 pmp->count = count;
1519 pmp->last_position = position;
1520 }
1521 pstate = rep->alt.p;
1522 return false;
1523 }
1524
1525 template <class BidiIterator, class Allocator, class traits>
unwind_non_greedy_repeat(bool r)1526 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1527 {
1528 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1529 if(!r)
1530 {
1531 position = pmp->position;
1532 pstate = pmp->pstate;
1533 ++(*next_count);
1534 }
1535 boost::re_detail::inplace_destroy(pmp++);
1536 m_backup_state = pmp;
1537 return r;
1538 }
1539
1540 template <class BidiIterator, class Allocator, class traits>
unwind_recursion(bool r)1541 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion(bool r)
1542 {
1543 saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
1544 if(!r)
1545 {
1546 recursion_stack.push_back(recursion_info<results_type>());
1547 recursion_stack.back().idx = pmp->recursion_id;
1548 recursion_stack.back().preturn_address = pmp->preturn_address;
1549 recursion_stack.back().results = pmp->results;
1550 }
1551 boost::re_detail::inplace_destroy(pmp++);
1552 m_backup_state = pmp;
1553 return true;
1554 }
1555
1556 template <class BidiIterator, class Allocator, class traits>
unwind_recursion_pop(bool r)1557 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop(bool r)
1558 {
1559 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1560 if(!r)
1561 {
1562 recursion_stack.pop_back();
1563 }
1564 boost::re_detail::inplace_destroy(pmp++);
1565 m_backup_state = pmp;
1566 return true;
1567 }
1568
1569 template <class BidiIterator, class Allocator, class traits>
push_recursion_pop()1570 void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_pop()
1571 {
1572 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1573 --pmp;
1574 if(pmp < m_stack_base)
1575 {
1576 extend_stack();
1577 pmp = static_cast<saved_state*>(m_backup_state);
1578 --pmp;
1579 }
1580 (void) new (pmp)saved_state(15);
1581 m_backup_state = pmp;
1582 }
1583 /*
1584 template <class BidiIterator, class Allocator, class traits>
1585 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_pop(bool r)
1586 {
1587 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1588 if(!r)
1589 {
1590 --parenthesis_stack_position;
1591 }
1592 boost::re_detail::inplace_destroy(pmp++);
1593 m_backup_state = pmp;
1594 return true;
1595 }
1596
1597 template <class BidiIterator, class Allocator, class traits>
1598 void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_pop()
1599 {
1600 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1601 --pmp;
1602 if(pmp < m_stack_base)
1603 {
1604 extend_stack();
1605 pmp = static_cast<saved_state*>(m_backup_state);
1606 --pmp;
1607 }
1608 (void) new (pmp)saved_state(16);
1609 m_backup_state = pmp;
1610 }
1611
1612 template <class BidiIterator, class Allocator, class traits>
1613 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_push(bool r)
1614 {
1615 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1616 if(!r)
1617 {
1618 parenthesis_stack[parenthesis_stack_position++] = pmp->position;
1619 }
1620 boost::re_detail::inplace_destroy(pmp++);
1621 m_backup_state = pmp;
1622 return true;
1623 }
1624
1625 template <class BidiIterator, class Allocator, class traits>
1626 inline void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_push(BidiIterator p)
1627 {
1628 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1629 --pmp;
1630 if(pmp < m_stack_base)
1631 {
1632 extend_stack();
1633 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1634 --pmp;
1635 }
1636 (void) new (pmp)saved_position<BidiIterator>(0, p, 17);
1637 m_backup_state = pmp;
1638 }
1639 */
1640 } // namespace re_detail
1641 } // namespace boost
1642
1643 #ifdef BOOST_MSVC
1644 # pragma warning(pop)
1645 #endif
1646
1647 #ifdef BOOST_MSVC
1648 #pragma warning(push)
1649 #pragma warning(disable: 4103)
1650 #endif
1651 #ifdef BOOST_HAS_ABI_HEADERS
1652 # include BOOST_ABI_SUFFIX
1653 #endif
1654 #ifdef BOOST_MSVC
1655 #pragma warning(pop)
1656 #endif
1657
1658 #endif
1659
1660
1661