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
25 #ifdef BOOST_HAS_ABI_HEADERS
26 # include BOOST_ABI_PREFIX
33 inline void inplace_destroy(T* p)
35 (void)p; // warning suppression
42 saved_state(unsigned i) : id(i) {}
45 template <class BidiIterator>
46 struct saved_matched_paren : public saved_state
49 sub_match<BidiIterator> sub;
50 saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){};
53 template <class BidiIterator>
54 struct saved_position : public saved_state
56 const re_syntax_base* pstate;
57 BidiIterator position;
58 saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){};
61 template <class BidiIterator>
62 struct saved_assertion : public saved_position<BidiIterator>
65 saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
66 : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){};
69 template <class BidiIterator>
70 struct saved_repeater : public saved_state
72 repeater_count<BidiIterator> count;
73 saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start)
74 : saved_state(saved_state_repeater_count), count(i,s,start){}
77 struct saved_extra_block : public saved_state
79 saved_state *base, *end;
80 saved_extra_block(saved_state* b, saved_state* e)
81 : saved_state(saved_state_extra_block), base(b), end(e) {}
84 struct save_state_init
87 save_state_init(saved_state** base, saved_state** end)
90 *base = static_cast<saved_state*>(get_mem_block());
91 *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
93 (void) new (*end)saved_state(0);
98 put_mem_block(*stack);
103 template <class BidiIterator>
104 struct saved_single_repeat : public saved_state
107 const re_repeat* rep;
108 BidiIterator last_position;
109 saved_single_repeat(unsigned c, const re_repeat* r, BidiIterator lp, int arg_id)
110 : saved_state(arg_id), count(c), rep(r), last_position(lp){}
113 template <class BidiIterator, class Allocator, class traits, class Allocator2>
114 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_all_states()
116 static matcher_proc_type const s_match_vtable[26] =
118 (&perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_startmark),
119 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_endmark,
120 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_literal,
121 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_start_line,
122 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_end_line,
123 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_wild,
124 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_match,
125 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_word_boundary,
126 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_within_word,
127 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_word_start,
128 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_word_end,
129 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_buffer_start,
130 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_buffer_end,
131 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_backref,
132 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_long_set,
133 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_set,
134 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_jump,
135 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_alt,
136 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_rep,
137 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_combining,
138 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_soft_buffer_end,
139 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_restart_continue,
140 (::boost::is_random_access_iterator<BidiIterator>::value ? &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_dot_repeat_fast : &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_dot_repeat_slow),
141 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_char_repeat,
142 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_set_repeat,
143 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_long_set_repeat,
146 push_recursion_stopper();
150 matcher_proc_type proc = s_match_vtable[pstate->type];
154 if(state_count > max_state_count)
155 raise_error(traits_inst, REG_ESPACE);
156 if((m_match_flags & match_partial) && (position == last))
157 m_has_partial_match = true;
158 if(false == unwind(false))
159 return m_recursive_result;
162 }while(unwind(true));
163 return m_recursive_result;
166 template <class BidiIterator, class Allocator, class traits, class Allocator2>
167 void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::extend_stack()
172 saved_state* stack_base;
173 saved_state* backup_state;
174 stack_base = static_cast<saved_state*>(get_mem_block());
175 backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
176 saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
178 (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
179 m_stack_base = stack_base;
180 m_backup_state = block;
183 raise_error(traits_inst, REG_E_MEMORY);
186 template <class BidiIterator, class Allocator, class traits, class Allocator2>
187 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
190 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
192 if(pmp < m_stack_base)
195 pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
198 (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
199 m_backup_state = pmp;
202 template <class BidiIterator, class Allocator, class traits, class Allocator2>
203 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::push_recursion_stopper()
205 saved_state* pmp = m_backup_state;
207 if(pmp < m_stack_base)
210 pmp = m_backup_state;
213 (void) new (pmp)saved_state(saved_type_recurse);
214 m_backup_state = pmp;
217 template <class BidiIterator, class Allocator, class traits, class Allocator2>
218 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::push_assertion(const re_syntax_base* ps, bool positive)
220 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
222 if(pmp < m_stack_base)
225 pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
228 (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
229 m_backup_state = pmp;
232 template <class BidiIterator, class Allocator, class traits, class Allocator2>
233 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::push_alt(const re_syntax_base* ps)
235 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
237 if(pmp < m_stack_base)
240 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
243 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
244 m_backup_state = pmp;
247 template <class BidiIterator, class Allocator, class traits, class Allocator2>
248 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::push_non_greedy_repeat(const re_syntax_base* ps)
250 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
252 if(pmp < m_stack_base)
255 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
258 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
259 m_backup_state = pmp;
262 template <class BidiIterator, class Allocator, class traits, class Allocator2>
263 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
265 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
267 if(pmp < m_stack_base)
270 pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
273 (void) new (pmp)saved_repeater<BidiIterator>(i, s, position);
274 m_backup_state = pmp;
277 template <class BidiIterator, class Allocator, class traits, class Allocator2>
278 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::push_single_repeat(unsigned c, const re_repeat* r, BidiIterator last_position, int id)
280 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
282 if(pmp < m_stack_base)
285 pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
288 (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, id);
289 m_backup_state = pmp;
292 template <class BidiIterator, class Allocator, class traits, class Allocator2>
293 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_startmark()
295 int index = static_cast<const re_brace*>(pstate)->index;
299 pstate = pstate->next.p;
304 // forward lookahead assert:
305 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
306 pstate = pstate->next.p->next.p;
307 push_assertion(next_pstate, index == -1);
312 // independent sub-expression, currently this is always recursive:
313 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
314 pstate = pstate->next.p->next.p;
315 bool r = match_all_states();
316 pstate = next_pstate;
317 #ifdef BOOST_REGEX_MATCH_EXTRA
318 if(r && (m_match_flags & match_extra))
321 // our captures have been stored in *m_presult
322 // we need to unpack them, and insert them
323 // back in the right order when we unwind the stack:
325 match_results<BidiIterator, Allocator> temp_match(*m_presult);
327 for(i = 0; i < temp_match.size(); ++i)
328 (*m_presult)[i].get_captures().clear();
329 // match everything else:
330 r = match_all_states();
331 // now place the stored captures back:
332 for(i = 0; i < temp_match.size(); ++i)
334 typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
335 seq& s1 = (*m_presult)[i].get_captures();
336 const seq& s2 = temp_match[i].captures();
349 if((m_match_flags & match_nosubs) == 0)
351 push_matched_paren(index, (*m_presult)[index]);
352 m_presult->set_first(position, index);
354 pstate = pstate->next.p;
361 template <class BidiIterator, class Allocator, class traits, class Allocator2>
362 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_alt()
364 bool take_first, take_second;
365 const re_jump* jmp = static_cast<const re_jump*>(pstate);
367 // find out which of these two alternatives we need to take:
370 take_first = jmp->can_be_null & mask_take;
371 take_second = jmp->can_be_null & mask_skip;
375 take_first = access::can_start(*position, jmp->_map, (unsigned char)mask_take);
376 take_second = access::can_start(*position, jmp->_map, (unsigned char)mask_skip);
381 // we can take the first alternative,
382 // see if we need to push next alternative:
385 push_alt(jmp->alt.p);
387 pstate = pstate->next.p;
395 return false; // neither option is possible
398 template <class BidiIterator, class Allocator, class traits, class Allocator2>
399 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_rep()
402 #pragma warning(push)
403 #pragma warning(disable:4127 4244)
406 #pragma option push -w-8008 -w-8066 -w-8004
408 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
410 // find out which of these two alternatives we need to take:
411 bool take_first, take_second;
414 take_first = rep->can_be_null & mask_take;
415 take_second = rep->can_be_null & mask_skip;
419 take_first = access::can_start(*position, rep->_map, (unsigned char)mask_take);
420 take_second = access::can_start(*position, rep->_map, (unsigned char)mask_skip);
423 if(take_first || (next_count->get_id() != rep->id))
425 // we're moving to a different repeat from the last
426 // one, so set up a counter object:
427 push_repeater_count(rep->id, &next_count);
430 // If we've had at least one repeat already, and the last one
431 // matched the NULL string then set the repeat count to
434 next_count->check_null_repeat(position, rep->max);
436 if(next_count->get_count() < rep->min)
438 // we must take the repeat:
441 // increase the counter:
443 pstate = rep->next.p;
451 // try and take the repeat if we can:
452 if((next_count->get_count() < rep->max) && take_first)
456 // store position in case we fail:
457 push_alt(rep->alt.p);
459 // increase the counter:
461 pstate = rep->next.p;
469 return false; // can't take anything, fail...
473 // try and skip the repeat if we can:
476 // store position in case we fail:
477 push_non_greedy_repeat(rep->next.p);
481 if((next_count->get_count() < rep->max) && take_first)
483 // increase the counter:
485 pstate = rep->next.p;
498 template <class BidiIterator, class Allocator, class traits, class Allocator2>
499 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_dot_repeat_slow()
502 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
503 re_syntax_base* psingle = rep->next.p;
504 // match compulsary repeats first:
505 while(count < rep->min)
514 // repeat for as long as we can:
515 while(count < rep->max)
522 // remember where we got to if this is a leading repeat:
523 if((rep->leading) && (count < rep->max))
525 // push backtrack info if available:
527 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
528 // jump to next state:
534 // non-greedy, push state and return true if we can skip:
536 push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
538 return (position == last) ? (rep->can_be_null & mask_skip) : access::can_start(*position, rep->_map, mask_skip);
542 template <class BidiIterator, class Allocator, class traits, class Allocator2>
543 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_dot_repeat_fast()
545 if(m_match_flags & (match_not_dot_newline | match_not_dot_null))
546 return match_dot_repeat_slow();
548 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
549 unsigned count = std::min(static_cast<unsigned>(re_detail::distance(position, last)), static_cast<unsigned>(rep->greedy ? rep->max : rep->min));
551 return false; // not enough text left to match
552 std::advance(position, count);
556 if((rep->leading) && (count < rep->max))
558 // push backtrack info if available:
560 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
561 // jump to next state:
567 // non-greedy, push state and return true if we can skip:
569 push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
571 return (position == last) ? (rep->can_be_null & mask_skip) : access::can_start(*position, rep->_map, mask_skip);
575 template <class BidiIterator, class Allocator, class traits, class Allocator2>
576 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_char_repeat()
579 #pragma warning(push)
580 #pragma warning(disable:4127)
583 #pragma option push -w-8008 -w-8066 -w-8004
585 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
586 assert(1 == static_cast<const re_literal*>(rep->next.p)->length);
587 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
590 // start by working out how much we can skip:
592 unsigned desired = rep->greedy ? rep->max : rep->min;
593 if(::boost::is_random_access_iterator<BidiIterator>::value)
595 BidiIterator end = position;
596 std::advance(end, std::min((unsigned)re_detail::distance(position, last), desired));
597 BidiIterator origin(position);
598 while((position != end) && (traits_inst.translate(*position, icase) == what))
602 count = (unsigned)re_detail::distance(origin, position);
606 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
618 if((rep->leading) && (count < rep->max))
620 // push backtrack info if available:
622 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
623 // jump to next state:
629 // non-greedy, push state and return true if we can skip:
631 push_single_repeat(count, rep, position, saved_state_rep_char);
633 return (position == last) ? (rep->can_be_null & mask_skip) : access::can_start(*position, rep->_map, mask_skip);
643 template <class BidiIterator, class Allocator, class traits, class Allocator2>
644 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_set_repeat()
647 #pragma warning(push)
648 #pragma warning(disable:4127)
651 #pragma option push -w-8008 -w-8066 -w-8004
653 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
654 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
657 // start by working out how much we can skip:
659 unsigned desired = rep->greedy ? rep->max : rep->min;
660 if(::boost::is_random_access_iterator<BidiIterator>::value)
662 BidiIterator end = position;
663 std::advance(end, std::min((unsigned)re_detail::distance(position, last), desired));
664 BidiIterator origin(position);
665 while((position != end) && map[(traits_uchar_type)traits_inst.translate(*position, icase)])
669 count = (unsigned)re_detail::distance(origin, position);
673 while((count < desired) && (position != last) && map[(traits_uchar_type)traits_inst.translate(*position, icase)])
685 if((rep->leading) && (count < rep->max))
687 // push backtrack info if available:
689 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
690 // jump to next state:
696 // non-greedy, push state and return true if we can skip:
698 push_single_repeat(count, rep, position, saved_state_rep_short_set);
700 return (position == last) ? (rep->can_be_null & mask_skip) : access::can_start(*position, rep->_map, mask_skip);
710 template <class BidiIterator, class Allocator, class traits, class Allocator2>
711 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::match_long_set_repeat()
714 #pragma warning(push)
715 #pragma warning(disable:4127)
718 #pragma option push -w-8008 -w-8066 -w-8004
720 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
721 const re_set_long* set = static_cast<const re_set_long*>(pstate->next.p);
724 // start by working out how much we can skip:
726 unsigned desired = rep->greedy ? rep->max : rep->min;
727 if(::boost::is_random_access_iterator<BidiIterator>::value)
729 BidiIterator end = position;
730 std::advance(end, std::min((unsigned)re_detail::distance(position, last), desired));
731 BidiIterator origin(position);
732 while((position != end) && (position != re_is_set_member(position, last, set, re)))
736 count = (unsigned)re_detail::distance(origin, position);
740 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re)))
752 if((rep->leading) && (count < rep->max))
754 // push backtrack info if available:
756 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
757 // jump to next state:
763 // non-greedy, push state and return true if we can skip:
765 push_single_repeat(count, rep, position, saved_state_rep_long_set);
767 return (position == last) ? (rep->can_be_null & mask_skip) : access::can_start(*position, rep->_map, mask_skip);
777 /****************************************************************************
779 Unwind and associated proceedures follow, these perform what normal stack
780 unwinding does in the recursive implementation.
782 ****************************************************************************/
784 template <class BidiIterator, class Allocator, class traits, class Allocator2>
785 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind(bool have_match)
787 static unwind_proc_type const s_unwind_table[14] =
789 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_end,
790 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_paren,
791 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_recursion_stopper,
792 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_assertion,
793 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_alt,
794 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_repeater_counter,
795 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_extra_block,
796 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_greedy_single_repeat,
797 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_slow_dot_repeat,
798 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_fast_dot_repeat,
799 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_char_repeat,
800 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_short_set_repeat,
801 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_long_set_repeat,
802 &perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_non_greedy_repeat,
805 m_recursive_result = have_match;
806 unwind_proc_type unwinder;
809 // keep unwinding our stack until we have something to do:
813 unwinder = s_unwind_table[m_backup_state->id];
814 cont = (this->*unwinder)(m_recursive_result);
817 // return true if we have more states to try:
819 return pstate ? true : false;
822 template <class BidiIterator, class Allocator, class traits, class Allocator2>
823 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_end(bool)
825 pstate = 0; // nothing left to search
826 return false; // end of stack nothing more to search
829 template <class BidiIterator, class Allocator, class traits, class Allocator2>
830 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_paren(bool have_match)
832 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
833 // restore previous values if no match was found:
834 if(have_match == false)
836 m_presult->set_first(pmp->sub.first, pmp->index);
837 m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched);
839 #ifdef BOOST_REGEX_MATCH_EXTRA
841 // we have a match, push the capture information onto the stack:
843 else if(pmp->sub.matched && (match_extra & m_match_flags))
844 ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
847 m_backup_state = pmp+1;
848 boost::re_detail::inplace_destroy(pmp);
849 return true; // keep looking
852 template <class BidiIterator, class Allocator, class traits, class Allocator2>
853 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_recursion_stopper(bool)
855 boost::re_detail::inplace_destroy(m_backup_state++);
856 pstate = 0; // nothing left to search
857 return false; // end of stack nothing more to search
860 template <class BidiIterator, class Allocator, class traits, class Allocator2>
861 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_assertion(bool r)
863 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
864 pstate = pmp->pstate;
865 position = pmp->position;
866 bool result = (r == pmp->positive);
867 m_recursive_result = pmp->positive ? r : !r;
868 boost::re_detail::inplace_destroy(pmp++);
869 m_backup_state = pmp;
870 return !result; // return false if the assertion was matched to stop search.
873 template <class BidiIterator, class Allocator, class traits, class Allocator2>
874 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_alt(bool r)
876 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
879 pstate = pmp->pstate;
880 position = pmp->position;
882 boost::re_detail::inplace_destroy(pmp++);
883 m_backup_state = pmp;
887 template <class BidiIterator, class Allocator, class traits, class Allocator2>
888 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_repeater_counter(bool)
890 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
891 boost::re_detail::inplace_destroy(pmp++);
892 m_backup_state = pmp;
893 return true; // keep looking
896 template <class BidiIterator, class Allocator, class traits, class Allocator2>
897 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_extra_block(bool)
899 saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
900 void* condemmed = m_stack_base;
901 m_stack_base = pmp->base;
902 m_backup_state = pmp->end;
903 boost::re_detail::inplace_destroy(pmp);
904 put_mem_block(condemmed);
905 return true; // keep looking
908 template <class BidiIterator, class Allocator, class traits, class Allocator2>
909 inline void perl_matcher<BidiIterator, Allocator, traits, Allocator2>::destroy_single_repeat()
911 saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
912 boost::re_detail::inplace_destroy(p++);
916 template <class BidiIterator, class Allocator, class traits, class Allocator2>
917 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_greedy_single_repeat(bool r)
919 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
921 // if we have a match, just discard this state:
924 destroy_single_repeat();
928 const re_repeat* rep = pmp->rep;
929 unsigned count = pmp->count;
935 if((m_match_flags & match_partial) && (position == last))
936 m_has_partial_match = true;
939 position = pmp->last_position;
941 // backtrack till we can skip out:
947 }while(count && !access::can_start(*position, rep->_map, mask_skip));
949 // if we've hit base, destroy this state:
952 destroy_single_repeat();
953 if(!access::can_start(*position, rep->_map, mask_skip))
958 pmp->count = count + rep->min;
959 pmp->last_position = position;
965 template <class BidiIterator, class Allocator, class traits, class Allocator2>
966 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_slow_dot_repeat(bool r)
968 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
970 // if we have a match, just discard this state:
973 destroy_single_repeat();
977 const re_repeat* rep = pmp->rep;
978 unsigned count = pmp->count;
979 assert(rep->type == syntax_element_dot_rep);
982 assert(rep->next.p->type == syntax_element_wild);
984 assert(count < rep->max);
985 pstate = rep->next.p;
986 position = pmp->last_position;
990 // wind forward until we can skip out of the repeat:
995 // failed repeat match, discard this state and look for another:
996 destroy_single_repeat();
1001 pstate = rep->next.p;
1002 }while((count < rep->max) && (position != last) && !access::can_start(*position, rep->_map, mask_skip));
1004 if(position == last)
1006 // can't repeat any more, remove the pushed state:
1007 destroy_single_repeat();
1008 if(0 == (rep->can_be_null & mask_skip))
1011 else if(count == rep->max)
1013 // can't repeat any more, remove the pushed state:
1014 destroy_single_repeat();
1015 if(!access::can_start(*position, rep->_map, mask_skip))
1021 pmp->last_position = position;
1023 pstate = rep->alt.p;
1027 template <class BidiIterator, class Allocator, class traits, class Allocator2>
1028 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_fast_dot_repeat(bool r)
1030 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1032 // if we have a match, just discard this state:
1035 destroy_single_repeat();
1039 const re_repeat* rep = pmp->rep;
1040 unsigned count = pmp->count;
1042 assert(count < rep->max);
1043 position = pmp->last_position;
1044 if(position != last)
1047 // wind forward until we can skip out of the repeat:
1053 }while((count < rep->max) && (position != last) && !access::can_start(*position, rep->_map, mask_skip));
1056 if(position == last)
1058 // can't repeat any more, remove the pushed state:
1059 destroy_single_repeat();
1060 if(0 == (rep->can_be_null & mask_skip))
1063 else if(count == rep->max)
1065 // can't repeat any more, remove the pushed state:
1066 destroy_single_repeat();
1067 if(!access::can_start(*position, rep->_map, mask_skip))
1073 pmp->last_position = position;
1075 pstate = rep->alt.p;
1079 template <class BidiIterator, class Allocator, class traits, class Allocator2>
1080 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_char_repeat(bool r)
1082 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1084 // if we have a match, just discard this state:
1087 destroy_single_repeat();
1091 const re_repeat* rep = pmp->rep;
1092 unsigned count = pmp->count;
1093 pstate = rep->next.p;
1094 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1095 position = pmp->last_position;
1097 assert(rep->type == syntax_element_char_rep);
1098 assert(rep->next.p);
1100 assert(rep->next.p->type == syntax_element_literal);
1101 assert(count < rep->max);
1103 if(position != last)
1105 // wind forward until we can skip out of the repeat:
1108 if(traits_inst.translate(*position, icase) != what)
1110 // failed repeat match, discard this state and look for another:
1111 destroy_single_repeat();
1117 pstate = rep->next.p;
1118 }while((count < rep->max) && (position != last) && !access::can_start(*position, rep->_map, mask_skip));
1120 if(position == last)
1122 // can't repeat any more, remove the pushed state:
1123 destroy_single_repeat();
1124 if(0 == (rep->can_be_null & mask_skip))
1127 else if(count == rep->max)
1129 // can't repeat any more, remove the pushed state:
1130 destroy_single_repeat();
1131 if(!access::can_start(*position, rep->_map, mask_skip))
1137 pmp->last_position = position;
1139 pstate = rep->alt.p;
1143 template <class BidiIterator, class Allocator, class traits, class Allocator2>
1144 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_short_set_repeat(bool r)
1146 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1148 // if we have a match, just discard this state:
1151 destroy_single_repeat();
1155 const re_repeat* rep = pmp->rep;
1156 unsigned count = pmp->count;
1157 pstate = rep->next.p;
1158 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1159 position = pmp->last_position;
1161 assert(rep->type == syntax_element_short_set_rep);
1162 assert(rep->next.p);
1164 assert(rep->next.p->type == syntax_element_set);
1165 assert(count < rep->max);
1167 if(position != last)
1169 // wind forward until we can skip out of the repeat:
1172 if(!map[(traits_uchar_type)traits_inst.translate(*position, icase)])
1174 // failed repeat match, discard this state and look for another:
1175 destroy_single_repeat();
1181 pstate = rep->next.p;
1182 }while((count < rep->max) && (position != last) && !access::can_start(*position, rep->_map, mask_skip));
1184 if(position == last)
1186 // can't repeat any more, remove the pushed state:
1187 destroy_single_repeat();
1188 if(0 == (rep->can_be_null & mask_skip))
1191 else if(count == rep->max)
1193 // can't repeat any more, remove the pushed state:
1194 destroy_single_repeat();
1195 if(!access::can_start(*position, rep->_map, mask_skip))
1201 pmp->last_position = position;
1203 pstate = rep->alt.p;
1207 template <class BidiIterator, class Allocator, class traits, class Allocator2>
1208 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_long_set_repeat(bool r)
1210 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1212 // if we have a match, just discard this state:
1215 destroy_single_repeat();
1219 const re_repeat* rep = pmp->rep;
1220 unsigned count = pmp->count;
1221 pstate = rep->next.p;
1222 const re_set_long* set = static_cast<const re_set_long*>(pstate);
1223 position = pmp->last_position;
1225 assert(rep->type == syntax_element_long_set_rep);
1226 assert(rep->next.p);
1228 assert(rep->next.p->type == syntax_element_long_set);
1229 assert(position != last);
1230 assert(count < rep->max);
1232 if(position != last)
1234 // wind forward until we can skip out of the repeat:
1237 if(position == re_is_set_member(position, last, set, re))
1239 // failed repeat match, discard this state and look for another:
1240 destroy_single_repeat();
1246 pstate = rep->next.p;
1247 }while((count < rep->max) && (position != last) && !access::can_start(*position, rep->_map, mask_skip));
1249 if(position == last)
1251 // can't repeat any more, remove the pushed state:
1252 destroy_single_repeat();
1253 if(0 == (rep->can_be_null & mask_skip))
1256 else if(count == rep->max)
1258 // can't repeat any more, remove the pushed state:
1259 destroy_single_repeat();
1260 if(!access::can_start(*position, rep->_map, mask_skip))
1266 pmp->last_position = position;
1268 pstate = rep->alt.p;
1272 template <class BidiIterator, class Allocator, class traits, class Allocator2>
1273 bool perl_matcher<BidiIterator, Allocator, traits, Allocator2>::unwind_non_greedy_repeat(bool r)
1275 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1278 position = pmp->position;
1279 pstate = pmp->pstate;
1282 boost::re_detail::inplace_destroy(pmp++);
1283 m_backup_state = pmp;
1287 } // namespace re_detail
1288 } // namespace boost
1290 #ifdef BOOST_HAS_ABI_HEADERS
1291 # include BOOST_ABI_SUFFIX