6 * Use, modification and distribution are subject to the
7 * Boost Software License, Version 1.0. (See accompanying file
8 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
13 * LOCATION: see http://www.boost.org for most recent version.
14 * FILE perl_matcher_common.cpp
15 * VERSION see <boost/version.hpp>
16 * DESCRIPTION: Definitions of perl_matcher member functions that are
17 * specific to the non-recursive implementation.
20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP
21 #define BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP
27 #pragma warning(disable: 4103)
29 #ifdef BOOST_HAS_ABI_HEADERS
30 # include BOOST_ABI_PREFIX
36 # pragma warning(push)
37 # pragma warning(disable: 4800)
44 inline void inplace_destroy(T* p)
46 (void)p; // warning suppression
53 unsigned int state_id;
54 // this padding ensures correct alignment on 64-bit platforms:
56 std::ptrdiff_t padding2;
59 saved_state(unsigned i) : state_id(i) {}
62 template <class BidiIterator>
63 struct saved_matched_paren : public saved_state
66 sub_match<BidiIterator> sub;
67 saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){};
70 template <class BidiIterator>
71 struct saved_position : public saved_state
73 const re_syntax_base* pstate;
74 BidiIterator position;
75 saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){};
78 template <class BidiIterator>
79 struct saved_assertion : public saved_position<BidiIterator>
82 saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
83 : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){};
86 template <class BidiIterator>
87 struct saved_repeater : public saved_state
89 repeater_count<BidiIterator> count;
90 saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start)
91 : saved_state(saved_state_repeater_count), count(i,s,start){}
94 struct saved_extra_block : public saved_state
96 saved_state *base, *end;
97 saved_extra_block(saved_state* b, saved_state* e)
98 : saved_state(saved_state_extra_block), base(b), end(e) {}
101 struct save_state_init
104 save_state_init(saved_state** base, saved_state** end)
107 *base = static_cast<saved_state*>(get_mem_block());
108 *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
110 (void) new (*end)saved_state(0);
111 BOOST_ASSERT(*end > *base);
115 put_mem_block(*stack);
120 template <class BidiIterator>
121 struct saved_single_repeat : public saved_state
124 const re_repeat* rep;
125 BidiIterator last_position;
126 saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
127 : saved_state(arg_id), count(c), rep(r), last_position(lp){}
130 template <class Results>
131 struct saved_recursion : public saved_state
133 saved_recursion(int id, const re_syntax_base* p, Results* pr)
134 : saved_state(14), recursion_id(id), preturn_address(p), results(*pr)
137 const re_syntax_base* preturn_address;
141 template <class BidiIterator, class Allocator, class traits>
142 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
144 static matcher_proc_type const s_match_vtable[30] =
146 (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
147 &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
148 &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
149 &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
150 &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
151 &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
152 &perl_matcher<BidiIterator, Allocator, traits>::match_match,
153 &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
154 &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
155 &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
156 &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
157 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
158 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
159 &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
160 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
161 &perl_matcher<BidiIterator, Allocator, traits>::match_set,
162 &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
163 &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
164 &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
165 &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
166 &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
167 &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
168 // Although this next line *should* be evaluated at compile time, in practice
169 // some compilers (VC++) emit run-time initialisation which breaks thread
170 // safety, so use a dispatch function instead:
171 //(::boost::is_random_access_iterator<BidiIterator>::value ? &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast : &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow),
172 &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
173 &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
174 &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
175 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
176 &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
177 &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
178 &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
179 &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
182 push_recursion_stopper();
186 matcher_proc_type proc = s_match_vtable[pstate->type];
190 if(state_count > max_state_count)
191 raise_error(traits_inst, regex_constants::error_complexity);
192 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
193 m_has_partial_match = true;
194 bool successful_unwind = unwind(false);
195 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
196 m_has_partial_match = true;
197 if(false == successful_unwind)
198 return m_recursive_result;
201 }while(unwind(true));
202 return m_recursive_result;
205 template <class BidiIterator, class Allocator, class traits>
206 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
211 saved_state* stack_base;
212 saved_state* backup_state;
213 stack_base = static_cast<saved_state*>(get_mem_block());
214 backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
215 saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
217 (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
218 m_stack_base = stack_base;
219 m_backup_state = block;
222 raise_error(traits_inst, regex_constants::error_stack);
225 template <class BidiIterator, class Allocator, class traits>
226 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
228 //BOOST_ASSERT(index);
229 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
231 if(pmp < m_stack_base)
234 pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
237 (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
238 m_backup_state = pmp;
241 template <class BidiIterator, class Allocator, class traits>
242 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
244 saved_state* pmp = m_backup_state;
246 if(pmp < m_stack_base)
249 pmp = m_backup_state;
252 (void) new (pmp)saved_state(saved_type_recurse);
253 m_backup_state = pmp;
256 template <class BidiIterator, class Allocator, class traits>
257 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
259 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
261 if(pmp < m_stack_base)
264 pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
267 (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
268 m_backup_state = pmp;
271 template <class BidiIterator, class Allocator, class traits>
272 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
274 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
276 if(pmp < m_stack_base)
279 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
282 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
283 m_backup_state = pmp;
286 template <class BidiIterator, class Allocator, class traits>
287 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
289 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
291 if(pmp < m_stack_base)
294 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
297 (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
298 m_backup_state = pmp;
301 template <class BidiIterator, class Allocator, class traits>
302 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
304 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
306 if(pmp < m_stack_base)
309 pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
312 (void) new (pmp)saved_repeater<BidiIterator>(i, s, position);
313 m_backup_state = pmp;
316 template <class BidiIterator, class Allocator, class traits>
317 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
319 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
321 if(pmp < m_stack_base)
324 pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
327 (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
328 m_backup_state = pmp;
331 template <class BidiIterator, class Allocator, class traits>
332 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion(int id, const re_syntax_base* p, results_type* presults)
334 saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
336 if(pmp < m_stack_base)
339 pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
342 (void) new (pmp)saved_recursion<results_type>(id, p, presults);
343 m_backup_state = pmp;
346 template <class BidiIterator, class Allocator, class traits>
347 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
349 int index = static_cast<const re_brace*>(pstate)->index;
350 icase = static_cast<const re_brace*>(pstate)->icase;
354 pstate = pstate->next.p;
359 // forward lookahead assert:
360 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
361 pstate = pstate->next.p->next.p;
362 push_assertion(next_pstate, index == -1);
367 // independent sub-expression, currently this is always recursive:
368 bool old_independent = m_independent;
369 m_independent = true;
370 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
371 pstate = pstate->next.p->next.p;
372 bool r = match_all_states();
373 pstate = next_pstate;
374 m_independent = old_independent;
375 #ifdef BOOST_REGEX_MATCH_EXTRA
376 if(r && (m_match_flags & match_extra))
379 // our captures have been stored in *m_presult
380 // we need to unpack them, and insert them
381 // back in the right order when we unwind the stack:
383 match_results<BidiIterator, Allocator> temp_match(*m_presult);
385 for(i = 0; i < temp_match.size(); ++i)
386 (*m_presult)[i].get_captures().clear();
387 // match everything else:
388 r = match_all_states();
389 // now place the stored captures back:
390 for(i = 0; i < temp_match.size(); ++i)
392 typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
393 seq& s1 = (*m_presult)[i].get_captures();
394 const seq& s2 = temp_match[i].captures();
406 // conditional expression:
407 const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
408 BOOST_ASSERT(alt->type == syntax_element_alt);
409 pstate = alt->next.p;
410 if(pstate->type == syntax_element_assert_backref)
412 if(!match_assert_backref())
418 // zero width assertion, have to match this recursively:
419 BOOST_ASSERT(pstate->type == syntax_element_startmark);
420 bool negated = static_cast<const re_brace*>(pstate)->index == -2;
421 BidiIterator saved_position = position;
422 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
423 pstate = pstate->next.p->next.p;
424 bool r = match_all_states();
425 position = saved_position;
429 pstate = next_pstate;
437 push_matched_paren(0, (*m_presult)[0]);
438 m_presult->set_first(position, 0, true);
439 pstate = pstate->next.p;
444 BOOST_ASSERT(index > 0);
445 if((m_match_flags & match_nosubs) == 0)
447 push_matched_paren(index, (*m_presult)[index]);
448 m_presult->set_first(position, index);
450 pstate = pstate->next.p;
457 template <class BidiIterator, class Allocator, class traits>
458 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
460 bool take_first, take_second;
461 const re_alt* jmp = static_cast<const re_alt*>(pstate);
463 // find out which of these two alternatives we need to take:
466 take_first = jmp->can_be_null & mask_take;
467 take_second = jmp->can_be_null & mask_skip;
471 take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
472 take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
477 // we can take the first alternative,
478 // see if we need to push next alternative:
481 push_alt(jmp->alt.p);
483 pstate = pstate->next.p;
491 return false; // neither option is possible
494 template <class BidiIterator, class Allocator, class traits>
495 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
498 #pragma warning(push)
499 #pragma warning(disable:4127 4244)
502 #pragma option push -w-8008 -w-8066 -w-8004
504 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
506 // find out which of these two alternatives we need to take:
507 bool take_first, take_second;
510 take_first = rep->can_be_null & mask_take;
511 take_second = rep->can_be_null & mask_skip;
515 take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
516 take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
519 if((m_backup_state->state_id != saved_state_repeater_count)
520 || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
521 || (next_count->get_id() != rep->state_id))
523 // we're moving to a different repeat from the last
524 // one, so set up a counter object:
525 push_repeater_count(rep->state_id, &next_count);
528 // If we've had at least one repeat already, and the last one
529 // matched the NULL string then set the repeat count to
532 next_count->check_null_repeat(position, rep->max);
534 if(next_count->get_count() < rep->min)
536 // we must take the repeat:
539 // increase the counter:
541 pstate = rep->next.p;
547 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
550 // try and take the repeat if we can:
551 if((next_count->get_count() < rep->max) && take_first)
555 // store position in case we fail:
556 push_alt(rep->alt.p);
558 // increase the counter:
560 pstate = rep->next.p;
568 return false; // can't take anything, fail...
572 // try and skip the repeat if we can:
575 if((next_count->get_count() < rep->max) && take_first)
577 // store position in case we fail:
578 push_non_greedy_repeat(rep->next.p);
583 if((next_count->get_count() < rep->max) && take_first)
585 // increase the counter:
587 pstate = rep->next.p;
600 template <class BidiIterator, class Allocator, class traits>
601 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
604 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
605 re_syntax_base* psingle = rep->next.p;
606 // match compulsary repeats first:
607 while(count < rep->min)
614 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
617 // repeat for as long as we can:
618 while(count < rep->max)
625 // remember where we got to if this is a leading repeat:
626 if((rep->leading) && (count < rep->max))
628 // push backtrack info if available:
630 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
631 // jump to next state:
637 // non-greedy, push state and return true if we can skip:
639 push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
641 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
645 template <class BidiIterator, class Allocator, class traits>
646 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
648 if(m_match_flags & match_not_dot_null)
649 return match_dot_repeat_slow();
650 if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
651 return match_dot_repeat_slow();
653 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
654 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
655 unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::re_detail::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));
659 return false; // not enough text left to match
661 std::advance(position, count);
665 if((rep->leading) && (count < rep->max))
667 // push backtrack info if available:
669 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
670 // jump to next state:
676 // non-greedy, push state and return true if we can skip:
678 push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
680 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
684 template <class BidiIterator, class Allocator, class traits>
685 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
688 #pragma warning(push)
689 #pragma warning(disable:4127)
692 #pragma option push -w-8008 -w-8066 -w-8004
694 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
695 BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
696 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
697 std::size_t count = 0;
699 // start by working out how much we can skip:
701 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
702 std::size_t desired = greedy ? rep->max : rep->min;
703 if(::boost::is_random_access_iterator<BidiIterator>::value)
705 BidiIterator end = position;
706 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
707 BidiIterator origin(position);
708 while((position != end) && (traits_inst.translate(*position, icase) == what))
712 count = (unsigned)::boost::re_detail::distance(origin, position);
716 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
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_char);
743 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
753 template <class BidiIterator, class Allocator, class traits>
754 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
757 #pragma warning(push)
758 #pragma warning(disable:4127)
761 #pragma option push -w-8008 -w-8066 -w-8004
763 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
764 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
765 std::size_t count = 0;
767 // start by working out how much we can skip:
769 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
770 std::size_t desired = greedy ? rep->max : rep->min;
771 if(::boost::is_random_access_iterator<BidiIterator>::value)
773 BidiIterator end = position;
774 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
775 BidiIterator origin(position);
776 while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
780 count = (unsigned)::boost::re_detail::distance(origin, position);
784 while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
796 if((rep->leading) && (count < rep->max))
798 // push backtrack info if available:
800 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
801 // jump to next state:
807 // non-greedy, push state and return true if we can skip:
809 push_single_repeat(count, rep, position, saved_state_rep_short_set);
811 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
821 template <class BidiIterator, class Allocator, class traits>
822 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
825 #pragma warning(push)
826 #pragma warning(disable:4127)
829 #pragma option push -w-8008 -w-8066 -w-8004
831 typedef typename traits::char_class_type mask_type;
832 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
833 const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate->next.p);
834 std::size_t count = 0;
836 // start by working out how much we can skip:
838 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
839 std::size_t desired = greedy ? rep->max : rep->min;
840 if(::boost::is_random_access_iterator<BidiIterator>::value)
842 BidiIterator end = position;
843 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
844 BidiIterator origin(position);
845 while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
849 count = (unsigned)::boost::re_detail::distance(origin, position);
853 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
865 if((rep->leading) && (count < rep->max))
867 // push backtrack info if available:
869 push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
870 // jump to next state:
876 // non-greedy, push state and return true if we can skip:
878 push_single_repeat(count, rep, position, saved_state_rep_long_set);
880 return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
890 template <class BidiIterator, class Allocator, class traits>
891 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
893 BOOST_ASSERT(pstate->type == syntax_element_recurse);
895 // Backup call stack:
897 push_recursion_pop();
899 // Set new call stack:
901 if(recursion_stack_position >= static_cast<int>(sizeof(recursion_stack)/sizeof(recursion_stack[0])))
905 recursion_stack[recursion_stack_position].preturn_address = pstate->next.p;
906 recursion_stack[recursion_stack_position].results = *m_presult;
907 if(static_cast<const re_recurse*>(pstate)->state_id > 0)
909 push_repeater_count(static_cast<const re_recurse*>(pstate)->state_id, &next_count);
911 pstate = static_cast<const re_jump*>(pstate)->alt.p;
912 recursion_stack[recursion_stack_position].id = static_cast<const re_brace*>(pstate)->index;
913 ++recursion_stack_position;
914 //BOOST_ASSERT(recursion_stack[recursion_stack_position-1].id);
919 template <class BidiIterator, class Allocator, class traits>
920 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
922 int index = static_cast<const re_brace*>(pstate)->index;
923 icase = static_cast<const re_brace*>(pstate)->icase;
926 if((m_match_flags & match_nosubs) == 0)
928 m_presult->set_second(position, index);
930 if(recursion_stack_position)
932 if(index == recursion_stack[recursion_stack_position-1].id)
934 --recursion_stack_position;
935 pstate = recursion_stack[recursion_stack_position].preturn_address;
936 *m_presult = recursion_stack[recursion_stack_position].results;
937 push_recursion(recursion_stack[recursion_stack_position].id, recursion_stack[recursion_stack_position].preturn_address, &recursion_stack[recursion_stack_position].results);
941 else if((index < 0) && (index != -4))
943 // matched forward lookahead:
947 pstate = pstate->next.p;
951 template <class BidiIterator, class Allocator, class traits>
952 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
954 if(recursion_stack_position)
956 BOOST_ASSERT(0 == recursion_stack[recursion_stack_position-1].id);
957 --recursion_stack_position;
958 pstate = recursion_stack[recursion_stack_position].preturn_address;
959 *m_presult = recursion_stack[recursion_stack_position].results;
960 push_recursion(recursion_stack[recursion_stack_position].id, recursion_stack[recursion_stack_position].preturn_address, &recursion_stack[recursion_stack_position].results);
963 if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
965 if((m_match_flags & match_all) && (position != last))
967 if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
969 m_presult->set_second(position);
971 m_has_found_match = true;
972 if((m_match_flags & match_posix) == match_posix)
974 m_result.maybe_assign(*m_presult);
975 if((m_match_flags & match_any) == 0)
978 #ifdef BOOST_REGEX_MATCH_EXTRA
979 if(match_extra & m_match_flags)
981 for(unsigned i = 0; i < m_presult->size(); ++i)
982 if((*m_presult)[i].matched)
983 ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
989 /****************************************************************************
991 Unwind and associated proceedures follow, these perform what normal stack
992 unwinding does in the recursive implementation.
994 ****************************************************************************/
996 template <class BidiIterator, class Allocator, class traits>
997 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
999 static unwind_proc_type const s_unwind_table[18] =
1001 &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
1002 &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
1003 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
1004 &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
1005 &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
1006 &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
1007 &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
1008 &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
1009 &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
1010 &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
1011 &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
1012 &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
1013 &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
1014 &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
1015 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion,
1016 &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop,
1019 m_recursive_result = have_match;
1020 unwind_proc_type unwinder;
1023 // keep unwinding our stack until we have something to do:
1027 unwinder = s_unwind_table[m_backup_state->state_id];
1028 cont = (this->*unwinder)(m_recursive_result);
1031 // return true if we have more states to try:
1033 return pstate ? true : false;
1036 template <class BidiIterator, class Allocator, class traits>
1037 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
1039 pstate = 0; // nothing left to search
1040 return false; // end of stack nothing more to search
1043 template <class BidiIterator, class Allocator, class traits>
1044 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
1046 saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
1047 // restore previous values if no match was found:
1048 if(have_match == false)
1050 m_presult->set_first(pmp->sub.first, pmp->index, pmp->index == 0);
1051 m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched, pmp->index == 0);
1053 #ifdef BOOST_REGEX_MATCH_EXTRA
1055 // we have a match, push the capture information onto the stack:
1057 else if(pmp->sub.matched && (match_extra & m_match_flags))
1058 ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
1061 m_backup_state = pmp+1;
1062 boost::re_detail::inplace_destroy(pmp);
1063 return true; // keep looking
1066 template <class BidiIterator, class Allocator, class traits>
1067 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
1069 boost::re_detail::inplace_destroy(m_backup_state++);
1070 pstate = 0; // nothing left to search
1071 return false; // end of stack nothing more to search
1074 template <class BidiIterator, class Allocator, class traits>
1075 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
1077 saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
1078 pstate = pmp->pstate;
1079 position = pmp->position;
1080 bool result = (r == pmp->positive);
1081 m_recursive_result = pmp->positive ? r : !r;
1082 boost::re_detail::inplace_destroy(pmp++);
1083 m_backup_state = pmp;
1084 return !result; // return false if the assertion was matched to stop search.
1087 template <class BidiIterator, class Allocator, class traits>
1088 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
1090 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1093 pstate = pmp->pstate;
1094 position = pmp->position;
1096 boost::re_detail::inplace_destroy(pmp++);
1097 m_backup_state = pmp;
1101 template <class BidiIterator, class Allocator, class traits>
1102 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
1104 saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
1105 boost::re_detail::inplace_destroy(pmp++);
1106 m_backup_state = pmp;
1107 return true; // keep looking
1110 template <class BidiIterator, class Allocator, class traits>
1111 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
1113 saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
1114 void* condemmed = m_stack_base;
1115 m_stack_base = pmp->base;
1116 m_backup_state = pmp->end;
1117 boost::re_detail::inplace_destroy(pmp);
1118 put_mem_block(condemmed);
1119 return true; // keep looking
1122 template <class BidiIterator, class Allocator, class traits>
1123 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
1125 saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1126 boost::re_detail::inplace_destroy(p++);
1130 template <class BidiIterator, class Allocator, class traits>
1131 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
1133 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1135 // if we have a match, just discard this state:
1138 destroy_single_repeat();
1142 const re_repeat* rep = pmp->rep;
1143 std::size_t count = pmp->count;
1144 BOOST_ASSERT(rep->next.p != 0);
1145 BOOST_ASSERT(rep->alt.p != 0);
1149 if((m_match_flags & match_partial) && (position == last))
1150 m_has_partial_match = true;
1152 BOOST_ASSERT(count);
1153 position = pmp->last_position;
1155 // backtrack till we can skip out:
1161 }while(count && !can_start(*position, rep->_map, mask_skip));
1163 // if we've hit base, destroy this state:
1166 destroy_single_repeat();
1167 if(!can_start(*position, rep->_map, mask_skip))
1172 pmp->count = count + rep->min;
1173 pmp->last_position = position;
1175 pstate = rep->alt.p;
1179 template <class BidiIterator, class Allocator, class traits>
1180 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1182 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1184 // if we have a match, just discard this state:
1187 destroy_single_repeat();
1191 const re_repeat* rep = pmp->rep;
1192 std::size_t count = pmp->count;
1193 BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1194 BOOST_ASSERT(rep->next.p != 0);
1195 BOOST_ASSERT(rep->alt.p != 0);
1196 BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1198 BOOST_ASSERT(count < rep->max);
1199 pstate = rep->next.p;
1200 position = pmp->last_position;
1202 if(position != last)
1204 // wind forward until we can skip out of the repeat:
1209 // failed repeat match, discard this state and look for another:
1210 destroy_single_repeat();
1215 pstate = rep->next.p;
1216 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1218 if(position == last)
1220 // can't repeat any more, remove the pushed state:
1221 destroy_single_repeat();
1222 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1223 m_has_partial_match = true;
1224 if(0 == (rep->can_be_null & mask_skip))
1227 else if(count == rep->max)
1229 // can't repeat any more, remove the pushed state:
1230 destroy_single_repeat();
1231 if(!can_start(*position, rep->_map, mask_skip))
1237 pmp->last_position = position;
1239 pstate = rep->alt.p;
1243 template <class BidiIterator, class Allocator, class traits>
1244 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1246 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1248 // if we have a match, just discard this state:
1251 destroy_single_repeat();
1255 const re_repeat* rep = pmp->rep;
1256 std::size_t count = pmp->count;
1258 BOOST_ASSERT(count < rep->max);
1259 position = pmp->last_position;
1260 if(position != last)
1263 // wind forward until we can skip out of the repeat:
1269 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1272 if(position == last)
1274 // can't repeat any more, remove the pushed state:
1275 destroy_single_repeat();
1276 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1277 m_has_partial_match = true;
1278 if(0 == (rep->can_be_null & mask_skip))
1281 else if(count == rep->max)
1283 // can't repeat any more, remove the pushed state:
1284 destroy_single_repeat();
1285 if(!can_start(*position, rep->_map, mask_skip))
1291 pmp->last_position = position;
1293 pstate = rep->alt.p;
1297 template <class BidiIterator, class Allocator, class traits>
1298 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1300 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1302 // if we have a match, just discard this state:
1305 destroy_single_repeat();
1309 const re_repeat* rep = pmp->rep;
1310 std::size_t count = pmp->count;
1311 pstate = rep->next.p;
1312 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1313 position = pmp->last_position;
1315 BOOST_ASSERT(rep->type == syntax_element_char_rep);
1316 BOOST_ASSERT(rep->next.p != 0);
1317 BOOST_ASSERT(rep->alt.p != 0);
1318 BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1319 BOOST_ASSERT(count < rep->max);
1321 if(position != last)
1323 // wind forward until we can skip out of the repeat:
1326 if(traits_inst.translate(*position, icase) != what)
1328 // failed repeat match, discard this state and look for another:
1329 destroy_single_repeat();
1335 pstate = rep->next.p;
1336 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1338 // remember where we got to if this is a leading repeat:
1339 if((rep->leading) && (count < rep->max))
1341 if(position == last)
1343 // can't repeat any more, remove the pushed state:
1344 destroy_single_repeat();
1345 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1346 m_has_partial_match = true;
1347 if(0 == (rep->can_be_null & mask_skip))
1350 else if(count == rep->max)
1352 // can't repeat any more, remove the pushed state:
1353 destroy_single_repeat();
1354 if(!can_start(*position, rep->_map, mask_skip))
1360 pmp->last_position = position;
1362 pstate = rep->alt.p;
1366 template <class BidiIterator, class Allocator, class traits>
1367 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1369 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1371 // if we have a match, just discard this state:
1374 destroy_single_repeat();
1378 const re_repeat* rep = pmp->rep;
1379 std::size_t count = pmp->count;
1380 pstate = rep->next.p;
1381 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1382 position = pmp->last_position;
1384 BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1385 BOOST_ASSERT(rep->next.p != 0);
1386 BOOST_ASSERT(rep->alt.p != 0);
1387 BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1388 BOOST_ASSERT(count < rep->max);
1390 if(position != last)
1392 // wind forward until we can skip out of the repeat:
1395 if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1397 // failed repeat match, discard this state and look for another:
1398 destroy_single_repeat();
1404 pstate = rep->next.p;
1405 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1407 // remember where we got to if this is a leading repeat:
1408 if((rep->leading) && (count < rep->max))
1410 if(position == last)
1412 // can't repeat any more, remove the pushed state:
1413 destroy_single_repeat();
1414 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1415 m_has_partial_match = true;
1416 if(0 == (rep->can_be_null & mask_skip))
1419 else if(count == rep->max)
1421 // can't repeat any more, remove the pushed state:
1422 destroy_single_repeat();
1423 if(!can_start(*position, rep->_map, mask_skip))
1429 pmp->last_position = position;
1431 pstate = rep->alt.p;
1435 template <class BidiIterator, class Allocator, class traits>
1436 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1438 typedef typename traits::char_class_type mask_type;
1439 saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1441 // if we have a match, just discard this state:
1444 destroy_single_repeat();
1448 const re_repeat* rep = pmp->rep;
1449 std::size_t count = pmp->count;
1450 pstate = rep->next.p;
1451 const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate);
1452 position = pmp->last_position;
1454 BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1455 BOOST_ASSERT(rep->next.p != 0);
1456 BOOST_ASSERT(rep->alt.p != 0);
1457 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1458 BOOST_ASSERT(count < rep->max);
1460 if(position != last)
1462 // wind forward until we can skip out of the repeat:
1465 if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1467 // failed repeat match, discard this state and look for another:
1468 destroy_single_repeat();
1474 pstate = rep->next.p;
1475 }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1477 // remember where we got to if this is a leading repeat:
1478 if((rep->leading) && (count < rep->max))
1480 if(position == last)
1482 // can't repeat any more, remove the pushed state:
1483 destroy_single_repeat();
1484 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1485 m_has_partial_match = true;
1486 if(0 == (rep->can_be_null & mask_skip))
1489 else if(count == rep->max)
1491 // can't repeat any more, remove the pushed state:
1492 destroy_single_repeat();
1493 if(!can_start(*position, rep->_map, mask_skip))
1499 pmp->last_position = position;
1501 pstate = rep->alt.p;
1505 template <class BidiIterator, class Allocator, class traits>
1506 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1508 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1511 position = pmp->position;
1512 pstate = pmp->pstate;
1515 boost::re_detail::inplace_destroy(pmp++);
1516 m_backup_state = pmp;
1520 template <class BidiIterator, class Allocator, class traits>
1521 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion(bool r)
1523 saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
1526 recursion_stack[recursion_stack_position].id = pmp->recursion_id;
1527 recursion_stack[recursion_stack_position].preturn_address = pmp->preturn_address;
1528 recursion_stack[recursion_stack_position].results = pmp->results;
1529 ++recursion_stack_position;
1531 boost::re_detail::inplace_destroy(pmp++);
1532 m_backup_state = pmp;
1536 template <class BidiIterator, class Allocator, class traits>
1537 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop(bool r)
1539 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1542 --recursion_stack_position;
1544 boost::re_detail::inplace_destroy(pmp++);
1545 m_backup_state = pmp;
1549 template <class BidiIterator, class Allocator, class traits>
1550 void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_pop()
1552 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1554 if(pmp < m_stack_base)
1557 pmp = static_cast<saved_state*>(m_backup_state);
1560 (void) new (pmp)saved_state(15);
1561 m_backup_state = pmp;
1564 template <class BidiIterator, class Allocator, class traits>
1565 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_pop(bool r)
1567 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1570 --parenthesis_stack_position;
1572 boost::re_detail::inplace_destroy(pmp++);
1573 m_backup_state = pmp;
1577 template <class BidiIterator, class Allocator, class traits>
1578 void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_pop()
1580 saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1582 if(pmp < m_stack_base)
1585 pmp = static_cast<saved_state*>(m_backup_state);
1588 (void) new (pmp)saved_state(16);
1589 m_backup_state = pmp;
1592 template <class BidiIterator, class Allocator, class traits>
1593 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_push(bool r)
1595 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1598 parenthesis_stack[parenthesis_stack_position++] = pmp->position;
1600 boost::re_detail::inplace_destroy(pmp++);
1601 m_backup_state = pmp;
1605 template <class BidiIterator, class Allocator, class traits>
1606 inline void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_push(BidiIterator p)
1608 saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1610 if(pmp < m_stack_base)
1613 pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1616 (void) new (pmp)saved_position<BidiIterator>(0, p, 17);
1617 m_backup_state = pmp;
1620 } // namespace re_detail
1621 } // namespace boost
1624 # pragma warning(pop)
1628 #pragma warning(push)
1629 #pragma warning(disable: 4103)
1631 #ifdef BOOST_HAS_ABI_HEADERS
1632 # include BOOST_ABI_SUFFIX
1635 #pragma warning(pop)