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)
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.
20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP
21 #define BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP
27 #pragma warning(disable: 4103)
29 #ifdef BOOST_HAS_ABI_HEADERS
30 # include BOOST_ABI_PREFIX
36 # pragma warning(push)
37 # pragma warning(disable: 4800)
44 inline void inplace_destroy(T* p)
46 (void)p; // warning suppression
53 unsigned int state_id;
54 // this padding ensures correct alignment on 64-bit platforms:
56 std::ptrdiff_t padding2;
59 saved_state(unsigned i) : state_id(i) {}
62 template <class BidiIterator>
63 struct saved_matched_paren : public saved_state
66 sub_match<BidiIterator> sub;
67 saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){};
70 template <class BidiIterator>
71 struct saved_position : public saved_state
73 const re_syntax_base* pstate;
74 BidiIterator position;
75 saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){};
78 template <class BidiIterator>
79 struct saved_assertion : public saved_position<BidiIterator>
82 saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
83 : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){};
86 template <class BidiIterator>
87 struct saved_repeater : public saved_state
89 repeater_count<BidiIterator> count;
90 saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start)
91 : saved_state(saved_state_repeater_count), count(i,s,start){}
94 struct saved_extra_block : public saved_state
96 saved_state *base, *end;
97 saved_extra_block(saved_state* b, saved_state* e)
98 : saved_state(saved_state_extra_block), base(b), end(e) {}
101 struct save_state_init
104 save_state_init(saved_state** base, saved_state** end)
107 *base = static_cast<saved_state*>(get_mem_block());
108 *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
110 (void) new (*end)saved_state(0);
111 BOOST_ASSERT(*end > *base);
115 put_mem_block(*stack);
120 template <class BidiIterator>
121 struct saved_single_repeat : public saved_state
124 const re_repeat* rep;
125 BidiIterator last_position;
126 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){}
130 template <class BidiIterator, class Allocator, class traits>
131 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
133 static matcher_proc_type const s_match_vtable[29] =
135 (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
136 &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
137 &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
138 &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
139 &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
140 &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
141 &perl_matcher<BidiIterator, Allocator, traits>::match_match,
142 &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
143 &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
144 &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
145 &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
146 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
147 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
148 &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
149 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
150 &perl_matcher<BidiIterator, Allocator, traits>::match_set,
151 &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
152 &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
153 &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
154 &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
155 &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
156 &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
157 (::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),
158 &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
159 &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
160 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
161 &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
162 &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
163 &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
166 push_recursion_stopper();
170 matcher_proc_type proc = s_match_vtable[pstate->type];
174 if(state_count > max_state_count)
175 raise_error(traits_inst, regex_constants::error_space);
176 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
177 m_has_partial_match = true;
178 bool successful_unwind = unwind(false);
179 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
180 m_has_partial_match = true;
181 if(false == successful_unwind)
182 return m_recursive_result;
185 }while(unwind(true));
186 return m_recursive_result;
189 template <class BidiIterator, class Allocator, class traits>
190 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
195 saved_state* stack_base;
196 saved_state* backup_state;
197 stack_base = static_cast<saved_state*>(get_mem_block());
198 backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
199 saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
201 (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
202 m_stack_base = stack_base;
203 m_backup_state = block;
206 raise_error(traits_inst, regex_constants::error_size);
209 template <class BidiIterator, class Allocator, class traits>
210 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
213 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
215 if(pmp < m_stack_base)
218 pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
221 (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
222 m_backup_state = pmp;
225 template <class BidiIterator, class Allocator, class traits>
226 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
228 saved_state* pmp = m_backup_state;
230 if(pmp < m_stack_base)
233 pmp = m_backup_state;
236 (void) new (pmp)saved_state(saved_type_recurse);
237 m_backup_state = pmp;
240 template <class BidiIterator, class Allocator, class traits>
241 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
243 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
245 if(pmp < m_stack_base)
248 pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
251 (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
252 m_backup_state = pmp;
255 template <class BidiIterator, class Allocator, class traits>
256 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
258 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
260 if(pmp < m_stack_base)
263 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
266 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
267 m_backup_state = pmp;
270 template <class BidiIterator, class Allocator, class traits>
271 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
273 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
275 if(pmp < m_stack_base)
278 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
281 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
282 m_backup_state = pmp;
285 template <class BidiIterator, class Allocator, class traits>
286 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
288 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
290 if(pmp < m_stack_base)
293 pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
296 (void) new (pmp)saved_repeater<BidiIterator>(i, s, position);
297 m_backup_state = pmp;
300 template <class BidiIterator, class Allocator, class traits>
301 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
303 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
305 if(pmp < m_stack_base)
308 pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
311 (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
312 m_backup_state = pmp;
315 template <class BidiIterator, class Allocator, class traits>
316 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
318 int index = static_cast<const re_brace*>(pstate)->index;
322 pstate = pstate->next.p;
327 // forward lookahead assert:
328 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
329 pstate = pstate->next.p->next.p;
330 push_assertion(next_pstate, index == -1);
335 // independent sub-expression, currently this is always recursive:
336 bool old_independent = m_independent;
337 m_independent = true;
338 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
339 pstate = pstate->next.p->next.p;
340 bool r = match_all_states();
341 pstate = next_pstate;
342 m_independent = old_independent;
343 #ifdef BOOST_REGEX_MATCH_EXTRA
344 if(r && (m_match_flags & match_extra))
347 // our captures have been stored in *m_presult
348 // we need to unpack them, and insert them
349 // back in the right order when we unwind the stack:
351 match_results<BidiIterator, Allocator> temp_match(*m_presult);
353 for(i = 0; i < temp_match.size(); ++i)
354 (*m_presult)[i].get_captures().clear();
355 // match everything else:
356 r = match_all_states();
357 // now place the stored captures back:
358 for(i = 0; i < temp_match.size(); ++i)
360 typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
361 seq& s1 = (*m_presult)[i].get_captures();
362 const seq& s2 = temp_match[i].captures();
374 // conditional expression:
375 const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
376 BOOST_ASSERT(alt->type == syntax_element_alt);
377 pstate = alt->next.p;
378 if(pstate->type == syntax_element_assert_backref)
380 if(!match_assert_backref())
386 // zero width assertion, have to match this recursively:
387 BOOST_ASSERT(pstate->type == syntax_element_startmark);
388 bool negated = static_cast<const re_brace*>(pstate)->index == -2;
389 BidiIterator saved_position = position;
390 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
391 pstate = pstate->next.p->next.p;
392 bool r = match_all_states();
393 position = saved_position;
397 pstate = next_pstate;
405 BOOST_ASSERT(index > 0);
406 if((m_match_flags & match_nosubs) == 0)
408 push_matched_paren(index, (*m_presult)[index]);
409 m_presult->set_first(position, index);
411 pstate = pstate->next.p;
418 template <class BidiIterator, class Allocator, class traits>
419 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
421 bool take_first, take_second;
422 const re_alt* jmp = static_cast<const re_alt*>(pstate);
424 // find out which of these two alternatives we need to take:
427 take_first = jmp->can_be_null & mask_take;
428 take_second = jmp->can_be_null & mask_skip;
432 take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
433 take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
438 // we can take the first alternative,
439 // see if we need to push next alternative:
442 push_alt(jmp->alt.p);
444 pstate = pstate->next.p;
452 return false; // neither option is possible
455 template <class BidiIterator, class Allocator, class traits>
456 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
459 #pragma warning(push)
460 #pragma warning(disable:4127 4244)
463 #pragma option push -w-8008 -w-8066 -w-8004
465 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
467 // find out which of these two alternatives we need to take:
468 bool take_first, take_second;
471 take_first = rep->can_be_null & mask_take;
472 take_second = rep->can_be_null & mask_skip;
476 take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
477 take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
480 if((m_backup_state->state_id != saved_state_repeater_count)
481 || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
482 || (next_count->get_id() != rep->state_id))
484 // we're moving to a different repeat from the last
485 // one, so set up a counter object:
486 push_repeater_count(rep->state_id, &next_count);
489 // If we've had at least one repeat already, and the last one
490 // matched the NULL string then set the repeat count to
493 next_count->check_null_repeat(position, rep->max);
495 if(next_count->get_count() < rep->min)
497 // we must take the repeat:
500 // increase the counter:
502 pstate = rep->next.p;
508 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
511 // try and take the repeat if we can:
512 if((next_count->get_count() < rep->max) && take_first)
516 // store position in case we fail:
517 push_alt(rep->alt.p);
519 // increase the counter:
521 pstate = rep->next.p;
529 return false; // can't take anything, fail...
533 // try and skip the repeat if we can:
536 if((next_count->get_count() < rep->max) && take_first)
538 // store position in case we fail:
539 push_non_greedy_repeat(rep->next.p);
544 if((next_count->get_count() < rep->max) && take_first)
546 // increase the counter:
548 pstate = rep->next.p;
561 template <class BidiIterator, class Allocator, class traits>
562 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
565 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
566 re_syntax_base* psingle = rep->next.p;
567 // match compulsary repeats first:
568 while(count < rep->min)
575 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
578 // repeat for as long as we can:
579 while(count < rep->max)
586 // remember where we got to if this is a leading repeat:
587 if((rep->leading) && (count < rep->max))
589 // push backtrack info if available:
591 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
592 // jump to next state:
598 // non-greedy, push state and return true if we can skip:
600 push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
602 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
606 template <class BidiIterator, class Allocator, class traits>
607 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
609 if(m_match_flags & match_not_dot_null)
610 return match_dot_repeat_slow();
611 if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
612 return match_dot_repeat_slow();
614 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
615 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
616 unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::re_detail::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));
620 return false; // not enough text left to match
622 std::advance(position, count);
626 if((rep->leading) && (count < rep->max))
628 // push backtrack info if available:
630 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
631 // jump to next state:
637 // non-greedy, push state and return true if we can skip:
639 push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
641 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
645 template <class BidiIterator, class Allocator, class traits>
646 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
649 #pragma warning(push)
650 #pragma warning(disable:4127)
653 #pragma option push -w-8008 -w-8066 -w-8004
655 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
656 BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
657 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
658 std::size_t count = 0;
660 // start by working out how much we can skip:
662 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
663 std::size_t desired = greedy ? rep->max : rep->min;
664 if(::boost::is_random_access_iterator<BidiIterator>::value)
666 BidiIterator end = position;
667 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
668 BidiIterator origin(position);
669 while((position != end) && (traits_inst.translate(*position, icase) == what))
673 count = (unsigned)::boost::re_detail::distance(origin, position);
677 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
689 if((rep->leading) && (count < rep->max))
691 // push backtrack info if available:
693 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
694 // jump to next state:
700 // non-greedy, push state and return true if we can skip:
702 push_single_repeat(count, rep, position, saved_state_rep_char);
704 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
714 template <class BidiIterator, class Allocator, class traits>
715 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
718 #pragma warning(push)
719 #pragma warning(disable:4127)
722 #pragma option push -w-8008 -w-8066 -w-8004
724 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
725 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
726 std::size_t count = 0;
728 // start by working out how much we can skip:
730 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
731 std::size_t desired = greedy ? rep->max : rep->min;
732 if(::boost::is_random_access_iterator<BidiIterator>::value)
734 BidiIterator end = position;
735 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
736 BidiIterator origin(position);
737 while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
741 count = (unsigned)::boost::re_detail::distance(origin, position);
745 while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
757 if((rep->leading) && (count < rep->max))
759 // push backtrack info if available:
761 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
762 // jump to next state:
768 // non-greedy, push state and return true if we can skip:
770 push_single_repeat(count, rep, position, saved_state_rep_short_set);
772 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
782 template <class BidiIterator, class Allocator, class traits>
783 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
786 #pragma warning(push)
787 #pragma warning(disable:4127)
790 #pragma option push -w-8008 -w-8066 -w-8004
792 typedef typename traits::char_class_type mask_type;
793 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
794 const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate->next.p);
795 std::size_t count = 0;
797 // start by working out how much we can skip:
799 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
800 std::size_t desired = greedy ? rep->max : rep->min;
801 if(::boost::is_random_access_iterator<BidiIterator>::value)
803 BidiIterator end = position;
804 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
805 BidiIterator origin(position);
806 while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
810 count = (unsigned)::boost::re_detail::distance(origin, position);
814 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
826 if((rep->leading) && (count < rep->max))
828 // push backtrack info if available:
830 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
831 // jump to next state:
837 // non-greedy, push state and return true if we can skip:
839 push_single_repeat(count, rep, position, saved_state_rep_long_set);
841 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
851 /****************************************************************************
853 Unwind and associated proceedures follow, these perform what normal stack
854 unwinding does in the recursive implementation.
856 ****************************************************************************/
858 template <class BidiIterator, class Allocator, class traits>
859 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
861 static unwind_proc_type const s_unwind_table[14] =
863 &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
864 &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
865 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
866 &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
867 &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
868 &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
869 &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
870 &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
871 &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
872 &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
873 &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
874 &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
875 &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
876 &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
879 m_recursive_result = have_match;
880 unwind_proc_type unwinder;
883 // keep unwinding our stack until we have something to do:
887 unwinder = s_unwind_table[m_backup_state->state_id];
888 cont = (this->*unwinder)(m_recursive_result);
891 // return true if we have more states to try:
893 return pstate ? true : false;
896 template <class BidiIterator, class Allocator, class traits>
897 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
899 pstate = 0; // nothing left to search
900 return false; // end of stack nothing more to search
903 template <class BidiIterator, class Allocator, class traits>
904 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
906 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
907 // restore previous values if no match was found:
908 if(have_match == false)
910 m_presult->set_first(pmp->sub.first, pmp->index);
911 m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched);
913 #ifdef BOOST_REGEX_MATCH_EXTRA
915 // we have a match, push the capture information onto the stack:
917 else if(pmp->sub.matched && (match_extra & m_match_flags))
918 ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
921 m_backup_state = pmp+1;
922 boost::re_detail::inplace_destroy(pmp);
923 return true; // keep looking
926 template <class BidiIterator, class Allocator, class traits>
927 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
929 boost::re_detail::inplace_destroy(m_backup_state++);
930 pstate = 0; // nothing left to search
931 return false; // end of stack nothing more to search
934 template <class BidiIterator, class Allocator, class traits>
935 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
937 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
938 pstate = pmp->pstate;
939 position = pmp->position;
940 bool result = (r == pmp->positive);
941 m_recursive_result = pmp->positive ? r : !r;
942 boost::re_detail::inplace_destroy(pmp++);
943 m_backup_state = pmp;
944 return !result; // return false if the assertion was matched to stop search.
947 template <class BidiIterator, class Allocator, class traits>
948 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
950 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
953 pstate = pmp->pstate;
954 position = pmp->position;
956 boost::re_detail::inplace_destroy(pmp++);
957 m_backup_state = pmp;
961 template <class BidiIterator, class Allocator, class traits>
962 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
964 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
965 boost::re_detail::inplace_destroy(pmp++);
966 m_backup_state = pmp;
967 return true; // keep looking
970 template <class BidiIterator, class Allocator, class traits>
971 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
973 saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
974 void* condemmed = m_stack_base;
975 m_stack_base = pmp->base;
976 m_backup_state = pmp->end;
977 boost::re_detail::inplace_destroy(pmp);
978 put_mem_block(condemmed);
979 return true; // keep looking
982 template <class BidiIterator, class Allocator, class traits>
983 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
985 saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
986 boost::re_detail::inplace_destroy(p++);
990 template <class BidiIterator, class Allocator, class traits>
991 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
993 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
995 // if we have a match, just discard this state:
998 destroy_single_repeat();
1002 const re_repeat* rep = pmp->rep;
1003 std::size_t count = pmp->count;
1004 BOOST_ASSERT(rep->next.p != 0);
1005 BOOST_ASSERT(rep->alt.p != 0);
1009 if((m_match_flags & match_partial) && (position == last))
1010 m_has_partial_match = true;
1012 BOOST_ASSERT(count);
1013 position = pmp->last_position;
1015 // backtrack till we can skip out:
1021 }while(count && !can_start(*position, rep->_map, mask_skip));
1023 // if we've hit base, destroy this state:
1026 destroy_single_repeat();
1027 if(!can_start(*position, rep->_map, mask_skip))
1032 pmp->count = count + rep->min;
1033 pmp->last_position = position;
1035 pstate = rep->alt.p;
1039 template <class BidiIterator, class Allocator, class traits>
1040 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1042 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1044 // if we have a match, just discard this state:
1047 destroy_single_repeat();
1051 const re_repeat* rep = pmp->rep;
1052 std::size_t count = pmp->count;
1053 BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1054 BOOST_ASSERT(rep->next.p != 0);
1055 BOOST_ASSERT(rep->alt.p != 0);
1056 BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1058 BOOST_ASSERT(count < rep->max);
1059 pstate = rep->next.p;
1060 position = pmp->last_position;
1062 if(position != last)
1064 // wind forward until we can skip out of the repeat:
1069 // failed repeat match, discard this state and look for another:
1070 destroy_single_repeat();
1075 pstate = rep->next.p;
1076 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1078 if(position == last)
1080 // can't repeat any more, remove the pushed state:
1081 destroy_single_repeat();
1082 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1083 m_has_partial_match = true;
1084 if(0 == (rep->can_be_null & mask_skip))
1087 else if(count == rep->max)
1089 // can't repeat any more, remove the pushed state:
1090 destroy_single_repeat();
1091 if(!can_start(*position, rep->_map, mask_skip))
1097 pmp->last_position = position;
1099 pstate = rep->alt.p;
1103 template <class BidiIterator, class Allocator, class traits>
1104 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1106 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1108 // if we have a match, just discard this state:
1111 destroy_single_repeat();
1115 const re_repeat* rep = pmp->rep;
1116 std::size_t count = pmp->count;
1118 BOOST_ASSERT(count < rep->max);
1119 position = pmp->last_position;
1120 if(position != last)
1123 // wind forward until we can skip out of the repeat:
1129 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1132 if(position == last)
1134 // can't repeat any more, remove the pushed state:
1135 destroy_single_repeat();
1136 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1137 m_has_partial_match = true;
1138 if(0 == (rep->can_be_null & mask_skip))
1141 else if(count == rep->max)
1143 // can't repeat any more, remove the pushed state:
1144 destroy_single_repeat();
1145 if(!can_start(*position, rep->_map, mask_skip))
1151 pmp->last_position = position;
1153 pstate = rep->alt.p;
1157 template <class BidiIterator, class Allocator, class traits>
1158 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1160 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1162 // if we have a match, just discard this state:
1165 destroy_single_repeat();
1169 const re_repeat* rep = pmp->rep;
1170 std::size_t count = pmp->count;
1171 pstate = rep->next.p;
1172 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1173 position = pmp->last_position;
1175 BOOST_ASSERT(rep->type == syntax_element_char_rep);
1176 BOOST_ASSERT(rep->next.p != 0);
1177 BOOST_ASSERT(rep->alt.p != 0);
1178 BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1179 BOOST_ASSERT(count < rep->max);
1181 if(position != last)
1183 // wind forward until we can skip out of the repeat:
1186 if(traits_inst.translate(*position, icase) != what)
1188 // failed repeat match, discard this state and look for another:
1189 destroy_single_repeat();
1195 pstate = rep->next.p;
1196 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1198 // remember where we got to if this is a leading repeat:
1199 if((rep->leading) && (count < rep->max))
1201 if(position == last)
1203 // can't repeat any more, remove the pushed state:
1204 destroy_single_repeat();
1205 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1206 m_has_partial_match = true;
1207 if(0 == (rep->can_be_null & mask_skip))
1210 else if(count == rep->max)
1212 // can't repeat any more, remove the pushed state:
1213 destroy_single_repeat();
1214 if(!can_start(*position, rep->_map, mask_skip))
1220 pmp->last_position = position;
1222 pstate = rep->alt.p;
1226 template <class BidiIterator, class Allocator, class traits>
1227 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1229 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1231 // if we have a match, just discard this state:
1234 destroy_single_repeat();
1238 const re_repeat* rep = pmp->rep;
1239 std::size_t count = pmp->count;
1240 pstate = rep->next.p;
1241 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1242 position = pmp->last_position;
1244 BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1245 BOOST_ASSERT(rep->next.p != 0);
1246 BOOST_ASSERT(rep->alt.p != 0);
1247 BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1248 BOOST_ASSERT(count < rep->max);
1250 if(position != last)
1252 // wind forward until we can skip out of the repeat:
1255 if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1257 // failed repeat match, discard this state and look for another:
1258 destroy_single_repeat();
1264 pstate = rep->next.p;
1265 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1267 // remember where we got to if this is a leading repeat:
1268 if((rep->leading) && (count < rep->max))
1270 if(position == last)
1272 // can't repeat any more, remove the pushed state:
1273 destroy_single_repeat();
1274 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1275 m_has_partial_match = true;
1276 if(0 == (rep->can_be_null & mask_skip))
1279 else if(count == rep->max)
1281 // can't repeat any more, remove the pushed state:
1282 destroy_single_repeat();
1283 if(!can_start(*position, rep->_map, mask_skip))
1289 pmp->last_position = position;
1291 pstate = rep->alt.p;
1295 template <class BidiIterator, class Allocator, class traits>
1296 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1298 typedef typename traits::char_class_type mask_type;
1299 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1301 // if we have a match, just discard this state:
1304 destroy_single_repeat();
1308 const re_repeat* rep = pmp->rep;
1309 std::size_t count = pmp->count;
1310 pstate = rep->next.p;
1311 const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate);
1312 position = pmp->last_position;
1314 BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1315 BOOST_ASSERT(rep->next.p != 0);
1316 BOOST_ASSERT(rep->alt.p != 0);
1317 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1318 BOOST_ASSERT(count < rep->max);
1320 if(position != last)
1322 // wind forward until we can skip out of the repeat:
1325 if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1327 // failed repeat match, discard this state and look for another:
1328 destroy_single_repeat();
1334 pstate = rep->next.p;
1335 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1337 // remember where we got to if this is a leading repeat:
1338 if((rep->leading) && (count < rep->max))
1340 if(position == last)
1342 // can't repeat any more, remove the pushed state:
1343 destroy_single_repeat();
1344 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1345 m_has_partial_match = true;
1346 if(0 == (rep->can_be_null & mask_skip))
1349 else if(count == rep->max)
1351 // can't repeat any more, remove the pushed state:
1352 destroy_single_repeat();
1353 if(!can_start(*position, rep->_map, mask_skip))
1359 pmp->last_position = position;
1361 pstate = rep->alt.p;
1365 template <class BidiIterator, class Allocator, class traits>
1366 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1368 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1371 position = pmp->position;
1372 pstate = pmp->pstate;
1375 boost::re_detail::inplace_destroy(pmp++);
1376 m_backup_state = pmp;
1380 } // namespace re_detail
1381 } // namespace boost
1384 # pragma warning(pop)
1388 #pragma warning(push)
1389 #pragma warning(disable: 4103)
1391 #ifdef BOOST_HAS_ABI_HEADERS
1392 # include BOOST_ABI_SUFFIX
1395 #pragma warning(pop)