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: 4706)
39 #pragma warning(disable:4800)
44 namespace BOOST_REGEX_DETAIL_NS{
47 inline void inplace_destroy(T* p)
49 (void)p; // warning suppression
56 unsigned int state_id;
57 // this padding ensures correct alignment on 64-bit platforms:
59 std::ptrdiff_t padding2;
62 saved_state(unsigned i) : state_id(i) {}
65 template <class BidiIterator>
66 struct saved_matched_paren : public saved_state
69 sub_match<BidiIterator> sub;
70 saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){}
73 template <class BidiIterator>
74 struct saved_position : public saved_state
76 const re_syntax_base* pstate;
77 BidiIterator position;
78 saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){}
81 template <class BidiIterator>
82 struct saved_assertion : public saved_position<BidiIterator>
85 saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
86 : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){}
89 template <class BidiIterator>
90 struct saved_repeater : public saved_state
92 repeater_count<BidiIterator> count;
93 saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start, int current_recursion_id)
94 : saved_state(saved_state_repeater_count), count(i, s, start, current_recursion_id){}
97 struct saved_extra_block : public saved_state
99 saved_state *base, *end;
100 saved_extra_block(saved_state* b, saved_state* e)
101 : saved_state(saved_state_extra_block), base(b), end(e) {}
104 struct save_state_init
107 save_state_init(saved_state** base, saved_state** end)
110 *base = static_cast<saved_state*>(get_mem_block());
111 *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
113 (void) new (*end)saved_state(0);
114 BOOST_ASSERT(*end > *base);
118 put_mem_block(*stack);
123 template <class BidiIterator>
124 struct saved_single_repeat : public saved_state
127 const re_repeat* rep;
128 BidiIterator last_position;
129 saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
130 : saved_state(arg_id), count(c), rep(r), last_position(lp){}
133 template <class Results>
134 struct saved_recursion : public saved_state
136 saved_recursion(int idx, const re_syntax_base* p, Results* pr, Results* pr2)
137 : saved_state(14), recursion_id(idx), preturn_address(p), internal_results(*pr), prior_results(*pr2) {}
139 const re_syntax_base* preturn_address;
140 Results internal_results, prior_results;
143 struct saved_change_case : public saved_state
146 saved_change_case(bool c) : saved_state(18), icase(c) {}
151 incrementer(unsigned* pu) : m_pu(pu) { ++*m_pu; }
152 ~incrementer() { --*m_pu; }
153 bool operator > (unsigned i) { return *m_pu > i; }
158 template <class BidiIterator, class Allocator, class traits>
159 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
161 static matcher_proc_type const s_match_vtable[34] =
163 (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
164 &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
165 &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
166 &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
167 &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
168 &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
169 &perl_matcher<BidiIterator, Allocator, traits>::match_match,
170 &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
171 &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
172 &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
173 &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
174 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
175 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
176 &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
177 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
178 &perl_matcher<BidiIterator, Allocator, traits>::match_set,
179 &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
180 &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
181 &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
182 &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
183 &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
184 &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
185 // Although this next line *should* be evaluated at compile time, in practice
186 // some compilers (VC++) emit run-time initialisation which breaks thread
187 // safety, so use a dispatch function instead:
188 //(::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),
189 &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
190 &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
191 &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
192 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
193 &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
194 &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
195 &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
196 &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
197 &perl_matcher<BidiIterator, Allocator, traits>::match_fail,
198 &perl_matcher<BidiIterator, Allocator, traits>::match_accept,
199 &perl_matcher<BidiIterator, Allocator, traits>::match_commit,
200 &perl_matcher<BidiIterator, Allocator, traits>::match_then,
202 incrementer inc(&m_recursions);
204 raise_error(traits_inst, regex_constants::error_complexity);
205 push_recursion_stopper();
209 matcher_proc_type proc = s_match_vtable[pstate->type];
213 if(state_count > max_state_count)
214 raise_error(traits_inst, regex_constants::error_complexity);
215 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
216 m_has_partial_match = true;
217 bool successful_unwind = unwind(false);
218 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
219 m_has_partial_match = true;
220 if(false == successful_unwind)
221 return m_recursive_result;
224 }while(unwind(true));
225 return m_recursive_result;
228 template <class BidiIterator, class Allocator, class traits>
229 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
234 saved_state* stack_base;
235 saved_state* backup_state;
236 stack_base = static_cast<saved_state*>(get_mem_block());
237 backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
238 saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
240 (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
241 m_stack_base = stack_base;
242 m_backup_state = block;
245 raise_error(traits_inst, regex_constants::error_stack);
248 template <class BidiIterator, class Allocator, class traits>
249 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
251 //BOOST_ASSERT(index);
252 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
254 if(pmp < m_stack_base)
257 pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
260 (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
261 m_backup_state = pmp;
264 template <class BidiIterator, class Allocator, class traits>
265 inline void perl_matcher<BidiIterator, Allocator, traits>::push_case_change(bool c)
267 //BOOST_ASSERT(index);
268 saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
270 if(pmp < m_stack_base)
273 pmp = static_cast<saved_change_case*>(m_backup_state);
276 (void) new (pmp)saved_change_case(c);
277 m_backup_state = pmp;
280 template <class BidiIterator, class Allocator, class traits>
281 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
283 saved_state* pmp = m_backup_state;
285 if(pmp < m_stack_base)
288 pmp = m_backup_state;
291 (void) new (pmp)saved_state(saved_type_recurse);
292 m_backup_state = pmp;
295 template <class BidiIterator, class Allocator, class traits>
296 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
298 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
300 if(pmp < m_stack_base)
303 pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
306 (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
307 m_backup_state = pmp;
310 template <class BidiIterator, class Allocator, class traits>
311 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
313 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
315 if(pmp < m_stack_base)
318 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
321 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
322 m_backup_state = pmp;
325 template <class BidiIterator, class Allocator, class traits>
326 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
328 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
330 if(pmp < m_stack_base)
333 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
336 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
337 m_backup_state = pmp;
340 template <class BidiIterator, class Allocator, class traits>
341 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
343 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
345 if(pmp < m_stack_base)
348 pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
351 (void) new (pmp)saved_repeater<BidiIterator>(i, s, position, this->recursion_stack.size() ? this->recursion_stack.back().idx : (INT_MIN + 3));
352 m_backup_state = pmp;
355 template <class BidiIterator, class Allocator, class traits>
356 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
358 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
360 if(pmp < m_stack_base)
363 pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
366 (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
367 m_backup_state = pmp;
370 template <class BidiIterator, class Allocator, class traits>
371 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion(int idx, const re_syntax_base* p, results_type* presults, results_type* presults2)
373 saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
375 if(pmp < m_stack_base)
378 pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
381 (void) new (pmp)saved_recursion<results_type>(idx, p, presults, presults2);
382 m_backup_state = pmp;
385 template <class BidiIterator, class Allocator, class traits>
386 bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
388 // change our case sensitivity:
389 push_case_change(this->icase);
390 this->icase = static_cast<const re_case*>(pstate)->icase;
391 pstate = pstate->next.p;
395 template <class BidiIterator, class Allocator, class traits>
396 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
398 int index = static_cast<const re_brace*>(pstate)->index;
399 icase = static_cast<const re_brace*>(pstate)->icase;
403 pstate = pstate->next.p;
408 // forward lookahead assert:
409 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
410 pstate = pstate->next.p->next.p;
411 push_assertion(next_pstate, index == -1);
416 // independent sub-expression, currently this is always recursive:
417 bool old_independent = m_independent;
418 m_independent = true;
419 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
420 pstate = pstate->next.p->next.p;
422 #if !defined(BOOST_NO_EXCEPTIONS)
425 r = match_all_states();
426 if(!r && !m_independent)
428 // Must be unwinding from a COMMIT/SKIP/PRUNE and the independent
429 // sub failed, need to unwind everything else:
430 while(unwind(false));
433 #if !defined(BOOST_NO_EXCEPTIONS)
437 pstate = next_pstate;
438 // unwind all pushed states, apart from anything else this
439 // ensures that all the states are correctly destructed
440 // not just the memory freed.
441 while(unwind(true)) {}
445 pstate = next_pstate;
446 m_independent = old_independent;
447 #ifdef BOOST_REGEX_MATCH_EXTRA
448 if(r && (m_match_flags & match_extra))
451 // our captures have been stored in *m_presult
452 // we need to unpack them, and insert them
453 // back in the right order when we unwind the stack:
455 match_results<BidiIterator, Allocator> temp_match(*m_presult);
457 for(i = 0; i < temp_match.size(); ++i)
458 (*m_presult)[i].get_captures().clear();
459 // match everything else:
460 #if !defined(BOOST_NO_EXCEPTIONS)
463 r = match_all_states();
464 #if !defined(BOOST_NO_EXCEPTIONS)
468 pstate = next_pstate;
469 // unwind all pushed states, apart from anything else this
470 // ensures that all the states are correctly destructed
471 // not just the memory freed.
472 while(unwind(true)) {}
476 // now place the stored captures back:
477 for(i = 0; i < temp_match.size(); ++i)
479 typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
480 seq& s1 = (*m_presult)[i].get_captures();
481 const seq& s2 = temp_match[i].captures();
493 // conditional expression:
494 const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
495 BOOST_ASSERT(alt->type == syntax_element_alt);
496 pstate = alt->next.p;
497 if(pstate->type == syntax_element_assert_backref)
499 if(!match_assert_backref())
505 // zero width assertion, have to match this recursively:
506 BOOST_ASSERT(pstate->type == syntax_element_startmark);
507 bool negated = static_cast<const re_brace*>(pstate)->index == -2;
508 BidiIterator saved_position = position;
509 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
510 pstate = pstate->next.p->next.p;
511 #if !defined(BOOST_NO_EXCEPTIONS)
514 bool r = match_all_states();
515 position = saved_position;
519 pstate = next_pstate;
522 #if !defined(BOOST_NO_EXCEPTIONS)
526 pstate = next_pstate;
527 // unwind all pushed states, apart from anything else this
528 // ensures that all the states are correctly destructed
529 // not just the memory freed.
530 while(unwind(true)){}
539 push_matched_paren(0, (*m_presult)[0]);
540 m_presult->set_first(position, 0, true);
541 pstate = pstate->next.p;
546 BOOST_ASSERT(index > 0);
547 if((m_match_flags & match_nosubs) == 0)
549 push_matched_paren(index, (*m_presult)[index]);
550 m_presult->set_first(position, index);
552 pstate = pstate->next.p;
559 template <class BidiIterator, class Allocator, class traits>
560 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
562 bool take_first, take_second;
563 const re_alt* jmp = static_cast<const re_alt*>(pstate);
565 // find out which of these two alternatives we need to take:
568 take_first = jmp->can_be_null & mask_take;
569 take_second = jmp->can_be_null & mask_skip;
573 take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
574 take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
579 // we can take the first alternative,
580 // see if we need to push next alternative:
583 push_alt(jmp->alt.p);
585 pstate = pstate->next.p;
593 return false; // neither option is possible
596 template <class BidiIterator, class Allocator, class traits>
597 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
600 #pragma warning(push)
601 #pragma warning(disable:4127 4244)
603 #ifdef BOOST_BORLANDC
604 #pragma option push -w-8008 -w-8066 -w-8004
606 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
608 // find out which of these two alternatives we need to take:
609 bool take_first, take_second;
612 take_first = rep->can_be_null & mask_take;
613 take_second = rep->can_be_null & mask_skip;
617 take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
618 take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
621 if((m_backup_state->state_id != saved_state_repeater_count)
622 || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
623 || (next_count->get_id() != rep->state_id))
625 // we're moving to a different repeat from the last
626 // one, so set up a counter object:
627 push_repeater_count(rep->state_id, &next_count);
630 // If we've had at least one repeat already, and the last one
631 // matched the NULL string then set the repeat count to
634 next_count->check_null_repeat(position, rep->max);
636 if(next_count->get_count() < rep->min)
638 // we must take the repeat:
641 // increase the counter:
643 pstate = rep->next.p;
649 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
652 // try and take the repeat if we can:
653 if((next_count->get_count() < rep->max) && take_first)
657 // store position in case we fail:
658 push_alt(rep->alt.p);
660 // increase the counter:
662 pstate = rep->next.p;
670 return false; // can't take anything, fail...
674 // try and skip the repeat if we can:
677 if((next_count->get_count() < rep->max) && take_first)
679 // store position in case we fail:
680 push_non_greedy_repeat(rep->next.p);
685 if((next_count->get_count() < rep->max) && take_first)
687 // increase the counter:
689 pstate = rep->next.p;
694 #ifdef BOOST_BORLANDC
702 template <class BidiIterator, class Allocator, class traits>
703 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
705 std::size_t count = 0;
706 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
707 re_syntax_base* psingle = rep->next.p;
708 // match compulsary repeats first:
709 while(count < rep->min)
716 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
719 // repeat for as long as we can:
720 while(count < rep->max)
727 // remember where we got to if this is a leading repeat:
728 if((rep->leading) && (count < rep->max))
730 // push backtrack info if available:
732 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
733 // jump to next state:
739 // non-greedy, push state and return true if we can skip:
741 push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
743 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
747 template <class BidiIterator, class Allocator, class traits>
748 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
750 if(m_match_flags & match_not_dot_null)
751 return match_dot_repeat_slow();
752 if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
753 return match_dot_repeat_slow();
755 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
756 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
757 std::size_t count = static_cast<std::size_t>((std::min)(static_cast<std::size_t>(::boost::BOOST_REGEX_DETAIL_NS::distance(position, last)), greedy ? rep->max : rep->min));
761 return false; // not enough text left to match
763 std::advance(position, count);
767 if((rep->leading) && (count < rep->max))
769 // push backtrack info if available:
771 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
772 // jump to next state:
778 // non-greedy, push state and return true if we can skip:
780 push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
782 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
786 template <class BidiIterator, class Allocator, class traits>
787 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
790 #pragma warning(push)
791 #pragma warning(disable:4127)
793 #ifdef BOOST_BORLANDC
794 #pragma option push -w-8008 -w-8066 -w-8004
796 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
797 BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
798 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
799 std::size_t count = 0;
801 // start by working out how much we can skip:
803 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
804 std::size_t desired = greedy ? rep->max : rep->min;
805 if(::boost::is_random_access_iterator<BidiIterator>::value)
807 BidiIterator end = position;
808 // Move end forward by "desired", preferably without using distance or advance if we can
809 // as these can be slow for some iterator types.
810 std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
814 std::advance(end, desired);
815 BidiIterator origin(position);
816 while((position != end) && (traits_inst.translate(*position, icase) == what))
820 count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
824 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
836 if((rep->leading) && (count < rep->max))
838 // push backtrack info if available:
840 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
841 // jump to next state:
847 // non-greedy, push state and return true if we can skip:
849 push_single_repeat(count, rep, position, saved_state_rep_char);
851 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
853 #ifdef BOOST_BORLANDC
861 template <class BidiIterator, class Allocator, class traits>
862 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
865 #pragma warning(push)
866 #pragma warning(disable:4127)
868 #ifdef BOOST_BORLANDC
869 #pragma option push -w-8008 -w-8066 -w-8004
871 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
872 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
873 std::size_t count = 0;
875 // start by working out how much we can skip:
877 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
878 std::size_t desired = greedy ? rep->max : rep->min;
879 if(::boost::is_random_access_iterator<BidiIterator>::value)
881 BidiIterator end = position;
882 // Move end forward by "desired", preferably without using distance or advance if we can
883 // as these can be slow for some iterator types.
884 std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
888 std::advance(end, desired);
889 BidiIterator origin(position);
890 while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
894 count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
898 while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
910 if((rep->leading) && (count < rep->max))
912 // push backtrack info if available:
914 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
915 // jump to next state:
921 // non-greedy, push state and return true if we can skip:
923 push_single_repeat(count, rep, position, saved_state_rep_short_set);
925 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
927 #ifdef BOOST_BORLANDC
935 template <class BidiIterator, class Allocator, class traits>
936 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
939 #pragma warning(push)
940 #pragma warning(disable:4127)
942 #ifdef BOOST_BORLANDC
943 #pragma option push -w-8008 -w-8066 -w-8004
945 typedef typename traits::char_class_type m_type;
946 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
947 const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate->next.p);
948 std::size_t count = 0;
950 // start by working out how much we can skip:
952 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
953 std::size_t desired = greedy ? rep->max : rep->min;
954 if(::boost::is_random_access_iterator<BidiIterator>::value)
956 BidiIterator end = position;
957 // Move end forward by "desired", preferably without using distance or advance if we can
958 // as these can be slow for some iterator types.
959 std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
963 std::advance(end, desired);
964 BidiIterator origin(position);
965 while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
969 count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
973 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
985 if((rep->leading) && (count < rep->max))
987 // push backtrack info if available:
989 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
990 // jump to next state:
996 // non-greedy, push state and return true if we can skip:
998 push_single_repeat(count, rep, position, saved_state_rep_long_set);
1000 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
1002 #ifdef BOOST_BORLANDC
1006 #pragma warning(pop)
1010 template <class BidiIterator, class Allocator, class traits>
1011 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
1013 BOOST_ASSERT(pstate->type == syntax_element_recurse);
1015 // See if we've seen this recursion before at this location, if we have then
1016 // we need to prevent infinite recursion:
1018 for(typename std::vector<recursion_info<results_type> >::reverse_iterator i = recursion_stack.rbegin(); i != recursion_stack.rend(); ++i)
1020 if(i->idx == static_cast<const re_brace*>(static_cast<const re_jump*>(pstate)->alt.p)->index)
1022 if(i->location_of_start == position)
1028 // Backup call stack:
1030 push_recursion_pop();
1032 // Set new call stack:
1034 if(recursion_stack.capacity() == 0)
1036 recursion_stack.reserve(50);
1038 recursion_stack.push_back(recursion_info<results_type>());
1039 recursion_stack.back().preturn_address = pstate->next.p;
1040 recursion_stack.back().results = *m_presult;
1041 pstate = static_cast<const re_jump*>(pstate)->alt.p;
1042 recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
1043 recursion_stack.back().location_of_start = position;
1044 //if(static_cast<const re_recurse*>(pstate)->state_id > 0)
1046 push_repeater_count(-(2 + static_cast<const re_brace*>(pstate)->index), &next_count);
1052 template <class BidiIterator, class Allocator, class traits>
1053 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
1055 int index = static_cast<const re_brace*>(pstate)->index;
1056 icase = static_cast<const re_brace*>(pstate)->icase;
1059 if((m_match_flags & match_nosubs) == 0)
1061 m_presult->set_second(position, index);
1063 if(!recursion_stack.empty())
1065 if(index == recursion_stack.back().idx)
1067 pstate = recursion_stack.back().preturn_address;
1068 *m_presult = recursion_stack.back().results;
1069 push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, m_presult, &recursion_stack.back().results);
1070 recursion_stack.pop_back();
1071 push_repeater_count(-(2 + index), &next_count);
1075 else if((index < 0) && (index != -4))
1077 // matched forward lookahead:
1081 pstate = pstate->next.p;
1085 template <class BidiIterator, class Allocator, class traits>
1086 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
1088 if(!recursion_stack.empty())
1090 BOOST_ASSERT(0 == recursion_stack.back().idx);
1091 pstate = recursion_stack.back().preturn_address;
1092 push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, m_presult, &recursion_stack.back().results);
1093 *m_presult = recursion_stack.back().results;
1094 recursion_stack.pop_back();
1097 if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
1099 if((m_match_flags & match_all) && (position != last))
1101 if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
1103 m_presult->set_second(position);
1105 m_has_found_match = true;
1106 if((m_match_flags & match_posix) == match_posix)
1108 m_result.maybe_assign(*m_presult);
1109 if((m_match_flags & match_any) == 0)
1112 #ifdef BOOST_REGEX_MATCH_EXTRA
1113 if(match_extra & m_match_flags)
1115 for(unsigned i = 0; i < m_presult->size(); ++i)
1116 if((*m_presult)[i].matched)
1117 ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
1123 template <class BidiIterator, class Allocator, class traits>
1124 bool perl_matcher<BidiIterator, Allocator, traits>::match_commit()
1126 // Ideally we would just junk all the states that are on the stack,
1127 // however we might not unwind correctly in that case, so for now,
1128 // just mark that we don't backtrack into whatever is left (or rather
1129 // we'll unwind it unconditionally without pausing to try other matches).
1131 switch(static_cast<const re_commit*>(pstate)->action)
1137 if(base != position)
1140 // Have to decrement restart since it will get incremented again later:
1148 saved_state* pmp = m_backup_state;
1150 if(pmp < m_stack_base)
1153 pmp = m_backup_state;
1156 (void) new (pmp)saved_state(16);
1157 m_backup_state = pmp;
1158 pstate = pstate->next.p;
1162 template <class BidiIterator, class Allocator, class traits>
1163 bool perl_matcher<BidiIterator, Allocator, traits>::match_then()
1165 // Just leave a mark that we need to skip to next alternative:
1166 saved_state* pmp = m_backup_state;
1168 if(pmp < m_stack_base)
1171 pmp = m_backup_state;
1174 (void) new (pmp)saved_state(17);
1175 m_backup_state = pmp;
1176 pstate = pstate->next.p;
1180 template <class BidiIterator, class Allocator, class traits>
1181 bool perl_matcher<BidiIterator, Allocator, traits>::skip_until_paren(int index, bool have_match)
1185 if(pstate->type == syntax_element_endmark)
1187 if(static_cast<const re_brace*>(pstate)->index == index)
1190 return this->match_endmark();
1191 pstate = pstate->next.p;
1196 // Unenclosed closing ), occurs when (*ACCEPT) is inside some other
1197 // parenthesis which may or may not have other side effects associated with it.
1198 const re_syntax_base* sp = pstate;
1203 // unwind may leave pstate NULL if we've unwound a forward lookahead, in which
1204 // case just move to the next state and keep looking...
1206 pstate = sp->next.p;
1211 else if(pstate->type == syntax_element_match)
1213 else if(pstate->type == syntax_element_startmark)
1215 int idx = static_cast<const re_brace*>(pstate)->index;
1216 pstate = pstate->next.p;
1217 skip_until_paren(idx, false);
1220 pstate = pstate->next.p;
1225 /****************************************************************************
1227 Unwind and associated proceedures follow, these perform what normal stack
1228 unwinding does in the recursive implementation.
1230 ****************************************************************************/
1232 template <class BidiIterator, class Allocator, class traits>
1233 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
1235 static unwind_proc_type const s_unwind_table[19] =
1237 &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
1238 &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
1239 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
1240 &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
1241 &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
1242 &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
1243 &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
1244 &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
1245 &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
1246 &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
1247 &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
1248 &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
1249 &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
1250 &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
1251 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion,
1252 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop,
1253 &perl_matcher<BidiIterator, Allocator, traits>::unwind_commit,
1254 &perl_matcher<BidiIterator, Allocator, traits>::unwind_then,
1255 &perl_matcher<BidiIterator, Allocator, traits>::unwind_case,
1258 m_recursive_result = have_match;
1259 m_unwound_lookahead = false;
1260 m_unwound_alt = false;
1261 unwind_proc_type unwinder;
1264 // keep unwinding our stack until we have something to do:
1268 unwinder = s_unwind_table[m_backup_state->state_id];
1269 cont = (this->*unwinder)(m_recursive_result);
1272 // return true if we have more states to try:
1274 return pstate ? true : false;
1277 template <class BidiIterator, class Allocator, class traits>
1278 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
1280 pstate = 0; // nothing left to search
1281 return false; // end of stack nothing more to search
1284 template <class BidiIterator, class Allocator, class traits>
1285 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_case(bool)
1287 saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
1289 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1290 m_backup_state = pmp;
1294 template <class BidiIterator, class Allocator, class traits>
1295 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
1297 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
1298 // restore previous values if no match was found:
1299 if(have_match == false)
1301 m_presult->set_first(pmp->sub.first, pmp->index, pmp->index == 0);
1302 m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched, pmp->index == 0);
1304 #ifdef BOOST_REGEX_MATCH_EXTRA
1306 // we have a match, push the capture information onto the stack:
1308 else if(pmp->sub.matched && (match_extra & m_match_flags))
1309 ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
1312 m_backup_state = pmp+1;
1313 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1314 return true; // keep looking
1317 template <class BidiIterator, class Allocator, class traits>
1318 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
1320 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1321 pstate = 0; // nothing left to search
1322 return false; // end of stack nothing more to search
1325 template <class BidiIterator, class Allocator, class traits>
1326 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
1328 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
1329 pstate = pmp->pstate;
1330 position = pmp->position;
1331 bool result = (r == pmp->positive);
1332 m_recursive_result = pmp->positive ? r : !r;
1333 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1334 m_backup_state = pmp;
1335 m_unwound_lookahead = true;
1336 return !result; // return false if the assertion was matched to stop search.
1339 template <class BidiIterator, class Allocator, class traits>
1340 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
1342 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1345 pstate = pmp->pstate;
1346 position = pmp->position;
1348 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1349 m_backup_state = pmp;
1354 template <class BidiIterator, class Allocator, class traits>
1355 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
1357 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
1358 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1359 m_backup_state = pmp;
1360 return true; // keep looking
1363 template <class BidiIterator, class Allocator, class traits>
1364 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
1366 saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
1367 void* condemmed = m_stack_base;
1368 m_stack_base = pmp->base;
1369 m_backup_state = pmp->end;
1370 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1371 put_mem_block(condemmed);
1372 return true; // keep looking
1375 template <class BidiIterator, class Allocator, class traits>
1376 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
1378 saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1379 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(p++);
1383 template <class BidiIterator, class Allocator, class traits>
1384 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
1386 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1388 // if we have a match, just discard this state:
1391 destroy_single_repeat();
1395 const re_repeat* rep = pmp->rep;
1396 std::size_t count = pmp->count;
1397 BOOST_ASSERT(rep->next.p != 0);
1398 BOOST_ASSERT(rep->alt.p != 0);
1402 if((m_match_flags & match_partial) && (position == last))
1403 m_has_partial_match = true;
1405 BOOST_ASSERT(count);
1406 position = pmp->last_position;
1408 // backtrack till we can skip out:
1414 }while(count && !can_start(*position, rep->_map, mask_skip));
1416 // if we've hit base, destroy this state:
1419 destroy_single_repeat();
1420 if(!can_start(*position, rep->_map, mask_skip))
1425 pmp->count = count + rep->min;
1426 pmp->last_position = position;
1428 pstate = rep->alt.p;
1432 template <class BidiIterator, class Allocator, class traits>
1433 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1435 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1437 // if we have a match, just discard this state:
1440 destroy_single_repeat();
1444 const re_repeat* rep = pmp->rep;
1445 std::size_t count = pmp->count;
1446 BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1447 BOOST_ASSERT(rep->next.p != 0);
1448 BOOST_ASSERT(rep->alt.p != 0);
1449 BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1451 BOOST_ASSERT(count < rep->max);
1452 pstate = rep->next.p;
1453 position = pmp->last_position;
1455 if(position != last)
1457 // wind forward until we can skip out of the repeat:
1462 // failed repeat match, discard this state and look for another:
1463 destroy_single_repeat();
1468 pstate = rep->next.p;
1469 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1471 if(position == last)
1473 // can't repeat any more, remove the pushed state:
1474 destroy_single_repeat();
1475 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1476 m_has_partial_match = true;
1477 if(0 == (rep->can_be_null & mask_skip))
1480 else if(count == rep->max)
1482 // can't repeat any more, remove the pushed state:
1483 destroy_single_repeat();
1484 if(!can_start(*position, rep->_map, mask_skip))
1490 pmp->last_position = position;
1492 pstate = rep->alt.p;
1496 template <class BidiIterator, class Allocator, class traits>
1497 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1499 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1501 // if we have a match, just discard this state:
1504 destroy_single_repeat();
1508 const re_repeat* rep = pmp->rep;
1509 std::size_t count = pmp->count;
1511 BOOST_ASSERT(count < rep->max);
1512 position = pmp->last_position;
1513 if(position != last)
1516 // wind forward until we can skip out of the repeat:
1522 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1525 // remember where we got to if this is a leading repeat:
1526 if((rep->leading) && (count < rep->max))
1528 if(position == last)
1530 // can't repeat any more, remove the pushed state:
1531 destroy_single_repeat();
1532 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1533 m_has_partial_match = true;
1534 if(0 == (rep->can_be_null & mask_skip))
1537 else if(count == rep->max)
1539 // can't repeat any more, remove the pushed state:
1540 destroy_single_repeat();
1541 if(!can_start(*position, rep->_map, mask_skip))
1547 pmp->last_position = position;
1549 pstate = rep->alt.p;
1553 template <class BidiIterator, class Allocator, class traits>
1554 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1556 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1558 // if we have a match, just discard this state:
1561 destroy_single_repeat();
1565 const re_repeat* rep = pmp->rep;
1566 std::size_t count = pmp->count;
1567 pstate = rep->next.p;
1568 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1569 position = pmp->last_position;
1571 BOOST_ASSERT(rep->type == syntax_element_char_rep);
1572 BOOST_ASSERT(rep->next.p != 0);
1573 BOOST_ASSERT(rep->alt.p != 0);
1574 BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1575 BOOST_ASSERT(count < rep->max);
1577 if(position != last)
1579 // wind forward until we can skip out of the repeat:
1582 if(traits_inst.translate(*position, icase) != what)
1584 // failed repeat match, discard this state and look for another:
1585 destroy_single_repeat();
1591 pstate = rep->next.p;
1592 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1594 // remember where we got to if this is a leading repeat:
1595 if((rep->leading) && (count < rep->max))
1597 if(position == last)
1599 // can't repeat any more, remove the pushed state:
1600 destroy_single_repeat();
1601 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1602 m_has_partial_match = true;
1603 if(0 == (rep->can_be_null & mask_skip))
1606 else if(count == rep->max)
1608 // can't repeat any more, remove the pushed state:
1609 destroy_single_repeat();
1610 if(!can_start(*position, rep->_map, mask_skip))
1616 pmp->last_position = position;
1618 pstate = rep->alt.p;
1622 template <class BidiIterator, class Allocator, class traits>
1623 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1625 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1627 // if we have a match, just discard this state:
1630 destroy_single_repeat();
1634 const re_repeat* rep = pmp->rep;
1635 std::size_t count = pmp->count;
1636 pstate = rep->next.p;
1637 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1638 position = pmp->last_position;
1640 BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1641 BOOST_ASSERT(rep->next.p != 0);
1642 BOOST_ASSERT(rep->alt.p != 0);
1643 BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1644 BOOST_ASSERT(count < rep->max);
1646 if(position != last)
1648 // wind forward until we can skip out of the repeat:
1651 if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1653 // failed repeat match, discard this state and look for another:
1654 destroy_single_repeat();
1660 pstate = rep->next.p;
1661 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1663 // remember where we got to if this is a leading repeat:
1664 if((rep->leading) && (count < rep->max))
1666 if(position == last)
1668 // can't repeat any more, remove the pushed state:
1669 destroy_single_repeat();
1670 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1671 m_has_partial_match = true;
1672 if(0 == (rep->can_be_null & mask_skip))
1675 else if(count == rep->max)
1677 // can't repeat any more, remove the pushed state:
1678 destroy_single_repeat();
1679 if(!can_start(*position, rep->_map, mask_skip))
1685 pmp->last_position = position;
1687 pstate = rep->alt.p;
1691 template <class BidiIterator, class Allocator, class traits>
1692 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1694 typedef typename traits::char_class_type m_type;
1695 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1697 // if we have a match, just discard this state:
1700 destroy_single_repeat();
1704 const re_repeat* rep = pmp->rep;
1705 std::size_t count = pmp->count;
1706 pstate = rep->next.p;
1707 const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate);
1708 position = pmp->last_position;
1710 BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1711 BOOST_ASSERT(rep->next.p != 0);
1712 BOOST_ASSERT(rep->alt.p != 0);
1713 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1714 BOOST_ASSERT(count < rep->max);
1716 if(position != last)
1718 // wind forward until we can skip out of the repeat:
1721 if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1723 // failed repeat match, discard this state and look for another:
1724 destroy_single_repeat();
1730 pstate = rep->next.p;
1731 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1733 // remember where we got to if this is a leading repeat:
1734 if((rep->leading) && (count < rep->max))
1736 if(position == last)
1738 // can't repeat any more, remove the pushed state:
1739 destroy_single_repeat();
1740 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1741 m_has_partial_match = true;
1742 if(0 == (rep->can_be_null & mask_skip))
1745 else if(count == rep->max)
1747 // can't repeat any more, remove the pushed state:
1748 destroy_single_repeat();
1749 if(!can_start(*position, rep->_map, mask_skip))
1755 pmp->last_position = position;
1757 pstate = rep->alt.p;
1761 template <class BidiIterator, class Allocator, class traits>
1762 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1764 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1767 position = pmp->position;
1768 pstate = pmp->pstate;
1771 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1772 m_backup_state = pmp;
1776 template <class BidiIterator, class Allocator, class traits>
1777 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion(bool r)
1779 // We are backtracking back inside a recursion, need to push the info
1780 // back onto the recursion stack, and do so unconditionally, otherwise
1781 // we can get mismatched pushes and pops...
1782 saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
1785 recursion_stack.push_back(recursion_info<results_type>());
1786 recursion_stack.back().idx = pmp->recursion_id;
1787 recursion_stack.back().preturn_address = pmp->preturn_address;
1788 recursion_stack.back().results = pmp->prior_results;
1789 recursion_stack.back().location_of_start = position;
1790 *m_presult = pmp->internal_results;
1792 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1793 m_backup_state = pmp;
1797 template <class BidiIterator, class Allocator, class traits>
1798 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop(bool r)
1800 // Backtracking out of a recursion, we must pop state off the recursion
1801 // stack unconditionally to ensure matched pushes and pops:
1802 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1803 if (!r && !recursion_stack.empty())
1805 *m_presult = recursion_stack.back().results;
1806 position = recursion_stack.back().location_of_start;
1807 recursion_stack.pop_back();
1809 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1810 m_backup_state = pmp;
1814 template <class BidiIterator, class Allocator, class traits>
1815 void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_pop()
1817 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1819 if(pmp < m_stack_base)
1822 pmp = static_cast<saved_state*>(m_backup_state);
1825 (void) new (pmp)saved_state(15);
1826 m_backup_state = pmp;
1829 template <class BidiIterator, class Allocator, class traits>
1830 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_commit(bool b)
1832 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1833 while(unwind(b) && !m_unwound_lookahead){}
1834 if(m_unwound_lookahead && pstate)
1837 // If we stop because we just unwound an assertion, put the
1838 // commit state back on the stack again:
1840 m_unwound_lookahead = false;
1841 saved_state* pmp = m_backup_state;
1843 if(pmp < m_stack_base)
1846 pmp = m_backup_state;
1849 (void) new (pmp)saved_state(16);
1850 m_backup_state = pmp;
1852 // This prevents us from stopping when we exit from an independent sub-expression:
1853 m_independent = false;
1857 template <class BidiIterator, class Allocator, class traits>
1858 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_then(bool b)
1860 // Unwind everything till we hit an alternative:
1861 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1862 bool result = false;
1863 while((result = unwind(b)) && !m_unwound_alt){}
1864 // We're now pointing at the next alternative, need one more backtrack
1865 // since *all* the other alternatives must fail once we've reached a THEN clause:
1866 if(result && m_unwound_alt)
1872 template <class BidiIterator, class Allocator, class traits>
1873 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_pop(bool r)
1875 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1878 --parenthesis_stack_position;
1880 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1881 m_backup_state = pmp;
1885 template <class BidiIterator, class Allocator, class traits>
1886 void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_pop()
1888 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1890 if(pmp < m_stack_base)
1893 pmp = static_cast<saved_state*>(m_backup_state);
1896 (void) new (pmp)saved_state(16);
1897 m_backup_state = pmp;
1900 template <class BidiIterator, class Allocator, class traits>
1901 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_push(bool r)
1903 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1906 parenthesis_stack[parenthesis_stack_position++] = pmp->position;
1908 boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1909 m_backup_state = pmp;
1913 template <class BidiIterator, class Allocator, class traits>
1914 inline void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_push(BidiIterator p)
1916 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1918 if(pmp < m_stack_base)
1921 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1924 (void) new (pmp)saved_position<BidiIterator>(0, p, 17);
1925 m_backup_state = pmp;
1928 } // namespace BOOST_REGEX_DETAIL_NS
1929 } // namespace boost
1932 # pragma warning(pop)
1936 #pragma warning(push)
1937 #pragma warning(disable: 4103)
1939 #ifdef BOOST_HAS_ABI_HEADERS
1940 # include BOOST_ABI_SUFFIX
1943 #pragma warning(pop)