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
43 // this padding ensures correct alignment on 64-bit platforms:
45 std::ptrdiff_t padding2;
48 saved_state(unsigned i) : id(i) {}
51 template <class BidiIterator>
52 struct saved_matched_paren : public saved_state
55 sub_match<BidiIterator> sub;
56 saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){};
59 template <class BidiIterator>
60 struct saved_position : public saved_state
62 const re_syntax_base* pstate;
63 BidiIterator position;
64 saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){};
67 template <class BidiIterator>
68 struct saved_assertion : public saved_position<BidiIterator>
71 saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
72 : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){};
75 template <class BidiIterator>
76 struct saved_repeater : public saved_state
78 repeater_count<BidiIterator> count;
79 saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start)
80 : saved_state(saved_state_repeater_count), count(i,s,start){}
83 struct saved_extra_block : public saved_state
85 saved_state *base, *end;
86 saved_extra_block(saved_state* b, saved_state* e)
87 : saved_state(saved_state_extra_block), base(b), end(e) {}
90 struct save_state_init
93 save_state_init(saved_state** base, saved_state** end)
96 *base = static_cast<saved_state*>(get_mem_block());
97 *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
99 (void) new (*end)saved_state(0);
100 BOOST_ASSERT(*end > *base);
104 put_mem_block(*stack);
109 template <class BidiIterator>
110 struct saved_single_repeat : public saved_state
113 const re_repeat* rep;
114 BidiIterator last_position;
115 saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
116 : saved_state(arg_id), count(c), rep(r), last_position(lp){}
119 template <class BidiIterator, class Allocator, class traits>
120 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
122 static matcher_proc_type const s_match_vtable[29] =
124 (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
125 &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
126 &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
127 &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
128 &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
129 &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
130 &perl_matcher<BidiIterator, Allocator, traits>::match_match,
131 &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
132 &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
133 &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
134 &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
135 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
136 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
137 &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
138 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
139 &perl_matcher<BidiIterator, Allocator, traits>::match_set,
140 &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
141 &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
142 &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
143 &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
144 &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
145 &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
146 (::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),
147 &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
148 &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
149 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
150 &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
151 &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
152 &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
155 push_recursion_stopper();
159 matcher_proc_type proc = s_match_vtable[pstate->type];
163 if(state_count > max_state_count)
164 raise_error(traits_inst, regex_constants::error_space);
165 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
166 m_has_partial_match = true;
167 bool successful_unwind = unwind(false);
168 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
169 m_has_partial_match = true;
170 if(false == successful_unwind)
171 return m_recursive_result;
174 }while(unwind(true));
175 return m_recursive_result;
178 template <class BidiIterator, class Allocator, class traits>
179 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
184 saved_state* stack_base;
185 saved_state* backup_state;
186 stack_base = static_cast<saved_state*>(get_mem_block());
187 backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
188 saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
190 (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
191 m_stack_base = stack_base;
192 m_backup_state = block;
195 raise_error(traits_inst, regex_constants::error_size);
198 template <class BidiIterator, class Allocator, class traits>
199 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
202 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
204 if(pmp < m_stack_base)
207 pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
210 (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
211 m_backup_state = pmp;
214 template <class BidiIterator, class Allocator, class traits>
215 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
217 saved_state* pmp = m_backup_state;
219 if(pmp < m_stack_base)
222 pmp = m_backup_state;
225 (void) new (pmp)saved_state(saved_type_recurse);
226 m_backup_state = pmp;
229 template <class BidiIterator, class Allocator, class traits>
230 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
232 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
234 if(pmp < m_stack_base)
237 pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
240 (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
241 m_backup_state = pmp;
244 template <class BidiIterator, class Allocator, class traits>
245 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
247 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
249 if(pmp < m_stack_base)
252 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
255 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
256 m_backup_state = pmp;
259 template <class BidiIterator, class Allocator, class traits>
260 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
262 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
264 if(pmp < m_stack_base)
267 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
270 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
271 m_backup_state = pmp;
274 template <class BidiIterator, class Allocator, class traits>
275 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
277 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
279 if(pmp < m_stack_base)
282 pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
285 (void) new (pmp)saved_repeater<BidiIterator>(i, s, position);
286 m_backup_state = pmp;
289 template <class BidiIterator, class Allocator, class traits>
290 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int id)
292 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
294 if(pmp < m_stack_base)
297 pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
300 (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, id);
301 m_backup_state = pmp;
304 template <class BidiIterator, class Allocator, class traits>
305 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
307 int index = static_cast<const re_brace*>(pstate)->index;
311 pstate = pstate->next.p;
316 // forward lookahead assert:
317 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
318 pstate = pstate->next.p->next.p;
319 push_assertion(next_pstate, index == -1);
324 // independent sub-expression, currently this is always recursive:
325 bool old_independent = m_independent;
326 m_independent = true;
327 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
328 pstate = pstate->next.p->next.p;
329 bool r = match_all_states();
330 pstate = next_pstate;
331 m_independent = old_independent;
332 #ifdef BOOST_REGEX_MATCH_EXTRA
333 if(r && (m_match_flags & match_extra))
336 // our captures have been stored in *m_presult
337 // we need to unpack them, and insert them
338 // back in the right order when we unwind the stack:
340 match_results<BidiIterator, Allocator> temp_match(*m_presult);
342 for(i = 0; i < temp_match.size(); ++i)
343 (*m_presult)[i].get_captures().clear();
344 // match everything else:
345 r = match_all_states();
346 // now place the stored captures back:
347 for(i = 0; i < temp_match.size(); ++i)
349 typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
350 seq& s1 = (*m_presult)[i].get_captures();
351 const seq& s2 = temp_match[i].captures();
363 // conditional expression:
364 const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
365 BOOST_ASSERT(alt->type == syntax_element_alt);
366 pstate = alt->next.p;
367 if(pstate->type == syntax_element_assert_backref)
369 if(!match_assert_backref())
375 // zero width assertion, have to match this recursively:
376 BOOST_ASSERT(pstate->type == syntax_element_startmark);
377 bool negated = static_cast<const re_brace*>(pstate)->index == -2;
378 BidiIterator saved_position = position;
379 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
380 pstate = pstate->next.p->next.p;
381 bool r = match_all_states();
382 position = saved_position;
386 pstate = next_pstate;
394 BOOST_ASSERT(index > 0);
395 if((m_match_flags & match_nosubs) == 0)
397 push_matched_paren(index, (*m_presult)[index]);
398 m_presult->set_first(position, index);
400 pstate = pstate->next.p;
407 template <class BidiIterator, class Allocator, class traits>
408 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
410 bool take_first, take_second;
411 const re_alt* jmp = static_cast<const re_alt*>(pstate);
413 // find out which of these two alternatives we need to take:
416 take_first = jmp->can_be_null & mask_take;
417 take_second = jmp->can_be_null & mask_skip;
421 take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
422 take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
427 // we can take the first alternative,
428 // see if we need to push next alternative:
431 push_alt(jmp->alt.p);
433 pstate = pstate->next.p;
441 return false; // neither option is possible
444 template <class BidiIterator, class Allocator, class traits>
445 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
448 #pragma warning(push)
449 #pragma warning(disable:4127 4244)
452 #pragma option push -w-8008 -w-8066 -w-8004
454 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
456 // find out which of these two alternatives we need to take:
457 bool take_first, take_second;
460 take_first = rep->can_be_null & mask_take;
461 take_second = rep->can_be_null & mask_skip;
465 take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
466 take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
469 if(take_first || (next_count->get_id() != rep->id))
471 // we're moving to a different repeat from the last
472 // one, so set up a counter object:
473 push_repeater_count(rep->id, &next_count);
476 // If we've had at least one repeat already, and the last one
477 // matched the NULL string then set the repeat count to
480 next_count->check_null_repeat(position, rep->max);
482 if(next_count->get_count() < rep->min)
484 // we must take the repeat:
487 // increase the counter:
489 pstate = rep->next.p;
495 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
498 // try and take the repeat if we can:
499 if((next_count->get_count() < rep->max) && take_first)
503 // store position in case we fail:
504 push_alt(rep->alt.p);
506 // increase the counter:
508 pstate = rep->next.p;
516 return false; // can't take anything, fail...
520 // try and skip the repeat if we can:
523 if((next_count->get_count() < rep->max) && take_first)
525 // store position in case we fail:
526 push_non_greedy_repeat(rep->next.p);
531 if((next_count->get_count() < rep->max) && take_first)
533 // increase the counter:
535 pstate = rep->next.p;
548 template <class BidiIterator, class Allocator, class traits>
549 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
552 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
553 re_syntax_base* psingle = rep->next.p;
554 // match compulsary repeats first:
555 while(count < rep->min)
562 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
565 // repeat for as long as we can:
566 while(count < rep->max)
573 // remember where we got to if this is a leading repeat:
574 if((rep->leading) && (count < rep->max))
576 // push backtrack info if available:
578 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
579 // jump to next state:
585 // non-greedy, push state and return true if we can skip:
587 push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
589 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
593 template <class BidiIterator, class Allocator, class traits>
594 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
596 if(m_match_flags & match_not_dot_null)
597 return match_dot_repeat_slow();
598 if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
599 return match_dot_repeat_slow();
601 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
602 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
603 unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::re_detail::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));
607 return false; // not enough text left to match
609 std::advance(position, count);
613 if((rep->leading) && (count < rep->max))
615 // push backtrack info if available:
617 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
618 // jump to next state:
624 // non-greedy, push state and return true if we can skip:
626 push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
628 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
632 template <class BidiIterator, class Allocator, class traits>
633 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
636 #pragma warning(push)
637 #pragma warning(disable:4127)
640 #pragma option push -w-8008 -w-8066 -w-8004
642 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
643 BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
644 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
645 std::size_t count = 0;
647 // start by working out how much we can skip:
649 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
650 std::size_t desired = greedy ? rep->max : rep->min;
651 if(::boost::is_random_access_iterator<BidiIterator>::value)
653 BidiIterator end = position;
654 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
655 BidiIterator origin(position);
656 while((position != end) && (traits_inst.translate(*position, icase) == what))
660 count = (unsigned)::boost::re_detail::distance(origin, position);
664 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
676 if((rep->leading) && (count < rep->max))
678 // push backtrack info if available:
680 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
681 // jump to next state:
687 // non-greedy, push state and return true if we can skip:
689 push_single_repeat(count, rep, position, saved_state_rep_char);
691 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
701 template <class BidiIterator, class Allocator, class traits>
702 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
705 #pragma warning(push)
706 #pragma warning(disable:4127)
709 #pragma option push -w-8008 -w-8066 -w-8004
711 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
712 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
713 std::size_t count = 0;
715 // start by working out how much we can skip:
717 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
718 std::size_t desired = greedy ? rep->max : rep->min;
719 if(::boost::is_random_access_iterator<BidiIterator>::value)
721 BidiIterator end = position;
722 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
723 BidiIterator origin(position);
724 while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
728 count = (unsigned)::boost::re_detail::distance(origin, position);
732 while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
744 if((rep->leading) && (count < rep->max))
746 // push backtrack info if available:
748 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
749 // jump to next state:
755 // non-greedy, push state and return true if we can skip:
757 push_single_repeat(count, rep, position, saved_state_rep_short_set);
759 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
769 template <class BidiIterator, class Allocator, class traits>
770 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
773 #pragma warning(push)
774 #pragma warning(disable:4127)
777 #pragma option push -w-8008 -w-8066 -w-8004
779 typedef typename traits::char_class_type mask_type;
780 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
781 const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate->next.p);
782 std::size_t count = 0;
784 // start by working out how much we can skip:
786 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
787 std::size_t desired = greedy ? rep->max : rep->min;
788 if(::boost::is_random_access_iterator<BidiIterator>::value)
790 BidiIterator end = position;
791 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
792 BidiIterator origin(position);
793 while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
797 count = (unsigned)::boost::re_detail::distance(origin, position);
801 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
813 if((rep->leading) && (count < rep->max))
815 // push backtrack info if available:
817 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
818 // jump to next state:
824 // non-greedy, push state and return true if we can skip:
826 push_single_repeat(count, rep, position, saved_state_rep_long_set);
828 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
838 /****************************************************************************
840 Unwind and associated proceedures follow, these perform what normal stack
841 unwinding does in the recursive implementation.
843 ****************************************************************************/
845 template <class BidiIterator, class Allocator, class traits>
846 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
848 static unwind_proc_type const s_unwind_table[14] =
850 &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
851 &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
852 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
853 &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
854 &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
855 &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
856 &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
857 &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
858 &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
859 &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
860 &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
861 &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
862 &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
863 &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
866 m_recursive_result = have_match;
867 unwind_proc_type unwinder;
870 // keep unwinding our stack until we have something to do:
874 unwinder = s_unwind_table[m_backup_state->id];
875 cont = (this->*unwinder)(m_recursive_result);
878 // return true if we have more states to try:
880 return pstate ? true : false;
883 template <class BidiIterator, class Allocator, class traits>
884 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
886 pstate = 0; // nothing left to search
887 return false; // end of stack nothing more to search
890 template <class BidiIterator, class Allocator, class traits>
891 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
893 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
894 // restore previous values if no match was found:
895 if(have_match == false)
897 m_presult->set_first(pmp->sub.first, pmp->index);
898 m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched);
900 #ifdef BOOST_REGEX_MATCH_EXTRA
902 // we have a match, push the capture information onto the stack:
904 else if(pmp->sub.matched && (match_extra & m_match_flags))
905 ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
908 m_backup_state = pmp+1;
909 boost::re_detail::inplace_destroy(pmp);
910 return true; // keep looking
913 template <class BidiIterator, class Allocator, class traits>
914 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
916 boost::re_detail::inplace_destroy(m_backup_state++);
917 pstate = 0; // nothing left to search
918 return false; // end of stack nothing more to search
921 template <class BidiIterator, class Allocator, class traits>
922 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
924 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
925 pstate = pmp->pstate;
926 position = pmp->position;
927 bool result = (r == pmp->positive);
928 m_recursive_result = pmp->positive ? r : !r;
929 boost::re_detail::inplace_destroy(pmp++);
930 m_backup_state = pmp;
931 return !result; // return false if the assertion was matched to stop search.
934 template <class BidiIterator, class Allocator, class traits>
935 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
937 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
940 pstate = pmp->pstate;
941 position = pmp->position;
943 boost::re_detail::inplace_destroy(pmp++);
944 m_backup_state = pmp;
948 template <class BidiIterator, class Allocator, class traits>
949 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
951 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
952 boost::re_detail::inplace_destroy(pmp++);
953 m_backup_state = pmp;
954 return true; // keep looking
957 template <class BidiIterator, class Allocator, class traits>
958 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
960 saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
961 void* condemmed = m_stack_base;
962 m_stack_base = pmp->base;
963 m_backup_state = pmp->end;
964 boost::re_detail::inplace_destroy(pmp);
965 put_mem_block(condemmed);
966 return true; // keep looking
969 template <class BidiIterator, class Allocator, class traits>
970 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
972 saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
973 boost::re_detail::inplace_destroy(p++);
977 template <class BidiIterator, class Allocator, class traits>
978 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
980 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
982 // if we have a match, just discard this state:
985 destroy_single_repeat();
989 const re_repeat* rep = pmp->rep;
990 std::size_t count = pmp->count;
991 BOOST_ASSERT(rep->next.p != 0);
992 BOOST_ASSERT(rep->alt.p != 0);
996 if((m_match_flags & match_partial) && (position == last))
997 m_has_partial_match = true;
1000 position = pmp->last_position;
1002 // backtrack till we can skip out:
1008 }while(count && !can_start(*position, rep->_map, mask_skip));
1010 // if we've hit base, destroy this state:
1013 destroy_single_repeat();
1014 if(!can_start(*position, rep->_map, mask_skip))
1019 pmp->count = count + rep->min;
1020 pmp->last_position = position;
1022 pstate = rep->alt.p;
1026 template <class BidiIterator, class Allocator, class traits>
1027 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1029 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1031 // if we have a match, just discard this state:
1034 destroy_single_repeat();
1038 const re_repeat* rep = pmp->rep;
1039 std::size_t count = pmp->count;
1040 BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1041 BOOST_ASSERT(rep->next.p != 0);
1042 BOOST_ASSERT(rep->alt.p != 0);
1043 BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1045 BOOST_ASSERT(count < rep->max);
1046 pstate = rep->next.p;
1047 position = pmp->last_position;
1049 if(position != last)
1051 // wind forward until we can skip out of the repeat:
1056 // failed repeat match, discard this state and look for another:
1057 destroy_single_repeat();
1062 pstate = rep->next.p;
1063 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1065 if(position == last)
1067 // can't repeat any more, remove the pushed state:
1068 destroy_single_repeat();
1069 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1070 m_has_partial_match = true;
1071 if(0 == (rep->can_be_null & mask_skip))
1074 else if(count == rep->max)
1076 // can't repeat any more, remove the pushed state:
1077 destroy_single_repeat();
1078 if(!can_start(*position, rep->_map, mask_skip))
1084 pmp->last_position = position;
1086 pstate = rep->alt.p;
1090 template <class BidiIterator, class Allocator, class traits>
1091 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1093 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1095 // if we have a match, just discard this state:
1098 destroy_single_repeat();
1102 const re_repeat* rep = pmp->rep;
1103 std::size_t count = pmp->count;
1105 BOOST_ASSERT(count < rep->max);
1106 position = pmp->last_position;
1107 if(position != last)
1110 // wind forward until we can skip out of the repeat:
1116 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1119 if(position == last)
1121 // can't repeat any more, remove the pushed state:
1122 destroy_single_repeat();
1123 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1124 m_has_partial_match = true;
1125 if(0 == (rep->can_be_null & mask_skip))
1128 else if(count == rep->max)
1130 // can't repeat any more, remove the pushed state:
1131 destroy_single_repeat();
1132 if(!can_start(*position, rep->_map, mask_skip))
1138 pmp->last_position = position;
1140 pstate = rep->alt.p;
1144 template <class BidiIterator, class Allocator, class traits>
1145 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1147 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1149 // if we have a match, just discard this state:
1152 destroy_single_repeat();
1156 const re_repeat* rep = pmp->rep;
1157 std::size_t count = pmp->count;
1158 pstate = rep->next.p;
1159 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1160 position = pmp->last_position;
1162 BOOST_ASSERT(rep->type == syntax_element_char_rep);
1163 BOOST_ASSERT(rep->next.p != 0);
1164 BOOST_ASSERT(rep->alt.p != 0);
1165 BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1166 BOOST_ASSERT(count < rep->max);
1168 if(position != last)
1170 // wind forward until we can skip out of the repeat:
1173 if(traits_inst.translate(*position, icase) != what)
1175 // failed repeat match, discard this state and look for another:
1176 destroy_single_repeat();
1182 pstate = rep->next.p;
1183 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1185 if(position == last)
1187 // can't repeat any more, remove the pushed state:
1188 destroy_single_repeat();
1189 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1190 m_has_partial_match = true;
1191 if(0 == (rep->can_be_null & mask_skip))
1194 else if(count == rep->max)
1196 // can't repeat any more, remove the pushed state:
1197 destroy_single_repeat();
1198 if(!can_start(*position, rep->_map, mask_skip))
1204 pmp->last_position = position;
1206 pstate = rep->alt.p;
1210 template <class BidiIterator, class Allocator, class traits>
1211 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1213 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1215 // if we have a match, just discard this state:
1218 destroy_single_repeat();
1222 const re_repeat* rep = pmp->rep;
1223 std::size_t count = pmp->count;
1224 pstate = rep->next.p;
1225 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1226 position = pmp->last_position;
1228 BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1229 BOOST_ASSERT(rep->next.p != 0);
1230 BOOST_ASSERT(rep->alt.p != 0);
1231 BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1232 BOOST_ASSERT(count < rep->max);
1234 if(position != last)
1236 // wind forward until we can skip out of the repeat:
1239 if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1241 // failed repeat match, discard this state and look for another:
1242 destroy_single_repeat();
1248 pstate = rep->next.p;
1249 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1251 if(position == last)
1253 // can't repeat any more, remove the pushed state:
1254 destroy_single_repeat();
1255 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1256 m_has_partial_match = true;
1257 if(0 == (rep->can_be_null & mask_skip))
1260 else if(count == rep->max)
1262 // can't repeat any more, remove the pushed state:
1263 destroy_single_repeat();
1264 if(!can_start(*position, rep->_map, mask_skip))
1270 pmp->last_position = position;
1272 pstate = rep->alt.p;
1276 template <class BidiIterator, class Allocator, class traits>
1277 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1279 typedef typename traits::char_class_type mask_type;
1280 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1282 // if we have a match, just discard this state:
1285 destroy_single_repeat();
1289 const re_repeat* rep = pmp->rep;
1290 std::size_t count = pmp->count;
1291 pstate = rep->next.p;
1292 const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate);
1293 position = pmp->last_position;
1295 BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1296 BOOST_ASSERT(rep->next.p != 0);
1297 BOOST_ASSERT(rep->alt.p != 0);
1298 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1299 BOOST_ASSERT(count < rep->max);
1301 if(position != last)
1303 // wind forward until we can skip out of the repeat:
1306 if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1308 // failed repeat match, discard this state and look for another:
1309 destroy_single_repeat();
1315 pstate = rep->next.p;
1316 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1318 if(position == last)
1320 // can't repeat any more, remove the pushed state:
1321 destroy_single_repeat();
1322 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1323 m_has_partial_match = true;
1324 if(0 == (rep->can_be_null & mask_skip))
1327 else if(count == rep->max)
1329 // can't repeat any more, remove the pushed state:
1330 destroy_single_repeat();
1331 if(!can_start(*position, rep->_map, mask_skip))
1337 pmp->last_position = position;
1339 pstate = rep->alt.p;
1343 template <class BidiIterator, class Allocator, class traits>
1344 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1346 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1349 position = pmp->position;
1350 pstate = pmp->pstate;
1353 boost::re_detail::inplace_destroy(pmp++);
1354 m_backup_state = pmp;
1358 } // namespace re_detail
1359 } // namespace boost
1361 #ifdef BOOST_HAS_ABI_HEADERS
1362 # include BOOST_ABI_SUFFIX